From 24ce194cfe493bb743c288ed049fcd86c37aace2 Mon Sep 17 00:00:00 2001 From: Juneyoung Lee Date: Sun, 2 May 2021 20:07:25 +0900 Subject: [PATCH] [InstCombine] generalize select + select/and/or folding using implied conditions MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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 Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D101720 --- .../Transforms/InstCombine/InstCombineAndOrXor.cpp | 28 ++++++++++++- .../Transforms/InstCombine/InstCombineInternal.h | 7 ++++ .../Transforms/InstCombine/InstCombineSelect.cpp | 47 +++++++++++++++++++++ .../InstCombine/select-safe-bool-transforms.ll | 24 +++-------- .../select-safe-impliedcond-transforms.ll | 48 ++++++---------------- 5 files changed, 99 insertions(+), 55 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index 8c0d796..e267173 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -1876,6 +1876,19 @@ Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) { if (Instruction *Z = narrowMaskedBinOp(I)) return Z; + if (I.getType()->isIntOrIntVectorTy(1)) { + if (auto *SI0 = dyn_cast(Op0)) { + if (auto *I = + foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ true)) + return I; + } + if (auto *SI1 = dyn_cast(Op1)) { + if (auto *I = + foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ true)) + return I; + } + } + if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I)) return FoldedLogic; @@ -2553,6 +2566,20 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { if (Value *V = SimplifyBSwap(I, Builder)) return replaceInstUsesWith(I, V); + Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); + if (I.getType()->isIntOrIntVectorTy(1)) { + if (auto *SI0 = dyn_cast(Op0)) { + if (auto *I = + foldAndOrOfSelectUsingImpliedCond(Op1, *SI0, /* IsAnd */ false)) + return I; + } + if (auto *SI1 = dyn_cast(Op1)) { + if (auto *I = + foldAndOrOfSelectUsingImpliedCond(Op0, *SI1, /* IsAnd */ false)) + return I; + } + } + if (Instruction *FoldedLogic = foldBinOpIntoSelectOrPhi(I)) return FoldedLogic; @@ -2577,7 +2604,6 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { } // (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)))) { diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h index edf8f0f..56204db 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h +++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h @@ -357,6 +357,13 @@ private: 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 /// diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp index dc72393..f5733b4 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp @@ -2586,6 +2586,48 @@ static Value *foldSelectWithFrozenICmp(SelectInst &Sel, InstCombiner::BuilderTy 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 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 condval = 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 op = false implies condval = 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 op = true implies condval = 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 op = false implies condval = false. + return SelectInst::Create(Op, One, B); + } +} + Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) { Value *CondVal = SI.getCondition(); Value *TrueVal = SI.getTrueValue(); @@ -2709,6 +2751,11 @@ Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) { replaceUse(*Y, FI); return replaceInstUsesWith(SI, Op1); } + + if (auto *Op1SI = dyn_cast(Op1)) + if (auto *I = foldAndOrOfSelectUsingImpliedCond(CondVal, *Op1SI, + /* IsAnd */ IsAnd)) + return I; } // select (select a, true, b), c, false -> select a, c, false diff --git a/llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll b/llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll index f86feba..d1d1b74 100644 --- a/llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll +++ b/llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll @@ -49,9 +49,7 @@ define i1 @land_band_left2(i1 %A, i1 %B) { ; (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 @@ -71,9 +69,7 @@ define i1 @land_lor_left2(i1 %A, i1 %B) { ; (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 @@ -129,9 +125,7 @@ define i1 @band_lor_left2(i1 %A, i1 %B) { ; (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 @@ -151,9 +145,7 @@ define i1 @lor_land_left2(i1 %A, i1 %B) { ; (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 @@ -309,9 +301,7 @@ define i1 @land_lor_right2(i1 %A, i1 %B) { ; 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 @@ -385,9 +375,7 @@ define i1 @lor_land_right2(i1 %A, i1 %B) { ; 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 diff --git a/llvm/test/Transforms/InstCombine/select-safe-impliedcond-transforms.ll b/llvm/test/Transforms/InstCombine/select-safe-impliedcond-transforms.ll index a8f7d25..730f568 100644 --- a/llvm/test/Transforms/InstCombine/select-safe-impliedcond-transforms.ll +++ b/llvm/test/Transforms/InstCombine/select-safe-impliedcond-transforms.ll @@ -4,9 +4,7 @@ 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 @@ -39,9 +37,7 @@ define <2 x i1> @a_true_implies_b_true_vec(i8 %z0, <2 x i1> %X, <2 x i1> %Y) { 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 @@ -54,9 +50,7 @@ define i1 @a_true_implies_b_true2(i8 %z, i1 %X, i1 %Y) { 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 @@ -69,9 +63,7 @@ define i1 @a_true_implies_b_true2_comm(i8 %z, i1 %X, i1 %Y) { 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 @@ -84,9 +76,7 @@ define i1 @a_true_implies_b_false(i8 %z, i1 %X, i1 %Y) { 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 @@ -99,9 +89,7 @@ define i1 @a_true_implies_b_false2(i8 %z, i1 %X, i1 %Y) { 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 @@ -114,9 +102,7 @@ define i1 @a_true_implies_b_false2_comm(i8 %z, i1 %X, i1 %Y) { 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 @@ -129,9 +115,7 @@ define i1 @a_false_implies_b_true(i8 %z, i1 %X, i1 %Y) { 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 @@ -144,9 +128,7 @@ define i1 @a_false_implies_b_true2(i8 %z, i1 %X, i1 %Y) { 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 @@ -159,9 +141,7 @@ define i1 @a_false_implies_b_true2_comm(i8 %z, i1 %X, i1 %Y) { 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 @@ -174,9 +154,7 @@ define i1 @a_false_implies_b_false(i8 %z, i1 %X, i1 %Y) { 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 @@ -189,9 +167,7 @@ define i1 @a_false_implies_b_false2(i8 %z, i1 %X, i1 %Y) { 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 -- 2.7.4