summaryrefslogtreecommitdiffstats
path: root/llvm/lib
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib')
-rw-r--r--llvm/lib/Analysis/ValueTracking.cpp83
-rw-r--r--llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp42
-rw-r--r--llvm/lib/Transforms/InstCombine/InstCombineInternal.h34
-rw-r--r--llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp41
4 files changed, 114 insertions, 86 deletions
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index 60981a1a720..05246a28817 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -3704,6 +3704,48 @@ OverflowResult llvm::computeOverflowForUnsignedMul(const Value *LHS,
return OverflowResult::MayOverflow;
}
+OverflowResult llvm::computeOverflowForSignedMul(const Value *LHS,
+ const Value *RHS,
+ const DataLayout &DL,
+ AssumptionCache *AC,
+ const Instruction *CxtI,
+ const DominatorTree *DT) {
+ // Multiplying n * m significant bits yields a result of n + m significant
+ // bits. If the total number of significant bits does not exceed the
+ // result bit width (minus 1), there is no overflow.
+ // This means if we have enough leading sign bits in the operands
+ // we can guarantee that the result does not overflow.
+ // Ref: "Hacker's Delight" by Henry Warren
+ unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
+
+ // Note that underestimating the number of sign bits gives a more
+ // conservative answer.
+ unsigned SignBits = ComputeNumSignBits(LHS, DL, 0, AC, CxtI, DT) +
+ ComputeNumSignBits(RHS, DL, 0, AC, CxtI, DT);
+
+ // First handle the easy case: if we have enough sign bits there's
+ // definitely no overflow.
+ if (SignBits > BitWidth + 1)
+ return OverflowResult::NeverOverflows;
+
+ // There are two ambiguous cases where there can be no overflow:
+ // SignBits == BitWidth + 1 and
+ // SignBits == BitWidth
+ // The second case is difficult to check, therefore we only handle the
+ // first case.
+ if (SignBits == BitWidth + 1) {
+ // It overflows only when both arguments are negative and the true
+ // product is exactly the minimum negative number.
+ // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000
+ // For simplicity we just check if at least one side is not negative.
+ KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT);
+ KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
+ if (LHSKnown.isNonNegative() || RHSKnown.isNonNegative())
+ return OverflowResult::NeverOverflows;
+ }
+ return OverflowResult::MayOverflow;
+}
+
OverflowResult llvm::computeOverflowForUnsignedAdd(const Value *LHS,
const Value *RHS,
const DataLayout &DL,
@@ -3833,6 +3875,47 @@ static OverflowResult computeOverflowForSignedAdd(const Value *LHS,
return OverflowResult::MayOverflow;
}
+OverflowResult llvm::computeOverflowForUnsignedSub(const Value *LHS,
+ const Value *RHS,
+ const DataLayout &DL,
+ AssumptionCache *AC,
+ const Instruction *CxtI,
+ const DominatorTree *DT) {
+ // If the LHS is negative and the RHS is non-negative, no unsigned wrap.
+ KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT);
+ KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT);
+ if (LHSKnown.isNegative() && RHSKnown.isNonNegative())
+ return OverflowResult::NeverOverflows;
+
+ return OverflowResult::MayOverflow;
+}
+
+OverflowResult llvm::computeOverflowForSignedSub(const Value *LHS,
+ const Value *RHS,
+ const DataLayout &DL,
+ AssumptionCache *AC,
+ const Instruction *CxtI,
+ const DominatorTree *DT) {
+ // If LHS and RHS each have at least two sign bits, the subtraction
+ // cannot overflow.
+ if (ComputeNumSignBits(LHS, DL, 0, AC, CxtI, DT) > 1 &&
+ ComputeNumSignBits(RHS, DL, 0, AC, CxtI, DT) > 1)
+ return OverflowResult::NeverOverflows;
+
+ KnownBits LHSKnown = computeKnownBits(LHS, DL, 0, AC, CxtI, DT);
+
+ KnownBits RHSKnown = computeKnownBits(RHS, DL, 0, AC, CxtI, DT);
+
+ // Subtraction of two 2's complement numbers having identical signs will
+ // never overflow.
+ if ((LHSKnown.isNegative() && RHSKnown.isNegative()) ||
+ (LHSKnown.isNonNegative() && RHSKnown.isNonNegative()))
+ return OverflowResult::NeverOverflows;
+
+ // TODO: implement logic similar to checkRippleForAdd
+ return OverflowResult::MayOverflow;
+}
+
bool llvm::isOverflowIntrinsicNoWrap(const IntrinsicInst *II,
const DominatorTree &DT) {
#ifndef NDEBUG
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
index d818441d09c..0df56bd0c07 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -856,48 +856,6 @@ Value *FAddCombine::createAddendVal(const FAddend &Opnd, bool &NeedNeg) {
return createFMul(OpndVal, Coeff.getValue(Instr->getType()));
}
-/// Return true if we can prove that:
-/// (sub LHS, RHS) === (sub nsw LHS, RHS)
-/// This basically requires proving that the add in the original type would not
-/// overflow to change the sign bit or have a carry out.
-/// TODO: Handle this for Vectors.
-bool InstCombiner::willNotOverflowSignedSub(const Value *LHS,
- const Value *RHS,
- const Instruction &CxtI) const {
- // If LHS and RHS each have at least two sign bits, the subtraction
- // cannot overflow.
- if (ComputeNumSignBits(LHS, 0, &CxtI) > 1 &&
- ComputeNumSignBits(RHS, 0, &CxtI) > 1)
- return true;
-
- KnownBits LHSKnown = computeKnownBits(LHS, 0, &CxtI);
-
- KnownBits RHSKnown = computeKnownBits(RHS, 0, &CxtI);
-
- // Subtraction of two 2's complement numbers having identical signs will
- // never overflow.
- if ((LHSKnown.isNegative() && RHSKnown.isNegative()) ||
- (LHSKnown.isNonNegative() && RHSKnown.isNonNegative()))
- return true;
-
- // TODO: implement logic similar to checkRippleForAdd
- return false;
-}
-
-/// Return true if we can prove that:
-/// (sub LHS, RHS) === (sub nuw LHS, RHS)
-bool InstCombiner::willNotOverflowUnsignedSub(const Value *LHS,
- const Value *RHS,
- const Instruction &CxtI) const {
- // If the LHS is negative and the RHS is non-negative, no unsigned wrap.
- KnownBits LHSKnown = computeKnownBits(LHS, /*Depth=*/0, &CxtI);
- KnownBits RHSKnown = computeKnownBits(RHS, /*Depth=*/0, &CxtI);
- if (LHSKnown.isNegative() && RHSKnown.isNonNegative())
- return true;
-
- return false;
-}
-
// Checks if any operand is negative and we can convert add to sub.
// This function checks for following negative patterns
// ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
index 56fb5e013d3..87d04483aec 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
+++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
@@ -442,11 +442,22 @@ private:
}
bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
- const Instruction &CxtI) const;
+ const Instruction &CxtI) const {
+ return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
+ OverflowResult::NeverOverflows;
+ }
+
bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
- const Instruction &CxtI) const;
+ const Instruction &CxtI) const {
+ return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
+ OverflowResult::NeverOverflows;
+ }
+
bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
- const Instruction &CxtI) const;
+ const Instruction &CxtI) const {
+ return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
+ OverflowResult::NeverOverflows;
+ }
bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
const Instruction &CxtI) const {
@@ -597,6 +608,12 @@ public:
return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
}
+ OverflowResult computeOverflowForSignedMul(const Value *LHS,
+ const Value *RHS,
+ const Instruction *CxtI) const {
+ return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
+ }
+
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
const Value *RHS,
const Instruction *CxtI) const {
@@ -609,6 +626,17 @@ public:
return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
}
+ OverflowResult computeOverflowForUnsignedSub(const Value *LHS,
+ const Value *RHS,
+ const Instruction *CxtI) const {
+ return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
+ }
+
+ OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS,
+ const Instruction *CxtI) const {
+ return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
+ }
+
/// Maximum size of array considered when transforming.
uint64_t MaxArraySizeForCombine;
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
index f9f9873cd24..420a28bfdf2 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -125,47 +125,6 @@ static Constant *getLogBase2(Type *Ty, Constant *C) {
return ConstantVector::get(Elts);
}
-/// Return true if we can prove that:
-/// (mul LHS, RHS) === (mul nsw LHS, RHS)
-bool InstCombiner::willNotOverflowSignedMul(const Value *LHS,
- const Value *RHS,
- const Instruction &CxtI) const {
- // Multiplying n * m significant bits yields a result of n + m significant
- // bits. If the total number of significant bits does not exceed the
- // result bit width (minus 1), there is no overflow.
- // This means if we have enough leading sign bits in the operands
- // we can guarantee that the result does not overflow.
- // Ref: "Hacker's Delight" by Henry Warren
- unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
-
- // Note that underestimating the number of sign bits gives a more
- // conservative answer.
- unsigned SignBits =
- ComputeNumSignBits(LHS, 0, &CxtI) + ComputeNumSignBits(RHS, 0, &CxtI);
-
- // First handle the easy case: if we have enough sign bits there's
- // definitely no overflow.
- if (SignBits > BitWidth + 1)
- return true;
-
- // There are two ambiguous cases where there can be no overflow:
- // SignBits == BitWidth + 1 and
- // SignBits == BitWidth
- // The second case is difficult to check, therefore we only handle the
- // first case.
- if (SignBits == BitWidth + 1) {
- // It overflows only when both arguments are negative and the true
- // product is exactly the minimum negative number.
- // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000
- // For simplicity we just check if at least one side is not negative.
- KnownBits LHSKnown = computeKnownBits(LHS, /*Depth=*/0, &CxtI);
- KnownBits RHSKnown = computeKnownBits(RHS, /*Depth=*/0, &CxtI);
- if (LHSKnown.isNonNegative() || RHSKnown.isNonNegative())
- return true;
- }
- return false;
-}
-
Instruction *InstCombiner::visitMul(BinaryOperator &I) {
bool Changed = SimplifyAssociativeOrCommutative(I);
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
OpenPOWER on IntegriCloud