From 30f017ad898bd86415aab001b45b5ac1373fa882 Mon Sep 17 00:00:00 2001 From: Christopher Lamb Date: Tue, 18 Dec 2007 09:34:41 +0000 Subject: [PATCH] Fold certain additions through selects (and their compares) so as to eliminate subtractions. This code is often produced by the SMAX expansion in SCEV. This implements test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45158 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/README.txt | 18 ------ .../Scalar/InstructionCombining.cpp | 61 +++++++++++++++++++ .../InstCombine/2007-12-18-AddSelCmpSub.ll | 38 ++++++++++++ 3 files changed, 99 insertions(+), 18 deletions(-) create mode 100644 test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll diff --git a/lib/Target/README.txt b/lib/Target/README.txt index c942d944712..37c0a359a2b 100644 --- a/lib/Target/README.txt +++ b/lib/Target/README.txt @@ -464,21 +464,3 @@ entry: } //===---------------------------------------------------------------------===// - -This code is often produced by the SMAX expansion in SCEV: - -define i32 @foo(i32 %a) { -entry: - %tmp15 = sub i32 99, %a ; [#uses=2] - %tmp16 = icmp slt i32 %tmp15, 0 ; [#uses=1] - %smax = select i1 %tmp16, i32 0, i32 %tmp15 ; [#uses=1] - %tmp12 = add i32 %smax, %a ; [#uses=1] - %tmp13 = add i32 %tmp12, 1 ; [#uses=1] - ret i32 %tmp13 -} - -Note that the tmp12 add can be pushed through the select operands, turning -it into a "select %tmp16, %a, 99". We apparently already do this in dag -combine because it isn't present in X86 output. - -//===---------------------------------------------------------------------===// diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp index 7989ebf1979..b059c49f0aa 100644 --- a/lib/Transforms/Scalar/InstructionCombining.cpp +++ b/lib/Transforms/Scalar/InstructionCombining.cpp @@ -2130,6 +2130,67 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) { return new PtrToIntInst(I2, CI->getType()); } } + + // add (select (icmp 0 (sub m A)) X Y) A -> + // add (select (icmp A m) X Y) A + // + // add (select X 0 (sub n A)) A -> + // select X A n -> + { + SelectInst *SI = dyn_cast(LHS); + Value *Other = RHS; + if (!SI) { + SI = dyn_cast(RHS); + Other = LHS; + } + if (SI) { + Value *TV = SI->getTrueValue(); + Value *FV = SI->getFalseValue(); + Value *A; + + // Can we fold the add into the argument of the compare? + Value *Cond = SI->getCondition(); + if (ICmpInst *IC = dyn_cast(Cond)) { + Value *ICOp0 = IC->getOperand(0); + Value *ICOp1 = IC->getOperand(1); + ConstantInt *C3, *C4; + + // Check both arguments of the compare for a matching subtract. + if (match(ICOp0, m_ConstantInt(C3)) && C3->getValue() == 0 && + match(ICOp1, m_Sub(m_ConstantInt(C4), m_Value(A))) && + A == Other) { + // We managed to fold the add into the RHS of the select condition. + Cond = new ICmpInst(IC->getPredicate(), A, C4, "asis", SI); + } else if (match(ICOp1, m_ConstantInt(C3)) && C3->getValue() == 0 && + match(ICOp0, m_Sub(m_ConstantInt(C4), m_Value(A))) && + A == Other) { + // We managed to fold the add into the LHS of the select condition. + Cond = new ICmpInst(IC->getPredicate(), C4, A, "asis", SI); + } + } + + // Can we fold the add into the argument of the select? + // We check both true and false select arguments for a matching subtract. + ConstantInt *C1, *C2; + if (match(FV, m_ConstantInt(C1)) && C1->getValue() == 0 && + match(TV, m_Sub(m_ConstantInt(C2), m_Value(A))) && + A == Other) { + // We managed to fold the add into the true select value, + // picking up a simplified condition, if available. + return new SelectInst(Cond, C2, A, "adselsub"); + } else if (match(TV, m_ConstantInt(C1)) && C1->getValue() == 0 && + match(FV, m_Sub(m_ConstantInt(C2), m_Value(A))) && + A == Other) { + // We managed to fold the add into the false select value, + // picking up a simplified condition, if available. + return new SelectInst(Cond, A, C2, "adselsub"); + } else if (Cond != SI->getCondition()) { + // We only managed to fold the add into the select condition. + SI->setOperand(0, Cond); + Changed = true; + } + } + } return Changed ? &I : 0; } diff --git a/test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll b/test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll new file mode 100644 index 00000000000..ef38eee30e2 --- /dev/null +++ b/test/Transforms/InstCombine/2007-12-18-AddSelCmpSub.ll @@ -0,0 +1,38 @@ +; RUN: llvm-as < %s | opt -instcombine | llvm-dis | not grep {sub} + +define i32 @foo(i32 %a) { +entry: + %tmp15 = sub i32 99, %a ; [#uses=2] + %tmp16 = icmp slt i32 %tmp15, 0 ; [#uses=1] + %smax = select i1 %tmp16, i32 0, i32 %tmp15 ; [#uses=1] + %tmp12 = add i32 %smax, %a ; [#uses=1] + %tmp13 = add i32 %tmp12, 1 ; [#uses=1] + ret i32 %tmp13 +} + +define i32 @bar(i32 %a) { +entry: + %tmp15 = sub i32 99, %a ; [#uses=2] + %tmp16 = icmp slt i32 %tmp15, 0 ; [#uses=1] + %smax = select i1 %tmp16, i32 0, i32 %tmp15 ; [#uses=1] + %tmp12 = add i32 %smax, %a ; [#uses=1] + ret i32 %tmp12 +} + +define i32 @baz(i32 %a) { +entry: + %tmp15 = sub i32 99, %a ; [#uses=1] + %tmp16 = icmp slt i32 %tmp15, 0 ; [#uses=1] + %smax = select i1 %tmp16, i32 0, i32 42 ; [#uses=1] + %tmp12 = add i32 %smax, %a ; [#uses=1] + ret i32 %tmp12 +} + +define i32 @fun(i32 %a) { +entry: + %tmp15 = sub i32 99, %a ; [#uses=1] + %tmp16 = icmp slt i32 %a, 0 ; [#uses=1] + %smax = select i1 %tmp16, i32 0, i32 %tmp15 ; [#uses=1] + %tmp12 = add i32 %smax, %a ; [#uses=1] + ret i32 %tmp12 +} \ No newline at end of file -- 2.34.1