[InstCombine] Fold x & (-1 >> y) == x to x u<= (-1 >> y)

[lebedev.ri]

Summary

https://bugs.llvm.org/show_bug.cgi?id=38123

This pattern will be produced by Implicit Integer Truncation sanitizer,
https://reviews.llvm.org/D48958
https://bugs.llvm.org/show_bug.cgi?id=21530
in unsigned case, therefore it is probably a good idea to improve it.

https://rise4fun.com/Alive/Rny
^ there are more opportunities for folds, i will follow up with them afterwards.

Caveat: this somehow exposes a missing opportunities
in test/Transforms/InstCombine/icmp-logical.ll
It seems, the problem is in foldLogOpOfMaskedICmps() in InstCombineAndOrXor.cpp.
But i'm not quite sure what is wrong, because it calls getMaskedTypeForICmpPair(),
which calls decomposeBitTestICmp() which should already work for these cases...
I would love to have some pointers on how to address it.

[lebedev.ri]

test/Transforms/InstCombine/canonicalize-low-bit-mask-and-icmp-eq-to-icmp-ule.ll

17–19

To spare time, yes, this is correct, https://rise4fun.com/Alive/J71

[lebedev.ri]

test/Transforms/InstCombine/icmp-mul-zext.ll

14–15

This too, https://rise4fun.com/Alive/twl2, note that br inverted, too.

[spatel]

I'm not too worried about the missing fold in foldLogOpOfMaskedICmps(). That's a complex mess, so not surprising that it has logic holes. I've wondered if we could rewrite that using ranges to simplify that code.

lib/Transforms/InstCombine/InstCombineCompares.cpp

4447–4449

We're also missing signed folds like:

Pre: isPowerOf2(C1+1)
%masked = and i32 %arg, C1
%truncheck = icmp sge i32 %masked, %arg
  =>
%truncheck = icmp sle i32 %arg, C1

https://rise4fun.com/Alive/K8H

...so I'd give this function a more general name: foldICmpWithMaskedVal?

4452–4458

Untested, but this could be less indent-crazy if we give some of it a local name like:

auto m_Mask = m_CombineOr(m_LShr(m_AllOnes(), m_Value()), m_LowBitMask());
if (!match(&I, m_c_ICmp(SrcPred,
                        m_c_And(m_CombineAnd(m_Mask, m_Value(M)), m_Value(X)),
                        m_Deferred(X))))

4462

I think you're planning to extend this soon, but it's best to leave a TODO comment with an explanation just in case that gets delayed.

4659–4660

There's no logic to fold ordering within visitICmpInst()...the new function could be called from within foldICmpBinOp() rather than the top-level?

[lebedev.ri]

Address @spatel's review notes.

In D49179#1158760, @spatel wrote:

I'm not too worried about the missing fold in foldLogOpOfMaskedICmps(). That's a complex mess, so not surprising that it has logic holes. I've wondered if we could rewrite that using ranges to simplify that code.

That's, relieving to know!
I have looked a bit more, and i'm not sure what goes wrong,
so one regression can slip, that'd be great.

lib/Transforms/InstCombine/InstCombineCompares.cpp

4447–4449

Yep, i didn't like that long name anyway.

4452–4458

Ha, nice one.

4659–4660

Hm, good idea.

[spatel]

LGTM.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2873

Nit: make the formula up here more general and then put the specific formulas within the 'switch'.

[lebedev.ri]

In D49179#1158930, @spatel wrote:

LGTM.

Thank you for such speedy review!

I'm wondering, what about the signed case?
https://godbolt.org/g/WvWX13
https://godbolt.org/g/DM7XA4
https://rise4fun.com/Alive/Qslx (check that 25 high bits are either all-ones, or all-zeros)

Can we do this in instcombine?
Or not, given that we were disabling some bit-fiddling transforms lately?

[lebedev.ri]

In D49179#1158957, @lebedev.ri wrote:

In D49179#1158930, @spatel wrote:

LGTM.

Thank you for such speedy review!

