From c34d53740af2d85e6f9bfbd1f7593aba0ea1cae4 Mon Sep 17 00:00:00 2001 From: Michael Hayes Date: Sun, 30 Jul 2000 10:35:03 +0000 Subject: [PATCH] basic-block.h (struct loops): New field rc_order. * basic-block.h (struct loops): New field rc_order. * flow.c (flow_loops_cfg_dump): Dump rc_order if computed. (flow_loops_free): Free rc_order. (flow_depth_first_order_compute): New parameter rc_order. (flow_loops_find): Allocate rc_order and swap usage with dfs_order. From-SVN: r35342 --- gcc/ChangeLog | 9 +++++++++ gcc/basic-block.h | 5 +++++ gcc/flow.c | 47 +++++++++++++++++++++++++++++++++++------------ 3 files changed, 49 insertions(+), 12 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 5935270..a90b9fc 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2000-07-25 Michael Hayes + + * basic-block.h (struct loops): New field rc_order. + * flow.c (flow_loops_cfg_dump): Dump rc_order if computed. + (flow_loops_free): Free rc_order. + (flow_depth_first_order_compute): New parameter rc_order. + (flow_loops_find): Allocate rc_order and swap usage with + dfs_order. + 2000-07-30 Herman A.J. ten Brugge Michael Hayes diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 633bdaf..084d56d 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -246,6 +246,7 @@ extern void tidy_fallthru_edge PARAMS ((edge, basic_block, /* Structure to hold information for each natural loop. */ struct loop { + /* Index into loops array. */ int num; /* Basic block of loop header. */ @@ -369,6 +370,10 @@ struct loops /* The ordering of the basic blocks in a depth first search. */ int *dfs_order; + + /* The reverse completion ordering of the basic blocks found in a + depth first search. */ + int *rc_order; } cfg; /* Headers shared by multiple loops that should be merged. */ diff --git a/gcc/flow.c b/gcc/flow.c index 7749d89..0d27ed9 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -397,7 +397,7 @@ static void flow_loops_cfg_dump PARAMS ((const struct loops *, FILE *)); static int flow_loop_nested_p PARAMS ((struct loop *, struct loop *)); static int flow_loop_exits_find PARAMS ((const sbitmap, edge **)); static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap)); -static int flow_depth_first_order_compute PARAMS ((int *)); +static int flow_depth_first_order_compute PARAMS ((int *, int *)); static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *)); static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *)); static void flow_loops_tree_build PARAMS ((struct loops *)); @@ -7070,6 +7070,14 @@ flow_loops_cfg_dump (loops, file) fprintf (file, "%d ", loops->cfg.dfs_order[i]); fputs ("\n", file); } + /* Dump the reverse completion node order. */ + if (loops->cfg.rc_order) + { + fputs (";; RC order: ", file); + for (i = 0; i < n_basic_blocks; i++) + fprintf (file, "%d ", loops->cfg.rc_order[i]); + fputs ("\n", file); + } } @@ -7135,7 +7143,8 @@ flow_loops_dump (loops, file, verbose) must be disjoint. */ disjoint = ! flow_loop_nested_p (smaller ? loop : oloop, smaller ? oloop : loop); - fprintf (file, ";; loop header %d shared by loops %d, %d %s\n", + fprintf (file, + ";; loop header %d shared by loops %d, %d %s\n", loop->header->index, i, j, disjoint ? "disjoint" : "nested"); } @@ -7307,16 +7316,20 @@ flow_loop_nodes_find (header, latch, nodes) /* Compute the depth first search order and store in the array - DFS_ORDER, marking the nodes visited in VISITED. Returns the - number of nodes visited. A depth first search tries to get as far - away from the starting point as quickly as possible. */ + DFS_ORDER if non-zero, marking the nodes visited in VISITED. If + RC_ORDER is non-zero, return the reverse completion number for each + node. Returns the number of nodes visited. A depth first search + tries to get as far away from the starting point as quickly as + possible. */ static int -flow_depth_first_order_compute (dfs_order) +flow_depth_first_order_compute (dfs_order, rc_order) int *dfs_order; + int *rc_order; { edge *stack; int sp; int dfsnum = 0; + int rcnum = n_basic_blocks - 1; sbitmap visited; /* Allocate stack for back-tracking up CFG. */ @@ -7348,6 +7361,9 @@ flow_depth_first_order_compute (dfs_order) { /* Mark that we have visited the destination. */ SET_BIT (visited, dest->index); + + if (dfs_order) + dfs_order[dfsnum++] = dest->index; if (dest->succ) { @@ -7358,8 +7374,9 @@ flow_depth_first_order_compute (dfs_order) else { /* There are no successors for the DEST node so assign - its DFS number. */ - dfs_order[n_basic_blocks - ++dfsnum] = dest->index; + its reverse completion number. */ + if (rc_order) + rc_order[rcnum--] = dest->index; } } else @@ -7367,8 +7384,9 @@ flow_depth_first_order_compute (dfs_order) if (! e->succ_next && src != ENTRY_BLOCK_PTR) { /* There are no more successors for the SRC node - so assign its DFS number. */ - dfs_order[n_basic_blocks - ++dfsnum] = src->index; + so assign its reverse completion number. */ + if (rc_order) + rc_order[rcnum--] = src->index; } if (e->succ_next) @@ -7557,11 +7575,13 @@ flow_loops_find (loops) sbitmap headers; sbitmap *dom; int *dfs_order; + int *rc_order; loops->num = 0; loops->array = NULL; loops->tree = NULL; dfs_order = NULL; + rc_order = NULL; /* Taking care of this degenerate case makes the rest of this code simpler. */ @@ -7602,7 +7622,8 @@ flow_loops_find (loops) /* Compute depth first search order of the CFG so that outer natural loops will be found before inner natural loops. */ dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int)); - flow_depth_first_order_compute (dfs_order); + rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int)); + flow_depth_first_order_compute (dfs_order, rc_order); /* Allocate loop structures. */ loops->array @@ -7623,7 +7644,7 @@ flow_loops_find (loops) /* Search the nodes of the CFG in DFS order that we can find outer loops first. */ - header = BASIC_BLOCK (dfs_order[b]); + header = BASIC_BLOCK (rc_order[b]); /* Look for all the possible latch blocks for this header. */ for (e = header->pred; e; e = e->pred_next) @@ -7645,6 +7666,7 @@ flow_loops_find (loops) loop->header = header; loop->latch = latch; + loop->num = num_loops; /* Keep track of blocks that are loop headers so that we can tell which loops should be merged. */ @@ -7696,6 +7718,7 @@ flow_loops_find (loops) /* Save CFG derived information to avoid recomputing it. */ loops->cfg.dom = dom; loops->cfg.dfs_order = dfs_order; + loops->cfg.rc_order = rc_order; /* Build the loop hierarchy tree. */ flow_loops_tree_build (loops); -- 2.7.4