Make processing @llvm.assume more efficient - operand bundles

[hfinkel]

Summary

There is an efficiency problem with how we process @llvm.assume in ValueTracking (and other places). The AssumptionCache tracks all of the assumptions in a given function. In order to find assumptions relevant to computing known bits, etc. we search every assumption in the function. For ValueTracking that means that we do O(#assumes * #values) work in InstCombine and other passes (with a constant factor that can be quite large because we'll repeat this search at every level of recursion of the analysis).

Several of us discussed this situation at the last developers' meeting, and here's the first step toward implementing the discussed solution: Make the values that an assume might affect operands of the assume itself. To avoid exposing this detail to frontends and passes that need not worry about it, I've used the new operand-bundle feature to add these extra call "operands" in a way that does not affect the intrinsic's signature. I think this solution is relatively clean. InstCombine adds these extra operands based on what ValueTracking, LVI, etc. will need and then those passes need only search the users of the values under consideration. This should fix the computational complexity problem.

My goal is to use this scheme to remove the need for the AssumptionCache all together. The only user not removed by the current patch is ScalarEvolution. @sanjoy, do you have a good idea of how this might be done? I looked at the handing of the guard intrinsics in SE, and it looks like we should handle both the same way, although the handling of the guard intrinsics seems to involve a lot of basic-block scanning, and I'd hope there was a more-efficient way.

[sanjoy]

Hi Hal,

Thanks for doing this! I have not yet looked at the code in detail, but I have some high level comments, questions and answers.

One high level question: did you look at keeping this "affected" set as part of the AssumptionCache itself? That is, keep a map that maps ValueHandles to the corresponding assume instruction they affect?

Despite being an implementation detail we should add some basic documentation about this operand bundle to the langref.

I don't have a good solution for using this in SCEV. One not-great solution is to have a pre-pass in SCEV that does this:

for (AssumeInst AI : all_assumes_in_func) {
  for (AffectOp : AI) {
    AffectedMap[getSCEV(AffectOp)].push_back(AI);
  }
}

and then use the AffectedMap instead of using the "affected" operand bundle directly.

You could also try to scan a SCEV expression to fetch Value s out of SCEVUnknown nodes and use the use lists of those values. But they won't catch cases like the loop preheader containing assume(%a + 1 < %b) and then a isKnownPredicate(%a + 1 < %b) query since getSCEV("%a + 1") will look through the addition and create an add expr.

As for your question about guards: while I initially wanted to use AssumptionCache (and I did have an RFC on llvm-dev about this), I did not go ahead with that idea since it wasn't obvious to me that it would be faster (that is, it isn't obviously a good idea; and I'd have to measure both sides to make an informed judgement). This is because we tend to have lots of guards in every function, and looking at each one *could* get expensive.

However, I think we will be able to use this "affected" infrastructure more readily.

[Prazek]

Does it solve my problem with assume vtable loads being processed slowly? If so, do I understand it correctly that it just keep track of what variables are effected by assume?

lib/Analysis/LazyValueInfo.cpp

966

auto
rename it to II?

lib/Analysis/ValueTracking.cpp

531

DITTO

[hfinkel]

In D27259#617956, @sanjoy wrote:

Hi Hal,

Thanks for doing this! I have not yet looked at the code in detail, but I have some high level comments, questions and answers.

One high level question: did you look at keeping this "affected" set as part of the AssumptionCache itself? That is, keep a map that maps ValueHandles to the corresponding assume instruction they affect?

I thought about this, but I wanted to first see if we could get rid of the assumption cache entirely. I don't really like requiring the side contract which needs to be updated by every place that might clone instructions. If we can't eliminate it, then I agree that keeping this information in the cache is cleaner.

Despite being an implementation detail we should add some basic documentation about this operand bundle to the langref.

Sure.

I don't have a good solution for using this in SCEV. One not-great solution is to have a pre-pass in SCEV that does this:

for (AssumeInst AI : all_assumes_in_func) {
  for (AffectOp : AI) {
    AffectedMap[getSCEV(AffectOp)].push_back(AI);
  }
}

and then use the AffectedMap instead of using the "affected" operand bundle directly.

Hrmm. I don't really want to scan if possible - in part because it seems like it would make SCEV much less lazy than it is now (and in part because I want to get rid of the assumption cache, and if I do that, then I don't have an efficient way to find the assumptions). What if I hooked getSCEV so that, if the value in question was affected by an assumptions, then we add that to the AffectedMap?

The code that I'm currently trying to replace, as such, is this:

// Check conditions due to any @llvm.assume intrinsics.
for (auto &AssumeVH : AC.assumptions()) {
  if (!AssumeVH)
    continue;
  auto *CI = cast<CallInst>(AssumeVH);
  if (!DT.dominates(CI, Latch->getTerminator()))
    continue;

  if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
    return true;
}

And so the problem is that I need to be able to figure out, given LHS and RHS, if the assumption condition might make isImpliedCond(Pred, LHS, RHS, ...) true. getSCEV(affected_value) might not be exactly equal to wither LHS or RHS for this to be the case. Perhaps, however, if AffectedMap was essentially the transitive closure of the getSCEV(affected_value) -- meaning that the map contains those SCEVs but also all other SCEVs that use those as operands -- it might work?

You could also try to scan a SCEV expression to fetch Value s out of SCEVUnknown nodes and use the use lists of those values. But they won't catch cases like the loop preheader containing assume(%a + 1 < %b) and then a isKnownPredicate(%a + 1 < %b) query since getSCEV("%a + 1") will look through the addition and create an add expr.

Yea, this was exactly my concern with trying to use the values from SCEVUnknown.

As for your question about guards: while I initially wanted to use AssumptionCache (and I did have an RFC on llvm-dev about this), I did not go ahead with that idea since it wasn't obvious to me that it would be faster (that is, it isn't obviously a good idea; and I'd have to measure both sides to make an informed judgement). This is because we tend to have lots of guards in every function, and looking at each one *could* get expensive.

However, I think we will be able to use this "affected" infrastructure more readily.

Sounds good. Thanks!

[hfinkel]

In D27259#620931, @Prazek wrote:

Does it solve my problem with assume vtable loads being processed slowly? If so, do I understand it correctly that it just keep track of what variables are effected by assume?

Fixing that, and related symptoms, is certainly my motivation.

lib/Analysis/LazyValueInfo.cpp

966

Sure.

lib/Analysis/ValueTracking.cpp

531

Sure.

[hfinkel]

Responded to review comments and implemented the discussed solution for ScalarEvolution.

At this point, no passes will depend on the AssumptionCache, and after this is committed, I'd unceremoniously rip that out as a follow-up change.

[hfinkel]

Added updates to the LangRef.

[Prazek]

LGTM, Thanks!

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);
-
-    // 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);
-  }
+  for (auto &B : L->blocks())
+    for (auto &I : *B)
+      if (auto *II = dyn_cast<IntrinsicInst>(&I))
+        if (II->getIntrinsicID() == Intrinsic::assume &&
+            EphValues.insert(II).second)
+          appendSpeculatableOperands(II, 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);
-    assert(I->getParent()->getParent() == F &&
-           "Found assumption for the wrong function!");
-
-    if (EphValues.insert(I).second)
-      appendSpeculatableOperands(I, Visited, Worklist);
-  }
+  for (auto &B : *F)
+    for (auto &I : B)
+      if (auto *II = dyn_cast<IntrinsicInst>(&I))
+        if (II->getIntrinsicID() == Intrinsic::assume &&
+            EphValues.insert(II).second)
+          appendSpeculatableOperands(II, Visited, Worklist);
 
   completeEphemeralValues(Visited, Worklist, EphValues);
 }
 
 /// Fill in the current structure with information gleaned from the specified
 /// block.
 void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
                                     const TargetTransformInfo &TTI,

lib/Analysis/LazyValueInfo.cpp

 // If we can determine a constraint on the value given conditions assumed by
 // the program, intersect those constraints with BBLV
 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
         Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
   if (!BBI)
     return;
 
