[AssumptionCache] Avoid dangling llvm.assume calls in the cache

[jdoerfert]

Summary

PR49043 exposed a problem when it comes to RAUW llvm.assumes. While
D96106 would fix it for GVNSink, it seems a more general concern. To
avoid future problems this patch moves away from the vector of weak
reference model used in the assumption cache. Instead, we track the
llvm.assume calls with a callback handle which will remove itself from
the cache if the call is deleted.

Fixes PR49043.

[jdoerfert]

@nikic, @lebedev.ri Once the tests are back, could either of you start a run of this to track compile time?

I realized I could simply remove the problematic assertion and we allow duplication in the AssumeHandles vector, though that doesn't sound too great either.
I hope this might actually be the better solution in the long run, assuming (pun intended) the compile time is not impacted negatively.

[nikic]

Compile-time is in the noise: https://llvm-compile-time-tracker.com/compare.php?from=6e1afd858757256afdb619665befb790c76418bb&to=9f7b74f200bdee05bda1fbd9447ffd6fbd7c6262&stat=instructions I don't think CTMark generates many assumes though. In any case, I don't see anything here that should have a negative compile-time effect.

The patch looks fine to me, but I think I still haven't really understood at which point the problem is introduced in GVNSink. Could you point me to where the duplicate would get inserted?

llvm/include/llvm/Analysis/AssumptionCache.h

51

Missing final.

289

Is it not sufficient to pass DenseMapInfo<Value *> as the second parameter to DenseSet?

[jdoerfert]

Address comments

[jdoerfert]

In D96168#2546741, @nikic wrote:

Compile-time is in the noise: https://llvm-compile-time-tracker.com/compare.php?from=6e1afd858757256afdb619665befb790c76418bb&to=9f7b74f200bdee05bda1fbd9447ffd6fbd7c6262&stat=instructions I don't think CTMark generates many assumes though. In any case, I don't see anything here that should have a negative compile-time effect.

The patch looks fine to me, but I think I still haven't really understood at which point the problem is introduced in GVNSink. Could you point me to where the duplicate would get inserted?

here: https://reviews.llvm.org/D96106#2546918

This also avoids ever having dangling references in the cache, which is kinda nice I guess.

[nikic]

LGTM

[Meinersbur]

llvm/include/llvm/Analysis/AssumptionCache.h

81

Changing this list to a DenseSet introduces indeterminism in Polly's test case ScopInfo/user_provided_assumptions.ll and even in basic.ll that is changed in this patch. ScalarEvolution is known to give different result depending on the order in which elements are processed. PredicateInfo might emit different IR depending on the order as well.

I think we should play it save and changed it back to a SmallVector. Unfortunately, a SetVector instead would be of no use since the removing an element still searches the element in the vector.

llvm/lib/Analysis/AssumptionCache.cpp

171

Call base method CallbackVH::deleted() here?

[jdoerfert]

llvm/include/llvm/Analysis/AssumptionCache.h

81

I'm not sure I follow. If the user would benefit from more assumptions that are now "later" in the traversal, they should scan on. basic.ll is a print method which can be non-determistic, IMHO. Long story short, I'd say SCEV or Polly should find the best information among all assumptions.

[Meinersbur]

llvm/include/llvm/Analysis/AssumptionCache.h

81

In the case of Polly, the added assumption are simplified using previous assumptions. This gives indeterministic results such as

remark: <unknown>:0:0: Use user assumption: [Debug, M] -> {  : Debug = 0 and 0 < M <= 100 }
remark: <unknown>:0:0: Use user assumption: [Debug, M, N] -> {  : Debug = 0 and 0 < M <= 100 and N >= -2147483648 - M }
remark: <unknown>:0:0: Use user assumption: [Debug, M, N] -> {  : Debug = 0 and 0 < M <= 100 and N > 0 }
remark: <unknown>:0:0: Use user assumption: [Debug, M, N] -> {  : Debug = 0 and 0 < M <= 100 and 0 < N <= 2147483647 - M }

remark: <unknown>:0:0: Use user assumption: [N, M] -> {  : M >= -2147483648 - N }
remark: <unknown>:0:0: Use user assumption: [N, M] -> {  : N > 0 and M >= -2147483648 - N }
remark: <unknown>:0:0: Use user assumption: [N, M] -> {  : N > 0 and -2147483648 - N <= M <= 2147483647 - N }
remark: <unknown>:0:0: Use user assumption: [N, M, Debug] -> {  : Debug = 0 and N > 0 and 0 < M <= 2147483647 - N and M <= 100 }

