Re: Switch statement optimization

["Martin Liška" <mliska@suse.cz>]

On 4/18/22 16:41, Paul Koning via Gcc wrote:
> In switch statements with dense case values, the typical result is a jump table, which is fast.  If the values are sparse, a tree of compares is generated instead.
> 
> What if nearly all cases are dense but there are a few outliers?  An example appears in the NFS protocol parser, where you get a switch statement with cases for each of the opcode values.  All but one are small integers assigned in sequence, but one is 10044.  So the "sparse" case kicks in and a compare tree is generated for everything.
> 
> I can avoid this by putting in special case code for the 10044 case, then all the rest ends up being a jump table.  That brings up the question if GCC should recognize such scenarios and break up the switch statement into "dense parts" handled by a jump table, leaving the sorting between those as a compare tree.

Hello.

We currently support identification of such dense/interesting groups of case values (we name them clusters).
See e.g. gcc/testsuite/gcc.dg/tree-ssa/switch-1.c where you can have a decision tree that contains
mix of individual cases, jump-tables (JT) and bit-tests (BT).

Can you please share your test-case so that I can analyze it?
You can investigate with -fdump-tree-switchlower1.

Cheers.
Martin

> 
> 	paul
>