-  for (auto &AssumeVH : AC->assumptions()) {
-    if (!AssumeVH)
+  for (auto *U : Val->users()) {
+    const IntrinsicInst *I = dyn_cast<IntrinsicInst>(U);
+    if (!I)
+      continue;
+    if (I->getIntrinsicID() != Intrinsic::assume)
       continue;
-    auto *I = cast<CallInst>(AssumeVH);
     if (!isValidAssumeForContext(I, BBI, DT))
       continue;
 
     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
   }
 
   // If guards are not used in the module, don't spend time looking for them
   auto *GuardDecl = BBI->getModule()->getFunction(

lib/Analysis/ValueTracking.cpp

static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
                                        const Query &Q) {
   // Use of assumptions is context-sensitive. If we don't have a context, we
   // cannot use them!
   if (!Q.AC || !Q.CxtI)
     return;
 
   unsigned BitWidth = KnownZero.getBitWidth();
 
-  for (auto &AssumeVH : Q.AC->assumptions()) {
-    if (!AssumeVH)
+  for (auto *U : V->users()) {
+    const IntrinsicInst *I = dyn_cast<IntrinsicInst>(U);
+    if (!I)
+      continue;
+    if (I->getIntrinsicID() != Intrinsic::assume)
       continue;
-    CallInst *I = cast<CallInst>(AssumeVH);
-    assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() &&
-           "Got assumption for the wrong function!");
     if (Q.isExcluded(I))
       continue;
 
-    // Warning: This loop can end up being somewhat performance sensetive.
-    // 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?");
       KnownZero.clearAllBits();
       KnownOne.setAllBits();
       return;
     }
 
+    // Note that the patterns below need to be kept in sync with the code
+    // in InstCombiner::visitCallInst that adds relevant values to each
+    // assume's operand bundles.
+
     // The remaining tests are all recursive, so bail out if we hit the limit.
     if (Depth == MaxDepth)
       continue;
 
     Value *A, *B;
     auto m_V = m_CombineOr(m_Specific(V),
                            m_CombineOr(m_PtrToInt(m_Specific(V)),
                            m_BitCast(m_Specific(V))));

lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::assume: {
     }
     // If there is a dominating assume with the same condition as this one,
     // then this one is redundant, and should be removed.
     APInt KnownZero(1, 0), KnownOne(1, 0);
     computeKnownBits(IIOperand, KnownZero, KnownOne, 0, II);
     if (KnownOne.isAllOnesValue())
       return eraseInstFromFunction(*II);
 
+    // For assumptions, add to the associated operand bundle the values to which
+    // the assumption might apply.
+    // Note: This code must be kept in-sync with the code in
+    // computeKnownBitsFromAssume in ValueTracking.
+    SmallVector<Value *, 16> Affected;
+    auto AddAffected = [&Affected](Value *V) {
+      if (isa<Argument>(V)) {
+        Affected.push_back(V);
+      } else if (auto *I = dyn_cast<Instruction>(V)) {
+        Affected.push_back(I);
+
+        if (I->getOpcode() == Instruction::BitCast ||
+            I->getOpcode() == Instruction::PtrToInt) {
+          V = I->getOperand(0);
+          if (isa<Instruction>(V) || isa<Argument>(V))
+            Affected.push_back(V);
+        }
+      }
+    };
+
+    CmpInst::Predicate Pred;
+    if (match(IIOperand, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
+      AddAffected(A);
+      AddAffected(B);
+
+      if (Pred == ICmpInst::ICMP_EQ) {
+        // For equality comparisons, we handle the case of bit inversion.
+        auto AddAffectedFromEq = [&AddAffected](Value *V) {
+          Value *A;
+          if (match(V, m_Not(m_Value(A)))) {
+            AddAffected(A);
+            V = A;
+          }
+
+          Value *B;
+          ConstantInt *C;
+          if (match(V,
+                    m_CombineOr(m_And(m_Value(A), m_Value(B)),
+                      m_CombineOr(m_Or(m_Value(A), m_Value(B)),
+                                  m_Xor(m_Value(A), m_Value(B)))))) {
+            AddAffected(A);
+            AddAffected(B);
+          } else if (match(V,
+                           m_CombineOr(m_Shl(m_Value(A), m_ConstantInt(C)),
+                             m_CombineOr(m_LShr(m_Value(A), m_ConstantInt(C)),
+                                         m_AShr(m_Value(A),
+                                                m_ConstantInt(C)))))) {
+            AddAffected(A);
+          }
+        };
+
+        AddAffectedFromEq(A);
+        AddAffectedFromEq(B);
+      }
+    }
+
+    // If the list of affected values is the same as the existing list then
+    // there's nothing more to do here.
+    if (!Affected.empty())
+      if (auto OB = CI.getOperandBundle("affected"))
+        if (Affected.size() == OB.getValue().Inputs.size() &&
+            std::equal(Affected.begin(), Affected.end(),
+                       OB.getValue().Inputs.begin()))
+          Affected.clear();
+
+    if (!Affected.empty()) {
+      Builder->CreateCall(AssumeIntrinsic, IIOperand,
+                          OperandBundleDef("affected", Affected),
+                          II->getName());
+      return eraseInstFromFunction(*II);
+    }
+
     break;
   }
   case Intrinsic::experimental_gc_relocate: {
     // Translate facts known about a pointer before relocating into
     // facts about the relocate value, while being careful to
     // preserve relocation semantics.
     Value *DerivedPtr = cast<GCRelocateInst>(II)->getDerivedPtr();
 

lib/Transforms/Scalar/AlignmentFromAssumptions.cpp

bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC,
                                            DominatorTree *DT_) {
   SE = SE_;
   DT = DT_;
 
   NewDestAlignments.clear();
   NewSrcAlignments.clear();
 
   bool Changed = false;
-  for (auto &AssumeVH : AC.assumptions())
-    if (AssumeVH)
-      Changed |= processAssumption(cast<CallInst>(AssumeVH));
+
+  for (auto &B : F)
+    for (auto &I : B)
+      if (auto *II = dyn_cast<IntrinsicInst>(&I))
+        if (II->getIntrinsicID() == Intrinsic::assume)
+          Changed |= processAssumption(II);
 
   return Changed;
 }
 
 PreservedAnalyses
 AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) {
 
   AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);

test/Transforms/CorrelatedValuePropagation/conflict.ll

 }
 
 declare void @llvm.assume(i1)
 
 ; Test that we can handle conflicting assume vs edge facts
 define i8 @test2(i8 %a) {
 ; CHECK-LABEL: @test2
   %cmp1 = icmp eq i8 %a, 5
-  call void @llvm.assume(i1 %cmp1)
+  call void @llvm.assume(i1 %cmp1) [ "affected"(i8 %a) ]
   %cmp2 = icmp eq i8 %a, 3
 ; CHECK: br i1 false, label %dead, label %exit
   br i1 %cmp2, label %dead, label %exit
 dead:
   ret i8 %a
 exit:
   ret i8 0
 }
 
 define i8 @test3(i8 %a) {
 ; CHECK-LABEL: @test3
   %cmp1 = icmp eq i8 %a, 5
   br i1 %cmp1, label %dead, label %exit
 dead:
   %cmp2 = icmp eq i8 %a, 3
 ; CHECK: call void @llvm.assume(i1 false)
-  call void @llvm.assume(i1 %cmp2)
+  call void @llvm.assume(i1 %cmp2) [ "affected"(i8 %a) ]
   ret i8 %a
 exit:
   ret i8 0
 }

