optimization of switch statements on i386

[Ian Lance Taylor]

"Godmar Back" <godmar@gmail.com> writes:

> I have a question regarding the compilation of switch statements for
> i386 targets. What heuristics or algorithm does gcc use to decide
> whether to use a binary search or a jump table? I'm specifically
> interested in switch statements for a dense range of values and in
> which the default: branch is unreachable.

Look at expand_case in gcc/stmt.c.

> I've tried a number of approaches in order to obtain a jump table, but
> it seems gcc 4.x always ends up creating binary searches. For
> instance, I've tried casting the switch value to a limited range enum
> and placing a gcc_unreachable() in the default: case. A cursory
> inspection of the source code also didn't reveal any documentation of
> the strategy used. Does gcc have reason to believe that a binary
> search is always faster?

No, it uses a heuristic to choose.  Probably the most relevant one
here is that if the difference between the maximum and minimum case
labels is more than 10 * the number of case labels, gcc will use
comparisons rather than a table.

> If so, is this true for all variants of i386?

I believe that all i386 variants are handled in the same way.

> Would it depend on the number of case arms?

Yes.

Ian