From: tbsaunde+gcc@tbsaunde.org
To: gcc-patches@gcc.gnu.org
Subject: [PATCH 12/13] make depth_first_search_ds a class
Date: Tue, 09 May 2017 20:53:00 -0000 [thread overview]
Message-ID: <20170509205242.2237-13-tbsaunde+gcc@tbsaunde.org> (raw)
In-Reply-To: <20170509205242.2237-1-tbsaunde+gcc@tbsaunde.org>
From: Trevor Saunders <tbsaunde+gcc@tbsaunde.org>
gcc/ChangeLog:
2017-05-09 Trevor Saunders <tbsaunde+gcc@tbsaunde.org>
* cfganal.c (connect_infinite_loops_to_exit): Adjust.
(depth_first_search::depth_first_search): Change structure init
function to this constructor.
(depth_first_search::add_bb): Rename function to this member.
(depth_first_search::execute): Likewise.
(flow_dfs_compute_reverse_finish): Adjust.
---
gcc/cfganal.c | 96 +++++++++++++++++++++--------------------------------------
1 file changed, 34 insertions(+), 62 deletions(-)
diff --git a/gcc/cfganal.c b/gcc/cfganal.c
index 1b01564e8c7..27b453ca3f7 100644
--- a/gcc/cfganal.c
+++ b/gcc/cfganal.c
@@ -28,25 +28,24 @@ along with GCC; see the file COPYING3. If not see
#include "cfganal.h"
#include "cfgloop.h"
+namespace {
/* Store the data structures necessary for depth-first search. */
-struct depth_first_search_ds {
- /* stack for backtracking during the algorithm */
- basic_block *stack;
+class depth_first_search
+ {
+public:
+ depth_first_search ();
+
+ basic_block execute (basic_block);
+ void add_bb (basic_block);
- /* number of edges in the stack. That is, positions 0, ..., sp-1
- have edges. */
- unsigned int sp;
+private:
+ /* stack for backtracking during the algorithm */
+ auto_vec<basic_block, 20> m_stack;
/* record of basic blocks already seen by depth-first search */
- sbitmap visited_blocks;
+ auto_sbitmap m_visited_blocks;
};
-
-static void flow_dfs_compute_reverse_init (depth_first_search_ds *);
-static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds *,
- basic_block);
-static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds *,
- basic_block);
-static void flow_dfs_compute_reverse_finish (depth_first_search_ds *);
+}
\f
/* Mark the back edges in DFS traversal.
Return nonzero if a loop (natural or otherwise) is present.
@@ -597,30 +596,23 @@ add_noreturn_fake_exit_edges (void)
void
connect_infinite_loops_to_exit (void)
{
- basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
- basic_block deadend_block;
- depth_first_search_ds dfs_ds;
-
/* Perform depth-first search in the reverse graph to find nodes
reachable from the exit block. */
- flow_dfs_compute_reverse_init (&dfs_ds);
- flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR_FOR_FN (cfun));
+ depth_first_search dfs;
+ dfs.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
/* Repeatedly add fake edges, updating the unreachable nodes. */
+ basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
while (1)
{
- unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
- unvisited_block);
+ unvisited_block = dfs.execute (unvisited_block);
if (!unvisited_block)
break;
- deadend_block = dfs_find_deadend (unvisited_block);
+ basic_block deadend_block = dfs_find_deadend (unvisited_block);
make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
- flow_dfs_compute_reverse_add_bb (&dfs_ds, deadend_block);
+ dfs.add_bb (deadend_block);
}
-
- flow_dfs_compute_reverse_finish (&dfs_ds);
- return;
}
\f
/* Compute reverse top sort order. This is computing a post order
@@ -1094,31 +1086,22 @@ pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
search context. If INITIALIZE_STACK is nonzero, there is an
element on the stack. */
-static void
-flow_dfs_compute_reverse_init (depth_first_search_ds *data)
+depth_first_search::depth_first_search () :
+ m_stack (n_basic_blocks_for_fn (cfun)),
+ m_visited_blocks (last_basic_block_for_fn (cfun))
{
- /* Allocate stack for back-tracking up CFG. */
- data->stack = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
- data->sp = 0;
-
- /* Allocate bitmap to track nodes that have been visited. */
- data->visited_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
-
- /* None of the nodes in the CFG have been visited yet. */
- bitmap_clear (data->visited_blocks);
-
- return;
+ bitmap_clear (m_visited_blocks);
}
/* Add the specified basic block to the top of the dfs data
structures. When the search continues, it will start at the
block. */
-static void
-flow_dfs_compute_reverse_add_bb (depth_first_search_ds *data, basic_block bb)
+void
+depth_first_search::add_bb (basic_block bb)
{
- data->stack[data->sp++] = bb;
- bitmap_set_bit (data->visited_blocks, bb->index);
+ m_stack.quick_push (bb);
+ bitmap_set_bit (m_visited_blocks, bb->index);
}
/* Continue the depth-first search through the reverse graph starting with the
@@ -1126,42 +1109,31 @@ flow_dfs_compute_reverse_add_bb (depth_first_search_ds *data, basic_block bb)
are marked. Returns an unvisited basic block, or NULL if there is none
available. */
-static basic_block
-flow_dfs_compute_reverse_execute (depth_first_search_ds *data,
- basic_block last_unvisited)
+basic_block
+depth_first_search::execute (basic_block last_unvisited)
{
basic_block bb;
edge e;
edge_iterator ei;
- while (data->sp > 0)
+ while (!m_stack.is_empty ())
{
- bb = data->stack[--data->sp];
+ bb = m_stack.pop ();
/* Perform depth-first search on adjacent vertices. */
FOR_EACH_EDGE (e, ei, bb->preds)
- if (!bitmap_bit_p (data->visited_blocks, e->src->index))
- flow_dfs_compute_reverse_add_bb (data, e->src);
+ if (!bitmap_bit_p (m_visited_blocks, e->src->index))
+ add_bb (e->src);
}
/* Determine if there are unvisited basic blocks. */
FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
- if (!bitmap_bit_p (data->visited_blocks, bb->index))
+ if (!bitmap_bit_p (m_visited_blocks, bb->index))
return bb;
return NULL;
}
-/* Destroy the data structures needed for depth-first search on the
- reverse graph. */
-
-static void
-flow_dfs_compute_reverse_finish (depth_first_search_ds *data)
-{
- free (data->stack);
- sbitmap_free (data->visited_blocks);
-}
-
/* Performs dfs search from BB over vertices satisfying PREDICATE;
if REVERSE, go against direction of edges. Returns number of blocks
found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
--
2.11.0
next prev parent reply other threads:[~2017-05-09 20:53 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-05-09 20:53 [PATCH 00/13] misc data structure stuff tbsaunde+gcc
2017-05-09 20:53 ` [PATCH 13/13] make inverted_post_order_compute() operate on a vec tbsaunde+gcc
2017-05-10 8:44 ` Richard Biener
2017-05-09 20:53 ` [PATCH 09/13] use auto_bitmap more with alternate obstacks tbsaunde+gcc
2017-05-10 8:31 ` Richard Biener
2017-05-09 20:53 ` [PATCH 04/13] allow auto_bitmap to use other bitmap obstacks tbsaunde+gcc
2017-05-10 8:27 ` Richard Biener
2017-05-09 20:53 ` [PATCH 10/13] make a member an auto_sbitmap tbsaunde+gcc
2017-05-10 8:26 ` Richard Biener
2017-05-09 20:53 ` [PATCH 08/13] move several bitmaps from gc memory to the default obstack and use auto_bitmap tbsaunde+gcc
2017-05-10 8:26 ` Richard Biener
2017-05-09 20:53 ` [PATCH 07/13] use auto_bitmap more tbsaunde+gcc
2017-05-10 8:28 ` Richard Biener
2017-05-09 20:53 ` [PATCH 06/13] replace some manual stacks with auto_vec tbsaunde+gcc
2017-05-10 8:26 ` Richard Biener
2017-05-09 20:53 ` [PATCH 05/13] allow constructing a auto_vec with a preallocation, and a possibly larger actual allocation size tbsaunde+gcc
2017-05-10 6:58 ` Richard Sandiford
2017-05-11 7:50 ` Trevor Saunders
2017-05-11 8:18 ` Richard Biener
2017-05-11 8:23 ` Trevor Saunders
2017-05-11 9:04 ` Richard Sandiford
2017-05-09 20:53 ` [PATCH 03/13] store the bitmap_head within the auto_bitmap tbsaunde+gcc
2017-05-10 8:25 ` Richard Biener
2017-05-09 20:53 ` [PATCH 02/13] improve bitmap / sbitmap compatability of bitmap_set_bit tbsaunde+gcc
2017-05-10 6:54 ` Richard Sandiford
2017-05-11 8:01 ` Trevor Saunders
2017-05-09 20:53 ` [PATCH 01/13] improve safety of freeing bitmaps tbsaunde+gcc
2017-05-10 8:15 ` Richard Biener
2017-05-10 10:55 ` Trevor Saunders
2017-05-10 11:11 ` Richard Biener
2017-05-09 20:53 ` tbsaunde+gcc [this message]
2017-05-10 8:29 ` [PATCH 12/13] make depth_first_search_ds a class Richard Biener
2017-05-09 20:55 ` [PATCH 11/13] make more vars auto_sbitmaps tbsaunde+gcc
2017-05-10 8:27 ` Richard Biener
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20170509205242.2237-13-tbsaunde+gcc@tbsaunde.org \
--to=tbsaunde+gcc@tbsaunde.org \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).