Rewrite switch code generation
Inspired by #10124 I looked at the code generation for enumeration and integer types, and I think this can be improved in a few ways. My goals are:
- Fancier code for integer types. Currently, the code for enumeration types will emit jump tables for dense choices; there is no reason to treat integer types differently.
- The ability to behave differently if some of the case alternatives are equal, and, as an extension of that,
- The possibility to create branchless code if multiple checks would go to the same jump.
The current scheme is roughly:
- When we generate Cmm code for a STG case expression, we handle enumeration types and literals separately.
- At this point, the decisions about what code to generate are made (jump tables (but only for enumeration types) or if-then-else trees).
- The Common Block Optimization on Cmm happens later in the pipeline, making it non-trivial to detect branches that do the same thing.
My plan is the following:
- In the STG→Cmm transformation, floats will be handled separately. Matching against literals is fishy anyways, so my suggestion is to simply generate a linear list of equality checks here – turning the intended operation (equality test) into something else (comparisons in a if-then-else tree) feels wrong to me for floats. And the rest would not work well for floats, so I’d like to have them out of the way.
- The case of enumeration types will be reduced to word literals, and treated the same from now on.
- For integer types, no code generation decisions is made at this point. Instead, always a
CmmSwitch
statement is generated. - In a separate Cmm transformation pass, which will run /after/ the common block optimization, we visit all
CmmSwitches
and create proper code for them.
I’d like to separate the algorithm that plans the code generation into a function (possibly even module) of its own, so that the decisions can easily by analyized and modified.
The algorithm has a few choices to make:
- If multiple values point to the same code, we can generate branchless code (
y := x == 1 || x == 5 || x = 7; if (y==0) then goto l1 else goto l2
). - If there are whole ranges pointing to the same code, the above can also use comparisons.
- If there are dense ranges (i.e. a range with more than half of the possible values mapped to something), we want to generate jump tables from them (still
CmmSwitch
values). - Unless all options are handled by one of these possibilities, they need to be combined using
if-then-else
trees.
The CmmSwitch
constructor needs to change for that. It currently takes a [Maybe Label]
argument, which is not suitable for before that pass, when its table may be sparse. I think an IntMap Label
would work nicely.