[Bug tree-optimization/54742] New: Switch elimination in FSM loop

[joey.ye at arm dot com]

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: unassigned@gcc.gnu.org
        ReportedBy: joey.ye@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;
}
---