remark: <unknown>:0:0: Use user assumption: [M, N] -> {  : N <= 2147483647 - M }
remark: <unknown>:0:0: Use user assumption: [M, N] -> {  : -2147483648 - M <= N <= 2147483647 - M }
remark: <unknown>:0:0: Use user assumption: [M, N, Debug] -> {  : Debug = 0 and 0 < M <= 100 and -2147483648 - M <= N <= 2147483647 - M }
remark: <unknown>:0:0: Use user assumption: [M, N, Debug] -> {  : Debug = 0 and 0 < M <= 100 and 0 < N <= 2147483647 - M }

i.e. it's not just the order in which they are printed.

Even if that can be fixed in Polly, as already mentioned the result ScalarEvolution returns depends on cached SCEVs (e.g. to resolve recursion), i.e. its result depends on previous queries, as much we dislike that. See for instance D74810.

[jdoerfert]

llvm/include/llvm/Analysis/AssumptionCache.h

81

I think I miss the point about ScalarEvolution here, is it impacted by the order of assumptions?

For polly, just to check, the set's are equivalent, right?

[Meinersbur]

llvm/include/llvm/Analysis/AssumptionCache.h

81

I think I miss the point about ScalarEvolution here, is it impacted by the order of assumptions?

ScalarEvolution::applyLoopGuards, while iterating over all assumptions calls getSCEV in order of the assumptions. A different call order, such as

getSCEV(A); 
getSCEV(B);

potentially gives a different result than

getSCEV(B); 
getSCEV(A);

and any query of getSCEV after that.

For polly, just to check, the set's are equivalent, right?

Nope, this is a FileCheck test for -Rpass remarks. No isl_set_is_equal within FileCheck.

[nikic]

llvm/include/llvm/Analysis/AssumptionCache.h

81

Yeah, we have quite a few places where order of assumptions can matter. This can also affect LVI because range intersections don't commute.

I think we should revert this change, as the original issue should already be addressed by the WeakTrackingVH -> WeakVH change.

[jdoerfert]

llvm/include/llvm/Analysis/AssumptionCache.h

81

Yeah, we have quite a few places where order of assumptions can matter. This can also affect LVI because range intersections don't commute.

We can fix the order but keep the self-removing property, llvm.assumes should not be deleted often.

That said, I think if assumption order matters it is also not great for users:

__builtin_assume(exp1);
__builtin_assume(exp2);

is blazing fast and

__builtin_assume(exp2);
__builtin_assume(exp1);

is slow. How do we explain that?

---

Nope, this is a FileCheck test for -Rpass remarks. No isl_set_is_equal within FileCheck.

That was not the question.

