diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp --- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp @@ -2773,6 +2773,10 @@ 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. @@ -2787,7 +2791,30 @@ 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(CondVal); + bool FalseLogicAnd = isa(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 @@ -2799,10 +2826,29 @@ 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(CondVal); + bool TrueLogicOr = isa(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. @@ -2817,8 +2863,6 @@ 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)))) && @@ -2847,7 +2891,6 @@ 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()) { diff --git a/llvm/test/Transforms/InstCombine/select-factorize.ll b/llvm/test/Transforms/InstCombine/select-factorize.ll --- a/llvm/test/Transforms/InstCombine/select-factorize.ll +++ b/llvm/test/Transforms/InstCombine/select-factorize.ll @@ -5,8 +5,8 @@ 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 @@ -17,8 +17,8 @@ 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 @@ -29,9 +29,8 @@ 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 @@ -42,9 +41,8 @@ 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 @@ -55,8 +53,8 @@ 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 @@ -67,9 +65,8 @@ 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 @@ -80,9 +77,8 @@ 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 @@ -93,8 +89,8 @@ 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 @@ -105,8 +101,8 @@ 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> , <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> , <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> @@ -117,8 +113,8 @@ 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> , <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> , <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> @@ -152,6 +148,8 @@ 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 @@ -343,8 +341,8 @@ 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 @@ -355,8 +353,8 @@ 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 @@ -367,9 +365,8 @@ 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 @@ -380,9 +377,8 @@ 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 @@ -393,8 +389,8 @@ 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 @@ -405,9 +401,8 @@ 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 @@ -418,9 +413,8 @@ 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 @@ -431,8 +425,8 @@ 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 @@ -443,8 +437,8 @@ 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> , <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> , <3 x i1> [[TMP1]] ; CHECK-NEXT: ret <3 x i1> [[OR]] ; %ac = select <3 x i1> %c, <3 x i1> , <3 x i1> %a @@ -480,8 +474,8 @@ 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> -; CHECK-NEXT: [[OR:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> , <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> , <3 x i1> [[TMP1]] ; CHECK-NEXT: ret <3 x i1> [[OR]] ; %ac = select <3 x i1> %c, <3 x i1> , <3 x i1> %a @@ -490,6 +484,8 @@ 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:%.*]]