X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Fcfgloopmanip.c;h=69ed980fa20bdf5f854440e27361588af337c107;hp=616909700db12447301539d27253470b390964bb;hb=910faa40ecc531beb5aa29f954ce561814f6aba7;hpb=50caf588c7dc25dbfaf4e0f300ecb2ad2d0d8980 diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 616909700db..69ed980fa20 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1,11 +1,12 @@ /* Loop manipulation code for GNU compiler. - Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009 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" @@ -24,67 +24,43 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tm.h" #include "rtl.h" #include "hard-reg-set.h" +#include "obstack.h" #include "basic-block.h" #include "cfgloop.h" #include "cfglayout.h" +#include "cfghooks.h" #include "output.h" +#include "tree-flow.h" -static void duplicate_subloops (struct loops *, struct loop *, struct loop *); -static void copy_loops_to (struct loops *, struct loop **, int, +static void copy_loops_to (struct loop **, int, struct loop *); static void loop_redirect_edge (edge, basic_block); -static bool loop_delete_branch_edge (edge, int); static void remove_bbs (basic_block *, int); -static bool rpe_enum_p (basic_block, void *); +static bool rpe_enum_p (const_basic_block, const void *); static int find_path (edge, basic_block **); -static bool alp_enum_p (basic_block, void *); -static void add_loop (struct loops *, struct loop *); -static void fix_loop_placements (struct loops *, struct loop *); -static bool fix_bb_placement (struct loops *, basic_block); -static void fix_bb_placements (struct loops *, basic_block); -static void place_new_loop (struct loops *, struct loop *); -static void scale_loop_frequencies (struct loop *, int, int); -static void scale_bbs_frequencies (basic_block *, int, int, int); -static basic_block create_preheader (struct loop *, int); -static void fix_irreducible_loops (basic_block); +static void fix_loop_placements (struct loop *, bool *); +static bool fix_bb_placement (basic_block); +static void fix_bb_placements (basic_block, bool *); +static void unloop (struct loop *, bool *); #define RDIV(X,Y) (((X) + (Y) / 2) / (Y)) -/* Splits basic block BB after INSN, returns created edge. Updates loops - and dominators. */ -edge -split_loop_bb (basic_block bb, rtx insn) -{ - edge e; - - /* Split the block. */ - e = split_block (bb, insn); - - /* Add dest to loop. */ - add_bb_to_loop (e->dest, e->src->loop_father); - - return e; -} - /* Checks whether basic block BB is dominated by DATA. */ static bool -rpe_enum_p (basic_block bb, void *data) +rpe_enum_p (const_basic_block bb, const void *data) { - return dominated_by_p (CDI_DOMINATORS, bb, data); + return dominated_by_p (CDI_DOMINATORS, bb, (const_basic_block) data); } -/* Remove basic blocks BBS from loop structure and dominance info, - and delete them afterwards. */ +/* Remove basic blocks BBS. NBBS is the number of the basic blocks. */ + static void remove_bbs (basic_block *bbs, int nbbs) { int i; for (i = 0; i < nbbs; i++) - { - remove_bb_from_loops (bbs[i]); - delete_basic_block (bbs[i]); - } + delete_basic_block (bbs[i]); } /* Find path -- i.e. the basic blocks dominated by edge E and put them @@ -96,15 +72,15 @@ remove_bbs (basic_block *bbs, int nbbs) static int find_path (edge e, basic_block **bbs) { - gcc_assert (!e->dest->pred->pred_next); + gcc_assert (EDGE_COUNT (e->dest->preds) <= 1); /* Find bbs in the path. */ - *bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); + *bbs = XCNEWVEC (basic_block, n_basic_blocks); return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs, n_basic_blocks, e->dest); } -/* Fix placement of basic block BB inside loop hierarchy stored in LOOPS -- +/* Fix placement of basic block BB inside loop hierarchy -- Let L be a loop to that BB belongs. Then every successor of BB must either 1) belong to some superloop of loop L, or 2) be a header of loop K such that K->outer is superloop of L @@ -112,19 +88,20 @@ find_path (edge e, basic_block **bbs) false if the placement of BB was already correct (provided that placements of its successors are correct). */ static bool -fix_bb_placement (struct loops *loops, basic_block bb) +fix_bb_placement (basic_block bb) { edge e; - struct loop *loop = loops->tree_root, *act; + edge_iterator ei; + struct loop *loop = current_loops->tree_root, *act; - for (e = bb->succ; e; e = e->succ_next) + FOR_EACH_EDGE (e, ei, bb->succs) { if (e->dest == EXIT_BLOCK_PTR) continue; act = e->dest->loop_father; if (act->header == e->dest) - act = act->outer; + act = loop_outer (act); if (flow_loop_nested_p (loop, act)) loop = act; @@ -139,6 +116,46 @@ fix_bb_placement (struct loops *loops, basic_block bb) return true; } +/* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop + of LOOP to that leads at least one exit edge of LOOP, and set it + as the immediate superloop of LOOP. Return true if the immediate superloop + of LOOP changed. */ + +static bool +fix_loop_placement (struct loop *loop) +{ + unsigned i; + edge e; + VEC (edge, heap) *exits = get_loop_exit_edges (loop); + struct loop *father = current_loops->tree_root, *act; + bool ret = false; + + for (i = 0; VEC_iterate (edge, exits, i, e); i++) + { + act = find_common_loop (loop, e->dest->loop_father); + if (flow_loop_nested_p (father, act)) + father = act; + } + + if (father != loop_outer (loop)) + { + for (act = loop_outer (loop); act != father; act = loop_outer (act)) + act->num_nodes -= loop->num_nodes; + flow_loop_tree_node_remove (loop); + flow_loop_tree_node_add (father, loop); + + /* The exit edges of LOOP no longer exits its original immediate + superloops; remove them from the appropriate exit lists. */ + for (i = 0; VEC_iterate (edge, exits, i, e); i++) + rescan_loop_exit (e, false, false); + + ret = true; + } + + VEC_free (edge, heap, exits); + return ret; +} + /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e. enforce condition condition stated in description of fix_bb_placement. We start from basic block FROM that had some of its successors removed, so that @@ -146,9 +163,14 @@ fix_bb_placement (struct loops *loops, basic_block bb) its predecessors that may change if placement of FROM changed. Also fix placement of subloops of FROM->loop_father, that might also be altered due to this change; the condition for them is similar, except that instead of - successors we consider edges coming out of the loops. */ + successors we consider edges coming out of the loops. + + If the changes may invalidate the information about irreducible regions, + IRRED_INVALIDATED is set to true. */ + static void -fix_bb_placements (struct loops *loops, basic_block from) +fix_bb_placements (basic_block from, + bool *irred_invalidated) { sbitmap in_queue; basic_block *queue, *qtop, *qbeg, *qend; @@ -163,7 +185,7 @@ fix_bb_placements (struct loops *loops, basic_block from) fix_loop_placement. */ base_loop = from->loop_father; - if (base_loop == loops->tree_root) + if (base_loop == current_loops->tree_root) return; in_queue = sbitmap_alloc (last_basic_block); @@ -172,7 +194,7 @@ fix_bb_placements (struct loops *loops, basic_block from) /* Prevent us from going out of the base_loop. */ SET_BIT (in_queue, base_loop->header->index); - queue = xmalloc ((base_loop->num_nodes + 1) * sizeof (basic_block)); + queue = XNEWVEC (basic_block, base_loop->num_nodes + 1); qtop = queue + base_loop->num_nodes + 1; qbeg = queue; qend = queue + 1; @@ -180,6 +202,7 @@ fix_bb_placements (struct loops *loops, basic_block from) while (qbeg != qend) { + edge_iterator ei; from = *qbeg; qbeg++; if (qbeg == qtop) @@ -195,16 +218,25 @@ fix_bb_placements (struct loops *loops, basic_block from) else { /* Ordinary basic block. */ - if (!fix_bb_placement (loops, from)) + if (!fix_bb_placement (from)) continue; } + FOR_EACH_EDGE (e, ei, from->succs) + { + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + *irred_invalidated = true; + } + /* Something has changed, insert predecessors into queue. */ - for (e = from->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, from->preds) { basic_block pred = e->src; struct loop *nca; + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + *irred_invalidated = true; + if (TEST_BIT (in_queue, pred->index)) continue; @@ -237,115 +269,51 @@ fix_bb_placements (struct loops *loops, basic_block from) free (queue); } -/* Basic block from has lost one or more of its predecessors, so it might - mo longer be part irreducible loop. Fix it and proceed recursively - for its successors if needed. */ -static void -fix_irreducible_loops (basic_block from) -{ - basic_block bb; - basic_block *stack; - int stack_top; - sbitmap on_stack; - edge *edges, e; - unsigned n_edges, i; - - if (!(from->flags & BB_IRREDUCIBLE_LOOP)) - return; - - on_stack = sbitmap_alloc (last_basic_block); - sbitmap_zero (on_stack); - SET_BIT (on_stack, from->index); - stack = xmalloc (from->loop_father->num_nodes * sizeof (basic_block)); - stack[0] = from; - stack_top = 1; - - while (stack_top) - { - bb = stack[--stack_top]; - RESET_BIT (on_stack, bb->index); - - for (e = bb->pred; e; e = e->pred_next) - if (e->flags & EDGE_IRREDUCIBLE_LOOP) - break; - if (e) - continue; - - bb->flags &= ~BB_IRREDUCIBLE_LOOP; - if (bb->loop_father->header == bb) - edges = get_loop_exit_edges (bb->loop_father, &n_edges); - else - { - n_edges = 0; - for (e = bb->succ; e; e = e->succ_next) - n_edges++; - edges = xmalloc (n_edges * sizeof (edge)); - n_edges = 0; - for (e = bb->succ; e; e = e->succ_next) - edges[n_edges++] = e; - } - - for (i = 0; i < n_edges; i++) - { - e = edges[i]; - - if (e->flags & EDGE_IRREDUCIBLE_LOOP) - { - if (!flow_bb_inside_loop_p (from->loop_father, e->dest)) - continue; - - e->flags &= ~EDGE_IRREDUCIBLE_LOOP; - if (TEST_BIT (on_stack, e->dest->index)) - continue; - - SET_BIT (on_stack, e->dest->index); - stack[stack_top++] = e->dest; - } - } - free (edges); - } - - free (on_stack); - free (stack); -} - /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E - and update loop structure stored in LOOPS and dominators. Return true if - we were able to remove the path, false otherwise (and nothing is affected - then). */ + and update loop structures and dominators. Return true if we were able + to remove the path, false otherwise (and nothing is affected then). */ bool -remove_path (struct loops *loops, edge e) +remove_path (edge e) { edge ae; - basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb; - int i, nrem, n_bord_bbs, n_dom_bbs; + basic_block *rem_bbs, *bord_bbs, from, bb; + VEC (basic_block, heap) *dom_bbs; + int i, nrem, n_bord_bbs; sbitmap seen; - bool deleted; + bool irred_invalidated = false; - if (!loop_delete_branch_edge (e, 0)) + if (!can_remove_branch_p (e)) return false; + /* Keep track of whether we need to update information about irreducible + regions. This is the case if the removed area is a part of the + irreducible region, or if the set of basic blocks that belong to a loop + that is inside an irreducible region is changed, or if such a loop is + removed. */ + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + irred_invalidated = true; + /* We need to check whether basic blocks are dominated by the edge e, but we only have basic block dominators. This is easy to fix -- when e->dest has exactly one predecessor, this corresponds to blocks dominated by e->dest, if not, split the edge. */ - if (e->dest->pred->pred_next) - e = loop_split_edge_with (e, NULL_RTX)->pred; + if (!single_pred_p (e->dest)) + e = single_pred_edge (split_edge (e)); /* It may happen that by removing path we remove one or more loops we belong to. In this case first unloop the loops, then proceed normally. We may assume that e->dest is not a header of any loop, as it now has exactly one predecessor. */ - while (e->src->loop_father->outer + while (loop_outer (e->src->loop_father) && dominated_by_p (CDI_DOMINATORS, e->src->loop_father->latch, e->dest)) - unloop (loops, e->src->loop_father); + unloop (e->src->loop_father, &irred_invalidated); /* Identify the path. */ nrem = find_path (e, &rem_bbs); n_bord_bbs = 0; - bord_bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); + bord_bbs = XCNEWVEC (basic_block, n_basic_blocks); seen = sbitmap_alloc (last_basic_block); sbitmap_zero (seen); @@ -354,31 +322,33 @@ remove_path (struct loops *loops, edge e) SET_BIT (seen, rem_bbs[i]->index); for (i = 0; i < nrem; i++) { + edge_iterator ei; bb = rem_bbs[i]; - for (ae = rem_bbs[i]->succ; ae; ae = ae->succ_next) + FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs) if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index)) { SET_BIT (seen, ae->dest->index); bord_bbs[n_bord_bbs++] = ae->dest; + + if (ae->flags & EDGE_IRREDUCIBLE_LOOP) + irred_invalidated = true; } } /* Remove the path. */ from = e->src; - deleted = loop_delete_branch_edge (e, 1); - gcc_assert (deleted); - dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); + remove_branch (e); + dom_bbs = NULL; /* Cancel loops contained in the path. */ for (i = 0; i < nrem; i++) if (rem_bbs[i]->loop_father->header == rem_bbs[i]) - cancel_loop_tree (loops, rem_bbs[i]->loop_father); + cancel_loop_tree (rem_bbs[i]->loop_father); remove_bbs (rem_bbs, nrem); free (rem_bbs); /* Find blocks whose dominators may be affected. */ - n_dom_bbs = 0; sbitmap_zero (seen); for (i = 0; i < n_bord_bbs; i++) { @@ -393,195 +363,430 @@ remove_path (struct loops *loops, edge e) ldom; ldom = next_dom_son (CDI_DOMINATORS, ldom)) if (!dominated_by_p (CDI_DOMINATORS, from, ldom)) - dom_bbs[n_dom_bbs++] = ldom; + VEC_safe_push (basic_block, heap, dom_bbs, ldom); } free (seen); /* Recount dominators. */ - iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); - free (dom_bbs); - - /* These blocks have lost some predecessor(s), thus their irreducible - status could be changed. */ - for (i = 0; i < n_bord_bbs; i++) - fix_irreducible_loops (bord_bbs[i]); + iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, true); + VEC_free (basic_block, heap, dom_bbs); free (bord_bbs); /* Fix placements of basic blocks inside loops and the placement of loops in the loop tree. */ - fix_bb_placements (loops, from); - fix_loop_placements (loops, from->loop_father); + fix_bb_placements (from, &irred_invalidated); + fix_loop_placements (from->loop_father, &irred_invalidated); + + if (irred_invalidated + && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)) + mark_irreducible_loops (); return true; } -/* Predicate for enumeration in add_loop. */ -static bool -alp_enum_p (basic_block bb, void *alp_header) +/* Creates place for a new LOOP in loops structure. */ + +static void +place_new_loop (struct loop *loop) { - return bb != (basic_block) alp_header; + loop->num = number_of_loops (); + VEC_safe_push (loop_p, gc, current_loops->larray, loop); } /* Given LOOP structure with filled header and latch, find the body of the - corresponding loop and add it to LOOPS tree. */ -static void -add_loop (struct loops *loops, struct loop *loop) + corresponding loop and add it to loops tree. Insert the LOOP as a son of + outer. */ + +void +add_loop (struct loop *loop, struct loop *outer) { basic_block *bbs; int i, n; + struct loop *subloop; + edge e; + edge_iterator ei; /* Add it to loop structure. */ - place_new_loop (loops, loop); - loop->level = 1; + place_new_loop (loop); + flow_loop_tree_node_add (outer, loop); /* Find its nodes. */ - bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); - n = dfs_enumerate_from (loop->latch, 1, alp_enum_p, - bbs, n_basic_blocks, loop->header); + bbs = XNEWVEC (basic_block, n_basic_blocks); + n = get_loop_body_with_size (loop, bbs, n_basic_blocks); for (i = 0; i < n; i++) - add_bb_to_loop (bbs[i], loop); - add_bb_to_loop (loop->header, loop); + { + if (bbs[i]->loop_father == outer) + { + remove_bb_from_loops (bbs[i]); + add_bb_to_loop (bbs[i], loop); + continue; + } - free (bbs); -} + loop->num_nodes++; -/* Multiply all frequencies of basic blocks in array BBS of length NBBS - by NUM/DEN. */ -static void -scale_bbs_frequencies (basic_block *bbs, int nbbs, int num, int den) -{ - int i; - edge e; + /* If we find a direct subloop of OUTER, move it to LOOP. */ + subloop = bbs[i]->loop_father; + if (loop_outer (subloop) == outer + && subloop->header == bbs[i]) + { + flow_loop_tree_node_remove (subloop); + flow_loop_tree_node_add (loop, subloop); + } + } - for (i = 0; i < nbbs; i++) + /* Update the information about loop exit edges. */ + for (i = 0; i < n; i++) { - bbs[i]->frequency = (bbs[i]->frequency * num) / den; - bbs[i]->count = RDIV (bbs[i]->count * num, den); - for (e = bbs[i]->succ; e; e = e->succ_next) - e->count = (e->count * num) /den; + FOR_EACH_EDGE (e, ei, bbs[i]->succs) + { + rescan_loop_exit (e, false, false); + } } + + free (bbs); } /* Multiply all frequencies in LOOP by NUM/DEN. */ -static void +void scale_loop_frequencies (struct loop *loop, int num, int den) { basic_block *bbs; bbs = get_loop_body (loop); - scale_bbs_frequencies (bbs, loop->num_nodes, num, den); + scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den); free (bbs); } +/* Recompute dominance information for basic blocks outside LOOP. */ + +static void +update_dominators_in_loop (struct loop *loop) +{ + VEC (basic_block, heap) *dom_bbs = NULL; + sbitmap seen; + basic_block *body; + unsigned i; + + seen = sbitmap_alloc (last_basic_block); + sbitmap_zero (seen); + body = get_loop_body (loop); + + for (i = 0; i < loop->num_nodes; i++) + SET_BIT (seen, body[i]->index); + + for (i = 0; i < loop->num_nodes; i++) + { + basic_block ldom; + + for (ldom = first_dom_son (CDI_DOMINATORS, body[i]); + ldom; + ldom = next_dom_son (CDI_DOMINATORS, ldom)) + if (!TEST_BIT (seen, ldom->index)) + { + SET_BIT (seen, ldom->index); + VEC_safe_push (basic_block, heap, dom_bbs, ldom); + } + } + + iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false); + free (body); + free (seen); + VEC_free (basic_block, heap, dom_bbs); +} + +/* Creates an if region as shown above. CONDITION is used to create + the test for the if. + + | + | ------------- ------------- + | | pred_bb | | pred_bb | + | ------------- ------------- + | | | + | | | ENTRY_EDGE + | | ENTRY_EDGE V + | | ====> ------------- + | | | cond_bb | + | | | CONDITION | + | | ------------- + | V / \ + | ------------- e_false / \ e_true + | | succ_bb | V V + | ------------- ----------- ----------- + | | false_bb | | true_bb | + | ----------- ----------- + | \ / + | \ / + | V V + | ------------- + | | join_bb | + | ------------- + | | exit_edge (result) + | V + | ----------- + | | succ_bb | + | ----------- + | + */ + +edge +create_empty_if_region_on_edge (edge entry_edge, tree condition) +{ + + basic_block cond_bb, true_bb, false_bb, join_bb; + edge e_true, e_false, exit_edge; + gimple cond_stmt; + tree simple_cond; + gimple_stmt_iterator gsi; + + cond_bb = split_edge (entry_edge); + + /* Insert condition in cond_bb. */ + gsi = gsi_last_bb (cond_bb); + simple_cond = + force_gimple_operand_gsi (&gsi, condition, true, NULL, + false, GSI_NEW_STMT); + cond_stmt = gimple_build_cond_from_tree (simple_cond, NULL_TREE, NULL_TREE); + gsi = gsi_last_bb (cond_bb); + gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); + + join_bb = split_edge (single_succ_edge (cond_bb)); + + e_true = single_succ_edge (cond_bb); + true_bb = split_edge (e_true); + + e_false = make_edge (cond_bb, join_bb, 0); + false_bb = split_edge (e_false); + + e_true->flags &= ~EDGE_FALLTHRU; + e_true->flags |= EDGE_TRUE_VALUE; + e_false->flags &= ~EDGE_FALLTHRU; + e_false->flags |= EDGE_FALSE_VALUE; + + set_immediate_dominator (CDI_DOMINATORS, cond_bb, entry_edge->src); + set_immediate_dominator (CDI_DOMINATORS, true_bb, cond_bb); + set_immediate_dominator (CDI_DOMINATORS, false_bb, cond_bb); + set_immediate_dominator (CDI_DOMINATORS, join_bb, cond_bb); + + exit_edge = single_succ_edge (join_bb); + + if (single_pred_p (exit_edge->dest)) + set_immediate_dominator (CDI_DOMINATORS, exit_edge->dest, join_bb); + + return exit_edge; +} + +/* create_empty_loop_on_edge + | + | - pred_bb - ------ pred_bb ------ + | | | | iv0 = initial_value | + | -----|----- ---------|----------- + | | ______ | entry_edge + | | entry_edge / | | + | | ====> | -V---V- loop_header ------------- + | V | | iv_before = phi (iv0, iv_after) | + | - succ_bb - | ---|----------------------------- + | | | | | + | ----------- | ---V--- loop_body --------------- + | | | iv_after = iv_before + stride | + | | | if (iv_before < upper_bound) | + | | ---|--------------\-------------- + | | | \ exit_e + | | V \ + | | - loop_latch - V- succ_bb - + | | | | | | + | | /------------- ----------- + | \ ___ / + + Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME + that is used before the increment of IV. IV_BEFORE should be used for + adding code to the body that uses the IV. OUTER is the outer loop in + which the new loop should be inserted. + + Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and + inserted on the loop entry edge. This implies that this function + should be used only when the UPPER_BOUND expression is a loop + invariant. */ + +struct loop * +create_empty_loop_on_edge (edge entry_edge, + tree initial_value, + tree stride, tree upper_bound, + tree iv, + tree *iv_before, + tree *iv_after, + struct loop *outer) +{ + basic_block loop_header, loop_latch, succ_bb, pred_bb; + struct loop *loop; + gimple_stmt_iterator gsi; + gimple_seq stmts; + gimple cond_expr; + tree exit_test; + edge exit_e; + int prob; + + gcc_assert (entry_edge && initial_value && stride && upper_bound && iv); + + /* Create header, latch and wire up the loop. */ + pred_bb = entry_edge->src; + loop_header = split_edge (entry_edge); + loop_latch = split_edge (single_succ_edge (loop_header)); + succ_bb = single_succ (loop_latch); + make_edge (loop_header, succ_bb, 0); + redirect_edge_succ_nodup (single_succ_edge (loop_latch), loop_header); + + /* Set immediate dominator information. */ + set_immediate_dominator (CDI_DOMINATORS, loop_header, pred_bb); + set_immediate_dominator (CDI_DOMINATORS, loop_latch, loop_header); + set_immediate_dominator (CDI_DOMINATORS, succ_bb, loop_header); + + /* Initialize a loop structure and put it in a loop hierarchy. */ + loop = alloc_loop (); + loop->header = loop_header; + loop->latch = loop_latch; + add_loop (loop, outer); + + /* TODO: Fix frequencies and counts. */ + prob = REG_BR_PROB_BASE / 2; + + scale_loop_frequencies (loop, REG_BR_PROB_BASE - prob, REG_BR_PROB_BASE); + + /* Update dominators. */ + update_dominators_in_loop (loop); + + /* Modify edge flags. */ + exit_e = single_exit (loop); + exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE; + single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE; + + /* Construct IV code in loop. */ + initial_value = force_gimple_operand (initial_value, &stmts, true, iv); + if (stmts) + { + gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts); + gsi_commit_edge_inserts (); + } + + upper_bound = force_gimple_operand (upper_bound, &stmts, true, NULL); + if (stmts) + { + gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts); + gsi_commit_edge_inserts (); + } + + gsi = gsi_last_bb (loop_header); + create_iv (initial_value, stride, iv, loop, &gsi, false, + iv_before, iv_after); + + /* Insert loop exit condition. */ + cond_expr = gimple_build_cond + (LT_EXPR, *iv_before, upper_bound, NULL_TREE, NULL_TREE); + + exit_test = gimple_cond_lhs (cond_expr); + exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL, + false, GSI_NEW_STMT); + gimple_cond_set_lhs (cond_expr, exit_test); + gsi = gsi_last_bb (exit_e->src); + gsi_insert_after (&gsi, cond_expr, GSI_NEW_STMT); + + split_block_after_labels (loop_header); + + return loop; +} + /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting - latch to header and update loop tree stored in LOOPS and dominators + latch to header and update loop tree and dominators accordingly. Everything between them plus LATCH_EDGE destination must be dominated by HEADER_EDGE destination, and back-reachable from LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB, - FALLTHRU_EDGE (SWITCH_BB) to original destination of HEADER_EDGE and - BRANCH_EDGE (SWITCH_BB) to original destination of LATCH_EDGE. - Returns newly created loop. */ + FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and + TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE. + Returns the newly created loop. Frequencies and counts in the new loop + are scaled by FALSE_SCALE and in the old one by TRUE_SCALE. */ struct loop * -loopify (struct loops *loops, edge latch_edge, edge header_edge, - basic_block switch_bb) +loopify (edge latch_edge, edge header_edge, + basic_block switch_bb, edge true_edge, edge false_edge, + bool redirect_all_edges, unsigned true_scale, unsigned false_scale) { basic_block succ_bb = latch_edge->dest; basic_block pred_bb = header_edge->src; - basic_block *dom_bbs, *body; - unsigned n_dom_bbs, i; - sbitmap seen; - struct loop *loop = xcalloc (1, sizeof (struct loop)); - struct loop *outer = succ_bb->loop_father->outer; - int freq, prob, tot_prob; + struct loop *loop = alloc_loop (); + struct loop *outer = loop_outer (succ_bb->loop_father); + int freq; gcov_type cnt; edge e; + edge_iterator ei; loop->header = header_edge->dest; loop->latch = latch_edge->src; freq = EDGE_FREQUENCY (header_edge); cnt = header_edge->count; - prob = switch_bb->succ->probability; - tot_prob = prob + switch_bb->succ->succ_next->probability; - if (tot_prob == 0) - tot_prob = 1; /* Redirect edges. */ loop_redirect_edge (latch_edge, loop->header); - loop_redirect_edge (BRANCH_EDGE (switch_bb), succ_bb); + loop_redirect_edge (true_edge, succ_bb); - loop_redirect_edge (header_edge, switch_bb); - loop_redirect_edge (FALLTHRU_EDGE (switch_bb), loop->header); + /* During loop versioning, one of the switch_bb edge is already properly + set. Do not redirect it again unless redirect_all_edges is true. */ + if (redirect_all_edges) + { + loop_redirect_edge (header_edge, switch_bb); + loop_redirect_edge (false_edge, loop->header); - /* Update dominators. */ - set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb); - set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb); + /* Update dominators. */ + set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb); + set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb); + } set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb); /* Compute new loop. */ - add_loop (loops, loop); - flow_loop_tree_node_add (outer, loop); + add_loop (loop, outer); /* Add switch_bb to appropriate loop. */ + if (switch_bb->loop_father) + remove_bb_from_loops (switch_bb); add_bb_to_loop (switch_bb, outer); /* Fix frequencies. */ - switch_bb->frequency = freq; - switch_bb->count = cnt; - for (e = switch_bb->succ; e; e = e->succ_next) - e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE; - scale_loop_frequencies (loop, prob, tot_prob); - scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob); - - /* Update dominators of blocks outside of LOOP. */ - dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); - n_dom_bbs = 0; - seen = sbitmap_alloc (last_basic_block); - sbitmap_zero (seen); - body = get_loop_body (loop); - - for (i = 0; i < loop->num_nodes; i++) - SET_BIT (seen, body[i]->index); - - for (i = 0; i < loop->num_nodes; i++) + if (redirect_all_edges) { - basic_block ldom; - - for (ldom = first_dom_son (CDI_DOMINATORS, body[i]); - ldom; - ldom = next_dom_son (CDI_DOMINATORS, ldom)) - if (!TEST_BIT (seen, ldom->index)) - { - SET_BIT (seen, ldom->index); - dom_bbs[n_dom_bbs++] = ldom; - } + switch_bb->frequency = freq; + switch_bb->count = cnt; + FOR_EACH_EDGE (e, ei, switch_bb->succs) + { + e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE; + } } - - iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); - - free (body); - free (seen); - free (dom_bbs); + scale_loop_frequencies (loop, false_scale, REG_BR_PROB_BASE); + scale_loop_frequencies (succ_bb->loop_father, true_scale, REG_BR_PROB_BASE); + update_dominators_in_loop (loop); return loop; } -/* Remove the latch edge of a LOOP and update LOOPS tree to indicate that +/* Remove the latch edge of a LOOP and update loops to indicate that the LOOP was removed. After this function, original loop latch will - have no successor, which caller is expected to fix somehow. */ -void -unloop (struct loops *loops, struct loop *loop) + have no successor, which caller is expected to fix somehow. + + If this may cause the information about irreducible regions to become + invalid, IRRED_INVALIDATED is set to true. */ + +static void +unloop (struct loop *loop, bool *irred_invalidated) { basic_block *body; struct loop *ploop; unsigned i, n; basic_block latch = loop->latch; - edge *edges; - unsigned n_edges; + bool dummy = false; + + if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP) + *irred_invalidated = true; /* This is relatively straightforward. The dominators are unchanged, as loop header dominates loop latch, so the only thing we have to care of @@ -590,13 +795,12 @@ unloop (struct loops *loops, struct loop *loop) its work. */ body = get_loop_body (loop); - edges = get_loop_exit_edges (loop, &n_edges); n = loop->num_nodes; for (i = 0; i < n; i++) if (body[i]->loop_father == loop) { remove_bb_from_loops (body[i]); - add_bb_to_loop (body[i], loop->outer); + add_bb_to_loop (body[i], loop_outer (loop)); } free(body); @@ -604,113 +808,61 @@ unloop (struct loops *loops, struct loop *loop) { ploop = loop->inner; flow_loop_tree_node_remove (ploop); - flow_loop_tree_node_add (loop->outer, ploop); + flow_loop_tree_node_add (loop_outer (loop), ploop); } /* Remove the loop and free its data. */ - flow_loop_tree_node_remove (loop); - loops->parray[loop->num] = NULL; - flow_loop_free (loop); - - remove_edge (latch->succ); - fix_bb_placements (loops, latch); - - /* If the loop was inside an irreducible region, we would have to somehow - update the irreducible marks inside its body. While it is certainly - possible to do, it is a bit complicated and this situation should be - very rare, so we just remark all loops in this case. */ - for (i = 0; i < n_edges; i++) - if (edges[i]->flags & EDGE_IRREDUCIBLE_LOOP) - break; - if (i != n_edges) - mark_irreducible_loops (loops); - free (edges); -} - -/* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop - FATHER of LOOP such that all of the edges coming out of LOOP belong to - FATHER, and set it as outer loop of LOOP. Return 1 if placement of - LOOP changed. */ -int -fix_loop_placement (struct loop *loop) -{ - basic_block *body; - unsigned i; - edge e; - struct loop *father = loop->pred[0], *act; + delete_loop (loop); - body = get_loop_body (loop); - for (i = 0; i < loop->num_nodes; i++) - for (e = body[i]->succ; e; e = e->succ_next) - if (!flow_bb_inside_loop_p (loop, e->dest)) - { - act = find_common_loop (loop, e->dest->loop_father); - if (flow_loop_nested_p (father, act)) - father = act; - } - free (body); + remove_edge (single_succ_edge (latch)); - if (father != loop->outer) - { - for (act = loop->outer; act != father; act = act->outer) - act->num_nodes -= loop->num_nodes; - flow_loop_tree_node_remove (loop); - flow_loop_tree_node_add (father, loop); - return 1; - } - return 0; + /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if + there is an irreducible region inside the cancelled loop, the flags will + be still correct. */ + fix_bb_placements (latch, &dummy); } /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that condition stated in description of fix_loop_placement holds for them. It is used in case when we removed some edges coming out of LOOP, which - may cause the right placement of LOOP inside loop tree to change. */ + may cause the right placement of LOOP inside loop tree to change. + + IRRED_INVALIDATED is set to true if a change in the loop structures might + invalidate the information about irreducible regions. */ + static void -fix_loop_placements (struct loops *loops, struct loop *loop) +fix_loop_placements (struct loop *loop, bool *irred_invalidated) { struct loop *outer; - while (loop->outer) + while (loop_outer (loop)) { - outer = loop->outer; + outer = loop_outer (loop); if (!fix_loop_placement (loop)) - break; + break; /* Changing the placement of a loop in the loop tree may alter the validity of condition 2) of the description of fix_bb_placement for its preheader, because the successor is the header and belongs to the loop. So call fix_bb_placements to fix up the placement of the preheader and (possibly) of its predecessors. */ - fix_bb_placements (loops, loop_preheader_edge (loop)->src); + fix_bb_placements (loop_preheader_edge (loop)->src, + irred_invalidated); loop = outer; } } -/* Creates place for a new LOOP in LOOPS structure. */ -static void -place_new_loop (struct loops *loops, struct loop *loop) -{ - loops->parray = - xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *)); - loops->parray[loops->num] = loop; - - loop->num = loops->num++; -} - /* Copies copy of LOOP as subloop of TARGET loop, placing newly - created loop into LOOPS structure. */ + created loop into loops structure. */ struct loop * -duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target) +duplicate_loop (struct loop *loop, struct loop *target) { struct loop *cloop; - cloop = xcalloc (1, sizeof (struct loop)); - place_new_loop (loops, cloop); - - /* Initialize copied loop. */ - cloop->level = loop->level; + cloop = alloc_loop (); + place_new_loop (cloop); - /* Set it as copy of loop. */ - loop->copy = cloop; + /* Mark the new loop as copy of LOOP. */ + set_loop_copy (loop, cloop); /* Add it to target. */ flow_loop_tree_node_add (target, cloop); @@ -719,31 +871,31 @@ duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target) } /* Copies structure of subloops of LOOP into TARGET loop, placing - newly created loops into loop tree stored in LOOPS. */ -static void -duplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target) + newly created loops into loop tree. */ +void +duplicate_subloops (struct loop *loop, struct loop *target) { struct loop *aloop, *cloop; for (aloop = loop->inner; aloop; aloop = aloop->next) { - cloop = duplicate_loop (loops, aloop, target); - duplicate_subloops (loops, aloop, cloop); + cloop = duplicate_loop (aloop, target); + duplicate_subloops (aloop, cloop); } } /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS, - into TARGET loop, placing newly created loops into loop tree LOOPS. */ + into TARGET loop, placing newly created loops into loop tree. */ static void -copy_loops_to (struct loops *loops, struct loop **copied_loops, int n, struct loop *target) +copy_loops_to (struct loop **copied_loops, int n, struct loop *target) { struct loop *aloop; int i; for (i = 0; i < n; i++) { - aloop = duplicate_loop (loops, copied_loops[i], target); - duplicate_subloops (loops, copied_loops[i], aloop); + aloop = duplicate_loop (copied_loops[i], target); + duplicate_subloops (copied_loops[i], aloop); } } @@ -757,86 +909,56 @@ loop_redirect_edge (edge e, basic_block dest) redirect_edge_and_branch_force (e, dest); } -/* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set, - just test whether it is possible to remove the edge. */ -static bool -loop_delete_branch_edge (edge e, int really_delete) -{ - basic_block src = e->src; - basic_block newdest; - int irr; - edge snd; - - gcc_assert (src->succ->succ_next); - - /* Cannot handle more than two exit edges. */ - if (src->succ->succ_next->succ_next) - return false; - /* And it must be just a simple branch. */ - if (!any_condjump_p (BB_END (src))) - return false; - - snd = e == src->succ ? src->succ->succ_next : src->succ; - newdest = snd->dest; - if (newdest == EXIT_BLOCK_PTR) - return false; - - /* Hopefully the above conditions should suffice. */ - if (!really_delete) - return true; - - /* Redirecting behaves wrongly wrto this flag. */ - irr = snd->flags & EDGE_IRREDUCIBLE_LOOP; - - if (!redirect_edge_and_branch (e, newdest)) - return false; - src->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP; - src->succ->flags |= irr; - - return true; -} - /* Check whether LOOP's body can be duplicated. */ bool -can_duplicate_loop_p (struct loop *loop) +can_duplicate_loop_p (const struct loop *loop) { int ret; basic_block *bbs = get_loop_body (loop); ret = can_copy_bbs_p (bbs, loop->num_nodes); free (bbs); - + return ret; } -/* The NBBS blocks in BBS will get duplicated and the copies will be placed - to LOOP. Update the single_exit information in superloops of LOOP. */ +/* Sets probability and count of edge E to zero. The probability and count + is redistributed evenly to the remaining edges coming from E->src. */ static void -update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs, - struct loop *loop) +set_zero_probability (edge e) { - unsigned i; - - for (i = 0; i < nbbs; i++) - bbs[i]->rbi->duplicated = 1; - - for (; loop->outer; loop = loop->outer) + basic_block bb = e->src; + edge_iterator ei; + edge ae, last = NULL; + unsigned n = EDGE_COUNT (bb->succs); + gcov_type cnt = e->count, cnt1; + unsigned prob = e->probability, prob1; + + gcc_assert (n > 1); + cnt1 = cnt / (n - 1); + prob1 = prob / (n - 1); + + FOR_EACH_EDGE (ae, ei, bb->succs) { - if (!loop->single_exit) + if (ae == e) continue; - if (loop->single_exit->src->rbi->duplicated) - loop->single_exit = NULL; + ae->probability += prob1; + ae->count += cnt1; + last = ae; } - for (i = 0; i < nbbs; i++) - bbs[i]->rbi->duplicated = 0; -} + /* Move the rest to one of the edges. */ + last->probability += prob % (n - 1); + last->count += cnt % (n - 1); + e->probability = 0; + e->count = 0; +} /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating - LOOPS structure and dominators. E's destination must be LOOP header for + loop structure and dominators. E's destination must be LOOP header for this to work, i.e. it must be entry or latch edge of this loop; these are unique, as the loops must have preheaders for this function to work correctly (in case E is latch, the function unrolls the loop, if E is entry @@ -845,11 +967,12 @@ update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs, original LOOP body, the other copies are numbered in order given by control flow through them) into TO_REMOVE array. Returns false if duplication is impossible. */ -int -duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, + +bool +duplicate_loop_to_header_edge (struct loop *loop, edge e, unsigned int ndupl, sbitmap wont_exit, - edge orig, edge *to_remove, - unsigned int *n_to_remove, int flags) + edge orig, VEC (edge, heap) **to_remove, + int flags) { struct loop *target, *aloop; struct loop **orig_loops; @@ -864,9 +987,13 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, unsigned i, j, n; int is_latch = (latch == e->src); int scale_act = 0, *scale_step = NULL, scale_main = 0; + int scale_after_exit = 0; int p, freq_in, freq_le, freq_out_orig; int prob_pass_thru, prob_pass_wont_exit, prob_pass_main; int add_irreducible_flag; + basic_block place_after; + bitmap bbs_to_scale = NULL; + bitmap_iterator bi; gcc_assert (e->dest == loop->header); gcc_assert (ndupl > 0); @@ -878,7 +1005,10 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest)); } - bbs = get_loop_body (loop); + n = loop->num_nodes; + bbs = get_loop_body_in_dom_order (loop); + gcc_assert (bbs[0] == loop->header); + gcc_assert (bbs[n - 1] == loop->latch); /* Check whether duplication is possible. */ if (!can_copy_bbs_p (bbs, loop->num_nodes)) @@ -886,7 +1016,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, free (bbs); return false; } - new_bbs = xmalloc (sizeof (basic_block) * loop->num_nodes); + new_bbs = XNEWVEC (basic_block, loop->num_nodes); /* In case we are doing loop peeling and the loop is in the middle of irreducible region, the peeled copies will be inside it too. */ @@ -913,14 +1043,51 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, prob_pass_wont_exit = RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in); - scale_step = xmalloc (ndupl * sizeof (int)); + if (orig + && REG_BR_PROB_BASE - orig->probability != 0) + { + /* The blocks that are dominated by a removed exit edge ORIG have + frequencies scaled by this. */ + scale_after_exit = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, + REG_BR_PROB_BASE - orig->probability); + bbs_to_scale = BITMAP_ALLOC (NULL); + for (i = 0; i < n; i++) + { + if (bbs[i] != orig->src + && dominated_by_p (CDI_DOMINATORS, bbs[i], orig->src)) + bitmap_set_bit (bbs_to_scale, i); + } + } + + scale_step = XNEWVEC (int, ndupl); - for (i = 1; i <= ndupl; i++) - scale_step[i - 1] = TEST_BIT (wont_exit, i) + for (i = 1; i <= ndupl; i++) + scale_step[i - 1] = TEST_BIT (wont_exit, i) ? prob_pass_wont_exit : prob_pass_thru; - if (is_latch) + /* Complete peeling is special as the probability of exit in last + copy becomes 1. */ + if (flags & DLTHE_FLAG_COMPLETTE_PEEL) + { + int wanted_freq = EDGE_FREQUENCY (e); + + if (wanted_freq > freq_in) + wanted_freq = freq_in; + + gcc_assert (!is_latch); + /* First copy has frequency of incoming edge. Each subsequent + frequency should be reduced by prob_pass_wont_exit. Caller + should've managed the flags so all except for original loop + has won't exist set. */ + scale_act = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in); + /* Now simulate the duplication adjustments and compute header + frequency of the last copy. */ + for (i = 0; i < ndupl; i++) + wanted_freq = RDIV (wanted_freq * scale_step[i], REG_BR_PROB_BASE); + scale_main = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in); + } + else if (is_latch) { prob_pass_main = TEST_BIT (wont_exit, 0) ? prob_pass_wont_exit @@ -955,62 +1122,60 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, n_orig_loops = 0; for (aloop = loop->inner; aloop; aloop = aloop->next) n_orig_loops++; - orig_loops = xcalloc (n_orig_loops, sizeof (struct loop *)); + orig_loops = XCNEWVEC (struct loop *, n_orig_loops); for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++) orig_loops[i] = aloop; - loop->copy = target; - - n = loop->num_nodes; + set_loop_copy (loop, target); - first_active = xmalloc (n * sizeof (basic_block)); + first_active = XNEWVEC (basic_block, n); if (is_latch) { memcpy (first_active, bbs, n * sizeof (basic_block)); first_active_latch = latch; } - /* Update the information about single exits. */ - if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) - update_single_exits_after_duplication (bbs, n, target); - - /* Record exit edge in original loop body. */ - if (orig && TEST_BIT (wont_exit, 0)) - to_remove[(*n_to_remove)++] = orig; - spec_edges[SE_ORIG] = orig; spec_edges[SE_LATCH] = latch_edge; + place_after = e->src; for (j = 0; j < ndupl; j++) { /* Copy loops. */ - copy_loops_to (loops, orig_loops, n_orig_loops, target); + copy_loops_to (orig_loops, n_orig_loops, target); /* Copy bbs. */ - copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop); + copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop, + place_after); + place_after = new_spec_edges[SE_LATCH]->src; - for (i = 0; i < n; i++) - new_bbs[i]->rbi->copy_number = j + 1; + if (flags & DLTHE_RECORD_COPY_NUMBER) + for (i = 0; i < n; i++) + { + gcc_assert (!new_bbs[i]->aux); + new_bbs[i]->aux = (void *)(size_t)(j + 1); + } /* Note whether the blocks and edges belong to an irreducible loop. */ if (add_irreducible_flag) { for (i = 0; i < n; i++) - new_bbs[i]->rbi->duplicated = 1; + new_bbs[i]->flags |= BB_DUPLICATED; for (i = 0; i < n; i++) { + edge_iterator ei; new_bb = new_bbs[i]; if (new_bb->loop_father == target) new_bb->flags |= BB_IRREDUCIBLE_LOOP; - for (ae = new_bb->succ; ae; ae = ae->succ_next) - if (ae->dest->rbi->duplicated + FOR_EACH_EDGE (ae, ei, new_bb->succs) + if ((ae->dest->flags & BB_DUPLICATED) && (ae->src->loop_father == target || ae->dest->loop_father == target)) ae->flags |= EDGE_IRREDUCIBLE_LOOP; } for (i = 0; i < n; i++) - new_bbs[i]->rbi->duplicated = 0; + new_bbs[i]->flags &= ~BB_DUPLICATED; } /* Redirect the special edges. */ @@ -1020,7 +1185,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, redirect_edge_and_branch_force (new_spec_edges[SE_LATCH], loop->header); set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch); - latch = loop->latch = new_bbs[1]; + latch = loop->latch = new_bbs[n - 1]; e = latch_edge = new_spec_edges[SE_LATCH]; } else @@ -1034,59 +1199,92 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, /* Record exit edge in this copy. */ if (orig && TEST_BIT (wont_exit, j + 1)) - to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG]; + { + if (to_remove) + VEC_safe_push (edge, heap, *to_remove, new_spec_edges[SE_ORIG]); + set_zero_probability (new_spec_edges[SE_ORIG]); + + /* Scale the frequencies of the blocks dominated by the exit. */ + if (bbs_to_scale) + { + EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi) + { + scale_bbs_frequencies_int (new_bbs + i, 1, scale_after_exit, + REG_BR_PROB_BASE); + } + } + } /* Record the first copy in the control flow order if it is not the original loop (i.e. in case of peeling). */ if (!first_active_latch) { memcpy (first_active, new_bbs, n * sizeof (basic_block)); - first_active_latch = new_bbs[1]; + first_active_latch = new_bbs[n - 1]; } /* Set counts and frequencies. */ if (flags & DLTHE_FLAG_UPDATE_FREQ) { - scale_bbs_frequencies (new_bbs, n, scale_act, REG_BR_PROB_BASE); + scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE); scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE); } } free (new_bbs); free (orig_loops); - + + /* Record the exit edge in the original loop body, and update the frequencies. */ + if (orig && TEST_BIT (wont_exit, 0)) + { + if (to_remove) + VEC_safe_push (edge, heap, *to_remove, orig); + set_zero_probability (orig); + + /* Scale the frequencies of the blocks dominated by the exit. */ + if (bbs_to_scale) + { + EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi) + { + scale_bbs_frequencies_int (bbs + i, 1, scale_after_exit, + REG_BR_PROB_BASE); + } + } + } + /* Update the original loop. */ if (!is_latch) set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src); if (flags & DLTHE_FLAG_UPDATE_FREQ) { - scale_bbs_frequencies (bbs, n, scale_main, REG_BR_PROB_BASE); + scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE); free (scale_step); } /* Update dominators of outer blocks if affected. */ for (i = 0; i < n; i++) { - basic_block dominated, dom_bb, *dom_bbs; - int n_dom_bbs,j; + basic_block dominated, dom_bb; + VEC (basic_block, heap) *dom_bbs; + unsigned j; bb = bbs[i]; - bb->rbi->copy_number = 0; + bb->aux = 0; - n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs); - for (j = 0; j < n_dom_bbs; j++) + dom_bbs = get_dominated_by (CDI_DOMINATORS, bb); + for (j = 0; VEC_iterate (basic_block, dom_bbs, j, dominated); j++) { - dominated = dom_bbs[j]; if (flow_bb_inside_loop_p (loop, dominated)) continue; dom_bb = nearest_common_dominator ( CDI_DOMINATORS, first_active[i], first_active_latch); - set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb); + set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb); } - free (dom_bbs); + VEC_free (basic_block, heap, dom_bbs); } free (first_active); free (bbs); + BITMAP_FREE (bbs_to_scale); return true; } @@ -1095,258 +1293,422 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, 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 +edge mfb_kj_edge; +bool mfb_keep_just (edge e) { return e != mfb_kj_edge; } -/* A callback for make_forwarder block, to update data structures for a basic - block JUMP created by redirecting an edge (only the latch edge is being - redirected). */ +/* True when a candidate preheader BLOCK has predecessors from LOOP. */ -static void -mfb_update_loops (basic_block jump) +static bool +has_preds_from_loop (basic_block block, struct loop *loop) { - struct loop *loop = jump->succ->dest->loop_father; + edge e; + edge_iterator ei; - if (dom_computed[CDI_DOMINATORS]) - set_immediate_dominator (CDI_DOMINATORS, jump, jump->pred->src); - add_bb_to_loop (jump, loop); - loop->latch = jump; + FOR_EACH_EDGE (e, ei, block->preds) + if (e->src->loop_father == loop) + return true; + return false; } /* Creates a pre-header for a LOOP. Returns newly created block. Unless CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single entry; otherwise we also force preheader block to have only one successor. + When CP_FALLTHRU_PREHEADERS is set in FLAGS, we force the preheader block + to be a fallthru predecessor to the loop header and to have only + predecessors from outside of the loop. The function also updates dominators. */ -static basic_block +basic_block create_preheader (struct loop *loop, int flags) { edge e, fallthru; basic_block dummy; - struct loop *cloop, *ploop; int nentry = 0; bool irred = false; + bool latch_edge_was_fallthru; + edge one_succ_pred = NULL, single_entry = NULL; + edge_iterator ei; - cloop = loop->outer; - - for (e = loop->header->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, loop->header->preds) { if (e->src == loop->latch) continue; irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0; nentry++; + single_entry = e; + if (single_succ_p (e->src)) + one_succ_pred = e; } gcc_assert (nentry); if (nentry == 1) { - for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next); - if (!(flags & CP_SIMPLE_PREHEADERS) - || !e->src->succ->succ_next) + bool need_forwarder_block = false; + + /* We do not allow entry block to be the loop preheader, since we + cannot emit code there. */ + if (single_entry->src == ENTRY_BLOCK_PTR) + need_forwarder_block = true; + else + { + /* If we want simple preheaders, also force the preheader to have + just a single successor. */ + if ((flags & CP_SIMPLE_PREHEADERS) + && !single_succ_p (single_entry->src)) + need_forwarder_block = true; + /* If we want fallthru preheaders, also create forwarder block when + preheader ends with a jump or has predecessors from loop. */ + else if ((flags & CP_FALLTHRU_PREHEADERS) + && (JUMP_P (BB_END (single_entry->src)) + || has_preds_from_loop (single_entry->src, loop))) + need_forwarder_block = true; + } + if (! need_forwarder_block) return NULL; } mfb_kj_edge = loop_latch_edge (loop); - fallthru = make_forwarder_block (loop->header, mfb_keep_just, - mfb_update_loops); + latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0; + fallthru = make_forwarder_block (loop->header, mfb_keep_just, NULL); dummy = fallthru->src; loop->header = fallthru->dest; - /* The header could be a latch of some superloop(s); due to design of - split_block, it would now move to fallthru->dest. */ - for (ploop = loop; ploop; ploop = ploop->outer) - if (ploop->latch == dummy) - ploop->latch = fallthru->dest; + /* Try to be clever in placing the newly created preheader. The idea is to + avoid breaking any "fallthruness" relationship between blocks. - /* Reorganize blocks so that the preheader is not stuck in the middle of the - loop. */ - for (e = dummy->pred; e; e = e->pred_next) - if (e->src != loop->latch) - break; - move_block_after (dummy, e->src); + The preheader was created just before the header and all incoming edges + to the header were redirected to the preheader, except the latch edge. + So the only problematic case is when this latch edge was a fallthru + edge: it is not anymore after the preheader creation so we have broken + the fallthruness. We're therefore going to look for a better place. */ + if (latch_edge_was_fallthru) + { + if (one_succ_pred) + e = one_succ_pred; + else + e = EDGE_PRED (dummy, 0); - loop->header->loop_father = loop; - add_bb_to_loop (dummy, cloop); + move_block_after (dummy, e->src); + } if (irred) { dummy->flags |= BB_IRREDUCIBLE_LOOP; - dummy->succ->flags |= EDGE_IRREDUCIBLE_LOOP; + single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP; } if (dump_file) fprintf (dump_file, "Created preheader block for loop %i\n", loop->num); + if (flags & CP_FALLTHRU_PREHEADERS) + gcc_assert ((single_succ_edge (dummy)->flags & EDGE_FALLTHRU) + && !JUMP_P (BB_END (dummy))); + return dummy; } -/* Create preheaders for each loop from loop tree stored in LOOPS; for meaning - of FLAGS see create_preheader. */ +/* Create preheaders for each loop; for meaning of FLAGS see create_preheader. */ + void -create_preheaders (struct loops *loops, int flags) +create_preheaders (int flags) { - unsigned i; - for (i = 1; i < loops->num; i++) - create_preheader (loops->parray[i], flags); - loops->state |= LOOPS_HAVE_PREHEADERS; + loop_iterator li; + struct loop *loop; + + if (!current_loops) + return; + + FOR_EACH_LOOP (li, loop, 0) + create_preheader (loop, flags); + loops_state_set (LOOPS_HAVE_PREHEADERS); } -/* Forces all loop latches of loops from loop tree LOOPS to have only single - successor. */ +/* Forces all loop latches to have only single successor. */ + void -force_single_succ_latches (struct loops *loops) +force_single_succ_latches (void) { - unsigned i; + loop_iterator li; struct loop *loop; edge e; - for (i = 1; i < loops->num; i++) + FOR_EACH_LOOP (li, loop, 0) { - loop = loops->parray[i]; - if (loop->latch != loop->header - && !loop->latch->succ->succ_next) + if (loop->latch != loop->header && single_succ_p (loop->latch)) continue; - for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next) - continue; + e = find_edge (loop->latch, loop->header); - loop_split_edge_with (e, NULL_RTX); + split_edge (e); } - loops->state |= LOOPS_HAVE_SIMPLE_LATCHES; + loops_state_set (LOOPS_HAVE_SIMPLE_LATCHES); } -/* A quite stupid function to put INSNS on edge E. They are supposed to form - just one basic block. Jumps in INSNS are not handled, so cfg do not have to - be ok after this function. The created block is placed on correct place - in LOOPS structure and its dominator is set. */ -basic_block -loop_split_edge_with (edge e, rtx insns) +/* This function is called from loop_version. It splits the entry edge + of the loop we want to version, adds the versioning condition, and + adjust the edges to the two versions of the loop appropriately. + e is an incoming edge. Returns the basic block containing the + condition. + + --- edge e ---- > [second_head] + + Split it and insert new conditional expression and adjust edges. + + --- edge e ---> [cond expr] ---> [first_head] + | + +---------> [second_head] + + THEN_PROB is the probability of then branch of the condition. */ + +static basic_block +lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head, + edge e, void *cond_expr, unsigned then_prob) { - basic_block src, dest, new_bb; - struct loop *loop_c; - edge new_e; + basic_block new_head = NULL; + edge e1; - src = e->src; - dest = e->dest; + gcc_assert (e->dest == second_head); - loop_c = find_common_loop (src->loop_father, dest->loop_father); + /* Split edge 'e'. This will create a new basic block, where we can + insert conditional expr. */ + new_head = split_edge (e); - /* Create basic block for it. */ + lv_add_condition_to_bb (first_head, second_head, new_head, + cond_expr); - new_bb = split_edge (e); - add_bb_to_loop (new_bb, loop_c); - new_bb->flags = insns ? BB_SUPERBLOCK : 0; + /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */ + e = single_succ_edge (new_head); + e1 = make_edge (new_head, first_head, + current_ir_type () == IR_GIMPLE ? EDGE_TRUE_VALUE : 0); + e1->probability = then_prob; + e->probability = REG_BR_PROB_BASE - then_prob; + e1->count = RDIV (e->count * e1->probability, REG_BR_PROB_BASE); + e->count = RDIV (e->count * e->probability, REG_BR_PROB_BASE); - new_e = new_bb->succ; - if (e->flags & EDGE_IRREDUCIBLE_LOOP) + set_immediate_dominator (CDI_DOMINATORS, first_head, new_head); + set_immediate_dominator (CDI_DOMINATORS, second_head, new_head); + + /* Adjust loop header phi nodes. */ + lv_adjust_loop_header_phi (first_head, second_head, new_head, e1); + + return new_head; +} + +/* Main entry point for Loop Versioning transformation. + + This transformation given a condition and a loop, creates + -if (condition) { loop_copy1 } else { loop_copy2 }, + where loop_copy1 is the loop transformed in one way, and loop_copy2 + is the loop transformed in another way (or unchanged). 'condition' + may be a run time test for things that were not resolved by static + analysis (overlapping ranges (anti-aliasing), alignment, etc.). + + THEN_PROB is the probability of the then edge of the if. THEN_SCALE + is the ratio by that the frequencies in the original loop should + be scaled. ELSE_SCALE is the ratio by that the frequencies in the + new loop should be scaled. + + If PLACE_AFTER is true, we place the new loop after LOOP in the + instruction stream, otherwise it is placed before LOOP. */ + +struct loop * +loop_version (struct loop *loop, + void *cond_expr, basic_block *condition_bb, + unsigned then_prob, unsigned then_scale, unsigned else_scale, + bool place_after) +{ + basic_block first_head, second_head; + edge entry, latch_edge, true_edge, false_edge; + int irred_flag; + struct loop *nloop; + basic_block cond_bb; + + /* Record entry and latch edges for the loop */ + entry = loop_preheader_edge (loop); + irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; + entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; + + /* Note down head of loop as first_head. */ + first_head = entry->dest; + + /* Duplicate loop. */ + if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, 1, + NULL, NULL, NULL, 0)) + return NULL; + + /* After duplication entry edge now points to new loop head block. + Note down new head as second_head. */ + second_head = entry->dest; + + /* Split loop entry edge and insert new block with cond expr. */ + cond_bb = lv_adjust_loop_entry_edge (first_head, second_head, + entry, cond_expr, then_prob); + if (condition_bb) + *condition_bb = cond_bb; + + if (!cond_bb) { - new_bb->flags |= BB_IRREDUCIBLE_LOOP; - new_e->flags |= EDGE_IRREDUCIBLE_LOOP; + entry->flags |= irred_flag; + return NULL; } - if (insns) - emit_insn_after (insns, BB_END (new_bb)); + latch_edge = single_succ_edge (get_bb_copy (loop->latch)); + + extract_cond_bb_edges (cond_bb, &true_edge, &false_edge); + nloop = loopify (latch_edge, + single_pred_edge (get_bb_copy (loop->header)), + cond_bb, true_edge, false_edge, + false /* Do not redirect all edges. */, + then_scale, else_scale); - if (dest->loop_father->latch == src) - dest->loop_father->latch = new_bb; + /* loopify redirected latch_edge. Update its PENDING_STMTS. */ + lv_flush_pending_stmts (latch_edge); - return new_bb; + /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */ + extract_cond_bb_edges (cond_bb, &true_edge, &false_edge); + lv_flush_pending_stmts (false_edge); + /* Adjust irreducible flag. */ + if (irred_flag) + { + cond_bb->flags |= BB_IRREDUCIBLE_LOOP; + loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP; + loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP; + single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP; + } + + if (place_after) + { + basic_block *bbs = get_loop_body_in_dom_order (nloop), after; + unsigned i; + + after = loop->latch; + + for (i = 0; i < nloop->num_nodes; i++) + { + move_block_after (bbs[i], after); + after = bbs[i]; + } + free (bbs); + } + + /* At this point condition_bb is loop preheader with two successors, + first_head and second_head. Make sure that loop preheader has only + one successor. */ + split_edge (loop_preheader_edge (loop)); + split_edge (loop_preheader_edge (nloop)); + + return nloop; } -/* Uses the natural loop discovery to recreate loop notes. */ +/* 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 -create_loop_notes (void) +fix_loop_structure (bitmap changed_bbs) { - rtx insn, head, end; - struct loops loops; - struct loop *loop; - basic_block *first, *last, bb, pbb; - struct loop **stack, **top; + basic_block bb; + struct loop *loop, *ploop; + loop_iterator li; + bool record_exits = false; + struct loop **superloop = XNEWVEC (struct loop *, number_of_loops ()); + + /* 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; + } -#ifdef ENABLE_CHECKING - /* Verify that there really are no loop notes. */ - for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) - gcc_assert (!NOTE_P (insn) || - NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG); -#endif + if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) + { + release_recorded_exits (); + record_exits = true; + } - flow_loops_find (&loops, LOOP_TREE); - free_dominance_info (CDI_DOMINATORS); - if (loops.num > 1) + /* 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) { - last = xcalloc (loops.num, sizeof (basic_block)); + if (loop->header) + continue; - FOR_EACH_BB (bb) + while (loop->inner) { - for (loop = bb->loop_father; loop->outer; loop = loop->outer) - last[loop->num] = bb; + ploop = loop->inner; + flow_loop_tree_node_remove (ploop); + flow_loop_tree_node_add (loop_outer (loop), ploop); } - first = xcalloc (loops.num, sizeof (basic_block)); - stack = xcalloc (loops.num, sizeof (struct loop *)); - top = stack; + /* 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) { - for (loop = bb->loop_father; loop->outer; loop = loop->outer) - { - if (!first[loop->num]) - { - *top++ = loop; - first[loop->num] = bb; - } + if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux) + bitmap_set_bit (changed_bbs, bb->index); - if (bb == last[loop->num]) - { - /* Prevent loops from overlapping. */ - while (*--top != loop) - last[(*top)->num] = EXIT_BLOCK_PTR; - - /* If loop starts with jump into it, place the note in - front of the jump. */ - insn = PREV_INSN (BB_HEAD (first[loop->num])); - if (insn - && BARRIER_P (insn)) - insn = PREV_INSN (insn); - - if (insn - && JUMP_P (insn) - && any_uncondjump_p (insn) - && onlyjump_p (insn)) - { - pbb = BLOCK_FOR_INSN (insn); - gcc_assert (pbb && pbb->succ && !pbb->succ->succ_next); - - if (!flow_bb_inside_loop_p (loop, pbb->succ->dest)) - insn = BB_HEAD (first[loop->num]); - } - else - insn = BB_HEAD (first[loop->num]); - - head = BB_HEAD (first[loop->num]); - emit_note_before (NOTE_INSN_LOOP_BEG, insn); - BB_HEAD (first[loop->num]) = head; - - /* Position the note correctly wrto barrier. */ - insn = BB_END (last[loop->num]); - if (NEXT_INSN (insn) - && BARRIER_P (NEXT_INSN (insn))) - insn = NEXT_INSN (insn); - - end = BB_END (last[loop->num]); - emit_note_after (NOTE_INSN_LOOP_END, insn); - BB_END (last[loop->num]) = end; - } - } + bb->aux = NULL; } - - free (first); - free (last); - free (stack); } - flow_loops_free (&loops); + + if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)) + create_preheaders (CP_SIMPLE_PREHEADERS); + + 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 (); + +#ifdef ENABLE_CHECKING + verify_loop_structure (); +#endif }