[AssumptionCache] caches @llvm.experimental.guard's

[caojoshua]

Summary

As discussed in https://github.com/llvm/llvm-project/issues/59901

This change is not NFC. There is one SCEV and EarlyCSE test that have an
improved analysis/optimization case. Rest of the tests are not failing.

I've mostly only added cleanup to SCEV since that is where this issue
started. As a follow up, I believe there is more cleanup opportunity in
SCEV and other affected passes.

There could be cases where there are missed registerAssumption of
guards, but this case is not so bad because there will be no
miscompilation. AssumptionCacheTracker should take care of deleted
guards.

[caojoshua]

An additional though: I have a lot of asserts that checks is assume || is guard. I'd like to add a helper in IntrinsicInst, but there is already a isAssumeLikeIntrinsic(), which is completely unrelated to this change. Maybe we can add isCondGuard()?

[nikic]

In D142330#4072524, @caojoshua wrote:

An additional though: I have a lot of asserts that checks is assume || is guard. I'd like to add a helper in IntrinsicInst, but there is already a isAssumeLikeIntrinsic(), which is completely unrelated to this change. Maybe we can add isCondGuard()?

I would recommend adding an extra instruction type next to here: https://github.com/llvm/llvm-project/blob/ea6e8d4f5913e89a1a6951f017b6509ed32c6be9/llvm/include/llvm/IR/IntrinsicInst.h#L1518 Given that the term "assume-like" is already taken, this could be AssumeOrGuardInst.

This will allow you to retain the more specific type information where currently AssumeInst is used.

[caojoshua]

• added a CondGuardInst that consists of assumes and guards
• added to AC's basic.ll test

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

620

Drop these asserts, they are implied by cast<> (rather than dyn_cast<>).

llvm/lib/Transforms/Utils/CodeExtractor.cpp

1670

This needs to use CondGuardInst.

[mkazantsev]

This chance has caused us a huge compile time degradation. @caojoshua I wonder, are you using guards for some reason? And why have you chosen to use it instead of new representation based on https://llvm.org/docs/LangRef.html#llvm-experimental-widenable-condition-intrinsic?

I think that experimental.guard wasn't our best design decision, and we in Azul are trying to completely get rid of them (it's moving slowly with pain, but it's moving). The reason of this is the requirement to duplicate every single branch-based transform for guards intrinsic, which is practically impossible. Unless there are strong reasons to stick with them, I would strongly recommend to use branch-based form that doesn't have this problem.

[nikic]

In D142330#4131091, @mkazantsev wrote:

This chance has caused us a huge compile time degradation.

Oh, that's surprising. I would have expected this to be a compile-time improvement. Do you have any information on where the slowdown is coming from?

I have two guesses:

• We have a number of places manually handling guards, and these might now end up handling guards both explicitly and via AssumptionCache, doing duplicate work. This would be easy to fix by just deleting the guard code.
• This automatically supports guards everywhere assumes are supported, so maybe we now have a lot more places handling guards.

[caojoshua]

@caojoshua I wonder, are you using guards for some reason?

No, I don't have specific use cases for guards not using guards, I just saw inconsistencies between how we handle assumptions and guards, and I thought this would be a nice code cleanup. I did not anticipate an increase in compile time.

I think both of nikic's guesses are entirely reasonable. Having information on which passes has the most slowdowns would be very helpful.

If helpful, I would not mind reverting this change. We can revisit this idea. Or since we would like to move away from guards, we could forget about this change all together.

[mkazantsev]

I plan to investigate that in a span of next few days, but the regression is REALLY huge. @caojoshua I will do the revert and report back when I know what's going on.

As for the intrinsic, my strong preference would be to deprecate it and transit to branch form in near future, but we'll see how it goes.

[anna]

Also, this caused a miscompile when assumption cache recorded guards. Specifically, in LazyValueAnalysis, when it was used by correlated-value-propagation. Took a while to root-cause to this change, since it was a miscompile. I will add a testcase in LVI/CVP to catch this in the future.

Specifically, LVI makes a distinction between guards and assumes (in intersectAssumeOrGuardBlockValueConstantRange), which was not held by this patch.

[anna]

