diff options
-rw-r--r-- | include/llvm/Analysis/InstructionSimplify.h | 10 | ||||
-rw-r--r-- | lib/Analysis/InstructionSimplify.cpp | 107 | ||||
-rw-r--r-- | lib/Transforms/InstCombine/InstCombineMulDivRem.cpp | 80 | ||||
-rw-r--r-- | test/Transforms/InstCombine/2008-11-20-DivMulRem.ll | 43 | ||||
-rw-r--r-- | test/Transforms/InstSimplify/2010-12-20-Reassociate.ll | 56 |
5 files changed, 235 insertions, 61 deletions
diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index 7588d6b..d39432d 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -40,6 +40,16 @@ namespace llvm { Value *SimplifyMulInst(Value *LHS, Value *RHS, const TargetData *TD = 0, const DominatorTree *DT = 0); + /// SimplifySDivInst - Given operands for an SDiv, see if we can + /// fold the result. If not, this returns null. + Value *SimplifySDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + const DominatorTree *DT = 0); + + /// SimplifyUDivInst - Given operands for a UDiv, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyUDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + const DominatorTree *DT = 0); + /// SimplifyShlInst - Given operands for a Shl, see if we can /// fold the result. If not, this returns null. Value *SimplifyShlInst(Value *Op0, Value *Op1, const TargetData *TD = 0, diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 833f6ca..790b619 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -747,6 +747,105 @@ Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit); } +/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can +/// fold the result. If not, this returns null. +static Value *SimplifyDiv(unsigned Opcode, Value *Op0, Value *Op1, + const TargetData *TD, const DominatorTree *DT, + unsigned MaxRecurse) { + if (Constant *C0 = dyn_cast<Constant>(Op0)) { + if (Constant *C1 = dyn_cast<Constant>(Op1)) { + Constant *Ops[] = { C0, C1 }; + return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD); + } + } + + // X / undef -> undef + if (isa<UndefValue>(Op1)) + return Op1; + + // undef / X -> 0 + if (isa<UndefValue>(Op0)) + return Constant::getNullValue(Op0->getType()); + + // 0 / X -> 0, we don't need to preserve faults! + if (match(Op0, m_Zero())) + return Op0; + + // X / 1 -> X + if (match(Op1, m_One())) + return Op0; + // Vector case. TODO: Have m_One match vectors. + if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1)) { + if (ConstantInt *X = cast_or_null<ConstantInt>(Op1V->getSplatValue())) + if (X->isOne()) + return Op0; + } + + if (Op0->getType()->isIntegerTy(1)) + // It can't be division by zero, hence it must be division by one. + return Op0; + + // X / X -> 1 + if (Op0 == Op1) + return ConstantInt::get(Op0->getType(), 1); + + // (X * Y) / Y -> X if the multiplication does not overflow. + Value *X = 0, *Y = 0; + if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { + if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 + BinaryOperator *Mul = dyn_cast<BinaryOperator>(Op0); + // If the Mul knows it does not overflow, then we are good to go. + bool isSigned = Opcode == Instruction::SDiv; + if ((isSigned && Mul->hasNoSignedWrap()) || + (!isSigned && Mul->hasNoUnsignedWrap())) + return X; + // If X has the form X = A / Y then X * Y cannot overflow. + if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) + if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) + return X; + } + + return 0; +} + +/// SimplifySDivInst - Given operands for an SDiv, see if we can +/// fold the result. If not, this returns null. +static Value *SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, + const DominatorTree *DT, unsigned MaxRecurse) { + if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, TD, DT, MaxRecurse)) + return V; + + // (X rem Y) / Y -> 0 + if (match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) + return Constant::getNullValue(Op0->getType()); + + return 0; +} + +Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, + const DominatorTree *DT) { + return ::SimplifySDivInst(Op0, Op1, TD, DT, RecursionLimit); +} + +/// SimplifyUDivInst - Given operands for a UDiv, see if we can +/// fold the result. If not, this returns null. +static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, + const DominatorTree *DT, unsigned MaxRecurse) { + if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, TD, DT, MaxRecurse)) + return V; + + // (X rem Y) / Y -> 0 + if (match(Op0, m_URem(m_Value(), m_Specific(Op1)))) + return Constant::getNullValue(Op0->getType()); + + return 0; +} + +Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, + const DominatorTree *DT) { + return ::SimplifyUDivInst(Op0, Op1, TD, DT, RecursionLimit); +} + /// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can /// fold the result. If not, this returns null. static Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, @@ -1649,6 +1748,8 @@ static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, /* isNUW */ false, TD, DT, MaxRecurse); case Instruction::Mul: return SimplifyMulInst(LHS, RHS, TD, DT, MaxRecurse); + case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, TD, DT, MaxRecurse); + case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, TD, DT, MaxRecurse); case Instruction::Shl: return SimplifyShlInst(LHS, RHS, TD, DT, MaxRecurse); case Instruction::LShr: return SimplifyLShrInst(LHS, RHS, TD, DT, MaxRecurse); case Instruction::AShr: return SimplifyAShrInst(LHS, RHS, TD, DT, MaxRecurse); @@ -1730,6 +1831,12 @@ Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, case Instruction::Mul: Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT); break; + case Instruction::SDiv: + Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), TD, DT); + break; + case Instruction::UDiv: + Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), TD, DT); + break; case Instruction::Shl: Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), TD, DT); break; diff --git a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp index 40b9cfd..b5b9841 100644 --- a/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp +++ b/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp @@ -304,28 +304,6 @@ bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { } -/// This function implements the transforms on div instructions that work -/// regardless of the kind of div instruction it is (udiv, sdiv, or fdiv). It is -/// used by the visitors to those instructions. -/// @brief Transforms common to all three div instructions -Instruction *InstCombiner::commonDivTransforms(BinaryOperator &I) { - Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - - // undef / X -> 0 for integer. - // undef / X -> undef for FP (the undef could be a snan). - if (isa<UndefValue>(Op0)) { - if (Op0->getType()->isFPOrFPVectorTy()) - return ReplaceInstUsesWith(I, Op0); - return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); - } - - // X / undef -> undef - if (isa<UndefValue>(Op1)) - return ReplaceInstUsesWith(I, Op1); - - return 0; -} - /// This function implements the transforms common to both integer division /// instructions (udiv and sdiv). It is called by the visitors to those integer /// division instructions. @@ -333,31 +311,12 @@ Instruction *InstCombiner::commonDivTransforms(BinaryOperator &I) { Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); - // (sdiv X, X) --> 1 (udiv X, X) --> 1 - if (Op0 == Op1) { - if (const VectorType *Ty = dyn_cast<VectorType>(I.getType())) { - Constant *CI = ConstantInt::get(Ty->getElementType(), 1); - std::vector<Constant*> Elts(Ty->getNumElements(), CI); - return ReplaceInstUsesWith(I, ConstantVector::get(Elts)); - } - - Constant *CI = ConstantInt::get(I.getType(), 1); - return ReplaceInstUsesWith(I, CI); - } - - if (Instruction *Common = commonDivTransforms(I)) - return Common; - // Handle cases involving: [su]div X, (select Cond, Y, Z) // This does not apply for fdiv. if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) return &I; if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { - // div X, 1 == X - if (RHS->equalsInt(1)) - return ReplaceInstUsesWith(I, Op0); - // (X / C1) / C2 -> X / (C1*C2) if (Instruction *LHS = dyn_cast<Instruction>(Op0)) if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode()) @@ -380,20 +339,13 @@ Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { } } - // 0 / X == 0, we don't need to preserve faults! - if (ConstantInt *LHS = dyn_cast<ConstantInt>(Op0)) - if (LHS->equalsInt(0)) - return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); - - // It can't be division by zero, hence it must be division by one. - if (I.getType()->isIntegerTy(1)) - return ReplaceInstUsesWith(I, Op0); - - if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1)) { - if (ConstantInt *X = cast_or_null<ConstantInt>(Op1V->getSplatValue())) - // div X, 1 == X - if (X->isOne()) - return ReplaceInstUsesWith(I, Op0); + // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y + Value *X = 0, *Z = 0; + if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 + bool isSigned = I.getOpcode() == Instruction::SDiv; + if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || + (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) + return BinaryOperator::Create(I.getOpcode(), X, Op1); } return 0; @@ -402,6 +354,9 @@ Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); + if (Value *V = SimplifyUDivInst(Op0, Op1, TD)) + return ReplaceInstUsesWith(I, V); + // Handle the integer div common cases if (Instruction *Common = commonIDivTransforms(I)) return Common; @@ -464,6 +419,9 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); + if (Value *V = SimplifySDivInst(Op0, Op1, TD)) + return ReplaceInstUsesWith(I, V); + // Handle the integer div common cases if (Instruction *Common = commonIDivTransforms(I)) return Common; @@ -516,7 +474,17 @@ Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { } Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { - return commonDivTransforms(I); + Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); + + // undef / X -> undef (the undef could be a snan). + if (isa<UndefValue>(Op0)) + return ReplaceInstUsesWith(I, Op0); + + // X / undef -> undef + if (isa<UndefValue>(Op1)) + return ReplaceInstUsesWith(I, Op1); + + return 0; } /// This function implements the transforms on rem instructions that work diff --git a/test/Transforms/InstCombine/2008-11-20-DivMulRem.ll b/test/Transforms/InstCombine/2008-11-20-DivMulRem.ll index b2774d6..43af190 100644 --- a/test/Transforms/InstCombine/2008-11-20-DivMulRem.ll +++ b/test/Transforms/InstCombine/2008-11-20-DivMulRem.ll @@ -1,34 +1,67 @@ -; RUN: opt < %s -instcombine -S > %t -; RUN: grep urem %t | count 3 -; RUN: grep srem %t | count 1 -; RUN: grep sub %t | count 2 -; RUN: grep add %t | count 1 +; RUN: opt < %s -instcombine -S | FileCheck %s ; PR3103 define i8 @test1(i8 %x, i8 %y) { +; CHECK: @test1 %A = udiv i8 %x, %y +; CHECK-NEXT: urem %B = mul i8 %A, %y %C = sub i8 %x, %B ret i8 %C +; CHECK-NEXT: ret } define i8 @test2(i8 %x, i8 %y) { +; CHECK: @test2 %A = sdiv i8 %x, %y +; CHECK-NEXT: srem %B = mul i8 %A, %y %C = sub i8 %x, %B ret i8 %C +; CHECK-NEXT: ret } define i8 @test3(i8 %x, i8 %y) { +; CHECK: @test3 %A = udiv i8 %x, %y +; CHECK-NEXT: urem %B = mul i8 %A, %y %C = sub i8 %B, %x +; CHECK-NEXT: sub ret i8 %C +; CHECK-NEXT: ret } define i8 @test4(i8 %x) { +; CHECK: @test4 %A = udiv i8 %x, 3 +; CHECK-NEXT: urem %B = mul i8 %A, -3 +; CHECK-NEXT: sub %C = sub i8 %x, %B +; CHECK-NEXT: add ret i8 %C +; CHECK-NEXT: ret +} + +define i32 @test5(i32 %x, i32 %y) { +; CHECK: @test5 +; (((X / Y) * Y) / Y) -> X / Y + %div = sdiv i32 %x, %y +; CHECK-NEXT: sdiv + %mul = mul i32 %div, %y + %r = sdiv i32 %mul, %y + ret i32 %r +; CHECK-NEXT: ret +} + +define i32 @test6(i32 %x, i32 %y) { +; CHECK: @test6 +; (((X / Y) * Y) / Y) -> X / Y + %div = udiv i32 %x, %y +; CHECK-NEXT: udiv + %mul = mul i32 %div, %y + %r = udiv i32 %mul, %y + ret i32 %r +; CHECK-NEXT: ret } diff --git a/test/Transforms/InstSimplify/2010-12-20-Reassociate.ll b/test/Transforms/InstSimplify/2010-12-20-Reassociate.ll index 1e2f7fa..1372466 100644 --- a/test/Transforms/InstSimplify/2010-12-20-Reassociate.ll +++ b/test/Transforms/InstSimplify/2010-12-20-Reassociate.ll @@ -90,3 +90,59 @@ define i32 @sub3(i32 %x, i32 %y) { ret i32 %r ; CHECK: ret i32 %x } + +define i32 @sdiv1(i32 %x, i32 %y) { +; CHECK: @sdiv1 +; (no overflow X * Y) / Y -> X + %mul = mul nsw i32 %x, %y + %r = sdiv i32 %mul, %y + ret i32 %r +; CHECK: ret i32 %x +} + +define i32 @sdiv2(i32 %x, i32 %y) { +; CHECK: @sdiv2 +; (((X / Y) * Y) / Y) -> X / Y + %div = sdiv i32 %x, %y + %mul = mul i32 %div, %y + %r = sdiv i32 %mul, %y + ret i32 %r +; CHECK: ret i32 %div +} + +define i32 @sdiv3(i32 %x, i32 %y) { +; CHECK: @sdiv3 +; (X rem Y) / Y -> 0 + %rem = srem i32 %x, %y + %div = sdiv i32 %rem, %y + ret i32 %div +; CHECK: ret i32 0 +} + +define i32 @udiv1(i32 %x, i32 %y) { +; CHECK: @udiv1 +; (no overflow X * Y) / Y -> X + %mul = mul nuw i32 %x, %y + %r = udiv i32 %mul, %y + ret i32 %r +; CHECK: ret i32 %x +} + +define i32 @udiv2(i32 %x, i32 %y) { +; CHECK: @udiv2 +; (((X / Y) * Y) / Y) -> X / Y + %div = udiv i32 %x, %y + %mul = mul i32 %div, %y + %r = udiv i32 %mul, %y + ret i32 %r +; CHECK: ret i32 %div +} + +define i32 @udiv3(i32 %x, i32 %y) { +; CHECK: @udiv3 +; (X rem Y) / Y -> 0 + %rem = urem i32 %x, %y + %div = udiv i32 %rem, %y + ret i32 %div +; CHECK: ret i32 0 +} |