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

    <tr>
        <th>Summary</th>
        <td>
            [SelectionDAG] Infinite loop when canonicalizing ABDU nodes with constants
        </td>
    </tr>

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

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

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

<pre>
    The following IR shows a reduced repro: trying to compile it with `llc` will cause SelectionDAG to get into an infinite loop

```llvm
target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-unknown-linux-gnu"

define <1 x i64> @do_stuff() {
  %1 = tail call <8 x i8> @llvm.aarch64.neon.umax.v8i8(<8 x i8> zeroinitializer, <8 x i8> <i8 -1, i8 -1, i8 -1, i8 -1, i8 -1, i8 -1, i8 -1, i8 -1>)
  %2 = tail call <8 x i8> @llvm.aarch64.neon.uabd.v8i8(<8 x i8> %1, <8 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>)
  %3 = zext <8 x i8> %2 to <8 x i16>
  %4 = bitcast <8 x i16> %3 to <4 x i32>
  %5 = shufflevector <4 x i32> %4, <4 x i32> zeroinitializer, <2 x i32> <i32 0, i32 1>
  %6 = shufflevector <8 x i8> %2, <8 x i8> zeroinitializer, <16 x i32> <i32 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison, i32 poison>
  %7 = bitcast <16 x i8> %6 to <2 x i64>
  %8 = shufflevector <2 x i64> %7, <2 x i64> zeroinitializer, <1 x i32> zeroinitializer
  %9 = tail call <1 x i64> @llvm.aarch64.neon.saddlp.v1i64.v2i32(<2 x i32> %5)
  %10 = or <1 x i64> %8, %9
  ret <1 x i64> %10
}

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(none)
declare <8 x i8> @llvm.aarch64.neon.umax.v8i8(<8 x i8>, <8 x i8>) #0

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(none)
declare <8 x i8> @llvm.aarch64.neon.uabd.v8i8(<8 x i8>, <8 x i8>) #0

; Function Attrs: nocallback nofree nosync nounwind willreturn memory(none)
declare <1 x i64> @llvm.aarch64.neon.saddlp.v1i64.v2i32(<2 x i32>) #0

attributes #0 = { nocallback nofree nosync nounwind willreturn memory(none) }
```

During post-legalize combine, we have this DAG:
```
SelectionDAG has 19 nodes:
    t51: v8i8 = BUILD_VECTOR Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>
    t52: v8i8 = AArch64ISD::MOVI Constant:i32<1>
 t39: v8i8 = abdu t51, t52
    t0: ch,glue = EntryToken
          t46: v16i8 = insert_subvector undef:v16i8, t39, Constant:i64<0>
        t47: v8i8 = AArch64ISD::DUPLANE8 t46, Constant:i64<0>
      t35: v1i64 = bitcast t47
            t11: v8i16 = zero_extend t39
          t37: v4i16 = extract_subvector t11, Constant:i64<0>
        t38: v2i32 = bitcast t37
      t43: v1i64 = AArch64ISD::SADDLP t38
    t30: v1i64 = or t35, t43
  t32: ch,glue = CopyToReg t0, Register:v1i64 $d0, t30
 t33: ch = AArch64ISD::RET_GLUE t32, Register:v1i64 $d0, t32:1
```
We try to combine `t11: v8i16 = zero_extend t39`, which hits `performExtendCombine`, which will eventually call into `canonicalizeCommutativeBinop` for the `abdu` node:
https://github.com/llvm/llvm-project/blob/67e05d380c2253319c22451d340e2e3c2043b6d8/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp#L6281-L6284

This swaps the two operands to move the `BUILD_VECTOR` to the right-hand side:
```
t54: v8i8 = abdu t52, t51
t55: v8i16 = zero_extend t54
```

We then try to combine this new node, `t54`. `DAGCombiner::combine()` doesn't manage to combine it with other operations, so it falls through to this code that tries to replace it with an existing commutation:
https://github.com/llvm/llvm-project/blob/67e05d380c2253319c22451d340e2e3c2043b6d8/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp#L2079-L2089