test/Transforms/InstCombine/assume-redundant.ll

 ; RUN: opt -domtree -instcombine -loops -S < %s | FileCheck %s
 ; Note: The -loops above can be anything that requires the domtree, and is
 ; necessary to work around a pass-manager bug.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 %struct.s = type { double* }
 
 ; Function Attrs: nounwind uwtable
 define void @_Z3fooR1s(%struct.s* nocapture readonly dereferenceable(8) %x) #0 {
 
 ; CHECK-LABEL: @_Z3fooR1s
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %maskcond) [ "affected"(i64 %maskedptr, i64 %ptrint, double* %{{.*}}) ]
 ; CHECK-NOT: call void @llvm.assume
 
 entry:
   %a = getelementptr inbounds %struct.s, %struct.s* %x, i64 0, i32 0
   %0 = load double*, double** %a, align 8
   %ptrint = ptrtoint double* %0 to i64
   %maskedptr = and i64 %ptrint, 31
   %maskcond = icmp eq i64 %maskedptr, 0

test/Transforms/InstCombine/assume.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind uwtable
 define i32 @foo1(i32* %a) #0 {
 entry:
   %0 = load i32, i32* %a, align 4
 
 ; Check that the alignment has been upgraded and that the assume has not
 ; been removed:
 ; CHECK-LABEL: @foo1
 ; CHECK-DAG: load i32, i32* %a, align 32
