cmd/compile: recognize continuous runs in switch cases

[josharian]

package src

func small(i int) bool {
    switch i {
    case 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15: // 9 is only small on a hot day
        return true
    }
    return false
}

func small2(i int) bool {
    switch {
    case 0 <= i && i <= 8, 10 <= i && i <= 15:
        return true
    }
    return false
}

We should compile small to the same code as small2. Instead, we handle each of the cases independently:

"".small t=1 size=112 args=0x10 locals=0x0
"".small2 t=1 size=48 args=0x10 locals=0x0

Worse, we end up paying a significant cost in the SSA backend juggling all the branches and blocks generated by the frontend.

This sounds theoretical, but I keep encountering large switch statements in functions with bad compile times, and I have seen a bunch of contiguous runs. Here's an excerpted example from cmd/vendor/golang.org/x/arch/x86/x86asm:

func gnuArg(inst *Inst, x Arg, usedPrefixes *bool) string {
// ...
        switch inst.Op {
        case CVTSI2SS, CVTSI2SD, CVTSS2SI, CVTSD2SI, CVTTSD2SI, CVTTSS2SI:
            if inst.DataSize == 16 && EAX <= x && x <= R15L {
                x -= EAX - AX
            }
// ...

Those constants all happen to be next to each other.

[griesemer]

The compiler's lexer code (and any typical lexer/scanner for that matter) contains a largish switch which might benefit from optimized compilation of switches. At the moment, we go out of our way (manually) to handle common cases separately. This directly affects lexing performance.

[josharian]

Here's an amazingly readable summary of switch lowering optimizations: https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf. Many of them require jump tables, which would require object file and linker changes, and which might no longer be a desirable strategy anyway. I plan to investigate some of the other strategies for Go 1.8.

[minux]

I think if we're going to do jump tables, we should aim for relative PC addresses rather than absolute PC in the table. Otherwise every entry requires a relocation in go.o for external linking and it will further complicate PIE (-buildmode shared) support.

[josharian]

Sorry if I was unclear. I am going to investigate the non-jump-table options.

[cespare]

Also, since nobody has mentioned it yet, #5496 already exists for compiling switches into jump tables.

[minux]

Yeah, I think jump tables are fine for very specific cases (very dense tables with a lot of different targets). Some C compilers also uses bitmask for dense switches, and it's especially useful on 64-bit machines without too many branch targets.

[josharian]

I poked through a bunch of switch statements. Based on what I saw, the two near term changes I would like to make are using ranges and bitmasks for dense integers that share a branch target. (For example, case 99, 100, 101: and case 99, 109, 119:.)

It's not obvious to me how this should interact with binary search, assuming the goal is to minimize the number of branches. If just ranges were supported, it'd be easy: Assign a weight of one to every range (including singleton ranges) and then pick a pivot value that balances those weights. With bitmasks, however, things are more complicated. Bitmask-able sets of values interact with each other (case 1, 3, 5: and case 1, 2, 8:) and with themselves (a case with, say, every odd number less than 100 must be split up somewhere into multiple bitmasks), so moving the pivot left or right no longer has an incrementally calculable, monotonic effect.

I'd love suggestions or references. I'd rather find something simple and cheap that limits the worst case rather than something optimal.

[ianlancetaylor]

This is what GCC does: https://gcc.gnu.org/viewcvs/gcc/trunk/gcc/tree-switch-conversion.c?revision=232055&view=markup

Might be interesting to read https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf

[josharian]

Thanks, Ian. The GCC restrictions on bitmasks suggests that I'd do well enough ignoring them for the moment, so that's what I'll do, which makes the path forward very clear. And that paper is actually where I started on this--it's very useful and well-written.

Go also has non-integer switches, which themselves are interesting and appear to be less-well-covered territory in the literature--e.g. #15164 and the general question of whether we should use tries of some kind for switches over strings. Yet more reason to keep the integer handling relatively simple.

---

For my own future reference, here are couple of other notes:

• If we had jump tables, "Efficient multiway search radix tree" might help with bit type switches, since they are sparse and integer-ish.
• Paper on LLVM's switch lowering: http://llvm.org/pubs/2007-05-31-Switch-Lowering.pdf. Mostly covers the same territory as the others, although it presents a heuristic for finding the pivot for binary search--I'm not convinced yet.
• Consider joining ranges when there is a small gap, and then testing for the gap.
• Recognize switches used to implement static data or static lookup and convert.

[odeke-em]

Hello @josharian, I believe you implemented contiguous range coalescing/recognition in CL https://go-review.googlesource.com/c/go/+/26770 if I am not mistaken i.e. the non-jump table solution and I just encountered this issue while combing through compiler issues such as #5496

Should we be closing this issue, or is there something else that we can do here?

[josharian]

There are a bunch of further tweaks we might want to do, such as "Consider joining ranges when there is a small gap, and then testing for the gap". But having a grab-bag issue such as this remain open for stuff like this isn't valuable, so yes, I'll close this. We can always open new issues as desired.