From 2f95707a4f249cd7eb5435d499adbf58a68d1916 Mon Sep 17 00:00:00 2001 From: dberlin Date: Tue, 28 Aug 2001 23:43:23 +0000 Subject: [PATCH] 2001-08-28 Daniel Berlin * df.h (struct df): Add rts_order variable. * df.c (df_visit_next_rts): New function. (df_visit_next): Renamed to df_visit_next_rc (df_analyse_1): Allocate/compute/free rts_order as well. (df_rd_global_compute): Use df_visit_next_rc instead of df_visit_next. (df_ru_global_compute): Use df_visit_next_rts instead of df_visit_next. * flow.c (flow_reverse_top_sort_order_compute): New function. * basic-block.h: Add prototype. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@45246 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 16 ++++++++++++++ gcc/basic-block.h | 1 + gcc/df.c | 31 +++++++++++++++++++++----- gcc/df.h | 1 + gcc/flow.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 108 insertions(+), 6 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7ecd770..648b5f5 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,21 @@ 2001-08-28 Daniel Berlin + * df.h (struct df): Add rts_order variable. + + * df.c (df_visit_next_rts): New function. + (df_visit_next): Renamed to df_visit_next_rc + (df_analyse_1): Allocate/compute/free rts_order as well. + (df_rd_global_compute): Use df_visit_next_rc instead of + df_visit_next. + (df_ru_global_compute): Use df_visit_next_rts instead of + df_visit_next. + + * flow.c (flow_reverse_top_sort_order_compute): New function. + + * basic-block.h: Add prototype. + +2001-08-28 Daniel Berlin + * ssa-ccp.c (ssa_ccp_df_delete_unreachable_insns): For unreachable blocks, the BB_REACHABLE is now set, rather than aux being non-NULL. Update the test to reflect this. diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 295748b..b875494 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -310,6 +310,7 @@ extern int flow_delete_block PARAMS ((basic_block)); extern void merge_blocks_nomove PARAMS ((basic_block, basic_block)); extern void tidy_fallthru_edge PARAMS ((edge, basic_block, basic_block)); +extern void flow_reverse_top_sort_order_compute PARAMS ((int *)); extern int flow_depth_first_order_compute PARAMS ((int *, int *)); extern void dump_edge_info PARAMS ((FILE *, edge, int)); extern void clear_edges PARAMS ((void)); diff --git a/gcc/df.c b/gcc/df.c index 6f1b18f..177da10 100644 --- a/gcc/df.c +++ b/gcc/df.c @@ -238,7 +238,8 @@ static void df_insn_refs_record PARAMS((struct df *, basic_block, rtx)); static void df_bb_refs_record PARAMS((struct df *, basic_block)); static void df_refs_record PARAMS((struct df *, bitmap)); -static int df_visit_next PARAMS ((struct df *, sbitmap)); +static int df_visit_next_rc PARAMS ((struct df *, sbitmap)); +static int df_visit_next_rts PARAMS ((struct df *, sbitmap)); static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block)); static void df_reg_def_chain_create PARAMS((struct df *, bitmap)); static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block)); @@ -1600,11 +1601,11 @@ df_ud_chain_create (df, blocks) } -/* Use depth first order, and the worklist, to figure out what block +/* Use reverse completion order, and the worklist, to figure out what block to look at next. */ static int -df_visit_next (df, blocks) +df_visit_next_rc (df, blocks) struct df *df ATTRIBUTE_UNUSED; sbitmap blocks; { @@ -1615,6 +1616,22 @@ df_visit_next (df, blocks) return sbitmap_first_set_bit (blocks); } +/* Use reverse topsort order, and the worklist, to figure out what block + to look at next. */ + +static int +df_visit_next_rts (df, blocks) + struct df *df ATTRIBUTE_UNUSED; + sbitmap blocks; +{ + int i=0; + for (i = 0; i < n_basic_blocks; i++) + if (TEST_BIT (blocks, df->rts_order[i])) + return df->rts_order[i]; + return sbitmap_first_set_bit (blocks); +} + + /* Calculate reaching defs for each basic block in BLOCKS, i.e., the defs that are live at the start of a basic block. */ static void @@ -1644,7 +1661,7 @@ df_rd_global_compute (df, blocks) bitmap_copy (bb_info->rd_out, bb_info->rd_gen); }); - while ((i = df_visit_next (df, worklist)) >= 0) + while ((i = df_visit_next_rc (df, worklist)) >= 0) { struct bb_info *bb_info; edge e; @@ -1722,7 +1739,7 @@ df_ru_global_compute (df, blocks) }); - while ((i = df_visit_next (df, worklist)) >= 0) + while ((i = df_visit_next_rts (df, worklist)) >= 0) { struct bb_info *bb_info; edge e; @@ -2221,9 +2238,10 @@ df_analyse_1 (df, blocks, flags, update) df->dfs_order = xmalloc (sizeof(int) * n_basic_blocks); df->rc_order = xmalloc (sizeof(int) * n_basic_blocks); + df->rts_order = xmalloc (sizeof(int) * n_basic_blocks); flow_depth_first_order_compute (df->dfs_order, df->rc_order); - + flow_reverse_top_sort_order_compute (df->rts_order); if (aflags & DF_RD) { /* Compute the sets of gens and kills for the defs of each bb. */ @@ -2280,6 +2298,7 @@ df_analyse_1 (df, blocks, flags, update) } free (df->dfs_order); free (df->rc_order); + free (df->rts_order); } diff --git a/gcc/df.h b/gcc/df.h index 3169e3f..c550afa 100644 --- a/gcc/df.h +++ b/gcc/df.h @@ -140,6 +140,7 @@ struct df bitmap *dom; int * dfs_order; int * rc_order; + int * rts_order; }; diff --git a/gcc/flow.c b/gcc/flow.c index d2f37e5..8ca0877 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -9466,6 +9466,71 @@ flow_loop_nodes_find (header, latch, nodes) return num_nodes; } +/* Compute reverse top sort order */ +void +flow_reverse_top_sort_order_compute (rts_order) + int *rts_order; +{ + edge *stack; + int sp; + int postnum = 0; + sbitmap visited; + + /* Allocate stack for back-tracking up CFG. */ + stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); + sp = 0; + + /* Allocate bitmap to track nodes that have been visited. */ + visited = sbitmap_alloc (n_basic_blocks); + + /* None of the nodes in the CFG have been visited yet. */ + sbitmap_zero (visited); + + /* Push the first edge on to the stack. */ + stack[sp++] = ENTRY_BLOCK_PTR->succ; + + while (sp) + { + edge e; + basic_block src; + basic_block dest; + + /* Look at the edge on the top of the stack. */ + e = stack[sp - 1]; + src = e->src; + dest = e->dest; + + /* Check if the edge destination has been visited yet. */ + if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) + { + /* Mark that we have visited the destination. */ + SET_BIT (visited, dest->index); + + if (dest->succ) + { + /* Since the DEST node has been visited for the first + time, check its successors. */ + stack[sp++] = dest->succ; + } + else + rts_order[postnum++] = dest->index; + } + else + { + if (! e->succ_next && src != ENTRY_BLOCK_PTR) + rts_order[postnum++] = src->index; + + if (e->succ_next) + stack[sp - 1] = e->succ_next; + else + sp--; + } + } + + free (stack); + sbitmap_free (visited); +} + /* Compute the depth first search order and store in the array DFS_ORDER if non-zero, marking the nodes visited in VISITED. If RC_ORDER is non-zero, return the reverse completion number for each -- 2.7.4