InstCombine: Combine two icmps into one if the RHSs agree

[majnemer]

Summary

consider:
%cmp1 = icmp CC %V1, C
%cmp2 = icmp CC %V2, C
%and = and %cmp1, %cmp2

we can transform this into:
%or = or %V1, %V2
%cmp = icmp CC %or, C

This saves us an instruction and generates considerably nicer assembly
for X86, X86-64, arm, powerpc64 and aarch64.

[majnemer]

• We only need to consider the uses of the and operands.

[majnemer]

• move the test from or.ll to and.ll

[mcrosier]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

819

Perhaps,
Ty->isIntOrIntVectorTy()

822

Should this be

if (LHS->hasOneUse() && RHS->hasOneUse())

We should check to make sure the both compares have one and only one use, right?

[mcrosier]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

814

Also, do we need a check to make sure the CCs match?

[mcrosier]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

814

Nevermind, I see the check now..

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (LHS->getOperand(0) == RHS->getOperand(0) &&
       return getNewICmpValue(isSigned, Code, Op0, Op1, Builder);
     }
   }
 
   // handle (roughly):  (icmp eq (A & B), C) & (icmp eq (A & D), E)
   if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
     return V;
 
-  // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
   Value *Val = LHS->getOperand(0), *Val2 = RHS->getOperand(0);
-  ConstantInt *LHSCst = dyn_cast<ConstantInt>(LHS->getOperand(1));
-  ConstantInt *RHSCst = dyn_cast<ConstantInt>(RHS->getOperand(1));
-  if (!LHSCst || !RHSCst) return nullptr;
 