But because that checks `isa<ConstantSDNode>(N0)` instead of `isConstantIntBuildVectorOrConstantInt`, it doesn't realise that it's already had its constant canonicalized to the RHS, and so we replace the new `abdu` with the old, uncanonicalised `abdu`. After that replacement and pruning dead nodes, we get back to where we started:
```
SelectionDAG has 19 nodes:
    t51: v8i8 = BUILD_VECTOR Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>, Constant:i32<255>
    t52: v8i8 = AArch64ISD::MOVI Constant:i32<1>
  t39: v8i8 = abdu t51, t52
    t0: ch,glue = EntryToken
          t46: v16i8 = insert_subvector undef:v16i8, t39, Constant:i64<0>
        t47: v8i8 = AArch64ISD::DUPLANE8 t46, Constant:i64<0>
      t35: v1i64 = bitcast t47
            t55: v8i16 = zero_extend t39
          t37: v4i16 = extract_subvector t55, Constant:i64<0>
        t38: v2i32 = bitcast t37
      t43: v1i64 = AArch64ISD::SADDLP t38
    t30: v1i64 = or t35, t43
  t32: ch,glue = CopyToReg t0, Register:v1i64 $d0, t30
  t33: ch = AArch64ISD::RET_GLUE t32, Register:v1i64 $d0, t32:1
```
And we will continue to do these in a loop

A bisect showed that this started happening in 120ce83660dea7e70abe1c8f9408f39fe2502f8d, which marked `ABDU` as commutative. However, I think this was just exposing a pre-existing issue. I think the underlying cause is `DAGCombiner::combine` uses `isa<ConstantSDNode>()` instead of `isConstantIntBuildVectorOrConstantInt()` like is used in `SelectionDAG::getNode`/`SelectionDAG::canonicalizeCommutativeBinop`, which would have been changed in commit 4f8fdf78279f0cb298dc0dc215ee56b0342235ee

I have verified that this still repros on the latest trunk, 5f8e4315979c266f3610f89d11a48bd43809533d

