1 //===-- llvm/Analysis/DependenceAnalysis.h -------------------- -*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // DependenceAnalysis is an LLVM pass that analyses dependences between memory 10 // accesses. Currently, it is an implementation of the approach described in 11 // 12 // Practical Dependence Testing 13 // Goff, Kennedy, Tseng 14 // PLDI 1991 15 // 16 // There's a single entry point that analyzes the dependence between a pair 17 // of memory references in a function, returning either NULL, for no dependence, 18 // or a more-or-less detailed description of the dependence between them. 19 // 20 // This pass exists to support the DependenceGraph pass. There are two separate 21 // passes because there's a useful separation of concerns. A dependence exists 22 // if two conditions are met: 23 // 24 // 1) Two instructions reference the same memory location, and 25 // 2) There is a flow of control leading from one instruction to the other. 26 // 27 // DependenceAnalysis attacks the first condition; DependenceGraph will attack 28 // the second (it's not yet ready). 29 // 30 // Please note that this is work in progress and the interface is subject to 31 // change. 32 // 33 // Plausible changes: 34 // Return a set of more precise dependences instead of just one dependence 35 // summarizing all. 36 // 37 //===----------------------------------------------------------------------===// 38 39 #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 40 #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 41 42 #include "llvm/ADT/SmallBitVector.h" 43 #include "llvm/IR/Instructions.h" 44 #include "llvm/IR/PassManager.h" 45 #include "llvm/Pass.h" 46 47 namespace llvm { 48 class AAResults; 49 template <typename T> class ArrayRef; 50 class Loop; 51 class LoopInfo; 52 class ScalarEvolution; 53 class SCEV; 54 class SCEVConstant; 55 class raw_ostream; 56 57 /// Dependence - This class represents a dependence between two memory 58 /// memory references in a function. It contains minimal information and 59 /// is used in the very common situation where the compiler is unable to 60 /// determine anything beyond the existence of a dependence; that is, it 61 /// represents a confused dependence (see also FullDependence). In most 62 /// cases (for output, flow, and anti dependences), the dependence implies 63 /// an ordering, where the source must precede the destination; in contrast, 64 /// input dependences are unordered. 65 /// 66 /// When a dependence graph is built, each Dependence will be a member of 67 /// the set of predecessor edges for its destination instruction and a set 68 /// if successor edges for its source instruction. These sets are represented 69 /// as singly-linked lists, with the "next" fields stored in the dependence 70 /// itelf. 71 class Dependence { 72 protected: 73 Dependence(Dependence &&) = default; 74 Dependence &operator=(Dependence &&) = default; 75 76 public: 77 Dependence(Instruction *Source, Instruction *Destination) 78 : Src(Source), Dst(Destination) {} 79 virtual ~Dependence() = default; 80 81 /// Dependence::DVEntry - Each level in the distance/direction vector 82 /// has a direction (or perhaps a union of several directions), and 83 /// perhaps a distance. 84 struct DVEntry { 85 enum : unsigned char { 86 NONE = 0, 87 LT = 1, 88 EQ = 2, 89 LE = 3, 90 GT = 4, 91 NE = 5, 92 GE = 6, 93 ALL = 7 94 }; 95 unsigned char Direction : 3; // Init to ALL, then refine. 96 bool Scalar : 1; // Init to true. 97 bool PeelFirst : 1; // Peeling the first iteration will break dependence. 98 bool PeelLast : 1; // Peeling the last iteration will break the dependence. 99 bool Splitable : 1; // Splitting the loop will break dependence. 100 const SCEV *Distance = nullptr; // NULL implies no distance available. 101 DVEntry() 102 : Direction(ALL), Scalar(true), PeelFirst(false), PeelLast(false), 103 Splitable(false) {} 104 }; 105 106 /// getSrc - Returns the source instruction for this dependence. 107 /// 108 Instruction *getSrc() const { return Src; } 109 110 /// getDst - Returns the destination instruction for this dependence. 111 /// 112 Instruction *getDst() const { return Dst; } 113 114 /// isInput - Returns true if this is an input dependence. 115 /// 116 bool isInput() const; 117 118 /// isOutput - Returns true if this is an output dependence. 119 /// 120 bool isOutput() const; 121 122 /// isFlow - Returns true if this is a flow (aka true) dependence. 123 /// 124 bool isFlow() const; 125 126 /// isAnti - Returns true if this is an anti dependence. 127 /// 128 bool isAnti() const; 129 130 /// isOrdered - Returns true if dependence is Output, Flow, or Anti 131 /// 132 bool isOrdered() const { return isOutput() || isFlow() || isAnti(); } 133 134 /// isUnordered - Returns true if dependence is Input 135 /// 136 bool isUnordered() const { return isInput(); } 137 138 /// isLoopIndependent - Returns true if this is a loop-independent 139 /// dependence. 140 virtual bool isLoopIndependent() const { return true; } 141 142 /// isConfused - Returns true if this dependence is confused 143 /// (the compiler understands nothing and makes worst-case 144 /// assumptions). 145 virtual bool isConfused() const { return true; } 146 147 /// isConsistent - Returns true if this dependence is consistent 148 /// (occurs every time the source and destination are executed). 149 virtual bool isConsistent() const { return false; } 150 151 /// getLevels - Returns the number of common loops surrounding the 152 /// source and destination of the dependence. 153 virtual unsigned getLevels() const { return 0; } 154 155 /// getDirection - Returns the direction associated with a particular 156 /// level. 157 virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; } 158 159 /// getDistance - Returns the distance (or NULL) associated with a 160 /// particular level. 161 virtual const SCEV *getDistance(unsigned Level) const { return nullptr; } 162 163 /// Check if the direction vector is negative. A negative direction 164 /// vector means Src and Dst are reversed in the actual program. 165 virtual bool isDirectionNegative() const { return false; } 166 167 /// If the direction vector is negative, normalize the direction 168 /// vector to make it non-negative. Normalization is done by reversing 169 /// Src and Dst, plus reversing the dependence directions and distances 170 /// in the vector. 171 virtual bool normalize(ScalarEvolution *SE) { return false; } 172 173 /// isPeelFirst - Returns true if peeling the first iteration from 174 /// this loop will break this dependence. 175 virtual bool isPeelFirst(unsigned Level) const { return false; } 176 177 /// isPeelLast - Returns true if peeling the last iteration from 178 /// this loop will break this dependence. 179 virtual bool isPeelLast(unsigned Level) const { return false; } 180 181 /// isSplitable - Returns true if splitting this loop will break 182 /// the dependence. 183 virtual bool isSplitable(unsigned Level) const { return false; } 184 185 /// isScalar - Returns true if a particular level is scalar; that is, 186 /// if no subscript in the source or destination mention the induction 187 /// variable associated with the loop at this level. 188 virtual bool isScalar(unsigned Level) const; 189 190 /// getNextPredecessor - Returns the value of the NextPredecessor 191 /// field. 192 const Dependence *getNextPredecessor() const { return NextPredecessor; } 193 194 /// getNextSuccessor - Returns the value of the NextSuccessor 195 /// field. 196 const Dependence *getNextSuccessor() const { return NextSuccessor; } 197 198 /// setNextPredecessor - Sets the value of the NextPredecessor 199 /// field. 200 void setNextPredecessor(const Dependence *pred) { NextPredecessor = pred; } 201 202 /// setNextSuccessor - Sets the value of the NextSuccessor 203 /// field. 204 void setNextSuccessor(const Dependence *succ) { NextSuccessor = succ; } 205 206 /// dump - For debugging purposes, dumps a dependence to OS. 207 /// 208 void dump(raw_ostream &OS) const; 209 210 protected: 211 Instruction *Src, *Dst; 212 213 private: 214 const Dependence *NextPredecessor = nullptr, *NextSuccessor = nullptr; 215 friend class DependenceInfo; 216 }; 217 218 /// FullDependence - This class represents a dependence between two memory 219 /// references in a function. It contains detailed information about the 220 /// dependence (direction vectors, etc.) and is used when the compiler is 221 /// able to accurately analyze the interaction of the references; that is, 222 /// it is not a confused dependence (see Dependence). In most cases 223 /// (for output, flow, and anti dependences), the dependence implies an 224 /// ordering, where the source must precede the destination; in contrast, 225 /// input dependences are unordered. 226 class FullDependence final : public Dependence { 227 public: 228 FullDependence(Instruction *Src, Instruction *Dst, bool LoopIndependent, 229 unsigned Levels); 230 231 /// isLoopIndependent - Returns true if this is a loop-independent 232 /// dependence. 233 bool isLoopIndependent() const override { return LoopIndependent; } 234 235 /// isConfused - Returns true if this dependence is confused 236 /// (the compiler understands nothing and makes worst-case 237 /// assumptions). 238 bool isConfused() const override { return false; } 239 240 /// isConsistent - Returns true if this dependence is consistent 241 /// (occurs every time the source and destination are executed). 242 bool isConsistent() const override { return Consistent; } 243 244 /// getLevels - Returns the number of common loops surrounding the 245 /// source and destination of the dependence. 246 unsigned getLevels() const override { return Levels; } 247 248 /// getDirection - Returns the direction associated with a particular 249 /// level. 250 unsigned getDirection(unsigned Level) const override; 251 252 /// getDistance - Returns the distance (or NULL) associated with a 253 /// particular level. 254 const SCEV *getDistance(unsigned Level) const override; 255 256 /// Check if the direction vector is negative. A negative direction 257 /// vector means Src and Dst are reversed in the actual program. 258 bool isDirectionNegative() const override; 259 260 /// If the direction vector is negative, normalize the direction 261 /// vector to make it non-negative. Normalization is done by reversing 262 /// Src and Dst, plus reversing the dependence directions and distances 263 /// in the vector. 264 bool normalize(ScalarEvolution *SE) override; 265 266 /// isPeelFirst - Returns true if peeling the first iteration from 267 /// this loop will break this dependence. 268 bool isPeelFirst(unsigned Level) const override; 269 270 /// isPeelLast - Returns true if peeling the last iteration from 271 /// this loop will break this dependence. 272 bool isPeelLast(unsigned Level) const override; 273 274 /// isSplitable - Returns true if splitting the loop will break 275 /// the dependence. 276 bool isSplitable(unsigned Level) const override; 277 278 /// isScalar - Returns true if a particular level is scalar; that is, 279 /// if no subscript in the source or destination mention the induction 280 /// variable associated with the loop at this level. 281 bool isScalar(unsigned Level) const override; 282 283 private: 284 unsigned short Levels; 285 bool LoopIndependent; 286 bool Consistent; // Init to true, then refine. 287 std::unique_ptr<DVEntry[]> DV; 288 friend class DependenceInfo; 289 }; 290 291 /// DependenceInfo - This class is the main dependence-analysis driver. 292 /// 293 class DependenceInfo { 294 public: 295 DependenceInfo(Function *F, AAResults *AA, ScalarEvolution *SE, 296 LoopInfo *LI) 297 : AA(AA), SE(SE), LI(LI), F(F) {} 298 299 /// Handle transitive invalidation when the cached analysis results go away. 300 bool invalidate(Function &F, const PreservedAnalyses &PA, 301 FunctionAnalysisManager::Invalidator &Inv); 302 303 /// depends - Tests for a dependence between the Src and Dst instructions. 304 /// Returns NULL if no dependence; otherwise, returns a Dependence (or a 305 /// FullDependence) with as much information as can be gleaned. 306 /// The flag PossiblyLoopIndependent should be set by the caller 307 /// if it appears that control flow can reach from Src to Dst 308 /// without traversing a loop back edge. 309 std::unique_ptr<Dependence> depends(Instruction *Src, 310 Instruction *Dst, 311 bool PossiblyLoopIndependent); 312 313 /// getSplitIteration - Give a dependence that's splittable at some 314 /// particular level, return the iteration that should be used to split 315 /// the loop. 316 /// 317 /// Generally, the dependence analyzer will be used to build 318 /// a dependence graph for a function (basically a map from instructions 319 /// to dependences). Looking for cycles in the graph shows us loops 320 /// that cannot be trivially vectorized/parallelized. 321 /// 322 /// We can try to improve the situation by examining all the dependences 323 /// that make up the cycle, looking for ones we can break. 324 /// Sometimes, peeling the first or last iteration of a loop will break 325 /// dependences, and there are flags for those possibilities. 326 /// Sometimes, splitting a loop at some other iteration will do the trick, 327 /// and we've got a flag for that case. Rather than waste the space to 328 /// record the exact iteration (since we rarely know), we provide 329 /// a method that calculates the iteration. It's a drag that it must work 330 /// from scratch, but wonderful in that it's possible. 331 /// 332 /// Here's an example: 333 /// 334 /// for (i = 0; i < 10; i++) 335 /// A[i] = ... 336 /// ... = A[11 - i] 337 /// 338 /// There's a loop-carried flow dependence from the store to the load, 339 /// found by the weak-crossing SIV test. The dependence will have a flag, 340 /// indicating that the dependence can be broken by splitting the loop. 341 /// Calling getSplitIteration will return 5. 342 /// Splitting the loop breaks the dependence, like so: 343 /// 344 /// for (i = 0; i <= 5; i++) 345 /// A[i] = ... 346 /// ... = A[11 - i] 347 /// for (i = 6; i < 10; i++) 348 /// A[i] = ... 349 /// ... = A[11 - i] 350 /// 351 /// breaks the dependence and allows us to vectorize/parallelize 352 /// both loops. 353 const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level); 354 355 Function *getFunction() const { return F; } 356 357 private: 358 AAResults *AA; 359 ScalarEvolution *SE; 360 LoopInfo *LI; 361 Function *F; 362 363 /// Subscript - This private struct represents a pair of subscripts from 364 /// a pair of potentially multi-dimensional array references. We use a 365 /// vector of them to guide subscript partitioning. 366 struct Subscript { 367 const SCEV *Src; 368 const SCEV *Dst; 369 enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification; 370 SmallBitVector Loops; 371 SmallBitVector GroupLoops; 372 SmallBitVector Group; 373 }; 374 375 struct CoefficientInfo { 376 const SCEV *Coeff; 377 const SCEV *PosPart; 378 const SCEV *NegPart; 379 const SCEV *Iterations; 380 }; 381 382 struct BoundInfo { 383 const SCEV *Iterations; 384 const SCEV *Upper[8]; 385 const SCEV *Lower[8]; 386 unsigned char Direction; 387 unsigned char DirSet; 388 }; 389 390 /// Constraint - This private class represents a constraint, as defined 391 /// in the paper 392 /// 393 /// Practical Dependence Testing 394 /// Goff, Kennedy, Tseng 395 /// PLDI 1991 396 /// 397 /// There are 5 kinds of constraint, in a hierarchy. 398 /// 1) Any - indicates no constraint, any dependence is possible. 399 /// 2) Line - A line ax + by = c, where a, b, and c are parameters, 400 /// representing the dependence equation. 401 /// 3) Distance - The value d of the dependence distance; 402 /// 4) Point - A point <x, y> representing the dependence from 403 /// iteration x to iteration y. 404 /// 5) Empty - No dependence is possible. 405 class Constraint { 406 private: 407 enum ConstraintKind { Empty, Point, Distance, Line, Any } Kind; 408 ScalarEvolution *SE; 409 const SCEV *A; 410 const SCEV *B; 411 const SCEV *C; 412 const Loop *AssociatedLoop; 413 414 public: 415 /// isEmpty - Return true if the constraint is of kind Empty. 416 bool isEmpty() const { return Kind == Empty; } 417 418 /// isPoint - Return true if the constraint is of kind Point. 419 bool isPoint() const { return Kind == Point; } 420 421 /// isDistance - Return true if the constraint is of kind Distance. 422 bool isDistance() const { return Kind == Distance; } 423 424 /// isLine - Return true if the constraint is of kind Line. 425 /// Since Distance's can also be represented as Lines, we also return 426 /// true if the constraint is of kind Distance. 427 bool isLine() const { return Kind == Line || Kind == Distance; } 428 429 /// isAny - Return true if the constraint is of kind Any; 430 bool isAny() const { return Kind == Any; } 431 432 /// getX - If constraint is a point <X, Y>, returns X. 433 /// Otherwise assert. 434 const SCEV *getX() const; 435 436 /// getY - If constraint is a point <X, Y>, returns Y. 437 /// Otherwise assert. 438 const SCEV *getY() const; 439 440 /// getA - If constraint is a line AX + BY = C, returns A. 441 /// Otherwise assert. 442 const SCEV *getA() const; 443 444 /// getB - If constraint is a line AX + BY = C, returns B. 445 /// Otherwise assert. 446 const SCEV *getB() const; 447 448 /// getC - If constraint is a line AX + BY = C, returns C. 449 /// Otherwise assert. 450 const SCEV *getC() const; 451 452 /// getD - If constraint is a distance, returns D. 453 /// Otherwise assert. 454 const SCEV *getD() const; 455 456 /// getAssociatedLoop - Returns the loop associated with this constraint. 457 const Loop *getAssociatedLoop() const; 458 459 /// setPoint - Change a constraint to Point. 460 void setPoint(const SCEV *X, const SCEV *Y, const Loop *CurrentLoop); 461 462 /// setLine - Change a constraint to Line. 463 void setLine(const SCEV *A, const SCEV *B, 464 const SCEV *C, const Loop *CurrentLoop); 465 466 /// setDistance - Change a constraint to Distance. 467 void setDistance(const SCEV *D, const Loop *CurrentLoop); 468 469 /// setEmpty - Change a constraint to Empty. 470 void setEmpty(); 471 472 /// setAny - Change a constraint to Any. 473 void setAny(ScalarEvolution *SE); 474 475 /// dump - For debugging purposes. Dumps the constraint 476 /// out to OS. 477 void dump(raw_ostream &OS) const; 478 }; 479 480 /// establishNestingLevels - Examines the loop nesting of the Src and Dst 481 /// instructions and establishes their shared loops. Sets the variables 482 /// CommonLevels, SrcLevels, and MaxLevels. 483 /// The source and destination instructions needn't be contained in the same 484 /// loop. The routine establishNestingLevels finds the level of most deeply 485 /// nested loop that contains them both, CommonLevels. An instruction that's 486 /// not contained in a loop is at level = 0. MaxLevels is equal to the level 487 /// of the source plus the level of the destination, minus CommonLevels. 488 /// This lets us allocate vectors MaxLevels in length, with room for every 489 /// distinct loop referenced in both the source and destination subscripts. 490 /// The variable SrcLevels is the nesting depth of the source instruction. 491 /// It's used to help calculate distinct loops referenced by the destination. 492 /// Here's the map from loops to levels: 493 /// 0 - unused 494 /// 1 - outermost common loop 495 /// ... - other common loops 496 /// CommonLevels - innermost common loop 497 /// ... - loops containing Src but not Dst 498 /// SrcLevels - innermost loop containing Src but not Dst 499 /// ... - loops containing Dst but not Src 500 /// MaxLevels - innermost loop containing Dst but not Src 501 /// Consider the follow code fragment: 502 /// for (a = ...) { 503 /// for (b = ...) { 504 /// for (c = ...) { 505 /// for (d = ...) { 506 /// A[] = ...; 507 /// } 508 /// } 509 /// for (e = ...) { 510 /// for (f = ...) { 511 /// for (g = ...) { 512 /// ... = A[]; 513 /// } 514 /// } 515 /// } 516 /// } 517 /// } 518 /// If we're looking at the possibility of a dependence between the store 519 /// to A (the Src) and the load from A (the Dst), we'll note that they 520 /// have 2 loops in common, so CommonLevels will equal 2 and the direction 521 /// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7. 522 /// A map from loop names to level indices would look like 523 /// a - 1 524 /// b - 2 = CommonLevels 525 /// c - 3 526 /// d - 4 = SrcLevels 527 /// e - 5 528 /// f - 6 529 /// g - 7 = MaxLevels 530 void establishNestingLevels(const Instruction *Src, 531 const Instruction *Dst); 532 533 unsigned CommonLevels, SrcLevels, MaxLevels; 534 535 /// mapSrcLoop - Given one of the loops containing the source, return 536 /// its level index in our numbering scheme. 537 unsigned mapSrcLoop(const Loop *SrcLoop) const; 538 539 /// mapDstLoop - Given one of the loops containing the destination, 540 /// return its level index in our numbering scheme. 541 unsigned mapDstLoop(const Loop *DstLoop) const; 542 543 /// isLoopInvariant - Returns true if Expression is loop invariant 544 /// in LoopNest. 545 bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const; 546 547 /// Makes sure all subscript pairs share the same integer type by 548 /// sign-extending as necessary. 549 /// Sign-extending a subscript is safe because getelementptr assumes the 550 /// array subscripts are signed. 551 void unifySubscriptType(ArrayRef<Subscript *> Pairs); 552 553 /// removeMatchingExtensions - Examines a subscript pair. 554 /// If the source and destination are identically sign (or zero) 555 /// extended, it strips off the extension in an effort to 556 /// simplify the actual analysis. 557 void removeMatchingExtensions(Subscript *Pair); 558 559 /// collectCommonLoops - Finds the set of loops from the LoopNest that 560 /// have a level <= CommonLevels and are referred to by the SCEV Expression. 561 void collectCommonLoops(const SCEV *Expression, 562 const Loop *LoopNest, 563 SmallBitVector &Loops) const; 564 565 /// checkSrcSubscript - Examines the SCEV Src, returning true iff it's 566 /// linear. Collect the set of loops mentioned by Src. 567 bool checkSrcSubscript(const SCEV *Src, 568 const Loop *LoopNest, 569 SmallBitVector &Loops); 570 571 /// checkDstSubscript - Examines the SCEV Dst, returning true iff it's 572 /// linear. Collect the set of loops mentioned by Dst. 573 bool checkDstSubscript(const SCEV *Dst, 574 const Loop *LoopNest, 575 SmallBitVector &Loops); 576 577 /// isKnownPredicate - Compare X and Y using the predicate Pred. 578 /// Basically a wrapper for SCEV::isKnownPredicate, 579 /// but tries harder, especially in the presence of sign and zero 580 /// extensions and symbolics. 581 bool isKnownPredicate(ICmpInst::Predicate Pred, 582 const SCEV *X, 583 const SCEV *Y) const; 584 585 /// isKnownLessThan - Compare to see if S is less than Size 586 /// Another wrapper for isKnownNegative(S - max(Size, 1)) with some extra 587 /// checking if S is an AddRec and we can prove lessthan using the loop 588 /// bounds. 589 bool isKnownLessThan(const SCEV *S, const SCEV *Size) const; 590 591 /// isKnownNonNegative - Compare to see if S is known not to be negative 592 /// Uses the fact that S comes from Ptr, which may be an inbound GEP, 593 /// Proving there is no wrapping going on. 594 bool isKnownNonNegative(const SCEV *S, const Value *Ptr) const; 595 596 /// collectUpperBound - All subscripts are the same type (on my machine, 597 /// an i64). The loop bound may be a smaller type. collectUpperBound 598 /// find the bound, if available, and zero extends it to the Type T. 599 /// (I zero extend since the bound should always be >= 0.) 600 /// If no upper bound is available, return NULL. 601 const SCEV *collectUpperBound(const Loop *l, Type *T) const; 602 603 /// collectConstantUpperBound - Calls collectUpperBound(), then 604 /// attempts to cast it to SCEVConstant. If the cast fails, 605 /// returns NULL. 606 const SCEVConstant *collectConstantUpperBound(const Loop *l, Type *T) const; 607 608 /// classifyPair - Examines the subscript pair (the Src and Dst SCEVs) 609 /// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. 610 /// Collects the associated loops in a set. 611 Subscript::ClassificationKind classifyPair(const SCEV *Src, 612 const Loop *SrcLoopNest, 613 const SCEV *Dst, 614 const Loop *DstLoopNest, 615 SmallBitVector &Loops); 616 617 /// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence. 618 /// Returns true if any possible dependence is disproved. 619 /// If there might be a dependence, returns false. 620 /// If the dependence isn't proven to exist, 621 /// marks the Result as inconsistent. 622 bool testZIV(const SCEV *Src, 623 const SCEV *Dst, 624 FullDependence &Result) const; 625 626 /// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence. 627 /// Things of the form [c1 + a1*i] and [c2 + a2*j], where 628 /// i and j are induction variables, c1 and c2 are loop invariant, 629 /// and a1 and a2 are constant. 630 /// Returns true if any possible dependence is disproved. 631 /// If there might be a dependence, returns false. 632 /// Sets appropriate direction vector entry and, when possible, 633 /// the distance vector entry. 634 /// If the dependence isn't proven to exist, 635 /// marks the Result as inconsistent. 636 bool testSIV(const SCEV *Src, 637 const SCEV *Dst, 638 unsigned &Level, 639 FullDependence &Result, 640 Constraint &NewConstraint, 641 const SCEV *&SplitIter) const; 642 643 /// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence. 644 /// Things of the form [c1 + a1*i] and [c2 + a2*j] 645 /// where i and j are induction variables, c1 and c2 are loop invariant, 646 /// and a1 and a2 are constant. 647 /// With minor algebra, this test can also be used for things like 648 /// [c1 + a1*i + a2*j][c2]. 649 /// Returns true if any possible dependence is disproved. 650 /// If there might be a dependence, returns false. 651 /// Marks the Result as inconsistent. 652 bool testRDIV(const SCEV *Src, 653 const SCEV *Dst, 654 FullDependence &Result) const; 655 656 /// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence. 657 /// Returns true if dependence disproved. 658 /// Can sometimes refine direction vectors. 659 bool testMIV(const SCEV *Src, 660 const SCEV *Dst, 661 const SmallBitVector &Loops, 662 FullDependence &Result) const; 663 664 /// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst) 665 /// for dependence. 666 /// Things of the form [c1 + a*i] and [c2 + a*i], 667 /// where i is an induction variable, c1 and c2 are loop invariant, 668 /// and a is a constant 669 /// Returns true if any possible dependence is disproved. 670 /// If there might be a dependence, returns false. 671 /// Sets appropriate direction and distance. 672 bool strongSIVtest(const SCEV *Coeff, 673 const SCEV *SrcConst, 674 const SCEV *DstConst, 675 const Loop *CurrentLoop, 676 unsigned Level, 677 FullDependence &Result, 678 Constraint &NewConstraint) const; 679 680 /// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair 681 /// (Src and Dst) for dependence. 682 /// Things of the form [c1 + a*i] and [c2 - a*i], 683 /// where i is an induction variable, c1 and c2 are loop invariant, 684 /// and a is a constant. 685 /// Returns true if any possible dependence is disproved. 686 /// If there might be a dependence, returns false. 687 /// Sets appropriate direction entry. 688 /// Set consistent to false. 689 /// Marks the dependence as splitable. 690 bool weakCrossingSIVtest(const SCEV *SrcCoeff, 691 const SCEV *SrcConst, 692 const SCEV *DstConst, 693 const Loop *CurrentLoop, 694 unsigned Level, 695 FullDependence &Result, 696 Constraint &NewConstraint, 697 const SCEV *&SplitIter) const; 698 699 /// ExactSIVtest - Tests the SIV subscript pair 700 /// (Src and Dst) for dependence. 701 /// Things of the form [c1 + a1*i] and [c2 + a2*i], 702 /// where i is an induction variable, c1 and c2 are loop invariant, 703 /// and a1 and a2 are constant. 704 /// Returns true if any possible dependence is disproved. 705 /// If there might be a dependence, returns false. 706 /// Sets appropriate direction entry. 707 /// Set consistent to false. 708 bool exactSIVtest(const SCEV *SrcCoeff, 709 const SCEV *DstCoeff, 710 const SCEV *SrcConst, 711 const SCEV *DstConst, 712 const Loop *CurrentLoop, 713 unsigned Level, 714 FullDependence &Result, 715 Constraint &NewConstraint) const; 716 717 /// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair 718 /// (Src and Dst) for dependence. 719 /// Things of the form [c1] and [c2 + a*i], 720 /// where i is an induction variable, c1 and c2 are loop invariant, 721 /// and a is a constant. See also weakZeroDstSIVtest. 722 /// Returns true if any possible dependence is disproved. 723 /// If there might be a dependence, returns false. 724 /// Sets appropriate direction entry. 725 /// Set consistent to false. 726 /// If loop peeling will break the dependence, mark appropriately. 727 bool weakZeroSrcSIVtest(const SCEV *DstCoeff, 728 const SCEV *SrcConst, 729 const SCEV *DstConst, 730 const Loop *CurrentLoop, 731 unsigned Level, 732 FullDependence &Result, 733 Constraint &NewConstraint) const; 734 735 /// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair 736 /// (Src and Dst) for dependence. 737 /// Things of the form [c1 + a*i] and [c2], 738 /// where i is an induction variable, c1 and c2 are loop invariant, 739 /// and a is a constant. See also weakZeroSrcSIVtest. 740 /// Returns true if any possible dependence is disproved. 741 /// If there might be a dependence, returns false. 742 /// Sets appropriate direction entry. 743 /// Set consistent to false. 744 /// If loop peeling will break the dependence, mark appropriately. 745 bool weakZeroDstSIVtest(const SCEV *SrcCoeff, 746 const SCEV *SrcConst, 747 const SCEV *DstConst, 748 const Loop *CurrentLoop, 749 unsigned Level, 750 FullDependence &Result, 751 Constraint &NewConstraint) const; 752 753 /// exactRDIVtest - Tests the RDIV subscript pair for dependence. 754 /// Things of the form [c1 + a*i] and [c2 + b*j], 755 /// where i and j are induction variable, c1 and c2 are loop invariant, 756 /// and a and b are constants. 757 /// Returns true if any possible dependence is disproved. 758 /// Marks the result as inconsistent. 759 /// Works in some cases that symbolicRDIVtest doesn't, 760 /// and vice versa. 761 bool exactRDIVtest(const SCEV *SrcCoeff, 762 const SCEV *DstCoeff, 763 const SCEV *SrcConst, 764 const SCEV *DstConst, 765 const Loop *SrcLoop, 766 const Loop *DstLoop, 767 FullDependence &Result) const; 768 769 /// symbolicRDIVtest - Tests the RDIV subscript pair for dependence. 770 /// Things of the form [c1 + a*i] and [c2 + b*j], 771 /// where i and j are induction variable, c1 and c2 are loop invariant, 772 /// and a and b are constants. 773 /// Returns true if any possible dependence is disproved. 774 /// Marks the result as inconsistent. 775 /// Works in some cases that exactRDIVtest doesn't, 776 /// and vice versa. Can also be used as a backup for 777 /// ordinary SIV tests. 778 bool symbolicRDIVtest(const SCEV *SrcCoeff, 779 const SCEV *DstCoeff, 780 const SCEV *SrcConst, 781 const SCEV *DstConst, 782 const Loop *SrcLoop, 783 const Loop *DstLoop) const; 784 785 /// gcdMIVtest - Tests an MIV subscript pair for dependence. 786 /// Returns true if any possible dependence is disproved. 787 /// Marks the result as inconsistent. 788 /// Can sometimes disprove the equal direction for 1 or more loops. 789 // Can handle some symbolics that even the SIV tests don't get, 790 /// so we use it as a backup for everything. 791 bool gcdMIVtest(const SCEV *Src, 792 const SCEV *Dst, 793 FullDependence &Result) const; 794 795 /// banerjeeMIVtest - Tests an MIV subscript pair for dependence. 796 /// Returns true if any possible dependence is disproved. 797 /// Marks the result as inconsistent. 798 /// Computes directions. 799 bool banerjeeMIVtest(const SCEV *Src, 800 const SCEV *Dst, 801 const SmallBitVector &Loops, 802 FullDependence &Result) const; 803 804 /// collectCoefficientInfo - Walks through the subscript, 805 /// collecting each coefficient, the associated loop bounds, 806 /// and recording its positive and negative parts for later use. 807 CoefficientInfo *collectCoeffInfo(const SCEV *Subscript, 808 bool SrcFlag, 809 const SCEV *&Constant) const; 810 811 /// getPositivePart - X^+ = max(X, 0). 812 /// 813 const SCEV *getPositivePart(const SCEV *X) const; 814 815 /// getNegativePart - X^- = min(X, 0). 816 /// 817 const SCEV *getNegativePart(const SCEV *X) const; 818 819 /// getLowerBound - Looks through all the bounds info and 820 /// computes the lower bound given the current direction settings 821 /// at each level. 822 const SCEV *getLowerBound(BoundInfo *Bound) const; 823 824 /// getUpperBound - Looks through all the bounds info and 825 /// computes the upper bound given the current direction settings 826 /// at each level. 827 const SCEV *getUpperBound(BoundInfo *Bound) const; 828 829 /// exploreDirections - Hierarchically expands the direction vector 830 /// search space, combining the directions of discovered dependences 831 /// in the DirSet field of Bound. Returns the number of distinct 832 /// dependences discovered. If the dependence is disproved, 833 /// it will return 0. 834 unsigned exploreDirections(unsigned Level, 835 CoefficientInfo *A, 836 CoefficientInfo *B, 837 BoundInfo *Bound, 838 const SmallBitVector &Loops, 839 unsigned &DepthExpanded, 840 const SCEV *Delta) const; 841 842 /// testBounds - Returns true iff the current bounds are plausible. 843 bool testBounds(unsigned char DirKind, 844 unsigned Level, 845 BoundInfo *Bound, 846 const SCEV *Delta) const; 847 848 /// findBoundsALL - Computes the upper and lower bounds for level K 849 /// using the * direction. Records them in Bound. 850 void findBoundsALL(CoefficientInfo *A, 851 CoefficientInfo *B, 852 BoundInfo *Bound, 853 unsigned K) const; 854 855 /// findBoundsLT - Computes the upper and lower bounds for level K 856 /// using the < direction. Records them in Bound. 857 void findBoundsLT(CoefficientInfo *A, 858 CoefficientInfo *B, 859 BoundInfo *Bound, 860 unsigned K) const; 861 862 /// findBoundsGT - Computes the upper and lower bounds for level K 863 /// using the > direction. Records them in Bound. 864 void findBoundsGT(CoefficientInfo *A, 865 CoefficientInfo *B, 866 BoundInfo *Bound, 867 unsigned K) const; 868 869 /// findBoundsEQ - Computes the upper and lower bounds for level K 870 /// using the = direction. Records them in Bound. 871 void findBoundsEQ(CoefficientInfo *A, 872 CoefficientInfo *B, 873 BoundInfo *Bound, 874 unsigned K) const; 875 876 /// intersectConstraints - Updates X with the intersection 877 /// of the Constraints X and Y. Returns true if X has changed. 878 bool intersectConstraints(Constraint *X, 879 const Constraint *Y); 880 881 /// propagate - Review the constraints, looking for opportunities 882 /// to simplify a subscript pair (Src and Dst). 883 /// Return true if some simplification occurs. 884 /// If the simplification isn't exact (that is, if it is conservative 885 /// in terms of dependence), set consistent to false. 886 bool propagate(const SCEV *&Src, 887 const SCEV *&Dst, 888 SmallBitVector &Loops, 889 SmallVectorImpl<Constraint> &Constraints, 890 bool &Consistent); 891 892 /// propagateDistance - Attempt to propagate a distance 893 /// constraint into a subscript pair (Src and Dst). 894 /// Return true if some simplification occurs. 895 /// If the simplification isn't exact (that is, if it is conservative 896 /// in terms of dependence), set consistent to false. 897 bool propagateDistance(const SCEV *&Src, 898 const SCEV *&Dst, 899 Constraint &CurConstraint, 900 bool &Consistent); 901 902 /// propagatePoint - Attempt to propagate a point 903 /// constraint into a subscript pair (Src and Dst). 904 /// Return true if some simplification occurs. 905 bool propagatePoint(const SCEV *&Src, 906 const SCEV *&Dst, 907 Constraint &CurConstraint); 908 909 /// propagateLine - Attempt to propagate a line 910 /// constraint into a subscript pair (Src and Dst). 911 /// Return true if some simplification occurs. 912 /// If the simplification isn't exact (that is, if it is conservative 913 /// in terms of dependence), set consistent to false. 914 bool propagateLine(const SCEV *&Src, 915 const SCEV *&Dst, 916 Constraint &CurConstraint, 917 bool &Consistent); 918 919 /// findCoefficient - Given a linear SCEV, 920 /// return the coefficient corresponding to specified loop. 921 /// If there isn't one, return the SCEV constant 0. 922 /// For example, given a*i + b*j + c*k, returning the coefficient 923 /// corresponding to the j loop would yield b. 924 const SCEV *findCoefficient(const SCEV *Expr, 925 const Loop *TargetLoop) const; 926 927 /// zeroCoefficient - Given a linear SCEV, 928 /// return the SCEV given by zeroing out the coefficient 929 /// corresponding to the specified loop. 930 /// For example, given a*i + b*j + c*k, zeroing the coefficient 931 /// corresponding to the j loop would yield a*i + c*k. 932 const SCEV *zeroCoefficient(const SCEV *Expr, 933 const Loop *TargetLoop) const; 934 935 /// addToCoefficient - Given a linear SCEV Expr, 936 /// return the SCEV given by adding some Value to the 937 /// coefficient corresponding to the specified TargetLoop. 938 /// For example, given a*i + b*j + c*k, adding 1 to the coefficient 939 /// corresponding to the j loop would yield a*i + (b+1)*j + c*k. 940 const SCEV *addToCoefficient(const SCEV *Expr, 941 const Loop *TargetLoop, 942 const SCEV *Value) const; 943 944 /// updateDirection - Update direction vector entry 945 /// based on the current constraint. 946 void updateDirection(Dependence::DVEntry &Level, 947 const Constraint &CurConstraint) const; 948 949 /// Given a linear access function, tries to recover subscripts 950 /// for each dimension of the array element access. 951 bool tryDelinearize(Instruction *Src, Instruction *Dst, 952 SmallVectorImpl<Subscript> &Pair); 953 954 /// Tries to delinearize \p Src and \p Dst access functions for a fixed size 955 /// multi-dimensional array. Calls tryDelinearizeFixedSizeImpl() to 956 /// delinearize \p Src and \p Dst separately, 957 bool tryDelinearizeFixedSize(Instruction *Src, Instruction *Dst, 958 const SCEV *SrcAccessFn, 959 const SCEV *DstAccessFn, 960 SmallVectorImpl<const SCEV *> &SrcSubscripts, 961 SmallVectorImpl<const SCEV *> &DstSubscripts); 962 963 /// Tries to delinearize access function for a multi-dimensional array with 964 /// symbolic runtime sizes. 965 /// Returns true upon success and false otherwise. 966 bool tryDelinearizeParametricSize( 967 Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn, 968 const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts, 969 SmallVectorImpl<const SCEV *> &DstSubscripts); 970 971 /// checkSubscript - Helper function for checkSrcSubscript and 972 /// checkDstSubscript to avoid duplicate code 973 bool checkSubscript(const SCEV *Expr, const Loop *LoopNest, 974 SmallBitVector &Loops, bool IsSrc); 975 }; // class DependenceInfo 976 977 /// AnalysisPass to compute dependence information in a function 978 class DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> { 979 public: 980 typedef DependenceInfo Result; 981 Result run(Function &F, FunctionAnalysisManager &FAM); 982 983 private: 984 static AnalysisKey Key; 985 friend struct AnalysisInfoMixin<DependenceAnalysis>; 986 }; // class DependenceAnalysis 987 988 /// Printer pass to dump DA results. 989 struct DependenceAnalysisPrinterPass 990 : public PassInfoMixin<DependenceAnalysisPrinterPass> { 991 DependenceAnalysisPrinterPass(raw_ostream &OS, 992 bool NormalizeResults = false) 993 : OS(OS), NormalizeResults(NormalizeResults) {} 994 995 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); 996 997 static bool isRequired() { return true; } 998 999 private: 1000 raw_ostream &OS; 1001 bool NormalizeResults; 1002 }; // class DependenceAnalysisPrinterPass 1003 1004 /// Legacy pass manager pass to access dependence information 1005 class DependenceAnalysisWrapperPass : public FunctionPass { 1006 public: 1007 static char ID; // Class identification, replacement for typeinfo 1008 DependenceAnalysisWrapperPass(); 1009 1010 bool runOnFunction(Function &F) override; 1011 void releaseMemory() override; 1012 void getAnalysisUsage(AnalysisUsage &) const override; 1013 void print(raw_ostream &, const Module * = nullptr) const override; 1014 DependenceInfo &getDI() const; 1015 1016 private: 1017 std::unique_ptr<DependenceInfo> info; 1018 }; // class DependenceAnalysisWrapperPass 1019 1020 /// createDependenceAnalysisPass - This creates an instance of the 1021 /// DependenceAnalysis wrapper pass. 1022 FunctionPass *createDependenceAnalysisWrapperPass(); 1023 1024 } // namespace llvm 1025 1026 #endif 1027