GitLab

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.