Feature

We should allow the egraph pass to rewrite instructions which have no result values.

This resembles #5908, in that no-result instructions have side effects and that currently prevents us from optimizing them. However the implementation details are quite different.

Benefit

Our current ISLE simplify term isn't usable for this because it can only rewrite an SSA value into other SSA values, so instructions without any value results have nothing to replace.

The only rewrites which need to be in the egraph pass are those which either pattern-match on SSA values or replace SSA values. But instructions which don't produce value results can still be in both of those categories. For example, if we pattern match the condition operand to brif and find that it's a constant, we can rewrite it to an unconditional jump. Removing the unreachable edge from the CFG can then mean that some block parameter is always equivalent to another SSA value, enabling more simplification rules.

The biggest benefits only come in combination with other optimizations that we haven't written yet. Notably, we need to integrate the "remove constant phis" pass into the egraph pass before branch-folding will change any later optimization results.

Implementation

Which no-result instructions can benefit from rewriting? I claim it's the ones which have no fixed value results, but have at least one fixed value operand. They could have variable operands, variable results, or block-call parameters, but we won't touch any of those.

A rewrite pattern is always based on knowing something about the meaning of a value operand. For variable operands like the function parameters in a call, the return values in a return, or the block parameters in a jump, there isn't any generic pattern we can apply to them because we don't know what they mean. Put another way, we don't need any opcode-specific handling for instructions where all we can do is update their value operands to reflect other rewrites.

Among those instructions, we also need to exclude store instructions, because we need alias analysis to rewrite those correctly.

The current instructions which meet these criteria are:

• Brif
• BrTable
• Trapz
• Trapnz
• ResumableTrapnz
• CallIndirect
• ReturnCallIndirect
• SetPinnedReg

Conditional branches, either as block terminators or conditional traps, are definitely interesting to rewrite.

• Brif can turn into Jump;
• BrTable can turn into either Brif or Jump;
• and Trapz/Trapnz can turn into either Trap or Nop.
  Rewriting traps resembles cranelift/egraphs: Allow rewriting to unconditional trap #6080 but in this case we're already replacing a no-result instruction so the mechanism looks pretty different.

Indirect calls are interesting to rewrite if we can prove that the call target is a constant.

I don't think SetPinnedReg has any useful rewrites based on the value operand, because it doesn't have any defined meaning in CLIF. It's just however the frontend wants to use it.

Alternatives

There are some implementation choices we haven't decided on.

I'd like to do this in ISLE rules because we may want to pattern-match arbitrary subtrees of the data-flow graph. However @cfallin has argued for doing this in pure Rust until we have good reason to implement rewrite rules that are complicated enough to justify hooking up ISLE.

We might find we have several alternative instructions to choose from, like we currently do for the simplify term. We could:

• Save a list of alternative instructions during the equality saturation phase, but that makes it difficult to do further optimizations based on simplifying the CFG.
• Defer rewriting these instructions until elaboration when we have the cost of every operand, but then it's not just difficult but impossible to make use of CFG simplifications during equality saturation.
• Compute instruction costs incrementally during equality saturation so we can pick the best option immediately and optimize the CFG based on the result. @cfallin says that's possible but had reasons for not doing it.
• Require these rewrite rules to pick a single alternative based on a static cost model. This is certainly easiest and may be good enough.