Index: llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp =================================================================== --- llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp +++ llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp @@ -2682,6 +2682,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. @@ -2696,7 +2700,26 @@ if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ false, /*IsSelectLogical*/ true)) return replaceInstUsesWith(SI, V); + + // X && Z || Y && Z --> (X || Y) && Z + 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) { + if (A == C) + return SelectInst::Create(A, Builder.CreateSelect(B, One, D), Zero); + if (A == D) + return SelectInst::Create(A, Builder.CreateSelect(B, One, C), Zero); + if (B == C) + return SelectInst::Create(B, Builder.CreateSelect(A, One, D), Zero); + 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 @@ -2708,10 +2731,25 @@ if (Value *V = foldLogicOfFCmps(LHS, RHS, /*IsAnd*/ true, /*IsSelectLogical*/ true)) return replaceInstUsesWith(SI, V); - } - auto *One = ConstantInt::getTrue(SelType); - auto *Zero = ConstantInt::getFalse(SelType); + // (X || Z) && (Y || Z) --> (X && Y) || Z + 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) { + if (A == C) + return SelectInst::Create(A, One, Builder.CreateSelect(B, D, Zero)); + if (A == D) + return SelectInst::Create(A, One, Builder.CreateSelect(B, C, Zero)); + if (B == C) + return SelectInst::Create(B, One, Builder.CreateSelect(A, D, Zero)); + 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. @@ -2726,8 +2764,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)))) && @@ -2756,7 +2792,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()) { Index: llvm/test/Transforms/InstCombine/select-factorize.ll =================================================================== --- llvm/test/Transforms/InstCombine/select-factorize.ll +++ llvm/test/Transforms/InstCombine/select-factorize.ll @@ -7,9 +7,8 @@ define i1 @logic_and_logic_or_1(i1 %c, i1 %a, i1 %b) { ; CHECK-LABEL: @logic_and_logic_or_1( -; 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: [[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 @@ -20,9 +19,8 @@ define i1 @logic_and_logic_or_2(i1 %c, i1 %a, i1 %b) { ; CHECK-LABEL: @logic_and_logic_or_2( -; 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 [[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 %a, i1 %c, i1 false @@ -33,9 +31,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 @@ -46,9 +43,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 @@ -59,9 +55,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 [[C:%.*]], i1 [[A:%.*]], 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 %c, i1 %a, i1 false @@ -72,9 +67,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 @@ -85,9 +79,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 @@ -98,9 +91,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 [[C:%.*]], i1 [[A:%.*]], 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 [[C:%.*]], i1 [[TMP1]], i1 false ; CHECK-NEXT: ret i1 [[OR]] ; %ac = select i1 %c, i1 %a, i1 false @@ -111,9 +103,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: [[AC:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> [[A:%.*]], <3 x i1> zeroinitializer -; CHECK-NEXT: [[BC:%.*]] = select <3 x i1> [[C]], <3 x i1> [[B:%.*]], <3 x i1> zeroinitializer -; CHECK-NEXT: [[OR:%.*]] = select <3 x i1> [[AC]], <3 x i1> , <3 x i1> [[BC]] +; 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> @@ -124,9 +115,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: [[AC:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> [[A:%.*]], <3 x i1> zeroinitializer -; CHECK-NEXT: [[BC:%.*]] = select <3 x i1> [[C]], <3 x i1> [[B:%.*]], <3 x i1> zeroinitializer -; CHECK-NEXT: [[OR:%.*]] = select <3 x i1> [[AC]], <3 x i1> , <3 x i1> [[BC]] +; 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> @@ -161,6 +151,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 @@ -359,9 +351,8 @@ define i1 @logic_or_logic_and_1(i1 %c, i1 %a, i1 %b) { ; CHECK-LABEL: @logic_or_logic_and_1( -; CHECK-NEXT: [[AC:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[A:%.*]] -; CHECK-NEXT: [[BC:%.*]] = select i1 [[C]], i1 true, i1 [[B:%.*]] -; 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 @@ -372,9 +363,8 @@ define i1 @logic_or_logic_and_2(i1 %c, i1 %a, i1 %b) { ; CHECK-LABEL: @logic_or_logic_and_2( -; 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 [[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 %a, i1 true, i1 %c @@ -385,9 +375,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 @@ -398,9 +387,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 @@ -411,9 +399,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 [[C:%.*]], i1 true, i1 [[A:%.*]] -; 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 %c, i1 true, i1 %a @@ -424,9 +411,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 @@ -437,9 +423,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 @@ -450,9 +435,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 [[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: [[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 @@ -463,9 +447,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: [[AC:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> , <3 x i1> [[A:%.*]] -; CHECK-NEXT: [[BC:%.*]] = select <3 x i1> [[C]], <3 x i1> , <3 x i1> [[B:%.*]] -; CHECK-NEXT: [[OR:%.*]] = select <3 x i1> [[AC]], <3 x i1> [[BC]], <3 x i1> zeroinitializer +; 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 @@ -502,9 +485,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: [[AC:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> , <3 x i1> [[A:%.*]] -; CHECK-NEXT: [[BC:%.*]] = select <3 x i1> [[C]], <3 x i1> , <3 x i1> [[B:%.*]] -; CHECK-NEXT: [[OR:%.*]] = select <3 x i1> [[AC]], <3 x i1> [[BC]], <3 x i1> +; 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 @@ -513,6 +495,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:%.*]]