Index: include/llvm/Analysis/DependenceAnalysis.h =================================================================== --- include/llvm/Analysis/DependenceAnalysis.h +++ include/llvm/Analysis/DependenceAnalysis.h @@ -206,7 +206,7 @@ private: Instruction *Src, *Dst; const Dependence *NextPredecessor, *NextSuccessor; - friend class DependenceAnalysis; + friend class DependenceInfo; }; /// FullDependence - This class represents a dependence between two memory @@ -274,16 +274,17 @@ bool LoopIndependent; bool Consistent; // Init to true, then refine. std::unique_ptr DV; - friend class DependenceAnalysis; + friend class DependenceInfo; }; - /// DependenceAnalysis - This class is the main dependence-analysis driver. + /// DependenceInfo - This class is the main dependence-analysis driver. /// - class DependenceAnalysis : public FunctionPass { - void operator=(const DependenceAnalysis &) = delete; - DependenceAnalysis(const DependenceAnalysis &) = delete; - + class DependenceInfo { public: + DependenceInfo(Function *F, AliasAnalysis *AA, ScalarEvolution *SE, + LoopInfo *LI) + : AA(AA), SE(SE), LI(LI), F(F) {} + /// depends - Tests for a dependence between the Src and Dst instructions. /// Returns NULL if no dependence; otherwise, returns a Dependence (or a /// FullDependence) with as much information as can be gleaned. @@ -336,6 +337,8 @@ /// both loops. const SCEV *getSplitIteration(const Dependence &Dep, unsigned Level); + Function *getFunction() const { return F; } + private: AliasAnalysis *AA; ScalarEvolution *SE; @@ -919,22 +922,36 @@ bool tryDelinearize(Instruction *Src, Instruction *Dst, SmallVectorImpl &Pair); + }; // class DependenceInfo + + /// \brief AnalysisPass to compute dependence information in a function + struct DependenceAnalysis : public AnalysisInfoMixin { + static char PassID; + typedef DependenceInfo Result; + Result run(Function &F, FunctionAnalysisManager &FAM); + }; // class DependenceAnalysis + /// \brief Legacy pass manager pass to access dependence information + class DependenceAnalysisWrapperPass : public FunctionPass { public: static char ID; // Class identification, replacement for typeinfo - DependenceAnalysis() : FunctionPass(ID) { - initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry()); + DependenceAnalysisWrapperPass() : FunctionPass(ID) { + initializeDependenceAnalysisWrapperPassPass(*PassRegistry::getPassRegistry()); } bool runOnFunction(Function &F) override; void releaseMemory() override; void getAnalysisUsage(AnalysisUsage &) const override; void print(raw_ostream &, const Module * = nullptr) const override; - }; // class DependenceAnalysis + DependenceInfo &getDI() const; + + private: + std::unique_ptr info; + }; // class DependenceAnalysisWrapperPass /// createDependenceAnalysisPass - This creates an instance of the - /// DependenceAnalysis pass. - FunctionPass *createDependenceAnalysisPass(); + /// DependenceAnalysis wrapper pass. + FunctionPass *createDependenceAnalysisWrapperPass(); } // namespace llvm Index: include/llvm/Analysis/Passes.h =================================================================== --- include/llvm/Analysis/Passes.h +++ include/llvm/Analysis/Passes.h @@ -40,10 +40,10 @@ //===--------------------------------------------------------------------===// // - // createDependenceAnalysisPass - This creates an instance of the - // DependenceAnalysis pass. + // createDependenceAnalysisWrapperPass - This creates an instance of the + // DependenceAnalysisWrapper pass. // - FunctionPass *createDependenceAnalysisPass(); + FunctionPass *createDependenceAnalysisWrapperPass(); //===--------------------------------------------------------------------===// // Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -109,7 +109,7 @@ void initializeDeadInstEliminationPass(PassRegistry&); void initializeDeadMachineInstructionElimPass(PassRegistry&); void initializeDelinearizationPass(PassRegistry &); -void initializeDependenceAnalysisPass(PassRegistry&); +void initializeDependenceAnalysisWrapperPassPass(PassRegistry&); void initializeDivergenceAnalysisPass(PassRegistry&); void initializeDomOnlyPrinterPass(PassRegistry&); void initializeDomOnlyViewerPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -82,7 +82,7 @@ (void) llvm::createDeadCodeEliminationPass(); (void) llvm::createDeadInstEliminationPass(); (void) llvm::createDeadStoreEliminationPass(); - (void) llvm::createDependenceAnalysisPass(); + (void) llvm::createDependenceAnalysisWrapperPass(); (void) llvm::createDivergenceAnalysisPass(); (void) llvm::createDomOnlyPrinterPass(); (void) llvm::createDomPrinterPass(); Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -35,7 +35,7 @@ initializeCFGOnlyViewerPass(Registry); initializeCFGOnlyPrinterPass(Registry); initializeCFLAAWrapperPassPass(Registry); - initializeDependenceAnalysisPass(Registry); + initializeDependenceAnalysisWrapperPassPass(Registry); initializeDelinearizationPass(Registry); initializeDemandedBitsPass(Registry); initializeDivergenceAnalysisPass(Registry); Index: lib/Analysis/DependenceAnalysis.cpp =================================================================== --- lib/Analysis/DependenceAnalysis.cpp +++ lib/Analysis/DependenceAnalysis.cpp @@ -114,36 +114,51 @@ //===----------------------------------------------------------------------===// // basics -INITIALIZE_PASS_BEGIN(DependenceAnalysis, "da", +DependenceAnalysis::Result DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { + auto &AA = FAM.getResult(F); + auto &SE = FAM.getResult(F); + auto &LI = FAM.getResult(F); + return DependenceInfo(&F, &AA, &SE, &LI); +} + +char DependenceAnalysis::PassID; + +INITIALIZE_PASS_BEGIN(DependenceAnalysisWrapperPass, "da", "Dependence Analysis", true, true) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) -INITIALIZE_PASS_END(DependenceAnalysis, "da", +INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis", true, true) -char DependenceAnalysis::ID = 0; +char DependenceAnalysisWrapperPass::ID = 0; -FunctionPass *llvm::createDependenceAnalysisPass() { - return new DependenceAnalysis(); +FunctionPass *llvm::createDependenceAnalysisWrapperPass() { + return new DependenceAnalysisWrapperPass(); } -bool DependenceAnalysis::runOnFunction(Function &F) { - this->F = &F; - AA = &getAnalysis().getAAResults(); - SE = &getAnalysis().getSE(); - LI = &getAnalysis().getLoopInfo(); +bool DependenceAnalysisWrapperPass::runOnFunction(Function &F) { + auto &AA = getAnalysis().getAAResults(); + auto &SE = getAnalysis().getSE(); + auto &LI = getAnalysis().getLoopInfo(); + info.reset(new DependenceInfo(&F, &AA, &SE, &LI)); return false; } -void DependenceAnalysis::releaseMemory() { +DependenceInfo &DependenceAnalysisWrapperPass::getDI() const { + assert(info && "Pass has not been run"); + return *info; } -void DependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { +void DependenceAnalysisWrapperPass::releaseMemory() { +} + + +void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequiredTransitive(); AU.addRequiredTransitive(); @@ -155,13 +170,12 @@ // Looks through the function, noting loads and stores. // Calls depends() on every possible pair and prints out the result. // Ignores all other instructions. -static -void dumpExampleDependence(raw_ostream &OS, Function *F, - DependenceAnalysis *DA) { - for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); +static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) { + for (inst_iterator SrcI = inst_begin(DA->getFunction()), + SrcE = inst_end(DA->getFunction()); SrcI != SrcE; ++SrcI) { if (isa(*SrcI) || isa(*SrcI)) { - for (inst_iterator DstI = SrcI, DstE = inst_end(F); + for (inst_iterator DstI = SrcI, DstE = inst_end(DA->getFunction()); DstI != DstE; ++DstI) { if (isa(*DstI) || isa(*DstI)) { OS << "da analyze - "; @@ -184,8 +198,9 @@ } -void DependenceAnalysis::print(raw_ostream &OS, const Module*) const { - dumpExampleDependence(OS, F, const_cast(this)); +void DependenceAnalysisWrapperPass::print(raw_ostream &OS, const Module*) const { + if (info) + dumpExampleDependence(OS, info.get()); } //===----------------------------------------------------------------------===// @@ -286,11 +301,11 @@ //===----------------------------------------------------------------------===// -// DependenceAnalysis::Constraint methods +// DependenceInfo::Constraint methods // If constraint is a point , returns X. // Otherwise assert. -const SCEV *DependenceAnalysis::Constraint::getX() const { +const SCEV *DependenceInfo::Constraint::getX() const { assert(Kind == Point && "Kind should be Point"); return A; } @@ -298,7 +313,7 @@ // If constraint is a point , returns Y. // Otherwise assert. -const SCEV *DependenceAnalysis::Constraint::getY() const { +const SCEV *DependenceInfo::Constraint::getY() const { assert(Kind == Point && "Kind should be Point"); return B; } @@ -306,7 +321,7 @@ // If constraint is a line AX + BY = C, returns A. // Otherwise assert. -const SCEV *DependenceAnalysis::Constraint::getA() const { +const SCEV *DependenceInfo::Constraint::getA() const { assert((Kind == Line || Kind == Distance) && "Kind should be Line (or Distance)"); return A; @@ -315,7 +330,7 @@ // If constraint is a line AX + BY = C, returns B. // Otherwise assert. -const SCEV *DependenceAnalysis::Constraint::getB() const { +const SCEV *DependenceInfo::Constraint::getB() const { assert((Kind == Line || Kind == Distance) && "Kind should be Line (or Distance)"); return B; @@ -324,7 +339,7 @@ // If constraint is a line AX + BY = C, returns C. // Otherwise assert. -const SCEV *DependenceAnalysis::Constraint::getC() const { +const SCEV *DependenceInfo::Constraint::getC() const { assert((Kind == Line || Kind == Distance) && "Kind should be Line (or Distance)"); return C; @@ -333,21 +348,21 @@ // If constraint is a distance, returns D. // Otherwise assert. -const SCEV *DependenceAnalysis::Constraint::getD() const { +const SCEV *DependenceInfo::Constraint::getD() const { assert(Kind == Distance && "Kind should be Distance"); return SE->getNegativeSCEV(C); } // Returns the loop associated with this constraint. -const Loop *DependenceAnalysis::Constraint::getAssociatedLoop() const { +const Loop *DependenceInfo::Constraint::getAssociatedLoop() const { assert((Kind == Distance || Kind == Line || Kind == Point) && "Kind should be Distance, Line, or Point"); return AssociatedLoop; } -void DependenceAnalysis::Constraint::setPoint(const SCEV *X, +void DependenceInfo::Constraint::setPoint(const SCEV *X, const SCEV *Y, const Loop *CurLoop) { Kind = Point; @@ -357,7 +372,7 @@ } -void DependenceAnalysis::Constraint::setLine(const SCEV *AA, +void DependenceInfo::Constraint::setLine(const SCEV *AA, const SCEV *BB, const SCEV *CC, const Loop *CurLoop) { @@ -369,7 +384,7 @@ } -void DependenceAnalysis::Constraint::setDistance(const SCEV *D, +void DependenceInfo::Constraint::setDistance(const SCEV *D, const Loop *CurLoop) { Kind = Distance; A = SE->getOne(D->getType()); @@ -379,19 +394,19 @@ } -void DependenceAnalysis::Constraint::setEmpty() { +void DependenceInfo::Constraint::setEmpty() { Kind = Empty; } -void DependenceAnalysis::Constraint::setAny(ScalarEvolution *NewSE) { +void DependenceInfo::Constraint::setAny(ScalarEvolution *NewSE) { SE = NewSE; Kind = Any; } // For debugging purposes. Dumps the constraint out to OS. -void DependenceAnalysis::Constraint::dump(raw_ostream &OS) const { +void DependenceInfo::Constraint::dump(raw_ostream &OS) const { if (isEmpty()) OS << " Empty\n"; else if (isAny()) @@ -416,7 +431,7 @@ // Practical Dependence Testing // Goff, Kennedy, Tseng // PLDI 1991 -bool DependenceAnalysis::intersectConstraints(Constraint *X, +bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) { ++DeltaApplications; DEBUG(dbgs() << "\tintersect constraints\n"); @@ -569,7 +584,7 @@ //===----------------------------------------------------------------------===// -// DependenceAnalysis methods +// DependenceInfo methods // For debugging purposes. Dumps a dependence to OS. void Dependence::dump(raw_ostream &OS) const { @@ -709,7 +724,7 @@ // e - 5 // f - 6 // g - 7 = MaxLevels -void DependenceAnalysis::establishNestingLevels(const Instruction *Src, +void DependenceInfo::establishNestingLevels(const Instruction *Src, const Instruction *Dst) { const BasicBlock *SrcBlock = Src->getParent(); const BasicBlock *DstBlock = Dst->getParent(); @@ -739,14 +754,14 @@ // Given one of the loops containing the source, return // its level index in our numbering scheme. -unsigned DependenceAnalysis::mapSrcLoop(const Loop *SrcLoop) const { +unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const { return SrcLoop->getLoopDepth(); } // Given one of the loops containing the destination, // return its level index in our numbering scheme. -unsigned DependenceAnalysis::mapDstLoop(const Loop *DstLoop) const { +unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const { unsigned D = DstLoop->getLoopDepth(); if (D > CommonLevels) return D - CommonLevels + SrcLevels; @@ -756,7 +771,7 @@ // Returns true if Expression is loop invariant in LoopNest. -bool DependenceAnalysis::isLoopInvariant(const SCEV *Expression, +bool DependenceInfo::isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const { if (!LoopNest) return true; @@ -768,7 +783,7 @@ // Finds the set of loops from the LoopNest that // have a level <= CommonLevels and are referred to by the SCEV Expression. -void DependenceAnalysis::collectCommonLoops(const SCEV *Expression, +void DependenceInfo::collectCommonLoops(const SCEV *Expression, const Loop *LoopNest, SmallBitVector &Loops) const { while (LoopNest) { @@ -779,7 +794,7 @@ } } -void DependenceAnalysis::unifySubscriptType(ArrayRef Pairs) { +void DependenceInfo::unifySubscriptType(ArrayRef Pairs) { unsigned widestWidthSeen = 0; Type *widestType; @@ -836,7 +851,7 @@ // 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 DependenceAnalysis::removeMatchingExtensions(Subscript *Pair) { +void DependenceInfo::removeMatchingExtensions(Subscript *Pair) { const SCEV *Src = Pair->Src; const SCEV *Dst = Pair->Dst; if ((isa(Src) && isa(Dst)) || @@ -855,7 +870,7 @@ // Examine the scev and return true iff it's linear. // Collect any loops mentioned in the set of "Loops". -bool DependenceAnalysis::checkSrcSubscript(const SCEV *Src, +bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest, SmallBitVector &Loops) { const SCEVAddRecExpr *AddRec = dyn_cast(Src); @@ -881,7 +896,7 @@ // Examine the scev and return true iff it's linear. // Collect any loops mentioned in the set of "Loops". -bool DependenceAnalysis::checkDstSubscript(const SCEV *Dst, +bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest, SmallBitVector &Loops) { const SCEVAddRecExpr *AddRec = dyn_cast(Dst); @@ -907,8 +922,8 @@ // 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. -DependenceAnalysis::Subscript::ClassificationKind -DependenceAnalysis::classifyPair(const SCEV *Src, const Loop *SrcLoopNest, +DependenceInfo::Subscript::ClassificationKind +DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest, const SCEV *Dst, const Loop *DstLoopNest, SmallBitVector &Loops) { SmallBitVector SrcLoops(MaxLevels + 1); @@ -942,7 +957,7 @@ // If SCEV::isKnownPredicate can't prove the predicate, // we try simple subtraction, which seems to help in some cases // involving symbolics. -bool DependenceAnalysis::isKnownPredicate(ICmpInst::Predicate Pred, +bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X, const SCEV *Y) const { if (Pred == CmpInst::ICMP_EQ || @@ -995,7 +1010,7 @@ // 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 *DependenceAnalysis::collectUpperBound(const Loop *L, +const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const { if (SE->hasLoopInvariantBackedgeTakenCount(L)) { const SCEV *UB = SE->getBackedgeTakenCount(L); @@ -1007,7 +1022,7 @@ // Calls collectUpperBound(), then attempts to cast it to SCEVConstant. // If the cast fails, returns NULL. -const SCEVConstant *DependenceAnalysis::collectConstantUpperBound(const Loop *L, +const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L, Type *T ) const { if (const SCEV *UB = collectUpperBound(L, T)) @@ -1026,7 +1041,7 @@ // 3) the values might be equal, so we have to assume a dependence. // // Return true if dependence disproved. -bool DependenceAnalysis::testZIV(const SCEV *Src, +bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const { DEBUG(dbgs() << " src = " << *Src << "\n"); @@ -1074,7 +1089,7 @@ // { > if d < 0 // // Return true if dependence disproved. -bool DependenceAnalysis::strongSIVtest(const SCEV *Coeff, +bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *CurLoop, @@ -1213,7 +1228,7 @@ // Can determine iteration for splitting. // // Return true if dependence disproved. -bool DependenceAnalysis::weakCrossingSIVtest(const SCEV *Coeff, +bool DependenceInfo::weakCrossingSIVtest(const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *CurLoop, @@ -1256,7 +1271,7 @@ } assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive"); - // compute SplitIter for use by DependenceAnalysis::getSplitIteration() + // compute SplitIter for use by DependenceInfo::getSplitIteration() SplitIter = SE->getUDivExpr( SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta), SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff)); @@ -1433,7 +1448,7 @@ // in the case of the strong SIV test, can compute Distances. // // Return true if dependence disproved. -bool DependenceAnalysis::exactSIVtest(const SCEV *SrcCoeff, +bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, const SCEV *SrcConst, const SCEV *DstConst, @@ -1645,7 +1660,7 @@ // (see also weakZeroDstSIVtest) // // Return true if dependence disproved. -bool DependenceAnalysis::weakZeroSrcSIVtest(const SCEV *DstCoeff, +bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *CurLoop, @@ -1756,7 +1771,7 @@ // (see also weakZeroSrcSIVtest) // // Return true if dependence disproved. -bool DependenceAnalysis::weakZeroDstSIVtest(const SCEV *SrcCoeff, +bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff, const SCEV *SrcConst, const SCEV *DstConst, const Loop *CurLoop, @@ -1842,7 +1857,7 @@ // 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 DependenceAnalysis::exactRDIVtest(const SCEV *SrcCoeff, +bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, const SCEV *SrcConst, const SCEV *DstConst, @@ -1986,7 +2001,7 @@ // a1*N1 <= c2 - c1 <= -a2*N2 // // return true if dependence disproved -bool DependenceAnalysis::symbolicRDIVtest(const SCEV *A1, +bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2, const SCEV *C1, const SCEV *C2, @@ -2103,7 +2118,7 @@ // they apply; they're cheaper and sometimes more precise. // // Return true if dependence disproved. -bool DependenceAnalysis::testSIV(const SCEV *Src, +bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level, FullDependence &Result, @@ -2174,7 +2189,7 @@ // [c1 + a1*i + a2*j][c2]. // // Return true if dependence disproved. -bool DependenceAnalysis::testRDIV(const SCEV *Src, +bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const { // we have 3 possible situations here: @@ -2241,7 +2256,7 @@ // Tests the single-subscript MIV pair (Src and Dst) for dependence. // Return true if dependence disproved. // Can sometimes refine direction vectors. -bool DependenceAnalysis::testMIV(const SCEV *Src, +bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst, const SmallBitVector &Loops, FullDependence &Result) const { @@ -2283,7 +2298,7 @@ // 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 DependenceAnalysis::gcdMIVtest(const SCEV *Src, +bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const { DEBUG(dbgs() << "starting gcd\n"); @@ -2503,7 +2518,7 @@ // for the lower bound, NULL denotes -inf. // // Return true if dependence disproved. -bool DependenceAnalysis::banerjeeMIVtest(const SCEV *Src, +bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst, const SmallBitVector &Loops, FullDependence &Result) const { @@ -2584,7 +2599,7 @@ // in the DirSet field of Bound. Returns the number of distinct // dependences discovered. If the dependence is disproved, // it will return 0. -unsigned DependenceAnalysis::exploreDirections(unsigned Level, +unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, @@ -2685,7 +2700,7 @@ // Returns true iff the current bounds are plausible. -bool DependenceAnalysis::testBounds(unsigned char DirKind, +bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level, BoundInfo *Bound, const SCEV *Delta) const { @@ -2715,7 +2730,7 @@ // 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 DependenceAnalysis::findBoundsALL(CoefficientInfo *A, +void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { @@ -2756,7 +2771,7 @@ // 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 DependenceAnalysis::findBoundsEQ(CoefficientInfo *A, +void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { @@ -2798,7 +2813,7 @@ // 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 DependenceAnalysis::findBoundsLT(CoefficientInfo *A, +void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { @@ -2844,7 +2859,7 @@ // 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 DependenceAnalysis::findBoundsGT(CoefficientInfo *A, +void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { @@ -2876,13 +2891,13 @@ // X^+ = max(X, 0) -const SCEV *DependenceAnalysis::getPositivePart(const SCEV *X) const { +const SCEV *DependenceInfo::getPositivePart(const SCEV *X) const { return SE->getSMaxExpr(X, SE->getZero(X->getType())); } // X^- = min(X, 0) -const SCEV *DependenceAnalysis::getNegativePart(const SCEV *X) const { +const SCEV *DependenceInfo::getNegativePart(const SCEV *X) const { return SE->getSMinExpr(X, SE->getZero(X->getType())); } @@ -2890,8 +2905,8 @@ // Walks through the subscript, // collecting each coefficient, the associated loop bounds, // and recording its positive and negative parts for later use. -DependenceAnalysis::CoefficientInfo * -DependenceAnalysis::collectCoeffInfo(const SCEV *Subscript, +DependenceInfo::CoefficientInfo * +DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag, const SCEV *&Constant) const { const SCEV *Zero = SE->getZero(Subscript->getType()); @@ -2937,7 +2952,7 @@ // 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 *DependenceAnalysis::getLowerBound(BoundInfo *Bound) const { +const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const { const SCEV *Sum = Bound[1].Lower[Bound[1].Direction]; for (unsigned K = 2; Sum && K <= MaxLevels; ++K) { if (Bound[K].Lower[Bound[K].Direction]) @@ -2953,7 +2968,7 @@ // 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 *DependenceAnalysis::getUpperBound(BoundInfo *Bound) const { +const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const { const SCEV *Sum = Bound[1].Upper[Bound[1].Direction]; for (unsigned K = 2; Sum && K <= MaxLevels; ++K) { if (Bound[K].Upper[Bound[K].Direction]) @@ -2974,7 +2989,7 @@ // 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 *DependenceAnalysis::findCoefficient(const SCEV *Expr, +const SCEV *DependenceInfo::findCoefficient(const SCEV *Expr, const Loop *TargetLoop) const { const SCEVAddRecExpr *AddRec = dyn_cast(Expr); if (!AddRec) @@ -2990,7 +3005,7 @@ // 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 *DependenceAnalysis::zeroCoefficient(const SCEV *Expr, +const SCEV *DependenceInfo::zeroCoefficient(const SCEV *Expr, const Loop *TargetLoop) const { const SCEVAddRecExpr *AddRec = dyn_cast(Expr); if (!AddRec) @@ -3009,7 +3024,7 @@ // 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 *DependenceAnalysis::addToCoefficient(const SCEV *Expr, +const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr, const Loop *TargetLoop, const SCEV *Value) const { const SCEVAddRecExpr *AddRec = dyn_cast(Expr); @@ -3046,7 +3061,7 @@ // Practical Dependence Testing // Goff, Kennedy, Tseng // PLDI 1991 -bool DependenceAnalysis::propagate(const SCEV *&Src, +bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst, SmallBitVector &Loops, SmallVectorImpl &Constraints, @@ -3071,7 +3086,7 @@ // 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 DependenceAnalysis::propagateDistance(const SCEV *&Src, +bool DependenceInfo::propagateDistance(const SCEV *&Src, const SCEV *&Dst, Constraint &CurConstraint, bool &Consistent) { @@ -3098,7 +3113,7 @@ // 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 DependenceAnalysis::propagateLine(const SCEV *&Src, +bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst, Constraint &CurConstraint, bool &Consistent) { @@ -3173,7 +3188,7 @@ // Attempt to propagate a point // constraint into a subscript pair (Src and Dst). // Return true if some simplification occurs. -bool DependenceAnalysis::propagatePoint(const SCEV *&Src, +bool DependenceInfo::propagatePoint(const SCEV *&Src, const SCEV *&Dst, Constraint &CurConstraint) { const Loop *CurLoop = CurConstraint.getAssociatedLoop(); @@ -3193,7 +3208,7 @@ // Update direction vector entry based on the current constraint. -void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level, +void DependenceInfo::updateDirection(Dependence::DVEntry &Level, const Constraint &CurConstraint ) const { DEBUG(dbgs() << "\tUpdate direction, constraint ="); @@ -3247,7 +3262,7 @@ /// 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 DependenceAnalysis::tryDelinearize(Instruction *Src, +bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst, SmallVectorImpl &Pair) { @@ -3361,7 +3376,7 @@ // Care is required to keep the routine below, getSplitIteration(), // up to date with respect to this routine. std::unique_ptr -DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, +DependenceInfo::depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent) { if (Src == Dst) PossiblyLoopIndependent = false; @@ -3817,7 +3832,7 @@ // // breaks the dependence and allows us to vectorize/parallelize // both loops. -const SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep, +const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep, unsigned SplitLevel) { assert(Dep.isSplitable(SplitLevel) && "Dep should be splitable at SplitLevel"); Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -24,6 +24,7 @@ #include "llvm/Analysis/CFLAliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LazyCallGraph.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -69,6 +69,7 @@ FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis()) FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis()) FUNCTION_ANALYSIS("loops", LoopAnalysis()) +FUNCTION_ANALYSIS("da", DependenceAnalysis()) FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis()) FUNCTION_ANALYSIS("regions", RegionInfoAnalysis()) FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis()) Index: lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- lib/Transforms/Scalar/LoopInterchange.cpp +++ lib/Transforms/Scalar/LoopInterchange.cpp @@ -72,7 +72,7 @@ #endif static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, - Loop *L, DependenceAnalysis *DA) { + Loop *L, DependenceInfo *DI) { typedef SmallVector ValueVector; ValueVector MemInstr; @@ -117,7 +117,7 @@ continue; if (isa(Src) && isa(Des)) continue; - if (auto D = DA->depends(Src, Des, true)) { + if (auto D = DI->depends(Src, Des, true)) { DEBUG(dbgs() << "Found Dependency between Src=" << Src << " Des=" << Des << "\n"); if (D->isFlow()) { @@ -430,11 +430,11 @@ static char ID; ScalarEvolution *SE; LoopInfo *LI; - DependenceAnalysis *DA; + DependenceInfo *DI; DominatorTree *DT; bool PreserveLCSSA; LoopInterchange() - : FunctionPass(ID), SE(nullptr), LI(nullptr), DA(nullptr), DT(nullptr) { + : FunctionPass(ID), SE(nullptr), LI(nullptr), DI(nullptr), DT(nullptr) { initializeLoopInterchangePass(*PassRegistry::getPassRegistry()); } @@ -443,7 +443,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequiredID(LoopSimplifyID); AU.addRequiredID(LCSSAID); } @@ -451,7 +451,7 @@ bool runOnFunction(Function &F) override { SE = &getAnalysis().getSE(); LI = &getAnalysis().getLoopInfo(); - DA = &getAnalysis(); + DI = &getAnalysis().getDI(); auto *DTWP = getAnalysisIfAvailable(); DT = DTWP ? &DTWP->getDomTree() : nullptr; PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); @@ -515,7 +515,7 @@ << "\n"); if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(), - OuterMostLoop, DA)) { + OuterMostLoop, DI)) { DEBUG(dbgs() << "Populating Dependency matrix failed\n"); return false; } @@ -1294,7 +1294,7 @@ INITIALIZE_PASS_BEGIN(LoopInterchange, "loop-interchange", "Interchanges loops for cache reuse", false, false) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) -INITIALIZE_PASS_DEPENDENCY(DependenceAnalysis) +INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) Index: lib/Transforms/Scalar/LoopSimplifyCFG.cpp =================================================================== --- lib/Transforms/Scalar/LoopSimplifyCFG.cpp +++ lib/Transforms/Scalar/LoopSimplifyCFG.cpp @@ -45,7 +45,7 @@ bool runOnLoop(Loop *L, LPPassManager &) override; void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addPreserved(); + AU.addPreserved(); getLoopAnalysisUsage(AU); } }; Index: lib/Transforms/Utils/LoopSimplify.cpp =================================================================== --- lib/Transforms/Utils/LoopSimplify.cpp +++ lib/Transforms/Utils/LoopSimplify.cpp @@ -748,7 +748,7 @@ AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. }