Re: PATCH: remove bb_ann_d's num_preds field

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> > > > > keeping the indices up-to-date.
> > > > 
> > > > This in fact is pretty straightforward -- we have only a few functions
> > > > that modify the edges directly (from what I remember from the time I
> > > > wrote the patch to implement this, actually only some 3 or 4 functions
> > > > needed to be changed).
> > > > 
> > > > Also it is quite simple to check that nothing goes wrong (the indices
> > > > can be verified in verify_cfg and failure to keep edges and arguments
> > > > of phi nodes in sync almost surely leads to failure in verify_ssa,
> > > > or if you want to be more thorough, you can still have edges recorded
> > > > in phi arguments with ENABLE_CHECKING).
> > > > 
> > > I do not see why you need any explicit connection between the phi data
> > > structure and the in-edge data structure. 
> > > 
> > > I would suggest that you change to the current linked list
> > > representation of the in-edges to use exactly the same vector
> > > representation that you use for the phi-function edges.  This way the
> > > index of the phi function operand becomes the index into the in-edge
> > > and vica-versa.
> > > 
> > > Since it makes no sense to add or delete operands without doing the
> > > same to the edges, they should stay in sync as long as the phi operands
> > > are created properly initially.  
> > > 
> > > This will centainly be the most space and time efficient, since there
> > > are no explicit cross connections to maintain or index thru.
> > 
> > you still need to know the index of the edge in the vector, so that you
> > are able to find argument on an edge in O(1) (which is basically what
> > we are arguing about here).
> I wonder how often we could get the index from out iterator.
> 
> ie, how often is it the case that we're doing something like
> 
> FOR_EACH_EDGE (e, ei, bb->succs)
>   FOR_EACH_PHI in e->dest
>     find the argument associated with e
> 
> vs finding a PHI argument for an arbitrary edge.
> 
> Or something similar.  For the first class of uses we ought to be able
> to get the index via the FOR_EACH_EDGE code by keeping an index
> in the iterator.  In the second case we'd need an index in the edge
> itself or something similar.

just a note -- there is another possibility that is sometimes used (and
maybe it is the one Kenneth referred to), and it is storing directly the
edge (not pointer to it) in predecessors vector, which indeed saves you
index in predecessors vector, and possibly you might also get a better
cache locality.

The problem with this solution is that when predecessors get added,
you may be forced to reallocate the predecessors vector, and then the
pointers to the edges get wrong and must be patched.  Similarly if you
change order of edges in the vector (for example due to edge removal
or redirection).

The other (minor) problem is that the solution is assymetric (in
successors vectors, you still store pointers to the edges), which makes
creating code that could be used for both directions a bit more
complicated (although with proper encalupsation of the accessor routines
this should not be that great problem).

Zdenek