[tree-ssa] Speeding things up

[law@redhat.com]

In message <20030129165747.GA712@tornado.toronto.redhat.com>, Diego Novillo wri
tes:
 >On Wed, 29 Jan 2003, Daniel Berlin wrote:
 >
 >> >
 >> >  1. We get a list of all the blocks B dominates via get_dominated_by
 >> >  instead of walking all the blocks checking get_immediate_dominator.
 >> >  This avoids two walks over all the basic blocks and a boatload of
 >> >  calls to get_immediate_dominator.
 >> >
 >> >  2. Immediate dominators are invariant when computing the dominance
 >> >  frontiers.  So we build a little cache of them so that looking up
 >> >  the immediate dominator for a block is an array index rather than
 >> >  a full blown function call.  This saves some time as well.
 >> 
 >> If you look, you'll notice i already added a cache inside 
 >> get_immediate_dominator.
 >> If the function call overhead is dominating, just move it to a header 
 >> and static inline it.
 >> There is no need to add *another* cache.
 >>
 >That's not where the big savings come from.  They come from not
 >doing a linear scan over ALL the blocks in the flowgraph looking
 >for dominator children (step 1).
Right.  The big big winner is fixing the dominator children search.

Daniel -- I know about the cache in get_immediate_dominator.  But
it's really silly to have to make all those calls just to get one
piece of information.  The only thing sillier would be to inline
get_immediate_dominator.  inline functions are not a solution for
lameness.

 >Caching dominator children is what saved the SSA rewriting so
 >much time.  Caching the immediate dominators or always calling
 >get_immediate_dominator didn't save any time.  This is not true
 >in mainline, though.  We do the ET-tree traversal everytime.
It saves a little time in normal runs.  It saves a lot of time in
a profiled run and makes the profiling data a lot more accurate.

Jeff