aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/InstructionSimplify.h10
-rw-r--r--lib/Analysis/InstructionSimplify.cpp107
-rw-r--r--lib/Transforms/InstCombine/InstCombineMulDivRem.cpp80
-rw-r--r--test/Transforms/InstCombine/2008-11-20-DivMulRem.ll43
-rw-r--r--test/Transforms/InstSimplify/2010-12-20-Reassociate.ll56
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
+}
generated by cgit v1.1 at 2024-10-28 09:23:19 +0000