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