From 135ebc3673ad7f952d7a2911b4ee9945855fa3ad Mon Sep 17 00:00:00 2001 From: Michael Hayes Date: Fri, 25 Aug 2000 10:20:22 +0000 Subject: [PATCH] basic-block.h (struct loop): Rename `exits' field to `exit_edges'. * basic-block.h (struct loop): Rename `exits' field to `exit_edges'. Add `entry_edges' and `num_entries' fields. * flow.c (flow_loop_exit_edges_find): Rename from flow_loop_exits_find. (flow_loop_entry_edges_find): Add. (flow_edge_list_print): Rename from flow_exits_print. (flow_loops_find): Call flow_loop_entry_edges_find. (flow_loop_dump): Dump entry_edges list. (flow_loops_free): Free entry_edges. From-SVN: r35980 --- gcc/ChangeLog | 12 +++++ gcc/basic-block.h | 8 ++- gcc/flow.c | 128 +++++++++++++++++++++++++++++++++++----------- 3 files changed, 118 insertions(+), 30 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index a48284ea4e8..e4b4d6e92f6 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,17 @@ 2000-08-26 Michael Hayes + * basic-block.h (struct loop): Rename `exits' field to + `exit_edges'. Add `entry_edges' and `num_entries' fields. + + * flow.c (flow_loop_exit_edges_find): Rename from flow_loop_exits_find. + (flow_loop_entry_edges_find): Add. + (flow_edge_list_print): Rename from flow_exits_print. + (flow_loops_find): Call flow_loop_entry_edges_find. + (flow_loop_dump): Dump entry_edges list. + (flow_loops_free): Free entry_edges. + +2000-08-26 Michael Hayes + * loop.c (loop_dump_aux, debug_loop): New functions. (LOOP_BLOCK_NUM_1, LOOP_BLOCK_NUM, LOOP_INSN_UID): New macros. diff --git a/gcc/basic-block.h b/gcc/basic-block.h index a6533245a8f..7e11ed5e5ec 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -288,8 +288,14 @@ struct loop /* Number of blocks contained within the loop. */ int num_nodes; + /* Array of edges that enter the loop. */ + edge *entry_edges; + + /* Number of edges that enter the loop. */ + int num_entries; + /* Array of edges that exit the loop. */ - edge *exits; + edge *exit_edges; /* Number of edges that exit the loop. */ int num_exits; diff --git a/gcc/flow.c b/gcc/flow.c index 4e7e756486c..a3597a26724 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -411,11 +411,17 @@ static void dump_edge_info PARAMS ((FILE *, edge, int)); static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *, rtx)); static void remove_fake_successors PARAMS ((basic_block)); -static void flow_nodes_print PARAMS ((const char *, const sbitmap, FILE *)); -static void flow_exits_print PARAMS ((const char *, const edge *, int, FILE *)); -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 void flow_nodes_print PARAMS ((const char *, const sbitmap, + FILE *)); +static void flow_edge_list_print PARAMS ((const char *, const edge *, + int, FILE *)); +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_entry_edges_find PARAMS ((basic_block, const sbitmap, + edge **)); +static int flow_loop_exit_edges_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 *, int *)); static void flow_dfs_compute_reverse_init @@ -7119,7 +7125,7 @@ redirect_edge_pred (e, new_pred) /* Dump the list of basic blocks in the bitmap NODES. */ -static void +static void flow_nodes_print (str, nodes, file) const char *str; const sbitmap nodes; @@ -7127,28 +7133,37 @@ flow_nodes_print (str, nodes, file) { int node; + if (! nodes) + return; + fprintf (file, "%s { ", str); EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);}); fputs ("}\n", file); } -/* Dump the list of exiting edges in the array EDGES. */ -static void -flow_exits_print (str, edges, num_edges, file) +/* Dump the list of edges in the array EDGE_LIST. */ + +static void +flow_edge_list_print (str, edge_list, num_edges, file) const char *str; - const edge *edges; + const edge *edge_list; int num_edges; FILE *file; { int i; + if (! edge_list) + return; + fprintf (file, "%s { ", str); for (i = 0; i < num_edges; i++) - fprintf (file, "%d->%d ", edges[i]->src->index, edges[i]->dest->index); + fprintf (file, "%d->%d ", edge_list[i]->src->index, + edge_list[i]->dest->index); fputs ("}\n", file); } + /* Dump loop related CFG information. */ static void @@ -7225,10 +7240,12 @@ flow_loop_dump (loop, file, loop_dump_aux, verbose) loop->depth, loop->level, (long) (loop->outer ? loop->outer->num : -1)); + flow_edge_list_print (";; entry edges", loop->entry_edges, + loop->num_entries, file); fprintf (file, ";; %d", loop->num_nodes); flow_nodes_print (" nodes", loop->nodes, file); - fprintf (file, ";; %d", loop->num_exits); - flow_exits_print (" exits", loop->exits, loop->num_exits, file); + flow_edge_list_print (";; exit edges", loop->exit_edges, + loop->num_exits, file); if (loop_dump_aux) loop_dump_aux (loop, file, verbose); @@ -7314,8 +7331,10 @@ flow_loops_free (loops) if (loop->nodes) sbitmap_free (loop->nodes); - if (loop->exits) - free (loop->exits); + if (loop->entry_edges) + free (loop->entry_edges); + if (loop->exit_edges) + free (loop->exit_edges); } free (loops->array); loops->array = NULL; @@ -7330,29 +7349,72 @@ flow_loops_free (loops) } -/* Find the exits from the loop using the bitmap of loop nodes NODES - and store in EXITS array. Return the number of exits from the - loop. */ +/* Find the entry edges into the loop with header HEADER and nodes + NODES and store in ENTRY_EDGES array. Return the number of entry + edges from the loop. */ + +static int +flow_loop_entry_edges_find (header, nodes, entry_edges) + basic_block header; + const sbitmap nodes; + edge **entry_edges; +{ + edge e; + int num_entries; + + *entry_edges = NULL; + + num_entries = 0; + for (e = header->pred; e; e = e->pred_next) + { + basic_block src = e->src; + + if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index)) + num_entries++; + } + + if (! num_entries) + abort (); + + *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *)); + + num_entries = 0; + for (e = header->pred; e; e = e->pred_next) + { + basic_block src = e->src; + + if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index)) + (*entry_edges)[num_entries++] = e; + } + + return num_entries; +} + + +/* Find the exit edges from the loop using the bitmap of loop nodes + NODES and store in EXIT_EDGES array. Return the number of + exit edges from the loop. */ static int -flow_loop_exits_find (nodes, exits) +flow_loop_exit_edges_find (nodes, exit_edges) const sbitmap nodes; - edge **exits; + edge **exit_edges; { edge e; int node; int num_exits; - *exits = NULL; + *exit_edges = NULL; /* Check all nodes within the loop to see if there are any successors not in the loop. Note that a node may have multiple - exiting edges. */ + exiting edges ????? A node can have one jumping edge and one fallthru + edge so only one of these can exit the loop. */ num_exits = 0; EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, { for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next) { - basic_block dest = e->dest; + basic_block dest = e->dest; if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) num_exits++; @@ -7362,23 +7424,24 @@ flow_loop_exits_find (nodes, exits) if (! num_exits) return 0; - *exits = (edge *) xmalloc (num_exits * sizeof (edge *)); + *exit_edges = (edge *) xmalloc (num_exits * sizeof (edge *)); /* Store all exiting edges into an array. */ num_exits = 0; EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, { for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next) { - basic_block dest = e->dest; + basic_block dest = e->dest; if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) - (*exits)[num_exits++] = e; + (*exit_edges)[num_exits++] = e; } }); return num_exits; } + /* Find the nodes contained within the loop with header HEADER and latch LATCH and store in NODES. Return the number of nodes within the loop. */ @@ -7918,10 +7981,17 @@ flow_loops_find (loops) loop->last = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes)); - /* Find edges which exit the loop. Note that a node - may have several exit edges. */ + /* Find edges which enter the loop header. + Note that the entry edges should only + enter the header of a natural loop. */ + loop->num_entries + = flow_loop_entry_edges_find (loop->header, loop->nodes, + &loop->entry_edges); + + /* Find edges which exit the loop. */ loop->num_exits - = flow_loop_exits_find (loop->nodes, &loop->exits); + = flow_loop_exit_edges_find (loop->nodes, + &loop->exit_edges); /* Look to see if the loop has a pre-header node. */ loop->pre_header = flow_loop_pre_header_find (header, dom); -- 2.30.2