public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r14-136] change DF to use the proper CFG order for DF_FORWARD problems
@ 2023-04-21 11:26 Richard Biener
0 siblings, 0 replies; only message in thread
From: Richard Biener @ 2023-04-21 11:26 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:94a04c24c33580179e51d3218f2edd2cf88cadcd
commit r14-136-g94a04c24c33580179e51d3218f2edd2cf88cadcd
Author: Richard Biener <rguenther@suse.de>
Date: Fri Apr 21 11:40:23 2023 +0200
change DF to use the proper CFG order for DF_FORWARD problems
This changes DF to use RPO on the forward graph for DF_FORWARD
problems. While that naturally maps to pre_and_rev_postorder_compute
we use the existing (wrong) CFG order for DF_BACKWARD problems
computed by post_order_compute since that provides the required
side-effect of deleting unreachable blocks.
The change requires turning the inconsistent vec<int> vs int * back
to consistent int *. A followup patch will change the
inverted_post_order_compute API and change the DF_BACKWARD problem
to use the correct RPO on the backward graph together with statistics
I produced last year for the combined effect.
* df.h (df_d::postorder_inverted): Change back to int *,
clarify comments.
* df-core.cc (rest_of_handle_df_finish): Adjust.
(df_analyze_1): Likewise.
(df_analyze): For DF_FORWARD problems use RPO on the forward
graph. Adjust.
(loop_inverted_post_order_compute): Adjust API.
(df_analyze_loop): Adjust.
(df_get_n_blocks): Likewise.
(df_get_postorder): Likewise.
Diff:
---
gcc/df-core.cc | 58 ++++++++++++++++++++++++++++++----------------------------
gcc/df.h | 8 ++++----
2 files changed, 34 insertions(+), 32 deletions(-)
diff --git a/gcc/df-core.cc b/gcc/df-core.cc
index de5cbd0c622..27123645da5 100644
--- a/gcc/df-core.cc
+++ b/gcc/df-core.cc
@@ -810,7 +810,7 @@ rest_of_handle_df_finish (void)
}
free (df->postorder);
- df->postorder_inverted.release ();
+ free (df->postorder_inverted);
free (df->hard_regs_live_count);
free (df);
df = NULL;
@@ -1207,9 +1207,6 @@ df_analyze_1 (void)
{
int i;
- /* These should be the same. */
- gcc_assert ((unsigned) df->n_blocks == df->postorder_inverted.length ());
-
/* We need to do this before the df_verify_all because this is
not kept incrementally up to date. */
df_compute_regs_ever_live (false);
@@ -1232,8 +1229,8 @@ df_analyze_1 (void)
if (dflow->problem->dir == DF_FORWARD)
df_analyze_problem (dflow,
df->blocks_to_analyze,
- df->postorder_inverted.address (),
- df->postorder_inverted.length ());
+ df->postorder_inverted,
+ df->n_blocks);
else
df_analyze_problem (dflow,
df->blocks_to_analyze,
@@ -1261,10 +1258,15 @@ df_analyze (void)
bitmap current_all_blocks = BITMAP_ALLOC (&df_bitmap_obstack);
free (df->postorder);
+ free (df->postorder_inverted);
df->postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
df->n_blocks = post_order_compute (df->postorder, true, true);
- df->postorder_inverted.truncate (0);
- inverted_post_order_compute (&df->postorder_inverted);
+ /* For DF_FORWARD use a RPO on the forward graph. Since we want to
+ have unreachable blocks deleted use post_order_compute and reverse
+ the order. */
+ df->postorder_inverted = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ for (int i = 0; i < df->n_blocks; ++i)
+ df->postorder_inverted[i] = df->postorder[df->n_blocks - 1 - i];
for (int i = 0; i < df->n_blocks; i++)
bitmap_set_bit (current_all_blocks, df->postorder[i]);
@@ -1273,7 +1275,7 @@ df_analyze (void)
{
/* Verify that POSTORDER_INVERTED only contains blocks reachable from
the ENTRY block. */
- for (unsigned int i = 0; i < df->postorder_inverted.length (); i++)
+ for (int i = 0; i < df->n_blocks; i++)
gcc_assert (bitmap_bit_p (current_all_blocks,
df->postorder_inverted[i]));
}
@@ -1283,12 +1285,11 @@ df_analyze (void)
if (df->analyze_subset)
{
bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
- df->n_blocks = df_prune_to_subcfg (df->postorder,
- df->n_blocks, df->blocks_to_analyze);
- unsigned int newlen = df_prune_to_subcfg (df->postorder_inverted.address (),
- df->postorder_inverted.length (),
- df->blocks_to_analyze);
- df->postorder_inverted.truncate (newlen);
+ unsigned int newlen = df_prune_to_subcfg (df->postorder, df->n_blocks,
+ df->blocks_to_analyze);
+ df_prune_to_subcfg (df->postorder_inverted, df->n_blocks,
+ df->blocks_to_analyze);
+ df->n_blocks = newlen;
BITMAP_FREE (current_all_blocks);
}
else
@@ -1364,14 +1365,13 @@ loop_post_order_compute (int *post_order, class loop *loop)
/* Compute the reverse top sort order of the inverted sub-CFG specified
by LOOP. Returns the number of blocks which is always loop->num_nodes. */
-static void
-loop_inverted_post_order_compute (vec<int> *post_order, class loop *loop)
+static int
+loop_inverted_post_order_compute (int *post_order, class loop *loop)
{
basic_block bb;
edge_iterator *stack;
int sp;
-
- post_order->reserve_exact (loop->num_nodes);
+ int post_order_num = 0;
/* Allocate stack for back-tracking up CFG. */
stack = XNEWVEC (edge_iterator, loop->num_nodes + 1);
@@ -1408,13 +1408,13 @@ loop_inverted_post_order_compute (vec<int> *post_order, class loop *loop)
time, check its predecessors. */
stack[sp++] = ei_start (pred->preds);
else
- post_order->quick_push (pred->index);
+ post_order[post_order_num++] = pred->index;
}
else
{
if (flow_bb_inside_loop_p (loop, bb)
&& ei_one_before_end_p (ei))
- post_order->quick_push (bb->index);
+ post_order[post_order_num++] = bb->index;
if (!ei_one_before_end_p (ei))
ei_next (&stack[sp - 1]);
@@ -1424,6 +1424,7 @@ loop_inverted_post_order_compute (vec<int> *post_order, class loop *loop)
}
free (stack);
+ return post_order_num;
}
@@ -1433,13 +1434,14 @@ void
df_analyze_loop (class loop *loop)
{
free (df->postorder);
+ free (df->postorder_inverted);
df->postorder = XNEWVEC (int, loop->num_nodes);
- df->postorder_inverted.truncate (0);
+ df->postorder_inverted = XNEWVEC (int, loop->num_nodes);
df->n_blocks = loop_post_order_compute (df->postorder, loop);
- loop_inverted_post_order_compute (&df->postorder_inverted, loop);
+ int n = loop_inverted_post_order_compute (df->postorder_inverted, loop);
gcc_assert ((unsigned) df->n_blocks == loop->num_nodes);
- gcc_assert (df->postorder_inverted.length () == loop->num_nodes);
+ gcc_assert ((unsigned) n == loop->num_nodes);
bitmap blocks = BITMAP_ALLOC (&df_bitmap_obstack);
for (int i = 0; i < df->n_blocks; ++i)
@@ -1460,8 +1462,8 @@ df_get_n_blocks (enum df_flow_dir dir)
if (dir == DF_FORWARD)
{
- gcc_assert (df->postorder_inverted.length ());
- return df->postorder_inverted.length ();
+ gcc_assert (df->postorder_inverted);
+ return df->n_blocks;
}
gcc_assert (df->postorder);
@@ -1480,8 +1482,8 @@ df_get_postorder (enum df_flow_dir dir)
if (dir == DF_FORWARD)
{
- gcc_assert (df->postorder_inverted.length ());
- return df->postorder_inverted.address ();
+ gcc_assert (df->postorder_inverted);
+ return df->postorder_inverted;
}
gcc_assert (df->postorder);
return df->postorder;
diff --git a/gcc/df.h b/gcc/df.h
index aec2223591a..402657a7076 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -581,10 +581,10 @@ public:
bitmap_head insns_to_delete;
bitmap_head insns_to_rescan;
bitmap_head insns_to_notes_rescan;
- int *postorder; /* The current set of basic blocks
- in reverse postorder. */
- vec<int> postorder_inverted; /* The current set of basic blocks
- in reverse postorder of inverted CFG. */
+ int *postorder; /* The current set of basic blocks in reverse
+ postorder for DF_BACKWARD problems. */
+ int *postorder_inverted; /* The current set of basic blocks in reverse
+ postorder for DF_FORWARD problems. */
int n_blocks; /* The number of blocks in reverse postorder. */
/* An array [FIRST_PSEUDO_REGISTER], indexed by regno, of the number
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2023-04-21 11:26 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-04-21 11:26 [gcc r14-136] change DF to use the proper CFG order for DF_FORWARD problems Richard Biener
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).