Issue 244521
Summary [fuzzer-found][DAGCombiner] visitUADDOLike folds `uaddo X, (uaddo_carry Y, 0, C):1` as if the carry-out were the sum, so the i256 multiply's high words are wrong on ARM
Labels backend:ARM, miscompilation, llvm:SelectionDAG, generated by fuzzer
Assignees
Reporter YuanchengJiang
    The following code:

IR-only reproducer: ARM caps `_BitInt` at 128 bits, and a visible power-of-two multiplier becomes a shift before codegen. Here the multiplier only becomes a constant inside SelectionDAG, through a `select` of an `icmp` of constants. `@f` returns the high 128 bits of `zext(x) * 2^126`, i.e. `x >> 2`. `main` prints the four words (low first) for two inputs, then `0` on success and `1` on mismatch.

```llvm
; ARM: (uaddo X, (uaddo_carry Y, 0, C):1) is folded to (uaddo_carry X, Y, C) -- DAGCombiner::visitUADDOLike
; does not check that the uaddo_carry operand is result 0 (the sum); here it is result 1 (the carry-out).
; @f computes the high 128 bits of (zext x) * 2^126, i.e. x >> 2. The multiplier only becomes a constant
; inside SelectionDAG (select of an icmp of constants, fuzzer style), so the IR passes do not turn it into a shift.
;   llc -O2 -mtriple=armv7-linux-gnueabihf repro.ll   (also thumbv7, thumbv7m; -O0 is wrong too)
; main prints the 4 words (low first) of f(x) for two inputs and then "0" on success / "1" on mismatch.
target triple = "armv7-unknown-linux-gnueabihf"
@fmt = private constant [4 x i8] c"%d\0A\00"
declare i32 @printf(ptr, ...)
@in0 = global i128 340282366920938463463374607431768211455
@in1 = global i128 182996295015194644789088449406157730320
define i128 @f(i128 %x) noinline {
 %c = icmp eq i128 85070591730234615865843651857942052864, 85070591730234615865843651857942052864
  %k = select i1 %c, i128 85070591730234615865843651857942052864, i128 7
  %xe = zext i128 %x to i256
  %ke = zext i128 %k to i256
  %p = mul i256 %xe, %ke
  %h = lshr i256 %p, 128
  %r = trunc i256 %h to i128
  ret i128 %r
}
define void @pr(i128 %r) {
  %s0 = lshr i128 %r, 0
  %w0 = trunc i128 %s0 to i32
 call i32 (ptr, ...) @printf(ptr @fmt, i32 %w0)
  %s1 = lshr i128 %r, 32
 %w1 = trunc i128 %s1 to i32
  call i32 (ptr, ...) @printf(ptr @fmt, i32 %w1)
  %s2 = lshr i128 %r, 64
  %w2 = trunc i128 %s2 to i32
  call i32 (ptr, ...) @printf(ptr @fmt, i32 %w2)
  %s3 = lshr i128 %r, 96
  %w3 = trunc i128 %s3 to i32
  call i32 (ptr, ...) @printf(ptr @fmt, i32 %w3)
 ret void
}
define i32 @main() {
entry:
  %x0 = load volatile i128, ptr @in0
  %r0 = call i128 @f(i128 %x0)
  call void @pr(i128 %r0)
  %b0 = icmp ne i128 %r0, 85070591730234615865843651857942052863
  %z0 = zext i1 %b0 to i32
  %x1 = load volatile i128, ptr @in1
  %r1 = call i128 @f(i128 %x1)
 call void @pr(i128 %r1)
  %b1 = icmp ne i128 %r1, 45749073753798661197272112351539432580
  %z1 = zext i1 %b1 to i32
  %bad = or i32 %z0, %z1
  call i32 (ptr, ...) @printf(ptr @fmt, i32 %bad)
  ret i32 %bad
}
```

Resulted in this output (`llc -O2 -mtriple=armv7-unknown-linux-gnueabihf`, run on an ARM emulator):
```
-1
-1
1073741822
1073741824
496307332
-4772186
-1
577434491
1
```

| input | expected `x >> 2` (words, low first) | -O2 |
|---|---|---|
| all ones | -1 -1 -1 1073741823 | -1 -1 **1073741822 1073741824** |
| second input | 496307332 -4772186 -1068969639 577434491 | 496307332 -4772186 **-1** 577434491 |

`-O0` gives the expected values. thumbv7 and thumbv7m are affected too.

Trunk: https://godbolt.org/z/WzxqYr8hE

Root cause: `DAGCombiner::visitUADDOLike` folds `(uaddo X, (uaddo_carry Y, 0, Carry))` into `(uaddo_carry X, Y, Carry)` when `Y + 1` cannot overflow. It never checks which result of the `uaddo_carry` is used. Here the operand is result 1, the carry-out. Under the fold's own condition that carry-out is always 0, yet the fold adds `Y + Carry` (here `x1 >> 2`) into the sum. The corresponding folds in `visitADD` and `visitSUB` do check `getResNo() == 0`.

Suggested fix: add `N1.getResNo() == 0 &&` to the condition in `visitUADDOLike`. Validated locally: with it the program prints the expected words and `0`, the AGT check no longer fires, and 291 llc RUN lines of the ARM/Thumb2 and X86/AArch64/RISC-V tests that use uaddo/addcarry give unchanged output.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to