-; CHECK-DAG: call void @llvm.assume
+; CHECK-DAG: call void @llvm.assume(i1 %maskcond) [ "affected"(i64 %maskedptr, i64 %ptrint, i32* %a) ]
 ; CHECK: ret i32
 
   %ptrint = ptrtoint i32* %a to i64
   %maskedptr = and i64 %ptrint, 31
   %maskcond = icmp eq i64 %maskedptr, 0
   tail call void @llvm.assume(i1 %maskcond)
 
   ret i32 %0
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @foo2(i32* %a) #0 {
 entry:
 ; Same check as in @foo1, but make sure it works if the assume is first too.
 ; CHECK-LABEL: @foo2
 ; CHECK-DAG: load i32, i32* %a, align 32
-; CHECK-DAG: call void @llvm.assume
+; CHECK-DAG: call void @llvm.assume(i1 %maskcond) [ "affected"(i64 %maskedptr, i64 %ptrint, i32* %a) ]
 ; CHECK: ret i32
 
   %ptrint = ptrtoint i32* %a to i64
   %maskedptr = and i64 %ptrint, 31
   %maskcond = icmp eq i64 %maskedptr, 0
   tail call void @llvm.assume(i1 %maskcond)
 
   %0 = load i32, i32* %a, align 4
   ret i32 %0
 }
 
 ; Function Attrs: nounwind
 declare void @llvm.assume(i1) #1
 
 define i32 @simple(i32 %a) #1 {
 entry:
 
 ; CHECK-LABEL: @simple
 ; CHECK: call void @llvm.assume
 ; CHECK: ret i32 4
 
   %cmp = icmp eq i32 %a, 4
