//===-- DependenceAnalysis.cpp - DA Implementation --------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // DependenceAnalysis is an LLVM pass that analyses dependences between memory // accesses. Currently, it is an (incomplete) implementation of the approach // described in // // Practical Dependence Testing // Goff, Kennedy, Tseng // PLDI 1991 // // There's a single entry point that analyzes the dependence between a pair // of memory references in a function, returning either NULL, for no dependence, // or a more-or-less detailed description of the dependence between them. // // Currently, the implementation cannot propagate constraints between // coupled RDIV subscripts and lacks a multi-subscript MIV test. // Both of these are conservative weaknesses; // that is, not a source of correctness problems. // // Since Clang linearizes some array subscripts, the dependence // analysis is using SCEV->delinearize to recover the representation of multiple // subscripts, and thus avoid the more expensive and less precise MIV tests. The // delinearization is controlled by the flag -da-delinearize. // // We should pay some careful attention to the possibility of integer overflow // in the implementation of the various tests. This could happen with Add, // Subtract, or Multiply, with both APInt's and SCEV's. // // Some non-linear subscript pairs can be handled by the GCD test // (and perhaps other tests). // Should explore how often these things occur. // // Finally, it seems like certain test cases expose weaknesses in the SCEV // simplification, especially in the handling of sign and zero extensions. // It could be useful to spend time exploring these. // // Please note that this is work in progress and the interface is subject to // change. // //===----------------------------------------------------------------------===// // // // In memory of Ken Kennedy, 1945 - 2007 // // // //===----------------------------------------------------------------------===// #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Delinearization.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/Module.h" #include "llvm/InitializePasses.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" usingnamespacellvm; #define DEBUG_TYPE … //===----------------------------------------------------------------------===// // statistics STATISTIC(TotalArrayPairs, "Array pairs tested"); STATISTIC(SeparableSubscriptPairs, "Separable subscript pairs"); STATISTIC(CoupledSubscriptPairs, "Coupled subscript pairs"); STATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs"); STATISTIC(ZIVapplications, "ZIV applications"); STATISTIC(ZIVindependence, "ZIV independence"); STATISTIC(StrongSIVapplications, "Strong SIV applications"); STATISTIC(StrongSIVsuccesses, "Strong SIV successes"); STATISTIC(StrongSIVindependence, "Strong SIV independence"); STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications"); STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes"); STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence"); STATISTIC(ExactSIVapplications, "Exact SIV applications"); STATISTIC(ExactSIVsuccesses, "Exact SIV successes"); STATISTIC(ExactSIVindependence, "Exact SIV independence"); STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications"); STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes"); STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence"); STATISTIC(ExactRDIVapplications, "Exact RDIV applications"); STATISTIC(ExactRDIVindependence, "Exact RDIV independence"); STATISTIC(SymbolicRDIVapplications, "Symbolic RDIV applications"); STATISTIC(SymbolicRDIVindependence, "Symbolic RDIV independence"); STATISTIC(DeltaApplications, "Delta applications"); STATISTIC(DeltaSuccesses, "Delta successes"); STATISTIC(DeltaIndependence, "Delta independence"); STATISTIC(DeltaPropagations, "Delta propagations"); STATISTIC(GCDapplications, "GCD applications"); STATISTIC(GCDsuccesses, "GCD successes"); STATISTIC(GCDindependence, "GCD independence"); STATISTIC(BanerjeeApplications, "Banerjee applications"); STATISTIC(BanerjeeIndependence, "Banerjee independence"); STATISTIC(BanerjeeSuccesses, "Banerjee successes"); static cl::opt<bool> Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::desc("Try to delinearize array references.")); static cl::opt<bool> DisableDelinearizationChecks( "da-disable-delinearization-checks", cl::Hidden, cl::desc( "Disable checks that try to statically verify validity of " "delinearized subscripts. Enabling this option may result in incorrect " "dependence vectors for languages that allow the subscript of one " "dimension to underflow or overflow into another dimension.")); static cl::opt<unsigned> MIVMaxLevelThreshold( "da-miv-max-level-threshold", cl::init(7), cl::Hidden, cl::desc("Maximum depth allowed for the recursive algorithm used to " "explore MIV direction vectors.")); //===----------------------------------------------------------------------===// // basics DependenceAnalysis::Result DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { … } AnalysisKey DependenceAnalysis::Key; INITIALIZE_PASS_BEGIN(DependenceAnalysisWrapperPass, "da", "Dependence Analysis", true, true) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis", true, true) char DependenceAnalysisWrapperPass::ID = …; DependenceAnalysisWrapperPass::DependenceAnalysisWrapperPass() : … { … } FunctionPass *llvm::createDependenceAnalysisWrapperPass() { … } bool DependenceAnalysisWrapperPass::runOnFunction(Function &F) { … } DependenceInfo &DependenceAnalysisWrapperPass::getDI() const { … } void DependenceAnalysisWrapperPass::releaseMemory() { … } void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … } // Used to test the dependence analyzer. // Looks through the function, noting instructions that may access memory. // Calls depends() on every possible pair and prints out the result. // Ignores all other instructions. static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA, ScalarEvolution &SE, bool NormalizeResults) { … } void DependenceAnalysisWrapperPass::print(raw_ostream &OS, const Module *) const { … } PreservedAnalyses DependenceAnalysisPrinterPass::run(Function &F, FunctionAnalysisManager &FAM) { … } //===----------------------------------------------------------------------===// // Dependence methods // Returns true if this is an input dependence. bool Dependence::isInput() const { … } // Returns true if this is an output dependence. bool Dependence::isOutput() const { … } // Returns true if this is an flow (aka true) dependence. bool Dependence::isFlow() const { … } // Returns true if this is an anti dependence. bool Dependence::isAnti() const { … } // Returns true if a particular level is scalar; that is, // if no subscript in the source or destination mention the induction // variable associated with the loop at this level. // Leave this out of line, so it will serve as a virtual method anchor bool Dependence::isScalar(unsigned level) const { … } //===----------------------------------------------------------------------===// // FullDependence methods FullDependence::FullDependence(Instruction *Source, Instruction *Destination, bool PossiblyLoopIndependent, unsigned CommonLevels) : … { … } // FIXME: in some cases the meaning of a negative direction vector // may not be straightforward, e.g., // for (int i = 0; i < 32; ++i) { // Src: A[i] = ...; // Dst: use(A[31 - i]); // } // The dependency is // flow { Src[i] -> Dst[31 - i] : when i >= 16 } and // anti { Dst[i] -> Src[31 - i] : when i < 16 }, // -- hence a [<>]. // As long as a dependence result contains '>' ('<>', '<=>', "*"), it // means that a reversed/normalized dependence needs to be considered // as well. Nevertheless, current isDirectionNegative() only returns // true with a '>' or '>=' dependency for ease of canonicalizing the // dependency vector, since the reverse of '<>', '<=>' and "*" is itself. bool FullDependence::isDirectionNegative() const { … } bool FullDependence::normalize(ScalarEvolution *SE) { … } // The rest are simple getters that hide the implementation. // getDirection - Returns the direction associated with a particular level. unsigned FullDependence::getDirection(unsigned Level) const { … } // Returns the distance (or NULL) associated with a particular level. const SCEV *FullDependence::getDistance(unsigned Level) const { … } // Returns true if a particular level is scalar; that is, // if no subscript in the source or destination mention the induction // variable associated with the loop at this level. bool FullDependence::isScalar(unsigned Level) const { … } // Returns true if peeling the first iteration from this loop // will break this dependence. bool FullDependence::isPeelFirst(unsigned Level) const { … } // Returns true if peeling the last iteration from this loop // will break this dependence. bool FullDependence::isPeelLast(unsigned Level) const { … } // Returns true if splitting this loop will break the dependence. bool FullDependence::isSplitable(unsigned Level) const { … } //===----------------------------------------------------------------------===// // DependenceInfo::Constraint methods // If constraint is a point <X, Y>, returns X. // Otherwise assert. const SCEV *DependenceInfo::Constraint::getX() const { … } // If constraint is a point <X, Y>, returns Y. // Otherwise assert. const SCEV *DependenceInfo::Constraint::getY() const { … } // If constraint is a line AX + BY = C, returns A. // Otherwise assert. const SCEV *DependenceInfo::Constraint::getA() const { … } // If constraint is a line AX + BY = C, returns B. // Otherwise assert. const SCEV *DependenceInfo::Constraint::getB() const { … } // If constraint is a line AX + BY = C, returns C. // Otherwise assert. const SCEV *DependenceInfo::Constraint::getC() const { … } // If constraint is a distance, returns D. // Otherwise assert. const SCEV *DependenceInfo::Constraint::getD() const { … } // Returns the loop associated with this constraint. const Loop *DependenceInfo::Constraint::getAssociatedLoop() const { … } void DependenceInfo::Constraint::setPoint(const SCEV *X, const SCEV *Y, const Loop *CurLoop) { … } void DependenceInfo::Constraint::setLine(const SCEV *AA, const SCEV *BB, const SCEV *CC, const Loop *CurLoop) { … } void DependenceInfo::Constraint::setDistance(const SCEV *D, const Loop *CurLoop) { … } void DependenceInfo::Constraint::setEmpty() { … } void DependenceInfo::Constraint::setAny(ScalarEvolution *NewSE) { … } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) // For debugging purposes. Dumps the constraint out to OS. LLVM_DUMP_METHOD void DependenceInfo::Constraint::dump(raw_ostream &OS) const { if (isEmpty()) OS << " Empty\n"; else if (isAny()) OS << " Any\n"; else if (isPoint()) OS << " Point is <" << *getX() << ", " << *getY() << ">\n"; else if (isDistance()) OS << " Distance is " << *getD() << " (" << *getA() << "*X + " << *getB() << "*Y = " << *getC() << ")\n"; else if (isLine()) OS << " Line is " << *getA() << "*X + " << *getB() << "*Y = " << *getC() << "\n"; else llvm_unreachable("unknown constraint type in Constraint::dump"); } #endif // Updates X with the intersection // of the Constraints X and Y. Returns true if X has changed. // Corresponds to Figure 4 from the paper // // Practical Dependence Testing // Goff, Kennedy, Tseng // PLDI 1991 bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) { … } //===----------------------------------------------------------------------===// // DependenceInfo methods // For debugging purposes. Dumps a dependence to OS. void Dependence::dump(raw_ostream &OS) const { … } // Returns NoAlias/MayAliass/MustAlias for two memory locations based upon their // underlaying objects. If LocA and LocB are known to not alias (for any reason: // tbaa, non-overlapping regions etc), then it is known there is no dependecy. // Otherwise the underlying objects are checked to see if they point to // different identifiable objects. static AliasResult underlyingObjectsAlias(AAResults *AA, const DataLayout &DL, const MemoryLocation &LocA, const MemoryLocation &LocB) { … } // Returns true if the load or store can be analyzed. Atomic and volatile // operations have properties which this analysis does not understand. static bool isLoadOrStore(const Instruction *I) { … } // Examines the loop nesting of the Src and Dst // instructions and establishes their shared loops. Sets the variables // CommonLevels, SrcLevels, and MaxLevels. // The source and destination instructions needn't be contained in the same // loop. The routine establishNestingLevels finds the level of most deeply // nested loop that contains them both, CommonLevels. An instruction that's // not contained in a loop is at level = 0. MaxLevels is equal to the level // of the source plus the level of the destination, minus CommonLevels. // This lets us allocate vectors MaxLevels in length, with room for every // distinct loop referenced in both the source and destination subscripts. // The variable SrcLevels is the nesting depth of the source instruction. // It's used to help calculate distinct loops referenced by the destination. // Here's the map from loops to levels: // 0 - unused // 1 - outermost common loop // ... - other common loops // CommonLevels - innermost common loop // ... - loops containing Src but not Dst // SrcLevels - innermost loop containing Src but not Dst // ... - loops containing Dst but not Src // MaxLevels - innermost loops containing Dst but not Src // Consider the follow code fragment: // for (a = ...) { // for (b = ...) { // for (c = ...) { // for (d = ...) { // A[] = ...; // } // } // for (e = ...) { // for (f = ...) { // for (g = ...) { // ... = A[]; // } // } // } // } // } // If we're looking at the possibility of a dependence between the store // to A (the Src) and the load from A (the Dst), we'll note that they // have 2 loops in common, so CommonLevels will equal 2 and the direction // vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7. // A map from loop names to loop numbers would look like // a - 1 // b - 2 = CommonLevels // c - 3 // d - 4 = SrcLevels // e - 5 // f - 6 // g - 7 = MaxLevels void DependenceInfo::establishNestingLevels(const Instruction *Src, const Instruction *Dst) { … } // Given one of the loops containing the source, return // its level index in our numbering scheme. unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const { … } // Given one of the loops containing the destination, // return its level index in our numbering scheme. unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const { … } // Returns true if Expression is loop invariant in LoopNest. bool DependenceInfo::isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const { … } // Finds the set of loops from the LoopNest that // have a level <= CommonLevels and are referred to by the SCEV Expression. void DependenceInfo::collectCommonLoops(const SCEV *Expression, const Loop *LoopNest, SmallBitVector &Loops) const { … } void DependenceInfo::unifySubscriptType(ArrayRef<Subscript *> Pairs) { … } // removeMatchingExtensions - Examines a subscript pair. // If the source and destination are identically sign (or zero) // extended, it strips off the extension in an effect to simplify // the actual analysis. void DependenceInfo::removeMatchingExtensions(Subscript *Pair) { … } // Examine the scev and return true iff it's affine. // Collect any loops mentioned in the set of "Loops". bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest, SmallBitVector &Loops, bool IsSrc) { … } // Examine the scev and return true iff it's linear. // Collect any loops mentioned in the set of "Loops". bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest, SmallBitVector &Loops) { … } // Examine the scev and return true iff it's linear. // Collect any loops mentioned in the set of "Loops". bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest, SmallBitVector &Loops) { … } // Examines the subscript pair (the Src and Dst SCEVs) // and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. // Collects the associated loops in a set. DependenceInfo::Subscript::ClassificationKind DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest, const SCEV *Dst, const Loop *DstLoopNest, SmallBitVector &Loops) { … } // A wrapper around SCEV::isKnownPredicate. // Looks for cases where we're interested in comparing for equality. // If both X and Y have been identically sign or zero extended, // it strips off the (confusing) extensions before invoking // SCEV::isKnownPredicate. Perhaps, someday, the ScalarEvolution package // will be similarly updated. // // If SCEV::isKnownPredicate can't prove the predicate, // we try simple subtraction, which seems to help in some cases // involving symbolics. bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X, const SCEV *Y) const { … } /// Compare to see if S is less than Size, using isKnownNegative(S - max(Size, 1)) /// with some extra checking if S is an AddRec and we can prove less-than using /// the loop bounds. bool DependenceInfo::isKnownLessThan(const SCEV *S, const SCEV *Size) const { … } bool DependenceInfo::isKnownNonNegative(const SCEV *S, const Value *Ptr) const { … } // All subscripts are all the same type. // Loop bound may be smaller (e.g., a char). // Should zero extend loop bound, since it's always >= 0. // This routine collects upper bound and extends or truncates if needed. // Truncating is safe when subscripts are known not to wrap. Cases without // nowrap flags should have been rejected earlier. // Return null if no bound available. const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const { … } // Calls collectUpperBound(), then attempts to cast it to SCEVConstant. // If the cast fails, returns NULL. const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L, Type *T) const { … } // testZIV - // When we have a pair of subscripts of the form [c1] and [c2], // where c1 and c2 are both loop invariant, we attack it using // the ZIV test. Basically, we test by comparing the two values, // but there are actually three possible results: // 1) the values are equal, so there's a dependence // 2) the values are different, so there's no dependence // 3) the values might be equal, so we have to assume a dependence. // // Return true if dependence disproved. bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const { … } // strongSIVtest - // From the paper, Practical Dependence Testing, Section 4.2.1 // // When we have a pair of subscripts of the form [c1 + a*i] and [c2 + a*i], // where i is an induction variable, c1 and c2 are loop invariant, // and a is a constant, we can solve it exactly using the Strong SIV test. // // Can prove independence. Failing that, can compute distance (and direction). // In the presence of symbolic terms, we can sometimes make progress. // // If there's a dependence, // // c1 + a*i = c2 + a*i' // // The dependence distance is // // d = i' - i = (c1 - c2)/a // // A dependence only exists if d is an integer and abs(d) <= U, where U is the // loop's upper bound. If a dependence exists, the dependence direction is // defined as // // { < if d > 0 // direction = { = if d = 0 // { > if d < 0 // // Return true if dependence disproved. bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *CurLoop, unsigned Level, FullDependence &Result, Constraint &NewConstraint) const { … } // weakCrossingSIVtest - // From the paper, Practical Dependence Testing, Section 4.2.2 // // When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i], // where i is an induction variable, c1 and c2 are loop invariant, // and a is a constant, we can solve it exactly using the // Weak-Crossing SIV test. // // Given c1 + a*i = c2 - a*i', we can look for the intersection of // the two lines, where i = i', yielding // // c1 + a*i = c2 - a*i // 2a*i = c2 - c1 // i = (c2 - c1)/2a // // If i < 0, there is no dependence. // If i > upperbound, there is no dependence. // If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0. // If i = upperbound, there's a dependence with distance = 0. // If i is integral, there's a dependence (all directions). // If the non-integer part = 1/2, there's a dependence (<> directions). // Otherwise, there's no dependence. // // Can prove independence. Failing that, // can sometimes refine the directions. // Can determine iteration for splitting. // // Return true if dependence disproved. bool DependenceInfo::weakCrossingSIVtest( const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *CurLoop, unsigned Level, FullDependence &Result, Constraint &NewConstraint, const SCEV *&SplitIter) const { … } // Kirch's algorithm, from // // Optimizing Supercompilers for Supercomputers // Michael Wolfe // MIT Press, 1989 // // Program 2.1, page 29. // Computes the GCD of AM and BM. // Also finds a solution to the equation ax - by = gcd(a, b). // Returns true if dependence disproved; i.e., gcd does not divide Delta. static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM, const APInt &Delta, APInt &G, APInt &X, APInt &Y) { … } static APInt floorOfQuotient(const APInt &A, const APInt &B) { … } static APInt ceilingOfQuotient(const APInt &A, const APInt &B) { … } // exactSIVtest - // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*i], // where i is an induction variable, c1 and c2 are loop invariant, and a1 // and a2 are constant, we can solve it exactly using an algorithm developed // by Banerjee and Wolfe. See Algorithm 6.2.1 (case 2.5) in: // // Dependence Analysis for Supercomputing // Utpal Banerjee // Kluwer Academic Publishers, 1988 // // It's slower than the specialized tests (strong SIV, weak-zero SIV, etc), // so use them if possible. They're also a bit better with symbolics and, // in the case of the strong SIV test, can compute Distances. // // Return true if dependence disproved. // // This is a modified version of the original Banerjee algorithm. The original // only tested whether Dst depends on Src. This algorithm extends that and // returns all the dependencies that exist between Dst and Src. bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *CurLoop, unsigned Level, FullDependence &Result, Constraint &NewConstraint) const { … } // Return true if the divisor evenly divides the dividend. static bool isRemainderZero(const SCEVConstant *Dividend, const SCEVConstant *Divisor) { … } // weakZeroSrcSIVtest - // From the paper, Practical Dependence Testing, Section 4.2.2 // // When we have a pair of subscripts of the form [c1] and [c2 + a*i], // where i is an induction variable, c1 and c2 are loop invariant, // and a is a constant, we can solve it exactly using the // Weak-Zero SIV test. // // Given // // c1 = c2 + a*i // // we get // // (c1 - c2)/a = i // // If i is not an integer, there's no dependence. // If i < 0 or > UB, there's no dependence. // If i = 0, the direction is >= and peeling the // 1st iteration will break the dependence. // If i = UB, the direction is <= and peeling the // last iteration will break the dependence. // Otherwise, the direction is *. // // Can prove independence. Failing that, we can sometimes refine // the directions. Can sometimes show that first or last // iteration carries all the dependences (so worth peeling). // // (see also weakZeroDstSIVtest) // // Return true if dependence disproved. bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *CurLoop, unsigned Level, FullDependence &Result, Constraint &NewConstraint) const { … } // weakZeroDstSIVtest - // From the paper, Practical Dependence Testing, Section 4.2.2 // // When we have a pair of subscripts of the form [c1 + a*i] and [c2], // where i is an induction variable, c1 and c2 are loop invariant, // and a is a constant, we can solve it exactly using the // Weak-Zero SIV test. // // Given // // c1 + a*i = c2 // // we get // // i = (c2 - c1)/a // // If i is not an integer, there's no dependence. // If i < 0 or > UB, there's no dependence. // If i = 0, the direction is <= and peeling the // 1st iteration will break the dependence. // If i = UB, the direction is >= and peeling the // last iteration will break the dependence. // Otherwise, the direction is *. // // Can prove independence. Failing that, we can sometimes refine // the directions. Can sometimes show that first or last // iteration carries all the dependences (so worth peeling). // // (see also weakZeroSrcSIVtest) // // Return true if dependence disproved. bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *CurLoop, unsigned Level, FullDependence &Result, Constraint &NewConstraint) const { … } // exactRDIVtest - Tests the RDIV subscript pair for dependence. // Things of the form [c1 + a*i] and [c2 + b*j], // where i and j are induction variable, c1 and c2 are loop invariant, // and a and b are constants. // Returns true if any possible dependence is disproved. // Marks the result as inconsistent. // Works in some cases that symbolicRDIVtest doesn't, and vice versa. bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *SrcLoop, const Loop *DstLoop, FullDependence &Result) const { … } // symbolicRDIVtest - // In Section 4.5 of the Practical Dependence Testing paper,the authors // introduce a special case of Banerjee's Inequalities (also called the // Extreme-Value Test) that can handle some of the SIV and RDIV cases, // particularly cases with symbolics. Since it's only able to disprove // dependence (not compute distances or directions), we'll use it as a // fall back for the other tests. // // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j] // where i and j are induction variables and c1 and c2 are loop invariants, // we can use the symbolic tests to disprove some dependences, serving as a // backup for the RDIV test. Note that i and j can be the same variable, // letting this test serve as a backup for the various SIV tests. // // For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some // 0 <= i <= N1 and some 0 <= j <= N2, where N1 and N2 are the (normalized) // loop bounds for the i and j loops, respectively. So, ... // // c1 + a1*i = c2 + a2*j // a1*i - a2*j = c2 - c1 // // To test for a dependence, we compute c2 - c1 and make sure it's in the // range of the maximum and minimum possible values of a1*i - a2*j. // Considering the signs of a1 and a2, we have 4 possible cases: // // 1) If a1 >= 0 and a2 >= 0, then // a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*0 // -a2*N2 <= c2 - c1 <= a1*N1 // // 2) If a1 >= 0 and a2 <= 0, then // a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N2 // 0 <= c2 - c1 <= a1*N1 - a2*N2 // // 3) If a1 <= 0 and a2 >= 0, then // a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0 // a1*N1 - a2*N2 <= c2 - c1 <= 0 // // 4) If a1 <= 0 and a2 <= 0, then // a1*N1 - a2*0 <= c2 - c1 <= a1*0 - a2*N2 // a1*N1 <= c2 - c1 <= -a2*N2 // // return true if dependence disproved bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2, const SCEV *C1, const SCEV *C2, const Loop *Loop1, const Loop *Loop2) const { … } // testSIV - // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i] // where i is an induction variable, c1 and c2 are loop invariant, and a1 and // a2 are constant, we attack it with an SIV test. While they can all be // solved with the Exact SIV test, it's worthwhile to use simpler tests when // they apply; they're cheaper and sometimes more precise. // // Return true if dependence disproved. bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level, FullDependence &Result, Constraint &NewConstraint, const SCEV *&SplitIter) const { … } // testRDIV - // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j] // where i and j are induction variables, c1 and c2 are loop invariant, // and a1 and a2 are constant, we can solve it exactly with an easy adaptation // of the Exact SIV test, the Restricted Double Index Variable (RDIV) test. // It doesn't make sense to talk about distance or direction in this case, // so there's no point in making special versions of the Strong SIV test or // the Weak-crossing SIV test. // // With minor algebra, this test can also be used for things like // [c1 + a1*i + a2*j][c2]. // // Return true if dependence disproved. bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const { … } // Tests the single-subscript MIV pair (Src and Dst) for dependence. // Return true if dependence disproved. // Can sometimes refine direction vectors. bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst, const SmallBitVector &Loops, FullDependence &Result) const { … } // Given a product, e.g., 10*X*Y, returns the first constant operand, // in this case 10. If there is no constant part, returns NULL. static const SCEVConstant *getConstantPart(const SCEV *Expr) { … } //===----------------------------------------------------------------------===// // gcdMIVtest - // Tests an MIV subscript pair for dependence. // Returns true if any possible dependence is disproved. // Marks the result as inconsistent. // Can sometimes disprove the equal direction for 1 or more loops, // as discussed in Michael Wolfe's book, // High Performance Compilers for Parallel Computing, page 235. // // We spend some effort (code!) to handle cases like // [10*i + 5*N*j + 15*M + 6], where i and j are induction variables, // but M and N are just loop-invariant variables. // This should help us handle linearized subscripts; // also makes this test a useful backup to the various SIV tests. // // It occurs to me that the presence of loop-invariant variables // changes the nature of the test from "greatest common divisor" // to "a common divisor". bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const { … } //===----------------------------------------------------------------------===// // banerjeeMIVtest - // Use Banerjee's Inequalities to test an MIV subscript pair. // (Wolfe, in the race-car book, calls this the Extreme Value Test.) // Generally follows the discussion in Section 2.5.2 of // // Optimizing Supercompilers for Supercomputers // Michael Wolfe // // The inequalities given on page 25 are simplified in that loops are // normalized so that the lower bound is always 0 and the stride is always 1. // For example, Wolfe gives // // LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k // // where A_k is the coefficient of the kth index in the source subscript, // B_k is the coefficient of the kth index in the destination subscript, // U_k is the upper bound of the kth index, L_k is the lower bound of the Kth // index, and N_k is the stride of the kth index. Since all loops are normalized // by the SCEV package, N_k = 1 and L_k = 0, allowing us to simplify the // equation to // // LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 1 // = (A^-_k - B_k)^- (U_k - 1) - B_k // // Similar simplifications are possible for the other equations. // // When we can't determine the number of iterations for a loop, // we use NULL as an indicator for the worst case, infinity. // When computing the upper bound, NULL denotes +inf; // for the lower bound, NULL denotes -inf. // // Return true if dependence disproved. bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst, const SmallBitVector &Loops, FullDependence &Result) const { … } // Hierarchically expands the direction vector // search space, combining the directions of discovered dependences // in the DirSet field of Bound. Returns the number of distinct // dependences discovered. If the dependence is disproved, // it will return 0. unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, const SmallBitVector &Loops, unsigned &DepthExpanded, const SCEV *Delta) const { … } // Returns true iff the current bounds are plausible. bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level, BoundInfo *Bound, const SCEV *Delta) const { … } // Computes the upper and lower bounds for level K // using the * direction. Records them in Bound. // Wolfe gives the equations // // LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k // UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k // // Since we normalize loops, we can simplify these equations to // // LB^*_k = (A^-_k - B^+_k)U_k // UB^*_k = (A^+_k - B^-_k)U_k // // We must be careful to handle the case where the upper bound is unknown. // Note that the lower bound is always <= 0 // and the upper bound is always >= 0. void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { … } // Computes the upper and lower bounds for level K // using the = direction. Records them in Bound. // Wolfe gives the equations // // LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k // UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k // // Since we normalize loops, we can simplify these equations to // // LB^=_k = (A_k - B_k)^- U_k // UB^=_k = (A_k - B_k)^+ U_k // // We must be careful to handle the case where the upper bound is unknown. // Note that the lower bound is always <= 0 // and the upper bound is always >= 0. void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { … } // Computes the upper and lower bounds for level K // using the < direction. Records them in Bound. // Wolfe gives the equations // // LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k // UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k // // Since we normalize loops, we can simplify these equations to // // LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k // UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k // // We must be careful to handle the case where the upper bound is unknown. void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { … } // Computes the upper and lower bounds for level K // using the > direction. Records them in Bound. // Wolfe gives the equations // // LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k // UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k // // Since we normalize loops, we can simplify these equations to // // LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k // UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k // // We must be careful to handle the case where the upper bound is unknown. void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { … } // X^+ = max(X, 0) const SCEV *DependenceInfo::getPositivePart(const SCEV *X) const { … } // X^- = min(X, 0) const SCEV *DependenceInfo::getNegativePart(const SCEV *X) const { … } // Walks through the subscript, // collecting each coefficient, the associated loop bounds, // and recording its positive and negative parts for later use. DependenceInfo::CoefficientInfo * DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag, const SCEV *&Constant) const { … } // Looks through all the bounds info and // computes the lower bound given the current direction settings // at each level. If the lower bound for any level is -inf, // the result is -inf. const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const { … } // Looks through all the bounds info and // computes the upper bound given the current direction settings // at each level. If the upper bound at any level is +inf, // the result is +inf. const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const { … } //===----------------------------------------------------------------------===// // Constraint manipulation for Delta test. // Given a linear SCEV, // return the coefficient (the step) // corresponding to the specified loop. // If there isn't one, return 0. // For example, given a*i + b*j + c*k, finding the coefficient // corresponding to the j loop would yield b. const SCEV *DependenceInfo::findCoefficient(const SCEV *Expr, const Loop *TargetLoop) const { … } // Given a linear SCEV, // return the SCEV given by zeroing out the coefficient // corresponding to the specified loop. // For example, given a*i + b*j + c*k, zeroing the coefficient // corresponding to the j loop would yield a*i + c*k. const SCEV *DependenceInfo::zeroCoefficient(const SCEV *Expr, const Loop *TargetLoop) const { … } // Given a linear SCEV Expr, // return the SCEV given by adding some Value to the // coefficient corresponding to the specified TargetLoop. // For example, given a*i + b*j + c*k, adding 1 to the coefficient // corresponding to the j loop would yield a*i + (b+1)*j + c*k. const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr, const Loop *TargetLoop, const SCEV *Value) const { … } // Review the constraints, looking for opportunities // to simplify a subscript pair (Src and Dst). // Return true if some simplification occurs. // If the simplification isn't exact (that is, if it is conservative // in terms of dependence), set consistent to false. // Corresponds to Figure 5 from the paper // // Practical Dependence Testing // Goff, Kennedy, Tseng // PLDI 1991 bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst, SmallBitVector &Loops, SmallVectorImpl<Constraint> &Constraints, bool &Consistent) { … } // Attempt to propagate a distance // constraint into a subscript pair (Src and Dst). // Return true if some simplification occurs. // If the simplification isn't exact (that is, if it is conservative // in terms of dependence), set consistent to false. bool DependenceInfo::propagateDistance(const SCEV *&Src, const SCEV *&Dst, Constraint &CurConstraint, bool &Consistent) { … } // Attempt to propagate a line // constraint into a subscript pair (Src and Dst). // Return true if some simplification occurs. // If the simplification isn't exact (that is, if it is conservative // in terms of dependence), set consistent to false. bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst, Constraint &CurConstraint, bool &Consistent) { … } // Attempt to propagate a point // constraint into a subscript pair (Src and Dst). // Return true if some simplification occurs. bool DependenceInfo::propagatePoint(const SCEV *&Src, const SCEV *&Dst, Constraint &CurConstraint) { … } // Update direction vector entry based on the current constraint. void DependenceInfo::updateDirection(Dependence::DVEntry &Level, const Constraint &CurConstraint) const { … } /// Check if we can delinearize the subscripts. If the SCEVs representing the /// source and destination array references are recurrences on a nested loop, /// this function flattens the nested recurrences into separate recurrences /// for each loop level. bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst, SmallVectorImpl<Subscript> &Pair) { … } /// Try to delinearize \p SrcAccessFn and \p DstAccessFn if the underlying /// arrays accessed are fixed-size arrays. Return true if delinearization was /// successful. bool DependenceInfo::tryDelinearizeFixedSize( Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn, const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts, SmallVectorImpl<const SCEV *> &DstSubscripts) { … } bool DependenceInfo::tryDelinearizeParametricSize( Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn, const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts, SmallVectorImpl<const SCEV *> &DstSubscripts) { … } //===----------------------------------------------------------------------===// #ifndef NDEBUG // For debugging purposes, dump a small bit vector to dbgs(). static void dumpSmallBitVector(SmallBitVector &BV) { dbgs() << "{"; for (unsigned VI : BV.set_bits()) { dbgs() << VI; if (BV.find_next(VI) >= 0) dbgs() << ' '; } dbgs() << "}\n"; } #endif bool DependenceInfo::invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv) { … } // depends - // Returns NULL if there is no dependence. // Otherwise, return a Dependence with as many details as possible. // Corresponds to Section 3.1 in the paper // // Practical Dependence Testing // Goff, Kennedy, Tseng // PLDI 1991 // // Care is required to keep the routine below, getSplitIteration(), // up to date with respect to this routine. std::unique_ptr<Dependence> DependenceInfo::depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent) { … } //===----------------------------------------------------------------------===// // getSplitIteration - // Rather than spend rarely-used space recording the splitting iteration // during the Weak-Crossing SIV test, we re-compute it on demand. // The re-computation is basically a repeat of the entire dependence test, // though simplified since we know that the dependence exists. // It's tedious, since we must go through all propagations, etc. // // Care is required to keep this code up to date with respect to the routine // above, depends(). // // Generally, the dependence analyzer will be used to build // a dependence graph for a function (basically a map from instructions // to dependences). Looking for cycles in the graph shows us loops // that cannot be trivially vectorized/parallelized. // // We can try to improve the situation by examining all the dependences // that make up the cycle, looking for ones we can break. // Sometimes, peeling the first or last iteration of a loop will break // dependences, and we've got flags for those possibilities. // Sometimes, splitting a loop at some other iteration will do the trick, // and we've got a flag for that case. Rather than waste the space to // record the exact iteration (since we rarely know), we provide // a method that calculates the iteration. It's a drag that it must work // from scratch, but wonderful in that it's possible. // // Here's an example: // // for (i = 0; i < 10; i++) // A[i] = ... // ... = A[11 - i] // // There's a loop-carried flow dependence from the store to the load, // found by the weak-crossing SIV test. The dependence will have a flag, // indicating that the dependence can be broken by splitting the loop. // Calling getSplitIteration will return 5. // Splitting the loop breaks the dependence, like so: // // for (i = 0; i <= 5; i++) // A[i] = ... // ... = A[11 - i] // for (i = 6; i < 10; i++) // A[i] = ... // ... = A[11 - i] // // breaks the dependence and allows us to vectorize/parallelize // both loops. const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep, unsigned SplitLevel) { … }
Codebase Browser
llvm