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
