elliottt opened issue #7639:
Our block lowering order currently inserts new blocks on critical edges to enable register allocation. When these blocks are inserted on edges that targeted blocks with block params, we add block params to the new block, and forward all of its block parameters to the original target through an unconditional branch.
We could simplify this by instead removing the block parameters from the original branch instruction, and adding them only to the block inserted to split the critical edge. We would need to modify the following case in the machinst lowering code, to instead of processing the block params for each branch of a conditional branch, move the processing of those blockparams to the critical edge splitting block.
This should be a fine transformation to make, as the critical edge splitting block will be dominated by the block that defines the values that will be passed through to the blockparams of the original successor.
elliottt added the cranelift label to Issue #7639.
elliottt commented on issue #7639:
Specifically, we'll need to move the call to
self.lower_branch_blockparam_args
out ofself.lower_clif_branches
, and make its call conditional on there being a single successor. Additionally we'll need to call that function in the else branch above, making sure to pull the blockparam assignments from the predecessor.
jameysharp commented on issue #7639:
Trevor and I were discussing this earlier and I want to note one detail we discussed.
There are three interesting kinds of branch edges for this purpose:
- Critical edge, from a block with multiple successors to a block with multiple predecessors
- Branch from a block with only one successor
- Branch to a block with only one predecessor
If a block has only one successor, we want to go ahead and pass block params along the edge. That successor may have other predecessors, in which case it needs to get different values according to which edge control flow arrived from.
For a critical edge, we can move the block params from the original predecessor onto the out-edge of the new block introduced to split the edge; this is the main idea of this issue.
But Trevor and I believe that Cranelift currently never has block params on blocks with only one predecessor, because they should be deleted by the
remove_constant_phis
pass, which we run unconditionally. Note that it's always safe to eliminate block-params on such edges because a block with only one predecessor must be dominated by that predecessor, so it can use any SSA values from that predecessor directly.We remove constant phis before the egraphs pass, so in theory that pass could break this invariant, but it doesn't currently modify control flow, so we don't believe it could break this today.
That said, it's probably worth at least debug-asserting that we only pass block params to the first two kinds of edges. This gets slightly more tedious to implement if single-predecessor blocks can also have block params.
(We also discussed that it might be useful to split critical edges before the egraphs pass, so computation which is only used on some branches isn't forced before the branch. And we considered the possibility of only allowing block params on unconditional branches in CLIF generally, forcing frontends to split critical edges. Neither of these is part of _this_ issue or even obviously a good idea, but I wanted to write them down while I'm thinking about them.)
Last updated: Dec 23 2024 at 12:05 UTC