cfganal.c revision 169689
1/* Control flow graph analysis code for GNU compiler. 2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22/* This file contains various simple utilities to analyze the CFG. */ 23#include "config.h" 24#include "system.h" 25#include "coretypes.h" 26#include "tm.h" 27#include "rtl.h" 28#include "obstack.h" 29#include "hard-reg-set.h" 30#include "basic-block.h" 31#include "insn-config.h" 32#include "recog.h" 33#include "toplev.h" 34#include "tm_p.h" 35#include "timevar.h" 36 37/* Store the data structures necessary for depth-first search. */ 38struct depth_first_search_dsS { 39 /* stack for backtracking during the algorithm */ 40 basic_block *stack; 41 42 /* number of edges in the stack. That is, positions 0, ..., sp-1 43 have edges. */ 44 unsigned int sp; 45 46 /* record of basic blocks already seen by depth-first search */ 47 sbitmap visited_blocks; 48}; 49typedef struct depth_first_search_dsS *depth_first_search_ds; 50 51static void flow_dfs_compute_reverse_init (depth_first_search_ds); 52static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds, 53 basic_block); 54static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds, 55 basic_block); 56static void flow_dfs_compute_reverse_finish (depth_first_search_ds); 57static bool flow_active_insn_p (rtx); 58 59/* Like active_insn_p, except keep the return value clobber around 60 even after reload. */ 61 62static bool 63flow_active_insn_p (rtx insn) 64{ 65 if (active_insn_p (insn)) 66 return true; 67 68 /* A clobber of the function return value exists for buggy 69 programs that fail to return a value. Its effect is to 70 keep the return value from being live across the entire 71 function. If we allow it to be skipped, we introduce the 72 possibility for register lifetime confusion. */ 73 if (GET_CODE (PATTERN (insn)) == CLOBBER 74 && REG_P (XEXP (PATTERN (insn), 0)) 75 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0))) 76 return true; 77 78 return false; 79} 80 81/* Return true if the block has no effect and only forwards control flow to 82 its single destination. */ 83 84bool 85forwarder_block_p (basic_block bb) 86{ 87 rtx insn; 88 89 if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR 90 || !single_succ_p (bb)) 91 return false; 92 93 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) 94 if (INSN_P (insn) && flow_active_insn_p (insn)) 95 return false; 96 97 return (!INSN_P (insn) 98 || (JUMP_P (insn) && simplejump_p (insn)) 99 || !flow_active_insn_p (insn)); 100} 101 102/* Return nonzero if we can reach target from src by falling through. */ 103 104bool 105can_fallthru (basic_block src, basic_block target) 106{ 107 rtx insn = BB_END (src); 108 rtx insn2; 109 edge e; 110 edge_iterator ei; 111 112 if (target == EXIT_BLOCK_PTR) 113 return true; 114 if (src->next_bb != target) 115 return 0; 116 FOR_EACH_EDGE (e, ei, src->succs) 117 if (e->dest == EXIT_BLOCK_PTR 118 && e->flags & EDGE_FALLTHRU) 119 return 0; 120 121 insn2 = BB_HEAD (target); 122 if (insn2 && !active_insn_p (insn2)) 123 insn2 = next_active_insn (insn2); 124 125 /* ??? Later we may add code to move jump tables offline. */ 126 return next_active_insn (insn) == insn2; 127} 128 129/* Return nonzero if we could reach target from src by falling through, 130 if the target was made adjacent. If we already have a fall-through 131 edge to the exit block, we can't do that. */ 132bool 133could_fall_through (basic_block src, basic_block target) 134{ 135 edge e; 136 edge_iterator ei; 137 138 if (target == EXIT_BLOCK_PTR) 139 return true; 140 FOR_EACH_EDGE (e, ei, src->succs) 141 if (e->dest == EXIT_BLOCK_PTR 142 && e->flags & EDGE_FALLTHRU) 143 return 0; 144 return true; 145} 146 147/* Mark the back edges in DFS traversal. 148 Return nonzero if a loop (natural or otherwise) is present. 149 Inspired by Depth_First_Search_PP described in: 150 151 Advanced Compiler Design and Implementation 152 Steven Muchnick 153 Morgan Kaufmann, 1997 154 155 and heavily borrowed from pre_and_rev_post_order_compute. */ 156 157bool 158mark_dfs_back_edges (void) 159{ 160 edge_iterator *stack; 161 int *pre; 162 int *post; 163 int sp; 164 int prenum = 1; 165 int postnum = 1; 166 sbitmap visited; 167 bool found = false; 168 169 /* Allocate the preorder and postorder number arrays. */ 170 pre = XCNEWVEC (int, last_basic_block); 171 post = XCNEWVEC (int, last_basic_block); 172 173 /* Allocate stack for back-tracking up CFG. */ 174 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 175 sp = 0; 176 177 /* Allocate bitmap to track nodes that have been visited. */ 178 visited = sbitmap_alloc (last_basic_block); 179 180 /* None of the nodes in the CFG have been visited yet. */ 181 sbitmap_zero (visited); 182 183 /* Push the first edge on to the stack. */ 184 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); 185 186 while (sp) 187 { 188 edge_iterator ei; 189 basic_block src; 190 basic_block dest; 191 192 /* Look at the edge on the top of the stack. */ 193 ei = stack[sp - 1]; 194 src = ei_edge (ei)->src; 195 dest = ei_edge (ei)->dest; 196 ei_edge (ei)->flags &= ~EDGE_DFS_BACK; 197 198 /* Check if the edge destination has been visited yet. */ 199 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 200 { 201 /* Mark that we have visited the destination. */ 202 SET_BIT (visited, dest->index); 203 204 pre[dest->index] = prenum++; 205 if (EDGE_COUNT (dest->succs) > 0) 206 { 207 /* Since the DEST node has been visited for the first 208 time, check its successors. */ 209 stack[sp++] = ei_start (dest->succs); 210 } 211 else 212 post[dest->index] = postnum++; 213 } 214 else 215 { 216 if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR 217 && pre[src->index] >= pre[dest->index] 218 && post[dest->index] == 0) 219 ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true; 220 221 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) 222 post[src->index] = postnum++; 223 224 if (!ei_one_before_end_p (ei)) 225 ei_next (&stack[sp - 1]); 226 else 227 sp--; 228 } 229 } 230 231 free (pre); 232 free (post); 233 free (stack); 234 sbitmap_free (visited); 235 236 return found; 237} 238 239/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */ 240 241void 242set_edge_can_fallthru_flag (void) 243{ 244 basic_block bb; 245 246 FOR_EACH_BB (bb) 247 { 248 edge e; 249 edge_iterator ei; 250 251 FOR_EACH_EDGE (e, ei, bb->succs) 252 { 253 e->flags &= ~EDGE_CAN_FALLTHRU; 254 255 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */ 256 if (e->flags & EDGE_FALLTHRU) 257 e->flags |= EDGE_CAN_FALLTHRU; 258 } 259 260 /* If the BB ends with an invertible condjump all (2) edges are 261 CAN_FALLTHRU edges. */ 262 if (EDGE_COUNT (bb->succs) != 2) 263 continue; 264 if (!any_condjump_p (BB_END (bb))) 265 continue; 266 if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0)) 267 continue; 268 invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0); 269 EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU; 270 EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU; 271 } 272} 273 274/* Find unreachable blocks. An unreachable block will have 0 in 275 the reachable bit in block->flags. A nonzero value indicates the 276 block is reachable. */ 277 278void 279find_unreachable_blocks (void) 280{ 281 edge e; 282 edge_iterator ei; 283 basic_block *tos, *worklist, bb; 284 285 tos = worklist = XNEWVEC (basic_block, n_basic_blocks); 286 287 /* Clear all the reachability flags. */ 288 289 FOR_EACH_BB (bb) 290 bb->flags &= ~BB_REACHABLE; 291 292 /* Add our starting points to the worklist. Almost always there will 293 be only one. It isn't inconceivable that we might one day directly 294 support Fortran alternate entry points. */ 295 296 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 297 { 298 *tos++ = e->dest; 299 300 /* Mark the block reachable. */ 301 e->dest->flags |= BB_REACHABLE; 302 } 303 304 /* Iterate: find everything reachable from what we've already seen. */ 305 306 while (tos != worklist) 307 { 308 basic_block b = *--tos; 309 310 FOR_EACH_EDGE (e, ei, b->succs) 311 { 312 basic_block dest = e->dest; 313 314 if (!(dest->flags & BB_REACHABLE)) 315 { 316 *tos++ = dest; 317 dest->flags |= BB_REACHABLE; 318 } 319 } 320 } 321 322 free (worklist); 323} 324 325/* Functions to access an edge list with a vector representation. 326 Enough data is kept such that given an index number, the 327 pred and succ that edge represents can be determined, or 328 given a pred and a succ, its index number can be returned. 329 This allows algorithms which consume a lot of memory to 330 represent the normally full matrix of edge (pred,succ) with a 331 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no 332 wasted space in the client code due to sparse flow graphs. */ 333 334/* This functions initializes the edge list. Basically the entire 335 flowgraph is processed, and all edges are assigned a number, 336 and the data structure is filled in. */ 337 338struct edge_list * 339create_edge_list (void) 340{ 341 struct edge_list *elist; 342 edge e; 343 int num_edges; 344 int block_count; 345 basic_block bb; 346 edge_iterator ei; 347 348 block_count = n_basic_blocks; /* Include the entry and exit blocks. */ 349 350 num_edges = 0; 351 352 /* Determine the number of edges in the flow graph by counting successor 353 edges on each basic block. */ 354 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 355 { 356 num_edges += EDGE_COUNT (bb->succs); 357 } 358 359 elist = XNEW (struct edge_list); 360 elist->num_blocks = block_count; 361 elist->num_edges = num_edges; 362 elist->index_to_edge = XNEWVEC (edge, num_edges); 363 364 num_edges = 0; 365 366 /* Follow successors of blocks, and register these edges. */ 367 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 368 FOR_EACH_EDGE (e, ei, bb->succs) 369 elist->index_to_edge[num_edges++] = e; 370 371 return elist; 372} 373 374/* This function free's memory associated with an edge list. */ 375 376void 377free_edge_list (struct edge_list *elist) 378{ 379 if (elist) 380 { 381 free (elist->index_to_edge); 382 free (elist); 383 } 384} 385 386/* This function provides debug output showing an edge list. */ 387 388void 389print_edge_list (FILE *f, struct edge_list *elist) 390{ 391 int x; 392 393 fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n", 394 elist->num_blocks, elist->num_edges); 395 396 for (x = 0; x < elist->num_edges; x++) 397 { 398 fprintf (f, " %-4d - edge(", x); 399 if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR) 400 fprintf (f, "entry,"); 401 else 402 fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index); 403 404 if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR) 405 fprintf (f, "exit)\n"); 406 else 407 fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index); 408 } 409} 410 411/* This function provides an internal consistency check of an edge list, 412 verifying that all edges are present, and that there are no 413 extra edges. */ 414 415void 416verify_edge_list (FILE *f, struct edge_list *elist) 417{ 418 int pred, succ, index; 419 edge e; 420 basic_block bb, p, s; 421 edge_iterator ei; 422 423 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 424 { 425 FOR_EACH_EDGE (e, ei, bb->succs) 426 { 427 pred = e->src->index; 428 succ = e->dest->index; 429 index = EDGE_INDEX (elist, e->src, e->dest); 430 if (index == EDGE_INDEX_NO_EDGE) 431 { 432 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ); 433 continue; 434 } 435 436 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) 437 fprintf (f, "*p* Pred for index %d should be %d not %d\n", 438 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); 439 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) 440 fprintf (f, "*p* Succ for index %d should be %d not %d\n", 441 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); 442 } 443 } 444 445 /* We've verified that all the edges are in the list, now lets make sure 446 there are no spurious edges in the list. */ 447 448 FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 449 FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) 450 { 451 int found_edge = 0; 452 453 FOR_EACH_EDGE (e, ei, p->succs) 454 if (e->dest == s) 455 { 456 found_edge = 1; 457 break; 458 } 459 460 FOR_EACH_EDGE (e, ei, s->preds) 461 if (e->src == p) 462 { 463 found_edge = 1; 464 break; 465 } 466 467 if (EDGE_INDEX (elist, p, s) 468 == EDGE_INDEX_NO_EDGE && found_edge != 0) 469 fprintf (f, "*** Edge (%d, %d) appears to not have an index\n", 470 p->index, s->index); 471 if (EDGE_INDEX (elist, p, s) 472 != EDGE_INDEX_NO_EDGE && found_edge == 0) 473 fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n", 474 p->index, s->index, EDGE_INDEX (elist, p, s)); 475 } 476} 477 478/* Given PRED and SUCC blocks, return the edge which connects the blocks. 479 If no such edge exists, return NULL. */ 480 481edge 482find_edge (basic_block pred, basic_block succ) 483{ 484 edge e; 485 edge_iterator ei; 486 487 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds)) 488 { 489 FOR_EACH_EDGE (e, ei, pred->succs) 490 if (e->dest == succ) 491 return e; 492 } 493 else 494 { 495 FOR_EACH_EDGE (e, ei, succ->preds) 496 if (e->src == pred) 497 return e; 498 } 499 500 return NULL; 501} 502 503/* This routine will determine what, if any, edge there is between 504 a specified predecessor and successor. */ 505 506int 507find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ) 508{ 509 int x; 510 511 for (x = 0; x < NUM_EDGES (edge_list); x++) 512 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred 513 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ) 514 return x; 515 516 return (EDGE_INDEX_NO_EDGE); 517} 518 519/* Dump the list of basic blocks in the bitmap NODES. */ 520 521void 522flow_nodes_print (const char *str, const sbitmap nodes, FILE *file) 523{ 524 unsigned int node = 0; 525 sbitmap_iterator sbi; 526 527 if (! nodes) 528 return; 529 530 fprintf (file, "%s { ", str); 531 EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi) 532 fprintf (file, "%d ", node); 533 fputs ("}\n", file); 534} 535 536/* Dump the list of edges in the array EDGE_LIST. */ 537 538void 539flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file) 540{ 541 int i; 542 543 if (! edge_list) 544 return; 545 546 fprintf (file, "%s { ", str); 547 for (i = 0; i < num_edges; i++) 548 fprintf (file, "%d->%d ", edge_list[i]->src->index, 549 edge_list[i]->dest->index); 550 551 fputs ("}\n", file); 552} 553 554 555/* This routine will remove any fake predecessor edges for a basic block. 556 When the edge is removed, it is also removed from whatever successor 557 list it is in. */ 558 559static void 560remove_fake_predecessors (basic_block bb) 561{ 562 edge e; 563 edge_iterator ei; 564 565 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 566 { 567 if ((e->flags & EDGE_FAKE) == EDGE_FAKE) 568 remove_edge (e); 569 else 570 ei_next (&ei); 571 } 572} 573 574/* This routine will remove all fake edges from the flow graph. If 575 we remove all fake successors, it will automatically remove all 576 fake predecessors. */ 577 578void 579remove_fake_edges (void) 580{ 581 basic_block bb; 582 583 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) 584 remove_fake_predecessors (bb); 585} 586 587/* This routine will remove all fake edges to the EXIT_BLOCK. */ 588 589void 590remove_fake_exit_edges (void) 591{ 592 remove_fake_predecessors (EXIT_BLOCK_PTR); 593} 594 595 596/* This function will add a fake edge between any block which has no 597 successors, and the exit block. Some data flow equations require these 598 edges to exist. */ 599 600void 601add_noreturn_fake_exit_edges (void) 602{ 603 basic_block bb; 604 605 FOR_EACH_BB (bb) 606 if (EDGE_COUNT (bb->succs) == 0) 607 make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 608} 609 610/* This function adds a fake edge between any infinite loops to the 611 exit block. Some optimizations require a path from each node to 612 the exit node. 613 614 See also Morgan, Figure 3.10, pp. 82-83. 615 616 The current implementation is ugly, not attempting to minimize the 617 number of inserted fake edges. To reduce the number of fake edges 618 to insert, add fake edges from _innermost_ loops containing only 619 nodes not reachable from the exit block. */ 620 621void 622connect_infinite_loops_to_exit (void) 623{ 624 basic_block unvisited_block = EXIT_BLOCK_PTR; 625 struct depth_first_search_dsS dfs_ds; 626 627 /* Perform depth-first search in the reverse graph to find nodes 628 reachable from the exit block. */ 629 flow_dfs_compute_reverse_init (&dfs_ds); 630 flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR); 631 632 /* Repeatedly add fake edges, updating the unreachable nodes. */ 633 while (1) 634 { 635 unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds, 636 unvisited_block); 637 if (!unvisited_block) 638 break; 639 640 make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE); 641 flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block); 642 } 643 644 flow_dfs_compute_reverse_finish (&dfs_ds); 645 return; 646} 647 648/* Compute reverse top sort order. 649 This is computing a post order numbering of the graph. */ 650 651int 652post_order_compute (int *post_order, bool include_entry_exit) 653{ 654 edge_iterator *stack; 655 int sp; 656 int post_order_num = 0; 657 sbitmap visited; 658 659 if (include_entry_exit) 660 post_order[post_order_num++] = EXIT_BLOCK; 661 662 /* Allocate stack for back-tracking up CFG. */ 663 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 664 sp = 0; 665 666 /* Allocate bitmap to track nodes that have been visited. */ 667 visited = sbitmap_alloc (last_basic_block); 668 669 /* None of the nodes in the CFG have been visited yet. */ 670 sbitmap_zero (visited); 671 672 /* Push the first edge on to the stack. */ 673 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); 674 675 while (sp) 676 { 677 edge_iterator ei; 678 basic_block src; 679 basic_block dest; 680 681 /* Look at the edge on the top of the stack. */ 682 ei = stack[sp - 1]; 683 src = ei_edge (ei)->src; 684 dest = ei_edge (ei)->dest; 685 686 /* Check if the edge destination has been visited yet. */ 687 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 688 { 689 /* Mark that we have visited the destination. */ 690 SET_BIT (visited, dest->index); 691 692 if (EDGE_COUNT (dest->succs) > 0) 693 /* Since the DEST node has been visited for the first 694 time, check its successors. */ 695 stack[sp++] = ei_start (dest->succs); 696 else 697 post_order[post_order_num++] = dest->index; 698 } 699 else 700 { 701 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) 702 post_order[post_order_num++] = src->index; 703 704 if (!ei_one_before_end_p (ei)) 705 ei_next (&stack[sp - 1]); 706 else 707 sp--; 708 } 709 } 710 711 if (include_entry_exit) 712 post_order[post_order_num++] = ENTRY_BLOCK; 713 714 free (stack); 715 sbitmap_free (visited); 716 return post_order_num; 717} 718 719/* Compute the depth first search order and store in the array 720 PRE_ORDER if nonzero, marking the nodes visited in VISITED. If 721 REV_POST_ORDER is nonzero, return the reverse completion number for each 722 node. Returns the number of nodes visited. A depth first search 723 tries to get as far away from the starting point as quickly as 724 possible. 725 726 pre_order is a really a preorder numbering of the graph. 727 rev_post_order is really a reverse postorder numbering of the graph. 728 */ 729 730int 731pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, 732 bool include_entry_exit) 733{ 734 edge_iterator *stack; 735 int sp; 736 int pre_order_num = 0; 737 int rev_post_order_num = n_basic_blocks - 1; 738 sbitmap visited; 739 740 /* Allocate stack for back-tracking up CFG. */ 741 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 742 sp = 0; 743 744 if (include_entry_exit) 745 { 746 if (pre_order) 747 pre_order[pre_order_num] = ENTRY_BLOCK; 748 pre_order_num++; 749 if (rev_post_order) 750 rev_post_order[rev_post_order_num--] = ENTRY_BLOCK; 751 } 752 else 753 rev_post_order_num -= NUM_FIXED_BLOCKS; 754 755 /* Allocate bitmap to track nodes that have been visited. */ 756 visited = sbitmap_alloc (last_basic_block); 757 758 /* None of the nodes in the CFG have been visited yet. */ 759 sbitmap_zero (visited); 760 761 /* Push the first edge on to the stack. */ 762 stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); 763 764 while (sp) 765 { 766 edge_iterator ei; 767 basic_block src; 768 basic_block dest; 769 770 /* Look at the edge on the top of the stack. */ 771 ei = stack[sp - 1]; 772 src = ei_edge (ei)->src; 773 dest = ei_edge (ei)->dest; 774 775 /* Check if the edge destination has been visited yet. */ 776 if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 777 { 778 /* Mark that we have visited the destination. */ 779 SET_BIT (visited, dest->index); 780 781 if (pre_order) 782 pre_order[pre_order_num] = dest->index; 783 784 pre_order_num++; 785 786 if (EDGE_COUNT (dest->succs) > 0) 787 /* Since the DEST node has been visited for the first 788 time, check its successors. */ 789 stack[sp++] = ei_start (dest->succs); 790 else if (rev_post_order) 791 /* There are no successors for the DEST node so assign 792 its reverse completion number. */ 793 rev_post_order[rev_post_order_num--] = dest->index; 794 } 795 else 796 { 797 if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR 798 && rev_post_order) 799 /* There are no more successors for the SRC node 800 so assign its reverse completion number. */ 801 rev_post_order[rev_post_order_num--] = src->index; 802 803 if (!ei_one_before_end_p (ei)) 804 ei_next (&stack[sp - 1]); 805 else 806 sp--; 807 } 808 } 809 810 free (stack); 811 sbitmap_free (visited); 812 813 if (include_entry_exit) 814 { 815 if (pre_order) 816 pre_order[pre_order_num] = EXIT_BLOCK; 817 pre_order_num++; 818 if (rev_post_order) 819 rev_post_order[rev_post_order_num--] = EXIT_BLOCK; 820 /* The number of nodes visited should be the number of blocks. */ 821 gcc_assert (pre_order_num == n_basic_blocks); 822 } 823 else 824 /* The number of nodes visited should be the number of blocks minus 825 the entry and exit blocks which are not visited here. */ 826 gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS); 827 828 return pre_order_num; 829} 830 831/* Compute the depth first search order on the _reverse_ graph and 832 store in the array DFS_ORDER, marking the nodes visited in VISITED. 833 Returns the number of nodes visited. 834 835 The computation is split into three pieces: 836 837 flow_dfs_compute_reverse_init () creates the necessary data 838 structures. 839 840 flow_dfs_compute_reverse_add_bb () adds a basic block to the data 841 structures. The block will start the search. 842 843 flow_dfs_compute_reverse_execute () continues (or starts) the 844 search using the block on the top of the stack, stopping when the 845 stack is empty. 846 847 flow_dfs_compute_reverse_finish () destroys the necessary data 848 structures. 849 850 Thus, the user will probably call ..._init(), call ..._add_bb() to 851 add a beginning basic block to the stack, call ..._execute(), 852 possibly add another bb to the stack and again call ..._execute(), 853 ..., and finally call _finish(). */ 854 855/* Initialize the data structures used for depth-first search on the 856 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is 857 added to the basic block stack. DATA is the current depth-first 858 search context. If INITIALIZE_STACK is nonzero, there is an 859 element on the stack. */ 860 861static void 862flow_dfs_compute_reverse_init (depth_first_search_ds data) 863{ 864 /* Allocate stack for back-tracking up CFG. */ 865 data->stack = XNEWVEC (basic_block, n_basic_blocks); 866 data->sp = 0; 867 868 /* Allocate bitmap to track nodes that have been visited. */ 869 data->visited_blocks = sbitmap_alloc (last_basic_block); 870 871 /* None of the nodes in the CFG have been visited yet. */ 872 sbitmap_zero (data->visited_blocks); 873 874 return; 875} 876 877/* Add the specified basic block to the top of the dfs data 878 structures. When the search continues, it will start at the 879 block. */ 880 881static void 882flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb) 883{ 884 data->stack[data->sp++] = bb; 885 SET_BIT (data->visited_blocks, bb->index); 886} 887 888/* Continue the depth-first search through the reverse graph starting with the 889 block at the stack's top and ending when the stack is empty. Visited nodes 890 are marked. Returns an unvisited basic block, or NULL if there is none 891 available. */ 892 893static basic_block 894flow_dfs_compute_reverse_execute (depth_first_search_ds data, 895 basic_block last_unvisited) 896{ 897 basic_block bb; 898 edge e; 899 edge_iterator ei; 900 901 while (data->sp > 0) 902 { 903 bb = data->stack[--data->sp]; 904 905 /* Perform depth-first search on adjacent vertices. */ 906 FOR_EACH_EDGE (e, ei, bb->preds) 907 if (!TEST_BIT (data->visited_blocks, e->src->index)) 908 flow_dfs_compute_reverse_add_bb (data, e->src); 909 } 910 911 /* Determine if there are unvisited basic blocks. */ 912 FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb) 913 if (!TEST_BIT (data->visited_blocks, bb->index)) 914 return bb; 915 916 return NULL; 917} 918 919/* Destroy the data structures needed for depth-first search on the 920 reverse graph. */ 921 922static void 923flow_dfs_compute_reverse_finish (depth_first_search_ds data) 924{ 925 free (data->stack); 926 sbitmap_free (data->visited_blocks); 927} 928 929/* Performs dfs search from BB over vertices satisfying PREDICATE; 930 if REVERSE, go against direction of edges. Returns number of blocks 931 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */ 932int 933dfs_enumerate_from (basic_block bb, int reverse, 934 bool (*predicate) (basic_block, void *), 935 basic_block *rslt, int rslt_max, void *data) 936{ 937 basic_block *st, lbb; 938 int sp = 0, tv = 0; 939 unsigned size; 940 941 /* A bitmap to keep track of visited blocks. Allocating it each time 942 this function is called is not possible, since dfs_enumerate_from 943 is often used on small (almost) disjoint parts of cfg (bodies of 944 loops), and allocating a large sbitmap would lead to quadratic 945 behavior. */ 946 static sbitmap visited; 947 static unsigned v_size; 948 949#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index)) 950#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index)) 951#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index)) 952 953 /* Resize the VISITED sbitmap if necessary. */ 954 size = last_basic_block; 955 if (size < 10) 956 size = 10; 957 958 if (!visited) 959 { 960 961 visited = sbitmap_alloc (size); 962 sbitmap_zero (visited); 963 v_size = size; 964 } 965 else if (v_size < size) 966 { 967 /* Ensure that we increase the size of the sbitmap exponentially. */ 968 if (2 * v_size > size) 969 size = 2 * v_size; 970 971 visited = sbitmap_resize (visited, size, 0); 972 v_size = size; 973 } 974 975 st = XCNEWVEC (basic_block, rslt_max); 976 rslt[tv++] = st[sp++] = bb; 977 MARK_VISITED (bb); 978 while (sp) 979 { 980 edge e; 981 edge_iterator ei; 982 lbb = st[--sp]; 983 if (reverse) 984 { 985 FOR_EACH_EDGE (e, ei, lbb->preds) 986 if (!VISITED_P (e->src) && predicate (e->src, data)) 987 { 988 gcc_assert (tv != rslt_max); 989 rslt[tv++] = st[sp++] = e->src; 990 MARK_VISITED (e->src); 991 } 992 } 993 else 994 { 995 FOR_EACH_EDGE (e, ei, lbb->succs) 996 if (!VISITED_P (e->dest) && predicate (e->dest, data)) 997 { 998 gcc_assert (tv != rslt_max); 999 rslt[tv++] = st[sp++] = e->dest; 1000 MARK_VISITED (e->dest); 1001 } 1002 } 1003 } 1004 free (st); 1005 for (sp = 0; sp < tv; sp++) 1006 UNMARK_VISITED (rslt[sp]); 1007 return tv; 1008#undef MARK_VISITED 1009#undef UNMARK_VISITED 1010#undef VISITED_P 1011} 1012 1013 1014/* Compute dominance frontiers, ala Harvey, Ferrante, et al. 1015 1016 This algorithm can be found in Timothy Harvey's PhD thesis, at 1017 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative 1018 dominance algorithms. 1019 1020 First, we identify each join point, j (any node with more than one 1021 incoming edge is a join point). 1022 1023 We then examine each predecessor, p, of j and walk up the dominator tree 1024 starting at p. 1025 1026 We stop the walk when we reach j's immediate dominator - j is in the 1027 dominance frontier of each of the nodes in the walk, except for j's 1028 immediate dominator. Intuitively, all of the rest of j's dominators are 1029 shared by j's predecessors as well. 1030 Since they dominate j, they will not have j in their dominance frontiers. 1031 1032 The number of nodes touched by this algorithm is equal to the size 1033 of the dominance frontiers, no more, no less. 1034*/ 1035 1036 1037static void 1038compute_dominance_frontiers_1 (bitmap *frontiers) 1039{ 1040 edge p; 1041 edge_iterator ei; 1042 basic_block b; 1043 FOR_EACH_BB (b) 1044 { 1045 if (EDGE_COUNT (b->preds) >= 2) 1046 { 1047 FOR_EACH_EDGE (p, ei, b->preds) 1048 { 1049 basic_block runner = p->src; 1050 basic_block domsb; 1051 if (runner == ENTRY_BLOCK_PTR) 1052 continue; 1053 1054 domsb = get_immediate_dominator (CDI_DOMINATORS, b); 1055 while (runner != domsb) 1056 { 1057 if (bitmap_bit_p (frontiers[runner->index], b->index)) 1058 break; 1059 bitmap_set_bit (frontiers[runner->index], 1060 b->index); 1061 runner = get_immediate_dominator (CDI_DOMINATORS, 1062 runner); 1063 } 1064 } 1065 } 1066 } 1067} 1068 1069 1070void 1071compute_dominance_frontiers (bitmap *frontiers) 1072{ 1073 timevar_push (TV_DOM_FRONTIERS); 1074 1075 compute_dominance_frontiers_1 (frontiers); 1076 1077 timevar_pop (TV_DOM_FRONTIERS); 1078} 1079 1080