Re: PATCH: remove bb_ann_d's num_preds field

[Jeffrey A Law <law at redhat dot com>]

On Wed, 2004-09-29 at 11:41, Andrew MacLeod wrote:
> On Wed, 2004-09-29 at 13:28, Jeffrey A Law wrote:
> > On Wed, 2004-09-29 at 07:54, Ben Elliston wrote:
> 
> > Probably the next thing to figure out is how to map between
> > incoming edges and phi node elements.
> > 
> > One possibility would be to record the index of each edge in its
> > pred/succ vectors.  So given an edge E, we can get the PHI arguments
> > associated with that edge from PHI_ARG_DEF (phi, E->pred_index).  At
> > first glance I tend to lean this direction, though I don't
> > particularly like the idea of enlarging the edge structure and
> > keeping the indices up-to-date.
> > 
> > Another would be to keep edges in the array in some well defined
> > order and use a binary search instead of a linear search.
> > 
> > Hopefully others have already thought through this problem enough to
> > provide better and more concrete suggestions.
> 
> For the immediate_uses stuff, I need to attach more use info to the PHI
> arguments. In doing so, we could also put each phi argument into a
> linked list hung off the edge. Given an edge, you could find all phi
> arguments associated with it. Given a phi argument, you could either
> traverse the list to the edge node, or alternatively keep a pointer to
> the edge.  More memory of course.
> 
> The list off the edge has some very nice properties for  removing edges
> or PHI nodes, but I havent gone down this path to actually implement it
> yet. It might not be so pleasant for other endevours.
Well, the two access patterns I see the most are:

  1. Iterate through all the arguments and perform an action on 
     them.  This happens often in DOM and CCP and in a few other
     places.  Edges aren't important -- we're usually trying to
     look at the args to determine something about the result.

  2. Iterate through all the PHIs associated with a particular
     edge.  Usually we still need the phi result & the arg in
     question.

#2 is what's causing us heartburn these days because we currently
walk all the args looking for the one we care about.  This gets
expensive with large in-degree nodes.

Hanging the PHI args off edges handles both reasonably well I think.
We just need to make sure that we can get both the result and the
PHI arg.

Jeff