If this change goes forward, we need to investigate all places where assumes/AssumptionCache is used and see if what is being done for assumes holds for guards as well. In LVI, what was done for assumes did not hold for guards.
Also, in future, when anyone adds assumption cache (under the idea that it handles assumes), we can very easily fall into the problem of having a miscompile with guards. For that reason and given that we are working towards moving away from this implementation, I would suggest we abandon this change altogether.

For the details, here is the code where we miscompile in LVI with this change (It can be fixed by checking that we're indeed intersecting with an assume from the AC) :

void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
          Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
...
BasicBlock *BB = BBI->getParent();
    for (auto &AssumeVH : AC->assumptionsFor(Val)) {
      if (!AssumeVH)
        continue;
  
      // Only check assumes in the block of the context instruction. Other
      // assumes will have already been taken into account when the value was
      // propagated from predecessor blocks.
      auto *I = cast<CallInst>(AssumeVH);
      if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))
        continue;
  
      BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0))); <-- we were intersecting with a guard here (!) without checking where the guard belonged 
    }
  
    // If guards are not used in the module, don't spend time looking for them
    if (GuardDecl && !GuardDecl->use_empty() &&
        BBI->getIterator() != BB->begin()) {
      for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()),
                                       BB->rend())) {
        Value *Cond = nullptr;
        if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
          BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
      }
    }
  
..
}

Note that with guards we intersect LVI by reverse traversing from the context instruction upwards till start of basic block. The assumption intersection above it does not do that - it just takes all assumes in the block. isValidAssumeForContext allows assumes which are after the context instruction as long as we will reach that assume (this would be incorrect in the case of guards). With this patch, we were intersecting the constant range with a guard's argument which was after Val and incorrectly folding a compare in correlated-value-propagation.

[nikic]

Note that with guards we intersect LVI by reverse traversing from the context instruction upwards till start of basic block. The assumption intersection above it does not do that - it just takes all assumes in the block. isValidAssumeForContext allows assumes which are after the context instruction as long as we will reach that assume (this would be incorrect in the case of guards).

Hm, would you mind explaining in more detail why this is not legal for guards (maybe with an IR sample)? It's not completely clear to me what the distinction is.

But in any case, we could easily accommodate this by adjusting isValidAssumeForContext() -- it has access to the call, so it could skip that particular logic for guards.

[anna]

In D142330#4150854, @nikic wrote:

Note that with guards we intersect LVI by reverse traversing from the context instruction upwards till start of basic block. The assumption intersection above it does not do that - it just takes all assumes in the block. isValidAssumeForContext allows assumes which are after the context instruction as long as we will reach that assume (this would be incorrect in the case of guards).

Hm, would you mind explaining in more detail why this is not legal for guards (maybe with an IR sample)? It's not completely clear to me what the distinction is.

Sure, consider this IR:

%local_48_ = phi i32 [ %172, %bci_664 ], [ 4, %bci_381 ]
...

bb:
 %145 = shl nsw i32 %local_48_, 16, !dbg !96
  %val = add i32 %145, 393216, !dbg !96
  %146 = ashr exact i32 %val, 16, !dbg !96
  %147 = icmp ult i32 %val, 32768000, !dbg !96
  call void (i1, ...) @llvm.experimental.guard(i1 %147, i32 13)

If we had an assume instead of a guard there, we can use the argument of the assume to make the constant range more precise. This works only when we are guaranteed to transfer execution from %val until the assume (which is part of what isValidAssumeForContext checks).

However, with the guard, the icmp ult i32 %val, 32768000 condition is not guaranteed to be true because the guard can fail. By considering the guard's range for the val, we unfortunately used circular logic and folded away the guard based on it (the CR for %val was incorrectly calculated as constantrange<0, 32768000>).
This is why when we try to make the constant range more precise with guards, we do backward traversal from the val until start of BB to find relevant guards. This is correct because by relying on guards *before* val, we know that we can use the guard's condition because we can reach val only if the guard passes.

But in any case, we could easily accommodate this by adjusting isValidAssumeForContext() -- it has access to the call, so it could skip that particular logic for guards.

Yes, that would work and handle all cases where the API of Assumption Cache is used.

[caojoshua]

If this change goes forward, we need to investigate all places where assumes/AssumptionCache is used and see if what is being done for assumes holds for guards as well. In LVI, what was done for assumes did not hold for guards.
Also, in future, when anyone adds assumption cache (under the idea that it handles assumes), we can very easily fall into the problem of having a miscompile with guards. For that reason and given that we are working towards moving away from this implementation, I would suggest we abandon this
change altogether.

