[InstCombine] reduce icmp(ashr X, C1), C2 to sign-bit test

[spatel]

Summary

This is a more basic pattern that we should handle before trying to solve:
https://llvm.org/PR48640

There might be a better way to think about this because the pre-condition that I came up with (number of sign bits in the compare constant) misses a potential transform for each of ugt and ult as commented on in the test file.

Tried to model this is in Alive:
https://rise4fun.com/Alive/juX1
...but I couldn't get the ComputeNumSignBits() pre-condition to work as expected, so replaced with leading 0/1 preconditions instead.

Name: ugt
Pre: countLeadingZeros(C2) <= C1 && countLeadingOnes(C2) <= C1
%a = ashr %x, C1
%r = icmp ugt i8 %a, C2
  =>
%r = icmp slt i8 %x, 0

Name: ult
Pre: countLeadingZeros(C2) <= C1 && countLeadingOnes(C2) <= C1
%a = ashr %x, C1
%r = icmp ult i4 %a, C2
  => 
%r = icmp sgt i4 %x, -1

[lebedev.ri]

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

512

It's a : (colon), not a ; (semicolon), does this test parse?

[spatel]

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

512

Oops - I pasted in the test comments after running ninja check, so missed the typo.

[spatel]

Patch updated:
Fixed semi-colon typos in test comments.

[spatel]

Ping.
Note: I added a bitwidth > 2 constraint to be safe and avoid degenerate narrow bit patterns, but I'm not sure how to write negative tests for that would actually survive to this point in instcombine (instsimplify appears to reduce those first).

[lebedev.ri]

Sorry for the delay.

