[InstCombine] generalize select + select/and/or folding using implied conditions

[aqjune]

Summary

This patch optimizes the remaining possible cases in D101191 by generalizing isImpliedCondition()-based
foldings.

Assume that there is op a, (select b, _, _) where op is one of and i1, or i1 or their select forms.

We can do the following optimization based on the result of isImpliedCondition(a, b):

If a = true implies…

• b = true:
  • select a, (select b, A, B), false => select a, A, false : https://alive2.llvm.org/ce/z/WCnZYh
  • and a, (select b, A, B) => select a, A, false : https://alive2.llvm.org/ce/z/uZhcMG
• b = false:
  • select a, (select b, A, B), false => select a, B, false : https://alive2.llvm.org/ce/z/c2hJpV
  • and a, (select b, A, B) => select a, B, false : https://alive2.llvm.org/ce/z/5ggwMM

If a = false implies…

• b = true:
  • select a, true, (select b, A, B) => select a, true, A : https://alive2.llvm.org/ce/z/tidKvH
  • or a, (select b, A, B) => select a, true, A : https://alive2.llvm.org/ce/z/cC-uyb
• b = false:
  • select a, true, (select b, A, B) => select a, true, B : https://alive2.llvm.org/ce/z/ZXpJq9
  • or a, (select b, A, B) => select a, true, B : https://alive2.llvm.org/ce/z/hnDrJj

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1881

/* IsAnd */ true etc

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2596

I'm not sure about this assert. Can't you end up with an i1 CondVal, but an <n x i1> SI here?

2628

Don't think we need this.

2757

Missing indent

[aqjune]

address comments

[aqjune]

remove assertion

[aqjune]

missing /* IsAnd */

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2596

To clarify, I do think you need to check for that case, but as a normal condition, not an assert. You do check this before calling the helper for the and/or case, but I don't think anything ensures it for the case where the root instruction is a select.

Could you please add a test for this kind of scalar/vector mismatch?

[aqjune]

add vector test

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2596

I think removing runtime check is fine: isImpliedCondition is handling this case well (simply returning None currently). Also, the created SelectInst does not contain Cond as well.
If isImpliesCondition is enhanced to deal with vector+nonvector ops, this code gets benefit as well.

I added the scalar/vector code mismatch test as well (a_true_implies_b_true_vec).

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2596

Okay, if isImpliedCondition already checks this, then it's fine. In that case, should we also drop the type check when this helper is called for and/or?

[aqjune]

• Relax the condition at and/or
• Add an assertion that Op should be i1 or vec i1
• Add missing updates in select-safe-bool-transform.ll, revive one deleting code because it caused regression

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2596

It needed i1 or vec i1 check, but it could be relaxed as suggested, thanks.

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2573

if (auto *SI0 = dyn_cast<SelectInst>(Op0)) would be more idiomatic, I think.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2615

a = true etc in these comments should be op = true.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2615

And b = true should be cond = true :)

[aqjune]

Address comments

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 //===- InstCombineAndOrXor.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
 //
 //===----------------------------------------------------------------------===//
 //
if (match(&I, m_And(m_OneUse(m_Shl(m_ZExt(m_Value(X)), m_Value(Y))),
     SanitizedSignMask =
         Constant::mergeUndefsWith(SanitizedSignMask, cast<Constant>(Y));
     return BinaryOperator::CreateAnd(SExt, SanitizedSignMask);
   }
 
   if (Instruction *Z = narrowMaskedBinOp(I))
     return Z;
 
+  if (I.getType()->isIntOrIntVectorTy(1)) {
+    auto *SI0 = dyn_cast<SelectInst>(Op0), *SI1 = dyn_cast<SelectInst>(Op1);
+    if (SI0) {
+      if (auto *I =
+              foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ true))
+        return I;
+    }
+    if (SI1) {
+      if (auto *I =
+              foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ true))
+        return I;
+    }
+  }
+
   if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
     return FoldedLogic;
 
   if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
     return DeMorgan;
 
   {
     Value *A, *B, *C;
Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
 
   // (A&B)|(A&C) -> A&(B|C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyBSwap(I, Builder))
     return replaceInstUsesWith(I, V);
 
+  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+  if (I.getType()->isIntOrIntVectorTy(1)) {
+    auto *SI0 = dyn_cast<SelectInst>(Op0), *SI1 = dyn_cast<SelectInst>(Op1);
+    if (SI0) {
+      if (auto *I =
+              foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ false))
+        return I;
+    }
+    if (SI1) {
+      if (auto *I =
+              foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ false))
+        return I;
+    }
+  }
+
   if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I))
     return FoldedLogic;
 
   if (Instruction *BSwap = matchBSwapOrBitReverse(I, /*MatchBSwaps*/ true,
                                                   /*MatchBitReversals*/ false))
     return BSwap;
 
   if (Instruction *Funnel = matchFunnelShift(I, *this))
     return Funnel;
 
   if (Instruction *Concat = matchOrConcat(I, Builder))
     return replaceInstUsesWith(I, Concat);
 
   Value *X, *Y;
   const APInt *CV;
   if (match(&I, m_c_Or(m_OneUse(m_Xor(m_Value(X), m_APInt(CV))), m_Value(Y))) &&
       !CV->isAllOnesValue() && MaskedValueIsZero(Y, *CV, 0, &I)) {
     // (X ^ C) | Y -> (X | Y) ^ C iff Y & C == 0
     // The check for a 'not' op is for efficiency (if Y is known zero --> ~X).
     Value *Or = Builder.CreateOr(X, Y);
     return BinaryOperator::CreateXor(Or, ConstantInt::get(I.getType(), *CV));
   }
 
   // (A & C)|(B & D)