I agree with Anna here. Although it should be possible to make this change work with isValidAssumeForContext(), it will be a lot of work and testing a bunch of passes with little benefit. And we hope to move away from guards anyway.

[nikic]

@anna Thanks for the example, I understand it now. We can only use the backwards reasoning with assume because assume violation is undefined behavior, while for guards we just exit this control flow path.

@caojoshua I think this depends a lot on when we can expect support for guard intrinsics to be removed. The LangRef note that this mechanism is obsolete has been there for more than 3 years, and as far as I can tell, there hasn't been any (upstream) movement to remove guard intrinsics in that time. If removing these intrinsics is just a vague plan for the future (rather than something people are actively working on right now), then I think it still makes sense to reapply a fixed version of this patch.

It sounds like a big part of the motivation for removing them is that they require special handling everywhere -- but with this patch, this is not really the case anymore, because they get handled as a side-effect of existing assume handling.

[mkazantsev]

Regarding compile time: I made some manual checks and don't see any CT impact from this patch. Our automated triage might have been wrong, I don't trust this anymore. But the miscompile concern still holds.

[mkazantsev]

My advice would still be to migrate to widenable conditions and eventually throw away experimental.guards. It has always been a bad idea.

llvm/include/llvm/Analysis/AssumptionCache.h

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include <memory>
 
 namespace llvm {
 
-class AssumeInst;
+class CondGuardInst;
 class Function;
 class raw_ostream;
 class TargetTransformInfo;
 class Value;
 
 /// A cache of \@llvm.assume calls within a function.
 ///
 /// This cache provides fast lookup of assumptions within a function by caching
bool invalidate(Function &, const PreservedAnalyses &,
                   FunctionAnalysisManager::Invalidator &) {
     return false;
   }
 
   /// Add an \@llvm.assume intrinsic to this function's cache.
   ///
   /// The call passed in must be an instruction within this function and must
   /// not already be in the cache.
-  void registerAssumption(AssumeInst *CI);
+  void registerAssumption(CondGuardInst *CI);
 
   /// Remove an \@llvm.assume intrinsic from this function's cache if it has
   /// been added to the cache earlier.
-  void unregisterAssumption(AssumeInst *CI);
+  void unregisterAssumption(CondGuardInst *CI);
 
   /// Update the cache of values being affected by this assumption (i.e.
   /// the values about which this assumption provides information).
-  void updateAffectedValues(AssumeInst *CI);
+  void updateAffectedValues(CondGuardInst *CI);
 
   /// Clear the cache of \@llvm.assume intrinsics for a function.
   ///
   /// It will be re-scanned the next time it is requested.
   void clear() {
     AssumeHandles.clear();
     AffectedValues.clear();
     Scanned = false;

llvm/include/llvm/IR/IntrinsicInst.h

static bool classof(const IntrinsicInst *I) {
     return I->getIntrinsicID() == Intrinsic::experimental_gc_result;
   }
 
   static bool classof(const Value *V) {
     return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
   }
 };
 
+/// This represents intrinsics that guard a condition
+class CondGuardInst : public IntrinsicInst {
+public:
+  static bool classof(const IntrinsicInst *I) {
+    return I->getIntrinsicID() == Intrinsic::assume ||
+           I->getIntrinsicID() == Intrinsic::experimental_guard;
+  }
+  static bool classof(const Value *V) {
+    return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
+  }
+};
 
 /// This represents the llvm.assume intrinsic.
-class AssumeInst : public IntrinsicInst {
+class AssumeInst : public CondGuardInst {
 public:
   static bool classof(const IntrinsicInst *I) {
     return I->getIntrinsicID() == Intrinsic::assume;
   }
   static bool classof(const Value *V) {
     return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
   }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_IR_INTRINSICINST_H

llvm/lib/Analysis/AssumeBundleQueries.cpp

llvm::getKnowledgeForValue(const Value *V,
                            function_ref<bool(RetainedKnowledge, Instruction *,
                                              const CallBase::BundleOpInfo *)>
                                Filter) {
   NumAssumeQueries++;
   if (!DebugCounter::shouldExecute(AssumeQueryCounter))
     return RetainedKnowledge::none();
   if (AC) {
     for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) {
-      auto *II = cast_or_null<AssumeInst>(Elem.Assume);
+      auto *II = dyn_cast_or_null<AssumeInst>(Elem.Assume);
       if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
         continue;
       if (RetainedKnowledge RK = getKnowledgeFromBundle(
               *II, II->bundle_op_info_begin()[Elem.Index])) {
         if (V != RK.WasOn)
           continue;
         if (is_contained(AttrKinds, RK.AttrKind) &&
             Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {

llvm/lib/Analysis/AssumptionCache.cpp

 //===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// This file contains a pass that keeps track of @llvm.assume intrinsics in
-// the functions of a module.
+// This file contains a pass that keeps track of @llvm.assume and
+// @llvm.experimental.guard intrinsics in the functions of a module.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
if (TTI) {
     const Value *Ptr;
     unsigned AS;
     std::tie(Ptr, AS) = TTI->getPredicatedAddrSpace(Cond);
     if (Ptr)
       AddAffected(const_cast<Value *>(Ptr->stripInBoundsOffsets()));
   }
 }
 
-void AssumptionCache::updateAffectedValues(AssumeInst *CI) {
+void AssumptionCache::updateAffectedValues(CondGuardInst *CI) {
   SmallVector<AssumptionCache::ResultElem, 16> Affected;
   findAffectedValues(CI, TTI, Affected);
 
   for (auto &AV : Affected) {
     auto &AVV = getOrInsertAffectedValues(AV.Assume);
     if (llvm::none_of(AVV, [&](ResultElem &Elem) {
           return Elem.Assume == CI && Elem.Index == AV.Index;
         }))
       AVV.push_back({CI, AV.Index});
   }
 }
 
-void AssumptionCache::unregisterAssumption(AssumeInst *CI) {
+void AssumptionCache::unregisterAssumption(CondGuardInst *CI) {
   SmallVector<AssumptionCache::ResultElem, 16> Affected;
   findAffectedValues(CI, TTI, Affected);
 
   for (auto &AV : Affected) {
     auto AVI = AffectedValues.find_as(AV.Assume);
     if (AVI == AffectedValues.end())
       continue;
     bool Found = false;

 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 &I : B)
-      if (isa<AssumeInst>(&I))
+      if (isa<CondGuardInst>(&I))
         AssumeHandles.push_back({&I, ExprResultIdx});
 
   // Mark the scan as complete.
   Scanned = true;
 
   // Update affected values.
   for (auto &A : AssumeHandles)
-    updateAffectedValues(cast<AssumeInst>(A));
+    updateAffectedValues(cast<CondGuardInst>(A));
 }
 
-void AssumptionCache::registerAssumption(AssumeInst *CI) {
+void AssumptionCache::registerAssumption(CondGuardInst *CI) {
   // 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});
 
 #ifndef NDEBUG
   assert(CI->getParent() &&
-         "Cannot register @llvm.assume call not in a basic block");
+         "Cannot a register CondGuardInst not in a basic block");
   assert(&F == CI->getParent()->getParent() &&
-         "Cannot register @llvm.assume call not in this function");
+         "Cannot a register CondGuardInst 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() &&
            "Cached assumption not inside this function!");
-    assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
-           "Cached something other than a call to @llvm.assume!");
+    assert(isa<CondGuardInst>(VH) &&
+           "Cached something other than CondGuardInst!");
     assert(AssumptionSet.insert(VH).second &&
            "Cache contains multiple copies of a call!");
   }
 #endif
 
   updateAffectedValues(CI);
 }
 

llvm/lib/Analysis/ScalarEvolution.cpp

if (AR->isAffine()) {
 
       // Normally, in the cases we can prove no-overflow via a
       // backedge guarding condition, we can also compute a backedge
       // taken count for the loop.  The exceptions are assumptions and
       // guards present in the loop -- SCEV is not great at exploiting
       // these to compute max backedge taken counts, but can still use
       // these to prove lack of overflow.  Use this fact to avoid
       // doing extra work that may not pay off.
-      if (!isa<SCEVCouldNotCompute>(MaxBECount) || HasGuards ||
-          !AC.assumptions().empty()) {
+      if (!isa<SCEVCouldNotCompute>(MaxBECount) || !AC.assumptions().empty()) {
 
         auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
         setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), NewFlags);
         if (AR->hasNoUnsignedWrap()) {
           // Same as nuw case above - duplicated here to avoid a compile time
           // issue.  It's not clear that the order of checks does matter, but
           // it's one of two issue possible causes for a change which was
           // reverted.  Be conservative for the moment.
ScalarEvolution::proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR) {
   // Normally, in the cases we can prove no-overflow via a
   // backedge guarding condition, we can also compute a backedge
   // taken count for the loop.  The exceptions are assumptions and
   // guards present in the loop -- SCEV is not great at exploiting
   // these to compute max backedge taken counts, but can still use
   // these to prove lack of overflow.  Use this fact to avoid
   // doing extra work that may not pay off.
 
-  if (isa<SCEVCouldNotCompute>(MaxBECount) && !HasGuards &&
-      AC.assumptions().empty())
+  if (isa<SCEVCouldNotCompute>(MaxBECount) && AC.assumptions().empty())
     return Result;
 
   // If the backedge is guarded by a comparison with the pre-inc  value the
   // addrec is safe. Also, if the entry is guarded by a comparison with the
   // start value and the backedge is guarded by a comparison with the post-inc
   // value, the addrec is safe.
   ICmpInst::Predicate Pred;
   const SCEV *OverflowLimit =
ScalarEvolution::proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR) {
   // Normally, in the cases we can prove no-overflow via a
   // backedge guarding condition, we can also compute a backedge
   // taken count for the loop.  The exceptions are assumptions and
   // guards present in the loop -- SCEV is not great at exploiting
   // these to compute max backedge taken counts, but can still use
   // these to prove lack of overflow.  Use this fact to avoid
   // doing extra work that may not pay off.
 
-  if (isa<SCEVCouldNotCompute>(MaxBECount) && !HasGuards &&
-      AC.assumptions().empty())
+  if (isa<SCEVCouldNotCompute>(MaxBECount) && AC.assumptions().empty())
     return Result;
 
   // If the backedge is guarded by a comparison with the pre-inc  value the
   // addrec is safe. Also, if the entry is guarded by a comparison with the
   // start value and the backedge is guarded by a comparison with the post-inc
   // value, the addrec is safe.
   if (isKnownPositive(Step)) {
     const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
return isKnownNonNegative(RHS) &&
          isKnownPredicate(CmpInst::ICMP_SGE, LHS, getZero(LHS->getType())) &&
          isKnownPredicate(CmpInst::ICMP_SLT, LHS, RHS);
 }
 
 bool ScalarEvolution::isImpliedViaGuard(const BasicBlock *BB,
                                         ICmpInst::Predicate Pred,
                                         const SCEV *LHS, const SCEV *RHS) {
   // No need to even try if we know the module has no guards.
-  if (!HasGuards)
+  if (AC.assumptions().empty())
     return false;
 
   return any_of(*BB, [&](const Instruction &I) {
     using namespace llvm::PatternMatch;
 
     Value *Condition;
     return match(&I, m_Intrinsic<Intrinsic::experimental_guard>(
                          m_Value(Condition))) &&
for (auto &AssumeVH : AC.assumptions()) {
     auto *CI = cast<CallInst>(AssumeVH);
     if (!DT.dominates(CI, BB))
       continue;
 
     if (ProveViaCond(CI->getArgOperand(0), false))
       return true;
   }
 
-  // Check conditions due to any @llvm.experimental.guard intrinsics.
-  auto *GuardDecl = F.getParent()->getFunction(
-      Intrinsic::getName(Intrinsic::experimental_guard));
-  if (GuardDecl)
-    for (const auto *GU : GuardDecl->users())
-      if (const auto *Guard = dyn_cast<IntrinsicInst>(GU))
-        if (Guard->getFunction() == BB->getParent() && DT.dominates(Guard, BB))
-          if (ProveViaCond(Guard->getArgOperand(0), false))
-            return true;
   return false;
 }
 
 bool ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
                                                ICmpInst::Predicate Pred,
                                                const SCEV *LHS,
                                                const SCEV *RHS) {
   // Interpret a null as meaning no loop, where there is obviously no guard

 //                   ScalarEvolution Class Implementation
 //===----------------------------------------------------------------------===//
 
 ScalarEvolution::ScalarEvolution(Function &F, TargetLibraryInfo &TLI,
                                  AssumptionCache &AC, DominatorTree &DT,
                                  LoopInfo &LI)
     : F(F), TLI(TLI), AC(AC), DT(DT), LI(LI),
       CouldNotCompute(new SCEVCouldNotCompute()), ValuesAtScopes(64),
-      LoopDispositions(64), BlockDispositions(64) {
-  // To use guards for proving predicates, we need to scan every instruction in
-  // relevant basic blocks, and not just terminators.  Doing this is a waste of
-  // time if the IR does not actually contain any calls to
-  // @llvm.experimental.guard, so do a quick check and remember this beforehand.
-  //
-  // This pessimizes the case where a pass that preserves ScalarEvolution wants
-  // to _add_ guards to the module when there weren't any before, and wants
-  // ScalarEvolution to optimize based on those guards.  For now we prefer to be
-  // efficient in lieu of being smart in that rather obscure case.
-
-  auto *GuardDecl = F.getParent()->getFunction(
-      Intrinsic::getName(Intrinsic::experimental_guard));
-  HasGuards = GuardDecl && !GuardDecl->use_empty();
-}
+      LoopDispositions(64), BlockDispositions(64) {}
 
 ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
-    : F(Arg.F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
-      LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)),
+    : F(Arg.F), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT), LI(Arg.LI),
+      CouldNotCompute(std::move(Arg.CouldNotCompute)),
       ValueExprMap(std::move(Arg.ValueExprMap)),
       PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)),
       PendingPhiRanges(std::move(Arg.PendingPhiRanges)),
       PendingMerges(std::move(Arg.PendingMerges)),
       MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       PredicatedBackedgeTakenCounts(
           std::move(Arg.PredicatedBackedgeTakenCounts)),
for (auto &AssumeVH : AC.assumptions()) {
     if (!AssumeVH)
       continue;
     auto *AssumeI = cast<CallInst>(AssumeVH);
     if (!DT.dominates(AssumeI, Header))
       continue;
     Terms.emplace_back(AssumeI->getOperand(0), true);
   }
 
-  // Second, collect information from llvm.experimental.guards dominating the loop.
-  auto *GuardDecl = F.getParent()->getFunction(
-      Intrinsic::getName(Intrinsic::experimental_guard));
-  if (GuardDecl)
-    for (const auto *GU : GuardDecl->users())
-      if (const auto *Guard = dyn_cast<IntrinsicInst>(GU))
-        if (Guard->getFunction() == Header->getParent() && DT.dominates(Guard, Header))
-          Terms.emplace_back(Guard->getArgOperand(0), true);
-
-  // Third, collect conditions from dominating branches. Starting at the loop
+  // Second, collect conditions from dominating branches. Starting at the loop
   // predecessor, climb up the predecessor chain, as long as there are
   // predecessors that can be found that have unique successors leading to the
   // original header.
   // TODO: share this logic with isLoopEntryGuardedByCond.
   for (std::pair<const BasicBlock *, const BasicBlock *> Pair(
            L->getLoopPredecessor(), Header);
        Pair.first; Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
 

llvm/lib/Analysis/ValueTracking.cpp

if (Q.CxtI && V->getType()->isPointerTy()) {
 
     if (getKnowledgeValidInContext(V, AttrKinds, Q.CxtI, Q.DT, Q.AC))
       return true;
   }
 
   for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     if (!AssumeVH)
       continue;
-    CallInst *I = cast<CallInst>(AssumeVH);
+    CondGuardInst *I = cast<CondGuardInst>(AssumeVH);
     assert(I->getFunction() == Q.CxtI->getFunction() &&
            "Got assumption for the wrong function!");
 
     // Warning: This loop can end up being somewhat performance sensitive.
     // We're running this loop for once for each value queried resulting in a
     // runtime of ~O(#assumes * #values).
 
-    assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
-           "must be an assume intrinsic");
-
     Value *RHS;
     CmpInst::Predicate Pred;
     auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V)));
     if (!match(I->getArgOperand(0), m_c_ICmp(Pred, m_V, m_Value(RHS))))
       return false;
 
     if (cmpExcludesZero(Pred, RHS) && isValidAssumeForContext(I, Q.CxtI, Q.DT))
       return true;
static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known,
   }
 
   // Note that the patterns below need to be kept in sync with the code
   // in AssumptionCache::updateAffectedValues.
 
   for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     if (!AssumeVH)
       continue;
-    CallInst *I = cast<CallInst>(AssumeVH);
+    CondGuardInst *I = cast<CondGuardInst>(AssumeVH);
     assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() &&
            "Got assumption for the wrong function!");
 
     // Warning: This loop can end up being somewhat performance sensitive.
     // We're running this loop for once for each value queried resulting in a
     // runtime of ~O(#assumes * #values).
 
-    assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
-           "must be an assume intrinsic");
-
     Value *Arg = I->getArgOperand(0);
 
     if (Arg == V && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
       assert(BitWidth == 1 && "assume operand is not i1?");
       Known.setAllOnes();
       return;
     }
     if (match(Arg, m_Not(m_Specific(V))) &&
if (auto *I = dyn_cast<Instruction>(V))
     if (auto *Range = IIQ.getMetadata(I, LLVMContext::MD_range))
       CR = CR.intersectWith(getConstantRangeFromMetadata(*Range));
 
   if (CtxI && AC) {
     // Try to restrict the range based on information from assumptions.
     for (auto &AssumeVH : AC->assumptionsFor(V)) {
       if (!AssumeVH)
         continue;
-      CallInst *I = cast<CallInst>(AssumeVH);
+      IntrinsicInst *I = cast<IntrinsicInst>(AssumeVH);
       assert(I->getParent()->getParent() == CtxI->getParent()->getParent() &&
              "Got assumption for the wrong function!");
-      assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
-             "must be an assume intrinsic");
 
       if (!isValidAssumeForContext(I, CtxI, DT))
         continue;
       Value *Arg = I->getArgOperand(0);
       ICmpInst *Cmp = dyn_cast<ICmpInst>(Arg);
       // Currently we just use information from comparisons.
       if (!Cmp || Cmp->getOperand(0) != V)
         continue;

llvm/lib/Transforms/Utils/CodeExtractor.cpp

if (BFI) {
     for (BasicBlock *Pred : predecessors(header)) {
       if (Blocks.count(Pred))
         continue;
       EntryFreq +=
           BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, header);
     }
   }
 
-  // Remove @llvm.assume calls that will be moved to the new function from the
-  // old function's assumption cache.
+  // Remove CondGuardInsts that will be moved to the new function from the old
+  // function's assumption cache.
   for (BasicBlock *Block : Blocks) {
     for (Instruction &I : llvm::make_early_inc_range(*Block)) {
-      if (auto *AI = dyn_cast<AssumeInst>(&I)) {
+      if (auto *CI = dyn_cast<CondGuardInst>(&I)) {
         if (AC)
-          AC->unregisterAssumption(AI);
-        AI->eraseFromParent();
+          AC->unregisterAssumption(CI);
+        CI->eraseFromParent();
       }
     }
   }
 
   // If we have any return instructions in the region, split those blocks so
   // that the return is not in the region.
   splitReturnBlocks();
 
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);
+    auto *I = dyn_cast_or_null<CondGuardInst>(AssumeVH);
     if (!I)
       continue;
 
     // 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.
     for (auto AffectedValVH : AC->assumptionsFor(I->getOperand(0))) {
-      auto *AffectedCI = dyn_cast_or_null<CallInst>(AffectedValVH);
+      auto *AffectedCI = dyn_cast_or_null<CondGuardInst>(AffectedValVH);
       if (!AffectedCI)
         continue;
       if (AffectedCI->getFunction() != &OldFunc)
         return true;
       auto *AssumedInst = cast<Instruction>(AffectedCI->getOperand(0));
       if (AssumedInst->getFunction() != &OldFunc)
         return true;
     }
   }
   return false;
 }
 
 void CodeExtractor::excludeArgFromAggregate(Value *Arg) {
   ExcludeArgsFromAggregate.insert(Arg);
 }

