| Issue |
243134
|
| Summary |
[InstCombine] Sinking down a chain of unconditional branches separates loads from their uses
|
| Labels |
llvm:instcombine,
missed-optimization
|
| Assignees |
|
| Reporter |
chfast
|
InstCombine sinks an instruction into its user's block when that block's only predecessor is the instruction's block ([InstructionCombining.cpp#L5925](https://github.com/llvm/llvm-project/blob/e0b437836a212942c47d86356316793a171b9a0b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp#L5925)). It also does this when the destination is the source block's only successor, where sinking doesn't make the instruction run any less often. In a chain of such blocks the arithmetic moves block by block to the end of the chain, but a load whose user is two blocks further down stays where it is: https://godbolt.org/z/GxK7r9vKK
```llvm
define i32 @f(ptr %w, i32 %a, i32 %b) {
entry:
%w0 = load i32, ptr %w, align 4
br label %f0
f0:
%x0 = xor i32 %a, %b
br label %l0
l0:
%s0 = add i32 %x0, %w0
%a1 = call i32 @llvm.fshl.i32(i32 %s0, i32 %s0, i32 11)
%p1 = getelementptr inbounds i8, ptr %w, i64 4
%w1 = load i32, ptr %p1, align 4
br label %f1
f1:
%x1 = xor i32 %a1, %b
br label %l1
l1:
%s1 = add i32 %x1, %w1
%a2 = call i32 @llvm.fshl.i32(i32 %s1, i32 %s1, i32 14)
%p2 = getelementptr inbounds i8, ptr %w, i64 8
%w2 = load i32, ptr %p2, align 4
br label %f2
f2:
%x2 = xor i32 %a2, %b
br label %l2
l2:
%s2 = add i32 %x2, %w2
%a3 = call i32 @llvm.fshl.i32(i32 %s2, i32 %s2, i32 15)
ret i32 %a3
}
```
`opt -passes=instcombine` moves all the arithmetic into `%l2` and leaves the loads behind:
```llvm
entry:
%w0 = load i32, ptr %w, align 4
br label %f0
f0:
br label %l0
l0:
%p1 = getelementptr inbounds nuw i8, ptr %w, i64 4
%w1 = load i32, ptr %p1, align 4
br label %f1
f1:
br label %l1
l1:
%p2 = getelementptr inbounds nuw i8, ptr %w, i64 8
%w2 = load i32, ptr %p2, align 4
br label %f2
f2:
br label %l2
l2:
%x0 = xor i32 %a, %b
%s0 = add i32 %x0, %w0
%a1 = call i32 @llvm.fshl.i32(i32 %s0, i32 %s0, i32 11)
%x1 = xor i32 %a1, %b
%s1 = add i32 %x1, %w1
%a2 = call i32 @llvm.fshl.i32(i32 %s1, i32 %s1, i32 14)
%x2 = xor i32 %a2, %b
%s2 = add i32 %x2, %w2
%a3 = call i32 @llvm.fshl.i32(i32 %s2, i32 %s2, i32 15)
ret i32 %a3
```
Expected: the instructions stay in their blocks, as with `-instcombine-code-sinking=false`. Once SimplifyCFG merges the blocks (`-passes=instcombine,simplifycfg`), the sunk version has all the loads first and all the arithmetic after them. With many iterations on x86 this costs spills.
The chain comes from fully unrolling a loop with a `?:` on the induction variable. SCCP folds the branches of each `?:`, and the next InstCombine runs before JumpThreading and SimplifyCFG merge the blocks.
### Real-world impact
This shows up in the RIPEMD-160 precompile of [evmone](https://github.com/ipsilon/evmone), an Ethereum Virtual Machine implementation. Each of the 80 steps of the compression function loops over the two lines, and the `?:` selects the boolean function for each line:
```cpp
template <size_t J>
[[gnu::always_inline]] inline void step(State z[L], const std::byte* block) noexcept
{
static constexpr auto I = J / B; // round index
for (size_t i = 0; i < L; ++i) // L = 2
{
const auto w = load_le<uint32_t>(&block[sizeof(uint32_t) * word_index[i][J]]);
// ...
const auto f = (i == 0) ? boolean_fn<I>(b, c, d) : boolean_fn<R - 1 - I>(b, c, d);
// ...
}
}
```
https://github.com/ipsilon/evmone/pull/1800 marked `step<J>()` [`[[gnu::always_inline]]`](https://github.com/ipsilon/evmone/blob/8411c60e9c70d4c36653f8d1f2886cd3adcacac6/lib/evmone_precompiles/ripemd160.cpp#L125) because GCC needs it: GCC 14 to 16 take 36k to 38k instructions per hash of 1 KiB without it and about 27.5k with it. Clang 23 gets slower with it: 29.4k instead of 28.4k (+3.5%), and `compress()` grows from 1657 to 1720 instructions. Since clang 18 the AlwaysInliner runs before the CGSCC inliner (https://reviews.llvm.org/D143624), so the 80 small loops are unrolled inside the big `compress()`. Without the attribute, clang still inlines every `step<J>()`, but unrolls its loop first, so the chain never forms in `compress()`.
A standalone copy, with `compress_src` built from `[[gnu::always_inline]]` steps and `compress_tgt` from plain `inline` ones: https://godbolt.org/z/qxG34cz7K (`-O3 -march=x86-64-v2`). Instructions in each function:
| | `compress_src` (`always_inline`) | `compress_tgt` (`inline`) |
|---|---|---|
| clang trunk | 1720 | 1659 |
| clang trunk `-mllvm -instcombine-code-sinking=false` | 1641 | 1659 |
| clang 17 | 1676 | 1676 |
In `compress_src` 47 of the 48 loads come before the first rotate, and the 61 extra instructions are all `mov`s: 36 spills and reloads and 25 register copies. The same happens at `-O2` and with `-march=x86-64-v3` (1620 vs 1565). AArch64 shows no difference.
This is similar to #216368, where the arithmetic sinks into a conditional block after a full unroll and a store keeps the loads behind. Here the destination is the only successor, so not sinking would be enough.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs