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