llvm/lib/Transforms/Utils/InlineFunction.cpp

Function::iterator FirstNewBlock;
     // Propagate metadata on the callsite if necessary.
     PropagateCallSiteMetadata(CB, FirstNewBlock, Caller->end());
 
     // Register any cloned assumptions.
     if (IFI.GetAssumptionCache)
       for (BasicBlock &NewBlock :
            make_range(FirstNewBlock->getIterator(), Caller->end()))
         for (Instruction &I : NewBlock)
-          if (auto *II = dyn_cast<AssumeInst>(&I))
+          if (auto *II = dyn_cast<CondGuardInst>(&I))
             IFI.GetAssumptionCache(*Caller).registerAssumption(II);
   }
 
   // If there are any alloca instructions in the block that used to be the entry
   // block for the callee, move them to the entry block of the caller.  First
   // calculate which instruction they should be inserted before.  We insert the
   // instructions at the end of the current alloca list.
   {

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)
+declare void @llvm.experimental.guard(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-NEXT: icmp ult i32 %{{.*}}, 0
+; CHECK-NEXT: icmp ugt 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)
+  %cond4 = icmp ult i32 %a, 0
+  call void (i1, ...) @llvm.experimental.guard(i1 %cond4) [ "deopt"() ]
+  %cond5 = icmp ugt i32 %a, 0
+  call void (i1, ...) @llvm.experimental.guard(i1 %cond5) [ "deopt"() ]
 
   ret void
 }

