[InstSimplify] Teach decomposeBitTestICmp to handle non-canonical compares

[craig.topper]

Summary

This adds support non-canonical compare predicates. InstSimplify can't rely on canonicalization to have occurred.

[spatel]

Make sure I'm seeing this correctly: this patch should contain additional tests for ule/uge; ult/ugt should be added to the step before this (D36593)?

[craig.topper]

Agreed. I'll go back and add the ugt and ult tests to the previous patch.

[craig.topper]

Add test changes for uge and ule.

[spatel]

LGTM.

lib/Analysis/CmpInstAnalysis.cpp

default:
     return false;
   case ICmpInst::ICMP_SLT:
     // X < 0 is equivalent to (X & SignMask) != 0.
     if (!C->isNullValue())
       return false;
     Mask = APInt::getSignMask(C->getBitWidth());
     Pred = ICmpInst::ICMP_NE;
     break;
+  case ICmpInst::ICMP_SLE:
+    // X <= -1 is equivalent to (X & SignMask) != 0.
+    if (!C->isAllOnesValue())
+      return false;
+    Mask = APInt::getSignMask(C->getBitWidth());
+    Pred = ICmpInst::ICMP_NE;
+    break;
   case ICmpInst::ICMP_SGT:
     // X > -1 is equivalent to (X & SignMask) == 0.
     if (!C->isAllOnesValue())
       return false;
     Mask = APInt::getSignMask(C->getBitWidth());
     Pred = ICmpInst::ICMP_EQ;
     break;
+  case ICmpInst::ICMP_SGE:
+    // X >= 0 is equivalent to (X & SignMask) == 0.
+    if (!C->isNullValue())
+      return false;
+    Mask = APInt::getSignMask(C->getBitWidth());
+    Pred = ICmpInst::ICMP_EQ;
+    break;
   case ICmpInst::ICMP_ULT:
     // X <u 2^n is equivalent to (X & ~(2^n-1)) == 0.
     if (!C->isPowerOf2())
       return false;
     Mask = -*C;
     Pred = ICmpInst::ICMP_EQ;
     break;
+  case ICmpInst::ICMP_ULE:
+    // X <=u 2^n-1 is equivalent to (X & ~(2^n-1)) == 0.
+    if (!(*C + 1).isPowerOf2())
+      return false;
+    Mask = ~*C;
+    Pred = ICmpInst::ICMP_EQ;
+    break;
   case ICmpInst::ICMP_UGT:
     // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0.
     if (!(*C + 1).isPowerOf2())
       return false;
     Mask = ~*C;
     Pred = ICmpInst::ICMP_NE;
     break;
+  case ICmpInst::ICMP_UGE:
+    // X >=u 2^n is equivalent to (X & ~(2^n-1)) != 0.
+    if (!C->isPowerOf2())
+      return false;
+    Mask = -*C;
+    Pred = ICmpInst::ICMP_NE;
+    break;
   }
 
   X = LHS;
   return true;
 }

test/Transforms/InstSimplify/select.ll

 ;
   %cmp = icmp slt i32 %X, 0
   %or = or i32 %X, -2147483648
   %cond = select i1 %cmp, i32 %X, i32 %or
   ret i32 %cond
 }
 
 ; Same as above, but the compare isn't canonical
-; TODO: we should be able to simplify this
 define i32 @test4noncanon(i32 %X) {
 ; CHECK-LABEL: @test4noncanon(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X]], -2147483648
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[OR]]
-; CHECK-NEXT:    ret i32 [[COND]]
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], -2147483648
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %cmp = icmp sle i32 %X, -1
   %or = or i32 %X, -2147483648
   %cond = select i1 %cmp, i32 %X, i32 %or
   ret i32 %cond
 }
 
 define i32 @test5(i32 %X) {

 ;
   %cmp = icmp sgt i32 %X, -1
   %or = or i32 %X, -2147483648
   %cond = select i1 %cmp, i32 %or, i32 %X
   ret i32 %cond
 }
 
 ; Same as above, but the compare isn't canonical
-; TODO: we should be able to simplify this
 define i32 @test9noncanon(i32 %X) {
 ; CHECK-LABEL: @test9noncanon(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X]], -2147483648
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[OR]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[COND]]
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], -2147483648
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %cmp = icmp sge i32 %X, 0
   %or = or i32 %X, -2147483648
   %cond = select i1 %cmp, i32 %or, i32 %X
   ret i32 %cond
 }
 
 define i32 @test10(i32 %X) {

 ;
   %cmp = icmp ult i32 %X, 4
   %and = and i32 %X, 3
   %cond = select i1 %cmp, i32 %X, i32 %and
   ret i32 %cond
 }
 
 ; Same as above, but the compare isn't canonical
-; TODO: we should be able to simplify this
 define i32 @test12noncanon(i32 %X) {
 ; CHECK-LABEL: @test12noncanon(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i32 [[X:%.*]], 3
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X]], 3
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[AND]]
-; CHECK-NEXT:    ret i32 [[COND]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 3
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %cmp = icmp ule i32 %X, 3
   %and = and i32 %X, 3
   %cond = select i1 %cmp, i32 %X, i32 %and
   ret i32 %cond
 }
 
 define i32 @test13(i32 %X) {
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %cmp = icmp ugt i32 %X, 3
   %and = and i32 %X, 3
   %cond = select i1 %cmp, i32 %and, i32 %X
   ret i32 %cond
 }
 
 ; Same as above, but the compare isn't canonical
-; TODO: we should be able to simplify this
 define i32 @test13noncanon(i32 %X) {
 ; CHECK-LABEL: @test13noncanon(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[X:%.*]], 4
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X]], 3
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[AND]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[COND]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 3
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %cmp = icmp uge i32 %X, 4
   %and = and i32 %X, 3
   %cond = select i1 %cmp, i32 %and, i32 %X
   ret i32 %cond
 }
 
 define i32 @select_icmp_and_8_eq_0_or_8(i32 %x) {