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 ↗

(On Diff #79744)

auto
rename it to II?

lib/Analysis/ValueTracking.cpp

531 ↗

(On Diff #79744)

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 ↗

(On Diff #79744)

Sure.

lib/Analysis/ValueTracking.cpp

531 ↗

(On Diff #79744)

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!

llvm/trunk/docs/LangRef.rst

 ``"gc-transition"`` operand bundle tag. These operand bundles mark a
 call as a transition between a function with one GC strategy to a
 function with a different GC strategy. If coordinating the transition
 between GC strategies requires additional code generation at the call
 site, these bundles may contain any values that are needed by the
 generated code.  For more details, see :ref:`GC Transitions
 <gc_transition_args>`.
 
+Affected Operand Bundles
+^^^^^^^^^^^^^^^^^^^^^^^^
+
+Affected operand bundles are characterized by the ``"affected"`` operand bundle
+tag. These operand bundles indicate that a call, specifically a call to an
+intrinsic like ``llvm.assume``, implies some additional knowledge about the
+values within the bundle. This enables the optimizer to efficiently find these
+relationships. The optimizer will add these automatically.
+
 .. _moduleasm:
 
 Module-Level Inline Assembly
 ----------------------------
 
 Modules may contain "module-level inline asm" blocks, which corresponds
 to the GCC "file scope inline asm" blocks. These blocks are internally
 concatenated by LLVM and treated as a single unit, but may be separated

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

private:
   ///
   typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>
       ValueExprMapType;
 
   /// This is a cache of the values we have analyzed so far.
   ///
   ValueExprMapType ValueExprMap;
 
+  /// This is a map of SCEVs to intrinsics (e.g. assumptions) that might affect
+  /// (i.e. imply something about) them.
+  DenseMap<const SCEV *, SetVector<Value *>> AffectedMap;
+
   /// Mark predicate values currently being processed by isImpliedCond.
   SmallPtrSet<Value *, 6> PendingLoopPredicates;
 
   /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
   /// conditions dominating the backedge of a loop.
   bool WalkingBEDominatingConds;
 
   /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop,
                                     const SCEV *MaxBECount, unsigned BitWidth);
 
   /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
   /// Stop} by "factoring out" a ternary expression from the add recurrence.
   /// Helper called by \c getRange.
   ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop,
                                      const SCEV *MaxBECount, unsigned BitWidth);
 
+  /// Add to the AffectedMap this SCEV if its operands are in the AffectedMap.
+  void addAffectedFromOperands(const SCEV *S);
+
   /// We know that there is no SCEV for the specified value.  Analyze the
   /// expression.
   const SCEV *createSCEV(Value *V);
 
   /// Provide the special handling we need to analyze PHI SCEVs.
   const SCEV *createNodeForPHI(PHINode *PN);
 
   /// Helper function called from createNodeForPHI.

llvm/trunk/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,

llvm/trunk/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()) {
+    auto *II = dyn_cast<IntrinsicInst>(U);
+    if (!II)
       continue;
-    auto *I = cast<CallInst>(AssumeVH);
-    if (!isValidAssumeForContext(I, BBI, DT))
+    if (II->getIntrinsicID() != Intrinsic::assume)
+      continue;
+    if (!isValidAssumeForContext(II, BBI, DT))
       continue;
 
-    BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
+    BBLV = intersect(BBLV, getValueFromCondition(Val, II->getArgOperand(0)));
   }
 
   // If guards are not used in the module, don't spend time looking for them
   auto *GuardDecl = BBI->getModule()->getFunction(
           Intrinsic::getName(Intrinsic::experimental_guard));
   if (!GuardDecl || GuardDecl->use_empty())
     return;
 

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op,
   }
 
   // The cast wasn't folded; create an explicit cast node. We can reuse
   // the existing insert position since if we get here, we won't have
   // made any changes which would invalidate it.
   SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator),
                                                  Op, Ty);
   UniqueSCEVs.InsertNode(S, IP);
+  addAffectedFromOperands(S);
   return S;
 }
 
 // Get the limit of a recurrence such that incrementing by Step cannot cause
 // signed overflow as long as the value of the recurrence within the
 // loop does not exceed this limit before incrementing.
 static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step,
                                                  ICmpInst::Predicate *Pred,
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()) {
+          !AffectedMap.empty()) {
         // 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) -
                                       getUnsignedRange(Step).getUnsignedMax());
const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op,
   }
 
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
                                                    Op, Ty);
   UniqueSCEVs.InsertNode(S, IP);