llvm/test/Analysis/ScalarEvolution/guards.ll

entry:
   %len = load i32, ptr %len_buf
   %entry.cond = icmp sgt i32 %len, 0
   call void(i1, ...) @llvm.experimental.guard(i1 %entry.cond) [ "deopt"() ]
   br label %loop
 
 loop:
 ; CHECK: loop:
 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 true) [ "deopt"() ]
-; CHECK:  %iv.inc.cmp = icmp slt i32 %iv.inc, %len
+; CHECK:  %iv.inc.cmp = icmp ult i32 %iv.inc, %len
 ; CHECK:  call void (i1, ...) @llvm.experimental.guard(i1 %iv.inc.cmp) [ "deopt"() ]
 ; CHECK: leave:
   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
   %iv.inc = add i32 %iv, 1
 
   %iv.cmp = icmp slt i32 %iv, %len
   call void(i1, ...) @llvm.experimental.guard(i1 %iv.cmp) [ "deopt"() ]
 

 left:
   ; Does not dominate the backedge, so cannot be used in the inductive proof
   %iv.inc.cmp = icmp slt i32 %iv.inc, %len
   call void(i1, ...) @llvm.experimental.guard(i1 %iv.inc.cmp) [ "deopt"() ]
   br label %be
 
 be:
 ; CHECK: be:
