1// Copyright (c) 2018 Google LLC.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef SOURCE_OPT_LOOP_DEPENDENCE_H_
16#define SOURCE_OPT_LOOP_DEPENDENCE_H_
17
18#include <algorithm>
19#include <cstdint>
20#include <list>
21#include <map>
22#include <memory>
23#include <ostream>
24#include <set>
25#include <string>
26#include <utility>
27#include <vector>
28
29#include "source/opt/instruction.h"
30#include "source/opt/ir_context.h"
31#include "source/opt/loop_descriptor.h"
32#include "source/opt/scalar_analysis.h"
33
34namespace spvtools {
35namespace opt {
36
37// Stores information about dependence between a load and a store wrt a single
38// loop in a loop nest.
39// DependenceInformation
40// * UNKNOWN if no dependence information can be gathered or is gathered
41// for it.
42// * DIRECTION if a dependence direction could be found, but not a
43// distance.
44// * DISTANCE if a dependence distance could be found.
45// * PEEL if peeling either the first or last iteration will break
46// dependence between the given load and store.
47// * IRRELEVANT if it has no effect on the dependence between the given
48// load and store.
49//
50// If peel_first == true, the analysis has found that peeling the first
51// iteration of this loop will break dependence.
52//
53// If peel_last == true, the analysis has found that peeling the last iteration
54// of this loop will break dependence.
55class DistanceEntry {
56 public:
57 enum DependenceInformation {
58 UNKNOWN = 0,
59 DIRECTION = 1,
60 DISTANCE = 2,
61 PEEL = 3,
62 IRRELEVANT = 4,
63 POINT = 5
64 };
65 enum Directions {
66 NONE = 0,
67 LT = 1,
68 EQ = 2,
69 LE = 3,
70 GT = 4,
71 NE = 5,
72 GE = 6,
73 ALL = 7
74 };
75 DependenceInformation dependence_information;
76 Directions direction;
77 int64_t distance;
78 bool peel_first;
79 bool peel_last;
80 int64_t point_x;
81 int64_t point_y;
82
83 DistanceEntry()
84 : dependence_information(DependenceInformation::UNKNOWN),
85 direction(Directions::ALL),
86 distance(0),
87 peel_first(false),
88 peel_last(false),
89 point_x(0),
90 point_y(0) {}
91
92 explicit DistanceEntry(Directions direction_)
93 : dependence_information(DependenceInformation::DIRECTION),
94 direction(direction_),
95 distance(0),
96 peel_first(false),
97 peel_last(false),
98 point_x(0),
99 point_y(0) {}
100
101 DistanceEntry(Directions direction_, int64_t distance_)
102 : dependence_information(DependenceInformation::DISTANCE),
103 direction(direction_),
104 distance(distance_),
105 peel_first(false),
106 peel_last(false),
107 point_x(0),
108 point_y(0) {}
109
110 DistanceEntry(int64_t x, int64_t y)
111 : dependence_information(DependenceInformation::POINT),
112 direction(Directions::ALL),
113 distance(0),
114 peel_first(false),
115 peel_last(false),
116 point_x(x),
117 point_y(y) {}
118
119 bool operator==(const DistanceEntry& rhs) const {
120 return direction == rhs.direction && peel_first == rhs.peel_first &&
121 peel_last == rhs.peel_last && distance == rhs.distance &&
122 point_x == rhs.point_x && point_y == rhs.point_y;
123 }
124
125 bool operator!=(const DistanceEntry& rhs) const { return !(*this == rhs); }
126};
127
128// Stores a vector of DistanceEntrys, one per loop in the analysis.
129// A DistanceVector holds all of the information gathered in a dependence
130// analysis wrt the loops stored in the LoopDependenceAnalysis performing the
131// analysis.
132class DistanceVector {
133 public:
134 explicit DistanceVector(size_t size) : entries(size, DistanceEntry{}) {}
135
136 explicit DistanceVector(std::vector<DistanceEntry> entries_)
137 : entries(entries_) {}
138
139 DistanceEntry& GetEntry(size_t index) { return entries[index]; }
140 const DistanceEntry& GetEntry(size_t index) const { return entries[index]; }
141
142 std::vector<DistanceEntry>& GetEntries() { return entries; }
143 const std::vector<DistanceEntry>& GetEntries() const { return entries; }
144
145 bool operator==(const DistanceVector& rhs) const {
146 if (entries.size() != rhs.entries.size()) {
147 return false;
148 }
149 for (size_t i = 0; i < entries.size(); ++i) {
150 if (entries[i] != rhs.entries[i]) {
151 return false;
152 }
153 }
154 return true;
155 }
156 bool operator!=(const DistanceVector& rhs) const { return !(*this == rhs); }
157
158 private:
159 std::vector<DistanceEntry> entries;
160};
161
162class DependenceLine;
163class DependenceDistance;
164class DependencePoint;
165class DependenceNone;
166class DependenceEmpty;
167
168class Constraint {
169 public:
170 explicit Constraint(const Loop* loop) : loop_(loop) {}
171 enum ConstraintType { Line, Distance, Point, None, Empty };
172
173 virtual ConstraintType GetType() const = 0;
174
175 virtual ~Constraint() {}
176
177 // Get the loop this constraint belongs to.
178 const Loop* GetLoop() const { return loop_; }
179
180 bool operator==(const Constraint& other) const;
181
182 bool operator!=(const Constraint& other) const;
183
184// clang-format off
185#define DeclareCastMethod(target) \
186 virtual target* As##target() { return nullptr; } \
187 virtual const target* As##target() const { return nullptr; }
188 DeclareCastMethod(DependenceLine)
189 DeclareCastMethod(DependenceDistance)
190 DeclareCastMethod(DependencePoint)
191 DeclareCastMethod(DependenceNone)
192 DeclareCastMethod(DependenceEmpty)
193#undef DeclareCastMethod
194
195 protected:
196 const Loop* loop_;
197};
198// clang-format on
199
200class DependenceLine : public Constraint {
201 public:
202 DependenceLine(SENode* a, SENode* b, SENode* c, const Loop* loop)
203 : Constraint(loop), a_(a), b_(b), c_(c) {}
204
205 ConstraintType GetType() const final { return Line; }
206
207 DependenceLine* AsDependenceLine() final { return this; }
208 const DependenceLine* AsDependenceLine() const final { return this; }
209
210 SENode* GetA() const { return a_; }
211 SENode* GetB() const { return b_; }
212 SENode* GetC() const { return c_; }
213
214 private:
215 SENode* a_;
216 SENode* b_;
217 SENode* c_;
218};
219
220class DependenceDistance : public Constraint {
221 public:
222 DependenceDistance(SENode* distance, const Loop* loop)
223 : Constraint(loop), distance_(distance) {}
224
225 ConstraintType GetType() const final { return Distance; }
226
227 DependenceDistance* AsDependenceDistance() final { return this; }
228 const DependenceDistance* AsDependenceDistance() const final { return this; }
229
230 SENode* GetDistance() const { return distance_; }
231
232 private:
233 SENode* distance_;
234};
235
236class DependencePoint : public Constraint {
237 public:
238 DependencePoint(SENode* source, SENode* destination, const Loop* loop)
239 : Constraint(loop), source_(source), destination_(destination) {}
240
241 ConstraintType GetType() const final { return Point; }
242
243 DependencePoint* AsDependencePoint() final { return this; }
244 const DependencePoint* AsDependencePoint() const final { return this; }
245
246 SENode* GetSource() const { return source_; }
247 SENode* GetDestination() const { return destination_; }
248
249 private:
250 SENode* source_;
251 SENode* destination_;
252};
253
254class DependenceNone : public Constraint {
255 public:
256 DependenceNone() : Constraint(nullptr) {}
257 ConstraintType GetType() const final { return None; }
258
259 DependenceNone* AsDependenceNone() final { return this; }
260 const DependenceNone* AsDependenceNone() const final { return this; }
261};
262
263class DependenceEmpty : public Constraint {
264 public:
265 DependenceEmpty() : Constraint(nullptr) {}
266 ConstraintType GetType() const final { return Empty; }
267
268 DependenceEmpty* AsDependenceEmpty() final { return this; }
269 const DependenceEmpty* AsDependenceEmpty() const final { return this; }
270};
271
272// Provides dependence information between a store instruction and a load
273// instruction inside the same loop in a loop nest.
274//
275// The analysis can only check dependence between stores and loads with regard
276// to the loop nest it is created with.
277//
278// The analysis can output debugging information to a stream. The output
279// describes the control flow of the analysis and what information it can deduce
280// at each step.
281// SetDebugStream and ClearDebugStream are provided for this functionality.
282//
283// The dependency algorithm is based on the 1990 Paper
284// Practical Dependence Testing
285// Gina Goff, Ken Kennedy, Chau-Wen Tseng
286//
287// The algorithm first identifies subscript pairs between the load and store.
288// Each pair is tested until all have been tested or independence is found.
289// The number of induction variables in a pair determines which test to perform
290// on it;
291// Zero Index Variable (ZIV) is used when no induction variables are present
292// in the pair.
293// Single Index Variable (SIV) is used when only one induction variable is
294// present, but may occur multiple times in the pair.
295// Multiple Index Variable (MIV) is used when more than one induction variable
296// is present in the pair.
297class LoopDependenceAnalysis {
298 public:
299 LoopDependenceAnalysis(IRContext* context, std::vector<const Loop*> loops)
300 : context_(context),
301 loops_(loops),
302 scalar_evolution_(context),
303 debug_stream_(nullptr),
304 constraints_{} {}
305
306 // Finds the dependence between |source| and |destination|.
307 // |source| should be an OpLoad.
308 // |destination| should be an OpStore.
309 // Any direction and distance information found will be stored in
310 // |distance_vector|.
311 // Returns true if independence is found, false otherwise.
312 bool GetDependence(const Instruction* source, const Instruction* destination,
313 DistanceVector* distance_vector);
314
315 // Returns true if |subscript_pair| represents a Zero Index Variable pair
316 // (ZIV)
317 bool IsZIV(const std::pair<SENode*, SENode*>& subscript_pair);
318
319 // Returns true if |subscript_pair| represents a Single Index Variable
320 // (SIV) pair
321 bool IsSIV(const std::pair<SENode*, SENode*>& subscript_pair);
322
323 // Returns true if |subscript_pair| represents a Multiple Index Variable
324 // (MIV) pair
325 bool IsMIV(const std::pair<SENode*, SENode*>& subscript_pair);
326
327 // Finds the lower bound of |loop| as an SENode* and returns the result.
328 // The lower bound is the starting value of the loops induction variable
329 SENode* GetLowerBound(const Loop* loop);
330
331 // Finds the upper bound of |loop| as an SENode* and returns the result.
332 // The upper bound is the last value before the loop exit condition is met.
333 SENode* GetUpperBound(const Loop* loop);
334
335 // Returns true if |value| is between |bound_one| and |bound_two| (inclusive).
336 bool IsWithinBounds(int64_t value, int64_t bound_one, int64_t bound_two);
337
338 // Finds the bounds of |loop| as upper_bound - lower_bound and returns the
339 // resulting SENode.
340 // If the operations can not be completed a nullptr is returned.
341 SENode* GetTripCount(const Loop* loop);
342
343 // Returns the SENode* produced by building an SENode from the result of
344 // calling GetInductionInitValue on |loop|.
345 // If the operation can not be completed a nullptr is returned.
346 SENode* GetFirstTripInductionNode(const Loop* loop);
347
348 // Returns the SENode* produced by building an SENode from the result of
349 // GetFirstTripInductionNode + (GetTripCount - 1) * induction_coefficient.
350 // If the operation can not be completed a nullptr is returned.
351 SENode* GetFinalTripInductionNode(const Loop* loop,
352 SENode* induction_coefficient);
353
354 // Returns all the distinct loops that appear in |nodes|.
355 std::set<const Loop*> CollectLoops(
356 const std::vector<SERecurrentNode*>& nodes);
357
358 // Returns all the distinct loops that appear in |source| and |destination|.
359 std::set<const Loop*> CollectLoops(SENode* source, SENode* destination);
360
361 // Returns true if |distance| is provably outside the loop bounds.
362 // |coefficient| must be an SENode representing the coefficient of the
363 // induction variable of |loop|.
364 // This method is able to handle some symbolic cases which IsWithinBounds
365 // can't handle.
366 bool IsProvablyOutsideOfLoopBounds(const Loop* loop, SENode* distance,
367 SENode* coefficient);
368
369 // Sets the ostream for debug information for the analysis.
370 void SetDebugStream(std::ostream& debug_stream) {
371 debug_stream_ = &debug_stream;
372 }
373
374 // Clears the stored ostream to stop debug information printing.
375 void ClearDebugStream() { debug_stream_ = nullptr; }
376
377 // Returns the ScalarEvolutionAnalysis used by this analysis.
378 ScalarEvolutionAnalysis* GetScalarEvolution() { return &scalar_evolution_; }
379
380 // Creates a new constraint of type |T| and returns the pointer to it.
381 template <typename T, typename... Args>
382 Constraint* make_constraint(Args&&... args) {
383 constraints_.push_back(
384 std::unique_ptr<Constraint>(new T(std::forward<Args>(args)...)));
385
386 return constraints_.back().get();
387 }
388
389 // Subscript partitioning as described in Figure 1 of 'Practical Dependence
390 // Testing' by Gina Goff, Ken Kennedy, and Chau-Wen Tseng from PLDI '91.
391 // Partitions the subscripts into independent subscripts and minimally coupled
392 // sets of subscripts.
393 // Returns the partitioning of subscript pairs. Sets of size 1 indicates an
394 // independent subscript-pair and others indicate coupled sets.
395 using PartitionedSubscripts =
396 std::vector<std::set<std::pair<Instruction*, Instruction*>>>;
397 PartitionedSubscripts PartitionSubscripts(
398 const std::vector<Instruction*>& source_subscripts,
399 const std::vector<Instruction*>& destination_subscripts);
400
401 // Returns the Loop* matching the loop for |subscript_pair|.
402 // |subscript_pair| must be an SIV pair.
403 const Loop* GetLoopForSubscriptPair(
404 const std::pair<SENode*, SENode*>& subscript_pair);
405
406 // Returns the DistanceEntry matching the loop for |subscript_pair|.
407 // |subscript_pair| must be an SIV pair.
408 DistanceEntry* GetDistanceEntryForSubscriptPair(
409 const std::pair<SENode*, SENode*>& subscript_pair,
410 DistanceVector* distance_vector);
411
412 // Returns the DistanceEntry matching |loop|.
413 DistanceEntry* GetDistanceEntryForLoop(const Loop* loop,
414 DistanceVector* distance_vector);
415
416 // Returns a vector of Instruction* which form the subscripts of the array
417 // access defined by the access chain |instruction|.
418 std::vector<Instruction*> GetSubscripts(const Instruction* instruction);
419
420 // Delta test as described in Figure 3 of 'Practical Dependence
421 // Testing' by Gina Goff, Ken Kennedy, and Chau-Wen Tseng from PLDI '91.
422 bool DeltaTest(
423 const std::vector<std::pair<SENode*, SENode*>>& coupled_subscripts,
424 DistanceVector* dv_entry);
425
426 // Constraint propagation as described in Figure 5 of 'Practical Dependence
427 // Testing' by Gina Goff, Ken Kennedy, and Chau-Wen Tseng from PLDI '91.
428 std::pair<SENode*, SENode*> PropagateConstraints(
429 const std::pair<SENode*, SENode*>& subscript_pair,
430 const std::vector<Constraint*>& constraints);
431
432 // Constraint intersection as described in Figure 4 of 'Practical Dependence
433 // Testing' by Gina Goff, Ken Kennedy, and Chau-Wen Tseng from PLDI '91.
434 Constraint* IntersectConstraints(Constraint* constraint_0,
435 Constraint* constraint_1,
436 const SENode* lower_bound,
437 const SENode* upper_bound);
438
439 // Returns true if each loop in |loops| is in a form supported by this
440 // analysis.
441 // A loop is supported if it has a single induction variable and that
442 // induction variable has a step of +1 or -1 per loop iteration.
443 bool CheckSupportedLoops(std::vector<const Loop*> loops);
444
445 // Returns true if |loop| is in a form supported by this analysis.
446 // A loop is supported if it has a single induction variable and that
447 // induction variable has a step of +1 or -1 per loop iteration.
448 bool IsSupportedLoop(const Loop* loop);
449
450 private:
451 IRContext* context_;
452
453 // The loop nest we are analysing the dependence of.
454 std::vector<const Loop*> loops_;
455
456 // The ScalarEvolutionAnalysis used by this analysis to store and perform much
457 // of its logic.
458 ScalarEvolutionAnalysis scalar_evolution_;
459
460 // The ostream debug information for the analysis to print to.
461 std::ostream* debug_stream_;
462
463 // Stores all the constraints created by the analysis.
464 std::list<std::unique_ptr<Constraint>> constraints_;
465
466 // Returns true if independence can be proven and false if it can't be proven.
467 bool ZIVTest(const std::pair<SENode*, SENode*>& subscript_pair);
468
469 // Analyzes the subscript pair to find an applicable SIV test.
470 // Returns true if independence can be proven and false if it can't be proven.
471 bool SIVTest(const std::pair<SENode*, SENode*>& subscript_pair,
472 DistanceVector* distance_vector);
473
474 // Takes the form a*i + c1, a*i + c2
475 // When c1 and c2 are loop invariant and a is constant
476 // distance = (c1 - c2)/a
477 // < if distance > 0
478 // direction = = if distance = 0
479 // > if distance < 0
480 // Returns true if independence is proven and false if it can't be proven.
481 bool StrongSIVTest(SENode* source, SENode* destination, SENode* coeff,
482 DistanceEntry* distance_entry);
483
484 // Takes for form a*i + c1, a*i + c2
485 // where c1 and c2 are loop invariant and a is constant.
486 // c1 and/or c2 contain one or more SEValueUnknown nodes.
487 bool SymbolicStrongSIVTest(SENode* source, SENode* destination,
488 SENode* coefficient,
489 DistanceEntry* distance_entry);
490
491 // Takes the form a1*i + c1, a2*i + c2
492 // where a1 = 0
493 // distance = (c1 - c2) / a2
494 // Returns true if independence is proven and false if it can't be proven.
495 bool WeakZeroSourceSIVTest(SENode* source, SERecurrentNode* destination,
496 SENode* coefficient,
497 DistanceEntry* distance_entry);
498
499 // Takes the form a1*i + c1, a2*i + c2
500 // where a2 = 0
501 // distance = (c2 - c1) / a1
502 // Returns true if independence is proven and false if it can't be proven.
503 bool WeakZeroDestinationSIVTest(SERecurrentNode* source, SENode* destination,
504 SENode* coefficient,
505 DistanceEntry* distance_entry);
506
507 // Takes the form a1*i + c1, a2*i + c2
508 // where a1 = -a2
509 // distance = (c2 - c1) / 2*a1
510 // Returns true if independence is proven and false if it can't be proven.
511 bool WeakCrossingSIVTest(SENode* source, SENode* destination,
512 SENode* coefficient, DistanceEntry* distance_entry);
513
514 // Uses the def_use_mgr to get the instruction referenced by
515 // SingleWordInOperand(|id|) when called on |instruction|.
516 Instruction* GetOperandDefinition(const Instruction* instruction, int id);
517
518 // Perform the GCD test if both, the source and the destination nodes, are in
519 // the form a0*i0 + a1*i1 + ... an*in + c.
520 bool GCDMIVTest(const std::pair<SENode*, SENode*>& subscript_pair);
521
522 // Finds the number of induction variables in |node|.
523 // Returns -1 on failure.
524 int64_t CountInductionVariables(SENode* node);
525
526 // Finds the number of induction variables shared between |source| and
527 // |destination|.
528 // Returns -1 on failure.
529 int64_t CountInductionVariables(SENode* source, SENode* destination);
530
531 // Takes the offset from the induction variable and subtracts the lower bound
532 // from it to get the constant term added to the induction.
533 // Returns the resuting constant term, or nullptr if it could not be produced.
534 SENode* GetConstantTerm(const Loop* loop, SERecurrentNode* induction);
535
536 // Marks all the distance entries in |distance_vector| that were relate to
537 // loops in |loops_| but were not used in any subscripts as irrelevant to the
538 // to the dependence test.
539 void MarkUnsusedDistanceEntriesAsIrrelevant(const Instruction* source,
540 const Instruction* destination,
541 DistanceVector* distance_vector);
542
543 // Converts |value| to a std::string and returns the result.
544 // This is required because Android does not compile std::to_string.
545 template <typename valueT>
546 std::string ToString(valueT value) {
547 std::ostringstream string_stream;
548 string_stream << value;
549 return string_stream.str();
550 }
551
552 // Prints |debug_msg| and "\n" to the ostream pointed to by |debug_stream_|.
553 // Won't print anything if |debug_stream_| is nullptr.
554 void PrintDebug(std::string debug_msg);
555};
556
557} // namespace opt
558} // namespace spvtools
559
560#endif // SOURCE_OPT_LOOP_DEPENDENCE_H_
561