Expand description
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.
What is here is the case where the answers are an affine function of the label, a * x + b.
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. The case where the answers are
arbitrary constants is a lookup table in a read only section, which is section 24.4’s other half
and is not here.
§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
The labels are consecutive. Not a simplification: a hole in the labels is a value the range check lets through and the arithmetic then answers, where the program said it should have gone to the default.
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.
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.
§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.
Structs§
- Switch
Conv - The pass.