[InstCombine] Transform bitwise (A >> C - 1, zext(icmp)) -> zext (bitwise(A < 0, icmp)) fold.

[XChy]

Summary

This extends foldCastedBitwiseLogic to handle the similar cases.
I have recently submitted a patch to implement a single fold like:

(A > 0) | (A < 0) -> zext (A != 0)

But it is not general enough, and some problems like a < b & a >= b - 1 happen again.

So I generalize this fold by matching the pattern bitwise(A >> C - 1, zext(icmp)), and replace A >> C - 1 with zext(A < 0) here.
(C is the scalar size bits of the type of A)
Then we get bitwise(zext(A < 0), zext(icmp)), this will be folded by original code in foldCastedBitwiseLogic, into zext(bitwise(A < 0, icmp)).
And finally, any related icmp fold will be automatically implemented because bitwise(icmp,icmp) had been implemented.

The proof of the correctness is obvious, because the folds below were previously proved and implemented.
A >> C - 1 -> zext(A < 0)
bitwise(zext(A), zext(B)) -> zext(bitwise(A, B))
And the fold of this patch is the combination of folds above.

Related issue:
a < b | a >b
a < b & a >= b - 1
Related patch:
D154126

[nikic]

The basic idea here is reasonable, but you need to be very careful about infinite loops: If you replace the shift with zext+icmp and it does *not* get folded afterwards, it will be converted back to the shift, and so on. I don't think the fold is guaranteed to happen, e.g. due to some unlucky interaction with shouldOptimizeCast().

I would recommend to instead directly produce the zext(binop(icmp, icmp)) sequence, rather than letting the following fold handle it.

Please add:

• Multi-use test.
• Test where we do not get any beneficial fold out of converting the lshr back into an icmp.

Depending on how the latter case looks like, we might want to further limit this -- e.g. does it make sense to do this if the lshr and icmp work on different variables or not?

[goldstein.w.n]

Throughout the comments/summary/title can you replace X with C to indicate its a constant. Also in a few places you forget the -1 in its description as sizeof_bits(A) - 1.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1741

lshr? The comments are all shl. Can you clarify one of them (looks like comments/summary is wrong).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1736

'and/or' -> 'bitwise' no?

1744

Is there a reason you create IsMatched as opposed to just embedding the match(...) logic in the if statement?

[XChy]

In D154791#4483474, @nikic wrote:

The basic idea here is reasonable, but you need to be very careful about infinite loops: If you replace the shift with zext+icmp and it does *not* get folded afterwards, it will be converted back to the shift, and so on. I don't think the fold is guaranteed to happen, e.g. due to some unlucky interaction with shouldOptimizeCast().

I would recommend to instead directly produce the zext(binop(icmp, icmp)) sequence, rather than letting the following fold handle it.

Please add:

• Multi-use test.
• Test where we do not get any beneficial fold out of converting the lshr back into an icmp.

Depending on how the latter case looks like, we might want to further limit this -- e.g. does it make sense to do this if the lshr and icmp work on different variables or not?

Thanks for your review! I agree with you. Actually, I came across infinite loops during developing and seem to solve it by letting the following fold handle IR. But it's just solved with few tests.

My original purpose is to use foldAndOrOfICmps to fold icmps as fold and/or( A < 0, icmp). From my perspective, if foldAndOrOfICmps doesn't fold the transformed IR, this fold should not happend.

I will add related tests here and try to find out where we do not get any beneficial fold later.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1736

Maybe and/or is right, since foldAndOrOfICmps do not fold xor.
I'm not sure what xor(icmp,icmp) is folded into.

1741

You're right. I mess it up in last patch too. I'll fix it.

1744

No, it's my personal habit to set a boolean variable when expression is too long. If needed, I can remove it.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1736

In that case, you need to only match and/or and probably should mention that in the summary.

1744

Its fine.

[nikic]

This is still missing multi-use tests. We'll need some m_OneUse guards to prevent unprofitable transforms.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1716–1732

X -> BW

1734–1740

1743

Needs clang-format.

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2886

The main multi-use test I'm looking for is one where the resulting binop does not get folded. That's the case where your current code will increase instructions, I believe.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1716–1732

comment incorrect shift.

1726

Does Op1 need to be an icmp, or can it just be any i1?

1727

nit:: LogicOp != Instruction::Xor should go before the match(...) imo.

