[InstCombine] Canonicalize icmp eq pow2 more thoroughly

[nikic]

Summary

We currently already canonicalize icmp eq (%x & Pow2), Pow2 to icmp ne (%x & Pow2), 0. This patch generalizes the fold based on known bits.

In particular, this allows us to handle comparisons against !range !{i64 0, i64 2} loads, which addresses an optimization regression in Rust caused by https://github.com/llvm/llvm-project/commit/8df376db7282b955e7990cb8887ee9dcd3565040.

[goldstein.w.n]

LGTM.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5765

nit: "is" -> "is known to be".
also maybe "Pow2" -> "C_Pow2" so its a little clearer to you are refering to the exact same value.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(BOp1, m_APInt(BOC)) && BO->hasOneUse() && RHS->isAllOnesValue()) {
       // Replace (X | C) == -1 with (X & ~C) == ~C.
       // This removes the -1 constant.
       Constant *NotBOC = ConstantExpr::getNot(cast<Constant>(BOp1));
       Value *And = Builder.CreateAnd(BOp0, NotBOC);
       return new ICmpInst(Pred, And, NotBOC);
     }
     break;
   }
-  case Instruction::And: {
-    const APInt *BOC;
-    if (match(BOp1, m_APInt(BOC))) {
-      // If we have ((X & C) == C), turn it into ((X & C) != 0).
-      if (C == *BOC && C.isPowerOf2())
-        return new ICmpInst(isICMP_NE ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
-                            BO, Constant::getNullValue(RHS->getType()));
-    }
-    break;
-  }
   case Instruction::UDiv:
     if (C.isZero()) {
       // (icmp eq/ne (udiv A, B), 0) -> (icmp ugt/ule i32 B, A)
       auto NewPred = isICMP_NE ? ICmpInst::ICMP_ULE : ICmpInst::ICMP_UGT;
       return new ICmpInst(NewPred, BOp1, BOp0);
     }
     break;
   default:
if (Op1Known.isZero()) {
           unsigned Log2C2 = C2Pow2.countr_zero();
           auto *CmpC = ConstantInt::get(XTy, Log2C2 - Log2C1);
           auto NewPred =
               Pred == CmpInst::ICMP_EQ ? CmpInst::ICMP_UGE : CmpInst::ICMP_ULT;
           return new ICmpInst(NewPred, X, CmpC);
         }
       }
     }