-  tail call void @llvm.assume(i1 %cmp)
+  tail call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
   ret i32 %a
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @can1(i1 %a, i1 %b, i1 %c) {
 entry:
   %and1 = and i1 %a, %b
   %and  = and i1 %and1, %c
; CHECK: ret i32
   ret i32 5
 }
 
 define i32 @bar1(i32 %a) #0 {
 entry:
   %and1 = and i32 %a, 3
 
 ; CHECK-LABEL: @bar1
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
 ; CHECK: ret i32 1
 
   %and = and i32 %a, 7
   %cmp = icmp eq i32 %and, 1
   tail call void @llvm.assume(i1 %cmp)
 
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @bar2(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @bar2
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
 ; CHECK: ret i32 1
 
   %and = and i32 %a, 7
   %cmp = icmp eq i32 %and, 1
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 3
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @bar3(i32 %a, i1 %x, i1 %y) #0 {
 entry:
   %and1 = and i32 %a, 3
 
 ; Don't be fooled by other assumes around.
 ; CHECK-LABEL: @bar3
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
 ; CHECK: ret i32 1
 
   tail call void @llvm.assume(i1 %x)
 
   %and = and i32 %a, 7
   %cmp = icmp eq i32 %and, 1
   tail call void @llvm.assume(i1 %cmp)
 
   tail call void @llvm.assume(i1 %y)
 
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @bar4(i32 %a, i32 %b) {
 entry:
   %and1 = and i32 %b, 3
 
 ; CHECK-LABEL: @bar4
-; CHECK: call void @llvm.assume
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
+; CHECK: call void @llvm.assume(i1 %cmp2) [ "affected"(i32 %a, i32 %b) ]
 ; CHECK: ret i32 1
 
   %and = and i32 %a, 7
   %cmp = icmp eq i32 %and, 1
   tail call void @llvm.assume(i1 %cmp)
 
   %cmp2 = icmp eq i32 %a, %b
   tail call void @llvm.assume(i1 %cmp2)
 
   ret i32 %and1
 }
 
 define i32 @icmp1(i32 %a) #0 {
 entry:
   %cmp = icmp sgt i32 %a, 5
   tail call void @llvm.assume(i1 %cmp)
   %conv = zext i1 %cmp to i32
   ret i32 %conv
 
 ; CHECK-LABEL: @icmp1
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 1
 
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @icmp2(i32 %a) #0 {
 entry:
   %cmp = icmp sgt i32 %a, 5
   tail call void @llvm.assume(i1 %cmp)
   %0 = zext i1 %cmp to i32
   %lnot.ext = xor i32 %0, 1
   ret i32 %lnot.ext
 
 ; CHECK-LABEL: @icmp2
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 0
 }
 
 declare void @escape(i32* %a)
 
 ; Do we canonicalize a nonnull assumption on a load into
 ; metadata form?
 define i1 @nonnull1(i32** %a) {
entry:
   %load = load i32, i32* %a
   %cmp = icmp ne i32 %load, 0
   tail call void @llvm.assume(i1 %cmp)
   %rval = icmp eq i32 %load, 0
   ret i1 %rval
 
 ; CHECK-LABEL: @nonnull2
 ; CHECK-NOT: !nonnull
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %load) ]
 }
 
 ; Make sure the above canonicalization does not trigger
 ; if the assume is control dependent on something else
 define i1 @nonnull3(i32** %a, i1 %control) {
 entry:
   %load = load i32*, i32** %a
   %cmp = icmp ne i32* %load, null
   br i1 %control, label %taken, label %not_taken
 taken:
   tail call void @llvm.assume(i1 %cmp)
   %rval = icmp eq i32* %load, null
   ret i1 %rval
 not_taken:
   ret i1 true
 
 ; CHECK-LABEL: @nonnull3
 ; CHECK-NOT: !nonnull
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32* %load) ]
 }
 
 ; Make sure the above canonicalization does not trigger
 ; if the path from the load to the assume is potentially 
 ; interrupted by an exception being thrown
 define i1 @nonnull4(i32** %a) {
 entry:
   %load = load i32*, i32** %a
   ;; This call may throw!
   tail call void @escape(i32* %load)
   %cmp = icmp ne i32* %load, null
   tail call void @llvm.assume(i1 %cmp)
   %rval = icmp eq i32* %load, null
   ret i1 %rval
 
 ; CHECK-LABEL: @nonnull4
 ; CHECK-NOT: !nonnull
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32* %load) ]
 }
 
 define i1 @nonnull5(i32** %a) {
 entry:
   %load = load i32*, i32** %a
   ;; This call cannot actually trap, and so should not disrupt the assume.
   %v = call i32* @llvm.noalias.p0i32(i32* %load, metadata !1)
   %cmp = icmp ne i32* %load, null

test/Transforms/InstCombine/assume2.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind
 declare void @llvm.assume(i1) #1
 
 ; Function Attrs: nounwind uwtable
 define i32 @test1(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test1
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %and, i32 %a) ]
 ; CHECK: ret i32 5
 
   %and = and i32 %a, 15
   %cmp = icmp eq i32 %and, 5
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 7
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test2(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test2
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a.not, i32 %a) ]
 ; CHECK: ret i32 2
 
   %and = and i32 %a, 15
   %nand = xor i32 %and, -1
   %cmp = icmp eq i32 %nand, 4294967285
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 7
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test3(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test3
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %v, i32 %a) ]
 ; CHECK: ret i32 5
 
   %v = or i32 %a, 4294967280
   %cmp = icmp eq i32 %v, 4294967285
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 7
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test4(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test4
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a.not, i32 %a) ]
 ; CHECK: ret i32 2
 
   %v = or i32 %a, 4294967280
   %nv = xor i32 %v, -1
   %cmp = icmp eq i32 %nv, 5
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 7
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test5(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test5
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 4
 
   %v = xor i32 %a, 1
   %cmp = icmp eq i32 %v, 5
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 7
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test6(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test6
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %v.mask, i32 %a) ]
 ; CHECK: ret i32 5
 
   %v = shl i32 %a, 2
   %cmp = icmp eq i32 %v, 20
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 63
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test7(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test7
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %v.mask, i32 %a) ]
 ; CHECK: ret i32 20
 
   %v = lshr i32 %a, 2
   %cmp = icmp eq i32 %v, 5
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 252
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test8(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test8
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %v.mask, i32 %a) ]
 ; CHECK: ret i32 20
 
   %v = lshr i32 %a, 2
   %cmp = icmp eq i32 %v, 5
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 252
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test9(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test9
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 0
 
   %cmp = icmp sgt i32 %a, 5
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 2147483648
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test10(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test10
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 -2147483648
 
   %cmp = icmp sle i32 %a, -2
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 2147483648
   ret i32 %and1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @test11(i32 %a) #0 {
 entry:
 ; CHECK-LABEL: @test11
-; CHECK: call void @llvm.assume
+; CHECK: call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
 ; CHECK: ret i32 0
 
   %cmp = icmp ule i32 %a, 256
   tail call void @llvm.assume(i1 %cmp)
 
   %and1 = and i32 %a, 3072
   ret i32 %and1
 }
 
 attributes #0 = { nounwind uwtable }
 attributes #1 = { nounwind }
 

test/Transforms/InstSimplify/add-mask.ll

 ; CHECK-NEXT:    [[B_AND:%.*]] = and i32 [[B]], 1
 ; CHECK-NEXT:    [[B_CND:%.*]] = icmp eq i32 [[B_AND]], 1
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[B_CND]])
 ; CHECK-NEXT:    ret i1 false
 ;
   %b = load i32, i32* @B
   %b.and = and i32 %b, 1
   %b.cnd = icmp eq i32 %b.and, 1
