1132718Skan/* Loop manipulation code for GNU compiler. 2169689Skan Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3132718Skan 4132718SkanThis file is part of GCC. 5132718Skan 6132718SkanGCC is free software; you can redistribute it and/or modify it under 7132718Skanthe terms of the GNU General Public License as published by the Free 8132718SkanSoftware Foundation; either version 2, or (at your option) any later 9132718Skanversion. 10132718Skan 11132718SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 12132718SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 13132718SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14132718Skanfor more details. 15132718Skan 16132718SkanYou should have received a copy of the GNU General Public License 17132718Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20132718Skan 21132718Skan#include "config.h" 22132718Skan#include "system.h" 23132718Skan#include "coretypes.h" 24132718Skan#include "tm.h" 25132718Skan#include "rtl.h" 26132718Skan#include "hard-reg-set.h" 27169689Skan#include "obstack.h" 28132718Skan#include "basic-block.h" 29132718Skan#include "cfgloop.h" 30132718Skan#include "cfglayout.h" 31169689Skan#include "cfghooks.h" 32132718Skan#include "output.h" 33132718Skan 34132718Skanstatic void duplicate_subloops (struct loops *, struct loop *, struct loop *); 35132718Skanstatic void copy_loops_to (struct loops *, struct loop **, int, 36132718Skan struct loop *); 37132718Skanstatic void loop_redirect_edge (edge, basic_block); 38132718Skanstatic bool loop_delete_branch_edge (edge, int); 39132718Skanstatic void remove_bbs (basic_block *, int); 40132718Skanstatic bool rpe_enum_p (basic_block, void *); 41132718Skanstatic int find_path (edge, basic_block **); 42132718Skanstatic bool alp_enum_p (basic_block, void *); 43132718Skanstatic void add_loop (struct loops *, struct loop *); 44169689Skanstatic void fix_loop_placements (struct loops *, struct loop *, bool *); 45132718Skanstatic bool fix_bb_placement (struct loops *, basic_block); 46169689Skanstatic void fix_bb_placements (struct loops *, basic_block, bool *); 47132718Skanstatic void place_new_loop (struct loops *, struct loop *); 48132718Skanstatic void scale_loop_frequencies (struct loop *, int, int); 49132718Skanstatic basic_block create_preheader (struct loop *, int); 50169689Skanstatic void unloop (struct loops *, struct loop *, bool *); 51132718Skan 52169689Skan#define RDIV(X,Y) (((X) + (Y) / 2) / (Y)) 53132718Skan 54132718Skan/* Checks whether basic block BB is dominated by DATA. */ 55132718Skanstatic bool 56132718Skanrpe_enum_p (basic_block bb, void *data) 57132718Skan{ 58132718Skan return dominated_by_p (CDI_DOMINATORS, bb, data); 59132718Skan} 60132718Skan 61132718Skan/* Remove basic blocks BBS from loop structure and dominance info, 62132718Skan and delete them afterwards. */ 63132718Skanstatic void 64132718Skanremove_bbs (basic_block *bbs, int nbbs) 65132718Skan{ 66132718Skan int i; 67132718Skan 68132718Skan for (i = 0; i < nbbs; i++) 69132718Skan { 70132718Skan remove_bb_from_loops (bbs[i]); 71169689Skan delete_basic_block (bbs[i]); 72132718Skan } 73132718Skan} 74132718Skan 75132718Skan/* Find path -- i.e. the basic blocks dominated by edge E and put them 76132718Skan into array BBS, that will be allocated large enough to contain them. 77132718Skan E->dest must have exactly one predecessor for this to work (it is 78132718Skan easy to achieve and we do not put it here because we do not want to 79132718Skan alter anything by this function). The number of basic blocks in the 80132718Skan path is returned. */ 81132718Skanstatic int 82132718Skanfind_path (edge e, basic_block **bbs) 83132718Skan{ 84169689Skan gcc_assert (EDGE_COUNT (e->dest->preds) <= 1); 85132718Skan 86132718Skan /* Find bbs in the path. */ 87169689Skan *bbs = XCNEWVEC (basic_block, n_basic_blocks); 88132718Skan return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs, 89132718Skan n_basic_blocks, e->dest); 90132718Skan} 91132718Skan 92132718Skan/* Fix placement of basic block BB inside loop hierarchy stored in LOOPS -- 93132718Skan Let L be a loop to that BB belongs. Then every successor of BB must either 94132718Skan 1) belong to some superloop of loop L, or 95132718Skan 2) be a header of loop K such that K->outer is superloop of L 96132718Skan Returns true if we had to move BB into other loop to enforce this condition, 97132718Skan false if the placement of BB was already correct (provided that placements 98132718Skan of its successors are correct). */ 99132718Skanstatic bool 100132718Skanfix_bb_placement (struct loops *loops, basic_block bb) 101132718Skan{ 102132718Skan edge e; 103169689Skan edge_iterator ei; 104132718Skan struct loop *loop = loops->tree_root, *act; 105132718Skan 106169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 107132718Skan { 108132718Skan if (e->dest == EXIT_BLOCK_PTR) 109132718Skan continue; 110132718Skan 111132718Skan act = e->dest->loop_father; 112132718Skan if (act->header == e->dest) 113132718Skan act = act->outer; 114132718Skan 115132718Skan if (flow_loop_nested_p (loop, act)) 116132718Skan loop = act; 117132718Skan } 118132718Skan 119132718Skan if (loop == bb->loop_father) 120132718Skan return false; 121132718Skan 122132718Skan remove_bb_from_loops (bb); 123132718Skan add_bb_to_loop (bb, loop); 124132718Skan 125132718Skan return true; 126132718Skan} 127132718Skan 128132718Skan/* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e. 129132718Skan enforce condition condition stated in description of fix_bb_placement. We 130132718Skan start from basic block FROM that had some of its successors removed, so that 131132718Skan his placement no longer has to be correct, and iteratively fix placement of 132132718Skan its predecessors that may change if placement of FROM changed. Also fix 133132718Skan placement of subloops of FROM->loop_father, that might also be altered due 134132718Skan to this change; the condition for them is similar, except that instead of 135169689Skan successors we consider edges coming out of the loops. 136169689Skan 137169689Skan If the changes may invalidate the information about irreducible regions, 138169689Skan IRRED_INVALIDATED is set to true. */ 139169689Skan 140132718Skanstatic void 141169689Skanfix_bb_placements (struct loops *loops, basic_block from, 142169689Skan bool *irred_invalidated) 143132718Skan{ 144132718Skan sbitmap in_queue; 145132718Skan basic_block *queue, *qtop, *qbeg, *qend; 146132718Skan struct loop *base_loop; 147132718Skan edge e; 148132718Skan 149132718Skan /* We pass through blocks back-reachable from FROM, testing whether some 150132718Skan of their successors moved to outer loop. It may be necessary to 151132718Skan iterate several times, but it is finite, as we stop unless we move 152132718Skan the basic block up the loop structure. The whole story is a bit 153132718Skan more complicated due to presence of subloops, those are moved using 154132718Skan fix_loop_placement. */ 155132718Skan 156132718Skan base_loop = from->loop_father; 157132718Skan if (base_loop == loops->tree_root) 158132718Skan return; 159132718Skan 160132718Skan in_queue = sbitmap_alloc (last_basic_block); 161132718Skan sbitmap_zero (in_queue); 162132718Skan SET_BIT (in_queue, from->index); 163132718Skan /* Prevent us from going out of the base_loop. */ 164132718Skan SET_BIT (in_queue, base_loop->header->index); 165132718Skan 166169689Skan queue = XNEWVEC (basic_block, base_loop->num_nodes + 1); 167132718Skan qtop = queue + base_loop->num_nodes + 1; 168132718Skan qbeg = queue; 169132718Skan qend = queue + 1; 170132718Skan *qbeg = from; 171132718Skan 172132718Skan while (qbeg != qend) 173132718Skan { 174169689Skan edge_iterator ei; 175132718Skan from = *qbeg; 176132718Skan qbeg++; 177132718Skan if (qbeg == qtop) 178132718Skan qbeg = queue; 179132718Skan RESET_BIT (in_queue, from->index); 180132718Skan 181132718Skan if (from->loop_father->header == from) 182132718Skan { 183132718Skan /* Subloop header, maybe move the loop upward. */ 184132718Skan if (!fix_loop_placement (from->loop_father)) 185132718Skan continue; 186132718Skan } 187132718Skan else 188132718Skan { 189132718Skan /* Ordinary basic block. */ 190132718Skan if (!fix_bb_placement (loops, from)) 191132718Skan continue; 192132718Skan } 193132718Skan 194169689Skan FOR_EACH_EDGE (e, ei, from->succs) 195169689Skan { 196169689Skan if (e->flags & EDGE_IRREDUCIBLE_LOOP) 197169689Skan *irred_invalidated = true; 198169689Skan } 199169689Skan 200132718Skan /* Something has changed, insert predecessors into queue. */ 201169689Skan FOR_EACH_EDGE (e, ei, from->preds) 202132718Skan { 203132718Skan basic_block pred = e->src; 204132718Skan struct loop *nca; 205132718Skan 206169689Skan if (e->flags & EDGE_IRREDUCIBLE_LOOP) 207169689Skan *irred_invalidated = true; 208169689Skan 209132718Skan if (TEST_BIT (in_queue, pred->index)) 210132718Skan continue; 211132718Skan 212132718Skan /* If it is subloop, then it either was not moved, or 213132718Skan the path up the loop tree from base_loop do not contain 214132718Skan it. */ 215132718Skan nca = find_common_loop (pred->loop_father, base_loop); 216132718Skan if (pred->loop_father != base_loop 217132718Skan && (nca == base_loop 218132718Skan || nca != pred->loop_father)) 219132718Skan pred = pred->loop_father->header; 220132718Skan else if (!flow_loop_nested_p (from->loop_father, pred->loop_father)) 221132718Skan { 222132718Skan /* No point in processing it. */ 223132718Skan continue; 224132718Skan } 225132718Skan 226132718Skan if (TEST_BIT (in_queue, pred->index)) 227132718Skan continue; 228132718Skan 229132718Skan /* Schedule the basic block. */ 230132718Skan *qend = pred; 231132718Skan qend++; 232132718Skan if (qend == qtop) 233132718Skan qend = queue; 234132718Skan SET_BIT (in_queue, pred->index); 235132718Skan } 236132718Skan } 237132718Skan free (in_queue); 238132718Skan free (queue); 239132718Skan} 240132718Skan 241132718Skan/* Removes path beginning at edge E, i.e. remove basic blocks dominated by E 242132718Skan and update loop structure stored in LOOPS and dominators. Return true if 243132718Skan we were able to remove the path, false otherwise (and nothing is affected 244132718Skan then). */ 245132718Skanbool 246132718Skanremove_path (struct loops *loops, edge e) 247132718Skan{ 248132718Skan edge ae; 249132718Skan basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb; 250132718Skan int i, nrem, n_bord_bbs, n_dom_bbs; 251132718Skan sbitmap seen; 252169689Skan bool deleted, irred_invalidated = false; 253132718Skan 254132718Skan if (!loop_delete_branch_edge (e, 0)) 255132718Skan return false; 256132718Skan 257169689Skan /* Keep track of whether we need to update information about irreducible 258169689Skan regions. This is the case if the removed area is a part of the 259169689Skan irreducible region, or if the set of basic blocks that belong to a loop 260169689Skan that is inside an irreducible region is changed, or if such a loop is 261169689Skan removed. */ 262169689Skan if (e->flags & EDGE_IRREDUCIBLE_LOOP) 263169689Skan irred_invalidated = true; 264169689Skan 265132718Skan /* We need to check whether basic blocks are dominated by the edge 266132718Skan e, but we only have basic block dominators. This is easy to 267132718Skan fix -- when e->dest has exactly one predecessor, this corresponds 268132718Skan to blocks dominated by e->dest, if not, split the edge. */ 269169689Skan if (!single_pred_p (e->dest)) 270169689Skan e = single_pred_edge (loop_split_edge_with (e, NULL_RTX)); 271132718Skan 272132718Skan /* It may happen that by removing path we remove one or more loops 273132718Skan we belong to. In this case first unloop the loops, then proceed 274132718Skan normally. We may assume that e->dest is not a header of any loop, 275132718Skan as it now has exactly one predecessor. */ 276132718Skan while (e->src->loop_father->outer 277132718Skan && dominated_by_p (CDI_DOMINATORS, 278132718Skan e->src->loop_father->latch, e->dest)) 279169689Skan unloop (loops, e->src->loop_father, &irred_invalidated); 280132718Skan 281132718Skan /* Identify the path. */ 282132718Skan nrem = find_path (e, &rem_bbs); 283132718Skan 284132718Skan n_bord_bbs = 0; 285169689Skan bord_bbs = XCNEWVEC (basic_block, n_basic_blocks); 286132718Skan seen = sbitmap_alloc (last_basic_block); 287132718Skan sbitmap_zero (seen); 288132718Skan 289132718Skan /* Find "border" hexes -- i.e. those with predecessor in removed path. */ 290132718Skan for (i = 0; i < nrem; i++) 291132718Skan SET_BIT (seen, rem_bbs[i]->index); 292132718Skan for (i = 0; i < nrem; i++) 293132718Skan { 294169689Skan edge_iterator ei; 295132718Skan bb = rem_bbs[i]; 296169689Skan FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs) 297132718Skan if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index)) 298132718Skan { 299132718Skan SET_BIT (seen, ae->dest->index); 300132718Skan bord_bbs[n_bord_bbs++] = ae->dest; 301169689Skan 302169689Skan if (ae->flags & EDGE_IRREDUCIBLE_LOOP) 303169689Skan irred_invalidated = true; 304132718Skan } 305132718Skan } 306132718Skan 307132718Skan /* Remove the path. */ 308132718Skan from = e->src; 309169689Skan deleted = loop_delete_branch_edge (e, 1); 310169689Skan gcc_assert (deleted); 311169689Skan dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); 312132718Skan 313132718Skan /* Cancel loops contained in the path. */ 314132718Skan for (i = 0; i < nrem; i++) 315132718Skan if (rem_bbs[i]->loop_father->header == rem_bbs[i]) 316132718Skan cancel_loop_tree (loops, rem_bbs[i]->loop_father); 317132718Skan 318132718Skan remove_bbs (rem_bbs, nrem); 319132718Skan free (rem_bbs); 320132718Skan 321132718Skan /* Find blocks whose dominators may be affected. */ 322132718Skan n_dom_bbs = 0; 323132718Skan sbitmap_zero (seen); 324132718Skan for (i = 0; i < n_bord_bbs; i++) 325132718Skan { 326132718Skan basic_block ldom; 327132718Skan 328132718Skan bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]); 329132718Skan if (TEST_BIT (seen, bb->index)) 330132718Skan continue; 331132718Skan SET_BIT (seen, bb->index); 332132718Skan 333132718Skan for (ldom = first_dom_son (CDI_DOMINATORS, bb); 334132718Skan ldom; 335132718Skan ldom = next_dom_son (CDI_DOMINATORS, ldom)) 336132718Skan if (!dominated_by_p (CDI_DOMINATORS, from, ldom)) 337132718Skan dom_bbs[n_dom_bbs++] = ldom; 338132718Skan } 339132718Skan 340132718Skan free (seen); 341132718Skan 342132718Skan /* Recount dominators. */ 343132718Skan iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); 344132718Skan free (dom_bbs); 345132718Skan free (bord_bbs); 346132718Skan 347132718Skan /* Fix placements of basic blocks inside loops and the placement of 348132718Skan loops in the loop tree. */ 349169689Skan fix_bb_placements (loops, from, &irred_invalidated); 350169689Skan fix_loop_placements (loops, from->loop_father, &irred_invalidated); 351132718Skan 352169689Skan if (irred_invalidated 353169689Skan && (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) != 0) 354169689Skan mark_irreducible_loops (loops); 355169689Skan 356132718Skan return true; 357132718Skan} 358132718Skan 359132718Skan/* Predicate for enumeration in add_loop. */ 360132718Skanstatic bool 361132718Skanalp_enum_p (basic_block bb, void *alp_header) 362132718Skan{ 363132718Skan return bb != (basic_block) alp_header; 364132718Skan} 365132718Skan 366132718Skan/* Given LOOP structure with filled header and latch, find the body of the 367132718Skan corresponding loop and add it to LOOPS tree. */ 368132718Skanstatic void 369132718Skanadd_loop (struct loops *loops, struct loop *loop) 370132718Skan{ 371132718Skan basic_block *bbs; 372132718Skan int i, n; 373132718Skan 374132718Skan /* Add it to loop structure. */ 375132718Skan place_new_loop (loops, loop); 376132718Skan loop->level = 1; 377132718Skan 378132718Skan /* Find its nodes. */ 379169689Skan bbs = XCNEWVEC (basic_block, n_basic_blocks); 380132718Skan n = dfs_enumerate_from (loop->latch, 1, alp_enum_p, 381132718Skan bbs, n_basic_blocks, loop->header); 382132718Skan 383132718Skan for (i = 0; i < n; i++) 384132718Skan add_bb_to_loop (bbs[i], loop); 385132718Skan add_bb_to_loop (loop->header, loop); 386132718Skan 387132718Skan free (bbs); 388132718Skan} 389132718Skan 390132718Skan/* Multiply all frequencies in LOOP by NUM/DEN. */ 391132718Skanstatic void 392132718Skanscale_loop_frequencies (struct loop *loop, int num, int den) 393132718Skan{ 394132718Skan basic_block *bbs; 395132718Skan 396132718Skan bbs = get_loop_body (loop); 397169689Skan scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den); 398132718Skan free (bbs); 399132718Skan} 400132718Skan 401132718Skan/* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting 402132718Skan latch to header and update loop tree stored in LOOPS and dominators 403132718Skan accordingly. Everything between them plus LATCH_EDGE destination must 404132718Skan be dominated by HEADER_EDGE destination, and back-reachable from 405132718Skan LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB, 406169689Skan FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and 407169689Skan TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE. 408132718Skan Returns newly created loop. */ 409169689Skan 410132718Skanstruct loop * 411169689Skanloopify (struct loops *loops, edge latch_edge, edge header_edge, 412169689Skan basic_block switch_bb, edge true_edge, edge false_edge, 413169689Skan bool redirect_all_edges) 414132718Skan{ 415132718Skan basic_block succ_bb = latch_edge->dest; 416132718Skan basic_block pred_bb = header_edge->src; 417132718Skan basic_block *dom_bbs, *body; 418132718Skan unsigned n_dom_bbs, i; 419132718Skan sbitmap seen; 420169689Skan struct loop *loop = XCNEW (struct loop); 421132718Skan struct loop *outer = succ_bb->loop_father->outer; 422132718Skan int freq, prob, tot_prob; 423132718Skan gcov_type cnt; 424132718Skan edge e; 425169689Skan edge_iterator ei; 426132718Skan 427132718Skan loop->header = header_edge->dest; 428132718Skan loop->latch = latch_edge->src; 429132718Skan 430132718Skan freq = EDGE_FREQUENCY (header_edge); 431132718Skan cnt = header_edge->count; 432169689Skan prob = EDGE_SUCC (switch_bb, 0)->probability; 433169689Skan tot_prob = prob + EDGE_SUCC (switch_bb, 1)->probability; 434132718Skan if (tot_prob == 0) 435132718Skan tot_prob = 1; 436132718Skan 437132718Skan /* Redirect edges. */ 438132718Skan loop_redirect_edge (latch_edge, loop->header); 439169689Skan loop_redirect_edge (true_edge, succ_bb); 440132718Skan 441169689Skan /* During loop versioning, one of the switch_bb edge is already properly 442169689Skan set. Do not redirect it again unless redirect_all_edges is true. */ 443169689Skan if (redirect_all_edges) 444169689Skan { 445169689Skan loop_redirect_edge (header_edge, switch_bb); 446169689Skan loop_redirect_edge (false_edge, loop->header); 447169689Skan 448169689Skan /* Update dominators. */ 449169689Skan set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb); 450169689Skan set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb); 451169689Skan } 452169689Skan 453132718Skan set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb); 454132718Skan 455132718Skan /* Compute new loop. */ 456132718Skan add_loop (loops, loop); 457132718Skan flow_loop_tree_node_add (outer, loop); 458132718Skan 459132718Skan /* Add switch_bb to appropriate loop. */ 460132718Skan add_bb_to_loop (switch_bb, outer); 461132718Skan 462132718Skan /* Fix frequencies. */ 463132718Skan switch_bb->frequency = freq; 464132718Skan switch_bb->count = cnt; 465169689Skan FOR_EACH_EDGE (e, ei, switch_bb->succs) 466132718Skan e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE; 467132718Skan scale_loop_frequencies (loop, prob, tot_prob); 468132718Skan scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob); 469132718Skan 470132718Skan /* Update dominators of blocks outside of LOOP. */ 471169689Skan dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); 472132718Skan n_dom_bbs = 0; 473132718Skan seen = sbitmap_alloc (last_basic_block); 474132718Skan sbitmap_zero (seen); 475132718Skan body = get_loop_body (loop); 476132718Skan 477132718Skan for (i = 0; i < loop->num_nodes; i++) 478132718Skan SET_BIT (seen, body[i]->index); 479132718Skan 480132718Skan for (i = 0; i < loop->num_nodes; i++) 481132718Skan { 482132718Skan basic_block ldom; 483132718Skan 484132718Skan for (ldom = first_dom_son (CDI_DOMINATORS, body[i]); 485132718Skan ldom; 486132718Skan ldom = next_dom_son (CDI_DOMINATORS, ldom)) 487132718Skan if (!TEST_BIT (seen, ldom->index)) 488132718Skan { 489132718Skan SET_BIT (seen, ldom->index); 490132718Skan dom_bbs[n_dom_bbs++] = ldom; 491132718Skan } 492132718Skan } 493132718Skan 494132718Skan iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); 495132718Skan 496132718Skan free (body); 497132718Skan free (seen); 498132718Skan free (dom_bbs); 499132718Skan 500132718Skan return loop; 501132718Skan} 502132718Skan 503132718Skan/* Remove the latch edge of a LOOP and update LOOPS tree to indicate that 504132718Skan the LOOP was removed. After this function, original loop latch will 505169689Skan have no successor, which caller is expected to fix somehow. 506169689Skan 507169689Skan If this may cause the information about irreducible regions to become 508169689Skan invalid, IRRED_INVALIDATED is set to true. */ 509169689Skan 510169689Skanstatic void 511169689Skanunloop (struct loops *loops, struct loop *loop, bool *irred_invalidated) 512132718Skan{ 513132718Skan basic_block *body; 514132718Skan struct loop *ploop; 515132718Skan unsigned i, n; 516132718Skan basic_block latch = loop->latch; 517169689Skan bool dummy = false; 518132718Skan 519169689Skan if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP) 520169689Skan *irred_invalidated = true; 521169689Skan 522132718Skan /* This is relatively straightforward. The dominators are unchanged, as 523132718Skan loop header dominates loop latch, so the only thing we have to care of 524132718Skan is the placement of loops and basic blocks inside the loop tree. We 525132718Skan move them all to the loop->outer, and then let fix_bb_placements do 526132718Skan its work. */ 527132718Skan 528132718Skan body = get_loop_body (loop); 529132718Skan n = loop->num_nodes; 530132718Skan for (i = 0; i < n; i++) 531132718Skan if (body[i]->loop_father == loop) 532132718Skan { 533132718Skan remove_bb_from_loops (body[i]); 534132718Skan add_bb_to_loop (body[i], loop->outer); 535132718Skan } 536132718Skan free(body); 537132718Skan 538132718Skan while (loop->inner) 539132718Skan { 540132718Skan ploop = loop->inner; 541132718Skan flow_loop_tree_node_remove (ploop); 542132718Skan flow_loop_tree_node_add (loop->outer, ploop); 543132718Skan } 544132718Skan 545132718Skan /* Remove the loop and free its data. */ 546132718Skan flow_loop_tree_node_remove (loop); 547132718Skan loops->parray[loop->num] = NULL; 548132718Skan flow_loop_free (loop); 549132718Skan 550169689Skan remove_edge (single_succ_edge (latch)); 551132718Skan 552169689Skan /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if 553169689Skan there is an irreducible region inside the cancelled loop, the flags will 554169689Skan be still correct. */ 555169689Skan fix_bb_placements (loops, latch, &dummy); 556132718Skan} 557132718Skan 558132718Skan/* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop 559132718Skan FATHER of LOOP such that all of the edges coming out of LOOP belong to 560169689Skan FATHER, and set it as outer loop of LOOP. Return true if placement of 561132718Skan LOOP changed. */ 562169689Skan 563132718Skanint 564132718Skanfix_loop_placement (struct loop *loop) 565132718Skan{ 566132718Skan basic_block *body; 567132718Skan unsigned i; 568132718Skan edge e; 569169689Skan edge_iterator ei; 570132718Skan struct loop *father = loop->pred[0], *act; 571132718Skan 572132718Skan body = get_loop_body (loop); 573132718Skan for (i = 0; i < loop->num_nodes; i++) 574169689Skan FOR_EACH_EDGE (e, ei, body[i]->succs) 575132718Skan if (!flow_bb_inside_loop_p (loop, e->dest)) 576132718Skan { 577132718Skan act = find_common_loop (loop, e->dest->loop_father); 578132718Skan if (flow_loop_nested_p (father, act)) 579132718Skan father = act; 580132718Skan } 581132718Skan free (body); 582132718Skan 583132718Skan if (father != loop->outer) 584132718Skan { 585132718Skan for (act = loop->outer; act != father; act = act->outer) 586132718Skan act->num_nodes -= loop->num_nodes; 587132718Skan flow_loop_tree_node_remove (loop); 588132718Skan flow_loop_tree_node_add (father, loop); 589132718Skan return 1; 590132718Skan } 591132718Skan return 0; 592132718Skan} 593132718Skan 594132718Skan/* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that 595132718Skan condition stated in description of fix_loop_placement holds for them. 596132718Skan It is used in case when we removed some edges coming out of LOOP, which 597169689Skan may cause the right placement of LOOP inside loop tree to change. 598169689Skan 599169689Skan IRRED_INVALIDATED is set to true if a change in the loop structures might 600169689Skan invalidate the information about irreducible regions. */ 601169689Skan 602132718Skanstatic void 603169689Skanfix_loop_placements (struct loops *loops, struct loop *loop, 604169689Skan bool *irred_invalidated) 605132718Skan{ 606132718Skan struct loop *outer; 607132718Skan 608132718Skan while (loop->outer) 609132718Skan { 610132718Skan outer = loop->outer; 611132718Skan if (!fix_loop_placement (loop)) 612169689Skan break; 613132718Skan 614132718Skan /* Changing the placement of a loop in the loop tree may alter the 615132718Skan validity of condition 2) of the description of fix_bb_placement 616132718Skan for its preheader, because the successor is the header and belongs 617132718Skan to the loop. So call fix_bb_placements to fix up the placement 618132718Skan of the preheader and (possibly) of its predecessors. */ 619169689Skan fix_bb_placements (loops, loop_preheader_edge (loop)->src, 620169689Skan irred_invalidated); 621132718Skan loop = outer; 622132718Skan } 623132718Skan} 624132718Skan 625132718Skan/* Creates place for a new LOOP in LOOPS structure. */ 626132718Skanstatic void 627132718Skanplace_new_loop (struct loops *loops, struct loop *loop) 628132718Skan{ 629132718Skan loops->parray = 630132718Skan xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *)); 631132718Skan loops->parray[loops->num] = loop; 632132718Skan 633132718Skan loop->num = loops->num++; 634132718Skan} 635132718Skan 636132718Skan/* Copies copy of LOOP as subloop of TARGET loop, placing newly 637132718Skan created loop into LOOPS structure. */ 638169689Skanstruct loop * 639132718Skanduplicate_loop (struct loops *loops, struct loop *loop, struct loop *target) 640132718Skan{ 641132718Skan struct loop *cloop; 642169689Skan cloop = XCNEW (struct loop); 643132718Skan place_new_loop (loops, cloop); 644132718Skan 645132718Skan /* Initialize copied loop. */ 646132718Skan cloop->level = loop->level; 647132718Skan 648132718Skan /* Set it as copy of loop. */ 649132718Skan loop->copy = cloop; 650132718Skan 651132718Skan /* Add it to target. */ 652132718Skan flow_loop_tree_node_add (target, cloop); 653132718Skan 654132718Skan return cloop; 655132718Skan} 656132718Skan 657132718Skan/* Copies structure of subloops of LOOP into TARGET loop, placing 658132718Skan newly created loops into loop tree stored in LOOPS. */ 659132718Skanstatic void 660132718Skanduplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target) 661132718Skan{ 662132718Skan struct loop *aloop, *cloop; 663132718Skan 664132718Skan for (aloop = loop->inner; aloop; aloop = aloop->next) 665132718Skan { 666132718Skan cloop = duplicate_loop (loops, aloop, target); 667132718Skan duplicate_subloops (loops, aloop, cloop); 668132718Skan } 669132718Skan} 670132718Skan 671132718Skan/* Copies structure of subloops of N loops, stored in array COPIED_LOOPS, 672132718Skan into TARGET loop, placing newly created loops into loop tree LOOPS. */ 673132718Skanstatic void 674132718Skancopy_loops_to (struct loops *loops, struct loop **copied_loops, int n, struct loop *target) 675132718Skan{ 676132718Skan struct loop *aloop; 677132718Skan int i; 678132718Skan 679132718Skan for (i = 0; i < n; i++) 680132718Skan { 681132718Skan aloop = duplicate_loop (loops, copied_loops[i], target); 682132718Skan duplicate_subloops (loops, copied_loops[i], aloop); 683132718Skan } 684132718Skan} 685132718Skan 686132718Skan/* Redirects edge E to basic block DEST. */ 687132718Skanstatic void 688132718Skanloop_redirect_edge (edge e, basic_block dest) 689132718Skan{ 690132718Skan if (e->dest == dest) 691132718Skan return; 692132718Skan 693132718Skan redirect_edge_and_branch_force (e, dest); 694132718Skan} 695132718Skan 696132718Skan/* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set, 697132718Skan just test whether it is possible to remove the edge. */ 698132718Skanstatic bool 699132718Skanloop_delete_branch_edge (edge e, int really_delete) 700132718Skan{ 701132718Skan basic_block src = e->src; 702169689Skan basic_block newdest; 703132718Skan int irr; 704132718Skan edge snd; 705132718Skan 706169689Skan gcc_assert (EDGE_COUNT (src->succs) > 1); 707132718Skan 708169689Skan /* Cannot handle more than two exit edges. */ 709169689Skan if (EDGE_COUNT (src->succs) > 2) 710169689Skan return false; 711169689Skan /* And it must be just a simple branch. */ 712169689Skan if (!any_condjump_p (BB_END (src))) 713169689Skan return false; 714132718Skan 715169689Skan snd = e == EDGE_SUCC (src, 0) ? EDGE_SUCC (src, 1) : EDGE_SUCC (src, 0); 716169689Skan newdest = snd->dest; 717169689Skan if (newdest == EXIT_BLOCK_PTR) 718169689Skan return false; 719132718Skan 720169689Skan /* Hopefully the above conditions should suffice. */ 721169689Skan if (!really_delete) 722169689Skan return true; 723132718Skan 724169689Skan /* Redirecting behaves wrongly wrto this flag. */ 725169689Skan irr = snd->flags & EDGE_IRREDUCIBLE_LOOP; 726132718Skan 727169689Skan if (!redirect_edge_and_branch (e, newdest)) 728169689Skan return false; 729169689Skan single_succ_edge (src)->flags &= ~EDGE_IRREDUCIBLE_LOOP; 730169689Skan single_succ_edge (src)->flags |= irr; 731132718Skan 732169689Skan return true; 733132718Skan} 734132718Skan 735132718Skan/* Check whether LOOP's body can be duplicated. */ 736132718Skanbool 737132718Skancan_duplicate_loop_p (struct loop *loop) 738132718Skan{ 739132718Skan int ret; 740132718Skan basic_block *bbs = get_loop_body (loop); 741132718Skan 742132718Skan ret = can_copy_bbs_p (bbs, loop->num_nodes); 743132718Skan free (bbs); 744169689Skan 745132718Skan return ret; 746132718Skan} 747132718Skan 748169689Skan/* The NBBS blocks in BBS will get duplicated and the copies will be placed 749169689Skan to LOOP. Update the single_exit information in superloops of LOOP. */ 750132718Skan 751169689Skanstatic void 752169689Skanupdate_single_exits_after_duplication (basic_block *bbs, unsigned nbbs, 753169689Skan struct loop *loop) 754169689Skan{ 755169689Skan unsigned i; 756169689Skan 757169689Skan for (i = 0; i < nbbs; i++) 758169689Skan bbs[i]->flags |= BB_DUPLICATED; 759169689Skan 760169689Skan for (; loop->outer; loop = loop->outer) 761169689Skan { 762169689Skan if (!loop->single_exit) 763169689Skan continue; 764169689Skan 765169689Skan if (loop->single_exit->src->flags & BB_DUPLICATED) 766169689Skan loop->single_exit = NULL; 767169689Skan } 768169689Skan 769169689Skan for (i = 0; i < nbbs; i++) 770169689Skan bbs[i]->flags &= ~BB_DUPLICATED; 771169689Skan} 772169689Skan 773132718Skan/* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating 774132718Skan LOOPS structure and dominators. E's destination must be LOOP header for 775132718Skan this to work, i.e. it must be entry or latch edge of this loop; these are 776132718Skan unique, as the loops must have preheaders for this function to work 777132718Skan correctly (in case E is latch, the function unrolls the loop, if E is entry 778132718Skan edge, it peels the loop). Store edges created by copying ORIG edge from 779132718Skan copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to 780132718Skan original LOOP body, the other copies are numbered in order given by control 781132718Skan flow through them) into TO_REMOVE array. Returns false if duplication is 782132718Skan impossible. */ 783169689Skanbool 784132718Skanduplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, 785132718Skan unsigned int ndupl, sbitmap wont_exit, 786132718Skan edge orig, edge *to_remove, 787132718Skan unsigned int *n_to_remove, int flags) 788132718Skan{ 789132718Skan struct loop *target, *aloop; 790132718Skan struct loop **orig_loops; 791132718Skan unsigned n_orig_loops; 792132718Skan basic_block header = loop->header, latch = loop->latch; 793132718Skan basic_block *new_bbs, *bbs, *first_active; 794132718Skan basic_block new_bb, bb, first_active_latch = NULL; 795132718Skan edge ae, latch_edge; 796132718Skan edge spec_edges[2], new_spec_edges[2]; 797132718Skan#define SE_LATCH 0 798132718Skan#define SE_ORIG 1 799132718Skan unsigned i, j, n; 800132718Skan int is_latch = (latch == e->src); 801132718Skan int scale_act = 0, *scale_step = NULL, scale_main = 0; 802132718Skan int p, freq_in, freq_le, freq_out_orig; 803132718Skan int prob_pass_thru, prob_pass_wont_exit, prob_pass_main; 804132718Skan int add_irreducible_flag; 805169689Skan basic_block place_after; 806132718Skan 807169689Skan gcc_assert (e->dest == loop->header); 808169689Skan gcc_assert (ndupl > 0); 809132718Skan 810132718Skan if (orig) 811132718Skan { 812132718Skan /* Orig must be edge out of the loop. */ 813169689Skan gcc_assert (flow_bb_inside_loop_p (loop, orig->src)); 814169689Skan gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest)); 815132718Skan } 816132718Skan 817169689Skan n = loop->num_nodes; 818169689Skan bbs = get_loop_body_in_dom_order (loop); 819169689Skan gcc_assert (bbs[0] == loop->header); 820169689Skan gcc_assert (bbs[n - 1] == loop->latch); 821132718Skan 822132718Skan /* Check whether duplication is possible. */ 823132718Skan if (!can_copy_bbs_p (bbs, loop->num_nodes)) 824132718Skan { 825132718Skan free (bbs); 826132718Skan return false; 827132718Skan } 828169689Skan new_bbs = XNEWVEC (basic_block, loop->num_nodes); 829132718Skan 830132718Skan /* In case we are doing loop peeling and the loop is in the middle of 831132718Skan irreducible region, the peeled copies will be inside it too. */ 832132718Skan add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP; 833169689Skan gcc_assert (!is_latch || !add_irreducible_flag); 834132718Skan 835132718Skan /* Find edge from latch. */ 836132718Skan latch_edge = loop_latch_edge (loop); 837132718Skan 838132718Skan if (flags & DLTHE_FLAG_UPDATE_FREQ) 839132718Skan { 840132718Skan /* Calculate coefficients by that we have to scale frequencies 841132718Skan of duplicated loop bodies. */ 842132718Skan freq_in = header->frequency; 843132718Skan freq_le = EDGE_FREQUENCY (latch_edge); 844132718Skan if (freq_in == 0) 845132718Skan freq_in = 1; 846132718Skan if (freq_in < freq_le) 847132718Skan freq_in = freq_le; 848132718Skan freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le; 849132718Skan if (freq_out_orig > freq_in - freq_le) 850132718Skan freq_out_orig = freq_in - freq_le; 851132718Skan prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in); 852132718Skan prob_pass_wont_exit = 853132718Skan RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in); 854132718Skan 855169689Skan scale_step = XNEWVEC (int, ndupl); 856132718Skan 857132718Skan for (i = 1; i <= ndupl; i++) 858132718Skan scale_step[i - 1] = TEST_BIT (wont_exit, i) 859132718Skan ? prob_pass_wont_exit 860132718Skan : prob_pass_thru; 861132718Skan 862169689Skan /* Complete peeling is special as the probability of exit in last 863169689Skan copy becomes 1. */ 864169689Skan if (flags & DLTHE_FLAG_COMPLETTE_PEEL) 865132718Skan { 866169689Skan int wanted_freq = EDGE_FREQUENCY (e); 867169689Skan 868169689Skan if (wanted_freq > freq_in) 869169689Skan wanted_freq = freq_in; 870169689Skan 871169689Skan gcc_assert (!is_latch); 872169689Skan /* First copy has frequency of incoming edge. Each subsequent 873169689Skan frequency should be reduced by prob_pass_wont_exit. Caller 874169689Skan should've managed the flags so all except for original loop 875169689Skan has won't exist set. */ 876169689Skan scale_act = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in); 877169689Skan /* Now simulate the duplication adjustments and compute header 878169689Skan frequency of the last copy. */ 879169689Skan for (i = 0; i < ndupl; i++) 880169689Skan wanted_freq = RDIV (wanted_freq * scale_step[i], REG_BR_PROB_BASE); 881169689Skan scale_main = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in); 882169689Skan } 883169689Skan else if (is_latch) 884169689Skan { 885132718Skan prob_pass_main = TEST_BIT (wont_exit, 0) 886132718Skan ? prob_pass_wont_exit 887132718Skan : prob_pass_thru; 888132718Skan p = prob_pass_main; 889132718Skan scale_main = REG_BR_PROB_BASE; 890132718Skan for (i = 0; i < ndupl; i++) 891132718Skan { 892132718Skan scale_main += p; 893132718Skan p = RDIV (p * scale_step[i], REG_BR_PROB_BASE); 894132718Skan } 895132718Skan scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main); 896132718Skan scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE); 897132718Skan } 898132718Skan else 899132718Skan { 900132718Skan scale_main = REG_BR_PROB_BASE; 901132718Skan for (i = 0; i < ndupl; i++) 902132718Skan scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE); 903132718Skan scale_act = REG_BR_PROB_BASE - prob_pass_thru; 904132718Skan } 905132718Skan for (i = 0; i < ndupl; i++) 906169689Skan gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE); 907169689Skan gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE 908169689Skan && scale_act >= 0 && scale_act <= REG_BR_PROB_BASE); 909132718Skan } 910132718Skan 911132718Skan /* Loop the new bbs will belong to. */ 912132718Skan target = e->src->loop_father; 913132718Skan 914132718Skan /* Original loops. */ 915132718Skan n_orig_loops = 0; 916132718Skan for (aloop = loop->inner; aloop; aloop = aloop->next) 917132718Skan n_orig_loops++; 918169689Skan orig_loops = XCNEWVEC (struct loop *, n_orig_loops); 919132718Skan for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++) 920132718Skan orig_loops[i] = aloop; 921132718Skan 922132718Skan loop->copy = target; 923132718Skan 924169689Skan first_active = XNEWVEC (basic_block, n); 925132718Skan if (is_latch) 926132718Skan { 927132718Skan memcpy (first_active, bbs, n * sizeof (basic_block)); 928132718Skan first_active_latch = latch; 929132718Skan } 930132718Skan 931169689Skan /* Update the information about single exits. */ 932169689Skan if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) 933169689Skan update_single_exits_after_duplication (bbs, n, target); 934169689Skan 935132718Skan /* Record exit edge in original loop body. */ 936132718Skan if (orig && TEST_BIT (wont_exit, 0)) 937132718Skan to_remove[(*n_to_remove)++] = orig; 938132718Skan 939132718Skan spec_edges[SE_ORIG] = orig; 940132718Skan spec_edges[SE_LATCH] = latch_edge; 941132718Skan 942169689Skan place_after = e->src; 943132718Skan for (j = 0; j < ndupl; j++) 944132718Skan { 945132718Skan /* Copy loops. */ 946132718Skan copy_loops_to (loops, orig_loops, n_orig_loops, target); 947132718Skan 948132718Skan /* Copy bbs. */ 949169689Skan copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop, 950169689Skan place_after); 951169689Skan place_after = new_spec_edges[SE_LATCH]->src; 952132718Skan 953169689Skan if (flags & DLTHE_RECORD_COPY_NUMBER) 954169689Skan for (i = 0; i < n; i++) 955169689Skan { 956169689Skan gcc_assert (!new_bbs[i]->aux); 957169689Skan new_bbs[i]->aux = (void *)(size_t)(j + 1); 958169689Skan } 959169689Skan 960132718Skan /* Note whether the blocks and edges belong to an irreducible loop. */ 961132718Skan if (add_irreducible_flag) 962132718Skan { 963132718Skan for (i = 0; i < n; i++) 964169689Skan new_bbs[i]->flags |= BB_DUPLICATED; 965132718Skan for (i = 0; i < n; i++) 966132718Skan { 967169689Skan edge_iterator ei; 968132718Skan new_bb = new_bbs[i]; 969132718Skan if (new_bb->loop_father == target) 970132718Skan new_bb->flags |= BB_IRREDUCIBLE_LOOP; 971132718Skan 972169689Skan FOR_EACH_EDGE (ae, ei, new_bb->succs) 973169689Skan if ((ae->dest->flags & BB_DUPLICATED) 974132718Skan && (ae->src->loop_father == target 975132718Skan || ae->dest->loop_father == target)) 976132718Skan ae->flags |= EDGE_IRREDUCIBLE_LOOP; 977132718Skan } 978132718Skan for (i = 0; i < n; i++) 979169689Skan new_bbs[i]->flags &= ~BB_DUPLICATED; 980132718Skan } 981132718Skan 982132718Skan /* Redirect the special edges. */ 983132718Skan if (is_latch) 984132718Skan { 985132718Skan redirect_edge_and_branch_force (latch_edge, new_bbs[0]); 986132718Skan redirect_edge_and_branch_force (new_spec_edges[SE_LATCH], 987132718Skan loop->header); 988132718Skan set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch); 989169689Skan latch = loop->latch = new_bbs[n - 1]; 990132718Skan e = latch_edge = new_spec_edges[SE_LATCH]; 991132718Skan } 992132718Skan else 993132718Skan { 994132718Skan redirect_edge_and_branch_force (new_spec_edges[SE_LATCH], 995132718Skan loop->header); 996132718Skan redirect_edge_and_branch_force (e, new_bbs[0]); 997132718Skan set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src); 998132718Skan e = new_spec_edges[SE_LATCH]; 999132718Skan } 1000132718Skan 1001132718Skan /* Record exit edge in this copy. */ 1002132718Skan if (orig && TEST_BIT (wont_exit, j + 1)) 1003132718Skan to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG]; 1004132718Skan 1005132718Skan /* Record the first copy in the control flow order if it is not 1006132718Skan the original loop (i.e. in case of peeling). */ 1007132718Skan if (!first_active_latch) 1008132718Skan { 1009132718Skan memcpy (first_active, new_bbs, n * sizeof (basic_block)); 1010169689Skan first_active_latch = new_bbs[n - 1]; 1011132718Skan } 1012132718Skan 1013132718Skan /* Set counts and frequencies. */ 1014132718Skan if (flags & DLTHE_FLAG_UPDATE_FREQ) 1015132718Skan { 1016169689Skan scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE); 1017132718Skan scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE); 1018132718Skan } 1019132718Skan } 1020132718Skan free (new_bbs); 1021132718Skan free (orig_loops); 1022169689Skan 1023132718Skan /* Update the original loop. */ 1024132718Skan if (!is_latch) 1025132718Skan set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src); 1026132718Skan if (flags & DLTHE_FLAG_UPDATE_FREQ) 1027132718Skan { 1028169689Skan scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE); 1029132718Skan free (scale_step); 1030132718Skan } 1031132718Skan 1032132718Skan /* Update dominators of outer blocks if affected. */ 1033132718Skan for (i = 0; i < n; i++) 1034132718Skan { 1035132718Skan basic_block dominated, dom_bb, *dom_bbs; 1036132718Skan int n_dom_bbs,j; 1037132718Skan 1038132718Skan bb = bbs[i]; 1039169689Skan bb->aux = 0; 1040169689Skan 1041132718Skan n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs); 1042132718Skan for (j = 0; j < n_dom_bbs; j++) 1043132718Skan { 1044132718Skan dominated = dom_bbs[j]; 1045132718Skan if (flow_bb_inside_loop_p (loop, dominated)) 1046132718Skan continue; 1047132718Skan dom_bb = nearest_common_dominator ( 1048132718Skan CDI_DOMINATORS, first_active[i], first_active_latch); 1049169689Skan set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb); 1050132718Skan } 1051132718Skan free (dom_bbs); 1052132718Skan } 1053132718Skan free (first_active); 1054132718Skan 1055132718Skan free (bbs); 1056132718Skan 1057132718Skan return true; 1058132718Skan} 1059132718Skan 1060169689Skan/* A callback for make_forwarder block, to redirect all edges except for 1061169689Skan MFB_KJ_EDGE to the entry part. E is the edge for that we should decide 1062169689Skan whether to redirect it. */ 1063169689Skan 1064169689Skanstatic edge mfb_kj_edge; 1065169689Skanstatic bool 1066169689Skanmfb_keep_just (edge e) 1067169689Skan{ 1068169689Skan return e != mfb_kj_edge; 1069169689Skan} 1070169689Skan 1071169689Skan/* A callback for make_forwarder block, to update data structures for a basic 1072169689Skan block JUMP created by redirecting an edge (only the latch edge is being 1073169689Skan redirected). */ 1074169689Skan 1075169689Skanstatic void 1076169689Skanmfb_update_loops (basic_block jump) 1077169689Skan{ 1078169689Skan struct loop *loop = single_succ (jump)->loop_father; 1079169689Skan 1080169689Skan if (dom_computed[CDI_DOMINATORS]) 1081169689Skan set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump)); 1082169689Skan add_bb_to_loop (jump, loop); 1083169689Skan loop->latch = jump; 1084169689Skan} 1085169689Skan 1086132718Skan/* Creates a pre-header for a LOOP. Returns newly created block. Unless 1087132718Skan CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single 1088132718Skan entry; otherwise we also force preheader block to have only one successor. 1089169689Skan The function also updates dominators. */ 1090169689Skan 1091132718Skanstatic basic_block 1092132718Skancreate_preheader (struct loop *loop, int flags) 1093132718Skan{ 1094132718Skan edge e, fallthru; 1095132718Skan basic_block dummy; 1096132718Skan struct loop *cloop, *ploop; 1097132718Skan int nentry = 0; 1098169689Skan bool irred = false; 1099169689Skan bool latch_edge_was_fallthru; 1100169689Skan edge one_succ_pred = 0; 1101169689Skan edge_iterator ei; 1102132718Skan 1103132718Skan cloop = loop->outer; 1104132718Skan 1105169689Skan FOR_EACH_EDGE (e, ei, loop->header->preds) 1106132718Skan { 1107132718Skan if (e->src == loop->latch) 1108132718Skan continue; 1109169689Skan irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0; 1110132718Skan nentry++; 1111169689Skan if (single_succ_p (e->src)) 1112169689Skan one_succ_pred = e; 1113132718Skan } 1114169689Skan gcc_assert (nentry); 1115132718Skan if (nentry == 1) 1116132718Skan { 1117169689Skan /* Get an edge that is different from the one from loop->latch 1118169689Skan to loop->header. */ 1119169689Skan e = EDGE_PRED (loop->header, 1120169689Skan EDGE_PRED (loop->header, 0)->src == loop->latch); 1121169689Skan 1122169689Skan if (!(flags & CP_SIMPLE_PREHEADERS) || single_succ_p (e->src)) 1123132718Skan return NULL; 1124132718Skan } 1125132718Skan 1126169689Skan mfb_kj_edge = loop_latch_edge (loop); 1127169689Skan latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0; 1128169689Skan fallthru = make_forwarder_block (loop->header, mfb_keep_just, 1129169689Skan mfb_update_loops); 1130132718Skan dummy = fallthru->src; 1131132718Skan loop->header = fallthru->dest; 1132132718Skan 1133132718Skan /* The header could be a latch of some superloop(s); due to design of 1134132718Skan split_block, it would now move to fallthru->dest. */ 1135132718Skan for (ploop = loop; ploop; ploop = ploop->outer) 1136132718Skan if (ploop->latch == dummy) 1137132718Skan ploop->latch = fallthru->dest; 1138132718Skan 1139169689Skan /* Try to be clever in placing the newly created preheader. The idea is to 1140169689Skan avoid breaking any "fallthruness" relationship between blocks. 1141132718Skan 1142169689Skan The preheader was created just before the header and all incoming edges 1143169689Skan to the header were redirected to the preheader, except the latch edge. 1144169689Skan So the only problematic case is when this latch edge was a fallthru 1145169689Skan edge: it is not anymore after the preheader creation so we have broken 1146169689Skan the fallthruness. We're therefore going to look for a better place. */ 1147169689Skan if (latch_edge_was_fallthru) 1148132718Skan { 1149169689Skan if (one_succ_pred) 1150169689Skan e = one_succ_pred; 1151169689Skan else 1152169689Skan e = EDGE_PRED (dummy, 0); 1153169689Skan 1154169689Skan move_block_after (dummy, e->src); 1155132718Skan } 1156132718Skan 1157169689Skan loop->header->loop_father = loop; 1158169689Skan add_bb_to_loop (dummy, cloop); 1159169689Skan 1160169689Skan if (irred) 1161132718Skan { 1162169689Skan dummy->flags |= BB_IRREDUCIBLE_LOOP; 1163169689Skan single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP; 1164132718Skan } 1165132718Skan 1166169689Skan if (dump_file) 1167169689Skan fprintf (dump_file, "Created preheader block for loop %i\n", 1168132718Skan loop->num); 1169132718Skan 1170132718Skan return dummy; 1171132718Skan} 1172132718Skan 1173132718Skan/* Create preheaders for each loop from loop tree stored in LOOPS; for meaning 1174132718Skan of FLAGS see create_preheader. */ 1175132718Skanvoid 1176132718Skancreate_preheaders (struct loops *loops, int flags) 1177132718Skan{ 1178132718Skan unsigned i; 1179132718Skan for (i = 1; i < loops->num; i++) 1180132718Skan create_preheader (loops->parray[i], flags); 1181132718Skan loops->state |= LOOPS_HAVE_PREHEADERS; 1182132718Skan} 1183132718Skan 1184132718Skan/* Forces all loop latches of loops from loop tree LOOPS to have only single 1185132718Skan successor. */ 1186132718Skanvoid 1187132718Skanforce_single_succ_latches (struct loops *loops) 1188132718Skan{ 1189132718Skan unsigned i; 1190132718Skan struct loop *loop; 1191132718Skan edge e; 1192132718Skan 1193132718Skan for (i = 1; i < loops->num; i++) 1194132718Skan { 1195132718Skan loop = loops->parray[i]; 1196169689Skan if (loop->latch != loop->header && single_succ_p (loop->latch)) 1197132718Skan continue; 1198132718Skan 1199169689Skan e = find_edge (loop->latch, loop->header); 1200132718Skan 1201132718Skan loop_split_edge_with (e, NULL_RTX); 1202132718Skan } 1203132718Skan loops->state |= LOOPS_HAVE_SIMPLE_LATCHES; 1204132718Skan} 1205132718Skan 1206132718Skan/* A quite stupid function to put INSNS on edge E. They are supposed to form 1207132718Skan just one basic block. Jumps in INSNS are not handled, so cfg do not have to 1208132718Skan be ok after this function. The created block is placed on correct place 1209132718Skan in LOOPS structure and its dominator is set. */ 1210132718Skanbasic_block 1211132718Skanloop_split_edge_with (edge e, rtx insns) 1212132718Skan{ 1213132718Skan basic_block src, dest, new_bb; 1214132718Skan struct loop *loop_c; 1215132718Skan 1216132718Skan src = e->src; 1217132718Skan dest = e->dest; 1218132718Skan 1219132718Skan loop_c = find_common_loop (src->loop_father, dest->loop_father); 1220132718Skan 1221132718Skan /* Create basic block for it. */ 1222132718Skan 1223132718Skan new_bb = split_edge (e); 1224132718Skan add_bb_to_loop (new_bb, loop_c); 1225169689Skan new_bb->flags |= (insns ? BB_SUPERBLOCK : 0); 1226132718Skan 1227132718Skan if (insns) 1228132718Skan emit_insn_after (insns, BB_END (new_bb)); 1229132718Skan 1230132718Skan if (dest->loop_father->latch == src) 1231132718Skan dest->loop_father->latch = new_bb; 1232132718Skan 1233132718Skan return new_bb; 1234132718Skan} 1235169689Skan 1236169689Skan/* This function is called from loop_version. It splits the entry edge 1237169689Skan of the loop we want to version, adds the versioning condition, and 1238169689Skan adjust the edges to the two versions of the loop appropriately. 1239169689Skan e is an incoming edge. Returns the basic block containing the 1240169689Skan condition. 1241169689Skan 1242169689Skan --- edge e ---- > [second_head] 1243169689Skan 1244169689Skan Split it and insert new conditional expression and adjust edges. 1245169689Skan 1246169689Skan --- edge e ---> [cond expr] ---> [first_head] 1247169689Skan | 1248169689Skan +---------> [second_head] 1249169689Skan*/ 1250169689Skan 1251169689Skanstatic basic_block 1252169689Skanlv_adjust_loop_entry_edge (basic_block first_head, 1253169689Skan basic_block second_head, 1254169689Skan edge e, 1255169689Skan void *cond_expr) 1256169689Skan{ 1257169689Skan basic_block new_head = NULL; 1258169689Skan edge e1; 1259169689Skan 1260169689Skan gcc_assert (e->dest == second_head); 1261169689Skan 1262169689Skan /* Split edge 'e'. This will create a new basic block, where we can 1263169689Skan insert conditional expr. */ 1264169689Skan new_head = split_edge (e); 1265169689Skan 1266169689Skan 1267169689Skan lv_add_condition_to_bb (first_head, second_head, new_head, 1268169689Skan cond_expr); 1269169689Skan 1270169689Skan /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */ 1271169689Skan e1 = make_edge (new_head, first_head, ir_type () ? EDGE_TRUE_VALUE : 0); 1272169689Skan set_immediate_dominator (CDI_DOMINATORS, first_head, new_head); 1273169689Skan set_immediate_dominator (CDI_DOMINATORS, second_head, new_head); 1274169689Skan 1275169689Skan /* Adjust loop header phi nodes. */ 1276169689Skan lv_adjust_loop_header_phi (first_head, second_head, new_head, e1); 1277169689Skan 1278169689Skan return new_head; 1279169689Skan} 1280169689Skan 1281169689Skan/* Main entry point for Loop Versioning transformation. 1282169689Skan 1283169689Skan This transformation given a condition and a loop, creates 1284169689Skan -if (condition) { loop_copy1 } else { loop_copy2 }, 1285169689Skan where loop_copy1 is the loop transformed in one way, and loop_copy2 1286169689Skan is the loop transformed in another way (or unchanged). 'condition' 1287169689Skan may be a run time test for things that were not resolved by static 1288169689Skan analysis (overlapping ranges (anti-aliasing), alignment, etc.). 1289169689Skan 1290169689Skan If PLACE_AFTER is true, we place the new loop after LOOP in the 1291169689Skan instruction stream, otherwise it is placed before LOOP. */ 1292169689Skan 1293169689Skanstruct loop * 1294169689Skanloop_version (struct loops *loops, struct loop * loop, 1295169689Skan void *cond_expr, basic_block *condition_bb, 1296169689Skan bool place_after) 1297169689Skan{ 1298169689Skan basic_block first_head, second_head; 1299169689Skan edge entry, latch_edge, exit, true_edge, false_edge; 1300169689Skan int irred_flag; 1301169689Skan struct loop *nloop; 1302169689Skan basic_block cond_bb; 1303169689Skan 1304169689Skan /* CHECKME: Loop versioning does not handle nested loop at this point. */ 1305169689Skan if (loop->inner) 1306169689Skan return NULL; 1307169689Skan 1308169689Skan /* Record entry and latch edges for the loop */ 1309169689Skan entry = loop_preheader_edge (loop); 1310169689Skan irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; 1311169689Skan entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; 1312169689Skan 1313169689Skan /* Note down head of loop as first_head. */ 1314169689Skan first_head = entry->dest; 1315169689Skan 1316169689Skan /* Duplicate loop. */ 1317169689Skan if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, loops, 1, 1318169689Skan NULL, NULL, NULL, NULL, 0)) 1319169689Skan return NULL; 1320169689Skan 1321169689Skan /* After duplication entry edge now points to new loop head block. 1322169689Skan Note down new head as second_head. */ 1323169689Skan second_head = entry->dest; 1324169689Skan 1325169689Skan /* Split loop entry edge and insert new block with cond expr. */ 1326169689Skan cond_bb = lv_adjust_loop_entry_edge (first_head, second_head, 1327169689Skan entry, cond_expr); 1328169689Skan if (condition_bb) 1329169689Skan *condition_bb = cond_bb; 1330169689Skan 1331169689Skan if (!cond_bb) 1332169689Skan { 1333169689Skan entry->flags |= irred_flag; 1334169689Skan return NULL; 1335169689Skan } 1336169689Skan 1337169689Skan latch_edge = single_succ_edge (get_bb_copy (loop->latch)); 1338169689Skan 1339169689Skan extract_cond_bb_edges (cond_bb, &true_edge, &false_edge); 1340169689Skan nloop = loopify (loops, 1341169689Skan latch_edge, 1342169689Skan single_pred_edge (get_bb_copy (loop->header)), 1343169689Skan cond_bb, true_edge, false_edge, 1344169689Skan false /* Do not redirect all edges. */); 1345169689Skan 1346169689Skan exit = loop->single_exit; 1347169689Skan if (exit) 1348169689Skan nloop->single_exit = find_edge (get_bb_copy (exit->src), exit->dest); 1349169689Skan 1350169689Skan /* loopify redirected latch_edge. Update its PENDING_STMTS. */ 1351169689Skan lv_flush_pending_stmts (latch_edge); 1352169689Skan 1353169689Skan /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */ 1354169689Skan extract_cond_bb_edges (cond_bb, &true_edge, &false_edge); 1355169689Skan lv_flush_pending_stmts (false_edge); 1356169689Skan /* Adjust irreducible flag. */ 1357169689Skan if (irred_flag) 1358169689Skan { 1359169689Skan cond_bb->flags |= BB_IRREDUCIBLE_LOOP; 1360169689Skan loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP; 1361169689Skan loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP; 1362169689Skan single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP; 1363169689Skan } 1364169689Skan 1365169689Skan if (place_after) 1366169689Skan { 1367169689Skan basic_block *bbs = get_loop_body_in_dom_order (nloop), after; 1368169689Skan unsigned i; 1369169689Skan 1370169689Skan after = loop->latch; 1371169689Skan 1372169689Skan for (i = 0; i < nloop->num_nodes; i++) 1373169689Skan { 1374169689Skan move_block_after (bbs[i], after); 1375169689Skan after = bbs[i]; 1376169689Skan } 1377169689Skan free (bbs); 1378169689Skan } 1379169689Skan 1380169689Skan /* At this point condition_bb is loop predheader with two successors, 1381169689Skan first_head and second_head. Make sure that loop predheader has only 1382169689Skan one successor. */ 1383169689Skan loop_split_edge_with (loop_preheader_edge (loop), NULL); 1384169689Skan loop_split_edge_with (loop_preheader_edge (nloop), NULL); 1385169689Skan 1386169689Skan return nloop; 1387169689Skan} 1388169689Skan 1389169689Skan/* The structure of LOOPS might have changed. Some loops might get removed 1390169689Skan (and their headers and latches were set to NULL), loop exists might get 1391169689Skan removed (thus the loop nesting may be wrong), and some blocks and edges 1392169689Skan were changed (so the information about bb --> loop mapping does not have 1393169689Skan to be correct). But still for the remaining loops the header dominates 1394169689Skan the latch, and loops did not get new subloobs (new loops might possibly 1395169689Skan get created, but we are not interested in them). Fix up the mess. 1396169689Skan 1397169689Skan If CHANGED_BBS is not NULL, basic blocks whose loop has changed are 1398169689Skan marked in it. */ 1399169689Skan 1400169689Skanvoid 1401169689Skanfix_loop_structure (struct loops *loops, bitmap changed_bbs) 1402169689Skan{ 1403169689Skan basic_block bb; 1404169689Skan struct loop *loop, *ploop; 1405169689Skan unsigned i; 1406169689Skan 1407169689Skan /* Remove the old bb -> loop mapping. */ 1408169689Skan FOR_EACH_BB (bb) 1409169689Skan { 1410169689Skan bb->aux = (void *) (size_t) bb->loop_father->depth; 1411169689Skan bb->loop_father = loops->tree_root; 1412169689Skan } 1413169689Skan 1414169689Skan /* Remove the dead loops from structures. */ 1415169689Skan loops->tree_root->num_nodes = n_basic_blocks; 1416169689Skan for (i = 1; i < loops->num; i++) 1417169689Skan { 1418169689Skan loop = loops->parray[i]; 1419169689Skan if (!loop) 1420169689Skan continue; 1421169689Skan 1422169689Skan loop->num_nodes = 0; 1423169689Skan if (loop->header) 1424169689Skan continue; 1425169689Skan 1426169689Skan while (loop->inner) 1427169689Skan { 1428169689Skan ploop = loop->inner; 1429169689Skan flow_loop_tree_node_remove (ploop); 1430169689Skan flow_loop_tree_node_add (loop->outer, ploop); 1431169689Skan } 1432169689Skan 1433169689Skan /* Remove the loop and free its data. */ 1434169689Skan flow_loop_tree_node_remove (loop); 1435169689Skan loops->parray[loop->num] = NULL; 1436169689Skan flow_loop_free (loop); 1437169689Skan } 1438169689Skan 1439169689Skan /* Rescan the bodies of loops, starting from the outermost. */ 1440169689Skan loop = loops->tree_root; 1441169689Skan while (1) 1442169689Skan { 1443169689Skan if (loop->inner) 1444169689Skan loop = loop->inner; 1445169689Skan else 1446169689Skan { 1447169689Skan while (!loop->next 1448169689Skan && loop != loops->tree_root) 1449169689Skan loop = loop->outer; 1450169689Skan if (loop == loops->tree_root) 1451169689Skan break; 1452169689Skan 1453169689Skan loop = loop->next; 1454169689Skan } 1455169689Skan 1456169689Skan loop->num_nodes = flow_loop_nodes_find (loop->header, loop); 1457169689Skan } 1458169689Skan 1459169689Skan /* Now fix the loop nesting. */ 1460169689Skan for (i = 1; i < loops->num; i++) 1461169689Skan { 1462169689Skan loop = loops->parray[i]; 1463169689Skan if (!loop) 1464169689Skan continue; 1465169689Skan 1466169689Skan bb = loop_preheader_edge (loop)->src; 1467169689Skan if (bb->loop_father != loop->outer) 1468169689Skan { 1469169689Skan flow_loop_tree_node_remove (loop); 1470169689Skan flow_loop_tree_node_add (bb->loop_father, loop); 1471169689Skan } 1472169689Skan } 1473169689Skan 1474169689Skan /* Mark the blocks whose loop has changed. */ 1475169689Skan FOR_EACH_BB (bb) 1476169689Skan { 1477169689Skan if (changed_bbs 1478169689Skan && (void *) (size_t) bb->loop_father->depth != bb->aux) 1479169689Skan bitmap_set_bit (changed_bbs, bb->index); 1480169689Skan 1481169689Skan bb->aux = NULL; 1482169689Skan } 1483169689Skan 1484169689Skan if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) 1485169689Skan mark_single_exit_loops (loops); 1486169689Skan if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 1487169689Skan mark_irreducible_loops (loops); 1488169689Skan} 1489