I'm wondering, what about the signed case?
https://godbolt.org/g/WvWX13
https://godbolt.org/g/DM7XA4
https://rise4fun.com/Alive/Qslx (check that 25 high bits are either all-ones, or all-zeros)

Can we do this in instcombine?
Or not, given that we were disabling some bit-fiddling transforms lately?

Actually, not sure that is any better, will leave that for now.
Though the reverse transform might be a good thing for dagcombine.

[spatel]

In D49179#1159024, @lebedev.ri wrote:

In D49179#1158957, @lebedev.ri wrote:

In D49179#1158930, @spatel wrote:

LGTM.

Thank you for such speedy review!

I'm wondering, what about the signed case?
https://godbolt.org/g/WvWX13
https://godbolt.org/g/DM7XA4
https://rise4fun.com/Alive/Qslx (check that 25 high bits are either all-ones, or all-zeros)

Can we do this in instcombine?
Or not, given that we were disabling some bit-fiddling transforms lately?

Actually, not sure that is any better, will leave that for now.
Though the reverse transform might be a good thing for dagcombine.

It's a good question, but probably better asked on the dev list than here. I think we prefer to canonicalize to the form with less instructions even if that means we lose information from the eliminated ops.

[hjyamauchi]

llvm/trunk/test/Transforms/InstCombine/icmp-logical.ll

91 ↗

