Issue 243056
Summary [SelectionDAG] Borrow of `0 - zext(i1 c)` is not folded to `c` in an expanded i128 compare
Labels missed-optimization, llvm:SelectionDAG
Assignees
Reporter chfast
    `@src` compares 2-word numbers as i128 with the low words' borrow in the low half, `(x1, 0) <s (y1, x0 <u y0)`. `@tgt` is the same compare written directly on `(x1, x0)` and `(y1, y0)`.

```llvm
define i1 @src(i64 %x0, i64 %x1, i64 %y0, i64 %y1) {
  %b = icmp ult i64 %x0, %y0
  %x1z = zext i64 %x1 to i128
  %x = shl nuw i128 %x1z, 64
  %y1z = zext i64 %y1 to i128
  %y1s = shl nuw i128 %y1z, 64
  %bz = zext i1 %b to i128
  %y = or disjoint i128 %y1s, %bz
  %r = icmp slt i128 %x, %y
  ret i1 %r
}

define i1 @tgt(i64 %x0, i64 %x1, i64 %y0, i64 %y1) {
  %x0z = zext i64 %x0 to i128
  %x1z = zext i64 %x1 to i128
  %x1s = shl nuw i128 %x1z, 64
  %x = or disjoint i128 %x1s, %x0z
  %y0z = zext i64 %y0 to i128
  %y1z = zext i64 %y1 to i128
 %y1s = shl nuw i128 %y1z, 64
  %y = or disjoint i128 %y1s, %y0z
  %r = icmp slt i128 %x, %y
  ret i1 %r
}
```

Alive2 (with i8 halves, i64 times out): https://alive2.llvm.org/ce/z/-AbaDY

llc, https://godbolt.org/z/qvnd8v3jc:

```asm
src: # x86-64
        xorl    %eax, %eax
        cmpq    %rdx, %rdi
 sbbq    %rax, %rax
        sbbq    %rcx, %rsi
        setl    %al
 retq
tgt:
        cmpq    %rdx, %rdi
        sbbq    %rcx, %rsi
 setl    %al
        retq
```

```asm
src: // AArch64
        cmp     x0, x2
        cset    w8, lo
        cmp xzr, x8
        sbcs    xzr, x1, x3
        cset    w0, lt
 ret
tgt:
        cmp     x0, x2
        sbcs    xzr, x1, x3
        cset w0, lt
        ret
```

After type legalization `@src` is:

```
 t34: i8 = setcc t2, t6, setult:ch
        t45: i64 = zero_extend t34
 t43: i64,i8 = usubo Constant:i64<0>, t45
    t44: i8 = setcccarry t4, t8, t43:1, setlt:ch
```

The borrow of `0 - zext(b)` is `b`, so the `usubo` can be dropped and `b` used as the carry-in directly, which gives the `@tgt` code. Instead, x86 materializes the borrow with `xor` + `sbb %rax, %rax` (which only copies CF), and AArch64 with `cset` + `cmp xzr`. The same happens with `icmp ult`.

Found while looking for a C spelling of intx's (multi-precision integers) signed 256-bit compare that compiles to the borrow chain: the lower words through `__builtin_subcll`, then the top words as `(__int128)((u128)x[3] << 64) < (__int128)(((u128)y[3] << 64) | borrow)`.

_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to