+  addAffectedFromOperands(S);
   return S;
 }
 
 const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
                                                Type *Ty) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
if (AR->isAffine()) {
       // 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()) {
+          !AffectedMap.empty()) {
         // 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 =
             getSignedOverflowLimitForStep(Step, &Pred, this);
if (isKnownNonNegative(Op))
     return getZeroExtendExpr(Op, Ty);
 
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
                                                    Op, Ty);
   UniqueSCEVs.InsertNode(S, IP);
+  addAffectedFromOperands(S);
   return S;
 }
 
 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
 /// unspecified bits out to the given type.
 ///
 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,
                                               Type *Ty) {
#endif
   SCEVAddExpr *S =
     static_cast<SCEVAddExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
   if (!S) {
     const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
     std::uninitialized_copy(Ops.begin(), Ops.end(), O);
     S = new (SCEVAllocator) SCEVAddExpr(ID.Intern(SCEVAllocator),
                                         O, Ops.size());
     UniqueSCEVs.InsertNode(S, IP);
+    addAffectedFromOperands(S);
   }
   S->setNoWrapFlags(Flags);
   return S;
 }
 
 static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow) {
   uint64_t k = i*j;
   if (j > 1 && k / j != i) Overflow = true;
#endif
   SCEVMulExpr *S =
     static_cast<SCEVMulExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
   if (!S) {
     const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
     std::uninitialized_copy(Ops.begin(), Ops.end(), O);
     S = new (SCEVAllocator) SCEVMulExpr(ID.Intern(SCEVAllocator),
                                         O, Ops.size());
     UniqueSCEVs.InsertNode(S, IP);
+    addAffectedFromOperands(S);
   }
   S->setNoWrapFlags(Flags);
   return S;
 }
 
 /// Get a canonical unsigned division expression, or something simpler if
 /// possible.
 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
   ID.AddInteger(scUDivExpr);
   ID.AddPointer(LHS);
   ID.AddPointer(RHS);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
                                              LHS, RHS);
   UniqueSCEVs.InsertNode(S, IP);
+  addAffectedFromOperands(S);
   return S;
 }
 
 static const APInt gcd(const SCEVConstant *C1, const SCEVConstant *C2) {
   APInt A = C1->getAPInt().abs();
   APInt B = C2->getAPInt().abs();
   uint32_t ABW = A.getBitWidth();
   uint32_t BBW = B.getBitWidth();
#endif
   SCEVAddRecExpr *S =
     static_cast<SCEVAddRecExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
   if (!S) {
     const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Operands.size());
     std::uninitialized_copy(Operands.begin(), Operands.end(), O);
     S = new (SCEVAllocator) SCEVAddRecExpr(ID.Intern(SCEVAllocator),
                                            O, Operands.size(), L);
     UniqueSCEVs.InsertNode(S, IP);
+    addAffectedFromOperands(S);
   }
   S->setNoWrapFlags(Flags);
   return S;
 }
 
 const SCEV *
 ScalarEvolution::getGEPExpr(GEPOperator *GEP,
                             const SmallVectorImpl<const SCEV *> &IndexExprs) {
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
   std::uninitialized_copy(Ops.begin(), Ops.end(), O);
   SCEV *S = new (SCEVAllocator) SCEVSMaxExpr(ID.Intern(SCEVAllocator),
                                              O, Ops.size());
   UniqueSCEVs.InsertNode(S, IP);
+  addAffectedFromOperands(S);
   return S;
 }
 
 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
   return getUMaxExpr(Ops);
 }
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
   std::uninitialized_copy(Ops.begin(), Ops.end(), O);
   SCEV *S = new (SCEVAllocator) SCEVUMaxExpr(ID.Intern(SCEVAllocator),
                                              O, Ops.size());
   UniqueSCEVs.InsertNode(S, IP);
+  addAffectedFromOperands(S);
   return S;
 }
 
 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   // ~smax(~x, ~y) == smin(x, y).
   return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
 }
if (Pair.second) {
       // increase the complexity of the expansion code.
       // If V is GetElementPtrInst, don't save Stripped -> {V, offset}
       // because it may generate add/sub instead of GEP in SCEV expansion.
       if (Offset != nullptr && !isa<SCEVUnknown>(Stripped) &&
           !isa<GetElementPtrInst>(V))
         ExprValueMap[Stripped].insert({V, Offset});
     }
   }
