1 //===-- llvm/Analysis/DependenceAnalysis.h -------------------- -*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // DependenceAnalysis is an LLVM pass that analyses dependences between memory 11 // accesses. Currently, it is an implementation of the approach described in 12 // 13 // Practical Dependence Testing 14 // Goff, Kennedy, Tseng 15 // PLDI 1991 16 // 17 // There's a single entry point that analyzes the dependence between a pair 18 // of memory references in a function, returning either NULL, for no dependence, 19 // or a more-or-less detailed description of the dependence between them. 20 // 21 // This pass exists to support the DependenceGraph pass. There are two separate 22 // passes because there's a useful separation of concerns. A dependence exists 23 // if two conditions are met: 24 // 25 // 1) Two instructions reference the same memory location, and 26 // 2) There is a flow of control leading from one instruction to the other. 27 // 28 // DependenceAnalysis attacks the first condition; DependenceGraph will attack 29 // the second (it's not yet ready). 30 // 31 // Please note that this is work in progress and the interface is subject to 32 // change. 33 // 34 // Plausible changes: 35 // Return a set of more precise dependences instead of just one dependence 36 // summarizing all. 37 // 38 //===----------------------------------------------------------------------===// 39 40 #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 41 #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 42 43 #include "llvm/ADT/SmallBitVector.h" 44 #include "llvm/IR/Instructions.h" 45 #include "llvm/Pass.h" 46 47 namespace llvm { 48 class AliasAnalysis; 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 public: 72 Dependence(Instruction *Source, 73 Instruction *Destination) : 74 Src(Source), 75 Dst(Destination), 76 NextPredecessor(nullptr), 77 NextSuccessor(nullptr) {} 78 virtual ~Dependence() {} 79 80 /// Dependence::DVEntry - Each level in the distance/direction vector 81 /// has a direction (or perhaps a union of several directions), and 82 /// perhaps a distance. 83 struct DVEntry { 84 enum { NONE = 0, 85 LT = 1, 86 EQ = 2, 87 LE = 3, 88 GT = 4, 89 NE = 5, 90 GE = 6, 91 ALL = 7 }; 92 unsigned char Direction : 3; // Init to ALL, then refine. 93 bool Scalar : 1; // Init to true. 94 bool PeelFirst : 1; // Peeling the first iteration will break dependence. 95 bool PeelLast : 1; // Peeling the last iteration will break the dependence. 96 bool Splitable : 1; // Splitting the loop will break dependence. 97 const SCEV *Distance; // NULL implies no distance available. 98 DVEntry() : Direction(ALL), Scalar(true), PeelFirst(false), 99 PeelLast(false), Splitable(false), Distance(nullptr) { } 100 }; 101 102 /// getSrc - Returns the source instruction for this dependence. 103 /// 104 Instruction *getSrc() const { return Src; } 105 106 /// getDst - Returns the destination instruction for this dependence. 107 /// 108 Instruction *getDst() const { return Dst; } 109 110 /// isInput - Returns true if this is an input dependence. 111 /// 112 bool isInput() const; 113 114 /// isOutput - Returns true if this is an output dependence. 115 /// 116 bool isOutput() const; 117 118 /// isFlow - Returns true if this is a flow (aka true) dependence. 119 /// 120 bool isFlow() const; 121 122 /// isAnti - Returns true if this is an anti dependence. 123 /// 124 bool isAnti() const; 125 126 /// isOrdered - Returns true if dependence is Output, Flow, or Anti 127 /// 128 bool isOrdered() const { return isOutput() || isFlow() || isAnti(); } 129 130 /// isUnordered - Returns true if dependence is Input 131 /// 132 bool isUnordered() const { return isInput(); } 133 134 /// isLoopIndependent - Returns true if this is a loop-independent 135 /// dependence. 136 virtual bool isLoopIndependent() const { return true; } 137 138 /// isConfused - Returns true if this dependence is confused 139 /// (the compiler understands nothing and makes worst-case 140 /// assumptions). 141 virtual bool isConfused() const { return true; } 142 143 /// isConsistent - Returns true if this dependence is consistent 144 /// (occurs every time the source and destination are executed). 145 virtual bool isConsistent() const { return false; } 146 147 /// getLevels - Returns the number of common loops surrounding the 148 /// source and destination of the dependence. 149 virtual unsigned getLevels() const { return 0; } 150 151 /// getDirection - Returns the direction associated with a particular 152 /// level. 153 virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; } 154 155 /// getDistance - Returns the distance (or NULL) associated with a 156 /// particular level. 157 virtual const SCEV *getDistance(unsigned Level) const { return nullptr; } 158 159 /// isPeelFirst - Returns true if peeling the first iteration from 160 /// this loop will break this dependence. 161 virtual bool isPeelFirst(unsigned Level) const { return false; } 162 163 /// isPeelLast - Returns true if peeling the last iteration from 164 /// this loop will break this dependence. 165 virtual bool isPeelLast(unsigned Level) const { return false; } 166 167 /// isSplitable - Returns true if splitting this loop will break 168 /// the dependence. 169 virtual bool isSplitable(unsigned Level) const { return false; } 170 171 /// isScalar - Returns true if a particular level is scalar; that is, 172 /// if no subscript in the source or destination mention the induction 173 /// variable associated with the loop at this level. 174 virtual bool isScalar(unsigned Level) const; 175 176 /// getNextPredecessor - Returns the value of the NextPredecessor 177 /// field. 178 const Dependence *getNextPredecessor() const { 179 return NextPredecessor; 180 } 181 182 /// getNextSuccessor - Returns the value of the NextSuccessor 183 /// field. 184 const Dependence *getNextSuccessor() const { 185 return NextSuccessor; 186 } 187 188 /// setNextPredecessor - Sets the value of the NextPredecessor 189 /// field. 190 void setNextPredecessor(const Dependence *pred) { 191 NextPredecessor = pred; 192 } 193 194 /// setNextSuccessor - Sets the value of the NextSuccessor 195 /// field. 196 void setNextSuccessor(const Dependence *succ) { 197 NextSuccessor = succ; 198 } 199 200 /// dump - For debugging purposes, dumps a dependence to OS. 201 /// 202 void dump(raw_ostream &OS) const; 203 private: 204 Instruction *Src, *Dst; 205 const Dependence *NextPredecessor, *NextSuccessor; 206 friend class DependenceAnalysis; 207 }; 208 209 210 /// FullDependence - This class represents a dependence between two memory 211 /// references in a function. It contains detailed information about the 212 /// dependence (direction vectors, etc.) and is used when the compiler is 213 /// able to accurately analyze the interaction of the references; that is, 214 /// it is not a confused dependence (see Dependence). In most cases 215 /// (for output, flow, and anti dependences), the dependence implies an 216 /// ordering, where the source must precede the destination; in contrast, 217 /// input dependences are unordered. 218 class FullDependence : public Dependence { 219 public: 220 FullDependence(Instruction *Src, 221 Instruction *Dst, 222 bool LoopIndependent, 223 unsigned Levels); 224 ~FullDependence() { 225 delete[] DV; 226 } 227 228 /// isLoopIndependent - Returns true if this is a loop-independent 229 /// dependence. 230 bool isLoopIndependent() const override { return LoopIndependent; } 231 232 /// isConfused - Returns true if this dependence is confused 233 /// (the compiler understands nothing and makes worst-case 234 /// assumptions). 235 bool isConfused() const override { return false; } 236 237 /// isConsistent - Returns true if this dependence is consistent 238 /// (occurs every time the source and destination are executed). 239 bool isConsistent() const override { return Consistent; } 240 241 /// getLevels - Returns the number of common loops surrounding the 242 /// source and destination of the dependence. 243 unsigned getLevels() const override { return Levels; } 244 245 /// getDirection - Returns the direction associated with a particular 246 /// level. 247 unsigned getDirection(unsigned Level) const override; 248 249 /// getDistance - Returns the distance (or NULL) associated with a 250 /// particular level. 251 const SCEV *getDistance(unsigned Level) const override; 252 253 /// isPeelFirst - Returns true if peeling the first iteration from 254 /// this loop will break this dependence. 255 bool isPeelFirst(unsigned Level) const override; 256 257 /// isPeelLast - Returns true if peeling the last iteration from 258 /// this loop will break this dependence. 259 bool isPeelLast(unsigned Level) const override; 260 261 /// isSplitable - Returns true if splitting the loop will break 262 /// the dependence. 263 bool isSplitable(unsigned Level) const override; 264 265 /// isScalar - Returns true if a particular level is scalar; that is, 266 /// if no subscript in the source or destination mention the induction 267 /// variable associated with the loop at this level. 268 bool isScalar(unsigned Level) const override; 269 private: 270 unsigned short Levels; 271 bool LoopIndependent; 272 bool Consistent; // Init to true, then refine. 273 DVEntry *DV; 274 friend class DependenceAnalysis; 275 }; 276 277 278 /// DependenceAnalysis - This class is the main dependence-analysis driver. 279 /// 280 class DependenceAnalysis : public FunctionPass { 281 void operator=(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; 282 DependenceAnalysis(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; 283 public: 284 /// depends - Tests for a dependence between the Src and Dst instructions. 285 /// Returns NULL if no dependence; otherwise, returns a Dependence (or a 286 /// FullDependence) with as much information as can be gleaned. 287 /// The flag PossiblyLoopIndependent should be set by the caller 288 /// if it appears that control flow can reach from Src to Dst 289 /// without traversing a loop back edge. 290 Dependence *depends(Instruction *Src, 291 Instruction *Dst, 292 bool PossiblyLoopIndependent); 293 294 /// getSplitIteration - Give a dependence that's splittable at some 295 /// particular level, return the iteration that should be used to split 296 /// the loop. 297 /// 298 /// Generally, the dependence analyzer will be used to build 299 /// a dependence graph for a function (basically a map from instructions 300 /// to dependences). Looking for cycles in the graph shows us loops 301 /// that cannot be trivially vectorized/parallelized. 302 /// 303 /// We can try to improve the situation by examining all the dependences 304 /// that make up the cycle, looking for ones we can break. 305 /// Sometimes, peeling the first or last iteration of a loop will break 306 /// dependences, and there are flags for those possibilities. 307 /// Sometimes, splitting a loop at some other iteration will do the trick, 308 /// and we've got a flag for that case. Rather than waste the space to 309 /// record the exact iteration (since we rarely know), we provide 310 /// a method that calculates the iteration. It's a drag that it must work 311 /// from scratch, but wonderful in that it's possible. 312 /// 313 /// Here's an example: 314 /// 315 /// for (i = 0; i < 10; i++) 316 /// A[i] = ... 317 /// ... = A[11 - i] 318 /// 319 /// There's a loop-carried flow dependence from the store to the load, 320 /// found by the weak-crossing SIV test. The dependence will have a flag, 321 /// indicating that the dependence can be broken by splitting the loop. 322 /// Calling getSplitIteration will return 5. 323 /// Splitting the loop breaks the dependence, like so: 324 /// 325 /// for (i = 0; i <= 5; i++) 326 /// A[i] = ... 327 /// ... = A[11 - i] 328 /// for (i = 6; i < 10; i++) 329 /// A[i] = ... 330 /// ... = A[11 - i] 331 /// 332 /// breaks the dependence and allows us to vectorize/parallelize 333 /// both loops. 334 const SCEV *getSplitIteration(const Dependence *Dep, unsigned Level); 335 336 private: 337 AliasAnalysis *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 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 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 /// removeMatchingExtensions - Examines a subscript pair. 527 /// If the source and destination are identically sign (or zero) 528 /// extended, it strips off the extension in an effort to 529 /// simplify the actual analysis. 530 void removeMatchingExtensions(Subscript *Pair); 531 532 /// collectCommonLoops - Finds the set of loops from the LoopNest that 533 /// have a level <= CommonLevels and are referred to by the SCEV Expression. 534 void collectCommonLoops(const SCEV *Expression, 535 const Loop *LoopNest, 536 SmallBitVector &Loops) const; 537 538 /// checkSrcSubscript - Examines the SCEV Src, returning true iff it's 539 /// linear. Collect the set of loops mentioned by Src. 540 bool checkSrcSubscript(const SCEV *Src, 541 const Loop *LoopNest, 542 SmallBitVector &Loops); 543 544 /// checkDstSubscript - Examines the SCEV Dst, returning true iff it's 545 /// linear. Collect the set of loops mentioned by Dst. 546 bool checkDstSubscript(const SCEV *Dst, 547 const Loop *LoopNest, 548 SmallBitVector &Loops); 549 550 /// isKnownPredicate - Compare X and Y using the predicate Pred. 551 /// Basically a wrapper for SCEV::isKnownPredicate, 552 /// but tries harder, especially in the presence of sign and zero 553 /// extensions and symbolics. 554 bool isKnownPredicate(ICmpInst::Predicate Pred, 555 const SCEV *X, 556 const SCEV *Y) const; 557 558 /// collectUpperBound - All subscripts are the same type (on my machine, 559 /// an i64). The loop bound may be a smaller type. collectUpperBound 560 /// find the bound, if available, and zero extends it to the Type T. 561 /// (I zero extend since the bound should always be >= 0.) 562 /// If no upper bound is available, return NULL. 563 const SCEV *collectUpperBound(const Loop *l, Type *T) const; 564 565 /// collectConstantUpperBound - Calls collectUpperBound(), then 566 /// attempts to cast it to SCEVConstant. If the cast fails, 567 /// returns NULL. 568 const SCEVConstant *collectConstantUpperBound(const Loop *l, Type *T) const; 569 570 /// classifyPair - Examines the subscript pair (the Src and Dst SCEVs) 571 /// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. 572 /// Collects the associated loops in a set. 573 Subscript::ClassificationKind classifyPair(const SCEV *Src, 574 const Loop *SrcLoopNest, 575 const SCEV *Dst, 576 const Loop *DstLoopNest, 577 SmallBitVector &Loops); 578 579 /// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence. 580 /// Returns true if any possible dependence is disproved. 581 /// If there might be a dependence, returns false. 582 /// If the dependence isn't proven to exist, 583 /// marks the Result as inconsistent. 584 bool testZIV(const SCEV *Src, 585 const SCEV *Dst, 586 FullDependence &Result) const; 587 588 /// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence. 589 /// Things of the form [c1 + a1*i] and [c2 + a2*j], where 590 /// i and j are induction variables, c1 and c2 are loop invariant, 591 /// and a1 and a2 are constant. 592 /// Returns true if any possible dependence is disproved. 593 /// If there might be a dependence, returns false. 594 /// Sets appropriate direction vector entry and, when possible, 595 /// the distance vector entry. 596 /// If the dependence isn't proven to exist, 597 /// marks the Result as inconsistent. 598 bool testSIV(const SCEV *Src, 599 const SCEV *Dst, 600 unsigned &Level, 601 FullDependence &Result, 602 Constraint &NewConstraint, 603 const SCEV *&SplitIter) const; 604 605 /// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence. 606 /// Things of the form [c1 + a1*i] and [c2 + a2*j] 607 /// where i and j are induction variables, c1 and c2 are loop invariant, 608 /// and a1 and a2 are constant. 609 /// With minor algebra, this test can also be used for things like 610 /// [c1 + a1*i + a2*j][c2]. 611 /// Returns true if any possible dependence is disproved. 612 /// If there might be a dependence, returns false. 613 /// Marks the Result as inconsistent. 614 bool testRDIV(const SCEV *Src, 615 const SCEV *Dst, 616 FullDependence &Result) const; 617 618 /// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence. 619 /// Returns true if dependence disproved. 620 /// Can sometimes refine direction vectors. 621 bool testMIV(const SCEV *Src, 622 const SCEV *Dst, 623 const SmallBitVector &Loops, 624 FullDependence &Result) const; 625 626 /// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst) 627 /// for dependence. 628 /// Things of the form [c1 + a*i] and [c2 + a*i], 629 /// where i is an induction variable, c1 and c2 are loop invariant, 630 /// and a is a constant 631 /// Returns true if any possible dependence is disproved. 632 /// If there might be a dependence, returns false. 633 /// Sets appropriate direction and distance. 634 bool strongSIVtest(const SCEV *Coeff, 635 const SCEV *SrcConst, 636 const SCEV *DstConst, 637 const Loop *CurrentLoop, 638 unsigned Level, 639 FullDependence &Result, 640 Constraint &NewConstraint) const; 641 642 /// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair 643 /// (Src and Dst) 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 entry. 650 /// Set consistent to false. 651 /// Marks the dependence as splitable. 652 bool weakCrossingSIVtest(const SCEV *SrcCoeff, 653 const SCEV *SrcConst, 654 const SCEV *DstConst, 655 const Loop *CurrentLoop, 656 unsigned Level, 657 FullDependence &Result, 658 Constraint &NewConstraint, 659 const SCEV *&SplitIter) const; 660 661 /// ExactSIVtest - Tests the SIV subscript pair 662 /// (Src and Dst) for dependence. 663 /// Things of the form [c1 + a1*i] and [c2 + a2*i], 664 /// where i is an induction variable, c1 and c2 are loop invariant, 665 /// and a1 and a2 are constant. 666 /// Returns true if any possible dependence is disproved. 667 /// If there might be a dependence, returns false. 668 /// Sets appropriate direction entry. 669 /// Set consistent to false. 670 bool exactSIVtest(const SCEV *SrcCoeff, 671 const SCEV *DstCoeff, 672 const SCEV *SrcConst, 673 const SCEV *DstConst, 674 const Loop *CurrentLoop, 675 unsigned Level, 676 FullDependence &Result, 677 Constraint &NewConstraint) const; 678 679 /// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair 680 /// (Src and Dst) for dependence. 681 /// Things of the form [c1] and [c2 + a*i], 682 /// where i is an induction variable, c1 and c2 are loop invariant, 683 /// and a is a constant. See also weakZeroDstSIVtest. 684 /// Returns true if any possible dependence is disproved. 685 /// If there might be a dependence, returns false. 686 /// Sets appropriate direction entry. 687 /// Set consistent to false. 688 /// If loop peeling will break the dependence, mark appropriately. 689 bool weakZeroSrcSIVtest(const SCEV *DstCoeff, 690 const SCEV *SrcConst, 691 const SCEV *DstConst, 692 const Loop *CurrentLoop, 693 unsigned Level, 694 FullDependence &Result, 695 Constraint &NewConstraint) const; 696 697 /// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair 698 /// (Src and Dst) for dependence. 699 /// Things of the form [c1 + a*i] and [c2], 700 /// where i is an induction variable, c1 and c2 are loop invariant, 701 /// and a is a constant. See also weakZeroSrcSIVtest. 702 /// Returns true if any possible dependence is disproved. 703 /// If there might be a dependence, returns false. 704 /// Sets appropriate direction entry. 705 /// Set consistent to false. 706 /// If loop peeling will break the dependence, mark appropriately. 707 bool weakZeroDstSIVtest(const SCEV *SrcCoeff, 708 const SCEV *SrcConst, 709 const SCEV *DstConst, 710 const Loop *CurrentLoop, 711 unsigned Level, 712 FullDependence &Result, 713 Constraint &NewConstraint) const; 714 715 /// exactRDIVtest - Tests the RDIV subscript pair for dependence. 716 /// Things of the form [c1 + a*i] and [c2 + b*j], 717 /// where i and j are induction variable, c1 and c2 are loop invariant, 718 /// and a and b are constants. 719 /// Returns true if any possible dependence is disproved. 720 /// Marks the result as inconsistent. 721 /// Works in some cases that symbolicRDIVtest doesn't, 722 /// and vice versa. 723 bool exactRDIVtest(const SCEV *SrcCoeff, 724 const SCEV *DstCoeff, 725 const SCEV *SrcConst, 726 const SCEV *DstConst, 727 const Loop *SrcLoop, 728 const Loop *DstLoop, 729 FullDependence &Result) const; 730 731 /// symbolicRDIVtest - 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 exactRDIVtest doesn't, 738 /// and vice versa. Can also be used as a backup for 739 /// ordinary SIV tests. 740 bool symbolicRDIVtest(const SCEV *SrcCoeff, 741 const SCEV *DstCoeff, 742 const SCEV *SrcConst, 743 const SCEV *DstConst, 744 const Loop *SrcLoop, 745 const Loop *DstLoop) const; 746 747 /// gcdMIVtest - Tests an MIV subscript pair for dependence. 748 /// Returns true if any possible dependence is disproved. 749 /// Marks the result as inconsistent. 750 /// Can sometimes disprove the equal direction for 1 or more loops. 751 // Can handle some symbolics that even the SIV tests don't get, 752 /// so we use it as a backup for everything. 753 bool gcdMIVtest(const SCEV *Src, 754 const SCEV *Dst, 755 FullDependence &Result) const; 756 757 /// banerjeeMIVtest - Tests an MIV subscript pair for dependence. 758 /// Returns true if any possible dependence is disproved. 759 /// Marks the result as inconsistent. 760 /// Computes directions. 761 bool banerjeeMIVtest(const SCEV *Src, 762 const SCEV *Dst, 763 const SmallBitVector &Loops, 764 FullDependence &Result) const; 765 766 /// collectCoefficientInfo - Walks through the subscript, 767 /// collecting each coefficient, the associated loop bounds, 768 /// and recording its positive and negative parts for later use. 769 CoefficientInfo *collectCoeffInfo(const SCEV *Subscript, 770 bool SrcFlag, 771 const SCEV *&Constant) const; 772 773 /// getPositivePart - X^+ = max(X, 0). 774 /// 775 const SCEV *getPositivePart(const SCEV *X) const; 776 777 /// getNegativePart - X^- = min(X, 0). 778 /// 779 const SCEV *getNegativePart(const SCEV *X) const; 780 781 /// getLowerBound - Looks through all the bounds info and 782 /// computes the lower bound given the current direction settings 783 /// at each level. 784 const SCEV *getLowerBound(BoundInfo *Bound) const; 785 786 /// getUpperBound - Looks through all the bounds info and 787 /// computes the upper bound given the current direction settings 788 /// at each level. 789 const SCEV *getUpperBound(BoundInfo *Bound) const; 790 791 /// exploreDirections - Hierarchically expands the direction vector 792 /// search space, combining the directions of discovered dependences 793 /// in the DirSet field of Bound. Returns the number of distinct 794 /// dependences discovered. If the dependence is disproved, 795 /// it will return 0. 796 unsigned exploreDirections(unsigned Level, 797 CoefficientInfo *A, 798 CoefficientInfo *B, 799 BoundInfo *Bound, 800 const SmallBitVector &Loops, 801 unsigned &DepthExpanded, 802 const SCEV *Delta) const; 803 804 /// testBounds - Returns true iff the current bounds are plausible. 805 /// 806 bool testBounds(unsigned char DirKind, 807 unsigned Level, 808 BoundInfo *Bound, 809 const SCEV *Delta) const; 810 811 /// findBoundsALL - Computes the upper and lower bounds for level K 812 /// using the * direction. Records them in Bound. 813 void findBoundsALL(CoefficientInfo *A, 814 CoefficientInfo *B, 815 BoundInfo *Bound, 816 unsigned K) const; 817 818 /// findBoundsLT - Computes the upper and lower bounds for level K 819 /// using the < direction. Records them in Bound. 820 void findBoundsLT(CoefficientInfo *A, 821 CoefficientInfo *B, 822 BoundInfo *Bound, 823 unsigned K) const; 824 825 /// findBoundsGT - Computes the upper and lower bounds for level K 826 /// using the > direction. Records them in Bound. 827 void findBoundsGT(CoefficientInfo *A, 828 CoefficientInfo *B, 829 BoundInfo *Bound, 830 unsigned K) const; 831 832 /// findBoundsEQ - Computes the upper and lower bounds for level K 833 /// using the = direction. Records them in Bound. 834 void findBoundsEQ(CoefficientInfo *A, 835 CoefficientInfo *B, 836 BoundInfo *Bound, 837 unsigned K) const; 838 839 /// intersectConstraints - Updates X with the intersection 840 /// of the Constraints X and Y. Returns true if X has changed. 841 bool intersectConstraints(Constraint *X, 842 const Constraint *Y); 843 844 /// propagate - Review the constraints, looking for opportunities 845 /// to simplify a subscript pair (Src and Dst). 846 /// Return true if some simplification occurs. 847 /// If the simplification isn't exact (that is, if it is conservative 848 /// in terms of dependence), set consistent to false. 849 bool propagate(const SCEV *&Src, 850 const SCEV *&Dst, 851 SmallBitVector &Loops, 852 SmallVectorImpl<Constraint> &Constraints, 853 bool &Consistent); 854 855 /// propagateDistance - Attempt to propagate a distance 856 /// constraint into a subscript pair (Src and Dst). 857 /// Return true if some simplification occurs. 858 /// If the simplification isn't exact (that is, if it is conservative 859 /// in terms of dependence), set consistent to false. 860 bool propagateDistance(const SCEV *&Src, 861 const SCEV *&Dst, 862 Constraint &CurConstraint, 863 bool &Consistent); 864 865 /// propagatePoint - Attempt to propagate a point 866 /// constraint into a subscript pair (Src and Dst). 867 /// Return true if some simplification occurs. 868 bool propagatePoint(const SCEV *&Src, 869 const SCEV *&Dst, 870 Constraint &CurConstraint); 871 872 /// propagateLine - Attempt to propagate a line 873 /// constraint into a subscript pair (Src and Dst). 874 /// Return true if some simplification occurs. 875 /// If the simplification isn't exact (that is, if it is conservative 876 /// in terms of dependence), set consistent to false. 877 bool propagateLine(const SCEV *&Src, 878 const SCEV *&Dst, 879 Constraint &CurConstraint, 880 bool &Consistent); 881 882 /// findCoefficient - Given a linear SCEV, 883 /// return the coefficient corresponding to specified loop. 884 /// If there isn't one, return the SCEV constant 0. 885 /// For example, given a*i + b*j + c*k, returning the coefficient 886 /// corresponding to the j loop would yield b. 887 const SCEV *findCoefficient(const SCEV *Expr, 888 const Loop *TargetLoop) const; 889 890 /// zeroCoefficient - Given a linear SCEV, 891 /// return the SCEV given by zeroing out the coefficient 892 /// corresponding to the specified loop. 893 /// For example, given a*i + b*j + c*k, zeroing the coefficient 894 /// corresponding to the j loop would yield a*i + c*k. 895 const SCEV *zeroCoefficient(const SCEV *Expr, 896 const Loop *TargetLoop) const; 897 898 /// addToCoefficient - Given a linear SCEV Expr, 899 /// return the SCEV given by adding some Value to the 900 /// coefficient corresponding to the specified TargetLoop. 901 /// For example, given a*i + b*j + c*k, adding 1 to the coefficient 902 /// corresponding to the j loop would yield a*i + (b+1)*j + c*k. 903 const SCEV *addToCoefficient(const SCEV *Expr, 904 const Loop *TargetLoop, 905 const SCEV *Value) const; 906 907 /// updateDirection - Update direction vector entry 908 /// based on the current constraint. 909 void updateDirection(Dependence::DVEntry &Level, 910 const Constraint &CurConstraint) const; 911 912 bool tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV, 913 SmallVectorImpl<Subscript> &Pair, 914 const SCEV *ElementSize) const; 915 916 public: 917 static char ID; // Class identification, replacement for typeinfo 918 DependenceAnalysis() : FunctionPass(ID) { 919 initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry()); 920 } 921 922 bool runOnFunction(Function &F) override; 923 void releaseMemory() override; 924 void getAnalysisUsage(AnalysisUsage &) const override; 925 void print(raw_ostream &, const Module * = nullptr) const override; 926 }; // class DependenceAnalysis 927 928 /// createDependenceAnalysisPass - This creates an instance of the 929 /// DependenceAnalysis pass. 930 FunctionPass *createDependenceAnalysisPass(); 931 932 } // namespace llvm 933 934 #endif 935
