Module switch_conv 

A switch whose arms are a function of the label, which is arithmetic and not branches.

Design: spec/optimizer/24-switch-lowering.md section 24.1, which is the transformation the GCC file tree-switch-conversion.cc is named after, and section 24.4, which puts it in the middle end rather than in the lowering and says why: what it produces is ordinary arithmetic that every pass after it optimizes, and what it needs to see is arms whose constancy earlier passes made visible.

The shape

switch (x) { case 0: return 1; case 1: return 2; case 2: return 3; case 3: return 4; }
return 0;

Four labels, four arms, and the arm for label k gives k + 1. The labels run consecutively and the answers run consecutively with them, so the whole statement is one range check and one addition. gcc reduces thirty three labels of this to a comparison and a lea, which is tamnd/rucc#728, and rucc emitted a comparison and a jump per label.

Where the answers are an affine function of the label, a * x + b, there is nothing to look up. That covers the shape above with a of one and b of one, the shape where every arm gives the same answer with a of zero, and the scaled ones in between.

Where they are not, the answers are a table. The arm for label k gives the constant in cell k - low of a read only array, and every arm becomes one load from it. That is section 24.4’s other half, and it is what gcc calls a CSWTCH array. The array is asked for through crate::readonly, because a pass is handed one function and the array is the module’s.

What it rewrites and what it leaves

The switch stays a switch. Every case edge is pointed at one new block, which works the answer out and hands it on, and the default edge is not touched at all. What that buys is that the range check is not written here: a switch whose cases are consecutive and all go to one place is exactly crates/rucc-codegen/src/switch.rs’s Cluster::Run, which is one subtraction and one unsigned comparison however long the run is, and which already gets the modular arithmetic and the run that covers a whole type right. Writing a second range check here would be a second place for section 24.6’s overflow to be got wrong.

The default is untouched for the reason section 24.6 gives, which is that the default is never dropped. A value that matches no case went to the default before this ran and goes to the same place afterwards, because the edge it goes down is the same edge.

What has to be true

For arithmetic, the labels are consecutive. A hole in the labels is a stretch the lowering would then have to cut the run at, and one comparison becomes several for a function that was only fitted to the labels either side of it.

For a table, the labels may have holes. Where the default hands on what the arms hand on with a constant in the answer’s place, which is default: return 0; and default: y = 0; break;, a hole’s cell is that constant and the hole is given a case of its own going to the load, as gcc’s gather_default_values does. The labels are then one run, which the lowering checks with one comparison, where a run with holes in it is a comparison and a bit test, and the bit test is a branch a stream of values mispredicts. Where the default does anything else, the switch still sends a value in a hole to the default, the hole’s cell is never read, and it is written as zero only because an array has to have something there. What bounds the holes is size: the table spans at most eight cells for every label it replaces, which is gcc’s switch-conversion-max-branch-ratio, so a switch over three labels a thousand apart stays a switch.

Every arm is a block nothing else reaches, holding nothing but the constants it hands on, and ending the same way as every other arm. The same way means a jump to the same block, or a return, and in either case with the same values in every position but one. That one is the answer. Section 24.5 gives up on arms that assign more than one thing and so does this.

The answers are a * label + b at every label, checked at every label rather than fitted to two of them and believed. The check is done in the answer’s own width with wrapping, because that is what the arithmetic this writes will do, and the arithmetic is written with no flags on it so that wrapping is what it is allowed to do.

For arithmetic, the label and the answer are the same width. A switch on an int whose arms give a long is the same transformation with a widening in front of the multiply, and which widening it is depends on how the label is read, which is a question this would have to answer and currently declines to ask. A table does not have that question, because the label only picks a cell and the cell is already as wide as the answer, so a table may be any whole number of bytes wide up to eight whatever the label is. A label wider than a word gets no table, since the index into one is a word.

Why three labels and not two

Two labels and a default is a shape phiopt already has something to say about, and what it says is a select between two constants that cost nothing to materialize. The arithmetic this writes is a multiply and an add against a range check, which is not obviously better than that and is worse when a is not one. From three labels up the chain being replaced is at least six instructions and what replaces it is at most five, so it is a win at three and grows from there.

A table is held to the same three. What replaces the chain is a subtraction, the range check, a widening and a load, which is five again, and the load is from a line the program keeps reading if the switch is hot.

Where the table goes

The array is internal, constant and aligned to its cell, which puts it in .rodata. It is named CSWTCH. and a number, as gcc names it, which nothing written in C can spell.

When the goal is size a cell is as narrow as the answers allow, and the load is widened back to the answer’s width with a sign or without one, whichever holds every answer. gcc 16 does the same at -Os and not at -O2, where the widening is an instruction on the path and the bytes it saves are data rather than code. Three int answers under ten are twelve bytes at -O2 and three at -Os, in gcc and here.

Structs

SwitchConv

The pass.