From c5cf6e536598a3b1e30fce616b771d66a071a54c Mon Sep 17 00:00:00 2001 From: Jean-Luc Duprat Date: Mon, 6 May 2013 16:55:50 +0000 Subject: Provide InstCombines for the following 3 cases: A * (1 - (uitofp i1 C)) -> select C, 0, A B * (uitofp i1 C) -> select C, B, 0 select C, 0, A + select C, B, 0 -> select C, B, A These come up in code that has been hand-optimized from a select to a linear blend, on platforms where that may have mattered. We want to undo such changes with the following transform: A*(1 - uitofp i1 C) + B*(uitofp i1 C) -> select C, A, B git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181216 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineMulDivRem.cpp | 28 ++++++++++++++++++++++ 1 file changed, 28 insertions(+) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index df73906..0ac0ca2 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -524,6 +524,34 @@ Instruction *InstCombiner::visitFMul(BinaryOperator &I) { } } + // B * (uitofp i1 C) -> select C, B, 0 + if(I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { + Value *LHS=Op0, *RHS=Op1; + Value *B, *C; + if (!match(RHS, m_UIToFp(m_Value(C)))) + std::swap(LHS, RHS); + + if (match(RHS, m_UIToFp(m_Value(C)))) { + B=LHS; + Value *Zero = ConstantFP::getNegativeZero(B->getType()); + return SelectInst::Create(C, B, Zero); + } + } + + // A * (1 - uitofp i1 C) -> select C, 0, A + if(I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { + Value *LHS=Op0, *RHS=Op1; + Value *A, *C; + if (!match(RHS, m_FSub(m_FPOne(), m_UIToFp(m_Value(C))))) + std::swap(LHS, RHS); + + if (match(RHS, m_FSub(m_FPOne(), m_UIToFp(m_Value(C))))) { + A=LHS; + Value *Zero = ConstantFP::getNegativeZero(A->getType()); + return SelectInst::Create(C, Zero, A); + } + } + if (!isa(Op1)) std::swap(Opnd0, Opnd1); else -- cgit v1.1 From 51dab6e3945a6d06a713869967ced3a8f9fb6294 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Fri, 10 May 2013 09:16:52 +0000 Subject: InstCombine: Verify the type before transforming uitofp into select. PR15952. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181586 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineMulDivRem.cpp | 45 +++++++++++----------- 1 file changed, 23 insertions(+), 22 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 0ac0ca2..ecc9fc3 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -525,31 +525,32 @@ Instruction *InstCombiner::visitFMul(BinaryOperator &I) { } // B * (uitofp i1 C) -> select C, B, 0 - if(I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { - Value *LHS=Op0, *RHS=Op1; - Value *B, *C; - if (!match(RHS, m_UIToFp(m_Value(C)))) - std::swap(LHS, RHS); - - if (match(RHS, m_UIToFp(m_Value(C)))) { - B=LHS; - Value *Zero = ConstantFP::getNegativeZero(B->getType()); - return SelectInst::Create(C, B, Zero); - } + if (I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { + Value *LHS = Op0, *RHS = Op1; + Value *B, *C; + if (!match(RHS, m_UIToFp(m_Value(C)))) + std::swap(LHS, RHS); + + if (match(RHS, m_UIToFp(m_Value(C))) && C->getType()->isIntegerTy(1)) { + B = LHS; + Value *Zero = ConstantFP::getNegativeZero(B->getType()); + return SelectInst::Create(C, B, Zero); + } } // A * (1 - uitofp i1 C) -> select C, 0, A - if(I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { - Value *LHS=Op0, *RHS=Op1; - Value *A, *C; - if (!match(RHS, m_FSub(m_FPOne(), m_UIToFp(m_Value(C))))) - std::swap(LHS, RHS); - - if (match(RHS, m_FSub(m_FPOne(), m_UIToFp(m_Value(C))))) { - A=LHS; - Value *Zero = ConstantFP::getNegativeZero(A->getType()); - return SelectInst::Create(C, Zero, A); - } + if (I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { + Value *LHS = Op0, *RHS = Op1; + Value *A, *C; + if (!match(RHS, m_FSub(m_FPOne(), m_UIToFp(m_Value(C))))) + std::swap(LHS, RHS); + + if (match(RHS, m_FSub(m_FPOne(), m_UIToFp(m_Value(C)))) && + C->getType()->isIntegerTy(1)) { + A = LHS; + Value *Zero = ConstantFP::getNegativeZero(A->getType()); + return SelectInst::Create(C, Zero, A); + } } if (!isa(Op1)) -- cgit v1.1 From a8ccefc0a31c868c79cfc028e2a957269de5aba6 Mon Sep 17 00:00:00 2001 From: David Majnemer Date: Sat, 11 May 2013 09:01:28 +0000 Subject: InstCombine: Turn urem to bitwise-and more often Use isKnownToBeAPowerOfTwo in visitUrem so that we may more aggressively fold away urem instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181661 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineMulDivRem.cpp | 22 ++-------------------- 1 file changed, 2 insertions(+), 20 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index ecc9fc3..2494078 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -1027,31 +1027,13 @@ Instruction *InstCombiner::visitURem(BinaryOperator &I) { if (Instruction *common = commonIRemTransforms(I)) return common; - // X urem C^2 -> X and C-1 - { const APInt *C; - if (match(Op1, m_Power2(C))) - return BinaryOperator::CreateAnd(Op0, - ConstantInt::get(I.getType(), *C-1)); - } - - // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1) - if (match(Op1, m_Shl(m_Power2(), m_Value()))) { + // X urem Y -> X and Y-1, where Y is a power of 2, + if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/true)) { Constant *N1 = Constant::getAllOnesValue(I.getType()); Value *Add = Builder->CreateAdd(Op1, N1); return BinaryOperator::CreateAnd(Op0, Add); } - // urem X, (select Cond, 2^C1, 2^C2) --> - // select Cond, (and X, C1-1), (and X, C2-1) - // when C1&C2 are powers of two. - { Value *Cond; const APInt *C1, *C2; - if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { - Value *TrueAnd = Builder->CreateAnd(Op0, *C1-1, Op1->getName()+".t"); - Value *FalseAnd = Builder->CreateAnd(Op0, *C2-1, Op1->getName()+".f"); - return SelectInst::Create(Cond, TrueAnd, FalseAnd); - } - } - // (zext A) urem (zext B) --> zext (A urem B) if (ZExtInst *ZOp0 = dyn_cast(Op0)) if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) -- cgit v1.1 From fa49d7d6e4384381e4307a0d2495e6e5b15821e3 Mon Sep 17 00:00:00 2001 From: David Majnemer Date: Sun, 12 May 2013 00:07:05 +0000 Subject: InstCombine: Flip the order of two urem transforms There are two transforms in visitUrem that conflict with each other. *) One, if a divisor is a power of two, subtracts one from the divisor and turns it into a bitwise-and. *) The other unwraps both operands if they are surrounded by zext instructions. Flipping the order allows the subtraction to go beneath the sign extension. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181668 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 2494078..87d5621 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -1027,6 +1027,12 @@ Instruction *InstCombiner::visitURem(BinaryOperator &I) { if (Instruction *common = commonIRemTransforms(I)) return common; + // (zext A) urem (zext B) --> zext (A urem B) + if (ZExtInst *ZOp0 = dyn_cast(Op0)) + if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) + return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), + I.getType()); + // X urem Y -> X and Y-1, where Y is a power of 2, if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/true)) { Constant *N1 = Constant::getAllOnesValue(I.getType()); @@ -1034,12 +1040,6 @@ Instruction *InstCombiner::visitURem(BinaryOperator &I) { return BinaryOperator::CreateAnd(Op0, Add); } - // (zext A) urem (zext B) --> zext (A urem B) - if (ZExtInst *ZOp0 = dyn_cast(Op0)) - if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) - return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), - I.getType()); - return 0; } -- cgit v1.1 From da2ed458b4e7066fc414c403173b882ccc2c8833 Mon Sep 17 00:00:00 2001 From: Sylvestre Ledru Date: Tue, 14 May 2013 23:36:24 +0000 Subject: Fix two typo git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181848 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 87d5621..51ca29b 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -846,7 +846,7 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { /// FP value and: /// 1) 1/C is exact, or /// 2) reciprocal is allowed. -/// If the convertion was successful, the simplified expression "X * 1/C" is +/// If the conversion was successful, the simplified expression "X * 1/C" is /// returned; otherwise, NULL is returned. /// static Instruction *CvtFDivConstToReciprocal(Value *Dividend, -- cgit v1.1 From 5e6cabd163c9c207df3778f3508b0de445578057 Mon Sep 17 00:00:00 2001 From: Jean-Luc Duprat Date: Wed, 22 May 2013 18:29:31 +0000 Subject: This is an update to a previous commit (r181216). MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The earlier change list introduced the following inst combines: B * (uitofp i1 C) —> select C, B, 0 A * (1 - uitofp i1 C) —> select C, 0, A select C, 0, B + select C, A, 0 —> select C, A, B Together these 3 changes would simplify : A * (1 - uitofp i1 C) + B * uitofp i1 C down to : select C, B, A In practice we found that the first two substitutions can have a negative effect on performance, because they reduce opportunities to use FMA contractions; between the two options FMAs are often the better choice. This change list amends the previous one to enable just these inst combines: select C, B, 0 + select C, 0, A —> select C, B, A A * (1 - uitofp i1 C) + B * uitofp i1 C —> select C, B, A git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@182499 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineMulDivRem.cpp | 29 ---------------------- 1 file changed, 29 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 51ca29b..2628f4b 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -524,35 +524,6 @@ Instruction *InstCombiner::visitFMul(BinaryOperator &I) { } } - // B * (uitofp i1 C) -> select C, B, 0 - if (I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { - Value *LHS = Op0, *RHS = Op1; - Value *B, *C; - if (!match(RHS, m_UIToFp(m_Value(C)))) - std::swap(LHS, RHS); - - if (match(RHS, m_UIToFp(m_Value(C))) && C->getType()->isIntegerTy(1)) { - B = LHS; - Value *Zero = ConstantFP::getNegativeZero(B->getType()); - return SelectInst::Create(C, B, Zero); - } - } - - // A * (1 - uitofp i1 C) -> select C, 0, A - if (I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { - Value *LHS = Op0, *RHS = Op1; - Value *A, *C; - if (!match(RHS, m_FSub(m_FPOne(), m_UIToFp(m_Value(C))))) - std::swap(LHS, RHS); - - if (match(RHS, m_FSub(m_FPOne(), m_UIToFp(m_Value(C)))) && - C->getType()->isIntegerTy(1)) { - A = LHS; - Value *Zero = ConstantFP::getNegativeZero(A->getType()); - return SelectInst::Create(C, Zero, A); - } - } - if (!isa(Op1)) std::swap(Opnd0, Opnd1); else -- cgit v1.1 From 4f3d7eea048c5d665436b8bd7a59739bcba5ec0b Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Fri, 31 May 2013 14:27:15 +0000 Subject: Simplify multiplications by vectors whose elements are powers of 2. Patch by Andrea Di Biagio. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183005 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../InstCombine/InstCombineMulDivRem.cpp | 64 ++++++++++++++++------ 1 file changed, 48 insertions(+), 16 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 2628f4b..2761bc2 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -95,6 +95,25 @@ static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) { return MulExt.slt(Min) || MulExt.sgt(Max); } +/// \brief A helper routine of InstCombiner::visitMul(). +/// +/// If C is a vector of known powers of 2, then this function returns +/// a new vector obtained from C replacing each element with its logBase2. +/// Return a null pointer otherwise. +static Constant *getLogBase2Vector(ConstantDataVector *CV) { + const APInt *IVal; + SmallVector Elts; + + for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) { + Constant *Elt = CV->getElementAsConstant(I); + if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2()) + return 0; + Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2())); + } + + return ConstantVector::get(Elts); +} + Instruction *InstCombiner::visitMul(BinaryOperator &I) { bool Changed = SimplifyAssociativeOrCommutative(I); Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); @@ -108,24 +127,37 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) { if (match(Op1, m_AllOnes())) // X * -1 == 0 - X return BinaryOperator::CreateNeg(Op0, I.getName()); - if (ConstantInt *CI = dyn_cast(Op1)) { - - // ((X << C1)*C2) == (X * (C2 << C1)) - if (BinaryOperator *SI = dyn_cast(Op0)) - if (SI->getOpcode() == Instruction::Shl) - if (Constant *ShOp = dyn_cast(SI->getOperand(1))) - return BinaryOperator::CreateMul(SI->getOperand(0), - ConstantExpr::getShl(CI, ShOp)); - - const APInt &Val = CI->getValue(); - if (Val.isPowerOf2()) { // Replace X*(2^C) with X << C - Constant *NewCst = ConstantInt::get(Op0->getType(), Val.logBase2()); - BinaryOperator *Shl = BinaryOperator::CreateShl(Op0, NewCst); - if (I.hasNoSignedWrap()) Shl->setHasNoSignedWrap(); - if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap(); - return Shl; + // Also allow combining multiply instructions on vectors. + { + Value *NewOp; + Constant *C1, *C2; + const APInt *IVal; + if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)), + m_Constant(C1))) && + match(C1, m_APInt(IVal))) + // ((X << C1)*C2) == (X * (C2 << C1)) + return BinaryOperator::CreateMul(NewOp, ConstantExpr::getShl(C1, C2)); + + if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) { + Constant *NewCst = 0; + if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2()) + // Replace X*(2^C) with X << C, where C is either a scalar or a splat. + NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2()); + else if (ConstantDataVector *CV = dyn_cast(C1)) + // Replace X*(2^C) with X << C, where C is a vector of known + // constant powers of 2. + NewCst = getLogBase2Vector(CV); + + if (NewCst) { + BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst); + if (I.hasNoSignedWrap()) Shl->setHasNoSignedWrap(); + if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap(); + return Shl; + } } + } + if (ConstantInt *CI = dyn_cast(Op1)) { // Canonicalize (X+C1)*CI -> X*CI+C1*CI. { Value *X; ConstantInt *C1; if (Op0->hasOneUse() && -- cgit v1.1 From 6a72c84b161c176da91ddae1bd97bae7aab6d968 Mon Sep 17 00:00:00 2001 From: Jakub Staszak Date: Thu, 6 Jun 2013 23:34:59 +0000 Subject: Simplify code. No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183461 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineMulDivRem.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 2761bc2..e36b762 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -616,8 +616,7 @@ bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { *I = SI->getOperand(NonNullOperand); Worklist.Add(BBI); } else if (*I == SelectCond) { - *I = NonNullOperand == 1 ? ConstantInt::getTrue(BBI->getContext()) : - ConstantInt::getFalse(BBI->getContext()); + *I = Builder->getInt1(NonNullOperand == 1); Worklist.Add(BBI); } } -- cgit v1.1