llvm / llvm/llvm-project

[NVPTX][SDAG] Slow compile times when lowering wide vector reduction operations

Open
#211,018 2 comments 0 reactions 0 assignees View on GitHub
backend:NVPTX slow-compile
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

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

Contributor guide

Open the contributing guide

Research direction

Reproduce the case with the supplied IR using ./bin/llc test.ll, then inspect llvm/lib/Target/NVPTX/NVPTXTargetTransformInfo.h around the linked lines and the reduction-lowering path. Compare the normal and reassociated reductions; done means wide illegal vector reductions no longer build a pathological linear DAG or take minutes to compile.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.