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