[PM] Convert IVUsers analysis to new pass manager.

[danielcdh]

Summary

Convert IVUsers analysis to new pass manager.

[silvas]

lgtm

include/llvm/ADT/ilist.h

iterator insert(iterator where, NodeTy *New) {
     else
       Head = New;
     this->setPrev(CurNode, New);
 
     this->addNodeToList(New);  // Notify traits that we added a node...
     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);
     else
       return insert(++where, New);
   }
 
   NodeTy *remove(iterator &IT) {

 
 
 template<typename NodeTy>
 struct ilist : public iplist<NodeTy> {
   typedef typename iplist<NodeTy>::size_type size_type;
   typedef typename iplist<NodeTy>::iterator iterator;
 
   ilist() {}
-  ilist(const ilist &right) {
+  ilist(const ilist &right) : iplist<NodeTy>() {
     insert(this->begin(), right.begin(), right.end());
   }
   explicit ilist(size_type count) {
     insert(this->begin(), count, NodeTy());
   }
   ilist(size_type count, const NodeTy &val) {
     insert(this->begin(), count, val);
   }

include/llvm/Analysis/IVUsers.h

template<> struct ilist_traits<IVStrideUse>
   IVStrideUse *provideInitialHead() const { return createSentinel(); }
   IVStrideUse *ensureHead(IVStrideUse*) const { return createSentinel(); }
   static void noteHead(IVStrideUse*, IVStrideUse*) {}
 
 private:
   mutable ilist_node<IVStrideUse> Sentinel;
 };
 
-class IVUsers : public LoopPass {
+class IVUsers {
   friend class IVStrideUse;
   Loop *L;
   AssumptionCache *AC;
   LoopInfo *LI;
   DominatorTree *DT;
   ScalarEvolution *SE;
   SmallPtrSet<Instruction*, 16> Processed;
 
   /// IVUses - A list of all tracked IV uses of induction variable expressions
   /// we are interested in.
   ilist<IVStrideUse> IVUses;
 
   // Ephemeral values used by @llvm.assume in this function.
   SmallPtrSet<const Value *, 32> 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; }
 
   /// AddUsersIfInteresting - Inspect the specified Instruction.  If it is a
   /// reducible SCEV, recursively add its users to the IVUsesByStride set and
   /// return true.  Otherwise, return false.
   bool AddUsersIfInteresting(Instruction *I);
 
public:
   const_iterator begin() const { return IVUses.begin(); }
   const_iterator end() const   { return IVUses.end(); }
   bool empty() const { return IVUses.empty(); }
 
   bool isIVUserOrOperand(Instruction *Inst) const {
     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<Loop*> &SimpleLoopNests);
 };
 
 Pass *createIVUsersPass();
 
+class IVUsersWrapperPass : public LoopPass {
+  std::unique_ptr<IVUsers> 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<IVUsersAnalysis> {
+  friend AnalysisInfoMixin<IVUsersAnalysis>;
+  static char PassID;
+
+public:
+  typedef IVUsers Result;
+
+  IVUsers run(Loop &L, AnalysisManager<Loop> &AM);
+};
+
+/// Printer pass for the \c IVUsers for a loop.
+class IVUsersPrinterPass : public PassInfoMixin<IVUsersPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit IVUsersPrinterPass(raw_ostream &OS) : OS(OS) {}
+  PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM);
+};
 }
 
 #endif

include/llvm/InitializePasses.h

 void initializeGlobalDCELegacyPassPass(PassRegistry&);
 void initializeGlobalMergePass(PassRegistry&);
 void initializeGlobalOptLegacyPassPass(PassRegistry&);
 void initializeGlobalsAAWrapperPassPass(PassRegistry&);
 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&);
 void initializeInductiveRangeCheckEliminationPass(PassRegistry&);
 void initializeInferFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeInlineCostAnalysisPass(PassRegistry&);
 void initializeInstCountPass(PassRegistry&);
 void initializeInstNamerPass(PassRegistry&);

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeDomOnlyViewerPass(Registry);
   initializePostDomViewerPass(Registry);
   initializeDomOnlyPrinterPass(Registry);
   initializePostDomPrinterPass(Registry);
   initializePostDomOnlyViewerPass(Registry);
   initializePostDomOnlyPrinterPass(Registry);
   initializeAAResultsWrapperPassPass(Registry);
   initializeGlobalsAAWrapperPassPass(Registry);