-  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   Value *A, *B, *C, *D;
   if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
       match(Op1, m_And(m_Value(B), m_Value(D)))) {
     // (A & C1)|(B & C2)
     ConstantInt *C1, *C2;
     if (match(C, m_ConstantInt(C1)) && match(D, m_ConstantInt(C2))) {
       Value *V1 = nullptr, *V2 = nullptr;
       if ((C1->getValue() & C2->getValue()).isNullValue()) {

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

 //===- InstCombineInternal.h - InstCombine pass internals -------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
private:
   Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
                                        BinaryOperator &Logic);
   Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
   Value *getSelectCondition(Value *A, Value *B);
 
   Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
   Instruction *foldFPSignBitOps(BinaryOperator &I);
 
+  // Optimize one of these forms:
+  //   and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
+  //   or i1 Op, SI  / select i1 Op, i1 true, i1 SI  (if IsAnd = false)
+  // into simplier select instruction using isImpliedCondition.
+  Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
+                                                 bool IsAnd);
+
 public:
   /// Inserts an instruction \p New before instruction \p Old
   ///
   /// Also adds the new instruction to the worklist and returns \p New so that
   /// it is suitable for use as the return from the visitation patterns.
   Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
     assert(New && !New->getParent() &&
            "New instruction already inserted into a basic block!");

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
 //
 //===----------------------------------------------------------------------===//
 //
if (FI->hasOneUse() &&
       match(Cond, m_c_ICmp(Pred, m_Specific(TrueVal), m_Specific(FalseVal))) &&
       (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)) {
     return Pred == ICmpInst::ICMP_EQ ? FalseVal : TrueVal;
   }
 
   return nullptr;
 }
 