llvm/include/llvm/Analysis/AssumptionCache.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
 #define LLVM_ANALYSIS_ASSUMPTIONCACHE_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include <memory>
 
 namespace llvm {
 
 class CallInst;

 /// register any new \@llvm.assume calls that they create. Deletions of
 /// \@llvm.assume calls do not require special handling.
 class AssumptionCache {
 public:
   /// Value of ResultElem::Index indicating that the argument to the call of the
   /// llvm.assume.
   enum : unsigned { ExprResultIdx = std::numeric_limits<unsigned>::max() };
 
+  /// Callback handle to ensure we do not have dangling pointers to llvm.assume
+  /// calls in our cache.
+  class AssumeHandle : CallbackVH {
+    AssumptionCache *AC;
+
+    /// Make sure llvm.assume calls that are deleted are removed from the cache.
+    void deleted() override;
+
+  public:
+    AssumeHandle(Value *V, AssumptionCache *AC = nullptr)
+        : CallbackVH(V), AC(AC) {}
+
+    operator Value *() const { return getValPtr(); }
+    CallInst *getAssumeCI() const { return cast<CallInst>(getValPtr()); }
+  };
+
   struct ResultElem {
     WeakTrackingVH Assume;
 
     /// contains either ExprResultIdx or the index of the operand bundle
     /// containing the knowledge.
     unsigned Index;
     operator Value *() const { return Assume; }
   };
 
 private:
   /// The function for which this cache is handling assumptions.
   ///
   /// We track this to lazily populate our assumptions.
   Function &F;
 
-  /// Vector of weak value handles to calls of the \@llvm.assume
-  /// intrinsic.
-  SmallVector<ResultElem, 4> AssumeHandles;
+  /// Set of value handles for calls of the \@llvm.assume intrinsic.
+  DenseSet<AssumeHandle> AssumeHandles;
 
   class AffectedValueCallbackVH final : public CallbackVH {
     AssumptionCache *AC;
 
     void deleted() override;
     void allUsesReplacedWith(Value *) override;
 
   public:
public:
   void clear() {
     AssumeHandles.clear();
     AffectedValues.clear();
     Scanned = false;
   }
 
   /// Access the list of assumption handles currently tracked for this
   /// function.
-  ///
-  /// Note that these produce weak handles that may be null. The caller must
-  /// handle that case.
-  /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
-  /// when we can write that to filter out the null values. Then caller code
-  /// will become simpler.
-  MutableArrayRef<ResultElem> assumptions() {
+  DenseSet<AssumeHandle> &assumptions() {
     if (!Scanned)
       scanFunction();
     return AssumeHandles;
   }
 
   /// Access the list of assumptions which affect this value.
   MutableArrayRef<ResultElem> assumptionsFor(const Value *V) {
     if (!Scanned)

 template<> struct simplify_type<const AssumptionCache::ResultElem> {
   using SimpleType = /*const*/ Value *;
 
   static SimpleType getSimplifiedValue(const AssumptionCache::ResultElem &Val) {
     return Val;
   }
 };
 
+/// Provide DenseMapInfo for AssumeHandles, using the DenseMapInfo for Value *.
+template <>
+struct DenseMapInfo<AssumptionCache::AssumeHandle> : DenseMapInfo<Value *> {
+  using AssumeHandle = AssumptionCache::AssumeHandle;
+  static inline AssumeHandle getEmptyKey() {
+    return AssumeHandle(DenseMapInfo<Value *>::getEmptyKey());
+  }
+
+  static inline AssumeHandle getTombstoneKey() {
+    return AssumeHandle(DenseMapInfo<Value *>::getTombstoneKey());
+  }
+};
+
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_ASSUMPTIONCACHE_H

llvm/lib/Analysis/AssumptionCache.cpp

for (ResultElem &Elem : AVI->second) {
       if (HasNonnull && Found)
         break;
     }
     assert(Found && "already unregistered or incorrect cache state");
     if (!HasNonnull)
       AffectedValues.erase(AVI);
   }
 
-  erase_value(AssumeHandles, CI);
+  AssumeHandles.erase({CI, this});
+}
+
+void AssumptionCache::AssumeHandle::deleted() {
+  AC->AssumeHandles.erase(*this);
+  // 'this' now dangles!
 }
 
 void AssumptionCache::AffectedValueCallbackVH::deleted() {
   AC->AffectedValues.erase(getValPtr());
   // 'this' now dangles!
 }
 
 void AssumptionCache::transferAffectedValuesInCache(Value *OV, Value *NV) {
void AssumptionCache::scanFunction() {
   assert(!Scanned && "Tried to scan the function twice!");
   assert(AssumeHandles.empty() && "Already have assumes when scanning!");
 
   // Go through all instructions in all blocks, add all calls to @llvm.assume
   // to this cache.
   for (BasicBlock &B : F)
     for (Instruction &II : B)
       if (match(&II, m_Intrinsic<Intrinsic::assume>()))
-        AssumeHandles.push_back({&II, ExprResultIdx});
+        AssumeHandles.insert({&II, this});
 
   // Mark the scan as complete.
   Scanned = true;
 
   // Update affected values.
-  for (auto &A : AssumeHandles)
-    updateAffectedValues(cast<CallInst>(A));
+  for (auto &AssumeVH : AssumeHandles)
+    updateAffectedValues(AssumeVH.getAssumeCI());
 }
 
 void AssumptionCache::registerAssumption(CallInst *CI) {
   assert(match(CI, m_Intrinsic<Intrinsic::assume>()) &&
          "Registered call does not call @llvm.assume");
 
   // If we haven't scanned the function yet, just drop this assumption. It will
   // be found when we scan later.
   if (!Scanned)
     return;
 
-  AssumeHandles.push_back({CI, ExprResultIdx});
+  AssumeHandles.insert({CI, this});
 
 #ifndef NDEBUG
   assert(CI->getParent() &&
          "Cannot register @llvm.assume call not in a basic block");
   assert(&F == CI->getParent()->getParent() &&
          "Cannot register @llvm.assume call not in this function");
 
-  // We expect the number of assumptions to be small, so in an asserts build
-  // check that we don't accumulate duplicates and that all assumptions point
-  // to the same function.
-  SmallPtrSet<Value *, 16> AssumptionSet;
-  for (auto &VH : AssumeHandles) {
-    if (!VH)
-      continue;
-
-    assert(&F == cast<Instruction>(VH)->getParent()->getParent() &&
+  for (auto &AssumeVH : AssumeHandles) {
+    assert(&F == AssumeVH.getAssumeCI()->getCaller() &&
            "Cached assumption not inside this function!");
-    assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
+    assert(match(AssumeVH.getAssumeCI(), m_Intrinsic<Intrinsic::assume>()) &&
            "Cached something other than a call to @llvm.assume!");
-    assert(AssumptionSet.insert(VH).second &&
-           "Cache contains multiple copies of a call!");
   }
 #endif
 
   updateAffectedValues(CI);
 }
 
 AnalysisKey AssumptionAnalysis::Key;
 
 PreservedAnalyses AssumptionPrinterPass::run(Function &F,
                                              FunctionAnalysisManager &AM) {
   AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
 
   OS << "Cached assumptions for function: " << F.getName() << "\n";
-  for (auto &VH : AC.assumptions())
-    if (VH)
-      OS << "  " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";
+  for (auto &AssumeVH : AC.assumptions())
+    OS << "  " << *AssumeVH.getAssumeCI()->getArgOperand(0) << "\n";
 
   return PreservedAnalyses::all();
 }
 
 void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
   auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
   if (I != ACT->AssumptionCaches.end())
     ACT->AssumptionCaches.erase(I);
void AssumptionCacheTracker::verifyAnalysis() const {
   // 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 (auto &AssumeVH : I.second->assumptions())
+      AssumptionSet.insert(AssumeVH.getAssumeCI());
 
     for (const BasicBlock &B : cast<Function>(*I.first))
       for (const Instruction &II : B)
         if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
             !AssumptionSet.count(cast<CallInst>(&II)))
           report_fatal_error("Assumption in scanned function not in cache");
   }
 }

llvm/lib/Analysis/CodeMetrics.cpp

 // Find all ephemeral values.
 void CodeMetrics::collectEphemeralValues(
     const Loop *L, AssumptionCache *AC,
     SmallPtrSetImpl<const Value *> &EphValues) {
   SmallPtrSet<const Value *, 32> Visited;
   SmallVector<const Value *, 16> Worklist;
 
   for (auto &AssumeVH : AC->assumptions()) {
-    if (!AssumeVH)
-      continue;
-    Instruction *I = cast<Instruction>(AssumeVH);
+    Instruction *I = AssumeVH.getAssumeCI();
 
     // Filter out call sites outside of the loop so we don't do a function's
     // worth of work for each of its loops (and, in the common case, ephemeral
     // values in the loop are likely due to @llvm.assume calls in the loop).
     if (!L->contains(I->getParent()))
       continue;
 
     if (EphValues.insert(I).second)
       appendSpeculatableOperands(I, Visited, Worklist);
   }
 
   completeEphemeralValues(Visited, Worklist, EphValues);
 }
 
 void CodeMetrics::collectEphemeralValues(
     const Function *F, AssumptionCache *AC,
     SmallPtrSetImpl<const Value *> &EphValues) {
   SmallPtrSet<const Value *, 32> Visited;
   SmallVector<const Value *, 16> Worklist;
 
   for (auto &AssumeVH : AC->assumptions()) {
-    if (!AssumeVH)
-      continue;
-    Instruction *I = cast<Instruction>(AssumeVH);
+    Instruction *I = AssumeVH.getAssumeCI();
     assert(I->getParent()->getParent() == F &&
            "Found assumption for the wrong function!");
 
     if (EphValues.insert(I).second)
       appendSpeculatableOperands(I, Visited, Worklist);
   }
 
   completeEphemeralValues(Visited, Worklist, EphValues);

llvm/lib/Analysis/ScalarEvolution.cpp

if (AR->isAffine()) {
           // it's one of two issue possible causes for a change which was
           // reverted.  Be conservative for the moment.
           return getAddRecExpr(
                 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this,
                                                          Depth + 1),
                 getZeroExtendExpr(Step, Ty, Depth + 1), L,
                 AR->getNoWrapFlags());
         }
-        
         // For a negative step, we can extend the operands iff doing so only
-        // traverses values in the range zext([0,UINT_MAX]). 
+        // traverses values in the range zext([0,UINT_MAX]).
         if (isKnownNegative(Step)) {
           const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
                                       getSignedRangeMin(Step));
           if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) ||
               isKnownOnEveryIteration(ICmpInst::ICMP_UGT, AR, N)) {
             // Cache knowledge of AR NW, which is propagated to this
             // AddRec.  Negative step causes unsigned wrap, but it
             // still can't self-wrap.
const SCEV *LoopCounter =
       getAddRecExpr(getZero(Ty), getOne(Ty), L, NoWrapFlags);
     if (isImpliedCond(Pred, LHS, RHS, ICmpInst::ICMP_ULT, LoopCounter,
                       LatchBECount))
       return true;
   }
 
   // Check conditions due to any @llvm.assume intrinsics.
   for (auto &AssumeVH : AC.assumptions()) {
-    if (!AssumeVH)
-      continue;
-    auto *CI = cast<CallInst>(AssumeVH);
+    auto *CI = AssumeVH.getAssumeCI();
     if (!DT.dominates(CI, Latch->getTerminator()))
       continue;
 
     if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
       return true;
   }
 
   // If the loop is not reachable from the entry block, we risk running into an
for (std::pair<const BasicBlock *, const BasicBlock *> Pair(PredBB, BB);
 
     if (ProveViaCond(LoopEntryPredicate->getCondition(),
                      LoopEntryPredicate->getSuccessor(0) != Pair.second))
       return true;
   }
 
   // Check conditions due to any @llvm.assume intrinsics.
   for (auto &AssumeVH : AC.assumptions()) {
-    if (!AssumeVH)
-      continue;
-    auto *CI = cast<CallInst>(AssumeVH);
+    auto *CI = AssumeVH.getAssumeCI();
     if (!DT.dominates(CI, BB))
       continue;
 
     if (ProveViaCond(CI->getArgOperand(0), false))
       return true;
   }
 
   return false;
for (std::pair<const BasicBlock *, const BasicBlock *> Pair(
     if (LoopEntryPredicate->getSuccessor(1) == Pair.second)
       Predicate = CmpInst::getInversePredicate(Predicate);
     CollectCondition(Predicate, getSCEV(Cmp->getOperand(0)),
                      getSCEV(Cmp->getOperand(1)), RewriteMap);
   }
 
   // Also collect information from assumptions dominating the loop.
   for (auto &AssumeVH : AC.assumptions()) {
-    if (!AssumeVH)
-      continue;
-    auto *AssumeI = cast<CallInst>(AssumeVH);
+    auto *AssumeI = AssumeVH.getAssumeCI();
     auto *Cmp = dyn_cast<ICmpInst>(AssumeI->getOperand(0));
     if (!Cmp || !DT.dominates(AssumeI, L->getHeader()))
       continue;
     CollectCondition(Cmp->getPredicate(), getSCEV(Cmp->getOperand(0)),
                      getSCEV(Cmp->getOperand(1)), RewriteMap);
   }
 
   if (RewriteMap.empty())
     return Expr;
   SCEVLoopGuardRewriter Rewriter(*this, RewriteMap);
   return Rewriter.visit(Expr);
 }

llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp

 
 bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC,
                                            ScalarEvolution *SE_,
                                            DominatorTree *DT_) {
   SE = SE_;
   DT = DT_;
 
   bool Changed = false;
-  for (auto &AssumeVH : AC.assumptions())
-    if (AssumeVH) {
-      CallInst *Call = cast<CallInst>(AssumeVH);
-      for (unsigned Idx = 0; Idx < Call->getNumOperandBundles(); Idx++)
-        Changed |= processAssumption(Call, Idx);
-    }
+  for (auto &AssumeVH : AC.assumptions()) {
+    CallInst *Call = AssumeVH.getAssumeCI();
 
   return Changed;
 }
 
 PreservedAnalyses
 AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) {
 
   AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);

llvm/lib/Transforms/Utils/CodeExtractor.cpp

CodeExtractor::extractCodeRegion(const CodeExtractorAnalysisCache &CEAC) {
   LLVM_DEBUG(if (AC && verifyAssumptionCache(*oldFunction, *newFunction, AC))
                  report_fatal_error("Stale Asumption cache for old Function!"));
   return newFunction;
 }
 
 bool CodeExtractor::verifyAssumptionCache(const Function &OldFunc,
                                           const Function &NewFunc,
                                           AssumptionCache *AC) {
-  for (auto AssumeVH : AC->assumptions()) {
-    auto *I = dyn_cast_or_null<CallInst>(AssumeVH);
-    if (!I)
-      continue;
+  for (auto &AssumeVH : AC->assumptions()) {
+    auto *I = AssumeVH.getAssumeCI();
 
     // There shouldn't be any llvm.assume intrinsics in the new function.
     if (I->getFunction() != &OldFunc)
       return true;
 
     // There shouldn't be any stale affected values in the assumption cache
     // that were previously in the old function, but that have now been moved
     // to the new function.

llvm/lib/Transforms/Utils/PredicateInfo.cpp

if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
       // Can't insert conditional information if they all go to the same place.
       if (BI->getSuccessor(0) == BI->getSuccessor(1))
         continue;
       processBranch(BI, BranchBB, OpsToRename);
     } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
       processSwitch(SI, BranchBB, OpsToRename);
     }
   }
-  for (auto &Assume : AC.assumptions()) {
-    if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
-      if (DT.isReachableFromEntry(II->getParent()))
-        processAssume(II, II->getParent(), OpsToRename);
+  for (auto &AssumeVH : AC.assumptions()) {
+    CallInst *AssumeCI = AssumeVH.getAssumeCI();
+    if (DT.isReachableFromEntry(AssumeCI->getParent()))
+      processAssume(cast<IntrinsicInst>(AssumeCI), AssumeCI->getParent(),
+                    OpsToRename);
   }
   // Now rename all our operations.
   renameUses(OpsToRename);
 }
 
 // Create a ssa_copy declaration with custom mangling, because
 // Intrinsic::getDeclaration does not handle overloaded unnamed types properly:
 // all unnamed types get mangled to the same string. We use the pointer

llvm/test/Analysis/AssumptionCache/basic.ll

 ; RUN: opt < %s -disable-output -passes='print<assumptions>' 2>&1 | FileCheck %s
 
 target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
 
 declare void @llvm.assume(i1)
 
 define void @test1(i32 %a) {
 ; CHECK-LABEL: Cached assumptions for function: test1
-; CHECK-NEXT: icmp ne i32 %{{.*}}, 0
-; CHECK-NEXT: icmp slt i32 %{{.*}}, 0
-; CHECK-NEXT: icmp sgt i32 %{{.*}}, 0
+; CHECK-DAG: icmp ne i32 %{{.*}}, 0
+; CHECK-DAG: icmp slt i32 %{{.*}}, 0
+; CHECK-DAG: icmp sgt i32 %{{.*}}, 0
 
 entry:
   %cond1 = icmp ne i32 %a, 0
   call void @llvm.assume(i1 %cond1)
   %cond2 = icmp slt i32 %a, 0
   call void @llvm.assume(i1 %cond2)
   %cond3 = icmp sgt i32 %a, 0
   call void @llvm.assume(i1 %cond3)
 
   ret void
 }

llvm/test/Transforms/GVNSink/assumption.ll

+; RUN: opt < %s -S -passes="print<assumptions>,gvn-sink,loop-unroll" -unroll-count=3 | FileCheck %s
+;
+; This crashed because the cached assumption was replaced and the replacement
+; was then in the cache twice.
+;
+; PR49043
+
+@g = external global i32
+
+define void @main() {
+bb:
+  %i1.i = load volatile i32, i32* @g
+  %i32.i = icmp eq i32 %i1.i, 0
+  call void @llvm.assume(i1 %i32.i) #3
+  br label %bb4.i
+
+bb4.i:                                            ; preds = %bb4.i, %bb
+  %i.i = load volatile i32, i32* @g
+  %i3.i = icmp eq i32 %i.i, 0
+  call void @llvm.assume(i1 %i3.i) #3
+  br label %bb4.i
+
+func_1.exit:                                      ; No predecessors!
+  unreachable
+}
+
+declare void @llvm.assume(i1)
+
+; CHECK:  call void @llvm.assume(
+; CHECK:  call void @llvm.assume(
+; CHECK:  call void @llvm.assume(
+