+
+  // If this value is an instruction or an argument, and might be affected by
+  // an assumption, and its SCEV to the AffectedMap.
+  if (isa<Instruction>(V) || isa<Argument>(V)) {
+    for (auto *U : V->users()) {
+      auto *II = dyn_cast<IntrinsicInst>(U);
+      if (!II)
+        continue;
+      if (II->getIntrinsicID() != Intrinsic::assume)
+        continue;
+
+      AffectedMap[S].insert(II);
+    }
+  }
+
   return S;
 }
 
+// If one of this SCEV's operands is in the AffectedMap (meaning that it might
+// be affected by an assumption), then this SCEV might be affected by the same
+// assumption.
+void ScalarEvolution::addAffectedFromOperands(const SCEV *S) {
+  if (auto *NS = dyn_cast<SCEVNAryExpr>(S))
+    for (auto *Op : NS->operands()) {
+      auto AMI = AffectedMap.find(Op);
+      if (AMI == AffectedMap.end())
+        continue;
+
+      AffectedMap[S].insert(AMI->second.begin(), AMI->second.end());
+    }
+}
+
 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   ValueExprMapType::iterator I = ValueExprMap.find_as(V);
   if (I != ValueExprMap.end()) {
     const SCEV *S = I->second;
     if (checkValidity(S))
       return S;
if (LatchBECount != getCouldNotCompute()) {
     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 CheckAssumptions = [&](const SCEV *S) {
+    auto AMI = AffectedMap.find(S);
+    if (AMI != AffectedMap.end())
+      for (auto *Assume : AMI->second) {
+        auto *CI = cast<CallInst>(Assume);
         if (!DT.dominates(CI, Latch->getTerminator()))
           continue;
 
         if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
           return true;
       }
 
+    return false;
+  };
+
+  if (CheckAssumptions(LHS) || CheckAssumptions(RHS))
+    return true;
+
   // If the loop is not reachable from the entry block, we risk running into an
   // infinite loop as we walk up into the dom tree.  These loops do not matter
   // anyway, so we just return a conservative answer when we see them.
   if (!DT.isReachableFromEntry(L->getHeader()))
     return false;
 
   if (isImpliedViaGuard(Latch, Pred, LHS, RHS))
     return true;
for (std::pair<BasicBlock *, BasicBlock *>
 
     if (isImpliedCond(Pred, LHS, RHS,
                       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 CheckAssumptions = [&](const SCEV *S) {
+    auto AMI = AffectedMap.find(S);
+    if (AMI != AffectedMap.end())
+      for (auto *Assume : AMI->second) {
+        auto *CI = cast<CallInst>(Assume);
         if (!DT.dominates(CI, L->getHeader()))
           continue;
 
         if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
           return true;
       }
 
     return false;
+  };
+
+  if (CheckAssumptions(LHS) || CheckAssumptions(RHS))
+    return true;
+
+  return false;
 }
 
 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred,
                                     const SCEV *LHS, const SCEV *RHS,
                                     Value *FoundCondValue,
                                     bool Inverse) {
   if (!PendingLoopPredicates.insert(FoundCondValue).second)
     return false;

llvm/trunk/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()) {
+    auto *II = dyn_cast<IntrinsicInst>(U);
+    if (!II)
       continue;
-    CallInst *I = cast<CallInst>(AssumeVH);
-    assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() &&
-           "Got assumption for the wrong function!");
-    if (Q.isExcluded(I))
+    if (II->getIntrinsicID() != Intrinsic::assume)
+      continue;
+    if (Q.isExcluded(II))
       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);
+    Value *Arg = II->getArgOperand(0);
 
-    if (Arg == V && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+    if (Arg == V && isValidAssumeForContext(II, 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))));
 
     CmpInst::Predicate Pred;
     ConstantInt *C;
     // assume(v = a)
     if (match(Arg, m_c_ICmp(Pred, m_V, m_Value(A))) &&
-        Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+        Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       KnownZero |= RHSKnownZero;
       KnownOne  |= RHSKnownOne;
     // assume(v & b = a)
     } else if (match(Arg,
                      m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0);
-      computeKnownBits(B, MaskKnownZero, MaskKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(B, MaskKnownZero, MaskKnownOne, Depth+1, Query(Q, II));
 
       // For those bits in the mask that are known to be one, we can propagate
       // known bits from the RHS to V.
       KnownZero |= RHSKnownZero & MaskKnownOne;
       KnownOne  |= RHSKnownOne  & MaskKnownOne;
     // assume(~(v & b) = a)
     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_And(m_V, m_Value(B))),
                                    m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0);
-      computeKnownBits(B, MaskKnownZero, MaskKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(B, MaskKnownZero, MaskKnownOne, Depth+1, Query(Q, II));
 
       // For those bits in the mask that are known to be one, we can propagate
       // inverted known bits from the RHS to V.
       KnownZero |= RHSKnownOne  & MaskKnownOne;
       KnownOne  |= RHSKnownZero & MaskKnownOne;
     // assume(v | b = a)
     } else if (match(Arg,
                      m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
-      computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, II));
 
       // For those bits in B that are known to be zero, we can propagate known
       // bits from the RHS to V.
       KnownZero |= RHSKnownZero & BKnownZero;
       KnownOne  |= RHSKnownOne  & BKnownZero;
     // assume(~(v | b) = a)
     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Or(m_V, m_Value(B))),
                                    m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
