[InstCombine] Fold logic-and/logic-or by distributive laws

[bcl5980]

Summary

X && Z || Y && Z --> (X || Y) && Z
https://alive2.llvm.org/ce/z/nM6kZb

(X || Z) && (Y || Z) --> (X && Y) || Z
https://alive2.llvm.org/ce/z/_EWLRR

Fix: https://github.com/llvm/llvm-project/issues/53861

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2799

Sorry if I've missed something (looooong day) - but how can this match as a SelectInst if its already matched as m_LogicalAnd above?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2799

/// Matches L && R either in the form of L & R or L ? R : false.
/// Note that the latter form is poison-blocking.
template <typename LHS, typename RHS>
inline LogicalOp_match<LHS, RHS, Instruction::And> m_LogicalAnd(const LHS &L,
                                                                const RHS &R) {
  return LogicalOp_match<LHS, RHS, Instruction::And>(L, R);
}

/// Matches L && R where L and R are arbitrary values.
inline auto m_LogicalAnd() { return m_LogicalAnd(m_Value(), m_Value()); }

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2799

Cheers - so what do we gain from matching with m_LogicalAnd first and then checking isa<SelectInst> ?

[bcl5980]

fix tests.

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2799

Hi @RKSimon , this should be first part of this change. Later I will send two folllow up patch for the case like:
and + and + select, and + select + select.
So check the m_LogicalAnd first is necessary.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2795

Use the same names as the code for consistency:

// (A && B) || (C && B) --> (A || C) && B

With logical-and/or, the pattern is not commutative. I think the code is correct, but it might be better to put this kind of label just above the line that does the transform, so it is clear that order of the common operand does matter.

[bcl5980]

address comments

[nikic]

Did this get subsumed by https://github.com/llvm/llvm-project/commit/9ddff66d0c9c3e18d56e6b20aa26a2a8cdfb6d2b?

[bcl5980]

rebase code

[bcl5980]

In D139408#3987800, @nikic wrote:

Did this get subsumed by https://github.com/llvm/llvm-project/commit/9ddff66d0c9c3e18d56e6b20aa26a2a8cdfb6d2b?

I rebase the code.
I think rG9ddff66d0c9c3e18d56e6b20aa26a2a8cdfb6d2b can cover part of this path. And it can't cover some cases like:

@logic_and_logic_or_3
@logic_and_logic_or_4
@logic_and_logic_or_6
@logic_and_logic_or_7

If any of you think this is redundant I can abandon it.

[spatel]

I'm not sure how much overlap we have vs. generality for these kinds of patterns, but this is still showing improvements, so LGTM.

[lebedev.ri]

This patch is not rebased, as per the test diffs.

[bcl5980]

In D139408#3991865, @lebedev.ri wrote:

This patch is not rebased, as per the test diffs.

Do you mean rGa888825aeef8d6592c6cf5f4e5854cc39af49633 update test will add {{[^@]+}} for every test?
It looks latest code already revert it by rG697bfa40a3f853d8b9103ead53cd80a4f7c5a7df.

[lebedev.ri]

In D139408#3992943, @bcl5980 wrote:

In D139408#3991865, @lebedev.ri wrote:

This patch is not rebased, as per the test diffs.

Do you mean rGa888825aeef8d6592c6cf5f4e5854cc39af49633 update test will add {{[^@]+}} for every test?
It looks latest code already revert it by rG697bfa40a3f853d8b9103ead53cd80a4f7c5a7df.

No, i'm saying that the test diff was showing spurious/misleading changes.
As you've noted, many of those tests (e.g. @logic_and_logic_or_1) got handled
in another patch, but the diff was still showing as-if they weren't handled before this patch.

[chfast]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2804

The new created select instructions do not copy metadata from the original ones. Is this worth doing so?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

2804

I don't think metadata can be safely preserved in this transform.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

