Skip to content

Comments

Cranelift: remove block params on critical-edge blocks.#10485

Merged
fitzgen merged 1 commit intobytecodealliance:mainfrom
cfallin:no-blockcall-args-on-critical-edges
Mar 31, 2025
Merged

Cranelift: remove block params on critical-edge blocks.#10485
fitzgen merged 1 commit intobytecodealliance:mainfrom
cfallin:no-blockcall-args-on-critical-edges

Conversation

@cfallin
Copy link
Member

@cfallin cfallin commented Mar 29, 2025

When a block has a terminator branch that targets two or more other blocks at the CLIF level, and any of these blocks have two or more precessors, the edge is a "critical edge" and we split it (insert a new empty block) so that the register allocator has a place to put moves that happen only on that edge. Otherwise, there is no location that works: in the predecessor, code runs no matter which outgoing edge we take; and in the successor, code runs no matter which incoming edge we came from.

Currently, when we generate these critical-edge blocks, we insert exactly one instruction: an unconditional branch. We wire up the blockparam dataflow by (i) adding block parameters to the critical-edge block with the same signature as the original target, and (ii) adding all of these arguments to the unconditional branch. In other words, we maintain the original block signature throughout.

This is fine and correct, but it has two downsides. The first is a minor loss in compile-time efficiency (more SSA values and block-params to process). The second, more interesting, is that it hinders future work with certain kinds of branches that may define values on edges.

In particular, this approach prevents exception-handling support: a try_call instruction that acts as a terminator branch (with normal-return and exceptional out-edges) defines normal-return values as block-call arguments that are usable on the normal-return edge. Some of these normal-return values may be defined by loads from a return-value area. These loads need somewhere to go; they can't go "after the terminator" (then it wouldn't be a terminator), so they go in an edge block; as a result, the block-call for the normal-return needs to use its arguments only in the unconditional branch out of the edge block, not in the initial branch to the edge block.

This PR alters the critical-edge blockparam handling to have no block-call args on the branch into the edge block, and use the original values (not the newly defined edge-block blockparams) in the block-call out of the edge block. This will allow these values to be possibly defined in the edge block rather than in the predecessor (the block with the original terminator).

This has no functional change today other than some perturbation of regalloc decisions and a possibly slight compile-time speedup.

When a block has a terminator branch that targets two or more other
blocks at the CLIF level, and any of these blocks have two or more
precessors, the edge is a "critical edge" and we split it (insert a
new empty block) so that the register allocator has a place to put
moves that happen only on that edge. Otherwise, there is no location
that works: in the predecessor, code runs no matter which outgoing
edge we take; and in the successor, code runs no matter which incoming
edge we came from.

Currently, when we generate these critical-edge blocks, we insert
exactly one instruction: an unconditional branch. We wire up the
blockparam dataflow by (i) adding block parameters to the
critical-edge block with the same signature as the original target,
and (ii) adding all of these arguments to the unconditional branch. In
other words, we maintain the original block signature throughout.

This is fine and correct, but it has two downsides. The first is a
minor loss in compile-time efficiency (more SSA values and
block-params to process). The second, more interesting, is that it
hinders future work with certain kinds of branches that may define
values *on edges*.

In particular, this approach prevents exception-handling support: a
`try_call` instruction that acts as a terminator branch (with
normal-return and exceptional out-edges) defines normal-return values
as block-call arguments that are usable on the normal-return
edge. Some of these normal-return values may be defined by loads from
a return-value area. These loads need somewhere to go; they can't go
"after the terminator" (then it wouldn't be a terminator), so they go
in an edge block; as a result, the block-call for the normal-return
needs to use its arguments only in the unconditional branch out of the
edge block, not in the initial branch to the edge block.

This PR alters the critical-edge blockparam handling to have no
block-call args on the branch into the edge block, and use the
original values (not the newly defined edge-block blockparams) in the
block-call out of the edge block. This will allow these values to be
possibly defined in the edge block rather than in the predecessor (the
block with the original terminator).

This has no functional change today other than some perturbation of
regalloc decisions and a possibly slight compile-time speedup.
@cfallin cfallin requested a review from fitzgen March 29, 2025 01:11
@cfallin cfallin requested review from a team as code owners March 29, 2025 01:11
@github-actions github-actions bot added cranelift Issues related to the Cranelift code generator cranelift:area:machinst Issues related to instruction selection and the new MachInst backend. labels Mar 29, 2025
Copy link
Member

@fitzgen fitzgen left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice!

@fitzgen fitzgen added this pull request to the merge queue Mar 31, 2025
Merged via the queue into bytecodealliance:main with commit 44e4919 Mar 31, 2025
41 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

cranelift:area:machinst Issues related to instruction selection and the new MachInst backend. cranelift Issues related to the Cranelift code generator

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants