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

    <tr>
        <th>Summary</th>
        <td>
            [Delinearization] Incorrect nsw/nuw flags
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          kasuga-fj
      </td>
    </tr>
</table>

<pre>
    Consider the following silly IR:

```llvm
; void f(char *a, unsigned long long d) {
;   if (d == UINT64_MAX)
;     for (unsigned long long i = 0; i != d; i++)
;       a[i * (d + 1)] = 42;
; }
define void @f(ptr %a, i64 %d) {
entry:
  %guard = icmp eq i64 %d, -1
  br i1 %guard, label %loop.preheader, label %exit

loop.preheader:
  %stride = add nsw i64 %d, 1  ; since %d is -1, %stride is 0
  br label %loop

loop:
  %i = phi i64 [ 0, %loop.preheader ], [ %i.next, %loop ]
  %offset = phi i64 [ 0, %loop.preheader ], [ %offset.next, %loop ]
  %idx = getelementptr inbounds i8, ptr %a, i64 %offset
  store i8 42, ptr %idx
  %i.next = add nuw i64 %i, 1
  %offset.next = add nsw nuw i64 %offset, %stride
  %cond = icmp eq i64 %i.next, %d
  br i1 %cond, label %exit, label %loop

exit:
  ret void
}
```

Running delinearization on this IR produces the following output ([godbolt](https://godbolt.org/z/K1Mn75ccP)):

```
Delinearization on function f:

Inst:  %idx = getelementptr inbounds i8, ptr %a, i64 %offset
In Loop with Header: loop
AccessFunction: 0
failed to delinearize

Inst:  store i8 42, ptr %idx, align 1
In Loop with Header: loop
AccessFunction: {0,+,(1 + %d)}<nuw><nsw><%loop>
Base offset: %a
ArrayDecl[UnknownSize][%d] with elements of 1 bytes.
ArrayRef[{0,+,1}<nuw><nsw><%loop>][{0,+,1}<nuw><nsw><%loop>]
```

Since the back-edge taken count is `2^64 - 1`, `{0,+,1}<nuw><nsw><%loop>` seems incorrect; we should drop the `nsw`.

The root cause appears to be that `SCEVDivision` propagates the no-wrap flags from the numerator to the quotient, which doesn't seem to hold in general.

https://github.com/llvm/llvm-project/blob/f7c6c7ce361b8664eee962f10803e92661582176/llvm/lib/Analysis/ScalarEvolutionDivision.cpp#L144-L148
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJysVl9v2zYQ_zT0yyGGRFmy_OAH_4mxYO0wJO2wt4ESTxIbmlRJKk766Yej5MRJumEtBgi2xLvf3e_-SsJ71RrENcu3LN_PxBA669b3wg-tuGq-zCorn9Y7a7yS6CB0CI3V2p6UacErrZ_g5pZlG5bEq0jGS-uHIz1nW3iwSkLDeFl3wgHjG8H4DgYT_UrQ1rTjj2R8BWy5nXAAqgHGSwks27NsD59vfvtULP76uPmT8dWzEkBjyWz5HYuKoJCQogLGU3qS8Ynxbbwu7QAIlm9JcTP55VtISSffR0MLzrIzO7bcs2QjsVEGxxDZIqEo-0Bs8hikKhZ0fxEYmuCexnQBidpBuBggqPrYA369wOzgKo16lQOVPmuTQIsKNZ1oa_t577BDIdG9EuGjCmNV3ii9ePfBKYnRvZASjD-9cp8CUKhemRrjIShPnPjuAqw8JGeWr2i9-L7wOFak79ToKN9CMpl7TRJYvo-CfBthc4OP4UIzyiebtmk8hp8zPGL_zbqSj9F0iwE1HtEEqrAylR2M9KBKwn2n6KPlaMUH6xBUSQ30oqzk47OPSOClDsNzHVSsw-tI3yj70yVgcntZojO6tua7rfYqufJ1xxHmfVe97cCx1FE0ldphiFNBkjgpz5th1L0djKENIlErg8KpbyIoa8AaCJ3ycHMLvbNyqNG_2Tl2CP0QaEBZvm2trKwOsaZlF0LviQA_MH6YRHPrWsYP3xg__Jp-NMu8rn-nkear90uLJZv9ez7NYOp43zwjboynSP-f_rgx8IF67qRCB7-cRxSmvG7qGr0_TBxIQDQboTRKCPYigfiG2z93Hd-B0Ko1sbF-1D1bbmmy4vbcMV6mcU1OW45qne3McGLZNd346ebcJ9k1SzZb4RGm8Mkg5SXZbJwTT3usNcu3n829sSdzR0Hle3ozkfl8P5Kc0uzBNpBC9RTQz88GbrEh9UuO6X8gNTr5CdS7xr6Ly5JathL1_RXKFiGIezRQ28EEWpesSDjLr4sFXEFKQJq8Ivlh90UCHvHoQZnaOod1oG19QvCdHbQE6WwfmbAiIXyRzEeOnzoEZ22AWgweQfQ9CuepmyqiLgIh7nbXf-zVg_JU9yKhcexFK8I0kMZenZzoodGi9dA4exyPhyM6Eawja3TwdbBBoYk749SpugNp0RvGlyGyJ73OagnKQIsGndATyzfjrEI3VPPaHhk_xK-L8e-qd_YLhc4PlbYV44dmWRf1ssasSKuyKBaIuCp4kyZlkuGKF0WalzxdFhd2FOE2Rugnrzzjh7taaOGuH6weqO3PaZjXfc949iFdLK4-pItyJteZXGUrMcN1uswX-SpZpOmsW4uyXCVNXqd5vuTLMsGVwKzJFkklBTaVnKk1T3ielMkyLdMsS-fVMitynoiqKrMmLQu2SPAolJ4TRdphM-X9gOs053lRzOL29edvNreOmaiG1rNFopUP_gUXVNDx6-7NaqNxujk3Dr1FGD_QeyQWdDY4vf7hAkSKlL-J5cOa_x0AAP__z9ARQA">