Instruction *InstCombinerImpl::foldSelectOfBools(SelectInst &SI) {
 
   // Avoid potential infinite loops by checking for non-constant condition.
   // TODO: Can we assert instead by improving canonicalizeSelectToShuffle()?
   //       Scalar select must have simplified?
   if (!SelType->isIntOrIntVectorTy(1) || isa<Constant>(CondVal) ||
       TrueVal->getType() != CondVal->getType())
     return nullptr;
 
+  auto *One = ConstantInt::getTrue(SelType);
+  auto *Zero = ConstantInt::getFalse(SelType);
+  Value *A, *B, *C, *D;
+
   // Folding select to and/or i1 isn't poison safe in general. impliesPoison
   // checks whether folding it does not convert a well-defined value into
   // poison.
   if (match(TrueVal, m_One())) {
     if (impliesPoison(FalseVal, CondVal)) {
       // Change: A = select B, true, C --> A = or B, C
       return BinaryOperator::CreateOr(CondVal, FalseVal);
     }
 
     if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
       if (auto *RHS = dyn_cast<FCmpInst>(FalseVal))
         if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false,
                                         /*IsSelectLogical*/ true))
           return replaceInstUsesWith(SI, V);
+
+    // (A && B) || (C && B) --> (A || C) && B
+    if (match(CondVal, m_LogicalAnd(m_Value(A), m_Value(B))) &&
+        match(FalseVal, m_LogicalAnd(m_Value(C), m_Value(D))) &&
+        (CondVal->hasOneUse() || FalseVal->hasOneUse())) {
+      bool CondLogicAnd = isa<SelectInst>(CondVal);
+      bool FalseLogicAnd = isa<SelectInst>(FalseVal);
+      if (CondLogicAnd && FalseLogicAnd) {
+        // (A ? B : 0) ? 1 : (A ? D : 0) --> A ? (B ? 1 : D) : 0
+        if (A == C)
+          return SelectInst::Create(A, Builder.CreateSelect(B, One, D), Zero);
+        // (A ? B : 0) ? 1 : (C ? A : 0) --> A ? (B ? 1 : C) : 0
+        if (A == D)
+          return SelectInst::Create(A, Builder.CreateSelect(B, One, C), Zero);
+        // (A ? B : 0) ? 1 : (B ? D : 0) --> B ? (A ? 1 : D) : 0
+        if (B == C)
+          return SelectInst::Create(B, Builder.CreateSelect(A, One, D), Zero);
+        // (A ? B : 0) ? 1 : (C ? B : 0) --> (A ? 1 : C) ? B : 0
+        if (B == D)
+          return SelectInst::Create(Builder.CreateSelect(A, One, C), B, Zero);
       }
+    }
+  }
+
   if (match(FalseVal, m_Zero())) {
     if (impliesPoison(TrueVal, CondVal)) {
       // Change: A = select B, C, false --> A = and B, C
       return BinaryOperator::CreateAnd(CondVal, TrueVal);
     }
 
     if (auto *LHS = dyn_cast<FCmpInst>(CondVal))
       if (auto *RHS = dyn_cast<FCmpInst>(TrueVal))
         if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true,
                                         /*IsSelectLogical*/ true))
           return replaceInstUsesWith(SI, V);
-  }
 
