[ValueTracking] don't recursively compute known bits using multiple llvm.assumes

[spatel]

Summary

This is an alternative to D99759 to avoid the compile-time explosion seen in:
https://llvm.org/PR49785

The suggestion was to make the exclusion logic stronger to avoid blowing up, but I'm not seeing how to do that. Note that we reduced the complexity of the exclusion mechanism in D16204 because it was too costly.

So I'm questioning the need for recursion/exclusion entirely - what is the optimization value vs. cost of recursively computing known bits based on assumptions? This was built into the implementation from the start with 60db058, and we have kept adding code/cost to deal with that capability.

By clearing the query's AssumptionCache inside computeKnownBitsFromAssume(), this patch retains all existing assume functionality except refining known bits based on even more assumptions.

We have 1 regression test that shows a difference in optimization power. Is that example representative of real-world llvm.assume usage?

[nikic]

The suggestion was to make the exclusion logic stronger to avoid blowing up, but I'm not seeing how to do that. Note that we reduced the complexity of the exclusion mechanism in D16204 because it was too costly.

What I had in mind was to exclude not a specific assume, but all assumes on a given value (the value passed to assumptionsFor). However, this change by itself did not fix the issue (only in conjunction with a limit on number of assumes visited in the loop).

I like your idea here though. Recursing over assumes does seem to be of rather questionable value. For the affected example, if we use less silly instruction ordering, GVN would canonicalize the variables (https://llvm.godbolt.org/z/1cn93nEh1) after which the recursion is no longer necessary.

So this LGTM. Maybe wait a bit in case someone has an alternative suggestion.

[lebedev.ri]

In D100573#2692006, @nikic wrote:

The suggestion was to make the exclusion logic stronger to avoid blowing up, but I'm not seeing how to do that. Note that we reduced the complexity of the exclusion mechanism in D16204 because it was too costly.

What I had in mind was to exclude not a specific assume, but all assumes on a given value (the value passed to assumptionsFor). However, this change by itself did not fix the issue (only in conjunction with a limit on number of assumes visited in the loop).

I like your idea here though. Recursing over assumes does seem to be of rather questionable value.

Note that we canonicalize assume(x && y) to assume(x), assume(y), so we really ought to do better than just give up.

For the affected example, if we use less silly instruction ordering, GVN would canonicalize the variables (https://llvm.godbolt.org/z/1cn93nEh1) after which the recursion is no longer necessary.

So this LGTM. Maybe wait a bit in case someone has an alternative suggestion.

[nikic]

In D100573#2692136, @lebedev.ri wrote:

Note that we canonicalize assume(x && y) to assume(x), assume(y), so we really ought to do better than just give up.

Not sure I see what relation that has to this issue. We still process all applicable assumes. We'll just not make use of even more assumes when doing recursive queries while already handling an assume.

Let me try to state the core problem here: ValueTracking walks are depth-limited. This is fine as long as the branching factor is low. At a typical branching factor <= 2, going to a depth of 6 has maximum complexity of 2^64, which is reasonable. However, we need to be careful whenever the branching factor is higher than that. For a factor b=3, complexity is already 3^6 = 729, which is beyond reasonable bounds. I believe there are only two cases where we can run into this issue: One is phi nodes, where the branching factor is the number of phi node arguments. The other are assumes, where the branching factor is the number of applicable assumes for a value.

In such cases, we need to apply *some* kind of limit to avoid pathological compile-time costs. What we do for phi nodes is to perform the recursive known bits queries with a depth of MaxDepth-1, which aggressively limits the number of recursions we can do with high branching factor. This patch uses an alternative approach, which forbids further use a assumes in the recursive queries.

That does also suggest a possible alternative approach here, which is to do the same thing we do for phi nodes and do the recursive queries with MaxDepth-1.

[spatel]

In D100573#2692336, @nikic wrote:

That does also suggest a possible alternative approach here, which is to do the same thing we do for phi nodes and do the recursive queries with MaxDepth-1.

Right - I drafted something with that approach, so I can clean it up and post it if that's preferable.

That's a more limiting approach IIUC because that would cut off all recursive analysis for the computeKnownBits calls within computeKnownBitsFromAssume(). The proposal here still allows recursion through other methods like computeKnownBitsFromOperator(), but only clips before we descend via another round of computeKnownBitsFromAssume().

[nikic]

In D100573#2692468, @spatel wrote:

In D100573#2692336, @nikic wrote:

That does also suggest a possible alternative approach here, which is to do the same thing we do for phi nodes and do the recursive queries with MaxDepth-1.

Right - I drafted something with that approach, so I can clean it up and post it if that's preferable.

That's a more limiting approach IIUC because that would cut off all recursive analysis for the computeKnownBits calls within computeKnownBitsFromAssume(). The proposal here still allows recursion through other methods like computeKnownBitsFromOperator(), but only clips before we descend via another round of computeKnownBitsFromAssume().

I think both variants would perform similarly in practice, because these recursive known bits calls are mostly just unnecessary over-generalization. In practice, we expect assume patterns to be things like (a & 15) == 0 to say that a value is aligned, not (a & k1) == k2, where we happen to be able to infer something based on known bits in k1 and k2.

As I don't expect either variant to have much practical impact, I'd be okay either way, but prefer the option you implemented in this patch, because it also gets rid of the assume exclusion mechanism. That's a nice cleanup.

llvm/lib/Analysis/ValueTracking.cpp

struct Query {
   AssumptionCache *AC;
   const Instruction *CxtI;
   const DominatorTree *DT;
 
   // Unlike the other analyses, this may be a nullptr because not all clients
   // provide it currently.
   OptimizationRemarkEmitter *ORE;
 
-  /// Set of assumptions that should be excluded from further queries.
-  /// This is because of the potential for mutual recursion to cause
-  /// computeKnownBits to repeatedly visit the same assume intrinsic. The
-  /// classic case of this is assume(x = y), which will attempt to determine
-  /// bits in x from bits in y, which will attempt to determine bits in y from
-  /// bits in x, etc. Regarding the mutual recursion, computeKnownBits can call
-  /// isKnownNonZero, which calls computeKnownBits and isKnownToBeAPowerOfTwo
-  /// (all of which can call computeKnownBits), and so on.
-  std::array<const Value *, MaxAnalysisRecursionDepth> Excluded;
-
   /// If true, it is safe to use metadata during simplification.
   InstrInfoQuery IIQ;
 
-  unsigned NumExcluded = 0;
-
   Query(const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI,
         const DominatorTree *DT, bool UseInstrInfo,
         OptimizationRemarkEmitter *ORE = nullptr)
       : DL(DL), AC(AC), CxtI(CxtI), DT(DT), ORE(ORE), IIQ(UseInstrInfo) {}
-
-  Query(const Query &Q, const Value *NewExcl)
-      : DL(Q.DL), AC(Q.AC), CxtI(Q.CxtI), DT(Q.DT), ORE(Q.ORE), IIQ(Q.IIQ),
-        NumExcluded(Q.NumExcluded) {
-    Excluded = Q.Excluded;
-    Excluded[NumExcluded++] = NewExcl;
-    assert(NumExcluded <= Excluded.size());
-  }
-
-  bool isExcluded(const Value *Value) const {
-    if (NumExcluded == 0)
-      return false;
-    auto End = Excluded.begin() + NumExcluded;
-    return std::find(Excluded.begin(), End, Value) != End;
-  }
 };
 
 } // end anonymous namespace
 
 // Given the provided Value and, potentially, a context instruction, return
 // the preferred context instruction (if any).
 static const Instruction *safeCxtI(const Value *V, const Instruction *CxtI) {
   // If we've been provided with a context instruction, then use that (provided
static bool isKnownNonZeroFromAssume(const Value *V, const Query &Q) {
   }
 
   for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     if (!AssumeVH)
       continue;
     CallInst *I = cast<CallInst>(AssumeVH);
     assert(I->getFunction() == Q.CxtI->getFunction() &&
            "Got assumption for the wrong function!");
-    if (Q.isExcluded(I))
-      continue;
 
     // Warning: This loop can end up being somewhat performance sensitive.
     // We're running this loop for once for each value queried resulting in a
     // runtime of ~O(#assumes * #values).
 
     assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
            "must be an assume intrinsic");
 
static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known,
   // in AssumptionCache::updateAffectedValues.
 
   for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     if (!AssumeVH)
       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 sensitive.
     // We're running this loop for once for each value queried resulting in a
     // runtime of ~O(#assumes * #values).
 
     assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
            "must be an assume intrinsic");
 