[XChy]

[clang-format]

[XChy]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1726

When folding A >> BW - 1 -> A < 0, there are many possible folds for (A < 0) bitwise (icmp).
However, if replacing icmp with an arbitrary i1, it seldom folds and just produces this single fold A >> BW - 1 -> A < 0, which is inefficient.

1736

I noticed foldXorOfICmps fold just now. Maybe I can add some related tests here.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1726

I see.

1727

It seems in addressing this you just remove the LogicOp != Xor ingeneral...

[XChy]

I update the diff to ensure that we fold exactly what can be folded by foldXorOfICmps and foldAndOrOfICmps.

However, I'm not sure what unexpected result the code below may bring.

// remove the deferred 2 instructions : 
// icmp slt A, 0
// bitwise (A < 0, icmp) 
// otherwise there will be infinite loops of combining
Worklist.popDeferred()->eraseFromParent();
Worklist.popDeferred()->eraseFromParent();

[XChy]

In D154791#4497148, @XChy wrote:

I update the diff to ensure that we fold exactly what can be folded by foldXorOfICmps and foldAndOrOfICmps.

However, I'm not sure what unexpected result the code below may bring.

// remove the deferred 2 instructions : 
// icmp slt A, 0
// bitwise (A < 0, icmp) 
// otherwise there will be infinite loops of combining
Worklist.popDeferred()->eraseFromParent();
Worklist.popDeferred()->eraseFromParent();

Actually, I copy and edit the code to avoid infinite loops from:

Instruction *eraseInstFromFunction(Instruction &I) override {
  LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
  assert(I.use_empty() && "Cannot erase instruction that is used!");
  salvageDebugInfo(I);

  // Make sure that we reprocess all operands now that we reduced their
  // use counts.
  SmallVector<Value *> Ops(I.operands());
  Worklist.remove(&I);
  I.eraseFromParent();
  for (Value *Op : Ops)
    Worklist.handleUseCountDecrement(Op);
  MadeIRChange = true;
  return nullptr; // Don't do anything with FI
}

I omit MadeIRChange = true; to avoid the infinite loops, which are caused by MadeIRChange with the same instructions deferred and erased(Actually, IR do not change).

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1756

@nikic, is this right?

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2901

Since you're now supporting xor, you need to add some tests for it.

[XChy]

Add xor tests

[XChy]

Limit the fold for multiuse cases

[XChy]

ping.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1754

I'm mostly okay with the change, but a little unhappy about this. It seems like a worrisome practice.
I guess it works, but it would be nice if there where a better way to accomplish it.

Generally I'd argue the best solution would be to refactor fold<BinOp>OfICmp to take the components rather than the final instructions, but those are both fairly complicated and propagate the instructions to other functions that would then need to be refactored. All in all more work than its worth.

I'm going to defer my opinion to @nikic about whether this is okay.

Other than my concern here, I'm basically ready to approve.

[XChy]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1754

Thanks for your comment! I agree with you. It's not a good way to erase some deferred instructions in a fold function. It's better to let InstCombinerImpl::run() control the logic of instruction erasion.

But there aren't other ways to determine whether some instructions can be folded by fold<BinOp>OfICmp, unless we just call it with the instructions built and deferred or we can extract a canFold<BinOp>OfICmp function to take the components.

The latter costs too much, since it may require refactoring all sub folds.

For that reason, I applied the former but I didn't find any similar situations in InstCombine. I just try to copy some of the logic of instructions erasion to solve the problem.

I'll search for more similar cases to get a better solution if possible. I'll highly appreciate it if you could give me some other advice.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1754

Unfortunately I don't really have a better idea than what you have here, but want to here nikic's opinion

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1754

We shouldn't do this kind of speculative transform. Either you can always do the transform based on a reasonably close heuristic (like zext and icmp on the same value) or change APIs in a way that allows doing the transform without materializing the icmp (I think this is not worth the trouble).

My 2c here is that it would be okay to convert to the zext(bitwise(icmp, icmp)) form even if it doesn't always fold, as this seems like the better representation at the IR level to me. Even if it doesn't fold in InstCombine, this is the form that is more likely to be usefully optimized by other passes. If we really care, we can undo this in the backend.

[XChy]

Produce zext(bitwise(icmp.icmp))

[XChy]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1754

