1/* Natural loop discovery code for GNU compiler. 2 Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-1301, USA. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "rtl.h" 26#include "hard-reg-set.h" 27#include "obstack.h" 28#include "function.h" 29#include "basic-block.h" 30#include "toplev.h" 31#include "cfgloop.h" 32#include "flags.h" 33#include "tree.h" 34#include "tree-flow.h" 35 36/* Ratio of frequencies of edges so that one of more latch edges is 37 considered to belong to inner loop with same header. */ 38#define HEAVY_EDGE_RATIO 8 39 40#define HEADER_BLOCK(B) (* (int *) (B)->aux) 41#define LATCH_EDGE(E) (*(int *) (E)->aux) 42 43static void flow_loops_cfg_dump (const struct loops *, FILE *); 44static int flow_loop_level_compute (struct loop *); 45static void flow_loops_level_compute (struct loops *); 46static void establish_preds (struct loop *); 47static void canonicalize_loop_headers (void); 48static bool glb_enum_p (basic_block, void *); 49 50/* Dump loop related CFG information. */ 51 52static void 53flow_loops_cfg_dump (const struct loops *loops, FILE *file) 54{ 55 int i; 56 basic_block bb; 57 58 if (! loops->num || ! file) 59 return; 60 61 FOR_EACH_BB (bb) 62 { 63 edge succ; 64 edge_iterator ei; 65 66 fprintf (file, ";; %d succs { ", bb->index); 67 FOR_EACH_EDGE (succ, ei, bb->succs) 68 fprintf (file, "%d ", succ->dest->index); 69 fprintf (file, "}\n"); 70 } 71 72 /* Dump the DFS node order. */ 73 if (loops->cfg.dfs_order) 74 { 75 fputs (";; DFS order: ", file); 76 for (i = 0; i < n_basic_blocks; i++) 77 fprintf (file, "%d ", loops->cfg.dfs_order[i]); 78 79 fputs ("\n", file); 80 } 81 82 /* Dump the reverse completion node order. */ 83 if (loops->cfg.rc_order) 84 { 85 fputs (";; RC order: ", file); 86 for (i = 0; i < n_basic_blocks; i++) 87 fprintf (file, "%d ", loops->cfg.rc_order[i]); 88 89 fputs ("\n", file); 90 } 91} 92 93/* Return nonzero if the nodes of LOOP are a subset of OUTER. */ 94 95bool 96flow_loop_nested_p (const struct loop *outer, const struct loop *loop) 97{ 98 return (loop->depth > outer->depth 99 && loop->pred[outer->depth] == outer); 100} 101 102/* Returns the loop such that LOOP is nested DEPTH (indexed from zero) 103 loops within LOOP. */ 104 105struct loop * 106superloop_at_depth (struct loop *loop, unsigned depth) 107{ 108 gcc_assert (depth <= (unsigned) loop->depth); 109 110 if (depth == (unsigned) loop->depth) 111 return loop; 112 113 return loop->pred[depth]; 114} 115 116/* Dump the loop information specified by LOOP to the stream FILE 117 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ 118 119void 120flow_loop_dump (const struct loop *loop, FILE *file, 121 void (*loop_dump_aux) (const struct loop *, FILE *, int), 122 int verbose) 123{ 124 basic_block *bbs; 125 unsigned i; 126 127 if (! loop || ! loop->header) 128 return; 129 130 fprintf (file, ";;\n;; Loop %d:%s\n", loop->num, 131 loop->invalid ? " invalid" : ""); 132 133 fprintf (file, ";; header %d, latch %d\n", 134 loop->header->index, loop->latch->index); 135 fprintf (file, ";; depth %d, level %d, outer %ld\n", 136 loop->depth, loop->level, 137 (long) (loop->outer ? loop->outer->num : -1)); 138 139 fprintf (file, ";; nodes:"); 140 bbs = get_loop_body (loop); 141 for (i = 0; i < loop->num_nodes; i++) 142 fprintf (file, " %d", bbs[i]->index); 143 free (bbs); 144 fprintf (file, "\n"); 145 146 if (loop_dump_aux) 147 loop_dump_aux (loop, file, verbose); 148} 149 150/* Dump the loop information specified by LOOPS to the stream FILE, 151 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ 152 153void 154flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) 155{ 156 int i; 157 int num_loops; 158 159 num_loops = loops->num; 160 if (! num_loops || ! file) 161 return; 162 163 fprintf (file, ";; %d loops found\n", num_loops); 164 165 for (i = 0; i < num_loops; i++) 166 { 167 struct loop *loop = loops->parray[i]; 168 169 if (!loop) 170 continue; 171 172 flow_loop_dump (loop, file, loop_dump_aux, verbose); 173 } 174 175 if (verbose) 176 flow_loops_cfg_dump (loops, file); 177} 178 179/* Free data allocated for LOOP. */ 180void 181flow_loop_free (struct loop *loop) 182{ 183 if (loop->pred) 184 free (loop->pred); 185 free (loop); 186} 187 188/* Free all the memory allocated for LOOPS. */ 189 190void 191flow_loops_free (struct loops *loops) 192{ 193 if (loops->parray) 194 { 195 unsigned i; 196 197 gcc_assert (loops->num); 198 199 /* Free the loop descriptors. */ 200 for (i = 0; i < loops->num; i++) 201 { 202 struct loop *loop = loops->parray[i]; 203 204 if (!loop) 205 continue; 206 207 flow_loop_free (loop); 208 } 209 210 free (loops->parray); 211 loops->parray = NULL; 212 213 if (loops->cfg.dfs_order) 214 free (loops->cfg.dfs_order); 215 if (loops->cfg.rc_order) 216 free (loops->cfg.rc_order); 217 218 } 219} 220 221/* Find the nodes contained within the LOOP with header HEADER. 222 Return the number of nodes within the loop. */ 223 224int 225flow_loop_nodes_find (basic_block header, struct loop *loop) 226{ 227 basic_block *stack; 228 int sp; 229 int num_nodes = 1; 230 231 header->loop_father = loop; 232 header->loop_depth = loop->depth; 233 234 if (loop->latch->loop_father != loop) 235 { 236 stack = xmalloc (n_basic_blocks * sizeof (basic_block)); 237 sp = 0; 238 num_nodes++; 239 stack[sp++] = loop->latch; 240 loop->latch->loop_father = loop; 241 loop->latch->loop_depth = loop->depth; 242 243 while (sp) 244 { 245 basic_block node; 246 edge e; 247 edge_iterator ei; 248 249 node = stack[--sp]; 250 251 FOR_EACH_EDGE (e, ei, node->preds) 252 { 253 basic_block ancestor = e->src; 254 255 if (ancestor != ENTRY_BLOCK_PTR 256 && ancestor->loop_father != loop) 257 { 258 ancestor->loop_father = loop; 259 ancestor->loop_depth = loop->depth; 260 num_nodes++; 261 stack[sp++] = ancestor; 262 } 263 } 264 } 265 free (stack); 266 } 267 return num_nodes; 268} 269 270/* For each loop in the lOOPS tree that has just a single exit 271 record the exit edge. */ 272 273void 274mark_single_exit_loops (struct loops *loops) 275{ 276 basic_block bb; 277 edge e; 278 struct loop *loop; 279 unsigned i; 280 281 for (i = 1; i < loops->num; i++) 282 { 283 loop = loops->parray[i]; 284 if (loop) 285 loop->single_exit = NULL; 286 } 287 288 FOR_EACH_BB (bb) 289 { 290 edge_iterator ei; 291 if (bb->loop_father == loops->tree_root) 292 continue; 293 FOR_EACH_EDGE (e, ei, bb->succs) 294 { 295 if (e->dest == EXIT_BLOCK_PTR) 296 continue; 297 298 if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) 299 continue; 300 301 for (loop = bb->loop_father; 302 loop != e->dest->loop_father; 303 loop = loop->outer) 304 { 305 /* If we have already seen an exit, mark this by the edge that 306 surely does not occur as any exit. */ 307 if (loop->single_exit) 308 loop->single_exit = single_succ_edge (ENTRY_BLOCK_PTR); 309 else 310 loop->single_exit = e; 311 } 312 } 313 } 314 315 for (i = 1; i < loops->num; i++) 316 { 317 loop = loops->parray[i]; 318 if (!loop) 319 continue; 320 321 if (loop->single_exit == single_succ_edge (ENTRY_BLOCK_PTR)) 322 loop->single_exit = NULL; 323 } 324 325 loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS; 326} 327 328static void 329establish_preds (struct loop *loop) 330{ 331 struct loop *ploop, *father = loop->outer; 332 333 loop->depth = father->depth + 1; 334 335 /* Remember the current loop depth if it is the largest seen so far. */ 336 cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth); 337 338 if (loop->pred) 339 free (loop->pred); 340 loop->pred = xmalloc (sizeof (struct loop *) * loop->depth); 341 memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth); 342 loop->pred[father->depth] = father; 343 344 for (ploop = loop->inner; ploop; ploop = ploop->next) 345 establish_preds (ploop); 346} 347 348/* Add LOOP to the loop hierarchy tree where FATHER is father of the 349 added loop. If LOOP has some children, take care of that their 350 pred field will be initialized correctly. */ 351 352void 353flow_loop_tree_node_add (struct loop *father, struct loop *loop) 354{ 355 loop->next = father->inner; 356 father->inner = loop; 357 loop->outer = father; 358 359 establish_preds (loop); 360} 361 362/* Remove LOOP from the loop hierarchy tree. */ 363 364void 365flow_loop_tree_node_remove (struct loop *loop) 366{ 367 struct loop *prev, *father; 368 369 father = loop->outer; 370 loop->outer = NULL; 371 372 /* Remove loop from the list of sons. */ 373 if (father->inner == loop) 374 father->inner = loop->next; 375 else 376 { 377 for (prev = father->inner; prev->next != loop; prev = prev->next); 378 prev->next = loop->next; 379 } 380 381 loop->depth = -1; 382 free (loop->pred); 383 loop->pred = NULL; 384} 385 386/* Helper function to compute loop nesting depth and enclosed loop level 387 for the natural loop specified by LOOP. Returns the loop level. */ 388 389static int 390flow_loop_level_compute (struct loop *loop) 391{ 392 struct loop *inner; 393 int level = 1; 394 395 if (! loop) 396 return 0; 397 398 /* Traverse loop tree assigning depth and computing level as the 399 maximum level of all the inner loops of this loop. The loop 400 level is equivalent to the height of the loop in the loop tree 401 and corresponds to the number of enclosed loop levels (including 402 itself). */ 403 for (inner = loop->inner; inner; inner = inner->next) 404 { 405 int ilevel = flow_loop_level_compute (inner) + 1; 406 407 if (ilevel > level) 408 level = ilevel; 409 } 410 411 loop->level = level; 412 return level; 413} 414 415/* Compute the loop nesting depth and enclosed loop level for the loop 416 hierarchy tree specified by LOOPS. Return the maximum enclosed loop 417 level. */ 418 419static void 420flow_loops_level_compute (struct loops *loops) 421{ 422 flow_loop_level_compute (loops->tree_root); 423} 424 425/* A callback to update latch and header info for basic block JUMP created 426 by redirecting an edge. */ 427 428static void 429update_latch_info (basic_block jump) 430{ 431 alloc_aux_for_block (jump, sizeof (int)); 432 HEADER_BLOCK (jump) = 0; 433 alloc_aux_for_edge (single_pred_edge (jump), sizeof (int)); 434 LATCH_EDGE (single_pred_edge (jump)) = 0; 435 set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump)); 436} 437 438/* A callback for make_forwarder block, to redirect all edges except for 439 MFB_KJ_EDGE to the entry part. E is the edge for that we should decide 440 whether to redirect it. */ 441 442static edge mfb_kj_edge; 443static bool 444mfb_keep_just (edge e) 445{ 446 return e != mfb_kj_edge; 447} 448 449/* A callback for make_forwarder block, to redirect the latch edges into an 450 entry part. E is the edge for that we should decide whether to redirect 451 it. */ 452 453static bool 454mfb_keep_nonlatch (edge e) 455{ 456 return LATCH_EDGE (e); 457} 458 459/* Takes care of merging natural loops with shared headers. */ 460 461static void 462canonicalize_loop_headers (void) 463{ 464 basic_block header; 465 edge e; 466 467 alloc_aux_for_blocks (sizeof (int)); 468 alloc_aux_for_edges (sizeof (int)); 469 470 /* Split blocks so that each loop has only single latch. */ 471 FOR_EACH_BB (header) 472 { 473 edge_iterator ei; 474 int num_latches = 0; 475 int have_abnormal_edge = 0; 476 477 FOR_EACH_EDGE (e, ei, header->preds) 478 { 479 basic_block latch = e->src; 480 481 if (e->flags & EDGE_ABNORMAL) 482 have_abnormal_edge = 1; 483 484 if (latch != ENTRY_BLOCK_PTR 485 && dominated_by_p (CDI_DOMINATORS, latch, header)) 486 { 487 num_latches++; 488 LATCH_EDGE (e) = 1; 489 } 490 } 491 if (have_abnormal_edge) 492 HEADER_BLOCK (header) = 0; 493 else 494 HEADER_BLOCK (header) = num_latches; 495 } 496 497 if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR))) 498 { 499 basic_block bb; 500 501 /* We could not redirect edges freely here. On the other hand, 502 we can simply split the edge from entry block. */ 503 bb = split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); 504 505 alloc_aux_for_edge (single_succ_edge (bb), sizeof (int)); 506 LATCH_EDGE (single_succ_edge (bb)) = 0; 507 alloc_aux_for_block (bb, sizeof (int)); 508 HEADER_BLOCK (bb) = 0; 509 } 510 511 FOR_EACH_BB (header) 512 { 513 int max_freq, is_heavy; 514 edge heavy, tmp_edge; 515 edge_iterator ei; 516 517 if (HEADER_BLOCK (header) <= 1) 518 continue; 519 520 /* Find a heavy edge. */ 521 is_heavy = 1; 522 heavy = NULL; 523 max_freq = 0; 524 FOR_EACH_EDGE (e, ei, header->preds) 525 if (LATCH_EDGE (e) && 526 EDGE_FREQUENCY (e) > max_freq) 527 max_freq = EDGE_FREQUENCY (e); 528 FOR_EACH_EDGE (e, ei, header->preds) 529 if (LATCH_EDGE (e) && 530 EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO) 531 { 532 if (heavy) 533 { 534 is_heavy = 0; 535 break; 536 } 537 else 538 heavy = e; 539 } 540 541 if (is_heavy) 542 { 543 /* Split out the heavy edge, and create inner loop for it. */ 544 mfb_kj_edge = heavy; 545 tmp_edge = make_forwarder_block (header, mfb_keep_just, 546 update_latch_info); 547 alloc_aux_for_block (tmp_edge->dest, sizeof (int)); 548 HEADER_BLOCK (tmp_edge->dest) = 1; 549 alloc_aux_for_edge (tmp_edge, sizeof (int)); 550 LATCH_EDGE (tmp_edge) = 0; 551 HEADER_BLOCK (header)--; 552 } 553 554 if (HEADER_BLOCK (header) > 1) 555 { 556 /* Create a new latch block. */ 557 tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch, 558 update_latch_info); 559 alloc_aux_for_block (tmp_edge->dest, sizeof (int)); 560 HEADER_BLOCK (tmp_edge->src) = 0; 561 HEADER_BLOCK (tmp_edge->dest) = 1; 562 alloc_aux_for_edge (tmp_edge, sizeof (int)); 563 LATCH_EDGE (tmp_edge) = 1; 564 } 565 } 566 567 free_aux_for_blocks (); 568 free_aux_for_edges (); 569 570#ifdef ENABLE_CHECKING 571 verify_dominators (CDI_DOMINATORS); 572#endif 573} 574 575/* Initialize all the parallel_p fields of the loops structure to true. */ 576 577static void 578initialize_loops_parallel_p (struct loops *loops) 579{ 580 unsigned int i; 581 582 for (i = 0; i < loops->num; i++) 583 { 584 struct loop *loop = loops->parray[i]; 585 loop->parallel_p = true; 586 } 587} 588 589/* Find all the natural loops in the function and save in LOOPS structure and 590 recalculate loop_depth information in basic block structures. 591 Return the number of natural loops found. */ 592 593int 594flow_loops_find (struct loops *loops) 595{ 596 int b; 597 int num_loops; 598 edge e; 599 sbitmap headers; 600 int *dfs_order; 601 int *rc_order; 602 basic_block header; 603 basic_block bb; 604 605 memset (loops, 0, sizeof *loops); 606 607 /* We are going to recount the maximum loop depth, 608 so throw away the last count. */ 609 cfun->max_loop_depth = 0; 610 611 /* Taking care of this degenerate case makes the rest of 612 this code simpler. */ 613 if (n_basic_blocks == 0) 614 return 0; 615 616 dfs_order = NULL; 617 rc_order = NULL; 618 619 /* Ensure that the dominators are computed. */ 620 calculate_dominance_info (CDI_DOMINATORS); 621 622 /* Join loops with shared headers. */ 623 canonicalize_loop_headers (); 624 625 /* Count the number of loop headers. This should be the 626 same as the number of natural loops. */ 627 headers = sbitmap_alloc (last_basic_block); 628 sbitmap_zero (headers); 629 630 num_loops = 0; 631 FOR_EACH_BB (header) 632 { 633 edge_iterator ei; 634 int more_latches = 0; 635 636 header->loop_depth = 0; 637 638 /* If we have an abnormal predecessor, do not consider the 639 loop (not worth the problems). */ 640 FOR_EACH_EDGE (e, ei, header->preds) 641 if (e->flags & EDGE_ABNORMAL) 642 break; 643 if (e) 644 continue; 645 646 FOR_EACH_EDGE (e, ei, header->preds) 647 { 648 basic_block latch = e->src; 649 650 gcc_assert (!(e->flags & EDGE_ABNORMAL)); 651 652 /* Look for back edges where a predecessor is dominated 653 by this block. A natural loop has a single entry 654 node (header) that dominates all the nodes in the 655 loop. It also has single back edge to the header 656 from a latch node. */ 657 if (latch != ENTRY_BLOCK_PTR 658 && dominated_by_p (CDI_DOMINATORS, latch, header)) 659 { 660 /* Shared headers should be eliminated by now. */ 661 gcc_assert (!more_latches); 662 more_latches = 1; 663 SET_BIT (headers, header->index); 664 num_loops++; 665 } 666 } 667 } 668 669 /* Allocate loop structures. */ 670 loops->parray = xcalloc (num_loops + 1, sizeof (struct loop *)); 671 672 /* Dummy loop containing whole function. */ 673 loops->parray[0] = xcalloc (1, sizeof (struct loop)); 674 loops->parray[0]->next = NULL; 675 loops->parray[0]->inner = NULL; 676 loops->parray[0]->outer = NULL; 677 loops->parray[0]->depth = 0; 678 loops->parray[0]->pred = NULL; 679 loops->parray[0]->num_nodes = n_basic_blocks + 2; 680 loops->parray[0]->latch = EXIT_BLOCK_PTR; 681 loops->parray[0]->header = ENTRY_BLOCK_PTR; 682 ENTRY_BLOCK_PTR->loop_father = loops->parray[0]; 683 EXIT_BLOCK_PTR->loop_father = loops->parray[0]; 684 685 loops->tree_root = loops->parray[0]; 686 687 /* Find and record information about all the natural loops 688 in the CFG. */ 689 loops->num = 1; 690 FOR_EACH_BB (bb) 691 bb->loop_father = loops->tree_root; 692 693 if (num_loops) 694 { 695 /* Compute depth first search order of the CFG so that outer 696 natural loops will be found before inner natural loops. */ 697 dfs_order = xmalloc (n_basic_blocks * sizeof (int)); 698 rc_order = xmalloc (n_basic_blocks * sizeof (int)); 699 flow_depth_first_order_compute (dfs_order, rc_order); 700 701 /* Save CFG derived information to avoid recomputing it. */ 702 loops->cfg.dfs_order = dfs_order; 703 loops->cfg.rc_order = rc_order; 704 705 num_loops = 1; 706 707 for (b = 0; b < n_basic_blocks; b++) 708 { 709 struct loop *loop; 710 edge_iterator ei; 711 712 /* Search the nodes of the CFG in reverse completion order 713 so that we can find outer loops first. */ 714 if (!TEST_BIT (headers, rc_order[b])) 715 continue; 716 717 header = BASIC_BLOCK (rc_order[b]); 718 719 loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop)); 720 721 loop->header = header; 722 loop->num = num_loops; 723 num_loops++; 724 725 /* Look for the latch for this header block. */ 726 FOR_EACH_EDGE (e, ei, header->preds) 727 { 728 basic_block latch = e->src; 729 730 if (latch != ENTRY_BLOCK_PTR 731 && dominated_by_p (CDI_DOMINATORS, latch, header)) 732 { 733 loop->latch = latch; 734 break; 735 } 736 } 737 738 flow_loop_tree_node_add (header->loop_father, loop); 739 loop->num_nodes = flow_loop_nodes_find (loop->header, loop); 740 } 741 742 /* Assign the loop nesting depth and enclosed loop level for each 743 loop. */ 744 flow_loops_level_compute (loops); 745 746 loops->num = num_loops; 747 initialize_loops_parallel_p (loops); 748 } 749 750 sbitmap_free (headers); 751 752 loops->state = 0; 753#ifdef ENABLE_CHECKING 754 verify_flow_info (); 755 verify_loop_structure (loops); 756#endif 757 758 return loops->num; 759} 760 761/* Return nonzero if basic block BB belongs to LOOP. */ 762bool 763flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb) 764{ 765 struct loop *source_loop; 766 767 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) 768 return 0; 769 770 source_loop = bb->loop_father; 771 return loop == source_loop || flow_loop_nested_p (loop, source_loop); 772} 773 774/* Return nonzero if edge E enters header of LOOP from outside of LOOP. */ 775 776bool 777flow_loop_outside_edge_p (const struct loop *loop, edge e) 778{ 779 gcc_assert (e->dest == loop->header); 780 return !flow_bb_inside_loop_p (loop, e->src); 781} 782 783/* Enumeration predicate for get_loop_body. */ 784static bool 785glb_enum_p (basic_block bb, void *glb_header) 786{ 787 return bb != (basic_block) glb_header; 788} 789 790/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs 791 order against direction of edges from latch. Specially, if 792 header != latch, latch is the 1-st block. */ 793basic_block * 794get_loop_body (const struct loop *loop) 795{ 796 basic_block *tovisit, bb; 797 unsigned tv = 0; 798 799 gcc_assert (loop->num_nodes); 800 801 tovisit = xcalloc (loop->num_nodes, sizeof (basic_block)); 802 tovisit[tv++] = loop->header; 803 804 if (loop->latch == EXIT_BLOCK_PTR) 805 { 806 /* There may be blocks unreachable from EXIT_BLOCK. */ 807 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks + 2); 808 FOR_EACH_BB (bb) 809 tovisit[tv++] = bb; 810 tovisit[tv++] = EXIT_BLOCK_PTR; 811 } 812 else if (loop->latch != loop->header) 813 { 814 tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p, 815 tovisit + 1, loop->num_nodes - 1, 816 loop->header) + 1; 817 } 818 819 gcc_assert (tv == loop->num_nodes); 820 return tovisit; 821} 822 823/* Fills dominance descendants inside LOOP of the basic block BB into 824 array TOVISIT from index *TV. */ 825 826static void 827fill_sons_in_loop (const struct loop *loop, basic_block bb, 828 basic_block *tovisit, int *tv) 829{ 830 basic_block son, postpone = NULL; 831 832 tovisit[(*tv)++] = bb; 833 for (son = first_dom_son (CDI_DOMINATORS, bb); 834 son; 835 son = next_dom_son (CDI_DOMINATORS, son)) 836 { 837 if (!flow_bb_inside_loop_p (loop, son)) 838 continue; 839 840 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son)) 841 { 842 postpone = son; 843 continue; 844 } 845 fill_sons_in_loop (loop, son, tovisit, tv); 846 } 847 848 if (postpone) 849 fill_sons_in_loop (loop, postpone, tovisit, tv); 850} 851 852/* Gets body of a LOOP (that must be different from the outermost loop) 853 sorted by dominance relation. Additionally, if a basic block s dominates 854 the latch, then only blocks dominated by s are be after it. */ 855 856basic_block * 857get_loop_body_in_dom_order (const struct loop *loop) 858{ 859 basic_block *tovisit; 860 int tv; 861 862 gcc_assert (loop->num_nodes); 863 864 tovisit = xcalloc (loop->num_nodes, sizeof (basic_block)); 865 866 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 867 868 tv = 0; 869 fill_sons_in_loop (loop, loop->header, tovisit, &tv); 870 871 gcc_assert (tv == (int) loop->num_nodes); 872 873 return tovisit; 874} 875 876/* Get body of a LOOP in breadth first sort order. */ 877 878basic_block * 879get_loop_body_in_bfs_order (const struct loop *loop) 880{ 881 basic_block *blocks; 882 basic_block bb; 883 bitmap visited; 884 unsigned int i = 0; 885 unsigned int vc = 1; 886 887 gcc_assert (loop->num_nodes); 888 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 889 890 blocks = xcalloc (loop->num_nodes, sizeof (basic_block)); 891 visited = BITMAP_ALLOC (NULL); 892 893 bb = loop->header; 894 while (i < loop->num_nodes) 895 { 896 edge e; 897 edge_iterator ei; 898 899 if (!bitmap_bit_p (visited, bb->index)) 900 { 901 /* This basic block is now visited */ 902 bitmap_set_bit (visited, bb->index); 903 blocks[i++] = bb; 904 } 905 906 FOR_EACH_EDGE (e, ei, bb->succs) 907 { 908 if (flow_bb_inside_loop_p (loop, e->dest)) 909 { 910 if (!bitmap_bit_p (visited, e->dest->index)) 911 { 912 bitmap_set_bit (visited, e->dest->index); 913 blocks[i++] = e->dest; 914 } 915 } 916 } 917 918 gcc_assert (i >= vc); 919 920 bb = blocks[vc++]; 921 } 922 923 BITMAP_FREE (visited); 924 return blocks; 925} 926 927/* Gets exit edges of a LOOP, returning their number in N_EDGES. */ 928edge * 929get_loop_exit_edges (const struct loop *loop, unsigned int *num_edges) 930{ 931 edge *edges, e; 932 unsigned i, n; 933 basic_block * body; 934 edge_iterator ei; 935 936 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 937 938 body = get_loop_body (loop); 939 n = 0; 940 for (i = 0; i < loop->num_nodes; i++) 941 FOR_EACH_EDGE (e, ei, body[i]->succs) 942 if (!flow_bb_inside_loop_p (loop, e->dest)) 943 n++; 944 edges = xmalloc (n * sizeof (edge)); 945 *num_edges = n; 946 n = 0; 947 for (i = 0; i < loop->num_nodes; i++) 948 FOR_EACH_EDGE (e, ei, body[i]->succs) 949 if (!flow_bb_inside_loop_p (loop, e->dest)) 950 edges[n++] = e; 951 free (body); 952 953 return edges; 954} 955 956/* Counts the number of conditional branches inside LOOP. */ 957 958unsigned 959num_loop_branches (const struct loop *loop) 960{ 961 unsigned i, n; 962 basic_block * body; 963 964 gcc_assert (loop->latch != EXIT_BLOCK_PTR); 965 966 body = get_loop_body (loop); 967 n = 0; 968 for (i = 0; i < loop->num_nodes; i++) 969 if (EDGE_COUNT (body[i]->succs) >= 2) 970 n++; 971 free (body); 972 973 return n; 974} 975 976/* Adds basic block BB to LOOP. */ 977void 978add_bb_to_loop (basic_block bb, struct loop *loop) 979{ 980 int i; 981 982 bb->loop_father = loop; 983 bb->loop_depth = loop->depth; 984 loop->num_nodes++; 985 for (i = 0; i < loop->depth; i++) 986 loop->pred[i]->num_nodes++; 987 } 988 989/* Remove basic block BB from loops. */ 990void 991remove_bb_from_loops (basic_block bb) 992{ 993 int i; 994 struct loop *loop = bb->loop_father; 995 996 loop->num_nodes--; 997 for (i = 0; i < loop->depth; i++) 998 loop->pred[i]->num_nodes--; 999 bb->loop_father = NULL; 1000 bb->loop_depth = 0; 1001} 1002 1003/* Finds nearest common ancestor in loop tree for given loops. */ 1004struct loop * 1005find_common_loop (struct loop *loop_s, struct loop *loop_d) 1006{ 1007 if (!loop_s) return loop_d; 1008 if (!loop_d) return loop_s; 1009 1010 if (loop_s->depth < loop_d->depth) 1011 loop_d = loop_d->pred[loop_s->depth]; 1012 else if (loop_s->depth > loop_d->depth) 1013 loop_s = loop_s->pred[loop_d->depth]; 1014 1015 while (loop_s != loop_d) 1016 { 1017 loop_s = loop_s->outer; 1018 loop_d = loop_d->outer; 1019 } 1020 return loop_s; 1021} 1022 1023/* Cancels the LOOP; it must be innermost one. */ 1024void 1025cancel_loop (struct loops *loops, struct loop *loop) 1026{ 1027 basic_block *bbs; 1028 unsigned i; 1029 1030 gcc_assert (!loop->inner); 1031 1032 /* Move blocks up one level (they should be removed as soon as possible). */ 1033 bbs = get_loop_body (loop); 1034 for (i = 0; i < loop->num_nodes; i++) 1035 bbs[i]->loop_father = loop->outer; 1036 1037 /* Remove the loop from structure. */ 1038 flow_loop_tree_node_remove (loop); 1039 1040 /* Remove loop from loops array. */ 1041 loops->parray[loop->num] = NULL; 1042 1043 /* Free loop data. */ 1044 flow_loop_free (loop); 1045} 1046 1047/* Cancels LOOP and all its subloops. */ 1048void 1049cancel_loop_tree (struct loops *loops, struct loop *loop) 1050{ 1051 while (loop->inner) 1052 cancel_loop_tree (loops, loop->inner); 1053 cancel_loop (loops, loop); 1054} 1055 1056/* Checks that LOOPS are all right: 1057 -- sizes of loops are all right 1058 -- results of get_loop_body really belong to the loop 1059 -- loop header have just single entry edge and single latch edge 1060 -- loop latches have only single successor that is header of their loop 1061 -- irreducible loops are correctly marked 1062 */ 1063void 1064verify_loop_structure (struct loops *loops) 1065{ 1066 unsigned *sizes, i, j; 1067 sbitmap irreds; 1068 basic_block *bbs, bb; 1069 struct loop *loop; 1070 int err = 0; 1071 edge e; 1072 1073 /* Check sizes. */ 1074 sizes = xcalloc (loops->num, sizeof (int)); 1075 sizes[0] = 2; 1076 1077 FOR_EACH_BB (bb) 1078 for (loop = bb->loop_father; loop; loop = loop->outer) 1079 sizes[loop->num]++; 1080 1081 for (i = 0; i < loops->num; i++) 1082 { 1083 if (!loops->parray[i]) 1084 continue; 1085 1086 if (loops->parray[i]->num_nodes != sizes[i]) 1087 { 1088 error ("size of loop %d should be %d, not %d", 1089 i, sizes[i], loops->parray[i]->num_nodes); 1090 err = 1; 1091 } 1092 } 1093 1094 /* Check get_loop_body. */ 1095 for (i = 1; i < loops->num; i++) 1096 { 1097 loop = loops->parray[i]; 1098 if (!loop) 1099 continue; 1100 bbs = get_loop_body (loop); 1101 1102 for (j = 0; j < loop->num_nodes; j++) 1103 if (!flow_bb_inside_loop_p (loop, bbs[j])) 1104 { 1105 error ("bb %d do not belong to loop %d", 1106 bbs[j]->index, i); 1107 err = 1; 1108 } 1109 free (bbs); 1110 } 1111 1112 /* Check headers and latches. */ 1113 for (i = 1; i < loops->num; i++) 1114 { 1115 loop = loops->parray[i]; 1116 if (!loop) 1117 continue; 1118 1119 if ((loops->state & LOOPS_HAVE_PREHEADERS) 1120 && EDGE_COUNT (loop->header->preds) != 2) 1121 { 1122 error ("loop %d's header does not have exactly 2 entries", i); 1123 err = 1; 1124 } 1125 if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES) 1126 { 1127 if (!single_succ_p (loop->latch)) 1128 { 1129 error ("loop %d's latch does not have exactly 1 successor", i); 1130 err = 1; 1131 } 1132 if (single_succ (loop->latch) != loop->header) 1133 { 1134 error ("loop %d's latch does not have header as successor", i); 1135 err = 1; 1136 } 1137 if (loop->latch->loop_father != loop) 1138 { 1139 error ("loop %d's latch does not belong directly to it", i); 1140 err = 1; 1141 } 1142 } 1143 if (loop->header->loop_father != loop) 1144 { 1145 error ("loop %d's header does not belong directly to it", i); 1146 err = 1; 1147 } 1148 if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 1149 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) 1150 { 1151 error ("loop %d's latch is marked as part of irreducible region", i); 1152 err = 1; 1153 } 1154 } 1155 1156 /* Check irreducible loops. */ 1157 if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) 1158 { 1159 /* Record old info. */ 1160 irreds = sbitmap_alloc (last_basic_block); 1161 FOR_EACH_BB (bb) 1162 { 1163 edge_iterator ei; 1164 if (bb->flags & BB_IRREDUCIBLE_LOOP) 1165 SET_BIT (irreds, bb->index); 1166 else 1167 RESET_BIT (irreds, bb->index); 1168 FOR_EACH_EDGE (e, ei, bb->succs) 1169 if (e->flags & EDGE_IRREDUCIBLE_LOOP) 1170 e->flags |= EDGE_ALL_FLAGS + 1; 1171 } 1172 1173 /* Recount it. */ 1174 mark_irreducible_loops (loops); 1175 1176 /* Compare. */ 1177 FOR_EACH_BB (bb) 1178 { 1179 edge_iterator ei; 1180 1181 if ((bb->flags & BB_IRREDUCIBLE_LOOP) 1182 && !TEST_BIT (irreds, bb->index)) 1183 { 1184 error ("basic block %d should be marked irreducible", bb->index); 1185 err = 1; 1186 } 1187 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP) 1188 && TEST_BIT (irreds, bb->index)) 1189 { 1190 error ("basic block %d should not be marked irreducible", bb->index); 1191 err = 1; 1192 } 1193 FOR_EACH_EDGE (e, ei, bb->succs) 1194 { 1195 if ((e->flags & EDGE_IRREDUCIBLE_LOOP) 1196 && !(e->flags & (EDGE_ALL_FLAGS + 1))) 1197 { 1198 error ("edge from %d to %d should be marked irreducible", 1199 e->src->index, e->dest->index); 1200 err = 1; 1201 } 1202 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP) 1203 && (e->flags & (EDGE_ALL_FLAGS + 1))) 1204 { 1205 error ("edge from %d to %d should not be marked irreducible", 1206 e->src->index, e->dest->index); 1207 err = 1; 1208 } 1209 e->flags &= ~(EDGE_ALL_FLAGS + 1); 1210 } 1211 } 1212 free (irreds); 1213 } 1214 1215 /* Check the single_exit. */ 1216 if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) 1217 { 1218 memset (sizes, 0, sizeof (unsigned) * loops->num); 1219 FOR_EACH_BB (bb) 1220 { 1221 edge_iterator ei; 1222 if (bb->loop_father == loops->tree_root) 1223 continue; 1224 FOR_EACH_EDGE (e, ei, bb->succs) 1225 { 1226 if (e->dest == EXIT_BLOCK_PTR) 1227 continue; 1228 1229 if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) 1230 continue; 1231 1232 for (loop = bb->loop_father; 1233 loop != e->dest->loop_father; 1234 loop = loop->outer) 1235 { 1236 sizes[loop->num]++; 1237 if (loop->single_exit 1238 && loop->single_exit != e) 1239 { 1240 error ("wrong single exit %d->%d recorded for loop %d", 1241 loop->single_exit->src->index, 1242 loop->single_exit->dest->index, 1243 loop->num); 1244 error ("right exit is %d->%d", 1245 e->src->index, e->dest->index); 1246 err = 1; 1247 } 1248 } 1249 } 1250 } 1251 1252 for (i = 1; i < loops->num; i++) 1253 { 1254 loop = loops->parray[i]; 1255 if (!loop) 1256 continue; 1257 1258 if (sizes[i] == 1 1259 && !loop->single_exit) 1260 { 1261 error ("single exit not recorded for loop %d", loop->num); 1262 err = 1; 1263 } 1264 1265 if (sizes[i] != 1 1266 && loop->single_exit) 1267 { 1268 error ("loop %d should not have single exit (%d -> %d)", 1269 loop->num, 1270 loop->single_exit->src->index, 1271 loop->single_exit->dest->index); 1272 err = 1; 1273 } 1274 } 1275 } 1276 1277 gcc_assert (!err); 1278 1279 free (sizes); 1280} 1281 1282/* Returns latch edge of LOOP. */ 1283edge 1284loop_latch_edge (const struct loop *loop) 1285{ 1286 return find_edge (loop->latch, loop->header); 1287} 1288 1289/* Returns preheader edge of LOOP. */ 1290edge 1291loop_preheader_edge (const struct loop *loop) 1292{ 1293 edge e; 1294 edge_iterator ei; 1295 1296 FOR_EACH_EDGE (e, ei, loop->header->preds) 1297 if (e->src != loop->latch) 1298 break; 1299 1300 return e; 1301} 1302 1303/* Returns true if E is an exit of LOOP. */ 1304 1305bool 1306loop_exit_edge_p (const struct loop *loop, edge e) 1307{ 1308 return (flow_bb_inside_loop_p (loop, e->src) 1309 && !flow_bb_inside_loop_p (loop, e->dest)); 1310} 1311