[InstCombine] Fold BW/2+1 tops bits are same pattern

[dmgreen]

Summary

Match icmp eq (trunc (lsr A, BW), (ashr (trunc A), BW-1)), which checks the top BW/2 + 1 bits are all the same. Create "A >=s INT_MIN && A <=s INT_MAX", which we generate as "icmp ult (add A, 2^BW-1), 2^BW" to skip a few steps of instcombining.
https://alive2.llvm.org/ce/z/NjH6Ty
https://alive2.llvm.org/ce/z/_fEQ9P

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4510

We don't need the commutative matcher (and the regression test shows this). That's because we always canonicalize the 'ashr' as op0 and 'trunc' as op1 based on getComplexity.

Actually, we don't need to rematch the icmp at all if we handle both predicates - see next comment.

4514

We should handle ICMP_NE for symmetry. Flip from ULT to UGE?
https://alive2.llvm.org/ce/z/_fEQ9P

[dmgreen]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4510

Oh that's good to hear. Yeah the only reason for starting the match at the ICmp was to get commutativity through the m_c_ICmp.

[dmgreen]

Remove commutative matchers, adding NE handling.

[foad]

"A >s INT_MIN && A <s INT_MAX"

>=s and <=s, in the commit message and the inline comment?

[dmgreen]

Yep, thanks. Update comment with = bounds.

[spatel]

The half-width truncate clause seems too restrictive. I assume we want to catch a case like this too:
https://alive2.llvm.org/ce/z/UAQ4yQ

[spatel]

In D109155#2982324, @spatel wrote:

The half-width truncate clause seems too restrictive. I assume we want to catch a case like this too:
https://alive2.llvm.org/ce/z/UAQ4yQ

Disregard that failed attempt at a proof. :)
Trying to find another example now...

[foad]

In D109155#2982324, @spatel wrote:

The half-width truncate clause seems too restrictive. I assume we want to catch a case like this too:
https://alive2.llvm.org/ce/z/UAQ4yQ

What does ashr i8 %t2, 25 do in that example? Surely it's poison?

[spatel]

In D109155#2982330, @foad wrote:

In D109155#2982324, @spatel wrote:

The half-width truncate clause seems too restrictive. I assume we want to catch a case like this too:
https://alive2.llvm.org/ce/z/UAQ4yQ

What does ashr i8 %t2, 25 do in that example? Surely it's poison?

Yes, that was all wrong. If we're not doing a half-width truncate, the bits aren't lined up consecutively, so it probably doesn't matter:
https://alive2.llvm.org/ce/z/YdoXeg

[dmgreen]

Yeah, that was what I thought about the now-half-width-cases. The maths doesn't work at as well, and they at least feel like a different case to me.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4503

lsr -> lshr

[lebedev.ri]

I agree that the double-the-bitwidth precondition is needed *for this pattern*, but there are other possible cases:
https://alive2.llvm.org/ce/z/RjUMzM (double)
https://alive2.llvm.org/ce/z/Jd3aHC (more than double => sext)
https://alive2.llvm.org/ce/z/CS2xkv (less than double => trunc)

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpEquality(ICmpInst &I) {
   if (A) {
     Type *Ty = A->getType();
     CallInst *CtPop = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, A);
     return Pred == ICmpInst::ICMP_EQ
         ? new ICmpInst(ICmpInst::ICMP_ULT, CtPop, ConstantInt::get(Ty, 2))
         : new ICmpInst(ICmpInst::ICMP_UGT, CtPop, ConstantInt::get(Ty, 1));
   }
 
