| 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