llvm / llvm/llvm-project

Code sinking (SinkingPass / MachineSink) can increase register pressure by sinking multi-operand instructions past a diamond

Open
#200,785 0 comments 0 reactions 0 assignees View on GitHub
llvm:transforms
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

Description
Both the IR-level sinking pass (llvm/lib/Transforms/Scalar/Sink.cpp) and the machine-level sinking pass (llvm/lib/CodeGen/MachineSink.cpp) decide where to move an instruction based on the dominator/post-dominator relationship of its users, but neither reliably checks whether the move increases register pressure.

When a sunk instruction has more input operands than results (the common case of a binary operation x = y + z), and those inputs have no other use at the sink target, sinking it:

shortens the live range of the single result (x), but
lengthens the live ranges of both inputs (y and z), which now have to stay live all the way from the original block to the sink target.

Example
CFG — a diamond nested inside a loop (this is the shape that triggered the regression in practice):

```
bb0 (loop header; defines the fadds)
/ \
bb1 bb2
\ /
bb3 (uses the fadds)
|
bb0 (back edge)
i.e. bb0 -> bb1, bb0 -> bb2, bb1 -> bb3, bb2 -> bb3, and bb3 -> bb0.
```

Minimal IR reproducing the IR-level sink (one binary op shown; the real case had a dozen fadds in a row):

```llvm
define void @sink_increases_pressure(ptr %p, ptr %q, i32 %n) {
entry:
br label %bb0

bb0: ; preds = %entry, %bb3
%iv = phi i32 [ 0, %entry ], [ %iv.next, %bb3 ]
%a = load volatile float, ptr %p ; only used by %sum
%b = load volatile float, ptr %q ; only used by %sum
%sum = fadd fast float %a, %b ; 2 inputs, 1 result
%c = icmp slt i32 %iv, %n
br i1 %c, label %bb1, label %bb2

bb1: ; preds = %bb0
br label %bb3

bb2: ; preds = %bb0
br label %bb3

bb3: ; preds = %bb1, %bb2
store volatile float %sum, ptr %p ; the only use of %sum
%iv.next = add i32 %iv, 1
%done = icmp sgt i32 %iv.next, %n
br i1 %done, label %end, label %bb0 ; back edge

end:
ret void
}
```

opt -passes=sink -S example.ll

```llvm
define void @sink_increases_pressure(ptr %p, ptr %q, i32 %n) {
entry:
br label %bb0

bb0: ; preds = %bb3, %entry
%iv = phi i32 [ 0, %entry ], [ %iv.next, %bb3 ]
%a = load volatile float, ptr %p, align 4
%b = load volatile float, ptr %q, align 4
%c = icmp slt i32 %iv, %n
br i1 %c, label %bb1, label %bb2

bb1: ; preds = %bb0
br label %bb3

bb2: ; preds = %bb0
br label %bb3

bb3: ; preds = %bb2, %bb1
%sum = fadd fast float %a, %b
store volatile float %sum, ptr %p, align 4
%iv.next = add i32 %iv, 1
%done = icmp sgt i32 %iv.next, %n
br i1 %done, label %end, label %bb0

end: ; preds = %bb3
ret void
}
```

Contributor guide

Open the contributing guide

Research direction

Start by reading llvm/lib/Transforms/Scalar/Sink.cpp and llvm/lib/CodeGen/MachineSink.cpp, then run opt -passes=sink -S on the supplied reproducer to observe the move. Trace how each pass chooses the sink and handles operand live ranges; done means the problematic register-pressure-increasing move is avoided for the diamond case in both passes.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.