Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Michael Matz]

Hi,

On Wed, 23 May 2018, Richard Biener wrote:

> > alloc_flags (>cfg->bb_flag_pool);
> > alloc_flags (>cfg->edge_flag_pool);
> 
> You'll end up with sth like
> 
>alloc_flags flag (BB_FLAG_POOL_FOR_FN (cfun));
> 
> then, mixing C++ RAII and macros! (eh)

First: I don't see the problem.  Second: if the above needs to use a macro 
you should have used a macro as well in your two classes.

> Note you missed to name the variable you declare.

Sure.

> And yes, template deduction should make this work w/o writing 
> alloc_flags flag (...).

If you insist on an template, maybe.  But why would you?


Ciao,
Michael.

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Richard Biener]

On Wed, 23 May 2018, Michael Matz wrote:

> Hi,
> 
> On Wed, 23 May 2018, Eric Botcazou wrote:
> 
> > > Maybe you should convert the thing to a template when the need arises
> > > instead of before?  You have now added 54 lines of code for wrapping an
> > > int!
> > 
> > Yeah, it took me 5 minutes to understand what all this fluff is about!
> 
> So, what I think this should look like: only one non-templated class for 
> RAII purposes, which get's the pool to allocate from as a parameter in the 
> ctor.
> 
> Use:
> 
> alloc_flags (>cfg->bb_flag_pool);
> alloc_flags (>cfg->edge_flag_pool);

You'll end up with sth like

   alloc_flags flag (BB_FLAG_POOL_FOR_FN (cfun));

then, mixing C++ RAII and macros! (eh)  Note you missed to name the
variable you declare.  And yes, template deduction should make this
work w/o writing alloc_flags flag (...).

> I don't see the sense in creating two classes for determining the pool 
> (and then adding a third class when another pool is invented somewhere 
> else) just for going from cfun to cfun->cfg->foopool.  Also Richi asked if 
> the flag pools (sigh, a large word for an int) should be merged.  I think 
> at this time they should be, but that the class ctor should still take the 
> pool param (instead of the function), even if right now there'd only be 
> one.
> 
> So much for bike shedding :)

:/

Richard.

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Michael Matz]

Hi,

On Wed, 23 May 2018, Eric Botcazou wrote:

> > Maybe you should convert the thing to a template when the need arises
> > instead of before?  You have now added 54 lines of code for wrapping an
> > int!
> 
> Yeah, it took me 5 minutes to understand what all this fluff is about!

So, what I think this should look like: only one non-templated class for 
RAII purposes, which get's the pool to allocate from as a parameter in the 
ctor.

Use:

alloc_flags (>cfg->bb_flag_pool);
alloc_flags (>cfg->edge_flag_pool);

I don't see the sense in creating two classes for determining the pool 
(and then adding a third class when another pool is invented somewhere 
else) just for going from cfun to cfun->cfg->foopool.  Also Richi asked if 
the flag pools (sigh, a large word for an int) should be merged.  I think 
at this time they should be, but that the class ctor should still take the 
pool param (instead of the function), even if right now there'd only be 
one.

So much for bike shedding :)


Ciao,
Michael.

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Eric Botcazou]

> Maybe you should convert the thing to a template when the need arises
> instead of before?  You have now added 54 lines of code for wrapping an
> int!

Yeah, it took me 5 minutes to understand what all this fluff is about!

-- 
Eric Botcazou

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Michael Matz]

Hi,

On Wed, 23 May 2018, Richard Biener wrote:

> > I messed up the conversion to a template. The bitnum should be 
> > subtracted from HOST_BITS_PER_WIDE_INT and yes, 1 in unsigned hwi 
> > should be shifted.

Maybe you should convert the thing to a template when the need arises 
instead of before?  You have now added 54 lines of code for wrapping an 
int!


Ciao,
Michael.

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Richard Biener]

On Tue, 22 May 2018, Richard Biener wrote:

