Fixed LegacyPassManager inconsistency

[JesperAntonsson]

Summary

This fix locks the "last use"-point for a pass as soon as the pass is determined to be "not preserved".

This prevents "last use" and "preservation" information from becoming inconsistent, i.e. a "last use" point beyond where the pass is no longer preserved. Since "last use" information is used to remove dead passes, this will make sure passes does not stay around when they are not preserved.

The LegacyPassManager has an algorithm that transitively calculates "last use", so a pass' last use point could otherwise be dragged along beyond non-preservation points, and thus stay alive for too long. For instance, two call graphs would exist at the same time, leading to various problems, especially value handle asserts.

This solves the following four llvm bugs:
26865 - Inliner crashes in ValueHandleBase::ValueIsDeleted
27050 - ArgumentPromotion crashing with "An asserting value handle still pointed to this value!"
27112 - Inliner crashing with "An asserting value handle still pointed to this value!"
27697 - Passmanager assertion failure in PassAnalysisSupport

[mehdi_amini]

include/llvm/IR/LegacyPassManagers.h

194

Could these be better documented here?

252

Why a small vector? Also the comment says it is a "Map" apparently, while it is used as a set.
We have SmallPtrSet for instance.

lib/IR/LegacyPassManager.cpp

877

Why removing the early return?

test/Feature/legacypassmanager.ll

20

Do we have a better way of testing PM?
Do we have C++ unit tests?

[mehdi_amini]

lib/IR/LegacyPassManager.cpp

877

(Sorry I meant to remove this comment before validating, you can ignore)

[JesperAntonsson]

Thank you to Mehdi Amini for good review comments. I've updated the diff accordingly: Improved description, changed to a more appropriate container type for the book-keeping and also I added a C++ unittest.

[mehdi_amini]

I'll need more time to figure if it is the right fix or if it is a bandaid on top of the existing complexity.

lib/IR/LegacyPassManager.cpp

557

Merge with previous if?

[JesperAntonsson]

Whether this is the the right fix or band-aid is a fair question. :-) The problematic operation seems to be the transitive update of LastUser, and that's what I'm restraining in a minimal way to retain consistency with preservation info. OTOH, I don't understand/like the transitive update at all, but perhaps you understand its implications and what, if anything, would need to be done if it were to be removed entirely? There are other possibilities as well but I guess those would require more fundamental redesign.

I'm going for vacation at the end of this work day. I'll be back mid August and won't do anything more until then, but if you find this patch the right way to go, please feel free to push it at any time. (I don't have commit rights yet anyway, so I need help with that.)

Thanks, and have a great summer! /Jesper

[JesperAntonsson]

So, I'm back in business. :-) Mehdi, what say you?

[mehdi_amini]

Welcome back!

I won't have time to get back to this before next week, ping me on Monday!

[JesperAntonsson]

Monday, so I'm pinging. :-)

[mehdi_amini]

(It is still in my list, sorry for the delay)

[JesperAntonsson]

Good that this isn't forgotten. :-) It's Monday, so I'm sending another friendly ping.

[JesperAntonsson]

Pinging Mehdi Amini. :-)

[mehdi_amini]

I don't have time to page-in the LegacyPassManager infrastructure, but I know @chandlerc has been reviewing stuff in this area recently, maybe he can have a look.

[davide]

@chandlerc is probably the right person to take a look at this.

[JesperAntonsson]

This fix is still relevant and would be nice to land, but 3 out of 4 related TR have gone into hiding/are non-reproducible after AssertingValueHandle functionality was changed. 27697 is still reproducible.

[JesperAntonsson]

Seems irrelevant now e.g. due to the new pass manager.

include/llvm/IR/LegacyPassManagers.h

public:
   /// Schedule pass P for execution. Make sure that passes required by
   /// P are run before P is run. Update analysis info maintained by
   /// the manager. Remove dead passes. This is a recursive function.
   void schedulePass(Pass *P);
 
   /// Set pass P as the last user of the given analysis passes.
   void setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P);
 
+  /// Set pass P as locked for last use changes. This is used to make sure the
+  /// LastUser indication for a pass won't move past the point where it is not
+  /// preserved, since this would create inconsistencies.
+  void setLockedLastUse(const Pass *P);
+
+  /// Determine if the last use of pass P is unlocked.
+  bool isLastUseUnlocked(const Pass *P);
+
   /// Collect passes whose last user is P
   void collectLastUses(SmallVectorImpl<Pass *> &LastUses, Pass *P);
 
   /// Find the pass that implements Analysis AID. Search immutable
   /// passes and all pass managers. If desired pass is not found
   /// then return NULL.
   Pass *findAnalysisPass(AnalysisID AID);
 
protected:
   /// Collection of pass managers
   SmallVector<PMDataManager *, 8> PassManagers;
 
 private:
   /// Collection of pass managers that are not directly maintained
   /// by this pass manager
   SmallVector<PMDataManager *, 8> IndirectPassManagers;
 
-  // Map to keep track of last user of the analysis pass.
-  // LastUser->second is the last user of Lastuser->first.
+  /// Map to keep track of last user of the analysis pass.
+  /// LastUser->second is the last user of Lastuser->first.
   DenseMap<Pass *, Pass *> LastUser;
 
-  // Map to keep track of passes that are last used by a pass.
-  // This inverse map is initialized at PM->run() based on
-  // LastUser map.
+  /// Set to keep track of locks on last use. A pass has its last use information
+  /// locked when the pass is no longer preserved.
+  SmallPtrSet<const Pass *, 16> LockedLastUse;
+
+  /// Map to keep track of passes that are last used by a pass.
+  /// This inverse map is initialized at PM->run() based on
+  /// LastUser map.
   DenseMap<Pass *, SmallPtrSet<Pass *, 8> > InversedLastUser;
 
   /// Immutable passes are managed by top level manager.
   SmallVector<ImmutablePass *, 16> ImmutablePasses;
 
   /// Map from ID to immutable passes.
   SmallDenseMap<AnalysisID, ImmutablePass *, 8> ImmutablePassMap;
 
protected:
   // then PMT_Last active pass mangers.
   DenseMap<AnalysisID, Pass *> *InheritedAnalysis[PMT_Last];
 
   /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions
   /// or higher is specified.
   bool isPassDebuggingExecutionsOrMore() const;
 
 private:
+  void removeNotPreservedAnalysis(Pass *P,
+      const AnalysisUsage::VectorType &PreservedSet,
+      DenseMap<AnalysisID, Pass*> &AnalysisSet);
+
   void dumpAnalysisUsage(StringRef Msg, const Pass *P,
                          const AnalysisUsage::VectorType &Set) const;
 
   // Set of available Analysis. This information is used while scheduling
   // pass. If a pass requires an analysis which is not available then
   // the required analysis pass is scheduled to run before the pass itself is
   // scheduled to run.
   DenseMap<AnalysisID, Pass*> AvailableAnalysis;

lib/IR/LegacyPassManager.cpp

 
 /// Initialize top level manager. Create first pass manager.
 PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) {
   PMDM->setTopLevelManager(this);
   addPassManager(PMDM);
   activeStack.push(PMDM);
 }
 
+/// Set pass P as locked for last use changes.
+void PMTopLevelManager::setLockedLastUse(const Pass *P) {
+  LockedLastUse.insert(P);
+}
+
+/// Determine if the last use of pass P is unlocked.
+bool PMTopLevelManager::isLastUseUnlocked(const Pass *P) {
+  return LockedLastUse.count(P) == 0;
+}
+
 /// Set pass P as the last user of the given analysis passes.
 void
 PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) {
   unsigned PDepth = 0;
   if (P->getResolver())
     PDepth = P->getResolver()->getPMDataManager().getDepth();
 
   for (Pass *AP : AnalysisPasses) {
+    if (isLastUseUnlocked(AP))
       LastUser[AP] = P;
 
     if (P == AP)
       continue;
 
     // Update the last users of passes that are required transitive by AP.
     AnalysisUsage *AnUsage = findAnalysisUsage(AP);
     const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
     SmallVector<Pass *, 12> LastUses;
for (Pass *AP : AnalysisPasses) {
 
     // If AP is the last user of other passes then make P last user of
     // such passes.
     for (DenseMap<Pass *, Pass *>::iterator LUI = LastUser.begin(),
            LUE = LastUser.end(); LUI != LUE; ++LUI) {
       if (LUI->second == AP)
         // DenseMap iterator is not invalidated here because
         // this is just updating existing entries.
+        if (isLastUseUnlocked(LUI->first))
           LastUser[LUI->first] = P;
     }
   }
 }
 
 /// Collect passes whose last user is P
 void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses,
                                         Pass *P) {
   DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI =
for (AnalysisUsage::VectorType::const_iterator I = PreservedSet.begin(),
     AnalysisID AID = *I;
     if (Pass *AP = findAnalysisPass(AID, true)) {
       TimeRegion PassTimer(getPassTimer(AP));
       AP->verifyAnalysis();
     }
   }
 }
 
