| Issue |
204098
|
| Summary |
[AVR][AggressiveInstCombine] TruncInstCombine bails on K&R uint8_t loop with outside-graph icmp user — emits 16-bit code where 8-bit is achievable
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
ravn
|
I have been doing some code density work on z80 backend optimizations in an out-of-tree fork with the help of Claude Code comparing llvm-z80 with z88dk sdcc and in the process found a pattern that also applies to the in-tree AVR backend.
This is only my second bug report to this project (the first is #202112, a related missed-opt in the same pass), so I would appreciate gentle help if it for any reason could be improved.
Background: The z80 is challenging because it has very few registers and limited 16-bit operations, so it is very important to get `i8` codegen for `uint8_t` patterns. The AVR is not as constrained, but the pattern also applies to it.
The root cause appears to be that `TruncInstCombine` bails on the whole rewrite when it sees an outside-graph user that isn't a `ZExt`/`SExt`, even if that user is an `icmp` whose operands are provably narrow under `KnownBits`.
I had Claude create a proof-of-concept fix, which gave a concrete 27.8% cycle improvement and ~31 % smaller code on the test case listed below for the AVR platform. As I understand Claude may fix the symptom but not the underlying cause I have not included its fix here to avoid distraction. If you agree on the cause I would be happy to share the work.
---
Note: The rest of the text and the test code is generated by Claude.
---
## Summary
On AVR (`atmega328p`, `clang --target=avr -Os`), `TruncInstCombine` (in `AggressiveInstCombine`) bails on the whole _expression_-graph rewrite when an in-graph value has an outside-graph user that isn't a `ZExt`/`SExt` — even when the outside user is an `icmp` whose operands are both provably narrow under `KnownBits`. The K&R-style `uint8_t` arithmetic pattern that's idiomatic in 1980s embedded-C cryptographic and protocol-parser code hits this path: a `do { ... if (atb == x) break; ... } while (++i)` loop ends up carrying its `atb` value as `i16` through the loop, with 16-bit AVR `cp + cpc` compares and `movw` register-pair shuffles in the hot path.
A reduction extracted verbatim from a public-domain AES-256 helper (Ilya O. Levin's `aes256.c`, 2007-2009) shows the function compiles to **70 bytes** on stock LLVM where **48 bytes** is achievable, and executes **~27.8 % more cycles** on a 256-input sweep (measured on simavr with Timer1 at clk/1).
The bail is at `getBestTruncatedType` in `llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp`:
```cpp
for (auto *U : I->users())
if (auto *UI = dyn_cast<Instruction>(U))
if (UI != CurrentTruncInst && !InstInfoMap.count(UI)) {
if (!IsExtInst)
return nullptr; // <-- bails here, forfeits the whole rewrite
...
```
## Reduction (verbatim)
```c
// avr-gflog-missed-opt.c — public-domain provenance below.
#include <stdint.h>
uint8_t gf_log(x)
uint8_t x;
{
uint8_t atb = 1, i = 0, z;
do {
if (atb == x) break;
z = atb; atb <<= 1; if (z & 0x80) atb ^= 0x1b; atb ^= z;
} while (++i > 0);
return i;
}
```
Build:
```sh
clang --target=avr -mmcu=atmega328p -Os -std=c89 \
-Wno-deprecated-non-prototype \
-c avr-gflog-missed-opt.c -o gflog.o
avr-size --format=berkeley gflog.o
avr-objdump -d gflog.o
```
Provenance: extracted verbatim from `gf_log` in Ilya O. Levin's public-domain AES-256 implementation (`literatecode.com`, 2007-2009). The K&R declaration `uint8_t gf_log(x) uint8_t x; { ... }` is preserved from the upstream source.
## Observed
```
text data bss dec hex filename
70 0 0 70 46 gflog.o
```
Hot loop (selected, annotated):
```
movw r22, r30 ; 16-bit register-pair shuffle
andi r23, 0x00
cp r22, r24 ; ← 16-bit compare (cp + cpc)
cpc r23, r25 ; against K&R-promoted i16 arg
breq +42
...
andi r30, 0x80
andi r31, 0x00 ; ← redundant high-byte mask
cp r30, r1
cpc r31, r1
...
movw r30, r22 ; ← another 16-bit shuffle
```
## Expected
```
text data bss dec hex filename
48 0 0 48 30 gflog.o
```
```
cp r18, r24 ; 8-bit compare; both operands i8
breq +32
...
add r22, r22 ; 8-bit shift
and r23, r23 ; sign-bit test
brpl +2
eor r22, r20 ; xor 0x1B
eor r18, r22
```
## IR diff (`clang -emit-llvm -S -Os`)
Observed (i16 phi, outside-graph icmp blocks the narrowing):
```llvm
define i8 @gf_log(i16 noundef %0) {
%2 = and i16 %0, 255 ; the K&R promotion's mask survives
br label %3
3:
%4 = phi i8 [ 0, %1 ], [ %17, %8 ]
%5 = phi i16 [ 1, %1 ], [ %16, %8 ] ; ← i16 phi
%6 = and i16 %5, 255
%7 = icmp eq i16 %6, %2 ; ← outside-graph icmp user
br i1 %7, label %19, label %8
8:
%9 = trunc i16 %5 to i8
%10 = shl i8 %9, 1
%11 = and i16 %5, 128
%12 = icmp eq i16 %11, 0 ; ← another outside-graph icmp user
...
```
Both `%7` and `%12` are width-compatible: `%6` and `%2` are `and i16 ..., 255` (KnownBits-narrow); `%11` is `and i16 %5, 128` against constant `0` (provably narrow on both sides). Yet the bail at `getBestTruncatedType` forfeits the whole narrowing.
Expected after narrowing:
```llvm
define i8 @gf_log(i16 noundef %0) {
%2 = trunc i16 %0 to i8 ; narrow at entry
br label %3
3:
%5 = phi i8 [ 1, %1 ], [ %12, %7 ] ; i8 phi
%6 = icmp eq i8 %5, %2 ; i8 compare
...
```
## Runtime cycle witness (optional, but concrete)
A self-contained AVR cycle harness using Timer1 at clk/1 (1 tick = 1 cycle) with overflow-counting brackets a 256-input sweep of `gf_log`:
| | Observed (stock LLVM) | Expected (if narrowed) |
|---|---|---|
| Cycles, 256-call sweep | **825,294** | **595,773** |
| Cycles per call (avg) | **3,224** | **2,327** |
Delta: **−229,521 cycles (−27.8 %)**.
(Source code for the harness and reproducer wiring available on request; uses simavr's `.mmcu` console hook with `AVR_MCU_SIMAVR_CONSOLE(0x3E)`.)
## Cause
`TruncInstCombine` walks back from a `trunc` to build an _expression_ graph of narrowable operations and rebuilds them at the narrow type. The outside-user check requires every in-graph value's users to be either (a) in the graph, or (b) a `ZExt`/`SExt` that the rewrite can collapse. The bail at `getBestTruncatedType` returns `nullptr` for *any* other outside user.
This is conservative-correct, but on 8-bit-native backends — where the source-level pattern is `uint8_t` arithmetic in a loop, int-promoted to `i16` through C's integer-promotion rules — the typical loop-exit comparison `icmp <pred> %wide, %other` blocks the narrowing for the entire graph despite both operands being trivially narrow.
## Source-level workarounds attempted
We tested whether straightforward source rewrites unblock the
narrowing on stock LLVM (no compiler patches). Six variants of
the gf_log body, same loop, different surface forms:
| Variant | Change vs original | Size on stock LLVM |
|---|---|---|
| v0 | original K&R declaration | **70 B** (the bug) |
| v1 | ANSI prototype only (`uint8_t gf_log(uint8_t x)`) | 62 B (partial) |
| v2 | K&R + cast in icmp (`if (atb == (uint8_t)x)`) | 70 B (no change) |
| v3 | K&R + local `uint8_t` copy (`uint8_t xb = x; if (atb == xb)`) | 70 B (no change) |
| v4 | ANSI + sign-bit form (`if ((int8_t)z < 0)` instead of `if (z & 0x80)`) | **48 B (fully unblocks)** |
| v5 | ANSI + branchless materialize of the bit-test mask | 66 B (partial) |
| v6 | prototype declaration + K&R definition body | 62 B (same as v1) |
| v7 | prototype + K&R body + sign-bit form | **48 B (same as v4)** |
Findings:
- **The two "obvious" workarounds — casting `(uint8_t)x` in the icmp
and copying `x` to a local — achieve nothing.** InstCombine doesn't
fold the cast or local before TruncInstCombine sees the IR, so the
i16 phi reaches the pass byte-identically to v0.
- **ANSI prototype alone (v1) is partial.** It unblocks the loop-exit
icmp side (the `atb == x` comparison narrows because `%0` arrives
as i8 in the IR), but the `z & 0x80` bit-test still produces an
outside-graph `and i16 %z, 128` shape that blocks the narrowing of
the phi-rooted graph.
- **The K&R-vs-ANSI distinction is at the *prototype*, not the
definition body.** A separate prototype declaration in scope
before a K&R-style definition (v6) gives byte-identical IR to a
full ANSI conversion (v1). Programmers who want to preserve the
K&R definition syntax can add the prototype without rewriting the
function body.
- **Two source-level changes together unblock the narrowing.**
ANSI prototype (or prototype-before-K&R-body) + rewriting the
bit-test as `(int8_t)z < 0` (which lowers to `icmp slt i8 %z, 0` —
no `and` operation in the IR) produces the optimal 48-byte codegen
on stock LLVM (variants v4 and v7).
In other words, the issue is concrete enough that "just rephrase the
C" is not a 30-second answer. A C programmer would have to anticipate
two specific IR shapes — the outside-graph icmp from int-promotion AND
the outside-graph and-mask from the bit-test — and rewrite both. The
two unobvious source changes that work are independent of each other;
one is a function signature change and the other is a bit-test idiom
change, and most embedded-C programmers would reach for the cast or
local copy first.
(Variant source available alongside the reducer if useful for review.)
## Direction (not a patch)
Admit the outside-graph user when **both** of the following hold:
1. It is an `ICmpInst` whose predicate is value-preserving at the narrow width. Equality/inequality (eq/ne) and unsigned predicates are always safe. Signed predicates require the narrow-width sign bit to stay clear (i.e. operands fit in `NarrowBits − 1`).
2. Both operands are provably narrow under `KnownBits`:
- The *in-graph* operand (the GraphValue) must have `computeKnownBits(GraphValue).getMaxValue().getActiveBits() <= NarrowBits` (the *fit-bits* threshold above for signed predicates). **This gate is load-bearing.**
- The *other* operand fits if it's a `ConstantInt` whose `getActiveBits() <= NarrowBits`, or a single-use variable whose `KnownBits` proves the same.
Rewrite the admitted icmp as `icmp <pred> (trunc lhs to NarrowTy), (trunc rhs to NarrowTy)` before the phi-erase loop in `ReduceExpressionGraph` (so still-wide icmp operands don't get RAUW'd to poison).
**Soundness boundary.** The in-graph KnownBits gate is the critical step. Without it, a graph value that fits in the narrow type for the in-graph users (the trunc) may have high bits set at the outside-graph icmp, and narrowing the icmp would change its result. Concrete witness: a related extension we carried on an out-of-tree fork for ~6 weeks omitted this gate and produced wrong results on the shape `%add = add i32 %x, 1; icmp ult i32 %add, (and y, 255)` when `%x = 65636` (low-16-bits of `%add` = 100 < 200 but full `%add` = 65637 > 200). The sound version with the gate passes our lit suite (304 lines, available on request).
A parallel admission for outside-graph `(and X, Const)` users where `Const fits the narrow type` is sound regardless of in-graph KnownBits because the mask discards high bits unconditionally. Same out-of-tree extension covers it with its own lit test.
## Notes for reviewers
- This is filed against AVR because the AVR reduction is self-contained and the size + cycle deltas are concrete. The optimization is target-independent middle-end and should also benefit MSP430, the in-tree experimental 6502/65816 ports, and any backend whose narrow ops are materially cheaper than its wide ones.
- We carry sound versions of both extensions as out-of-tree commits on an experimental Z80 backend; happy to share the lit witnesses, the runtime soundness probes, and the diffs on request if any of this is useful for upstream review.
- Filed standalone rather than as an RFC because the AVR reproducer and the cycle witness are concrete enough. Happy to mirror to a Discourse RFC thread if maintainers prefer the broader discussion venue.
## Reproducer files (available on request)
- `avr-gflog-missed-opt.c` — single-file C reduction (above)
- `avr-gflog-runtime.c` — Timer1 cycle harness for the runtime witness
- The two together build into an `.elf` that runs cleanly under simavr master (apt's pre-1.7 simavr lacks the `.mmcu` section parser)
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
