[PH] Remove all use of AssertingVH from members of analysis results.

[chandlerc]

Summary

These are fundamentally incompatible with cache-invalidation of analysis
results. The invaliadtion happens after the AssertingVH has already
fired. There are more appropriate tools to use in these scenarios if and
when someone needs them to debug things. For example, a debug-build-only
WeakVH and an explicit assert that it hasn't gone null when it is *used*
so that it can still *exist* even when the value goes away.

This patch also removes all of the (numerous) doomed attempts to work
around this fundamental incompatibility. It is a pretty significant
simplification IMO.

The most interesting change is in the Inliner where we still do some
clearing because we don't want to rely on the coarse grained
invalidation strategy of the containing pass manager. However, I prefer
the approach that contains this logic to the cleanup phase of the
Inliner, and I think we could enhance the CGSCC analysis management
layer to make this even better in the future if desired.

The rest is straight cleanup.

I've also added a test for one of the harder cases to work around: when
a *module analysis* contains many AssertingVHes pointing at functions.

Note that this remains a bit controversial. See the llvm-dev discussion here:
http://lists.llvm.org/pipermail/llvm-dev/2017-January/109394.html

[hfinkel]

include/llvm/Analysis/ScalarEvolution.h

603 ↗

(On Diff #85330)

This seems relatively safe. If you remove a loop's exiting block, you'll need to call SE->forgetLoop(L).

lib/Analysis/LazyValueInfo.cpp

384 ↗

(On Diff #85330)

This seems less obvious; once you remove any blocks that LVI might have visited, if you add any other blocks, the analysis becomes instantly invalid in a subtle way for all other queries (i.e. subject to allocator-reuse-triggered non-determinism bugs), even for completely-unrelated parts of the function, even if you've proven the removed block dynamically unreachable, etc.

A callback handle here that removes the cached values if you remove the block would add value here in making this much less fragile. Even though flawed, I'm concerned that the asserting VH here is adding value by forcefully reminding us of this fragility. Fixing this "for real" seems straightforward (just like we do in SE in other cases).

[davide]

No objections to having this in in some form, but I agree with Hal about LVI.

lib/Analysis/LazyValueInfo.cpp

384 ↗

(On Diff #85330)

Agree.

lib/Transforms/IPO/Inliner.cpp

941 ↗

(On Diff #85330)

s/cclear/clear/

[sanjoy]

Hi Chandler,

I'm not sure this is a good idea.

If this is the *only* path forward then I'll be okay going ahead with
it, but I think AssertingVH (not unlike most other similar things)
is useful and provides a superset of functionality provided by
sanitizers.

For example, a debug-build-only
WeakVH and an explicit assert that it hasn't gone null when it is *used*
so that it can still *exist* even when the value goes away.

But we don't *have* such a thing today, and for that reason this
change is a strict decrease in debug-ability. If you wanted to add
something like that, and replace existing AssertingVH uses with it
then I may feel better about this; however AssertingVH is stronger
than what you suggest since AssertingVH catches cases where we've
keyed a hash table off AssertingVH s. To be on part with that
functionality, we'd also need to write data structures like DenseMap
that can be "poisoned" by a CallbackVH key.

[chandlerc]

Update to use a new PoisoningVH to implement this logic.

[chandlerc]

This time with code that compiles.

[sanjoy]

lgtm!

Thanks for indulging my paranoia!

llvm/trunk/include/llvm/Analysis/CallGraph.h

public:
   /// new one.
   ///
   /// Note that this method takes linear time, so it should be used sparingly.
   void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode);
 
 private:
   friend class CallGraph;
 
-  AssertingVH<Function> F;
+  Function *F;
 
   std::vector<CallRecord> CalledFunctions;
 
   /// \brief The number of times that this CallGraphNode occurs in the
   /// CalledFunctions array of this or other CallGraphNodes.
   unsigned NumReferences;
 
   CallGraphNode(const CallGraphNode &) = delete;

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

struct ExitLimit {
     bool hasFullInfo() const {
       return !isa<SCEVCouldNotCompute>(ExactNotTaken);
     }
   };
 
   /// Information about the number of times a particular loop exit may be
   /// reached before exiting the loop.
   struct ExitNotTakenInfo {
-    AssertingVH<BasicBlock> ExitingBlock;
+    PoisoningVH<BasicBlock> ExitingBlock;
     const SCEV *ExactNotTaken;
     std::unique_ptr<SCEVUnionPredicate> Predicate;
     bool hasAlwaysTruePredicate() const {
       return !Predicate || Predicate->isAlwaysTrue();
     }
 
-    explicit ExitNotTakenInfo(AssertingVH<BasicBlock> ExitingBlock,
+    explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock,
                               const SCEV *ExactNotTaken,
                               std::unique_ptr<SCEVUnionPredicate> Predicate)
         : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
           Predicate(std::move(Predicate)) {}
   };
 
   /// Information about the backedge-taken count of a loop. This currently
   /// includes an exact count and a maximum count.

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

class LazyValueInfoCache {
     /// This is all of the cached block information for exactly one Value*.
     /// The entries are sorted by the BasicBlock* of the
     /// entries, allowing us to do a lookup with a binary search.
     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
     /// memory overhead.
     struct ValueCacheEntryTy {
       ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
       LVIValueHandle Handle;
-      SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
+      SmallDenseMap<PoisoningVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
     };
 
     /// This is all of the cached information for all values,
     /// mapped from Value* to key information.
     DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
 
     /// This tracks, on a per-block basis, the set of values that are
     /// over-defined at the end of that block.
-    typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
+    typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
         OverDefinedCacheTy;
     OverDefinedCacheTy OverDefinedCache;
 
     /// Keep track of all blocks that we have ever seen, so we
     /// don't spend time removing unused blocks from our caches.
-    DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
+    DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
 
   public:
     void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
       SeenBlocks.insert(BB);
 
       // Insert over-defined values into their own cache to reduce memory
       // overhead.
       if (Result.isOverdefined())

 }
 
 void LazyValueInfoCache::eraseValue(Value *V) {
   SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
   for (auto &I : OverDefinedCache) {
     SmallPtrSetImpl<Value *> &ValueSet = I.second;
     ValueSet.erase(V);
     if (ValueSet.empty())
-      ToErase.push_back(I.first);
+      ToErase.push_back(&*I.first);
   }
   for (auto &BB : ToErase)
-    OverDefinedCache.erase(BB);
+    OverDefinedCache.erase(&*BB);
 
   ValueCache.erase(V);
 }
 
 void LVIValueHandle::deleted() {
   // This erasure deallocates *this, so it MUST happen after we're done
   // using any and all members of *this.
   Parent->eraseValue(*this);
 }
 
 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
   // Shortcut if we have never seen this block.
-  DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
+  DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
   if (I == SeenBlocks.end())
     return;
   SeenBlocks.erase(I);
 
   auto ODI = OverDefinedCache.find(BB);
   if (ODI != OverDefinedCache.end())
     OverDefinedCache.erase(ODI);
 

llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp

bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
 
   return deduceFunctionAttributeInRPO(M, CG);
 }
 
 PreservedAnalyses
 ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) {
   auto &CG = AM.getResult<CallGraphAnalysis>(M);
 
-  bool Changed = deduceFunctionAttributeInRPO(M, CG);
-
-  // CallGraphAnalysis holds AssertingVH and must be invalidated eagerly so
-  // that other passes don't delete stuff from under it.
-  // FIXME: We need to invalidate this to avoid PR28400. Is there a better
-  // solution?
-  AM.invalidate<CallGraphAnalysis>(M);
-
-  if (!Changed)
+  if (!deduceFunctionAttributeInRPO(M, CG))
     return PreservedAnalyses::all();
+
   PreservedAnalyses PA;
   PA.preserve<CallGraphAnalysis>();
   return PA;
 }

llvm/trunk/lib/Transforms/IPO/GlobalDCE.cpp

if (!AliveGlobals.count(&GV)) {
       if (GV.hasInitializer()) {
         Constant *Init = GV.getInitializer();
         GV.setInitializer(nullptr);
         if (isSafeToDestroyConstant(Init))
           Init->destroyConstant();
       }
     }
 
-  // Because we may have cached analyses for functions we take extra care when
-  // deleting them if there is an active proxy. If there isn't, then we get to
-  // assume that everything in the function AM has been cleared already.
-  // FIXME: Note that all of this will happen automatically when this pass
-  // finishes. Unfortuantely there are analyses which hold asserting VHs to
-  // IR units. We could make those weak VHs that would assert if ever used
-  // without asserting eagerly and then all of this knowledge of the analysis
-  // manager could go away.
-  FunctionAnalysisManager *FAM = nullptr;
-  if (auto *FAMProxy =
-          MAM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M))
-    FAM = &FAMProxy->getManager();
-
   // The second pass drops the bodies of functions which are dead...
   std::vector<Function *> DeadFunctions;
   for (Function &F : M)
     if (!AliveGlobals.count(&F)) {
       DeadFunctions.push_back(&F);         // Keep track of dead globals
-      if (!F.isDeclaration()) {
-        if (FAM)
-          FAM->clear(F);
+      if (!F.isDeclaration())
         F.deleteBody();
-      }
-    }
 
   // The third pass drops targets of aliases which are dead...
   std::vector<GlobalAlias*> DeadAliases;
   for (GlobalAlias &GA : M.aliases())
     if (!AliveGlobals.count(&GA)) {
       DeadAliases.push_back(&GA);
       GA.setAliasee(nullptr);
     }