> On May 22, 2018 6:53:57 PM GMT+02:00, Joseph Myers  
> wrote:
> >On Tue, 22 May 2018, Richard Biener wrote:
> >
> >> +  if (*sptr & (1 << (CHAR_BIT * sizeof (T) - 1)))
> >> +  gcc_unreachable ();
> >> +  m_flag = 1 << ((CHAR_BIT * sizeof (T)) - clz_hwi (*sptr));
> >
> >I don't see how the use of clz_hwi works with a type T that may be 
> >narrower than HOST_WIDE_INT.  Surely this logic requires a count of 
> >leading zeros in something of type T, not a possibly larger number of 
> >leading zeros after conversion to HOST_WIDE_INT?  Also, if T is wider
> >than 
> >int, shifting plain 1 won't work here.
> 
> I messed up the conversion to a template. The bitnum should be subtracted 
> from HOST_BITS_PER_WIDE_INT and yes, 1 in unsigned hwi should be shifted. 

So this is the final patch, I've changed the flags compute to use ffs
which is better suited to find a "random" unset bit.  For types
smaller than HOST_WIDE_INT we'll find bits outside of the range but
the truncated mask will be zero.  I guess the
ffsl ((unsigned long)~intvar) cannot be easily pattern-matched to
ffs so a way to do that unsigned conversion would be nice (or
mass-change all signed flag ints to unsigned...).

I took the opportunity to change dfs_enumerate_from to use
an auto_bb_flag rather than a static sbitmap.  That should be
profitable given we currently have the cacheline with BB flags
loaded anyways because we access BB index.  So using a BB flag
will avoid pulling in the sbitmap cachelines.  But it trades
possibly less memory stores for it in case the sbitmap modifications
were adjacent.  OTOH applying a mask should be cheaper than
variable shifts involved in sbitmap bit access.  It's definitely
less code ;)

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

OK for trunk?

Thanks,
Richard.

>From 0091e95a133454da62973ad570c97e7b61bfd0ec Mon Sep 17 00:00:00 2001
From: Richard Guenther 
Date: Fri, 18 May 2018 13:01:36 +0200
Subject: [PATCH] add dynamic cfg flag allocation

* cfg.h (struct control_flow_graph): Add edge_flags_allocated and
bb_flags_allocated members.
(auto_flag): New RAII class for allocating flags.
(auto_edge_flag): New RAII class for allocating edge flags.
(auto_bb_flag): New RAII class for allocating bb flags.
* cfgloop.c (verify_loop_structure): Allocate temporary edge
flag dynamically.
* cfganal.c (dfs_enumerate_from): Remove use of visited sbitmap
in favor of temporarily allocated BB flag.
* hsa-brig.c: Re-order includes.
* hsa-dump.c: Likewise.
* hsa-regalloc.c: Likewise.
* print-rtl.c: Likewise.
* profile-count.c: Likewise.

diff --git a/gcc/cfg.c b/gcc/cfg.c
index 11026e7209a..f8b217d39ca 100644
--- a/gcc/cfg.c
+++ b/gcc/cfg.c
@@ -79,6 +79,8 @@ init_flow (struct function *the_fun)
 = EXIT_BLOCK_PTR_FOR_FN (the_fun);
   EXIT_BLOCK_PTR_FOR_FN (the_fun)->prev_bb
 = ENTRY_BLOCK_PTR_FOR_FN (the_fun);
+  the_fun->cfg->edge_flags_allocated = EDGE_ALL_FLAGS;
+  the_fun->cfg->bb_flags_allocated = BB_ALL_FLAGS;
 }
 
 /* Helper function for remove_edge and clear_edges.  Frees edge structure
diff --git a/gcc/cfg.h b/gcc/cfg.h
index 0953456782b..9fff135d11f 100644
--- a/gcc/cfg.h
+++ b/gcc/cfg.h
@@ -74,6 +74,10 @@ struct GTY(()) control_flow_graph {
 
   /* Maximal count of BB in function.  */
   profile_count count_max;