+  // Match icmp eq (trunc (lsr A, BW), (ashr (trunc A), BW-1)), which checks the
+  // top BW/2 + 1 bits are all the same. Create "A >s INT_MIN && A <s INT_MAX",
+  // which we generate as "icmp ult (add A, 2^BW-1), 2^BW" to skip a few steps
+  // of instcombine.
+  unsigned BitWidth = I.getOperand(0)->getType()->getScalarSizeInBits();
+  CmpInst::Predicate TPred;
+  if (match(&I,
+            m_c_ICmp(
+                TPred, m_Trunc(m_LShr(m_Value(A), m_SpecificInt(BitWidth))),
+                m_AShr(m_Trunc(m_Deferred(A)), m_SpecificInt(BitWidth - 1)))) &&
+      A->getType()->getScalarSizeInBits() == BitWidth * 2 &&
+      TPred == ICmpInst::ICMP_EQ &&
+      (I.getOperand(0)->hasOneUse() || I.getOperand(1)->hasOneUse())) {
+    APInt C = APInt::getOneBitSet(BitWidth * 2, BitWidth - 1);
+    auto *Add = Builder.CreateAdd(A, ConstantInt::get(A->getType(), C));
+    return new ICmpInst(ICmpInst::ICMP_ULT, Add,
+                        ConstantInt::get(A->getType(), C.shl(1)));
+  }
+
   return nullptr;
 }
 
 static Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp,
                                            InstCombiner::BuilderTy &Builder) {
   assert(isa<CastInst>(ICmp.getOperand(0)) && "Expected cast for operand 0");
   auto *CastOp0 = cast<CastInst>(ICmp.getOperand(0));
   Value *X;

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 
 declare void @use(i8)
 declare void @use16(i16)
 
 define i1 @testi16i8(i16 %add) {
 ; CHECK-LABEL: @testi16i8(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i16 [[ADD:%.*]], 8
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i16 [[SH]] to i8
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD]] to i8
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i8 [[CONV1_I]], 7
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i8 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[ADD:%.*]], 128
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i16 [[TMP1]], 256
 ; CHECK-NEXT:    ret i1 [[CMP_NOT_I]]
 ;
   %sh = lshr i16 %add, 8
   %conv.i = trunc i16 %sh to i8
   %conv1.i = trunc i16 %add to i8
   %shr2.i = ashr i8 %conv1.i, 7
   %cmp.not.i = icmp eq i8 %shr2.i, %conv.i
   ret i1 %cmp.not.i
 }
 
 define i1 @testi16i8_com(i16 %add) {
 ; CHECK-LABEL: @testi16i8_com(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i16 [[ADD:%.*]], 8
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i16 [[SH]] to i8
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD]] to i8
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i8 [[CONV1_I]], 7
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i8 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[ADD:%.*]], 128
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i16 [[TMP1]], 256
 ; CHECK-NEXT:    ret i1 [[CMP_NOT_I]]
 ;
   %sh = lshr i16 %add, 8
   %conv.i = trunc i16 %sh to i8
   %conv1.i = trunc i16 %add to i8
   %shr2.i = ashr i8 %conv1.i, 7
   %cmp.not.i = icmp eq i8 %conv.i, %shr2.i
   ret i1 %cmp.not.i
 }
 
 define i1 @testi64i32(i64 %add) {
 ; CHECK-LABEL: @testi64i32(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i64 [[ADD:%.*]], 32
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i64 [[SH]] to i32
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD]] to i32
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i32 [[CONV1_I]], 31
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i32 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[ADD:%.*]], 2147483648
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i64 [[TMP1]], 4294967296
 ; CHECK-NEXT:    ret i1 [[CMP_NOT_I]]
 ;
   %sh = lshr i64 %add, 32
   %conv.i = trunc i64 %sh to i32
   %conv1.i = trunc i64 %add to i32
   %shr2.i = ashr i32 %conv1.i, 31
   %cmp.not.i = icmp eq i32 %shr2.i, %conv.i
   ret i1 %cmp.not.i
;
   %cmp.not.i = icmp eq i8 %shr2.i, %conv.i
   ret i1 %cmp.not.i
 }
 
 ; Use checks
 
 define i1 @extrause_a(i16 %add) {
 ; CHECK-LABEL: @extrause_a(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i16 [[ADD:%.*]], 8
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i16 [[SH]] to i8
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD]] to i8
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD:%.*]] to i8
 ; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i8 [[CONV1_I]], 7
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i8 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[ADD]], 128
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i16 [[TMP1]], 256
 ; CHECK-NEXT:    call void @use(i8 [[SHR2_I]])
 ; CHECK-NEXT:    ret i1 [[CMP_NOT_I]]
 ;
   %sh = lshr i16 %add, 8
   %conv.i = trunc i16 %sh to i8
   %conv1.i = trunc i16 %add to i8
   %shr2.i = ashr i8 %conv1.i, 7
   %cmp.not.i = icmp eq i8 %shr2.i, %conv.i
   call void @use(i8 %shr2.i)
   ret i1 %cmp.not.i
 }
 
 define i1 @extrause_l(i16 %add) {
 ; CHECK-LABEL: @extrause_l(
 ; CHECK-NEXT:    [[SH:%.*]] = lshr i16 [[ADD:%.*]], 8
 ; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i16 [[SH]] to i8
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD]] to i8
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i8 [[CONV1_I]], 7
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i8 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[ADD]], 128
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i16 [[TMP1]], 256
 ; CHECK-NEXT:    call void @use(i8 [[CONV_I]])
 ; CHECK-NEXT:    ret i1 [[CMP_NOT_I]]
 ;
   %sh = lshr i16 %add, 8
   %conv.i = trunc i16 %sh to i8
   %conv1.i = trunc i16 %add to i8
   %shr2.i = ashr i8 %conv1.i, 7
   %cmp.not.i = icmp eq i8 %shr2.i, %conv.i

