| /* Loop manipulation code for GNU compiler. |
| Copyright (C) 2002, 2003, 2004, 2005 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 |
| version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 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, 51 Franklin Street, Fifth Floor, Boston, MA |
| 02110-1301, USA. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #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" |
| /* APPLE LOCAL 4321079 */ |
| #include "options.h" |
| |
| static void duplicate_subloops (struct loops *, struct loop *, struct loop *); |
| static void copy_loops_to (struct loops *, 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 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 *, bool *); |
| static bool fix_bb_placement (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 basic_block create_preheader (struct loop *, int); |
| static void unloop (struct loops *, struct loop *, bool *); |
| |
| #define RDIV(X,Y) (((X) + (Y) / 2) / (Y)) |
| |
| /* Checks whether basic block BB is dominated by DATA. */ |
| static bool |
| rpe_enum_p (basic_block bb, void *data) |
| { |
| return dominated_by_p (CDI_DOMINATORS, bb, data); |
| } |
| |
| /* Remove basic blocks BBS from loop structure and dominance info, |
| and delete them afterwards. */ |
| 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]); |
| } |
| } |
| |
| /* Find path -- i.e. the basic blocks dominated by edge E and put them |
| into array BBS, that will be allocated large enough to contain them. |
| E->dest must have exactly one predecessor for this to work (it is |
| easy to achieve and we do not put it here because we do not want to |
| alter anything by this function). The number of basic blocks in the |
| path is returned. */ |
| static int |
| find_path (edge e, basic_block **bbs) |
| { |
| gcc_assert (EDGE_COUNT (e->dest->preds) <= 1); |
| |
| /* Find bbs in the path. */ |
| *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 -- |
| 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 |
| Returns true if we had to move BB into other loop to enforce this condition, |
| 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) |
| { |
| edge e; |
| edge_iterator ei; |
| struct loop *loop = loops->tree_root, *act; |
| |
| 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; |
| |
| if (flow_loop_nested_p (loop, act)) |
| loop = act; |
| } |
| |
| if (loop == bb->loop_father) |
| return false; |
| |
| remove_bb_from_loops (bb); |
| add_bb_to_loop (bb, loop); |
| |
| return true; |
| } |
| |
| /* 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 |
| his placement no longer has to be correct, and iteratively fix placement of |
| 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. |
| |
| 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, |
| bool *irred_invalidated) |
| { |
| sbitmap in_queue; |
| basic_block *queue, *qtop, *qbeg, *qend; |
| struct loop *base_loop; |
| edge e; |
| |
| /* We pass through blocks back-reachable from FROM, testing whether some |
| of their successors moved to outer loop. It may be necessary to |
| iterate several times, but it is finite, as we stop unless we move |
| the basic block up the loop structure. The whole story is a bit |
| more complicated due to presence of subloops, those are moved using |
| fix_loop_placement. */ |
| |
| base_loop = from->loop_father; |
| if (base_loop == loops->tree_root) |
| return; |
| |
| in_queue = sbitmap_alloc (last_basic_block); |
| sbitmap_zero (in_queue); |
| SET_BIT (in_queue, from->index); |
| /* Prevent us from going out of the base_loop. */ |
| SET_BIT (in_queue, base_loop->header->index); |
| |
| queue = XNEWVEC (basic_block, base_loop->num_nodes + 1); |
| qtop = queue + base_loop->num_nodes + 1; |
| qbeg = queue; |
| qend = queue + 1; |
| *qbeg = from; |
| |
| while (qbeg != qend) |
| { |
| edge_iterator ei; |
| from = *qbeg; |
| qbeg++; |
| if (qbeg == qtop) |
| qbeg = queue; |
| RESET_BIT (in_queue, from->index); |
| |
| if (from->loop_father->header == from) |
| { |
| /* Subloop header, maybe move the loop upward. */ |
| if (!fix_loop_placement (from->loop_father)) |
| continue; |
| } |
| else |
| { |
| /* Ordinary basic block. */ |
| if (!fix_bb_placement (loops, 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; |
| |
| /* If it is subloop, then it either was not moved, or |
| the path up the loop tree from base_loop do not contain |
| it. */ |
| nca = find_common_loop (pred->loop_father, base_loop); |
| if (pred->loop_father != base_loop |
| && (nca == base_loop |
| || nca != pred->loop_father)) |
| pred = pred->loop_father->header; |
| else if (!flow_loop_nested_p (from->loop_father, pred->loop_father)) |
| { |
| /* No point in processing it. */ |
| continue; |
| } |
| |
| if (TEST_BIT (in_queue, pred->index)) |
| continue; |
| |
| /* Schedule the basic block. */ |
| *qend = pred; |
| qend++; |
| if (qend == qtop) |
| qend = queue; |
| SET_BIT (in_queue, pred->index); |
| } |
| } |
| free (in_queue); |
| free (queue); |
| } |
| |
| /* 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). */ |
| bool |
| remove_path (struct loops *loops, edge e) |
| { |
| edge ae; |
| basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb; |
| int i, nrem, n_bord_bbs, n_dom_bbs; |
| sbitmap seen; |
| 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 (!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 |
| 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 |
| && dominated_by_p (CDI_DOMINATORS, |
| e->src->loop_father->latch, e->dest)) |
| unloop (loops, e->src->loop_father, &irred_invalidated); |
| |
| /* Identify the path. */ |
| nrem = find_path (e, &rem_bbs); |
| |
| n_bord_bbs = 0; |
| bord_bbs = XCNEWVEC (basic_block, n_basic_blocks); |
| seen = sbitmap_alloc (last_basic_block); |
| sbitmap_zero (seen); |
| |
| /* Find "border" hexes -- i.e. those with predecessor in removed path. */ |
| for (i = 0; i < nrem; i++) |
| SET_BIT (seen, rem_bbs[i]->index); |
| for (i = 0; i < nrem; i++) |
| { |
| edge_iterator ei; |
| bb = rem_bbs[i]; |
| 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 = XCNEWVEC (basic_block, n_basic_blocks); |
| |
| /* 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); |
| |
| 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++) |
| { |
| basic_block ldom; |
| |
| bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]); |
| if (TEST_BIT (seen, bb->index)) |
| continue; |
| SET_BIT (seen, bb->index); |
| |
| for (ldom = first_dom_son (CDI_DOMINATORS, bb); |
| ldom; |
| ldom = next_dom_son (CDI_DOMINATORS, ldom)) |
| if (!dominated_by_p (CDI_DOMINATORS, from, ldom)) |
| dom_bbs[n_dom_bbs++] = ldom; |
| } |
| |
| free (seen); |
| |
| /* Recount dominators. */ |
| iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); |
| free (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, &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; |
| } |
| |
| /* Predicate for enumeration in add_loop. */ |
| static bool |
| alp_enum_p (basic_block bb, void *alp_header) |
| { |
| return bb != (basic_block) alp_header; |
| } |
| |
| /* 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) |
| { |
| basic_block *bbs; |
| int i, n; |
| |
| /* Add it to loop structure. */ |
| place_new_loop (loops, loop); |
| loop->level = 1; |
| |
| /* Find its nodes. */ |
| bbs = XCNEWVEC (basic_block, n_basic_blocks); |
| n = dfs_enumerate_from (loop->latch, 1, alp_enum_p, |
| bbs, n_basic_blocks, loop->header); |
| |
| for (i = 0; i < n; i++) |
| add_bb_to_loop (bbs[i], loop); |
| add_bb_to_loop (loop->header, loop); |
| |
| free (bbs); |
| } |
| |
| /* Multiply all frequencies in LOOP by NUM/DEN. */ |
| static void |
| scale_loop_frequencies (struct loop *loop, int num, int den) |
| { |
| basic_block *bbs; |
| |
| bbs = get_loop_body (loop); |
| scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den); |
| free (bbs); |
| } |
| |
| /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting |
| latch to header and update loop tree stored in LOOPS 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, |
| FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and |
| TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE. |
| Returns newly created loop. */ |
| |
| struct loop * |
| loopify (struct loops *loops, edge latch_edge, edge header_edge, |
| basic_block switch_bb, edge true_edge, edge false_edge, |
| bool redirect_all_edges) |
| { |
| 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 = XCNEW (struct loop); |
| struct loop *outer = succ_bb->loop_father->outer; |
| int freq, prob, tot_prob; |
| 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 = EDGE_SUCC (switch_bb, 0)->probability; |
| tot_prob = prob + EDGE_SUCC (switch_bb, 1)->probability; |
| if (tot_prob == 0) |
| tot_prob = 1; |
| |
| /* Redirect edges. */ |
| loop_redirect_edge (latch_edge, loop->header); |
| loop_redirect_edge (true_edge, succ_bb); |
| |
| /* 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); |
| } |
| |
| set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb); |
| |
| /* Compute new loop. */ |
| add_loop (loops, loop); |
| flow_loop_tree_node_add (outer, loop); |
| |
| /* Add switch_bb to appropriate loop. */ |
| add_bb_to_loop (switch_bb, outer); |
| |
| /* Fix frequencies. */ |
| 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; |
| 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 = XCNEWVEC (basic_block, n_basic_blocks); |
| 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++) |
| { |
| 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; |
| } |
| } |
| |
| iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); |
| |
| free (body); |
| free (seen); |
| free (dom_bbs); |
| |
| return loop; |
| } |
| |
| /* 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. |
| |
| 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, bool *irred_invalidated) |
| { |
| basic_block *body; |
| struct loop *ploop; |
| unsigned i, n; |
| basic_block latch = loop->latch; |
| 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 |
| is the placement of loops and basic blocks inside the loop tree. We |
| move them all to the loop->outer, and then let fix_bb_placements do |
| its work. */ |
| |
| body = get_loop_body (loop); |
| 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); |
| } |
| free(body); |
| |
| while (loop->inner) |
| { |
| ploop = loop->inner; |
| flow_loop_tree_node_remove (ploop); |
| flow_loop_tree_node_add (loop->outer, 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 (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 true if placement of |
| LOOP changed. */ |
| |
| int |
| fix_loop_placement (struct loop *loop) |
| { |
| basic_block *body; |
| unsigned i; |
| edge e; |
| edge_iterator ei; |
| struct loop *father = loop->pred[0], *act; |
| |
| body = get_loop_body (loop); |
| for (i = 0; i < loop->num_nodes; i++) |
| FOR_EACH_EDGE (e, ei, body[i]->succs) |
| if (!flow_bb_inside_loop_p (loop, e->dest)) |
| { |
| act = find_common_loop (loop, e->dest->loop_father); |
| if (flow_loop_nested_p (father, act)) |
| father = act; |
| } |
| free (body); |
| |
| 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; |
| } |
| |
| /* 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. |
| |
| 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, |
| bool *irred_invalidated) |
| { |
| struct loop *outer; |
| |
| while (loop->outer) |
| { |
| outer = loop->outer; |
| if (!fix_loop_placement (loop)) |
| 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, |
| 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. */ |
| struct loop * |
| duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target) |
| { |
| struct loop *cloop; |
| cloop = XCNEW (struct loop); |
| place_new_loop (loops, cloop); |
| |
| /* Initialize copied loop. */ |
| cloop->level = loop->level; |
| |
| /* Set it as copy of loop. */ |
| loop->copy = cloop; |
| |
| /* Add it to target. */ |
| flow_loop_tree_node_add (target, cloop); |
| |
| return cloop; |
| } |
| |
| /* 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) |
| { |
| struct loop *aloop, *cloop; |
| |
| for (aloop = loop->inner; aloop; aloop = aloop->next) |
| { |
| cloop = duplicate_loop (loops, aloop, target); |
| duplicate_subloops (loops, 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. */ |
| static void |
| copy_loops_to (struct loops *loops, 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); |
| } |
| } |
| |
| /* Redirects edge E to basic block DEST. */ |
| static void |
| loop_redirect_edge (edge e, basic_block dest) |
| { |
| if (e->dest == dest) |
| return; |
| |
| 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 (EDGE_COUNT (src->succs) > 1); |
| |
| /* Cannot handle more than two exit edges. */ |
| if (EDGE_COUNT (src->succs) > 2) |
| return false; |
| /* And it must be just a simple branch. */ |
| if (!any_condjump_p (BB_END (src))) |
| return false; |
| |
| snd = e == EDGE_SUCC (src, 0) ? EDGE_SUCC (src, 1) : EDGE_SUCC (src, 0); |
| 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; |
| single_succ_edge (src)->flags &= ~EDGE_IRREDUCIBLE_LOOP; |
| single_succ_edge (src)->flags |= irr; |
| |
| return true; |
| } |
| |
| /* Check whether LOOP's body can be duplicated. */ |
| bool |
| can_duplicate_loop_p (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. */ |
| |
| static void |
| update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs, |
| struct loop *loop) |
| { |
| unsigned i; |
| |
| for (i = 0; i < nbbs; i++) |
| bbs[i]->flags |= BB_DUPLICATED; |
| |
| for (; loop->outer; loop = loop->outer) |
| { |
| if (!loop->single_exit) |
| continue; |
| |
| if (loop->single_exit->src->flags & BB_DUPLICATED) |
| loop->single_exit = NULL; |
| } |
| |
| for (i = 0; i < nbbs; i++) |
| bbs[i]->flags &= ~BB_DUPLICATED; |
| } |
| |
| /* 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 |
| 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 |
| edge, it peels the loop). Store edges created by copying ORIG edge from |
| copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to |
| 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. */ |
| 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, |
| unsigned int *n_to_remove, int flags) |
| { |
| struct loop *target, *aloop; |
| struct loop **orig_loops; |
| unsigned n_orig_loops; |
| basic_block header = loop->header, latch = loop->latch; |
| basic_block *new_bbs, *bbs, *first_active; |
| basic_block new_bb, bb, first_active_latch = NULL; |
| edge ae, latch_edge; |
| edge spec_edges[2], new_spec_edges[2]; |
| #define SE_LATCH 0 |
| #define SE_ORIG 1 |
| unsigned i, j, n; |
| int is_latch = (latch == e->src); |
| int scale_act = 0, *scale_step = NULL, scale_main = 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; |
| |
| gcc_assert (e->dest == loop->header); |
| gcc_assert (ndupl > 0); |
| |
| if (orig) |
| { |
| /* Orig must be edge out of the loop. */ |
| gcc_assert (flow_bb_inside_loop_p (loop, orig->src)); |
| gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest)); |
| } |
| |
| 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)) |
| { |
| free (bbs); |
| return false; |
| } |
| 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. */ |
| add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP; |
| gcc_assert (!is_latch || !add_irreducible_flag); |
| |
| /* Find edge from latch. */ |
| latch_edge = loop_latch_edge (loop); |
| |
| if (flags & DLTHE_FLAG_UPDATE_FREQ) |
| { |
| /* Calculate coefficients by that we have to scale frequencies |
| of duplicated loop bodies. */ |
| freq_in = header->frequency; |
| freq_le = EDGE_FREQUENCY (latch_edge); |
| if (freq_in == 0) |
| freq_in = 1; |
| if (freq_in < freq_le) |
| freq_in = freq_le; |
| freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le; |
| if (freq_out_orig > freq_in - freq_le) |
| freq_out_orig = freq_in - freq_le; |
| prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in); |
| prob_pass_wont_exit = |
| RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in); |
| |
| 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; |
| |
| /* 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 |
| : prob_pass_thru; |
| p = prob_pass_main; |
| scale_main = REG_BR_PROB_BASE; |
| for (i = 0; i < ndupl; i++) |
| { |
| scale_main += p; |
| p = RDIV (p * scale_step[i], REG_BR_PROB_BASE); |
| } |
| scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main); |
| scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE); |
| } |
| else |
| { |
| scale_main = REG_BR_PROB_BASE; |
| for (i = 0; i < ndupl; i++) |
| scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE); |
| scale_act = REG_BR_PROB_BASE - prob_pass_thru; |
| } |
| for (i = 0; i < ndupl; i++) |
| gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE); |
| gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE |
| && scale_act >= 0 && scale_act <= REG_BR_PROB_BASE); |
| } |
| |
| /* Loop the new bbs will belong to. */ |
| target = e->src->loop_father; |
| |
| /* Original loops. */ |
| n_orig_loops = 0; |
| for (aloop = loop->inner; aloop; aloop = aloop->next) |
| n_orig_loops++; |
| 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; |
| |
| 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 bbs. */ |
| copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop, |
| place_after); |
| place_after = new_spec_edges[SE_LATCH]->src; |
| |
| 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]->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_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]->flags &= ~BB_DUPLICATED; |
| } |
| |
| /* Redirect the special edges. */ |
| if (is_latch) |
| { |
| redirect_edge_and_branch_force (latch_edge, new_bbs[0]); |
| 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[n - 1]; |
| e = latch_edge = new_spec_edges[SE_LATCH]; |
| } |
| else |
| { |
| redirect_edge_and_branch_force (new_spec_edges[SE_LATCH], |
| loop->header); |
| redirect_edge_and_branch_force (e, new_bbs[0]); |
| set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src); |
| e = new_spec_edges[SE_LATCH]; |
| } |
| |
| /* Record exit edge in this copy. */ |
| if (orig && TEST_BIT (wont_exit, j + 1)) |
| to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG]; |
| |
| /* 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[n - 1]; |
| } |
| |
| /* Set counts and frequencies. */ |
| if (flags & DLTHE_FLAG_UPDATE_FREQ) |
| { |
| 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_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; |
| |
| bb = bbs[i]; |
| bb->aux = 0; |
| |
| n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs); |
| for (j = 0; j < n_dom_bbs; 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); |
| } |
| free (dom_bbs); |
| } |
| free (first_active); |
| |
| free (bbs); |
| |
| return true; |
| } |
| |
| /* A callback for make_forwarder block, to redirect all edges except for |
| MFB_KJ_EDGE to the entry part. E is the edge for that we should decide |
| whether to redirect it. */ |
| |
| static edge mfb_kj_edge; |
| static bool |
| mfb_keep_just (edge e) |
| { |
| return e != mfb_kj_edge; |
| } |
| |
| /* 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). */ |
| |
| static void |
| mfb_update_loops (basic_block jump) |
| { |
| struct loop *loop = single_succ (jump)->loop_father; |
| |
| if (dom_computed[CDI_DOMINATORS]) |
| set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump)); |
| add_bb_to_loop (jump, loop); |
| loop->latch = jump; |
| } |
| |
| /* 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. |
| The function also updates dominators. */ |
| |
| static 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 = 0; |
| edge_iterator ei; |
| |
| cloop = loop->outer; |
| |
| FOR_EACH_EDGE (e, ei, loop->header->preds) |
| { |
| if (e->src == loop->latch) |
| 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) |
| { |
| /* Get an edge that is different from the one from loop->latch |
| to loop->header. */ |
| e = EDGE_PRED (loop->header, |
| EDGE_PRED (loop->header, 0)->src == loop->latch); |
| |
| 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; |
| 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. |
| |
| 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); |
| |
| if (irred) |
| { |
| dummy->flags |= BB_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); |
| |
| return dummy; |
| } |
| |
| /* Create preheaders for each loop from loop tree stored in LOOPS; for meaning |
| of FLAGS see create_preheader. */ |
| void |
| create_preheaders (struct loops *loops, int flags) |
| { |
| unsigned i; |
| for (i = 1; i < loops->num; i++) |
| create_preheader (loops->parray[i], flags); |
| loops->state |= LOOPS_HAVE_PREHEADERS; |
| } |
| |
| /* Forces all loop latches of loops from loop tree LOOPS to have only single |
| successor. */ |
| void |
| force_single_succ_latches (struct loops *loops) |
| { |
| unsigned i; |
| struct loop *loop; |
| edge e; |
| |
| for (i = 1; i < loops->num; i++) |
| { |
| loop = loops->parray[i]; |
| if (loop->latch != loop->header && single_succ_p (loop->latch)) |
| continue; |
| |
| e = find_edge (loop->latch, loop->header); |
| |
| loop_split_edge_with (e, NULL_RTX); |
| } |
| loops->state |= 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) |
| { |
| basic_block src, dest, new_bb; |
| struct loop *loop_c; |
| |
| src = e->src; |
| dest = e->dest; |
| |
| loop_c = find_common_loop (src->loop_father, dest->loop_father); |
| |
| /* Create basic block for it. */ |
| |
| new_bb = split_edge (e); |
| add_bb_to_loop (new_bb, loop_c); |
| new_bb->flags |= (insns ? BB_SUPERBLOCK : 0); |
| |
| if (insns) |
| emit_insn_after (insns, BB_END (new_bb)); |
| |
| if (dest->loop_father->latch == src) |
| dest->loop_father->latch = new_bb; |
| |
| return new_bb; |
| } |
| |
| /* 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 |
| fix_loop_structure (struct loops *loops, bitmap changed_bbs) |
| { |
| basic_block bb; |
| struct loop *loop, *ploop; |
| unsigned i; |
| |
| /* Remove the old bb -> loop mapping. */ |
| FOR_EACH_BB (bb) |
| { |
| bb->aux = (void *) (size_t) bb->loop_father->depth; |
| bb->loop_father = loops->tree_root; |
| } |
| |
| /* 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) |
| { |
| ploop = loop->inner; |
| flow_loop_tree_node_remove (ploop); |
| flow_loop_tree_node_add (loop->outer, ploop); |
| } |
| |
| /* Remove the loop and free its data. */ |
| flow_loop_tree_node_remove (loop); |
| loops->parray[loop->num] = NULL; |
| flow_loop_free (loop); |
| } |
| |
| /* Rescan the bodies of loops, starting from the outermost. */ |
| loop = loops->tree_root; |
| while (1) |
| { |
| if (loop->inner) |
| loop = loop->inner; |
| else |
| { |
| 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); |
| } |
| } |
| |
| /* 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; |
| } |
| |
| 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); |
| } |