| Issue |
208943
|
| Summary |
hexagon miscompile bn_mp_div_2d.c at -O2
|
| Labels |
backend:Hexagon
|
| Assignees |
iajbar
|
| Reporter |
androm3da
|
# Hexagon Clang 22.1.8 Miscompilation: bn_mp_div_2d.c at -O2
## Summary
Hexagon clang 22.1.8 miscompiles `bn_mp_div_2d.c` (from libtommath, bundled with dropbear-2026.91) at optimization level `-O2` and `-O3`. The carry propagation in the right-shift loop is broken: when processing 3+ digits, the carry from digit N-2 is incorrectly used instead of the carry from digit N-1.
## Compiler Version
```
clang version 22.1.8
Target: hexagon-unknown-linux-musl
Thread model: posix
InstalledDir: /local/mnt/workspace/upstream/buildroot/output/host/opt/ext-toolchain/x86_64-linux-gnu/bin
Build config: +assertions
```
## Source File
`bn_mp_div_2d.c` from libtommath (part of dropbear-2026.91). The preprocessed source is provided in `bn_mp_div_2d.i`.
The relevant function:
```c
mp_err mp_div_2d(const mp_int *a, int b, mp_int *c, mp_int *d) {
mp_digit D, r, rr;
int x;
mp_err err;
if (b <= 0) { return mp_copy(a, c); }
if ((err = mp_copy(a, c)) != MP_OKAY) { return err; }
if (b >= MP_DIGIT_BIT) { mp_rshd(c, b / MP_DIGIT_BIT); }
D = (mp_digit)(b % MP_DIGIT_BIT);
if (D != 0u) {
mp_digit *tmpc, mask, shift;
mask = ((mp_digit)1 << D) - 1uL;
shift = (mp_digit)MP_DIGIT_BIT - D;
tmpc = c->dp + (c->used - 1);
r = 0;
for (x = c->used - 1; x >= 0; x--) {
rr = *tmpc & mask;
*tmpc = (*tmpc >> D) | (r << shift);
--tmpc;
r = rr;
}
}
mp_clamp(c);
return MP_OKAY;
}
```
Where `MP_DIGIT_BIT = 28`, `mp_digit = uint32_t`.
## Reproduction
### Compile commands
```sh
# Produces WRONG results:
hexagon-unknown-linux-musl-clang -mv68 -O2 -c bn_mp_div_2d.c -o bn_mp_div_2d.O2.o
# Produces CORRECT results:
hexagon-unknown-linux-musl-clang -mv68 -O0 -c bn_mp_div_2d.c -o bn_mp_div_2d.O0.o
hexagon-unknown-linux-musl-clang -mv68 -O1 -c bn_mp_div_2d.c -o bn_mp_div_2d.O1.o
hexagon-unknown-linux-musl-clang -mv68 -Os -c bn_mp_div_2d.c -o bn_mp_div_2d.Os.o
```
### Test case
See `test_reproducer.c`. Link against the -O2 compiled object:
```sh
hexagon-unknown-linux-musl-clang -mv68 -O0 -static test_reproducer.c bn_mp_div_2d.O2.o -o test
qemu-hexagon ./test
```
### Input
```
mp_int with:
used = 3
dp[0] = 0x0E12C420
dp[1] = 0x0B17D1F2
dp[2] = 0x00000006
Call: mp_div_2d(&a, 4, &c, NULL) (right-shift by 4 bits)
```
### Expected output
```
c.dp[0] = 0x02E12C42 (carry of 0x2 from dp[1])
c.dp[1] = 0x06B17D1F (carry of 0x6 from dp[2])
c.dp[2] = 0x00000000
```
### Actual output (with -O2)
```
c.dp[0] = 0x06E12C42 (WRONG: carry of 0x6 from dp[2], skipping dp[1])
c.dp[1] = 0x06B17D1F (correct)
c.dp[2] = 0x00000000 (correct)
```
## Root Cause Analysis
At -O2, the compiler unrolls the loop by 8 and generates an epilogue loop for the
remainder. The epilogue has this structure:
```asm
.LBB0_14: // epilogue entry
p0 = cmp.gtu(r3,#1) // r3 = remaining count (3 in our case)
r7 = add(r3,#-1) // loop trip count = 2
r6 = memw(r1+#0) // load highest digit
loop0(.LBB0_16,r7) // hardware loop, 2 iterations
r3 = lsr(r6,r17) // shift highest digit
r5 = and(r6,r2) // extract carry from highest digit (=0x6)
if (!p0) jump .LBB0_18
r6 = r5 // r6 = carry
.LBB0_16: // loop body
{ r3 |= asl(r4,r0) // combine incoming carry with shifted value
r4 = r6 // save current carry for next iteration
r7 = memw(r1+#-4) // load next digit
memw(r1++#-4) = r3.new } // store result
{ r3 = lsr(r7,r17) // shift newly loaded digit
r6 = and(r7,r2) } // extract carry
:endloop0
// %bb.17: // BUG IS HERE
r4 = r5 // WRONG: overwrites r4 (carry from dp[1] = 0x2)
// with r5 (carry from dp[2] = 0x6)
.LBB0_18: // final store
{ r3 |= asl(r4,r0) // uses wrong carry!
memw(r1++#-4) = r3.new }
```
The `r4 = r5` instruction after the loop is incorrect. At this point:
- `r4` contains the correct carry from the last loop iteration (0x2, from dp[1])
- `r5` contains the carry extracted from the FIRST element (dp[2]) during setup (0x6)
The compiler's code generation is wrong: it should NOT restore r5 into r4 after the
loop when the loop executed 2+ times. This instruction appears to be dead code from
the single-iteration case (where r5 IS the correct carry) that was incorrectly left
in the multi-iteration path.
- `bn_mp_div_2d.i` - Preprocessed source - [bn_mp_div_2d.i.txt](https://github.com/user-attachments/files/29929842/bn_mp_div_2d.i.txt)
- `test_reproducer.c` - Standalone test harness [test_reproducer.c](https://github.com/user-attachments/files/29929841/test_reproducer.c)
## Reproduced on main / regression status
Also seen on clang built from upstream `main` 5302608fec8ed7d8ce300d4a0d599a26b24dc972).
**This is not a regression** -- the miscompilation has been present since at least clang 16, and is still present on current `main`.
## Flags to reproduce
```
hexagon-unknown-linux-musl-clang \
-mv68 -O2 \
-DLTM_NOTHING \
-DMP_28BIT \
-I. \
-c bn_mp_div_2d.c \
-o bn_mp_div_2d.O2.o
```
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
