Issue 243060
Summary [DAGCombiner][X86] 2-word compare as a select condition becomes a cmov chain instead of a borrow chain
Labels backend:X86, missed-optimization, llvm:SelectionDAG
Assignees
Reporter chfast
    A select on the unsigned compare of 2-word numbers `(x1, x0)` and `(y1, y0)`, `x1 <u y1 || (x1 == y1 && x0 <u y0)` (https://godbolt.org/z/sjzznvMYn):

```llvm
define i32 @select_ult2(i64 %x0, i64 %x1, i64 %y0, i64 %y1, i32 %a, i32 %b) {
  %lo = icmp ult i64 %x0, %y0
  %hi = icmp ult i64 %x1, %y1
  %eq = icmp eq i64 %x1, %y1
  %t = and i1 %eq, %lo
  %c = or i1 %hi, %t
  %r = select i1 %c, i32 %a, i32 %b
  ret i32 %r
}
```

`llc -mtriple=x86_64`:

```asm
select_ult2:
 cmpq    %rdx, %rdi
        movl    %r9d, %eax
        cmovbl  %r8d, %eax
 cmpq    %rcx, %rsi
        cmovnel %r9d, %eax
        cmovbl  %r8d, %eax
        retq
```

Expected, as llc already emits for a select on `icmp ult i128`:

```asm
select_ult2:
        movl    %r8d, %eax
 cmpq    %rdx, %rdi
        sbbq    %rcx, %rsi
        cmovael %r9d, %eax
 retq
```

AArch64 already gives `cmp; sbcs; csel`.

Since #193707, `combineOrOfSetCCToUSUBOCarry()` (called from `visitOR`) rebuilds the borrow chain for this compare, and the compare alone is `cmp; sbb; setb`. But DAGCombiner visits the `select` first: `visitSELECT` splits `select (or a, b), x, y` into a chain of selects, and then the `and` too (`shouldNormalizeToSelectSequence()` is true on X86). So `visitOR` never sees the `or`:

```
Combining: t20: i32 = select t19, t10, t12
 ... into: t26: i32 = select t15, t10, t25
Combining: t25: i32 = select t18, t10, t12
 ... into: t28: i32 = select t17, t27, t12
```

The difference grows with the number of words: with 4 words through `__builtin_subcll`, the select is an 18-instruction `cmov` chain on x86-64.

Found while optimizing evmone's (Ethereum VM) comparison 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