From 1a44452b113ca9c988f636e52064fc64f87791e6 Mon Sep 17 00:00:00 2001 From: Dehao Chen Date: Sat, 16 Jul 2016 22:51:33 +0000 Subject: [PATCH] [PM] Convert IVUsers analysis to new pass manager. Summary: Convert IVUsers analysis to new pass manager. Reviewers: davidxl, silvas Subscribers: junbuml, sanjoy, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D22434 llvm-svn: 275698 --- llvm/include/llvm/ADT/ilist.h | 6 +- llvm/include/llvm/Analysis/IVUsers.h | 56 ++++++++++--- llvm/include/llvm/InitializePasses.h | 2 +- llvm/lib/Analysis/Analysis.cpp | 2 +- llvm/lib/Analysis/IVUsers.cpp | 96 +++++++++++++--------- llvm/lib/CodeGen/MachineFunctionPass.cpp | 2 +- llvm/lib/Passes/PassBuilder.cpp | 1 + llvm/lib/Passes/PassRegistry.def | 2 + llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp | 8 +- .../LoopStrengthReduce/quadradic-exit-value.ll | 1 + 10 files changed, 121 insertions(+), 55 deletions(-) diff --git a/llvm/include/llvm/ADT/ilist.h b/llvm/include/llvm/ADT/ilist.h index f4dde44..8e4d45d 100644 --- a/llvm/include/llvm/ADT/ilist.h +++ b/llvm/include/llvm/ADT/ilist.h @@ -422,6 +422,10 @@ public: return iterator(New); } + iterator insert(iterator where, const NodeTy &New) { + return this->insert(where, new NodeTy(New)); + } + iterator insertAfter(iterator where, NodeTy *New) { if (empty()) return insert(begin(), New); @@ -668,7 +672,7 @@ struct ilist : public iplist { typedef typename iplist::iterator iterator; ilist() {} - ilist(const ilist &right) { + ilist(const ilist &right) : iplist() { insert(this->begin(), right.begin(), right.end()); } explicit ilist(size_type count) { diff --git a/llvm/include/llvm/Analysis/IVUsers.h b/llvm/include/llvm/Analysis/IVUsers.h index 37d0149..e68a775 100644 --- a/llvm/include/llvm/Analysis/IVUsers.h +++ b/llvm/include/llvm/Analysis/IVUsers.h @@ -117,7 +117,7 @@ private: mutable ilist_node Sentinel; }; -class IVUsers : public LoopPass { +class IVUsers { friend class IVStrideUse; Loop *L; AssumptionCache *AC; @@ -133,15 +133,9 @@ class IVUsers : public LoopPass { // Ephemeral values used by @llvm.assume in this function. SmallPtrSet EphValues; - void getAnalysisUsage(AnalysisUsage &AU) const override; - - bool runOnLoop(Loop *L, LPPassManager &LPM) override; - - void releaseMemory() override; - public: - static char ID; // Pass ID, replacement for typeid - IVUsers(); + IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, + ScalarEvolution *SE); Loop *getLoop() const { return L; } @@ -173,16 +167,58 @@ public: return Processed.count(Inst); } - void print(raw_ostream &OS, const Module* = nullptr) const override; + void releaseMemory(); + + void print(raw_ostream &OS, const Module * = nullptr) const; /// dump - This method is used for debugging. void dump() const; + protected: bool AddUsersImpl(Instruction *I, SmallPtrSetImpl &SimpleLoopNests); }; Pass *createIVUsersPass(); +class IVUsersWrapperPass : public LoopPass { + std::unique_ptr IU; + +public: + static char ID; + + IVUsersWrapperPass(); + + IVUsers &getIU() { return *IU; } + const IVUsers &getIU() const { return *IU; } + + void getAnalysisUsage(AnalysisUsage &AU) const override; + + bool runOnLoop(Loop *L, LPPassManager &LPM) override; + + void releaseMemory() override; + + void print(raw_ostream &OS, const Module * = nullptr) const override; +}; + +/// Analysis pass that exposes the \c IVUsers for a loop. +class IVUsersAnalysis : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + static char PassID; + +public: + typedef IVUsers Result; + + IVUsers run(Loop &L, AnalysisManager &AM); +}; + +/// Printer pass for the \c IVUsers for a loop. +class IVUsersPrinterPass : public PassInfoMixin { + raw_ostream &OS; + +public: + explicit IVUsersPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Loop &L, AnalysisManager &AM); +}; } #endif diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h index 20eaa89..f8ec858 100644 --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -143,7 +143,7 @@ void initializeGuardWideningLegacyPassPass(PassRegistry&); void initializeIPCPPass(PassRegistry&); void initializeIPSCCPLegacyPassPass(PassRegistry &); void initializeIRTranslatorPass(PassRegistry &); -void initializeIVUsersPass(PassRegistry&); +void initializeIVUsersWrapperPassPass(PassRegistry&); void initializeIfConverterPass(PassRegistry&); void initializeImplicitNullChecksPass(PassRegistry&); void initializeIndVarSimplifyLegacyPassPass(PassRegistry&); diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp index ffc4b2e..105a9fd 100644 --- a/llvm/lib/Analysis/Analysis.cpp +++ b/llvm/lib/Analysis/Analysis.cpp @@ -51,7 +51,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializePostDomOnlyPrinterPass(Registry); initializeAAResultsWrapperPassPass(Registry); initializeGlobalsAAWrapperPassPass(Registry); - initializeIVUsersPass(Registry); + initializeIVUsersWrapperPassPass(Registry); initializeInstCountPass(Registry); initializeIntervalPartitionPass(Registry); initializeLazyBlockFrequencyInfoPassPass(Registry); diff --git a/llvm/lib/Analysis/IVUsers.cpp b/llvm/lib/Analysis/IVUsers.cpp index e974cb9..43c0ba1 100644 --- a/llvm/lib/Analysis/IVUsers.cpp +++ b/llvm/lib/Analysis/IVUsers.cpp @@ -12,11 +12,12 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Analysis/IVUsers.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CodeMetrics.h" -#include "llvm/Analysis/IVUsers.h" #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/LoopPassManager.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Constants.h" @@ -33,19 +34,35 @@ using namespace llvm; #define DEBUG_TYPE "iv-users" -char IVUsers::ID = 0; -INITIALIZE_PASS_BEGIN(IVUsers, "iv-users", +char IVUsersAnalysis::PassID; + +IVUsers IVUsersAnalysis::run(Loop &L, AnalysisManager &AM) { + const auto &FAM = + AM.getResult(L).getManager(); + Function *F = L.getHeader()->getParent(); + + return IVUsers(&L, FAM.getCachedResult(*F), + FAM.getCachedResult(*F), + FAM.getCachedResult(*F), + FAM.getCachedResult(*F)); +} + +PreservedAnalyses IVUsersPrinterPass::run(Loop &L, AnalysisManager &AM) { + AM.getResult(L).print(OS); + return PreservedAnalyses::all(); +} + +char IVUsersWrapperPass::ID = 0; +INITIALIZE_PASS_BEGIN(IVUsersWrapperPass, "iv-users", "Induction Variable Users", false, true) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) -INITIALIZE_PASS_END(IVUsers, "iv-users", - "Induction Variable Users", false, true) +INITIALIZE_PASS_END(IVUsersWrapperPass, "iv-users", "Induction Variable Users", + false, true) -Pass *llvm::createIVUsersPass() { - return new IVUsers(); -} +Pass *llvm::createIVUsersPass() { return new IVUsersWrapperPass(); } /// isInteresting - Test whether the given expression is "interesting" when /// used by the given expression, within the context of analyzing the @@ -246,28 +263,9 @@ IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) { return IVUses.back(); } -IVUsers::IVUsers() - : LoopPass(ID) { - initializeIVUsersPass(*PassRegistry::getPassRegistry()); -} - -void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); - AU.setPreservesAll(); -} - -bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { - - L = l; - AC = &getAnalysis().getAssumptionCache( - *L->getHeader()->getParent()); - LI = &getAnalysis().getLoopInfo(); - DT = &getAnalysis().getDomTree(); - SE = &getAnalysis().getSE(); - +IVUsers::IVUsers(Loop *L, AssumptionCache *AC, LoopInfo *LI, DominatorTree *DT, + ScalarEvolution *SE) + : L(L), AC(AC), LI(LI), DT(DT), SE(SE), IVUses() { // Collect ephemeral values so that AddUsersIfInteresting skips them. EphValues.clear(); CodeMetrics::collectEphemeralValues(L, AC, EphValues); @@ -277,16 +275,13 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { // this loop. If they are induction variables, inspect their uses. for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) (void)AddUsersIfInteresting(&*I); - - return false; } void IVUsers::print(raw_ostream &OS, const Module *M) const { OS << "IV Users for loop "; L->getHeader()->printAsOperand(OS, false); if (SE->hasLoopInvariantBackedgeTakenCount(L)) { - OS << " with backedge-taken count " - << *SE->getBackedgeTakenCount(L); + OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L); } OS << ":\n"; @@ -309,9 +304,7 @@ void IVUsers::print(raw_ostream &OS, const Module *M) const { } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -LLVM_DUMP_METHOD void IVUsers::dump() const { - print(dbgs()); -} +LLVM_DUMP_METHOD void IVUsers::dump() const { print(dbgs()); } #endif void IVUsers::releaseMemory() { @@ -319,6 +312,35 @@ void IVUsers::releaseMemory() { IVUses.clear(); } +IVUsersWrapperPass::IVUsersWrapperPass() : LoopPass(ID) { + initializeIVUsersWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +void IVUsersWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.setPreservesAll(); +} + +bool IVUsersWrapperPass::runOnLoop(Loop *L, LPPassManager &LPM) { + auto *AC = &getAnalysis().getAssumptionCache( + *L->getHeader()->getParent()); + auto *LI = &getAnalysis().getLoopInfo(); + auto *DT = &getAnalysis().getDomTree(); + auto *SE = &getAnalysis().getSE(); + + IU.reset(new IVUsers(L, AC, LI, DT, SE)); + return false; +} + +void IVUsersWrapperPass::print(raw_ostream &OS, const Module *M) const { + IU->print(OS, M); +} + +void IVUsersWrapperPass::releaseMemory() { IU->releaseMemory(); } + /// getReplacementExpr - Return a SCEV expression which computes the /// value of the OperandValToReplace. const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const { diff --git a/llvm/lib/CodeGen/MachineFunctionPass.cpp b/llvm/lib/CodeGen/MachineFunctionPass.cpp index 16aecb9..228fe17 100644 --- a/llvm/lib/CodeGen/MachineFunctionPass.cpp +++ b/llvm/lib/CodeGen/MachineFunctionPass.cpp @@ -78,7 +78,7 @@ void MachineFunctionPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp index b5d72d4..5cbbd73 100644 --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -32,6 +32,7 @@ #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/IVUsers.h" #include "llvm/Analysis/LazyCallGraph.h" #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/LoopAccessAnalysis.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def index 5ff803f..cfe2dc5 100644 --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -182,6 +182,7 @@ FUNCTION_PASS("verify", RegionInfoVerifierPass()) #endif LOOP_ANALYSIS("no-op-loop", NoOpLoopAnalysis()) LOOP_ANALYSIS("access-info", LoopAccessAnalysis()) +LOOP_ANALYSIS("ivusers", IVUsersAnalysis()) #undef LOOP_ANALYSIS #ifndef LOOP_PASS @@ -198,4 +199,5 @@ LOOP_PASS("loop-deletion", LoopDeletionPass()) LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass()) LOOP_PASS("indvars", IndVarSimplifyPass()) LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs())) +LOOP_PASS("print", IVUsersPrinterPass(dbgs())) #undef LOOP_PASS diff --git a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp index e49bd9e..77c77eb 100644 --- a/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -4949,7 +4949,7 @@ INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce", INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) -INITIALIZE_PASS_DEPENDENCY(IVUsers) +INITIALIZE_PASS_DEPENDENCY(IVUsersWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_END(LoopStrengthReduce, "loop-reduce", @@ -4979,8 +4979,8 @@ void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const { // Requiring LoopSimplify a second time here prevents IVUsers from running // twice, since LoopSimplify was invalidated by running ScalarEvolution. AU.addRequiredID(LoopSimplifyID); - AU.addRequired(); - AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); } @@ -4988,7 +4988,7 @@ bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) { if (skipLoop(L)) return false; - auto &IU = getAnalysis(); + auto &IU = getAnalysis().getIU(); auto &SE = getAnalysis().getSE(); auto &DT = getAnalysis().getDomTree(); auto &LI = getAnalysis().getLoopInfo(); diff --git a/llvm/test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll b/llvm/test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll index c6d6690..315ae8d 100644 --- a/llvm/test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll +++ b/llvm/test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -analyze -iv-users | FileCheck %s +; RUN: opt -passes='function(require),print' -S < %s 2>&1| FileCheck %s ; Provide legal integer types. target datalayout = "n8:16:32:64" -- 2.7.4