Re: c/7344: performance regression on huge case statements

[Nathanael Nerode <neroden at twcny dot rr dot com>]

Partial analysis:

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=7344

It's stuck in a loop in et-forest.c at line 420,
in caclulate_value(node) -- this loop is taking a very, very, long time,
which indicates that that the tree being looked at is very deep.  Oh,
and node->parent->right is equal to node->parent every time.

This is called from et_forest_common_ancestor as the condition (!!) on a 
while
statement, making it doubly nested.  (Horrible... horrible...)

This is all, eventunally, called from note_prediction_to_br_prob in 
predict.c.

The call to note_prediction_to_br_prob was added to rest_of_compilation 
in toplev.c with the change from revision 1.620 to 1.621 of toplev.c.
Sure enough, everything is fine with the May 7th CVS.  CC1 spends a 
large amount of time cycling through basic blocks, but it doesn't hang 
yet.  I haven't pinned down the patch which causes it to hang.

Why is this code path even getting executed at -O0 ?  Prediction notes
and branch probabilities are irrelevant when optimization is off, aren't 
they?  Conditionalizing the call on optimization would probably provide 
a quick fix which would work for 3.3.

In the long run, it needs to get fixed for optimization on, as well, of
course, but how to avoid the nested loops in that case is beyond me.

--Nathanael