alive1 does not actually have a countLeadingOnes() precondition
(at least as per https://github.com/nunoplopes/alive/blob/master/constants.py),
so the proof is faulty. ComputeNumSignBits(), OTOH, works for me:

$ cat /tmp/test.ll
Name: lshr ugt
Pre: ComputeNumSignBits(C2) <= C1
%a = lshr i8 %x, C1
%r = icmp ugt i8 %a, C2
  =>
%r = icmp slt i8 %x, 0

Name: lshr ult
Pre: ComputeNumSignBits(C2) <= C1
%a = lshr i8 %x, C1
%r = icmp ult i8 %a, C2
  =>
%r = icmp sgt i8 %x, -1

Name: ashr ugt
Pre: ComputeNumSignBits(C2) <= C1
%a = ashr i8 %x, C1
%r = icmp ugt i8 %a, C2
  =>
%r = icmp slt i8 %x, 0

Name: ashr ult
Pre: ComputeNumSignBits(C2) <= C1
%a = ashr i8 %x, C1
%r = icmp ult i8 %a, C2
  =>
%r = icmp sgt i8 %x, -1

$ /repositories/alive/alive.py /tmp/test.ll 
----------------------------------------
Optimization: lshr ugt
Precondition: (ComputeNumSignBits(C2) <= C1)
  %a = lshr i8 %x, C1
  %r = icmp ugt i8 %a, C2
=>
  %r = icmp slt i8 %x, 0


ERROR: Mismatch in values of i1 %r

Example:
%x i8 = 0x80 (128, -128)
C1 i8 = 0x07 (7)
C2 i8 = 0xD0 (208, -48)
%a i8 = 0x01 (1)
Source value: 0x0 (0)
Target value: 0x1 (1, -1)

Am i holding it wrong, or is this missing some preconditions?

[spatel]

In D94014#2490113, @lebedev.ri wrote:

alive1 does not actually have a countLeadingOnes() precondition

Weird - maybe @nlopes can tell us how this example parses at all then: https://rise4fun.com/Alive/juX1

(at least as per https://github.com/nunoplopes/alive/blob/master/constants.py),
so the proof is faulty. ComputeNumSignBits(), OTOH, works for me:

...

Am i holding it wrong, or is this missing some preconditions?

Your example has lshr, but we only want to check ashr here, right?

Take a look at this one:
https://rise4fun.com/Alive/o8vS

ERROR: Mismatch in values of i1 %r

Example:
%x i8 = 0x80 (128, -128)
C1 i8 = 0x04 (4)
C2 i8 = 0xFA (250, -6)
%a i8 = 0xF8 (248, -8)
Source value: 0x0 (0)
Target value: 0x1 (1, -1)

This failure does not correspond to the pre-condition, does it? The number of signbits in C2 == 0xFA is 5, and 5 <= 4 is not true.

[nlopes]

In D94014#2490258, @spatel wrote:

In D94014#2490113, @lebedev.ri wrote:

alive1 does not actually have a countLeadingOnes() precondition

Weird - maybe @nlopes can tell us how this example parses at all then: https://rise4fun.com/Alive/juX1

(at least as per https://github.com/nunoplopes/alive/blob/master/constants.py),

Ah, the rise4fun.com version uses the newsema branch. countLeadingOnes seems to be implemented in newsema but not in master.
(the newsema has better support for undef & poison, which wasn't complete in the original/master version. I don't remember why this branch wasn't merged, but I think it broke some functionality)

[spatel]

Anyone see problems with this Alive2 implementation using count-leading-*?
https://alive2.llvm.org/ce/z/SWxadd

I also manually entered all of the i4 regression tests with fixed constants in Alive1 (rise4fun), and they appear to be correct as shown in the test diffs.

[lebedev.ri]

LGTM

In D94014#2490334, @spatel wrote:

Anyone see problems with this Alive2 implementation using count-leading-*?
https://alive2.llvm.org/ce/z/SWxadd

I also manually entered all of the i4 regression tests with fixed constants in Alive1 (rise4fun), and they appear to be correct as shown in the test diffs.

https://alive2.llvm.org/ce/z/u5hCcz

[nlopes]

In D94014#2490334, @spatel wrote:

Anyone see problems with this Alive2 implementation using count-leading-*?
https://alive2.llvm.org/ce/z/SWxadd

I also manually entered all of the i4 regression tests with fixed constants in Alive1 (rise4fun), and they appear to be correct as shown in the test diffs.

That's a clever way!
Another way is to use assume to encode the precondition if you prefer: https://alive2.llvm.org/ce/z/__szVL

[spatel]

In D94014#2490458, @nlopes wrote:

Another way is to use assume to encode the precondition if you prefer: https://alive2.llvm.org/ce/z/__szVL

In D94014#2490431, @lebedev.ri wrote:

https://alive2.llvm.org/ce/z/u5hCcz

Thanks for the improved examples! It would be great if we collected things like that to use as reference/documentation (maybe there's already a folder, but I just don't know about it?).

[lebedev.ri]

In D94014#2490627, @spatel wrote:

In D94014#2490458, @nlopes wrote:

Another way is to use assume to encode the precondition if you prefer: https://alive2.llvm.org/ce/z/__szVL

In D94014#2490431, @lebedev.ri wrote:

https://alive2.llvm.org/ce/z/u5hCcz

Thanks for the improved examples!

It would be great if we collected things like that to use as reference/documentation

Yes

(maybe there's already a folder, but I just don't know about it?).

Not that i know of, which means it [effectively] doesn't exist.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (IsAShr) {
     }
     if (Pred == CmpInst::ICMP_SGT) {
       // icmp sgt (ashr X, ShAmtC), C --> icmp sgt X, ((C + 1) << ShAmtC) - 1
       APInt ShiftedC = (C + 1).shl(ShAmtVal) - 1;
       if (!C.isMaxSignedValue() && !(C + 1).shl(ShAmtVal).isMinSignedValue() &&
           (ShiftedC + 1).ashr(ShAmtVal) == (C + 1))
         return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
     }
+
+    // If the compare constant has significant bits above the lowest sign-bit,
+    // then convert an unsigned cmp to a test of the sign-bit:
+    // (ashr X, ShiftC) u> C --> X s< 0
+    // (ashr X, ShiftC) u< C --> X s> -1
+    if (C.getBitWidth() > 2 && C.getNumSignBits() <= ShAmtVal) {
+      if (Pred == CmpInst::ICMP_UGT) {
+        return new ICmpInst(CmpInst::ICMP_SLT, X,
+                            ConstantInt::getNullValue(ShrTy));
+      }
+      if (Pred == CmpInst::ICMP_ULT) {
+        return new ICmpInst(CmpInst::ICMP_SGT, X,
+                            ConstantInt::getAllOnesValue(ShrTy));
+      }
+    }
   } else {
     if (Pred == CmpInst::ICMP_ULT || (Pred == CmpInst::ICMP_UGT && IsExact)) {
       // icmp ult (lshr X, ShAmtC), C --> icmp ult X, (C << ShAmtC)
       // icmp ugt (lshr exact X, ShAmtC), C --> icmp ugt X, (C << ShAmtC)
       APInt ShiftedC = C.shl(ShAmtVal);
       if (ShiftedC.lshr(ShAmtVal) == C)
         return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
     }

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

 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %sh = ashr exact <2 x i32> %x, %y
   %cmp = icmp eq <2 x i32> %sh, zeroinitializer
   call void @foo2(<2 x i32> %sh)
   ret <2 x i1> %cmp
 }
 
+; Verify conversions of ashr+icmp to a sign-bit test.
+
+; negative test, but different transform possible
+
 define i1 @ashr_ugt_0(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_0(
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[X:%.*]], 1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 0 ; 0b0000
   ret i1 %r
 }
 
+; negative test
+
 define i1 @ashr_ugt_1(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_1(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], 1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 1 ; 0b0001
   ret i1 %r
 }
 
+; negative test
+
 define i1 @ashr_ugt_2(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_2(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], 2
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 2 ; 0b0010
   ret i1 %r
 }
 
+; negative test
+; TODO: This is a sign-bit test, but we don't recognize the pattern.
+
 define i1 @ashr_ugt_3(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_3(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], 3
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 3 ; 0b0011
   ret i1 %r
 }
 
 define i1 @ashr_ugt_4(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_4(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], 4
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 4 ; 0b0100
   ret i1 %r
 }
 
 define i1 @ashr_ugt_5(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_5(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], 5
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 5 ; 0b0101
   ret i1 %r
 }
 
 define i1 @ashr_ugt_6(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_6(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], 6
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 6 ; 0b0110
   ret i1 %r
 }
 
 define i1 @ashr_ugt_7(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_7(
 ; CHECK-NEXT:    [[R:%.*]] = icmp slt i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 7 ; 0b0111
   ret i1 %r
 }
 
 define i1 @ashr_ugt_8(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_8(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], -8
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 8 ; 0b1000
   ret i1 %r
 }
 
 define i1 @ashr_ugt_9(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_9(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], -7
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 9 ; 0b1001
   ret i1 %r
 }
 
 define i1 @ashr_ugt_10(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_10(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], -6
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 10 ; 0b1010
   ret i1 %r
 }
 
 define i1 @ashr_ugt_11(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_11(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], -5
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 11 ; 0b1011
   ret i1 %r
 }
 
+; negative test
+
 define i1 @ashr_ugt_12(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_12(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], -4
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 12 ; 0b1100
   ret i1 %r
 }
 
+; negative test
+
 define i1 @ashr_ugt_13(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_13(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], -3
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 13 ; 0b1101
   ret i1 %r
 }
 
+; negative test, but different transform possible
+
 define i1 @ashr_ugt_14(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_14(
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[X:%.*]], -3
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 14 ; 0b1110
   ret i1 %r
 }
 
+; negative test, but simplifies
+
 define i1 @ashr_ugt_15(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_15(
 ; CHECK-NEXT:    ret i1 false
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 15 ; 0b1111
   ret i1 %r
 }
 
+; negative test, but simplifies
+
 define i1 @ashr_ult_0(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_0(
 ; CHECK-NEXT:    ret i1 false
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 0 ; 0b0000
   ret i1 %r
 }
 
+; negative test, but different transform possible
+
 define i1 @ashr_ult_1(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_1(
 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[X:%.*]], 2
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 1 ; 0b0001
   ret i1 %r
 }
 
+; negative test
+
 define i1 @ashr_ult_2(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_2(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], 2
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 2 ; 0b0010
   ret i1 %r
 }
 
+; negative test
+
 define i1 @ashr_ult_3(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_3(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], 3
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 3 ; 0b0011
   ret i1 %r
 }
 
 define i1 @ashr_ult_4(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_4(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], 4
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 4 ; 0b0100
   ret i1 %r
 }
 
 define i1 @ashr_ult_5(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_5(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], 5
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 5 ; 0b0101
   ret i1 %r
 }
 
 define i1 @ashr_ult_6(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_6(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], 6
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 6 ; 0b0110
   ret i1 %r
 }
 
 define i1 @ashr_ult_7(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_7(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], 7
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 7 ; 0b0111
   ret i1 %r
 }
 
 define i1 @ashr_ult_8(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_8(
 ; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 8 ; 0b1000
   ret i1 %r
 }
 
 define i1 @ashr_ult_9(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_9(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], -7
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 9 ; 0b1001
   ret i1 %r
 }
 
 define i1 @ashr_ult_10(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_10(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], -6
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 10 ; 0b1010
   ret i1 %r
 }
 
 define i1 @ashr_ult_11(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_11(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], -5
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 11 ; 0b1011
   ret i1 %r
 }
 
+; negative test
+; TODO: This is a sign-bit test, but we don't recognize the pattern.
+
 define i1 @ashr_ult_12(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_12(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], -4
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 12 ; 0b1100
   ret i1 %r
 }
 
+; negative test
+
 define i1 @ashr_ult_13(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_13(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], -3
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 13 ; 0b1101
   ret i1 %r
 }
 
+; negative test
+
 define i1 @ashr_ult_14(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_14(
 ; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[S]], -2
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 14 ; 0b1110
   ret i1 %r
 }
 
+; negative test, but different transform possible
+
 define i1 @ashr_ult_15(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_15(
 ; CHECK-NEXT:    [[R:%.*]] = icmp ult i4 [[X:%.*]], -2
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 15 ; 0b1111
   ret i1 %r
 }