Skip to content

pan/bi: Convert to SSA in the IR

Alyssa Rosenzweig requested to merge alyssa/mesa:bi/phi-2 into main

This admittedly large series converts the Bifrost/Valhall compiler IR to SSA internally. Currently, the pipeline looks like, where parantheses denote the register allocator:

NIR SSA -> NIR out-of-SSA -> Backend non-SSA optimizer -> (Backend RA <---> Backend spill)

After this series, the pipeline is:

NIR SSA -> Backend SSA optimizer -> (Backend out-of-SSA -> (Backend RA <---> Backend spill))

Notably, the input to the register allocator is SSA. This means the RA can be replaced with an SSA-based allocator, as SSA form is maintained all the way through the optimizer. The next step after this MR is adding an SSA-based spiller, getting the pipeline:

NIR SSA -> Backend SSA optimizer -> (Backend SSA-based spiller -> Backend convert_from_ssa -> (Backend RA <---> Backend spill))

Spill code quality should be greatly improved at that point, though we still need the secondary backend spiller because going out-of-SSA before register allocation increases register pressure unpredictably (calculating the increase is NP-complete for the same reason as calculating the chromatic number of an arbitrary graph).

After that will be one more step, going out-of-SSA after assigning registers, likely with the tree scan algorithm. The "dream" pipeline is thus:

NIR SSA -> Backend SSA optimizer -> (Backend SSA-based spiller -> Backend RA --> Backend out-of-SSA)

To actually get there, this MR shaves all the yaks:

  • Dynamically allocate sources, since phis can have almost arbitrary many sources. We give destinations the same treatment, which should also improve efficiency, needed for parallel copies if we need to introduce them.
  • Eliminate null destinations. This requires some IR changes (notably introducing a TEXC_DUAL pseudo-instruction on Bifrost), but the result is fewer special cases in the optimizer and a cleaner IR. This follows from dynamically allocated destinations.
  • Eliminate some null sources. Unfortunately it's hard to eliminate them all, as bi_null is used as a placeholder in some funny places.
  • Translate phis into backend IR instructions.
  • Add phi-aware versions of optimizations, notably liveness analysis and dead code elimination.
  • Switch to a backend out-of-SSA pass. The pass here is significantly less clever than NIR's, but it does more aggressive copyprop than our optimizer otherwise does, so it's actually a net reduction in instruction according to shaderdb.
  • Defeature nir_register. This reduces a pile of special cases in the backend optimizer.

Draft due to two missing optimizations compared to the old:

  • ATOM_C_RETURN -> ATOM_C when the result is discarded. No shader-db impact from this one, but probably a good idea.
  • Special handling for if-statements with an empty else body. This has to happen after going out-of-SSA, so it can't happen during instruction selection anymore. Why? For one, going out-of-SSA can add moves to a previously empty block. And we can't delete the block altogether -- the empty else block is required to avoid critical edges.
Edited by Alyssa Rosenzweig

Merge request reports