cmd/compile: AMD64 `CMOV*` lowering rules depend on the values schedule

[Jorropo]

Look at theses rules:

// Lowering conditional moves
// If the condition is a SETxx, we can just run a CMOV from the comparison that was
// setting the flags.
// Legend: HI=unsigned ABOVE, CS=unsigned BELOW, CC=unsigned ABOVE EQUAL, LS=unsigned BELOW EQUAL
(CondSelect <t> x y (SET(EQ|NE|L|G|LE|GE|A|B|AE|BE|EQF|NEF|GF|GEF) cond)) && (is64BitInt(t) || isPtr(t))
    => (CMOVQ(EQ|NE|LT|GT|LE|GE|HI|CS|CC|LS|EQF|NEF|GTF|GEF) y x cond)
(CondSelect <t> x y (SET(EQ|NE|L|G|LE|GE|A|B|AE|BE|EQF|NEF|GF|GEF) cond)) && is32BitInt(t)
    => (CMOVL(EQ|NE|LT|GT|LE|GE|HI|CS|CC|LS|EQF|NEF|GTF|GEF) y x cond)
(CondSelect <t> x y (SET(EQ|NE|L|G|LE|GE|A|B|AE|BE|EQF|NEF|GF|GEF) cond)) && is16BitInt(t)
    => (CMOVW(EQ|NE|LT|GT|LE|GE|HI|CS|CC|LS|EQF|NEF|GTF|GEF) y x cond)

// If the condition does not set the flags, we need to generate a comparison.
(CondSelect <t> x y check) && !check.Type.IsFlags() && check.Type.Size() == 1
    => (CondSelect <t> x y (MOVBQZX <typ.UInt64> check))
(CondSelect <t> x y check) && !check.Type.IsFlags() && check.Type.Size() == 2
    => (CondSelect <t> x y (MOVWQZX <typ.UInt64> check))
(CondSelect <t> x y check) && !check.Type.IsFlags() && check.Type.Size() == 4
    => (CondSelect <t> x y (MOVLQZX <typ.UInt64> check))

(CondSelect <t> x y check) && !check.Type.IsFlags() && check.Type.Size() == 8 && (is64BitInt(t) || isPtr(t))
    => (CMOVQNE y x (CMPQconst [0] check))
(CondSelect <t> x y check) && !check.Type.IsFlags() && check.Type.Size() == 8 && is32BitInt(t)
    => (CMOVLNE y x (CMPQconst [0] check))
(CondSelect <t> x y check) && !check.Type.IsFlags() && check.Type.Size() == 8 && is16BitInt(t)
    => (CMOVWNE y x (CMPQconst [0] check))

// Absorb InvertFlags
(CMOVQ(EQ|NE|LT|GT|LE|GE|HI|CS|CC|LS) x y (InvertFlags cond))
    => (CMOVQ(EQ|NE|GT|LT|GE|LE|CS|HI|LS|CC) x y cond)
(CMOVL(EQ|NE|LT|GT|LE|GE|HI|CS|CC|LS) x y (InvertFlags cond))
    => (CMOVL(EQ|NE|GT|LT|GE|LE|CS|HI|LS|CC) x y cond)
(CMOVW(EQ|NE|LT|GT|LE|GE|HI|CS|CC|LS) x y (InvertFlags cond))
    => (CMOVW(EQ|NE|GT|LT|GE|LE|CS|HI|LS|CC) x y cond)

My code generate:

(CondSelect x y (Neq64 z y))

However due to how my code is written CondSelect is always scheduled before Neq (the CondSelect is from an v.reset while Neq is from b.NewValue both in the same block, so they will always act like this).
This cause the following rule to fire first:

(CondSelect <t> x y check) && !check.Type.IsFlags() && check.Type.Size() == 1
    => (CondSelect <t> x y (MOVBQZX <typ.UInt64> check))

Then:

(CondSelect <t> x y check) && !check.Type.IsFlags() && check.Type.Size() == 8 && (is64BitInt(t) || isPtr(t))
    => (CMOVQNE y x (CMPQconst [0] check))

At this point we're stuck.
Neq is gonna be rewritten to SETNE, but the rule we wanted to match:

(CondSelect <t> x y (SET(EQ|NE|L|G|LE|GE|A|B|AE|BE|EQF|NEF|GF|GEF) cond)) && (is64BitInt(t) || isPtr(t))
    => (CMOVQ(EQ|NE|LT|GT|LE|GE|HI|CS|CC|LS|EQF|NEF|GTF|GEF) y x cond)

Can't match anymore since among other thing CondSelect is long dead.

This mean we get the following assembly:

 v3 (+13) = TESTQ <flags> v7 v7
v12 (+13) = SETNE <bool> v3
v14 (+13) = MOVBQZX <uint64> v12
 v4 (+13) = TESTQ <flags> v14 v14
v16 (+13) = CMOVQNE <uint> v9 v8 v4

If the Neq is rewritten before the CondSelect we get the faster assembly:

v14 (+13) = TESTQ <flags> v7 v7
v16 (+13) = CMOVQNE <uint> v9 v8 v14

Note: the scheduling of instructions is meaningless before the schedule pass all passes are expected to work on any schedule and the only meaningful schedule is the one from the dependencies (v.Args) digraph.

[Jorropo]

A simple working solution is to topologically sort all values before rewriting them just like https://go-review.googlesource.com/c/go/+/714920.

Altho a naive implementation would could be expensive.

[gabyhelp]

Related Issues

• cmd/compile: optimize unsigned comparisons with zero/one #21439

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[gopherbot]

Change https://go.dev/cl/715060 mentions this issue: cmd/compile: rewrite arguments before rewriting value

[randall77]

How about (TESTQ x:(MOVBQZX (SETNE y)) x) => y?

I don't think that's quite right (flags other than equal aren't right?), but something along those lines might work.