X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Fcfgloop.c;h=0e95323008a3ee1420c432d60d5f90797a839ead;hp=26a9cdee8986076a13f74c718c862c3346626186;hb=e1ab78748da58d43da7f08cc64b9de80577f470e;hpb=9585423d4580309499a933f64af0496f2005a990 diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 26a9cdee898..0e95323008a 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -1,11 +1,12 @@ /* Natural loop discovery code for GNU compiler. - Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007 + Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -14,9 +15,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -25,41 +25,27 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "rtl.h" #include "hard-reg-set.h" #include "obstack.h" +#include "function.h" #include "basic-block.h" #include "toplev.h" #include "cfgloop.h" #include "flags.h" #include "tree.h" #include "tree-flow.h" +#include "pointer-set.h" +#include "output.h" +#include "ggc.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 void flow_loop_entry_edges_find (struct loop *); -static void flow_loop_exit_edges_find (struct loop *); -static int flow_loop_nodes_find (basic_block, struct loop *); -static void flow_loop_pre_header_scan (struct loop *); -static basic_block flow_loop_pre_header_find (basic_block); -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 *); +static void flow_loops_cfg_dump (FILE *); /* Dump loop related CFG information. */ static void -flow_loops_cfg_dump (const struct loops *loops, FILE *file) +flow_loops_cfg_dump (FILE *file) { - int i; basic_block bb; - if (! loops->num || ! file) + if (!file) return; FOR_EACH_BB (bb) @@ -72,26 +58,6 @@ flow_loops_cfg_dump (const struct loops *loops, FILE *file) fprintf (file, "%d ", succ->dest->index); fprintf (file, "}\n"); } - - /* 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); - } - - /* 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); - } } /* Return nonzero if the nodes of LOOP are a subset of OUTER. */ @@ -99,8 +65,10 @@ flow_loops_cfg_dump (const struct loops *loops, FILE *file) bool flow_loop_nested_p (const struct loop *outer, const struct loop *loop) { - return (loop->depth > outer->depth - && loop->pred[outer->depth] == outer); + unsigned odepth = loop_depth (outer); + + return (loop_depth (loop) > odepth + && VEC_index (loop_p, loop->superloops, odepth) == outer); } /* Returns the loop such that LOOP is nested DEPTH (indexed from zero) @@ -109,12 +77,32 @@ flow_loop_nested_p (const struct loop *outer, const struct loop *loop) struct loop * superloop_at_depth (struct loop *loop, unsigned depth) { - gcc_assert (depth <= (unsigned) loop->depth); + unsigned ldepth = loop_depth (loop); - if (depth == (unsigned) loop->depth) + gcc_assert (depth <= ldepth); + + if (depth == ldepth) return loop; - return loop->pred[depth]; + return VEC_index (loop_p, loop->superloops, depth); +} + +/* Returns the list of the latch edges of LOOP. */ + +static VEC (edge, heap) * +get_loop_latch_edges (const struct loop *loop) +{ + edge_iterator ei; + edge e; + VEC (edge, heap) *ret = NULL; + + FOR_EACH_EDGE (e, ei, loop->header->preds) + { + if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header)) + VEC_safe_push (edge, heap, ret, e); + } + + return ret; } /* Dump the loop information specified by LOOP to the stream FILE @@ -127,81 +115,87 @@ flow_loop_dump (const struct loop *loop, FILE *file, { basic_block *bbs; unsigned i; + VEC (edge, heap) *latches; + edge e; if (! loop || ! loop->header) return; - fprintf (file, ";;\n;; Loop %d:%s\n", loop->num, - loop->invalid ? " invalid" : ""); + fprintf (file, ";;\n;; Loop %d\n", loop->num); - fprintf (file, ";; header %d, latch %d, pre-header %d\n", - loop->header->index, loop->latch->index, - loop->pre_header ? loop->pre_header->index : -1); - fprintf (file, ";; depth %d, level %d, outer %ld\n", - loop->depth, loop->level, - (long) (loop->outer ? loop->outer->num : -1)); + fprintf (file, ";; header %d, ", loop->header->index); + if (loop->latch) + fprintf (file, "latch %d\n", loop->latch->index); + else + { + fprintf (file, "multiple latches:"); + latches = get_loop_latch_edges (loop); + for (i = 0; VEC_iterate (edge, latches, i, e); i++) + fprintf (file, " %d", e->src->index); + VEC_free (edge, heap, latches); + fprintf (file, "\n"); + } - if (loop->pre_header_edges) - flow_edge_list_print (";; pre-header edges", loop->pre_header_edges, - loop->num_pre_header_edges, file); + fprintf (file, ";; depth %d, outer %ld\n", + loop_depth (loop), (long) (loop_outer (loop) + ? loop_outer (loop)->num : -1)); - flow_edge_list_print (";; entry edges", loop->entry_edges, - loop->num_entries, 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"); - flow_edge_list_print (";; exit edges", loop->exit_edges, - loop->num_exits, file); if (loop_dump_aux) loop_dump_aux (loop, file, verbose); } -/* Dump the loop information specified by LOOPS to the stream FILE, +/* Dump the loop information about loops to the stream FILE, using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ void -flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) +flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) { - int i; - int num_loops; + loop_iterator li; + struct loop *loop; - num_loops = loops->num; - if (! num_loops || ! file) + if (!current_loops || ! file) return; - fprintf (file, ";; %d loops found\n", num_loops); + fprintf (file, ";; %d loops found\n", number_of_loops ()); - for (i = 0; i < num_loops; i++) + FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT) { - struct loop *loop = loops->parray[i]; - - if (!loop) - continue; - flow_loop_dump (loop, file, loop_dump_aux, verbose); } if (verbose) - flow_loops_cfg_dump (loops, file); + flow_loops_cfg_dump (file); } /* Free data allocated for LOOP. */ + void flow_loop_free (struct loop *loop) { - if (loop->pre_header_edges) - free (loop->pre_header_edges); - if (loop->entry_edges) - free (loop->entry_edges); - if (loop->exit_edges) - free (loop->exit_edges); - if (loop->pred) - free (loop->pred); - free (loop); + struct loop_exit *exit, *next; + + VEC_free (loop_p, gc, loop->superloops); + + /* Break the list of the loop exit records. They will be freed when the + corresponding edge is rescanned or removed, and this avoids + accessing the (already released) head of the list stored in the + loop structure. */ + for (exit = loop->exits->next; exit != loop->exits; exit = next) + { + next = exit->next; + exit->next = exit; + exit->prev = exit; + } + + ggc_free (loop->exits); + ggc_free (loop); } /* Free all the memory allocated for LOOPS. */ @@ -209,315 +203,95 @@ flow_loop_free (struct loop *loop) void flow_loops_free (struct loops *loops) { - if (loops->parray) + if (loops->larray) { unsigned i; - - gcc_assert (loops->num); + loop_p loop; /* Free the loop descriptors. */ - for (i = 0; i < loops->num; i++) + for (i = 0; VEC_iterate (loop_p, loops->larray, i, loop); i++) { - struct loop *loop = loops->parray[i]; - if (!loop) continue; flow_loop_free (loop); } - 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); - - } -} - -/* Find the entry edges into the LOOP. */ - -static void -flow_loop_entry_edges_find (struct loop *loop) -{ - edge e; - edge_iterator ei; - int num_entries; - - num_entries = 0; - FOR_EACH_EDGE (e, ei, loop->header->preds) - { - if (flow_loop_outside_edge_p (loop, e)) - num_entries++; - } - - gcc_assert (num_entries); - - loop->entry_edges = xmalloc (num_entries * sizeof (edge *)); - - num_entries = 0; - FOR_EACH_EDGE (e, ei, loop->header->preds) - { - if (flow_loop_outside_edge_p (loop, e)) - loop->entry_edges[num_entries++] = e; - } - - loop->num_entries = num_entries; -} - -/* Find the exit edges from the LOOP. */ - -static void -flow_loop_exit_edges_find (struct loop *loop) -{ - edge e; - basic_block node, *bbs; - unsigned num_exits, i; - - loop->exit_edges = NULL; - loop->num_exits = 0; - - /* 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; - bbs = get_loop_body (loop); - for (i = 0; i < loop->num_nodes; i++) - { - edge_iterator ei; - node = bbs[i]; - FOR_EACH_EDGE (e, ei, node->succs) - { - basic_block dest = e->dest; - - if (!flow_bb_inside_loop_p (loop, dest)) - num_exits++; - } - } - - if (! num_exits) - { - free (bbs); - return; - } - - loop->exit_edges = xmalloc (num_exits * sizeof (edge *)); - - /* Store all exiting edges into an array. */ - num_exits = 0; - for (i = 0; i < loop->num_nodes; i++) - { - edge_iterator ei; - node = bbs[i]; - FOR_EACH_EDGE (e, ei, node->succs) - { - basic_block dest = e->dest; - - if (!flow_bb_inside_loop_p (loop, dest)) - { - e->flags |= EDGE_LOOP_EXIT; - loop->exit_edges[num_exits++] = e; - } - } + VEC_free (loop_p, gc, loops->larray); } - free (bbs); - loop->num_exits = num_exits; } /* Find the nodes contained within the LOOP with header HEADER. Return the number of nodes within the loop. */ -static int +int flow_loop_nodes_find (basic_block header, struct loop *loop) { - basic_block *stack; - int sp; + VEC (basic_block, heap) *stack = NULL; int num_nodes = 1; + edge latch; + edge_iterator latch_ei; + unsigned depth = loop_depth (loop); header->loop_father = loop; - header->loop_depth = loop->depth; + header->loop_depth = depth; - if (loop->latch->loop_father != loop) + FOR_EACH_EDGE (latch, latch_ei, loop->header->preds) { - stack = xmalloc (n_basic_blocks * sizeof (basic_block)); - sp = 0; + if (latch->src->loop_father == loop + || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header)) + continue; + num_nodes++; - stack[sp++] = loop->latch; - loop->latch->loop_father = loop; - loop->latch->loop_depth = loop->depth; + VEC_safe_push (basic_block, heap, stack, latch->src); + latch->src->loop_father = loop; + latch->src->loop_depth = depth; - while (sp) + while (!VEC_empty (basic_block, stack)) { basic_block node; edge e; edge_iterator ei; - node = stack[--sp]; + node = VEC_pop (basic_block, stack); FOR_EACH_EDGE (e, ei, node->preds) { basic_block ancestor = e->src; - if (ancestor != ENTRY_BLOCK_PTR - && ancestor->loop_father != loop) + if (ancestor->loop_father != loop) { ancestor->loop_father = loop; - ancestor->loop_depth = loop->depth; + ancestor->loop_depth = depth; num_nodes++; - stack[sp++] = ancestor; + VEC_safe_push (basic_block, heap, stack, ancestor); } } } - free (stack); - } - return num_nodes; -} - -/* For each loop in the lOOPS tree that has just a single exit - record the exit edge. */ - -void -mark_single_exit_loops (struct loops *loops) -{ - basic_block bb; - edge e; - struct loop *loop; - unsigned i; - - for (i = 1; i < loops->num; i++) - { - loop = loops->parray[i]; - if (loop) - loop->single_exit = NULL; - } - - 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) - { - /* 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 = EDGE_SUCC (ENTRY_BLOCK_PTR, 0); - else - loop->single_exit = e; - } - } - } - - for (i = 1; i < loops->num; i++) - { - loop = loops->parray[i]; - if (!loop) - continue; - - if (loop->single_exit == EDGE_SUCC (ENTRY_BLOCK_PTR, 0)) - loop->single_exit = NULL; } + VEC_free (basic_block, heap, stack); - loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS; -} - -/* 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 (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; - EDGE_PRED (ebb, 0)->src != ENTRY_BLOCK_PTR && EDGE_COUNT (ebb->preds) == 1; - num++) - ebb = EDGE_PRED (ebb, 0)->src; - - loop->pre_header_edges = xmalloc (num * sizeof (edge)); - loop->num_pre_header_edges = num; - - /* 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 = EDGE_PRED (e->src, 0)) - loop->pre_header_edges[--num] = e; + return num_nodes; } -/* Return the block for the pre-header of the loop with header - HEADER. Return NULL if there is no pre-header. */ - -static basic_block -flow_loop_pre_header_find (basic_block header) -{ - basic_block pre_header; - edge e; - edge_iterator ei; - - /* 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_EACH_EDGE (e, ei, header->preds) - { - basic_block node = e->src; - - if (node != ENTRY_BLOCK_PTR - && ! dominated_by_p (CDI_DOMINATORS, node, header)) - { - 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; -} +/* Records the vector of superloops of the loop LOOP, whose immediate + superloop is FATHER. */ static void -establish_preds (struct loop *loop) +establish_preds (struct loop *loop, struct loop *father) { - struct loop *ploop, *father = loop->outer; + loop_p ploop; + unsigned depth = loop_depth (father) + 1; + unsigned i; - loop->depth = father->depth + 1; - 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; + VEC_truncate (loop_p, loop->superloops, 0); + VEC_reserve (loop_p, gc, loop->superloops, depth); + for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++) + VEC_quick_push (loop_p, loop->superloops, ploop); + VEC_quick_push (loop_p, loop->superloops, father); for (ploop = loop->inner; ploop; ploop = ploop->next) - establish_preds (ploop); + establish_preds (ploop, loop); } /* Add LOOP to the loop hierarchy tree where FATHER is father of the @@ -529,9 +303,8 @@ flow_loop_tree_node_add (struct loop *father, struct loop *loop) { loop->next = father->inner; father->inner = loop; - loop->outer = father; - establish_preds (loop); + establish_preds (loop, father); } /* Remove LOOP from the loop hierarchy tree. */ @@ -541,268 +314,64 @@ flow_loop_tree_node_remove (struct loop *loop) { struct loop *prev, *father; - father = loop->outer; - loop->outer = NULL; + father = loop_outer (loop); /* 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); + for (prev = father->inner; prev->next != loop; prev = prev->next) + continue; prev->next = loop->next; } - 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. Returns the loop level. */ - -static int -flow_loop_level_compute (struct loop *loop) -{ - struct loop *inner; - int level = 1; - - 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 (including - itself). */ - for (inner = loop->inner; inner; inner = inner->next) - { - int ilevel = flow_loop_level_compute (inner) + 1; - - if (ilevel > level) - level = ilevel; - } - - loop->level = level; - return level; + VEC_truncate (loop_p, loop->superloops, 0); } -/* Compute the loop nesting depth and enclosed loop level for the loop - hierarchy tree specified by LOOPS. Return the maximum enclosed loop - level. */ +/* Allocates and returns new loop structure. */ -static void -flow_loops_level_compute (struct loops *loops) -{ - flow_loop_level_compute (loops->tree_root); -} - -/* Scan a single natural loop specified by LOOP collecting information - about it specified by FLAGS. */ - -int -flow_loop_scan (struct loop *loop, int flags) -{ - 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. */ - flow_loop_entry_edges_find (loop); - } - - if (flags & LOOP_EXIT_EDGES) - { - /* Find edges which exit the loop. */ - flow_loop_exit_edges_find (loop); - } - - if (flags & LOOP_PRE_HEADER) - { - /* Look to see if the loop has a pre-header node. */ - loop->pre_header = flow_loop_pre_header_find (loop->header); - - /* Find the blocks within the extended basic block of - the loop pre-header. */ - flow_loop_pre_header_scan (loop); - } - - return 1; -} - -/* 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 (EDGE_PRED (jump, 0), sizeof (int)); - LATCH_EDGE (EDGE_PRED (jump, 0)) = 0; - set_immediate_dominator (CDI_DOMINATORS, jump, EDGE_PRED (jump, 0)->src); -} - -/* 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) +struct loop * +alloc_loop (void) { - return e != mfb_kj_edge; -} + struct loop *loop = GGC_CNEW (struct loop); -/* 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. */ + loop->exits = GGC_CNEW (struct loop_exit); + loop->exits->next = loop->exits->prev = loop->exits; -static bool -mfb_keep_nonlatch (edge e) -{ - return LATCH_EDGE (e); + return loop; } -/* Takes care of merging natural loops with shared headers. */ +/* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops + (including the root of the loop tree). */ static void -canonicalize_loop_headers (void) +init_loops_structure (struct loops *loops, unsigned num_loops) { - 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) - { - 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 (HEADER_BLOCK (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest)) - { - 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 (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)); - - alloc_aux_for_edge (EDGE_SUCC (bb, 0), sizeof (int)); - LATCH_EDGE (EDGE_SUCC (bb, 0)) = 0; - alloc_aux_for_block (bb, sizeof (int)); - HEADER_BLOCK (bb) = 0; - } - - 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 (); + struct loop *root; -#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; + memset (loops, 0, sizeof *loops); + loops->larray = VEC_alloc (loop_p, gc, num_loops); - for (i = 0; i < loops->num; i++) - { - struct loop *loop = loops->parray[i]; - loop->parallel_p = true; - } + /* Dummy loop containing whole function. */ + root = alloc_loop (); + root->num_nodes = n_basic_blocks; + root->latch = EXIT_BLOCK_PTR; + root->header = ENTRY_BLOCK_PTR; + ENTRY_BLOCK_PTR->loop_father = root; + EXIT_BLOCK_PTR->loop_father = root; + + VEC_quick_push (loop_p, loops->larray, root); + loops->tree_root = root; } /* 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 (struct loops *loops, int flags) +flow_loops_find (struct loops *loops) { - int i; int b; int num_loops; edge e; @@ -812,27 +381,20 @@ flow_loops_find (struct loops *loops, int flags) basic_block header; basic_block bb; - /* 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. */ - gcc_assert (flags & LOOP_TREE); - - memset (loops, 0, sizeof *loops); + /* Ensure that the dominators are computed. */ + calculate_dominance_info (CDI_DOMINATORS); /* Taking care of this degenerate case makes the rest of this code simpler. */ - if (n_basic_blocks == 0) - return 0; + if (n_basic_blocks == NUM_FIXED_BLOCKS) + { + init_loops_structure (loops, 1); + return 1; + } dfs_order = NULL; rc_order = NULL; - /* Ensure that the dominators are computed. */ - calculate_dominance_info (CDI_DOMINATORS); - - /* Join loops with shared headers. */ - canonicalize_loop_headers (); - /* Count the number of loop headers. This should be the same as the number of natural loops. */ headers = sbitmap_alloc (last_basic_block); @@ -842,7 +404,6 @@ flow_loops_find (struct loops *loops, int flags) FOR_EACH_BB (header) { edge_iterator ei; - int more_latches = 0; header->loop_depth = 0; @@ -869,8 +430,6 @@ flow_loops_find (struct loops *loops, int flags) && 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++; } @@ -878,26 +437,10 @@ flow_loops_find (struct loops *loops, int flags) } /* 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]; + init_loops_structure (loops, num_loops + 1); /* 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; @@ -905,17 +448,13 @@ flow_loops_find (struct loops *loops, int flags) { /* Compute depth first search order of the CFG so that outer natural loops will be found before inner natural loops. */ - 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.dfs_order = dfs_order; - loops->cfg.rc_order = rc_order; + dfs_order = XNEWVEC (int, n_basic_blocks); + rc_order = XNEWVEC (int, n_basic_blocks); + pre_and_rev_post_order_compute (dfs_order, rc_order, false); num_loops = 1; - for (b = 0; b < n_basic_blocks; b++) + for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++) { struct loop *loop; edge_iterator ei; @@ -927,55 +466,309 @@ flow_loops_find (struct loops *loops, int flags) header = BASIC_BLOCK (rc_order[b]); - loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop)); + loop = alloc_loop (); + VEC_quick_push (loop_p, loops->larray, loop); loop->header = header; loop->num = num_loops; num_loops++; - /* Look for the latch for this header block. */ + flow_loop_tree_node_add (header->loop_father, loop); + loop->num_nodes = flow_loop_nodes_find (loop->header, loop); + + /* Look for the latch for this header block, if it has just a + single one. */ FOR_EACH_EDGE (e, ei, header->preds) { basic_block latch = e->src; - if (latch != ENTRY_BLOCK_PTR - && dominated_by_p (CDI_DOMINATORS, latch, header)) + if (flow_bb_inside_loop_p (loop, latch)) { + if (loop->latch != NULL) + { + /* More than one latch edge. */ + loop->latch = NULL; + break; + } loop->latch = latch; - break; } } + } - flow_loop_tree_node_add (header->loop_father, loop); - loop->num_nodes = flow_loop_nodes_find (loop->header, loop); + free (dfs_order); + free (rc_order); + } + + sbitmap_free (headers); + + loops->exits = NULL; + return VEC_length (loop_p, loops->larray); +} + +/* 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 + +/* Minimum number of samples for that we apply + find_subloop_latch_edge_by_profile heuristics. */ +#define HEAVY_EDGE_MIN_SAMPLES 10 + +/* If the profile info is available, finds an edge in LATCHES that much more + frequent than the remaining edges. Returns such an edge, or NULL if we do + not find one. + + We do not use guessed profile here, only the measured one. The guessed + profile is usually too flat and unreliable for this (and it is mostly based + on the loop structure of the program, so it does not make much sense to + derive the loop structure from it). */ + +static edge +find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches) +{ + unsigned i; + edge e, me = NULL; + gcov_type mcount = 0, tcount = 0; + + for (i = 0; VEC_iterate (edge, latches, i, e); i++) + { + if (e->count > mcount) + { + me = e; + mcount = e->count; } + tcount += e->count; + } + + if (tcount < HEAVY_EDGE_MIN_SAMPLES + || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount) + return NULL; + + if (dump_file) + fprintf (dump_file, + "Found latch edge %d -> %d using profile information.\n", + me->src->index, me->dest->index); + return me; +} + +/* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based + on the structure of induction variables. Returns this edge, or NULL if we + do not find any. + + We are quite conservative, and look just for an obvious simple innermost + loop (which is the case where we would lose the most performance by not + disambiguating the loop). More precisely, we look for the following + situation: The source of the chosen latch edge dominates sources of all + the other latch edges. Additionally, the header does not contain a phi node + such that the argument from the chosen edge is equal to the argument from + another edge. */ + +static edge +find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, VEC (edge, heap) *latches) +{ + edge e, latch = VEC_index (edge, latches, 0); + unsigned i; + gimple phi; + gimple_stmt_iterator psi; + tree lop; + basic_block bb; + + /* Find the candidate for the latch edge. */ + for (i = 1; VEC_iterate (edge, latches, i, e); i++) + if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src)) + latch = e; + + /* Verify that it dominates all the latch edges. */ + for (i = 0; VEC_iterate (edge, latches, i, e); i++) + if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src)) + return NULL; + + /* Check for a phi node that would deny that this is a latch edge of + a subloop. */ + for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) + { + phi = gsi_stmt (psi); + lop = PHI_ARG_DEF_FROM_EDGE (phi, latch); + + /* Ignore the values that are not changed inside the subloop. */ + if (TREE_CODE (lop) != SSA_NAME + || SSA_NAME_DEF_STMT (lop) == phi) + continue; + bb = gimple_bb (SSA_NAME_DEF_STMT (lop)); + if (!bb || !flow_bb_inside_loop_p (loop, bb)) + continue; + + for (i = 0; VEC_iterate (edge, latches, i, e); i++) + if (e != latch + && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop) + return NULL; + } + + if (dump_file) + fprintf (dump_file, + "Found latch edge %d -> %d using iv structure.\n", + latch->src->index, latch->dest->index); + return latch; +} + +/* If we can determine that one of the several latch edges of LOOP behaves + as a latch edge of a separate subloop, returns this edge. Otherwise + returns NULL. */ + +static edge +find_subloop_latch_edge (struct loop *loop) +{ + VEC (edge, heap) *latches = get_loop_latch_edges (loop); + edge latch = NULL; + + if (VEC_length (edge, latches) > 1) + { + latch = find_subloop_latch_edge_by_profile (latches); + + if (!latch + /* We consider ivs to guess the latch edge only in SSA. Perhaps we + should use cfghook for this, but it is hard to imagine it would + be useful elsewhere. */ + && current_ir_type () == IR_GIMPLE) + latch = find_subloop_latch_edge_by_ivs (loop, latches); + } + + VEC_free (edge, heap, latches); + return latch; +} + +/* Callback for make_forwarder_block. Returns true if the edge E is marked + in the set MFB_REIS_SET. */ + +static struct pointer_set_t *mfb_reis_set; +static bool +mfb_redirect_edges_in_set (edge e) +{ + return pointer_set_contains (mfb_reis_set, e); +} + +/* Creates a subloop of LOOP with latch edge LATCH. */ + +static void +form_subloop (struct loop *loop, edge latch) +{ + edge_iterator ei; + edge e, new_entry; + struct loop *new_loop; + + mfb_reis_set = pointer_set_create (); + FOR_EACH_EDGE (e, ei, loop->header->preds) + { + if (e != latch) + pointer_set_insert (mfb_reis_set, e); + } + new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, + NULL); + pointer_set_destroy (mfb_reis_set); + + loop->header = new_entry->src; + + /* Find the blocks and subloops that belong to the new loop, and add it to + the appropriate place in the loop tree. */ + new_loop = alloc_loop (); + new_loop->header = new_entry->dest; + new_loop->latch = latch->src; + add_loop (new_loop, loop); +} + +/* Make all the latch edges of LOOP to go to a single forwarder block -- + a new latch of LOOP. */ + +static void +merge_latch_edges (struct loop *loop) +{ + VEC (edge, heap) *latches = get_loop_latch_edges (loop); + edge latch, e; + unsigned i; + + gcc_assert (VEC_length (edge, latches) > 0); + + if (VEC_length (edge, latches) == 1) + loop->latch = VEC_index (edge, latches, 0)->src; + else + { + if (dump_file) + fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num); + + mfb_reis_set = pointer_set_create (); + for (i = 0; VEC_iterate (edge, latches, i, e); i++) + pointer_set_insert (mfb_reis_set, e); + latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, + NULL); + pointer_set_destroy (mfb_reis_set); + + loop->header = latch->dest; + loop->latch = latch->src; + } + + VEC_free (edge, heap, latches); +} - /* Assign the loop nesting depth and enclosed loop level for each - loop. */ - flow_loops_level_compute (loops); +/* LOOP may have several latch edges. Transform it into (possibly several) + loops with single latch edge. */ - /* Scan the loops. */ - for (i = 1; i < num_loops; i++) - flow_loop_scan (loops->parray[i], flags); +static void +disambiguate_multiple_latches (struct loop *loop) +{ + edge e; + + /* We eliminate the multiple latches by splitting the header to the forwarder + block F and the rest R, and redirecting the edges. There are two cases: + + 1) If there is a latch edge E that corresponds to a subloop (we guess + that based on profile -- if it is taken much more often than the + remaining edges; and on trees, using the information about induction + variables of the loops), we redirect E to R, all the remaining edges to + F, then rescan the loops and try again for the outer loop. + 2) If there is no such edge, we redirect all latch edges to F, and the + entry edges to R, thus making F the single latch of the loop. */ + + if (dump_file) + fprintf (dump_file, "Disambiguating loop %d with multiple latches\n", + loop->num); + + /* During latch merging, we may need to redirect the entry edges to a new + block. This would cause problems if the entry edge was the one from the + entry block. To avoid having to handle this case specially, split + such entry edge. */ + e = find_edge (ENTRY_BLOCK_PTR, loop->header); + if (e) + split_edge (e); + + while (1) + { + e = find_subloop_latch_edge (loop); + if (!e) + break; - loops->num = num_loops; - initialize_loops_parallel_p (loops); + form_subloop (loop, e); } - sbitmap_free (headers); + merge_latch_edges (loop); +} + +/* Split loops with multiple latch edges. */ - loops->state = 0; -#ifdef ENABLE_CHECKING - verify_flow_info (); - verify_loop_structure (loops); -#endif +void +disambiguate_loops_with_multiple_latches (void) +{ + loop_iterator li; + struct loop *loop; - return loops->num; + FOR_EACH_LOOP (li, loop, 0) + { + if (!loop->latch) + disambiguate_multiple_latches (loop); + } } /* Return nonzero if basic block BB belongs to LOOP. */ bool -flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb) +flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb) { struct loop *source_loop; @@ -986,53 +779,59 @@ flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb) 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) +/* Enumeration predicate for get_loop_body_with_size. */ +static bool +glb_enum_p (const_basic_block bb, const void *glb_loop) { - gcc_assert (e->dest == loop->header); - return !flow_bb_inside_loop_p (loop, e->src); + const struct loop *const loop = (const struct loop *) glb_loop; + return (bb != loop->header + && dominated_by_p (CDI_DOMINATORS, bb, loop->header)); } -/* Enumeration predicate for get_loop_body. */ -static bool -glb_enum_p (basic_block bb, void *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. LOOP cannot be the fake + loop tree root, and its size must be at most MAX_SIZE. The blocks + in the LOOP body are stored to BODY, and the size of the LOOP is + returned. */ + +unsigned +get_loop_body_with_size (const struct loop *loop, basic_block *body, + unsigned max_size) { - return bb != (basic_block) glb_header; + return dfs_enumerate_from (loop->header, 1, glb_enum_p, + body, max_size, loop); } /* 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; + basic_block *body, bb; unsigned tv = 0; gcc_assert (loop->num_nodes); - tovisit = xcalloc (loop->num_nodes, sizeof (basic_block)); - tovisit[tv++] = loop->header; + body = XCNEWVEC (basic_block, loop->num_nodes); if (loop->latch == EXIT_BLOCK_PTR) { - /* There may be blocks unreachable from EXIT_BLOCK. */ - gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks + 2); + /* There may be blocks unreachable from EXIT_BLOCK, hence we need to + special-case the fake loop that contains the whole function. */ + gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks); + body[tv++] = loop->header; + body[tv++] = EXIT_BLOCK_PTR; 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; + body[tv++] = bb; } + else + tv = get_loop_body_with_size (loop, body, loop->num_nodes); gcc_assert (tv == loop->num_nodes); - return tovisit; + return body; } /* Fills dominance descendants inside LOOP of the basic block BB into @@ -1076,7 +875,7 @@ get_loop_body_in_dom_order (const struct loop *loop) gcc_assert (loop->num_nodes); - tovisit = xcalloc (loop->num_nodes, sizeof (basic_block)); + tovisit = XCNEWVEC (basic_block, loop->num_nodes); gcc_assert (loop->latch != EXIT_BLOCK_PTR); @@ -1088,6 +887,19 @@ get_loop_body_in_dom_order (const struct loop *loop) return tovisit; } +/* Gets body of a LOOP sorted via provided BB_COMPARATOR. */ + +basic_block * +get_loop_body_in_custom_order (const struct loop *loop, + int (*bb_comparator) (const void *, const void *)) +{ + basic_block *bbs = get_loop_body (loop); + + qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator); + + return bbs; +} + /* Get body of a LOOP in breadth first sort order. */ basic_block * @@ -1102,68 +914,254 @@ get_loop_body_in_bfs_order (const struct loop *loop) gcc_assert (loop->num_nodes); gcc_assert (loop->latch != EXIT_BLOCK_PTR); - blocks = xcalloc (loop->num_nodes, sizeof (basic_block)); - visited = BITMAP_XMALLOC (); + blocks = XCNEWVEC (basic_block, loop->num_nodes); + 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; - } - + { + /* 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; - } - } - } - + { + 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++]; } - - BITMAP_XFREE (visited); + + BITMAP_FREE (visited); return blocks; } -/* 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) +/* Hash function for struct loop_exit. */ + +static hashval_t +loop_exit_hash (const void *ex) { - edge *edges, e; - unsigned i, n; - basic_block * body; + const struct loop_exit *const exit = (const struct loop_exit *) ex; + + return htab_hash_pointer (exit->e); +} + +/* Equality function for struct loop_exit. Compares with edge. */ + +static int +loop_exit_eq (const void *ex, const void *e) +{ + const struct loop_exit *const exit = (const struct loop_exit *) ex; + + return exit->e == e; +} + +/* Frees the list of loop exit descriptions EX. */ + +static void +loop_exit_free (void *ex) +{ + struct loop_exit *exit = (struct loop_exit *) ex, *next; + + for (; exit; exit = next) + { + next = exit->next_e; + + exit->next->prev = exit->prev; + exit->prev->next = exit->next; + + ggc_free (exit); + } +} + +/* Returns the list of records for E as an exit of a loop. */ + +static struct loop_exit * +get_exit_descriptions (edge e) +{ + return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e, + htab_hash_pointer (e)); +} + +/* Updates the lists of loop exits in that E appears. + If REMOVED is true, E is being removed, and we + just remove it from the lists of exits. + If NEW_EDGE is true and E is not a loop exit, we + do not try to remove it from loop exit lists. */ + +void +rescan_loop_exit (edge e, bool new_edge, bool removed) +{ + void **slot; + struct loop_exit *exits = NULL, *exit; + struct loop *aloop, *cloop; + + if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + return; + + if (!removed + && e->src->loop_father != NULL + && e->dest->loop_father != NULL + && !flow_bb_inside_loop_p (e->src->loop_father, e->dest)) + { + cloop = find_common_loop (e->src->loop_father, e->dest->loop_father); + for (aloop = e->src->loop_father; + aloop != cloop; + aloop = loop_outer (aloop)) + { + exit = GGC_NEW (struct loop_exit); + exit->e = e; + + exit->next = aloop->exits->next; + exit->prev = aloop->exits; + exit->next->prev = exit; + exit->prev->next = exit; + + exit->next_e = exits; + exits = exit; + } + } + + if (!exits && new_edge) + return; + + slot = htab_find_slot_with_hash (current_loops->exits, e, + htab_hash_pointer (e), + exits ? INSERT : NO_INSERT); + if (!slot) + return; + + if (exits) + { + if (*slot) + loop_exit_free (*slot); + *slot = exits; + } + else + htab_clear_slot (current_loops->exits, slot); +} + +/* For each loop, record list of exit edges, and start maintaining these + lists. */ + +void +record_loop_exits (void) +{ + basic_block bb; + edge_iterator ei; + edge e; + + if (!current_loops) + return; + + if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + return; + loops_state_set (LOOPS_HAVE_RECORDED_EXITS); + + gcc_assert (current_loops->exits == NULL); + current_loops->exits = htab_create_alloc (2 * number_of_loops (), + loop_exit_hash, + loop_exit_eq, + loop_exit_free, + ggc_calloc, ggc_free); + + FOR_EACH_BB (bb) + { + FOR_EACH_EDGE (e, ei, bb->succs) + { + rescan_loop_exit (e, true, false); + } + } +} + +/* Dumps information about the exit in *SLOT to FILE. + Callback for htab_traverse. */ + +static int +dump_recorded_exit (void **slot, void *file) +{ + struct loop_exit *exit = (struct loop_exit *) *slot; + unsigned n = 0; + edge e = exit->e; + + for (; exit != NULL; exit = exit->next_e) + n++; + + fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n", + e->src->index, e->dest->index, n); + + return 1; +} + +/* Dumps the recorded exits of loops to FILE. */ + +extern void dump_recorded_exits (FILE *); +void +dump_recorded_exits (FILE *file) +{ + if (!current_loops->exits) + return; + htab_traverse (current_loops->exits, dump_recorded_exit, file); +} + +/* Releases lists of loop exits. */ + +void +release_recorded_exits (void) +{ + gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)); + htab_delete (current_loops->exits); + current_loops->exits = NULL; + loops_state_clear (LOOPS_HAVE_RECORDED_EXITS); +} + +/* Returns the list of the exit edges of a LOOP. */ + +VEC (edge, heap) * +get_loop_exit_edges (const struct loop *loop) +{ + VEC (edge, heap) *edges = NULL; + edge e; + unsigned i; + basic_block *body; edge_iterator ei; + struct loop_exit *exit; 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); + /* If we maintain the lists of exits, use them. Otherwise we must + scan the body of the loop. */ + if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + { + for (exit = loop->exits->next; exit->e; exit = exit->next) + VEC_safe_push (edge, heap, edges, exit->e); + } + else + { + body = get_loop_body (loop); + 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)) + VEC_safe_push (edge, heap, edges, e); + } + free (body); + } return edges; } @@ -1192,83 +1190,124 @@ num_loop_branches (const struct loop *loop) void add_bb_to_loop (basic_block bb, struct loop *loop) { - int i; + unsigned i; + loop_p ploop; + edge_iterator ei; + edge e; - bb->loop_father = loop; - bb->loop_depth = loop->depth; - loop->num_nodes++; - for (i = 0; i < loop->depth; i++) - loop->pred[i]->num_nodes++; - } + gcc_assert (bb->loop_father == NULL); + bb->loop_father = loop; + bb->loop_depth = loop_depth (loop); + loop->num_nodes++; + for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++) + ploop->num_nodes++; + + FOR_EACH_EDGE (e, ei, bb->succs) + { + rescan_loop_exit (e, true, false); + } + FOR_EACH_EDGE (e, ei, bb->preds) + { + rescan_loop_exit (e, true, false); + } +} /* Remove basic block BB from loops. */ void remove_bb_from_loops (basic_block bb) { - int i; - struct loop *loop = bb->loop_father; + int i; + struct loop *loop = bb->loop_father; + loop_p ploop; + edge_iterator ei; + edge e; + + gcc_assert (loop != NULL); + loop->num_nodes--; + for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++) + ploop->num_nodes--; + bb->loop_father = NULL; + bb->loop_depth = 0; - loop->num_nodes--; - for (i = 0; i < loop->depth; i++) - loop->pred[i]->num_nodes--; - bb->loop_father = NULL; - bb->loop_depth = 0; - } + FOR_EACH_EDGE (e, ei, bb->succs) + { + rescan_loop_exit (e, false, true); + } + FOR_EACH_EDGE (e, ei, bb->preds) + { + rescan_loop_exit (e, false, true); + } +} /* Finds nearest common ancestor in loop tree for given loops. */ struct loop * find_common_loop (struct loop *loop_s, struct loop *loop_d) { + unsigned sdepth, ddepth; + 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]; + sdepth = loop_depth (loop_s); + ddepth = loop_depth (loop_d); + + if (sdepth < ddepth) + loop_d = VEC_index (loop_p, loop_d->superloops, sdepth); + else if (sdepth > ddepth) + loop_s = VEC_index (loop_p, loop_s->superloops, ddepth); while (loop_s != loop_d) { - loop_s = loop_s->outer; - loop_d = loop_d->outer; + loop_s = loop_outer (loop_s); + loop_d = loop_outer (loop_d); } return loop_s; } -/* Cancels the LOOP; it must be innermost one. */ +/* Removes LOOP from structures and frees its data. */ + void -cancel_loop (struct loops *loops, struct loop *loop) +delete_loop (struct loop *loop) +{ + /* Remove the loop from structure. */ + flow_loop_tree_node_remove (loop); + + /* Remove loop from loops array. */ + VEC_replace (loop_p, current_loops->larray, loop->num, NULL); + + /* Free loop data. */ + flow_loop_free (loop); +} + +/* Cancels the LOOP; it must be innermost one. */ + +static void +cancel_loop (struct loop *loop) { basic_block *bbs; unsigned i; + struct loop *outer = loop_outer (loop); 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; + bbs[i]->loop_father = outer; - /* Free loop data. */ - flow_loop_free (loop); + delete_loop (loop); } /* Cancels LOOP and all its subloops. */ void -cancel_loop_tree (struct loops *loops, struct loop *loop) +cancel_loop_tree (struct loop *loop) { while (loop->inner) - cancel_loop_tree (loops, loop->inner); - cancel_loop (loops, loop); + cancel_loop_tree (loop->inner); + cancel_loop (loop); } -/* Checks that LOOPS are all right: +/* Checks that information about loops is correct -- 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 @@ -1276,7 +1315,7 @@ cancel_loop_tree (struct loops *loops, struct loop *loop) -- irreducible loops are correctly marked */ void -verify_loop_structure (struct loops *loops) +verify_loop_structure (void) { unsigned *sizes, i, j; sbitmap irreds; @@ -1284,92 +1323,89 @@ verify_loop_structure (struct loops *loops) struct loop *loop; int err = 0; edge e; + unsigned num = number_of_loops (); + loop_iterator li; + struct loop_exit *exit, *mexit; /* Check sizes. */ - sizes = xcalloc (loops->num, sizeof (int)); + sizes = XCNEWVEC (unsigned, num); sizes[0] = 2; FOR_EACH_BB (bb) - for (loop = bb->loop_father; loop; loop = loop->outer) + for (loop = bb->loop_father; loop; loop = loop_outer (loop)) sizes[loop->num]++; - for (i = 0; i < loops->num; i++) + FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT) { - if (!loops->parray[i]) - continue; + i = loop->num; - if (loops->parray[i]->num_nodes != sizes[i]) + if (loop->num_nodes != sizes[i]) { - error ("Size of loop %d should be %d, not %d.", - i, sizes[i], loops->parray[i]->num_nodes); + error ("size of loop %d should be %d, not %d", + i, sizes[i], loop->num_nodes); err = 1; } } /* Check get_loop_body. */ - for (i = 1; i < loops->num; i++) + FOR_EACH_LOOP (li, loop, 0) { - 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); + error ("bb %d do not belong to loop %d", + bbs[j]->index, loop->num); err = 1; } free (bbs); } /* Check headers and latches. */ - for (i = 1; i < loops->num; i++) + FOR_EACH_LOOP (li, loop, 0) { - loop = loops->parray[i]; - if (!loop) - continue; + i = loop->num; - if ((loops->state & LOOPS_HAVE_PREHEADERS) + if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS) && EDGE_COUNT (loop->header->preds) != 2) { - error ("Loop %d's header does not have exactly 2 entries.", i); + error ("loop %d's header does not have exactly 2 entries", i); err = 1; } - if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES) + if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES)) { - if (EDGE_COUNT (loop->latch->succs) != 1) + if (!single_succ_p (loop->latch)) { - error ("Loop %d's latch does not have exactly 1 successor.", i); + error ("loop %d's latch does not have exactly 1 successor", i); err = 1; } - if (EDGE_SUCC (loop->latch, 0)->dest != loop->header) + if (single_succ (loop->latch) != loop->header) { - error ("Loop %d's latch does not have header as successor.", i); + 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); + 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); + error ("loop %d's header does not belong directly to it", i); err = 1; } - if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) + if (loops_state_satisfies_p (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); + 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) + if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)) { /* Record old info. */ irreds = sbitmap_alloc (last_basic_block); @@ -1386,7 +1422,7 @@ verify_loop_structure (struct loops *loops) } /* Recount it. */ - mark_irreducible_loops (loops); + mark_irreducible_loops (); /* Compare. */ FOR_EACH_BB (bb) @@ -1396,13 +1432,13 @@ verify_loop_structure (struct loops *loops) if ((bb->flags & BB_IRREDUCIBLE_LOOP) && !TEST_BIT (irreds, bb->index)) { - error ("Basic block %d should be marked irreducible.", 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); + error ("basic block %d should not be marked irreducible", bb->index); err = 1; } FOR_EACH_EDGE (e, ei, bb->succs) @@ -1410,14 +1446,14 @@ verify_loop_structure (struct loops *loops) if ((e->flags & EDGE_IRREDUCIBLE_LOOP) && !(e->flags & (EDGE_ALL_FLAGS + 1))) { - error ("Edge from %d to %d should be marked irreducible.", + 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.", + error ("edge from %d to %d should not be marked irreducible", e->src->index, e->dest->index); err = 1; } @@ -1427,63 +1463,104 @@ verify_loop_structure (struct loops *loops) free (irreds); } - /* Check the single_exit. */ - if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) + /* Check the recorded loop exits. */ + FOR_EACH_LOOP (li, loop, 0) + { + if (!loop->exits || loop->exits->e != NULL) + { + error ("corrupted head of the exits list of loop %d", + loop->num); + err = 1; + } + else + { + /* Check that the list forms a cycle, and all elements except + for the head are nonnull. */ + for (mexit = loop->exits, exit = mexit->next, i = 0; + exit->e && exit != mexit; + exit = exit->next) + { + if (i++ & 1) + mexit = mexit->next; + } + + if (exit != loop->exits) + { + error ("corrupted exits list of loop %d", loop->num); + err = 1; + } + } + + if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + { + if (loop->exits->next != loop->exits) + { + error ("nonempty exits list of loop %d, but exits are not recorded", + loop->num); + err = 1; + } + } + } + + if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) { - memset (sizes, 0, sizeof (unsigned) * loops->num); + unsigned n_exits = 0, eloops; + + memset (sizes, 0, sizeof (unsigned) * num); FOR_EACH_BB (bb) { edge_iterator ei; - if (bb->loop_father == loops->tree_root) + if (bb->loop_father == current_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; + n_exits++; + exit = get_exit_descriptions (e); + if (!exit) + { + error ("Exit %d->%d not recorded", + e->src->index, e->dest->index); + err = 1; + } + eloops = 0; + for (; exit; exit = exit->next_e) + eloops++; + for (loop = bb->loop_father; loop != e->dest->loop_father; - loop = loop->outer) + loop = loop_outer (loop)) { + eloops--; 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; - } + } + + if (eloops != 0) + { + error ("Wrong list of exited loops for edge %d->%d", + e->src->index, e->dest->index); + err = 1; } } } - for (i = 1; i < loops->num; i++) + if (n_exits != htab_elements (current_loops->exits)) { - 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; - } + error ("Too many loop exits recorded"); + err = 1; + } - if (sizes[i] != 1 - && loop->single_exit) + FOR_EACH_LOOP (li, loop, 0) + { + eloops = 0; + for (exit = loop->exits->next; exit->e; exit = exit->next) + eloops++; + if (eloops != sizes[loop->num]) { - error ("Loop %d should not have single exit (%d -> %d).", - loop->num, - loop->single_exit->src->index, - loop->single_exit->dest->index); + error ("%d exits recorded for loop %d (having %d exits)", + eloops, loop->num, sizes[loop->num]); err = 1; } } @@ -1508,9 +1585,38 @@ loop_preheader_edge (const struct loop *loop) edge e; edge_iterator ei; + gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)); + 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, const_edge e) +{ + return (flow_bb_inside_loop_p (loop, e->src) + && !flow_bb_inside_loop_p (loop, e->dest)); +} + +/* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit + or more than one exit. If loops do not have the exits recorded, NULL + is returned always. */ + +edge +single_exit (const struct loop *loop) +{ + struct loop_exit *exit = loop->exits->next; + + if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + return NULL; + + if (exit->e && exit->next == loop->exits) + return exit->e; + else + return NULL; +}