Assertion failure: "multiplicative inverse is only defined for odd numbers" exposed through usage in SCEV #87798
Comments
annamthomas
changed the title
EugeneZelenko
added
llvm:SCEV
|
CC @jayfoad |
|
I think the old API (multiplicativeInverse when modulo provided) was hiding this bug since multiplicative inverse shouldn't be asked for 0. Here, W is one (bit width = 1 and I believe this is the bug) and we are trying to represent Mult=4 in one bit. That makes One thing we can obviously do is in the newly introduced API, explicitly check if the APInt is 0 and return 0 (this makes behaviour same as the old API). |
|
Suggestion: diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index e030b9fc7dac..3f8c390614ff 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -928,11 +928,9 @@ static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
APInt OddFactorial(W, 1);
unsigned T = 1;
for (unsigned i = 3; i <= K; ++i) {
- APInt Mult(W, i);
- unsigned TwoFactors = Mult.countr_zero();
+ unsigned TwoFactors = countr_zero(i);
T += TwoFactors;
- Mult.lshrInPlace(TwoFactors);
- OddFactorial *= Mult;
+ OddFactorial *= i >> TwoFactors;
}
// We need at least W + T bits for the multiplication step |
|
yes, that would probably work as well (since we avoid representing Mult in W bit width), but how can the bitWidth of the SCEV result |
No idea! I have only looked at |
|
The function is supposed to compute Given the way the function works, truncating "i" after the shift looks like the right solution. |
BinomialCoefficient computes the value of W-bit IV at iteration It of a loop. When W is 1, we can call multiplicative inverse on 0 which triggers an assert since 1b76120. Since the arithmetic is supposed to wrap if It or K does not fit in W bits, do the truncation into W bits after we do the shift. Fixes llvm#87798
BinomialCoefficient computes the value of W-bit IV at iteration It of a loop. When W is 1, we can call multiplicative inverse on 0 which triggers an assert since 1b76120. Since the arithmetic is supposed to wrap if It or K does not fit in W bits, do the truncation into W bits after we do the shift. Fixes llvm#87798
BinomialCoefficient computes the value of W-bit IV at iteration It of a loop. When W is 1, we can call multiplicative inverse on 0 which triggers an assert since 1b76120. Since the arithmetic is supposed to wrap if It or K does not fit in W bits, do the truncation into W bits after we do the shift. Fixes llvm#87798
BinomialCoefficient computes the value of W-bit IV at iteration It of a loop. When W is 1, we can call multiplicative inverse on 0 which triggers an assert since 1b76120. Since the arithmetic is supposed to wrap if It or K does not fit in W bits, do the truncation into W bits after we do the shift. Fixes #87798
With this change 1b76120 landed in #87610, we started seeing an assertion failure on the introduced API.
This change caused an assertion failure in usage of multiplicativeInverse in SCEV's BinomialCoefficient algorithm (which was also updated by the change to use this overloaded API). The
oddFactorialin this algorithm becomes 0 and the assertion in newly introduced API gets triggered. Note that the old API for multiplicativeInverse (which passed in the explicit modulo) returned 0 when the input was also 0, and probably hid this bug in SCEV.Here's a minimal reproducer for trunk:
opt -passes=indvars reduced.ll produces:
The text was updated successfully, but these errors were encountered: