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

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, 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;
  ...
}

The idea is to first make class vec look more like an STL container.
This would also allow iterating it with std::for_each and use C++11
range based for loop (in a few years maybe).  It would also make it
easier to replace vec uses with STL containers if needed and vice versa.

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).
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
depends on the container type, which is vec<edge, ...>, and the
container type is defined/selected by the basic_block class.

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*.

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.

Comments and feedback appreciated.

Cheers,
Oleg

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.

> 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?

> 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.

> 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?

> 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

> 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.

> 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.

Trev

> Comments and feedback appreciated.
> 
> Cheers,
> Oleg

> Index: gcc/coretypes.h
> ===================================================================
> --- gcc/coretypes.h	(revision 205801)
> +++ gcc/coretypes.h	(working copy)
> @@ -153,8 +153,8 @@
>  typedef struct edge_def *edge;
>  typedef const struct edge_def *const_edge;
>  struct basic_block_def;
> -typedef struct basic_block_def *basic_block;
> -typedef const struct basic_block_def *const_basic_block;
> +class basic_block;
> +class const_basic_block;
>  
>  #define obstack_chunk_alloc	((void *(*) (long)) xmalloc)
>  #define obstack_chunk_free	((void (*) (void *)) free)
> Index: gcc/tracer.c
> ===================================================================
> --- gcc/tracer.c	(revision 205801)
> +++ gcc/tracer.c	(working copy)
> @@ -102,7 +102,7 @@
>  
>    /* A transaction is a single entry multiple exit region.  It must be
>       duplicated in its entirety or not at all.  */
> -  g = last_stmt (CONST_CAST_BB (bb));
> +  g = last_stmt (basic_block (bb));
>    if (g && gimple_code (g) == GIMPLE_TRANSACTION)
>      return true;
>  
> Index: gcc/emit-rtl.c
> ===================================================================
> --- gcc/emit-rtl.c	(revision 205801)
> +++ gcc/emit-rtl.c	(working copy)
> @@ -4446,7 +4446,7 @@
>  emit_note_after (enum insn_note subtype, rtx after)
>  {
>    rtx note = make_note_raw (subtype);
> -  basic_block bb = BARRIER_P (after) ? NULL : BLOCK_FOR_INSN (after);
> +  basic_block bb = BARRIER_P (after) ? (basic_block_def*)NULL : (basic_block_def*)BLOCK_FOR_INSN (after);
>    bool on_bb_boundary_p = (bb != NULL && BB_END (bb) == after);
>  
>    if (note_outside_basic_block_p (subtype, on_bb_boundary_p))
> @@ -4462,7 +4462,7 @@
>  emit_note_before (enum insn_note subtype, rtx before)
>  {
>    rtx note = make_note_raw (subtype);
> -  basic_block bb = BARRIER_P (before) ? NULL : BLOCK_FOR_INSN (before);
> +  basic_block bb = BARRIER_P (before) ? (basic_block_def*)NULL : (basic_block_def*)BLOCK_FOR_INSN (before);
>    bool on_bb_boundary_p = (bb != NULL && BB_HEAD (bb) == before);
>  
>    if (note_outside_basic_block_p (subtype, on_bb_boundary_p))
> Index: gcc/vec.h
> ===================================================================
> --- gcc/vec.h	(revision 205801)
> +++ 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]; }
> +
>    /* vec class can access our internal data and functions.  */
>    template <typename, typename, typename> friend struct vec;
>  
> Index: gcc/tree-cfg.c
> ===================================================================
> --- gcc/tree-cfg.c	(revision 205801)
> +++ gcc/tree-cfg.c	(working copy)
> @@ -7350,7 +7350,7 @@
>  static bool
>  gimple_block_ends_with_condjump_p (const_basic_block bb)
>  {
> -  gimple stmt = last_stmt (CONST_CAST_BB (bb));
> +  gimple stmt = last_stmt (basic_block (bb));
>    return (stmt && gimple_code (stmt) == GIMPLE_COND);
>  }
>  
> Index: gcc/tree-inline.h
> ===================================================================
> --- gcc/tree-inline.h	(revision 205801)
> +++ gcc/tree-inline.h	(working copy)
> @@ -117,7 +117,7 @@
>    struct pointer_set_t *statements_to_fold;
>  
>    /* Entry basic block to currently copied body.  */
> -  basic_block entry_bb;
> +  basic_block_def* entry_bb;
>  
>    /* For partial function versioning, bitmap of bbs to be copied,
>       otherwise NULL.  */
> Index: gcc/dominance.c
> ===================================================================
> --- gcc/dominance.c	(revision 205801)
> +++ gcc/dominance.c	(working copy)
> @@ -500,6 +500,8 @@
>    TBB v, w, k, par;
>    basic_block en_block;
>    edge_iterator ei, einext;
> +  TBB k1;
> +  basic_block b;
>  
>    if (reverse)
>      en_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
> @@ -535,9 +537,6 @@
>           semidominator.  */
>        while (!ei_end_p (ei))
>  	{
> -	  TBB k1;
> -	  basic_block b;
> -
>  	  e = ei_edge (ei);
>  	  b = (reverse) ? e->dest : e->src;
>  	  einext = ei;
> Index: gcc/basic-block.h
> ===================================================================
> --- gcc/basic-block.h	(revision 205801)
> +++ gcc/basic-block.h	(working copy)
> @@ -23,6 +23,7 @@
>  #include "predict.h"
>  #include "vec.h"
>  #include "function.h"
> +#include "basic-block2.h"
>  
>  /* Use gcov_type to hold basic block counters.  Should be at least
>     64bit.  Although a counter cannot be negative, we use a signed
> @@ -169,6 +170,12 @@
>    vec<edge, va_gc> *preds;
>    vec<edge, va_gc> *succs;
>  
> +  vec<edge, va_gc>& pred_edges (void) { return *preds; }
> +  const vec<edge, va_gc>& pred_edges (void) const { return *preds; }
> +
> +  vec<edge, va_gc>& succ_edges (void) { return *succs; }
> +  const vec<edge, va_gc>& succ_edges (void) const { return *succs; }
> +
>    /* Auxiliary info specific to a pass.  */
>    PTR GTY ((skip (""))) aux;
>  
> Index: gcc/config/sh/sh_optimize_sett_clrt.cc
> ===================================================================
> --- gcc/config/sh/sh_optimize_sett_clrt.cc	(revision 205801)
> +++ gcc/config/sh/sh_optimize_sett_clrt.cc	(working copy)
> @@ -390,10 +390,10 @@
>      {
>        prev_visited_bb.push_back (bb);
>  
> -      for (edge_iterator ei = ei_start (bb->preds); !ei_end_p (ei);
> -	   ei_next (&ei))
> +      for (basic_block::edge_iterator ei = bb->pred_edges ().begin ();
> +	   ei != bb->pred_edges ().end (); ++ei)
>  	{
> -	  basic_block pred_bb = ei_edge (ei)->src;
> +	  basic_block pred_bb = (*ei)->src;
>  	  pred_bb_count += 1;
>  	  find_last_ccreg_values (BB_END (pred_bb), pred_bb, values_out,
>  				  prev_visited_bb);
> Index: gcc/cfgloop.h
> ===================================================================
> --- gcc/cfgloop.h	(revision 205801)
> +++ gcc/cfgloop.h	(working copy)
> @@ -24,6 +24,7 @@
>  #include "bitmap.h"
>  #include "sbitmap.h"
>  #include "function.h"
> +#include "basic-block2.h"
>  
>  /* Structure to hold decision about unrolling/peeling.  */
>  enum lpt_dec
> Index: gcc/dumpfile.c
> ===================================================================
> --- gcc/dumpfile.c	(revision 205801)
> +++ gcc/dumpfile.c	(working copy)
> @@ -25,6 +25,7 @@
>  #include "tree.h"
>  #include "gimple-pretty-print.h"
>  #include "context.h"
> +#include "basic-block2.h"
>  
>  /* If non-NULL, return one past-the-end of the matching SUBPART of
>     the WHOLE string.  */
> Index: gcc/tree-ssa-strlen.c
> ===================================================================
> --- gcc/tree-ssa-strlen.c	(revision 205801)
> +++ gcc/tree-ssa-strlen.c	(working copy)
> @@ -2033,7 +2033,7 @@
>  
>    bb->aux = stridx_to_strinfo;
>    if (vec_safe_length (stridx_to_strinfo) && !strinfo_shared ())
> -    (*stridx_to_strinfo)[0] = (strinfo) bb;
> +    (*stridx_to_strinfo)[0] = (strinfo) bb.get ();
>  }
>  
>  /* Callback for walk_dominator_tree.  Free strinfo vector if it is
> @@ -2046,7 +2046,7 @@
>      {
>        stridx_to_strinfo = ((vec<strinfo, va_heap, vl_embed> *) bb->aux);
>        if (vec_safe_length (stridx_to_strinfo)
> -	  && (*stridx_to_strinfo)[0] == (strinfo) bb)
> +	  && (*stridx_to_strinfo)[0] == (strinfo) bb.get ())
>  	{
>  	  unsigned int i;
>  	  strinfo si;
> Index: gcc/rtl.h
> ===================================================================
> --- gcc/rtl.h	(revision 205801)
> +++ gcc/rtl.h	(working copy)
> @@ -29,6 +29,7 @@
>  #include "alias.h"
>  #include "hashtab.h"
>  #include "flags.h"
> +#include "basic-block2.h"
>  
>  /* Value used by some passes to "recognize" noop moves as valid
>   instructions.  */
> @@ -193,7 +194,7 @@
>    addr_diff_vec_flags rt_addr_diff_vec_flags;
>    struct cselib_val_struct *rt_cselib;
>    tree rt_tree;
> -  basic_block rt_bb;
> +  basic_block_in_union rt_bb;
>    mem_attrs *rt_mem;
>    reg_attrs *rt_reg;
>    struct constant_descriptor_rtx *rt_constant;
> Index: gcc/df.h
> ===================================================================
> --- gcc/df.h	(revision 205801)
> +++ gcc/df.h	(working copy)
> @@ -392,7 +392,7 @@
>  
>    /* Artificial refs do not have an insn, so to get the basic block,
>       it must be explicitly here.  */
> -  basic_block bb;
> +  basic_block_in_union bb;
>  };
>  
>  
> Index: gcc/ifcvt.c
> ===================================================================
> --- gcc/ifcvt.c	(revision 205801)
> +++ gcc/ifcvt.c	(working copy)
> @@ -65,7 +65,7 @@
>  
>  #define IFCVT_MULTIPLE_DUMPS 1
>  
> -#define NULL_BLOCK	((basic_block) NULL)
> +#define NULL_BLOCK	(basic_block ((basic_block_def*) NULL))
>  
>  /* True if after combine pass.  */
>  static bool ifcvt_after_combine;

On Wed, Dec 11, 2013 at 6:47 PM, Oleg Endo <oleg.endo@t-online.de> 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, 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;
>   ...
> }
>
> The idea is to first make class vec look more like an STL container.
> This would also allow iterating it with std::for_each and use C++11
> range based for loop (in a few years maybe).  It would also make it
> easier to replace vec uses with STL containers if needed and vice versa.
>
> 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).
> 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
> depends on the container type, which is vec<edge, ...>, and the
> container type is defined/selected by the basic_block class.
>
> 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*.
>
> 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.
>
> Comments and feedback appreciated.

Apart from the issues raised by Trevor I want to question if we want
to transition
to STL-like iterators (yeah, I know, the gsi_ ones are already
similar).  An obvious
cleanup to the existing FOR_EACH machinery is to declare the iterator inside
the FOR_EACH, thus make it an implementation detail (like I did with the loop
iterator).

Richard.

> Cheers,
> Oleg

On Fri, 2013-12-13 at 10:38 +0100, Richard Biener wrote:

> Apart from the issues raised by Trevor I want to question if we want
> to transition
> to STL-like iterators (yeah, I know, the gsi_ ones are already
> similar).

I think it's easier to read and -- more importantly -- understand
"foreign" code if that code is using well established names and
semantics for doing common trivial things.  Iterating over containers is
one such thing.  Moreover, STL usage is allowed in GCC and adopting STL
container semantics will make it easier to switch container
implementations (e.g. try using std::vector instead of vec) and have a
more consistent way of doing such common things.

>   An obvious
> cleanup to the existing FOR_EACH machinery is to declare the iterator inside
> the FOR_EACH, thus make it an implementation detail (like I did with the loop
> iterator).

I think variable declarations with hard coded names hidden in macros are
not always straight forward to follow.
If there was a common way of iterating over stuff, something like
boost's FOR_EACH could be added instead, although I don't think it's
worth the effort to re-implement it.

Cheers,
Oleg