1 /* Natural loop discovery code for GNU compiler. 2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2010 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 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 "function.h" 29 #include "basic-block.h" 30 #include "cfgloop.h" 31 #include "diagnostic-core.h" 32 #include "flags.h" 33 #include "tree.h" 34 #include "tree-flow.h" 35 #include "pointer-set.h" 36 #include "output.h" 37 #include "ggc.h" 38 39 static void flow_loops_cfg_dump (FILE *); 40 41 /* Dump loop related CFG information. */ 42 43 static void 44 flow_loops_cfg_dump (FILE *file) 45 { 46 basic_block bb; 47 48 if (!file) 49 return; 50 51 FOR_EACH_BB (bb) 52 { 53 edge succ; 54 edge_iterator ei; 55 56 fprintf (file, ";; %d succs { ", bb->index); 57 FOR_EACH_EDGE (succ, ei, bb->succs) 58 fprintf (file, "%d ", succ->dest->index); 59 fprintf (file, "}\n"); 60 } 61 } 62 63 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */ 64 65 bool 66 flow_loop_nested_p (const struct loop *outer, const struct loop *loop) 67 { 68 unsigned odepth = loop_depth (outer); 69 70 return (loop_depth (loop) > odepth 71 && VEC_index (loop_p, loop->superloops, odepth) == outer); 72 } 73 74 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero) 75 loops within LOOP. */ 76 77 struct loop * 78 superloop_at_depth (struct loop *loop, unsigned depth) 79 { 80 unsigned ldepth = loop_depth (loop); 81 82 gcc_assert (depth <= ldepth); 83 84 if (depth == ldepth) 85 return loop; 86 87 return VEC_index (loop_p, loop->superloops, depth); 88 } 89 90 /* Returns the list of the latch edges of LOOP. */ 91 92 static VEC (edge, heap) * 93 get_loop_latch_edges (const struct loop *loop) 94 { 95 edge_iterator ei; 96 edge e; 97 VEC (edge, heap) *ret = NULL; 98 99 FOR_EACH_EDGE (e, ei, loop->header->preds) 100 { 101 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header)) 102 VEC_safe_push (edge, heap, ret, e); 103 } 104 105 return ret; 106 } 107 108 /* Dump the loop information specified by LOOP to the stream FILE 109 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ 110 111 void 112 flow_loop_dump (const struct loop *loop, FILE *file, 113 void (*loop_dump_aux) (const struct loop *, FILE *, int), 114 int verbose) 115 { 116 basic_block *bbs; 117 unsigned i; 118 VEC (edge, heap) *latches; 119 edge e; 120 121 if (! loop || ! loop->header) 122 return; 123 124 fprintf (file, ";;\n;; Loop %d\n", loop->num); 125 126 fprintf (file, ";; header %d, ", loop->header->index); 127 if (loop->latch) 128 fprintf (file, "latch %d\n", loop->latch->index); 129 else 130 { 131 fprintf (file, "multiple latches:"); 132 latches = get_loop_latch_edges (loop); 133 FOR_EACH_VEC_ELT (edge, latches, i, e) 134 fprintf (file, " %d", e->src->index); 135 VEC_free (edge, heap, latches); 136 fprintf (file, "\n"); 137 } 138 139 fprintf (file, ";; depth %d, outer %ld\n", 140 loop_depth (loop), (long) (loop_outer (loop) 141 ? loop_outer (loop)->num : -1)); 142 143 fprintf (file, ";; nodes:"); 144 bbs = get_loop_body (loop); 145 for (i = 0; i < loop->num_nodes; i++) 146 fprintf (file, " %d", bbs[i]->index); 147 free (bbs); 148 fprintf (file, "\n"); 149 150 if (loop_dump_aux) 151 loop_dump_aux (loop, file, verbose); 152 } 153 154 /* Dump the loop information about loops to the stream FILE, 155 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ 156 157 void 158 flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) 159 { 160 loop_iterator li; 161 struct loop *loop; 162 163 if (!current_loops || ! file) 164 return; 165 166 fprintf (file, ";; %d loops found\n", number_of_loops ()); 167 168 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT) 169 { 170 flow_loop_dump (loop, file, loop_dump_aux, verbose); 171 } 172 173 if (verbose) 174 flow_loops_cfg_dump (file); 175 } 176 177 /* Free data allocated for LOOP. */ 178 179 void 180 flow_loop_free (struct loop *loop) 181 { 182 struct loop_exit *exit, *next; 183 184 VEC_free (loop_p, gc, loop->superloops); 185 186 /* Break the list of the loop exit records. They will be freed when the 187 corresponding edge is rescanned or removed, and this avoids 188 accessing the (already released) head of the list stored in the 189 loop structure. */ 190 for (exit = loop->exits->next; exit != loop->exits; exit = next) 191 { 192 next = exit->next; 193 exit->next = exit; 194 exit->prev = exit; 195 } 196 197 ggc_free (loop->exits); 198 ggc_free (loop); 199 } 200 201 /* Free all the memory allocated for LOOPS. */ 202 203 void 204 flow_loops_free (struct loops *loops) 205 { 206 if (loops->larray) 207 { 208 unsigned i; 209 loop_p loop; 210 211 /* Free the loop descriptors. */ 212 FOR_EACH_VEC_ELT (loop_p, loops->larray, i, loop) 213 { 214 if (!loop) 215 continue; 216 217 flow_loop_free (loop); 218 } 219 220 VEC_free (loop_p, gc, loops->larray); 221 } 222 } 223 224 /* Find the nodes contained within the LOOP with header HEADER. 225 Return the number of nodes within the loop. */ 226 227 int 228 flow_loop_nodes_find (basic_block header, struct loop *loop) 229 { 230 VEC (basic_block, heap) *stack = NULL; 231 int num_nodes = 1; 232 edge latch; 233 edge_iterator latch_ei; 234 unsigned depth = loop_depth (loop); 235 236 header->loop_father = loop; 237 header->loop_depth = depth; 238 239 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds) 240 { 241 if (latch->src->loop_father == loop 242 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header)) 243 continue; 244 245 num_nodes++; 246 VEC_safe_push (basic_block, heap, stack, latch->src); 247 latch->src->loop_father = loop; 248 latch->src->loop_depth = depth; 249 250 while (!VEC_empty (basic_block, stack)) 251 { 252 basic_block node; 253 edge e; 254 edge_iterator ei; 255 256 node = VEC_pop (basic_block, stack); 257 258 FOR_EACH_EDGE (e, ei, node->preds) 259 { 260 basic_block ancestor = e->src; 261 262 if (ancestor->loop_father != loop) 263 { 264 ancestor->loop_father = loop; 265 ancestor->loop_depth = depth; 266 num_nodes++; 267 VEC_safe_push (basic_block, heap, stack, ancestor); 268 } 269 } 270 } 271 } 272 VEC_free (basic_block, heap, stack); 273 274 return num_nodes; 275 } 276 277 /* Records the vector of superloops of the loop LOOP, whose immediate 278 superloop is FATHER. */ 279 280 static void 281 establish_preds (struct loop *loop, struct loop *father) 282 { 283 loop_p ploop; 284 unsigned depth = loop_depth (father) + 1; 285 unsigned i; 286 287 VEC_truncate (loop_p, loop->superloops, 0); 288 VEC_reserve (loop_p, gc, loop->superloops, depth); 289 FOR_EACH_VEC_ELT (loop_p, father->superloops, i, ploop) 290 VEC_quick_push (loop_p, loop->superloops, ploop); 291 VEC_quick_push (loop_p, loop->superloops, father); 292 293 for (ploop = loop->inner; ploop; ploop = ploop->next) 294 establish_preds (ploop, loop); 295 } 296 297 /* Add LOOP to the loop hierarchy tree where FATHER is father of the 298 added loop. If LOOP has some children, take care of that their 299 pred field will be initialized correctly. */ 300 301 void 302 flow_loop_tree_node_add (struct loop *father, struct loop *loop) 303 { 304 loop->next = father->inner; 305 father->inner = loop; 306 307 establish_preds (loop, father); 308 } 309 310 /* Remove LOOP from the loop hierarchy tree. */ 311 312 void 313 flow_loop_tree_node_remove (struct loop *loop) 314 { 315 struct loop *prev, *father; 316 317 father = loop_outer (loop); 318 319 /* Remove loop from the list of sons. */ 320 if (father->inner == loop) 321 father->inner = loop->next; 322 else 323 { 324 for (prev = father->inner; prev->next != loop; prev = prev->next) 325 continue; 326 prev->next = loop->next; 327 } 328 329 VEC_truncate (loop_p, loop->superloops, 0); 330 } 331 332 /* Allocates and returns new loop structure. */ 333 334 struct loop * 335 alloc_loop (void) 336 { 337 struct loop *loop = ggc_alloc_cleared_loop (); 338 339 loop->exits = ggc_alloc_cleared_loop_exit (); 340 loop->exits->next = loop->exits->prev = loop->exits; 341 loop->can_be_parallel = false; 342 343 return loop; 344 } 345 346 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops 347 (including the root of the loop tree). */ 348 349 static void 350 init_loops_structure (struct loops *loops, unsigned num_loops) 351 { 352 struct loop *root; 353 354 memset (loops, 0, sizeof *loops); 355 loops->larray = VEC_alloc (loop_p, gc, num_loops); 356 357 /* Dummy loop containing whole function. */ 358 root = alloc_loop (); 359 root->num_nodes = n_basic_blocks; 360 root->latch = EXIT_BLOCK_PTR; 361 root->header = ENTRY_BLOCK_PTR; 362 ENTRY_BLOCK_PTR->loop_father = root; 363 EXIT_BLOCK_PTR->loop_father = root; 364 365 VEC_quick_push (loop_p, loops->larray, root); 366 loops->tree_root = root; 367 } 368 369 /* Find all the natural loops in the function and save in LOOPS structure and 370 recalculate loop_depth information in basic block structures. 371 Return the number of natural loops found. */ 372 373 int 374 flow_loops_find (struct loops *loops) 375 { 376 int b; 377 int num_loops; 378 edge e; 379 sbitmap headers; 380 int *dfs_order; 381 int *rc_order; 382 basic_block header; 383 basic_block bb; 384 385 /* Ensure that the dominators are computed. */ 386 calculate_dominance_info (CDI_DOMINATORS); 387 388 /* Taking care of this degenerate case makes the rest of 389 this code simpler. */ 390 if (n_basic_blocks == NUM_FIXED_BLOCKS) 391 { 392 init_loops_structure (loops, 1); 393 return 1; 394 } 395 396 dfs_order = NULL; 397 rc_order = NULL; 398 399 /* Count the number of loop headers. This should be the 400 same as the number of natural loops. */ 401 headers = sbitmap_alloc (last_basic_block); 402 sbitmap_zero (headers); 403 404 num_loops = 0; 405 FOR_EACH_BB (header) 406 { 407 edge_iterator ei; 408 409 header->loop_depth = 0; 410 411 /* If we have an abnormal predecessor, do not consider the 412 loop (not worth the problems). */ 413 if (bb_has_abnormal_pred (header)) 414 continue; 415 416 FOR_EACH_EDGE (e, ei, header->preds) 417 { 418 basic_block latch = e->src; 419 420 gcc_assert (!(e->flags & EDGE_ABNORMAL)); 421 422 /* Look for back edges where a predecessor is dominated 423 by this block. A natural loop has a single entry 424 node (header) that dominates all the nodes in the 425 loop. It also has single back edge to the header 426 from a latch node. */ 427 if (latch != ENTRY_BLOCK_PTR 428 && dominated_by_p (CDI_DOMINATORS, latch, header)) 429 { 430 /* Shared headers should be eliminated by now. */ 431 SET_BIT (headers, header->index); 432 num_loops++; 433 } 434 } 435 } 436 437 /* Allocate loop structures. */ 438 init_loops_structure (loops, num_loops + 1); 439 440 /* Find and record information about all the natural loops 441 in the CFG. */ 442 FOR_EACH_BB (bb) 443 bb->loop_father = loops->tree_root; 444 445 if (num_loops) 446 { 447 /* Compute depth first search order of the CFG so that outer 448 natural loops will be found before inner natural loops. */ 449 dfs_order = XNEWVEC (int, n_basic_blocks); 450 rc_order = XNEWVEC (int, n_basic_blocks); 451 pre_and_rev_post_order_compute (dfs_order, rc_order, false); 452 453 num_loops = 1; 454 455 for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++) 456 { 457 struct loop *loop; 458 edge_iterator ei; 459 460 /* Search the nodes of the CFG in reverse completion order 461 so that we can find outer loops first. */ 462 if (!TEST_BIT (headers, rc_order[b])) 463 continue; 464 465 header = BASIC_BLOCK (rc_order[b]); 466 467 loop = alloc_loop (); 468 VEC_quick_push (loop_p, loops->larray, loop); 469 470 loop->header = header; 471 loop->num = num_loops; 472 num_loops++; 473 474 flow_loop_tree_node_add (header->loop_father, loop); 475 loop->num_nodes = flow_loop_nodes_find (loop->header, loop); 476 477 /* Look for the latch for this header block, if it has just a 478 single one. */ 479 FOR_EACH_EDGE (e, ei, header->preds) 480 { 481 basic_block latch = e->src; 482 483 if (flow_bb_inside_loop_p (loop, latch)) 484 { 485 if (loop->latch != NULL) 486 { 487 /* More than one latch edge. */ 488 loop->latch = NULL; 489 break; 490 } 491 loop->latch = latch; 492 } 493 } 494 } 495 496 free (dfs_order); 497 free (rc_order); 498 } 499 500 sbitmap_free (headers); 501 502 loops->exits = NULL; 503 return VEC_length (loop_p, loops->larray); 504 } 505 506 /* Ratio of frequencies of edges so that one of more latch edges is 507 considered to belong to inner loop with same header. */ 508 #define HEAVY_EDGE_RATIO 8 509 510 /* Minimum number of samples for that we apply 511 find_subloop_latch_edge_by_profile heuristics. */ 512 #define HEAVY_EDGE_MIN_SAMPLES 10 513 514 /* If the profile info is available, finds an edge in LATCHES that much more 515 frequent than the remaining edges. Returns such an edge, or NULL if we do 516 not find one. 517 518 We do not use guessed profile here, only the measured one. The guessed 519 profile is usually too flat and unreliable for this (and it is mostly based 520 on the loop structure of the program, so it does not make much sense to 521 derive the loop structure from it). */ 522 523 static edge 524 find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches) 525 { 526 unsigned i; 527 edge e, me = NULL; 528 gcov_type mcount = 0, tcount = 0; 529 530 FOR_EACH_VEC_ELT (edge, latches, i, e) 531 { 532 if (e->count > mcount) 533 { 534 me = e; 535 mcount = e->count; 536 } 537 tcount += e->count; 538 } 539 540 if (tcount < HEAVY_EDGE_MIN_SAMPLES 541 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount) 542 return NULL; 543 544 if (dump_file) 545 fprintf (dump_file, 546 "Found latch edge %d -> %d using profile information.\n", 547 me->src->index, me->dest->index); 548 return me; 549 } 550 551 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based 552 on the structure of induction variables. Returns this edge, or NULL if we 553 do not find any. 554 555 We are quite conservative, and look just for an obvious simple innermost 556 loop (which is the case where we would lose the most performance by not 557 disambiguating the loop). More precisely, we look for the following 558 situation: The source of the chosen latch edge dominates sources of all 559 the other latch edges. Additionally, the header does not contain a phi node 560 such that the argument from the chosen edge is equal to the argument from 561 another edge. */ 562 563 static edge 564 find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, VEC (edge, heap) *latches) 565 { 566 edge e, latch = VEC_index (edge, latches, 0); 567 unsigned i; 568 gimple phi; 569 gimple_stmt_iterator psi; 570 tree lop; 571 basic_block bb; 572 573 /* Find the candidate for the latch edge. */ 574 for (i = 1; VEC_iterate (edge, latches, i, e); i++) 575 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src)) 576 latch = e; 577 578 /* Verify that it dominates all the latch edges. */ 579 FOR_EACH_VEC_ELT (edge, latches, i, e) 580 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src)) 581 return NULL; 582 583 /* Check for a phi node that would deny that this is a latch edge of 584 a subloop. */ 585 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) 586 { 587 phi = gsi_stmt (psi); 588 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch); 589 590 /* Ignore the values that are not changed inside the subloop. */ 591 if (TREE_CODE (lop) != SSA_NAME 592 || SSA_NAME_DEF_STMT (lop) == phi) 593 continue; 594 bb = gimple_bb (SSA_NAME_DEF_STMT (lop)); 595 if (!bb || !flow_bb_inside_loop_p (loop, bb)) 596 continue; 597 598 FOR_EACH_VEC_ELT (edge, latches, i, e) 599 if (e != latch 600 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop) 601 return NULL; 602 } 603 604 if (dump_file) 605 fprintf (dump_file, 606 "Found latch edge %d -> %d using iv structure.\n", 607 latch->src->index, latch->dest->index); 608 return latch; 609 } 610 611 /* If we can determine that one of the several latch edges of LOOP behaves 612 as a latch edge of a separate subloop, returns this edge. Otherwise 613 returns NULL. */ 614 615 static edge 616 find_subloop_latch_edge (struct loop *loop) 617 { 618 VEC (edge, heap) *latches = get_loop_latch_edges (loop); 619 edge latch = NULL; 620 621 if (VEC_length (edge, latches) > 1) 622 { 623 latch = find_subloop_latch_edge_by_profile (latches); 624 625 if (!latch 626 /* We consider ivs to guess the latch edge only in SSA. Perhaps we 627 should use cfghook for this, but it is hard to imagine it would 628 be useful elsewhere. */ 629 && current_ir_type () == IR_GIMPLE) 630 latch = find_subloop_latch_edge_by_ivs (loop, latches); 631 } 632 633 VEC_free (edge, heap, latches); 634 return latch; 635 } 636 637 /* Callback for make_forwarder_block. Returns true if the edge E is marked 638 in the set MFB_REIS_SET. */ 639 640 static struct pointer_set_t *mfb_reis_set; 641 static bool 642 mfb_redirect_edges_in_set (edge e) 643 { 644 return pointer_set_contains (mfb_reis_set, e); 645 } 646 647 /* Creates a subloop of LOOP with latch edge LATCH. */ 648 649 static void 650 form_subloop (struct loop *loop, edge latch) 651 { 652 edge_iterator ei; 653 edge e, new_entry; 654 struct loop *new_loop; 655 656 mfb_reis_set = pointer_set_create (); 657 FOR_EACH_EDGE (e, ei, loop->header->preds) 658 { 659 if (e != latch) 660 pointer_set_insert (mfb_reis_set, e); 661 } 662 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, 663 NULL); 664 pointer_set_destroy (mfb_reis_set); 665 666 loop->header = new_entry->src; 667 668 /* Find the blocks and subloops that belong to the new loop, and add it to 669 the appropriate place in the loop tree. */ 670 new_loop = alloc_loop (); 671 new_loop->header = new_entry->dest; 672 new_loop->latch = latch->src; 673 add_loop (new_loop, loop); 674 } 675 676 /* Make all the latch edges of LOOP to go to a single forwarder block -- 677 a new latch of LOOP. */ 678 679 static void 680 merge_latch_edges (struct loop *loop) 681 { 682 VEC (edge, heap) *latches = get_loop_latch_edges (loop); 683 edge latch, e; 684 unsigned i; 685 686 gcc_assert (VEC_length (edge, latches) > 0); 687 688 if (VEC_length (edge, latches) == 1) 689 loop->latch = VEC_index (edge, latches, 0)->src; 690 else 691 { 692 if (dump_file) 693 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num); 694 695 mfb_reis_set = pointer_set_create (); 696 FOR_EACH_VEC_ELT (edge, latches, i, e) 697 pointer_set_insert (mfb_reis_set, e); 698 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, 699 NULL); 700 pointer_set_destroy (mfb_reis_set); 701 702 loop->header = latch->dest; 703 loop->latch = latch->src; 704 } 705 706 VEC_free (edge, heap, latches); 707 } 708 709 /* LOOP may have several latch edges. Transform it into (possibly several) 710 loops with single latch edge. */ 711 712 static void 713 disambiguate_multiple_latches (struct loop *loop) 714 { 715 edge e; 716 717 /* We eliminate the multiple latches by splitting the header to the forwarder 718 block F and the rest R, and redirecting the edges. There are two cases: 719 720 1) If there is a latch edge E that corresponds to a subloop (we guess 721 that based on profile -- if it is taken much more often than the 722 remaining edges; and on trees, using the information about induction 723 variables of the loops), we redirect E to R, all the remaining edges to 724 F, then rescan the loops and try again for the outer loop. 725 2) If there is no such edge, we redirect all latch edges to F, and the 726 entry edges to R, thus making F the single latch of the loop. */ 727 728 if (dump_file) 729 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n", 730 loop->num); 731 732 /* During latch merging, we may need to redirect the entry edges to a new 733 block. This would cause problems if the entry edge was the one from the 734 entry block. To avoid having to handle this case specially, split 735 such entry edge. */ 736 e = find_edge (ENTRY_BLOCK_PTR, loop->header); 737 if (e) 738 split_edge (e); 739 740 while (1) 741 { 742 e = find_subloop_latch_edge (loop); 743 if (!e) 744 break; 745 746 form_subloop (loop, e); 747 } 748 749 merge_latch_edges (loop); 750 } 751 752 /* Split loops with multiple latch edges. */ 753 754 void 755 disambiguate_loops_with_multiple_latches (void) 756 { 757 loop_iterator li; 758 struct loop *loop; 759 760 FOR_EACH_LOOP (li, loop, 0) 761 { 762 if (!loop->latch) 763 disambiguate_multiple_latches (loop); 764 } 765 } 766 767 /* Return nonzero if basic block BB belongs to LOOP. */ 768 bool 769 flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb) 770 { 771 struct loop *source_loop; 772 773 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) 774 return 0; 775 776 source_loop = bb->loop_father; 777 return loop == source_loop || flow_loop_nested_p (loop, source_loop); 778 } 779 780 /* Enumeration predicate for get_loop_body_with_size. */ 781 static bool 782 glb_enum_p (const_basic_block bb, const void *glb_loop) 783 { 784 const struct loop *const loop = (const struct loop *) glb_loop; 785 return (bb != loop->header 786 && dominated_by_p (CDI_DOMINATORS, bb, loop->header)); 787 } 788 789 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs 790 order against direction of edges from latch. Specially, if 791 header != latch, latch is the 1-st block. LOOP cannot be the fake 792 loop tree root, and its size must be at most MAX_SIZE. The blocks 793 in the LOOP body are stored to BODY, and the size of the LOOP is 794 returned. */ 795 796 unsigned 797 get_loop_body_with_size (const struct loop *loop, basic_block *body, 798 unsigned max_size) 799 { 800 return dfs_enumerate_from (loop->header, 1, glb_enum_p, 801 body, max_size, loop); 802 } 803 804 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs 805 order against direction of edges from latch. Specially, if 806 header != latch, latch is the 1-st block. */ 807 808 basic_block * 809 get_loop_body (const struct loop *loop) 810 { 811 basic_block *body, bb; 812 unsigned tv = 0; 813 814 gcc_assert (loop->num_nodes); 815 816 body = XCNEWVEC (basic_block, loop->num_nodes); 817 818 if (loop->latch == EXIT_BLOCK_PTR) 819 { 820 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to 821 special-case the fake loop that contains the whole function. */ 822 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks); 823 body[tv++] = loop->header; 824 body[tv++] = EXIT_BLOCK_PTR; 825 FOR_EACH_BB (bb) 826 body[tv++] = bb; 827 } 828 else 829 tv = get_loop_body_with_size (loop, body, loop->num_nodes); 830 831 gcc_assert (tv == loop->num_nodes); 832 return body; 833 } 834 835 /* Fills dominance descendants inside LOOP of the basic block BB into 836 array TOVISIT from index *TV. */ 837 838 static void 839 fill_sons_in_loop (const struct loop *loop, basic_block bb, 840 basic_block *tovisit, int *tv) 841 { 842 basic_block son, postpone = NULL; 843 844 tovisit[(*tv)++] = bb; 845 for (son = first_dom_son (CDI_DOMINATORS, bb); 846 son; 847 son = next_dom_son (CDI_DOMINATORS, son)) 848 { 849 if (!flow_bb_inside_loop_p (loop, son)) 850 continue; 851 852 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son)) 853 { 854 postpone = son; 855 continue; 856 } 857 fill_sons_in_loop (loop, son, tovisit, tv); 858 } 859 860 if (postpone) 861 fill_sons_in_loop (loop, postpone, tovisit, tv); 862 } 863 864 /* Gets body of a LOOP (that must be different from the outermost loop) 865 sorted by dominance relation. Additionally, if a basic block s dominates 866 the latch, then only blocks dominated by s are be after it. */ 867 868 basic_block * 869 get_loop_body_in_dom_order (const struct loop *loop) 870 { 871 basic_block *tovisit; 872 int tv; 873 874 gcc_assert (loop->num_nodes); 875 876 tovisit = XCNEWVEC (basic_block, loop->num_nodes); 877 878 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 879 880 tv = 0; 881 fill_sons_in_loop (loop, loop->header, tovisit, &tv); 882 883 gcc_assert (tv == (int) loop->num_nodes); 884 885 return tovisit; 886 } 887 888 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */ 889 890 basic_block * 891 get_loop_body_in_custom_order (const struct loop *loop, 892 int (*bb_comparator) (const void *, const void *)) 893 { 894 basic_block *bbs = get_loop_body (loop); 895 896 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator); 897 898 return bbs; 899 } 900 901 /* Get body of a LOOP in breadth first sort order. */ 902 903 basic_block * 904 get_loop_body_in_bfs_order (const struct loop *loop) 905 { 906 basic_block *blocks; 907 basic_block bb; 908 bitmap visited; 909 unsigned int i = 0; 910 unsigned int vc = 1; 911 912 gcc_assert (loop->num_nodes); 913 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 914 915 blocks = XCNEWVEC (basic_block, loop->num_nodes); 916 visited = BITMAP_ALLOC (NULL); 917 918 bb = loop->header; 919 while (i < loop->num_nodes) 920 { 921 edge e; 922 edge_iterator ei; 923 924 if (bitmap_set_bit (visited, bb->index)) 925 /* This basic block is now visited */ 926 blocks[i++] = bb; 927 928 FOR_EACH_EDGE (e, ei, bb->succs) 929 { 930 if (flow_bb_inside_loop_p (loop, e->dest)) 931 { 932 if (bitmap_set_bit (visited, e->dest->index)) 933 blocks[i++] = e->dest; 934 } 935 } 936 937 gcc_assert (i >= vc); 938 939 bb = blocks[vc++]; 940 } 941 942 BITMAP_FREE (visited); 943 return blocks; 944 } 945 946 /* Hash function for struct loop_exit. */ 947 948 static hashval_t 949 loop_exit_hash (const void *ex) 950 { 951 const struct loop_exit *const exit = (const struct loop_exit *) ex; 952 953 return htab_hash_pointer (exit->e); 954 } 955 956 /* Equality function for struct loop_exit. Compares with edge. */ 957 958 static int 959 loop_exit_eq (const void *ex, const void *e) 960 { 961 const struct loop_exit *const exit = (const struct loop_exit *) ex; 962 963 return exit->e == e; 964 } 965 966 /* Frees the list of loop exit descriptions EX. */ 967 968 static void 969 loop_exit_free (void *ex) 970 { 971 struct loop_exit *exit = (struct loop_exit *) ex, *next; 972 973 for (; exit; exit = next) 974 { 975 next = exit->next_e; 976 977 exit->next->prev = exit->prev; 978 exit->prev->next = exit->next; 979 980 ggc_free (exit); 981 } 982 } 983 984 /* Returns the list of records for E as an exit of a loop. */ 985 986 static struct loop_exit * 987 get_exit_descriptions (edge e) 988 { 989 return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e, 990 htab_hash_pointer (e)); 991 } 992 993 /* Updates the lists of loop exits in that E appears. 994 If REMOVED is true, E is being removed, and we 995 just remove it from the lists of exits. 996 If NEW_EDGE is true and E is not a loop exit, we 997 do not try to remove it from loop exit lists. */ 998 999 void 1000 rescan_loop_exit (edge e, bool new_edge, bool removed) 1001 { 1002 void **slot; 1003 struct loop_exit *exits = NULL, *exit; 1004 struct loop *aloop, *cloop; 1005 1006 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1007 return; 1008 1009 if (!removed 1010 && e->src->loop_father != NULL 1011 && e->dest->loop_father != NULL 1012 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest)) 1013 { 1014 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father); 1015 for (aloop = e->src->loop_father; 1016 aloop != cloop; 1017 aloop = loop_outer (aloop)) 1018 { 1019 exit = ggc_alloc_loop_exit (); 1020 exit->e = e; 1021 1022 exit->next = aloop->exits->next; 1023 exit->prev = aloop->exits; 1024 exit->next->prev = exit; 1025 exit->prev->next = exit; 1026 1027 exit->next_e = exits; 1028 exits = exit; 1029 } 1030 } 1031 1032 if (!exits && new_edge) 1033 return; 1034 1035 slot = htab_find_slot_with_hash (current_loops->exits, e, 1036 htab_hash_pointer (e), 1037 exits ? INSERT : NO_INSERT); 1038 if (!slot) 1039 return; 1040 1041 if (exits) 1042 { 1043 if (*slot) 1044 loop_exit_free (*slot); 1045 *slot = exits; 1046 } 1047 else 1048 htab_clear_slot (current_loops->exits, slot); 1049 } 1050 1051 /* For each loop, record list of exit edges, and start maintaining these 1052 lists. */ 1053 1054 void 1055 record_loop_exits (void) 1056 { 1057 basic_block bb; 1058 edge_iterator ei; 1059 edge e; 1060 1061 if (!current_loops) 1062 return; 1063 1064 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1065 return; 1066 loops_state_set (LOOPS_HAVE_RECORDED_EXITS); 1067 1068 gcc_assert (current_loops->exits == NULL); 1069 current_loops->exits = htab_create_ggc (2 * number_of_loops (), 1070 loop_exit_hash, loop_exit_eq, 1071 loop_exit_free); 1072 1073 FOR_EACH_BB (bb) 1074 { 1075 FOR_EACH_EDGE (e, ei, bb->succs) 1076 { 1077 rescan_loop_exit (e, true, false); 1078 } 1079 } 1080 } 1081 1082 /* Dumps information about the exit in *SLOT to FILE. 1083 Callback for htab_traverse. */ 1084 1085 static int 1086 dump_recorded_exit (void **slot, void *file) 1087 { 1088 struct loop_exit *exit = (struct loop_exit *) *slot; 1089 unsigned n = 0; 1090 edge e = exit->e; 1091 1092 for (; exit != NULL; exit = exit->next_e) 1093 n++; 1094 1095 fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n", 1096 e->src->index, e->dest->index, n); 1097 1098 return 1; 1099 } 1100 1101 /* Dumps the recorded exits of loops to FILE. */ 1102 1103 extern void dump_recorded_exits (FILE *); 1104 void 1105 dump_recorded_exits (FILE *file) 1106 { 1107 if (!current_loops->exits) 1108 return; 1109 htab_traverse (current_loops->exits, dump_recorded_exit, file); 1110 } 1111 1112 /* Releases lists of loop exits. */ 1113 1114 void 1115 release_recorded_exits (void) 1116 { 1117 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)); 1118 htab_delete (current_loops->exits); 1119 current_loops->exits = NULL; 1120 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS); 1121 } 1122 1123 /* Returns the list of the exit edges of a LOOP. */ 1124 1125 VEC (edge, heap) * 1126 get_loop_exit_edges (const struct loop *loop) 1127 { 1128 VEC (edge, heap) *edges = NULL; 1129 edge e; 1130 unsigned i; 1131 basic_block *body; 1132 edge_iterator ei; 1133 struct loop_exit *exit; 1134 1135 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 1136 1137 /* If we maintain the lists of exits, use them. Otherwise we must 1138 scan the body of the loop. */ 1139 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1140 { 1141 for (exit = loop->exits->next; exit->e; exit = exit->next) 1142 VEC_safe_push (edge, heap, edges, exit->e); 1143 } 1144 else 1145 { 1146 body = get_loop_body (loop); 1147 for (i = 0; i < loop->num_nodes; i++) 1148 FOR_EACH_EDGE (e, ei, body[i]->succs) 1149 { 1150 if (!flow_bb_inside_loop_p (loop, e->dest)) 1151 VEC_safe_push (edge, heap, edges, e); 1152 } 1153 free (body); 1154 } 1155 1156 return edges; 1157 } 1158 1159 /* Counts the number of conditional branches inside LOOP. */ 1160 1161 unsigned 1162 num_loop_branches (const struct loop *loop) 1163 { 1164 unsigned i, n; 1165 basic_block * body; 1166 1167 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 1168 1169 body = get_loop_body (loop); 1170 n = 0; 1171 for (i = 0; i < loop->num_nodes; i++) 1172 if (EDGE_COUNT (body[i]->succs) >= 2) 1173 n++; 1174 free (body); 1175 1176 return n; 1177 } 1178 1179 /* Adds basic block BB to LOOP. */ 1180 void 1181 add_bb_to_loop (basic_block bb, struct loop *loop) 1182 { 1183 unsigned i; 1184 loop_p ploop; 1185 edge_iterator ei; 1186 edge e; 1187 1188 gcc_assert (bb->loop_father == NULL); 1189 bb->loop_father = loop; 1190 bb->loop_depth = loop_depth (loop); 1191 loop->num_nodes++; 1192 FOR_EACH_VEC_ELT (loop_p, loop->superloops, i, ploop) 1193 ploop->num_nodes++; 1194 1195 FOR_EACH_EDGE (e, ei, bb->succs) 1196 { 1197 rescan_loop_exit (e, true, false); 1198 } 1199 FOR_EACH_EDGE (e, ei, bb->preds) 1200 { 1201 rescan_loop_exit (e, true, false); 1202 } 1203 } 1204 1205 /* Remove basic block BB from loops. */ 1206 void 1207 remove_bb_from_loops (basic_block bb) 1208 { 1209 int i; 1210 struct loop *loop = bb->loop_father; 1211 loop_p ploop; 1212 edge_iterator ei; 1213 edge e; 1214 1215 gcc_assert (loop != NULL); 1216 loop->num_nodes--; 1217 FOR_EACH_VEC_ELT (loop_p, loop->superloops, i, ploop) 1218 ploop->num_nodes--; 1219 bb->loop_father = NULL; 1220 bb->loop_depth = 0; 1221 1222 FOR_EACH_EDGE (e, ei, bb->succs) 1223 { 1224 rescan_loop_exit (e, false, true); 1225 } 1226 FOR_EACH_EDGE (e, ei, bb->preds) 1227 { 1228 rescan_loop_exit (e, false, true); 1229 } 1230 } 1231 1232 /* Finds nearest common ancestor in loop tree for given loops. */ 1233 struct loop * 1234 find_common_loop (struct loop *loop_s, struct loop *loop_d) 1235 { 1236 unsigned sdepth, ddepth; 1237 1238 if (!loop_s) return loop_d; 1239 if (!loop_d) return loop_s; 1240 1241 sdepth = loop_depth (loop_s); 1242 ddepth = loop_depth (loop_d); 1243 1244 if (sdepth < ddepth) 1245 loop_d = VEC_index (loop_p, loop_d->superloops, sdepth); 1246 else if (sdepth > ddepth) 1247 loop_s = VEC_index (loop_p, loop_s->superloops, ddepth); 1248 1249 while (loop_s != loop_d) 1250 { 1251 loop_s = loop_outer (loop_s); 1252 loop_d = loop_outer (loop_d); 1253 } 1254 return loop_s; 1255 } 1256 1257 /* Removes LOOP from structures and frees its data. */ 1258 1259 void 1260 delete_loop (struct loop *loop) 1261 { 1262 /* Remove the loop from structure. */ 1263 flow_loop_tree_node_remove (loop); 1264 1265 /* Remove loop from loops array. */ 1266 VEC_replace (loop_p, current_loops->larray, loop->num, NULL); 1267 1268 /* Free loop data. */ 1269 flow_loop_free (loop); 1270 } 1271 1272 /* Cancels the LOOP; it must be innermost one. */ 1273 1274 static void 1275 cancel_loop (struct loop *loop) 1276 { 1277 basic_block *bbs; 1278 unsigned i; 1279 struct loop *outer = loop_outer (loop); 1280 1281 gcc_assert (!loop->inner); 1282 1283 /* Move blocks up one level (they should be removed as soon as possible). */ 1284 bbs = get_loop_body (loop); 1285 for (i = 0; i < loop->num_nodes; i++) 1286 bbs[i]->loop_father = outer; 1287 1288 free (bbs); 1289 delete_loop (loop); 1290 } 1291 1292 /* Cancels LOOP and all its subloops. */ 1293 void 1294 cancel_loop_tree (struct loop *loop) 1295 { 1296 while (loop->inner) 1297 cancel_loop_tree (loop->inner); 1298 cancel_loop (loop); 1299 } 1300 1301 /* Checks that information about loops is correct 1302 -- sizes of loops are all right 1303 -- results of get_loop_body really belong to the loop 1304 -- loop header have just single entry edge and single latch edge 1305 -- loop latches have only single successor that is header of their loop 1306 -- irreducible loops are correctly marked 1307 */ 1308 DEBUG_FUNCTION void 1309 verify_loop_structure (void) 1310 { 1311 unsigned *sizes, i, j; 1312 sbitmap irreds; 1313 basic_block *bbs, bb; 1314 struct loop *loop; 1315 int err = 0; 1316 edge e; 1317 unsigned num = number_of_loops (); 1318 loop_iterator li; 1319 struct loop_exit *exit, *mexit; 1320 1321 /* Check sizes. */ 1322 sizes = XCNEWVEC (unsigned, num); 1323 sizes[0] = 2; 1324 1325 FOR_EACH_BB (bb) 1326 for (loop = bb->loop_father; loop; loop = loop_outer (loop)) 1327 sizes[loop->num]++; 1328 1329 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT) 1330 { 1331 i = loop->num; 1332 1333 if (loop->num_nodes != sizes[i]) 1334 { 1335 error ("size of loop %d should be %d, not %d", 1336 i, sizes[i], loop->num_nodes); 1337 err = 1; 1338 } 1339 } 1340 1341 /* Check get_loop_body. */ 1342 FOR_EACH_LOOP (li, loop, 0) 1343 { 1344 bbs = get_loop_body (loop); 1345 1346 for (j = 0; j < loop->num_nodes; j++) 1347 if (!flow_bb_inside_loop_p (loop, bbs[j])) 1348 { 1349 error ("bb %d do not belong to loop %d", 1350 bbs[j]->index, loop->num); 1351 err = 1; 1352 } 1353 free (bbs); 1354 } 1355 1356 /* Check headers and latches. */ 1357 FOR_EACH_LOOP (li, loop, 0) 1358 { 1359 i = loop->num; 1360 1361 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS) 1362 && EDGE_COUNT (loop->header->preds) != 2) 1363 { 1364 error ("loop %d%'s header does not have exactly 2 entries", i); 1365 err = 1; 1366 } 1367 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES)) 1368 { 1369 if (!single_succ_p (loop->latch)) 1370 { 1371 error ("loop %d%'s latch does not have exactly 1 successor", i); 1372 err = 1; 1373 } 1374 if (single_succ (loop->latch) != loop->header) 1375 { 1376 error ("loop %d%'s latch does not have header as successor", i); 1377 err = 1; 1378 } 1379 if (loop->latch->loop_father != loop) 1380 { 1381 error ("loop %d%'s latch does not belong directly to it", i); 1382 err = 1; 1383 } 1384 } 1385 if (loop->header->loop_father != loop) 1386 { 1387 error ("loop %d%'s header does not belong directly to it", i); 1388 err = 1; 1389 } 1390 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 1391 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) 1392 { 1393 error ("loop %d%'s latch is marked as part of irreducible region", i); 1394 err = 1; 1395 } 1396 } 1397 1398 /* Check irreducible loops. */ 1399 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)) 1400 { 1401 /* Record old info. */ 1402 irreds = sbitmap_alloc (last_basic_block); 1403 FOR_EACH_BB (bb) 1404 { 1405 edge_iterator ei; 1406 if (bb->flags & BB_IRREDUCIBLE_LOOP) 1407 SET_BIT (irreds, bb->index); 1408 else 1409 RESET_BIT (irreds, bb->index); 1410 FOR_EACH_EDGE (e, ei, bb->succs) 1411 if (e->flags & EDGE_IRREDUCIBLE_LOOP) 1412 e->flags |= EDGE_ALL_FLAGS + 1; 1413 } 1414 1415 /* Recount it. */ 1416 mark_irreducible_loops (); 1417 1418 /* Compare. */ 1419 FOR_EACH_BB (bb) 1420 { 1421 edge_iterator ei; 1422 1423 if ((bb->flags & BB_IRREDUCIBLE_LOOP) 1424 && !TEST_BIT (irreds, bb->index)) 1425 { 1426 error ("basic block %d should be marked irreducible", bb->index); 1427 err = 1; 1428 } 1429 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP) 1430 && TEST_BIT (irreds, bb->index)) 1431 { 1432 error ("basic block %d should not be marked irreducible", bb->index); 1433 err = 1; 1434 } 1435 FOR_EACH_EDGE (e, ei, bb->succs) 1436 { 1437 if ((e->flags & EDGE_IRREDUCIBLE_LOOP) 1438 && !(e->flags & (EDGE_ALL_FLAGS + 1))) 1439 { 1440 error ("edge from %d to %d should be marked irreducible", 1441 e->src->index, e->dest->index); 1442 err = 1; 1443 } 1444 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP) 1445 && (e->flags & (EDGE_ALL_FLAGS + 1))) 1446 { 1447 error ("edge from %d to %d should not be marked irreducible", 1448 e->src->index, e->dest->index); 1449 err = 1; 1450 } 1451 e->flags &= ~(EDGE_ALL_FLAGS + 1); 1452 } 1453 } 1454 free (irreds); 1455 } 1456 1457 /* Check the recorded loop exits. */ 1458 FOR_EACH_LOOP (li, loop, 0) 1459 { 1460 if (!loop->exits || loop->exits->e != NULL) 1461 { 1462 error ("corrupted head of the exits list of loop %d", 1463 loop->num); 1464 err = 1; 1465 } 1466 else 1467 { 1468 /* Check that the list forms a cycle, and all elements except 1469 for the head are nonnull. */ 1470 for (mexit = loop->exits, exit = mexit->next, i = 0; 1471 exit->e && exit != mexit; 1472 exit = exit->next) 1473 { 1474 if (i++ & 1) 1475 mexit = mexit->next; 1476 } 1477 1478 if (exit != loop->exits) 1479 { 1480 error ("corrupted exits list of loop %d", loop->num); 1481 err = 1; 1482 } 1483 } 1484 1485 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1486 { 1487 if (loop->exits->next != loop->exits) 1488 { 1489 error ("nonempty exits list of loop %d, but exits are not recorded", 1490 loop->num); 1491 err = 1; 1492 } 1493 } 1494 } 1495 1496 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1497 { 1498 unsigned n_exits = 0, eloops; 1499 1500 memset (sizes, 0, sizeof (unsigned) * num); 1501 FOR_EACH_BB (bb) 1502 { 1503 edge_iterator ei; 1504 if (bb->loop_father == current_loops->tree_root) 1505 continue; 1506 FOR_EACH_EDGE (e, ei, bb->succs) 1507 { 1508 if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) 1509 continue; 1510 1511 n_exits++; 1512 exit = get_exit_descriptions (e); 1513 if (!exit) 1514 { 1515 error ("exit %d->%d not recorded", 1516 e->src->index, e->dest->index); 1517 err = 1; 1518 } 1519 eloops = 0; 1520 for (; exit; exit = exit->next_e) 1521 eloops++; 1522 1523 for (loop = bb->loop_father; 1524 loop != e->dest->loop_father; 1525 loop = loop_outer (loop)) 1526 { 1527 eloops--; 1528 sizes[loop->num]++; 1529 } 1530 1531 if (eloops != 0) 1532 { 1533 error ("wrong list of exited loops for edge %d->%d", 1534 e->src->index, e->dest->index); 1535 err = 1; 1536 } 1537 } 1538 } 1539 1540 if (n_exits != htab_elements (current_loops->exits)) 1541 { 1542 error ("too many loop exits recorded"); 1543 err = 1; 1544 } 1545 1546 FOR_EACH_LOOP (li, loop, 0) 1547 { 1548 eloops = 0; 1549 for (exit = loop->exits->next; exit->e; exit = exit->next) 1550 eloops++; 1551 if (eloops != sizes[loop->num]) 1552 { 1553 error ("%d exits recorded for loop %d (having %d exits)", 1554 eloops, loop->num, sizes[loop->num]); 1555 err = 1; 1556 } 1557 } 1558 } 1559 1560 gcc_assert (!err); 1561 1562 free (sizes); 1563 } 1564 1565 /* Returns latch edge of LOOP. */ 1566 edge 1567 loop_latch_edge (const struct loop *loop) 1568 { 1569 return find_edge (loop->latch, loop->header); 1570 } 1571 1572 /* Returns preheader edge of LOOP. */ 1573 edge 1574 loop_preheader_edge (const struct loop *loop) 1575 { 1576 edge e; 1577 edge_iterator ei; 1578 1579 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)); 1580 1581 FOR_EACH_EDGE (e, ei, loop->header->preds) 1582 if (e->src != loop->latch) 1583 break; 1584 1585 return e; 1586 } 1587 1588 /* Returns true if E is an exit of LOOP. */ 1589 1590 bool 1591 loop_exit_edge_p (const struct loop *loop, const_edge e) 1592 { 1593 return (flow_bb_inside_loop_p (loop, e->src) 1594 && !flow_bb_inside_loop_p (loop, e->dest)); 1595 } 1596 1597 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit 1598 or more than one exit. If loops do not have the exits recorded, NULL 1599 is returned always. */ 1600 1601 edge 1602 single_exit (const struct loop *loop) 1603 { 1604 struct loop_exit *exit = loop->exits->next; 1605 1606 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1607 return NULL; 1608 1609 if (exit->e && exit->next == loop->exits) 1610 return exit->e; 1611 else 1612 return NULL; 1613 } 1614 1615 /* Returns true when BB has an incoming edge exiting LOOP. */ 1616 1617 bool 1618 loop_exits_to_bb_p (struct loop *loop, basic_block bb) 1619 { 1620 edge e; 1621 edge_iterator ei; 1622 1623 FOR_EACH_EDGE (e, ei, bb->preds) 1624 if (loop_exit_edge_p (loop, e)) 1625 return true; 1626 1627 return false; 1628 } 1629 1630 /* Returns true when BB has an outgoing edge exiting LOOP. */ 1631 1632 bool 1633 loop_exits_from_bb_p (struct loop *loop, basic_block bb) 1634 { 1635 edge e; 1636 edge_iterator ei; 1637 1638 FOR_EACH_EDGE (e, ei, bb->succs) 1639 if (loop_exit_edge_p (loop, e)) 1640 return true; 1641 1642 return false; 1643 } 1644