llvm / llvm/llvm-project

[hexagon] software pipeliner corrupts SHA-512 message-schedule loop at -O2/-O3

Open
#209,946 2 comments 0 reactions 1 assignee Claimed by @iajbar View on GitHub
backend:Hexagon
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

At `-O2`/`-O3`, the Hexagon backend miscompiles a pure 64-bit integer loop (the SHA-512 message-schedule recurrence, `W[i] = W[i-16] + s0 + W[i-7] + s1` with two 64-bit rotate/shift terms `s0`, `s1`). The program computes the wrong answer at runtime. `-O0`, `-O1`, `-Os` all produce the correct answer, as does x86-64 at any optimization level.

The result is also **non-deterministic across otherwise-identical runs of the same `-O2` binary** -- it varies with `argv` and `cwd`, even though the program takes no input and performs no I/O other than `printf`.

This is a real-world-impacting bug: it is the SHA-512 implementation used by dropbear's bundled libtomcrypt. A miscompiled SHA-512 corrupts ed25519 key generation and signing (ed25519 is the only common SSH algorithm that uses
SHA-512), causing OpenSSH to reject signatures from an affected host with
"incorrect signature".

Could be related to #208943 ?

# pipeliner

Disabling the Hexagon/generic software pipeliner (SMS modulo scheduler) fixes the bug, with everything else at `-O2` held constant:

```
llc -march=hexagon -O2 -relocation-model=pic -enable-pipeliner=false ... # PASS
llc -march=hexagon -O2 -relocation-model=pic ... # FAIL
```

`opt-bisect-limit` bisection on `llc -march=hexagon -O2` pinpoints the
transition from PASS to FAIL to exactly one pass:

```
BISECT: running pass (98) hwloops on function (schedule) <- still PASS at limit=98
BISECT: running pass (99) pipeliner on function (schedule) <- FAILS starting at limit=99
```

## Regression bisection across releases

Tested the reproducer against several hexagon-unknown-linux-musl cross toolchains, at `-O2`, run under `qemu-hexagon -cpu v68`:

| Toolchain version | Result |
|---|---|
| 16.0.5 | PASS |
| 17.0.0-rc3 | PASS |
| 18.1.2 | PASS |
| **19.1.2** | **FAIL** |
| 19.1.5 | FAIL |
| 20.1.4 | FAIL |
| 21.1.8 | FAIL |
| 22.1.0 | FAIL |
| 22.1.4 | FAIL |
| 22.1.8 | FAIL |

So this is a **regression**, introduced somewhere between the 18.1.2 and 19.1.2 release points (no cross-hexagon build for 18.1.8 or 19.1.0 was available locally to narrow the window further). It has persisted, unfixed, through 22.1.8 and reproduces on current top-of-tree (commit `d4676e649ba86d7c389e1afe6d9ed4d8443e23ef`, see below).

### Minimal repro commands

repro.c:

```c
/*
* Minimal reproducer: hexagon clang miscompiles 64-bit rotate/shift/add code
* at -O2/-O3. This is the SHA-512 message-schedule loop (pure 64-bit integer
* arithmetic, no crypto/library dependencies).
*
* Correct result (x86-64 any -O, and hexagon at -O0/-O1/-Os): 5aea16350b8629e8
* hexagon clang -O2/-O3 produces: a7bb380548394629
*
* x86-64: cc -O2 repro.c -o r && ./r -> PASS
* hexagon: clang -O2 repro.c -o r && qemu-hexagon -L ./r -> FAIL
* clang -O0/-O1/-Os -> PASS
*
* Toolchain observed: hexagon-unknown-linux-musl clang 23.0.0
* (llvm-project 753195e74f9b27b7165baf464aee23d0424216b6)
* (same family as https://github.com/llvm/llvm-project/issues/208943, the
* libtommath 64-bit miscompile; both are 64-bit arithmetic on a 32-bit target).
*
* Real-world impact: this is the SHA-512 used by dropbear's bundled libtomcrypt.
* A miscompiled SHA-512 corrupts ed25519 key generation and signing (ed25519 is
* the only common SSH algorithm that uses SHA-512), so an ed25519 host key
* produces signatures OpenSSH rejects with "incorrect signature". RSA/ECDSA and
* the curve25519-sha256 KEX use SHA-256 and are unaffected.
*/
#include

typedef unsigned long long u64;

#define ROR64(x,n) (((x) >> (n)) | ((x) << (64 - (n))))

/* SHA-512 message schedule: W[16..79] from W[0..15]. */
__attribute__((noinline)) static void schedule(u64 W[80]) {
for (int i = 16; i < 80; i++) {
u64 s0 = ROR64(W[i-15], 1) ^ ROR64(W[i-15], 8) ^ (W[i-15] >> 7);
u64 s1 = ROR64(W[i-2], 19) ^ ROR64(W[i-2], 61) ^ (W[i-2] >> 6);
W[i] = W[i-16] + s0 + W[i-7] + s1;
}
}

int main(void) {
u64 W[80];
for (int i = 0; i < 16; i++)
W[i] = 0x0123456789abcdefULL * (i + 1) + i;
schedule(W);

u64 sum = 0;
for (int i = 0; i < 80; i++) sum += W[i] * (i + 1);

u64 expected = 0x5aea16350b8629e8ULL;
printf("sum = %016llx\n", (unsigned long long)sum);
printf("expected = %016llx\n", (unsigned long long)expected);
int ok = (sum == expected);
printf("%s\n", ok ? "PASS" : "FAIL (hexagon -O2 miscompile)");
return ok ? 0 : 1;
}
```

```sh
TC=/local/mnt/workspace/install/clang+llvm-22.1.8-cross-hexagon-unknown-linux-musl/x86_64-ubuntu-22.04
SYSROOT=$TC/target/hexagon-unknown-linux-musl
QEMU=/local/mnt/workspace/install/qemu-v10.2.0/bin/qemu-hexagon

$TC/bin/hexagon-unknown-linux-musl-clang -O2 repro.c -o r_o2
$TC/bin/hexagon-unknown-linux-musl-clang -O1 repro.c -o r_o1

$QEMU -cpu v68 -L $SYSROOT ./r_o1 # PASS
$QEMU -cpu v68 -L $SYSROOT ./r_o2 # FAIL (hexagon -O2 miscompile)
```

Using a top-of-tree build instead of the installed 22.1.8 release reproduces identically:

```sh
LLC=obj_claude/bin/llc
CLANG=obj_claude/bin/clang

# unoptimized IR -> optimized backend, isolating the backend from clang's
# frontend/middle-end IR optimizations:
$CLANG --target=hexagon-unknown-linux-musl --sysroot=$SYSROOT \
-O2 -S -emit-llvm repro.c -o repro.O2.ll

$LLC -march=hexagon -O2 -relocation-model=pic -filetype=obj repro.O2.ll -o t.o
$CLANG --target=hexagon-unknown-linux-musl --sysroot=$SYSROOT -fuse-ld=lld t.o -o t
$QEMU -cpu v68 -L $SYSROOT ./t # FAIL

$LLC -march=hexagon -O2 -relocation-model=pic -enable-pipeliner=false -filetype=obj repro.O2.ll -o t2.o
$CLANG --target=hexagon-unknown-linux-musl --sysroot=$SYSROOT -fuse-ld=lld t2.o -o t2
$QEMU -cpu v68 -L $SYSROOT ./t2 # PASS
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.