[InstSimplify] Use knownbits for simplifying `(icmp ugt/ule (or X, Y), X)`; PR64610

[goldstein.w.n]

Summary

(icmp ule (or X, Y), X)

If there are any unique bits between `X` and `Y`
--> false

(icmp ugt (or X, Y), X)

If there are any unique bits between `X` and `Y`
--> true

Proofs: https://alive2.llvm.org/ce/z/igZM4Q

This patch adds new functionality to InstCombine/InstSimplify,
although it should be noted, this logic did exist elsewhere in
LLVM pipeline.

The rationale is InstCombine can produce (icmp (or X, Y), X)
relatively late in the pipeline (after the other passes that would
normally simplify this well have run), leading to missed
optimizations: https://github.com/llvm/llvm-project/issues/64610

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

3135–3140

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

3135–3140

Is that right. It's really 'have a common bit not set', it's okay if there are some though

[goldstein.w.n]

Rebase

llvm/lib/Analysis/InstructionSimplify.cpp

3135–3140

I added some tests that have some overlapping bits to make it more clear.

[nikic]

LGTM

llvm/lib/Analysis/InstructionSimplify.cpp

3135–3140

Oh, I see, I misunderstood what you're going for here. In that case I don't think your comment in the patch description that this does not add new capability is probably not right. I don't think we'd fold the case where there are common bits elsewhere.

I personally think writing the condition here as if ((YKnown.One & RHSKnown.Zero) != 0) would be cleaner.

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

3135–3140

We handle this in other passes. Its new to instsimplify/instcombine.

[goldstein.w.n]

Use nikics suggestion.

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

3135–3140

Used your suggestion, also updated summary to be more clear this is new to instcombine.

[nikic]

I just had the thought that a better way to handle this would be to fold ugt to ne and ule to eq. In fact, this is what D144610 does. I think that would fix the motivating case as well?

llvm/lib/Analysis/InstructionSimplify.cpp

3135

equivalent

[goldstein.w.n]

In D157755#4582486, @nikic wrote:

I just had the thought that a better way to handle this would be to fold ugt to ne and ule to eq. In fact, this is what D144610 does. I think that would fix the motivating case as well?

I believe that would work as well. Happy to replace with D144610

[goldstein.w.n]

Going to go forward with D144610 instead.

[foad]

(icmp ule (or X, Y), X)

If there are any unique bits between X and Y
--> false

