Assertion failure: "multiplicative inverse is only defined for odd numbers" exposed through usage in SCEV

[annamthomas]

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 oddFactorial in 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:

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
target triple = "x86_64-unknown-linux-gnu"

define i32 @"static jint Test.iMeth(jlong, jint, jint)2272037699586"() {
bci_0:
  br label %bci_71.preheader

bci_71.preheader:                                 ; preds = %bci_71.preheader, %bci_0
  %local_9_242 = phi i32 [ 0, %bci_0 ], [ %1, %bci_71.preheader ]
  %local_7_241 = phi i32 [ 0, %bci_0 ], [ %0, %bci_71.preheader ]
  %local_4_239 = phi i32 [ 0, %bci_0 ], [ %3, %bci_71.preheader ]
  %0 = add i32 %local_7_241, %local_4_239
  %.neg14 = mul i32 %local_7_241, %local_4_239
  %1 = add i32 %.neg14, %local_9_242
  %2 = and i32 %local_9_242, 1
  %3 = add i32 %local_4_239, 1
  br i1 true, label %bci_10.i38.preheader, label %bci_71.preheader

bci_10.i38:                                       ; preds = %bci_10.i38.preheader, %bci_10.i38
  br label %bci_10.i38

"static jlong FuzzerUtils.checkSum(jobject)2306397437964.exit": ; No predecessors!
  %4 = zext i32 %.lcssa596 to i64
  ret i32 0

bci_10.i38.preheader:                             ; preds = %bci_71.preheader
  %.lcssa596 = phi i32 [ %2, %bci_71.preheader ]
  br label %bci_10.i38
}

opt -passes=indvars reduced.ll produces:

opt: /root/llvm-project/llvm/lib/Support/APInt.cpp:1245: llvm::APInt llvm::APInt::multiplicativeInverse() const: Assertion `(*this)[0] && "multiplicative inverse is only defined for odd numbers!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: /opt/compiler-explorer/clang-assertions-trunk/bin/opt -o /app/output.s -S -passes=indvars <source>
 #0 0x0000000004cfc568 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4cfc568)
 #1 0x0000000004cf9cbc SignalHandler(int) Signals.cpp:0:0
 #2 0x00007f7209e42520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x00007f7209e969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #4 0x00007f7209e42476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #5 0x00007f7209e287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #6 0x00007f7209e2871b (/lib/x86_64-linux-gnu/libc.so.6+0x2871b)
 #7 0x00007f7209e39e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
 #8 0x0000000004bf9eff llvm::APInt::multiplicativeInverse() const (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4bf9eff)
 #9 0x000000000443a4b5 llvm::SCEVAddRecExpr::evaluateAtIteration(llvm::ArrayRef<llvm::SCEV const*>, llvm::SCEV const*, llvm::ScalarEvolution&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x443a4b5)
#10 0x000000000443cb4f llvm::ScalarEvolution::computeSCEVAtScope(llvm::SCEV const*, llvm::Loop const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x443cb4f)
#11 0x000000000443cfee llvm::ScalarEvolution::getSCEVAtScope(llvm::SCEV const*, llvm::Loop const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x443cfee)
#12 0x000000000443c525 llvm::ScalarEvolution::computeSCEVAtScope(llvm::SCEV const*, llvm::Loop const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x443c525)
#13 0x000000000443cfee llvm::ScalarEvolution::getSCEVAtScope(llvm::SCEV const*, llvm::Loop const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x443cfee)
#14 0x000000000404eca0 llvm::rewriteLoopExitValues(llvm::Loop*, llvm::LoopInfo*, llvm::TargetLibraryInfo*, llvm::ScalarEvolution*, llvm::TargetTransformInfo const*, llvm::SCEVExpander&, llvm::DominatorTree*, llvm::ReplaceExitVal, llvm::SmallVector<llvm::WeakTrackingVH, 16u>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x404eca0)
#15 0x0000000003a10fd8 (anonymous namespace)::IndVarSimplify::run(llvm::Loop*) IndVarSimplify.cpp:0:0
#16 0x0000000003a11c1a llvm::IndVarSimplifyPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3a11c1a)
#17 0x00000000029ffd4e llvm::detail::PassModel<llvm::Loop, llvm::IndVarSimplifyPass, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x29ffd4e)
#18 0x0000000003aaef56 std::optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::Loop, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>>>>(llvm::Loop&, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>>>&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3aaef56)
#19 0x0000000003aaf1ee llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithoutLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3aaf1ee)
#20 0x0000000003ab05d9 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3ab05d9)
...

[topperc]

CC @jayfoad

[annamthomas]

I think the old API (multiplicativeInverse when modulo provided) was hiding this bug since multiplicative inverse shouldn't be asked for 0.
Also, the reason the oddFactorial becomes 0 here is because of this:

// Calculate K! / 2^T and T; we divide out the factors of two before
    // multiplying for calculating K! / 2^T to avoid overflow.
    // Other overflow doesn't matter because we only care about the bottom
    // W bits of the result.
    APInt OddFactorial(W, 1);
    unsigned T = 1;
    for (unsigned i = 3; i <= K; ++i) {
      APInt Mult(W, i);
      unsigned TwoFactors = Mult.countr_zero();
      T += TwoFactors;
      Mult.lshrInPlace(TwoFactors);
      OddFactorial *= Mult; 
    }

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 Mult 0 and hence OddFactorial 0.

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).
But I think this is hiding the bug.

[jayfoad]

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

[annamthomas]

yes, that would probably work as well (since we avoid representing Mult in W bit width), but how can the bitWidth of the SCEV resultW be 1 in the first place?

[jayfoad]

yes, that would probably work as well (since we avoid representing Mult in W bit width), but how can the bitWidth of the SCEV resultW be 1 in the first place?

No idea! I have only looked at BinomialCoefficient itself, not at its callers. I assume it is supposed to work for any W > 0 and K > 0. At least I don't see it mentioned that K has to be representable in W bits, or anything like that.

[efriedma-quic]

The function is supposed to compute BC(It, K) mod 2^W, i.e. the binomial coefficient truncated to fit into a W-bit integer. This is useful for computing the value of a W-bit induction variable at iteration "It" of a loop. There isn't any expectation that "It" or "K" fit losslessly into "W": the arithmetic is supposed to wrap.

Given the way the function works, truncating "i" after the shift looks like the right solution.