-  call void @llvm.assume(i1 %b.cnd)
+  call void @llvm.assume(i1 %b.cnd) [ "affected"(i32 %b.and, i32 %b) ]
 
   %rhs = add i32 %a, %b
   %and = and i32 %a, %rhs
   %res = icmp eq i32 %and, 1
   ret i1 %res
 }
 
 ; Negative test - even number

test/Transforms/JumpThreading/assume-edge-dom.ll

 ; RUN: opt -S -jump-threading < %s | FileCheck %s
 
 declare i8* @escape()
 declare void @llvm.assume(i1)
 
 define i1 @test1(i1 %cond) {
 entry:
     br i1 %cond, label %taken, label %not_taken
 
 ; CHECK-LABEL: @test1
 ; CHECK: br i1 %cond, label %no, label %yes
 ; CHECK: ret i1 true
 
 taken:
     %res1 = call i8* @escape()
     %a = icmp eq i8* %res1, null
-    tail call void @llvm.assume(i1 %a)
+    tail call void @llvm.assume(i1 %a) [ "affected"(i8* %res1) ]
     br label %done
 not_taken:
     %res2 = call i8* @escape()
     %b = icmp ne i8* %res2, null
-    tail call void @llvm.assume(i1 %b)
+    tail call void @llvm.assume(i1 %b) [ "affected"(i8* %res2) ]
     br label %done
 
 ; An assume that can be used to simplify this comparison dominates each
 ; predecessor branch (although no assume dominates the cmp itself). Make sure
 ; this still can be simplified.
 
 done:
     %res = phi i8* [ %res1, %taken ], [ %res2, %not_taken ]

test/Transforms/JumpThreading/assume.ll

 ; RUN: opt -S -jump-threading -dce < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind uwtable
 define i32 @test1(i32 %a, i32 %b) #0 {
 entry:
   %cmp = icmp sgt i32 %a, 5
-  tail call void @llvm.assume(i1 %cmp)
+  tail call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
   %cmp1 = icmp sgt i32 %b, 1234
   br i1 %cmp1, label %if.then, label %if.else
 
 ; CHECK-LABEL: @test1
 ; CHECK: icmp sgt i32 %a, 5
 ; CHECK: call void @llvm.assume
 ; CHECK-NOT: icmp sgt i32 %a, 3
 ; CHECK: ret i32

 return:                                           ; preds = %if.else, %if.then, %if.then3
   %retval.0 = phi i32 [ 1, %if.then3 ], [ 0, %if.then ], [ 0, %if.else ]
   ret i32 %retval.0
 }
 
 define i32 @test2(i32 %a) #0 {
 entry:
   %cmp = icmp sgt i32 %a, 5
