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