<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/87798>87798</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Assertion failure with newly introduced multiplicativeInverse API
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          annamthomas
      </td>
    </tr>
</table>

<pre>
    With this change [1b76120](https://github.com/llvm/llvm-project/commit/1b761205f2686516cebadbcbc37f798197d9c482), 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)
...
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWl1T47jS_jXiRpWULX9fcBEC1FK1s0VN2NlLSrbajhZZ8ivJQPbXvyXZCXYIM8MeTtXunKHA2Jb60dMf6m7HocbwRgKco-QCJZdntLdbpc-plLS1W9VSc1Yqtjv_g9sttltucLWlsgGMkouwzNKQBCi5RCTfWtsZFK0QuUbkuuF225fLSrWIXAvxuP-36LT6EyqLyHWl2pa7kxEmqUmap0mYVlBSVlZlFWV1VuRhkbGiinOCSIHIGj8BNpZqCwwbAC4bTCWmxoC2XElcUy56DVhJbLeAubRasb4Chle3N0sUXKJgNRzvJtpUtDfATiNxiXtDG8Cqxm0vLO8Er6jlj3AjH0EbP2OzvvqCSGbwBZeq5VSsFdQ1rzhIi6lolOZ222JE8qctr7b4iRpMhVG47xh1upQ7z3fkYxXuDQwGV4-ghaJsUAGRYonvtoBRGijGrmllleZUoDRwPLzEy3olVKoFg3GAqWR-hRcFucQSnsTuyEi4AWuw1bxpQANb4t-UdVSo9fJKDLNqpd8wx0HJzq3FBlqA4dnN5Ba3ivVCIVJgDbbXEhgO8NMW9h7revtin8D53HHvtCppKXZ4y9mgZtk3e9Mv8dSzv4AG7wyKWy55SwXW0A0qak_c6l4-uGgdpNJg_PWXluoGLGbUUkF3qrcYRZcYEQKLFkUrWHQkC1C0iog_uMtwfunO0tgfFvxwEpIcRauQ5Is6D8Yz6W-le_E0Xmz8be5uLzqyH8jHv4gMYwQRMmNrNe8E7Jk-5-l9Gi96-SDVk1wILvvnRSP7g9RwZFBzCZhHBKM4QIQYSy2v8J9cWnwHxi75J7BbRPI_hZKNc4UbevlfEJKRIMrSokjy1KGT3DkWZRfDCmXF74ODoTEuNRa0BIERSdxYFi47DVugDPSU2auxaIW_9YOiC9xpYGa0wusFyHp_O9gTQiQRqqLivrgnMfGS3ZYPJkkuhvDby2Cf6tZ-AJEknIxNl_HTjuGzexKH74IP3gMf35OoeBd89H3wgQeljA2gM3VGhAmDieBSQhPGXrrtxXulw-NlB7iZjPfYRGbwnssVs8WGaWSNw8nc6LRaA43p3FJjHrp8Ae72LHbDYMmjfB5e3x3cg_D3hPVXgvsUg9nQW9tuOjoeXza_2-r4uv_rL9C_Wy7MstpC9bDpW5cHVDnU74JEQRoVWRxlRRov4dnVcpepPNPflCcLFRijtEFkavshKP6CZ3twrqiMoUmRusLnEuY4WcMwJThtvXl6-Pb2nwTnYcHjLePi6Dt2xlcNml2erCvDUXUWL3xlNCi65JI9Um2wBl9_l0LgsVCZt8qT6qxXl1xrpezrxmrfbvESketN33VKu9ur2xtpl1XX-coTJw7DT41WKFr50ePr4fRkkR_zfKWk8WxWh67C8XSDK1ejXc-WXLgWESOSIpK64jQHxHzfRRmspNjhoSgxX6cVY1j2bQlDDLn6kvnGDNjYy93-erXaXGHTly23mPqmQIPT2cXSu7tSbkwPBpHrIY_ISvQMhs5MU7PFJa0erKYVjMtvLK0eMOvb7uCuYImC4larRtMWU930LUhrRpc55_net-MC9ML1REq7jXtdCSqbxaE7M4uhRyHXJZeDIF4oB0G7zl33tuvt0uDF5kQ4oWhtVK8rQNHVGLKIRAEOnoP9T1zVVZLmE5-bnRlObjWX1mt251RFJH-ZpOnTvTJWA229R9d4aASwd_p_pB8iF8HzSMsFzoF3eMS7qMoKb3gjqfiFSiYcfj7SGG6bMdAD_3cAIiNQVmckKCAmCQlG4sN2GfumSb_kBqqlUct0oOdEZuSiOWaRFnWFO7vVQNn9AxfifQt4-dkC8THpOEtxY7ye7yUfZ-kMO5ljkzyrI0xLt3vehewFZ8jpK-SwfDdmWM4wszlm5Kz9PkwvMsPMZ7FV1gXU9d_Mgx-2BQYWM5rFjGYc0bhMJjTdM9CKsc9QXT13ergHj1T01MLK3ljQ1K0428krrenuM9QoWs-BxqxOVi55uJ7mjdH5UEUF1VePSvTDSulHJoVB4YNFXE4IjixSlXH9FT7-pqPQW_DWsptKdfPc9hX1flWqmwx9pGaO-Eyz8FizGuBbmjVg_2Fa1QAzrcixVglJ_p3-Ssg8EqMf0l_xTKsghooGEyoanjS34BhdPXP7hQrfN-Vzsic1uJG1ejVw5z_G-JWXmurdyRmvMsxJhDtNpamVbh3GW7lqffXl6rmj0j8ypfPBS9VySa3Sd9pZ5Ej0M3SCVjCqfATbUiG-QGWVnuXUP4D6RuqBy-bLL_7pMu19bv3QHDm4aObDZOrDiIZBzXK3HpVK7lrVGyxpC6bzTV4xsL2R7AvVG952gte70dm9PO3aAs-nv267HI30iEZYhXRitznELTXma6seuWslqdgZbj5RSRuYG34QOA6_jaWSUc32kp_B9MIahzz65B0S87m3n373H-fqj3XtaLKZa7OpTUlR1yyeJh0GlnIxtvPUmE-KgfiGcU744b9r6o-xc3T1M1xm4TJGwyxc8vkWpFAnKTaWDUxU5_DoPEBuNRjQjzDq4Z4vrybsfVR9lxX_-XGz4bIRMGSeE-QOduol_78e7js7V-J4s62VrKCz_1qzTFVmUNNe2HsGAiz80Gofft_IIj_D4H8oDP5FhWN9lJVvpLHaf-pIP_5RfKwds-JSHBWXOpw9AP1IleIPbreqtw7rNzD2dvjg9WfbMUSGc_w0Mkgwj4wySFjxg0bGzyAYgsD7-BAEy-Xy6CXWGTuPWBEV9AzOwywkUUSKPDzbnheQRWWdpgWUAaUlI1BUEWSERDSiIavP-DkJSBzEQRKmQRSESyBpwIKkSKssIzGtURxAS7lYOj2XSjdn_nXOeZ5lRX7m39cZ_0UnQiQ8YT-ICEHJ5Zk-9y-Cyr4xKA4EN9a8oFhuBZyvXn0z6Inb7euv0Jz-Uszq9uas1-L877-R8lr8fwAAAP__ktWQMw">