[tree-ssa]: Generic link routines and some insert infrastructure

[Daniel Berlin]

On Wednesday, March 5, 2003, at 03:18  PM, Andrew MacLeod wrote:

> This is the first patch which provides some generalized routines which 
> the
> insert routines build upon.
>
> First, there is a set of routines for the tsi_stmt_iterator to add and
> remove statements as well as start new statement lists. These are 
> intended to
> be a generic interface which all tree's are constructed through. If 
> all the
> front ends are later modified to build trees through this mechanism, 
> then we are
> free to modify the implementation of trees. This in turn will allow us 
> to get
> rid of CE nodes as a linking mechanism, for instance.  All we'd need to
> change is the implementation of the tsi_ routines.
>
> That said, anyone actually trying to do this may discover there are 
> weaknesses
> or problems with this interface, and we may have to extend or change 
> it. We
> have to start somewhere, and these seems like a reasonable place to 
> begin. The
> insert routines use these to link in any new statements created as 
> well.
>
> The interface basically consists of:
>
>   enum tsi_iterator_update
>   {
>     TSI_NEW_STMT,
>     TSI_SAME_STMT
>   };
>
>   void tsi_link_before (tree_stmt_iterator *, tree, enum 
> tsi_iterator_update)
>   void tsi_link_after  (tree_stmt_iterator *, tree, enum 
> tsi_iterator_update)
>
> The third parameter indicates how we want the iterator passed in to be 
> modified.
> It can either be 'left alone' and point to the same stmt, or it can 
> point to the
> new stmt which was created. I thought about seperate routines, but 
> couldn't
> think of decent concise names, so this seemed reasonably clear.
>
>   void tsi_delink (tree_stmt_iterator *)
>
> The iterator is updated to point to the next statement after the one 
> delinked.
>
>   typedef tree tree_stmt_anchor;
>   tree_stmt_iterator tsi_new_stmt_list  (tree, tree_stmt_anchor *)
>
> An anchor is simply something which starts a stmt list. Currently, its 
> simply
> a tree pointer, but down the road, an implementation of trees could
> conceivably have the links outside the tree node. In this case an 
> anchor would
> be something else. At some point, child stmt lists will have to be
> tree_anchor's instead of trees as they are now. But for the moment I 
> haven't
> done anything about it, thats an issue to deal with once we have an 
> interface
> we like.  The routine tsi_new_stmt_list initializes a tree_stmt_anchor 
> to
> an initial tree stmt.
>
>   tree_stmt_iterator tsi_stmt_list_head (tree_stmt_anchor)
>
> Given an anchor, returns an iterator to the first stmt.
>
>
> These routines have been modestly tested, but not extensively. So far, 
> they
> aren't actually being used by anything. Its important to note that 
> using these
> routines and the tsi_stmt_iterator, you will never see a CE node, it 
> should
> always be under the covers.
>
> ---------
>
> I modified bsi_remove() to pass in the address of the iterator, and
> update it to the next statement. Previously, stmts were being removed,
> and the iterator bumped after removal... If we actually delinked the
> stmt under the covers when removing it, then our bumping would then be
> broken. I think its cleaner to have the bsi_remove routine update the
> iterator itself.
>
> I've added a sbitmap_realloc routine. When we add basic blocks or new
> variables during insertion, we have some bitmaps that need to grow as 
> well. I
> was suprised there wasn't a realloc routine already, but oh well.
>
> Although the implementation's aren't included in this patch, the 
> prototypes
> for the bsi_insert routines are present. The implementations will 
> follow
> before long.
>
> Anyway, this all bootstraps, and doesn't seem to cause any new errors.
>
> So, is this OK, or are there a few things we'd like to change? :-)

Give me a few minutes, i'll hook it up to SSAPRE and let you know.