[ValueTracking] Teach isImpliedCondition a new bitwise trick

[sanjoy]

Summary

This change teaches isImpliedCondition to prove things like

(A | 15) < L  ==>  (A | 14) < L

if the low 4 bits of A are known to be zero.

Depends on D14391

[reames]

lib/Analysis/ValueTracking.cpp

4123

A cleaner way of framing this content is simply to state that X | C where X low bits are zero is equivalent to X+C.

4136

Hm, might it be cleaner to introduce a matcher which matches both adds and adds implemented via OR? Doing so would simplify this code, but might involve recomputing known bits twice. Not sure if this is actually a good idea or not.

4143

This is equivalent to 1 << LowZeroes right?

Might be clearer as uge(MaskOfOnesForLowZeros).

[sanjoy]

• address review

[reames]

LGTM w/fix for issues in comment and test which would have caught same.

lib/Analysis/ValueTracking.cpp

4127

match(B? You have A repeated twice.

[sanjoy]

lib/Analysis/ValueTracking.cpp

4127

Thanks for catching that!

When re-reading the code, I noticed something else -- the ULT and UGT clauses in isTruePredicate are unused / untested, since we only ever call it with ULE and UGE. Given that, I'm inclined to remove the the unused / untested clauses (in a separate change) -- what do you think?

[sanjoy]

lib/Analysis/ValueTracking.cpp

4127

I removed the untested cases in r252676.

lib/Analysis/ValueTracking.cpp

case CmpInst::ICMP_ULE: {
 
     // LHS u<  LHS +_{nuw} C   if C != 0
     // LHS u<= LHS +_{nuw} C
     if (match(RHS, m_NUWAdd(m_Specific(LHS), m_ConstantInt(CI)))) {
       if (Pred == CmpInst::ICMP_ULT)
         return !CI->isZero();
       return true;
     }
+
+    // If the low K bits of X are known to be zero, and both C0 and C1
+    // fit in K bits, then
+    //
+    // (X | C0) u<  (X | C1)    iff C0 u<  C1
+    // (X | C0) u<= (X | C1)    iff C0 u<= C1
+    //
+    // Informally, the easiest way to justify this is to see that
+    // "X | C" if C fits in K bits (where the low K bits of X are
+    // zero) is equal to "X +_{nuw} C".  Then this rule is effectively
+    // the same as "C0 u< C1" ==> "(X +_{nuw} C0) u< (X +_{nuw} C1)".
+
+    Value *X;
+    ConstantInt *CI0, *CI1;
+    if (match(LHS, m_Or(m_Value(X), m_ConstantInt(CI0))) &&
+        match(RHS, m_Or(m_Specific(X), m_ConstantInt(CI1)))) {
+      unsigned BitWidth = cast<IntegerType>(LHS->getType())->getBitWidth();
+      APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
+      computeKnownBits(X, KnownZero, KnownOne, DL, Depth + 1, AC, CxtI, DT);
+
+      unsigned LowZeroes = KnownZero.countTrailingOnes();
+      APInt UpperLimit =
+          APInt::getBitsSet(KnownZero.getBitWidth(), LowZeroes, LowZeroes + 1);
+
+      if (UpperLimit.ugt(CI0->getValue()) && UpperLimit.ugt(CI1->getValue())) {
+        if (Pred == CmpInst::ICMP_ULE)
+          return CI0->getValue().ule(CI1->getValue());
+        return CI0->getValue().ult(CI1->getValue());
+      }
+    }
     return false;
   }
   }
 }
 
 /// Return true if "icmp Pred BLHS BRHS" is true whenever "icmp Pred
 /// ALHS ARHS" is true.
 static bool isImpliedCondOperands(CmpInst::Predicate Pred, Value *ALHS,

test/Transforms/InstSimplify/implies.ll

 ; CHECK: ret i1 true
   %iplus1 = add nuw i32 %i, -100
   %var29 = icmp ult i32 %i, %length.i
   %var30 = icmp ult i32 %iplus1, %length.i
   %res = icmp ule i1 %var30, %var29
   ret i1 %res
 }
 
+define i1 @test10(i32 %length.i, i32 %x.full) {
+; CHECK-LABEL: @test10(
+; CHECK:  ret i1 true
+
+  %x = and i32 %x.full, 4294901760  ;; 4294901760 == 0xffff0000
+  %large = or i32 %x, 100
+  %small = or i32 %x, 90
+  %known = icmp ult i32 %large, %length.i
+  %to.prove = icmp ult i32 %small, %length.i
+  %res = icmp ule i1 %known, %to.prove
+  ret i1 %res
+}
+
+define i1 @test11(i32 %length.i, i32 %x) {
+; CHECK-LABEL: @test11(
+; CHECK: %res = icmp ule i1 %known, %to.prove
+; CHECK: ret i1 %res
+
+  %large = or i32 %x, 100
+  %small = or i32 %x, 90
+  %known = icmp ult i32 %large, %length.i
+  %to.prove = icmp ult i32 %small, %length.i
+  %res = icmp ule i1 %known, %to.prove
+  ret i1 %res
+}
+
+define i1 @test12(i32 %length.i, i32 %x.full) {
+; CHECK-LABEL: @test12(
+; CHECK: %res = icmp ule i1 %known, %to.prove
+; CHECK: ret i1 %res
+
+  %x = and i32 %x.full, 4294901760  ;; 4294901760 == 0xffff0000
+  %large = or i32 %x, 65536 ;; 65536 == 0x00010000
+  %small = or i32 %x, 90
+  %known = icmp ult i32 %large, %length.i
+  %to.prove = icmp ult i32 %small, %length.i
+  %res = icmp ule i1 %known, %to.prove
+  ret i1 %res
+}
+
 ; X >=(s) Y == X ==> Y (i1 1 becomes -1 for reasoning)
 define i1 @test_sge(i32 %length.i, i32 %i) {
 ; CHECK-LABEL: @test_sge
 ; CHECK: ret i1 true
   %iplus1 = add nsw nuw i32 %i, 1
   %var29 = icmp ult i32 %i, %length.i
   %var30 = icmp ult i32 %iplus1, %length.i
   %res = icmp sge i1 %var30, %var29
   ret i1 %res
 }