-      computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, II));
 
       // For those bits in B that are known to be zero, we can propagate
       // inverted known bits from the RHS to V.
       KnownZero |= RHSKnownOne  & BKnownZero;
       KnownOne  |= RHSKnownZero & BKnownZero;
     // assume(v ^ b = a)
     } else if (match(Arg,
                      m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
-      computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, II));
 
       // For those bits in B that are known to be zero, we can propagate known
       // bits from the RHS to V. For those bits in B that are known to be one,
       // we can propagate inverted known bits from the RHS to V.
       KnownZero |= RHSKnownZero & BKnownZero;
       KnownOne  |= RHSKnownOne  & BKnownZero;
       KnownZero |= RHSKnownOne  & BKnownOne;
       KnownOne  |= RHSKnownZero & BKnownOne;
     // assume(~(v ^ b) = a)
     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_c_Xor(m_V, m_Value(B))),
                                    m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       APInt BKnownZero(BitWidth, 0), BKnownOne(BitWidth, 0);
-      computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(B, BKnownZero, BKnownOne, Depth+1, Query(Q, II));
 
       // For those bits in B that are known to be zero, we can propagate
       // inverted known bits from the RHS to V. For those bits in B that are
       // known to be one, we can propagate known bits from the RHS to V.
       KnownZero |= RHSKnownOne  & BKnownZero;
       KnownOne  |= RHSKnownZero & BKnownZero;
       KnownZero |= RHSKnownZero & BKnownOne;
       KnownOne  |= RHSKnownOne  & BKnownOne;
     // assume(v << c = a)
     } else if (match(Arg, m_c_ICmp(Pred, m_Shl(m_V, m_ConstantInt(C)),
                                    m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       // For those bits in RHS that are known, we can propagate them to known
       // bits in V shifted to the right by C.
       KnownZero |= RHSKnownZero.lshr(C->getZExtValue());
       KnownOne  |= RHSKnownOne.lshr(C->getZExtValue());
     // assume(~(v << c) = a)
     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))),
                                    m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       // For those bits in RHS that are known, we can propagate them inverted
       // to known bits in V shifted to the right by C.
       KnownZero |= RHSKnownOne.lshr(C->getZExtValue());
       KnownOne  |= RHSKnownZero.lshr(C->getZExtValue());
     // assume(v >> c = a)
     } else if (match(Arg,
                      m_c_ICmp(Pred, m_CombineOr(m_LShr(m_V, m_ConstantInt(C)),
                                                 m_AShr(m_V, m_ConstantInt(C))),
                               m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       // For those bits in RHS that are known, we can propagate them to known
       // bits in V shifted to the right by C.
       KnownZero |= RHSKnownZero << C->getZExtValue();
       KnownOne  |= RHSKnownOne  << C->getZExtValue();
     // assume(~(v >> c) = a)
     } else if (match(Arg, m_c_ICmp(Pred, m_Not(m_CombineOr(
                                              m_LShr(m_V, m_ConstantInt(C)),
                                              m_AShr(m_V, m_ConstantInt(C)))),
                                    m_Value(A))) &&
                Pred == ICmpInst::ICMP_EQ &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
       // For those bits in RHS that are known, we can propagate them inverted
       // to known bits in V shifted to the right by C.
       KnownZero |= RHSKnownOne  << C->getZExtValue();
       KnownOne  |= RHSKnownZero << C->getZExtValue();
     // assume(v >=_s c) where c is non-negative
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_SGE &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
 
       if (RHSKnownZero.isNegative()) {
         // We know that the sign bit is zero.
         KnownZero |= APInt::getSignBit(BitWidth);
       }
     // assume(v >_s c) where c is at least -1.
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_SGT &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
 
       if (RHSKnownOne.isAllOnesValue() || RHSKnownZero.isNegative()) {
         // We know that the sign bit is zero.
         KnownZero |= APInt::getSignBit(BitWidth);
       }
     // assume(v <=_s c) where c is negative
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_SLE &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
 
       if (RHSKnownOne.isNegative()) {
         // We know that the sign bit is one.
         KnownOne |= APInt::getSignBit(BitWidth);
       }
     // assume(v <_s c) where c is non-positive
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_SLT &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
 
       if (RHSKnownZero.isAllOnesValue() || RHSKnownOne.isNegative()) {
         // We know that the sign bit is one.
         KnownOne |= APInt::getSignBit(BitWidth);
       }
     // assume(v <=_u c)
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_ULE &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
 
       // Whatever high bits in c are zero are known to be zero.
       KnownZero |=
         APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
     // assume(v <_u c)
     } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                Pred == ICmpInst::ICMP_ULT &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+               isValidAssumeForContext(II, Q.CxtI, Q.DT)) {
       APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0);
-      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I));
+      computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, II));
 
       // Whatever high bits in c are zero are known to be zero (if c is a power
       // of 2, then one more).
