Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Forward blockparams to critical edge blocks #7639

Open
elliottt opened this issue Dec 5, 2023 · 2 comments
Open

Forward blockparams to critical edge blocks #7639

elliottt opened this issue Dec 5, 2023 · 2 comments
Labels
cranelift Issues related to the Cranelift code generator

Comments

@elliottt
Copy link
Member

elliottt commented Dec 5, 2023

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.

// End branches.
if let Some(bb) = lb.orig_block() {
if let Some(branch) = self.collect_branches_and_targets(bindex, bb, &mut targets) {
self.lower_clif_branches(backend, bindex, bb, branch, &targets)?;
self.finish_ir_inst(self.srcloc(branch));
}
} else {
// If no orig block, this must be a pure edge block;
// get the successor and emit a jump. Add block params
// according to the one successor, and pass them
// through; note that the successor must have an
// original block.
let (_, succs) = self.vcode.block_order().succ_indices(bindex);
let succ = succs[0];

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
Copy link
Member Author

elliottt commented Dec 5, 2023

Specifically, we'll need to move the call to self.lower_branch_blockparam_args out of self.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
Copy link
Contributor

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.)

jameysharp added a commit to jameysharp/wasmtime that referenced this issue Aug 26, 2024
This lets us stop allocating temporary VRegs for critical edges that
have block parameters. That makes the register allocation problem a
little smaller, and also allows reusing lower_branch_blockparam_args for
all block parameters.

Fixes bytecodealliance#7639, and unblocks bytecodealliance/regalloc2#170
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
cranelift Issues related to the Cranelift code generator
Projects
None yet
Development

No branches or pull requests

2 participants