Module layout 

Putting the blocks in an order, and turning the edges between them into jumps.

Design: spec/10-backend.md section 10.6.

Up to here a function is a set of blocks and a set of edges, and nothing has said which block comes first in memory. A machine has no such thing: it runs the instruction after the one it just ran, so an order is not a presentation detail but the last piece of what the function means. This is what chooses one, and then writes the jumps that make the edges the order did not put next to each other still go where they went.

What the order is

Reverse postorder over the CFG, with each block’s successors walked in reverse, and anything unreachable put at the end in block order.

That is the -O0 order spec/10-backend.md section 10.3 asks for, and it is not arbitrary. Walking the successors in reverse is what makes the first arm of a branch come out first, because a depth-first walk finishes its last child first and reverse postorder then puts that child last. So an if with no else falls through into its body, and a loop comes out as its header, its body and then whatever follows it, which is the shape where the back edge is the only jump in it. The chain construction weighted by block frequency that section 10.6 describes is what replaces this above -O0, and it is not written yet.

Unreachable blocks are laid out rather than deleted. Deleting one is a decision about what the program does and this pass has no business making it, and a block nothing reaches costs the bytes it occupies and nothing else.

What a block looks like afterwards

A block still holds where it goes, and it still holds every arm, which is what keeps the control flow graph readable after this has run. What changes is that the order the arms are in now means something it did not mean before:

  no arms      it returns
  one arm      it falls into that block if that block is next, and jumps to it if not
  two arms     a test and a conditional jump to the first, and the second is always next

So a jump target is a block without an instruction growing a field for one. rucc_mir::InstData is twenty four bytes by assertion and a block reference does not fit in it, and every pass over the graph already reads the arms, so putting the target where the graph already is costs nothing and keeps the two from disagreeing.

Which arm is which is no longer which way the condition went, because a block that falls into the arm the condition is true for is a block whose jump has to be taken when it is false. That is what the two conditional jumps in BranchInsts are for, and it is why the arms may come out swapped: what the condition meant is in the opcode afterwards, and what the arms mean is where the jump goes and what comes next.

The block a branch sometimes needs

A branch whose second arm cannot be laid out next, because both its arms are blocks the walk has already been to, would need two jumps in one block. Rather than write one, this makes the block it needs: an empty one on the second edge, laid out immediately after the branch, that jumps where the edge went. That is exactly the critical edge splitting in crate::split, done for a different reason, and it costs the same jump the second jump would have cost while leaving every block with at most one.

Why it runs last

crate::finish finds the blocks a function returns from by looking for the ones that go nowhere. Nothing here creates one of those, but everything here reads and writes the arms, and a pass that reorders them is one nothing before it should be looking at. Running the layout after the prologue and the epilogue are in is also what makes the epilogue something it can lay out around rather than something it has to leave room for.

Functions

blocks

Puts a function’s blocks in an order and writes the jumps that order needs.