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