diff options
-rw-r--r-- | gcc/ChangeLog | 16 | ||||
-rw-r--r-- | gcc/cfgloop.c | 240 | ||||
-rw-r--r-- | gcc/cfgloop.h | 3 | ||||
-rw-r--r-- | gcc/cfgloopmanip.c | 156 | ||||
-rw-r--r-- | gcc/loop-init.c | 155 | ||||
-rw-r--r-- | gcc/testsuite/ChangeLog | 5 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/torture/pr56181.c | 25 |
7 files changed, 303 insertions, 297 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 38173e9..5175c84 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,19 @@ +2013-02-08 Richard Biener <rguenther@suse.de> + + PR middle-end/56181 + * cfgloop.h (flow_loops_find): Adjust. + (bb_loop_header_p): Declare. + * cfgloop.c (bb_loop_header_p): New function split out from ... + (flow_loops_find): ... here. Adjust function signature, + support incremental loop structure update. + (verify_loop_structure): Cleanup. Verify a loop is a loop. + * cfgloopmanip.c (fix_loop_structure): Move ... + * loop-init.c (fix_loop_structure): ... here. + (apply_loop_flags): Split out from ... + (loop_optimizer_init): ... here. + (fix_loop_structure): Use apply_loop_flags. Use flow_loops_find + in incremental mode, only remove dead loops here. + 2013-02-08 Georg-Johann Lay <avr@gjlay.de> PR target/54222 diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 3c8df30..60fc6e8 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -359,139 +359,156 @@ init_loops_structure (struct loops *loops, unsigned num_loops) loops->tree_root = root; } +/* Returns whether HEADER is a loop header. */ + +bool +bb_loop_header_p (basic_block header) +{ + edge_iterator ei; + edge e; + + /* If we have an abnormal predecessor, do not consider the + loop (not worth the problems). */ + if (bb_has_abnormal_pred (header)) + return false; + + /* 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. */ + FOR_EACH_EDGE (e, ei, header->preds) + { + basic_block latch = e->src; + if (latch != ENTRY_BLOCK_PTR + && dominated_by_p (CDI_DOMINATORS, latch, header)) + return true; + } + + return false; +} + /* Find all the natural loops in the function and save in LOOPS structure and recalculate loop_father information in basic block structures. - Return the number of natural loops found. */ + If LOOPS is non-NULL then the loop structures for already recorded loops + will be re-used and their number will not change. We assume that no + stale loops exist in LOOPS. + When LOOPS is NULL it is allocated and re-built from scratch. + Return the built LOOPS structure. */ -int +struct loops * flow_loops_find (struct loops *loops) { - int b; - int num_loops; - edge e; - sbitmap headers; - int *dfs_order; + bool from_scratch = (loops == NULL); int *rc_order; - basic_block header; - basic_block bb; + int b; + unsigned i; + vec<loop_p> larray; /* 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 == NUM_FIXED_BLOCKS) + if (!loops) { + loops = ggc_alloc_cleared_loops (); init_loops_structure (loops, 1); - return 1; } - dfs_order = NULL; - rc_order = NULL; + /* Ensure that loop exits were released. */ + gcc_assert (loops->exits == NULL); - /* Count the number of loop headers. This should be the - same as the number of natural loops. */ - headers = sbitmap_alloc (last_basic_block); - bitmap_clear (headers); + /* Taking care of this degenerate case makes the rest of + this code simpler. */ + if (n_basic_blocks == NUM_FIXED_BLOCKS) + return loops; - num_loops = 0; - FOR_EACH_BB (header) - { - edge_iterator ei; + /* The root loop node contains all basic-blocks. */ + loops->tree_root->num_nodes = n_basic_blocks; - /* If we have an abnormal predecessor, do not consider the - loop (not worth the problems). */ - if (bb_has_abnormal_pred (header)) - continue; + /* Compute depth first search order of the CFG so that outer + natural loops will be found before inner natural loops. */ + rc_order = XNEWVEC (int, n_basic_blocks); + pre_and_rev_post_order_compute (NULL, rc_order, false); - FOR_EACH_EDGE (e, ei, header->preds) + /* Gather all loop headers in reverse completion order and allocate + loop structures for loops that are not already present. */ + larray.create (loops->larray->length()); + for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++) + { + basic_block header = BASIC_BLOCK (rc_order[b]); + if (bb_loop_header_p (header)) { - basic_block latch = e->src; - - gcc_assert (!(e->flags & EDGE_ABNORMAL)); + struct loop *loop; - /* 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. */ - if (latch != ENTRY_BLOCK_PTR - && dominated_by_p (CDI_DOMINATORS, latch, header)) + /* The current active loop tree has valid loop-fathers for + header blocks. */ + if (!from_scratch + && header->loop_father->header == header) { - /* Shared headers should be eliminated by now. */ - bitmap_set_bit (headers, header->index); - num_loops++; + loop = header->loop_father; + /* If we found an existing loop remove it from the + loop tree. It is going to be inserted again + below. */ + flow_loop_tree_node_remove (loop); } + else + { + /* Otherwise allocate a new loop structure for the loop. */ + loop = alloc_loop (); + /* ??? We could re-use unused loop slots here. */ + loop->num = loops->larray->length (); + vec_safe_push (loops->larray, loop); + loop->header = header; + + if (!from_scratch + && dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "flow_loops_find: discovered new " + "loop %d with header %d\n", + loop->num, header->index); + } + larray.safe_push (loop); } - } - /* Allocate loop structures. */ - init_loops_structure (loops, num_loops + 1); + /* Make blocks part of the loop root node at start. */ + header->loop_father = loops->tree_root; + } - /* Find and record information about all the natural loops - in the CFG. */ - FOR_EACH_BB (bb) - bb->loop_father = loops->tree_root; + free (rc_order); - if (num_loops) + /* Now iterate over the loops found, insert them into the loop tree + and assign basic-block ownership. */ + for (i = 0; i < larray.length (); ++i) { - /* Compute depth first search order of the CFG so that outer - natural loops will be found before inner natural loops. */ - 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); + struct loop *loop = larray[i]; + basic_block header = loop->header; + edge_iterator ei; + edge e; - num_loops = 1; + flow_loop_tree_node_add (header->loop_father, loop); + loop->num_nodes = flow_loop_nodes_find (loop->header, loop); - for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++) + /* Look for the latch for this header block, if it has just a + single one. */ + FOR_EACH_EDGE (e, ei, header->preds) { - struct loop *loop; - edge_iterator ei; - - /* Search the nodes of the CFG in reverse completion order - so that we can find outer loops first. */ - if (!bitmap_bit_p (headers, rc_order[b])) - continue; - - header = BASIC_BLOCK (rc_order[b]); - - loop = alloc_loop (); - loops->larray->quick_push (loop); - - loop->header = header; - loop->num = num_loops; - num_loops++; - - flow_loop_tree_node_add (header->loop_father, loop); - loop->num_nodes = flow_loop_nodes_find (loop->header, loop); + basic_block latch = e->src; - /* Look for the latch for this header block, if it has just a - single one. */ - FOR_EACH_EDGE (e, ei, header->preds) + if (flow_bb_inside_loop_p (loop, latch)) { - basic_block latch = e->src; - - if (flow_bb_inside_loop_p (loop, latch)) + if (loop->latch != NULL) { - if (loop->latch != NULL) - { - /* More than one latch edge. */ - loop->latch = NULL; - break; - } - loop->latch = latch; + /* More than one latch edge. */ + loop->latch = NULL; + break; } + loop->latch = latch; } } - - free (dfs_order); - free (rc_order); } - sbitmap_free (headers); + larray.release(); - loops->exits = NULL; - return loops->larray->length (); + return loops; } /* Ratio of frequencies of edges so that one of more latch edges is @@ -1300,7 +1317,7 @@ verify_loop_structure (void) { unsigned *sizes, i, j; sbitmap irreds; - basic_block *bbs, bb; + basic_block bb; struct loop *loop; int err = 0; edge e; @@ -1308,7 +1325,7 @@ verify_loop_structure (void) loop_iterator li; struct loop_exit *exit, *mexit; bool dom_available = dom_info_available_p (CDI_DOMINATORS); - sbitmap visited = sbitmap_alloc (last_basic_block); + sbitmap visited; /* We need up-to-date dominators, compute or verify them. */ if (!dom_available) @@ -1337,28 +1354,23 @@ verify_loop_structure (void) } /* Check get_loop_body. */ - FOR_EACH_LOOP (li, loop, 0) - { - 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 does not belong to loop %d", - bbs[j]->index, loop->num); - err = 1; - } - free (bbs); - } + visited = sbitmap_alloc (last_basic_block); bitmap_clear (visited); FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) { - bbs = get_loop_body (loop); + basic_block *bbs = get_loop_body (loop); for (j = 0; j < loop->num_nodes; j++) { bb = bbs[j]; + if (!flow_bb_inside_loop_p (loop, bb)) + { + error ("bb %d does not belong to loop %d", + bb->index, loop->num); + err = 1; + } + /* Ignore this block if it is in an inner loop. */ if (bitmap_bit_p (visited, bb->index)) continue; @@ -1371,14 +1383,21 @@ verify_loop_structure (void) err = 1; } } + free (bbs); } + sbitmap_free (visited); /* Check headers and latches. */ FOR_EACH_LOOP (li, loop, 0) { i = loop->num; + if (!bb_loop_header_p (loop->header)) + { + error ("loop %d%'s header is not a loop header", i); + err = 1; + } if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS) && EDGE_COUNT (loop->header->preds) != 2) { @@ -1585,7 +1604,6 @@ verify_loop_structure (void) gcc_assert (!err); - sbitmap_free (visited); free (sizes); if (!dom_available) free_dominance_info (CDI_DOMINATORS); diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 071c8c1..7506ac5 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -205,7 +205,8 @@ struct GTY (()) loops { }; /* Loop recognition. */ -extern int flow_loops_find (struct loops *); +bool bb_loop_header_p (basic_block); +extern struct loops *flow_loops_find (struct loops *); extern void disambiguate_loops_with_multiple_latches (void); extern void flow_loops_free (struct loops *); extern void flow_loops_dump (FILE *, diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index c72ceda..3e53aa0 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1760,159 +1760,3 @@ loop_version (struct loop *loop, return nloop; } - -/* The structure of loops might have changed. Some loops might get removed - (and their headers and latches were set to NULL), loop exists might get - removed (thus the loop nesting may be wrong), and some blocks and edges - were changed (so the information about bb --> loop mapping does not have - to be correct). But still for the remaining loops the header dominates - the latch, and loops did not get new subloops (new loops might possibly - get created, but we are not interested in them). Fix up the mess. - - If CHANGED_BBS is not NULL, basic blocks whose loop has changed are - marked in it. */ - -void -fix_loop_structure (bitmap changed_bbs) -{ - basic_block bb; - struct loop *loop, *ploop; - loop_iterator li; - bool record_exits = false; - struct loop **superloop = XNEWVEC (struct loop *, number_of_loops ()); - - /* We need exact and fast dominance info to be available. */ - gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK); - - /* Remove the old bb -> loop mapping. Remember the depth of the blocks in - the loop hierarchy, so that we can recognize blocks whose loop nesting - relationship has changed. */ - FOR_EACH_BB (bb) - { - if (changed_bbs) - bb->aux = (void *) (size_t) loop_depth (bb->loop_father); - bb->loop_father = current_loops->tree_root; - } - - if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) - { - release_recorded_exits (); - record_exits = true; - } - - /* First re-compute loop latches. */ - FOR_EACH_LOOP (li, loop, 0) - { - edge_iterator ei; - edge e, first_latch = NULL, latch = NULL; - - if (!loop->header) - continue; - - FOR_EACH_EDGE (e, ei, loop->header->preds) - if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header)) - { - if (!first_latch) - first_latch = latch = e; - else - { - latch = NULL; - break; - } - } - /* If there was no latch, schedule the loop for removal. */ - if (!first_latch) - loop->header = NULL; - /* If there was a single latch, record it. */ - else if (latch) - loop->latch = latch->src; - /* Otherwise there are multiple latches which are eventually - disambiguated below. */ - else - loop->latch = NULL; - } - - /* Remove the dead loops from structures. We start from the innermost - loops, so that when we remove the loops, we know that the loops inside - are preserved, and do not waste time relinking loops that will be - removed later. */ - FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) - { - if (loop->header) - continue; - - while (loop->inner) - { - ploop = loop->inner; - flow_loop_tree_node_remove (ploop); - flow_loop_tree_node_add (loop_outer (loop), ploop); - } - - /* Remove the loop and free its data. */ - delete_loop (loop); - } - - /* Rescan the bodies of loops, starting from the outermost ones. We assume - that no optimization interchanges the order of the loops, i.e., it cannot - happen that L1 was superloop of L2 before and it is subloop of L2 now - (without explicitly updating loop information). At the same time, we also - determine the new loop structure. */ - current_loops->tree_root->num_nodes = n_basic_blocks; - FOR_EACH_LOOP (li, loop, 0) - { - superloop[loop->num] = loop->header->loop_father; - loop->num_nodes = flow_loop_nodes_find (loop->header, loop); - } - - /* Now fix the loop nesting. */ - FOR_EACH_LOOP (li, loop, 0) - { - ploop = superloop[loop->num]; - if (ploop != loop_outer (loop)) - { - flow_loop_tree_node_remove (loop); - flow_loop_tree_node_add (ploop, loop); - } - } - free (superloop); - - /* Mark the blocks whose loop has changed. */ - if (changed_bbs) - { - FOR_EACH_BB (bb) - { - if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux) - bitmap_set_bit (changed_bbs, bb->index); - - bb->aux = NULL; - } - } - - if (!loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)) - disambiguate_loops_with_multiple_latches (); - - if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)) - { - int cp_flags = CP_SIMPLE_PREHEADERS; - - if (loops_state_satisfies_p (LOOPS_HAVE_FALLTHRU_PREHEADERS)) - cp_flags |= CP_FALLTHRU_PREHEADERS; - - create_preheaders (cp_flags); - } - - if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES)) - force_single_succ_latches (); - - if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)) - mark_irreducible_loops (); - - if (record_exits) - record_loop_exits (); - - loops_state_clear (LOOPS_NEED_FIXUP); - -#ifdef ENABLE_CHECKING - verify_loop_structure (); -#endif -} diff --git a/gcc/loop-init.c b/gcc/loop-init.c index 7e33de0..d64c110 100644 --- a/gcc/loop-init.c +++ b/gcc/loop-init.c @@ -32,37 +32,11 @@ along with GCC; see the file COPYING3. If not see #include "ggc.h" -/* Initialize loop structures. This is used by the tree and RTL loop - optimizers. FLAGS specify what properties to compute and/or ensure for - loops. */ +/* Apply FLAGS to the loop state. */ -void -loop_optimizer_init (unsigned flags) +static void +apply_loop_flags (unsigned flags) { - timevar_push (TV_LOOP_INIT); - if (!current_loops) - { - struct loops *loops = ggc_alloc_cleared_loops (); - - gcc_assert (!(cfun->curr_properties & PROP_loops)); - - /* Find the loops. */ - - flow_loops_find (loops); - current_loops = loops; - } - else - { - gcc_assert (cfun->curr_properties & PROP_loops); - - /* Ensure that the dominators are computed, like flow_loops_find does. */ - calculate_dominance_info (CDI_DOMINATORS); - -#ifdef ENABLE_CHECKING - verify_loop_structure (); -#endif - } - if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES) { /* If the loops may have multiple latches, we cannot canonicalize @@ -97,6 +71,38 @@ loop_optimizer_init (unsigned flags) if (flags & LOOPS_HAVE_RECORDED_EXITS) record_loop_exits (); +} + +/* Initialize loop structures. This is used by the tree and RTL loop + optimizers. FLAGS specify what properties to compute and/or ensure for + loops. */ + +void +loop_optimizer_init (unsigned flags) +{ + timevar_push (TV_LOOP_INIT); + + if (!current_loops) + { + gcc_assert (!(cfun->curr_properties & PROP_loops)); + + /* Find the loops. */ + current_loops = flow_loops_find (NULL); + } + else + { + gcc_assert (cfun->curr_properties & PROP_loops); + + /* Ensure that the dominators are computed, like flow_loops_find does. */ + calculate_dominance_info (CDI_DOMINATORS); + +#ifdef ENABLE_CHECKING + verify_loop_structure (); +#endif + } + + /* Apply flags to loops. */ + apply_loop_flags (flags); /* Dump loops. */ flow_loops_dump (dump_file, NULL, 1); @@ -157,6 +163,97 @@ loop_fini_done: timevar_pop (TV_LOOP_FINI); } +/* The structure of loops might have changed. Some loops might get removed + (and their headers and latches were set to NULL), loop exists might get + removed (thus the loop nesting may be wrong), and some blocks and edges + were changed (so the information about bb --> loop mapping does not have + to be correct). But still for the remaining loops the header dominates + the latch, and loops did not get new subloops (new loops might possibly + get created, but we are not interested in them). Fix up the mess. + + If CHANGED_BBS is not NULL, basic blocks whose loop has changed are + marked in it. */ + +void +fix_loop_structure (bitmap changed_bbs) +{ + basic_block bb; + int record_exits = 0; + loop_iterator li; + struct loop *loop; + + timevar_push (TV_LOOP_INIT); + + /* We need exact and fast dominance info to be available. */ + gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK); + + if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + { + release_recorded_exits (); + record_exits = LOOPS_HAVE_RECORDED_EXITS; + } + + /* Remember the depth of the blocks in the loop hierarchy, so that we can + recognize blocks whose loop nesting relationship has changed. */ + if (changed_bbs) + FOR_EACH_BB (bb) + bb->aux = (void *) (size_t) loop_depth (bb->loop_father); + + /* Remove the dead loops from structures. We start from the innermost + loops, so that when we remove the loops, we know that the loops inside + are preserved, and do not waste time relinking loops that will be + removed later. */ + FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) + { + /* Detect the case that the loop is no longer present even though + it wasn't marked for removal. + ??? If we do that we can get away with not marking loops for + removal at all. And possibly avoid some spurious removals. */ + if (loop->header + && bb_loop_header_p (loop->header)) + continue; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "fix_loop_structure: removing loop %d\n", + loop->num); + + while (loop->inner) + { + struct loop *ploop = loop->inner; + flow_loop_tree_node_remove (ploop); + flow_loop_tree_node_add (loop_outer (loop), ploop); + } + + /* Remove the loop and free its data. */ + delete_loop (loop); + } + + /* Re-compute loop structure in-place. */ + flow_loops_find (current_loops); + + /* Mark the blocks whose loop has changed. */ + if (changed_bbs) + { + FOR_EACH_BB (bb) + { + if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux) + bitmap_set_bit (changed_bbs, bb->index); + + bb->aux = NULL; + } + } + + loops_state_clear (LOOPS_NEED_FIXUP); + + /* Apply flags to loops. */ + apply_loop_flags (current_loops->state | record_exits); + +#ifdef ENABLE_CHECKING + verify_loop_structure (); +#endif + + timevar_pop (TV_LOOP_INIT); +} /* Gate for the RTL loop superpass. The actual passes are subpasses. See passes.c for more on that. */ diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index c12303d..2dcd876 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2013-02-08 Richard Biener <rguenther@suse.de> + + PR middle-end/56181 + * gcc.dg/torture/pr56181.c: New testcase. + 2013-02-08 Georg-Johann Lay <avr@gjlay.de> PR target/54222 diff --git a/gcc/testsuite/gcc.dg/torture/pr56181.c b/gcc/testsuite/gcc.dg/torture/pr56181.c new file mode 100644 index 0000000..c382b29 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr56181.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */
+/* { dg-options "-ftracer" } */
+
+int a, b;
+
+void f(void)
+{
+ if(a++)
+ {
+ for(a = 0; a < 1;)
+ {
+ for(b = 0; b < 1; b++)
+ {
+ while(a++ < 0);
+lbl:
+ ;
+ }
+
+ if(a)
+ goto lbl;
+ }
+
+ goto lbl;
+ }
+}
|