-  initializeIVUsersPass(Registry);
+  initializeIVUsersWrapperPassPass(Registry);
   initializeInstCountPass(Registry);
   initializeIntervalPartitionPass(Registry);
   initializeLazyBlockFrequencyInfoPassPass(Registry);
   initializeLazyValueInfoWrapperPassPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);

lib/Analysis/IVUsers.cpp

 //===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements bookkeeping for "interesting" users of expressions
 // computed from induction variables.
 //
 //===----------------------------------------------------------------------===//
 
+#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"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 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<Loop> &AM) {
+  const auto &FAM =
+      AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
+  Function *F = L.getHeader()->getParent();
+
+  return IVUsers(&L, FAM.getCachedResult<AssumptionAnalysis>(*F),
+                 FAM.getCachedResult<LoopAnalysis>(*F),
+                 FAM.getCachedResult<DominatorTreeAnalysis>(*F),
+                 FAM.getCachedResult<ScalarEvolutionAnalysis>(*F));
+}
+
+PreservedAnalyses IVUsersPrinterPass::run(Loop &L, AnalysisManager<Loop> &AM) {
+  AM.getResult<IVUsersAnalysis>(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
 /// given loop.
 static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
                           ScalarEvolution *SE, LoopInfo *LI) {
   // An addrec is interesting if it's affine or if it has an interesting start.
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
bool IVUsers::AddUsersIfInteresting(Instruction *I) {
   return AddUsersImpl(I, SimpleLoopNests);
 }
 
 IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) {
   IVUses.push_back(new IVStrideUse(this, User, Operand));
   return IVUses.back();
 }
 
-IVUsers::IVUsers()
-    : LoopPass(ID) {
-  initializeIVUsersPass(*PassRegistry::getPassRegistry());
-}
-
-void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.addRequired<AssumptionCacheTracker>();
-  AU.addRequired<LoopInfoWrapperPass>();
-  AU.addRequired<DominatorTreeWrapperPass>();
-  AU.addRequired<ScalarEvolutionWrapperPass>();
-  AU.setPreservesAll();
-}
-
-bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
-
-  L = l;
-  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
-      *L->getHeader()->getParent());
-  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  SE = &getAnalysis<ScalarEvolutionWrapperPass>().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);
 
   // Find all uses of induction variables in this loop, and categorize
   // them by stride.  Start by finding all of the PHI nodes in the header for
   // this loop.  If they are induction variables, inspect their uses.
   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(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";
 
   for (const IVStrideUse &IVUse : IVUses) {
     OS << "  ";
     IVUse.getOperandValToReplace()->printAsOperand(OS, false);
     OS << " = " << *getReplacementExpr(IVUse);
     for (auto PostIncLoop : IVUse.PostIncLoops) {
       OS << " (post-inc with loop ";
       PostIncLoop->getHeader()->printAsOperand(OS, false);
       OS << ")";
     }
     OS << " in  ";
     if (IVUse.getUser())
       IVUse.getUser()->print(OS);
     else
       OS << "Printing <null> User";
     OS << '\n';
   }
 }
 
 #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() {
   Processed.clear();
   IVUses.clear();
 }
 
