https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70861
Bug ID: 70861
Summary: Improve code generation of switch tables
Product: gcc
Version: 7.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: middle-end
Assignee: unassigned at gcc dot gnu.org
Reporter: wdijkstr at arm dot com
Target Milestone: ---
GCC uses a very basic check to determine whether to use a switch table. A
simple example from https://gcc.gnu.org/bugzilla/show_bug.cgi?id=11823 still
generates a huge table with mostly default entries with -O2:
int i;
int func(int a)
{
switch(a)
{
case 0: i = 20; break;
case 1: i = 50; break;
case 2: i = 29; break;
case 3: i = 20; break;
case 4: i = 50; break;
case 5: i = 29; break;
case 6: i = 20; break;
case 7: i = 50; break;
case 8: i = 29; break;
case 9: i = 79; break;
case 110: i = 27; break;
default: i = 77; break;
}
return i;
}
This shows several issues:
1. The density calculation is not adjustable depending on the expected size of
switch table entries (which depends on the target).
2. A table may contain not only 90% default entries, but they can be
consecutive as well. To avoid this the maximum number of default cases should
be limited to say 3x the average gap between real cases.
3. There is no reduction in minimum required density for larger switches - the
wastage becomes quite significant for larger switches and targets that use 4
bytes per table entry.
4. Dense regions and outlier values are not split off and handled seperately.
