1243789Sdim//===-- llvm/Analysis/DependenceAnalysis.h -------------------- -*- C++ -*-===// 2243789Sdim// 3243789Sdim// The LLVM Compiler Infrastructure 4243789Sdim// 5243789Sdim// This file is distributed under the University of Illinois Open Source 6243789Sdim// License. See LICENSE.TXT for details. 7243789Sdim// 8243789Sdim//===----------------------------------------------------------------------===// 9243789Sdim// 10243789Sdim// DependenceAnalysis is an LLVM pass that analyses dependences between memory 11243789Sdim// accesses. Currently, it is an implementation of the approach described in 12243789Sdim// 13243789Sdim// Practical Dependence Testing 14243789Sdim// Goff, Kennedy, Tseng 15243789Sdim// PLDI 1991 16243789Sdim// 17243789Sdim// There's a single entry point that analyzes the dependence between a pair 18243789Sdim// of memory references in a function, returning either NULL, for no dependence, 19243789Sdim// or a more-or-less detailed description of the dependence between them. 20243789Sdim// 21249423Sdim// This pass exists to support the DependenceGraph pass. There are two separate 22249423Sdim// passes because there's a useful separation of concerns. A dependence exists 23249423Sdim// if two conditions are met: 24249423Sdim// 25249423Sdim// 1) Two instructions reference the same memory location, and 26249423Sdim// 2) There is a flow of control leading from one instruction to the other. 27249423Sdim// 28249423Sdim// DependenceAnalysis attacks the first condition; DependenceGraph will attack 29249423Sdim// the second (it's not yet ready). 30249423Sdim// 31243789Sdim// Please note that this is work in progress and the interface is subject to 32243789Sdim// change. 33243789Sdim// 34243789Sdim// Plausible changes: 35243789Sdim// Return a set of more precise dependences instead of just one dependence 36243789Sdim// summarizing all. 37243789Sdim// 38243789Sdim//===----------------------------------------------------------------------===// 39243789Sdim 40243789Sdim#ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 41243789Sdim#define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H 42243789Sdim 43249423Sdim#include "llvm/ADT/SmallBitVector.h" 44249423Sdim#include "llvm/IR/Instructions.h" 45243789Sdim#include "llvm/Pass.h" 46243789Sdim 47243789Sdimnamespace llvm { 48243789Sdim class AliasAnalysis; 49243789Sdim class Loop; 50243789Sdim class LoopInfo; 51243789Sdim class ScalarEvolution; 52243789Sdim class SCEV; 53243789Sdim class SCEVConstant; 54243789Sdim class raw_ostream; 55243789Sdim 56243789Sdim /// Dependence - This class represents a dependence between two memory 57243789Sdim /// memory references in a function. It contains minimal information and 58243789Sdim /// is used in the very common situation where the compiler is unable to 59243789Sdim /// determine anything beyond the existence of a dependence; that is, it 60243789Sdim /// represents a confused dependence (see also FullDependence). In most 61243789Sdim /// cases (for output, flow, and anti dependences), the dependence implies 62243789Sdim /// an ordering, where the source must precede the destination; in contrast, 63243789Sdim /// input dependences are unordered. 64263508Sdim /// 65263508Sdim /// When a dependence graph is built, each Dependence will be a member of 66263508Sdim /// the set of predecessor edges for its destination instruction and a set 67263508Sdim /// if successor edges for its source instruction. These sets are represented 68263508Sdim /// as singly-linked lists, with the "next" fields stored in the dependence 69263508Sdim /// itelf. 70243789Sdim class Dependence { 71243789Sdim public: 72249423Sdim Dependence(Instruction *Source, 73249423Sdim Instruction *Destination) : 74263508Sdim Src(Source), 75263508Sdim Dst(Destination), 76263508Sdim NextPredecessor(NULL), 77263508Sdim NextSuccessor(NULL) {} 78243789Sdim virtual ~Dependence() {} 79243789Sdim 80243789Sdim /// Dependence::DVEntry - Each level in the distance/direction vector 81243789Sdim /// has a direction (or perhaps a union of several directions), and 82243789Sdim /// perhaps a distance. 83243789Sdim struct DVEntry { 84243789Sdim enum { NONE = 0, 85243789Sdim LT = 1, 86243789Sdim EQ = 2, 87243789Sdim LE = 3, 88243789Sdim GT = 4, 89243789Sdim NE = 5, 90243789Sdim GE = 6, 91243789Sdim ALL = 7 }; 92243789Sdim unsigned char Direction : 3; // Init to ALL, then refine. 93243789Sdim bool Scalar : 1; // Init to true. 94243789Sdim bool PeelFirst : 1; // Peeling the first iteration will break dependence. 95243789Sdim bool PeelLast : 1; // Peeling the last iteration will break the dependence. 96243789Sdim bool Splitable : 1; // Splitting the loop will break dependence. 97243789Sdim const SCEV *Distance; // NULL implies no distance available. 98243789Sdim DVEntry() : Direction(ALL), Scalar(true), PeelFirst(false), 99243789Sdim PeelLast(false), Splitable(false), Distance(NULL) { } 100243789Sdim }; 101243789Sdim 102243789Sdim /// getSrc - Returns the source instruction for this dependence. 103243789Sdim /// 104249423Sdim Instruction *getSrc() const { return Src; } 105243789Sdim 106243789Sdim /// getDst - Returns the destination instruction for this dependence. 107243789Sdim /// 108249423Sdim Instruction *getDst() const { return Dst; } 109243789Sdim 110243789Sdim /// isInput - Returns true if this is an input dependence. 111243789Sdim /// 112243789Sdim bool isInput() const; 113243789Sdim 114243789Sdim /// isOutput - Returns true if this is an output dependence. 115243789Sdim /// 116243789Sdim bool isOutput() const; 117243789Sdim 118243789Sdim /// isFlow - Returns true if this is a flow (aka true) dependence. 119243789Sdim /// 120243789Sdim bool isFlow() const; 121243789Sdim 122243789Sdim /// isAnti - Returns true if this is an anti dependence. 123243789Sdim /// 124243789Sdim bool isAnti() const; 125243789Sdim 126243789Sdim /// isOrdered - Returns true if dependence is Output, Flow, or Anti 127243789Sdim /// 128243789Sdim bool isOrdered() const { return isOutput() || isFlow() || isAnti(); } 129243789Sdim 130243789Sdim /// isUnordered - Returns true if dependence is Input 131243789Sdim /// 132243789Sdim bool isUnordered() const { return isInput(); } 133243789Sdim 134243789Sdim /// isLoopIndependent - Returns true if this is a loop-independent 135243789Sdim /// dependence. 136243789Sdim virtual bool isLoopIndependent() const { return true; } 137243789Sdim 138243789Sdim /// isConfused - Returns true if this dependence is confused 139243789Sdim /// (the compiler understands nothing and makes worst-case 140243789Sdim /// assumptions). 141243789Sdim virtual bool isConfused() const { return true; } 142243789Sdim 143243789Sdim /// isConsistent - Returns true if this dependence is consistent 144243789Sdim /// (occurs every time the source and destination are executed). 145243789Sdim virtual bool isConsistent() const { return false; } 146243789Sdim 147243789Sdim /// getLevels - Returns the number of common loops surrounding the 148243789Sdim /// source and destination of the dependence. 149243789Sdim virtual unsigned getLevels() const { return 0; } 150243789Sdim 151243789Sdim /// getDirection - Returns the direction associated with a particular 152243789Sdim /// level. 153243789Sdim virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; } 154243789Sdim 155243789Sdim /// getDistance - Returns the distance (or NULL) associated with a 156243789Sdim /// particular level. 157243789Sdim virtual const SCEV *getDistance(unsigned Level) const { return NULL; } 158243789Sdim 159243789Sdim /// isPeelFirst - Returns true if peeling the first iteration from 160243789Sdim /// this loop will break this dependence. 161243789Sdim virtual bool isPeelFirst(unsigned Level) const { return false; } 162243789Sdim 163243789Sdim /// isPeelLast - Returns true if peeling the last iteration from 164243789Sdim /// this loop will break this dependence. 165243789Sdim virtual bool isPeelLast(unsigned Level) const { return false; } 166243789Sdim 167243789Sdim /// isSplitable - Returns true if splitting this loop will break 168243789Sdim /// the dependence. 169243789Sdim virtual bool isSplitable(unsigned Level) const { return false; } 170243789Sdim 171243789Sdim /// isScalar - Returns true if a particular level is scalar; that is, 172243789Sdim /// if no subscript in the source or destination mention the induction 173243789Sdim /// variable associated with the loop at this level. 174243789Sdim virtual bool isScalar(unsigned Level) const; 175243789Sdim 176263508Sdim /// getNextPredecessor - Returns the value of the NextPredecessor 177263508Sdim /// field. 178263508Sdim const Dependence *getNextPredecessor() const { 179263508Sdim return NextPredecessor; 180263508Sdim } 181263508Sdim 182263508Sdim /// getNextSuccessor - Returns the value of the NextSuccessor 183263508Sdim /// field. 184263508Sdim const Dependence *getNextSuccessor() const { 185263508Sdim return NextSuccessor; 186263508Sdim } 187263508Sdim 188263508Sdim /// setNextPredecessor - Sets the value of the NextPredecessor 189263508Sdim /// field. 190263508Sdim void setNextPredecessor(const Dependence *pred) { 191263508Sdim NextPredecessor = pred; 192263508Sdim } 193263508Sdim 194263508Sdim /// setNextSuccessor - Sets the value of the NextSuccessor 195263508Sdim /// field. 196263508Sdim void setNextSuccessor(const Dependence *succ) { 197263508Sdim NextSuccessor = succ; 198263508Sdim } 199263508Sdim 200243789Sdim /// dump - For debugging purposes, dumps a dependence to OS. 201243789Sdim /// 202243789Sdim void dump(raw_ostream &OS) const; 203243789Sdim private: 204249423Sdim Instruction *Src, *Dst; 205263508Sdim const Dependence *NextPredecessor, *NextSuccessor; 206243789Sdim friend class DependenceAnalysis; 207243789Sdim }; 208243789Sdim 209243789Sdim 210243789Sdim /// FullDependence - This class represents a dependence between two memory 211243789Sdim /// references in a function. It contains detailed information about the 212249423Sdim /// dependence (direction vectors, etc.) and is used when the compiler is 213243789Sdim /// able to accurately analyze the interaction of the references; that is, 214243789Sdim /// it is not a confused dependence (see Dependence). In most cases 215243789Sdim /// (for output, flow, and anti dependences), the dependence implies an 216243789Sdim /// ordering, where the source must precede the destination; in contrast, 217243789Sdim /// input dependences are unordered. 218243789Sdim class FullDependence : public Dependence { 219243789Sdim public: 220249423Sdim FullDependence(Instruction *Src, 221249423Sdim Instruction *Dst, 222243789Sdim bool LoopIndependent, 223243789Sdim unsigned Levels); 224243789Sdim ~FullDependence() { 225249423Sdim delete[] DV; 226243789Sdim } 227243789Sdim 228243789Sdim /// isLoopIndependent - Returns true if this is a loop-independent 229243789Sdim /// dependence. 230243789Sdim bool isLoopIndependent() const { return LoopIndependent; } 231243789Sdim 232243789Sdim /// isConfused - Returns true if this dependence is confused 233243789Sdim /// (the compiler understands nothing and makes worst-case 234243789Sdim /// assumptions). 235243789Sdim bool isConfused() const { return false; } 236243789Sdim 237243789Sdim /// isConsistent - Returns true if this dependence is consistent 238243789Sdim /// (occurs every time the source and destination are executed). 239243789Sdim bool isConsistent() const { return Consistent; } 240243789Sdim 241243789Sdim /// getLevels - Returns the number of common loops surrounding the 242243789Sdim /// source and destination of the dependence. 243243789Sdim unsigned getLevels() const { return Levels; } 244243789Sdim 245243789Sdim /// getDirection - Returns the direction associated with a particular 246243789Sdim /// level. 247243789Sdim unsigned getDirection(unsigned Level) const; 248243789Sdim 249243789Sdim /// getDistance - Returns the distance (or NULL) associated with a 250243789Sdim /// particular level. 251243789Sdim const SCEV *getDistance(unsigned Level) const; 252243789Sdim 253243789Sdim /// isPeelFirst - Returns true if peeling the first iteration from 254243789Sdim /// this loop will break this dependence. 255243789Sdim bool isPeelFirst(unsigned Level) const; 256243789Sdim 257243789Sdim /// isPeelLast - Returns true if peeling the last iteration from 258243789Sdim /// this loop will break this dependence. 259243789Sdim bool isPeelLast(unsigned Level) const; 260243789Sdim 261243789Sdim /// isSplitable - Returns true if splitting the loop will break 262243789Sdim /// the dependence. 263243789Sdim bool isSplitable(unsigned Level) const; 264243789Sdim 265243789Sdim /// isScalar - Returns true if a particular level is scalar; that is, 266243789Sdim /// if no subscript in the source or destination mention the induction 267243789Sdim /// variable associated with the loop at this level. 268243789Sdim bool isScalar(unsigned Level) const; 269243789Sdim private: 270243789Sdim unsigned short Levels; 271243789Sdim bool LoopIndependent; 272243789Sdim bool Consistent; // Init to true, then refine. 273243789Sdim DVEntry *DV; 274243789Sdim friend class DependenceAnalysis; 275243789Sdim }; 276243789Sdim 277243789Sdim 278243789Sdim /// DependenceAnalysis - This class is the main dependence-analysis driver. 279243789Sdim /// 280243789Sdim class DependenceAnalysis : public FunctionPass { 281249423Sdim void operator=(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; 282249423Sdim DependenceAnalysis(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; 283243789Sdim public: 284243789Sdim /// depends - Tests for a dependence between the Src and Dst instructions. 285243789Sdim /// Returns NULL if no dependence; otherwise, returns a Dependence (or a 286243789Sdim /// FullDependence) with as much information as can be gleaned. 287243789Sdim /// The flag PossiblyLoopIndependent should be set by the caller 288243789Sdim /// if it appears that control flow can reach from Src to Dst 289243789Sdim /// without traversing a loop back edge. 290249423Sdim Dependence *depends(Instruction *Src, 291249423Sdim Instruction *Dst, 292243789Sdim bool PossiblyLoopIndependent); 293243789Sdim 294249423Sdim /// getSplitIteration - Give a dependence that's splittable at some 295243789Sdim /// particular level, return the iteration that should be used to split 296243789Sdim /// the loop. 297243789Sdim /// 298243789Sdim /// Generally, the dependence analyzer will be used to build 299243789Sdim /// a dependence graph for a function (basically a map from instructions 300243789Sdim /// to dependences). Looking for cycles in the graph shows us loops 301243789Sdim /// that cannot be trivially vectorized/parallelized. 302243789Sdim /// 303243789Sdim /// We can try to improve the situation by examining all the dependences 304243789Sdim /// that make up the cycle, looking for ones we can break. 305243789Sdim /// Sometimes, peeling the first or last iteration of a loop will break 306243789Sdim /// dependences, and there are flags for those possibilities. 307243789Sdim /// Sometimes, splitting a loop at some other iteration will do the trick, 308243789Sdim /// and we've got a flag for that case. Rather than waste the space to 309243789Sdim /// record the exact iteration (since we rarely know), we provide 310243789Sdim /// a method that calculates the iteration. It's a drag that it must work 311243789Sdim /// from scratch, but wonderful in that it's possible. 312243789Sdim /// 313243789Sdim /// Here's an example: 314243789Sdim /// 315243789Sdim /// for (i = 0; i < 10; i++) 316243789Sdim /// A[i] = ... 317243789Sdim /// ... = A[11 - i] 318243789Sdim /// 319243789Sdim /// There's a loop-carried flow dependence from the store to the load, 320243789Sdim /// found by the weak-crossing SIV test. The dependence will have a flag, 321243789Sdim /// indicating that the dependence can be broken by splitting the loop. 322243789Sdim /// Calling getSplitIteration will return 5. 323243789Sdim /// Splitting the loop breaks the dependence, like so: 324243789Sdim /// 325243789Sdim /// for (i = 0; i <= 5; i++) 326243789Sdim /// A[i] = ... 327243789Sdim /// ... = A[11 - i] 328243789Sdim /// for (i = 6; i < 10; i++) 329243789Sdim /// A[i] = ... 330243789Sdim /// ... = A[11 - i] 331243789Sdim /// 332243789Sdim /// breaks the dependence and allows us to vectorize/parallelize 333243789Sdim /// both loops. 334243789Sdim const SCEV *getSplitIteration(const Dependence *Dep, unsigned Level); 335243789Sdim 336243789Sdim private: 337243789Sdim AliasAnalysis *AA; 338243789Sdim ScalarEvolution *SE; 339243789Sdim LoopInfo *LI; 340243789Sdim Function *F; 341243789Sdim 342243789Sdim /// Subscript - This private struct represents a pair of subscripts from 343243789Sdim /// a pair of potentially multi-dimensional array references. We use a 344243789Sdim /// vector of them to guide subscript partitioning. 345243789Sdim struct Subscript { 346243789Sdim const SCEV *Src; 347243789Sdim const SCEV *Dst; 348243789Sdim enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification; 349243789Sdim SmallBitVector Loops; 350243789Sdim SmallBitVector GroupLoops; 351243789Sdim SmallBitVector Group; 352243789Sdim }; 353243789Sdim 354243789Sdim struct CoefficientInfo { 355243789Sdim const SCEV *Coeff; 356243789Sdim const SCEV *PosPart; 357243789Sdim const SCEV *NegPart; 358243789Sdim const SCEV *Iterations; 359243789Sdim }; 360243789Sdim 361243789Sdim struct BoundInfo { 362243789Sdim const SCEV *Iterations; 363243789Sdim const SCEV *Upper[8]; 364243789Sdim const SCEV *Lower[8]; 365243789Sdim unsigned char Direction; 366243789Sdim unsigned char DirSet; 367243789Sdim }; 368243789Sdim 369243789Sdim /// Constraint - This private class represents a constraint, as defined 370243789Sdim /// in the paper 371243789Sdim /// 372243789Sdim /// Practical Dependence Testing 373243789Sdim /// Goff, Kennedy, Tseng 374243789Sdim /// PLDI 1991 375243789Sdim /// 376243789Sdim /// There are 5 kinds of constraint, in a hierarchy. 377243789Sdim /// 1) Any - indicates no constraint, any dependence is possible. 378243789Sdim /// 2) Line - A line ax + by = c, where a, b, and c are parameters, 379243789Sdim /// representing the dependence equation. 380243789Sdim /// 3) Distance - The value d of the dependence distance; 381243789Sdim /// 4) Point - A point <x, y> representing the dependence from 382243789Sdim /// iteration x to iteration y. 383243789Sdim /// 5) Empty - No dependence is possible. 384243789Sdim class Constraint { 385243789Sdim private: 386243789Sdim enum ConstraintKind { Empty, Point, Distance, Line, Any } Kind; 387243789Sdim ScalarEvolution *SE; 388243789Sdim const SCEV *A; 389243789Sdim const SCEV *B; 390243789Sdim const SCEV *C; 391243789Sdim const Loop *AssociatedLoop; 392243789Sdim public: 393243789Sdim /// isEmpty - Return true if the constraint is of kind Empty. 394243789Sdim bool isEmpty() const { return Kind == Empty; } 395243789Sdim 396243789Sdim /// isPoint - Return true if the constraint is of kind Point. 397243789Sdim bool isPoint() const { return Kind == Point; } 398243789Sdim 399243789Sdim /// isDistance - Return true if the constraint is of kind Distance. 400243789Sdim bool isDistance() const { return Kind == Distance; } 401243789Sdim 402243789Sdim /// isLine - Return true if the constraint is of kind Line. 403243789Sdim /// Since Distance's can also be represented as Lines, we also return 404243789Sdim /// true if the constraint is of kind Distance. 405243789Sdim bool isLine() const { return Kind == Line || Kind == Distance; } 406243789Sdim 407243789Sdim /// isAny - Return true if the constraint is of kind Any; 408243789Sdim bool isAny() const { return Kind == Any; } 409243789Sdim 410243789Sdim /// getX - If constraint is a point <X, Y>, returns X. 411243789Sdim /// Otherwise assert. 412243789Sdim const SCEV *getX() const; 413243789Sdim 414243789Sdim /// getY - If constraint is a point <X, Y>, returns Y. 415243789Sdim /// Otherwise assert. 416243789Sdim const SCEV *getY() const; 417243789Sdim 418243789Sdim /// getA - If constraint is a line AX + BY = C, returns A. 419243789Sdim /// Otherwise assert. 420243789Sdim const SCEV *getA() const; 421243789Sdim 422243789Sdim /// getB - If constraint is a line AX + BY = C, returns B. 423243789Sdim /// Otherwise assert. 424243789Sdim const SCEV *getB() const; 425243789Sdim 426243789Sdim /// getC - If constraint is a line AX + BY = C, returns C. 427243789Sdim /// Otherwise assert. 428243789Sdim const SCEV *getC() const; 429243789Sdim 430243789Sdim /// getD - If constraint is a distance, returns D. 431243789Sdim /// Otherwise assert. 432243789Sdim const SCEV *getD() const; 433243789Sdim 434243789Sdim /// getAssociatedLoop - Returns the loop associated with this constraint. 435243789Sdim const Loop *getAssociatedLoop() const; 436243789Sdim 437243789Sdim /// setPoint - Change a constraint to Point. 438243789Sdim void setPoint(const SCEV *X, const SCEV *Y, const Loop *CurrentLoop); 439243789Sdim 440243789Sdim /// setLine - Change a constraint to Line. 441243789Sdim void setLine(const SCEV *A, const SCEV *B, 442243789Sdim const SCEV *C, const Loop *CurrentLoop); 443243789Sdim 444243789Sdim /// setDistance - Change a constraint to Distance. 445243789Sdim void setDistance(const SCEV *D, const Loop *CurrentLoop); 446243789Sdim 447243789Sdim /// setEmpty - Change a constraint to Empty. 448243789Sdim void setEmpty(); 449243789Sdim 450243789Sdim /// setAny - Change a constraint to Any. 451243789Sdim void setAny(ScalarEvolution *SE); 452243789Sdim 453243789Sdim /// dump - For debugging purposes. Dumps the constraint 454243789Sdim /// out to OS. 455243789Sdim void dump(raw_ostream &OS) const; 456243789Sdim }; 457243789Sdim 458243789Sdim 459243789Sdim /// establishNestingLevels - Examines the loop nesting of the Src and Dst 460243789Sdim /// instructions and establishes their shared loops. Sets the variables 461243789Sdim /// CommonLevels, SrcLevels, and MaxLevels. 462243789Sdim /// The source and destination instructions needn't be contained in the same 463243789Sdim /// loop. The routine establishNestingLevels finds the level of most deeply 464243789Sdim /// nested loop that contains them both, CommonLevels. An instruction that's 465243789Sdim /// not contained in a loop is at level = 0. MaxLevels is equal to the level 466243789Sdim /// of the source plus the level of the destination, minus CommonLevels. 467243789Sdim /// This lets us allocate vectors MaxLevels in length, with room for every 468243789Sdim /// distinct loop referenced in both the source and destination subscripts. 469243789Sdim /// The variable SrcLevels is the nesting depth of the source instruction. 470243789Sdim /// It's used to help calculate distinct loops referenced by the destination. 471243789Sdim /// Here's the map from loops to levels: 472243789Sdim /// 0 - unused 473243789Sdim /// 1 - outermost common loop 474243789Sdim /// ... - other common loops 475243789Sdim /// CommonLevels - innermost common loop 476243789Sdim /// ... - loops containing Src but not Dst 477243789Sdim /// SrcLevels - innermost loop containing Src but not Dst 478243789Sdim /// ... - loops containing Dst but not Src 479243789Sdim /// MaxLevels - innermost loop containing Dst but not Src 480243789Sdim /// Consider the follow code fragment: 481243789Sdim /// for (a = ...) { 482243789Sdim /// for (b = ...) { 483243789Sdim /// for (c = ...) { 484243789Sdim /// for (d = ...) { 485243789Sdim /// A[] = ...; 486243789Sdim /// } 487243789Sdim /// } 488243789Sdim /// for (e = ...) { 489243789Sdim /// for (f = ...) { 490243789Sdim /// for (g = ...) { 491243789Sdim /// ... = A[]; 492243789Sdim /// } 493243789Sdim /// } 494243789Sdim /// } 495243789Sdim /// } 496243789Sdim /// } 497243789Sdim /// If we're looking at the possibility of a dependence between the store 498243789Sdim /// to A (the Src) and the load from A (the Dst), we'll note that they 499243789Sdim /// have 2 loops in common, so CommonLevels will equal 2 and the direction 500243789Sdim /// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7. 501243789Sdim /// A map from loop names to level indices would look like 502243789Sdim /// a - 1 503243789Sdim /// b - 2 = CommonLevels 504243789Sdim /// c - 3 505243789Sdim /// d - 4 = SrcLevels 506243789Sdim /// e - 5 507243789Sdim /// f - 6 508243789Sdim /// g - 7 = MaxLevels 509243789Sdim void establishNestingLevels(const Instruction *Src, 510243789Sdim const Instruction *Dst); 511243789Sdim 512243789Sdim unsigned CommonLevels, SrcLevels, MaxLevels; 513243789Sdim 514243789Sdim /// mapSrcLoop - Given one of the loops containing the source, return 515243789Sdim /// its level index in our numbering scheme. 516243789Sdim unsigned mapSrcLoop(const Loop *SrcLoop) const; 517243789Sdim 518243789Sdim /// mapDstLoop - Given one of the loops containing the destination, 519243789Sdim /// return its level index in our numbering scheme. 520243789Sdim unsigned mapDstLoop(const Loop *DstLoop) const; 521243789Sdim 522243789Sdim /// isLoopInvariant - Returns true if Expression is loop invariant 523243789Sdim /// in LoopNest. 524243789Sdim bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const; 525243789Sdim 526243789Sdim /// removeMatchingExtensions - Examines a subscript pair. 527243789Sdim /// If the source and destination are identically sign (or zero) 528243789Sdim /// extended, it strips off the extension in an effort to 529243789Sdim /// simplify the actual analysis. 530243789Sdim void removeMatchingExtensions(Subscript *Pair); 531243789Sdim 532243789Sdim /// collectCommonLoops - Finds the set of loops from the LoopNest that 533243789Sdim /// have a level <= CommonLevels and are referred to by the SCEV Expression. 534243789Sdim void collectCommonLoops(const SCEV *Expression, 535243789Sdim const Loop *LoopNest, 536243789Sdim SmallBitVector &Loops) const; 537243789Sdim 538243789Sdim /// checkSrcSubscript - Examines the SCEV Src, returning true iff it's 539243789Sdim /// linear. Collect the set of loops mentioned by Src. 540243789Sdim bool checkSrcSubscript(const SCEV *Src, 541243789Sdim const Loop *LoopNest, 542243789Sdim SmallBitVector &Loops); 543243789Sdim 544243789Sdim /// checkDstSubscript - Examines the SCEV Dst, returning true iff it's 545243789Sdim /// linear. Collect the set of loops mentioned by Dst. 546243789Sdim bool checkDstSubscript(const SCEV *Dst, 547243789Sdim const Loop *LoopNest, 548243789Sdim SmallBitVector &Loops); 549243789Sdim 550243789Sdim /// isKnownPredicate - Compare X and Y using the predicate Pred. 551243789Sdim /// Basically a wrapper for SCEV::isKnownPredicate, 552243789Sdim /// but tries harder, especially in the presence of sign and zero 553243789Sdim /// extensions and symbolics. 554243789Sdim bool isKnownPredicate(ICmpInst::Predicate Pred, 555243789Sdim const SCEV *X, 556243789Sdim const SCEV *Y) const; 557243789Sdim 558243789Sdim /// collectUpperBound - All subscripts are the same type (on my machine, 559243789Sdim /// an i64). The loop bound may be a smaller type. collectUpperBound 560243789Sdim /// find the bound, if available, and zero extends it to the Type T. 561243789Sdim /// (I zero extend since the bound should always be >= 0.) 562243789Sdim /// If no upper bound is available, return NULL. 563243789Sdim const SCEV *collectUpperBound(const Loop *l, Type *T) const; 564243789Sdim 565243789Sdim /// collectConstantUpperBound - Calls collectUpperBound(), then 566243789Sdim /// attempts to cast it to SCEVConstant. If the cast fails, 567243789Sdim /// returns NULL. 568243789Sdim const SCEVConstant *collectConstantUpperBound(const Loop *l, Type *T) const; 569243789Sdim 570243789Sdim /// classifyPair - Examines the subscript pair (the Src and Dst SCEVs) 571243789Sdim /// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. 572243789Sdim /// Collects the associated loops in a set. 573243789Sdim Subscript::ClassificationKind classifyPair(const SCEV *Src, 574243789Sdim const Loop *SrcLoopNest, 575243789Sdim const SCEV *Dst, 576243789Sdim const Loop *DstLoopNest, 577243789Sdim SmallBitVector &Loops); 578243789Sdim 579243789Sdim /// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence. 580243789Sdim /// Returns true if any possible dependence is disproved. 581243789Sdim /// If there might be a dependence, returns false. 582243789Sdim /// If the dependence isn't proven to exist, 583243789Sdim /// marks the Result as inconsistent. 584243789Sdim bool testZIV(const SCEV *Src, 585243789Sdim const SCEV *Dst, 586243789Sdim FullDependence &Result) const; 587243789Sdim 588243789Sdim /// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence. 589243789Sdim /// Things of the form [c1 + a1*i] and [c2 + a2*j], where 590243789Sdim /// i and j are induction variables, c1 and c2 are loop invariant, 591243789Sdim /// and a1 and a2 are constant. 592243789Sdim /// Returns true if any possible dependence is disproved. 593243789Sdim /// If there might be a dependence, returns false. 594243789Sdim /// Sets appropriate direction vector entry and, when possible, 595243789Sdim /// the distance vector entry. 596243789Sdim /// If the dependence isn't proven to exist, 597243789Sdim /// marks the Result as inconsistent. 598243789Sdim bool testSIV(const SCEV *Src, 599243789Sdim const SCEV *Dst, 600243789Sdim unsigned &Level, 601243789Sdim FullDependence &Result, 602243789Sdim Constraint &NewConstraint, 603243789Sdim const SCEV *&SplitIter) const; 604243789Sdim 605243789Sdim /// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence. 606243789Sdim /// Things of the form [c1 + a1*i] and [c2 + a2*j] 607243789Sdim /// where i and j are induction variables, c1 and c2 are loop invariant, 608243789Sdim /// and a1 and a2 are constant. 609243789Sdim /// With minor algebra, this test can also be used for things like 610243789Sdim /// [c1 + a1*i + a2*j][c2]. 611243789Sdim /// Returns true if any possible dependence is disproved. 612243789Sdim /// If there might be a dependence, returns false. 613243789Sdim /// Marks the Result as inconsistent. 614243789Sdim bool testRDIV(const SCEV *Src, 615243789Sdim const SCEV *Dst, 616243789Sdim FullDependence &Result) const; 617243789Sdim 618243789Sdim /// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence. 619243789Sdim /// Returns true if dependence disproved. 620243789Sdim /// Can sometimes refine direction vectors. 621243789Sdim bool testMIV(const SCEV *Src, 622243789Sdim const SCEV *Dst, 623243789Sdim const SmallBitVector &Loops, 624243789Sdim FullDependence &Result) const; 625243789Sdim 626243789Sdim /// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst) 627243789Sdim /// for dependence. 628243789Sdim /// Things of the form [c1 + a*i] and [c2 + a*i], 629243789Sdim /// where i is an induction variable, c1 and c2 are loop invariant, 630243789Sdim /// and a is a constant 631243789Sdim /// Returns true if any possible dependence is disproved. 632243789Sdim /// If there might be a dependence, returns false. 633243789Sdim /// Sets appropriate direction and distance. 634243789Sdim bool strongSIVtest(const SCEV *Coeff, 635243789Sdim const SCEV *SrcConst, 636243789Sdim const SCEV *DstConst, 637243789Sdim const Loop *CurrentLoop, 638243789Sdim unsigned Level, 639243789Sdim FullDependence &Result, 640243789Sdim Constraint &NewConstraint) const; 641243789Sdim 642243789Sdim /// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair 643243789Sdim /// (Src and Dst) for dependence. 644243789Sdim /// Things of the form [c1 + a*i] and [c2 - a*i], 645243789Sdim /// where i is an induction variable, c1 and c2 are loop invariant, 646243789Sdim /// and a is a constant. 647243789Sdim /// Returns true if any possible dependence is disproved. 648243789Sdim /// If there might be a dependence, returns false. 649243789Sdim /// Sets appropriate direction entry. 650243789Sdim /// Set consistent to false. 651243789Sdim /// Marks the dependence as splitable. 652243789Sdim bool weakCrossingSIVtest(const SCEV *SrcCoeff, 653243789Sdim const SCEV *SrcConst, 654243789Sdim const SCEV *DstConst, 655243789Sdim const Loop *CurrentLoop, 656243789Sdim unsigned Level, 657243789Sdim FullDependence &Result, 658243789Sdim Constraint &NewConstraint, 659243789Sdim const SCEV *&SplitIter) const; 660243789Sdim 661243789Sdim /// ExactSIVtest - Tests the SIV subscript pair 662243789Sdim /// (Src and Dst) for dependence. 663243789Sdim /// Things of the form [c1 + a1*i] and [c2 + a2*i], 664243789Sdim /// where i is an induction variable, c1 and c2 are loop invariant, 665243789Sdim /// and a1 and a2 are constant. 666243789Sdim /// Returns true if any possible dependence is disproved. 667243789Sdim /// If there might be a dependence, returns false. 668243789Sdim /// Sets appropriate direction entry. 669243789Sdim /// Set consistent to false. 670243789Sdim bool exactSIVtest(const SCEV *SrcCoeff, 671243789Sdim const SCEV *DstCoeff, 672243789Sdim const SCEV *SrcConst, 673243789Sdim const SCEV *DstConst, 674243789Sdim const Loop *CurrentLoop, 675243789Sdim unsigned Level, 676243789Sdim FullDependence &Result, 677243789Sdim Constraint &NewConstraint) const; 678243789Sdim 679243789Sdim /// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair 680243789Sdim /// (Src and Dst) for dependence. 681243789Sdim /// Things of the form [c1] and [c2 + a*i], 682243789Sdim /// where i is an induction variable, c1 and c2 are loop invariant, 683243789Sdim /// and a is a constant. See also weakZeroDstSIVtest. 684243789Sdim /// Returns true if any possible dependence is disproved. 685243789Sdim /// If there might be a dependence, returns false. 686243789Sdim /// Sets appropriate direction entry. 687243789Sdim /// Set consistent to false. 688243789Sdim /// If loop peeling will break the dependence, mark appropriately. 689243789Sdim bool weakZeroSrcSIVtest(const SCEV *DstCoeff, 690243789Sdim const SCEV *SrcConst, 691243789Sdim const SCEV *DstConst, 692243789Sdim const Loop *CurrentLoop, 693243789Sdim unsigned Level, 694243789Sdim FullDependence &Result, 695243789Sdim Constraint &NewConstraint) const; 696243789Sdim 697243789Sdim /// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair 698243789Sdim /// (Src and Dst) for dependence. 699243789Sdim /// Things of the form [c1 + a*i] and [c2], 700243789Sdim /// where i is an induction variable, c1 and c2 are loop invariant, 701243789Sdim /// and a is a constant. See also weakZeroSrcSIVtest. 702243789Sdim /// Returns true if any possible dependence is disproved. 703243789Sdim /// If there might be a dependence, returns false. 704243789Sdim /// Sets appropriate direction entry. 705243789Sdim /// Set consistent to false. 706243789Sdim /// If loop peeling will break the dependence, mark appropriately. 707243789Sdim bool weakZeroDstSIVtest(const SCEV *SrcCoeff, 708243789Sdim const SCEV *SrcConst, 709243789Sdim const SCEV *DstConst, 710243789Sdim const Loop *CurrentLoop, 711243789Sdim unsigned Level, 712243789Sdim FullDependence &Result, 713243789Sdim Constraint &NewConstraint) const; 714243789Sdim 715243789Sdim /// exactRDIVtest - Tests the RDIV subscript pair for dependence. 716243789Sdim /// Things of the form [c1 + a*i] and [c2 + b*j], 717243789Sdim /// where i and j are induction variable, c1 and c2 are loop invariant, 718243789Sdim /// and a and b are constants. 719243789Sdim /// Returns true if any possible dependence is disproved. 720243789Sdim /// Marks the result as inconsistent. 721243789Sdim /// Works in some cases that symbolicRDIVtest doesn't, 722243789Sdim /// and vice versa. 723243789Sdim bool exactRDIVtest(const SCEV *SrcCoeff, 724243789Sdim const SCEV *DstCoeff, 725243789Sdim const SCEV *SrcConst, 726243789Sdim const SCEV *DstConst, 727243789Sdim const Loop *SrcLoop, 728243789Sdim const Loop *DstLoop, 729243789Sdim FullDependence &Result) const; 730243789Sdim 731243789Sdim /// symbolicRDIVtest - Tests the RDIV subscript pair for dependence. 732243789Sdim /// Things of the form [c1 + a*i] and [c2 + b*j], 733243789Sdim /// where i and j are induction variable, c1 and c2 are loop invariant, 734243789Sdim /// and a and b are constants. 735243789Sdim /// Returns true if any possible dependence is disproved. 736243789Sdim /// Marks the result as inconsistent. 737243789Sdim /// Works in some cases that exactRDIVtest doesn't, 738243789Sdim /// and vice versa. Can also be used as a backup for 739243789Sdim /// ordinary SIV tests. 740243789Sdim bool symbolicRDIVtest(const SCEV *SrcCoeff, 741243789Sdim const SCEV *DstCoeff, 742243789Sdim const SCEV *SrcConst, 743243789Sdim const SCEV *DstConst, 744243789Sdim const Loop *SrcLoop, 745243789Sdim const Loop *DstLoop) const; 746243789Sdim 747243789Sdim /// gcdMIVtest - Tests an MIV subscript pair for dependence. 748243789Sdim /// Returns true if any possible dependence is disproved. 749243789Sdim /// Marks the result as inconsistent. 750243789Sdim /// Can sometimes disprove the equal direction for 1 or more loops. 751243789Sdim // Can handle some symbolics that even the SIV tests don't get, 752243789Sdim /// so we use it as a backup for everything. 753243789Sdim bool gcdMIVtest(const SCEV *Src, 754243789Sdim const SCEV *Dst, 755243789Sdim FullDependence &Result) const; 756243789Sdim 757243789Sdim /// banerjeeMIVtest - Tests an MIV subscript pair for dependence. 758243789Sdim /// Returns true if any possible dependence is disproved. 759243789Sdim /// Marks the result as inconsistent. 760243789Sdim /// Computes directions. 761243789Sdim bool banerjeeMIVtest(const SCEV *Src, 762243789Sdim const SCEV *Dst, 763243789Sdim const SmallBitVector &Loops, 764243789Sdim FullDependence &Result) const; 765243789Sdim 766243789Sdim /// collectCoefficientInfo - Walks through the subscript, 767243789Sdim /// collecting each coefficient, the associated loop bounds, 768243789Sdim /// and recording its positive and negative parts for later use. 769243789Sdim CoefficientInfo *collectCoeffInfo(const SCEV *Subscript, 770243789Sdim bool SrcFlag, 771243789Sdim const SCEV *&Constant) const; 772243789Sdim 773243789Sdim /// getPositivePart - X^+ = max(X, 0). 774243789Sdim /// 775243789Sdim const SCEV *getPositivePart(const SCEV *X) const; 776243789Sdim 777243789Sdim /// getNegativePart - X^- = min(X, 0). 778243789Sdim /// 779243789Sdim const SCEV *getNegativePart(const SCEV *X) const; 780243789Sdim 781243789Sdim /// getLowerBound - Looks through all the bounds info and 782243789Sdim /// computes the lower bound given the current direction settings 783243789Sdim /// at each level. 784243789Sdim const SCEV *getLowerBound(BoundInfo *Bound) const; 785243789Sdim 786243789Sdim /// getUpperBound - Looks through all the bounds info and 787243789Sdim /// computes the upper bound given the current direction settings 788243789Sdim /// at each level. 789243789Sdim const SCEV *getUpperBound(BoundInfo *Bound) const; 790243789Sdim 791243789Sdim /// exploreDirections - Hierarchically expands the direction vector 792243789Sdim /// search space, combining the directions of discovered dependences 793243789Sdim /// in the DirSet field of Bound. Returns the number of distinct 794243789Sdim /// dependences discovered. If the dependence is disproved, 795243789Sdim /// it will return 0. 796243789Sdim unsigned exploreDirections(unsigned Level, 797243789Sdim CoefficientInfo *A, 798243789Sdim CoefficientInfo *B, 799243789Sdim BoundInfo *Bound, 800243789Sdim const SmallBitVector &Loops, 801243789Sdim unsigned &DepthExpanded, 802243789Sdim const SCEV *Delta) const; 803243789Sdim 804243789Sdim /// testBounds - Returns true iff the current bounds are plausible. 805243789Sdim /// 806243789Sdim bool testBounds(unsigned char DirKind, 807243789Sdim unsigned Level, 808243789Sdim BoundInfo *Bound, 809243789Sdim const SCEV *Delta) const; 810243789Sdim 811243789Sdim /// findBoundsALL - Computes the upper and lower bounds for level K 812243789Sdim /// using the * direction. Records them in Bound. 813243789Sdim void findBoundsALL(CoefficientInfo *A, 814243789Sdim CoefficientInfo *B, 815243789Sdim BoundInfo *Bound, 816243789Sdim unsigned K) const; 817243789Sdim 818243789Sdim /// findBoundsLT - Computes the upper and lower bounds for level K 819243789Sdim /// using the < direction. Records them in Bound. 820243789Sdim void findBoundsLT(CoefficientInfo *A, 821243789Sdim CoefficientInfo *B, 822243789Sdim BoundInfo *Bound, 823243789Sdim unsigned K) const; 824243789Sdim 825243789Sdim /// findBoundsGT - Computes the upper and lower bounds for level K 826243789Sdim /// using the > direction. Records them in Bound. 827243789Sdim void findBoundsGT(CoefficientInfo *A, 828243789Sdim CoefficientInfo *B, 829243789Sdim BoundInfo *Bound, 830243789Sdim unsigned K) const; 831243789Sdim 832243789Sdim /// findBoundsEQ - Computes the upper and lower bounds for level K 833243789Sdim /// using the = direction. Records them in Bound. 834243789Sdim void findBoundsEQ(CoefficientInfo *A, 835243789Sdim CoefficientInfo *B, 836243789Sdim BoundInfo *Bound, 837243789Sdim unsigned K) const; 838243789Sdim 839243789Sdim /// intersectConstraints - Updates X with the intersection 840243789Sdim /// of the Constraints X and Y. Returns true if X has changed. 841243789Sdim bool intersectConstraints(Constraint *X, 842243789Sdim const Constraint *Y); 843243789Sdim 844243789Sdim /// propagate - Review the constraints, looking for opportunities 845243789Sdim /// to simplify a subscript pair (Src and Dst). 846243789Sdim /// Return true if some simplification occurs. 847243789Sdim /// If the simplification isn't exact (that is, if it is conservative 848243789Sdim /// in terms of dependence), set consistent to false. 849243789Sdim bool propagate(const SCEV *&Src, 850243789Sdim const SCEV *&Dst, 851243789Sdim SmallBitVector &Loops, 852263508Sdim SmallVectorImpl<Constraint> &Constraints, 853243789Sdim bool &Consistent); 854243789Sdim 855243789Sdim /// propagateDistance - Attempt to propagate a distance 856243789Sdim /// constraint into a subscript pair (Src and Dst). 857243789Sdim /// Return true if some simplification occurs. 858243789Sdim /// If the simplification isn't exact (that is, if it is conservative 859243789Sdim /// in terms of dependence), set consistent to false. 860243789Sdim bool propagateDistance(const SCEV *&Src, 861243789Sdim const SCEV *&Dst, 862243789Sdim Constraint &CurConstraint, 863243789Sdim bool &Consistent); 864243789Sdim 865243789Sdim /// propagatePoint - Attempt to propagate a point 866243789Sdim /// constraint into a subscript pair (Src and Dst). 867243789Sdim /// Return true if some simplification occurs. 868243789Sdim bool propagatePoint(const SCEV *&Src, 869243789Sdim const SCEV *&Dst, 870243789Sdim Constraint &CurConstraint); 871243789Sdim 872243789Sdim /// propagateLine - Attempt to propagate a line 873243789Sdim /// constraint into a subscript pair (Src and Dst). 874243789Sdim /// Return true if some simplification occurs. 875243789Sdim /// If the simplification isn't exact (that is, if it is conservative 876243789Sdim /// in terms of dependence), set consistent to false. 877243789Sdim bool propagateLine(const SCEV *&Src, 878243789Sdim const SCEV *&Dst, 879243789Sdim Constraint &CurConstraint, 880243789Sdim bool &Consistent); 881243789Sdim 882243789Sdim /// findCoefficient - Given a linear SCEV, 883243789Sdim /// return the coefficient corresponding to specified loop. 884243789Sdim /// If there isn't one, return the SCEV constant 0. 885243789Sdim /// For example, given a*i + b*j + c*k, returning the coefficient 886243789Sdim /// corresponding to the j loop would yield b. 887243789Sdim const SCEV *findCoefficient(const SCEV *Expr, 888243789Sdim const Loop *TargetLoop) const; 889243789Sdim 890243789Sdim /// zeroCoefficient - Given a linear SCEV, 891243789Sdim /// return the SCEV given by zeroing out the coefficient 892243789Sdim /// corresponding to the specified loop. 893243789Sdim /// For example, given a*i + b*j + c*k, zeroing the coefficient 894243789Sdim /// corresponding to the j loop would yield a*i + c*k. 895243789Sdim const SCEV *zeroCoefficient(const SCEV *Expr, 896243789Sdim const Loop *TargetLoop) const; 897243789Sdim 898243789Sdim /// addToCoefficient - Given a linear SCEV Expr, 899243789Sdim /// return the SCEV given by adding some Value to the 900243789Sdim /// coefficient corresponding to the specified TargetLoop. 901243789Sdim /// For example, given a*i + b*j + c*k, adding 1 to the coefficient 902243789Sdim /// corresponding to the j loop would yield a*i + (b+1)*j + c*k. 903243789Sdim const SCEV *addToCoefficient(const SCEV *Expr, 904243789Sdim const Loop *TargetLoop, 905243789Sdim const SCEV *Value) const; 906243789Sdim 907243789Sdim /// updateDirection - Update direction vector entry 908243789Sdim /// based on the current constraint. 909243789Sdim void updateDirection(Dependence::DVEntry &Level, 910243789Sdim const Constraint &CurConstraint) const; 911263508Sdim 912263508Sdim bool tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV, 913263508Sdim SmallVectorImpl<Subscript> &Pair) const; 914263508Sdim 915243789Sdim public: 916243789Sdim static char ID; // Class identification, replacement for typeinfo 917243789Sdim DependenceAnalysis() : FunctionPass(ID) { 918243789Sdim initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry()); 919243789Sdim } 920243789Sdim 921243789Sdim bool runOnFunction(Function &F); 922243789Sdim void releaseMemory(); 923243789Sdim void getAnalysisUsage(AnalysisUsage &) const; 924243789Sdim void print(raw_ostream &, const Module * = 0) const; 925243789Sdim }; // class DependenceAnalysis 926243789Sdim 927243789Sdim /// createDependenceAnalysisPass - This creates an instance of the 928243789Sdim /// DependenceAnalysis pass. 929243789Sdim FunctionPass *createDependenceAnalysisPass(); 930243789Sdim 931243789Sdim} // namespace llvm 932243789Sdim 933243789Sdim#endif 934