(On Diff #155042)

It seems like the simplification of this change (D49179) triggers before this original simplification triggers and the original simplification no longer triggers? My guess is that this test just means to test a plain or-case and it may make sense to use some other values like 14 and 78 (shifted left by 1 bit, instead of 7 and 39) and preserve the original intention of the test.

Note the next test @masked_or_A_slightly_optimized has the same code as the after-simplification code of this function. Not sure if it is a just a coincidence.

[lebedev.ri]

llvm/trunk/test/Transforms/InstCombine/icmp-logical.ll

91 ↗

(On Diff #155042)

and the original simplification no longer triggers?

In any case, the original simplification clearly does not handle this pattern.

My guess is that this test just means to test a plain or-case and it may make sense to use some other values like 14 and 78 (shifted left by 1 bit, instead of 7 and 39) and preserve the original intention of the test.

Hmm, thanks, might be a good idea..

Note the next test @masked_or_A_slightly_optimized has the same code as the after-simplification code of this function. Not sure if it is a just a coincidence.

I have added @masked_or_A_slightly_optimized in rL336784 after noticing this regression, to have a test regardless.

[lebedev.ri]

In D49179#1159036, @spatel wrote:

In D49179#1159024, @lebedev.ri wrote:

In D49179#1158957, @lebedev.ri wrote:

In D49179#1158930, @spatel wrote:

LGTM.

Thank you for such speedy review!

I'm wondering, what about the signed case?
https://godbolt.org/g/WvWX13
https://godbolt.org/g/DM7XA4
https://rise4fun.com/Alive/Qslx (check that 25 high bits are either all-ones, or all-zeros)

Can we do this in instcombine?
Or not, given that we were disabling some bit-fiddling transforms lately?

Actually, not sure that is any better, will leave that for now.
Though the reverse transform might be a good thing for dagcombine.

It's a good question, but probably better asked on the dev list than here. I think we prefer to canonicalize to the form with less instructions even if that means we lose information from the eliminated ops.

For future reference, here is a more straight-forward fold https://rise4fun.com/Alive/XuW, that will afterwards fold back into and+icmp https://godbolt.org/g/bm3yZu
But any such fold will clearly need dagcombine work, since the 'naive' version with shifts seems to produce optimal assembly already.
So after all i'm not sure i'm motivated to look into the 'signed truncation pattern' right now..

x86-signed-truncation-check.ll9 KBDownload

aarch64-signed-truncation-check.ll4 KBDownload

[spatel]

In D49179#1160020, @lebedev.ri wrote:

In D49179#1159036, @spatel wrote:

In D49179#1159024, @lebedev.ri wrote:

In D49179#1158957, @lebedev.ri wrote:

In D49179#1158930, @spatel wrote:

LGTM.

Thank you for such speedy review!

I'm wondering, what about the signed case?
https://godbolt.org/g/WvWX13
https://godbolt.org/g/DM7XA4
https://rise4fun.com/Alive/Qslx (check that 25 high bits are either all-ones, or all-zeros)

Can we do this in instcombine?
Or not, given that we were disabling some bit-fiddling transforms lately?

Actually, not sure that is any better, will leave that for now.
Though the reverse transform might be a good thing for dagcombine.

It's a good question, but probably better asked on the dev list than here. I think we prefer to canonicalize to the form with less instructions even if that means we lose information from the eliminated ops.

For future reference, here is a more straight-forward fold https://rise4fun.com/Alive/XuW, that will afterwards fold back into and+icmp https://godbolt.org/g/bm3yZu
But any such fold will clearly need dagcombine work, since the 'naive' version with shifts seems to produce optimal assembly already.
So after all i'm not sure i'm motivated to look into the 'signed truncation pattern' right now..

x86-signed-truncation-check.ll9 KBDownload

aarch64-signed-truncation-check.ll4 KBDownload

Name: signed truncation check
  %old0 = shl i16 %x, 8
  %old1 = ashr exact i16 %old0, 8
  %ret = icmp eq i16 %old1, %x
=>
  %new0 = icmp slt i16 %x, 128
  %new1 = icmp sgt i16 %x, -129
  %ret = and i1 %new1, %new0

Name: and-of-icmps
  %new0 = icmp slt i16 %x, 128
  %new1 = icmp sgt i16 %x, -129
  %ret = and i1 %new1, %new0
=>
  %x.off = add i16 %x, 128
  %ret = icmp ult i16 %x.off, 256

Let me make sure I'm seeing it - as a question of IR canonicalization, we're deciding which of these 3 forms is best? I don't see any reason to favor the 1st two options over the 3rd (shorter) one. We already convert the 2nd to the 3rd (although as noted here, that transform is not happening as expected in all cases).

If the backend can't produce optimal code from the 3rd form, that's a concern, but it doesn't necessarily have to hold up the IR improvement. We might live with that (hopefully minor and temporary) problem because the IR improvement can lead to optimizations in other passes that we don't see in any of the minimal examples.

[lebedev.ri]

In D49179#1160049, @spatel wrote:

In D49179#1160020, @lebedev.ri wrote:

In D49179#1159036, @spatel wrote:

In D49179#1159024, @lebedev.ri wrote:

In D49179#1158957, @lebedev.ri wrote:

In D49179#1158930, @spatel wrote:

LGTM.

Thank you for such speedy review!

I'm wondering, what about the signed case?
https://godbolt.org/g/WvWX13
https://godbolt.org/g/DM7XA4
https://rise4fun.com/Alive/Qslx (check that 25 high bits are either all-ones, or all-zeros)

Can we do this in instcombine?
Or not, given that we were disabling some bit-fiddling transforms lately?

Actually, not sure that is any better, will leave that for now.
Though the reverse transform might be a good thing for dagcombine.

It's a good question, but probably better asked on the dev list than here. I think we prefer to canonicalize to the form with less instructions even if that means we lose information from the eliminated ops.

For future reference, here is a more straight-forward fold https://rise4fun.com/Alive/XuW, that will afterwards fold back into and+icmp https://godbolt.org/g/bm3yZu
But any such fold will clearly need dagcombine work, since the 'naive' version with shifts seems to produce optimal assembly already.
So after all i'm not sure i'm motivated to look into the 'signed truncation pattern' right now..

x86-signed-truncation-check.ll9 KBDownload

aarch64-signed-truncation-check.ll4 KBDownload

Name: signed truncation check
  %old0 = shl i16 %x, 8
  %old1 = ashr exact i16 %old0, 8
  %ret = icmp eq i16 %old1, %x
=>
  %new0 = icmp slt i16 %x, 128
  %new1 = icmp sgt i16 %x, -129
  %ret = and i1 %new1, %new0

Name: and-of-icmps
  %new0 = icmp slt i16 %x, 128
  %new1 = icmp sgt i16 %x, -129
  %ret = and i1 %new1, %new0
=>
  %x.off = add i16 %x, 128
  %ret = icmp ult i16 %x.off, 256

Let me make sure I'm seeing it - as a question of IR canonicalization, we're deciding which of these 3 forms is best?

Not really. I agree that the last one is the best from IR clarity standpoint.
I was just looking for some other variants of this pattern.
(Sadly souper was of no help here, strangely.)

I don't see any reason to favor the 1st two options over the 3rd (shorter) one. We already convert the 2nd to the 3rd (although as noted here, that transform is not happening as expected in all cases).

I agree.

If the backend can't produce optimal code from the 3rd form, that's a concern, but it doesn't necessarily have to hold up the IR improvement.
We might live with that (hopefully minor and temporary) problem because the IR improvement can lead to optimizations in other passes that we don't see in any of the minimal examples.

[lebedev.ri]

Filed https://bugs.llvm.org/show_bug.cgi?id=38149 to track the signed part of the pattern.

[lebedev.ri]

llvm/trunk/test/Transforms/InstCombine/icmp-logical.ll

91 ↗

(On Diff #155042)

@yamauchi committed in rL336912, thanks!

include/llvm/IR/PatternMatch.h

struct is_sign_mask {
   bool isValue(const APInt &C) { return C.isSignMask(); }
 };
 /// Match an integer or vector with only the sign bit(s) set.
 /// For vectors, this includes constants with undefined elements.
 inline cst_pred_ty<is_sign_mask> m_SignMask() {
   return cst_pred_ty<is_sign_mask>();
 }
 
+struct is_lowbit_mask {
+  bool isValue(const APInt &C) { return C.isMask(); }
+};
+/// Match an integer or vector with only the low bit(s) set.
+/// For vectors, this includes constants with undefined elements.
+inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
+  return cst_pred_ty<is_lowbit_mask>();
+}
+
 struct is_nan {
   bool isValue(const APFloat &C) { return C.isNaN(); }
 };
 /// Match an arbitrary NaN constant. This includes quiet and signalling nans.
 /// For vectors, this includes constants with undefined elements.
 inline cstfp_pred_ty<is_nan> m_NaN() {
   return cstfp_pred_ty<is_nan>();
 }

lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::foldICmpInstWithConstantNotInt(ICmpInst &I) {
 
   return nullptr;
 }
 
 /// Try to fold icmp (binop), X or icmp X, (binop).
 /// TODO: A large part of this logic is duplicated in InstSimplify's
 /// simplifyICmpWithBinOp(). We should be able to share that and avoid the code
 /// duplication.
 Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   // Special logic for binary operators.
   BinaryOperator *BO0 = dyn_cast<BinaryOperator>(Op0);
   BinaryOperator *BO1 = dyn_cast<BinaryOperator>(Op1);
   if (!BO0 && !BO1)
     return nullptr;
 
case ICmpInst::ICMP_SGE:
     std::swap(A, B);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SLE:
     // icmp sle i1 A, B -> A | ~B
     return BinaryOperator::CreateOr(Builder.CreateNot(B), A);
   }
 }
 
