Track validity of pass results

[sepavloff]

Summary

This change introduces a flag in the Pass class to mark passes that have
valid results. The flag is set when the pass is run and cleared if it is
skipped or freed.

The flag allows to avoid verification when it is not possible. With the change more
than 500 failing test now pass in the builds with expensive checks enabled.

[sepavloff]

Made use of the availability flag more consistent.

[sepavloff]

Adapted a test to check loop verification.

[davide]

As this touches the internals of the pass manager, I'll be more confident to see this one going in if @chandlerc reviews it.

[chandlerc]

Generally I like where this is going, especially as it gives us a nice assert for getAnalysis that would have cought several bugs for me.

However, I'd really like to isolate this for analysis passes only so that we don't have to do so much with skipFunction. Is there no way to do that? Relatedly, the logic for when to set things available doesn't really make sense in the current patch. Might just need comments, but it seems very non-obvious when things become available.

include/llvm/Pass.h

86

I wouldn't put the doxygen comment here (or use end-of-line doxygen generally). Instead see my comment below...

97

This needs a doxygen comment as much or more than the rest. =] I also wouldn't try to group with the above method.

99–102

Does this need to be virtual? It seems a waste just for immutable passes. Is it even necessary there? It seems like those should be handled by the existing logic...

Also, I would find a 'setAvailable' without a default argument more clear. Or two functions, one to mark and one to clear.

lib/Analysis/LoopInfo.cpp

730–734

This looks like it is working around a bug. We should always have domtree when we are running LoopInfo...

lib/Analysis/LoopPass.cpp

178

I don't understand why passes are being marked available here?

[sepavloff]

Addressed reviewer's notes.

[sepavloff]

However, I'd really like to isolate this for analysis passes only so that we don't have to do so much with skipFunction.

This facility indeed is used only for analysis passes. However analysis passes share the same code path with non-analysis ones and it is easier to maintain the flag for all passes. Besides there is no simple way to know if this particular pass is an analysis. There is a comment to PassInfo that states it can be obtained from a Pass by getPassInfo (https://github.com/llvm-mirror/llvm/blob/master/include/llvm/PassInfo.h#L28-L29), however such method does not exist in Pass.

On the other hand the new flag is not tied to analysis only, actually it tracks the fact whether the pass was executed or not. I renamed the flag to Executed and associated function accordingly in hope that the code becomes clearer.

Relatedly, the logic for when to set things available doesn't really make sense in the current patch. Might just need comments, but it seems very non-obvious when things become available.

When the flag must change is described in the comment to the method setExecuted.

include/llvm/Pass.h

99–102

The method is no more virtual. It however required a check in freePass to avoid invalidation of immutable passes. There is no default argument now.

lib/Analysis/LoopInfo.cpp

730–734

This is not about running LoopInfo, it is about *verification* of it. This method are run by a pass that clams it preserves LoopInfo. The LoopInfo results are valid at this point, but DomTree may be already freed because the last user of it has already executed.

Generally we have at least three options here:

• skip verification if DomTree is not available,
• do not free unneeded passes if verification is required,
• make passes transitively dependent on passes required for verification.

Of these options the first is the most obvious and the least pervasive.

lib/Analysis/LoopPass.cpp

178

Unneeded change. Removed.

[davide]

In D27190#615533, @sepavloff wrote:

However, I'd really like to isolate this for analysis passes only so that we don't have to do so much with skipFunction.

This facility indeed is used only for analysis passes. However analysis passes share the same code path with non-analysis ones and it is easier to maintain the flag for all passes. Besides there is no simple way to know if this particular pass is an analysis. There is a comment to PassInfo that states it can be obtained from a Pass by getPassInfo (https://github.com/llvm-mirror/llvm/blob/master/include/llvm/PassInfo.h#L28-L29), however such method does not exist in Pass.

On the other hand the new flag is not tied to analysis only, actually it tracks the fact whether the pass was executed or not. I renamed the flag to Executed and associated function accordingly in hope that the code becomes clearer.

Relatedly, the logic for when to set things available doesn't really make sense in the current patch. Might just need comments, but it seems very non-obvious when things become available.

When the flag must change is described in the comment to the method setExecuted.

ping @chandlerc

[davide]

I looked at this more closely and I guess it's correct. Please wait for @chandlerc to sign-off, though.

[mehdi_amini]

Did @chandlerc approve?

[mehdi_amini]

Ping?

[chandlerc]

In D27190#644818, @mehdi_amini wrote:

Did @chandlerc approve?

No...

And I'm not a big fan. I don't understand why we can't make this specific to analyses, or whether it's really worthwhile if we can't...

[davide]

I lost track of this. Please revert as Chandler raised some concerns about the approach. Please also consider to wait if you're asked to.

[sepavloff]

Reverted in r292062.
I am sorry for misunderstanding.

include/llvm/Pass.h

 // bottom), so the APIs exposed by these files are also automatically available
 // to all users of this file.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_PASS_H
 #define LLVM_PASS_H
 
+#include <assert.h>
 #include <string>
 
 namespace llvm {
 
 class BasicBlock;
 class Function;
 class Module;
 class AnalysisUsage;

 /// Pass interface - Implemented by all 'passes'.  Subclass this if you are an
 /// interprocedural optimization or you do not fit into any of the more
 /// constrained passes described below.
 ///
 class Pass {
   AnalysisResolver *Resolver;  // Used to resolve analysis
   const void *PassID;
   PassKind Kind;
+  bool Executed;
+
   void operator=(const Pass&) = delete;
   Pass(const Pass &) = delete;
 
 public:
   explicit Pass(PassKind K, char &pid)
-    : Resolver(nullptr), PassID(&pid), Kind(K) { }
+    : Resolver(nullptr), PassID(&pid), Kind(K), Executed(false) { }
   virtual ~Pass();
 
-
   PassKind getPassKind() const { return Kind; }
 
+  /// Returns true if the pass has already executed.
+  ///
+  /// For an analysis pass it means the result is available. If the function
+  /// returns false, the pass was not run, was skipped or freed.
+  ///
+  bool isExecuted() const { return Executed; }
+
+  /// Marks the pass as executed or not.
+  ///
+  /// A pass should be marked as executed, if its 'runOn*' method successfully
+  /// finished. When the pass is not needed anymore, it is marked as
+  /// 'non-executed', it takes place in \c freePass. It also occurs when the
+  /// pass is skipped for some reason.
+  ///
+  /// The flag should be set prior to call to 'runOn*' method. If it decides
+  /// that the pass should be skipped, it will reset the flag.
+  ///
+  void setExecuted(bool x) {
+    assert(x || !getAsImmutablePass()); // Immutable pass cannot be invalidated.
+    Executed = x;
+  }
+
   /// getPassName - Return a nice clean name for a pass.  This usually
   /// implemented in terms of the name that is registered by one of the
   /// Registration templates, but can be overloaded directly.
   ///
   virtual StringRef getPassName() const;
 
   /// getPassID - Return the PassID number that corresponds to this pass.
   AnalysisID getPassID() const {
public:
   virtual void initializePass();
 
   ImmutablePass *getAsImmutablePass() override { return this; }
 
   /// ImmutablePasses are never run.
   ///
   bool runOnModule(Module &) override { return false; }
 
-  explicit ImmutablePass(char &pid)
-  : ModulePass(pid) {}
+  explicit ImmutablePass(char &pid) : ModulePass(pid) { setExecuted(true); }
 
   // Force out-of-line virtual method.
   ~ImmutablePass() override;
 };
 
 //===----------------------------------------------------------------------===//
 /// FunctionPass class - This class is used to implement most global
 /// optimizations.  Optimizations should subclass this class if they meet the
public:
   void assignPassManager(PMStack &PMS, PassManagerType T) override;
 
   ///  Return what kind of Pass Manager can manage this pass.
   PassManagerType getPotentialPassManagerType() const override;
 
 protected:
   /// Optional passes call this function to check whether the pass should be
   /// skipped. This is the case when Attribute::OptimizeNone is set or when
-  /// optimization bisect is over the limit.
-  bool skipFunction(const Function &F) const;
+  /// optimization bisect is over the limit. It also resets flag Executed on
+  /// the pass.
+  bool skipFunction(const Function &F);
 };
 
 
 
 //===----------------------------------------------------------------------===//
 /// BasicBlockPass class - This class is used to implement most local
 /// optimizations.  Optimizations should subclass this class if they
 /// meet the following constraints:

include/llvm/PassAnalysisSupport.h

 AnalysisType *Pass::getAnalysisIfAvailable() const {
   assert(Resolver && "Pass not resident in a PassManager object!");
 
   const void *PI = &AnalysisType::ID;
 
   Pass *ResultPass = Resolver->getAnalysisIfAvailable(PI, true);
   if (!ResultPass) return nullptr;
 
+  if (!ResultPass->isExecuted())
+    return nullptr;
+
   // Because the AnalysisType may not be a subclass of pass (for
   // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially
   // adjust the return pointer (because the class may multiply inherit, once
   // from pass, once from AnalysisType).
   return (AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI);
 }
 
 /// getAnalysis<AnalysisType>() - This function is used by subclasses to get
AnalysisType &Pass::getAnalysisID(AnalysisID PI) const {
   assert(Resolver&&"Pass has not been inserted into a PassManager object!");
   // PI *must* appear in AnalysisImpls.  Because the number of passes used
   // should be a small number, we just do a linear search over a (dense)
   // vector.
   Pass *ResultPass = Resolver->findImplPass(PI);
   assert (ResultPass && 
           "getAnalysis*() called on an analysis that was not "
           "'required' by pass!");
+  assert(ResultPass->isExecuted() &&
+         "getAnalysis*() called on an analysis that was freed");
 
   // Because the AnalysisType may not be a subclass of pass (for
   // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially
   // adjust the return pointer (because the class may multiply inherit, once
   // from pass, once from AnalysisType).
   return *(AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI);
 }
 

lib/Analysis/CallGraphSCCPass.cpp

bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
   #endif
       dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
     }
     dumpRequiredSet(P);
     
     initializeAnalysisImpl(P);
     
     // Actually run this pass on the current SCC.
+    P->setExecuted(true);
     Changed |= RunPassOnSCC(P, CurSCC, CG,
                             CallGraphUpToDate, DevirtualizedCall);
     
     if (Changed)
       dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
     dumpPreservedSet(P);
     
     verifyPreservedAnalysis(P);      

lib/Analysis/LoopInfo.cpp

 
 void LoopInfoWrapperPass::verifyAnalysis() const {
   // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
   // function each time verifyAnalysis is called is very expensive. The
   // -verify-loop-info option can enable this. In order to perform some
   // checking by default, LoopPass has been taught to call verifyLoop manually
   // during loop pass sequences.
   if (VerifyLoopInfo) {
-    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    if (auto *Analysis = getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {
+      auto &DT = Analysis->getDomTree();
       LI.verify(DT);
     }
   }
+}
 
 void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<DominatorTreeWrapperPass>();
 }
 
 void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
   LI.print(OS);

lib/Analysis/LoopPass.cpp

bool LPPassManager::runOnFunction(Function &F) {
 
   if (LQ.empty()) // No loops, skip calling finalizers
     return false;
 
   // Initialization
   for (Loop *L : LQ) {
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       LoopPass *P = getContainedPass(Index);
       Changed |= P->doInitialization(L, *this);
     }
   }
 
   // Walk Loops
   while (!LQ.empty()) {
     bool LoopWasDeleted = false;
     CurrentLoop = LQ.back();
 
     // Run all passes on the current Loop.
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       LoopPass *P = getContainedPass(Index);
 
       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
                    CurrentLoop->getHeader()->getName());
       dumpRequiredSet(P);
 
       initializeAnalysisImpl(P);
 
       {
         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
         TimeRegion PassTimer(getPassTimer(P));
 
+        P->setExecuted(true);
         Changed |= P->runOnLoop(CurrentLoop, *this);
       }
       LoopWasDeleted = CurrentLoop->isInvalid();
 
       if (Changed)
         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
                      LoopWasDeleted ? "<deleted>"
                                     : CurrentLoop->getHeader()->getName());

lib/CodeGen/MachineDominators.cpp

MachineDominatorTree::~MachineDominatorTree() {
   delete DT;
 }
 
 void MachineDominatorTree::releaseMemory() {
   DT->releaseMemory();
 }
 
 void MachineDominatorTree::verifyAnalysis() const {
-  if (VerifyMachineDomInfo)
+  if (VerifyMachineDomInfo && isExecuted())
     verifyDomTree();
 }
 
 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
   DT->print(OS);
 }
 
 void MachineDominatorTree::applySplitCriticalEdges() const {

lib/CodeGen/MachineFunctionPass.cpp

 Pass *MachineFunctionPass::createPrinterPass(raw_ostream &O,
                                              const std::string &Banner) const {
   return createMachineFunctionPrinterPass(O, Banner);
 }
 
 bool MachineFunctionPass::runOnFunction(Function &F) {
   // Do not codegen any 'available_externally' functions at all, they have
   // definitions outside the translation unit.
-  if (F.hasAvailableExternallyLinkage())
+  if (F.hasAvailableExternallyLinkage()) {
+    setExecuted(false);
     return false;
+  }
 
   MachineModuleInfo &MMI = getAnalysis<MachineModuleInfo>();
   MachineFunction &MF = MMI.getMachineFunction(F);
 
   MachineFunctionProperties &MFProps = MF.getProperties();
 
 #ifndef NDEBUG
   if (!MFProps.verifyRequiredProperties(RequiredProperties)) {

lib/IR/LegacyPassManager.cpp

if (const PassInfo *PInf = TPM->findAnalysisPassInfo(PI)) {
     const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
     for (unsigned i = 0, e = II.size(); i != e; ++i) {
       DenseMap<AnalysisID, Pass*>::iterator Pos =
         AvailableAnalysis.find(II[i]->getTypeInfo());
       if (Pos != AvailableAnalysis.end() && Pos->second == P)
         AvailableAnalysis.erase(Pos);
     }
   }
+
+  if (!P->getAsImmutablePass())
+    P->setExecuted(false);
 }
 
 /// Add pass P into the PassVector. Update
 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
 void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
   // This manager is going to manage pass P. Set up analysis resolver
   // to connect them.
   AnalysisResolver *AR = new AnalysisResolver(*this);
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 
       initializeAnalysisImpl(BP);
 
       {
         // If the pass crashes, remember this.
         PassManagerPrettyStackEntry X(BP, *I);
         TimeRegion PassTimer(getPassTimer(BP));
 
+        BP->setExecuted(true);
         LocalChanged |= BP->runOnBasicBlock(*I);
       }
 
       Changed |= LocalChanged;
       if (LocalChanged)
         dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
                      I->getName());
       dumpPreservedSet(BP);

 // Execute all the passes managed by this top level manager.
 // Return true if any function is modified by a pass.
 bool FunctionPassManagerImpl::run(Function &F) {
   bool Changed = false;
   TimingInfo::createTheTimeInfo();
 
   initializeAllAnalysisInfo();
   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
-    Changed |= getContainedManager(Index)->runOnFunction(F);
+    FPPassManager *P = getContainedManager(Index);
+    P->setExecuted(true);
+    Changed |= P->runOnFunction(F);
     F.getContext().yield();
   }
 
   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
     getContainedManager(Index)->cleanup();
 
   wasRun = true;
   return Changed;
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     dumpRequiredSet(FP);
 
     initializeAnalysisImpl(FP);
 
     {
       PassManagerPrettyStackEntry X(FP, F);
       TimeRegion PassTimer(getPassTimer(FP));
 
+      FP->setExecuted(true);
       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;
 }
 
 bool FPPassManager::runOnModule(Module &M) {
   bool Changed = false;
 
-  for (Function &F : M)
+  for (Function &F : M) {
+    setExecuted(true);
     Changed |= runOnFunction(F);
+  }
 
   return Changed;
 }
 
 bool FPPassManager::doInitialization(Module &M) {
   bool Changed = false;
 
   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     dumpRequiredSet(MP);
 
     initializeAnalysisImpl(MP);
 
     {
       PassManagerPrettyStackEntry X(MP, M);
       TimeRegion PassTimer(getPassTimer(MP));
 
+      MP->setExecuted(true);
       LocalChanged |= MP->runOnModule(M);
     }
 
     Changed |= LocalChanged;
     if (LocalChanged)
       dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
                    M.getModuleIdentifier());
     dumpPreservedSet(MP);
bool PassManagerImpl::run(Module &M) {
   dumpArguments();
   dumpPasses();
 
   for (ImmutablePass *ImPass : getImmutablePasses())
     Changed |= ImPass->doInitialization(M);
 
   initializeAllAnalysisInfo();
   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
-    Changed |= getContainedManager(Index)->runOnModule(M);
+    MPPassManager *P = getContainedManager(Index);
+    P->setExecuted(true);
+    Changed |= P->runOnModule(M);
     M.getContext().yield();
   }
 
   for (ImmutablePass *ImPass : getImmutablePasses())
     Changed |= ImPass->doFinalization(M);
 
   return Changed;
 }

