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

[androm3da]

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:

/*
 * 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 <sysroot> ./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 <stdio.h>

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;
}

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:

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

[llvmorg-github-actions]

@llvm/issue-subscribers-backend-hexagon

Author: Brian Cain (androm3da)

Details

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:

/*
 * 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 <sysroot> ./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 <stdio.h>

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;
}

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:

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

[iajbar]

I verified this is a different pipeliner defect than #208943: it corrupts the SHA schedule loop even though the modulo scheduler ultimately fails to produce a schedule for it.