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