+
+  /* Dynamically allocated edge/bb flags.  */
+  int edge_flags_allocated;
+  int bb_flags_allocated;
 };
 
 
@@ -121,4 +125,60 @@ extern basic_block get_bb_copy (basic_block);
 void set_loop_copy (struct loop *, struct loop *);
 struct loop *get_loop_copy (struct loop *);
 
+/* Generic RAII class to allocate a bit from storage of integer type T.
+   The allocated bit is accessible as mask with the single bit set
+   via the conversion operator to T.  */
+
+template 
+class auto_flag
+{
+public:
+  /* static assert T is integer type of max HOST_WIDE_INT precision.  */
+  auto_flag (T *sptr)
+{
+  m_sptr = sptr;
+  int free_bit = ffs_hwi (~*sptr);
+  /* If there are no unset bits... */
+  if (free_bit == 0)
+   gcc_unreachable ();
+  m_flag = HOST_WIDE_INT_1U << (free_bit - 1);
+  /* ...or if T is signed and thus the complement is sign-extended,
+ check if we ran out of bits.  We could spare us this bit
+if we could use C++11 std::make_unsigned::type to pass
+~*sptr to ffs_hwi.  */
+  if (m_flag == 0)
+   gcc_unreachable ();
+  gcc_checking_assert ((*sptr & m_flag) == 0);
+  *sptr |= m_flag;
+}
+  ~auto_flag ()
+{
+  gcc_checking_assert ((*m_sptr & m_flag) == m_flag);
+  *m_sptr &= ~m_flag;
+}
+  operator T () const { return m_flag; }
+private:
+  T *m_sptr;
+  T m_flag;
+};
+
+/* RAII class to allocate an edge flag for temporary use.  You have
+   to clear the flag from all edges when 

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Richard Biener]

On May 22, 2018 6:53:57 PM GMT+02:00, Joseph Myers  
wrote:
>On Tue, 22 May 2018, Richard Biener wrote:
>
>> +  if (*sptr & (1 << (CHAR_BIT * sizeof (T) - 1)))
>> +gcc_unreachable ();
>> +  m_flag = 1 << ((CHAR_BIT * sizeof (T)) - clz_hwi (*sptr));
>
>I don't see how the use of clz_hwi works with a type T that may be 
>narrower than HOST_WIDE_INT.  Surely this logic requires a count of 
>leading zeros in something of type T, not a possibly larger number of 
>leading zeros after conversion to HOST_WIDE_INT?  Also, if T is wider
>than 
>int, shifting plain 1 won't work here.

I messed up the conversion to a template. The bitnum should be subtracted from 
HOST_BITS_PER_WIDE_INT and yes, 1 in unsigned hwi should be shifted. 

Richard. 

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Joseph Myers]

On Tue, 22 May 2018, Richard Biener wrote:

> +  if (*sptr & (1 << (CHAR_BIT * sizeof (T) - 1)))
> + gcc_unreachable ();
> +  m_flag = 1 << ((CHAR_BIT * sizeof (T)) - clz_hwi (*sptr));

I don't see how the use of clz_hwi works with a type T that may be 
narrower than HOST_WIDE_INT.  Surely this logic requires a count of 
leading zeros in something of type T, not a possibly larger number of 
leading zeros after conversion to HOST_WIDE_INT?  Also, if T is wider than 
int, shifting plain 1 won't work here.

-- 
Joseph S. Myers
jos...@codesourcery.com

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Richard Biener]

On Tue, 22 May 2018, David Malcolm wrote:

> On Tue, 2018-05-22 at 10:43 +0200, Richard Biener wrote:
> > On Mon, 21 May 2018, Jeff Law wrote:
> > 
> > > On 05/18/2018 07:15 AM, David Malcolm wrote:
> > > > On Fri, 2018-05-18 at 13:11 +0200, Richard Biener wrote:
> > > > > The following adds a simple alloc/free_flag machinery
> > > > > allocating
> > > > > bits from an int typed pool and applies that to bb->flags and
> > > > > edge-
> > > > > > flags.
> > > > > 
> > > > > This should allow infrastructure pieces to use egde/bb flags
> > > > > temporarily
> > > > > without worrying that users might already use it as for example
> > > > > BB_VISITED and friends.  It converts one clever user to the new
> > > > > interface.
> > > > > 
> > > > > The allocation state is per CFG but we could also make it
> > > > > global
> > > > > or merge the two pools so one allocates a flag that can be used
> > > > > for
> > > > > bbs and edges at the same time.
> > > > > 
> > > > > Thus - any opinions welcome.  I'm mainly targeting cfganal
> > > > > algorithms
> > > > > where I want to add a few region-based ones that to be
> > > > > O(region-size)
> > > > > complexity may not use sbitmaps for visited sets because of the
> > > > > clearing
> > > > > overhead and bitmaps are probably more expensive to use than a
> > > > > BB/edge
> > > > > flag that needs to be cleared afterwards.
> > > > > 
> > > > > Built on x86_64, otherwise untested.
> > > > > 
> > > > > Any comments?
> > > > 
> > > > Rather than putting alloc/free pairs at the usage sites, how
> > > > about an
> > > > RAII class?  Something like this:
> > > 
> > > Yes, please if at all possible we should be using RAII.
> > 
> > So like the following?  (see comments in the hwint.h hunk for
> > extra C++ questions...)
> > 
> > I dropped the non-RAII interface - it's very likely never needed.
> > 
> > Better suggestions for placement of auto_flag welcome.
> 
> Do you have ideas for other uses?  If not, maybe just put it in cfg.h
> right in front of auto_edge_flag and auto_bb_flag, for simplicity?

I don't have more users but of course gimple stmts and tree nodes
would come to my mind ;)  Basically nodes in any data structure we walk
and that we can (cheaply) re-walk to clear flags in the end.  Cost
comparison would always be to a simple pointer-set or bitmap.

But sure, I'll stick it to cfg.h for the moment.  As said, my
main use case didn't materialize on trunk yet but is in a patchset
I have to bring up-to-date.

> > Thanks,
> > Richard.
> [...snip...]
> 
> The new classes are missing leading comments.  I think it's worth
> noting that the auto_flag (and thus their subclasses) hold a pointer
> into a control_flow_graph instance, but they don't interact with the
> garbage collector, so there's an implicit assumption that the auto_flag
> instances are short-lived and that the underlying storage is kept alive
> some other way (e.g. as cfun is kept alive by cfun being a GC root).

Ah, yes - missed a comment.

> 
> > +class auto_edge_flag : public auto_flag
> > +{
> > +public:
> > +  auto_edge_flag (function *fun)
> > +: auto_flag (>cfg->edge_flags_allocated) {}
> > +};
> > +
> > +class auto_bb_flag : public auto_flag
> > +{
> > +public:
> > +  auto_bb_flag (function *fun)
> > +: auto_flag (>cfg->bb_flags_allocated) {}
> > +};
> > +
> >  #endif /* GCC_CFG_H */
> 
> [...snip...]
> 
> Hope this is constructive

Sure!

Thanks,
Richard.

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[David Malcolm]

On Tue, 2018-05-22 at 10:43 +0200, Richard Biener wrote:
> On Mon, 21 May 2018, Jeff Law wrote:
> 
> > On 05/18/2018 07:15 AM, David Malcolm wrote:
> > > On Fri, 2018-05-18 at 13:11 +0200, Richard Biener wrote:
> > > > The following adds a simple alloc/free_flag machinery
> > > > allocating
> > > > bits from an int typed pool and applies that to bb->flags and
> > > > edge-
> > > > > flags.
> > > > 
> > > > This should allow infrastructure pieces to use egde/bb flags
> > > > temporarily
> > > > without worrying that users might already use it as for example
> > > > BB_VISITED and friends.  It converts one clever user to the new
> > > > interface.
> > > > 
> > > > The allocation state is per CFG but we could also make it
> > > > global
> > > > or merge the two pools so one allocates a flag that can be used
> > > > for
> > > > bbs and edges at the same time.
> > > > 
> > > > Thus - any opinions welcome.  I'm mainly targeting cfganal
> > > > algorithms
> > > > where I want to add a few region-based ones that to be
> > > > O(region-size)
> > > > complexity may not use sbitmaps for visited sets because of the
> > > > clearing
> > > > overhead and bitmaps are probably more expensive to use than a
> > > > BB/edge
> > > > flag that needs to be cleared afterwards.
> > > > 
> > > > Built on x86_64, otherwise untested.
> > > > 
> > > > Any comments?
> > > 
> > > Rather than putting alloc/free pairs at the usage sites, how
> > > about an
> > > RAII class?  Something like this:
> > 
> > Yes, please if at all possible we should be using RAII.
> 
> So like the following?  (see comments in the hwint.h hunk for
> extra C++ questions...)
> 
> I dropped the non-RAII interface - it's very likely never needed.
> 
> Better suggestions for placement of auto_flag welcome.