-; CHECK-NEXT:  %iv.cmp = icmp slt i32 %iv, %len
+; CHECK-NEXT:  %iv.cmp = icmp ult i32 %iv, %len
 ; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 %iv.cmp) [ "deopt"() ]
 ; CHECK: leave:
 
   %iv.cmp = icmp slt i32 %iv, %len
   call void(i1, ...) @llvm.experimental.guard(i1 %iv.cmp) [ "deopt"() ]
 
   %becond = load volatile i1, ptr %cond_buf
   br i1 %becond, label %loop, label %leave
 
 leave:
   ret void
 }

llvm/test/Transforms/EarlyCSE/guards.ll

 }
 
 define i32 @test3.unhandled(i32 %val) {
 ; After a guard has executed the condition it was guarding is known to
 ; be true.
 ; CHECK-LABEL: @test3.unhandled(
 ; CHECK-NEXT:    [[COND0:%.*]] = icmp slt i32 [[VAL:%.*]], 40
 ; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[COND0]]) [ "deopt"() ]
-; CHECK-NEXT:    [[COND1:%.*]] = icmp sge i32 [[VAL]], 40
-; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 [[COND1]]) [ "deopt"() ]
+; CHECK-NEXT:    call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
 ; CHECK-NEXT:    ret i32 0
 ;
 
-; Demonstrates a case we do not yet handle (it is legal to fold %cond2
-; to false)
   %cond0 = icmp slt i32 %val, 40
   call void(i1,...) @llvm.experimental.guard(i1 %cond0) [ "deopt"() ]
   %cond1 = icmp sge i32 %val, 40
   call void(i1,...) @llvm.experimental.guard(i1 %cond1) [ "deopt"() ]
   ret i32 0
 }
 
 define i32 @test4(i32 %val, i1 %c) {