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

    <tr>
        <th>Summary</th>
        <td>
            [NVPTX][SDAG] Slow compile times when lowering wide vector reduction operations
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            slow-compile,
            backend:NVPTX
      </td>
    </tr>

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

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

<pre>
    IR:

```llvm
; ./bin/llc test.ll
target datalayout = "e-p:64:64-i64:64-i128:128-v16:16-v32:32-n16:32:64-S32"
target triple = "nvptx64-nvidia-cuda"

declare float @llvm.vector.reduce.fadd.v65536f32(float, <65536 x float>)

define void @kernel(ptr addrspace(1) %out, ptr addrspace(1) %in) {
entry:
    %val = load <65536 x float>, ptr addrspace(1) %in, align 32
    %mul = fmul <65536 x float> %val, %val
    %res = call float @llvm.vector.reduce.fadd.v65536f32(float 0.000000e+00, <65536 x float> %mul)
    store float %res, ptr addrspace(1) %out, align 4
    ret void
}
```

We don't seem to handle vector reduction operations of wide (illegal) types properly, as the above code is lowered by trying to emit an enormous DAG, leading to pathological compile times (~2mins, although it drops to seconds when the compiler is allowed to lower the reduction into a tree via `reassoc` flag).

It may be worth revisiting the compilation strategy, perhaps expanding the reduction into a loop for widths above threshold, rather than a linear chain:

https://github.com/llvm/llvm-project/blob/62bbe3fffc16d77a07cfbbb9333ef19fd01b135b/llvm/lib/Target/NVPTX/NVPTXTargetTransformInfo.h#L93-L98


</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJycVV-P66YT_TTkZRQLg__ED3nIbn75aaWrququ2r5iM7bpxWABdjYv_ewVOLt71du7UhtZMeDhzJwzwyC8V4NBPJLygZTnnVjCaN1RmGCNsr1Tw4gh2F1r5e349AvhJ0LTU9Ht0Xqd4pw_QEbYpVWGsIvWHQT0IdOa0FMQbsAAUgShxc0uAQg_A2EM9zPhp6pIf3v1PsjZgfBTzg77Na_iqNqvnBF-4mxv0kqaVcX-mTPC2IeP4NSs8Q3frHN4rYq9WZVUYt8tUmzWhJ4kdlo4hF5bEYAUiUi2YhesyxzKpcOsF1Jma1WWvOqjo0MyJuwRCH9My_C6ARD-P8KaN-ReGYTVKhlxv6IzqAk7zMGBkNL5WXRI2CEnrAHCSrskyB99joI2QOoHQk9ogrttOQCA-HUVOrHVVsh_jupz5EcQWg0GOPvAnJYNs98G32He_SYdttH7Voc-be2E1v9BWqAZTT8k7IHSHyh9j3ETPDr2wX5kMgXxGe273hvv4g7hMKSMxRTW528LfEvqbwjSGsLqAB5xgmBhFEZqhI0XJF5BWQN2RifiyIPt4aokAmEHpTUOUbQGwm1GD7OLhvqWYvEQRgTR2hWhsxJBedD2ig4ltDcI7qbMEJ3ipAIIA2ism-zi4Xz6f0TQKOTdZBZhtNoOqhMaOjvNSiMENcXUsMOfbFLGbwKE0S7DCCqAdHb2cbPHzhrp4TqiSTHdAVyMSOgYk4x2Kbhk8EFcmWBBQHCIsCoBpKIOhfe2IxWFXouBsCbb9HwKMIkbtAhX68IIDlflVUgU3r0mFcEHJwIOSagZ3ShmD_g6CyPfrL8LQVs7Q29dVD-M_i5sGB360WoZkZwIY2IgTNygDAoH3SiUee9xYwizjzN2IewyqDAubdbZKTW49e21n539A7sQm5-2LWGXirUt8r7vu7ySdS1o3fVt2zacc-zzppc0b3Nett_gqDh5ST2MsMtPv_788vvbe1t9ccL43rrpyfQ2GwnjXxq-_9IctlB38shlwxuxw2NeH4qqOFQN3Y1HxihS0dRIedN2JW3qtu7yupGF5CWX-U4dGWUVrVmel0VR0ozyvKg6UeRCdqzNa1JQnITSWTrF1g075f2CR5bnND_stGhR-3R9MOa1ve7vFRM7LXskjLWi-4pGEn6682LxonHHJF67DD52COWD__AQVNDpStp2lGdSPjzHSi_P8Kzt9W9lnYo1VWSsiHTiPjmVu8Xp47_ObSLtCbvcea9H9lcAAAD__xh7RE8">