llvm/test/Transforms/InstCombine/truncating-saturate.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 
 declare void @use(i32)
 declare void @use1(i1)
 
 define i8 @testi16i8(i16 %add) {
 ; CHECK-LABEL: @testi16i8(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i16 [[ADD:%.*]], 8
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i16 [[SH]] to i8
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD]] to i8
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i8 [[CONV1_I]], 7
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i8 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD:%.*]] to i8
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[ADD]], 128
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i16 [[TMP1]], 256
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i16 [[ADD]], 15
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i16 [[SHR4_I]] to i8
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i8 [[CONV5_I]], 127
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i8 [[CONV1_I]], i8 [[XOR_I]]
 ; CHECK-NEXT:    ret i8 [[COND_I]]
 ;
   %sh = lshr i16 %add, 8
   %conv.i = trunc i16 %sh to i8
   %conv1.i = trunc i16 %add to i8
   %shr2.i = ashr i8 %conv1.i, 7
   %cmp.not.i = icmp eq i8 %shr2.i, %conv.i
   %shr4.i = ashr i16 %add, 15
   %conv5.i = trunc i16 %shr4.i to i8
   %xor.i = xor i8 %conv5.i, 127
   %cond.i = select i1 %cmp.not.i, i8 %conv1.i, i8 %xor.i
   ret i8 %cond.i
 }
 
 define i32 @testi64i32(i64 %add) {
 ; CHECK-LABEL: @testi64i32(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i64 [[ADD:%.*]], 32
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i64 [[SH]] to i32
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD]] to i32
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i32 [[CONV1_I]], 31
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i32 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD:%.*]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[ADD]], 2147483648
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i64 [[TMP1]], 4294967296
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i64 [[ADD]], 63
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i64 [[SHR4_I]] to i32
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i32 [[CONV5_I]], 2147483647
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i32 [[CONV1_I]], i32 [[XOR_I]]
 ; CHECK-NEXT:    ret i32 [[COND_I]]
 ;
   %sh = lshr i64 %add, 32
   %conv.i = trunc i64 %sh to i32
   %conv1.i = trunc i64 %add to i32
   %shr2.i = ashr i32 %conv1.i, 31
   %cmp.not.i = icmp eq i32 %shr2.i, %conv.i
   %shr4.i = ashr i64 %add, 63
   %conv5.i = trunc i64 %shr4.i to i32
   %xor.i = xor i32 %conv5.i, 2147483647
   %cond.i = select i1 %cmp.not.i, i32 %conv1.i, i32 %xor.i
   ret i32 %cond.i
 }
 
 define i32 @testi64i32addsat(i32 %a, i32 %b) {
 ; CHECK-LABEL: @testi64i32addsat(
 ; CHECK-NEXT:    [[SA:%.*]] = sext i32 [[A:%.*]] to i64
 ; CHECK-NEXT:    [[SB:%.*]] = sext i32 [[B:%.*]] to i64
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[SA]], [[SB]]
-; CHECK-NEXT:    [[SH:%.*]] = lshr i64 [[ADD]], 32
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i64 [[SH]] to i32
 ; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD]] to i32
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i32 [[CONV1_I]], 31
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i32 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[ADD]], 2147483648
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i64 [[TMP1]], 4294967296
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i64 [[ADD]], 63
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i64 [[SHR4_I]] to i32
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i32 [[CONV5_I]], 2147483647
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i32 [[CONV1_I]], i32 [[XOR_I]]
 ; CHECK-NEXT:    ret i32 [[COND_I]]
 ;
   %sa = sext i32 %a to i64
   %sb = sext i32 %b to i64
   %add = add i64 %sa, %sb
   %sh = lshr i64 %add, 32
   %conv.i = trunc i64 %sh to i32
   %conv1.i = trunc i64 %add to i32
   %shr2.i = ashr i32 %conv1.i, 31
   %cmp.not.i = icmp eq i32 %shr2.i, %conv.i
   %shr4.i = ashr i64 %add, 63
   %conv5.i = trunc i64 %shr4.i to i32
   %xor.i = xor i32 %conv5.i, 2147483647
   %cond.i = select i1 %cmp.not.i, i32 %conv1.i, i32 %xor.i
   ret i32 %cond.i
 }
 
 define <4 x i8> @testv4i16i8(<4 x i16> %add) {
 ; CHECK-LABEL: @testv4i16i8(
-; CHECK-NEXT:    [[SH:%.*]] = lshr <4 x i16> [[ADD:%.*]], <i16 8, i16 8, i16 8, i16 8>
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc <4 x i16> [[SH]] to <4 x i8>
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc <4 x i16> [[ADD]] to <4 x i8>
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr <4 x i8> [[CONV1_I]], <i8 7, i8 7, i8 7, i8 7>
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq <4 x i8> [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc <4 x i16> [[ADD:%.*]] to <4 x i8>
+; CHECK-NEXT:    [[TMP1:%.*]] = add <4 x i16> [[ADD]], <i16 128, i16 128, i16 128, i16 128>
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult <4 x i16> [[TMP1]], <i16 256, i16 256, i16 256, i16 256>
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr <4 x i16> [[ADD]], <i16 15, i16 15, i16 15, i16 15>
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc <4 x i16> [[SHR4_I]] to <4 x i8>
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor <4 x i8> [[CONV5_I]], <i8 127, i8 127, i8 127, i8 127>
 ; CHECK-NEXT:    [[COND_I:%.*]] = select <4 x i1> [[CMP_NOT_I]], <4 x i8> [[CONV1_I]], <4 x i8> [[XOR_I]]
 ; CHECK-NEXT:    ret <4 x i8> [[COND_I]]
 ;
   %sh = lshr <4 x i16> %add, <i16 8, i16 8, i16 8, i16 8>
   %conv.i = trunc <4 x i16> %sh to <4 x i8>
   %conv1.i = trunc <4 x i16> %add to <4 x i8>
   %shr2.i = ashr <4 x i8> %conv1.i, <i8 7, i8 7, i8 7, i8 7>
   %cmp.not.i = icmp eq <4 x i8> %shr2.i, %conv.i
   %shr4.i = ashr <4 x i16> %add, <i16 15, i16 15, i16 15, i16 15>
   %conv5.i = trunc <4 x i16> %shr4.i to <4 x i8>
   %xor.i = xor <4 x i8> %conv5.i, <i8 127, i8 127, i8 127, i8 127>
   %cond.i = select <4 x i1> %cmp.not.i, <4 x i8> %conv1.i, <4 x i8> %xor.i
   ret <4 x i8> %cond.i
 }
 
 define <4 x i8> @testv4i16i8add(<4 x i8> %a, <4 x i8> %b) {
 ; CHECK-LABEL: @testv4i16i8add(
 ; CHECK-NEXT:    [[SA:%.*]] = sext <4 x i8> [[A:%.*]] to <4 x i16>
 ; CHECK-NEXT:    [[SB:%.*]] = sext <4 x i8> [[B:%.*]] to <4 x i16>
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw <4 x i16> [[SA]], [[SB]]
-; CHECK-NEXT:    [[SH:%.*]] = lshr <4 x i16> [[ADD]], <i16 8, i16 8, i16 8, i16 8>
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc <4 x i16> [[SH]] to <4 x i8>
 ; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc <4 x i16> [[ADD]] to <4 x i8>
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr <4 x i8> [[CONV1_I]], <i8 7, i8 7, i8 7, i8 7>
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq <4 x i8> [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw <4 x i16> [[ADD]], <i16 128, i16 128, i16 128, i16 128>
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult <4 x i16> [[TMP1]], <i16 256, i16 256, i16 256, i16 256>
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr <4 x i16> [[ADD]], <i16 15, i16 15, i16 15, i16 15>
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc <4 x i16> [[SHR4_I]] to <4 x i8>
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor <4 x i8> [[CONV5_I]], <i8 127, i8 127, i8 127, i8 127>
 ; CHECK-NEXT:    [[COND_I:%.*]] = select <4 x i1> [[CMP_NOT_I]], <4 x i8> [[CONV1_I]], <4 x i8> [[XOR_I]]
 ; CHECK-NEXT:    ret <4 x i8> [[COND_I]]
 ;
   %sa = sext <4 x i8> %a to <4 x i16>
   %sb = sext <4 x i8> %b to <4 x i16>
   %add = add <4 x i16> %sa, %sb
   %sh = lshr <4 x i16> %add, <i16 8, i16 8, i16 8, i16 8>
   %conv.i = trunc <4 x i16> %sh to <4 x i8>
   %conv1.i = trunc <4 x i16> %add to <4 x i8>
   %shr2.i = ashr <4 x i8> %conv1.i, <i8 7, i8 7, i8 7, i8 7>
   %cmp.not.i = icmp eq <4 x i8> %shr2.i, %conv.i
   %shr4.i = ashr <4 x i16> %add, <i16 15, i16 15, i16 15, i16 15>
   %conv5.i = trunc <4 x i16> %shr4.i to <4 x i8>
   %xor.i = xor <4 x i8> %conv5.i, <i8 127, i8 127, i8 127, i8 127>
   %cond.i = select <4 x i1> %cmp.not.i, <4 x i8> %conv1.i, <4 x i8> %xor.i
   ret <4 x i8> %cond.i
 }
 
 define i8 @testi16i8_revcmp(i16 %add) {
 ; CHECK-LABEL: @testi16i8_revcmp(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i16 [[ADD:%.*]], 8
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i16 [[SH]] to i8
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD]] to i8
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i8 [[CONV1_I]], 7
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i8 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD:%.*]] to i8
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[ADD]], 128
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i16 [[TMP1]], 256
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i16 [[ADD]], 15
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i16 [[SHR4_I]] to i8
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i8 [[CONV5_I]], 127
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i8 [[CONV1_I]], i8 [[XOR_I]]
 ; CHECK-NEXT:    ret i8 [[COND_I]]
 ;
   %sh = lshr i16 %add, 8
   %conv.i = trunc i16 %sh to i8
   %conv1.i = trunc i16 %add to i8
   %shr2.i = ashr i8 %conv1.i, 7
   %cmp.not.i = icmp eq i8 %conv.i, %shr2.i
   %shr4.i = ashr i16 %add, 15
   %conv5.i = trunc i16 %shr4.i to i8
   %xor.i = xor i8 %conv5.i, 127
   %cond.i = select i1 %cmp.not.i, i8 %conv1.i, i8 %xor.i
   ret i8 %cond.i
 }
 
 define i8 @testi16i8_revselect(i16 %add) {
 ; CHECK-LABEL: @testi16i8_revselect(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i16 [[ADD:%.*]], 8
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i16 [[SH]] to i8
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD]] to i8
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i8 [[CONV1_I]], 7
-; CHECK-NEXT:    [[CMP_NOT_I_NOT:%.*]] = icmp eq i8 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD:%.*]] to i8
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[ADD]], 128
+; CHECK-NEXT:    [[CMP_NOT_I_NOT:%.*]] = icmp ult i16 [[TMP1]], 256
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i16 [[ADD]], 15
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i16 [[SHR4_I]] to i8
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i8 [[CONV5_I]], 127
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I_NOT]], i8 [[CONV1_I]], i8 [[XOR_I]]
 ; CHECK-NEXT:    ret i8 [[COND_I]]
 ;
   %sh = lshr i16 %add, 8
   %conv.i = trunc i16 %sh to i8
