From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id ADB75385700C; Fri, 21 Apr 2023 11:26:04 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org ADB75385700C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682076364; bh=cgcC9ESEqGaJl0oRnRvPocMx/cMOD13LxiFO04P9jFw=; h=From:To:Subject:Date:From; b=uZCQaUBZbuRJYzNR5qHjwuGZQOb99xbv1HVmAWO1HFi90erzFQbT4cI77M7Ii4zkP eLooeS5wxCWv7pNioWMfUeI/HzcIjOdIrqPEFt4QhSwhVukKiuZCDqaDvH7q99tqFD wHtHeYJZPrUV9eb0b+6zRnYHm7SoPTCFYKUsB/Zg= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r14-136] change DF to use the proper CFG order for DF_FORWARD problems X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: d06e9264b0192c2c77e07d7fb0fe090efcb510c0 X-Git-Newrev: 94a04c24c33580179e51d3218f2edd2cf88cadcd Message-Id: <20230421112604.ADB75385700C@sourceware.org> Date: Fri, 21 Apr 2023 11:26:04 +0000 (GMT) List-Id: https://gcc.gnu.org/g:94a04c24c33580179e51d3218f2edd2cf88cadcd commit r14-136-g94a04c24c33580179e51d3218f2edd2cf88cadcd Author: Richard Biener 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 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 *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 *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 *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 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