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

Reply via email to