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.

All 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.

A Cluster::Table is a stretch of clusters dense enough that a table with one cell per value is cheaper than testing them, and it is one range check and one jump through the table however many cases are in it, which is what the dispatch loop of an interpreter wants and what tamnd/rucc#1548 found missing: pcre2’s matcher is a switch of about a hundred opcodes, and walking a tree down to one of them on every step cost more than four times what gcc’s table did. The table is not written here. What is written is the range check and then a switch again, on the value less the lowest case and widened to a word, which crate::lower turns into the load and the jump, and rucc_asm writes the table itself, in .rodata on x86-64 ELF the way gcc does and after the function’s last instruction everywhere else. See JUMP_TABLE_GROWTH for what dense means.

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.

A hot case

Section 24.5 asks for the tree to lean towards the hot cases rather than be balanced. What says a case is hot is the hint on its arm, which __builtin_expect on the operand writes and a profile would write in the same place. A case whose hint is at least SWITCH_PEEL_PERCENT is taken out and tested on its own before anything else, which is what LLVM calls peeling, and the rest is lowered behind it as if the case had never been there. The branch in front carries the hint, so the layout puts the hot case next.

One case and not an ordering of all of them. A hint says which value is likely and nothing about the others, and the others share what is left evenly, so there is nothing to order them by.

What it says it did

Section 24.7 asks for every switch in the corpus to be compared with what gcc made of it, so each one lowered here comes back as a Lowered, and -fopt-info prints it as one line: how many cases, which shape, and what the partition was. The same section asks what each shape would have cost on a hot switch, and Force is how that is measured. -Zswitch= forces one shape on every switch in the file, and nothing else reaches for it.

Structs

Lowered

What one switch became, which is what -fopt-info says about it.

Enums

Force

A shape forced on every switch, which is what -Zswitch= asks for.

Constants

FORCED_CELLS

The most cells a forced table may have. A switch spread wider than this keeps the shape it would have had, since a table of a million cells measures the cache and not the dispatch.

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.

lowered

The same, with a shape forced on every switch when force names one, answering what each switch became in the order they were found.

switches

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