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