for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     // The remaining tests are all recursive, so bail out if we hit the limit.
     if (Depth == MaxAnalysisRecursionDepth)
       continue;
 
     ICmpInst *Cmp = dyn_cast<ICmpInst>(Arg);
     if (!Cmp)
       continue;
 
+    // We are attempting to compute known bits for the operands of an assume.
+    // Do not try to use other assumptions for those recursive calls because
+    // that can lead to mutual recursion and a compile-time explosion.
+    // An example of the mutual recursion: computeKnownBits can call
+    // isKnownNonZero which calls computeKnownBitsFromAssume (this function)
+    // and so on.
+    Query QueryNoAC = Q;
+    QueryNoAC.AC = nullptr;
+
     // Note that ptrtoint may change the bitwidth.
     Value *A, *B;
     auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V)));
 
     CmpInst::Predicate Pred;
     uint64_t C;
     switch (Cmp->getPredicate()) {
     default:
       break;
     case ICmpInst::ICMP_EQ:
       // assume(v = a)
       if (match(Cmp, m_c_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         Known.Zero |= RHSKnown.Zero;
         Known.One  |= RHSKnown.One;
       // assume(v & b = a)
       } else if (match(Cmp,
                        m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits MaskKnown =
-            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in the mask that are known to be one, we can propagate
         // known bits from the RHS to V.
         Known.Zero |= RHSKnown.Zero & MaskKnown.One;
         Known.One  |= RHSKnown.One  & MaskKnown.One;
       // assume(~(v & b) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_c_And(m_V, m_Value(B))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits MaskKnown =
-            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in the mask that are known to be one, we can propagate
         // inverted known bits from the RHS to V.
         Known.Zero |= RHSKnown.One  & MaskKnown.One;
         Known.One  |= RHSKnown.Zero & MaskKnown.One;
       // assume(v | b = a)
       } else if (match(Cmp,
                        m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits BKnown =
-            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate known
         // bits from the RHS to V.
         Known.Zero |= RHSKnown.Zero & BKnown.Zero;
         Known.One  |= RHSKnown.One  & BKnown.Zero;
       // assume(~(v | b) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_c_Or(m_V, m_Value(B))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits BKnown =
-            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate
         // inverted known bits from the RHS to V.
         Known.Zero |= RHSKnown.One  & BKnown.Zero;
         Known.One  |= RHSKnown.Zero & BKnown.Zero;
       // assume(v ^ b = a)
       } else if (match(Cmp,
                        m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits BKnown =
-            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // 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.
         Known.Zero |= RHSKnown.Zero & BKnown.Zero;
         Known.One  |= RHSKnown.One  & BKnown.Zero;
         Known.Zero |= RHSKnown.One  & BKnown.One;
         Known.One  |= RHSKnown.Zero & BKnown.One;
       // assume(~(v ^ b) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_c_Xor(m_V, m_Value(B))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         KnownBits BKnown =
-            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(B, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // 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.
         Known.Zero |= RHSKnown.One  & BKnown.Zero;
         Known.One  |= RHSKnown.Zero & BKnown.Zero;
         Known.Zero |= RHSKnown.Zero & BKnown.One;
         Known.One  |= RHSKnown.One  & BKnown.One;
       // assume(v << c = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Shl(m_V, m_ConstantInt(C)),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // For those bits in RHS that are known, we can propagate them to known
         // bits in V shifted to the right by C.
         RHSKnown.Zero.lshrInPlace(C);
         Known.Zero |= RHSKnown.Zero;
         RHSKnown.One.lshrInPlace(C);
         Known.One  |= RHSKnown.One;
       // assume(~(v << c) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         // For those bits in RHS that are known, we can propagate them inverted
         // to known bits in V shifted to the right by C.
         RHSKnown.One.lshrInPlace(C);
         Known.Zero |= RHSKnown.One;
         RHSKnown.Zero.lshrInPlace(C);
         Known.One  |= RHSKnown.Zero;
       // assume(v >> c = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Shr(m_V, m_ConstantInt(C)),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         // For those bits in RHS that are known, we can propagate them to known
         // bits in V shifted to the right by C.
         Known.Zero |= RHSKnown.Zero << C;
         Known.One  |= RHSKnown.One  << C;
       // assume(~(v >> c) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_Shr(m_V, m_ConstantInt(C))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
         // For those bits in RHS that are known, we can propagate them inverted
         // to known bits in V shifted to the right by C.
         Known.Zero |= RHSKnown.One  << C;
         Known.One  |= RHSKnown.Zero << C;
       }
       break;
     case ICmpInst::ICMP_SGE:
       // assume(v >=_s c) where c is non-negative
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth + 1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         if (RHSKnown.isNonNegative()) {
           // We know that the sign bit is zero.
           Known.makeNonNegative();
         }
       }
       break;
     case ICmpInst::ICMP_SGT:
       // assume(v >_s c) where c is at least -1.
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth + 1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         if (RHSKnown.isAllOnes() || RHSKnown.isNonNegative()) {
           // We know that the sign bit is zero.
           Known.makeNonNegative();
         }
       }
       break;
     case ICmpInst::ICMP_SLE:
       // assume(v <=_s c) where c is negative
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth + 1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         if (RHSKnown.isNegative()) {
           // We know that the sign bit is one.
           Known.makeNegative();
         }
       }
       break;
     case ICmpInst::ICMP_SLT:
       // assume(v <_s c) where c is non-positive
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         if (RHSKnown.isZero() || RHSKnown.isNegative()) {
           // We know that the sign bit is one.
           Known.makeNegative();
         }
       }
       break;
     case ICmpInst::ICMP_ULE:
       // assume(v <=_u c)
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // Whatever high bits in c are zero are known to be zero.
         Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros());
       }
       break;
     case ICmpInst::ICMP_ULT:
       // assume(v <_u c)
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown =
-            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+            computeKnownBits(A, Depth+1, QueryNoAC).anyextOrTrunc(BitWidth);
 
         // If the RHS is known zero, then this assumption must be wrong (nothing
         // is unsigned less than zero). Signal a conflict and get out of here.
         if (RHSKnown.isZero()) {
           Known.Zero.setAllBits();
           Known.One.setAllBits();
           break;
         }
 
         // 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, QueryNoAC))
           Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros() + 1);
         else
           Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros());
       }
       break;
     }
   }
 

llvm/test/Transforms/InstCombine/assume.ll

; Don't be fooled by other assumes around.
   %cmp = icmp eq i32 %and, 1
   tail call void @llvm.assume(i1 %cmp)
 
   tail call void @llvm.assume(i1 %y)
 
   ret i32 %and1
 }
 
-define i32 @bar4(i32 %a, i32 %b) {
-; CHECK-LABEL: @bar4(
+; If we allow recursive known bits queries based on
+; assumptions, we could do better here:
+; a == b and a & 7 == 1, so b & 7 == 1, so b & 3 == 1, so return 1.
+
+define i32 @known_bits_recursion_via_assumes(i32 %a, i32 %b) {
+; CHECK-LABEL: @known_bits_recursion_via_assumes(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], 3
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A:%.*]], 7
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 1
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[A]], [[B:%.*]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[A]], [[B]]
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
-; CHECK-NEXT:    ret i32 1
+; CHECK-NEXT:    ret i32 [[AND1]]
 ;
 entry:
   %and1 = and i32 %b, 3
   %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)