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

    <tr>
        <th>Summary</th>
        <td>
            [SLPVectorizer] Miscompile due to incorrect nuw handling
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          max-quazan
      </td>
    </tr>
</table>

<pre>
    Godbolt repro: https://godbolt.org/z/qeeo1P5Ej
Test:
opt -passes=slp-vectorizer -S
```
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-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 @test() {
entry:
  br label %loop

loop:
  %tmp = phi i32 [ -2, %entry ], [ %tmp13, %loop ]
  %tmp2 = add nuw nsw i32 %tmp, 1
  %tmp3 = add nsw i32 %tmp2, 1
  %tmp4 = add nuw nsw i32 %tmp3, 1
  %tmp5 = add nuw nsw i32 %tmp4, 1
  %tmp6 = add nuw nsw i32 %tmp5, 1
  %tmp7 = add nuw nsw i32 %tmp6, 1
  %tmp8 = add nuw nsw i32 %tmp7, 1
  %tmp9 = add nuw nsw i32 %tmp8, 1
  %tmp10 = add nuw nsw i32 %tmp9, 1
  %tmp11 = add nuw nsw i32 %tmp10, 1
  %tmp12 = add nuw nsw i32 %tmp11, 1
  %tmp13 = add nuw nsw i32 %tmp12, 1
  %tmp14 = icmp ugt i32 %tmp12, 12668
  br i1 %tmp14, label %exit, label %loop

exit:
  ret i32 %tmp12
}

```
Output:
```
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-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 @test() {
entry:
  br label %loop

loop:                                             ; preds = %loop, %entry
  %tmp = phi i32 [ -2, %entry ], [ %tmp13, %loop ]
  %0 = call i32 @llvm.vector.reduce.add.v8i32(<8 x i32> <i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1>)
  %op.rdx = add nuw nsw i32 2, %tmp
  %op.rdx1 = add nuw nsw i32 %0, %op.rdx
  %tmp12 = add nuw nsw i32 %op.rdx1, 1
  %tmp13 = add nuw nsw i32 %tmp12, 1
  %tmp14 = icmp ugt i32 %tmp12, 12668
  br i1 %tmp14, label %exit, label %loop

exit:                                             ; preds = %loop
  ret i32 %tmp12
}

declare i32 @llvm.vector.reduce.add.v8i32(<8 x i32>) #0

attributes #0 = { nocallback nofree nosync nounwind readnone willreturn }
```

Before SLP vectorizer, nuw flag wasn't present in %tmp3:
```
  %tmp = phi i32 [ -2, %bb ], [ %tmp13, %bb1 ]
  %tmp2 = add nuw nsw i32 %tmp, 1
  %tmp3 = add nsw i32 %tmp2, 1
```
because at this moment this value crosses border of zero, and therefore makes unsigned wrap. The whole program is well-defined and exits once the counter exceeds 12668.

After slp:
```
  %op.rdx = add nuw nsw i32 2, %tmp
```
is poison starting 1st iteration when `%tmp = -2` and whole program is UB.

Our triage points at this patch as guilty:
```
commit 7ea03f0b4e4ec5d91d48ba2976f5adc299089ffd
Author: Alexey Bataev <a.bataev@outlook.com>
Date: Thu Nov 18 08:08:01 2021 -0800

[SLP]Improve reductions analysis and emission, part 1.

Currently SLP vectorizer walks through the instructions and selects
3 main classes of values: 1) reduction operations - instructions with same
reduction opcode (add, mul, min/max, etc.), which build the reduction,
2) reduced values - instructions with the same opcodes, but different
from the reduction opcode, 3) extra arguments - all other values,
instructions from the different basic block rather than the root node,
instructions with to many/less uses.

This scheme is not very efficient. It excludes some instructions and all
non-instruction values from the reductions (constants, proficient
gathers), to many possibly reduced values are marked as extra arguments.
Patch improves this process by introducing a bit extended analysis
stage. During this stage, we still try to select 3 classes of the
values: 1) reduction operations - same as before, 2) possibly reduced
values - all instructions from the current block/non-instructions, which
may build a vectorization tree, 3) extra arguments - instructions from
the different basic blocks. Additionally, an extra sorting of the
possibly reduced values occurs to build the scalar sequences which
highly likely will bed vectorized, e.g. loads are grouped by the
distance between them, constants are grouped together, cmp instructions
are sorted by their compare types and predicates, extractelement
instructions are sorted by the vector operand, etc. Also, these groups
are reordered by their length so the longest group is the first in the
list of the possibly reduced values.

The vectorization process tries to emit the reductions for all these
groups. These reductions, remaining non-vectorized possible reduced
values and extra arguments are then combined into the final expression
just like it was before.

Differential Revision: https://reviews.llvm.org/D114171
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWFuP27oR_jXeF8KGLpYtP_hhN06KA7Q9QZP2taAkSmJWEhWSWq_z6_sNKV_k9bonPW2BAl14LUqcGc71m5EzVRy2f1BFphrLtOi1msWPrLa2N1jMok_4VH57oXSFux_4_y6ECj8nH7_Ngt0sePwqjCVqd6N6y-Y9N0ZAws40_fxF5FZp-UNoNv_iiWarYPy4W8t1JSwruOUNP6jBMrCyWRSJeQvBYt5H6wCLOHJfdBtOb2m1WrqvuTwuypSYwiiddyktVkce7H1xjyU9Bv9xIx3_IdTtRdBhoqLVsm_EUb3XdPV3yBq6507tu3kju-F1XnXDict_F6KUnWAyjthsGVjyVpTOog2brZ88heisPpxcyFimWcMz0eCQpFGqv5Tm7s-koLBt7zTqa-kPSZ7YHKp_oE0nGo927h47niGMx30S57Yn8iInkBcF64Y968zeC3Z7xBhOyeMz-YQ0ukG7vCM6vkGf3KFf3qBf3aFPbtCv79CvbtCnd-jXN-g3d-jTG_RhcIdhc4shvMMQBrc47oU3DG9xxPc4boU59HGWOZJzqOxb8mi1Si_yXYYnRto-pb94lXby4LoeHMG5HrS4OsuTrneXPFf48-tg--Es5P_o9LvRif3M3yx-Yr0WhRk190Iv4Os_iHW-2HLeNEcPNM1Lu_A9awGlhlwskPaLlxT75Jn4Q8peiXgWfwTzB2JzJfN7FvFHePxCLdUvdPF6s-aOxhISXzO8iwTByOTJfisajEL_J_Hg35CBP4MohcgbrsW_kkSu1qI4uBTHLWo5G1CNbsurtX5inaJUzXj-jGWphcDFHLocl6Hby66AtrzoFAp6L5sGqg-6Y2ddp8jmv59EqaD5lz9-ZudRjVxMkS0bXrE9N90sWlvykUGRMdmdGvY7oPnPizXL7lRqloX_laHkSutM5HwwgnFgaS0Na1VL5rr1C28GwXKtaLRlmdIFBlpVMjhLkUQO59taaO_Nlj-DauiMrDpRsL3m_YJ9rRGWWgGiMWhXmrcMcveiaeYehAsnhBLYMNXlguSxHJG1OEq85oIy1BXK4jKAjyXtY9S-G4yfgZQrfmjZK2lUxww6jZVdxUKDLMCx3Eo83tcCGQHyc8wR51Xg7Hlj8V-fJur_OmjqXLwSdEoH24_u77nNa8YNqwbZ2MN75uWqbaVla8GDuAyypViKPCk2YbFMMx5t1qsy4UUebTZBuinLYnTaYGulCSgeG_EqDuwJ_V28EKLzRebWqGN0e0DB8wJHUKU6zh23gvi-1gP7s3phYcoCasv-K2RREIVsHqTBpMqQ5Kgw5PQvLVzxIpiDBfIe7O14czDS-PC30hg8ppj08DYLJ976MGiNnGwOVwWLIm2eDfym1VDVLnNkZ6w-n1EwIxrQGy8oRo6ijgFbLqGRyS7D6b2POtPmrCBT_Rhow-ZTqXtpa2Z4K7zMS5ZcFRhFohTJRqa0Q-MuEoZ9avkr3QibL6jvYbmvJUKdIc6uis6HY9PLjk46oU68qje1IW7SaFTBkHQgKStkWQpynRdXatVOTxoZiD6ms8Sr1ZxhshoIBOgwmhIU1fjRVUfdJlqcJJ9OZBk3MmdZo4Db8CRJsDXv_PlKWcC3O_iGNG-TQrC6AzzXCANYQcAmSfGVqsXktYDZWHWQ-CIwComylLmEBgv2iyUEaQZ4hBnV3sgOWOeloX3ML3aPzn7rMWpOaY6r5XCQS1itxhO9qMoZa8Ygj2agzJHhGVL4KpzcAad-JiA01_4fDf7sMEH6IjIjTmiVk1-yA6yyWkEoYRRnmSSrregKh62-yrwc6FyJBdsNmkidGPfIJSMyyKJ9MhonobSvGxZfFgvs8oJ-W9W4jIRRmWsPdIjL52tPXIocE-52buUeBnxOIS-uYmZONeUltvwwFhc_YYaHbosh4k7Kvzl9fOF4L73Ngj0WhSR6KH_wjXGUa5TvHZfeey8VVA4LDTn_jAkGsw9HoxPfB4HuaC4NrGVVQ0ojnwUuNPvA1cUZHx0GiUW1YI3ihU-1ClDZgwhpc9KnkJTMaL2ZsHshXIm2xHtK8wmrVXjvqv24RJPtJAR-kgM1GX46R2rIant6bg-98LVHw6fM0Vhc4Jy7cousa0-VNC3Xa6GjoT7nuuIIruhtxg0nIDGj1hd6aeGmmEvVGtFVBOnKSW1UV-GF0DMSstDDUmrjRsCT0xo4bYzqe7V9BVfiKguPFYw5QLioC-roV2CDynEV4YwZ8cVZ5CYrc0lLNmtBDY4SjorjnAlHFcXNovMT2LQMXKxoxEHgMjenAWbU6AzkORhoMnZd28n6NsAhlIuYkWh6Hst-4oTdsXwkBPxFvEjH_ubXV40dsTcL90bhf4LdheEyXF9PsA_FNi428YY_WGkbsfUDx9_OE32yY3-ShnJPwvYCwyxskF2ugCRANxoI0ZOKBh57GHSzvfoVGH1oyNwghC4EZcbLHKH7Bn7cYm5xTfFTkqzS9KHerooNXwq8rayLIAnzJFlnGU_ydRSVhVhuVg_uJc6QqrMo6gSmURJBP1Akuwe5xSQVBQneXlfLKFktcpElGx7nWVSWcbLeYD6jEDcn3zzorVMpGypDL2FIy7PjHgDdNIw7z5B87ibALWaR-feB_-Ddgzt967T_B2w3ASU">