-/// Remove Analysis not preserved by Pass P
-void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
-  AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
-  if (AnUsage->getPreservesAll())
-    return;
-
-  const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
-  for (DenseMap<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
-         E = AvailableAnalysis.end(); I != E; ) {
+void PMDataManager::removeNotPreservedAnalysis(Pass *P,
+    const AnalysisUsage::VectorType &PreservedSet,
+    DenseMap<AnalysisID, Pass*> &AnalysisSet) {
+  for (DenseMap<AnalysisID, Pass*>::iterator I = AnalysisSet.begin(),
+         E = AnalysisSet.end(); I != E; ) {
     DenseMap<AnalysisID, Pass*>::iterator Info = I++;
     if (Info->second->getAsImmutablePass() == nullptr &&
         std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
         PreservedSet.end()) {
       // Remove this analysis
-      if (PassDebugging >= Details) {
-        Pass *S = Info->second;
+      if (PassDebugging >= Details) {
         dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
         dbgs() << S->getPassName() << "'\n";
       }
-      AvailableAnalysis.erase(Info);
+      TPM->setLockedLastUse(S);
+      AnalysisSet.erase(Info);
     }
   }
+}
+
+/// Remove Analysis not preserved by Pass P
+void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
+  AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
+  if (AnUsage->getPreservesAll())
+    return;
+
+  const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
+  removeNotPreservedAnalysis(P, PreservedSet, AvailableAnalysis);
 
   // Check inherited analysis also. If P is not preserving analysis
   // provided by parent manager then remove it here.
   for (unsigned Index = 0; Index < PMT_Last; ++Index) {
 
     if (!InheritedAnalysis[Index])
       continue;
 
-    for (DenseMap<AnalysisID, Pass*>::iterator
-           I = InheritedAnalysis[Index]->begin(),
-           E = InheritedAnalysis[Index]->end(); I != E; ) {
-      DenseMap<AnalysisID, Pass *>::iterator Info = I++;
-      if (Info->second->getAsImmutablePass() == nullptr &&
-          std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
-             PreservedSet.end()) {
-        // Remove this analysis
-        if (PassDebugging >= Details) {
-          Pass *S = Info->second;
-          dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
-          dbgs() << S->getPassName() << "'\n";
-        }
-        InheritedAnalysis[Index]->erase(Info);
-      }
-    }
+    removeNotPreservedAnalysis(P, PreservedSet, *InheritedAnalysis[Index]);
   }
 }
 
 /// Remove analysis passes that are not used any longer
 void PMDataManager::removeDeadPasses(Pass *P, StringRef Msg,
                                      enum PassDebuggingString DBG_STR) {
 
   SmallVector<Pass *, 12> DeadPasses;

test/Feature/legacypassmanager.ll

+; RUN: opt < %s -S -globals-aa -lcssa -argpromotion
+;
+; This is to verify a fix to bug 27050. The opt arguments expands to a series
+; that involves -basiccg twice. Before the fix, both those CallGraphs were
+; live at the same time during execution, which caused a value handle assert
+; during argpromotion since only the latest CG's asserting value handles were
+; removed when a function was deleted.
+
+%rec = type { i8 }
+
+define void @bar() {
+  call void @foo(%rec* undef)
+  ret void
+}
+
+define internal void @foo(%rec* %par0) {
+  ret void
+}
+

unittests/IR/LegacyPassManagerTest.cpp

 using namespace llvm;
 
 namespace llvm {
   void initializeModuleNDMPass(PassRegistry&);
   void initializeFPassPass(PassRegistry&);
   void initializeCGPassPass(PassRegistry&);
   void initializeLPassPass(PassRegistry&);
   void initializeBPassPass(PassRegistry&);
+  void initializeModuleDupePass(PassRegistry&);
+  void initializeModuleDupeUserPass(PassRegistry&);
+  void initializeModuleDupePreservationBreakerPass(PassRegistry&);
 
   namespace {
     // ND = no deps
     // NM = no modifications
     struct ModuleNDNM: public ModulePass {
     public:
       static char run;
       static char ID;
Module *makeLLVMModule(LLVMContext &Context) {
         BranchInst::Create(label_bb1, label_return, int1_f, label_bb1);
 
         // Block return (label_return)
         ReturnInst::Create(Context, label_return);
       }
       return mod;
     }
 
+     
+    // This verifies that the locking of LastUser propagation works.
+    struct ModuleDupe : public ModulePass {
+    public:
+      static char run;
+      static char ID;
+      static char allocated;
+      ModuleDupe() : ModulePass(ID) {
+        initializeModuleDupePass(*PassRegistry::getPassRegistry());
+      }
+      bool runOnModule(Module &M) override {
+        EXPECT_EQ(allocated, 0);  // This is the core expect!
+        run++;
+        allocated++;
+        return true;
+      }
+      void releaseMemory() override {
+        EXPECT_GT(run, 0);
+        EXPECT_GT(allocated, 0);
+        allocated--;
+      }
+      void getAnalysisUsage(AnalysisUsage &AU) const override {
+        AU.setPreservesAll();
+      }
+    };
+    char ModuleDupe::ID=0;
+    char ModuleDupe::run=0;
+    char ModuleDupe::allocated=0;
+
+    struct ModuleDupePreservationBreaker : public ModulePass {
+    public:
+      static char run;
+      static char ID;
+      ModuleDupePreservationBreaker() : ModulePass(ID) {
+        initializeModuleDupePreservationBreakerPass(*PassRegistry::getPassRegistry());
+      }
+      bool runOnModule(Module &M) override {
+        run++;
+        return true;
+      }
+      void getAnalysisUsage(AnalysisUsage &AU) const override {
+        AU.addRequired<ModuleDupe>();
+      }
+    };
+    char ModuleDupePreservationBreaker::ID=0;
+    char ModuleDupePreservationBreaker::run=0;
+
+    struct ModuleDupeUser: public ModulePass {
+    public:
+      static char run;
+      static char ID;
+      ModuleDupeUser() : ModulePass(ID) {
+        initializeModuleDupeUserPass(*PassRegistry::getPassRegistry());
+      }
+      bool runOnModule(Module &M) override {
+        run++;
+        return false;
+      }
+      void getAnalysisUsage(AnalysisUsage &AU) const override {
+        AU.addRequired<ModuleDupePreservationBreaker>();
+        AU.addRequired<ModuleDupe>();
+        AU.setPreservesAll();
+      }
+    };
+    char ModuleDupeUser::ID=0;
+    char ModuleDupeUser::run=0;
+
+    TEST(PassManager, CheckOldUnpreservedPassHasBeenRemovedBeforeNewIsRun) {
+      LLVMContext Context;
+      Module M("test-checkoldunpreservedpasshasbeenremoved", Context);
+      struct ModuleDupe *mDupe = new ModuleDupe();
+      struct ModuleDupePreservationBreaker *mDPB = new ModuleDupePreservationBreaker();
+      struct ModuleDupeUser *mDupeUser = new ModuleDupeUser();
+
+      mDupe->run = mDupeUser->run = mDPB->run = 0;
+
+      legacy::PassManager Passes;
+      Passes.add(mDupe);
+      Passes.add(mDPB);
+      Passes.add(mDupeUser);
+
+      // The mDPB is not preserving mDupe, so a new Dupe will be scheduled
+      // before DupeUser. This means we'll have this sequence of passes:
+      // Dupe
+      // DupePreservationBreaker
+      // Dupe
+      // DupeUser
+      //
+      // The DupeUser is requiring DupePreservationBreaker, which tries to trick
+      // the LegacyPassManager to transitively move the LastUse of the first
+      // Dupe to DupeUser. This would make it not remove the first Dupe before
+      // creating the second one, which would risk errors when we have two
+      // active Dupe instances simultaneously. Dupe has a check for allocation
+      // that verifies that this doesn't happen.
+
+      Passes.run(M);
+      EXPECT_EQ(2, mDupe->run);
+      EXPECT_EQ(1, mDPB->run);
+      EXPECT_EQ(1, mDupeUser->run);
+    }
+
   }
 }
 
 INITIALIZE_PASS(ModuleNDM, "mndm", "mndm", false, false)
 INITIALIZE_PASS_BEGIN(CGPass, "cgp","cgp", false, false)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_END(CGPass, "cgp","cgp", false, false)
 INITIALIZE_PASS(FPass, "fp","fp", false, false)
 INITIALIZE_PASS_BEGIN(LPass, "lp","lp", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(LPass, "lp","lp", false, false)
 INITIALIZE_PASS(BPass, "bp","bp", false, false)
+INITIALIZE_PASS(ModuleDupe, "mdupe", "mdupe", false, false)
+INITIALIZE_PASS(ModuleDupeUser, "mdupeuser", "mdupeuser", false, false)
+INITIALIZE_PASS(ModuleDupePreservationBreaker, "mdupepb", "mdupepb", false, false)