[LPM] Teach the legacy pass manager to support *using* an analysis without *requiring* it.

[chandlerc]

Summary

This let's a pass indicate that it will use an analysis if available
(through getAnalysisIfAvailable). When the pass manager knows this, it
will refrain from deleting that analysis if it can. Naturally, it will
still get invalidated at the correct time. These passes are not
considered when scheduling the pass pipeline, so typically they will
require manual scheduling, but this may also allow passes with
getAnalysisIfAvailable to find the analysis more often if nothing after
them requires that analysis and it wasn't invalidated.

I don't have a particular use case with the current passes, but with my
new structure for alias analyses, this will be very useful. We want to
allow people to customize the set of AAs available by scheduling
additional passes. These's aren't ever *required* for obvious reasons.
So we need some way to mark in the legacy pass manager that they will
still be used if available.

This is essentially how analysis groups already work. But this makes the
feature generally available and more explicit. It should allow the AA
change to not impact how people trigger a custom alias analysis being
available at a certain point in compilation.

[hfinkel]

This seems really nice; if I understand correctly what this does, it fixes a long-standing bug (assuming that the passes themselves are updated). I recall writing workarounds in regression tests like this (in test/Transforms/InstCombine/assume-loop-align.ll):

; RUN: opt -domtree -instcombine -loops -S < %s | FileCheck %s
; Note: The -loops above can be anything that requires the domtree, and is
; necessary to work around a pass-manager bug.

