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

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

The following reply was made to PR c/7344; it has been noted by GNATS.

From: Nathanael Nerode <neroden@twcny.rr.com>
To: Daniel Berlin <dberlin@dberlin.org>
Cc: gcc-gnats@gcc.gnu.org, gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org,
   rschiele@uni-mannhiem.de, jh <jh@suse.cz>
Subject: Re: c/7344: performance regression on huge case statements
Date: Thu, 10 Oct 2002 22:13:02 -0400

 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