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