lib/IR/Pass.cpp

Pass *FunctionPass::createPrinterPass(raw_ostream &O,
                                       const std::string &Banner) const {
   return createPrintFunctionPass(O, Banner);
 }
 
 PassManagerType FunctionPass::getPotentialPassManagerType() const {
   return PMT_FunctionPassManager;
 }
 
-bool FunctionPass::skipFunction(const Function &F) const {
-  if (!F.getContext().getOptBisect().shouldRunPass(this, F))
+bool FunctionPass::skipFunction(const Function &F) {
+  if (!F.getContext().getOptBisect().shouldRunPass(this, F)) {
+    setExecuted(false);
     return true;
+  }
 
   if (F.hasFnAttribute(Attribute::OptimizeNone)) {
     DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' on function "
                  << F.getName() << "\n");
+    setExecuted(false);
     return true;
   }
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 // BasicBlockPass Implementation
 //

test/CodeGen/Generic/externally_available.ll

-; RUN: llc < %s | not grep test_
+; RUN: llc -verify-machine-dom-info < %s | not grep test_
 
 ; test_function should not be emitted to the .s file.
 define available_externally i32 @test_function() {
   ret i32 4
 }
 
 ; test_global should not be emitted to the .s file.
 @test_global = available_externally global i32 4
 

test/CodeGen/Mips/mul.ll

-; RUN: llc  -march=mipsel -mattr=mips16 -relocation-model=pic -O3 < %s | FileCheck %s -check-prefix=16
+; RUN: llc  -march=mipsel -mattr=mips16 -relocation-model=pic -O3 -verify-loop-info < %s | FileCheck %s -check-prefix=16
 
 @iiii = global i32 5, align 4
 @jjjj = global i32 -6, align 4
 @kkkk = common global i32 0, align 4
 
 define void @test() nounwind {
 entry:
   %0 = load i32, i32* @iiii, align 4
   %1 = load i32, i32* @jjjj, align 4
   %mul = mul nsw i32 %1, %0
 ; 16: mult  ${{[0-9]+}}, ${{[0-9]+}}
 ; 16:   mflo  ${{[0-9]+}}
 
   store i32 %mul, i32* @kkkk, align 4
   ret void
 }