Do you have ideas for other uses?  If not, maybe just put it in cfg.h
right in front of auto_edge_flag and auto_bb_flag, for simplicity?

> Thanks,
> Richard.
[...snip...]

The new classes are missing leading comments.  I think it's worth
noting that the auto_flag (and thus their subclasses) hold a pointer
into a control_flow_graph instance, but they don't interact with the
garbage collector, so there's an implicit assumption that the auto_flag
instances are short-lived and that the underlying storage is kept alive
some other way (e.g. as cfun is kept alive by cfun being a GC root).


> +class auto_edge_flag : public auto_flag
> +{
> +public:
> +  auto_edge_flag (function *fun)
> +: auto_flag (>cfg->edge_flags_allocated) {}
> +};
> +
> +class auto_bb_flag : public auto_flag
> +{
> +public:
> +  auto_bb_flag (function *fun)
> +: auto_flag (>cfg->bb_flags_allocated) {}
> +};
> +
>  #endif /* GCC_CFG_H */

[...snip...]

Hope this is constructive
Dave

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Richard Biener]

On Mon, 21 May 2018, Jeff Law wrote:

> On 05/18/2018 07:15 AM, David Malcolm wrote:
> > On Fri, 2018-05-18 at 13:11 +0200, Richard Biener wrote:
> >> The following adds a simple alloc/free_flag machinery allocating
> >> bits from an int typed pool and applies that to bb->flags and edge-
> >>> flags.
> >> This should allow infrastructure pieces to use egde/bb flags
> >> temporarily
> >> without worrying that users might already use it as for example
> >> BB_VISITED and friends.  It converts one clever user to the new
> >> interface.
> >>
> >> The allocation state is per CFG but we could also make it global
> >> or merge the two pools so one allocates a flag that can be used for
> >> bbs and edges at the same time.
> >>
> >> Thus - any opinions welcome.  I'm mainly targeting cfganal algorithms
> >> where I want to add a few region-based ones that to be O(region-size)
> >> complexity may not use sbitmaps for visited sets because of the
> >> clearing
> >> overhead and bitmaps are probably more expensive to use than a
> >> BB/edge
> >> flag that needs to be cleared afterwards.
> >>
> >> Built on x86_64, otherwise untested.
> >>
> >> Any comments?
> > 
> > Rather than putting alloc/free pairs at the usage sites, how about an
> > RAII class?  Something like this:
> Yes, please if at all possible we should be using RAII.

So like the following?  (see comments in the hwint.h hunk for
extra C++ questions...)

I dropped the non-RAII interface - it's very likely never needed.

Better suggestions for placement of auto_flag welcome.

Thanks,
Richard.

>From 8ae07eb0aa6c430605a16f043ec08726f81b2442 Mon Sep 17 00:00:00 2001
From: Richard Guenther 
Date: Fri, 18 May 2018 13:01:36 +0200
Subject: [PATCH 2/2] add dynamic cfg flag allocation

* cfg.h (struct control_flow_graph): Add edge_flags_allocated and
bb_flags_allocated members.
(auto_edge_flag): New RAII class for allocating edge flags.
(auto_bb_flag): New RAII class for allocating bb flags.
* hwint.h (auto_flag): New RAII class for allocating flags.
* cfgloop.c (verify_loop_structure): Allocate temporary edge
flag dynamically.

cfg flag

diff --git a/gcc/cfg.c b/gcc/cfg.c
index 11026e7209a..f8b217d39ca 100644
--- a/gcc/cfg.c
+++ b/gcc/cfg.c
@@ -79,6 +79,8 @@ init_flow (struct function *the_fun)
 = EXIT_BLOCK_PTR_FOR_FN (the_fun);
   EXIT_BLOCK_PTR_FOR_FN (the_fun)->prev_bb
 = ENTRY_BLOCK_PTR_FOR_FN (the_fun);
+  the_fun->cfg->edge_flags_allocated = EDGE_ALL_FLAGS;
+  the_fun->cfg->bb_flags_allocated = BB_ALL_FLAGS;
 }
 
 /* Helper function for remove_edge and clear_edges.  Frees edge structure
diff --git a/gcc/cfg.h b/gcc/cfg.h
index 0953456782b..f9f762a520b 100644
--- a/gcc/cfg.h
+++ b/gcc/cfg.h
@@ -74,6 +74,10 @@ struct GTY(()) control_flow_graph {
 
   /* Maximal count of BB in function.  */
   profile_count count_max;
+
+  /* Dynamically allocated edge/bb flags.  */
+  int edge_flags_allocated;
+  int bb_flags_allocated;
 };
 
 
@@ -121,4 +125,18 @@ extern basic_block get_bb_copy (basic_block);
 void set_loop_copy (struct loop *, struct loop *);
 struct loop *get_loop_copy (struct loop *);
 
+class auto_edge_flag : public auto_flag
+{
+public:
+  auto_edge_flag (function *fun)
+: auto_flag (>cfg->edge_flags_allocated) {}
+};
+
+class auto_bb_flag : public auto_flag
+{
+public:
+  auto_bb_flag (function *fun)
+: auto_flag (>cfg->bb_flags_allocated) {}
+};
+
 #endif /* GCC_CFG_H */
diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index 8af793c6015..fb5ebad1dfd 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -1539,6 +1539,7 @@ verify_loop_structure (void)
   /* Check irreducible loops.  */
   if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
 {
+  auto_edge_flag saved_irr_mask (cfun);
   /* Record old info.  */
   auto_sbitmap irreds (last_basic_block_for_fn (cfun));
   FOR_EACH_BB_FN (bb, cfun)
@@ -1550,7 +1551,7 @@ verify_loop_structure (void)
bitmap_clear_bit (irreds, bb->index);
  FOR_EACH_EDGE (e, ei, bb->succs)
if (e->flags & EDGE_IRREDUCIBLE_LOOP)
- e->flags |= EDGE_ALL_FLAGS + 1;
+ e->flags |= saved_irr_mask;
}
 
   /* Recount it.  */
@@ -1576,20 +1577,20 @@ verify_loop_structure (void)
  FOR_EACH_EDGE (e, ei, bb->succs)
{
  if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
- && !(e->flags & (EDGE_ALL_FLAGS + 1)))
+ && !(e->flags & saved_irr_mask))
{
  error ("edge from %d to %d should be marked irreducible",
 e->src->index, e->dest->index);
  err = 1;
}
  else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
