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