1 /* Loop manipulation code for GNU compiler. 2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 2, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING. If not, write to the Free 18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19 02110-1301, USA. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "rtl.h" 26 #include "hard-reg-set.h" 27 #include "obstack.h" 28 #include "basic-block.h" 29 #include "cfgloop.h" 30 #include "cfglayout.h" 31 #include "cfghooks.h" 32 #include "output.h" 33 34 static void duplicate_subloops (struct loops *, struct loop *, struct loop *); 35 static void copy_loops_to (struct loops *, struct loop **, int, 36 struct loop *); 37 static void loop_redirect_edge (edge, basic_block); 38 static bool loop_delete_branch_edge (edge, int); 39 static void remove_bbs (basic_block *, int); 40 static bool rpe_enum_p (basic_block, void *); 41 static int find_path (edge, basic_block **); 42 static bool alp_enum_p (basic_block, void *); 43 static void add_loop (struct loops *, struct loop *); 44 static void fix_loop_placements (struct loops *, struct loop *, bool *); 45 static bool fix_bb_placement (struct loops *, basic_block); 46 static void fix_bb_placements (struct loops *, basic_block, bool *); 47 static void place_new_loop (struct loops *, struct loop *); 48 static void scale_loop_frequencies (struct loop *, int, int); 49 static basic_block create_preheader (struct loop *, int); 50 static void unloop (struct loops *, struct loop *, bool *); 51 52 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y)) 53 54 /* Checks whether basic block BB is dominated by DATA. */ 55 static bool 56 rpe_enum_p (basic_block bb, void *data) 57 { 58 return dominated_by_p (CDI_DOMINATORS, bb, data); 59 } 60 61 /* Remove basic blocks BBS from loop structure and dominance info, 62 and delete them afterwards. */ 63 static void 64 remove_bbs (basic_block *bbs, int nbbs) 65 { 66 int i; 67 68 for (i = 0; i < nbbs; i++) 69 { 70 remove_bb_from_loops (bbs[i]); 71 delete_basic_block (bbs[i]); 72 } 73 } 74 75 /* Find path -- i.e. the basic blocks dominated by edge E and put them 76 into array BBS, that will be allocated large enough to contain them. 77 E->dest must have exactly one predecessor for this to work (it is 78 easy to achieve and we do not put it here because we do not want to 79 alter anything by this function). The number of basic blocks in the 80 path is returned. */ 81 static int 82 find_path (edge e, basic_block **bbs) 83 { 84 gcc_assert (EDGE_COUNT (e->dest->preds) <= 1); 85 86 /* Find bbs in the path. */ 87 *bbs = XCNEWVEC (basic_block, n_basic_blocks); 88 return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs, 89 n_basic_blocks, e->dest); 90 } 91 92 /* Fix placement of basic block BB inside loop hierarchy stored in LOOPS -- 93 Let L be a loop to that BB belongs. Then every successor of BB must either 94 1) belong to some superloop of loop L, or 95 2) be a header of loop K such that K->outer is superloop of L 96 Returns true if we had to move BB into other loop to enforce this condition, 97 false if the placement of BB was already correct (provided that placements 98 of its successors are correct). */ 99 static bool 100 fix_bb_placement (struct loops *loops, basic_block bb) 101 { 102 edge e; 103 edge_iterator ei; 104 struct loop *loop = loops->tree_root, *act; 105 106 FOR_EACH_EDGE (e, ei, bb->succs) 107 { 108 if (e->dest == EXIT_BLOCK_PTR) 109 continue; 110 111 act = e->dest->loop_father; 112 if (act->header == e->dest) 113 act = act->outer; 114 115 if (flow_loop_nested_p (loop, act)) 116 loop = act; 117 } 118 119 if (loop == bb->loop_father) 120 return false; 121 122 remove_bb_from_loops (bb); 123 add_bb_to_loop (bb, loop); 124 125 return true; 126 } 127 128 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e. 129 enforce condition condition stated in description of fix_bb_placement. We 130 start from basic block FROM that had some of its successors removed, so that 131 his placement no longer has to be correct, and iteratively fix placement of 132 its predecessors that may change if placement of FROM changed. Also fix 133 placement of subloops of FROM->loop_father, that might also be altered due 134 to this change; the condition for them is similar, except that instead of 135 successors we consider edges coming out of the loops. 136 137 If the changes may invalidate the information about irreducible regions, 138 IRRED_INVALIDATED is set to true. */ 139 140 static void 141 fix_bb_placements (struct loops *loops, basic_block from, 142 bool *irred_invalidated) 143 { 144 sbitmap in_queue; 145 basic_block *queue, *qtop, *qbeg, *qend; 146 struct loop *base_loop; 147 edge e; 148 149 /* We pass through blocks back-reachable from FROM, testing whether some 150 of their successors moved to outer loop. It may be necessary to 151 iterate several times, but it is finite, as we stop unless we move 152 the basic block up the loop structure. The whole story is a bit 153 more complicated due to presence of subloops, those are moved using 154 fix_loop_placement. */ 155 156 base_loop = from->loop_father; 157 if (base_loop == loops->tree_root) 158 return; 159 160 in_queue = sbitmap_alloc (last_basic_block); 161 sbitmap_zero (in_queue); 162 SET_BIT (in_queue, from->index); 163 /* Prevent us from going out of the base_loop. */ 164 SET_BIT (in_queue, base_loop->header->index); 165 166 queue = XNEWVEC (basic_block, base_loop->num_nodes + 1); 167 qtop = queue + base_loop->num_nodes + 1; 168 qbeg = queue; 169 qend = queue + 1; 170 *qbeg = from; 171 172 while (qbeg != qend) 173 { 174 edge_iterator ei; 175 from = *qbeg; 176 qbeg++; 177 if (qbeg == qtop) 178 qbeg = queue; 179 RESET_BIT (in_queue, from->index); 180 181 if (from->loop_father->header == from) 182 { 183 /* Subloop header, maybe move the loop upward. */ 184 if (!fix_loop_placement (from->loop_father)) 185 continue; 186 } 187 else 188 { 189 /* Ordinary basic block. */ 190 if (!fix_bb_placement (loops, from)) 191 continue; 192 } 193 194 FOR_EACH_EDGE (e, ei, from->succs) 195 { 196 if (e->flags & EDGE_IRREDUCIBLE_LOOP) 197 *irred_invalidated = true; 198 } 199 200 /* Something has changed, insert predecessors into queue. */ 201 FOR_EACH_EDGE (e, ei, from->preds) 202 { 203 basic_block pred = e->src; 204 struct loop *nca; 205 206 if (e->flags & EDGE_IRREDUCIBLE_LOOP) 207 *irred_invalidated = true; 208 209 if (TEST_BIT (in_queue, pred->index)) 210 continue; 211 212 /* If it is subloop, then it either was not moved, or 213 the path up the loop tree from base_loop do not contain 214 it. */ 215 nca = find_common_loop (pred->loop_father, base_loop); 216 if (pred->loop_father != base_loop 217 && (nca == base_loop 218 || nca != pred->loop_father)) 219 pred = pred->loop_father->header; 220 else if (!flow_loop_nested_p (from->loop_father, pred->loop_father)) 221 { 222 /* No point in processing it. */ 223 continue; 224 } 225 226 if (TEST_BIT (in_queue, pred->index)) 227 continue; 228 229 /* Schedule the basic block. */ 230 *qend = pred; 231 qend++; 232 if (qend == qtop) 233 qend = queue; 234 SET_BIT (in_queue, pred->index); 235 } 236 } 237 free (in_queue); 238 free (queue); 239 } 240 241 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E 242 and update loop structure stored in LOOPS and dominators. Return true if 243 we were able to remove the path, false otherwise (and nothing is affected 244 then). */ 245 bool 246 remove_path (struct loops *loops, edge e) 247 { 248 edge ae; 249 basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb; 250 int i, nrem, n_bord_bbs, n_dom_bbs; 251 sbitmap seen; 252 bool deleted, irred_invalidated = false; 253 254 if (!loop_delete_branch_edge (e, 0)) 255 return false; 256 257 /* Keep track of whether we need to update information about irreducible 258 regions. This is the case if the removed area is a part of the 259 irreducible region, or if the set of basic blocks that belong to a loop 260 that is inside an irreducible region is changed, or if such a loop is 261 removed. */ 262 if (e->flags & EDGE_IRREDUCIBLE_LOOP) 263 irred_invalidated = true; 264 265 /* We need to check whether basic blocks are dominated by the edge 266 e, but we only have basic block dominators. This is easy to 267 fix -- when e->dest has exactly one predecessor, this corresponds 268 to blocks dominated by e->dest, if not, split the edge. */ 269 if (!single_pred_p (e->dest)) 270 e = single_pred_edge (loop_split_edge_with (e, NULL_RTX)); 271 272 /* It may happen that by removing path we remove one or more loops 273 we belong to. In this case first unloop the loops, then proceed 274 normally. We may assume that e->dest is not a header of any loop, 275 as it now has exactly one predecessor. */ 276 while (e->src->loop_father->outer 277 && dominated_by_p (CDI_DOMINATORS, 278 e->src->loop_father->latch, e->dest)) 279 unloop (loops, e->src->loop_father, &irred_invalidated); 280 281 /* Identify the path. */ 282 nrem = find_path (e, &rem_bbs); 283 284 n_bord_bbs = 0; 285 bord_bbs = XCNEWVEC (basic_block, n_basic_blocks); 286 seen = sbitmap_alloc (last_basic_block); 287 sbitmap_zero (seen); 288 289 /* Find "border" hexes -- i.e. those with predecessor in removed path. */ 290 for (i = 0; i < nrem; i++) 291 SET_BIT (seen, rem_bbs[i]->index); 292 for (i = 0; i < nrem; i++) 293 { 294 edge_iterator ei; 295 bb = rem_bbs[i]; 296 FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs) 297 if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index)) 298 { 299 SET_BIT (seen, ae->dest->index); 300 bord_bbs[n_bord_bbs++] = ae->dest; 301 302 if (ae->flags & EDGE_IRREDUCIBLE_LOOP) 303 irred_invalidated = true; 304 } 305 } 306 307 /* Remove the path. */ 308 from = e->src; 309 deleted = loop_delete_branch_edge (e, 1); 310 gcc_assert (deleted); 311 dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); 312 313 /* Cancel loops contained in the path. */ 314 for (i = 0; i < nrem; i++) 315 if (rem_bbs[i]->loop_father->header == rem_bbs[i]) 316 cancel_loop_tree (loops, rem_bbs[i]->loop_father); 317 318 remove_bbs (rem_bbs, nrem); 319 free (rem_bbs); 320 321 /* Find blocks whose dominators may be affected. */ 322 n_dom_bbs = 0; 323 sbitmap_zero (seen); 324 for (i = 0; i < n_bord_bbs; i++) 325 { 326 basic_block ldom; 327 328 bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]); 329 if (TEST_BIT (seen, bb->index)) 330 continue; 331 SET_BIT (seen, bb->index); 332 333 for (ldom = first_dom_son (CDI_DOMINATORS, bb); 334 ldom; 335 ldom = next_dom_son (CDI_DOMINATORS, ldom)) 336 if (!dominated_by_p (CDI_DOMINATORS, from, ldom)) 337 dom_bbs[n_dom_bbs++] = ldom; 338 } 339 340 free (seen); 341 342 /* Recount dominators. */ 343 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); 344 free (dom_bbs); 345 free (bord_bbs); 346 347 /* Fix placements of basic blocks inside loops and the placement of 348 loops in the loop tree. */ 349 fix_bb_placements (loops, from, &irred_invalidated); 350 fix_loop_placements (loops, from->loop_father, &irred_invalidated); 351 352 if (irred_invalidated 353 && (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) != 0) 354 mark_irreducible_loops (loops); 355 356 return true; 357 } 358 359 /* Predicate for enumeration in add_loop. */ 360 static bool 361 alp_enum_p (basic_block bb, void *alp_header) 362 { 363 return bb != (basic_block) alp_header; 364 } 365 366 /* Given LOOP structure with filled header and latch, find the body of the 367 corresponding loop and add it to LOOPS tree. */ 368 static void 369 add_loop (struct loops *loops, struct loop *loop) 370 { 371 basic_block *bbs; 372 int i, n; 373 374 /* Add it to loop structure. */ 375 place_new_loop (loops, loop); 376 loop->level = 1; 377 378 /* Find its nodes. */ 379 bbs = XCNEWVEC (basic_block, n_basic_blocks); 380 n = dfs_enumerate_from (loop->latch, 1, alp_enum_p, 381 bbs, n_basic_blocks, loop->header); 382 383 for (i = 0; i < n; i++) 384 add_bb_to_loop (bbs[i], loop); 385 add_bb_to_loop (loop->header, loop); 386 387 free (bbs); 388 } 389 390 /* Multiply all frequencies in LOOP by NUM/DEN. */ 391 static void 392 scale_loop_frequencies (struct loop *loop, int num, int den) 393 { 394 basic_block *bbs; 395 396 bbs = get_loop_body (loop); 397 scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den); 398 free (bbs); 399 } 400 401 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting 402 latch to header and update loop tree stored in LOOPS and dominators 403 accordingly. Everything between them plus LATCH_EDGE destination must 404 be dominated by HEADER_EDGE destination, and back-reachable from 405 LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB, 406 FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and 407 TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE. 408 Returns newly created loop. */ 409 410 struct loop * 411 loopify (struct loops *loops, edge latch_edge, edge header_edge, 412 basic_block switch_bb, edge true_edge, edge false_edge, 413 bool redirect_all_edges) 414 { 415 basic_block succ_bb = latch_edge->dest; 416 basic_block pred_bb = header_edge->src; 417 basic_block *dom_bbs, *body; 418 unsigned n_dom_bbs, i; 419 sbitmap seen; 420 struct loop *loop = XCNEW (struct loop); 421 struct loop *outer = succ_bb->loop_father->outer; 422 int freq, prob, tot_prob; 423 gcov_type cnt; 424 edge e; 425 edge_iterator ei; 426 427 loop->header = header_edge->dest; 428 loop->latch = latch_edge->src; 429 430 freq = EDGE_FREQUENCY (header_edge); 431 cnt = header_edge->count; 432 prob = EDGE_SUCC (switch_bb, 0)->probability; 433 tot_prob = prob + EDGE_SUCC (switch_bb, 1)->probability; 434 if (tot_prob == 0) 435 tot_prob = 1; 436 437 /* Redirect edges. */ 438 loop_redirect_edge (latch_edge, loop->header); 439 loop_redirect_edge (true_edge, succ_bb); 440 441 /* During loop versioning, one of the switch_bb edge is already properly 442 set. Do not redirect it again unless redirect_all_edges is true. */ 443 if (redirect_all_edges) 444 { 445 loop_redirect_edge (header_edge, switch_bb); 446 loop_redirect_edge (false_edge, loop->header); 447 448 /* Update dominators. */ 449 set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb); 450 set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb); 451 } 452 453 set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb); 454 455 /* Compute new loop. */ 456 add_loop (loops, loop); 457 flow_loop_tree_node_add (outer, loop); 458 459 /* Add switch_bb to appropriate loop. */ 460 add_bb_to_loop (switch_bb, outer); 461 462 /* Fix frequencies. */ 463 switch_bb->frequency = freq; 464 switch_bb->count = cnt; 465 FOR_EACH_EDGE (e, ei, switch_bb->succs) 466 e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE; 467 scale_loop_frequencies (loop, prob, tot_prob); 468 scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob); 469 470 /* Update dominators of blocks outside of LOOP. */ 471 dom_bbs = XCNEWVEC (basic_block, n_basic_blocks); 472 n_dom_bbs = 0; 473 seen = sbitmap_alloc (last_basic_block); 474 sbitmap_zero (seen); 475 body = get_loop_body (loop); 476 477 for (i = 0; i < loop->num_nodes; i++) 478 SET_BIT (seen, body[i]->index); 479 480 for (i = 0; i < loop->num_nodes; i++) 481 { 482 basic_block ldom; 483 484 for (ldom = first_dom_son (CDI_DOMINATORS, body[i]); 485 ldom; 486 ldom = next_dom_son (CDI_DOMINATORS, ldom)) 487 if (!TEST_BIT (seen, ldom->index)) 488 { 489 SET_BIT (seen, ldom->index); 490 dom_bbs[n_dom_bbs++] = ldom; 491 } 492 } 493 494 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs); 495 496 free (body); 497 free (seen); 498 free (dom_bbs); 499 500 return loop; 501 } 502 503 /* Remove the latch edge of a LOOP and update LOOPS tree to indicate that 504 the LOOP was removed. After this function, original loop latch will 505 have no successor, which caller is expected to fix somehow. 506 507 If this may cause the information about irreducible regions to become 508 invalid, IRRED_INVALIDATED is set to true. */ 509 510 static void 511 unloop (struct loops *loops, struct loop *loop, bool *irred_invalidated) 512 { 513 basic_block *body; 514 struct loop *ploop; 515 unsigned i, n; 516 basic_block latch = loop->latch; 517 bool dummy = false; 518 519 if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP) 520 *irred_invalidated = true; 521 522 /* This is relatively straightforward. The dominators are unchanged, as 523 loop header dominates loop latch, so the only thing we have to care of 524 is the placement of loops and basic blocks inside the loop tree. We 525 move them all to the loop->outer, and then let fix_bb_placements do 526 its work. */ 527 528 body = get_loop_body (loop); 529 n = loop->num_nodes; 530 for (i = 0; i < n; i++) 531 if (body[i]->loop_father == loop) 532 { 533 remove_bb_from_loops (body[i]); 534 add_bb_to_loop (body[i], loop->outer); 535 } 536 free(body); 537 538 while (loop->inner) 539 { 540 ploop = loop->inner; 541 flow_loop_tree_node_remove (ploop); 542 flow_loop_tree_node_add (loop->outer, ploop); 543 } 544 545 /* Remove the loop and free its data. */ 546 flow_loop_tree_node_remove (loop); 547 loops->parray[loop->num] = NULL; 548 flow_loop_free (loop); 549 550 remove_edge (single_succ_edge (latch)); 551 552 /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if 553 there is an irreducible region inside the cancelled loop, the flags will 554 be still correct. */ 555 fix_bb_placements (loops, latch, &dummy); 556 } 557 558 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop 559 FATHER of LOOP such that all of the edges coming out of LOOP belong to 560 FATHER, and set it as outer loop of LOOP. Return true if placement of 561 LOOP changed. */ 562 563 int 564 fix_loop_placement (struct loop *loop) 565 { 566 basic_block *body; 567 unsigned i; 568 edge e; 569 edge_iterator ei; 570 struct loop *father = loop->pred[0], *act; 571 572 body = get_loop_body (loop); 573 for (i = 0; i < loop->num_nodes; i++) 574 FOR_EACH_EDGE (e, ei, body[i]->succs) 575 if (!flow_bb_inside_loop_p (loop, e->dest)) 576 { 577 act = find_common_loop (loop, e->dest->loop_father); 578 if (flow_loop_nested_p (father, act)) 579 father = act; 580 } 581 free (body); 582 583 if (father != loop->outer) 584 { 585 for (act = loop->outer; act != father; act = act->outer) 586 act->num_nodes -= loop->num_nodes; 587 flow_loop_tree_node_remove (loop); 588 flow_loop_tree_node_add (father, loop); 589 return 1; 590 } 591 return 0; 592 } 593 594 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that 595 condition stated in description of fix_loop_placement holds for them. 596 It is used in case when we removed some edges coming out of LOOP, which 597 may cause the right placement of LOOP inside loop tree to change. 598 599 IRRED_INVALIDATED is set to true if a change in the loop structures might 600 invalidate the information about irreducible regions. */ 601 602 static void 603 fix_loop_placements (struct loops *loops, struct loop *loop, 604 bool *irred_invalidated) 605 { 606 struct loop *outer; 607 608 while (loop->outer) 609 { 610 outer = loop->outer; 611 if (!fix_loop_placement (loop)) 612 break; 613 614 /* Changing the placement of a loop in the loop tree may alter the 615 validity of condition 2) of the description of fix_bb_placement 616 for its preheader, because the successor is the header and belongs 617 to the loop. So call fix_bb_placements to fix up the placement 618 of the preheader and (possibly) of its predecessors. */ 619 fix_bb_placements (loops, loop_preheader_edge (loop)->src, 620 irred_invalidated); 621 loop = outer; 622 } 623 } 624 625 /* Creates place for a new LOOP in LOOPS structure. */ 626 static void 627 place_new_loop (struct loops *loops, struct loop *loop) 628 { 629 loops->parray = 630 xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *)); 631 loops->parray[loops->num] = loop; 632 633 loop->num = loops->num++; 634 } 635 636 /* Copies copy of LOOP as subloop of TARGET loop, placing newly 637 created loop into LOOPS structure. */ 638 struct loop * 639 duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target) 640 { 641 struct loop *cloop; 642 cloop = XCNEW (struct loop); 643 place_new_loop (loops, cloop); 644 645 /* Initialize copied loop. */ 646 cloop->level = loop->level; 647 648 /* Set it as copy of loop. */ 649 loop->copy = cloop; 650 651 /* Add it to target. */ 652 flow_loop_tree_node_add (target, cloop); 653 654 return cloop; 655 } 656 657 /* Copies structure of subloops of LOOP into TARGET loop, placing 658 newly created loops into loop tree stored in LOOPS. */ 659 static void 660 duplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target) 661 { 662 struct loop *aloop, *cloop; 663 664 for (aloop = loop->inner; aloop; aloop = aloop->next) 665 { 666 cloop = duplicate_loop (loops, aloop, target); 667 duplicate_subloops (loops, aloop, cloop); 668 } 669 } 670 671 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS, 672 into TARGET loop, placing newly created loops into loop tree LOOPS. */ 673 static void 674 copy_loops_to (struct loops *loops, struct loop **copied_loops, int n, struct loop *target) 675 { 676 struct loop *aloop; 677 int i; 678 679 for (i = 0; i < n; i++) 680 { 681 aloop = duplicate_loop (loops, copied_loops[i], target); 682 duplicate_subloops (loops, copied_loops[i], aloop); 683 } 684 } 685 686 /* Redirects edge E to basic block DEST. */ 687 static void 688 loop_redirect_edge (edge e, basic_block dest) 689 { 690 if (e->dest == dest) 691 return; 692 693 redirect_edge_and_branch_force (e, dest); 694 } 695 696 /* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set, 697 just test whether it is possible to remove the edge. */ 698 static bool 699 loop_delete_branch_edge (edge e, int really_delete) 700 { 701 basic_block src = e->src; 702 basic_block newdest; 703 int irr; 704 edge snd; 705 706 gcc_assert (EDGE_COUNT (src->succs) > 1); 707 708 /* Cannot handle more than two exit edges. */ 709 if (EDGE_COUNT (src->succs) > 2) 710 return false; 711 /* And it must be just a simple branch. */ 712 if (!any_condjump_p (BB_END (src))) 713 return false; 714 715 snd = e == EDGE_SUCC (src, 0) ? EDGE_SUCC (src, 1) : EDGE_SUCC (src, 0); 716 newdest = snd->dest; 717 if (newdest == EXIT_BLOCK_PTR) 718 return false; 719 720 /* Hopefully the above conditions should suffice. */ 721 if (!really_delete) 722 return true; 723 724 /* Redirecting behaves wrongly wrto this flag. */ 725 irr = snd->flags & EDGE_IRREDUCIBLE_LOOP; 726 727 if (!redirect_edge_and_branch (e, newdest)) 728 return false; 729 single_succ_edge (src)->flags &= ~EDGE_IRREDUCIBLE_LOOP; 730 single_succ_edge (src)->flags |= irr; 731 732 return true; 733 } 734 735 /* Check whether LOOP's body can be duplicated. */ 736 bool 737 can_duplicate_loop_p (struct loop *loop) 738 { 739 int ret; 740 basic_block *bbs = get_loop_body (loop); 741 742 ret = can_copy_bbs_p (bbs, loop->num_nodes); 743 free (bbs); 744 745 return ret; 746 } 747 748 /* The NBBS blocks in BBS will get duplicated and the copies will be placed 749 to LOOP. Update the single_exit information in superloops of LOOP. */ 750 751 static void 752 update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs, 753 struct loop *loop) 754 { 755 unsigned i; 756 757 for (i = 0; i < nbbs; i++) 758 bbs[i]->flags |= BB_DUPLICATED; 759 760 for (; loop->outer; loop = loop->outer) 761 { 762 if (!loop->single_exit) 763 continue; 764 765 if (loop->single_exit->src->flags & BB_DUPLICATED) 766 loop->single_exit = NULL; 767 } 768 769 for (i = 0; i < nbbs; i++) 770 bbs[i]->flags &= ~BB_DUPLICATED; 771 } 772 773 /* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating 774 LOOPS structure and dominators. E's destination must be LOOP header for 775 this to work, i.e. it must be entry or latch edge of this loop; these are 776 unique, as the loops must have preheaders for this function to work 777 correctly (in case E is latch, the function unrolls the loop, if E is entry 778 edge, it peels the loop). Store edges created by copying ORIG edge from 779 copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to 780 original LOOP body, the other copies are numbered in order given by control 781 flow through them) into TO_REMOVE array. Returns false if duplication is 782 impossible. */ 783 bool 784 duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops, 785 unsigned int ndupl, sbitmap wont_exit, 786 edge orig, edge *to_remove, 787 unsigned int *n_to_remove, int flags) 788 { 789 struct loop *target, *aloop; 790 struct loop **orig_loops; 791 unsigned n_orig_loops; 792 basic_block header = loop->header, latch = loop->latch; 793 basic_block *new_bbs, *bbs, *first_active; 794 basic_block new_bb, bb, first_active_latch = NULL; 795 edge ae, latch_edge; 796 edge spec_edges[2], new_spec_edges[2]; 797 #define SE_LATCH 0 798 #define SE_ORIG 1 799 unsigned i, j, n; 800 int is_latch = (latch == e->src); 801 int scale_act = 0, *scale_step = NULL, scale_main = 0; 802 int p, freq_in, freq_le, freq_out_orig; 803 int prob_pass_thru, prob_pass_wont_exit, prob_pass_main; 804 int add_irreducible_flag; 805 basic_block place_after; 806 807 gcc_assert (e->dest == loop->header); 808 gcc_assert (ndupl > 0); 809 810 if (orig) 811 { 812 /* Orig must be edge out of the loop. */ 813 gcc_assert (flow_bb_inside_loop_p (loop, orig->src)); 814 gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest)); 815 } 816 817 n = loop->num_nodes; 818 bbs = get_loop_body_in_dom_order (loop); 819 gcc_assert (bbs[0] == loop->header); 820 gcc_assert (bbs[n - 1] == loop->latch); 821 822 /* Check whether duplication is possible. */ 823 if (!can_copy_bbs_p (bbs, loop->num_nodes)) 824 { 825 free (bbs); 826 return false; 827 } 828 new_bbs = XNEWVEC (basic_block, loop->num_nodes); 829 830 /* In case we are doing loop peeling and the loop is in the middle of 831 irreducible region, the peeled copies will be inside it too. */ 832 add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP; 833 gcc_assert (!is_latch || !add_irreducible_flag); 834 835 /* Find edge from latch. */ 836 latch_edge = loop_latch_edge (loop); 837 838 if (flags & DLTHE_FLAG_UPDATE_FREQ) 839 { 840 /* Calculate coefficients by that we have to scale frequencies 841 of duplicated loop bodies. */ 842 freq_in = header->frequency; 843 freq_le = EDGE_FREQUENCY (latch_edge); 844 if (freq_in == 0) 845 freq_in = 1; 846 if (freq_in < freq_le) 847 freq_in = freq_le; 848 freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le; 849 if (freq_out_orig > freq_in - freq_le) 850 freq_out_orig = freq_in - freq_le; 851 prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in); 852 prob_pass_wont_exit = 853 RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in); 854 855 scale_step = XNEWVEC (int, ndupl); 856 857 for (i = 1; i <= ndupl; i++) 858 scale_step[i - 1] = TEST_BIT (wont_exit, i) 859 ? prob_pass_wont_exit 860 : prob_pass_thru; 861 862 /* Complete peeling is special as the probability of exit in last 863 copy becomes 1. */ 864 if (flags & DLTHE_FLAG_COMPLETTE_PEEL) 865 { 866 int wanted_freq = EDGE_FREQUENCY (e); 867 868 if (wanted_freq > freq_in) 869 wanted_freq = freq_in; 870 871 gcc_assert (!is_latch); 872 /* First copy has frequency of incoming edge. Each subsequent 873 frequency should be reduced by prob_pass_wont_exit. Caller 874 should've managed the flags so all except for original loop 875 has won't exist set. */ 876 scale_act = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in); 877 /* Now simulate the duplication adjustments and compute header 878 frequency of the last copy. */ 879 for (i = 0; i < ndupl; i++) 880 wanted_freq = RDIV (wanted_freq * scale_step[i], REG_BR_PROB_BASE); 881 scale_main = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in); 882 } 883 else if (is_latch) 884 { 885 prob_pass_main = TEST_BIT (wont_exit, 0) 886 ? prob_pass_wont_exit 887 : prob_pass_thru; 888 p = prob_pass_main; 889 scale_main = REG_BR_PROB_BASE; 890 for (i = 0; i < ndupl; i++) 891 { 892 scale_main += p; 893 p = RDIV (p * scale_step[i], REG_BR_PROB_BASE); 894 } 895 scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main); 896 scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE); 897 } 898 else 899 { 900 scale_main = REG_BR_PROB_BASE; 901 for (i = 0; i < ndupl; i++) 902 scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE); 903 scale_act = REG_BR_PROB_BASE - prob_pass_thru; 904 } 905 for (i = 0; i < ndupl; i++) 906 gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE); 907 gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE 908 && scale_act >= 0 && scale_act <= REG_BR_PROB_BASE); 909 } 910 911 /* Loop the new bbs will belong to. */ 912 target = e->src->loop_father; 913 914 /* Original loops. */ 915 n_orig_loops = 0; 916 for (aloop = loop->inner; aloop; aloop = aloop->next) 917 n_orig_loops++; 918 orig_loops = XCNEWVEC (struct loop *, n_orig_loops); 919 for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++) 920 orig_loops[i] = aloop; 921 922 loop->copy = target; 923 924 first_active = XNEWVEC (basic_block, n); 925 if (is_latch) 926 { 927 memcpy (first_active, bbs, n * sizeof (basic_block)); 928 first_active_latch = latch; 929 } 930 931 /* Update the information about single exits. */ 932 if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) 933 update_single_exits_after_duplication (bbs, n, target); 934 935 /* Record exit edge in original loop body. */ 936 if (orig && TEST_BIT (wont_exit, 0)) 937 to_remove[(*n_to_remove)++] = orig; 938 939 spec_edges[SE_ORIG] = orig; 940 spec_edges[SE_LATCH] = latch_edge; 941 942 place_after = e->src; 943 for (j = 0; j < ndupl; j++) 944 { 945 /* Copy loops. */ 946 copy_loops_to (loops, orig_loops, n_orig_loops, target); 947 948 /* Copy bbs. */ 949 copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop, 950 place_after); 951 place_after = new_spec_edges[SE_LATCH]->src; 952 953 if (flags & DLTHE_RECORD_COPY_NUMBER) 954 for (i = 0; i < n; i++) 955 { 956 gcc_assert (!new_bbs[i]->aux); 957 new_bbs[i]->aux = (void *)(size_t)(j + 1); 958 } 959 960 /* Note whether the blocks and edges belong to an irreducible loop. */ 961 if (add_irreducible_flag) 962 { 963 for (i = 0; i < n; i++) 964 new_bbs[i]->flags |= BB_DUPLICATED; 965 for (i = 0; i < n; i++) 966 { 967 edge_iterator ei; 968 new_bb = new_bbs[i]; 969 if (new_bb->loop_father == target) 970 new_bb->flags |= BB_IRREDUCIBLE_LOOP; 971 972 FOR_EACH_EDGE (ae, ei, new_bb->succs) 973 if ((ae->dest->flags & BB_DUPLICATED) 974 && (ae->src->loop_father == target 975 || ae->dest->loop_father == target)) 976 ae->flags |= EDGE_IRREDUCIBLE_LOOP; 977 } 978 for (i = 0; i < n; i++) 979 new_bbs[i]->flags &= ~BB_DUPLICATED; 980 } 981 982 /* Redirect the special edges. */ 983 if (is_latch) 984 { 985 redirect_edge_and_branch_force (latch_edge, new_bbs[0]); 986 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH], 987 loop->header); 988 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch); 989 latch = loop->latch = new_bbs[n - 1]; 990 e = latch_edge = new_spec_edges[SE_LATCH]; 991 } 992 else 993 { 994 redirect_edge_and_branch_force (new_spec_edges[SE_LATCH], 995 loop->header); 996 redirect_edge_and_branch_force (e, new_bbs[0]); 997 set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src); 998 e = new_spec_edges[SE_LATCH]; 999 } 1000 1001 /* Record exit edge in this copy. */ 1002 if (orig && TEST_BIT (wont_exit, j + 1)) 1003 to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG]; 1004 1005 /* Record the first copy in the control flow order if it is not 1006 the original loop (i.e. in case of peeling). */ 1007 if (!first_active_latch) 1008 { 1009 memcpy (first_active, new_bbs, n * sizeof (basic_block)); 1010 first_active_latch = new_bbs[n - 1]; 1011 } 1012 1013 /* Set counts and frequencies. */ 1014 if (flags & DLTHE_FLAG_UPDATE_FREQ) 1015 { 1016 scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE); 1017 scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE); 1018 } 1019 } 1020 free (new_bbs); 1021 free (orig_loops); 1022 1023 /* Update the original loop. */ 1024 if (!is_latch) 1025 set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src); 1026 if (flags & DLTHE_FLAG_UPDATE_FREQ) 1027 { 1028 scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE); 1029 free (scale_step); 1030 } 1031 1032 /* Update dominators of outer blocks if affected. */ 1033 for (i = 0; i < n; i++) 1034 { 1035 basic_block dominated, dom_bb, *dom_bbs; 1036 int n_dom_bbs,j; 1037 1038 bb = bbs[i]; 1039 bb->aux = 0; 1040 1041 n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs); 1042 for (j = 0; j < n_dom_bbs; j++) 1043 { 1044 dominated = dom_bbs[j]; 1045 if (flow_bb_inside_loop_p (loop, dominated)) 1046 continue; 1047 dom_bb = nearest_common_dominator ( 1048 CDI_DOMINATORS, first_active[i], first_active_latch); 1049 set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb); 1050 } 1051 free (dom_bbs); 1052 } 1053 free (first_active); 1054 1055 free (bbs); 1056 1057 return true; 1058 } 1059 1060 /* A callback for make_forwarder block, to redirect all edges except for 1061 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide 1062 whether to redirect it. */ 1063 1064 static edge mfb_kj_edge; 1065 static bool 1066 mfb_keep_just (edge e) 1067 { 1068 return e != mfb_kj_edge; 1069 } 1070 1071 /* A callback for make_forwarder block, to update data structures for a basic 1072 block JUMP created by redirecting an edge (only the latch edge is being 1073 redirected). */ 1074 1075 static void 1076 mfb_update_loops (basic_block jump) 1077 { 1078 struct loop *loop = single_succ (jump)->loop_father; 1079 1080 if (dom_computed[CDI_DOMINATORS]) 1081 set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump)); 1082 add_bb_to_loop (jump, loop); 1083 loop->latch = jump; 1084 } 1085 1086 /* Creates a pre-header for a LOOP. Returns newly created block. Unless 1087 CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single 1088 entry; otherwise we also force preheader block to have only one successor. 1089 The function also updates dominators. */ 1090 1091 static basic_block 1092 create_preheader (struct loop *loop, int flags) 1093 { 1094 edge e, fallthru; 1095 basic_block dummy; 1096 struct loop *cloop, *ploop; 1097 int nentry = 0; 1098 bool irred = false; 1099 bool latch_edge_was_fallthru; 1100 edge one_succ_pred = 0; 1101 edge_iterator ei; 1102 1103 cloop = loop->outer; 1104 1105 FOR_EACH_EDGE (e, ei, loop->header->preds) 1106 { 1107 if (e->src == loop->latch) 1108 continue; 1109 irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0; 1110 nentry++; 1111 if (single_succ_p (e->src)) 1112 one_succ_pred = e; 1113 } 1114 gcc_assert (nentry); 1115 if (nentry == 1) 1116 { 1117 /* Get an edge that is different from the one from loop->latch 1118 to loop->header. */ 1119 e = EDGE_PRED (loop->header, 1120 EDGE_PRED (loop->header, 0)->src == loop->latch); 1121 1122 if (!(flags & CP_SIMPLE_PREHEADERS) || single_succ_p (e->src)) 1123 return NULL; 1124 } 1125 1126 mfb_kj_edge = loop_latch_edge (loop); 1127 latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0; 1128 fallthru = make_forwarder_block (loop->header, mfb_keep_just, 1129 mfb_update_loops); 1130 dummy = fallthru->src; 1131 loop->header = fallthru->dest; 1132 1133 /* The header could be a latch of some superloop(s); due to design of 1134 split_block, it would now move to fallthru->dest. */ 1135 for (ploop = loop; ploop; ploop = ploop->outer) 1136 if (ploop->latch == dummy) 1137 ploop->latch = fallthru->dest; 1138 1139 /* Try to be clever in placing the newly created preheader. The idea is to 1140 avoid breaking any "fallthruness" relationship between blocks. 1141 1142 The preheader was created just before the header and all incoming edges 1143 to the header were redirected to the preheader, except the latch edge. 1144 So the only problematic case is when this latch edge was a fallthru 1145 edge: it is not anymore after the preheader creation so we have broken 1146 the fallthruness. We're therefore going to look for a better place. */ 1147 if (latch_edge_was_fallthru) 1148 { 1149 if (one_succ_pred) 1150 e = one_succ_pred; 1151 else 1152 e = EDGE_PRED (dummy, 0); 1153 1154 move_block_after (dummy, e->src); 1155 } 1156 1157 loop->header->loop_father = loop; 1158 add_bb_to_loop (dummy, cloop); 1159 1160 if (irred) 1161 { 1162 dummy->flags |= BB_IRREDUCIBLE_LOOP; 1163 single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP; 1164 } 1165 1166 if (dump_file) 1167 fprintf (dump_file, "Created preheader block for loop %i\n", 1168 loop->num); 1169 1170 return dummy; 1171 } 1172 1173 /* Create preheaders for each loop from loop tree stored in LOOPS; for meaning 1174 of FLAGS see create_preheader. */ 1175 void 1176 create_preheaders (struct loops *loops, int flags) 1177 { 1178 unsigned i; 1179 for (i = 1; i < loops->num; i++) 1180 create_preheader (loops->parray[i], flags); 1181 loops->state |= LOOPS_HAVE_PREHEADERS; 1182 } 1183 1184 /* Forces all loop latches of loops from loop tree LOOPS to have only single 1185 successor. */ 1186 void 1187 force_single_succ_latches (struct loops *loops) 1188 { 1189 unsigned i; 1190 struct loop *loop; 1191 edge e; 1192 1193 for (i = 1; i < loops->num; i++) 1194 { 1195 loop = loops->parray[i]; 1196 if (loop->latch != loop->header && single_succ_p (loop->latch)) 1197 continue; 1198 1199 e = find_edge (loop->latch, loop->header); 1200 1201 loop_split_edge_with (e, NULL_RTX); 1202 } 1203 loops->state |= LOOPS_HAVE_SIMPLE_LATCHES; 1204 } 1205 1206 /* A quite stupid function to put INSNS on edge E. They are supposed to form 1207 just one basic block. Jumps in INSNS are not handled, so cfg do not have to 1208 be ok after this function. The created block is placed on correct place 1209 in LOOPS structure and its dominator is set. */ 1210 basic_block 1211 loop_split_edge_with (edge e, rtx insns) 1212 { 1213 basic_block src, dest, new_bb; 1214 struct loop *loop_c; 1215 1216 src = e->src; 1217 dest = e->dest; 1218 1219 loop_c = find_common_loop (src->loop_father, dest->loop_father); 1220 1221 /* Create basic block for it. */ 1222 1223 new_bb = split_edge (e); 1224 add_bb_to_loop (new_bb, loop_c); 1225 new_bb->flags |= (insns ? BB_SUPERBLOCK : 0); 1226 1227 if (insns) 1228 emit_insn_after (insns, BB_END (new_bb)); 1229 1230 if (dest->loop_father->latch == src) 1231 dest->loop_father->latch = new_bb; 1232 1233 return new_bb; 1234 } 1235 1236 /* This function is called from loop_version. It splits the entry edge 1237 of the loop we want to version, adds the versioning condition, and 1238 adjust the edges to the two versions of the loop appropriately. 1239 e is an incoming edge. Returns the basic block containing the 1240 condition. 1241 1242 --- edge e ---- > [second_head] 1243 1244 Split it and insert new conditional expression and adjust edges. 1245 1246 --- edge e ---> [cond expr] ---> [first_head] 1247 | 1248 +---------> [second_head] 1249 */ 1250 1251 static basic_block 1252 lv_adjust_loop_entry_edge (basic_block first_head, 1253 basic_block second_head, 1254 edge e, 1255 void *cond_expr) 1256 { 1257 basic_block new_head = NULL; 1258 edge e1; 1259 1260 gcc_assert (e->dest == second_head); 1261 1262 /* Split edge 'e'. This will create a new basic block, where we can 1263 insert conditional expr. */ 1264 new_head = split_edge (e); 1265 1266 1267 lv_add_condition_to_bb (first_head, second_head, new_head, 1268 cond_expr); 1269 1270 /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there. */ 1271 e1 = make_edge (new_head, first_head, ir_type () ? EDGE_TRUE_VALUE : 0); 1272 set_immediate_dominator (CDI_DOMINATORS, first_head, new_head); 1273 set_immediate_dominator (CDI_DOMINATORS, second_head, new_head); 1274 1275 /* Adjust loop header phi nodes. */ 1276 lv_adjust_loop_header_phi (first_head, second_head, new_head, e1); 1277 1278 return new_head; 1279 } 1280 1281 /* Main entry point for Loop Versioning transformation. 1282 1283 This transformation given a condition and a loop, creates 1284 -if (condition) { loop_copy1 } else { loop_copy2 }, 1285 where loop_copy1 is the loop transformed in one way, and loop_copy2 1286 is the loop transformed in another way (or unchanged). 'condition' 1287 may be a run time test for things that were not resolved by static 1288 analysis (overlapping ranges (anti-aliasing), alignment, etc.). 1289 1290 If PLACE_AFTER is true, we place the new loop after LOOP in the 1291 instruction stream, otherwise it is placed before LOOP. */ 1292 1293 struct loop * 1294 loop_version (struct loops *loops, struct loop * loop, 1295 void *cond_expr, basic_block *condition_bb, 1296 bool place_after) 1297 { 1298 basic_block first_head, second_head; 1299 edge entry, latch_edge, exit, true_edge, false_edge; 1300 int irred_flag; 1301 struct loop *nloop; 1302 basic_block cond_bb; 1303 1304 /* CHECKME: Loop versioning does not handle nested loop at this point. */ 1305 if (loop->inner) 1306 return NULL; 1307 1308 /* Record entry and latch edges for the loop */ 1309 entry = loop_preheader_edge (loop); 1310 irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP; 1311 entry->flags &= ~EDGE_IRREDUCIBLE_LOOP; 1312 1313 /* Note down head of loop as first_head. */ 1314 first_head = entry->dest; 1315 1316 /* Duplicate loop. */ 1317 if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, loops, 1, 1318 NULL, NULL, NULL, NULL, 0)) 1319 return NULL; 1320 1321 /* After duplication entry edge now points to new loop head block. 1322 Note down new head as second_head. */ 1323 second_head = entry->dest; 1324 1325 /* Split loop entry edge and insert new block with cond expr. */ 1326 cond_bb = lv_adjust_loop_entry_edge (first_head, second_head, 1327 entry, cond_expr); 1328 if (condition_bb) 1329 *condition_bb = cond_bb; 1330 1331 if (!cond_bb) 1332 { 1333 entry->flags |= irred_flag; 1334 return NULL; 1335 } 1336 1337 latch_edge = single_succ_edge (get_bb_copy (loop->latch)); 1338 1339 extract_cond_bb_edges (cond_bb, &true_edge, &false_edge); 1340 nloop = loopify (loops, 1341 latch_edge, 1342 single_pred_edge (get_bb_copy (loop->header)), 1343 cond_bb, true_edge, false_edge, 1344 false /* Do not redirect all edges. */); 1345 1346 exit = loop->single_exit; 1347 if (exit) 1348 nloop->single_exit = find_edge (get_bb_copy (exit->src), exit->dest); 1349 1350 /* loopify redirected latch_edge. Update its PENDING_STMTS. */ 1351 lv_flush_pending_stmts (latch_edge); 1352 1353 /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */ 1354 extract_cond_bb_edges (cond_bb, &true_edge, &false_edge); 1355 lv_flush_pending_stmts (false_edge); 1356 /* Adjust irreducible flag. */ 1357 if (irred_flag) 1358 { 1359 cond_bb->flags |= BB_IRREDUCIBLE_LOOP; 1360 loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP; 1361 loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP; 1362 single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP; 1363 } 1364 1365 if (place_after) 1366 { 1367 basic_block *bbs = get_loop_body_in_dom_order (nloop), after; 1368 unsigned i; 1369 1370 after = loop->latch; 1371 1372 for (i = 0; i < nloop->num_nodes; i++) 1373 { 1374 move_block_after (bbs[i], after); 1375 after = bbs[i]; 1376 } 1377 free (bbs); 1378 } 1379 1380 /* At this point condition_bb is loop predheader with two successors, 1381 first_head and second_head. Make sure that loop predheader has only 1382 one successor. */ 1383 loop_split_edge_with (loop_preheader_edge (loop), NULL); 1384 loop_split_edge_with (loop_preheader_edge (nloop), NULL); 1385 1386 return nloop; 1387 } 1388 1389 /* The structure of LOOPS might have changed. Some loops might get removed 1390 (and their headers and latches were set to NULL), loop exists might get 1391 removed (thus the loop nesting may be wrong), and some blocks and edges 1392 were changed (so the information about bb --> loop mapping does not have 1393 to be correct). But still for the remaining loops the header dominates 1394 the latch, and loops did not get new subloobs (new loops might possibly 1395 get created, but we are not interested in them). Fix up the mess. 1396 1397 If CHANGED_BBS is not NULL, basic blocks whose loop has changed are 1398 marked in it. */ 1399 1400 void 1401 fix_loop_structure (struct loops *loops, bitmap changed_bbs) 1402 { 1403 basic_block bb; 1404 struct loop *loop, *ploop; 1405 unsigned i; 1406 1407 /* Remove the old bb -> loop mapping. */ 1408 FOR_EACH_BB (bb) 1409 { 1410 bb->aux = (void *) (size_t) bb->loop_father->depth; 1411 bb->loop_father = loops->tree_root; 1412 } 1413 1414 /* Remove the dead loops from structures. */ 1415 loops->tree_root->num_nodes = n_basic_blocks; 1416 for (i = 1; i < loops->num; i++) 1417 { 1418 loop = loops->parray[i]; 1419 if (!loop) 1420 continue; 1421 1422 loop->num_nodes = 0; 1423 if (loop->header) 1424 continue; 1425 1426 while (loop->inner) 1427 { 1428 ploop = loop->inner; 1429 flow_loop_tree_node_remove (ploop); 1430 flow_loop_tree_node_add (loop->outer, ploop); 1431 } 1432 1433 /* Remove the loop and free its data. */ 1434 flow_loop_tree_node_remove (loop); 1435 loops->parray[loop->num] = NULL; 1436 flow_loop_free (loop); 1437 } 1438 1439 /* Rescan the bodies of loops, starting from the outermost. */ 1440 loop = loops->tree_root; 1441 while (1) 1442 { 1443 if (loop->inner) 1444 loop = loop->inner; 1445 else 1446 { 1447 while (!loop->next 1448 && loop != loops->tree_root) 1449 loop = loop->outer; 1450 if (loop == loops->tree_root) 1451 break; 1452 1453 loop = loop->next; 1454 } 1455 1456 loop->num_nodes = flow_loop_nodes_find (loop->header, loop); 1457 } 1458 1459 /* Now fix the loop nesting. */ 1460 for (i = 1; i < loops->num; i++) 1461 { 1462 loop = loops->parray[i]; 1463 if (!loop) 1464 continue; 1465 1466 bb = loop_preheader_edge (loop)->src; 1467 if (bb->loop_father != loop->outer) 1468 { 1469 flow_loop_tree_node_remove (loop); 1470 flow_loop_tree_node_add (bb->loop_father, loop); 1471 } 1472 } 1473 1474 /* Mark the blocks whose loop has changed. */ 1475 FOR_EACH_BB (bb) 1476 { 1477 if (changed_bbs 1478 && (void *) (size_t) bb->loop_father->depth != bb->aux) 1479 bitmap_set_bit (changed_bbs, bb->index); 1480 1481 bb->aux = NULL; 1482 } 1483 1484 if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) 1485 mark_single_exit_loops (loops); 1486 if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 1487 mark_irreducible_loops (loops); 1488 } 1489