+/// Some comparisons can be simplified.
+/// In this case, we are looking for comparisons that look like
+/// a check for a lossy truncation.
+/// Folds:
+///   x & (-1 >> y) == x    to     x u<= (-1 >> y)
+/// The Mask can be a constant, too.
+static Value *
+canonicalizeUnsignedTruncationCheckLikeICmps(ICmpInst &I,
+                                             InstCombiner::BuilderTy &Builder) {
+  ICmpInst::Predicate SrcPred;
+  Value *X, *M;
+  if (!match(&I, m_c_ICmp(SrcPred,
+                          m_c_And(m_CombineAnd(m_CombineOr(m_LShr(m_AllOnes(),
+                                                                  m_Value()),
+                                                           m_LowBitMask()),
+                                               m_Value(M)),
+                                  m_Value(X)),
+                          m_Deferred(X))))
+    return nullptr;
+
+  ICmpInst::Predicate DstPred;
+  switch (SrcPred) {
+  case ICmpInst::Predicate::ICMP_EQ:
+    DstPred = ICmpInst::Predicate::ICMP_ULE;
+    break;
+  default:
+    return nullptr;
+  }
+
+  return Builder.CreateICmp(DstPred, X, M);
+}
+
 Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
   bool Changed = false;
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   unsigned Op0Cplxity = getComplexity(Op0);
   unsigned Op1Cplxity = getComplexity(Op1);
 
   /// Orders the operands of the compare so that they are listed from most
   /// complex to least complex.  This puts constants before unary operators,
