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

Reply via email to