-  && (e->flags & (EDGE_ALL_FLAGS + 1)))
+  && (e->flags & saved_irr_mask))
{
  error ("edge from %d to %d should not be marked irreducible",
   

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[Jeff Law]

On 05/18/2018 07:15 AM, David Malcolm wrote:
> On Fri, 2018-05-18 at 13:11 +0200, Richard Biener wrote:
>> The following adds a simple alloc/free_flag machinery allocating
>> bits from an int typed pool and applies that to bb->flags and edge-
>>> flags.
>> This should allow infrastructure pieces to use egde/bb flags
>> temporarily
>> without worrying that users might already use it as for example
>> BB_VISITED and friends.  It converts one clever user to the new
>> interface.
>>
>> The allocation state is per CFG but we could also make it global
>> or merge the two pools so one allocates a flag that can be used for
>> bbs and edges at the same time.
>>
>> Thus - any opinions welcome.  I'm mainly targeting cfganal algorithms
>> where I want to add a few region-based ones that to be O(region-size)
>> complexity may not use sbitmaps for visited sets because of the
>> clearing
>> overhead and bitmaps are probably more expensive to use than a
>> BB/edge
>> flag that needs to be cleared afterwards.
>>
>> Built on x86_64, otherwise untested.
>>
>> Any comments?
> 
> Rather than putting alloc/free pairs at the usage sites, how about an
> RAII class?  Something like this:
Yes, please if at all possible we should be using RAII.

jeff

Re: [PATCH][RFC] Add dynamic edge/bb flag allocation

[David Malcolm]

On Fri, 2018-05-18 at 13:11 +0200, Richard Biener wrote:
> The following adds a simple alloc/free_flag machinery allocating
> bits from an int typed pool and applies that to bb->flags and edge-
> >flags.
> This should allow infrastructure pieces to use egde/bb flags
> temporarily
> without worrying that users might already use it as for example
> BB_VISITED and friends.  It converts one clever user to the new
> interface.
> 
> The allocation state is per CFG but we could also make it global
> or merge the two pools so one allocates a flag that can be used for
> bbs and edges at the same time.
> 
> Thus - any opinions welcome.  I'm mainly targeting cfganal algorithms
> where I want to add a few region-based ones that to be O(region-size)
> complexity may not use sbitmaps for visited sets because of the
> clearing
> overhead and bitmaps are probably more expensive to use than a
> BB/edge
> flag that needs to be cleared afterwards.
> 
> Built on x86_64, otherwise untested.
> 
> Any comments?

Rather than putting alloc/free pairs at the usage sites, how about an
RAII class?  Something like this:

class auto_edge_flag
{
public:
   auto_edge_flag (function *fun)
   : m_flag (alloc_edge_flag (fun)), m_fun (fun)
   {}

   ~auto_edge_flag ()
   {
  free_edge_flag (m_fun, m_flag);
   }

   operator int () const { return m_flag; }

private:
  int m_flag;
  function *m_fun;
};


> Templating the core flag allocator comes to my mind (up to max
> HOST_WIDE_INT) as well as moving the implementation elsewhere
> (hwi.h?).

Maybe wrap the data type up in a class?  Passing around an "int *"
seemed a bit low-level to me.  (But maybe that's me overthinking it)

[...snip...]

> diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
> index 8af793c6015..64ad42c83ca 100644
> --- a/gcc/cfgloop.c
> +++ b/gcc/cfgloop.c
> @@ -1539,6 +1539,7 @@ verify_loop_structure (void)
>/* Check irreducible loops.  */
>if (loops_state_satisfies_p
> (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
>  {
> +  int saved_irr_mask = alloc_edge_flag (cfun);

 auto_edge_flag saved_irr_mask (cfun);

[...snip...]


Dave