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?
Templating the core flag allocator comes to my mind (up to max
HOST_WIDE_INT) as well as moving the implementation elsewhere (hwi.h?).
Thanks,
Richard.
>From 739d8f202a161b4714cad8b19844ae5fa7924118 Mon Sep 17 00:00:00 2001
From: Richard Guenther <rguent...@suse.de>
Date: Fri, 18 May 2018 13:01:36 +0200
Subject: [PATCH 4/4] add dynamic cfg flag allocation
* cfg.h (struct control_flow_graph): Add edge_flags_allocated and
bb_flags_allocated members.
(alloc_flag): Declare.
(free_flag): Likewise.
(alloc_bb_flag): New inline function.
(alloc_edge_flag): Likewise.
(free_bb_flag): Likewise.
(free_edge_flag): Likewise.
* cfg.c (alloc_flag): New function.
(free_flag): Likewise.
(init_flow): Mark static bb and edge flag allocated.
* cfgloop.c (verify_loop_structure): Allocate temporary edge
flag dynamically.
diff --git a/gcc/cfg.c b/gcc/cfg.c
index 11026e7209a..30fc417d28f 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
@@ -1167,3 +1169,26 @@ get_loop_copy (struct loop *loop)
else
return NULL;
}
+
+/* Allocate a bit from *POOL and return a corresponding mask. */
+
+int
+alloc_flag (int *pool)
+{
+ int bitnum = clz_hwi (*pool);
+ /* out of bits */
+ gcc_assert (bitnum != 0);
+ int mask = 1 << (HOST_BITS_PER_INT - bitnum);
+ gcc_assert ((*pool & mask) == 0);
+ *pool |= mask;
+ return mask;
+}
+
+/* Release a bit with MASK to *POOL. */
+
+void
+free_flag (int *pool, int mask)
+{
+ gcc_assert (popcount_hwi (mask) == 1 && (*pool & mask) == mask);
+ *pool &= ~mask;
+}
diff --git a/gcc/cfg.h b/gcc/cfg.h
index 0953456782b..23b02346751 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,28 @@ extern basic_block get_bb_copy (basic_block);
void set_loop_copy (struct loop *, struct loop *);
struct loop *get_loop_copy (struct loop *);
+extern int alloc_flag (int *);
+extern void free_flag (int *, int);
+
+inline int
+alloc_edge_flag (struct function *fn)
+{
+ return alloc_flag (&fn->cfg->edge_flags_allocated);
+}
+inline int
+alloc_bb_flag (struct function *fn)
+{
+ return alloc_flag (&fn->cfg->bb_flags_allocated);
+}
+inline void
+free_edge_flag (struct function *fn, int mask)
+{
+ free_flag (&fn->cfg->edge_flags_allocated, mask);
+}
+inline void
+free_bb_flag (struct function *fn, int mask)
+{
+ free_flag (&fn->cfg->bb_flags_allocated, mask);
+}
+
#endif /* GCC_CFG_H */
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);
/* 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,22 +1577,23 @@ 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",
e->src->index, e->dest->index);
err = 1;
}
- e->flags &= ~(EDGE_ALL_FLAGS + 1);
+ e->flags &= ~saved_irr_mask;
}
}
+ free_edge_flag (cfun, saved_irr_mask);
}
/* Check the recorded loop exits. */
diff --git a/gcc/hsa-brig.c b/gcc/hsa-brig.c
index d3efff40453..ca066118ebd 100644
--- a/gcc/hsa-brig.c
+++ b/gcc/hsa-brig.c
@@ -35,8 +35,8 @@ along with GCC; see the file COPYING3. If not see
#include "stor-layout.h"
#include "output.h"
#include "basic-block.h"
-#include "cfg.h"
#include "function.h"
+#include "cfg.h"
#include "fold-const.h"
#include "stringpool.h"
#include "gimple-pretty-print.h"
diff --git a/gcc/hsa-dump.c b/gcc/hsa-dump.c
index 4ee53c81277..77fef5ee5d8 100644
--- a/gcc/hsa-dump.c
+++ b/gcc/hsa-dump.c
@@ -27,8 +27,8 @@ along with GCC; see the file COPYING3. If not see
#include "vec.h"
#include "tree.h"
#include "basic-block.h"
-#include "cfg.h"
#include "function.h"
+#include "cfg.h"
#include "dumpfile.h"
#include "gimple-pretty-print.h"
#include "cgraph.h"
diff --git a/gcc/hsa-regalloc.c b/gcc/hsa-regalloc.c
index f402587408d..819f680d1bc 100644
--- a/gcc/hsa-regalloc.c
+++ b/gcc/hsa-regalloc.c
@@ -27,9 +27,9 @@ along with GCC; see the file COPYING3. If not see
#include "tree.h"
#include "dominance.h"
#include "basic-block.h"
-#include "cfg.h"
-#include "cfganal.h"
#include "function.h"
+#include "cfganal.h"
+#include "cfg.h"
#include "bitmap.h"
#include "dumpfile.h"
#include "cgraph.h"
diff --git a/gcc/print-rtl.c b/gcc/print-rtl.c
index 37c0d53fae2..ba7aa260194 100644
--- a/gcc/print-rtl.c
+++ b/gcc/print-rtl.c
@@ -36,11 +36,11 @@ along with GCC; see the file COPYING3. If not see
#include "alias.h"
#include "tree.h"
#include "basic-block.h"
-#include "cfg.h"
#include "print-tree.h"
#include "flags.h"
#include "predict.h"
#include "function.h"
+#include "cfg.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "tree-pretty-print.h"
diff --git a/gcc/profile-count.c b/gcc/profile-count.c
index 3d411cfbfb3..3745ae073c8 100644
--- a/gcc/profile-count.c
+++ b/gcc/profile-count.c
@@ -25,8 +25,8 @@ along with GCC; see the file COPYING3. If not see
#include "options.h"
#include "tree.h"
#include "basic-block.h"
-#include "cfg.h"
#include "function.h"
+#include "cfg.h"
#include "gimple.h"
#include "data-streamer.h"
#include "cgraph.h"
--
2.12.3
