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