;
   %conv5.i = trunc i16 %shr4.i to i8
   %xor.i = xor i8 %conv5.i, 127
   %cond.i = select i1 %cmp.not.i, i8 %conv1.i, i8 %xor.i
   ret i8 %cond.i
 }
 
 define i8 @badimm3(i16 %add) {
 ; CHECK-LABEL: @badimm3(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i16 [[ADD:%.*]], 8
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i16 [[SH]] to i8
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD]] to i8
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i8 [[CONV1_I]], 7
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i8 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD:%.*]] to i8
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[ADD]], 128
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i16 [[TMP1]], 256
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i16 [[ADD]], 14
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i16 [[SHR4_I]] to i8
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i8 [[CONV5_I]], 127
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i8 [[CONV1_I]], i8 [[XOR_I]]
 ; CHECK-NEXT:    ret i8 [[COND_I]]
 ;
   %sh = lshr i16 %add, 8
   %conv.i = trunc i16 %sh to i8
   %conv1.i = trunc i16 %add to i8
   %shr2.i = ashr i8 %conv1.i, 7
   %cmp.not.i = icmp eq i8 %shr2.i, %conv.i
   %shr4.i = ashr i16 %add, 14
   %conv5.i = trunc i16 %shr4.i to i8
   %xor.i = xor i8 %conv5.i, 127
   %cond.i = select i1 %cmp.not.i, i8 %conv1.i, i8 %xor.i
   ret i8 %cond.i
 }
 
 define i8 @badimm4(i16 %add) {
 ; CHECK-LABEL: @badimm4(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i16 [[ADD:%.*]], 8
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i16 [[SH]] to i8
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD]] to i8
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i8 [[CONV1_I]], 7
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i8 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i16 [[ADD:%.*]] to i8
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[ADD]], 128
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i16 [[TMP1]], 256
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i16 [[ADD]], 15
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i16 [[SHR4_I]] to i8
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i8 [[CONV5_I]], 126
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i8 [[CONV1_I]], i8 [[XOR_I]]
 ; CHECK-NEXT:    ret i8 [[COND_I]]
 ;
   %sh = lshr i16 %add, 8
   %conv.i = trunc i16 %sh to i8
   %conv1.i = trunc i16 %add to i8
   %shr2.i = ashr i8 %conv1.i, 7
   %cmp.not.i = icmp eq i8 %shr2.i, %conv.i
   %shr4.i = ashr i16 %add, 15
   %conv5.i = trunc i16 %shr4.i to i8
   %xor.i = xor i8 %conv5.i, 126
   %cond.i = select i1 %cmp.not.i, i8 %conv1.i, i8 %xor.i
   ret i8 %cond.i
 }
 
 ; One use checks
 
 define i32 @oneusexor(i64 %add) {
 ; CHECK-LABEL: @oneusexor(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i64 [[ADD:%.*]], 32
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i64 [[SH]] to i32
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD]] to i32
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i32 [[CONV1_I]], 31
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i32 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD:%.*]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[ADD]], 2147483648
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i64 [[TMP1]], 4294967296
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i64 [[ADD]], 63
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i64 [[SHR4_I]] to i32
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i32 [[CONV5_I]], 2147483647
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i32 [[CONV1_I]], i32 [[XOR_I]]
 ; CHECK-NEXT:    call void @use(i32 [[XOR_I]])
 ; CHECK-NEXT:    ret i32 [[COND_I]]
 ;
   %sh = lshr i64 %add, 32
   %conv.i = trunc i64 %sh to i32
   %conv1.i = trunc i64 %add to i32
   %shr2.i = ashr i32 %conv1.i, 31
   %cmp.not.i = icmp eq i32 %shr2.i, %conv.i
   %shr4.i = ashr i64 %add, 63
   %conv5.i = trunc i64 %shr4.i to i32
   %xor.i = xor i32 %conv5.i, 2147483647
   %cond.i = select i1 %cmp.not.i, i32 %conv1.i, i32 %xor.i
   call void @use(i32 %xor.i)
   ret i32 %cond.i
 }
 
 define i32 @oneuseconv(i64 %add) {
 ; CHECK-LABEL: @oneuseconv(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i64 [[ADD:%.*]], 32
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i64 [[SH]] to i32
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD]] to i32
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i32 [[CONV1_I]], 31
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i32 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD:%.*]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[ADD]], 2147483648
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i64 [[TMP1]], 4294967296
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i64 [[ADD]], 63
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i64 [[SHR4_I]] to i32
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i32 [[CONV5_I]], 2147483647
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i32 [[CONV1_I]], i32 [[XOR_I]]
 ; CHECK-NEXT:    call void @use(i32 [[CONV1_I]])
 ; CHECK-NEXT:    ret i32 [[COND_I]]
 ;
   %sh = lshr i64 %add, 32
   %conv.i = trunc i64 %sh to i32
   %conv1.i = trunc i64 %add to i32
   %shr2.i = ashr i32 %conv1.i, 31
   %cmp.not.i = icmp eq i32 %shr2.i, %conv.i
   %shr4.i = ashr i64 %add, 63
   %conv5.i = trunc i64 %shr4.i to i32
   %xor.i = xor i32 %conv5.i, 2147483647
   %cond.i = select i1 %cmp.not.i, i32 %conv1.i, i32 %xor.i
   call void @use(i32 %conv1.i)
   ret i32 %cond.i
 }
 
 define i32 @oneusecmp(i64 %add) {
 ; CHECK-LABEL: @oneusecmp(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i64 [[ADD:%.*]], 32
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i64 [[SH]] to i32
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD]] to i32
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i32 [[CONV1_I]], 31
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i32 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD:%.*]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[ADD]], 2147483648
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i64 [[TMP1]], 4294967296
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i64 [[ADD]], 63
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i64 [[SHR4_I]] to i32
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i32 [[CONV5_I]], 2147483647
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i32 [[CONV1_I]], i32 [[XOR_I]]
 ; CHECK-NEXT:    call void @use1(i1 [[CMP_NOT_I]])
 ; CHECK-NEXT:    ret i32 [[COND_I]]
 ;
   %sh = lshr i64 %add, 32
   %conv.i = trunc i64 %sh to i32
   %conv1.i = trunc i64 %add to i32
   %shr2.i = ashr i32 %conv1.i, 31
   %cmp.not.i = icmp eq i32 %shr2.i, %conv.i
   %shr4.i = ashr i64 %add, 63
   %conv5.i = trunc i64 %shr4.i to i32
   %xor.i = xor i32 %conv5.i, 2147483647
   %cond.i = select i1 %cmp.not.i, i32 %conv1.i, i32 %xor.i
   call void @use1(i1 %cmp.not.i)
   ret i32 %cond.i
 }
 
 define i32 @oneuseboth(i64 %add) {
 ; CHECK-LABEL: @oneuseboth(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i64 [[ADD:%.*]], 32
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i64 [[SH]] to i32
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD]] to i32
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i32 [[CONV1_I]], 31
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i32 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD:%.*]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[ADD]], 2147483648
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i64 [[TMP1]], 4294967296
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i64 [[ADD]], 63
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i64 [[SHR4_I]] to i32
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i32 [[CONV5_I]], 2147483647
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i32 [[CONV1_I]], i32 [[XOR_I]]
 ; CHECK-NEXT:    call void @use(i32 [[XOR_I]])
 ; CHECK-NEXT:    call void @use(i32 [[CONV1_I]])
 ; CHECK-NEXT:    ret i32 [[COND_I]]
 ;
   %sh = lshr i64 %add, 32
   %conv.i = trunc i64 %sh to i32
   %conv1.i = trunc i64 %add to i32
   %shr2.i = ashr i32 %conv1.i, 31
   %cmp.not.i = icmp eq i32 %shr2.i, %conv.i
   %shr4.i = ashr i64 %add, 63
   %conv5.i = trunc i64 %shr4.i to i32
   %xor.i = xor i32 %conv5.i, 2147483647
   %cond.i = select i1 %cmp.not.i, i32 %conv1.i, i32 %xor.i
   call void @use(i32 %xor.i)
   call void @use(i32 %conv1.i)
   ret i32 %cond.i
 }
 
 define i32 @oneusethree(i64 %add) {
 ; CHECK-LABEL: @oneusethree(
-; CHECK-NEXT:    [[SH:%.*]] = lshr i64 [[ADD:%.*]], 32
-; CHECK-NEXT:    [[CONV_I:%.*]] = trunc i64 [[SH]] to i32
-; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD]] to i32
-; CHECK-NEXT:    [[SHR2_I:%.*]] = ashr i32 [[CONV1_I]], 31
-; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp eq i32 [[SHR2_I]], [[CONV_I]]
+; CHECK-NEXT:    [[CONV1_I:%.*]] = trunc i64 [[ADD:%.*]] to i32
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[ADD]], 2147483648
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i64 [[TMP1]], 4294967296
 ; CHECK-NEXT:    [[SHR4_I:%.*]] = ashr i64 [[ADD]], 63
 ; CHECK-NEXT:    [[CONV5_I:%.*]] = trunc i64 [[SHR4_I]] to i32
 ; CHECK-NEXT:    [[XOR_I:%.*]] = xor i32 [[CONV5_I]], 2147483647
 ; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[CMP_NOT_I]], i32 [[CONV1_I]], i32 [[XOR_I]]
 ; CHECK-NEXT:    call void @use(i32 [[XOR_I]])
 ; CHECK-NEXT:    call void @use(i32 [[CONV1_I]])
 ; CHECK-NEXT:    call void @use1(i1 [[CMP_NOT_I]])
 ; CHECK-NEXT:    ret i32 [[COND_I]]