-  auto *One = ConstantInt::getTrue(SelType);
-  auto *Zero = ConstantInt::getFalse(SelType);
+    // (A || B) && (C || B) --> (A && C) || B
+    if (match(CondVal, m_LogicalOr(m_Value(A), m_Value(B))) &&
+        match(TrueVal, m_LogicalOr(m_Value(C), m_Value(D))) &&
+        (CondVal->hasOneUse() || TrueVal->hasOneUse())) {
+      bool CondLogicOr = isa<SelectInst>(CondVal);
+      bool TrueLogicOr = isa<SelectInst>(TrueVal);
+      if (CondLogicOr && TrueLogicOr) {
+        // (A ? 1 : B) ? (A ? 1 : D) : 0 --> A ? 1 : (B ? D : 0)
+        if (A == C)
+          return SelectInst::Create(A, One, Builder.CreateSelect(B, D, Zero));
+        // (A ? 1 : B) ? (C ? 1 : A) : 0 --> A ? 1 : (B ? C : 0)
+        if (A == D)
+          return SelectInst::Create(A, One, Builder.CreateSelect(B, C, Zero));
+        // (A ? 1 : B) ? (B ? 1 : D) : 0 --> B ? 1 : (A ? D : 0)
+        if (B == C)
+          return SelectInst::Create(B, One, Builder.CreateSelect(A, D, Zero));
+        // (A ? 1 : B) ? (C ? 1 : B) : 0 --> (A ? C : 0) ? 1 : B
+        if (B == D)
+          return SelectInst::Create(Builder.CreateSelect(A, C, Zero), One, B);
+      }
+    }
+  }
 
   // We match the "full" 0 or 1 constant here to avoid a potential infinite
   // loop with vectors that may have undefined/poison elements.
   // select a, false, b -> select !a, b, false
   if (match(TrueVal, m_Specific(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_Specific(One))) {
     Value *NotCond = Builder.CreateNot(CondVal, "not." + CondVal->getName());
     return SelectInst::Create(NotCond, One, TrueVal);
   }
 
-  Value *A, *B;
-
   // DeMorgan in select form: !a && !b --> !(a || b)
   // select !a, !b, false --> not (select a, true, b)
   if (match(&SI, m_LogicalAnd(m_Not(m_Value(A)), m_Not(m_Value(B)))) &&
       (CondVal->hasOneUse() || TrueVal->hasOneUse()) &&
       !match(A, m_ConstantExpr()) && !match(B, m_ConstantExpr()))
     return BinaryOperator::CreateNot(Builder.CreateSelect(A, One, B));
 
   // DeMorgan in select form: !a || !b --> !(a && b)
if (match(CondVal, m_Select(m_Value(A), m_Value(B), m_Zero())) &&
       match(TrueVal, m_Specific(B)) && match(FalseVal, m_Zero()))
     return replaceOperand(SI, 0, A);
 
   // ~(A & B) & (A | B) --> A ^ B
   if (match(&SI, m_c_LogicalAnd(m_Not(m_LogicalAnd(m_Value(A), m_Value(B))),
                                 m_c_LogicalOr(m_Deferred(A), m_Deferred(B)))))
     return BinaryOperator::CreateXor(A, B);
 
-  Value *C;
   // select (~a | c), a, b -> and a, (or c, freeze(b))
   if (match(CondVal, m_c_Or(m_Not(m_Specific(TrueVal)), m_Value(C))) &&
       CondVal->hasOneUse()) {
     FalseVal = Builder.CreateFreeze(FalseVal);
     return BinaryOperator::CreateAnd(TrueVal, Builder.CreateOr(C, FalseVal));
   }
   // select (~c & b), a, b -> and b, (or freeze(a), c)
   if (match(CondVal, m_c_And(m_Not(m_Value(C)), m_Specific(FalseVal))) &&

llvm/test/Transforms/InstCombine/select-factorize.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=instcombine -S < %s | FileCheck %s
 
 declare void @use(i1)
 
 define i1 @logic_and_logic_or_1(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_and_logic_or_1(
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[BC]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 false
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %c, i1 %a, i1 false
   %bc = select i1 %c, i1 %b, i1 false
   %or = select i1 %ac, i1 true, i1 %bc
   ret i1 %or
 }
 
 define i1 @logic_and_logic_or_2(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_and_logic_or_2(
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[BC]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 false
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %a, i1 %c, i1 false
   %bc = select i1 %c, i1 %b, i1 false
   %or = select i1 %ac, i1 true, i1 %bc
   ret i1 %or
 }
 
 define i1 @logic_and_logic_or_3(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_and_logic_or_3(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[A:%.*]], i1 [[C:%.*]], i1 false
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[B:%.*]], i1 [[C]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[AC]], i1 true, i1 [[BC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[TMP1]], i1 [[C:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %a, i1 %c, i1 false
   %bc = select i1 %b, i1 %c, i1 false
   %or = select i1 %ac, i1 true, i1 %bc
   ret i1 %or
 }
 
 define i1 @logic_and_logic_or_4(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_and_logic_or_4(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[C:%.*]], i1 [[A:%.*]], i1 false
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[B:%.*]], i1 [[C]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[AC]], i1 true, i1 [[BC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[B:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 false
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %c, i1 %a, i1 false
   %bc = select i1 %b, i1 %c, i1 false
   %or = select i1 %ac, i1 true, i1 %bc
   ret i1 %or
 }
 
 define i1 @logic_and_logic_or_5(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_and_logic_or_5(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[AC]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 false
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %c, i1 %a, i1 false
   %bc = select i1 %c, i1 %b, i1 false
   %or = select i1 %bc, i1 true, i1 %ac
   ret i1 %or
 }
 
 define i1 @logic_and_logic_or_6(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_and_logic_or_6(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[A:%.*]], i1 [[C:%.*]], i1 false
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[C]], i1 [[B:%.*]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[BC]], i1 true, i1 [[AC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 false
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %a, i1 %c, i1 false
   %bc = select i1 %c, i1 %b, i1 false
   %or = select i1 %bc, i1 true, i1 %ac
   ret i1 %or
 }
 
 define i1 @logic_and_logic_or_7(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_and_logic_or_7(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[A:%.*]], i1 [[C:%.*]], i1 false
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[B:%.*]], i1 [[C]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[BC]], i1 true, i1 [[AC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[TMP1]], i1 [[C:%.*]], i1 false
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %a, i1 %c, i1 false
   %bc = select i1 %b, i1 %c, i1 false
   %or = select i1 %bc, i1 true, i1 %ac
   ret i1 %or
 }
 
 define i1 @logic_and_logic_or_8(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_and_logic_or_8(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[AC]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[A:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 false
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %c, i1 %a, i1 false
   %bc = select i1 %b, i1 %c, i1 false
   %or = select i1 %bc, i1 true, i1 %ac
   ret i1 %or
 }
 
 define <3 x i1> @logic_and_logic_or_vector(<3 x i1> %c, <3 x i1> %a, <3 x i1> %b) {
 ; CHECK-LABEL: @logic_and_logic_or_vector(
-; CHECK-NEXT:    [[BC:%.*]] = select <3 x i1> [[A:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[B:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> [[BC]], <3 x i1> zeroinitializer
+; CHECK-NEXT:    [[TMP1:%.*]] = select <3 x i1> [[A:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[B:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> [[TMP1]], <3 x i1> zeroinitializer
 ; CHECK-NEXT:    ret <3 x i1> [[OR]]
 ;
   %ac = select <3 x i1> %c, <3 x i1> %a, <3 x i1> <i1 false, i1 false, i1 false>
   %bc = select <3 x i1> %c, <3 x i1> %b, <3 x i1> <i1 false, i1 false, i1 false>
   %or = select <3 x i1> %ac, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %bc
   ret <3 x i1> %or
 }
 
 define <3 x i1> @logic_and_logic_or_vector_poison1(<3 x i1> %c, <3 x i1> %a, <3 x i1> %b) {
 ; CHECK-LABEL: @logic_and_logic_or_vector_poison1(
-; CHECK-NEXT:    [[BC:%.*]] = select <3 x i1> [[A:%.*]], <3 x i1> <i1 true, i1 true, i1 poison>, <3 x i1> [[B:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> [[BC]], <3 x i1> zeroinitializer
+; CHECK-NEXT:    [[TMP1:%.*]] = select <3 x i1> [[A:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[B:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> [[TMP1]], <3 x i1> zeroinitializer
 ; CHECK-NEXT:    ret <3 x i1> [[OR]]
 ;
   %ac = select <3 x i1> %c, <3 x i1> %a, <3 x i1> <i1 false, i1 false, i1 false>
   %bc = select <3 x i1> %c, <3 x i1> %b, <3 x i1> <i1 false, i1 false, i1 false>
   %or = select <3 x i1> %ac, <3 x i1> <i1 true, i1 true, i1 poison>, <3 x i1> %bc
   ret <3 x i1> %or
 }
 

 ; CHECK-NEXT:    ret <3 x i1> [[OR]]
 ;
   %ac = select <3 x i1> %c, <3 x i1> %a, <3 x i1> <i1 false, i1 false, i1 false>
   %bc = select <3 x i1> %c, <3 x i1> %b, <3 x i1> <i1 poison, i1 false, i1 false>
   %or = select <3 x i1> %ac, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %bc
   ret <3 x i1> %or
 }
 
+; negative test: not one use for both op
+
 define i1 @logic_and_logic_or_not_one_use(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_and_logic_or_not_one_use(
 ; CHECK-NEXT:    [[AC:%.*]] = select i1 [[C:%.*]], i1 [[A:%.*]], i1 false
 ; CHECK-NEXT:    [[BC:%.*]] = select i1 [[C]], i1 [[B:%.*]], i1 false
 ; CHECK-NEXT:    [[OR:%.*]] = select i1 [[AC]], i1 true, i1 [[BC]]
 ; CHECK-NEXT:    call void @use(i1 [[AC]])
 ; CHECK-NEXT:    call void @use(i1 [[BC]])
 ; CHECK-NEXT:    ret i1 [[OR]]
;
   %or = select i1 %bc, i1 true, i1 %ac
   call void @use(i1 %ac)
   call void @use(i1 %bc)
   ret i1 %or
 }
 
 define i1 @logic_or_logic_and_1(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_or_logic_and_1(
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[BC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %c, i1 true, i1 %a
   %bc = select i1 %c, i1 true, i1 %b
   %or = select i1 %ac, i1 %bc, i1 false
   ret i1 %or
 }
 
 define i1 @logic_or_logic_and_2(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_or_logic_and_2(
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[BC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %a, i1 true, i1 %c
   %bc = select i1 %c, i1 true, i1 %b
   %or = select i1 %ac, i1 %bc, i1 false
   ret i1 %or
 }
 
 define i1 @logic_or_logic_and_3(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_or_logic_and_3(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[C:%.*]]
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[C]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[AC]], i1 [[BC]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[TMP1]], i1 true, i1 [[C:%.*]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %a, i1 true, i1 %c
   %bc = select i1 %b, i1 true, i1 %c
   %or = select i1 %ac, i1 %bc, i1 false
   ret i1 %or
 }
 
 define i1 @logic_or_logic_and_4(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_or_logic_and_4(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[A:%.*]]
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[C]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[AC]], i1 [[BC]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[A:%.*]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %c, i1 true, i1 %a
   %bc = select i1 %b, i1 true, i1 %c
   %or = select i1 %ac, i1 %bc, i1 false
   ret i1 %or
 }
 
 define i1 @logic_or_logic_and_5(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_or_logic_and_5(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[AC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %c, i1 true, i1 %a
   %bc = select i1 %c, i1 true, i1 %b
   %or = select i1 %bc, i1 %ac, i1 false
   ret i1 %or
 }
 
 define i1 @logic_or_logic_and_6(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_or_logic_and_6(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[C:%.*]]
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[C]], i1 true, i1 [[B:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[BC]], i1 [[AC]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %a, i1 true, i1 %c
   %bc = select i1 %c, i1 true, i1 %b
   %or = select i1 %bc, i1 %ac, i1 false
   ret i1 %or
 }
 
 define i1 @logic_or_logic_and_7(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_or_logic_and_7(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[A:%.*]], i1 true, i1 [[C:%.*]]
-; CHECK-NEXT:    [[BC:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[C]]
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[BC]], i1 [[AC]], i1 false
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[TMP1]], i1 true, i1 [[C:%.*]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %a, i1 true, i1 %c
   %bc = select i1 %b, i1 true, i1 %c
   %or = select i1 %bc, i1 %ac, i1 false
   ret i1 %or
 }
 
 define i1 @logic_or_logic_and_8(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_or_logic_and_8(
-; CHECK-NEXT:    [[AC:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[AC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[B:%.*]], i1 [[A:%.*]], i1 false
+; CHECK-NEXT:    [[OR:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %ac = select i1 %c, i1 true, i1 %a
   %bc = select i1 %b, i1 true, i1 %c
   %or = select i1 %bc, i1 %ac, i1 false
   ret i1 %or
 }
 
 define <3 x i1> @logic_or_logic_and_vector(<3 x i1> %c, <3 x i1> %a, <3 x i1> %b) {
 ; CHECK-LABEL: @logic_or_logic_and_vector(
-; CHECK-NEXT:    [[BC:%.*]] = select <3 x i1> [[A:%.*]], <3 x i1> [[B:%.*]], <3 x i1> zeroinitializer
-; CHECK-NEXT:    [[OR:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[BC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select <3 x i1> [[A:%.*]], <3 x i1> [[B:%.*]], <3 x i1> zeroinitializer
+; CHECK-NEXT:    [[OR:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[TMP1]]
 ; CHECK-NEXT:    ret <3 x i1> [[OR]]
 ;
   %ac = select <3 x i1> %c, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %a
   %bc = select <3 x i1> %c, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %b
   %or = select <3 x i1> %ac, <3 x i1> %bc, <3 x i1> <i1 false, i1 false, i1 false>
   ret <3 x i1> %or
 }
 
;
   %ac = select <3 x i1> %c, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %a
   %bc = select <3 x i1> %c, <3 x i1> <i1 true, i1 poison, i1 true>, <3 x i1> %b
   %or = select <3 x i1> %ac, <3 x i1> %bc, <3 x i1> <i1 false, i1 false, i1 false>
   ret <3 x i1> %or
 }
 
 define <3 x i1> @logic_or_logic_and_vector_poison3(<3 x i1> %c, <3 x i1> %a, <3 x i1> %b) {
 ; CHECK-LABEL: @logic_or_logic_and_vector_poison3(
-; CHECK-NEXT:    [[BC:%.*]] = select <3 x i1> [[A:%.*]], <3 x i1> [[B:%.*]], <3 x i1> <i1 false, i1 false, i1 poison>
-; CHECK-NEXT:    [[OR:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[BC]]
+; CHECK-NEXT:    [[TMP1:%.*]] = select <3 x i1> [[A:%.*]], <3 x i1> [[B:%.*]], <3 x i1> zeroinitializer
+; CHECK-NEXT:    [[OR:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[TMP1]]
 ; CHECK-NEXT:    ret <3 x i1> [[OR]]
 ;
   %ac = select <3 x i1> %c, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %a
   %bc = select <3 x i1> %c, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %b
   %or = select <3 x i1> %ac, <3 x i1> %bc, <3 x i1> <i1 false, i1 false, i1 poison>
   ret <3 x i1> %or
 }
 
+; negative test: not one use for both op
+
 define i1 @logic_or_logic_and_not_one_use(i1 %c, i1 %a, i1 %b) {
 ; CHECK-LABEL: @logic_or_logic_and_not_one_use(
 ; CHECK-NEXT:    [[AC:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[A:%.*]]
 ; CHECK-NEXT:    [[BC:%.*]] = select i1 [[B:%.*]], i1 true, i1 [[C]]
 ; CHECK-NEXT:    [[OR:%.*]] = select i1 [[BC]], i1 [[AC]], i1 false
 ; CHECK-NEXT:    call void @use(i1 [[AC]])
 ; CHECK-NEXT:    call void @use(i1 [[BC]])
 ; CHECK-NEXT:    ret i1 [[OR]]