http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54742
Bug #: 54742
Summary: Switch elimination in FSM loop
Classification: Unclassified
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
AssignedTo: unassig...@gcc.gnu.org
ReportedBy: joey...@arm.com
Following interesting case is reduced from a benchmark. It implements a FSM
with a loop and switch. There is opportunity to eliminate the switch since all
state transition is definite in compile time.
Source program:
---
int sum0, sum1, sum2, sum3;
int foo(const char * str)
{
int state=0;
const char *s=str;
for (; *s; s++)
{
char c=*s;
switch (state) {
case 0:
if (c == '+') state = 1;
else if (c != '-') sum0+=c;
break;
case 1:
if (c == '+') state = 2;
else if (c == '-') state = 0;
else sum1+=c;
break;
case 2:
if (c == '+') state = 3;
else if (c == '-') state = 1;
else sum2+=c;
break;
case 3:
if (c == '-') state = 2;
else if (c != '+') sum3+=c;
break;
default:
break;
}
}
return state;
}
---
Say, instead of setting state=1 and loop back to switch head, it can be
optimized to setting state=1, check loop end condition and jump directly to the
label of case_1. Thus the overhead of switch (either if-then-else or jump
table) is eliminated. On machine without sophisticate branch prediction, such
an optimization is even more appealing.
GCC trunk 4.8 doesn't have such a optimization.
Expected tree output in source form:
---
int sum0, sum1, sum2, sum3;
int foo(const char * str)
{
int state=0;
const char *s=str;
char c=*s;
if (!c) goto end;
state_0:
if (c == '+') {
state = 1;
if ((c=* (++s))!=0) goto state_1; // Check loop end condition and go
directly to next state
else goto end;
}
else if (c != '-') sum0+=c;
if ((c=* (++s))!=0) goto state_0;
goto end;
state_1:
if (c == '+') {
state = 2;
if ((c=* (++s))!=0) goto state_2;
else goto end;
}
else if (c == '-') {
state = 0;
if ((c=* (++s))!=0) goto state_0;
else goto end;
}
else sum1+=c;
if ((c=* (++s))!=0) goto state_1;
goto end;
state_2:
if (c == '+') {
state = 3;
if ((c=* (++s))!=0) goto state_3;
else goto end;
}
else if (c == '-') {
state = 1;
if ((c=* (++s))!=0) goto state_1;
else goto end;
}
else sum1+=c;
if ((c=* (++s))!=0) goto state_2;
goto end;
state_3:
if (c == '-') {
state = 2;
if ((c=* (++s))!=0) goto state_2;
else goto end;
}
else if (c != '+') sum3+=c;
if ((c=* (++s))!=0) goto state_3;
end:
return state;
}
---