+IVUsersWrapperPass::IVUsersWrapperPass() : LoopPass(ID) {
+  initializeIVUsersWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+void IVUsersWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<AssumptionCacheTracker>();
+  AU.addRequired<LoopInfoWrapperPass>();
+  AU.addRequired<DominatorTreeWrapperPass>();
+  AU.addRequired<ScalarEvolutionWrapperPass>();
+  AU.setPreservesAll();
+}
+
+bool IVUsersWrapperPass::runOnLoop(Loop *L, LPPassManager &LPM) {
+  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
+      *L->getHeader()->getParent());
+  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().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 {
   return SE->getSCEV(IU.getOperandValToReplace());
 }
 
 /// getExpr - Return the expression for the use.
 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const {

lib/CodeGen/MachineFunctionPass.cpp

void MachineFunctionPass::getAnalysisUsage(AnalysisUsage &AU) const {
   // passes explicitly. This does not include setPreservesCFG,
   // because CodeGen overloads that to mean preserving the MachineBasicBlock
   // CFG in addition to the LLVM IR CFG.
   AU.addPreserved<BasicAAWrapperPass>();
   AU.addPreserved<DominanceFrontierWrapperPass>();
   AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addPreserved<AAResultsWrapperPass>();
   AU.addPreserved<GlobalsAAWrapperPass>();
-  AU.addPreserved<IVUsers>();
+  AU.addPreserved<IVUsersWrapperPass>();
   AU.addPreserved<LoopInfoWrapperPass>();
   AU.addPreserved<MemoryDependenceWrapperPass>();
   AU.addPreserved<ScalarEvolutionWrapperPass>();
   AU.addPreserved<SCEVAAWrapperPass>();
   AU.addPreserved<StackProtector>();
 
   FunctionPass::getAnalysisUsage(AU);
 }

lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #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/IVUsers.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/RegionInfo.h"

lib/Passes/PassRegistry.def

 FUNCTION_PASS("verify<regions>", RegionInfoVerifierPass())
 #undef FUNCTION_PASS
 
 #ifndef LOOP_ANALYSIS
 #define LOOP_ANALYSIS(NAME, CREATE_PASS)
 #endif
 LOOP_ANALYSIS("no-op-loop", NoOpLoopAnalysis())
 LOOP_ANALYSIS("access-info", LoopAccessAnalysis())
+LOOP_ANALYSIS("ivusers", IVUsersAnalysis())
 #undef LOOP_ANALYSIS
 
 #ifndef LOOP_PASS
 #define LOOP_PASS(NAME, CREATE_PASS)
 #endif
 LOOP_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 LOOP_PASS("licm", LICMPass())
 LOOP_PASS("loop-idiom", LoopIdiomRecognizePass())
 LOOP_PASS("loop-instsimplify", LoopInstSimplifyPass())
 LOOP_PASS("rotate", LoopRotatePass())
 LOOP_PASS("no-op-loop", NoOpLoopPass())
 LOOP_PASS("print", PrintLoopPass(dbgs()))
 LOOP_PASS("loop-deletion", LoopDeletionPass())
 LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass())
 LOOP_PASS("indvars", IndVarSimplifyPass())
 LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs()))
+LOOP_PASS("print<ivusers>", IVUsersPrinterPass(dbgs()))
 #undef LOOP_PASS

lib/Transforms/Scalar/LoopStrengthReduce.cpp

 }
 
 char LoopStrengthReduce::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce",
                 "Loop Strength Reduction", false, false)
 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",
                 "Loop Strength Reduction", false, false)
 
 
 Pass *llvm::createLoopStrengthReducePass() {
   return new LoopStrengthReduce();
void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequiredID(LoopSimplifyID);
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addRequired<ScalarEvolutionWrapperPass>();
   AU.addPreserved<ScalarEvolutionWrapperPass>();
   // Requiring LoopSimplify a second time here prevents IVUsers from running
   // twice, since LoopSimplify was invalidated by running ScalarEvolution.
   AU.addRequiredID(LoopSimplifyID);
-  AU.addRequired<IVUsers>();
-  AU.addPreserved<IVUsers>();
+  AU.addRequired<IVUsersWrapperPass>();
+  AU.addPreserved<IVUsersWrapperPass>();
   AU.addRequired<TargetTransformInfoWrapperPass>();
 }
 
 bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) {
   if (skipLoop(L))
     return false;
 
-  auto &IU = getAnalysis<IVUsers>();
+  auto &IU = getAnalysis<IVUsersWrapperPass>().getIU();
   auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   const auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
       *L->getHeader()->getParent());
   bool Changed = false;
 
   // Run the main LSR transformation.

test/Transforms/LoopStrengthReduce/quadradic-exit-value.ll

 ; RUN: opt < %s -analyze -iv-users | FileCheck %s
+; RUN: opt -passes='function(require<scalar-evolution>),print<ivusers>' -S < %s 2>&1| FileCheck %s
 
 ; Provide legal integer types.
 target datalayout = "n8:16:32:64"
 
 ; The value of %r is dependent on a polynomial iteration expression.
 ;
 ; CHECK-LABEL: IV Users for loop %foo.loop
 ; CHECK: {1,+,3,+,2}<%foo.loop>