Module switch 

What a switch becomes on the way to the machine, and how that shape is chosen.

Design: spec/optimizer/24-switch-lowering.md. Section 24.4 puts the choice here, at the boundary into the machine level and nowhere earlier, and section 24.2 says what the choice looks like.

Why the shape is decided here and not in the front end

What a switch should become is a target decision and not a language one. A chain of compares is right for three cases and wrong for two hundred, where the answer is a jump table, and wrong again for twenty spread over a million, where it is a binary search on the value. A front end that picked one would be picking for every target at once, and the IR would no longer hold what the program said. So the switch survives as far as here, and here is where it is given up.

Keeping it whole that long buys something on the way as well. A switch is one node from which the range on each outgoing edge is exact: on the edge to case five the operand is five, and on the default edge it is outside the case set. A switch lowered early is a pile of branches that every pass afterwards has to work those facts back out of.

A switch is a partition and not a shape

The reason to sort the cases and cut them into runs, rather than pick one shape for the whole statement, is that a real switch is more than one thing at once. A switch in a parser has a dense stretch of ASCII values best served by a jump table, a few scattered large constants best served by comparisons, and a set of aliased cases best served by a bit test, all in the same statement. A design that picks one shape for the whole of it cannot say that. So the case list is sorted, partitioned into clusters, and a decision tree is built over the clusters.

Three of the four shapes are written. A Cluster::One is one case value and one equality test, which is what every case was before this module existed. A Cluster::Run is a stretch of consecutive values that all go to the same place, and it is one subtraction and one unsigned comparison however long the stretch is, which is what makes case 'a' ... 'z' twenty six cases in the IR and two instructions in the machine code. A Cluster::Bits is a set of values scattered through a span narrower than a word, each destination holding the bits of a mask, and it is one shift and one test per destination however many values are in it, which is what makes case 'a': case 'e': case 'i': case 'o': case 'u': five compares before this and one after.

The one that is not written is the jump table, and it is a variant this enum gains rather than a rewrite of anything here. It is waiting on Opcode::IndirectBr, which is tamnd/rucc#353 and is the same thing a computed goto waits on, and on a read only section to put the table in.

Why the tree compares signed

The IR gives a switch a width and not a signedness, because signedness in this IR is a property of an operation rather than of a type, so there is nothing here to ask whether the program switched on an int or an unsigned. What makes that harmless is that the sort and the tree use the same order: the cases are sorted by their signed reading and the tree splits with a signed comparison, so the tree is consistent with itself and every value comes down it to the one cluster that can hold it. Sorting one way and comparing the other is the bug this is written to not have.

A run is not affected either way. Testing x - low against high - low unsigned is modular arithmetic and gives the same answer whichever way the operand is read.

What it refuses to get wrong

Section 24.6 lists the ways this goes wrong and two of them are arithmetic. The width of a run is worked out in i128, which holds the difference of any two values of any type C can switch on, so nothing here overflows the way the same computation in the switch’s own type would. A run that covers a whole type comes out as a width of every bit set, which read as an unsigned comparison is a test that is true of everything, and that is exactly right for a switch no value falls out of.

The third is the default edge, and the rule is that it is never dropped. Every leaf of the tree ends by branching to the default, so a value that matches nothing arrives there whichever way it came down, and there is no path through any of this that leaves a block without saying where control goes next.

The fourth is the bit test’s shift. Shifting by more than the width of the word being shifted is undefined, and the amount is the operand, so it is the operand that has to be shown to be in range first. Section 24.6 is firm that the bound before the shift is not an optimization decision and cannot be dropped when the value looks like it has to be in range, and here it is written by the same code that writes the shift rather than added afterwards.

What it does not carry yet

Section 24.5 asks for document 11’s Frequency on every cluster from the start, so that the tree can lean towards the hot cases rather than be balanced, and so that adding it later is not a change to every place a cluster is built. It is not here because there is nowhere to read it from. Block frequencies are worked out in rucc-opt, which is above this crate rather than below it, and what would carry the number down is the IR, which has nowhere to put it yet.

Constants

LINEAR

The most clusters a leaf of the decision tree tests one at a time, which is also the count below which nothing new is built at all. A switch of this many clusters or fewer stays the chain of compares it has always been, in the block it has always been in.

Functions

blocks_for

The blocks a leaf chain of n clusters needs beyond the ones the program already had.

switches

Rewrites every switch in the function into branches, and leaves everything else alone.