InstCombine: Infer nuw for multiplies
A multiply cannot unsigned wrap if there are bitwidth, or more, leading
zero bits between the two operands.
llvm-svn: 224849
diff --git a/llvm/lib/Transforms/InstCombine/InstCombine.h b/llvm/lib/Transforms/InstCombine/InstCombine.h
index d6eb6d4..b4d1efc 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombine.h
+++ b/llvm/lib/Transforms/InstCombine/InstCombine.h
@@ -286,6 +286,7 @@
bool WillNotOverflowSignedSub(Value *LHS, Value *RHS, Instruction *CxtI);
bool WillNotOverflowUnsignedSub(Value *LHS, Value *RHS, Instruction *CxtI);
bool WillNotOverflowSignedMul(Value *LHS, Value *RHS, Instruction *CxtI);
+ bool WillNotOverflowUnsignedMul(Value *LHS, Value *RHS, Instruction *CxtI);
Value *EmitGEPOffset(User *GEP);
Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask);
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
index 5beaf00..d444d33 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -165,6 +165,39 @@
return false;
}
+/// \brief Return true if we can prove that:
+/// (mul LHS, RHS) === (mul nuw LHS, RHS)
+bool InstCombiner::WillNotOverflowUnsignedMul(Value *LHS, Value *RHS,
+ Instruction *CxtI) {
+ // 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 zero 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();
+ APInt LHSKnownZero(BitWidth, 0);
+ APInt RHSKnownZero(BitWidth, 0);
+ APInt TmpKnownOne(BitWidth, 0);
+ computeKnownBits(LHS, LHSKnownZero, TmpKnownOne, 0, CxtI);
+ computeKnownBits(RHS, RHSKnownZero, TmpKnownOne, 0, CxtI);
+ // Note that underestimating the number of zero bits gives a more
+ // conservative answer.
+ unsigned ZeroBits = LHSKnownZero.countLeadingOnes() +
+ RHSKnownZero.countLeadingOnes();
+ // First handle the easy case: if we have enough zero bits there's
+ // definitely no overflow.
+ if (ZeroBits >= BitWidth)
+ return true;
+
+ // There is an ambiguous cases where there can be no overflow:
+ // ZeroBits == BitWidth - 1
+ // However, determining overflow requires calculating the sign bit of
+ // LHS * RHS/2.
+
+ return false;
+}
+
Instruction *InstCombiner::visitMul(BinaryOperator &I) {
bool Changed = SimplifyAssociativeOrCommutative(I);
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
@@ -380,6 +413,11 @@
I.setHasNoSignedWrap(true);
}
+ if (!I.hasNoUnsignedWrap() && WillNotOverflowUnsignedMul(Op0, Op1, &I)) {
+ Changed = true;
+ I.setHasNoUnsignedWrap(true);
+ }
+
return Changed ? &I : nullptr;
}