1/* Natural loop discovery code for GNU compiler. 2 Copyright (C) 2000-2015 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 3, 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 COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "tm.h" 24#include "rtl.h" 25#include "hashtab.h" 26#include "hash-set.h" 27#include "vec.h" 28#include "symtab.h" 29#include "inchash.h" 30#include "machmode.h" 31#include "hard-reg-set.h" 32#include "input.h" 33#include "function.h" 34#include "predict.h" 35#include "dominance.h" 36#include "cfg.h" 37#include "cfganal.h" 38#include "basic-block.h" 39#include "cfgloop.h" 40#include "diagnostic-core.h" 41#include "flags.h" 42#include "tree.h" 43#include "fold-const.h" 44#include "tree-ssa-alias.h" 45#include "internal-fn.h" 46#include "gimple-expr.h" 47#include "is-a.h" 48#include "gimple.h" 49#include "gimple-iterator.h" 50#include "gimple-ssa.h" 51#include "dumpfile.h" 52 53static void flow_loops_cfg_dump (FILE *); 54 55/* Dump loop related CFG information. */ 56 57static void 58flow_loops_cfg_dump (FILE *file) 59{ 60 basic_block bb; 61 62 if (!file) 63 return; 64 65 FOR_EACH_BB_FN (bb, cfun) 66 { 67 edge succ; 68 edge_iterator ei; 69 70 fprintf (file, ";; %d succs { ", bb->index); 71 FOR_EACH_EDGE (succ, ei, bb->succs) 72 fprintf (file, "%d ", succ->dest->index); 73 fprintf (file, "}\n"); 74 } 75} 76 77/* Return nonzero if the nodes of LOOP are a subset of OUTER. */ 78 79bool 80flow_loop_nested_p (const struct loop *outer, const struct loop *loop) 81{ 82 unsigned odepth = loop_depth (outer); 83 84 return (loop_depth (loop) > odepth 85 && (*loop->superloops)[odepth] == outer); 86} 87 88/* Returns the loop such that LOOP is nested DEPTH (indexed from zero) 89 loops within LOOP. */ 90 91struct loop * 92superloop_at_depth (struct loop *loop, unsigned depth) 93{ 94 unsigned ldepth = loop_depth (loop); 95 96 gcc_assert (depth <= ldepth); 97 98 if (depth == ldepth) 99 return loop; 100 101 return (*loop->superloops)[depth]; 102} 103 104/* Returns the list of the latch edges of LOOP. */ 105 106static vec<edge> 107get_loop_latch_edges (const struct loop *loop) 108{ 109 edge_iterator ei; 110 edge e; 111 vec<edge> ret = vNULL; 112 113 FOR_EACH_EDGE (e, ei, loop->header->preds) 114 { 115 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header)) 116 ret.safe_push (e); 117 } 118 119 return ret; 120} 121 122/* Dump the loop information specified by LOOP to the stream FILE 123 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ 124 125void 126flow_loop_dump (const struct loop *loop, FILE *file, 127 void (*loop_dump_aux) (const struct loop *, FILE *, int), 128 int verbose) 129{ 130 basic_block *bbs; 131 unsigned i; 132 vec<edge> latches; 133 edge e; 134 135 if (! loop || ! loop->header) 136 return; 137 138 fprintf (file, ";;\n;; Loop %d\n", loop->num); 139 140 fprintf (file, ";; header %d, ", loop->header->index); 141 if (loop->latch) 142 fprintf (file, "latch %d\n", loop->latch->index); 143 else 144 { 145 fprintf (file, "multiple latches:"); 146 latches = get_loop_latch_edges (loop); 147 FOR_EACH_VEC_ELT (latches, i, e) 148 fprintf (file, " %d", e->src->index); 149 latches.release (); 150 fprintf (file, "\n"); 151 } 152 153 fprintf (file, ";; depth %d, outer %ld\n", 154 loop_depth (loop), (long) (loop_outer (loop) 155 ? loop_outer (loop)->num : -1)); 156 157 fprintf (file, ";; nodes:"); 158 bbs = get_loop_body (loop); 159 for (i = 0; i < loop->num_nodes; i++) 160 fprintf (file, " %d", bbs[i]->index); 161 free (bbs); 162 fprintf (file, "\n"); 163 164 if (loop_dump_aux) 165 loop_dump_aux (loop, file, verbose); 166} 167 168/* Dump the loop information about loops to the stream FILE, 169 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ 170 171void 172flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) 173{ 174 struct loop *loop; 175 176 if (!current_loops || ! file) 177 return; 178 179 fprintf (file, ";; %d loops found\n", number_of_loops (cfun)); 180 181 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) 182 { 183 flow_loop_dump (loop, file, loop_dump_aux, verbose); 184 } 185 186 if (verbose) 187 flow_loops_cfg_dump (file); 188} 189 190/* Free data allocated for LOOP. */ 191 192void 193flow_loop_free (struct loop *loop) 194{ 195 struct loop_exit *exit, *next; 196 197 vec_free (loop->superloops); 198 199 /* Break the list of the loop exit records. They will be freed when the 200 corresponding edge is rescanned or removed, and this avoids 201 accessing the (already released) head of the list stored in the 202 loop structure. */ 203 for (exit = loop->exits->next; exit != loop->exits; exit = next) 204 { 205 next = exit->next; 206 exit->next = exit; 207 exit->prev = exit; 208 } 209 210 ggc_free (loop->exits); 211 ggc_free (loop); 212} 213 214/* Free all the memory allocated for LOOPS. */ 215 216void 217flow_loops_free (struct loops *loops) 218{ 219 if (loops->larray) 220 { 221 unsigned i; 222 loop_p loop; 223 224 /* Free the loop descriptors. */ 225 FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop) 226 { 227 if (!loop) 228 continue; 229 230 flow_loop_free (loop); 231 } 232 233 vec_free (loops->larray); 234 } 235} 236 237/* Find the nodes contained within the LOOP with header HEADER. 238 Return the number of nodes within the loop. */ 239 240int 241flow_loop_nodes_find (basic_block header, struct loop *loop) 242{ 243 vec<basic_block> stack = vNULL; 244 int num_nodes = 1; 245 edge latch; 246 edge_iterator latch_ei; 247 248 header->loop_father = loop; 249 250 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds) 251 { 252 if (latch->src->loop_father == loop 253 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header)) 254 continue; 255 256 num_nodes++; 257 stack.safe_push (latch->src); 258 latch->src->loop_father = loop; 259 260 while (!stack.is_empty ()) 261 { 262 basic_block node; 263 edge e; 264 edge_iterator ei; 265 266 node = stack.pop (); 267 268 FOR_EACH_EDGE (e, ei, node->preds) 269 { 270 basic_block ancestor = e->src; 271 272 if (ancestor->loop_father != loop) 273 { 274 ancestor->loop_father = loop; 275 num_nodes++; 276 stack.safe_push (ancestor); 277 } 278 } 279 } 280 } 281 stack.release (); 282 283 return num_nodes; 284} 285 286/* Records the vector of superloops of the loop LOOP, whose immediate 287 superloop is FATHER. */ 288 289static void 290establish_preds (struct loop *loop, struct loop *father) 291{ 292 loop_p ploop; 293 unsigned depth = loop_depth (father) + 1; 294 unsigned i; 295 296 loop->superloops = 0; 297 vec_alloc (loop->superloops, depth); 298 FOR_EACH_VEC_SAFE_ELT (father->superloops, i, ploop) 299 loop->superloops->quick_push (ploop); 300 loop->superloops->quick_push (father); 301 302 for (ploop = loop->inner; ploop; ploop = ploop->next) 303 establish_preds (ploop, loop); 304} 305 306/* Add LOOP to the loop hierarchy tree where FATHER is father of the 307 added loop. If LOOP has some children, take care of that their 308 pred field will be initialized correctly. */ 309 310void 311flow_loop_tree_node_add (struct loop *father, struct loop *loop) 312{ 313 loop->next = father->inner; 314 father->inner = loop; 315 316 establish_preds (loop, father); 317} 318 319/* Remove LOOP from the loop hierarchy tree. */ 320 321void 322flow_loop_tree_node_remove (struct loop *loop) 323{ 324 struct loop *prev, *father; 325 326 father = loop_outer (loop); 327 328 /* Remove loop from the list of sons. */ 329 if (father->inner == loop) 330 father->inner = loop->next; 331 else 332 { 333 for (prev = father->inner; prev->next != loop; prev = prev->next) 334 continue; 335 prev->next = loop->next; 336 } 337 338 loop->superloops = NULL; 339} 340 341/* Allocates and returns new loop structure. */ 342 343struct loop * 344alloc_loop (void) 345{ 346 struct loop *loop = ggc_cleared_alloc<struct loop> (); 347 348 loop->exits = ggc_cleared_alloc<loop_exit> (); 349 loop->exits->next = loop->exits->prev = loop->exits; 350 loop->can_be_parallel = false; 351 loop->nb_iterations_upper_bound = 0; 352 loop->nb_iterations_estimate = 0; 353 return loop; 354} 355 356/* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops 357 (including the root of the loop tree). */ 358 359void 360init_loops_structure (struct function *fn, 361 struct loops *loops, unsigned num_loops) 362{ 363 struct loop *root; 364 365 memset (loops, 0, sizeof *loops); 366 vec_alloc (loops->larray, num_loops); 367 368 /* Dummy loop containing whole function. */ 369 root = alloc_loop (); 370 root->num_nodes = n_basic_blocks_for_fn (fn); 371 root->latch = EXIT_BLOCK_PTR_FOR_FN (fn); 372 root->header = ENTRY_BLOCK_PTR_FOR_FN (fn); 373 ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root; 374 EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root; 375 376 loops->larray->quick_push (root); 377 loops->tree_root = root; 378} 379 380/* Returns whether HEADER is a loop header. */ 381 382bool 383bb_loop_header_p (basic_block header) 384{ 385 edge_iterator ei; 386 edge e; 387 388 /* If we have an abnormal predecessor, do not consider the 389 loop (not worth the problems). */ 390 if (bb_has_abnormal_pred (header)) 391 return false; 392 393 /* Look for back edges where a predecessor is dominated 394 by this block. A natural loop has a single entry 395 node (header) that dominates all the nodes in the 396 loop. It also has single back edge to the header 397 from a latch node. */ 398 FOR_EACH_EDGE (e, ei, header->preds) 399 { 400 basic_block latch = e->src; 401 if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun) 402 && dominated_by_p (CDI_DOMINATORS, latch, header)) 403 return true; 404 } 405 406 return false; 407} 408 409/* Find all the natural loops in the function and save in LOOPS structure and 410 recalculate loop_father information in basic block structures. 411 If LOOPS is non-NULL then the loop structures for already recorded loops 412 will be re-used and their number will not change. We assume that no 413 stale loops exist in LOOPS. 414 When LOOPS is NULL it is allocated and re-built from scratch. 415 Return the built LOOPS structure. */ 416 417struct loops * 418flow_loops_find (struct loops *loops) 419{ 420 bool from_scratch = (loops == NULL); 421 int *rc_order; 422 int b; 423 unsigned i; 424 425 /* Ensure that the dominators are computed. */ 426 calculate_dominance_info (CDI_DOMINATORS); 427 428 if (!loops) 429 { 430 loops = ggc_cleared_alloc<struct loops> (); 431 init_loops_structure (cfun, loops, 1); 432 } 433 434 /* Ensure that loop exits were released. */ 435 gcc_assert (loops->exits == NULL); 436 437 /* Taking care of this degenerate case makes the rest of 438 this code simpler. */ 439 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS) 440 return loops; 441 442 /* The root loop node contains all basic-blocks. */ 443 loops->tree_root->num_nodes = n_basic_blocks_for_fn (cfun); 444 445 /* Compute depth first search order of the CFG so that outer 446 natural loops will be found before inner natural loops. */ 447 rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); 448 pre_and_rev_post_order_compute (NULL, rc_order, false); 449 450 /* Gather all loop headers in reverse completion order and allocate 451 loop structures for loops that are not already present. */ 452 auto_vec<loop_p> larray (loops->larray->length ()); 453 for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++) 454 { 455 basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]); 456 if (bb_loop_header_p (header)) 457 { 458 struct loop *loop; 459 460 /* The current active loop tree has valid loop-fathers for 461 header blocks. */ 462 if (!from_scratch 463 && header->loop_father->header == header) 464 { 465 loop = header->loop_father; 466 /* If we found an existing loop remove it from the 467 loop tree. It is going to be inserted again 468 below. */ 469 flow_loop_tree_node_remove (loop); 470 } 471 else 472 { 473 /* Otherwise allocate a new loop structure for the loop. */ 474 loop = alloc_loop (); 475 /* ??? We could re-use unused loop slots here. */ 476 loop->num = loops->larray->length (); 477 vec_safe_push (loops->larray, loop); 478 loop->header = header; 479 480 if (!from_scratch 481 && dump_file && (dump_flags & TDF_DETAILS)) 482 fprintf (dump_file, "flow_loops_find: discovered new " 483 "loop %d with header %d\n", 484 loop->num, header->index); 485 } 486 /* Reset latch, we recompute it below. */ 487 loop->latch = NULL; 488 larray.safe_push (loop); 489 } 490 491 /* Make blocks part of the loop root node at start. */ 492 header->loop_father = loops->tree_root; 493 } 494 495 free (rc_order); 496 497 /* Now iterate over the loops found, insert them into the loop tree 498 and assign basic-block ownership. */ 499 for (i = 0; i < larray.length (); ++i) 500 { 501 struct loop *loop = larray[i]; 502 basic_block header = loop->header; 503 edge_iterator ei; 504 edge e; 505 506 flow_loop_tree_node_add (header->loop_father, loop); 507 loop->num_nodes = flow_loop_nodes_find (loop->header, loop); 508 509 /* Look for the latch for this header block, if it has just a 510 single one. */ 511 FOR_EACH_EDGE (e, ei, header->preds) 512 { 513 basic_block latch = e->src; 514 515 if (flow_bb_inside_loop_p (loop, latch)) 516 { 517 if (loop->latch != NULL) 518 { 519 /* More than one latch edge. */ 520 loop->latch = NULL; 521 break; 522 } 523 loop->latch = latch; 524 } 525 } 526 } 527 528 return loops; 529} 530 531/* Ratio of frequencies of edges so that one of more latch edges is 532 considered to belong to inner loop with same header. */ 533#define HEAVY_EDGE_RATIO 8 534 535/* Minimum number of samples for that we apply 536 find_subloop_latch_edge_by_profile heuristics. */ 537#define HEAVY_EDGE_MIN_SAMPLES 10 538 539/* If the profile info is available, finds an edge in LATCHES that much more 540 frequent than the remaining edges. Returns such an edge, or NULL if we do 541 not find one. 542 543 We do not use guessed profile here, only the measured one. The guessed 544 profile is usually too flat and unreliable for this (and it is mostly based 545 on the loop structure of the program, so it does not make much sense to 546 derive the loop structure from it). */ 547 548static edge 549find_subloop_latch_edge_by_profile (vec<edge> latches) 550{ 551 unsigned i; 552 edge e, me = NULL; 553 gcov_type mcount = 0, tcount = 0; 554 555 FOR_EACH_VEC_ELT (latches, i, e) 556 { 557 if (e->count > mcount) 558 { 559 me = e; 560 mcount = e->count; 561 } 562 tcount += e->count; 563 } 564 565 if (tcount < HEAVY_EDGE_MIN_SAMPLES 566 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount) 567 return NULL; 568 569 if (dump_file) 570 fprintf (dump_file, 571 "Found latch edge %d -> %d using profile information.\n", 572 me->src->index, me->dest->index); 573 return me; 574} 575 576/* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based 577 on the structure of induction variables. Returns this edge, or NULL if we 578 do not find any. 579 580 We are quite conservative, and look just for an obvious simple innermost 581 loop (which is the case where we would lose the most performance by not 582 disambiguating the loop). More precisely, we look for the following 583 situation: The source of the chosen latch edge dominates sources of all 584 the other latch edges. Additionally, the header does not contain a phi node 585 such that the argument from the chosen edge is equal to the argument from 586 another edge. */ 587 588static edge 589find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, vec<edge> latches) 590{ 591 edge e, latch = latches[0]; 592 unsigned i; 593 gphi *phi; 594 gphi_iterator psi; 595 tree lop; 596 basic_block bb; 597 598 /* Find the candidate for the latch edge. */ 599 for (i = 1; latches.iterate (i, &e); i++) 600 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src)) 601 latch = e; 602 603 /* Verify that it dominates all the latch edges. */ 604 FOR_EACH_VEC_ELT (latches, i, e) 605 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src)) 606 return NULL; 607 608 /* Check for a phi node that would deny that this is a latch edge of 609 a subloop. */ 610 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi)) 611 { 612 phi = psi.phi (); 613 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch); 614 615 /* Ignore the values that are not changed inside the subloop. */ 616 if (TREE_CODE (lop) != SSA_NAME 617 || SSA_NAME_DEF_STMT (lop) == phi) 618 continue; 619 bb = gimple_bb (SSA_NAME_DEF_STMT (lop)); 620 if (!bb || !flow_bb_inside_loop_p (loop, bb)) 621 continue; 622 623 FOR_EACH_VEC_ELT (latches, i, e) 624 if (e != latch 625 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop) 626 return NULL; 627 } 628 629 if (dump_file) 630 fprintf (dump_file, 631 "Found latch edge %d -> %d using iv structure.\n", 632 latch->src->index, latch->dest->index); 633 return latch; 634} 635 636/* If we can determine that one of the several latch edges of LOOP behaves 637 as a latch edge of a separate subloop, returns this edge. Otherwise 638 returns NULL. */ 639 640static edge 641find_subloop_latch_edge (struct loop *loop) 642{ 643 vec<edge> latches = get_loop_latch_edges (loop); 644 edge latch = NULL; 645 646 if (latches.length () > 1) 647 { 648 latch = find_subloop_latch_edge_by_profile (latches); 649 650 if (!latch 651 /* We consider ivs to guess the latch edge only in SSA. Perhaps we 652 should use cfghook for this, but it is hard to imagine it would 653 be useful elsewhere. */ 654 && current_ir_type () == IR_GIMPLE) 655 latch = find_subloop_latch_edge_by_ivs (loop, latches); 656 } 657 658 latches.release (); 659 return latch; 660} 661 662/* Callback for make_forwarder_block. Returns true if the edge E is marked 663 in the set MFB_REIS_SET. */ 664 665static hash_set<edge> *mfb_reis_set; 666static bool 667mfb_redirect_edges_in_set (edge e) 668{ 669 return mfb_reis_set->contains (e); 670} 671 672/* Creates a subloop of LOOP with latch edge LATCH. */ 673 674static void 675form_subloop (struct loop *loop, edge latch) 676{ 677 edge_iterator ei; 678 edge e, new_entry; 679 struct loop *new_loop; 680 681 mfb_reis_set = new hash_set<edge>; 682 FOR_EACH_EDGE (e, ei, loop->header->preds) 683 { 684 if (e != latch) 685 mfb_reis_set->add (e); 686 } 687 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, 688 NULL); 689 delete mfb_reis_set; 690 691 loop->header = new_entry->src; 692 693 /* Find the blocks and subloops that belong to the new loop, and add it to 694 the appropriate place in the loop tree. */ 695 new_loop = alloc_loop (); 696 new_loop->header = new_entry->dest; 697 new_loop->latch = latch->src; 698 add_loop (new_loop, loop); 699} 700 701/* Make all the latch edges of LOOP to go to a single forwarder block -- 702 a new latch of LOOP. */ 703 704static void 705merge_latch_edges (struct loop *loop) 706{ 707 vec<edge> latches = get_loop_latch_edges (loop); 708 edge latch, e; 709 unsigned i; 710 711 gcc_assert (latches.length () > 0); 712 713 if (latches.length () == 1) 714 loop->latch = latches[0]->src; 715 else 716 { 717 if (dump_file) 718 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num); 719 720 mfb_reis_set = new hash_set<edge>; 721 FOR_EACH_VEC_ELT (latches, i, e) 722 mfb_reis_set->add (e); 723 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, 724 NULL); 725 delete mfb_reis_set; 726 727 loop->header = latch->dest; 728 loop->latch = latch->src; 729 } 730 731 latches.release (); 732} 733 734/* LOOP may have several latch edges. Transform it into (possibly several) 735 loops with single latch edge. */ 736 737static void 738disambiguate_multiple_latches (struct loop *loop) 739{ 740 edge e; 741 742 /* We eliminate the multiple latches by splitting the header to the forwarder 743 block F and the rest R, and redirecting the edges. There are two cases: 744 745 1) If there is a latch edge E that corresponds to a subloop (we guess 746 that based on profile -- if it is taken much more often than the 747 remaining edges; and on trees, using the information about induction 748 variables of the loops), we redirect E to R, all the remaining edges to 749 F, then rescan the loops and try again for the outer loop. 750 2) If there is no such edge, we redirect all latch edges to F, and the 751 entry edges to R, thus making F the single latch of the loop. */ 752 753 if (dump_file) 754 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n", 755 loop->num); 756 757 /* During latch merging, we may need to redirect the entry edges to a new 758 block. This would cause problems if the entry edge was the one from the 759 entry block. To avoid having to handle this case specially, split 760 such entry edge. */ 761 e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header); 762 if (e) 763 split_edge (e); 764 765 while (1) 766 { 767 e = find_subloop_latch_edge (loop); 768 if (!e) 769 break; 770 771 form_subloop (loop, e); 772 } 773 774 merge_latch_edges (loop); 775} 776 777/* Split loops with multiple latch edges. */ 778 779void 780disambiguate_loops_with_multiple_latches (void) 781{ 782 struct loop *loop; 783 784 FOR_EACH_LOOP (loop, 0) 785 { 786 if (!loop->latch) 787 disambiguate_multiple_latches (loop); 788 } 789} 790 791/* Return nonzero if basic block BB belongs to LOOP. */ 792bool 793flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb) 794{ 795 struct loop *source_loop; 796 797 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) 798 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 799 return 0; 800 801 source_loop = bb->loop_father; 802 return loop == source_loop || flow_loop_nested_p (loop, source_loop); 803} 804 805/* Enumeration predicate for get_loop_body_with_size. */ 806static bool 807glb_enum_p (const_basic_block bb, const void *glb_loop) 808{ 809 const struct loop *const loop = (const struct loop *) glb_loop; 810 return (bb != loop->header 811 && dominated_by_p (CDI_DOMINATORS, bb, loop->header)); 812} 813 814/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs 815 order against direction of edges from latch. Specially, if 816 header != latch, latch is the 1-st block. LOOP cannot be the fake 817 loop tree root, and its size must be at most MAX_SIZE. The blocks 818 in the LOOP body are stored to BODY, and the size of the LOOP is 819 returned. */ 820 821unsigned 822get_loop_body_with_size (const struct loop *loop, basic_block *body, 823 unsigned max_size) 824{ 825 return dfs_enumerate_from (loop->header, 1, glb_enum_p, 826 body, max_size, loop); 827} 828 829/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs 830 order against direction of edges from latch. Specially, if 831 header != latch, latch is the 1-st block. */ 832 833basic_block * 834get_loop_body (const struct loop *loop) 835{ 836 basic_block *body, bb; 837 unsigned tv = 0; 838 839 gcc_assert (loop->num_nodes); 840 841 body = XNEWVEC (basic_block, loop->num_nodes); 842 843 if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun)) 844 { 845 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to 846 special-case the fake loop that contains the whole function. */ 847 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun)); 848 body[tv++] = loop->header; 849 body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun); 850 FOR_EACH_BB_FN (bb, cfun) 851 body[tv++] = bb; 852 } 853 else 854 tv = get_loop_body_with_size (loop, body, loop->num_nodes); 855 856 gcc_assert (tv == loop->num_nodes); 857 return body; 858} 859 860/* Fills dominance descendants inside LOOP of the basic block BB into 861 array TOVISIT from index *TV. */ 862 863static void 864fill_sons_in_loop (const struct loop *loop, basic_block bb, 865 basic_block *tovisit, int *tv) 866{ 867 basic_block son, postpone = NULL; 868 869 tovisit[(*tv)++] = bb; 870 for (son = first_dom_son (CDI_DOMINATORS, bb); 871 son; 872 son = next_dom_son (CDI_DOMINATORS, son)) 873 { 874 if (!flow_bb_inside_loop_p (loop, son)) 875 continue; 876 877 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son)) 878 { 879 postpone = son; 880 continue; 881 } 882 fill_sons_in_loop (loop, son, tovisit, tv); 883 } 884 885 if (postpone) 886 fill_sons_in_loop (loop, postpone, tovisit, tv); 887} 888 889/* Gets body of a LOOP (that must be different from the outermost loop) 890 sorted by dominance relation. Additionally, if a basic block s dominates 891 the latch, then only blocks dominated by s are be after it. */ 892 893basic_block * 894get_loop_body_in_dom_order (const struct loop *loop) 895{ 896 basic_block *tovisit; 897 int tv; 898 899 gcc_assert (loop->num_nodes); 900 901 tovisit = XNEWVEC (basic_block, loop->num_nodes); 902 903 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)); 904 905 tv = 0; 906 fill_sons_in_loop (loop, loop->header, tovisit, &tv); 907 908 gcc_assert (tv == (int) loop->num_nodes); 909 910 return tovisit; 911} 912 913/* Gets body of a LOOP sorted via provided BB_COMPARATOR. */ 914 915basic_block * 916get_loop_body_in_custom_order (const struct loop *loop, 917 int (*bb_comparator) (const void *, const void *)) 918{ 919 basic_block *bbs = get_loop_body (loop); 920 921 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator); 922 923 return bbs; 924} 925 926/* Get body of a LOOP in breadth first sort order. */ 927 928basic_block * 929get_loop_body_in_bfs_order (const struct loop *loop) 930{ 931 basic_block *blocks; 932 basic_block bb; 933 bitmap visited; 934 unsigned int i = 0; 935 unsigned int vc = 1; 936 937 gcc_assert (loop->num_nodes); 938 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)); 939 940 blocks = XNEWVEC (basic_block, loop->num_nodes); 941 visited = BITMAP_ALLOC (NULL); 942 943 bb = loop->header; 944 while (i < loop->num_nodes) 945 { 946 edge e; 947 edge_iterator ei; 948 949 if (bitmap_set_bit (visited, bb->index)) 950 /* This basic block is now visited */ 951 blocks[i++] = bb; 952 953 FOR_EACH_EDGE (e, ei, bb->succs) 954 { 955 if (flow_bb_inside_loop_p (loop, e->dest)) 956 { 957 if (bitmap_set_bit (visited, e->dest->index)) 958 blocks[i++] = e->dest; 959 } 960 } 961 962 gcc_assert (i >= vc); 963 964 bb = blocks[vc++]; 965 } 966 967 BITMAP_FREE (visited); 968 return blocks; 969} 970 971/* Hash function for struct loop_exit. */ 972 973hashval_t 974loop_exit_hasher::hash (loop_exit *exit) 975{ 976 return htab_hash_pointer (exit->e); 977} 978 979/* Equality function for struct loop_exit. Compares with edge. */ 980 981bool 982loop_exit_hasher::equal (loop_exit *exit, edge e) 983{ 984 return exit->e == e; 985} 986 987/* Frees the list of loop exit descriptions EX. */ 988 989void 990loop_exit_hasher::remove (loop_exit *exit) 991{ 992 loop_exit *next; 993 for (; exit; exit = next) 994 { 995 next = exit->next_e; 996 997 exit->next->prev = exit->prev; 998 exit->prev->next = exit->next; 999 1000 ggc_free (exit); 1001 } 1002} 1003 1004/* Returns the list of records for E as an exit of a loop. */ 1005 1006static struct loop_exit * 1007get_exit_descriptions (edge e) 1008{ 1009 return current_loops->exits->find_with_hash (e, htab_hash_pointer (e)); 1010} 1011 1012/* Updates the lists of loop exits in that E appears. 1013 If REMOVED is true, E is being removed, and we 1014 just remove it from the lists of exits. 1015 If NEW_EDGE is true and E is not a loop exit, we 1016 do not try to remove it from loop exit lists. */ 1017 1018void 1019rescan_loop_exit (edge e, bool new_edge, bool removed) 1020{ 1021 struct loop_exit *exits = NULL, *exit; 1022 struct loop *aloop, *cloop; 1023 1024 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1025 return; 1026 1027 if (!removed 1028 && e->src->loop_father != NULL 1029 && e->dest->loop_father != NULL 1030 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest)) 1031 { 1032 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father); 1033 for (aloop = e->src->loop_father; 1034 aloop != cloop; 1035 aloop = loop_outer (aloop)) 1036 { 1037 exit = ggc_alloc<loop_exit> (); 1038 exit->e = e; 1039 1040 exit->next = aloop->exits->next; 1041 exit->prev = aloop->exits; 1042 exit->next->prev = exit; 1043 exit->prev->next = exit; 1044 1045 exit->next_e = exits; 1046 exits = exit; 1047 } 1048 } 1049 1050 if (!exits && new_edge) 1051 return; 1052 1053 loop_exit **slot 1054 = current_loops->exits->find_slot_with_hash (e, htab_hash_pointer (e), 1055 exits ? INSERT : NO_INSERT); 1056 if (!slot) 1057 return; 1058 1059 if (exits) 1060 { 1061 if (*slot) 1062 loop_exit_hasher::remove (*slot); 1063 *slot = exits; 1064 } 1065 else 1066 current_loops->exits->clear_slot (slot); 1067} 1068 1069/* For each loop, record list of exit edges, and start maintaining these 1070 lists. */ 1071 1072void 1073record_loop_exits (void) 1074{ 1075 basic_block bb; 1076 edge_iterator ei; 1077 edge e; 1078 1079 if (!current_loops) 1080 return; 1081 1082 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1083 return; 1084 loops_state_set (LOOPS_HAVE_RECORDED_EXITS); 1085 1086 gcc_assert (current_loops->exits == NULL); 1087 current_loops->exits 1088 = hash_table<loop_exit_hasher>::create_ggc (2 * number_of_loops (cfun)); 1089 1090 FOR_EACH_BB_FN (bb, cfun) 1091 { 1092 FOR_EACH_EDGE (e, ei, bb->succs) 1093 { 1094 rescan_loop_exit (e, true, false); 1095 } 1096 } 1097} 1098 1099/* Dumps information about the exit in *SLOT to FILE. 1100 Callback for htab_traverse. */ 1101 1102int 1103dump_recorded_exit (loop_exit **slot, FILE *file) 1104{ 1105 struct loop_exit *exit = *slot; 1106 unsigned n = 0; 1107 edge e = exit->e; 1108 1109 for (; exit != NULL; exit = exit->next_e) 1110 n++; 1111 1112 fprintf (file, "Edge %d->%d exits %u loops\n", 1113 e->src->index, e->dest->index, n); 1114 1115 return 1; 1116} 1117 1118/* Dumps the recorded exits of loops to FILE. */ 1119 1120extern void dump_recorded_exits (FILE *); 1121void 1122dump_recorded_exits (FILE *file) 1123{ 1124 if (!current_loops->exits) 1125 return; 1126 current_loops->exits->traverse<FILE *, dump_recorded_exit> (file); 1127} 1128 1129/* Releases lists of loop exits. */ 1130 1131void 1132release_recorded_exits (void) 1133{ 1134 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)); 1135 current_loops->exits->empty (); 1136 current_loops->exits = NULL; 1137 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS); 1138} 1139 1140/* Returns the list of the exit edges of a LOOP. */ 1141 1142vec<edge> 1143get_loop_exit_edges (const struct loop *loop) 1144{ 1145 vec<edge> edges = vNULL; 1146 edge e; 1147 unsigned i; 1148 basic_block *body; 1149 edge_iterator ei; 1150 struct loop_exit *exit; 1151 1152 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)); 1153 1154 /* If we maintain the lists of exits, use them. Otherwise we must 1155 scan the body of the loop. */ 1156 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1157 { 1158 for (exit = loop->exits->next; exit->e; exit = exit->next) 1159 edges.safe_push (exit->e); 1160 } 1161 else 1162 { 1163 body = get_loop_body (loop); 1164 for (i = 0; i < loop->num_nodes; i++) 1165 FOR_EACH_EDGE (e, ei, body[i]->succs) 1166 { 1167 if (!flow_bb_inside_loop_p (loop, e->dest)) 1168 edges.safe_push (e); 1169 } 1170 free (body); 1171 } 1172 1173 return edges; 1174} 1175 1176/* Counts the number of conditional branches inside LOOP. */ 1177 1178unsigned 1179num_loop_branches (const struct loop *loop) 1180{ 1181 unsigned i, n; 1182 basic_block * body; 1183 1184 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)); 1185 1186 body = get_loop_body (loop); 1187 n = 0; 1188 for (i = 0; i < loop->num_nodes; i++) 1189 if (EDGE_COUNT (body[i]->succs) >= 2) 1190 n++; 1191 free (body); 1192 1193 return n; 1194} 1195 1196/* Adds basic block BB to LOOP. */ 1197void 1198add_bb_to_loop (basic_block bb, struct loop *loop) 1199{ 1200 unsigned i; 1201 loop_p ploop; 1202 edge_iterator ei; 1203 edge e; 1204 1205 gcc_assert (bb->loop_father == NULL); 1206 bb->loop_father = loop; 1207 loop->num_nodes++; 1208 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop) 1209 ploop->num_nodes++; 1210 1211 FOR_EACH_EDGE (e, ei, bb->succs) 1212 { 1213 rescan_loop_exit (e, true, false); 1214 } 1215 FOR_EACH_EDGE (e, ei, bb->preds) 1216 { 1217 rescan_loop_exit (e, true, false); 1218 } 1219} 1220 1221/* Remove basic block BB from loops. */ 1222void 1223remove_bb_from_loops (basic_block bb) 1224{ 1225 unsigned i; 1226 struct loop *loop = bb->loop_father; 1227 loop_p ploop; 1228 edge_iterator ei; 1229 edge e; 1230 1231 gcc_assert (loop != NULL); 1232 loop->num_nodes--; 1233 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop) 1234 ploop->num_nodes--; 1235 bb->loop_father = NULL; 1236 1237 FOR_EACH_EDGE (e, ei, bb->succs) 1238 { 1239 rescan_loop_exit (e, false, true); 1240 } 1241 FOR_EACH_EDGE (e, ei, bb->preds) 1242 { 1243 rescan_loop_exit (e, false, true); 1244 } 1245} 1246 1247/* Finds nearest common ancestor in loop tree for given loops. */ 1248struct loop * 1249find_common_loop (struct loop *loop_s, struct loop *loop_d) 1250{ 1251 unsigned sdepth, ddepth; 1252 1253 if (!loop_s) return loop_d; 1254 if (!loop_d) return loop_s; 1255 1256 sdepth = loop_depth (loop_s); 1257 ddepth = loop_depth (loop_d); 1258 1259 if (sdepth < ddepth) 1260 loop_d = (*loop_d->superloops)[sdepth]; 1261 else if (sdepth > ddepth) 1262 loop_s = (*loop_s->superloops)[ddepth]; 1263 1264 while (loop_s != loop_d) 1265 { 1266 loop_s = loop_outer (loop_s); 1267 loop_d = loop_outer (loop_d); 1268 } 1269 return loop_s; 1270} 1271 1272/* Removes LOOP from structures and frees its data. */ 1273 1274void 1275delete_loop (struct loop *loop) 1276{ 1277 /* Remove the loop from structure. */ 1278 flow_loop_tree_node_remove (loop); 1279 1280 /* Remove loop from loops array. */ 1281 (*current_loops->larray)[loop->num] = NULL; 1282 1283 /* Free loop data. */ 1284 flow_loop_free (loop); 1285} 1286 1287/* Cancels the LOOP; it must be innermost one. */ 1288 1289static void 1290cancel_loop (struct loop *loop) 1291{ 1292 basic_block *bbs; 1293 unsigned i; 1294 struct loop *outer = loop_outer (loop); 1295 1296 gcc_assert (!loop->inner); 1297 1298 /* Move blocks up one level (they should be removed as soon as possible). */ 1299 bbs = get_loop_body (loop); 1300 for (i = 0; i < loop->num_nodes; i++) 1301 bbs[i]->loop_father = outer; 1302 1303 free (bbs); 1304 delete_loop (loop); 1305} 1306 1307/* Cancels LOOP and all its subloops. */ 1308void 1309cancel_loop_tree (struct loop *loop) 1310{ 1311 while (loop->inner) 1312 cancel_loop_tree (loop->inner); 1313 cancel_loop (loop); 1314} 1315 1316/* Checks that information about loops is correct 1317 -- sizes of loops are all right 1318 -- results of get_loop_body really belong to the loop 1319 -- loop header have just single entry edge and single latch edge 1320 -- loop latches have only single successor that is header of their loop 1321 -- irreducible loops are correctly marked 1322 -- the cached loop depth and loop father of each bb is correct 1323 */ 1324DEBUG_FUNCTION void 1325verify_loop_structure (void) 1326{ 1327 unsigned *sizes, i, j; 1328 sbitmap irreds; 1329 basic_block bb, *bbs; 1330 struct loop *loop; 1331 int err = 0; 1332 edge e; 1333 unsigned num = number_of_loops (cfun); 1334 struct loop_exit *exit, *mexit; 1335 bool dom_available = dom_info_available_p (CDI_DOMINATORS); 1336 sbitmap visited; 1337 1338 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP)) 1339 { 1340 error ("loop verification on loop tree that needs fixup"); 1341 err = 1; 1342 } 1343 1344 /* We need up-to-date dominators, compute or verify them. */ 1345 if (!dom_available) 1346 calculate_dominance_info (CDI_DOMINATORS); 1347 else 1348 verify_dominators (CDI_DOMINATORS); 1349 1350 /* Check the headers. */ 1351 FOR_EACH_BB_FN (bb, cfun) 1352 if (bb_loop_header_p (bb)) 1353 { 1354 if (bb->loop_father->header == NULL) 1355 { 1356 error ("loop with header %d marked for removal", bb->index); 1357 err = 1; 1358 } 1359 else if (bb->loop_father->header != bb) 1360 { 1361 error ("loop with header %d not in loop tree", bb->index); 1362 err = 1; 1363 } 1364 } 1365 else if (bb->loop_father->header == bb) 1366 { 1367 error ("non-loop with header %d not marked for removal", bb->index); 1368 err = 1; 1369 } 1370 1371 /* Check the recorded loop father and sizes of loops. */ 1372 visited = sbitmap_alloc (last_basic_block_for_fn (cfun)); 1373 bitmap_clear (visited); 1374 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); 1375 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) 1376 { 1377 unsigned n; 1378 1379 if (loop->header == NULL) 1380 { 1381 error ("removed loop %d in loop tree", loop->num); 1382 err = 1; 1383 continue; 1384 } 1385 1386 n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun)); 1387 if (loop->num_nodes != n) 1388 { 1389 error ("size of loop %d should be %d, not %d", 1390 loop->num, n, loop->num_nodes); 1391 err = 1; 1392 } 1393 1394 for (j = 0; j < n; j++) 1395 { 1396 bb = bbs[j]; 1397 1398 if (!flow_bb_inside_loop_p (loop, bb)) 1399 { 1400 error ("bb %d does not belong to loop %d", 1401 bb->index, loop->num); 1402 err = 1; 1403 } 1404 1405 /* Ignore this block if it is in an inner loop. */ 1406 if (bitmap_bit_p (visited, bb->index)) 1407 continue; 1408 bitmap_set_bit (visited, bb->index); 1409 1410 if (bb->loop_father != loop) 1411 { 1412 error ("bb %d has father loop %d, should be loop %d", 1413 bb->index, bb->loop_father->num, loop->num); 1414 err = 1; 1415 } 1416 } 1417 } 1418 free (bbs); 1419 sbitmap_free (visited); 1420 1421 /* Check headers and latches. */ 1422 FOR_EACH_LOOP (loop, 0) 1423 { 1424 i = loop->num; 1425 if (loop->header == NULL) 1426 continue; 1427 if (!bb_loop_header_p (loop->header)) 1428 { 1429 error ("loop %d%'s header is not a loop header", i); 1430 err = 1; 1431 } 1432 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS) 1433 && EDGE_COUNT (loop->header->preds) != 2) 1434 { 1435 error ("loop %d%'s header does not have exactly 2 entries", i); 1436 err = 1; 1437 } 1438 if (loop->latch) 1439 { 1440 if (!find_edge (loop->latch, loop->header)) 1441 { 1442 error ("loop %d%'s latch does not have an edge to its header", i); 1443 err = 1; 1444 } 1445 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, loop->header)) 1446 { 1447 error ("loop %d%'s latch is not dominated by its header", i); 1448 err = 1; 1449 } 1450 } 1451 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES)) 1452 { 1453 if (!single_succ_p (loop->latch)) 1454 { 1455 error ("loop %d%'s latch does not have exactly 1 successor", i); 1456 err = 1; 1457 } 1458 if (single_succ (loop->latch) != loop->header) 1459 { 1460 error ("loop %d%'s latch does not have header as successor", i); 1461 err = 1; 1462 } 1463 if (loop->latch->loop_father != loop) 1464 { 1465 error ("loop %d%'s latch does not belong directly to it", i); 1466 err = 1; 1467 } 1468 } 1469 if (loop->header->loop_father != loop) 1470 { 1471 error ("loop %d%'s header does not belong directly to it", i); 1472 err = 1; 1473 } 1474 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 1475 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) 1476 { 1477 error ("loop %d%'s latch is marked as part of irreducible region", i); 1478 err = 1; 1479 } 1480 } 1481 1482 /* Check irreducible loops. */ 1483 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)) 1484 { 1485 /* Record old info. */ 1486 irreds = sbitmap_alloc (last_basic_block_for_fn (cfun)); 1487 FOR_EACH_BB_FN (bb, cfun) 1488 { 1489 edge_iterator ei; 1490 if (bb->flags & BB_IRREDUCIBLE_LOOP) 1491 bitmap_set_bit (irreds, bb->index); 1492 else 1493 bitmap_clear_bit (irreds, bb->index); 1494 FOR_EACH_EDGE (e, ei, bb->succs) 1495 if (e->flags & EDGE_IRREDUCIBLE_LOOP) 1496 e->flags |= EDGE_ALL_FLAGS + 1; 1497 } 1498 1499 /* Recount it. */ 1500 mark_irreducible_loops (); 1501 1502 /* Compare. */ 1503 FOR_EACH_BB_FN (bb, cfun) 1504 { 1505 edge_iterator ei; 1506 1507 if ((bb->flags & BB_IRREDUCIBLE_LOOP) 1508 && !bitmap_bit_p (irreds, bb->index)) 1509 { 1510 error ("basic block %d should be marked irreducible", bb->index); 1511 err = 1; 1512 } 1513 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP) 1514 && bitmap_bit_p (irreds, bb->index)) 1515 { 1516 error ("basic block %d should not be marked irreducible", bb->index); 1517 err = 1; 1518 } 1519 FOR_EACH_EDGE (e, ei, bb->succs) 1520 { 1521 if ((e->flags & EDGE_IRREDUCIBLE_LOOP) 1522 && !(e->flags & (EDGE_ALL_FLAGS + 1))) 1523 { 1524 error ("edge from %d to %d should be marked irreducible", 1525 e->src->index, e->dest->index); 1526 err = 1; 1527 } 1528 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP) 1529 && (e->flags & (EDGE_ALL_FLAGS + 1))) 1530 { 1531 error ("edge from %d to %d should not be marked irreducible", 1532 e->src->index, e->dest->index); 1533 err = 1; 1534 } 1535 e->flags &= ~(EDGE_ALL_FLAGS + 1); 1536 } 1537 } 1538 free (irreds); 1539 } 1540 1541 /* Check the recorded loop exits. */ 1542 FOR_EACH_LOOP (loop, 0) 1543 { 1544 if (!loop->exits || loop->exits->e != NULL) 1545 { 1546 error ("corrupted head of the exits list of loop %d", 1547 loop->num); 1548 err = 1; 1549 } 1550 else 1551 { 1552 /* Check that the list forms a cycle, and all elements except 1553 for the head are nonnull. */ 1554 for (mexit = loop->exits, exit = mexit->next, i = 0; 1555 exit->e && exit != mexit; 1556 exit = exit->next) 1557 { 1558 if (i++ & 1) 1559 mexit = mexit->next; 1560 } 1561 1562 if (exit != loop->exits) 1563 { 1564 error ("corrupted exits list of loop %d", loop->num); 1565 err = 1; 1566 } 1567 } 1568 1569 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1570 { 1571 if (loop->exits->next != loop->exits) 1572 { 1573 error ("nonempty exits list of loop %d, but exits are not recorded", 1574 loop->num); 1575 err = 1; 1576 } 1577 } 1578 } 1579 1580 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1581 { 1582 unsigned n_exits = 0, eloops; 1583 1584 sizes = XCNEWVEC (unsigned, num); 1585 memset (sizes, 0, sizeof (unsigned) * num); 1586 FOR_EACH_BB_FN (bb, cfun) 1587 { 1588 edge_iterator ei; 1589 if (bb->loop_father == current_loops->tree_root) 1590 continue; 1591 FOR_EACH_EDGE (e, ei, bb->succs) 1592 { 1593 if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) 1594 continue; 1595 1596 n_exits++; 1597 exit = get_exit_descriptions (e); 1598 if (!exit) 1599 { 1600 error ("exit %d->%d not recorded", 1601 e->src->index, e->dest->index); 1602 err = 1; 1603 } 1604 eloops = 0; 1605 for (; exit; exit = exit->next_e) 1606 eloops++; 1607 1608 for (loop = bb->loop_father; 1609 loop != e->dest->loop_father 1610 /* When a loop exit is also an entry edge which 1611 can happen when avoiding CFG manipulations 1612 then the last loop exited is the outer loop 1613 of the loop entered. */ 1614 && loop != loop_outer (e->dest->loop_father); 1615 loop = loop_outer (loop)) 1616 { 1617 eloops--; 1618 sizes[loop->num]++; 1619 } 1620 1621 if (eloops != 0) 1622 { 1623 error ("wrong list of exited loops for edge %d->%d", 1624 e->src->index, e->dest->index); 1625 err = 1; 1626 } 1627 } 1628 } 1629 1630 if (n_exits != current_loops->exits->elements ()) 1631 { 1632 error ("too many loop exits recorded"); 1633 err = 1; 1634 } 1635 1636 FOR_EACH_LOOP (loop, 0) 1637 { 1638 eloops = 0; 1639 for (exit = loop->exits->next; exit->e; exit = exit->next) 1640 eloops++; 1641 if (eloops != sizes[loop->num]) 1642 { 1643 error ("%d exits recorded for loop %d (having %d exits)", 1644 eloops, loop->num, sizes[loop->num]); 1645 err = 1; 1646 } 1647 } 1648 1649 free (sizes); 1650 } 1651 1652 gcc_assert (!err); 1653 1654 if (!dom_available) 1655 free_dominance_info (CDI_DOMINATORS); 1656} 1657 1658/* Returns latch edge of LOOP. */ 1659edge 1660loop_latch_edge (const struct loop *loop) 1661{ 1662 return find_edge (loop->latch, loop->header); 1663} 1664 1665/* Returns preheader edge of LOOP. */ 1666edge 1667loop_preheader_edge (const struct loop *loop) 1668{ 1669 edge e; 1670 edge_iterator ei; 1671 1672 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)); 1673 1674 FOR_EACH_EDGE (e, ei, loop->header->preds) 1675 if (e->src != loop->latch) 1676 break; 1677 1678 return e; 1679} 1680 1681/* Returns true if E is an exit of LOOP. */ 1682 1683bool 1684loop_exit_edge_p (const struct loop *loop, const_edge e) 1685{ 1686 return (flow_bb_inside_loop_p (loop, e->src) 1687 && !flow_bb_inside_loop_p (loop, e->dest)); 1688} 1689 1690/* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit 1691 or more than one exit. If loops do not have the exits recorded, NULL 1692 is returned always. */ 1693 1694edge 1695single_exit (const struct loop *loop) 1696{ 1697 struct loop_exit *exit = loop->exits->next; 1698 1699 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS)) 1700 return NULL; 1701 1702 if (exit->e && exit->next == loop->exits) 1703 return exit->e; 1704 else 1705 return NULL; 1706} 1707 1708/* Returns true when BB has an incoming edge exiting LOOP. */ 1709 1710bool 1711loop_exits_to_bb_p (struct loop *loop, basic_block bb) 1712{ 1713 edge e; 1714 edge_iterator ei; 1715 1716 FOR_EACH_EDGE (e, ei, bb->preds) 1717 if (loop_exit_edge_p (loop, e)) 1718 return true; 1719 1720 return false; 1721} 1722 1723/* Returns true when BB has an outgoing edge exiting LOOP. */ 1724 1725bool 1726loop_exits_from_bb_p (struct loop *loop, basic_block bb) 1727{ 1728 edge e; 1729 edge_iterator ei; 1730 1731 FOR_EACH_EDGE (e, ei, bb->succs) 1732 if (loop_exit_edge_p (loop, e)) 1733 return true; 1734 1735 return false; 1736} 1737 1738/* Return location corresponding to the loop control condition if possible. */ 1739 1740location_t 1741get_loop_location (struct loop *loop) 1742{ 1743 rtx_insn *insn = NULL; 1744 struct niter_desc *desc = NULL; 1745 edge exit; 1746 1747 /* For a for or while loop, we would like to return the location 1748 of the for or while statement, if possible. To do this, look 1749 for the branch guarding the loop back-edge. */ 1750 1751 /* If this is a simple loop with an in_edge, then the loop control 1752 branch is typically at the end of its source. */ 1753 desc = get_simple_loop_desc (loop); 1754 if (desc->in_edge) 1755 { 1756 FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn) 1757 { 1758 if (INSN_P (insn) && INSN_HAS_LOCATION (insn)) 1759 return INSN_LOCATION (insn); 1760 } 1761 } 1762 /* If loop has a single exit, then the loop control branch 1763 must be at the end of its source. */ 1764 if ((exit = single_exit (loop))) 1765 { 1766 FOR_BB_INSNS_REVERSE (exit->src, insn) 1767 { 1768 if (INSN_P (insn) && INSN_HAS_LOCATION (insn)) 1769 return INSN_LOCATION (insn); 1770 } 1771 } 1772 /* Next check the latch, to see if it is non-empty. */ 1773 FOR_BB_INSNS_REVERSE (loop->latch, insn) 1774 { 1775 if (INSN_P (insn) && INSN_HAS_LOCATION (insn)) 1776 return INSN_LOCATION (insn); 1777 } 1778 /* Finally, if none of the above identifies the loop control branch, 1779 return the first location in the loop header. */ 1780 FOR_BB_INSNS (loop->header, insn) 1781 { 1782 if (INSN_P (insn) && INSN_HAS_LOCATION (insn)) 1783 return INSN_LOCATION (insn); 1784 } 1785 /* If all else fails, simply return the current function location. */ 1786 return DECL_SOURCE_LOCATION (current_function_decl); 1787} 1788 1789/* Records that every statement in LOOP is executed I_BOUND times. 1790 REALISTIC is true if I_BOUND is expected to be close to the real number 1791 of iterations. UPPER is true if we are sure the loop iterates at most 1792 I_BOUND times. */ 1793 1794void 1795record_niter_bound (struct loop *loop, const widest_int &i_bound, 1796 bool realistic, bool upper) 1797{ 1798 /* Update the bounds only when there is no previous estimation, or when the 1799 current estimation is smaller. */ 1800 if (upper 1801 && (!loop->any_upper_bound 1802 || wi::ltu_p (i_bound, loop->nb_iterations_upper_bound))) 1803 { 1804 loop->any_upper_bound = true; 1805 loop->nb_iterations_upper_bound = i_bound; 1806 } 1807 if (realistic 1808 && (!loop->any_estimate 1809 || wi::ltu_p (i_bound, loop->nb_iterations_estimate))) 1810 { 1811 loop->any_estimate = true; 1812 loop->nb_iterations_estimate = i_bound; 1813 } 1814 1815 /* If an upper bound is smaller than the realistic estimate of the 1816 number of iterations, use the upper bound instead. */ 1817 if (loop->any_upper_bound 1818 && loop->any_estimate 1819 && wi::ltu_p (loop->nb_iterations_upper_bound, 1820 loop->nb_iterations_estimate)) 1821 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; 1822} 1823 1824/* Similar to get_estimated_loop_iterations, but returns the estimate only 1825 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate 1826 on the number of iterations of LOOP could not be derived, returns -1. */ 1827 1828HOST_WIDE_INT 1829get_estimated_loop_iterations_int (struct loop *loop) 1830{ 1831 widest_int nit; 1832 HOST_WIDE_INT hwi_nit; 1833 1834 if (!get_estimated_loop_iterations (loop, &nit)) 1835 return -1; 1836 1837 if (!wi::fits_shwi_p (nit)) 1838 return -1; 1839 hwi_nit = nit.to_shwi (); 1840 1841 return hwi_nit < 0 ? -1 : hwi_nit; 1842} 1843 1844/* Returns an upper bound on the number of executions of statements 1845 in the LOOP. For statements before the loop exit, this exceeds 1846 the number of execution of the latch by one. */ 1847 1848HOST_WIDE_INT 1849max_stmt_executions_int (struct loop *loop) 1850{ 1851 HOST_WIDE_INT nit = get_max_loop_iterations_int (loop); 1852 HOST_WIDE_INT snit; 1853 1854 if (nit == -1) 1855 return -1; 1856 1857 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1); 1858 1859 /* If the computation overflows, return -1. */ 1860 return snit < 0 ? -1 : snit; 1861} 1862 1863/* Sets NIT to the estimated number of executions of the latch of the 1864 LOOP. If we have no reliable estimate, the function returns false, otherwise 1865 returns true. */ 1866 1867bool 1868get_estimated_loop_iterations (struct loop *loop, widest_int *nit) 1869{ 1870 /* Even if the bound is not recorded, possibly we can derrive one from 1871 profile. */ 1872 if (!loop->any_estimate) 1873 { 1874 if (loop->header->count) 1875 { 1876 *nit = gcov_type_to_wide_int 1877 (expected_loop_iterations_unbounded (loop) + 1); 1878 return true; 1879 } 1880 return false; 1881 } 1882 1883 *nit = loop->nb_iterations_estimate; 1884 return true; 1885} 1886 1887/* Sets NIT to an upper bound for the maximum number of executions of the 1888 latch of the LOOP. If we have no reliable estimate, the function returns 1889 false, otherwise returns true. */ 1890 1891bool 1892get_max_loop_iterations (struct loop *loop, widest_int *nit) 1893{ 1894 if (!loop->any_upper_bound) 1895 return false; 1896 1897 *nit = loop->nb_iterations_upper_bound; 1898 return true; 1899} 1900 1901/* Similar to get_max_loop_iterations, but returns the estimate only 1902 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate 1903 on the number of iterations of LOOP could not be derived, returns -1. */ 1904 1905HOST_WIDE_INT 1906get_max_loop_iterations_int (struct loop *loop) 1907{ 1908 widest_int nit; 1909 HOST_WIDE_INT hwi_nit; 1910 1911 if (!get_max_loop_iterations (loop, &nit)) 1912 return -1; 1913 1914 if (!wi::fits_shwi_p (nit)) 1915 return -1; 1916 hwi_nit = nit.to_shwi (); 1917 1918 return hwi_nit < 0 ? -1 : hwi_nit; 1919} 1920 1921/* Returns the loop depth of the loop BB belongs to. */ 1922 1923int 1924bb_loop_depth (const_basic_block bb) 1925{ 1926 return bb->loop_father ? loop_depth (bb->loop_father) : 0; 1927} 1928 1929/* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */ 1930 1931void 1932mark_loop_for_removal (loop_p loop) 1933{ 1934 if (loop->header == NULL) 1935 return; 1936 loop->former_header = loop->header; 1937 loop->header = NULL; 1938 loop->latch = NULL; 1939 loops_state_set (LOOPS_NEED_FIXUP); 1940} 1941