[Bug c/52640] New: performance bottleneck: gcc/tree.c;value_member

[ncahill_alt at yahoo dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52640

             Bug #: 52640
           Summary: performance bottleneck: gcc/tree.c;value_member
    Classification: Unclassified
           Product: gcc
           Version: 4.6.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: ncahill_alt@yahoo.com


Created attachment 26935
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26935
source, output, profiling data indicating problem

It was made known to me that the code provided takes a long time to compile. 
Looking into it, the culprit seems to be the value_member function of
gcc/tree.c.  Here is that code (preprocessed):

####
tree value_member (tree elem, tree list)
{
    while (list) 
    {
        if (elem == ((list)->list.value))
            return list;
        list = ((list)->common.chain);
    }
    return (tree) ((void *)0);
}
####

A sample of profiling data, from OProfile and using gcc 4.6.2:

####
samples  %        image name               symbol name
19955    43.1814  cc1                      value_member
1179      2.5513  cc1                      record_reference
1122      2.4279  cc1                      insert_aux

####

With a table of 10000 rows, it takes ~40% of the execution time, and with
200000 rows, ~90%.  The former takes 5 seconds, the later is not finished in 20
minutes.

Provided is a sample source file with output from cc1 and profiling data as
above.

Thank you.
Neil.