llvm/trunk/lib/Transforms/IPO/Inliner.cpp

while (!Calls.empty()) {
       // dead. In that case, we can drop the body of the function eagerly
       // which may reduce the number of callers of other functions to one,
       // changing inline cost thresholds.
       if (Callee.hasLocalLinkage()) {
         // To check this we also need to nuke any dead constant uses (perhaps
         // made dead by this operation on other functions).
         Callee.removeDeadConstantUsers();
         if (Callee.use_empty()) {
-          // Clear all analyses and the body and queue the function itself for
-          // deletion when we finish inlining and call graph updates.
+          // Clear the body and queue the function itself for deletion when we
+          // finish inlining and call graph updates.
           // Note that after this point, it is an error to do anything other
           // than use the callee's address or delete it.
-          FAM.clear(Callee);
           Callee.dropAllReferences();
           assert(find(DeadFunctions, &Callee) == DeadFunctions.end() &&
                  "Cannot put cause a function to become dead twice!");
           DeadFunctions.push_back(&Callee);
         }
       }
     }
 
PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
   // all of the trivially dead functions, updating the call graph and the CGSCC
   // pass manager in the process.
   //
   // Note that this walks a pointer set which has non-deterministic order but
   // that is OK as all we do is delete things and add pointers to unordered
   // sets.
   for (Function *DeadF : DeadFunctions) {
     // Get the necessary information out of the call graph and nuke the
-    // function there.
+    // function there. Also, cclear out any cached analyses.
     auto &DeadC = *CG.lookupSCC(*CG.lookup(*DeadF));
+    FunctionAnalysisManager &FAM =
+        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(DeadC, CG)
+            .getManager();
+    FAM.clear(*DeadF);
+    AM.clear(DeadC);
     auto &DeadRC = DeadC.getOuterRefSCC();
     CG.removeDeadFunction(*DeadF);
 
     // Mark the relevant parts of the call graph as invalid so we don't visit
     // them.
     UR.InvalidatedSCCs.insert(&DeadC);
     UR.InvalidatedRefSCCs.insert(&DeadRC);
 
     // And delete the actual function from the module.
     M.getFunctionList().erase(DeadF);
   }
   return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
 }

