[InstCombine] Conditionally fold select i1 into and/or

[aqjune]

Summary

This patch fixes llvm.org/pr49688 by conditionally folding select i1 into and/or:

select cond, cond2, false
->
and cond, cond2

This is not safe if cond2 is poison whereas cond isn’t.

Unconditionally disabling this transformation affects later pipelines that depend on and/or i1s.
To minimize its impact, this patch conservatively checks whether cond2 is an instruction that
creates a poison or its operand creates a poison.
This approach is similar to what InstSimplify's SimplifyWithOpReplaced is doing.

[aqjune]

llvm/test/Transforms/InstCombine/and-fcmp.ll

79

This optimization can be supported by inserting freeze again.
If this patch is accepted, I'll record this as a regression at bugzilla and make a patch then.

[nikic]

Unconditionally disabling this transformation affects later pipelines that depend on and/or i1s.
To minimize its impact, this patch conservatively checks whether cond2 is an instruction that
creates a poison or its operand creates a poison.

Do you have any further information on the regressions this would result in?

Given all the preliminary work that has gone into this, I'd really like to have the option flipped outright, and not introduce another hack.

llvm/test/Transforms/InstCombine/pr49668.ll

1 ↗

(On Diff #334483)

Wrong filename? https://bugs.llvm.org/show_bug.cgi?id=49668 does not look related.

[aqjune]

In D99674#2662023, @nikic wrote:

Unconditionally disabling this transformation affects later pipelines that depend on and/or i1s.
To minimize its impact, this patch conservatively checks whether cond2 is an instruction that
creates a poison or its operand creates a poison.

Do you have any further information on the regressions this would result in?

Given all the preliminary work that has gone into this, I'd really like to have the option flipped outright, and not introduce another hack.

If -instcombine-unsafe-select-transform is flipped from true to false, we have 35 LLVM unit test failures. A few of them are unsafe ones so okay to be removed, but the remaining ones need updates in analysis or transformations to reenable them.
To minimize performance regression, what do you think about this workflow?
(1) This patch is landed to fix the miscompilation without significant regressions
(2) The clang noundef patch is enabled by default (I left a comment at its test-only patch)
(3) Flip -instcombine-unsafe-select-transform to false

Enabling the clang noundef flag reduces assembly diffs from LLVM test suite.
Without the noundef flag, the # of different assembly files is 737/5247 when -instcombine-unsafe-select-transform is flipped from true to false.
With the noundef flag, it becomes 632/5247.
It looks big, but about 80% of those are simply from reordering of basic blocks (I randomly picked 5 samples and 4 were such cases).
With this patch (D99674) only, the assembly diff # is already 439/5247, so 632 isn't very big.

[aqjune]

rebase, correctify the test file name

[nikic]

In D99674#2664219, @aqjune wrote:

If -instcombine-unsafe-select-transform is flipped from true to false, we have 35 LLVM unit test failures. A few of them are unsafe ones so okay to be removed, but the remaining ones need updates in analysis or transformations to reenable them.
To minimize performance regression, what do you think about this workflow?
(1) This patch is landed to fix the miscompilation without significant regressions
(2) The clang noundef patch is enabled by default (I left a comment at its test-only patch)
(3) Flip -instcombine-unsafe-select-transform to false

Enabling the clang noundef flag reduces assembly diffs from LLVM test suite.
Without the noundef flag, the # of different assembly files is 737/5247 when -instcombine-unsafe-select-transform is flipped from true to false.
With the noundef flag, it becomes 632/5247.
It looks big, but about 80% of those are simply from reordering of basic blocks (I randomly picked 5 samples and 4 were such cases).
With this patch (D99674) only, the assembly diff # is already 439/5247, so 632 isn't very big.

I'm OK with landing this first to fix an active miscompile, but I don't think we should block flipping the switch on noundef work. I think your numbers support that we shouldn't wait on that, because the noundef impact it small relative to the whole change (it only makes a 15% difference in affected files).

llvm/test/Transforms/PhaseOrdering/unsigned-multiply-overflow-check.ll

116 ↗

(On Diff #334724)

This test update looks unnecessary? Only changes names.

[aqjune]

In D99674#2667634, @nikic wrote:

I'm OK with landing this first to fix an active miscompile, but I don't think we should block flipping the switch on noundef work. I think your numbers support that we shouldn't wait on that, because the noundef impact it small relative to the whole change (it only makes a 15% difference in affected files).

Let's wait for two weeks after this patch is landed to see whether any serious regression from this patch is reported - if there is no such report, I think it is a good sign and we can move forward without waiting for the noundef patch.
Thanks for the review!

[aqjune]

rebase, clang-format

[bjope]

I've seen problems with infinite loops in InstCombine after mergin this patch downstream:

IC: Visiting:   %not. = xor <4 x i1> %271, <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: Visiting:   %274 = select <4 x i1> %not., <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, <4 x i1> %273, !dbg !252
IC: ADD DEFERRED:   %not. = xor <4 x i1> %271, <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: Mod =   %274 = select <4 x i1> %not., <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, <4 x i1> %273, !dbg !252
    New =   %274 = select <4 x i1> %271, <4 x i1> %273, <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: ADD:   %274 = select <4 x i1> %271, <4 x i1> %273, <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: ERASE   %not. = xor <4 x i1> %271, <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: ADD DEFERRED:   %271 = and <4 x i1> %broadcast.splat2008, %270, !dbg !252
IC: ADD:   %271 = and <4 x i1> %broadcast.splat2008, %270, !dbg !252
IC: Visiting:   %271 = and <4 x i1> %broadcast.splat2008, %270, !dbg !252
IC: Visiting:   %274 = select <4 x i1> %271, <4 x i1> %273, <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: ADD DEFERRED:   %not. = xor <4 x i1> %271, <i1 true, i1 true, i1 true, i1 true>
IC: Old =   %274 = select <4 x i1> %271, <4 x i1> %273, <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
    New =   <badref> = select <4 x i1> %not., <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i1> %273
IC: ADD:   %274 = select <4 x i1> %not., <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i1> %273, !dbg !252
IC: ERASE   %275 = select <4 x i1> %271, <4 x i1> %273, <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: ADD DEFERRED:   %271 = and <4 x i1> %broadcast.splat2008, %270, !dbg !252
IC: ADD DEFERRED:   %273 = icmp sge <4 x i32> %272, %broadcast.splat2010, !dbg !252
IC: ADD:   %273 = icmp sge <4 x i32> %272, %broadcast.splat2010, !dbg !252
IC: ADD:   %271 = and <4 x i1> %broadcast.splat2008, %270, !dbg !252
IC: ADD:   %not. = xor <4 x i1> %271, <i1 true, i1 true, i1 true, i1 true>, !dbg !252
IC: Visiting:   %not. = xor <4 x i1> %271, <i1 true, i1 true, i1 true, i1 true>, !dbg !252
IC: Visiting:   %271 = and <4 x i1> %broadcast.splat2008, %270, !dbg !252
IC: Visiting:   %273 = icmp sge <4 x i32> %272, %broadcast.splat2010, !dbg !252
IC: Visiting:   %274 = select <4 x i1> %not., <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i1> %273, !dbg !252
IC: Visiting:   %predphi = select <4 x i1> %274, <4 x i32> %281, <4 x i32> <i32 poison, i32 poison, i32 poison, i32 0>, !dbg !252
IC: Visiting:   %282 = extractelement <4 x i32> %predphi, i32 3
IC: ADD DEFERRED:   %not. = xor <4 x i1> %271, <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: ADD DEFERRED:   %274 = select <4 x i1> %not., <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, <4 x i1> %273, !dbg !252
IC: ADD DEFERRED:   %predphi = select <4 x i1> %274, <4 x i32> %281, <4 x i32> <i32 poison, i32 poison, i32 poison, i32 0>, !dbg !252
IC: Mod =   %282 = extractelement <4 x i32> %predphi, i32 3
    New =   %282 = extractelement <4 x i32> %predphi, i32 3
IC: ADD:   %282 = extractelement <4 x i32> %predphi, i32 3
IC: ADD:   %predphi = select <4 x i1> %274, <4 x i32> %281, <4 x i32> <i32 poison, i32 poison, i32 poison, i32 0>, !dbg !252
IC: ADD:   %274 = select <4 x i1> %not., <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, <4 x i1> %273, !dbg !252
IC: ADD:   %not. = xor <4 x i1> %271, <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: Visiting:   %not. = xor <4 x i1> %271, <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: Visiting:   %274 = select <4 x i1> %not., <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, <4 x i1> %273, !dbg !252
IC: ADD DEFERRED:   %not. = xor <4 x i1> %271, <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: Mod =   %274 = select <4 x i1> %not., <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, <4 x i1> %273, !dbg !252
    New =   %274 = select <4 x i1> %271, <4 x i1> %273, <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: ADD:   %274 = select <4 x i1> %271, <4 x i1> %273, <4 x i1> <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: ERASE   %not. = xor <4 x i1> %271, <i1 poison, i1 poison, i1 poison, i1 true>, !dbg !252
IC: ADD DEFERRED:   %271 = and <4 x i1> %broadcast.splat2008, %270, !dbg !252
...

Working on reducing the test case a bit, and if I can find a reproducer for the main trunk then I think we need to revert this patch.

[bjope]

Here is a reduced reproducer that goes into infinite loop with this patch:

; RUN: opt < %s -instcombine -S -o /dev/null

; This test case end up in an infinite loop with:
;    commit 5207cde5cb4147155c469e1861427ea9d569bd5a
;    Date:   Sun Apr 4 13:35:33 2021 +0900
;
;        [InstCombine] Conditionally fold select i1 into and/or

define dso_local void @main(i16* %in, i32* %out, i32 %a) local_unnamed_addr {
entry:
  %0 = load i16, i16* %in, align 1
  %conv456 = sext i16 %0 to i32
  %cmp468 = icmp sgt i16 %0, 0
  %broadcast.splatinsert2007 = insertelement <4 x i1> poison, i1 %cmp468, i32 0
  %broadcast.splat2008 = shufflevector <4 x i1> %broadcast.splatinsert2007, <4 x i1> poison, <4 x i32> zeroinitializer
  %broadcast.splatinsert2009 = insertelement <4 x i32> poison, i32 %conv456, i32 0
  %broadcast.splat2010 = shufflevector <4 x i32> %broadcast.splatinsert2009, <4 x i32> poison, <4 x i32> zeroinitializer
  %broadcast.splatinsert2005 = insertelement <4 x i32> poison, i32 %a, i32 0
  %broadcast.splat2006 = shufflevector <4 x i32> %broadcast.splatinsert2005, <4 x i32> poison, <4 x i32> zeroinitializer
  %1 = add <4 x i32> %broadcast.splat2006, <i32 1, i32 1, i32 1, i32 1>
  %2 = select <4 x i1> zeroinitializer, <4 x i32> zeroinitializer, <4 x i32> %1
  %3 = icmp slt <4 x i32> %2, zeroinitializer
  %4 = and <4 x i1> %broadcast.splat2008, %3
  %5 = add nsw <4 x i32> %2, <i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647>
  %6 = icmp slt <4 x i32> %5, %broadcast.splat2010
  %7 = select <4 x i1> %4, <4 x i1> %6, <4 x i1> zeroinitializer
  %8 = sub nsw <4 x i32> %broadcast.splat2010, %2
  %9 = select <4 x i1> zeroinitializer, <4 x i32> zeroinitializer, <4 x i32> %8
  %10 = xor <4 x i1> %7, <i1 true, i1 true, i1 true, i1 true>
  %predphi = select <4 x i1> %10, <4 x i32> %9, <4 x i32> zeroinitializer
  %11 = extractelement <4 x i32> %predphi, i32 1
  store i32 %11, i32* %out, align 1
  ret void
}

[spatel]

Apart from being unsafe, this pair of transforms also goes against the usual rule of not creating more instructions than we started with:

// select a, false, b -> select !a, b, false
if (match(TrueVal, m_Zero())) {
  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
  return SelectInst::Create(NotCond, FalseVal, Zero);
}
// select a, b, true -> select !a, true, b
if (match(FalseVal, m_One())) {
  Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
  return SelectInst::Create(NotCond, One, TrueVal);
}

I think we should just delete those (either with or without reverting this patch). We can add a safe transform for "select i1 %x, i1 0, i1 1 --> xor i1 %x, -1" to avoid a regression:
https://alive2.llvm.org/ce/z/Bhdy-Y

[nikic]

@spatel These are important canonicalization transforms, that allow us to treat logical and/or the same way as and/or in many other passes. There is shouldAvoidAbsorbingNotIntoSelect() to guard against infinite loops, and probably it needs to be applied in more places.

[spatel]

In D99674#2673844, @nikic wrote:

@spatel These are important canonicalization transforms, that allow us to treat logical and/or the same way as and/or in many other passes. There is shouldAvoidAbsorbingNotIntoSelect() to guard against infinite loops, and probably it needs to be applied in more places.

Ah - I stepped into the example here for a closer look. It's a vector partial-undef problem (conflicting with a demanded elements transform). I think we can avoid it by just making sure we're matching a true zero or one constant (no undef/poison elements).

Here's what I have the test down to:

define i32 @main(<2 x i1> %a, <2 x i1> %b, <2 x i32> %x, <2 x i32> %y) {
  %t5 = add nsw <2 x i32> %y, <i32 2147483647, i32 2147483647>
  %t6 = icmp slt <2 x i32> %t5, %x
  %ab = and <2 x i1> %a, %b
  %t7 = select <2 x i1> %ab, <2 x i1> %t6, <2 x i1> <i1 0, i1 poison>
  %t10 = xor <2 x i1> %t7, <i1 true, i1 poison>
  %p = select <2 x i1> %t10, <2 x i32> zeroinitializer, <2 x i32> %y
  %t11 = extractelement <2 x i32> %p, i32 0
  ret i32 %t11
}

[aqjune]

There hasn't been any performance regression reported (modulo the instruction cost issue, the patch of which was swiftly landed); maybe it is time to remove the folding.
I'll make the patch in a day or two.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

 //===- InstCombineSelect.cpp ----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) {
 
   if (Instruction *I = canonicalizeScalarSelectOfVecs(SI, *this))
     return I;
 
   CmpInst::Predicate Pred;
 
   if (SelType->isIntOrIntVectorTy(1) &&
       TrueVal->getType() == CondVal->getType()) {
-    if (match(TrueVal, m_One()) &&
-        (EnableUnsafeSelectTransform || impliesPoison(FalseVal, CondVal))) {
+    auto IsSafeToConvert = [&](Value *OtherVal) {
+      if (impliesPoison(OtherVal, CondVal))
+        return true;
+
+      if (!EnableUnsafeSelectTransform)
+        return false;
+
+      // We block this transformation if OtherVal or its operand can create
+      // poison. See PR49688
+      if (auto *Op = dyn_cast<Operator>(OtherVal)) {
+        if (canCreatePoison(Op))
+          return false;
+        if (propagatesPoison(Op) &&
+            llvm::any_of(Op->operand_values(), [](Value *V) {
+              return isa<Operator>(V) ? canCreatePoison(cast<Operator>(V))
+                                      : false;
+            }))
+          return false;
+      }
+      return true;
+    };
+    if (match(TrueVal, m_One()) && IsSafeToConvert(FalseVal)) {
       // Change: A = select B, true, C --> A = or B, C
       return BinaryOperator::CreateOr(CondVal, FalseVal);
     }
-    if (match(FalseVal, m_Zero()) &&
-        (EnableUnsafeSelectTransform || impliesPoison(TrueVal, CondVal))) {
+    if (match(FalseVal, m_Zero()) && IsSafeToConvert(TrueVal)) {
       // Change: A = select B, C, false --> A = and B, C
       return BinaryOperator::CreateAnd(CondVal, TrueVal);
     }
 
     auto *One = ConstantInt::getTrue(SelType);
     auto *Zero = ConstantInt::getFalse(SelType);
 
     // select a, false, b -> select !a, b, false

llvm/test/Transforms/InstCombine/and-fcmp.ll

 ;
   %ord1 = fcmp ninf ord float %c, 0.0
   %and = and i1 %ord1, %z
   %ord2 = fcmp ninf reassoc ord float %d, 0.0
   %r = and i1 %ord2, %and
   ret i1 %r
 }
 
+; TODO: this should be fixed using freeze
 define i1 @PR41069_commute_logical(i1 %z, float %c, float %d) {
 ; CHECK-LABEL: @PR41069_commute_logical(
-; CHECK-NEXT:    [[TMP1:%.*]] = fcmp ninf ord float [[D:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = and i1 [[TMP1]], [[Z:%.*]]
+; CHECK-NEXT:    [[ORD1:%.*]] = fcmp ninf ord float [[C:%.*]], 0.000000e+00
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[ORD1]], [[Z:%.*]]
+; CHECK-NEXT:    [[ORD2:%.*]] = fcmp reassoc ninf ord float [[D:%.*]], 0.000000e+00
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[ORD2]], i1 [[AND]], i1 false
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %ord1 = fcmp ninf ord float %c, 0.0
   %and = select i1 %ord1, i1 %z, i1 false
   %ord2 = fcmp ninf reassoc ord float %d, 0.0
   %r = select i1 %ord2, i1 %and, i1 false
   ret i1 %r
 }

llvm/test/Transforms/InstCombine/onehot_merge.ll

 
 define i1 @foo1_and_signbit_lshr_without_shifting_signbit_logical(i32 %k, i32 %c1, i32 %c2) {
 ; CHECK-LABEL: @foo1_and_signbit_lshr_without_shifting_signbit_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[K:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 0
 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[K]], [[C2:%.*]]
 ; CHECK-NEXT:    [[T4:%.*]] = icmp sgt i32 [[T3]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[T2]], [[T4]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T2]], i1 true, i1 [[T4]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 1, %c1
   %t1 = and i32 %t0, %k
   %t2 = icmp eq i32 %t1, 0
   %t3 = shl i32 %k, %c2
   %t4 = icmp sgt i32 %t3, -1
   %or = select i1 %t2, i1 true, i1 %t4

 
 define i1 @foo1_or_signbit_lshr_without_shifting_signbit_logical(i32 %k, i32 %c1, i32 %c2) {
 ; CHECK-LABEL: @foo1_or_signbit_lshr_without_shifting_signbit_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[K:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = icmp ne i32 [[T1]], 0
 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[K]], [[C2:%.*]]
 ; CHECK-NEXT:    [[T4:%.*]] = icmp slt i32 [[T3]], 0
-; CHECK-NEXT:    [[OR:%.*]] = and i1 [[T2]], [[T4]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T2]], i1 [[T4]], i1 false
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 1, %c1
   %t1 = and i32 %t0, %k
   %t2 = icmp ne i32 %t1, 0
   %t3 = shl i32 %k, %c2
   %t4 = icmp slt i32 %t3, 0
   %or = select i1 %t2, i1 %t4, i1 false
;
   %t0 = shl i32 %k, %c1
   %t1 = icmp sgt i32 %t0, -1
   %t2 = shl i32 %k, %c2
   %t3 = icmp sgt i32 %t2, -1
   %or = or i1 %t1, %t3
   ret i1 %or
 }
 
+; %t2 can be poison where as %t0 isn't; merging these two is unsafe.
 define i1 @foo1_and_signbit_lshr_without_shifting_signbit_both_sides_logical(i32 %k, i32 %c1, i32 %c2) {
 ; CHECK-LABEL: @foo1_and_signbit_lshr_without_shifting_signbit_both_sides_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 [[K:%.*]], [[C1:%.*]]
+; CHECK-NEXT:    [[T1:%.*]] = icmp sgt i32 [[T0]], -1
 ; CHECK-NEXT:    [[T2:%.*]] = shl i32 [[K]], [[C2:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[T0]], [[T2]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[TMP1]], -1
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[T3:%.*]] = icmp sgt i32 [[T2]], -1
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T1]], i1 true, i1 [[T3]]
+; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 %k, %c1
   %t1 = icmp sgt i32 %t0, -1
   %t2 = shl i32 %k, %c2
   %t3 = icmp sgt i32 %t2, -1
   %or = select i1 %t1, i1 true, i1 %t3
   ret i1 %or
 }
;
   %t0 = shl i32 %k, %c1
   %t1 = icmp slt i32 %t0, 0
   %t2 = shl i32 %k, %c2
   %t3 = icmp slt i32 %t2, 0
   %or = and i1 %t1, %t3
   ret i1 %or
 }
 
+; %t2 can be poison where as %t0 isn't; merging these two is unsafe.
 define i1 @foo1_or_signbit_lshr_without_shifting_signbit_both_sides_logical(i32 %k, i32 %c1, i32 %c2) {
 ; CHECK-LABEL: @foo1_or_signbit_lshr_without_shifting_signbit_both_sides_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 [[K:%.*]], [[C1:%.*]]
+; CHECK-NEXT:    [[T1:%.*]] = icmp slt i32 [[T0]], 0
 ; CHECK-NEXT:    [[T2:%.*]] = shl i32 [[K]], [[C2:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[T0]], [[T2]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i32 [[TMP1]], 0
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[T3:%.*]] = icmp slt i32 [[T2]], 0
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T1]], i1 [[T3]], i1 false
+; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 %k, %c1
   %t1 = icmp slt i32 %t0, 0
   %t2 = shl i32 %k, %c2
   %t3 = icmp slt i32 %t2, 0
   %or = select i1 %t1, i1 %t3, i1 false
   ret i1 %or
 }

 define i1 @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_shl1_logical(i32 %k, i32 %c1, i32 %c2, i32* %p) {
 ; CHECK-LABEL: @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_shl1_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    store i32 [[T0]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[K:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 0
 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[K]], [[C2:%.*]]
 ; CHECK-NEXT:    [[T4:%.*]] = icmp sgt i32 [[T3]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[T2]], [[T4]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T2]], i1 true, i1 [[T4]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 1, %c1
   store i32 %t0, i32* %p  ; extra use of shl
   %t1 = and i32 %t0, %k
   %t2 = icmp eq i32 %t1, 0
   %t3 = shl i32 %k, %c2
   %t4 = icmp sgt i32 %t3, -1

 define i1 @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_and_logical(i32 %k, i32 %c1, i32 %c2, i32* %p) {
 ; CHECK-LABEL: @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_and_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[K:%.*]]
 ; CHECK-NEXT:    store i32 [[T1]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 0
 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[K]], [[C2:%.*]]
 ; CHECK-NEXT:    [[T4:%.*]] = icmp sgt i32 [[T3]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[T2]], [[T4]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T2]], i1 true, i1 [[T4]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 1, %c1
   %t1 = and i32 %t0, %k
   store i32 %t1, i32* %p  ; extra use of and
   %t2 = icmp eq i32 %t1, 0
   %t3 = shl i32 %k, %c2
   %t4 = icmp sgt i32 %t3, -1

 define i1 @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_cmp1_logical(i32 %k, i32 %c1, i32 %c2, i1* %p) {
 ; CHECK-LABEL: @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_cmp1_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[K:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 0
 ; CHECK-NEXT:    store i1 [[T2]], i1* [[P:%.*]], align 1
 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[K]], [[C2:%.*]]
 ; CHECK-NEXT:    [[T4:%.*]] = icmp sgt i32 [[T3]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[T2]], [[T4]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T2]], i1 true, i1 [[T4]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 1, %c1
   %t1 = and i32 %t0, %k
   %t2 = icmp eq i32 %t1, 0
   store i1 %t2, i1* %p  ; extra use of cmp
   %t3 = shl i32 %k, %c2
   %t4 = icmp sgt i32 %t3, -1

 define i1 @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_shl2_logical(i32 %k, i32 %c1, i32 %c2, i32* %p) {
 ; CHECK-LABEL: @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_shl2_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[K:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 0
 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[K]], [[C2:%.*]]
 ; CHECK-NEXT:    store i32 [[T3]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[T4:%.*]] = icmp sgt i32 [[T3]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[T2]], [[T4]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T2]], i1 true, i1 [[T4]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 1, %c1
   %t1 = and i32 %t0, %k
   %t2 = icmp eq i32 %t1, 0
   %t3 = shl i32 %k, %c2
   store i32 %t3, i32* %p  ; extra use of shl
   %t4 = icmp sgt i32 %t3, -1

 define i1 @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_cmp2_logical(i32 %k, i32 %c1, i32 %c2, i1* %p) {
 ; CHECK-LABEL: @foo1_and_signbit_lshr_without_shifting_signbit_extra_use_cmp2_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[K:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 0
 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[K]], [[C2:%.*]]
 ; CHECK-NEXT:    [[T4:%.*]] = icmp sgt i32 [[T3]], -1
 ; CHECK-NEXT:    store i1 [[T4]], i1* [[P:%.*]], align 1
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[T2]], [[T4]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T2]], i1 true, i1 [[T4]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 1, %c1
   %t1 = and i32 %t0, %k
   %t2 = icmp eq i32 %t1, 0
   %t3 = shl i32 %k, %c2
   %t4 = icmp sgt i32 %t3, -1
   store i1 %t4, i1* %p  ; extra use of cmp

 
 define i1 @foo1_and_signbit_lshr_without_shifting_signbit_not_pwr2_logical(i32 %k, i32 %c1, i32 %c2) {
 ; CHECK-LABEL: @foo1_and_signbit_lshr_without_shifting_signbit_not_pwr2_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 3, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = and i32 [[T0]], [[K:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[T1]], 0
 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[K]], [[C2:%.*]]
 ; CHECK-NEXT:    [[T4:%.*]] = icmp sgt i32 [[T3]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[T2]], [[T4]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[T2]], i1 true, i1 [[T4]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %t0 = shl i32 3, %c1
   %t1 = and i32 %t0, %k
   %t2 = icmp eq i32 %t1, 0
   %t3 = shl i32 %k, %c2
   %t4 = icmp sgt i32 %t3, -1
   %or = select i1 %t2, i1 true, i1 %t4
   ret i1 %or
 }

llvm/test/Transforms/InstCombine/pr49688.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
+; %cmp should not vanish
 define i1 @f(i32 %i1) {
 ; CHECK-LABEL: @f(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 7, [[I1:%.*]]
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SHR]], [[I1]]
-; CHECK-NEXT:    ret i1 [[TMP0]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I1:%.*]], 0
+; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 7, [[I1]]
+; CHECK-NEXT:    [[CMP4:%.*]] = icmp slt i32 [[SHR]], [[I1]]
+; CHECK-NEXT:    [[I2:%.*]] = select i1 [[CMP]], i1 true, i1 [[CMP4]]
+; CHECK-NEXT:    ret i1 [[I2]]
 ;
 entry:
   %cmp = icmp slt i32 %i1, 0
   %shr = ashr i32 7, %i1
   %cmp4 = icmp sgt i32 %i1, %shr
   %i2 = select i1 %cmp, i1 true, i1 %cmp4
   ret i1 %i2
 }
 
+; %cmp should not vanish
 define i32 @f2(i32 signext %g, i32 zeroext %h) {
 ; CHECK-LABEL: @f2(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[G:%.*]], 0
 ; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 7, [[H:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[SHR]], [[G:%.*]]
-; CHECK-NEXT:    [[LOR_EXT:%.*]] = zext i1 [[TMP1]] to i32
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[SHR]], [[G]]
+; CHECK-NEXT:    [[DOT0:%.*]] = select i1 [[CMP]], i1 true, i1 [[CMP1]]
+; CHECK-NEXT:    [[LOR_EXT:%.*]] = zext i1 [[DOT0]] to i32
 ; CHECK-NEXT:    ret i32 [[LOR_EXT]]
 ;
   %cmp = icmp slt i32 %g, 0
   %shr = ashr i32 7, %h
   %cmp1 = icmp sgt i32 %g, %shr
   %.0 = select i1 %cmp, i1 true, i1 %cmp1
   %lor.ext = zext i1 %.0 to i32
   ret i32 %lor.ext
 }

llvm/test/Transforms/InstCombine/signed-truncation-check.ll

 ; CHECK-NEXT:    [[T2:%.*]] = icmp sgt i8 [[T1]], -1
 ; CHECK-NEXT:    call void @use1(i1 [[T2]])
 ; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[ARG]], 24
 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
 ; CHECK-NEXT:    [[T4:%.*]] = ashr exact i32 [[T3]], 24
 ; CHECK-NEXT:    call void @use32(i32 [[T4]])
 ; CHECK-NEXT:    [[T5:%.*]] = icmp eq i32 [[T4]], [[ARG]]
 ; CHECK-NEXT:    call void @use1(i1 [[T5]])
-; CHECK-NEXT:    [[T6:%.*]] = and i1 [[T2]], [[T5]]
+; CHECK-NEXT:    [[T6:%.*]] = select i1 [[T2]], i1 [[T5]], i1 false
 ; CHECK-NEXT:    ret i1 [[T6]]
 ;
   %t1 = trunc i32 %arg to i8
   call void @use8(i8 %t1)
   %t2 = icmp sgt i8 %t1, -1
   call void @use1(i1 %t2)
   %t3 = shl i32 %arg, 24
   call void @use32(i32 %t3)

llvm/test/Transforms/InstCombine/widenable-conditions.ll

;
   %lhs = and i1 %b, %wc
   %and = and i1 %lhs, %a
   ret i1 %and
 }
 
 define i1 @test1_logical(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test1_logical(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[WC]], [[B:%.*]]
+; CHECK-NEXT:    [[LHS:%.*]] = select i1 [[B:%.*]], i1 [[WC]], i1 false
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %lhs = select i1 %b, i1 %wc, i1 false
   %and = select i1 %lhs, i1 %a, i1 false
   ret i1 %and
 }
;
   call void @use(i1 %lhs)
   %and = and i1 %lhs, %a
   ret i1 %and
 }
 
 define i1 @test1b_logical(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test1b_logical(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[WC]], [[B:%.*]]
+; CHECK-NEXT:    [[LHS:%.*]] = select i1 [[B:%.*]], i1 [[WC]], i1 false
 ; CHECK-NEXT:    call void @use(i1 [[LHS]])
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %lhs = select i1 %b, i1 %wc, i1 false
   call void @use(i1 %lhs)
   %and = select i1 %lhs, i1 %a, i1 false

 }
 
 define i1 @test1c_logical(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test1c_logical(
 ; CHECK-NEXT:    call void @use(i1 [[A:%.*]])
 ; CHECK-NEXT:    call void @use(i1 [[B:%.*]])
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    call void @use(i1 [[WC]])
-; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[WC]], [[B]]
+; CHECK-NEXT:    [[LHS:%.*]] = select i1 [[B]], i1 [[WC]], i1 false
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[A]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   call void @use(i1 %a)
   call void @use(i1 %b)
   %wc = call i1 @llvm.experimental.widenable.condition()
   call void @use(i1 %wc)
   %lhs = select i1 %b, i1 %wc, i1 false
;
   %and = and i1 %lhs, %rhs
   ret i1 %and
 }
 
 define i1 @test3_logical(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @test3_logical(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[RHS:%.*]] = and i1 [[WC]], [[C:%.*]]
+; CHECK-NEXT:    [[RHS:%.*]] = select i1 [[C:%.*]], i1 [[WC]], i1 false
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[RHS]]
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %lhs = select i1 %a, i1 %b, i1 false
   %rhs = select i1 %c, i1 %wc, i1 false
   %and = select i1 %lhs, i1 %rhs, i1 false
   ret i1 %and
;
   ret i1 %and
 }
 
 define i1 @test4_logical(i1 %a, i1 %b, i1 %c) {
 ; CHECK-LABEL: @test4_logical(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[LHS:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[RHS:%.*]] = and i1 [[WC]], [[C:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[LHS]], [[RHS]]
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[LHS]], i1 [[RHS]], i1 false
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %lhs = select i1 %a, i1 %b, i1 false
   %rhs = select i1 %wc, i1 %c, i1 false
   %and = select i1 %lhs, i1 %rhs, i1 false
   ret i1 %and
 }
;
   %and = and i1 %wc, %wc2
   ret i1 %and
 }
 
 define i1 @test6_logical(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test6_logical(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[WC2:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[WC2]]
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[WC]], i1 [[WC2]], i1 false
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %wc2 = call i1 @llvm.experimental.widenable.condition()
   %and = select i1 %wc, i1 %wc2, i1 false
   ret i1 %and
 }
 
;
   ret i1 %and
 }
 
 define i1 @test7_logical(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test7_logical(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    call void @use(i1 [[WC]])
 ; CHECK-NEXT:    [[WC2:%.*]] = call i1 @llvm.experimental.widenable.condition()
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[WC2]]
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[WC]], i1 [[WC2]], i1 false
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   call void @use(i1 %wc)
   %wc2 = call i1 @llvm.experimental.widenable.condition()
   %and = select i1 %wc, i1 %wc2, i1 false
   ret i1 %and
 }
;
   ret i1 %and
 }
 
 define i1 @test8_logical(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test8_logical(
 ; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[WC2:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    call void @use(i1 [[WC2]])
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[WC]], [[WC2]]
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[WC]], i1 [[WC2]], i1 false
 ; CHECK-NEXT:    ret i1 [[AND]]
 ;
   %wc = call i1 @llvm.experimental.widenable.condition()
   %wc2 = call i1 @llvm.experimental.widenable.condition()
   call void @use(i1 %wc2)
   %and = select i1 %wc, i1 %wc2, i1 false
   ret i1 %and
 }
 
 
 declare void @use(i1)
 declare i1 @llvm.experimental.widenable.condition()