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.

The test a comparison makes unnecessary

Almost every branch a C program writes is on a comparison, and a comparison has already set the flags by the time the byte it wrote is tested against itself. So where the instruction in front of the branch is that comparison, and the branch is the whole of what reads its byte, the byte and the test both go and the jump names the condition the comparison was asked about instead of naming zero. Three instructions become two, and the two are what the machine has a comparison and a conditional jump for.

This is where it happens rather than anywhere earlier because of what the flags are. Between the comparison and the jump they are live and they are not a register: no pass could be told about them, so no pass may put an instruction between the two. After this one there is no pass left, which is the whole of the argument, and it is the same argument rucc_target::x86_64::Form::CmpSet is one form rather than two under.

What this cannot work out for itself is whether the byte has another reader. Every register is physical by the time this runs and a physical register is written many times in a function, so the question has to be asked while they are still virtual and written once. fusable is that question, asked before allocation, and its answer is one of the arguments to blocks. The same arrangement, and for the same reason, as the addresses crate::finish has still to write and crate::fold is handed.

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.

fusable

The comparisons a branch on their answer is the whole of what reads, which blocks may fold the test out of.