AssumptionCache: Disable the verifier by default, move it behind a hidden cl::opt and verify from releaseMemory().

[pcc]

Summary

This is a short term solution to the problem that many passes currently fail
to update the assumption cache. In the long term the verifier should not
be controllable with a flag. We should either fix all passes to correctly
update the assumption cache and enable the verifier unconditionally or
somehow arrange for the assumption list to be updated automatically by passes.

[pcc]

• Tweaks

[hfinkel]

LGTM

[sanjoy]

I guess I'm late to the party here, but checking my assumptions (no pun intended!) -- if AssumptionCacheTracker::verifyAnalysis fails after a pass Frobnicate then we're in a situation where opt -frobnicate -other-pass may have different behavior than opt -frobnicate | opt -other-pass (assuming other-pass uses AssumptionCache), right? If so, that's troubling.

[• dberlin]

While i agree it's troubling, it's interesting to note that we have that behavior elsewhere.

For example memdep caches, but not in a way that invalidates fully.

Thus, opt -gvn -gvn will give different answers than opt -gvn | opt -gvn
both are "correct" answers, just the former is more conservative than the latter.

[chandlerc]

In D30003#677918, @dberlin wrote:

While i agree it's troubling, it's interesting to note that we have that behavior elsewhere.

For example memdep caches, but not in a way that invalidates fully.

Thus, opt -gvn -gvn will give different answers than opt -gvn | opt -gvn
both are "correct" answers, just the former is more conservative than the latter.

Yeah, SCEV also has this property. So do several other analyses IIRC. =[

I'm not thrilled about making it worse, and we have a PR tracking this. My current best idea is to pull this up into a function analysis that can actually be invalidated. We can trivially make the new PM work this way today, and with some work could probably get it to work in the old PM as well.

(There remains the meta discussion of whether an analysis invalidation strategy to be conservatively correct is the most efficient approach or we should do something else, but even if we decide to do something else that seems significantly longer term to me.)

[• dberlin]

(There remains the meta discussion of whether an analysis invalidation strategy to be conservatively correct is the most efficient approach or we should do something else, but even if we decide to do something else that seems significantly longer term to me.)

FWIW: GCC computes aliasing exactly twice, and only does conservative updates in between.
It beats us in precision :)

SO i'm not worried on the memdepish front. AC i'd be more worried about.

[hfinkel]

In D30003#677903, @sanjoy wrote:

I guess I'm late to the party here, but checking my assumptions (no pun intended!) -- if AssumptionCacheTracker::verifyAnalysis fails after a pass Frobnicate then we're in a situation where opt -frobnicate -other-pass may have different behavior than opt -frobnicate | opt -other-pass (assuming other-pass uses AssumptionCache), right? If so, that's troubling.

Yea, the problem is: do you prefer different answers or an assertion failure. We discussed on IRC that Peter found a number of places where we already don't update the cache and, thus, only luck was preventing hitting asserts later. We should use the flag introduced in this pass to search out and fix these things, but in the mean time, we shouldn't trouble our users with assertion failures.

[sanjoy]

We should use the flag introduced in this pass to search out and fix these things, but in the mean time, we shouldn't trouble our users with assertion failures.

[realized after writing: I guess this is what @chandlerc said above?]
The other option would be to not make it an ImmutablePass and instead treat it like an analysis that gets preserved explicitly.

Btw, in WritingAnLLVMPass.rst ImmutablePass is described as "that do not have to be run, do not change state, and never need to be updated". That means either AC is not an ImmutablePass or the definition of an immutable pass needs to be relaxed.

llvm/trunk/include/llvm/Analysis/AssumptionCache.h

171

"The nature of the AssumptionCache is that it is not invalidated by any changes to the function body" no longer seems accurate.

Since forgetting to update the AC (after cloning) will fail "verification", perhaps we should either state that cloning will invalidate AC or avoid calling the thing we do later "verification"?

llvm/trunk/include/llvm/Analysis/AssumptionCache.h

