From: tbsaunde+gcc@tbsaunde.org
To: gcc-patches@gcc.gnu.org
Subject: [PATCH 06/13] replace some manual stacks with auto_vec
Date: Tue, 09 May 2017 20:53:00 -0000 [thread overview]
Message-ID: <20170509205242.2237-7-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 (mark_dfs_back_edges): Replace manual stack with
auto_vec.
(post_order_compute): Likewise.
(inverted_post_order_compute): Likewise.
(pre_and_rev_post_order_compute_fn): Likewise.
---
gcc/cfganal.c | 92 +++++++++++++++++++++++------------------------------------
1 file changed, 36 insertions(+), 56 deletions(-)
diff --git a/gcc/cfganal.c b/gcc/cfganal.c
index 7377a7a0434..1b01564e8c7 100644
--- a/gcc/cfganal.c
+++ b/gcc/cfganal.c
@@ -61,10 +61,8 @@ static void flow_dfs_compute_reverse_finish (depth_first_search_ds *);
bool
mark_dfs_back_edges (void)
{
- edge_iterator *stack;
int *pre;
int *post;
- int sp;
int prenum = 1;
int postnum = 1;
bool found = false;
@@ -74,8 +72,7 @@ mark_dfs_back_edges (void)
post = XCNEWVEC (int, last_basic_block_for_fn (cfun));
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
- sp = 0;
+ auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
/* Allocate bitmap to track nodes that have been visited. */
auto_sbitmap visited (last_basic_block_for_fn (cfun));
@@ -84,16 +81,15 @@ mark_dfs_back_edges (void)
bitmap_clear (visited);
/* Push the first edge on to the stack. */
- stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
+ stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
- while (sp)
+ while (!stack.is_empty ())
{
- edge_iterator ei;
basic_block src;
basic_block dest;
/* Look at the edge on the top of the stack. */
- ei = stack[sp - 1];
+ edge_iterator ei = stack.last ();
src = ei_edge (ei)->src;
dest = ei_edge (ei)->dest;
ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
@@ -110,7 +106,7 @@ mark_dfs_back_edges (void)
{
/* Since the DEST node has been visited for the first
time, check its successors. */
- stack[sp++] = ei_start (dest->succs);
+ stack.quick_push (ei_start (dest->succs));
}
else
post[dest->index] = postnum++;
@@ -128,15 +124,14 @@ mark_dfs_back_edges (void)
post[src->index] = postnum++;
if (!ei_one_before_end_p (ei))
- ei_next (&stack[sp - 1]);
+ ei_next (&stack.last ());
else
- sp--;
+ stack.pop ();
}
}
free (pre);
free (post);
- free (stack);
return found;
}
@@ -637,8 +632,6 @@ int
post_order_compute (int *post_order, bool include_entry_exit,
bool delete_unreachable)
{
- edge_iterator *stack;
- int sp;
int post_order_num = 0;
int count;
@@ -646,8 +639,7 @@ post_order_compute (int *post_order, bool include_entry_exit,
post_order[post_order_num++] = EXIT_BLOCK;
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
- sp = 0;
+ auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
/* Allocate bitmap to track nodes that have been visited. */
auto_sbitmap visited (last_basic_block_for_fn (cfun));
@@ -656,16 +648,15 @@ post_order_compute (int *post_order, bool include_entry_exit,
bitmap_clear (visited);
/* Push the first edge on to the stack. */
- stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
+ stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
- while (sp)
+ while (!stack.is_empty ())
{
- edge_iterator ei;
basic_block src;
basic_block dest;
/* Look at the edge on the top of the stack. */
- ei = stack[sp - 1];
+ edge_iterator ei = stack.last ();
src = ei_edge (ei)->src;
dest = ei_edge (ei)->dest;
@@ -679,7 +670,7 @@ post_order_compute (int *post_order, bool include_entry_exit,
if (EDGE_COUNT (dest->succs) > 0)
/* Since the DEST node has been visited for the first
time, check its successors. */
- stack[sp++] = ei_start (dest->succs);
+ stack.quick_push (ei_start (dest->succs));
else
post_order[post_order_num++] = dest->index;
}
@@ -690,9 +681,9 @@ post_order_compute (int *post_order, bool include_entry_exit,
post_order[post_order_num++] = src->index;
if (!ei_one_before_end_p (ei))
- ei_next (&stack[sp - 1]);
+ ei_next (&stack.last ());
else
- sp--;
+ stack.pop ();
}
}
@@ -722,7 +713,6 @@ post_order_compute (int *post_order, bool include_entry_exit,
tidy_fallthru_edges ();
}
- free (stack);
return post_order_num;
}
@@ -813,16 +803,13 @@ inverted_post_order_compute (int *post_order,
sbitmap *start_points)
{
basic_block bb;
- edge_iterator *stack;
- int sp;
int post_order_num = 0;
if (flag_checking)
verify_no_unreachable_blocks ();
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
- sp = 0;
+ auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
/* Allocate bitmap to track nodes that have been visited. */
auto_sbitmap visited (last_basic_block_for_fn (cfun));
@@ -836,12 +823,12 @@ inverted_post_order_compute (int *post_order,
if (bitmap_bit_p (*start_points, bb->index)
&& EDGE_COUNT (bb->preds) > 0)
{
- stack[sp++] = ei_start (bb->preds);
+ stack.quick_push (ei_start (bb->preds));
bitmap_set_bit (visited, bb->index);
}
if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds))
{
- stack[sp++] = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
+ stack.quick_push (ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds));
bitmap_set_bit (visited, EXIT_BLOCK_PTR_FOR_FN (cfun)->index);
}
}
@@ -853,7 +840,7 @@ inverted_post_order_compute (int *post_order,
/* Push the initial edge on to the stack. */
if (EDGE_COUNT (bb->preds) > 0)
{
- stack[sp++] = ei_start (bb->preds);
+ stack.quick_push (ei_start (bb->preds));
bitmap_set_bit (visited, bb->index);
}
}
@@ -863,13 +850,13 @@ inverted_post_order_compute (int *post_order,
bool has_unvisited_bb = false;
/* The inverted traversal loop. */
- while (sp)
+ while (!stack.is_empty ())
{
edge_iterator ei;
basic_block pred;
/* Look at the edge on the top of the stack. */
- ei = stack[sp - 1];
+ ei = stack.last ();
bb = ei_edge (ei)->dest;
pred = ei_edge (ei)->src;
@@ -882,7 +869,7 @@ inverted_post_order_compute (int *post_order,
if (EDGE_COUNT (pred->preds) > 0)
/* Since the predecessor node has been visited for the first
time, check its predecessors. */
- stack[sp++] = ei_start (pred->preds);
+ stack.quick_push (ei_start (pred->preds));
else
post_order[post_order_num++] = pred->index;
}
@@ -893,15 +880,15 @@ inverted_post_order_compute (int *post_order,
post_order[post_order_num++] = bb->index;
if (!ei_one_before_end_p (ei))
- ei_next (&stack[sp - 1]);
+ ei_next (&stack.last ());
else
- sp--;
+ stack.pop ();
}
}
/* Detect any infinite loop and activate the kludge.
Note that this doesn't check EXIT_BLOCK itself
- since EXIT_BLOCK is always added after the outer do-while loop. */
+ since EXIT_BLOCK is always added after the outer do-while loop. */
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
if (!bitmap_bit_p (visited, bb->index))
@@ -926,31 +913,30 @@ inverted_post_order_compute (int *post_order,
basic_block be = dfs_find_deadend (bb);
gcc_assert (be != NULL);
bitmap_set_bit (visited, be->index);
- stack[sp++] = ei_start (be->preds);
+ stack.quick_push (ei_start (be->preds));
break;
}
}
}
- if (has_unvisited_bb && sp == 0)
+ if (has_unvisited_bb && stack.is_empty ())
{
- /* No blocks are reachable from EXIT at all.
+ /* No blocks are reachable from EXIT at all.
Find a dead-end from the ENTRY, and restart the iteration. */
basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun));
gcc_assert (be != NULL);
bitmap_set_bit (visited, be->index);
- stack[sp++] = ei_start (be->preds);
+ stack.quick_push (ei_start (be->preds));
}
/* The only case the below while fires is
when there's an infinite loop. */
}
- while (sp);
+ while (!stack.is_empty ());
/* EXIT_BLOCK is always included. */
post_order[post_order_num++] = EXIT_BLOCK;
- free (stack);
return post_order_num;
}
@@ -971,14 +957,11 @@ pre_and_rev_post_order_compute_fn (struct function *fn,
int *pre_order, int *rev_post_order,
bool include_entry_exit)
{
- edge_iterator *stack;
- int sp;
int pre_order_num = 0;
int rev_post_order_num = n_basic_blocks_for_fn (cfun) - 1;
/* Allocate stack for back-tracking up CFG. */
- stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
- sp = 0;
+ auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
if (include_entry_exit)
{
@@ -998,16 +981,15 @@ pre_and_rev_post_order_compute_fn (struct function *fn,
bitmap_clear (visited);
/* Push the first edge on to the stack. */
- stack[sp++] = ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs);
+ stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs));
- while (sp)
+ while (!stack.is_empty ())
{
- edge_iterator ei;
basic_block src;
basic_block dest;
/* Look at the edge on the top of the stack. */
- ei = stack[sp - 1];
+ edge_iterator ei = stack.last ();
src = ei_edge (ei)->src;
dest = ei_edge (ei)->dest;
@@ -1026,7 +1008,7 @@ pre_and_rev_post_order_compute_fn (struct function *fn,
if (EDGE_COUNT (dest->succs) > 0)
/* Since the DEST node has been visited for the first
time, check its successors. */
- stack[sp++] = ei_start (dest->succs);
+ stack.quick_push (ei_start (dest->succs));
else if (rev_post_order)
/* There are no successors for the DEST node so assign
its reverse completion number. */
@@ -1042,14 +1024,12 @@ pre_and_rev_post_order_compute_fn (struct function *fn,
rev_post_order[rev_post_order_num--] = src->index;
if (!ei_one_before_end_p (ei))
- ei_next (&stack[sp - 1]);
+ ei_next (&stack.last ());
else
- sp--;
+ stack.pop ();
}
}
- free (stack);
-
if (include_entry_exit)
{
if (pre_order)
--
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 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 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 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 ` [PATCH 12/13] make depth_first_search_ds a class tbsaunde+gcc
2017-05-10 8:29 ` 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 ` tbsaunde+gcc [this message]
2017-05-10 8:26 ` [PATCH 06/13] replace some manual stacks with auto_vec Richard Biener
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: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-7-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).