-      if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, Query(Q, I)))
+      if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, Query(Q, II)))
         KnownZero |=
           APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes()+1);
       else
         KnownZero |=
           APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
     }
   }
 }

llvm/trunk/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();
 

llvm/trunk/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);

llvm/trunk/test/Analysis/ScalarEvolution/no-wrap-unknown-becount.ll

 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
   %iv.inc = add i32 %iv, 3
   %iv.sext = sext i32 %iv to i64
   %cmp = icmp slt i32 %iv, 10000
 ; CHECK:  %iv.sext = sext i32 %iv to i64
 ; CHECK-NEXT:  -->  {0,+,3}<nuw><nsw><%loop>
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i32 %iv) ]
   %c = load volatile i1, i1* %cond
   br i1 %c, label %loop, label %leave
 
 leave:
   ret void
 }
 
 define void @s_3(i32 %start, i1* %cond) {

 
 loop:
   %iv = phi i32 [ 30000, %entry ], [ %iv.inc, %loop ]
   %iv.inc = add i32 %iv, -2
   %iv.zext = zext i32 %iv to i64
   %cmp = icmp ugt i32 %iv.inc, -10000
 ; CHECK:  %iv.zext = zext i32 %iv to i64
 ; CHECK-NEXT:  -->  {30000,+,-2}<nw><%loop>
-  call void @llvm.assume(i1 %cmp)
+  call void @llvm.assume(i1 %cmp) [ "affected"(i32 %iv.inc) ]
   %c = load volatile i1, i1* %cond
   br i1 %c, label %loop, label %leave
 
 leave:
   ret void
 }
 
 define void @u_3(i32 %start, i1* %cond) {

llvm/trunk/test/Analysis/ScalarEvolution/nsw-offset-assume.ll

 ; RUN: opt < %s -S -analyze -scalar-evolution | FileCheck %s
 
 ; ScalarEvolution should be able to fold away the sign-extensions
 ; on this loop with a primary induction variable incremented with
 ; a nsw add of 2 (this test is derived from the nsw-offset.ll test, but uses an
 ; assume instead of a preheader conditional branch to guard the loop).
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 
 define void @foo(i32 %no, double* nocapture %d, double* nocapture %q) nounwind {
 entry:
   %n = and i32 %no, 4294967294
   %0 = icmp sgt i32 %n, 0                         ; <i1> [#uses=1]
-  tail call void @llvm.assume(i1 %0)
+  tail call void @llvm.assume(i1 %0) [ "affected"(i32 %n) ]
   br label %bb.nph
 
 bb.nph:                                           ; preds = %entry
   br label %bb
 
 bb:                                               ; preds = %bb.nph, %bb1
   %i.01 = phi i32 [ %16, %bb1 ], [ 0, %bb.nph ]   ; <i32> [#uses=5]
 

llvm/trunk/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
 }

llvm/trunk/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

llvm/trunk/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) ]
 }
 
 
 
 
 attributes #0 = { nounwind uwtable }
 attributes #1 = { nounwind }
 

llvm/trunk/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 }
 

llvm/trunk/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

llvm/trunk/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 ]

llvm/trunk/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

llvm/trunk/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

llvm/trunk/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)