For priority/triage purposes: this was not found in manually-written code, but was hit by a fuzzer to test SIMD codegen
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWU9v27gS_zTKhbBBkZIsHXJw7KQbINsukrR7LChxZLGRSYGk4rif_mEoO5adtN1ugH19eFs0tkXN_xnO_CgJ59RKA5xH6UWULs9E7xtjzy9Af1HanZVGbs_vGyC1aVuzUXpFrm-Ja8zGEUEsyL4CSSx01kR8TrzdIok3pDLrTrVAlCcb5RsSZbRtqyijZKPallSid0DuoIXKK6OX83fItAJPlPaGCE2UrpVWHkhrTBfRZUTnu8-MDv_b9nE9LHlhkVUKL1qxNb0nEV-SiDGYrCM-h4nKIz7HP84mKs4iPg8feJUlEZ9nyUTFDAlilk80Z8PaHa4xdqTEW9W1sFcghK2aLJn0-kGbjZ60SvdPk5Xun9mGTwm10si1iMkTCUovSZRQaT4739d1hIoKEs0uBnpCIpbGQYsXCuPVtsidI3e-Y8YATHcWTDUYPe3X4mn6mKsc5Y2pv4I1GE4lWvUVbMQWJ9L4QuVkEuONt_zglxErRi6wn3dBlPJVFzAg37B7b8DPf5_ay4O9X-HJk1PlDCt0v4jlczniSwJfqXwlnD-mGsQOvAmuYnWNedPA65q-rlt4hMobe0wbFOxcH62-nlM2YuMLxRmhwVvOBncPerPX9R47_SLir2uNs2-rfeOPzihn9D9wdRSc2WlCBw_3ccl2CWXPu3nEm78eWDba-SydjfM1rH4jtN_O-EFl8XKfHTealxvNCSnbbvoYqyyZPjJUEXYcO6q79Hh_xDQoGhyKjxzKg70sfSa34F9SxXTXFmfLo6bOL8hVr8MwIHPvrcNxog06U4rqgWhTWwCijdvqimjT643SMgwTC763mqxhbew2Yrk2Gp6tllC1wsIbeufpDgh9mnH6q5n_jb75q5j_9nJ8zXLhvVVl78GFW8NYnl28zXZyKM491hjrXPYWQU5nnJ-0sAp7EfFOqZB7QTZAGvEIxDfKkeX8XcRPkctweYR-GuFIXBBtJLhnBkII8WmMycDMBu8uPl7fLD9_ulzcf7glC6OdF9pHfB5itMANO-T8f_fWyHV25Pp8Hurl-m6JEeLz3z98un4pZTTlPC-OBIhS9iGgbBGEHzRRpKuaiC1WbT-gu0vt7fbePIA-0A3_fJIFsXG2k6u0A-s_u77cdfteS6gjPg8kQRsvTl3GvbCgRw4PwmffdXr58Y-b-fvLPFjxV0R6ng7WquwYpaCmE88I8fG-3OJsh4Ws-QxPHrQMXpzGgg_mJnt6ePJWVONgoMi_6DvPgzDc_cem8iNTfcKPXToN0t18ubz5I8g75JjTYyY0jachOwnf0_mA_U9KYWG67b25hRUWCluQW1gp58GGDAdxLJF0yDN9rj0-CHrVwNvL-8_vbj5eBn0_kIgGxa92kD8BT1y741YZDhgZ_WEGsyB306iqIY3yDpk6sLWx68tAtdj1sjFhOLXBI2jfi7bdDigjnNWijFZCG62q0AkXZr3uvfDqES6UNh0e-WoMdROswy2IS9jonvtc430Xuh67itjVSvmmL6eVWUfsKhzyhq9JZ80XqHzErsrWlBG7ymZAU8lzWjGWch4XFWNJGkueUGDAK0YTXmYyH8lRyLcwEt6BjtjVuAefXE6rrosYv8lYHk_wMxkPgXts7m4jOhc88xtDTAdWaOkwH2sTBkBwedyx0XVvwh2rVo2fNEJL4tQoGCc59mnyWg9jQw-L90Tpd3KeJt-ZZn8GO_VpIYXhpWEzJAoxREZRUEan-HM5f7erEjsU9PP8w3MseikNOB2xmSdrocUKxsL3DwWMb8AOccOgO9TjDN6uRdtiZK3pV80QMeVIZSRaJsIpHEKgLXStqA4ihSbwpJzHCV3tSxHB_a9WaqMI7iuN0VkxuWE0L8YJuug9KWF4YBJ8rxqoHsKuVU5EfLFvrHfL92FTXUYsf093aVDaeRCSmHpg2BNfa3_Rq1Z-Cj36gx2t7_a98qMcWhCt2hugfMRmjojWgpBb0ghJsI1UOxFk3A7kvtxvf7tDqaHcDWKkfebwJhbaqDmETOK6aSUy9fog0oEckU7JvPZgB7t2EtegfdDT2V5jHUgMwICsBni2Ak8CNvSGbBqwgIvOC-tB_ovW_lto7V-49jfg2ncb_9-Da2n6fwjX_hG8NsdzJ-yegBvtle7DXJShRTogShPx4oH3nJTKQeXDY3dsqGEABvwxtCzSiK6D0OqUJjGjFeQ8y6gEMYMZFSXEVV4XCc1rXtTAUsrqXB6w3VrYh6Grzi-WH7EBC3cYno8wJb-ZDTwOT6SuUbV-GAzYCEe-9M4TeOqMQwME6SxMnkewcq6H6YgJwmazbXhPMAw15b6LKDJKegc_mHdvmHbPzK16CMb0OGKURglHMztYtQIftOKMvHqV4gdgeASpTd_K4VFBCaBJ1Qi9GlRj8JUnSZ3Xsp7lbFbUtCpZkcuKyorFKUCalZQnjPEUYFwt14PER7CqVifVgnUX3tU4YnRIRis84Ia1vX5Ay9I6h4THaTErKpZlNc9iWueFjGOR5KVMeE6LlHM51nhlLOmsMlb5bcSuvFUI97redsaF8XioFW08qU2vg5NrocNZYrKxynsMwA5qlr0P1I3ypNwSQer-61cc8oYEa--uf18G4hXoM3nOZcELcQbncZbPMkZTzs-a8zxNZnVMU5nFsQAOVZHU1UzUM57UBdTJmTpnlHGasSROWZ7yaSqziha8BChlkRWzKKGwFqqdhodVxq7OQjWfZzwp4rNWlNC68NqMMcQv4WbEWJQuz-x5QJFlv3JRQlvlvDtI8cq34X3bUe2kS3I9fuWFwESPoRRuGNyfA-oYMNIecrmz3rbnP41tg8kO0S269J8AAAD__0A7JZc">