[tree-ssa] Speeding things up

[Diego Novillo]

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).

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.


Diego.