(I don't know if we currently have a good example in a regression test because, since instcombine was changed to require a domtree, the workaround in this specific test should no longer be necessary).

include/llvm/PassAnalysisSupport.h

95 ↗

(On Diff #32446)

Should we call this addUsedIfAvailable, or similar, to make it clearer what this does (and, specifically, how it differs from addRequired)?

[chandlerc]

include/llvm/PassAnalysisSupport.h

95 ↗

(On Diff #32446)

Seems a small gain, but if you like. I don't really care. You (or others) give me a spelling.

[hfinkel]

include/llvm/PassAnalysisSupport.h

95 ↗

(On Diff #32446)

Eh; many things changed during code review have small gains ;)

I think that addUsedIfAvailable goes well with getAnalysisIfAvailable. If anyone else has a preference, please speak up.

[chandlerc]

Thanks, submitting with the suggested change from Hal based on his feedback.

Feel free to grumble about better names in post-commit review if needed.

include/llvm/PassAnalysisSupport.h

95 ↗

(On Diff #32446)

Done and submitting. Thanks!

llvm/trunk/include/llvm/IR/LegacyPassManagers.h

for (unsigned i = 0; i < PMT_Last; ++i)
       InheritedAnalysis[i] = nullptr;
   }
 
   // Return true if P preserves high level analysis used by other
   // passes that are managed by this manager.
   bool preserveHigherLevelAnalysis(Pass *P);
 
 
-  /// Populate RequiredPasses with analysis pass that are required by
-  /// pass P and are available. Populate ReqPassNotAvailable with analysis
-  /// pass that are required by pass P but are not available.
-  void collectRequiredAnalysis(SmallVectorImpl<Pass *> &RequiredPasses,
-                               SmallVectorImpl<AnalysisID> &ReqPassNotAvailable,
-                               Pass *P);
+  /// Populate UsedPasses with analysis pass that are used or required by pass
+  /// P and are available. Populate ReqPassNotAvailable with analysis pass that
+  /// are required by pass P but are not available.
+  void collectRequiredAndUsedAnalyses(
+      SmallVectorImpl<Pass *> &UsedPasses,
+      SmallVectorImpl<AnalysisID> &ReqPassNotAvailable, Pass *P);
 
   /// All Required analyses should be available to the pass as it runs!  Here
   /// we fill in the AnalysisImpls member of the pass so that it can
   /// successfully use the getAnalysis() method to retrieve the
   /// implementations it needs.
   void initializeAnalysisImpl(Pass *P);
 
   /// Find the pass that implements Analysis AID. If desired pass is not found
public:
 
   // Print routines used by debug-pass
   void dumpLastUses(Pass *P, unsigned Offset) const;
   void dumpPassArguments() const;
   void dumpPassInfo(Pass *P, enum PassDebuggingString S1,
                     enum PassDebuggingString S2, StringRef Msg);
   void dumpRequiredSet(const Pass *P) const;
   void dumpPreservedSet(const Pass *P) const;
+  void dumpUsedSet(const Pass *P) const;
 
   unsigned getNumContainedPasses() const {
     return (unsigned)PassVector.size();
   }
 
   virtual PassManagerType getPassManagerType() const {
     assert ( 0 && "Invalid use of getPassManagerType");
     return PMT_Unknown;

llvm/trunk/include/llvm/PassAnalysisSupport.h

 /// infrastructure through the getAnalysisUsage virtual function.
 ///
 class AnalysisUsage {
 public:
   typedef SmallVector<AnalysisID, 32> VectorType;
 
 private:
   /// Sets of analyses required and preserved by a pass
-  VectorType Required, RequiredTransitive, Preserved;
+  VectorType Required, RequiredTransitive, Preserved, Used;
   bool PreservesAll;
 
 public:
   AnalysisUsage() : PreservesAll(false) {}
 
   ///@{
   /// Add the specified ID to the required set of the usage info for a pass.
   AnalysisUsage &addRequiredID(const void *ID);
public:
   /// Add the specified Pass class to the set of analyses preserved by this pass.
   template<class PassClass>
   AnalysisUsage &addPreserved() {
     Preserved.push_back(&PassClass::ID);
     return *this;
   }
   ///@}
 
+  ///@{
+  /// Add the specified ID to the set of analyses used by this pass if they are
+  /// available..
+  AnalysisUsage &addUsedIfAvailableID(const void *ID) {
+    Used.push_back(ID);
+    return *this;
+  }
+  AnalysisUsage &addUsedIfAvailableID(char &ID) {
+    Used.push_back(&ID);
+    return *this;
+  }
+  /// Add the specified Pass class to the set of analyses used by this pass.
+  template<class PassClass>
+  AnalysisUsage &addUsedIfAvailable() {
+    Used.push_back(&PassClass::ID);
+    return *this;
+  }
+  ///@}
+
   /// Add the Pass with the specified argument string to the set of analyses
   /// preserved by this pass. If no such Pass exists, do nothing. This can be
   /// useful when a pass is trivially preserved, but may not be linked in. Be
   /// careful about spelling!
   AnalysisUsage &addPreserved(StringRef Arg);
 
   /// Set by analyses that do not transform their input at all
   void setPreservesAll() { PreservesAll = true; }
public:
   ///
   void setPreservesCFG();
 
   const VectorType &getRequiredSet() const { return Required; }
   const VectorType &getRequiredTransitiveSet() const {
     return RequiredTransitive;
   }
   const VectorType &getPreservedSet() const { return Preserved; }
+  const VectorType &getUsedSet() const { return Used; }
 };
 
 //===----------------------------------------------------------------------===//
 /// AnalysisResolver - Simple interface used by Pass objects to pull all
 /// analysis information out of pass manager that is responsible to manage
 /// the pass.
 ///
 class PMDataManager;

llvm/trunk/lib/IR/LegacyPassManager.cpp

void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
   if (!ProcessAnalysis) {
     // Add pass
     PassVector.push_back(P);
     return;
   }
 
   // At the moment, this pass is the last user of all required passes.
   SmallVector<Pass *, 12> LastUses;
-  SmallVector<Pass *, 8> RequiredPasses;
+  SmallVector<Pass *, 8> UsedPasses;
   SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
 
   unsigned PDepth = this->getDepth();
 
-  collectRequiredAnalysis(RequiredPasses,
-                          ReqAnalysisNotAvailable, P);
-  for (Pass *PRequired : RequiredPasses) {
+  collectRequiredAndUsedAnalyses(UsedPasses, ReqAnalysisNotAvailable, P);
+  for (Pass *PUsed : UsedPasses) {
     unsigned RDepth = 0;
 
-    assert(PRequired->getResolver() && "Analysis Resolver is not set");
-    PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
+    assert(PUsed->getResolver() && "Analysis Resolver is not set");
+    PMDataManager &DM = PUsed->getResolver()->getPMDataManager();
     RDepth = DM.getDepth();
 
     if (PDepth == RDepth)
-      LastUses.push_back(PRequired);
+      LastUses.push_back(PUsed);
     else if (PDepth > RDepth) {
       // Let the parent claim responsibility of last use
-      TransferLastUses.push_back(PRequired);
+      TransferLastUses.push_back(PUsed);
       // Keep track of higher level analysis used by this manager.
-      HigherLevelAnalysis.push_back(PRequired);
+      HigherLevelAnalysis.push_back(PUsed);
     } else
-      llvm_unreachable("Unable to accommodate Required Pass");
+      llvm_unreachable("Unable to accommodate Used Pass");
   }
 
   // Set P as P's last user until someone starts using P.
   // However, if P is a Pass Manager then it does not need
   // to record its last user.
   if (!P->getAsPMDataManager())
     LastUses.push_back(P);
   TPM->setLastUser(LastUses, P);
void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
   removeNotPreservedAnalysis(P);
   recordAvailableAnalysis(P);
 
   // Add pass
   PassVector.push_back(P);
 }
 
 
-/// Populate RP with analysis pass that are required by
+/// Populate UP with analysis pass that are used or required by
 /// pass P and are available. Populate RP_NotAvail with analysis
 /// pass that are required by pass P but are not available.
-void PMDataManager::collectRequiredAnalysis(SmallVectorImpl<Pass *> &RP,
-                                       SmallVectorImpl<AnalysisID> &RP_NotAvail,
-                                            Pass *P) {
+void PMDataManager::collectRequiredAndUsedAnalyses(
+    SmallVectorImpl<Pass *> &UP, SmallVectorImpl<AnalysisID> &RP_NotAvail,
   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
+
+  for (const auto &UsedID : AnUsage->getUsedSet())
+    if (Pass *AnalysisPass = findAnalysisPass(UsedID, true))
+      UP.push_back(AnalysisPass);
+
   for (const auto &RequiredID : AnUsage->getRequiredSet())
     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
-      RP.push_back(AnalysisPass);
+      UP.push_back(AnalysisPass);
     else
       RP_NotAvail.push_back(RequiredID);
 
   for (const auto &RequiredID : AnUsage->getRequiredTransitiveSet())
     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
-      RP.push_back(AnalysisPass);
+      UP.push_back(AnalysisPass);
     else
       RP_NotAvail.push_back(RequiredID);
 }
 
 // All Required analyses should be available to the pass as it runs!  Here
 // we fill in the AnalysisImpls member of the pass so that it can
 // successfully use the getAnalysis() method to retrieve the
 // implementations it needs.
void PMDataManager::dumpPreservedSet(const Pass *P) const {
   if (PassDebugging < Details)
     return;
 
   AnalysisUsage analysisUsage;
   P->getAnalysisUsage(analysisUsage);
   dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet());
 }
 
+void PMDataManager::dumpUsedSet(const Pass *P) const {
+  if (PassDebugging < Details)
+    return;
+
+  AnalysisUsage analysisUsage;
+  P->getAnalysisUsage(analysisUsage);
+  dumpAnalysisUsage("Used", P, analysisUsage.getUsedSet());
+}
+
 void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P,
                                    const AnalysisUsage::VectorType &Set) const {
   assert(PassDebugging >= Details);
   if (Set.empty())
     return;
   dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
   for (unsigned i = 0; i != Set.size(); ++i) {
     if (i) dbgs() << ',';
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
         LocalChanged |= BP->runOnBasicBlock(*I);
       }
 
       Changed |= LocalChanged;
       if (LocalChanged)
         dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
                      I->getName());
       dumpPreservedSet(BP);
+      dumpUsedSet(BP);
 
       verifyPreservedAnalysis(BP);
       removeNotPreservedAnalysis(BP);
       recordAvailableAnalysis(BP);
       removeDeadPasses(BP, I->getName(), ON_BASICBLOCK_MSG);
     }
 
   return doFinalization(F) || Changed;
initializeAnalysisImpl(FP);
 
       LocalChanged |= FP->runOnFunction(F);
     }
 
     Changed |= LocalChanged;
     if (LocalChanged)
       dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
     dumpPreservedSet(FP);
+    dumpUsedSet(FP);
 
     verifyPreservedAnalysis(FP);
     removeNotPreservedAnalysis(FP);
     recordAvailableAnalysis(FP);
     removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
   }
   return Changed;
 }
initializeAnalysisImpl(MP);
       LocalChanged |= MP->runOnModule(M);
     }
 
     Changed |= LocalChanged;
     if (LocalChanged)
       dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
                    M.getModuleIdentifier());
     dumpPreservedSet(MP);
+    dumpUsedSet(MP);
 
     verifyPreservedAnalysis(MP);
     removeNotPreservedAnalysis(MP);
     recordAvailableAnalysis(MP);
     removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG);
   }
 
   // Finalize module passes