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 ↗

(On Diff #194477)

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 ↗

(On Diff #194477)

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 ↗

(On Diff #194477)

Yes, I agree that is clearer.

631 ↗

(On Diff #194477)

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

821 ↗

(On Diff #194526)

indentation looks wrong here

831 ↗

(On Diff #194526)

indentation looks wrong here

[sdesmalen]

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

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (match(Arg, m_Not(m_Specific(V))) &&
       Known.setAllZero();
       return;
     }
 
     // The remaining tests are all recursive, so bail out if we hit the limit.
     if (Depth == MaxDepth)
       continue;
 
+    ICmpInst *Cmp = dyn_cast<ICmpInst>(Arg);
+    if (!Cmp)
+      continue;
+
     Value *A, *B;
     auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V)));
 
     CmpInst::Predicate Pred;
     uint64_t C;
+    if (Cmp->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)) {
+      if (match(Cmp, m_c_ICmp(Pred, m_V, m_Value(A))) &&
+          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,
+      } else if (match(Cmp,
                        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))),
+      } else if (match(Cmp, 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,
+      } else if (match(Cmp,
                        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))),
+      } else if (match(Cmp, 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,
+      } else if (match(Cmp,
                        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))),
+      } else if (match(Cmp, 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)),
+      } else if (match(Cmp, 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) {
+                 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))),
+      } else if (match(Cmp, 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) {
+                 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)),
+      } else if (match(Cmp, 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) {
+                 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))),
+      } else if (match(Cmp, 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) {
+                 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 (Cmp->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(Cmp, 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 (Cmp->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(Cmp, 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 (Cmp->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(Cmp, 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 (Cmp->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))) &&
-               Pred == ICmpInst::ICMP_SLT &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
         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))) &&
-               Pred == ICmpInst::ICMP_ULE &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+    } else if (Cmp->getPredicate() == ICmpInst::ICMP_ULE) {
+      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
         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))) &&
-               Pred == ICmpInst::ICMP_ULT &&
-               isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
+    } else if (Cmp->getPredicate() == ICmpInst::ICMP_ULT) {
+      if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
         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();