if (isa<CastInst>(Op0)) {
     //   if (X) ...
     // For generality, we handle any zero-extension of any operand comparison
     // with a constant or another cast from the same type.
     if (isa<Constant>(Op1) || isa<CastInst>(Op1))
       if (Instruction *R = foldICmpWithCastAndCast(I))
         return R;
   }
 
   if (Instruction *Res = foldICmpBinOp(I))
     return Res;
 
   if (Instruction *Res = foldICmpWithMinMax(I))
     return Res;
 
   {
     Value *A, *B;
     // Transform (A & ~B) == 0 --> (A & B) != 0
     // and       (A & ~B) != 0 --> (A & B) == 0
if (I.getPredicate() == ICmpInst::ICMP_EQ)
     // icmp X+Cst, X
     if (match(Op0, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op1 == X)
       return foldICmpAddOpConst(X, Cst, I.getPredicate());
 
     // icmp X, X+Cst
     if (match(Op1, m_Add(m_Value(X), m_ConstantInt(Cst))) && Op0 == X)
       return foldICmpAddOpConst(X, Cst, I.getSwappedPredicate());
   }
+
+  if (Value *V = canonicalizeUnsignedTruncationCheckLikeICmps(I, Builder))
+    return replaceInstUsesWith(I, V);
+
   return Changed ? &I : nullptr;
 }
 
 /// Fold fcmp ([us]itofp x, cst) if possible.
 Instruction *InstCombiner::foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
                                                 Constant *RHSC) {
   if (!isa<ConstantFP>(RHSC)) return nullptr;
   const APFloat &RHS = cast<ConstantFP>(RHSC)->getValueAPF();

test/Transforms/InstCombine/canonicalize-constant-low-bit-mask-and-icmp-eq-to-icmp-ule.ll

 ; Iff: isPowerOf2(C + 1)
 
 ; ============================================================================ ;
 ; Basic positive tests
 ; ============================================================================ ;
 
 define i1 @p0(i8 %x) {
 ; CHECK-LABEL: @p0(
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[TMP0]], [[X]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[X:%.*]], 4
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %tmp0 = and i8 %x, 3
   %ret = icmp eq i8 %tmp0, %x
   ret i1 %ret
 }
 
 ; ============================================================================ ;
 ; Vector tests
 ; ============================================================================ ;
 
 define <2 x i1> @p1_vec_splat(<2 x i8> %x) {
 ; CHECK-LABEL: @p1_vec_splat(
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X:%.*]], <i8 3, i8 3>
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP0]], [[X]]
-; CHECK-NEXT:    ret <2 x i1> [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult <2 x i8> [[X:%.*]], <i8 4, i8 4>
+; CHECK-NEXT:    ret <2 x i1> [[TMP1]]
 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 3>
   %ret = icmp eq <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }
 
 define <2 x i1> @p2_vec_nonsplat(<2 x i8> %x) {
 ; CHECK-LABEL: @p2_vec_nonsplat(
-; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i8> [[X:%.*]], <i8 3, i8 15>
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP0]], [[X]]
-; CHECK-NEXT:    ret <2 x i1> [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult <2 x i8> [[X:%.*]], <i8 4, i8 16>
+; CHECK-NEXT:    ret <2 x i1> [[TMP1]]
 ;
   %tmp0 = and <2 x i8> %x, <i8 3, i8 15> ; doesn't have to be splat.
   %ret = icmp eq <2 x i8> %tmp0, %x
   ret <2 x i1> %ret
 }
 
 define <3 x i1> @p3_vec_splat_undef(<3 x i8> %x) {
 ; CHECK-LABEL: @p3_vec_splat_undef(
-; CHECK-NEXT:    [[TMP0:%.*]] = and <3 x i8> [[X:%.*]], <i8 3, i8 undef, i8 3>
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq <3 x i8> [[TMP0]], [[X]]
-; CHECK-NEXT:    ret <3 x i1> [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult <3 x i8> [[X:%.*]], <i8 4, i8 undef, i8 4>
+; CHECK-NEXT:    ret <3 x i1> [[TMP1]]
 ;
   %tmp0 = and <3 x i8> %x, <i8 3, i8 undef, i8 3>
   %ret = icmp eq <3 x i8> %tmp0, %x
   ret <3 x i1> %ret
 }
 
 ; ============================================================================ ;
 ; Commutativity tests.
 ; ============================================================================ ;
 
 declare i8 @gen8()
 
 define i1 @c0() {
 ; CHECK-LABEL: @c0(
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X]], 3
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[X]], [[TMP0]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[X]], 4
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %x = call i8 @gen8()
   %tmp0 = and i8 %x, 3
   %ret = icmp eq i8 %x, %tmp0 ; swapped order
   ret i1 %ret
 }
 
 ; ============================================================================ ;
 ; One-use tests. We don't care about multi-uses here.
 ; ============================================================================ ;
 
 declare void @use8(i8)
 
 define i1 @oneuse0(i8 %x) {
 ; CHECK-LABEL: @oneuse0(
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[X:%.*]], 3
 ; CHECK-NEXT:    call void @use8(i8 [[TMP0]])
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[TMP0]], [[X]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 [[X]], 4
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %tmp0 = and i8 %x, 3
   call void @use8(i8 %tmp0)
   %ret = icmp eq i8 %tmp0, %x
   ret i1 %ret
 }
 
 ; ============================================================================ ;

test/Transforms/InstCombine/canonicalize-low-bit-mask-and-icmp-eq-to-icmp-ule.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; https://bugs.llvm.org/show_bug.cgi?id=38123
 
 ; Pattern:
 ;   x & (-1 >> y) == x
 ; Should be transformed into:
 ;   x u<= (-1 >> y)
 
 ; ============================================================================ ;
 ; Basic positive tests
 ; ============================================================================ ;
 
 define i1 @p0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @p0(
 ; CHECK-NEXT:    [[TMP0:%.*]] = lshr i8 -1, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], [[X:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[TMP1]], [[X]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i8 [[TMP0]], [[X:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %tmp0 = lshr i8 -1, %y
   %tmp1 = and i8 %tmp0, %x
   %ret = icmp eq i8 %tmp1, %x
   ret i1 %ret
 }
 
 ; ============================================================================ ;
 ; Vector tests
 ; ============================================================================ ;
 
 define <2 x i1> @p1_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @p1_vec(
 ; CHECK-NEXT:    [[TMP0:%.*]] = lshr <2 x i8> <i8 -1, i8 -1>, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[TMP0]], [[X:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq <2 x i8> [[TMP1]], [[X]]
-; CHECK-NEXT:    ret <2 x i1> [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge <2 x i8> [[TMP0]], [[X:%.*]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP1]]
 ;
   %tmp0 = lshr <2 x i8> <i8 -1, i8 -1>, %y
   %tmp1 = and <2 x i8> %tmp0, %x
   %ret = icmp eq <2 x i8> %tmp1, %x
   ret <2 x i1> %ret
 }
 
 define <3 x i1> @p2_vec_undef(<3 x i8> %x, <3 x i8> %y) {
 ; CHECK-LABEL: @p2_vec_undef(
 ; CHECK-NEXT:    [[TMP0:%.*]] = lshr <3 x i8> <i8 -1, i8 undef, i8 -1>, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and <3 x i8> [[TMP0]], [[X:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq <3 x i8> [[TMP1]], [[X]]
-; CHECK-NEXT:    ret <3 x i1> [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge <3 x i8> [[TMP0]], [[X:%.*]]
+; CHECK-NEXT:    ret <3 x i1> [[TMP1]]
 ;
   %tmp0 = lshr <3 x i8> <i8 -1, i8 undef, i8 -1>, %y
   %tmp1 = and <3 x i8> %tmp0, %x
   %ret = icmp eq <3 x i8> %tmp1, %x
   ret <3 x i1> %ret
 }
 
 ; ============================================================================ ;
 ; Commutativity tests.
 ; ============================================================================ ;
 
 declare i8 @gen8()
 
 define i1 @c0(i8 %y) {
 ; CHECK-LABEL: @c0(
 ; CHECK-NEXT:    [[TMP0:%.*]] = lshr i8 -1, [[Y:%.*]]
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], [[TMP0]]
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[TMP1]], [[X]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ule i8 [[X]], [[TMP0]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %tmp0 = lshr i8 -1, %y
   %x = call i8 @gen8()
   %tmp1 = and i8 %x, %tmp0 ; swapped order
   %ret = icmp eq i8 %tmp1, %x
   ret i1 %ret
 }
 
 define i1 @c1(i8 %y) {
 ; CHECK-LABEL: @c1(
 ; CHECK-NEXT:    [[TMP0:%.*]] = lshr i8 -1, [[Y:%.*]]
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], [[X]]
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[X]], [[TMP1]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ule i8 [[X]], [[TMP0]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %tmp0 = lshr i8 -1, %y
   %x = call i8 @gen8()
   %tmp1 = and i8 %tmp0, %x
   %ret = icmp eq i8 %x, %tmp1 ; swapped order
   ret i1 %ret
 }
 
 define i1 @c2(i8 %y) {
 ; CHECK-LABEL: @c2(
 ; CHECK-NEXT:    [[TMP0:%.*]] = lshr i8 -1, [[Y:%.*]]
 ; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], [[TMP0]]
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[X]], [[TMP1]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ule i8 [[X]], [[TMP0]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %tmp0 = lshr i8 -1, %y
   %x = call i8 @gen8()
   %tmp1 = and i8 %x, %tmp0 ; swapped order
   %ret = icmp eq i8 %x, %tmp1 ; swapped order
   ret i1 %ret
 }
 
 ; ============================================================================ ;
 ; One-use tests. We don't care about multi-uses here.
 ; ============================================================================ ;
 
 declare void @use8(i8)
 
 define i1 @oneuse0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @oneuse0(
 ; CHECK-NEXT:    [[TMP0:%.*]] = lshr i8 -1, [[Y:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[TMP0]])
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], [[X:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[TMP1]], [[X]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i8 [[TMP0]], [[X:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %tmp0 = lshr i8 -1, %y
   call void @use8(i8 %tmp0)
   %tmp1 = and i8 %tmp0, %x
   %ret = icmp eq i8 %tmp1, %x
   ret i1 %ret
 }
 
 define i1 @oneuse1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @oneuse1(
 ; CHECK-NEXT:    [[TMP0:%.*]] = lshr i8 -1, [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[TMP1]])
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[TMP1]], [[X]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i8 [[TMP0]], [[X]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %tmp0 = lshr i8 -1, %y
   %tmp1 = and i8 %tmp0, %x
   call void @use8(i8 %tmp1)
   %ret = icmp eq i8 %tmp1, %x
   ret i1 %ret
 }
 
 define i1 @oneuse2(i8 %x, i8 %y) {
 ; CHECK-LABEL: @oneuse2(
 ; CHECK-NEXT:    [[TMP0:%.*]] = lshr i8 -1, [[Y:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[TMP0]])
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP0]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[TMP1]])
-; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[TMP1]], [[X]]
-; CHECK-NEXT:    ret i1 [[RET]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i8 [[TMP0]], [[X]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %tmp0 = lshr i8 -1, %y
   call void @use8(i8 %tmp0)
   %tmp1 = and i8 %tmp0, %x
   call void @use8(i8 %tmp1)
   %ret = icmp eq i8 %tmp1, %x
   ret i1 %ret
 }

test/Transforms/InstCombine/icmp-logical.ll

;
   %mask2 = and i32 %A, 39
   %tst2 = icmp ne i32 %mask2, %A
   %res = and i1 %tmp0, %tst2
   ret i1 %res
 }
 
 define i1 @masked_or_A(i32 %A) {
 ; CHECK-LABEL: @masked_or_A(
-; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A:%.*]], 39
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[A:%.*]], 8
+; CHECK-NEXT:    [[MASK2:%.*]] = and i32 [[A]], 39
 ; CHECK-NEXT:    [[TST2:%.*]] = icmp eq i32 [[MASK2]], [[A]]
-; CHECK-NEXT:    ret i1 [[TST2]]
+; CHECK-NEXT:    [[RES:%.*]] = or i1 [[TMP1]], [[TST2]]
+; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %mask1 = and i32 %A, 7
   %tst1 = icmp eq i32 %mask1, %A
   %mask2 = and i32 %A, 39
   %tst2 = icmp eq i32 %mask2, %A
   %res = or i1 %tst1, %tst2
   ret i1 %res
 }

test/Transforms/InstCombine/icmp-mul-zext.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i32 @sterix(i32, i8, i64) {
 ; CHECK-LABEL: @sterix(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i32 [[TMP0:%.*]] to i64
 ; CHECK-NEXT:    [[CONV1:%.*]] = sext i8 [[TMP1:%.*]] to i32
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[CONV1]], 1945964878
 ; CHECK-NEXT:    [[SH_PROM:%.*]] = trunc i64 [[TMP2:%.*]] to i32
 ; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[MUL]], [[SH_PROM]]
 ; CHECK-NEXT:    [[CONV2:%.*]] = zext i32 [[SHR]] to i64
 ; CHECK-NEXT:    [[MUL3:%.*]] = mul nuw nsw i64 [[CONV]], [[CONV2]]
-; CHECK-NEXT:    [[CONV6:%.*]] = and i64 [[MUL3]], 4294967295
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[CONV6]], [[MUL3]]
-; CHECK-NEXT:    br i1 [[TOBOOL]], label [[LOR_RHS:%.*]], label [[LOR_END:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ugt i64 [[MUL3]], 4294967295
+; CHECK-NEXT:    br i1 [[TMP3]], label [[LOR_END:%.*]], label [[LOR_RHS:%.*]]
 ; CHECK:       lor.rhs:
 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[MUL3]], [[TMP2]]
 ; CHECK-NEXT:    [[CONV4:%.*]] = trunc i64 [[AND]] to i32
 ; CHECK-NEXT:    [[TOBOOL7:%.*]] = icmp eq i32 [[CONV4]], 0
 ; CHECK-NEXT:    [[PHITMP:%.*]] = zext i1 [[TOBOOL7]] to i32
 ; CHECK-NEXT:    br label [[LOR_END]]
 ; CHECK:       lor.end:
-; CHECK-NEXT:    [[TMP3:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[PHITMP]], [[LOR_RHS]] ]
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[PHITMP]], [[LOR_RHS]] ]
+; CHECK-NEXT:    ret i32 [[TMP4]]
 ;
 entry:
   %conv = zext i32 %0 to i64
   %conv1 = sext i8 %1 to i32
   %mul = mul i32 %conv1, 1945964878
   %sh_prom = trunc i64 %2 to i32
   %shr = lshr i32 %mul, %sh_prom
   %conv2 = zext i32 %shr to i64