llvm/trunk/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp

 }
 
 PreservedAnalyses
 AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) {
 
   AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
   ScalarEvolution &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
-  bool Changed = runImpl(F, AC, &SE, &DT);
-
-  // FIXME: We need to invalidate this to avoid PR28400. Is there a better
-  // solution?
-  AM.invalidate<ScalarEvolutionAnalysis>(F);
-
-  if (!Changed)
+  if (!runImpl(F, AC, &SE, &DT))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<AAManager>();
   PA.preserve<ScalarEvolutionAnalysis>();
   PA.preserve<GlobalsAA>();
   return PA;
 }

llvm/trunk/lib/Transforms/Scalar/NaryReassociate.cpp

 PreservedAnalyses NaryReassociatePass::run(Function &F,
                                            FunctionAnalysisManager &AM) {
   auto *AC = &AM.getResult<AssumptionAnalysis>(F);
   auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
   auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
   auto *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
   auto *TTI = &AM.getResult<TargetIRAnalysis>(F);
 
-  bool Changed = runImpl(F, AC, DT, SE, TLI, TTI);
-
-  // FIXME: We need to invalidate this to avoid PR28400. Is there a better
-  // solution?
-  AM.invalidate<ScalarEvolutionAnalysis>(F);
-
-  if (!Changed)
+  if (!runImpl(F, AC, DT, SE, TLI, TTI))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<ScalarEvolutionAnalysis>();
   return PA;
 }
 

llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp

PreservedAnalyses LoopSimplifyPass::run(Function &F,
   ScalarEvolution *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
   AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F);
 
   // Note that we don't preserve LCSSA in the new PM, if you need it run LCSSA
   // after simplifying the loops.
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
     Changed |= simplifyLoop(*I, DT, LI, SE, AC, /*PreserveLCSSA*/ false);
 
-  // FIXME: We need to invalidate this to avoid PR28400. Is there a better
-  // solution?
-  AM.invalidate<ScalarEvolutionAnalysis>(F);
-
   if (!Changed)
     return PreservedAnalyses::all();
+
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<LoopAnalysis>();
   PA.preserve<BasicAA>();
   PA.preserve<GlobalsAA>();
   PA.preserve<SCEVAA>();
   PA.preserve<ScalarEvolutionAnalysis>();
   PA.preserve<DependenceAnalysis>();

llvm/trunk/test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running analysis: LoopAnalysis
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-O-NEXT: Starting Loop pass manager run.
 ; CHECK-O-NEXT: Finished Loop pass manager run.
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LoopStandardAnalysisResults{{.*}}>
-; CHECK-O-NEXT: Invalidating analysis: ScalarEvolutionAnalysis
-; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-O-NEXT: Starting Loop pass manager run.
 ; CHECK-O-NEXT: Finished Loop pass manager run.
 ; CHECK-Os-NEXT: Running pass: MergedLoadStoreMotionPass
 ; CHECK-Os-NEXT: Running pass: GVN
 ; CHECK-Oz-NEXT: Running pass: MergedLoadStoreMotionPass
 ; CHECK-Oz-NEXT: Running pass: GVN
 ; CHECK-O2-NEXT: Running pass: MergedLoadStoreMotionPass
 ; CHECK-O2-NEXT: Running pass: GVN

 ; CHECK-O-NEXT: Running analysis: PostDominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O-NEXT: Finished CGSCC pass manager run.
 ; CHECK-O-NEXT: Running pass: EliminateAvailableExternallyPass
 ; CHECK-O-NEXT: Running pass: ReversePostOrderFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: CallGraphAnalysis
-; CHECK-O-NEXT: Invalidating analysis: CallGraphAnalysis
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: Float2IntPass
 ; CHECK-O-NEXT: Running pass: LoopDistributePass
 ; CHECK-O-NEXT: Running pass: LoopVectorizePass
 ; CHECK-O-NEXT: Running analysis: BlockFrequencyAnalysis
 ; CHECK-O-NEXT: Running analysis: BranchProbabilityAnalysis
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Running pass: SLPVectorizerPass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Running pass: AlignmentFromAssumptionsPass
-; CHECK-O-NEXT: Invalidating analysis: ScalarEvolutionAnalysis
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: GlobalDCEPass
 ; CHECK-O-NEXT: Running pass: ConstantMergePass
 ; CHECK-O-NEXT: Finished llvm::Module pass manager run.
 ; CHECK-O-NEXT: Running pass: PrintModulePass
 ;
 ; Make sure we get the IR back out without changes when we print the module.
 ; CHECK-O-LABEL: define void @foo(i32 %n) local_unnamed_addr {

llvm/trunk/test/Other/new-pm-lto-defaults.ll

 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph{{.*}}>
 ; CHECK-O-NEXT: Running analysis: AAManager
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: ReversePostOrderFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: CallGraphAnalysis
-; CHECK-O-NEXT: Invalidating analysis: CallGraphAnalysis
 ; CHECK-O-NEXT: Running pass: GlobalSplitPass
 ; CHECK-O-NEXT: Running pass: WholeProgramDevirtPass
 ; CHECK-O2-NEXT: Running pass: GlobalOptPass
 ; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PromotePass>
 ; CHECK-O2-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-O2-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-O2-NEXT: Running pass: ConstantMergePass
 ; CHECK-O2-NEXT: Running pass: DeadArgumentEliminationPass

llvm/trunk/test/Transforms/GlobalDCE/crash-assertingvh.ll

 ; Make sure that if a pass like jump threading populates a function analysis
 ; like LVI with asserting handles into the body of a function, those don't begin
 ; to assert when global DCE deletes the body of the function.
 ;
 ; RUN: opt -disable-output < %s -passes='module(function(jump-threading),globaldce)'
+; RUN: opt -disable-output < %s -passes='module(rpo-functionattrs,globaldce)'
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare i32 @bar()
 
 define internal i32 @foo() {
 entry:

llvm/trunk/test/Transforms/Inline/clear-analyses.ll

-; Test that the inliner clears analyses which may hold references to function
-; bodies when it decides to delete them after inlining the last caller.
-; We check this by using correlated-propagation to populate LVI with basic
-; block references that would dangle if we failed to clear the inlined function
-; body.
+; Test that when a pass like correlated-propagation populates an analysis such
+; as LVI with references back into the IR of a function that the inliner will
+; delete, this doesn't crash or go awry despite the inliner clearing the analyses
+; separately from when it deletes the function.
 ;
 ; RUN: opt -debug-pass-manager -S < %s 2>&1 \
 ; RUN:     -passes='cgscc(inline,function(correlated-propagation))' \
 ; RUN:     | FileCheck %s
 ;
 ; CHECK-LABEL: Starting llvm::Module pass manager run.
 ; CHECK: Running pass: InlinerPass on (callee)
 ; CHECK: Running pass: CorrelatedValuePropagationPass on callee