This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: C++ edge_iterator (was: Re: [SH] PR 53976 - Add RTL pass to eliminate clrt, sett insns)
- From: Trevor Saunders <tsaunders at mozilla dot com>
- To: Oleg Endo <oleg dot endo at t-online dot de>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Mon, 16 Dec 2013 09:57:51 -0500
- Subject: Re: C++ edge_iterator (was: Re: [SH] PR 53976 - Add RTL pass to eliminate clrt, sett insns)
- Authentication-results: sourceware.org; auth=none
- References: <1384975779 dot 2438 dot 119 dot camel at yam-132-YW-E178-FTW> <CABu31nPbcThrjzPN49E=VO3BrZjz5noaE95gjj-vx=0ikPj6+g at mail dot gmail dot com> <1386784057 dot 2455 dot 73 dot camel at yam-132-YW-E178-FTW> <20131212081349 dot GA1708 at tsaunders-iceball dot corp dot tor1 dot mozilla dot com> <1386968457 dot 2455 dot 129 dot camel at yam-132-YW-E178-FTW>
On Fri, Dec 13, 2013 at 10:00:57PM +0100, Oleg Endo wrote:
> 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.
yeah, somehow didn't occur to me T* just works (not that it wouldn't be
easier to see if the type had * in it)
> > > 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.
I'm saying I'd rather have edge_iterator than
basic_blokc::edge_iterator.
> 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 = ...)
actually what I really want to do is make returning a const vector part
of the api for getting the edge list from a basic block and then just
write
for (edge *e = vec.begin (); e != vec.end (); e++)
which imo makes it clear what's happening and is short, but I guess
richi doesn't like the interface being that a vector is returned :/
> but that means, that there can be only one type of edge container ever.
gcc seems to have survived for a long time with a single edge_iterator
so I don't see much reason to worry about allowing
basic_block::edge_iterator and foobar::edge_iterator.
> > > 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...
well, I meant edge_iterator instead of basic_block::edge_iterator which
afaik is what you proposed?
> > > 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).
I know doing this for pointer wrappers is common and I think that's
fine. However I'm not really convinced we need to or should make
basic_block a pointer wrapper class, I'd wrather see basic_block_def
become basic_block, and use basic_block * all over.
> 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.
yeah, I'm not really a fan of that style of iterator :/
> > > 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.
sure, I agree C++ makes memory management easier.
Trev
> Cheers,
> Oleg
>