+
+    // Op0 eq C_Pow2 -> Op0 ne 0 if Op0 is known to be C_Pow2 or zero.
+    if (Op1Known.isConstant() && Op1Known.getConstant().isPowerOf2() &&
+        (Op0Known & Op1Known) == Op0Known)
+      return new ICmpInst(CmpInst::getInversePredicate(Pred), Op0,
+                          ConstantInt::getNullValue(Op1->getType()));
     break;
   }
   case ICmpInst::ICMP_ULT: {
     if (Op0Max.ult(Op1Min)) // A <u B -> true if max(A) < min(B)
       return replaceInstUsesWith(I, ConstantInt::getTrue(I.getType()));
     if (Op0Min.uge(Op1Max)) // A <u B -> false if min(A) >= max(B)
       return replaceInstUsesWith(I, ConstantInt::getFalse(I.getType()));
     break;

llvm/test/Transforms/InstCombine/div.ll

 ;
   %mul = mul nuw i32 %a, 36
   %div = udiv i32 %mul, 3
   ret i32 %div
 }
 
 define i32 @test29(i32 %a) {
 ; CHECK-LABEL: @test29(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i32 [[A:%.*]], 0
 ; CHECK-NEXT:    [[DIV:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK-NEXT:    ret i32 [[DIV]]
 ;
   %mul = shl nsw i32 %a, 31
   %div = sdiv i32 %mul, -2147483648
   ret i32 %div
 }
 

llvm/test/Transforms/InstCombine/icmp-range.ll

;
   %val = load i64, ptr %ptr, align 8, !range !{i64 0, i64 2}
   %cmp = icmp eq i64 %val, 0
   ret i1 %cmp
 }
 
 define i1 @icmp_eq_bool_1(ptr %ptr) {
 ; CHECK-LABEL: @icmp_eq_bool_1(
 ; CHECK-NEXT:    [[VAL:%.*]] = load i64, ptr [[PTR:%.*]], align 8, !range [[RNG6]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[VAL]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[VAL]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %val = load i64, ptr %ptr, align 8, !range !{i64 0, i64 2}
   %cmp = icmp eq i64 %val, 1
   ret i1 %cmp
 }
 
 define i1 @icmp_ne_bool_0(ptr %ptr) {
 ; CHECK-LABEL: @icmp_ne_bool_0(
 ; CHECK-NEXT:    [[VAL:%.*]] = load i64, ptr [[PTR:%.*]], align 8, !range [[RNG6]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[VAL]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %val = load i64, ptr %ptr, align 8, !range !{i64 0, i64 2}
   %cmp = icmp ne i64 %val, 0
   ret i1 %cmp
 }
 
 define i1 @icmp_ne_bool_1(ptr %ptr) {
 ; CHECK-LABEL: @icmp_ne_bool_1(
 ; CHECK-NEXT:    [[VAL:%.*]] = load i64, ptr [[PTR:%.*]], align 8, !range [[RNG6]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[VAL]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[VAL]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %val = load i64, ptr %ptr, align 8, !range !{i64 0, i64 2}
   %cmp = icmp ne i64 %val, 1
   ret i1 %cmp
 }
 
 !0 = !{i32 1, i32 6}
 !1 = !{i32 0, i32 6}
 !2 = !{i8 0, i8 1}
 !3 = !{i8 0, i8 6}
 !4 = !{i32 1, i32 6, i32 8, i32 10}
 !5 = !{i32 5, i32 10}
 !6 = !{i32 8, i32 16}

llvm/test/Transforms/InstCombine/icmp-shl-nsw.ll

 }
 
 ; Compares with 126 and 127 are recognized as always false.
 
 ; Known bits analysis turns this into an equality predicate.
 
 define i1 @icmp_sgt9(i8 %x) {
 ; CHECK-LABEL: @icmp_sgt9(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X:%.*]], -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl nsw i8 %x, 7
   %cmp = icmp sgt i8 %shl, -128
   ret i1 %cmp
 }
 
 define i1 @icmp_sgt10(i8 %x) {

 }
 
 ; Compares with 126 and 127 are recognized as always true.
 
 ; Known bits analysis turns this into an equality predicate.
 
 define i1 @icmp_sle9(i8 %x) {
 ; CHECK-LABEL: @icmp_sle9(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], -1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl nsw i8 %x, 7
   %cmp = icmp sle i8 %shl, -128
   ret i1 %cmp
 }
 
 define i1 @icmp_sle10(i8 %x) {

llvm/test/Transforms/InstCombine/icmp-shr-lt-gt.ll

 ;
   %s = lshr exact i4 %x, 3
   %c = icmp ult i4 %s, 0
   ret i1 %c
 }
 
 define i1 @lshrult_03_01_exact(i4 %x) {
 ; CHECK-LABEL: @lshrult_03_01_exact(
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i4 [[X:%.*]], -8
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = lshr exact i4 %x, 3
   %c = icmp ult i4 %s, 1
   ret i1 %c
 }
 
 define i1 @lshrult_03_02_exact(i4 %x) {

llvm/test/Transforms/InstCombine/zext.ll

;
   %cmp = icmp eq i64 %val, 0
   %len = zext i1 %cmp to i64
   ret i64 %len
 }
 
 define i64 @zext_icmp_eq_bool_1(ptr %ptr) {
 ; CHECK-LABEL: @zext_icmp_eq_bool_1(
 ; CHECK-NEXT:    [[VAL:%.*]] = load i64, ptr [[PTR:%.*]], align 8, !range [[RNG0]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[VAL]], 1
-; CHECK-NEXT:    [[LEN:%.*]] = zext i1 [[CMP]] to i64
-; CHECK-NEXT:    ret i64 [[LEN]]
+; CHECK-NEXT:    ret i64 [[VAL]]
 ;
   %val = load i64, ptr %ptr, align 8, !range !{i64 0, i64 2}
   %cmp = icmp eq i64 %val, 1
   %len = zext i1 %cmp to i64
   ret i64 %len
 }
 
 define i64 @zext_icmp_ne_bool_0(ptr %ptr) {
 ; CHECK-LABEL: @zext_icmp_ne_bool_0(
 ; CHECK-NEXT:    [[VAL:%.*]] = load i64, ptr [[PTR:%.*]], align 8, !range [[RNG0]]
 ; CHECK-NEXT:    ret i64 [[VAL]]
 ;
   %val = load i64, ptr %ptr, align 8, !range !{i64 0, i64 2}
   %cmp = icmp ne i64 %val, 0
   %len = zext i1 %cmp to i64
   ret i64 %len
 }
 
 define i64 @zext_icmp_ne_bool_1(ptr %ptr) {
 ; CHECK-LABEL: @zext_icmp_ne_bool_1(
 ; CHECK-NEXT:    [[VAL:%.*]] = load i64, ptr [[PTR:%.*]], align 8, !range [[RNG0]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[VAL]], 1
-; CHECK-NEXT:    [[LEN:%.*]] = zext i1 [[CMP]] to i64
+; CHECK-NEXT:    [[LEN:%.*]] = xor i64 [[VAL]], 1
 ; CHECK-NEXT:    ret i64 [[LEN]]
 ;
   %val = load i64, ptr %ptr, align 8, !range !{i64 0, i64 2}
   %cmp = icmp ne i64 %val, 1
   %len = zext i1 %cmp to i64
   ret i64 %len
 }