+Instruction *InstCombinerImpl::foldAndOrOfSelectUsingImpliedCond(Value *Op,
+                                                                 SelectInst &SI,
+                                                                 bool IsAnd) {
+  Value *CondVal = SI.getCondition();
+  Value *A = SI.getTrueValue();
+  Value *B = SI.getFalseValue();
+
+  assert(Op->getType()->isIntOrIntVectorTy(1) &&
+         "Op must be either i1 or vector of i1.");
+
+  Optional<bool> Res = isImpliedCondition(Op, CondVal, DL, IsAnd);
+  if (!Res)
+    return nullptr;
+
+  Value *Zero = Constant::getNullValue(A->getType());
+  Value *One = Constant::getAllOnesValue(A->getType());
+
+  if (*Res == true) {
+    if (IsAnd)
+      // select op, (select cond, A, B), false => select op, A, false
+      // and    op, (select cond, A, B)        => select op, A, false
+      //   if op = true implies b = true.
+      return SelectInst::Create(Op, A, Zero);
+    else
+      // select op, true, (select cond, A, B) => select op, true, A
+      // or     op, (select cond, A, B)       => select op, true, A
+      //   if a = false implies b = true.
+      return SelectInst::Create(Op, One, A);
+  } else {
+    if (IsAnd)
+      // select op, (select cond, A, B), false => select op, B, false
+      // and    op, (select cond, A, B)        => select op, B, false
+      //   if a = true implies b = false.
+      return SelectInst::Create(Op, B, Zero);
+    else
+      // select op, true, (select cond, A, B) => select op, true, B
+      // or     op, (select cond, A, B)       => select op, true, B
+      //   if a = false implies b = false.
+      return SelectInst::Create(Op, One, B);
+  }
+}
+
 Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) {
   Value *CondVal = SI.getCondition();
   Value *TrueVal = SI.getTrueValue();
   Value *FalseVal = SI.getFalseValue();
   Type *SelType = SI.getType();
 
   // FIXME: Remove this workaround when freeze related patches are done.
   // For select with undef operand which feeds into an equality comparison,
if (match(FalseVal, m_Zero()) || match(TrueVal, m_One())) {
       bool IsAnd = match(FalseVal, m_Zero()) ? true : false;
       Value *Op1 = IsAnd ? TrueVal : FalseVal;
       if (isCheckForZeroAndMulWithOverflow(CondVal, Op1, IsAnd, Y)) {
         auto *FI = new FreezeInst(*Y, (*Y)->getName() + ".fr");
         InsertNewInstBefore(FI, *cast<Instruction>(Y->getUser()));
         replaceUse(*Y, FI);
         return replaceInstUsesWith(SI, Op1);
       }
+
+      if (auto *Op1SI = dyn_cast<SelectInst>(Op1))
+        if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI,
+                                                        /* IsAnd */ IsAnd))
+          return I;
     }
 
     // select (select a, true, b), c, false -> select a, c, false
     // select c, (select a, true, b), false -> select c, a, false
     //   if c implies that b is false.
     if (match(CondVal, m_Select(m_Value(A), m_One(), m_Value(B))) &&
         match(FalseVal, m_Zero())) {
       Optional<bool> Res = isImpliedCondition(TrueVal, B, DL);

llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll

;
   %c = select i1 %B, i1 %A, i1 false
   %res = and i1 %c, %A
   ret i1 %res
 }
 
 ; (A land B) lor A
 define i1 @land_lor_left1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_lor_left1(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[C]], [[A]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %A, i1 %B, i1 false
   %res = select i1 %c, i1 true, i1 %A
   ret i1 %res
 }
 define i1 @land_lor_left2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_lor_left2(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], i1 true, i1 [[A]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %B, i1 %A, i1 false
   %res = select i1 %c, i1 true, i1 %A
   ret i1 %res
 }
 
 ; (A land B) bor A
 define i1 @land_bor_left1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_bor_left1(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[C]], [[A]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %A, i1 %B, i1 false
   %res = or i1 %c, %A
   ret i1 %res
 }
 define i1 @land_bor_left2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_bor_left2(
 ; CHECK-NEXT:    ret i1 [[A:%.*]]
;
   %c = and i1 %B, %A
   %res = select i1 %c, i1 true, i1 %A
   ret i1 %res
 }
 
 ; (A lor B) land A
 define i1 @lor_land_left1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_land_left1(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[C]], [[A]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %A, i1 true, i1 %B
   %res = select i1 %c, i1 %A, i1 false
   ret i1 %res
 }
 define i1 @lor_land_left2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_land_left2(
 ; CHECK-NEXT:    [[C:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
 ; CHECK-NEXT:    [[RES:%.*]] = select i1 [[C]], i1 [[A]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %c = select i1 %B, i1 true, i1 %A
   %res = select i1 %c, i1 %A, i1 false
   ret i1 %res
 }
 
 ; (A lor B) band A
 define i1 @lor_band_left1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_band_left1(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[C]], [[A]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %A, i1 true, i1 %B
   %res = and i1 %c, %A
   ret i1 %res
 }
 define i1 @lor_band_left2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_band_left2(
 ; CHECK-NEXT:    ret i1 [[A:%.*]]
;
   %c = select i1 %B, i1 %A, i1 false
   %res = select i1 %A, i1 true, i1 %c
   ret i1 %res
 }
 
 ; A bor (A land B)
 define i1 @land_bor_right1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_bor_right1(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[C]], [[A]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %A, i1 %B, i1 false
   %res = or i1 %A, %c
   ret i1 %res
 }
 define i1 @land_bor_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @land_bor_right2(
 ; CHECK-NEXT:    ret i1 [[A:%.*]]
;
   %c = select i1 %B, i1 true, i1 %A
   %res = select i1 %A, i1 %c, i1 false
   ret i1 %res
 }
 
 ; A band (A lor B)
 define i1 @lor_band_right1(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_band_right1(
-; CHECK-NEXT:    [[C:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[C]], [[A]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 [[A:%.*]]
 ;
   %c = select i1 %A, i1 true, i1 %B
   %res = and i1 %A, %c
   ret i1 %res
 }
 define i1 @lor_band_right2(i1 %A, i1 %B) {
 ; CHECK-LABEL: @lor_band_right2(
 ; CHECK-NEXT:    ret i1 [[A:%.*]]

llvm/test/Transforms/InstCombine/select-safe-impliedcond-transforms.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine-unsafe-select-transform=0 -instcombine -S | FileCheck %s
 
 define i1 @a_true_implies_b_true(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_true_implies_b_true(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 20
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[Z]], 10
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[SEL]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[X:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 20
   %b = icmp ugt i8 %z, 10
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = select i1 %a, i1 %sel, i1 false
   ret i1 %res
 }
;
   %sel = select i1 %b, <2 x i1> %X, <2 x i1> %Y
   %res = select <2 x i1> %a, <2 x i1> %sel, <2 x i1> zeroinitializer
   ret <2 x i1> %res
 }
 
 define i1 @a_true_implies_b_true2(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_true_implies_b_true2(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 20
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[Z]], 10
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[A]], [[SEL]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[X:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 20
   %b = icmp ugt i8 %z, 10
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = and i1 %a, %sel
   ret i1 %res
 }
 
 define i1 @a_true_implies_b_true2_comm(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_true_implies_b_true2_comm(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 20
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[Z]], 10
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[SEL]], [[A]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[X:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 20
   %b = icmp ugt i8 %z, 10
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = and i1 %sel, %a
   ret i1 %res
 }
 
 define i1 @a_true_implies_b_false(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_true_implies_b_false(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 20
-; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[Z]], 10
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[SEL]], i1 false
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[Y:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 20
   %b = icmp ult i8 %z, 10
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = select i1 %a, i1 %sel, i1 false
   ret i1 %res
 }
 
 define i1 @a_true_implies_b_false2(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_true_implies_b_false2(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 20
-; CHECK-NEXT:    [[B:%.*]] = icmp eq i8 [[Z]], 10
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[A]], [[SEL]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[Y:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 20
   %b = icmp eq i8 %z, 10
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = and i1 %a, %sel
   ret i1 %res
 }
 
 define i1 @a_true_implies_b_false2_comm(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_true_implies_b_false2_comm(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 20
-; CHECK-NEXT:    [[B:%.*]] = icmp eq i8 [[Z]], 10
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = and i1 [[SEL]], [[A]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 [[Y:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 20
   %b = icmp eq i8 %z, 10
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = and i1 %sel, %a
   ret i1 %res
 }
 
 define i1 @a_false_implies_b_true(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_false_implies_b_true(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 10
-; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[Z]], 20
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[SEL]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 10
   %b = icmp ult i8 %z, 20
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = select i1 %a, i1 true, i1 %sel
   ret i1 %res
 }
 
 define i1 @a_false_implies_b_true2(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_false_implies_b_true2(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 10
-; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[Z]], 20
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[A]], [[SEL]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 10
   %b = icmp ult i8 %z, 20
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = or i1 %a, %sel
   ret i1 %res
 }
 
 define i1 @a_false_implies_b_true2_comm(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_false_implies_b_true2_comm(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 10
-; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[Z]], 20
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[SEL]], [[A]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[X:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 10
   %b = icmp ult i8 %z, 20
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = or i1 %sel, %a
   ret i1 %res
 }
 
 define i1 @a_false_implies_b_false(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_false_implies_b_false(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 10
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[Z]], 20
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[SEL]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 10
   %b = icmp ugt i8 %z, 20
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = select i1 %a, i1 true, i1 %sel
   ret i1 %res
 }
 
 define i1 @a_false_implies_b_false2(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_false_implies_b_false2(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 10
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[Z]], 20
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[A]], [[SEL]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 10
   %b = icmp ugt i8 %z, 20
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = or i1 %a, %sel
   ret i1 %res
 }
 
 define i1 @a_false_implies_b_false2_comm(i8 %z, i1 %X, i1 %Y) {
 ; CHECK-LABEL: @a_false_implies_b_false2_comm(
 ; CHECK-NEXT:    [[A:%.*]] = icmp ugt i8 [[Z:%.*]], 10
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[Z]], 20
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[B]], i1 [[X:%.*]], i1 [[Y:%.*]]
-; CHECK-NEXT:    [[RES:%.*]] = or i1 [[SEL]], [[A]]
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[A]], i1 true, i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %a = icmp ugt i8 %z, 10
   %b = icmp ugt i8 %z, 20
   %sel = select i1 %b, i1 %X, i1 %Y
   %res = or i1 %sel, %a
   ret i1 %res
 }