-  if (LHSCst == RHSCst && LHSCC == RHSCC) {
-    // (icmp ult A, C) & (icmp ult B, C) --> (icmp ult (A|B), C)
-    // where C is a power of 2
-    if (LHSCC == ICmpInst::ICMP_ULT &&
-        LHSCst->getValue().isPowerOf2()) {
+  // (icmp CC A, C) & (icmp CC B, C) --> (icmp CC (A|B), C)
+  if (LHS->getOperand(1) == RHS->getOperand(1) && LHSCC == RHSCC) {
+    const Type *Ty = Val->getType();
+    if (Ty->isIntegerTy() ||
+        (Ty->isVectorTy() &&
+         cast<VectorType>(Ty)->getElementType()->isIntegerTy())) {
+      // We are creating two instructions; make sure we are replacing at least
+      // that many.
+      if (LHS->hasOneUse() || RHS->hasOneUse()) {
         Value *NewOr = Builder->CreateOr(Val, Val2);
-      return Builder->CreateICmp(LHSCC, NewOr, LHSCst);
+        return Builder->CreateICmp(LHSCC, NewOr, LHS->getOperand(1));
       }
-
-    // (icmp eq A, 0) & (icmp eq B, 0) --> (icmp eq (A|B), 0)
-    if (LHSCC == ICmpInst::ICMP_EQ && LHSCst->isZero()) {
-      Value *NewOr = Builder->CreateOr(Val, Val2);
-      return Builder->CreateICmp(LHSCC, NewOr, LHSCst);
     }
   }
 
+  // This only handles icmp of constants: (icmp1 A, C1) & (icmp2 B, C2).
+  ConstantInt *LHSCst = dyn_cast<ConstantInt>(LHS->getOperand(1));
+  ConstantInt *RHSCst = dyn_cast<ConstantInt>(RHS->getOperand(1));
+  if (!LHSCst || !RHSCst) return nullptr;
+
   // (trunc x) == C1 & (and x, CA) == C2 -> (and x, CA|CMAX) == C1|C2
   // where CMAX is the all ones value for the truncated type,
   // iff the lower bits of C2 and CA are zero.
   if (LHSCC == ICmpInst::ICMP_EQ && LHSCC == RHSCC &&
       LHS->hasOneUse() && RHS->hasOneUse()) {
     Value *V;
     ConstantInt *AndCst, *SmallCst = nullptr, *BigCst = nullptr;
 

test/Transforms/InstCombine/2008-08-05-And.ll

-; RUN: opt < %s -instcombine -S | not grep or
+; RUN: opt < %s -instcombine -S | FileCheck %s
 ; PR2629
 
 define void @f(i8* %x) nounwind  {
 entry:
         br label %bb
 
 bb:
   %g1 = getelementptr i8* %x, i32 0
         %l1 = load i8* %g1, align 1
   %s1 = sub i8 %l1, 6
   %c1 = icmp ugt i8 %s1, 2
   %s2 = sub i8 %l1, 10
         %c2 = icmp ugt i8 %s2, 2
         %a1 = and i1 %c1, %c2
+; CHECK:      %[[LOAD:.*]] = load i8* %x, align 1
+; CHECK-NEXT: %[[ADD1:.*]] = add i8 %[[LOAD]], -6
+; CHECK-NEXT: %[[ADD2:.*]] = add i8 %[[LOAD]], -10
+; CHECK-NEXT: %[[OR:.*]] = or i8 %[[ADD1]], %[[ADD2]]
+; CHECK-NEXT: %[[ICMP:.*]] = icmp ugt i8 %[[OR]], 2
   br i1 %a1, label %incompatible, label %okay
 
 okay:
         ret void
 
 incompatible:
         ret void
 }

test/Transforms/InstCombine/and.ll

 ; This test makes sure that these instructions are properly eliminated.
 ;
 
-; RUN: opt < %s -instcombine -S | not grep and
+; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i32 @test1(i32 %A) {
-        ; zero result
         %B = and i32 %A, 0              ; <i32> [#uses=1]
         ret i32 %B
+; CHECK-LABEL: @test1(
+; CHECK: ret i32 0
 }
 
 define i32 @test2(i32 %A) {
-        ; noop
         %B = and i32 %A, -1             ; <i32> [#uses=1]
         ret i32 %B
+; CHECK-LABEL: @test2(
+; CHECK: ret i32 %A
 }
 
 define i1 @test3(i1 %A) {
         ; always = false
         %B = and i1 %A, false           ; <i1> [#uses=1]
         ret i1 %B
+; CHECK-LABEL: @test3(
+; CHECK: ret i1 false
 }
 
 define i1 @test4(i1 %A) {
         ; noop
         %B = and i1 %A, true            ; <i1> [#uses=1]
         ret i1 %B
+; CHECK-LABEL: @test4(
+; CHECK: ret i1 %A
 }
 
 define i32 @test5(i32 %A) {
         %B = and i32 %A, %A             ; <i32> [#uses=1]
         ret i32 %B
+; CHECK-LABEL: @test5(
+; CHECK: ret i32 %A
 }
 
 define i1 @test6(i1 %A) {
         %B = and i1 %A, %A              ; <i1> [#uses=1]
         ret i1 %B
+; CHECK-LABEL: @test6(
+; CHECK: ret i1 %A
 }
 
 ; A & ~A == 0
 define i32 @test7(i32 %A) {
         %NotA = xor i32 %A, -1          ; <i32> [#uses=1]
         %B = and i32 %A, %NotA          ; <i32> [#uses=1]
         ret i32 %B
+; CHECK-LABEL: @test7(
+; CHECK: ret i32 0
 }
 
 ; AND associates
 define i8 @test8(i8 %A) {
         %B = and i8 %A, 3               ; <i8> [#uses=1]
         %C = and i8 %B, 4               ; <i8> [#uses=1]
         ret i8 %C
+; CHECK-LABEL: @test8(
+; CHECK: ret i8 0
 }
 
 define i1 @test9(i32 %A) {
         ; Test of sign bit, convert to setle %A, 0
         %B = and i32 %A, -2147483648            ; <i32> [#uses=1]
         %C = icmp ne i32 %B, 0          ; <i1> [#uses=1]
         ret i1 %C
+; CHECK-LABEL: @test9(
+; CHECK: %[[CMP:.*]] = icmp slt i32 %A, 0
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i1 @test9a(i32 %A) {
         ; Test of sign bit, convert to setle %A, 0
         %B = and i32 %A, -2147483648            ; <i32> [#uses=1]
         %C = icmp ne i32 %B, 0          ; <i1> [#uses=1]
         ret i1 %C
+; CHECK-LABEL: @test9a(
+; CHECK: %[[CMP:.*]] = icmp slt i32 %A, 0
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i32 @test10(i32 %A) {
         %B = and i32 %A, 12             ; <i32> [#uses=1]
         %C = xor i32 %B, 15             ; <i32> [#uses=1]
         ; (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
         %D = and i32 %C, 1              ; <i32> [#uses=1]
         ret i32 %D
+; CHECK-LABEL: @test10(
+; CHECK: ret i32 1
 }
 
 define i32 @test11(i32 %A, i32* %P) {
         %B = or i32 %A, 3               ; <i32> [#uses=1]
         %C = xor i32 %B, 12             ; <i32> [#uses=2]
         ; additional use of C
         store i32 %C, i32* %P
         ; %C = and uint %B, 3 --> 3
         %D = and i32 %C, 3              ; <i32> [#uses=1]
         ret i32 %D
+; CHECK-LABEL: @test11(
+; CHECK: ret i32 3
 }
 
 define i1 @test12(i32 %A, i32 %B) {
         %C1 = icmp ult i32 %A, %B               ; <i1> [#uses=1]
         %C2 = icmp ule i32 %A, %B               ; <i1> [#uses=1]
         ; (A < B) & (A <= B) === (A < B)
         %D = and i1 %C1, %C2            ; <i1> [#uses=1]
         ret i1 %D
+; CHECK-LABEL: @test12(
+; CHECK: %[[CMP:.*]] = icmp ult i32 %A, %B
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i1 @test13(i32 %A, i32 %B) {
         %C1 = icmp ult i32 %A, %B               ; <i1> [#uses=1]
         %C2 = icmp ugt i32 %A, %B               ; <i1> [#uses=1]
         ; (A < B) & (A > B) === false
         %D = and i1 %C1, %C2            ; <i1> [#uses=1]
         ret i1 %D
+; CHECK-LABEL: @test13(
+; CHECK: ret i1 false
 }
 
 define i1 @test14(i8 %A) {
         %B = and i8 %A, -128            ; <i8> [#uses=1]
         %C = icmp ne i8 %B, 0           ; <i1> [#uses=1]
         ret i1 %C
+; CHECK-LABEL: @test14(
+; CHECK: %[[CMP:.*]] = icmp slt i8 %A, 0
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i8 @test15(i8 %A) {
         %B = lshr i8 %A, 7              ; <i8> [#uses=1]
         ; Always equals zero
         %C = and i8 %B, 2               ; <i8> [#uses=1]
         ret i8 %C
+; CHECK-LABEL: @test15(
+; CHECK: ret i8 0
 }
 
 define i8 @test16(i8 %A) {
         %B = shl i8 %A, 2               ; <i8> [#uses=1]
         %C = and i8 %B, 3               ; <i8> [#uses=1]
         ret i8 %C
+; CHECK-LABEL: @test16(
+; CHECK: ret i8 0
 }
 
 ;; ~(~X & Y) --> (X | ~Y)
 define i8 @test17(i8 %X, i8 %Y) {
         %B = xor i8 %X, -1              ; <i8> [#uses=1]
         %C = and i8 %B, %Y              ; <i8> [#uses=1]
         %D = xor i8 %C, -1              ; <i8> [#uses=1]
         ret i8 %D
+; CHECK-LABEL: @test17(
+; CHECK: %[[XOR:.*]] = xor i8 %Y, -1
+; CHECK: %[[OR:.*]] = or i8 %X, %[[XOR]]
+; CHECK: ret i8 %[[OR]]
 }
 
 define i1 @test18(i32 %A) {
         %B = and i32 %A, -128           ; <i32> [#uses=1]
         ;; C >= 128
         %C = icmp ne i32 %B, 0          ; <i1> [#uses=1]
         ret i1 %C
+; CHECK-LABEL: @test18(
+; CHECK: %[[CMP:.*]] = icmp ugt i32 %A, 127
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i1 @test18a(i8 %A) {
         %B = and i8 %A, -2              ; <i8> [#uses=1]
         %C = icmp eq i8 %B, 0           ; <i1> [#uses=1]
         ret i1 %C
+; CHECK-LABEL: @test18a(
+; CHECK: %[[CMP:.*]] = icmp ult i8 %A, 2
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i32 @test19(i32 %A) {
         %B = shl i32 %A, 3              ; <i32> [#uses=1]
         ;; Clearing a zero bit
         %C = and i32 %B, -2             ; <i32> [#uses=1]
         ret i32 %C
+; CHECK-LABEL: @test19(
+; CHECK: %[[SHL:.*]] = shl i32 %A, 3
+; CHECK: ret i32 %[[SHL]]
 }
 
 define i8 @test20(i8 %A) {
         %C = lshr i8 %A, 7              ; <i8> [#uses=1]
         ;; Unneeded
         %D = and i8 %C, 1               ; <i8> [#uses=1]
         ret i8 %D
+; CHECK-LABEL: @test20(
+; CHECK: %[[SHL:.*]] = lshr i8 %A, 7
+; CHECK: ret i8 %[[SHL]]
 }
 
 define i1 @test22(i32 %A) {
         %B = icmp eq i32 %A, 1          ; <i1> [#uses=1]
         %C = icmp sge i32 %A, 3         ; <i1> [#uses=1]
         ;; false
         %D = and i1 %B, %C              ; <i1> [#uses=1]
         ret i1 %D
+; CHECK-LABEL: @test22(
+; CHECK: ret i1 false
 }
 
 define i1 @test23(i32 %A) {
         %B = icmp sgt i32 %A, 1         ; <i1> [#uses=1]
         %C = icmp sle i32 %A, 2         ; <i1> [#uses=1]
         ;; A == 2
         %D = and i1 %B, %C              ; <i1> [#uses=1]
         ret i1 %D
+; CHECK-LABEL: @test23(
+; CHECK: %[[CMP:.*]] = icmp eq i32 %A, 2
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i1 @test24(i32 %A) {
         %B = icmp sgt i32 %A, 1         ; <i1> [#uses=1]
         %C = icmp ne i32 %A, 2          ; <i1> [#uses=1]
         ;; A > 2
         %D = and i1 %B, %C              ; <i1> [#uses=1]
         ret i1 %D
+; CHECK-LABEL: @test24(
+; CHECK: %[[CMP:.*]] = icmp sgt i32 %A, 2
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i1 @test25(i32 %A) {
         %B = icmp sge i32 %A, 50                ; <i1> [#uses=1]
         %C = icmp slt i32 %A, 100               ; <i1> [#uses=1]
         ;; (A-50) <u 50
         %D = and i1 %B, %C              ; <i1> [#uses=1]
         ret i1 %D
+; CHECK-LABEL: @test25(
+; CHECK: %[[ADD:.*]] = add i32 %A, -50
+; CHECK: %[[CMP:.*]] = icmp ult i32 %[[ADD]], 50
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i1 @test26(i32 %A) {
         %B = icmp ne i32 %A, 49         ; <i1> [#uses=1]
         %C = icmp ne i32 %A, 50         ; <i1> [#uses=1]
         ;; (A-49) > 1
         %D = and i1 %B, %C              ; <i1> [#uses=1]
         ret i1 %D
+; CHECK-LABEL: @test26(
+; CHECK: %[[ADD:.*]] = add i32 %A, -49
+; CHECK: %[[CMP:.*]] = icmp ugt i32 %[[ADD]], 1
+; CHECK: ret i1 %[[CMP]]
 }
 
 define i8 @test27(i8 %A) {
         %B = and i8 %A, 4               ; <i8> [#uses=1]
         %C = sub i8 %B, 16              ; <i8> [#uses=1]
         ;; 0xF0
         %D = and i8 %C, -16             ; <i8> [#uses=1]
         %E = add i8 %D, 16              ; <i8> [#uses=1]
         ret i8 %E
+; CHECK-LABEL: @test27(
+; CHECK: ret i8 0
 }
 
 ;; This is juse a zero extending shr.
 define i32 @test28(i32 %X) {
         ;; Sign extend
         %Y = ashr i32 %X, 24            ; <i32> [#uses=1]
         ;; Mask out sign bits
         %Z = and i32 %Y, 255            ; <i32> [#uses=1]
         ret i32 %Z
+; CHECK-LABEL: @test28(
+; CHECK: %[[SHL:.*]] = lshr i32 %X, 24
+; CHECK: ret i32 %[[SHL]]
 }
 
 define i32 @test29(i8 %X) {
         %Y = zext i8 %X to i32          ; <i32> [#uses=1]
        ;; Zero extend makes this unneeded.
         %Z = and i32 %Y, 255            ; <i32> [#uses=1]
         ret i32 %Z
+; CHECK-LABEL: @test29(
+; CHECK: %[[ZEXT:.*]] = zext i8 %X to i32
+; CHECK: ret i32 %[[ZEXT]]
 }
 
 define i32 @test30(i1 %X) {
         %Y = zext i1 %X to i32          ; <i32> [#uses=1]
         %Z = and i32 %Y, 1              ; <i32> [#uses=1]
         ret i32 %Z
+; CHECK-LABEL: @test30(
+; CHECK: %[[ZEXT:.*]] = zext i1 %X to i32
+; CHECK: ret i32 %[[ZEXT]]
 }
 
 define i32 @test31(i1 %X) {
         %Y = zext i1 %X to i32          ; <i32> [#uses=1]
         %Z = shl i32 %Y, 4              ; <i32> [#uses=1]
         %A = and i32 %Z, 16             ; <i32> [#uses=1]
         ret i32 %A
+; CHECK-LABEL: @test31(
+; CHECK: %[[ZEXT:.*]] = zext i1 %X to i32
+; CHECK: %[[SHL:.*]] = shl nuw nsw i32 %[[ZEXT]], 4
+; CHECK: ret i32 %[[SHL]]
 }
 
 define i32 @test32(i32 %In) {
         %Y = and i32 %In, 16            ; <i32> [#uses=1]
         %Z = lshr i32 %Y, 2             ; <i32> [#uses=1]
         %A = and i32 %Z, 1              ; <i32> [#uses=1]
         ret i32 %A
+; CHECK-LABEL: @test32(
+; CHECK: ret i32 0
 }
 
 ;; Code corresponding to one-bit bitfield ^1.
 define i32 @test33(i32 %b) {
         %tmp.4.mask = and i32 %b, 1             ; <i32> [#uses=1]
         %tmp.10 = xor i32 %tmp.4.mask, 1                ; <i32> [#uses=1]
         %tmp.12 = and i32 %b, -2                ; <i32> [#uses=1]
         %tmp.13 = or i32 %tmp.12, %tmp.10               ; <i32> [#uses=1]
         ret i32 %tmp.13
+; CHECK-LABEL: @test33(
+; CHECK: %[[XOR:.*]] = xor i32 %b, 1
+; CHECK: ret i32 %[[XOR]]
 }
 
 define i32 @test34(i32 %A, i32 %B) {
         %tmp.2 = or i32 %B, %A          ; <i32> [#uses=1]
         %tmp.4 = and i32 %tmp.2, %B             ; <i32> [#uses=1]
         ret i32 %tmp.4
+; CHECK-LABEL: @test34(
+; CHECK: ret i32 %B
 }
 
+define i1 @test35(i32 %a, i32 %b) {
+  %cmp1 = icmp slt i32 %a, 8
+  %cmp2 = icmp slt i32 %b, 8
+  %ret = and i1 %cmp1, %cmp2
+  ret i1 %ret
+; CHECK-LABEL: test35(
+; CHECK-NEXT: %[[OR:.*]]  = or i32 %a, %b
+; CHECK-NEXT: %[[CMP:.*]] = icmp slt i32 %[[OR]], 8
+; CHECK-NEXT: ret i1 %[[CMP]]
+}