This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
Re: c/7344: performance regression on huge case statements
- From: Nathanael Nerode <neroden at twcny dot rr dot com>
- To: Daniel Berlin <dberlin at dberlin dot org>
- Cc: gcc-gnats at gcc dot gnu dot org, gcc-bugs at gcc dot gnu dot org, nobody at gcc dot gnu dot org, rschiele at uni-mannhiem dot de, jh <jh at suse dot cz>
- Date: Thu, 10 Oct 2002 22:13:02 -0400
- Subject: Re: c/7344: performance regression on huge case statements
- References: <028E1AA5-DCBE-11D6-86E9-000393575BCC@dberlin.org>
Daniel Berlin wrote:
On Thu, 10 Oct 2002, Nathanael Nerode wrote:
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.
Through nearest_common_dominator, which is called by
dominated_by_p, perchance?
If so, this is a known problem.
It doesn't cache the info (I think Jan said he could make it constant
time
in the alternative, which would also solve the problem), so it is
constantly recomputing a value that hasn't changed.
(...and one which is expensive to compute using the current algorithm)
Yep, that's the one. Thanks for identifying this.
Try replacing dominance.c with the one from the tree-ssa-branch, and see
if that helps.
Haven't tried that yet (busy working on something else).
Well, so much for one high-priority bug. Shouldn't be hard for Jan to
fix then should it? ;-)
--Nathanael