From: Richard Biener <richard.guenther@gmail.com>
To: tbsaunde+gcc@tbsaunde.org
Cc: GCC Patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH 06/13] replace some manual stacks with auto_vec
Date: Wed, 10 May 2017 08:26:00 -0000 [thread overview]
Message-ID: <CAFiYyc1GkEh9qcqSS+-aTq8-L=FKcSvaGS_28DsQ3kmqO9dKeg@mail.gmail.com> (raw)
In-Reply-To: <20170509205242.2237-7-tbsaunde+gcc@tbsaunde.org>
On Tue, May 9, 2017 at 10:52 PM, <tbsaunde+gcc@tbsaunde.org> wrote:
> From: Trevor Saunders <tbsaunde+gcc@tbsaunde.org>
>
> gcc/ChangeLog:
Ok.
Richard.
> 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-10 8:25 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 06/13] replace some manual stacks with auto_vec tbsaunde+gcc
2017-05-10 8:26 ` Richard Biener [this message]
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 ` [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 09/13] use auto_bitmap more with alternate obstacks tbsaunde+gcc
2017-05-10 8:31 ` 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 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: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='CAFiYyc1GkEh9qcqSS+-aTq8-L=FKcSvaGS_28DsQ3kmqO9dKeg@mail.gmail.com' \
--to=richard.guenther@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=tbsaunde+gcc@tbsaunde.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).