X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcfgloop.c;h=0e258c64a342eeed34e62d076a6be6d1d943039e;hb=782858b8cb5960a958ff47f1fe62fd9896596002;hp=aed264172fdd0ed60f28ac5bb76ab549c039129d;hpb=03bfa804173a9f41755a786319fdda37c6af0ff5;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index aed264172fd..0e258c64a34 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -1,5 +1,5 @@ /* Natural loop discovery code for GNU compiler. - Copyright (C) 2000, 2001 Free Software Foundation, Inc. + Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc. This file is part of GCC. @@ -20,49 +20,53 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "config.h" #include "system.h" +#include "coretypes.h" +#include "tm.h" #include "rtl.h" #include "hard-reg-set.h" +#include "obstack.h" +#include "function.h" #include "basic-block.h" - -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 void flow_loop_pre_header_scan PARAMS ((struct loop *)); -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 *)); -static int flow_loop_level_compute PARAMS ((struct loop *, int)); -static int flow_loops_level_compute PARAMS ((struct loops *)); +#include "toplev.h" +#include "cfgloop.h" +#include "flags.h" +#include "tree.h" +#include "tree-flow.h" + +/* Ratio of frequencies of edges so that one of more latch edges is + considered to belong to inner loop with same header. */ +#define HEAVY_EDGE_RATIO 8 + +#define HEADER_BLOCK(B) (* (int *) (B)->aux) +#define LATCH_EDGE(E) (*(int *) (E)->aux) + +static void flow_loops_cfg_dump (const struct loops *, FILE *); +static int flow_loop_level_compute (struct loop *); +static void flow_loops_level_compute (struct loops *); +static void establish_preds (struct loop *); +static void canonicalize_loop_headers (void); +static bool glb_enum_p (basic_block, void *); /* Dump loop related CFG information. */ static void -flow_loops_cfg_dump (loops, file) - const struct loops *loops; - FILE *file; +flow_loops_cfg_dump (const struct loops *loops, FILE *file) { int i; basic_block bb; - if (! loops->num || ! file || ! loops->cfg.dom) + if (! loops->num || ! file) return; FOR_EACH_BB (bb) { edge succ; + edge_iterator ei; fprintf (file, ";; %d succs { ", bb->index); - for (succ = bb->succ; succ; succ = succ->succ_next) + FOR_EACH_EDGE (succ, ei, bb->succs) fprintf (file, "%d ", succ->dest->index); - flow_nodes_print ("} dom", loops->cfg.dom[bb->index], file); + fprintf (file, "}\n"); } /* Dump the DFS node order. */ @@ -86,59 +90,58 @@ flow_loops_cfg_dump (loops, file) } } -/* Return non-zero if the nodes of LOOP are a subset of OUTER. */ +/* Return nonzero if the nodes of LOOP are a subset of OUTER. */ -static int -flow_loop_nested_p (outer, loop) - struct loop *outer; - struct loop *loop; +bool +flow_loop_nested_p (const struct loop *outer, const struct loop *loop) +{ + return (loop->depth > outer->depth + && loop->pred[outer->depth] == outer); +} + +/* Returns the loop such that LOOP is nested DEPTH (indexed from zero) + loops within LOOP. */ + +struct loop * +superloop_at_depth (struct loop *loop, unsigned depth) { - return sbitmap_a_subset_b_p (loop->nodes, outer->nodes); + gcc_assert (depth <= (unsigned) loop->depth); + + if (depth == (unsigned) loop->depth) + return loop; + + return loop->pred[depth]; } /* Dump the loop information specified by LOOP to the stream FILE using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ void -flow_loop_dump (loop, file, loop_dump_aux, verbose) - const struct loop *loop; - FILE *file; - void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int)); - int verbose; +flow_loop_dump (const struct loop *loop, FILE *file, + void (*loop_dump_aux) (const struct loop *, FILE *, int), + int verbose) { + basic_block *bbs; + unsigned i; + if (! loop || ! loop->header) return; - if (loop->first->head && loop->last->end) - fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n", - loop->num, INSN_UID (loop->first->head), - INSN_UID (loop->last->end), - loop->shared ? " shared" : "", loop->invalid ? " invalid" : ""); - else - fprintf (file, ";;\n;; Loop %d:%s%s\n", loop->num, - loop->shared ? " shared" : "", loop->invalid ? " invalid" : ""); + fprintf (file, ";;\n;; Loop %d:%s\n", loop->num, + loop->invalid ? " invalid" : ""); - fprintf (file, ";; header %d, latch %d, pre-header %d, first %d, last %d\n", - loop->header->index, loop->latch->index, - loop->pre_header ? loop->pre_header->index : -1, - loop->first->index, loop->last->index); + fprintf (file, ";; header %d, latch %d\n", + loop->header->index, loop->latch->index); fprintf (file, ";; depth %d, level %d, outer %ld\n", loop->depth, loop->level, (long) (loop->outer ? loop->outer->num : -1)); - if (loop->pre_header_edges) - flow_edge_list_print (";; pre-header edges", loop->pre_header_edges, - loop->num_pre_header_edges, file); - - 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); - flow_edge_list_print (";; exit edges", loop->exit_edges, - loop->num_exits, file); - - if (loop->exits_doms) - flow_nodes_print (";; exit doms", loop->exits_doms, file); + fprintf (file, ";; nodes:"); + bbs = get_loop_body (loop); + for (i = 0; i < loop->num_nodes; i++) + fprintf (file, " %d", bbs[i]->index); + free (bbs); + fprintf (file, "\n"); if (loop_dump_aux) loop_dump_aux (loop, file, verbose); @@ -148,382 +151,243 @@ flow_loop_dump (loop, file, loop_dump_aux, verbose) using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ void -flow_loops_dump (loops, file, loop_dump_aux, verbose) - const struct loops *loops; - FILE *file; - void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int)); - int verbose; +flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) { - int i, j; + int i; int num_loops; num_loops = loops->num; if (! num_loops || ! file) return; - fprintf (file, ";; %d loops found, %d levels\n", num_loops, loops->levels); + fprintf (file, ";; %d loops found\n", num_loops); + for (i = 0; i < num_loops; i++) { - struct loop *loop = &loops->array[i]; + struct loop *loop = loops->parray[i]; - flow_loop_dump (loop, file, loop_dump_aux, verbose); - if (loop->shared) - for (j = 0; j < i; j++) - { - struct loop *oloop = &loops->array[j]; + if (!loop) + continue; - 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, - smaller ? oloop : loop); - fprintf (file, - ";; loop header %d shared by loops %d, %d %s\n", - loop->header->index, i, j, - disjoint ? "disjoint" : "nested"); - } - } + flow_loop_dump (loop, file, loop_dump_aux, verbose); } if (verbose) flow_loops_cfg_dump (loops, file); } +/* Free data allocated for LOOP. */ +void +flow_loop_free (struct loop *loop) +{ + if (loop->pred) + free (loop->pred); + free (loop); +} + /* Free all the memory allocated for LOOPS. */ void -flow_loops_free (loops) - struct loops *loops; +flow_loops_free (struct loops *loops) { - if (loops->array) + if (loops->parray) { - int i; + unsigned i; - if (! loops->num) - abort (); + gcc_assert (loops->num); /* Free the loop descriptors. */ for (i = 0; i < loops->num; i++) { - struct loop *loop = &loops->array[i]; - - if (loop->pre_header_edges) - free (loop->pre_header_edges); - if (loop->nodes) - sbitmap_free (loop->nodes); - if (loop->entry_edges) - free (loop->entry_edges); - if (loop->exit_edges) - free (loop->exit_edges); - if (loop->exits_doms) - sbitmap_free (loop->exits_doms); - } + struct loop *loop = loops->parray[i]; + + if (!loop) + continue; - free (loops->array); - loops->array = NULL; + flow_loop_free (loop); + } - if (loops->cfg.dom) - sbitmap_vector_free (loops->cfg.dom); + free (loops->parray); + loops->parray = NULL; if (loops->cfg.dfs_order) free (loops->cfg.dfs_order); + if (loops->cfg.rc_order) + free (loops->cfg.rc_order); - if (loops->shared_headers) - sbitmap_free (loops->shared_headers); } } -/* 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. */ +/* Find the nodes contained within the LOOP with header HEADER. + Return the number of nodes within the loop. */ -static int -flow_loop_entry_edges_find (header, nodes, entry_edges) - basic_block header; - const sbitmap nodes; - edge **entry_edges; +int +flow_loop_nodes_find (basic_block header, struct loop *loop) { - edge e; - int num_entries; + basic_block *stack; + int sp; + int num_nodes = 1; - *entry_edges = NULL; + header->loop_father = loop; + header->loop_depth = loop->depth; - num_entries = 0; - for (e = header->pred; e; e = e->pred_next) + if (loop->latch->loop_father != loop) { - basic_block src = e->src; - - if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index)) - num_entries++; - } + stack = xmalloc (n_basic_blocks * sizeof (basic_block)); + sp = 0; + num_nodes++; + stack[sp++] = loop->latch; + loop->latch->loop_father = loop; + loop->latch->loop_depth = loop->depth; - if (! num_entries) - abort (); + while (sp) + { + basic_block node; + edge e; + edge_iterator ei; - *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge)); + node = stack[--sp]; - num_entries = 0; - for (e = header->pred; e; e = e->pred_next) - { - basic_block src = e->src; + FOR_EACH_EDGE (e, ei, node->preds) + { + basic_block ancestor = e->src; - if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index)) - (*entry_edges)[num_entries++] = e; + if (ancestor != ENTRY_BLOCK_PTR + && ancestor->loop_father != loop) + { + ancestor->loop_father = loop; + ancestor->loop_depth = loop->depth; + num_nodes++; + stack[sp++] = ancestor; + } + } + } + free (stack); } - - return num_entries; + return num_nodes; } -/* 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. */ +/* For each loop in the lOOPS tree that has just a single exit + record the exit edge. */ -static int -flow_loop_exit_edges_find (nodes, exit_edges) - const sbitmap nodes; - edge **exit_edges; +void +mark_single_exit_loops (struct loops *loops) { + basic_block bb; edge e; - int node; - int num_exits; - - *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 ????? 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; - - if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) - num_exits++; - } - }); - - if (! num_exits) - return 0; - - *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; - - if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) - (*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. */ - -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++; - header->loop_depth++; + struct loop *loop; + unsigned i; - /* Push the loop latch on to the stack. */ - if (! TEST_BIT (nodes, latch->index)) + for (i = 1; i < loops->num; i++) { - SET_BIT (nodes, latch->index); - latch->loop_depth++; - num_nodes++; - stack[sp++] = latch; + loop = loops->parray[i]; + if (loop) + loop->single_exit = NULL; } - while (sp) + FOR_EACH_BB (bb) { - basic_block node; - edge e; - - node = stack[--sp]; - for (e = node->pred; e; e = e->pred_next) + edge_iterator ei; + if (bb->loop_father == loops->tree_root) + continue; + FOR_EACH_EDGE (e, ei, bb->succs) { - basic_block ancestor = e->src; + if (e->dest == EXIT_BLOCK_PTR) + continue; + + if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) + continue; - /* 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)) + for (loop = bb->loop_father; + loop != e->dest->loop_father; + loop = loop->outer) { - SET_BIT (nodes, ancestor->index); - ancestor->loop_depth++; - num_nodes++; - stack[sp++] = ancestor; + /* If we have already seen an exit, mark this by the edge that + surely does not occur as any exit. */ + if (loop->single_exit) + loop->single_exit = single_succ_edge (ENTRY_BLOCK_PTR); + else + loop->single_exit = e; } } } - free (stack); - return num_nodes; -} -/* Find the root node of the loop pre-header extended basic block and - the edges along the trace from the root node to the loop header. */ - -static void -flow_loop_pre_header_scan (loop) - struct loop *loop; -{ - int num; - basic_block ebb; - edge e; - - loop->num_pre_header_edges = 0; - if (loop->num_entries != 1) - return; - - ebb = loop->entry_edges[0]->src; - if (ebb == ENTRY_BLOCK_PTR) - return; - - /* Count number of edges along trace from loop header to - root of pre-header extended basic block. Usually this is - only one or two edges. */ - for (num = 1; ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next; - num++) - ebb = ebb->pred->src; + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + if (!loop) + continue; - loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge)); - loop->num_pre_header_edges = num; + if (loop->single_exit == single_succ_edge (ENTRY_BLOCK_PTR)) + loop->single_exit = NULL; + } - /* Store edges in order that they are followed. The source of the first edge - is the root node of the pre-header extended basic block and the - destination of the last last edge is the loop header. */ - for (e = loop->entry_edges[0]; num; e = e->src->pred) - loop->pre_header_edges[--num] = e; + loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS; } -/* 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; +static void +establish_preds (struct loop *loop) { - basic_block pre_header; - edge e; + struct loop *ploop, *father = loop->outer; - /* 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; + loop->depth = father->depth + 1; - 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; - } - } - } + /* Remember the current loop depth if it is the largest seen so far. */ + cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth); - return pre_header; + if (loop->pred) + free (loop->pred); + loop->pred = xmalloc (sizeof (struct loop *) * loop->depth); + memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth); + loop->pred[father->depth] = father; + + for (ploop = loop->inner; ploop; ploop = ploop->next) + establish_preds (ploop); } -/* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop - previously added. The insertion algorithm assumes that the loops - are added in the order found by a depth first search of the CFG. */ +/* Add LOOP to the loop hierarchy tree where FATHER is father of the + added loop. If LOOP has some children, take care of that their + pred field will be initialized correctly. */ -static void -flow_loop_tree_node_add (prevloop, loop) - struct loop *prevloop; - struct loop *loop; +void +flow_loop_tree_node_add (struct loop *father, struct loop *loop) { + loop->next = father->inner; + father->inner = loop; + loop->outer = father; - if (flow_loop_nested_p (prevloop, loop)) - { - prevloop->inner = loop; - loop->outer = prevloop; - return; - } - - for (; prevloop->outer; prevloop = prevloop->outer) - if (flow_loop_nested_p (prevloop->outer, loop)) - { - prevloop->next = loop; - loop->outer = prevloop->outer; - return; - } - - prevloop->next = loop; - loop->outer = NULL; + establish_preds (loop); } -/* Build the loop hierarchy tree for LOOPS. */ +/* Remove LOOP from the loop hierarchy tree. */ -static void -flow_loops_tree_build (loops) - struct loops *loops; +void +flow_loop_tree_node_remove (struct loop *loop) { - int i; - int num_loops; + struct loop *prev, *father; - num_loops = loops->num; - if (! num_loops) - return; + father = loop->outer; + loop->outer = NULL; - /* 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_root = &loops->array[0]; - loops->tree_root->outer = loops->tree_root->inner - = loops->tree_root->next = NULL; + /* Remove loop from the list of sons. */ + if (father->inner == loop) + father->inner = loop->next; + else + { + for (prev = father->inner; prev->next != loop; prev = prev->next); + prev->next = loop->next; + } - /* Add the remaining loops to the tree. */ - for (i = 1; i < num_loops; i++) - flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]); + loop->depth = -1; + free (loop->pred); + loop->pred = NULL; } /* 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. */ + for the natural loop specified by LOOP. Returns the loop level. */ static int -flow_loop_level_compute (loop, depth) - struct loop *loop; - int depth; +flow_loop_level_compute (struct loop *loop) { struct loop *inner; int level = 1; @@ -538,13 +402,13 @@ flow_loop_level_compute (loop, depth) itself). */ for (inner = loop->inner; inner; inner = inner->next) { - int ilevel = flow_loop_level_compute (inner, depth + 1) + 1; + int ilevel = flow_loop_level_compute (inner) + 1; - level = MAX (ilevel, level); + if (ilevel > level) + level = ilevel; } loop->level = level; - loop->depth = depth; return level; } @@ -552,108 +416,198 @@ flow_loop_level_compute (loop, depth) hierarchy tree specified by LOOPS. Return the maximum enclosed loop level. */ -static int -flow_loops_level_compute (loops) - struct loops *loops; +static void +flow_loops_level_compute (struct loops *loops) { - int levels = 0; - struct loop *loop; - int level; + flow_loop_level_compute (loops->tree_root); +} - /* Traverse all the outer level loops. */ - for (loop = loops->tree_root; loop; loop = loop->next) - { - level = flow_loop_level_compute (loop, 1); - levels = MAX (levels, level); - } +/* A callback to update latch and header info for basic block JUMP created + by redirecting an edge. */ + +static void +update_latch_info (basic_block jump) +{ + alloc_aux_for_block (jump, sizeof (int)); + HEADER_BLOCK (jump) = 0; + alloc_aux_for_edge (single_pred_edge (jump), sizeof (int)); + LATCH_EDGE (single_pred_edge (jump)) = 0; + set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump)); +} - return levels; +/* A callback for make_forwarder block, to redirect all edges except for + MFB_KJ_EDGE to the entry part. E is the edge for that we should decide + whether to redirect it. */ + +static edge mfb_kj_edge; +static bool +mfb_keep_just (edge e) +{ + return e != mfb_kj_edge; } -/* Scan a single natural loop specified by LOOP collecting information - about it specified by FLAGS. */ +/* A callback for make_forwarder block, to redirect the latch edges into an + entry part. E is the edge for that we should decide whether to redirect + it. */ -int -flow_loop_scan (loops, loop, flags) - struct loops *loops; - struct loop *loop; - int flags; -{ - /* Determine prerequisites. */ - if ((flags & LOOP_EXITS_DOMS) && ! loop->exit_edges) - flags |= LOOP_EXIT_EDGES; - - if (flags & LOOP_ENTRY_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); - - if (flags & LOOP_EXIT_EDGES) - /* Find edges which exit the loop. */ - loop->num_exits - = flow_loop_exit_edges_find (loop->nodes, &loop->exit_edges); - - if (flags & LOOP_EXITS_DOMS) +static bool +mfb_keep_nonlatch (edge e) +{ + return LATCH_EDGE (e); +} + +/* Takes care of merging natural loops with shared headers. */ + +static void +canonicalize_loop_headers (void) +{ + basic_block header; + edge e; + + alloc_aux_for_blocks (sizeof (int)); + alloc_aux_for_edges (sizeof (int)); + + /* Split blocks so that each loop has only single latch. */ + FOR_EACH_BB (header) { - int j; - - /* Determine which loop nodes dominate all the exits - of the loop. */ - loop->exits_doms = sbitmap_alloc (last_basic_block); - sbitmap_copy (loop->exits_doms, loop->nodes); - for (j = 0; j < loop->num_exits; j++) - sbitmap_a_and_b (loop->exits_doms, loop->exits_doms, - loops->cfg.dom[loop->exit_edges[j]->src->index]); - - /* The header of a natural loop must dominate - all exits. */ - if (! TEST_BIT (loop->exits_doms, loop->header->index)) - abort (); + edge_iterator ei; + int num_latches = 0; + int have_abnormal_edge = 0; + + FOR_EACH_EDGE (e, ei, header->preds) + { + basic_block latch = e->src; + + if (e->flags & EDGE_ABNORMAL) + have_abnormal_edge = 1; + + if (latch != ENTRY_BLOCK_PTR + && dominated_by_p (CDI_DOMINATORS, latch, header)) + { + num_latches++; + LATCH_EDGE (e) = 1; + } + } + if (have_abnormal_edge) + HEADER_BLOCK (header) = 0; + else + HEADER_BLOCK (header) = num_latches; } - if (flags & LOOP_PRE_HEADER) + if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR))) { - /* Look to see if the loop has a pre-header node. */ - loop->pre_header - = flow_loop_pre_header_find (loop->header, loops->cfg.dom); + basic_block bb; + + /* We could not redirect edges freely here. On the other hand, + we can simply split the edge from entry block. */ + bb = split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); - /* Find the blocks within the extended basic block of - the loop pre-header. */ - flow_loop_pre_header_scan (loop); + alloc_aux_for_edge (single_succ_edge (bb), sizeof (int)); + LATCH_EDGE (single_succ_edge (bb)) = 0; + alloc_aux_for_block (bb, sizeof (int)); + HEADER_BLOCK (bb) = 0; } - return 1; + FOR_EACH_BB (header) + { + int max_freq, is_heavy; + edge heavy, tmp_edge; + edge_iterator ei; + + if (HEADER_BLOCK (header) <= 1) + continue; + + /* Find a heavy edge. */ + is_heavy = 1; + heavy = NULL; + max_freq = 0; + FOR_EACH_EDGE (e, ei, header->preds) + if (LATCH_EDGE (e) && + EDGE_FREQUENCY (e) > max_freq) + max_freq = EDGE_FREQUENCY (e); + FOR_EACH_EDGE (e, ei, header->preds) + if (LATCH_EDGE (e) && + EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO) + { + if (heavy) + { + is_heavy = 0; + break; + } + else + heavy = e; + } + + if (is_heavy) + { + /* Split out the heavy edge, and create inner loop for it. */ + mfb_kj_edge = heavy; + tmp_edge = make_forwarder_block (header, mfb_keep_just, + update_latch_info); + alloc_aux_for_block (tmp_edge->dest, sizeof (int)); + HEADER_BLOCK (tmp_edge->dest) = 1; + alloc_aux_for_edge (tmp_edge, sizeof (int)); + LATCH_EDGE (tmp_edge) = 0; + HEADER_BLOCK (header)--; + } + + if (HEADER_BLOCK (header) > 1) + { + /* Create a new latch block. */ + tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch, + update_latch_info); + alloc_aux_for_block (tmp_edge->dest, sizeof (int)); + HEADER_BLOCK (tmp_edge->src) = 0; + HEADER_BLOCK (tmp_edge->dest) = 1; + alloc_aux_for_edge (tmp_edge, sizeof (int)); + LATCH_EDGE (tmp_edge) = 1; + } + } + + free_aux_for_blocks (); + free_aux_for_edges (); + +#ifdef ENABLE_CHECKING + verify_dominators (CDI_DOMINATORS); +#endif +} + +/* Initialize all the parallel_p fields of the loops structure to true. */ + +static void +initialize_loops_parallel_p (struct loops *loops) +{ + unsigned int i; + + for (i = 0; i < loops->num; i++) + { + struct loop *loop = loops->parray[i]; + loop->parallel_p = true; + } } /* Find all the natural loops in the function and save in LOOPS structure and - recalculate loop_depth information in basic block structures. FLAGS - controls which loop information is collected. Return the number of natural - loops found. */ + recalculate loop_depth information in basic block structures. + Return the number of natural loops found. */ int -flow_loops_find (loops, flags) - struct loops *loops; - int flags; +flow_loops_find (struct loops *loops) { - int i; int b; int num_loops; edge e; sbitmap headers; - sbitmap *dom; int *dfs_order; int *rc_order; basic_block header; - - /* This function cannot be repeatedly called with different - flags to build up the loop information. The loop tree - must always be built if this function is called. */ - if (! (flags & LOOP_TREE)) - abort (); + basic_block bb; memset (loops, 0, sizeof *loops); + /* We are going to recount the maximum loop depth, + so throw away the last count. */ + cfun->max_loop_depth = 0; + /* Taking care of this degenerate case makes the rest of this code simpler. */ if (n_basic_blocks == 0) @@ -662,171 +616,695 @@ flow_loops_find (loops, flags) dfs_order = NULL; rc_order = NULL; - /* Compute the dominators. */ - dom = sbitmap_vector_alloc (last_basic_block, last_basic_block); - calculate_dominance_info (NULL, dom, CDI_DOMINATORS); + /* Ensure that the dominators are computed. */ + calculate_dominance_info (CDI_DOMINATORS); + + /* Join loops with shared headers. */ + canonicalize_loop_headers (); - /* Count the number of loop edges (back edges). This should be the + /* Count the number of loop headers. This should be the same as the number of natural loops. */ + headers = sbitmap_alloc (last_basic_block); + sbitmap_zero (headers); + num_loops = 0; FOR_EACH_BB (header) { + edge_iterator ei; + int more_latches = 0; + header->loop_depth = 0; - for (e = header->pred; e; e = e->pred_next) + /* If we have an abnormal predecessor, do not consider the + loop (not worth the problems). */ + FOR_EACH_EDGE (e, ei, header->preds) + if (e->flags & EDGE_ABNORMAL) + break; + if (e) + continue; + + FOR_EACH_EDGE (e, ei, header->preds) { basic_block latch = e->src; + gcc_assert (!(e->flags & EDGE_ABNORMAL)); + /* 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)) - num_loops++; + from a latch node. */ + if (latch != ENTRY_BLOCK_PTR + && dominated_by_p (CDI_DOMINATORS, latch, header)) + { + /* Shared headers should be eliminated by now. */ + gcc_assert (!more_latches); + more_latches = 1; + SET_BIT (headers, header->index); + num_loops++; + } } } + /* Allocate loop structures. */ + loops->parray = xcalloc (num_loops + 1, sizeof (struct loop *)); + + /* Dummy loop containing whole function. */ + loops->parray[0] = xcalloc (1, sizeof (struct loop)); + loops->parray[0]->next = NULL; + loops->parray[0]->inner = NULL; + loops->parray[0]->outer = NULL; + loops->parray[0]->depth = 0; + loops->parray[0]->pred = NULL; + loops->parray[0]->num_nodes = n_basic_blocks + 2; + loops->parray[0]->latch = EXIT_BLOCK_PTR; + loops->parray[0]->header = ENTRY_BLOCK_PTR; + ENTRY_BLOCK_PTR->loop_father = loops->parray[0]; + EXIT_BLOCK_PTR->loop_father = loops->parray[0]; + + loops->tree_root = loops->parray[0]; + + /* Find and record information about all the natural loops + in the CFG. */ + loops->num = 1; + FOR_EACH_BB (bb) + bb->loop_father = loops->tree_root; + 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)); - rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int)); + dfs_order = xmalloc (n_basic_blocks * sizeof (int)); + rc_order = xmalloc (n_basic_blocks * sizeof (int)); flow_depth_first_order_compute (dfs_order, rc_order); /* Save CFG derived information to avoid recomputing it. */ - loops->cfg.dom = dom; loops->cfg.dfs_order = dfs_order; loops->cfg.rc_order = rc_order; - /* Allocate loop structures. */ - loops->array - = (struct loop *) xcalloc (num_loops, sizeof (struct loop)); - - headers = sbitmap_alloc (last_basic_block); - sbitmap_zero (headers); + num_loops = 1; - loops->shared_headers = sbitmap_alloc (last_basic_block); - sbitmap_zero (loops->shared_headers); - - /* Find and record information about all the natural loops - in the CFG. */ - num_loops = 0; - for (b = n_basic_blocks - 1; b >= 0; b--) + for (b = 0; b < n_basic_blocks; b++) { - basic_block latch; + struct loop *loop; + edge_iterator ei; /* Search the nodes of the CFG in reverse completion order so that we can find outer loops first. */ - latch = BASIC_BLOCK (rc_order[b]); + if (!TEST_BIT (headers, rc_order[b])) + continue; - /* Look for all the possible headers for this latch block. */ - for (e = latch->succ; e; e = e->succ_next) - { - basic_block header = e->dest; - - /* Look for forward edges where this block is dominated by - a successor of 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 (header != EXIT_BLOCK_PTR - && TEST_BIT (dom[latch->index], header->index)) - { - struct loop *loop; + header = BASIC_BLOCK (rc_order[b]); - loop = loops->array + num_loops; + loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop)); - loop->header = header; - loop->latch = latch; - loop->num = num_loops; + loop->header = header; + loop->num = num_loops; + num_loops++; + + /* Look for the latch for this header block. */ + FOR_EACH_EDGE (e, ei, header->preds) + { + basic_block latch = e->src; - num_loops++; + if (latch != ENTRY_BLOCK_PTR + && dominated_by_p (CDI_DOMINATORS, latch, header)) + { + loop->latch = latch; + break; } } + + flow_loop_tree_node_add (header->loop_father, loop); + loop->num_nodes = flow_loop_nodes_find (loop->header, loop); } - for (i = 0; i < num_loops; i++) + /* Assign the loop nesting depth and enclosed loop level for each + loop. */ + flow_loops_level_compute (loops); + + loops->num = num_loops; + initialize_loops_parallel_p (loops); + } + + sbitmap_free (headers); + + loops->state = 0; +#ifdef ENABLE_CHECKING + verify_flow_info (); + verify_loop_structure (loops); +#endif + + return loops->num; +} + +/* Return nonzero if basic block BB belongs to LOOP. */ +bool +flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb) +{ + struct loop *source_loop; + + if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) + return 0; + + source_loop = bb->loop_father; + return loop == source_loop || flow_loop_nested_p (loop, source_loop); +} + +/* Return nonzero if edge E enters header of LOOP from outside of LOOP. */ + +bool +flow_loop_outside_edge_p (const struct loop *loop, edge e) +{ + gcc_assert (e->dest == loop->header); + return !flow_bb_inside_loop_p (loop, e->src); +} + +/* Enumeration predicate for get_loop_body. */ +static bool +glb_enum_p (basic_block bb, void *glb_header) +{ + return bb != (basic_block) glb_header; +} + +/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs + order against direction of edges from latch. Specially, if + header != latch, latch is the 1-st block. */ +basic_block * +get_loop_body (const struct loop *loop) +{ + basic_block *tovisit, bb; + unsigned tv = 0; + + gcc_assert (loop->num_nodes); + + tovisit = xcalloc (loop->num_nodes, sizeof (basic_block)); + tovisit[tv++] = loop->header; + + if (loop->latch == EXIT_BLOCK_PTR) + { + /* There may be blocks unreachable from EXIT_BLOCK. */ + gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks + 2); + FOR_EACH_BB (bb) + tovisit[tv++] = bb; + tovisit[tv++] = EXIT_BLOCK_PTR; + } + else if (loop->latch != loop->header) + { + tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p, + tovisit + 1, loop->num_nodes - 1, + loop->header) + 1; + } + + gcc_assert (tv == loop->num_nodes); + return tovisit; +} + +/* Fills dominance descendants inside LOOP of the basic block BB into + array TOVISIT from index *TV. */ + +static void +fill_sons_in_loop (const struct loop *loop, basic_block bb, + basic_block *tovisit, int *tv) +{ + basic_block son, postpone = NULL; + + tovisit[(*tv)++] = bb; + for (son = first_dom_son (CDI_DOMINATORS, bb); + son; + son = next_dom_son (CDI_DOMINATORS, son)) + { + if (!flow_bb_inside_loop_p (loop, son)) + continue; + + if (dominated_by_p (CDI_DOMINATORS, loop->latch, son)) { - struct loop *loop = &loops->array[i]; - - /* Keep track of blocks that are loop headers so - that we can tell which loops should be merged. */ - if (TEST_BIT (headers, loop->header->index)) - SET_BIT (loops->shared_headers, loop->header->index); - SET_BIT (headers, loop->header->index); - - /* Find nodes contained within the loop. */ - loop->nodes = sbitmap_alloc (last_basic_block); - loop->num_nodes - = flow_loop_nodes_find (loop->header, loop->latch, loop->nodes); - - /* Compute first and last blocks within the loop. - These are often the same as the loop header and - loop latch respectively, but this is not always - the case. */ - loop->first - = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes)); - loop->last - = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes)); - - flow_loop_scan (loops, loop, flags); + postpone = son; + continue; } + fill_sons_in_loop (loop, son, tovisit, tv); + } + + if (postpone) + fill_sons_in_loop (loop, postpone, tovisit, tv); +} + +/* Gets body of a LOOP (that must be different from the outermost loop) + sorted by dominance relation. Additionally, if a basic block s dominates + the latch, then only blocks dominated by s are be after it. */ + +basic_block * +get_loop_body_in_dom_order (const struct loop *loop) +{ + basic_block *tovisit; + int tv; + + gcc_assert (loop->num_nodes); + + tovisit = xcalloc (loop->num_nodes, sizeof (basic_block)); + + gcc_assert (loop->latch != EXIT_BLOCK_PTR); + + tv = 0; + fill_sons_in_loop (loop, loop->header, tovisit, &tv); + + gcc_assert (tv == (int) loop->num_nodes); + + return tovisit; +} + +/* Get body of a LOOP in breadth first sort order. */ + +basic_block * +get_loop_body_in_bfs_order (const struct loop *loop) +{ + basic_block *blocks; + basic_block bb; + bitmap visited; + unsigned int i = 0; + unsigned int vc = 1; - /* 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; + gcc_assert (loop->num_nodes); + gcc_assert (loop->latch != EXIT_BLOCK_PTR); - sbitmap_free (headers); + blocks = xcalloc (loop->num_nodes, sizeof (basic_block)); + visited = BITMAP_ALLOC (NULL); + + bb = loop->header; + while (i < loop->num_nodes) + { + edge e; + edge_iterator ei; + + if (!bitmap_bit_p (visited, bb->index)) + { + /* This basic block is now visited */ + bitmap_set_bit (visited, bb->index); + blocks[i++] = bb; + } + + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (flow_bb_inside_loop_p (loop, e->dest)) + { + if (!bitmap_bit_p (visited, e->dest->index)) + { + bitmap_set_bit (visited, e->dest->index); + blocks[i++] = e->dest; + } + } + } + + gcc_assert (i >= vc); + + bb = blocks[vc++]; } - else - sbitmap_vector_free (dom); + + BITMAP_FREE (visited); + return blocks; +} - loops->num = num_loops; +/* Gets exit edges of a LOOP, returning their number in N_EDGES. */ +edge * +get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges) +{ + edge *edges, e; + unsigned i, n; + basic_block * body; + edge_iterator ei; + + gcc_assert (loop->latch != EXIT_BLOCK_PTR); + + body = get_loop_body (loop); + n = 0; + for (i = 0; i < loop->num_nodes; i++) + FOR_EACH_EDGE (e, ei, body[i]->succs) + if (!flow_bb_inside_loop_p (loop, e->dest)) + n++; + edges = xmalloc (n * sizeof (edge)); + *n_edges = n; + n = 0; + for (i = 0; i < loop->num_nodes; i++) + FOR_EACH_EDGE (e, ei, body[i]->succs) + if (!flow_bb_inside_loop_p (loop, e->dest)) + edges[n++] = e; + free (body); + + return edges; +} + +/* Counts the number of conditional branches inside LOOP. */ - /* Build the loop hierarchy tree. */ - flow_loops_tree_build (loops); +unsigned +num_loop_branches (const struct loop *loop) +{ + unsigned i, n; + basic_block * body; - /* Assign the loop nesting depth and enclosed loop level for each - loop. */ - loops->levels = flow_loops_level_compute (loops); + gcc_assert (loop->latch != EXIT_BLOCK_PTR); - return num_loops; + body = get_loop_body (loop); + n = 0; + for (i = 0; i < loop->num_nodes; i++) + if (EDGE_COUNT (body[i]->succs) >= 2) + n++; + free (body); + + return n; } -/* Update the information regarding the loops in the CFG - specified by LOOPS. */ +/* Adds basic block BB to LOOP. */ +void +add_bb_to_loop (basic_block bb, struct loop *loop) +{ + int i; + + bb->loop_father = loop; + bb->loop_depth = loop->depth; + loop->num_nodes++; + for (i = 0; i < loop->depth; i++) + loop->pred[i]->num_nodes++; + } -int -flow_loops_update (loops, flags) - struct loops *loops; - int flags; +/* Remove basic block BB from loops. */ +void +remove_bb_from_loops (basic_block bb) +{ + int i; + struct loop *loop = bb->loop_father; + + loop->num_nodes--; + for (i = 0; i < loop->depth; i++) + loop->pred[i]->num_nodes--; + bb->loop_father = NULL; + bb->loop_depth = 0; +} + +/* Finds nearest common ancestor in loop tree for given loops. */ +struct loop * +find_common_loop (struct loop *loop_s, struct loop *loop_d) { - /* One day we may want to update the current loop data. For now - throw away the old stuff and rebuild what we need. */ - if (loops->array) - flow_loops_free (loops); + if (!loop_s) return loop_d; + if (!loop_d) return loop_s; + + if (loop_s->depth < loop_d->depth) + loop_d = loop_d->pred[loop_s->depth]; + else if (loop_s->depth > loop_d->depth) + loop_s = loop_s->pred[loop_d->depth]; - return flow_loops_find (loops, flags); + while (loop_s != loop_d) + { + loop_s = loop_s->outer; + loop_d = loop_d->outer; + } + return loop_s; } -/* Return non-zero if edge E enters header of LOOP from outside of LOOP. */ +/* Cancels the LOOP; it must be innermost one. */ +void +cancel_loop (struct loops *loops, struct loop *loop) +{ + basic_block *bbs; + unsigned i; -int -flow_loop_outside_edge_p (loop, e) - const struct loop *loop; - edge e; + gcc_assert (!loop->inner); + + /* Move blocks up one level (they should be removed as soon as possible). */ + bbs = get_loop_body (loop); + for (i = 0; i < loop->num_nodes; i++) + bbs[i]->loop_father = loop->outer; + + /* Remove the loop from structure. */ + flow_loop_tree_node_remove (loop); + + /* Remove loop from loops array. */ + loops->parray[loop->num] = NULL; + + /* Free loop data. */ + flow_loop_free (loop); +} + +/* Cancels LOOP and all its subloops. */ +void +cancel_loop_tree (struct loops *loops, struct loop *loop) { - if (e->dest != loop->header) - abort (); + while (loop->inner) + cancel_loop_tree (loops, loop->inner); + cancel_loop (loops, loop); +} - return (e->src == ENTRY_BLOCK_PTR) - || ! TEST_BIT (loop->nodes, e->src->index); +/* Checks that LOOPS are all right: + -- sizes of loops are all right + -- results of get_loop_body really belong to the loop + -- loop header have just single entry edge and single latch edge + -- loop latches have only single successor that is header of their loop + -- irreducible loops are correctly marked + */ +void +verify_loop_structure (struct loops *loops) +{ + unsigned *sizes, i, j; + sbitmap irreds; + basic_block *bbs, bb; + struct loop *loop; + int err = 0; + edge e; + + /* Check sizes. */ + sizes = xcalloc (loops->num, sizeof (int)); + sizes[0] = 2; + + FOR_EACH_BB (bb) + for (loop = bb->loop_father; loop; loop = loop->outer) + sizes[loop->num]++; + + for (i = 0; i < loops->num; i++) + { + if (!loops->parray[i]) + continue; + + if (loops->parray[i]->num_nodes != sizes[i]) + { + error ("Size of loop %d should be %d, not %d.", + i, sizes[i], loops->parray[i]->num_nodes); + err = 1; + } + } + + /* Check get_loop_body. */ + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + if (!loop) + continue; + bbs = get_loop_body (loop); + + for (j = 0; j < loop->num_nodes; j++) + if (!flow_bb_inside_loop_p (loop, bbs[j])) + { + error ("Bb %d do not belong to loop %d.", + bbs[j]->index, i); + err = 1; + } + free (bbs); + } + + /* Check headers and latches. */ + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + if (!loop) + continue; + + if ((loops->state & LOOPS_HAVE_PREHEADERS) + && EDGE_COUNT (loop->header->preds) != 2) + { + error ("Loop %d's header does not have exactly 2 entries.", i); + err = 1; + } + if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES) + { + if (!single_succ_p (loop->latch)) + { + error ("Loop %d's latch does not have exactly 1 successor.", i); + err = 1; + } + if (single_succ (loop->latch) != loop->header) + { + error ("Loop %d's latch does not have header as successor.", i); + err = 1; + } + if (loop->latch->loop_father != loop) + { + error ("Loop %d's latch does not belong directly to it.", i); + err = 1; + } + } + if (loop->header->loop_father != loop) + { + error ("Loop %d's header does not belong directly to it.", i); + err = 1; + } + if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) + && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) + { + error ("Loop %d's latch is marked as part of irreducible region.", i); + err = 1; + } + } + + /* Check irreducible loops. */ + if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) + { + /* Record old info. */ + irreds = sbitmap_alloc (last_basic_block); + FOR_EACH_BB (bb) + { + edge_iterator ei; + if (bb->flags & BB_IRREDUCIBLE_LOOP) + SET_BIT (irreds, bb->index); + else + RESET_BIT (irreds, bb->index); + FOR_EACH_EDGE (e, ei, bb->succs) + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + e->flags |= EDGE_ALL_FLAGS + 1; + } + + /* Recount it. */ + mark_irreducible_loops (loops); + + /* Compare. */ + FOR_EACH_BB (bb) + { + edge_iterator ei; + + if ((bb->flags & BB_IRREDUCIBLE_LOOP) + && !TEST_BIT (irreds, bb->index)) + { + error ("Basic block %d should be marked irreducible.", bb->index); + err = 1; + } + else if (!(bb->flags & BB_IRREDUCIBLE_LOOP) + && TEST_BIT (irreds, bb->index)) + { + error ("Basic block %d should not be marked irreducible.", bb->index); + err = 1; + } + FOR_EACH_EDGE (e, ei, bb->succs) + { + if ((e->flags & EDGE_IRREDUCIBLE_LOOP) + && !(e->flags & (EDGE_ALL_FLAGS + 1))) + { + error ("Edge from %d to %d should be marked irreducible.", + e->src->index, e->dest->index); + err = 1; + } + else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP) + && (e->flags & (EDGE_ALL_FLAGS + 1))) + { + error ("Edge from %d to %d should not be marked irreducible.", + e->src->index, e->dest->index); + err = 1; + } + e->flags &= ~(EDGE_ALL_FLAGS + 1); + } + } + free (irreds); + } + + /* Check the single_exit. */ + if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) + { + memset (sizes, 0, sizeof (unsigned) * loops->num); + FOR_EACH_BB (bb) + { + edge_iterator ei; + if (bb->loop_father == loops->tree_root) + continue; + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (e->dest == EXIT_BLOCK_PTR) + continue; + + if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) + continue; + + for (loop = bb->loop_father; + loop != e->dest->loop_father; + loop = loop->outer) + { + sizes[loop->num]++; + if (loop->single_exit + && loop->single_exit != e) + { + error ("Wrong single exit %d->%d recorded for loop %d.", + loop->single_exit->src->index, + loop->single_exit->dest->index, + loop->num); + error ("Right exit is %d->%d.", + e->src->index, e->dest->index); + err = 1; + } + } + } + } + + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + if (!loop) + continue; + + if (sizes[i] == 1 + && !loop->single_exit) + { + error ("Single exit not recorded for loop %d.", loop->num); + err = 1; + } + + if (sizes[i] != 1 + && loop->single_exit) + { + error ("Loop %d should not have single exit (%d -> %d).", + loop->num, + loop->single_exit->src->index, + loop->single_exit->dest->index); + err = 1; + } + } + } + + gcc_assert (!err); + + free (sizes); +} + +/* Returns latch edge of LOOP. */ +edge +loop_latch_edge (const struct loop *loop) +{ + return find_edge (loop->latch, loop->header); +} + +/* Returns preheader edge of LOOP. */ +edge +loop_preheader_edge (const struct loop *loop) +{ + edge e; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, loop->header->preds) + if (e->src != loop->latch) + break; + + return e; +} + +/* Returns true if E is an exit of LOOP. */ + +bool +loop_exit_edge_p (const struct loop *loop, edge e) +{ + return (flow_bb_inside_loop_p (loop, e->src) + && !flow_bb_inside_loop_p (loop, e->dest)); }