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