From 4dc9341c04ba95ac73093573f645b49dcff494bf Mon Sep 17 00:00:00 2001 From: Michael Hayes Date: Tue, 30 Nov 1999 10:42:29 +0000 Subject: [PATCH] flow.c (flow_nodes_print, [...]): New functions. * flow.c (flow_nodes_print, flow_loops_cfg_dump): New functions. (flow_loop_nested_p, flow_loops_dump, flow_loops_free): Likewise. (flow_loop_exits_find, flow_loop_nodes_find): Likewise. (flow_depth_first_order_compute, flow_loop_pre_header_find): Likewise. (flow_loop_tree_node_add, flow_loops_tree_build): Likewise. (flow_loop_level_compute, low_loops_level_compute): Likewise. (flow_loops_find, flow_loop_outside_edge_p): Likewise. * basic-block.h: Protect from multiple inclusion. (flow_loops_find, flow_loops_free, flow_loop_dump): Add protoypes. (struct loops, struct loop): Define structures. * sbitmap.c (sbitmap_a_subset_b_p): New function. * sbitmap.h: Protect from multiple inclusion. (sbitmap_a_subset_b_p): Add prototype. * Makefile.in (LOOP_H): New macro. (stmt.o, integrate.o, loop.o, unroll.o): Replace loop.h with LOOP_H. From-SVN: r30720 --- gcc/ChangeLog | 18 ++ gcc/Makefile.in | 9 +- gcc/basic-block.h | 90 ++++++ gcc/flow.c | 681 ++++++++++++++++++++++++++++++++++++++++++++++ gcc/sbitmap.c | 19 ++ gcc/sbitmap.h | 5 + 6 files changed, 818 insertions(+), 4 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index dff51d3d83e2..facaadc56981 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,21 @@ +1999-11-30 Michael Hayes + + * flow.c (flow_nodes_print, flow_loops_cfg_dump): New functions. + (flow_loop_nested_p, flow_loops_dump, flow_loops_free): Likewise. + (flow_loop_exits_find, flow_loop_nodes_find): Likewise. + (flow_depth_first_order_compute, flow_loop_pre_header_find): Likewise. + (flow_loop_tree_node_add, flow_loops_tree_build): Likewise. + (flow_loop_level_compute, low_loops_level_compute): Likewise. + (flow_loops_find, flow_loop_outside_edge_p): Likewise. + * basic-block.h: Protect from multiple inclusion. + (flow_loops_find, flow_loops_free, flow_loop_dump): Add protoypes. + (struct loops, struct loop): Define structures. + * sbitmap.c (sbitmap_a_subset_b_p): New function. + * sbitmap.h: Protect from multiple inclusion. + (sbitmap_a_subset_b_p): Add prototype. + * Makefile.in (LOOP_H): New macro. + (stmt.o, integrate.o, loop.o, unroll.o): Replace loop.h with LOOP_H. + Tue Nov 30 01:34:47 1999 Philippe De Muyter * cppinit.c (CAT): The argument list of this macro may not contain diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 17a6a2bfef17..61144c4f14cc 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -748,6 +748,7 @@ DEMANGLE_H = $(srcdir)/../include/demangle.h RECOG_H = recog.h EXPR_H = expr.h insn-codes.h REGS_H = regs.h varray.h $(MACHMODE_H) +LOOP_H = loop.h varray.h # # Language makefile fragments. @@ -1484,7 +1485,7 @@ function.o : function.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \ insn-config.h $(RECOG_H) output.h toplev.h except.h hash.h ggc.h stmt.o : stmt.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h function.h \ insn-flags.h insn-config.h insn-codes.h hard-reg-set.h $(EXPR_H) except.h \ - loop.h $(RECOG_H) toplev.h output.h varray.h ggc.h + $(LOOP_H) $(RECOG_H) toplev.h output.h varray.h ggc.h except.o : except.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \ function.h insn-flags.h $(EXPR_H) $(REGS_H) hard-reg-set.h \ insn-config.h $(RECOG_H) output.h except.h toplev.h intl.h ggc.h @@ -1527,7 +1528,7 @@ emit-rtl.o : emit-rtl.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \ real.o : real.c $(CONFIG_H) system.h $(TREE_H) toplev.h integrate.o : integrate.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \ integrate.h insn-flags.h insn-config.h $(EXPR_H) real.h $(REGS_H) \ - intl.h function.h output.h $(RECOG_H) except.h toplev.h loop.h + intl.h function.h output.h $(RECOG_H) except.h toplev.h $(LOOP_H) jump.o : jump.c $(CONFIG_H) system.h $(RTL_H) flags.h hard-reg-set.h $(REGS_H) \ insn-config.h insn-flags.h $(RECOG_H) $(EXPR_H) real.h except.h function.h \ toplev.h insn-attr.h @@ -1550,11 +1551,11 @@ lcm.o : lcm.c $(CONFIG_H) system.h $(RTL_H) $(REGS_H) hard-reg-set.h flags.h \ profile.o : profile.c $(CONFIG_H) system.h $(RTL_H) flags.h insn-flags.h \ gcov-io.h $(TREE_H) output.h $(REGS_H) toplev.h function.h insn-config.h \ ggc.h -loop.o : loop.c $(CONFIG_H) system.h $(RTL_H) flags.h loop.h insn-config.h \ +loop.o : loop.c $(CONFIG_H) system.h $(RTL_H) flags.h $(LOOP_H) insn-config.h \ insn-flags.h $(REGS_H) hard-reg-set.h $(RECOG_H) $(EXPR_H) real.h \ $(BASIC_BLOCK_H) function.h toplev.h varray.h except.h unroll.o : unroll.c $(CONFIG_H) system.h $(RTL_H) insn-config.h function.h \ - integrate.h $(REGS_H) $(RECOG_H) flags.h $(EXPR_H) loop.h toplev.h varray.h + integrate.h $(REGS_H) $(RECOG_H) flags.h $(EXPR_H) $(LOOP_H) toplev.h varray.h flow.o : flow.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h insn-config.h \ $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \ insn-flags.h function.h except.h diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 499f86ec4de4..ef7276e0b873 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -18,6 +18,8 @@ along with GNU CC; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ +#ifndef _BASIC_BLOCK_H +#define _BASIC_BLOCK_H 1 #include "bitmap.h" #include "sbitmap.h" @@ -222,6 +224,92 @@ extern void remove_fake_edges PROTO ((void)); extern void add_noreturn_fake_exit_edges PROTO ((void)); extern void flow_delete_insn_chain PROTO((rtx, rtx)); + +/* Structure to hold information for each natural loop. */ +struct loop +{ + int num; + + /* Basic block of loop header. */ + basic_block header; + + /* Basic block of loop latch. */ + basic_block latch; + + /* Basic block of loop pre-header or NULL if it does not exist. */ + basic_block pre_header; + + /* Bitmap of blocks contained within the loop. */ + sbitmap nodes; + + /* Number of blocks contained within the loop. */ + int num_nodes; + + /* Array of edges that exit the loop. */ + edge *exits; + + /* Number of edges that exit the loop. */ + int num_exits; + + /* The loop nesting depth. */ + int depth; + + /* The height of the loop (enclosed loop levels) within the loop + hierarchy tree. */ + int level; + + /* The outer (parent) loop or NULL if outermost loop. */ + struct loop *outer; + + /* The first inner (child) loop or NULL if innermost loop. */ + struct loop *inner; + + /* Link to the next (sibling) loop. */ + struct loop *next; + + /* Non-zero if the loop shares a header with another loop. */ + int shared; + + /* Non-zero if the loop is invalid (e.g., contains setjmp.). */ + int invalid; + + /* Auxiliary info specific to a pass. */ + void *info; +}; + + +/* Structure to hold CFG information about natural loops within a function. */ +struct loops +{ + /* Number of natural loops in the function. */ + int num; + + /* Array of natural loop descriptors (scanning this array in reverse order + will find the inner loops before their enclosing outer loops). */ + struct loop *array; + + /* Pointer to root of loop heirachy tree. */ + struct loop *tree; + + /* Information derived from the CFG. */ + struct cfg + { + /* The bitmap vector of dominators or NULL if not computed. */ + sbitmap *dom; + + /* The ordering of the basic blocks in a depth first search. */ + int *dfs_order; + } cfg; + + /* Headers shared by multiple loops that should be merged. */ + sbitmap shared_headers; +}; + +extern int flow_loops_find PROTO ((struct loops *)); +extern void flow_loops_free PROTO ((struct loops *)); +extern void flow_loops_dump PROTO ((const struct loops *, FILE *, int)); + + /* This structure maintains an edge list vector. */ struct edge_list { @@ -295,3 +383,5 @@ extern void compute_available PROTO ((sbitmap *, sbitmap *, /* In emit-rtl.c. */ extern rtx emit_block_insn_after PROTO((rtx, rtx, basic_block)); extern rtx emit_block_insn_before PROTO((rtx, rtx, basic_block)); + +#endif /* _BASIC_BLOCK_H */ diff --git a/gcc/flow.c b/gcc/flow.c index 837837222885..f147b7e4e514 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -6332,3 +6332,684 @@ add_noreturn_fake_exit_edges () if (BASIC_BLOCK (x)->succ == NULL) make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE); } + +/* Dump the list of basic blocks in the bitmap NODES. */ +static void +flow_nodes_print (str, nodes, file) + const char *str; + const sbitmap nodes; + FILE *file; +{ + int node; + + 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) + const char *str; + const edge *edges; + int num_edges; + FILE *file; +{ + int i; + + fprintf (file, "%s { ", str); + for (i = 0; i < num_edges; i++) + fprintf (file, "%d->%d ", edges[i]->src->index, edges[i]->dest->index); + fputs ("}\n", file); +} + + +/* Dump loop related CFG information. */ +static void +flow_loops_cfg_dump (loops, file) + const struct loops *loops; + FILE *file; +{ + int i; + + if (! loops->num || ! file || ! loops->cfg.dom) + return; + + for (i = 0; i < n_basic_blocks; i++) + { + edge succ; + + fprintf (file, ";; %d succs { ", i); + for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next) + fprintf (file, "%d ", succ->dest->index); + flow_nodes_print ("} dom", loops->cfg.dom[i], file); + } + + + /* Dump the DFS node order. */ + if (loops->cfg.dfs_order) + { + fputs (";; DFS order: ", file); + for (i = 0; i < n_basic_blocks; i++) + fprintf (file, "%d ", loops->cfg.dfs_order[i]); + fputs ("\n", file); + } +} + + +/* Return non-zero if the nodes of LOOP are a subset of OUTER. */ +int +flow_loop_nested_p (outer, loop) + struct loop *outer; + struct loop *loop; +{ + return sbitmap_a_subset_b_p (loop->nodes, outer->nodes); +} + + +/* Dump the loop information specified by LOOPS to the stream FILE. */ +void +flow_loops_dump (loops, file, verbose) + const struct loops *loops; + FILE *file; + int verbose; +{ + int i; + int num_loops; + + num_loops = loops->num; + if (! num_loops || ! file) + return; + + fprintf (file, ";; %d loops found\n", num_loops); + + for (i = 0; i < num_loops; i++) + { + struct loop *loop = &loops->array[i]; + + fprintf (file, ";; loop %d (%d to %d):\n" + ";; header %d, latch %d, pre-header %d," + " depth %d, level %d, outer %d\n", + i, INSN_UID (loop->header->head), INSN_UID (loop->latch->end), + loop->header->index, loop->latch->index, + loop->pre_header ? loop->pre_header->index : -1, + loop->depth, loop->level, + loop->outer ? (loop->outer - loops->array) : -1); + 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); + + if (loop->shared) + { + int j; + + for (j = 0; j < i; j++) + { + struct loop *oloop = &loops->array[j]; + + if (loop->header == oloop->header) + { + int disjoint; + int smaller; + + smaller = loop->num_nodes < oloop->num_nodes; + + /* If the union of LOOP and OLOOP is different than + the larger of LOOP and OLOOP then LOOP and OLOOP + must be disjoint. */ + disjoint = ! flow_loop_nested_p (smaller ? loop : oloop); + fprintf (file, ";; loop header %d shared by loops %d, %d" + " %s\n", + loop->header->index, i, j, + disjoint ? "disjoint" : "nested"); + } + } + } + + if (verbose) + { + /* Print diagnostics to compare our concept of a loop with + what the loop notes say. */ + if (GET_CODE (PREV_INSN (loop->header->head)) != NOTE + || NOTE_LINE_NUMBER (PREV_INSN (loop->header->head)) + != NOTE_INSN_LOOP_BEG) + fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n", + INSN_UID (PREV_INSN (loop->header->head))); + if (GET_CODE (NEXT_INSN (loop->latch->end)) != NOTE + || NOTE_LINE_NUMBER (NEXT_INSN (loop->latch->end)) + != NOTE_INSN_LOOP_END) + fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n", + INSN_UID (NEXT_INSN (loop->latch->end))); + } + } + + if (verbose) + flow_loops_cfg_dump (loops, file); +} + + +/* Free all the memory allocated for LOOPS. */ +void +flow_loops_free (loops) + struct loops *loops; +{ + if (loops->array) + { + int i; + + if (! loops->num) + abort (); + + /* Free the loop descriptors. */ + for (i = 0; i < loops->num; i++) + { + struct loop *loop = &loops->array[i]; + + if (loop->nodes) + sbitmap_free (loop->nodes); + if (loop->exits) + free (loop->exits); + } + free (loops->array); + loops->array = NULL; + + if (loops->cfg.dom) + sbitmap_vector_free (loops->cfg.dom); + if (loops->cfg.dfs_order) + free (loops->cfg.dfs_order); + + sbitmap_free (loops->shared_headers); + } +} + + +/* 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. */ +static int +flow_loop_exits_find (nodes, exits) + const sbitmap nodes; + edge **exits; +{ + edge e; + int node; + int num_exits; + + *exits = 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. */ + 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; + + if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) + num_exits++; + } + }); + + if (! num_exits) + return 0; + + *exits = (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; + + if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) + (*exits)[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. */ +static int +flow_loop_nodes_find (header, latch, nodes) + basic_block header; + basic_block latch; + sbitmap nodes; +{ + basic_block *stack; + int sp; + int num_nodes = 0; + + stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block)); + sp = 0; + + /* Start with only the loop header in the set of loop nodes. */ + sbitmap_zero (nodes); + SET_BIT (nodes, header->index); + num_nodes++; + + /* Push the loop latch on to the stack. */ + if (! TEST_BIT (nodes, latch->index)) + { + SET_BIT (nodes, latch->index); + num_nodes++; + stack[sp++] = latch; + } + + while (sp) + { + basic_block node; + edge e; + + node = stack[--sp]; + for (e = node->pred; e; e = e->pred_next) + { + basic_block ancestor = e->src; + + /* If each ancestor not marked as part of loop, add to set of + loop nodes and push on to stack. */ + if (ancestor != ENTRY_BLOCK_PTR + && ! TEST_BIT (nodes, ancestor->index)) + { + SET_BIT (nodes, ancestor->index); + num_nodes++; + stack[sp++] = ancestor; + } + } + } + free (stack); + return num_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. */ +static int +flow_depth_first_order_compute (dfs_order) + int *dfs_order; +{ + edge e; + edge *stack; + int sp; + int dfsnum = 0; + sbitmap visited; + + /* Allocate stack for back-tracking up CFG. */ + stack = (edge *) xmalloc (n_basic_blocks * 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); + + /* Start with the first successor edge from the entry block. */ + e = ENTRY_BLOCK_PTR->succ; + while (e) + { + basic_block src = e->src; + basic_block dest = e->dest; + + /* Mark that we have visited this node. */ + if (src != ENTRY_BLOCK_PTR) + SET_BIT (visited, src->index); + + /* If this node has not been visited before, push the current + edge on to the stack and proceed with the first successor + edge of this node. */ + if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index) + && dest->succ) + { + stack[sp++] = e; + e = dest->succ; + } + else + { + if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index) + && ! dest->succ) + { + /* DEST has no successors (for example, a non-returning + function is called) so do not push the current edge + but carry on with its next successor. */ + dfs_order[dest->index] = n_basic_blocks - ++dfsnum; + SET_BIT (visited, dest->index); + } + + while (! e->succ_next && src != ENTRY_BLOCK_PTR) + { + dfs_order[src->index] = n_basic_blocks - ++dfsnum; + + /* Pop edge off stack. */ + e = stack[--sp]; + src = e->src; + } + e = e->succ_next; + } + } + free (stack); + sbitmap_free (visited); + + /* The number of nodes visited should not be greater than + n_basic_blocks. */ + if (dfsnum > n_basic_blocks) + abort (); + + /* There are some nodes left in the CFG that are unreachable. */ + if (dfsnum < n_basic_blocks) + abort (); + return dfsnum; +} + + +/* Return the block for the pre-header of the loop with header + HEADER where DOM specifies the dominator information. Return NULL if + there is no pre-header. */ +static basic_block +flow_loop_pre_header_find (header, dom) + basic_block header; + const sbitmap *dom; +{ + basic_block pre_header; + edge e; + + /* If block p is a predecessor of the header and is the only block + that the header does not dominate, then it is the pre-header. */ + pre_header = NULL; + for (e = header->pred; e; e = e->pred_next) + { + basic_block node = e->src; + + if (node != ENTRY_BLOCK_PTR + && ! TEST_BIT (dom[node->index], header->index)) + { + if (pre_header == NULL) + pre_header = node; + else + { + /* There are multiple edges into the header from outside + the loop so there is no pre-header block. */ + pre_header = NULL; + break; + } + } + } + return pre_header; +} + + +/* Add LOOP to the loop hierarchy tree so that it is a sibling or a + descendant of ROOT. */ +static void +flow_loop_tree_node_add (root, loop) + struct loop *root; + struct loop *loop; +{ + struct loop *outer; + + if (! loop) + return; + + for (outer = root; outer; outer = outer->next) + { + if (flow_loop_nested_p (outer, loop)) + { + if (outer->inner) + { + /* Add LOOP as a sibling or descendent of OUTER->INNER. */ + flow_loop_tree_node_add (outer->inner, loop); + } + else + { + /* Add LOOP as child of OUTER. */ + outer->inner = loop; + loop->outer = outer; + loop->next = NULL; + } + return; + } + } + /* Add LOOP as a sibling of ROOT. */ + loop->next = root->next; + root->next = loop; + loop->outer = root->outer; +} + + +/* Build the loop hierarchy tree for LOOPS. */ +static void +flow_loops_tree_build (loops) + struct loops *loops; +{ + int i; + int num_loops; + + num_loops = loops->num; + if (! num_loops) + return; + + /* Root the loop hierarchy tree with the first loop found. + Since we used a depth first search this should be the + outermost loop. */ + loops->tree = &loops->array[0]; + loops->tree->outer = loops->tree->inner = loops->tree->next = NULL; + + /* Add the remaining loops to the tree. */ + for (i = 1; i < num_loops; i++) + flow_loop_tree_node_add (loops->tree, &loops->array[i]); +} + + +/* Helper function to compute loop nesting depth and enclosed loop level + for the natural loop specified by LOOP at the loop depth DEPTH. + Returns the loop level. */ +static int +flow_loop_level_compute (loop, depth) + struct loop *loop; + int depth; +{ + struct loop *inner; + int level = 0; + + if (! loop) + return 0; + + /* Traverse loop tree assigning depth and computing level as the + maximum level of all the inner loops of this loop. The loop + level is equivalent to the height of the loop in the loop tree + and corresponds to the number of enclosed loop levels. */ + for (inner = loop->inner; inner; inner = inner->next) + { + int ilevel; + + ilevel = flow_loop_level_compute (inner, depth + 1) + 1; + + if (ilevel > level) + level = ilevel; + } + loop->level = level; + loop->depth = depth; + return level; +} + + +/* Compute the loop nesting depth and enclosed loop level for the loop + hierarchy tree specfied by LOOPS. Return the maximum enclosed loop + level. */ +static int +flow_loops_level_compute (loops) + struct loops *loops; +{ + return flow_loop_level_compute (loops->tree, 0); +} + + +/* Find all the natural loops in the function and save in LOOPS structure. + Return the number of natural loops found. */ +int +flow_loops_find (loops) + struct loops *loops; +{ + int i; + int b; + int num_loops; + edge e; + sbitmap headers; + sbitmap *dom; + int *dfs_order; + + loops->num = 0; + loops->array = NULL; + loops->tree = NULL; + dfs_order = NULL; + + /* Taking care of this degenerate case makes the rest of + this code simpler. */ + if (n_basic_blocks == 0) + return 0; + + /* Compute the dominators. */ + dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); + compute_flow_dominators (dom, NULL); + + /* Count the number of loop edges (back edges). This should be the + same as the number of natural loops. */ + num_loops = 0; + for (b = 0; b < n_basic_blocks; b++) + { + for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next) + { + basic_block latch = e->src; + + /* Look for back edges where a predecessor is dominated + by this block. A natural loop has a single entry + node (header) that dominates all the nodes in the + loop. It also has single back edge to the header + from a latch node. Note that multiple natural loops + may share the same header. */ + if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b)) + num_loops++; + } + } + + if (num_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); + + /* Allocate loop structures. */ + loops->array = (struct loop *) + xcalloc (num_loops, sizeof (struct loop)); + + headers = sbitmap_alloc (n_basic_blocks); + sbitmap_zero (headers); + + loops->shared_headers = sbitmap_alloc (n_basic_blocks); + sbitmap_zero (loops->shared_headers); + + /* Find and record information about all the natural loops + in the CFG. */ + num_loops = 0; + for (b = 0; b < n_basic_blocks; b++) + { + basic_block header; + + /* Search the nodes of the CFG in DFS order that we can find + outer loops first. */ + header = BASIC_BLOCK (dfs_order[b]); + + /* Look for all the possible latch blocks for this header. */ + for (e = header->pred; e; e = e->pred_next) + { + basic_block latch = e->src; + + /* Look for back edges where a predecessor is dominated + by this block. A natural loop has a single entry + node (header) that dominates all the nodes in the + loop. It also has single back edge to the header + from a latch node. Note that multiple natural loops + may share the same header. */ + if (latch != ENTRY_BLOCK_PTR + && TEST_BIT (dom[latch->index], header->index)) + { + struct loop *loop; + + loop = loops->array + num_loops; + + loop->header = header; + loop->latch = latch; + + /* Keep track of blocks that are loop headers so + that we can tell which loops should be merged. */ + if (TEST_BIT (headers, header->index)) + SET_BIT (loops->shared_headers, header->index); + SET_BIT (headers, header->index); + + /* Find nodes contained within the loop. */ + loop->nodes = sbitmap_alloc (n_basic_blocks); + loop->num_nodes = + flow_loop_nodes_find (header, latch, loop->nodes); + + /* Find edges which exit the loop. Note that a node + may have several exit edges. */ + loop->num_exits + = flow_loop_exits_find (loop->nodes, &loop->exits); + + /* Look to see if the loop has a pre-header node. */ + loop->pre_header + = flow_loop_pre_header_find (header, dom); + + num_loops++; + } + } + } + + /* Natural loops with shared headers may either be disjoint or + nested. Disjoint loops with shared headers cannot be inner + loops and should be merged. For now just mark loops that share + headers. */ + for (i = 0; i < num_loops; i++) + if (TEST_BIT (loops->shared_headers, loops->array[i].header->index)) + loops->array[i].shared = 1; + + sbitmap_free (headers); + } + + loops->num = num_loops; + + /* Save CFG derived information to avoid recomputing it. */ + loops->cfg.dom = dom; + loops->cfg.dfs_order = dfs_order; + + /* Build the loop hierarchy tree. */ + flow_loops_tree_build (loops); + + /* Assign the loop nesting depth and enclosed loop level for each + loop. */ + flow_loops_level_compute (loops); + + return num_loops; +} + + +/* Return non-zero if edge E enters header of LOOP from outside of LOOP. */ +int +flow_loop_outside_edge_p (loop, e) + const struct loop *loop; + edge e; +{ + if (e->dest != loop->header) + abort (); + return (e->src == ENTRY_BLOCK_PTR) + || ! TEST_BIT (loop->nodes, e->src->index); +} diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c index 4cc7c85f5c1b..dece5e5ef250 100644 --- a/gcc/sbitmap.c +++ b/gcc/sbitmap.c @@ -265,6 +265,25 @@ sbitmap_a_or_b (dst, a, b) } return changed; } +/* Return non-zero if A is a subset of B. */ + +int +sbitmap_a_subset_b_p (a, b) + sbitmap a, b; +{ + int i; + sbitmap_ptr ap, bp; + + ap = a->elms; + bp = b->elms; + for (i = 0; i < a->size; i++) + { + if ((*ap | *bp) != *bp) + return 0; + ap++; bp++; + } + return 1; +} /* Set DST to be (A or (B and C)). Return non-zero if any change is made. */ diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h index ca2f99730a55..1fc300412238 100644 --- a/gcc/sbitmap.h +++ b/gcc/sbitmap.h @@ -18,6 +18,9 @@ along with GNU CC; see the file COPYING. If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ +#ifndef _SBITMAP_H +#define _SBITMAP_H 1 + /* It's not clear yet whether using bitmap.[ch] will be a win. It should be straightforward to convert so for now we keep things simple while more important issues are dealt with. */ @@ -109,6 +112,7 @@ extern int sbitmap_a_or_b_and_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); extern int sbitmap_a_and_b_or_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); extern int sbitmap_a_and_b PROTO ((sbitmap, sbitmap, sbitmap)); extern int sbitmap_a_or_b PROTO ((sbitmap, sbitmap, sbitmap)); +extern int sbitmap_a_subset_b_p PROTO ((sbitmap, sbitmap)); struct int_list; extern void sbitmap_intersect_of_predsucc PROTO ((sbitmap, sbitmap *, @@ -129,3 +133,4 @@ extern void sbitmap_intersection_of_preds PROTO ((sbitmap, sbitmap *, int)); extern void sbitmap_union_of_succs PROTO ((sbitmap, sbitmap *, int)); extern void sbitmap_union_of_preds PROTO ((sbitmap, sbitmap *, int)); +#endif /* _SBITMAP_H */ -- 2.39.2