| Issue |
243059
|
| Summary |
[DAGCombiner] Negated 2-word compare `x >=u y` (and/or of `uge`, `ne`) is not lowered to a borrow chain
|
| Labels |
missed-optimization,
llvm:SelectionDAG
|
| Assignees |
|
| Reporter |
chfast
|
`x >=u y` for 2-word numbers `(x1, x0)` and `(y1, y0)`, in the form InstCombine gives `!(x1 <u y1 || (x1 == y1 && x0 <u y0))`: the `not` is pushed into the compares (https://godbolt.org/z/8d9jPbETv):
```llvm
define i1 @uge2(i64 %x0, i64 %x1, i64 %y0, i64 %y1) {
%lo = icmp uge i64 %x0, %y0
%hi = icmp uge i64 %x1, %y1
%ne = icmp ne i64 %x1, %y1
%t = or i1 %ne, %lo
%r = and i1 %hi, %t
ret i1 %r
}
```
x86-64:
```asm
uge2:
cmpq %rdx, %rdi
setae %dl
cmpq %rcx, %rsi
setae %cl
setne %al
orb %dl, %al
andb %cl, %al
retq
```
AArch64:
```asm
uge2:
cmp x1, x3
cset w8, ne
cmp x0, x2
csinc w8, w8, wzr, lo
cmp x1, x3
csel w0, wzr, w8, lo
ret
```
Expected, as llc already emits for `icmp uge i128`:
```asm
uge2: # x86-64
cmpq %rdx, %rdi
sbbq %rcx, %rsi
setae %al
retq
```
```asm
uge2: // AArch64
cmp x0, x2
sbcs xzr, x1, x3
cset w0, hs
ret
```
#193707 added `combineOrOfSetCCToUSUBOCarry()`, which turns `or(setcc ult A, B, and(setcc eq A, B, Carry))` into `USUBO_CARRY(A, B, Carry)`. The negated form is `and(setcc uge A, B, or(setcc ne A, B, NotCarry))`, where `NotCarry` is the inverted borrow of the lower words (here `x0 >=u y0`). It could become the inverted carry of `USUBO_CARRY(A, B, not(NotCarry))`.
The difference grows with the number of words: `x <= y` for 4 words through `__builtin_subcll` (as `!(y < x)`) is 21 instructions on x86-64 instead of `cmp`, 3 × `sbb`, `setae`.
Found while optimizing evmone's (Ethereum VM) LT/GT instructions on 256-bit words.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs