Cranelift: missing optimization on icmp + select + icmp + brif

[playX18]

Thanks for filing an issue! Please fill out the TODOs below.

.clif Test Case

function %a(i64) -> i64 {
block0(v2: i64):
    v3 = band_imm v2, -562949953421310
    v4 = icmp_imm eq v3, 0
    v5 = iconst.i64 6
    v6 = iconst.i64 7
    v7 = select v4, v6, v5  ; v6 = 7, v5 = 6
    v8 = icmp_imm eq v7, 6
    brif v8, block2, block1

block1:
    v9 = iconst.i64 100
    jump block3(v9)

block2:
    v10 = iconst.i64 101
    jump block3(v10)

block3(v11: i64):
    return v11
}

Steps to Reproduce

1. Have a code that generates icmp + select and then generates another icmp together with brif
2. Compile

Expected Results

There is potential rewrite possible here where select and icmp can be removed to simply checking result of v3 or v4 in the snippet above.

Actual Results

Code snippet above will generate x86 code with test, cmove, test, jne sequence which is not optimal.

   7:   41 b9 06 00 00 00       mov    $0x6,%r9d
   d:   48 85 15 2c 00 00 00    test   %rdx,0x2c(%rip)        # 40 <.Lfn0+0x40>
  14:   49 89 d3                mov    %rdx,%r11
  17:   4c 0f 44 0d 29 00 00    cmove  0x29(%rip),%r9        # 48 <.Lfn0+0x48>
  1e:   00 
  1f:   49 83 f9 06             cmp    $0x6,%r9
  23:   0f 84 0d 00 00 00       je     36 <.Lfn0+0x36>

Versions and Environment

Cranelift version or commit: 0.123.1

Operating system: Fedora 42

Architecture: x86_64

[alexcrichton]

Slightly more backgrond on Zulip too

[cfallin]

@playX18 could you clarify a bit more what rewrite you would expect here? There are at least two that are conceptually possible:

• Do you expect the v8 = icmp_imm eq v7, 6 comparison to "see through" the v7 = select ..., with both of its inputs equal to constants, and remove this icmp in favor of using the select's condition (v4) directly?

  That seems feasible with a rewrite rule -- feel free to contribute a PR if you're up for it! It would go in the ISLE mid-end rules we have in cranelift/codegen/src/opts/. Keep in mind that icmp_imm will be legalized to an icmp before the mid-end runs, so you'll want to match on something like (icmp _ (IntCC.Equal) (select _ inner_cond (iconst_u _ k1) (iconst_u _ k2)) (iconst_u _ k1)) and rewrite to inner_cond with a side condition that k1 != k2 (and probably the other variations on that, e.g. NotEqual, and opposite argument order).

• Do you expect that the brif on v8 with an if-else diamond computing two values and then merging them with a blockparam will become a select (i.e., no control flow)?

  This one is considerably harder: it requires support for seeing through blockparams during mid-end opts, which has very subtle interactions with the single-pass acyclic nature of our rewrite system; and it requires editing the control-flow graph, which also has complex interactions with the way that the rewrite pass works. At some point we'd like to support this, but it would require pretty deep investment from core Cranelift folks to think it through.