I see. I have reverted to the version producing zext(bitwise(icmp.icmp))

[XChy]

ping.

[nikic]

Looks mostly fine, but I think the one-use check isn't quite correct.

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2670

Not _fail?

2914

Creating more instructions here. You should probably always require one-use on the lshr rather than one-use on one of the operands.

[XChy]

• Apply m_OneUse guard to lshr.
• Fix nits

[XChy]

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2914

If replacing icmp eq 100 with other icmp that can be optimized along with icmp slt 0, there will be a better IR, except just one extra instruction. Is there some principles that determine whether a one-use guard is necessary or whether a fold is too agressive/conservative? Maybe I can apply them to similar situation in future contributions.

[nikic]

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2914

For multi-use we want to avoid instruction increase in the worst case.

2947

Based on this we should have m_OneUse on the zext(icmp) as well.

[XChy]

• Add m_OneUse guard to zext(icmp).

llvm/test/Transforms/InstCombine/and-or-icmps.ll

2914

OK. Thanks for suggestion.

[nikic]

LGTM

[XChy]

In D154791#4527350, @nikic wrote:

LGTM

I don't have commit access, can you please land this for me? Please use 'XChy [e-mail]' for the commit.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 
 /// Fold {and,or,xor} (cast X), Y.
 Instruction *InstCombinerImpl::foldCastedBitwiseLogic(BinaryOperator &I) {
   auto LogicOpc = I.getOpcode();
   assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic folding");
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
-  // ( A << (X - 1) ) | ((A > 0) zext to iX)
-  // <=> A < 0 | A > 0
-  // <=> (A != 0) zext to iX
-  Value *A;
+  // fold bitwise(A >> BW - 1, zext(icmp))     (BW is the scalar bits of the
+  // type of A)
+  //   -> bitwise(zext(A < 0), zext(icmp))
+  //   -> zext(bitwise(A < 0, icmp))
+  auto FoldBitwiseICmpZeroWithICmp = [&](Value *Op0,
+                                         Value *Op1) -> Instruction * {
     ICmpInst::Predicate Pred;
+    Value *A;
+    bool IsMatched =
+        match(Op0,
+              m_OneUse(m_LShr(
+                  m_Value(A),
+                  m_SpecificInt(Op0->getType()->getScalarSizeInBits() - 1)))) &&
+        match(Op1, m_ZExt(m_ICmp(Pred, m_Value(), m_Value())));
+
+    if (!IsMatched)
+      return nullptr;
+
+    auto *ICmpL =
+        Builder.CreateICmpSLT(A, Constant::getNullValue(A->getType()));
+    auto *ICmpR = cast<ZExtInst>(Op1)->getOperand(0);
+    auto *BitwiseOp = Builder.CreateBinOp(LogicOpc, ICmpL, ICmpR);
 
-  auto MatchOrZExtICmp = [&](Value *Op0, Value *Op1) -> bool {
-    return match(Op0, m_LShr(m_Value(A), m_SpecificInt(Op0->getType()->getScalarSizeInBits() - 1))) &&
-           match(Op1, m_ZExt(m_ICmp(Pred, m_Specific(A), m_Zero())));
+    return new ZExtInst(BitwiseOp, Op0->getType());
   };
 
-  if (LogicOpc == Instruction::Or &&
-      (MatchOrZExtICmp(Op0, Op1) || MatchOrZExtICmp(Op1, Op0)) &&
-      Pred == ICmpInst::ICMP_SGT) {
-      Value *Cmp =
-          Builder.CreateICmpNE(A, Constant::getNullValue(A->getType()));
-      return new ZExtInst(Cmp, A->getType());
-  }
+  if (auto *Ret = FoldBitwiseICmpZeroWithICmp(Op0, Op1))
+    return Ret;
+
+  if (auto *Ret = FoldBitwiseICmpZeroWithICmp(Op1, Op0))
+    return Ret;
 
   CastInst *Cast0 = dyn_cast<CastInst>(Op0);
   if (!Cast0)
     return nullptr;
 
   // This must be a cast from an integer or integer vector source type to allow
   // transformation of the logic operation to the source type.
   Type *DestTy = I.getType();
   Type *SrcTy = Cast0->getSrcTy();
   if (!SrcTy->isIntOrIntVectorTy())
     return nullptr;
 
   if (Instruction *Ret = foldLogicCastConstant(I, Cast0, Builder))
     return Ret;
 
   CastInst *Cast1 = dyn_cast<CastInst>(Op1);
   if (!Cast1)
     return nullptr;

llvm/test/Transforms/InstCombine/and-or-icmps.ll

;
   %A = icmp slt <2 x i64> %x, <i64 0,i64 0>
   %B = icmp sgt <2 x i64> %x, <i64 0,i64 0>
   %C = zext <2 x i1> %A to <2 x i64>
   %D = zext <2 x i1> %B to <2 x i64>
   %E = or <2 x i64> %C, %D
   ret <2 x i64> %E
 }
 
 define <2 x i64> @icmp_slt_0_or_icmp_sgt_0_i64x2_fail(<2 x i64> %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sgt_0_i64x2_fail(
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt <2 x i64> [[X:%.*]], <i64 1, i64 1>
-; CHECK-NEXT:    [[C:%.*]] = lshr <2 x i64> [[X]], <i64 63, i64 63>
-; CHECK-NEXT:    [[D:%.*]] = zext <2 x i1> [[B]] to <2 x i64>
-; CHECK-NEXT:    [[E:%.*]] = or <2 x i64> [[C]], [[D]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt <2 x i64> [[X:%.*]], <i64 1, i64 1>
+; CHECK-NEXT:    [[E:%.*]] = zext <2 x i1> [[TMP1]] to <2 x i64>
 ; CHECK-NEXT:    ret <2 x i64> [[E]]
 ;
   %B = icmp sgt <2 x i64> %x, <i64 1, i64 1>
   %C = lshr <2 x i64> %x, <i64 63, i64 63>
   %D = zext <2 x i1> %B to <2 x i64>
   %E = or <2 x i64> %C, %D
   ret <2 x i64> %E
 
 }
 
 define i32 @icmp_slt_0_and_icmp_sge_neg1_i32(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_sge_neg1_i32(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = and i32 [[C]], [[B]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 0
 ;
   %A = icmp sgt i32 %x, -1
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = and i32 %C, %B
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_or_icmp_sge_neg1_i32(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sge_neg1_i32(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], -2
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = or i32 [[C]], [[B]]
-; CHECK-NEXT:    ret i32 [[D]]
+; CHECK-NEXT:    ret i32 1
 ;
   %A = icmp sge i32 %x, -1
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = or i32 %C, %B
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_or_icmp_sge_100_i32(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_sge_100_i32(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], 99
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = or i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[X:%.*]], 99
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp sge i32 %x, 100
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = or i32 %C, %B
   ret i32 %D
 }
 
 define i64 @icmp_slt_0_and_icmp_sge_neg1_i64(i64 %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_sge_neg1_i64(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt i64 [[X:%.*]], -2
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i64
-; CHECK-NEXT:    [[C:%.*]] = lshr i64 [[X]], 63
-; CHECK-NEXT:    [[D:%.*]] = and i64 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[X:%.*]], -1
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP1]] to i64
 ; CHECK-NEXT:    ret i64 [[D]]
 ;
   %A = icmp sge i64 %x, -1
   %B = zext i1 %A to i64
   %C = lshr i64 %x, 63
   %D = and i64 %C, %B
   ret i64 %D
 }
 
 define i64 @icmp_slt_0_and_icmp_sge_neg2_i64(i64 %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_sge_neg2_i64(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt i64 [[X:%.*]], -3
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i64
-; CHECK-NEXT:    [[C:%.*]] = lshr i64 [[X]], 63
-; CHECK-NEXT:    [[D:%.*]] = and i64 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i64 [[X:%.*]], -3
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP1]] to i64
 ; CHECK-NEXT:    ret i64 [[D]]
 ;
   %A = icmp sge i64 %x, -2
   %B = zext i1 %A to i64
   %C = lshr i64 %x, 63
   %D = and i64 %C, %B
   ret i64 %D
 }
 
 define i64 @ashr_and_icmp_sge_neg1_i64(i64 %x) {
 ; CHECK-LABEL: @ashr_and_icmp_sge_neg1_i64(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt i64 [[X:%.*]], -2
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i64
-; CHECK-NEXT:    [[C1:%.*]] = lshr i64 [[X]], 63
-; CHECK-NEXT:    [[D:%.*]] = and i64 [[C1]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[X:%.*]], -1
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP1]] to i64
 ; CHECK-NEXT:    ret i64 [[D]]
 ;
   %A = icmp sge i64 %x, -1
   %B = zext i1 %A to i64
   %C = ashr i64 %x, 63
   %D = and i64 %C, %B
   ret i64 %D
 }
 
 define i64 @icmp_slt_0_and_icmp_sgt_neg1_i64(i64 %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_sgt_neg1_i64(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt i64 [[X:%.*]], -1
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i64
-; CHECK-NEXT:    [[C:%.*]] = lshr i64 [[X]], 63
-; CHECK-NEXT:    [[D:%.*]] = and i64 [[C]], [[B]]
-; CHECK-NEXT:    ret i64 [[D]]
+; CHECK-NEXT:    ret i64 0
 ;
   %A = icmp sgt i64 %x, -1
   %B = zext i1 %A to i64
   %C = lshr i64 %x, 63
   %D = and i64 %C, %B
   ret i64 %D
 }
 
;
   %B = zext i1 %A to i64
   %C = lshr i64 %x, 62
   %D = and i64 %C, %B
   ret i64 %D
 }
 
 define <2 x i32> @icmp_slt_0_and_icmp_sge_neg1_i32x2(<2 x i32> %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_sge_neg1_i32x2(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt <2 x i32> [[X:%.*]], <i32 -2, i32 -2>
-; CHECK-NEXT:    [[B:%.*]] = zext <2 x i1> [[A]] to <2 x i32>
-; CHECK-NEXT:    [[C:%.*]] = lshr <2 x i32> [[X]], <i32 31, i32 31>
-; CHECK-NEXT:    [[D:%.*]] = and <2 x i32> [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[D:%.*]] = zext <2 x i1> [[TMP1]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[D]]
 ;
   %A = icmp sge <2 x i32> %x, <i32 -1, i32 -1>
   %B = zext <2 x i1> %A to <2 x i32>
   %C = lshr <2 x i32> %x, <i32 31, i32 31>
   %D = and <2 x i32> %C, %B
   ret <2 x i32> %D
 }
 
 define <2 x i32> @icmp_slt_0_and_icmp_sge_neg2_i32x2(<2 x i32> %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_sge_neg2_i32x2(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt <2 x i32> [[X:%.*]], <i32 -3, i32 -3>
-; CHECK-NEXT:    [[B:%.*]] = zext <2 x i1> [[A]] to <2 x i32>
-; CHECK-NEXT:    [[C:%.*]] = lshr <2 x i32> [[X]], <i32 31, i32 31>
-; CHECK-NEXT:    [[D:%.*]] = and <2 x i32> [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt <2 x i32> [[X:%.*]], <i32 -3, i32 -3>
+; CHECK-NEXT:    [[D:%.*]] = zext <2 x i1> [[TMP1]] to <2 x i32>
 ; CHECK-NEXT:    ret <2 x i32> [[D]]
 ;
   %A = icmp sge <2 x i32> %x, <i32 -2, i32 -2>
   %B = zext <2 x i1> %A to <2 x i32>
   %C = lshr <2 x i32> %x, <i32 31, i32 31>
   %D = and <2 x i32> %C, %B
   ret <2 x i32> %D
 }
 
 
 define i32 @icmp_x_slt_0_xor_icmp_y_sgt_neg1_i32(i32 %x, i32 %y) {
 ; CHECK-LABEL: @icmp_x_slt_0_xor_icmp_y_sgt_neg1_i32(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[Y:%.*]], 31
-; CHECK-NEXT:    [[D:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[TMP1]], -1
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp sgt i32 %x, -1
   %B = zext i1 %A to i32
   %C = lshr i32 %y, 31
   %D = xor i32 %C, %B
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_xor_icmp_sgt_neg2_i32(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_xor_icmp_sgt_neg2_i32(
-; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], -2
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp sgt i32 %x, -2
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = xor i32 %C, %B
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_and_icmp_sge_neg1_i32_multiuse0(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_sge_neg1_i32_multiuse0(
 ; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], -3
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[X]], -3
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK-NEXT:    call void @use(i1 [[A]])
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp sge i32 %x, -2
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = and i32 %C, %B
   call void @use(i1 %A)
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_and_icmp_sge_neg2_i32_multiuse1(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_sge_neg2_i32_multiuse1(
 ; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], -3
 ; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[X]], -3
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK-NEXT:    call void @use32(i32 [[B]])
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp sge i32 %x, -2
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = and i32 %C, %B
   call void @use32(i32 %B)

 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp sge i32 %x, -2
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = and i32 %C, %B
   call void @use32(i32 %C)
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_and_icmp_sge_neg2_i32_multiuse_fail0(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_sge_neg2_i32_multiuse_fail0(
 ; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], -3
 ; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
 ; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
 ; CHECK-NEXT:    [[D:%.*]] = and i32 [[C]], [[B]]
 ; CHECK-NEXT:    call void @use32(i32 [[B]])
 ; CHECK-NEXT:    call void @use32(i32 [[C]])
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp sge i32 %x, -2
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = and i32 %C, %B
   call void @use32(i32 %B)
   call void @use32(i32 %C)
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_or_icmp_eq_100_i32_multiuse_fail1(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_eq_100_i32_multiuse_fail1(
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], 100
 ; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
 ; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
 ; CHECK-NEXT:    [[D:%.*]] = or i32 [[C]], [[B]]
 ; CHECK-NEXT:    call void @use32(i32 [[C]])
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp eq i32 %x, 100
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = or i32 %C, %B
   call void @use32(i32 %C)
   ret i32 %D
 }
;
   call void @use32(i32 %C)
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_or_icmp_eq_100_i32_multiuse_fail3(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_eq_100_i32_multiuse_fail3(
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], 100
 ; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = or i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    call void @use32(i32 [[B]])
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp eq i32 %x, 100
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = or i32 %C, %B
   call void @use32(i32 %B)
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_or_icmp_eq_100_i32_fail(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_eq_100_i32_fail(
 ; CHECK-NEXT:    [[A:%.*]] = icmp eq i32 [[X:%.*]], 100
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = or i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp eq i32 %x, 100
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = or i32 %C, %B
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_and_icmp_ne_neg2_i32_fail(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_and_icmp_ne_neg2_i32_fail(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[X:%.*]], -2
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp ne i32 %x, -2
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = and i32 %C, %B
   ret i32 %D
 }
 
 define i32 @icmp_x_slt_0_and_icmp_y_ne_neg2_i32_fail(i32 %x, i32 %y) {
 ; CHECK-LABEL: @icmp_x_slt_0_and_icmp_y_ne_neg2_i32_fail(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ne i32 [[X:%.*]], -2
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[Y:%.*]], 31
-; CHECK-NEXT:    [[D:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp ne i32 %x, -2
   %B = zext i1 %A to i32
   %C = lshr i32 %y, 31
   %D = and i32 %C, %B
   ret i32 %D
 }
 
 define i32 @icmp_x_slt_0_and_icmp_y_sgt_neg1_i32_fail(i32 %x, i32 %y) {
 ; CHECK-LABEL: @icmp_x_slt_0_and_icmp_y_sgt_neg1_i32_fail(
 ; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[Y:%.*]], 31
-; CHECK-NEXT:    [[D:%.*]] = and i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp sgt i32 %x, -1
   %B = zext i1 %A to i32
   %C = lshr i32 %y, 31
   %D = and i32 %C, %B
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_xor_icmp_sge_neg2_i32_fail(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_xor_icmp_sge_neg2_i32_fail(
 ; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X:%.*]], -3
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i1 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %A = icmp sge i32 %x, -2
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = xor i32 %C, %B
   ret i32 %D
 }
 
 define i32 @icmp_slt_0_or_icmp_add_1_sge_100_i32_fail(i32 %x) {
 ; CHECK-LABEL: @icmp_slt_0_or_icmp_add_1_sge_100_i32_fail(
 ; CHECK-NEXT:    [[X1:%.*]] = add i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[A:%.*]] = icmp sgt i32 [[X1]], 99
-; CHECK-NEXT:    [[B:%.*]] = zext i1 [[A]] to i32
-; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[X]], 31
-; CHECK-NEXT:    [[D:%.*]] = or i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = or i1 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[D:%.*]] = zext i1 [[TMP2]] to i32
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
   %X1 = add i32 %x, 1
   %A = icmp sge i32 %X1, 100
   %B = zext i1 %A to i32
   %C = lshr i32 %x, 31
   %D = or i32 %C, %B
   ret i32 %D
 }