Index: llvm/trunk/include/llvm/Analysis/DependenceAnalysis.h =================================================================== --- llvm/trunk/include/llvm/Analysis/DependenceAnalysis.h +++ llvm/trunk/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,41 @@ bool tryDelinearize(Instruction *Src, Instruction *Dst, SmallVectorImpl &Pair); + }; // class DependenceInfo + /// \brief AnalysisPass to compute dependence information in a function + class DependenceAnalysis : public AnalysisInfoMixin { + public: + typedef DependenceInfo Result; + Result run(Function &F, FunctionAnalysisManager &FAM); + + private: + static char PassID; + friend struct AnalysisInfoMixin; + }; // 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: llvm/trunk/include/llvm/Analysis/Passes.h =================================================================== --- llvm/trunk/include/llvm/Analysis/Passes.h +++ llvm/trunk/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: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -111,6 +111,7 @@ void initializeDelinearizationPass(PassRegistry &); void initializeDependenceAnalysisPass(PassRegistry&); void initializeDetectDeadLanesPass(PassRegistry&); +void initializeDependenceAnalysisWrapperPassPass(PassRegistry&); void initializeDivergenceAnalysisPass(PassRegistry&); void initializeDomOnlyPrinterPass(PassRegistry&); void initializeDomOnlyViewerPass(PassRegistry&); Index: llvm/trunk/include/llvm/LinkAllPasses.h =================================================================== --- llvm/trunk/include/llvm/LinkAllPasses.h +++ llvm/trunk/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: llvm/trunk/lib/Analysis/Analysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/Analysis.cpp +++ llvm/trunk/lib/Analysis/Analysis.cpp @@ -35,7 +35,7 @@ initializeCFGOnlyViewerPass(Registry); initializeCFGOnlyPrinterPass(Registry); initializeCFLAAWrapperPassPass(Registry); - initializeDependenceAnalysisPass(Registry); + initializeDependenceAnalysisWrapperPassPass(Registry); initializeDelinearizationPass(Registry); initializeDemandedBitsWrapperPassPass(Registry); initializeDivergenceAnalysisPass(Registry); Index: llvm/trunk/lib/Analysis/DependenceAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/DependenceAnalysis.cpp +++ llvm/trunk/lib/Analysis/DependenceAnalysis.cpp @@ -114,36 +114,43 @@ //===----------------------------------------------------------------------===// // 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", - "Dependence Analysis", true, true) +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; } +DependenceInfo &DependenceAnalysisWrapperPass::getDI() const { return *info; } -void DependenceAnalysis::releaseMemory() { -} - +void DependenceAnalysisWrapperPass::releaseMemory() { info.reset(); } -void DependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { +void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequiredTransitive(); AU.addRequiredTransitive(); @@ -155,11 +162,10 @@ // 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); - SrcI != SrcE; ++SrcI) { +static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) { + auto *F = DA->getFunction(); + for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE; + ++SrcI) { if (isa(*SrcI) || isa(*SrcI)) { for (inst_iterator DstI = SrcI, DstE = inst_end(F); DstI != DstE; ++DstI) { @@ -183,9 +189,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 { + dumpExampleDependence(OS, info.get()); } //===----------------------------------------------------------------------===// @@ -286,11 +292,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 +304,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 +312,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 +321,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 +330,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,34 +339,29 @@ // 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, - const SCEV *Y, - const Loop *CurLoop) { +void DependenceInfo::Constraint::setPoint(const SCEV *X, const SCEV *Y, + const Loop *CurLoop) { Kind = Point; A = X; B = Y; AssociatedLoop = CurLoop; } - -void DependenceAnalysis::Constraint::setLine(const SCEV *AA, - const SCEV *BB, - const SCEV *CC, - const Loop *CurLoop) { +void DependenceInfo::Constraint::setLine(const SCEV *AA, const SCEV *BB, + const SCEV *CC, const Loop *CurLoop) { Kind = Line; A = AA; B = BB; @@ -368,9 +369,8 @@ AssociatedLoop = CurLoop; } - -void DependenceAnalysis::Constraint::setDistance(const SCEV *D, - const Loop *CurLoop) { +void DependenceInfo::Constraint::setDistance(const SCEV *D, + const Loop *CurLoop) { Kind = Distance; A = SE->getOne(D->getType()); B = SE->getNegativeSCEV(A); @@ -378,20 +378,16 @@ AssociatedLoop = CurLoop; } +void DependenceInfo::Constraint::setEmpty() { Kind = Empty; } -void DependenceAnalysis::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,8 +412,7 @@ // Practical Dependence Testing // Goff, Kennedy, Tseng // PLDI 1991 -bool DependenceAnalysis::intersectConstraints(Constraint *X, - const Constraint *Y) { +bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) { ++DeltaApplications; DEBUG(dbgs() << "\tintersect constraints\n"); DEBUG(dbgs() << "\t X ="; X->dump(dbgs())); @@ -569,7 +564,7 @@ //===----------------------------------------------------------------------===// -// DependenceAnalysis methods +// DependenceInfo methods // For debugging purposes. Dumps a dependence to OS. void Dependence::dump(raw_ostream &OS) const { @@ -709,8 +704,8 @@ // e - 5 // f - 6 // g - 7 = MaxLevels -void DependenceAnalysis::establishNestingLevels(const Instruction *Src, - const Instruction *Dst) { +void DependenceInfo::establishNestingLevels(const Instruction *Src, + const Instruction *Dst) { const BasicBlock *SrcBlock = Src->getParent(); const BasicBlock *DstBlock = Dst->getParent(); unsigned SrcLevel = LI->getLoopDepth(SrcBlock); @@ -739,14 +734,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,8 +751,8 @@ // Returns true if Expression is loop invariant in LoopNest. -bool DependenceAnalysis::isLoopInvariant(const SCEV *Expression, - const Loop *LoopNest) const { +bool DependenceInfo::isLoopInvariant(const SCEV *Expression, + const Loop *LoopNest) const { if (!LoopNest) return true; return SE->isLoopInvariant(Expression, LoopNest) && @@ -768,9 +763,9 @@ // 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, - const Loop *LoopNest, - SmallBitVector &Loops) const { +void DependenceInfo::collectCommonLoops(const SCEV *Expression, + const Loop *LoopNest, + SmallBitVector &Loops) const { while (LoopNest) { unsigned Level = LoopNest->getLoopDepth(); if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest)) @@ -779,7 +774,7 @@ } } -void DependenceAnalysis::unifySubscriptType(ArrayRef Pairs) { +void DependenceInfo::unifySubscriptType(ArrayRef Pairs) { unsigned widestWidthSeen = 0; Type *widestType; @@ -836,7 +831,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,9 +850,8 @@ // 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, - const Loop *LoopNest, - SmallBitVector &Loops) { +bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest, + SmallBitVector &Loops) { const SCEVAddRecExpr *AddRec = dyn_cast(Src); if (!AddRec) return isLoopInvariant(Src, LoopNest); @@ -881,9 +875,8 @@ // 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, - const Loop *LoopNest, - SmallBitVector &Loops) { +bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest, + SmallBitVector &Loops) { const SCEVAddRecExpr *AddRec = dyn_cast(Dst); if (!AddRec) return isLoopInvariant(Dst, LoopNest); @@ -907,10 +900,10 @@ // 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, - const SCEV *Dst, const Loop *DstLoopNest, - SmallBitVector &Loops) { +DependenceInfo::Subscript::ClassificationKind +DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest, + const SCEV *Dst, const Loop *DstLoopNest, + SmallBitVector &Loops) { SmallBitVector SrcLoops(MaxLevels + 1); SmallBitVector DstLoops(MaxLevels + 1); if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops)) @@ -942,9 +935,8 @@ // 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, - const SCEV *X, - const SCEV *Y) const { +bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X, + const SCEV *Y) const { if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) { if ((isa(X) && @@ -995,8 +987,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, - Type *T) const { +const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const { if (SE->hasLoopInvariantBackedgeTakenCount(L)) { const SCEV *UB = SE->getBackedgeTakenCount(L); return SE->getTruncateOrZeroExtend(UB, T); @@ -1007,9 +998,8 @@ // Calls collectUpperBound(), then attempts to cast it to SCEVConstant. // If the cast fails, returns NULL. -const SCEVConstant *DependenceAnalysis::collectConstantUpperBound(const Loop *L, - Type *T - ) const { +const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L, + Type *T) const { if (const SCEV *UB = collectUpperBound(L, T)) return dyn_cast(UB); return nullptr; @@ -1026,9 +1016,8 @@ // 3) the values might be equal, so we have to assume a dependence. // // Return true if dependence disproved. -bool DependenceAnalysis::testZIV(const SCEV *Src, - const SCEV *Dst, - FullDependence &Result) const { +bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst, + FullDependence &Result) const { DEBUG(dbgs() << " src = " << *Src << "\n"); DEBUG(dbgs() << " dst = " << *Dst << "\n"); ++ZIVapplications; @@ -1074,13 +1063,10 @@ // { > if d < 0 // // Return true if dependence disproved. -bool DependenceAnalysis::strongSIVtest(const SCEV *Coeff, - const SCEV *SrcConst, - const SCEV *DstConst, - const Loop *CurLoop, - unsigned Level, - FullDependence &Result, - Constraint &NewConstraint) const { +bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst, + const SCEV *DstConst, const Loop *CurLoop, + unsigned Level, FullDependence &Result, + Constraint &NewConstraint) const { DEBUG(dbgs() << "\tStrong SIV test\n"); DEBUG(dbgs() << "\t Coeff = " << *Coeff); DEBUG(dbgs() << ", " << *Coeff->getType() << "\n"); @@ -1213,14 +1199,10 @@ // Can determine iteration for splitting. // // Return true if dependence disproved. -bool DependenceAnalysis::weakCrossingSIVtest(const SCEV *Coeff, - const SCEV *SrcConst, - const SCEV *DstConst, - const Loop *CurLoop, - unsigned Level, - FullDependence &Result, - Constraint &NewConstraint, - const SCEV *&SplitIter) const { +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 { DEBUG(dbgs() << "\tWeak-Crossing SIV test\n"); DEBUG(dbgs() << "\t Coeff = " << *Coeff << "\n"); DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); @@ -1256,7 +1238,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,14 +1415,11 @@ // in the case of the strong SIV test, can compute Distances. // // Return true if dependence disproved. -bool DependenceAnalysis::exactSIVtest(const SCEV *SrcCoeff, - const SCEV *DstCoeff, - const SCEV *SrcConst, - const SCEV *DstConst, - const Loop *CurLoop, - unsigned Level, - FullDependence &Result, - Constraint &NewConstraint) const { +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 { DEBUG(dbgs() << "\tExact SIV test\n"); DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n"); DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n"); @@ -1645,13 +1624,12 @@ // (see also weakZeroDstSIVtest) // // Return true if dependence disproved. -bool DependenceAnalysis::weakZeroSrcSIVtest(const SCEV *DstCoeff, - const SCEV *SrcConst, - const SCEV *DstConst, - const Loop *CurLoop, - unsigned Level, - FullDependence &Result, - Constraint &NewConstraint) const { +bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff, + const SCEV *SrcConst, + const SCEV *DstConst, + const Loop *CurLoop, unsigned Level, + FullDependence &Result, + Constraint &NewConstraint) const { // For the WeakSIV test, it's possible the loop isn't common to // the Src and Dst loops. If it isn't, then there's no need to // record a direction. @@ -1756,13 +1734,12 @@ // (see also weakZeroSrcSIVtest) // // Return true if dependence disproved. -bool DependenceAnalysis::weakZeroDstSIVtest(const SCEV *SrcCoeff, - const SCEV *SrcConst, - const SCEV *DstConst, - const Loop *CurLoop, - unsigned Level, - FullDependence &Result, - Constraint &NewConstraint) const { +bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff, + const SCEV *SrcConst, + const SCEV *DstConst, + const Loop *CurLoop, unsigned Level, + FullDependence &Result, + Constraint &NewConstraint) const { // For the WeakSIV test, it's possible the loop isn't common to the // Src and Dst loops. If it isn't, then there's no need to record a direction. DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n"); @@ -1842,13 +1819,10 @@ // 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, - const SCEV *DstCoeff, - const SCEV *SrcConst, - const SCEV *DstConst, - const Loop *SrcLoop, - const Loop *DstLoop, - FullDependence &Result) const { +bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, + const SCEV *SrcConst, const SCEV *DstConst, + const Loop *SrcLoop, const Loop *DstLoop, + FullDependence &Result) const { DEBUG(dbgs() << "\tExact RDIV test\n"); DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << " = AM\n"); DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << " = BM\n"); @@ -1986,12 +1960,10 @@ // a1*N1 <= c2 - c1 <= -a2*N2 // // return true if dependence disproved -bool DependenceAnalysis::symbolicRDIVtest(const SCEV *A1, - const SCEV *A2, - const SCEV *C1, - const SCEV *C2, - const Loop *Loop1, - const Loop *Loop2) const { +bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2, + const SCEV *C1, const SCEV *C2, + const Loop *Loop1, + const Loop *Loop2) const { ++SymbolicRDIVapplications; DEBUG(dbgs() << "\ttry symbolic RDIV test\n"); DEBUG(dbgs() << "\t A1 = " << *A1); @@ -2103,12 +2075,9 @@ // they apply; they're cheaper and sometimes more precise. // // Return true if dependence disproved. -bool DependenceAnalysis::testSIV(const SCEV *Src, - const SCEV *Dst, - unsigned &Level, - FullDependence &Result, - Constraint &NewConstraint, - const SCEV *&SplitIter) const { +bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level, + FullDependence &Result, Constraint &NewConstraint, + const SCEV *&SplitIter) const { DEBUG(dbgs() << " src = " << *Src << "\n"); DEBUG(dbgs() << " dst = " << *Dst << "\n"); const SCEVAddRecExpr *SrcAddRec = dyn_cast(Src); @@ -2174,9 +2143,8 @@ // [c1 + a1*i + a2*j][c2]. // // Return true if dependence disproved. -bool DependenceAnalysis::testRDIV(const SCEV *Src, - const SCEV *Dst, - FullDependence &Result) const { +bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst, + FullDependence &Result) const { // we have 3 possible situations here: // 1) [a*i + b] and [c*j + d] // 2) [a*i + c*j + b] and [d] @@ -2241,10 +2209,9 @@ // 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, - const SCEV *Dst, - const SmallBitVector &Loops, - FullDependence &Result) const { +bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst, + const SmallBitVector &Loops, + FullDependence &Result) const { DEBUG(dbgs() << " src = " << *Src << "\n"); DEBUG(dbgs() << " dst = " << *Dst << "\n"); Result.Consistent = false; @@ -2284,9 +2251,8 @@ // 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, - const SCEV *Dst, - FullDependence &Result) const { +bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst, + FullDependence &Result) const { DEBUG(dbgs() << "starting gcd\n"); ++GCDapplications; unsigned BitWidth = SE->getTypeSizeInBits(Src->getType()); @@ -2488,10 +2454,9 @@ // for the lower bound, NULL denotes -inf. // // Return true if dependence disproved. -bool DependenceAnalysis::banerjeeMIVtest(const SCEV *Src, - const SCEV *Dst, - const SmallBitVector &Loops, - FullDependence &Result) const { +bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst, + const SmallBitVector &Loops, + FullDependence &Result) const { DEBUG(dbgs() << "starting Banerjee\n"); ++BanerjeeApplications; DEBUG(dbgs() << " Src = " << *Src << '\n'); @@ -2569,13 +2534,11 @@ // 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, - CoefficientInfo *A, - CoefficientInfo *B, - BoundInfo *Bound, - const SmallBitVector &Loops, - unsigned &DepthExpanded, - const SCEV *Delta) const { +unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A, + CoefficientInfo *B, BoundInfo *Bound, + const SmallBitVector &Loops, + unsigned &DepthExpanded, + const SCEV *Delta) const { if (Level > CommonLevels) { // record result DEBUG(dbgs() << "\t["); @@ -2670,10 +2633,8 @@ // Returns true iff the current bounds are plausible. -bool DependenceAnalysis::testBounds(unsigned char DirKind, - unsigned Level, - BoundInfo *Bound, - const SCEV *Delta) const { +bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level, + BoundInfo *Bound, const SCEV *Delta) const { Bound[Level].Direction = DirKind; if (const SCEV *LowerBound = getLowerBound(Bound)) if (isKnownPredicate(CmpInst::ICMP_SGT, LowerBound, Delta)) @@ -2700,10 +2661,8 @@ // 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, - CoefficientInfo *B, - BoundInfo *Bound, - unsigned K) const { +void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B, + BoundInfo *Bound, unsigned K) const { Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity. Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity. if (Bound[K].Iterations) { @@ -2741,10 +2700,8 @@ // 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, - CoefficientInfo *B, - BoundInfo *Bound, - unsigned K) const { +void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B, + BoundInfo *Bound, unsigned K) const { Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity. Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity. if (Bound[K].Iterations) { @@ -2783,10 +2740,8 @@ // 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, - CoefficientInfo *B, - BoundInfo *Bound, - unsigned K) const { +void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B, + BoundInfo *Bound, unsigned K) const { Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity. Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity. if (Bound[K].Iterations) { @@ -2829,10 +2784,8 @@ // 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, - CoefficientInfo *B, - BoundInfo *Bound, - unsigned K) const { +void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B, + BoundInfo *Bound, unsigned K) const { Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity. Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity. if (Bound[K].Iterations) { @@ -2861,13 +2814,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())); } @@ -2875,10 +2828,9 @@ // 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, - bool SrcFlag, - const SCEV *&Constant) const { +DependenceInfo::CoefficientInfo * +DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag, + const SCEV *&Constant) const { const SCEV *Zero = SE->getZero(Subscript->getType()); CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1]; for (unsigned K = 1; K <= MaxLevels; ++K) { @@ -2922,7 +2874,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]) @@ -2938,7 +2890,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]) @@ -2959,8 +2911,8 @@ // 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 Loop *TargetLoop) const { +const SCEV *DependenceInfo::findCoefficient(const SCEV *Expr, + const Loop *TargetLoop) const { const SCEVAddRecExpr *AddRec = dyn_cast(Expr); if (!AddRec) return SE->getZero(Expr->getType()); @@ -2975,8 +2927,8 @@ // 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 Loop *TargetLoop) const { +const SCEV *DependenceInfo::zeroCoefficient(const SCEV *Expr, + const Loop *TargetLoop) const { const SCEVAddRecExpr *AddRec = dyn_cast(Expr); if (!AddRec) return Expr; // ignore @@ -2994,9 +2946,9 @@ // 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 Loop *TargetLoop, - const SCEV *Value) const { +const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr, + const Loop *TargetLoop, + const SCEV *Value) const { const SCEVAddRecExpr *AddRec = dyn_cast(Expr); if (!AddRec) // create a new addRec return SE->getAddRecExpr(Expr, @@ -3031,11 +2983,10 @@ // Practical Dependence Testing // Goff, Kennedy, Tseng // PLDI 1991 -bool DependenceAnalysis::propagate(const SCEV *&Src, - const SCEV *&Dst, - SmallBitVector &Loops, - SmallVectorImpl &Constraints, - bool &Consistent) { +bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst, + SmallBitVector &Loops, + SmallVectorImpl &Constraints, + bool &Consistent) { bool Result = false; for (int LI = Loops.find_first(); LI >= 0; LI = Loops.find_next(LI)) { DEBUG(dbgs() << "\t Constraint[" << LI << "] is"); @@ -3056,10 +3007,9 @@ // 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, - const SCEV *&Dst, - Constraint &CurConstraint, - bool &Consistent) { +bool DependenceInfo::propagateDistance(const SCEV *&Src, const SCEV *&Dst, + Constraint &CurConstraint, + bool &Consistent) { const Loop *CurLoop = CurConstraint.getAssociatedLoop(); DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n"); const SCEV *A_K = findCoefficient(Src, CurLoop); @@ -3083,10 +3033,9 @@ // 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, - const SCEV *&Dst, - Constraint &CurConstraint, - bool &Consistent) { +bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst, + Constraint &CurConstraint, + bool &Consistent) { const Loop *CurLoop = CurConstraint.getAssociatedLoop(); const SCEV *A = CurConstraint.getA(); const SCEV *B = CurConstraint.getB(); @@ -3158,9 +3107,8 @@ // 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, - const SCEV *&Dst, - Constraint &CurConstraint) { +bool DependenceInfo::propagatePoint(const SCEV *&Src, const SCEV *&Dst, + Constraint &CurConstraint) { const Loop *CurLoop = CurConstraint.getAssociatedLoop(); const SCEV *A_K = findCoefficient(Src, CurLoop); const SCEV *AP_K = findCoefficient(Dst, CurLoop); @@ -3178,9 +3126,8 @@ // Update direction vector entry based on the current constraint. -void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level, - const Constraint &CurConstraint - ) const { +void DependenceInfo::updateDirection(Dependence::DVEntry &Level, + const Constraint &CurConstraint) const { DEBUG(dbgs() << "\tUpdate direction, constraint ="); DEBUG(CurConstraint.dump(dbgs())); if (CurConstraint.isAny()) @@ -3232,10 +3179,8 @@ /// 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, - Instruction *Dst, - SmallVectorImpl &Pair) -{ +bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst, + SmallVectorImpl &Pair) { Value *SrcPtr = getPointerOperand(Src); Value *DstPtr = getPointerOperand(Dst); @@ -3346,8 +3291,8 @@ // 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, - bool PossiblyLoopIndependent) { +DependenceInfo::depends(Instruction *Src, Instruction *Dst, + bool PossiblyLoopIndependent) { if (Src == Dst) PossiblyLoopIndependent = false; @@ -3802,8 +3747,8 @@ // // breaks the dependence and allows us to vectorize/parallelize // both loops. -const SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep, - unsigned SplitLevel) { +const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep, + unsigned SplitLevel) { assert(Dep.isSplitable(SplitLevel) && "Dep should be splitable at SplitLevel"); Instruction *Src = Dep.getSrc(); Index: llvm/trunk/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/trunk/lib/Passes/PassBuilder.cpp +++ llvm/trunk/lib/Passes/PassBuilder.cpp @@ -28,6 +28,7 @@ #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/DemandedBits.h" +#include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LazyCallGraph.h" Index: llvm/trunk/lib/Passes/PassRegistry.def =================================================================== --- llvm/trunk/lib/Passes/PassRegistry.def +++ llvm/trunk/lib/Passes/PassRegistry.def @@ -82,6 +82,7 @@ FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis()) 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: llvm/trunk/lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LoopInterchange.cpp +++ llvm/trunk/lib/Transforms/Scalar/LoopInterchange.cpp @@ -71,7 +71,7 @@ #endif static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level, - Loop *L, DependenceAnalysis *DA) { + Loop *L, DependenceInfo *DI) { typedef SmallVector ValueVector; ValueVector MemInstr; @@ -116,7 +116,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()) { @@ -429,11 +429,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()); } @@ -442,7 +442,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequiredID(LoopSimplifyID); AU.addRequiredID(LCSSAID); } @@ -453,7 +453,7 @@ SE = &getAnalysis().getSE(); LI = &getAnalysis().getLoopInfo(); - DA = &getAnalysis(); + DI = &getAnalysis().getDI(); auto *DTWP = getAnalysisIfAvailable(); DT = DTWP ? &DTWP->getDomTree() : nullptr; PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); @@ -517,7 +517,7 @@ << "\n"); if (!populateDependencyMatrix(DependencyMatrix, LoopList.size(), - OuterMostLoop, DA)) { + OuterMostLoop, DI)) { DEBUG(dbgs() << "Populating Dependency matrix failed\n"); return false; } @@ -1296,7 +1296,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: llvm/trunk/lib/Transforms/Scalar/LoopSimplifyCFG.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LoopSimplifyCFG.cpp +++ llvm/trunk/lib/Transforms/Scalar/LoopSimplifyCFG.cpp @@ -95,7 +95,7 @@ } void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addPreserved(); + AU.addPreserved(); getLoopAnalysisUsage(AU); } }; Index: llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp +++ llvm/trunk/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. }