Module split 

Splitting critical edges, so that every edge that carries values has somewhere to put them.

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

An edge carries values when the block it goes to takes parameters, and giving a parameter its value is a move. The move has to happen on the edge and not before it or after it, because before it is a block that goes somewhere else too and after it is a block that is arrived at from somewhere else too, and in either case the move would run on a path it was not written for. An edge out of a block with one successor can put its moves at the end of that block, since every path through it takes the edge. An edge into a block with one predecessor can put them at the start of that block, for the same reason the other way round. An edge that is neither, which is what a critical edge is, has neither place, and the allocator says so: rucc_regalloc asserts that it never sees one.

So one is turned into two. A block with nothing in it goes on the edge, the arguments move on to the second half, and both halves are now uncritical: the first goes to a block with one predecessor and the second leaves a block with one successor. Which of the two the moves end up in is the allocator’s answer and not this one’s, and either is correct.

What it leaves behind

An empty block, which is a jump to the next thing unless the layout puts it where it falls through. That is a cost, and it is why an edge with nothing to carry is left alone: there are no moves to find a place for, so splitting it would buy a jump and nothing else.

The other edge with nowhere to put a move

A computed goto leaves its block through a register, and the moves an edge out of it carries would have to be written somewhere the jump has already gone past. So there is a second pass here, indirect, which takes the values off those edges and puts them in a block of their own in front of each label. It runs first, and what it leaves behind is edges the splitting below then has nothing to do about.

pads is here for the same reason and not for a reason of its own: the blocks those labels begin at are addresses an indirect branch arrives at, and a machine that checks the forward edge wants a landing pad at every one of them. Which block an address names is settled by the pass above, so the pad is written after it and not where the prologue’s own pad is written.

Functions

critical

Splits every critical edge that carries values, and gives back how many it split.

indirect

Takes the values off every edge out of a computed goto, and gives back how many blocks it made to hold them.

pads

Puts a landing pad at the front of every block whose address is taken, and gives back how many it wrote.