public:
   explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 /// \brief An immutable pass that tracks lazily created \c AssumptionCache
 /// objects.
 ///
 /// This is essentially a workaround for the legacy pass manager's weaknesses
 /// which associates each assumption cache with Function and clears it if the
 /// function is deleted. The nature of the AssumptionCache is that it is not
 /// invalidated by any changes to the function body and so this is sufficient
 /// to be conservatively correct.
 class AssumptionCacheTracker : public ImmutablePass {
   /// A callback value handle applied to function objects, which we use to
   /// delete our cache of intrinsics for a function when it is deleted.
   class FunctionCallbackVH final : public CallbackVH {
     AssumptionCacheTracker *ACT;
public:
   ///
   /// If no assumptions are cached, this will scan the function. Otherwise, the
   /// existing cache will be returned.
   AssumptionCache &getAssumptionCache(Function &F);
 
   AssumptionCacheTracker();
   ~AssumptionCacheTracker() override;
 
-  void releaseMemory() override { AssumptionCaches.shrink_and_clear(); }
+  void releaseMemory() override {
+    verifyAnalysis();
+    AssumptionCaches.shrink_and_clear();
+  }
 
   void verifyAnalysis() const override;
   bool doFinalization(Module &) override {
     verifyAnalysis();
     return false;
   }
 
   static char ID; // Pass identification, replacement for typeid
 };
 
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/Analysis/AssumptionCache.cpp

 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
+static cl::opt<bool>
+    VerifyAssumptionCache("verify-assumption-cache", cl::Hidden,
+                          cl::desc("Enable verification of assumption cache"),
+                          cl::init(false));
+
 SmallVector<WeakVH, 1> &AssumptionCache::getOrInsertAffectedValues(Value *V) {
   // Try using find_as first to avoid creating extra value handles just for the
   // purpose of doing the lookup.
   auto AVI = AffectedValues.find_as(V);
   if (AVI != AffectedValues.end())
     return AVI->second;
 
   auto AVIP = AffectedValues.insert({
AssumptionCache &AssumptionCacheTracker::getAssumptionCache(Function &F) {
   // handle into our map, and return the newly populated cache.
   auto IP = AssumptionCaches.insert(std::make_pair(
       FunctionCallbackVH(&F, this), llvm::make_unique<AssumptionCache>(F)));
   assert(IP.second && "Scanning function already in the map?");
   return *IP.first->second;
 }
 
 void AssumptionCacheTracker::verifyAnalysis() const {
-#ifndef NDEBUG
+  // FIXME: In the long term the verifier should not be controllable with a
+  // flag. We should either fix all passes to correctly update the assumption
+  // cache and enable the verifier unconditionally or somehow arrange for the
+  // assumption list to be updated automatically by passes.
+  if (!VerifyAssumptionCache)
+    return;
+
   SmallPtrSet<const CallInst *, 4> AssumptionSet;
   for (const auto &I : AssumptionCaches) {
     for (auto &VH : I.second->assumptions())
       if (VH)
         AssumptionSet.insert(cast<CallInst>(VH));
 
     for (const BasicBlock &B : cast<Function>(*I.first))
       for (const Instruction &II : B)
-        if (match(&II, m_Intrinsic<Intrinsic::assume>()))
-          assert(AssumptionSet.count(cast<CallInst>(&II)) &&
-                 "Assumption in scanned function not in cache");
+        if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
+            !AssumptionSet.count(cast<CallInst>(&II)))
+          report_fatal_error("Assumption in scanned function not in cache");
   }
-#endif
 }
 
 AssumptionCacheTracker::AssumptionCacheTracker() : ImmutablePass(ID) {
   initializeAssumptionCacheTrackerPass(*PassRegistry::getPassRegistry());
 }
 
 AssumptionCacheTracker::~AssumptionCacheTracker() {}
 
 INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
                 "Assumption Cache Tracker", false, true)
 char AssumptionCacheTracker::ID = 0;

llvm/trunk/test/Transforms/SimplifyCFG/critedge-assume.ll

-; RUN: opt -o %t %s -instcombine -simplifycfg -thinlto-bc
+; RUN: opt -o %t %s -instcombine -simplifycfg -thinlto-bc -verify-assumption-cache
 ; RUN: llvm-dis -o - %t | FileCheck %s
 
 ; Test that the simplifycfg pass correctly updates the assumption cache
 ; when it clones the llvm.assume call as part of creating a critical
 ; edge. To do that, we set up a pass pipeline such that (1) an assumption
 ; cache is created for foo before simplifycfg updates it, and (2) foo's
 ; assumption cache is verified after simplifycfg has run. To satisfy 1, we
 ; run the instcombine pass first in our pipeline. To satisfy 2, we use the