Re: C++ edge_iterator (was: Re: [SH] PR 53976 - Add RTL pass to eliminate clrt, sett insns)

[Oleg Endo <oleg dot endo at t-online dot de>]

On Thu, 2013-12-12 at 03:13 -0500, Trevor Saunders wrote:
> On Wed, Dec 11, 2013 at 06:47:37PM +0100, Oleg Endo wrote:
> > On Thu, 2013-11-21 at 00:04 +0100, Steven Bosscher wrote:
> > > Declaring the edge_iterator inside the for() is not a good argument
> > > against FOR_EACH_EDGE. Of course, brownie points are up for grabs for
> > > the brave soul daring enough to make edge iterators be proper C++
> > > iterators... ;-)
> 
> so, as a first question why do we have a special edge iterator at all? it
> seems like we could just have a vec iterator and use that removing a
> bunch of indirection that seems pretty useless.

I don't know why it's there.  Looks like a remainder from the pre-C++
code, as the conversion is being done step by step.

> 
> > So, I gave it a try -- see the attached patch.
> > It allows edge iteration to look more like STL container iteration:
> > 
> > for (basic_block::edge_iterator ei = bb->pred_edges ().begin ();
> >      ei != bb->pred_edges ().end (); ++ei)
> > {
> >   basic_block pred_bb = (*ei)->src;
> >   ...
> > }
> 
> personally I'm not really a fan of overloading ++ / * that way, but I
> can't speak for anyone else.  I'd prefer something like
> 
> for (vec_iterator i = vec.forward_iterator (); !i.done (); i.next ())
> and
> for (backward_vec_iterator i = vec.backward_iterator (); !i.done (); i.next ())
> 
> but that might break range base for loops?

Right, that doesn't work with range-based for loops, since it doesn't
follow the standard concept of iteration.  For a more detailed
explanation, see also for example
http://www.codesynthesis.com/~boris/blog/2012/05/16/cxx11-range-based-for-loop/

BTW, if you look at the patch, I haven't overloaded any ++ operators:

Index: gcc/vec.h
===================================================================
--- gcc/vec.h	(revision 205866)
+++ gcc/vec.h	(working copy)
@@ -482,6 +482,15 @@
   void quick_grow (unsigned len);
   void quick_grow_cleared (unsigned len);
 
+  /* STL like iterator interface.  */
+  typedef T* iterator;
+  typedef const T* const_iterator;
+
+  iterator begin (void) { return &m_vecdata[0]; }
+  iterator end (void) { return &m_vecdata[m_vecpfx.m_num]; }
+  const_iterator begin (void) const { return &m_vecdata[0]; }
+  const_iterator end (void) const { &m_vecdata[m_vecpfx.m_num]; }

This is because raw pointers can be used as random access iterators.


> > Then the
> > typedef struct basic_block_def* basic_block;
> > 
> > is replaced with a wrapper class 'basic_block', which is just a simple
> > POD wrapper around a basic_block_def*.  There should be no penalties
> > compared to passing/storing raw pointers.  Because of the union with
> > constructor restriction of C++98 an additional wrapper class
> > 'basic_block_in_union' is required, which doesn't have any constructors
> > defined.
> > 
> > Having 'basic_block' as a class allows putting typedefs for the edge
> > iterator types in there (initially I tried putting the typedefs into
> > struct basic_block_def, but gengtype would bail out).
> 
> namespacing like that seems a little messy, but so is vec_iterator or
> such I guess.

I'm not sure which part of the namespacing you're referring to exactly.
The basic_block::edge_iterator thing?  Usually the iterator type is
defined in the container type.  In this case it would be vec<edge,
va_gc>.  The choice of the container type for storing edges is done in
basic_block_def.  Thus, ideally the iterator type should be obtained
from the basic_block_def class somehow.  A more bureaucratic way would
be to have a typedef inside basic_block_def (which is not possible
because of gengtype as mentioned before, so let's assume it's in
basic_block)... 

class basic_block
{
public:
  typedef vec<edge, va_gc> edge_container;

  edge_container& pred_edges (void);
  edge_container& succ_edges (void);

...
};

and then access the iterator via 
for (basic_block::edge_container::iterator i = bb->bb->pred_edges
().begin (); ...)

Having to type out iterator types is a well known annoyance of C++98.
Of course it's shorter to write
for (edge_iterator i = ...)

but that means, that there can be only one type of edge container ever.


> > It would also be possible to have a free standing definition / typedef
> > of edge_iterator, but it would conflict with the existing one and
> > require too many changes at once.  Moreover, the iterator type actually
> 
> I bet it'll be a lot of work but changing everything seems nice so maybe
> its worth just sitting down for a couple days and banging it out if it
> gives nicer names?

Nicer names than "edge_iterator" you mean?  I can't think of any at the
moment... 

> 
> > depends on the container type, which is vec<edge, ...>, and the
> > container type is defined/selected by the basic_block class.
> 
> I don't see how this is relevent

I hope that the explanation above makes it somewhat clearer.

> 
> > The following
> >   basic_block pred_bb = (*ei)->src;
> > 
> > can also be written as
> >   basic_block pred_bb = ei->src;
> > 
> > after converting the edge typedef to a wrapper of edge_def*.
> 
> this is assuming you overload operator -> on the iterator? I'm a c++ guy
> not a stl guy, but that seems pretty dubious to me.

Yes, that requires overloading of "operator ->".  However, in this case
not in the iterator, but in the pointer wrapper as I've done it already
in the patch for class basic_block (in the file basic_block2.h).  This
is common practice for pointer wrappers (see e.g. std::shared_ptr).

Overloading "operator ->" is also required in iterators.  See
http://www.cplusplus.com/reference/iterator/
If raw pointers are used as iterators (as in my example patch), there's
nothing to overload for those of course.

> > The idea of the approach is to allow co-existence of the new
> > edge_iterator and the old and thus be able to gradually convert code.
> > The wrappers around raw pointers also helo encapsulating the underlying
> > memory management issues.  For example, it would be much easier to
> > replace garbage collected objects with intrusive reference counting.
> 
> I don't think there's actually a memory management issue here,
> edge_iterator can only work if you allocate it on the stack since its
> not marked for gty, and afaik ggc doesn't scan the stack so the
> edge_iterator can't keep the vector alive.  Now I think it would be nice
> if these vectors moved out of gc memory, but I don't think this is
> particularly helpful for that.

Sorry, I think I caused a misunderstanding here.  By "memory management
issue" I just meant the way a container stores its objects, like whether
it's storing pointers to garbage collected objects, smart pointers like
shared_ptr<edge> or whatever.  I didn't mean that the iterator should
somehow influence the lifetime of the container.

Cheers,
Oleg