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.

Functions

critical

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