-  tail call void @llvm.assume(i1 %cmp)
+  tail call void @llvm.assume(i1 %cmp) [ "affected"(i32 %a) ]
   %cmp1 = icmp sgt i32 %a, 3
   br i1 %cmp1, label %if.then, label %return
 
 ; CHECK-LABEL: @test2
 ; CHECK: icmp sgt i32 %a, 5
 ; CHECK: tail call void @llvm.assume
 ; CHECK: tail call void (...) @bar()
 ; CHECK: ret i32 1

test/Transforms/NaryReassociate/NVPTX/nary-gep.ll

 ; t1 = &a[zext(j)];
 ; foo(t1);
 ; t2 = t1 + sext(i);
 ; foo(t2);
 define void @reassociate_gep_assume(float* %a, i32 %i, i32 %j) {
 ; CHECK-LABEL: @reassociate_gep_assume(
   ; assume(j >= 0)
   %cmp = icmp sgt i32 %j, -1
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i32 %j) ]
   %1 = add i32 %i, %j
   %cmp2 = icmp sgt i32 %1, -1
-  call void @llvm.assume(i1 %cmp2)
+  call void @llvm.assume(i1 %cmp2) [ "affected"(i32 %1) ]
 
   %idxprom.j = zext i32 %j to i64
   %2 = getelementptr float, float* %a, i64 %idxprom.j
 ; CHECK: [[t1:[^ ]+]] = getelementptr float, float* %a, i64 %idxprom.j
   call void @foo(float* %2)
 ; CHECK: call void @foo(float* [[t1]])
 
   %idxprom.1 = zext i32 %1 to i64

test/Transforms/SimplifyCFG/switch-dead-default.ll

; CHECK-NEXT: call void @foo
   ret void
 }  
 
 ; All but one bit known zero
 define void @test5(i8 %a) {
 ; CHECK-LABEL: @test5
 ; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
   %cmp = icmp ult i8 %a, 2 
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i8 %a) ]
   switch i8 %a, label %default [i8 1, label %true
                                 i8 0, label %false]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)
   ret void
 default:
   call void @foo(i32 2)
   ret void
 } 
 
 ;; All but one bit known one
 define void @test6(i8 %a) {
 ; CHECK-LABEL: @test6
 ; CHECK: @llvm.assume
 ; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, 254 
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i8 %and, i8 %a) ]
   switch i8 %a, label %default [i8 255, label %true
                                 i8 254, label %false]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)
   ret void
 default:
   call void @foo(i32 2)
   ret void
 }
 
 ; Check that we can eliminate both dead cases and dead defaults
 ; within a single run of simplify-cfg
 define void @test7(i8 %a) {
 ; CHECK-LABEL: @test7
 ; CHECK: @llvm.assume
 ; CHECK: br i1 [[IGNORE:%.*]], label %true, label %false
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, 254 
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i8 %and, i8 %a) ]
   switch i8 %a, label %default [i8 255, label %true
                                 i8 254, label %false
                                 i8 0, label %also_dead]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)

 ;; case this is protecting against is that a bit could be assumed both zero 
 ;; *or* one given we know it's undef.  ValueTracking doesn't do this today,
 ;; but it doesn't hurt to confirm.
 define void @test8(i8 %a) {
 ; CHECK-LABEL: @test8(
 ; CHECK: switch i8
   %and = and i8 %a, 254
   %cmp = icmp eq i8 %and, undef
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i8 %and, i8 %a) ]
   switch i8 %a, label %default [i8 255, label %true
                                 i8 254, label %false]
 true:
   call void @foo(i32 1)
   ret void
 false:
   call void @foo(i32 3)
   ret void
 default:
   call void @foo(i32 2)
   ret void
 }
 
 declare void @llvm.assume(i1)