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