X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcfgloopmanip.c;h=638b2996584052c535005b4f6b9acc61cd3dfea8;hb=6e8435a1039a5266c33343f12606821de0c68c54;hp=77988c20c2f61c2ce445777cd1dfc08359ad6d99;hpb=050ecc41f80af0d1719bab230a2afc85f95bb236;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 77988c20c2f..638b2996584 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1,5 +1,5 @@ /* Loop manipulation code for GNU compiler. - Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. This file is part of GCC. @@ -15,8 +15,8 @@ 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. */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ #include "config.h" #include "system.h" @@ -28,6 +28,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "basic-block.h" #include "cfgloop.h" #include "cfglayout.h" +#include "cfghooks.h" #include "output.h" static void duplicate_subloops (struct loops *, struct loop *, struct loop *); @@ -40,34 +41,16 @@ static bool rpe_enum_p (basic_block, 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 void fix_loop_placements (struct loops *, struct loop *, bool *); static bool fix_bb_placement (struct loops *, basic_block); -static void fix_bb_placements (struct loops *, basic_block); +static void fix_bb_placements (struct loops *, basic_block, bool *); 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 unloop (struct loops *, struct loop *); +static void unloop (struct loops *, 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, void *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) @@ -101,7 +84,7 @@ find_path (edge e, basic_block **bbs) 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); } @@ -149,9 +132,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 (struct loops *loops, basic_block from, + bool *irred_invalidated) { sbitmap in_queue; basic_block *queue, *qtop, *qbeg, *qend; @@ -175,7 +163,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; @@ -203,12 +191,21 @@ fix_bb_placements (struct loops *loops, basic_block 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_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; @@ -241,76 +238,6 @@ 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) - { - edge_iterator ei; - bb = stack[--stack_top]; - RESET_BIT (on_stack, bb->index); - - FOR_EACH_EDGE (e, ei, bb->preds) - 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 = EDGE_COUNT (bb->succs); - edges = xmalloc (n_edges * sizeof (edge)); - FOR_EACH_EDGE (e, ei, bb->succs) - edges[ei.index] = 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 @@ -322,17 +249,25 @@ remove_path (struct loops *loops, edge e) basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb; int i, nrem, n_bord_bbs, n_dom_bbs; sbitmap seen; - bool deleted; + bool deleted, irred_invalidated = false; if (!loop_delete_branch_edge (e, 0)) 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 (EDGE_COUNT (e->dest->preds) > 1) - e = EDGE_PRED (loop_split_edge_with (e, NULL_RTX), 0); + if (!single_pred_p (e->dest)) + e = single_pred_edge (loop_split_edge_with (e, NULL_RTX)); /* 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 @@ -341,13 +276,13 @@ remove_path (struct loops *loops, edge e) while (e->src->loop_father->outer && dominated_by_p (CDI_DOMINATORS, e->src->loop_father->latch, e->dest)) - unloop (loops, e->src->loop_father); + unloop (loops, 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); @@ -363,6 +298,9 @@ remove_path (struct loops *loops, edge e) { SET_BIT (seen, ae->dest->index); bord_bbs[n_bord_bbs++] = ae->dest; + + if (ae->flags & EDGE_IRREDUCIBLE_LOOP) + irred_invalidated = true; } } @@ -370,7 +308,7 @@ remove_path (struct loops *loops, edge e) from = e->src; deleted = loop_delete_branch_edge (e, 1); gcc_assert (deleted); - dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); + dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); /* Cancel loops contained in the path. */ for (i = 0; i < nrem; i++) @@ -404,17 +342,16 @@ remove_path (struct loops *loops, edge e) /* 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]); 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 (loops, from, &irred_invalidated); + fix_loop_placements (loops, from->loop_father, &irred_invalidated); + + if (irred_invalidated + && (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) != 0) + mark_irreducible_loops (loops); return true; } @@ -439,7 +376,7 @@ add_loop (struct loops *loops, struct loop *loop) loop->level = 1; /* Find its nodes. */ - bbs = xcalloc (n_basic_blocks, sizeof (basic_block)); + bbs = XCNEWVEC (basic_block, n_basic_blocks); n = dfs_enumerate_from (loop->latch, 1, alp_enum_p, bbs, n_basic_blocks, loop->header); @@ -450,24 +387,6 @@ add_loop (struct loops *loops, struct loop *loop) free (bbs); } -/* 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; - - for (i = 0; i < nbbs; i++) - { - edge_iterator ei; - bbs[i]->frequency = (bbs[i]->frequency * num) / den; - bbs[i]->count = RDIV (bbs[i]->count * num, den); - FOR_EACH_EDGE (e, ei, bbs[i]->succs) - e->count = (e->count * num) /den; - } -} - /* Multiply all frequencies in LOOP by NUM/DEN. */ static void scale_loop_frequencies (struct loop *loop, int num, int den) @@ -475,7 +394,7 @@ 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); } @@ -489,7 +408,7 @@ scale_loop_frequencies (struct loop *loop, int num, int den) Returns newly created loop. */ struct loop * -loopify (struct loops *loops, edge latch_edge, edge header_edge, +loopify (struct loops *loops, edge latch_edge, edge header_edge, basic_block switch_bb, edge true_edge, edge false_edge, bool redirect_all_edges) { @@ -498,7 +417,7 @@ loopify (struct loops *loops, edge latch_edge, edge header_edge, basic_block *dom_bbs, *body; unsigned n_dom_bbs, i; sbitmap seen; - struct loop *loop = xcalloc (1, sizeof (struct loop)); + struct loop *loop = XCNEW (struct loop); struct loop *outer = succ_bb->loop_father->outer; int freq, prob, tot_prob; gcov_type cnt; @@ -524,8 +443,8 @@ loopify (struct loops *loops, edge latch_edge, edge header_edge, if (redirect_all_edges) { loop_redirect_edge (header_edge, switch_bb); - loop_redirect_edge (false_edge, loop->header); - + 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); @@ -549,7 +468,7 @@ loopify (struct loops *loops, edge latch_edge, edge header_edge, 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)); + dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); n_dom_bbs = 0; seen = sbitmap_alloc (last_basic_block); sbitmap_zero (seen); @@ -583,16 +502,22 @@ loopify (struct loops *loops, edge latch_edge, edge header_edge, /* Remove the latch edge of a LOOP and update LOOPS tree to indicate that the LOOP was removed. After this function, original loop latch will - have no successor, which caller is expected to fix somehow. */ + 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 loops *loops, struct loop *loop) +unloop (struct loops *loops, 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 @@ -601,7 +526,6 @@ 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) @@ -623,25 +547,19 @@ unloop (struct loops *loops, struct loop *loop) loops->parray[loop->num] = NULL; flow_loop_free (loop); - remove_edge (EDGE_SUCC (latch, 0)); - 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); + remove_edge (single_succ_edge (latch)); + + /* 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 (loops, latch, &dummy); } /* 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 + FATHER, and set it as outer loop of LOOP. Return true if placement of LOOP changed. */ + int fix_loop_placement (struct loop *loop) { @@ -676,9 +594,14 @@ fix_loop_placement (struct loop *loop) /* 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 loops *loops, struct loop *loop, + bool *irred_invalidated) { struct loop *outer; @@ -686,14 +609,15 @@ fix_loop_placements (struct loops *loops, struct loop *loop) { outer = loop->outer; 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 (loops, loop_preheader_edge (loop)->src, + irred_invalidated); loop = outer; } } @@ -715,7 +639,7 @@ struct loop * duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target) { struct loop *cloop; - cloop = xcalloc (1, sizeof (struct loop)); + cloop = XCNEW (struct loop); place_new_loop (loops, cloop); /* Initialize copied loop. */ @@ -780,7 +704,7 @@ loop_delete_branch_edge (edge e, int really_delete) edge snd; gcc_assert (EDGE_COUNT (src->succs) > 1); - + /* Cannot handle more than two exit edges. */ if (EDGE_COUNT (src->succs) > 2) return false; @@ -802,9 +726,9 @@ loop_delete_branch_edge (edge e, int really_delete) if (!redirect_edge_and_branch (e, newdest)) return false; - EDGE_SUCC (src, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP; - EDGE_SUCC (src, 0)->flags |= irr; - + single_succ_edge (src)->flags &= ~EDGE_IRREDUCIBLE_LOOP; + single_succ_edge (src)->flags |= irr; + return true; } @@ -817,7 +741,7 @@ can_duplicate_loop_p (struct loop *loop) ret = can_copy_bbs_p (bbs, loop->num_nodes); free (bbs); - + return ret; } @@ -831,19 +755,19 @@ update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs, unsigned i; for (i = 0; i < nbbs; i++) - bbs[i]->rbi->duplicated = 1; + bbs[i]->flags |= BB_DUPLICATED; for (; loop->outer; loop = loop->outer) { if (!loop->single_exit) continue; - if (loop->single_exit->src->rbi->duplicated) + if (loop->single_exit->src->flags & BB_DUPLICATED) loop->single_exit = NULL; } for (i = 0; i < nbbs; i++) - bbs[i]->rbi->duplicated = 0; + bbs[i]->flags &= ~BB_DUPLICATED; } /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating @@ -856,7 +780,7 @@ 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 +bool duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, unsigned int ndupl, sbitmap wont_exit, edge orig, edge *to_remove, @@ -878,6 +802,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, 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; gcc_assert (e->dest == loop->header); gcc_assert (ndupl > 0); @@ -889,7 +814,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)) @@ -897,7 +825,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. */ @@ -924,14 +852,35 @@ 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)); + scale_step = XNEWVEC (int, ndupl); 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 @@ -966,15 +915,13 @@ 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; - - first_active = xmalloc (n * sizeof (basic_block)); + first_active = XNEWVEC (basic_block, n); if (is_latch) { memcpy (first_active, bbs, n * sizeof (basic_block)); @@ -992,22 +939,29 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, 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 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; @@ -1016,13 +970,13 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, new_bb->flags |= BB_IRREDUCIBLE_LOOP; FOR_EACH_EDGE (ae, ei, new_bb->succs) - if (ae->dest->rbi->duplicated + 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. */ @@ -1032,7 +986,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 @@ -1053,25 +1007,25 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, 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); - + /* 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); } @@ -1082,7 +1036,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, int n_dom_bbs,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++) @@ -1092,7 +1046,7 @@ duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, 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); } @@ -1121,10 +1075,10 @@ mfb_keep_just (edge e) static void mfb_update_loops (basic_block jump) { - struct loop *loop = EDGE_SUCC (jump, 0)->dest->loop_father; + struct loop *loop = single_succ (jump)->loop_father; if (dom_computed[CDI_DOMINATORS]) - set_immediate_dominator (CDI_DOMINATORS, jump, EDGE_PRED (jump, 0)->src); + set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump)); add_bb_to_loop (jump, loop); loop->latch = jump; } @@ -1142,6 +1096,8 @@ create_preheader (struct loop *loop, int flags) struct loop *cloop, *ploop; int nentry = 0; bool irred = false; + bool latch_edge_was_fallthru; + edge one_succ_pred = 0; edge_iterator ei; cloop = loop->outer; @@ -1152,6 +1108,8 @@ create_preheader (struct loop *loop, int flags) continue; irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0; nentry++; + if (single_succ_p (e->src)) + one_succ_pred = e; } gcc_assert (nentry); if (nentry == 1) @@ -1161,11 +1119,12 @@ create_preheader (struct loop *loop, int flags) e = EDGE_PRED (loop->header, EDGE_PRED (loop->header, 0)->src == loop->latch); - if (!(flags & CP_SIMPLE_PREHEADERS) || EDGE_COUNT (e->src->succs) == 1) + if (!(flags & CP_SIMPLE_PREHEADERS) || single_succ_p (e->src)) return NULL; } mfb_kj_edge = loop_latch_edge (loop); + latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0; fallthru = make_forwarder_block (loop->header, mfb_keep_just, mfb_update_loops); dummy = fallthru->src; @@ -1177,13 +1136,23 @@ create_preheader (struct loop *loop, int flags) if (ploop->latch == dummy) ploop->latch = fallthru->dest; - /* Reorganize blocks so that the preheader is not stuck in the middle of the - loop. */ - - /* Get an edge that is different from the one from loop->latch to - dummy. */ - e = EDGE_PRED (dummy, EDGE_PRED (dummy, 0)->src == loop->latch); - move_block_after (dummy, e->src); + /* Try to be clever in placing the newly created preheader. The idea is to + avoid breaking any "fallthruness" relationship between blocks. + + 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); + + move_block_after (dummy, e->src); + } loop->header->loop_father = loop; add_bb_to_loop (dummy, cloop); @@ -1191,7 +1160,7 @@ create_preheader (struct loop *loop, int flags) if (irred) { dummy->flags |= BB_IRREDUCIBLE_LOOP; - EDGE_SUCC (dummy, 0)->flags |= EDGE_IRREDUCIBLE_LOOP; + single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP; } if (dump_file) @@ -1224,7 +1193,7 @@ force_single_succ_latches (struct loops *loops) for (i = 1; i < loops->num; i++) { loop = loops->parray[i]; - if (loop->latch != loop->header && EDGE_COUNT (loop->latch->succs) == 1) + if (loop->latch != loop->header && single_succ_p (loop->latch)) continue; e = find_edge (loop->latch, loop->header); @@ -1264,96 +1233,256 @@ loop_split_edge_with (edge e, rtx insns) return new_bb; } -/* Uses the natural loop discovery to recreate loop notes. */ +/* 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] +*/ + +static basic_block +lv_adjust_loop_entry_edge (basic_block first_head, + basic_block second_head, + edge e, + void *cond_expr) +{ + basic_block new_head = NULL; + edge e1; + + gcc_assert (e->dest == second_head); + + /* Split edge 'e'. This will create a new basic block, where we can + insert conditional expr. */ + new_head = split_edge (e); + + + lv_add_condition_to_bb (first_head, second_head, new_head, + cond_expr); + + /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */ + e1 = make_edge (new_head, first_head, ir_type () ? EDGE_TRUE_VALUE : 0); + 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.). + + 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 loops *loops, struct loop * loop, + void *cond_expr, basic_block *condition_bb, + bool place_after) +{ + basic_block first_head, second_head; + edge entry, latch_edge, exit, true_edge, false_edge; + int irred_flag; + struct loop *nloop; + basic_block cond_bb; + + /* CHECKME: Loop versioning does not handle nested loop at this point. */ + if (loop->inner) + return NULL; + + /* 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, loops, 1, + NULL, 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); + if (condition_bb) + *condition_bb = cond_bb; + + if (!cond_bb) + { + entry->flags |= irred_flag; + return NULL; + } + + latch_edge = single_succ_edge (get_bb_copy (loop->latch)); + + extract_cond_bb_edges (cond_bb, &true_edge, &false_edge); + nloop = loopify (loops, + latch_edge, + single_pred_edge (get_bb_copy (loop->header)), + cond_bb, true_edge, false_edge, + false /* Do not redirect all edges. */); + + exit = loop->single_exit; + if (exit) + nloop->single_exit = find_edge (get_bb_copy (exit->src), exit->dest); + + /* loopify redirected latch_edge. Update its PENDING_STMTS. */ + lv_flush_pending_stmts (latch_edge); + + /* 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 predheader with two successors, + first_head and second_head. Make sure that loop predheader has only + one successor. */ + loop_split_edge_with (loop_preheader_edge (loop), NULL); + loop_split_edge_with (loop_preheader_edge (nloop), NULL); + + 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 subloobs (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 (struct loops *loops, bitmap changed_bbs) { - rtx insn, head, end; - struct loops loops; - struct loop *loop; - basic_block *first, *last, bb, pbb; - struct loop **stack, **top; - -#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 - - flow_loops_find (&loops, LOOP_TREE); - free_dominance_info (CDI_DOMINATORS); - if (loops.num > 1) + basic_block bb; + struct loop *loop, *ploop; + unsigned i; + + /* Remove the old bb -> loop mapping. */ + FOR_EACH_BB (bb) { - last = xcalloc (loops.num, sizeof (basic_block)); + bb->aux = (void *) (size_t) bb->loop_father->depth; + bb->loop_father = loops->tree_root; + } - FOR_EACH_BB (bb) + /* Remove the dead loops from structures. */ + loops->tree_root->num_nodes = n_basic_blocks; + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + if (!loop) + continue; + + loop->num_nodes = 0; + if (loop->header) + continue; + + 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, ploop); } - first = xcalloc (loops.num, sizeof (basic_block)); - stack = xcalloc (loops.num, sizeof (struct loop *)); - top = stack; + /* Remove the loop and free its data. */ + flow_loop_tree_node_remove (loop); + loops->parray[loop->num] = NULL; + flow_loop_free (loop); + } - FOR_EACH_BB (bb) + /* Rescan the bodies of loops, starting from the outermost. */ + loop = loops->tree_root; + while (1) + { + if (loop->inner) + loop = loop->inner; + else { - for (loop = bb->loop_father; loop->outer; loop = loop->outer) - { - if (!first[loop->num]) - { - *top++ = loop; - first[loop->num] = bb; - } - - 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 && EDGE_COUNT (pbb->succs) == 1); - - if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (pbb, 0)->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; - } - } + while (!loop->next + && loop != loops->tree_root) + loop = loop->outer; + if (loop == loops->tree_root) + break; + + loop = loop->next; + } + + loop->num_nodes = flow_loop_nodes_find (loop->header, loop); + } + + /* Now fix the loop nesting. */ + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + if (!loop) + continue; + + bb = loop_preheader_edge (loop)->src; + if (bb->loop_father != loop->outer) + { + flow_loop_tree_node_remove (loop); + flow_loop_tree_node_add (bb->loop_father, loop); } + } - free (first); - free (last); - free (stack); + /* Mark the blocks whose loop has changed. */ + FOR_EACH_BB (bb) + { + if (changed_bbs + && (void *) (size_t) bb->loop_father->depth != bb->aux) + bitmap_set_bit (changed_bbs, bb->index); + + bb->aux = NULL; } - flow_loops_free (&loops); + + if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) + mark_single_exit_loops (loops); + if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) + mark_irreducible_loops (loops); }