NFC: Improve pattern matching in computeKnownBitsFromAssume.

[sdesmalen]

Summary

This patch changes the order of pattern matching by first testing
a compare instruction's predicate, before doing the pattern
match for the whole expression tree. This has a positive impact
on compilation cost.

Patch by Paul Walker.

[spatel]

Seems like a good micro-optimization while actually improving readability slightly. Do you have any performance numbers for this change? It would be good to note those here and in the commit message.

lib/Analysis/ValueTracking.cpp

619–620

IMO, it would make things a bit clearer to name this "Cmp" instead of recycling "Arg" as the name. Then use that name throughout the later code.

631

Here and later, please remove the duplicated check of the predicate value.

[sdesmalen]

We found a case where repeated calls into computeKnownBits(FromAssume) skyrocketed our build-times after we added a call to llvm.assume after vectorized loops to describe the range of a newly introduced induction variable, causing some builds to time-out.
Because the 'less then' or 'less then equal' case was way down this list in this function, it had to go through all the matching calls. Unfortunately I don't have any real numbers to back this up, because we did this work a while ago.

lib/Analysis/ValueTracking.cpp

619–620

Yes, I agree that is clearer.

631

Good catch!

[sdesmalen]

• Removed redundant checks for predicate value.
• Renamed ArgV to Cmp

[spatel]

LGTM

1. Re-run clang-format or manually check indentation; I marked a couple of lines that don't look right.
2. Since this code is still a potential perf problem, consider converting the chain of if-else to a switch on the compare predicate as a follow-up. [insert joke about using a good optimizing compiler... :) ]
3. This patch should not be titled with 'NFC' because it has external motivation/intent. "Improve compile-time performance in computeKnownBitsFromAssume" ?

lib/Analysis/ValueTracking.cpp

846

indentation looks wrong here

864

indentation looks wrong here

[sdesmalen]

Thanks @spatel. I'll also create a follow-up patch to use a switch statement as you suggested!

lib/Analysis/ValueTracking.cpp

for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
 
     // Warning: This loop can end up being somewhat performance sensitive.
     // We're running this loop for once for each value queried resulting in a
     // runtime of ~O(#assumes * #values).
 
     assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
            "must be an assume intrinsic");
 
-    Value *Arg = I->getArgOperand(0);
+    Value *ArgV = I->getArgOperand(0);
 
-    if (Arg == V && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+    if (ArgV == V && isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
       assert(BitWidth == 1 && "assume operand is not i1?");
       Known.setAllOnes();
       return;
     }
-    if (match(Arg, m_Not(m_Specific(V))) &&
+    if (match(ArgV, m_Not(m_Specific(V))) &&
         isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
       assert(BitWidth == 1 && "assume operand is not i1?");
       Known.setAllZero();
       return;
     }
 
     // The remaining tests are all recursive, so bail out if we hit the limit.
     if (Depth == MaxDepth)
       continue;
 
+    ICmpInst *Arg = dyn_cast<ICmpInst>(I->getArgOperand(0));
+    if (!Arg)
+      continue;
+
     Value *A, *B;
     auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V)));
 
     CmpInst::Predicate Pred;
     uint64_t C;
+    if (Arg->getPredicate() == ICmpInst::ICMP_EQ) {
       // 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)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         Known.Zero |= RHSKnown.Zero;
         Known.One  |= RHSKnown.One;
       // 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)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         KnownBits MaskKnown(BitWidth);
         computeKnownBits(B, MaskKnown, Depth+1, Query(Q, I));
 
         // 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(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)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         KnownBits MaskKnown(BitWidth);
         computeKnownBits(B, MaskKnown, Depth+1, Query(Q, I));
 
         // 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(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)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         KnownBits BKnown(BitWidth);
         computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
 
         // 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(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)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         KnownBits BKnown(BitWidth);
         computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
 
         // 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(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)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         KnownBits BKnown(BitWidth);
         computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
 
         // 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(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)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         KnownBits BKnown(BitWidth);
         computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
 
         // 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(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) &&
                  C < BitWidth) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         // 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(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) &&
                  C < BitWidth) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         // 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(Arg,
                        m_c_ICmp(Pred, m_Shr(m_V, m_ConstantInt(C)),
                                 m_Value(A))) &&
                  Pred == ICmpInst::ICMP_EQ &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) &&
                  C < BitWidth) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         // 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(Arg, m_c_ICmp(Pred, m_Not(m_Shr(m_V, m_ConstantInt(C))),
                                      m_Value(A))) &&
                  Pred == ICmpInst::ICMP_EQ &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) &&
                  C < BitWidth) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
         // 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;
+      }
+    } else if (Arg->getPredicate() == ICmpInst::ICMP_SGE) {
       // 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)) {
+      if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
         KnownBits RHSKnown(BitWidth);
-      computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        computeKnownBits(A, RHSKnown, Depth + 1, Query(Q, I));
 
         if (RHSKnown.isNonNegative()) {
           // We know that the sign bit is zero.
           Known.makeNonNegative();
         }
+      }
+    } else if (Arg->getPredicate() == ICmpInst::ICMP_SGT) {
       // 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)) {
+      if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
         KnownBits RHSKnown(BitWidth);
-      computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        computeKnownBits(A, RHSKnown, Depth + 1, Query(Q, I));
 
         if (RHSKnown.isAllOnes() || RHSKnown.isNonNegative()) {
           // We know that the sign bit is zero.
           Known.makeNonNegative();
         }
+      }
+    } else if (Arg->getPredicate() == ICmpInst::ICMP_SLE) {
       // 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)) {
+      if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
         KnownBits RHSKnown(BitWidth);
-      computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        computeKnownBits(A, RHSKnown, Depth + 1, Query(Q, I));
 
         if (RHSKnown.isNegative()) {
           // We know that the sign bit is one.
           Known.makeNegative();
         }
+      }
+    } else if (Arg->getPredicate() == ICmpInst::ICMP_SLT) {
       // assume(v <_s c) where c is non-positive
-    } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
+      if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                  Pred == ICmpInst::ICMP_SLT &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
 
         if (RHSKnown.isZero() || RHSKnown.isNegative()) {
           // We know that the sign bit is one.
           Known.makeNegative();
         }
+      }
     // assume(v <=_u c)
-    } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
+    } else if (Arg->getPredicate() == ICmpInst::ICMP_ULE) {
+      if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                  Pred == ICmpInst::ICMP_ULE &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
 
         // Whatever high bits in c are zero are known to be zero.
         Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros());
+      }
       // assume(v <_u c)
-    } else if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
+    } else if (Arg->getPredicate() == ICmpInst::ICMP_ULT) {
+      if (match(Arg, m_ICmp(Pred, m_V, m_Value(A))) &&
                  Pred == ICmpInst::ICMP_ULT &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
         KnownBits RHSKnown(BitWidth);
         computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
 
         // 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)))
           Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros() + 1);
         else
           Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros());
       }
     }
+  }
 
   // If assumptions conflict with each other or previous known bits, then we
   // have a logical fallacy. It's possible that the assumption is not reachable,
   // so this isn't a real bug. On the other hand, the program may have undefined
   // behavior, or we might have a bug in the compiler. We can't assert/crash, so
   // clear out the known bits, try to warn the user, and hope for the best.
   if (Known.Zero.intersects(Known.One)) {
     Known.resetAll();