I don't understand "unique bits between". I think you mean: if there are any bits set in Y that are not set in X?

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyICmpWithBinOpOnLHS(CmpInst::Predicate Pred,
   Value *Y = nullptr;
   // icmp pred (or X, Y), X
   if (match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) {
     if (Pred == ICmpInst::ICMP_ULT)
       return getFalse(ITy);
     if (Pred == ICmpInst::ICMP_UGE)
       return getTrue(ITy);
 
-    if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
+    if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE ||
+        Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_UGT) {
       KnownBits RHSKnown = computeKnownBits(RHS, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
       KnownBits YKnown = computeKnownBits(Y, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+
+      if (ICmpInst::isSigned(Pred)) {
         if (RHSKnown.isNonNegative() && YKnown.isNegative())
           return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy);
         if (RHSKnown.isNegative() || YKnown.isNonNegative())
           return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy);
+
+      }
+      // Check if there are any bits in Y set that are not set in RHS.
+      // If this is the case the `(or X, Y)` cannot equal `X`. For ULE/UGT, the
+      // only case the equality is true/false is equality, so we can constant
+      // fold those cases.
+      // NB: Y.One & RHS.Zero is equivilent of ~Y & RHS != 0.
+      else if ((YKnown.One & RHSKnown.Zero) != 0) {
+        // We could also do EQ/NE here, but seems unnecessary as they are
+        // handled elsewhere so no reason to spend the extra time on
+        // computeKnownBits.
+        return ICmpInst::isTrueWhenEqual(Pred) ? getFalse(ITy) : getTrue(ITy);
+      }
     }
   }
 
   // icmp pred (and X, Y), X
   if (match(LBO, m_c_And(m_Value(), m_Specific(RHS)))) {
     if (Pred == ICmpInst::ICMP_UGT)
       return getFalse(ITy);
     if (Pred == ICmpInst::ICMP_ULE)

llvm/test/Transforms/InstSimplify/icmp-orx-x.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instsimplify -S | FileCheck %s
 
 define i1 @or_simplify_ule(i8 %y_in, i8 %rhs_in, i1 %c) {
 ; CHECK-LABEL: @or_simplify_ule(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[Y_IN:%.*]], 1
-; CHECK-NEXT:    [[RHS:%.*]] = and i8 [[RHS_IN:%.*]], -2
-; CHECK-NEXT:    [[LBO:%.*]] = or i8 [[Y]], [[RHS]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[LBO]], [[RHS]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %y = or i8 %y_in, 1
   %rhs = and i8 %rhs_in, -2
   %lbo = or i8 %y, %rhs
   %r = icmp ule i8 %lbo, %rhs
   ret i1 %r
 }
 
 define i1 @or_simplify_uge(i8 %y_in, i8 %rhs_in, i1 %c) {
 ; CHECK-LABEL: @or_simplify_uge(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[Y_IN:%.*]], -127
-; CHECK-NEXT:    [[RHS:%.*]] = and i8 [[RHS_IN:%.*]], 127
-; CHECK-NEXT:    [[LBO:%.*]] = or i8 [[Y]], [[RHS]]
-; CHECK-NEXT:    [[R:%.*]] = icmp uge i8 [[RHS]], [[LBO]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %y = or i8 %y_in, 129
   %rhs = and i8 %rhs_in, 127
   %lbo = or i8 %y, %rhs
   %r = icmp uge i8 %rhs, %lbo
   ret i1 %r
 }
 
;
   %rhs = and i8 %rhs_in, 127
   %lbo = or i8 %y, %rhs
   %r = icmp ule i8 %lbo, %rhs
   ret i1 %r
 }
 
 define i1 @or_simplify_ugt(i8 %y_in, i8 %rhs_in) {
 ; CHECK-LABEL: @or_simplify_ugt(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[Y_IN:%.*]], 1
-; CHECK-NEXT:    [[RHS:%.*]] = and i8 [[RHS_IN:%.*]], -2
-; CHECK-NEXT:    [[LBO:%.*]] = or i8 [[Y]], [[RHS]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[LBO]], [[RHS]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = or i8 %y_in, 1
   %rhs = and i8 %rhs_in, -2
   %lbo = or i8 %y, %rhs
   %r = icmp ugt i8 %lbo, %rhs
   ret i1 %r
 }
 
 define i1 @or_simplify_ult(i8 %y_in, i8 %rhs_in) {
 ; CHECK-LABEL: @or_simplify_ult(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[Y_IN:%.*]], 36
-; CHECK-NEXT:    [[RHS:%.*]] = and i8 [[RHS_IN:%.*]], -5
-; CHECK-NEXT:    [[LBO:%.*]] = or i8 [[Y]], [[RHS]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[RHS]], [[LBO]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = or i8 %y_in, 36
   %rhs = and i8 %rhs_in, -5
   %lbo = or i8 %y, %rhs
   %r = icmp ult i8 %rhs, %lbo
   ret i1 %r
 }
 
;
   %rhs = or i8 %rhs_in, 1
   %lbo = or i8 %y, %rhs
   %r = icmp ugt i8 %lbo, %rhs
   ret i1 %r
 }
 
 define i1 @pr64610(ptr %b) {
 ; CHECK-LABEL: @pr64610(
-; CHECK-NEXT:    [[V:%.*]] = load i1, ptr [[B:%.*]], align 2
-; CHECK-NEXT:    [[S:%.*]] = select i1 [[V]], i32 74, i32 0
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[S]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i32 [[OR]], [[S]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %v = load i1, ptr %b, align 2
   %s = select i1 %v, i32 74, i32 0
   %or = or i32 %s, 1
   %r = icmp ugt i32 %or, %s
   ret i1 %r
 }