From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugs-return-402217-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 8870 invoked by alias); 29 Sep 2012 03:16:49 -0000
Received: (qmail 8841 invoked by uid 48); 29 Sep 2012 03:16:31 -0000
From: "joey.ye at arm dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/54742] New: Switch elimination in FSM loop
Date: Sat, 29 Sep 2012 03:16:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: joey.ye at arm dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Changed-Fields:
Message-ID: <bug-54742-4@http.gcc.gnu.org/bugzilla/>
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
X-SW-Source: 2012-09/txt/msg02383.txt.bz2


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;
}
---