cfg.c revision 96263
1/* Control flow graph manipulation code for GNU compiler. 2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2002 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, 59 Temple Place - Suite 330, Boston, MA 2002111-1307, USA. */ 21 22/* This file contains low level functions to manipulate the CFG and 23 analyze it. All other modules should not transform the datastructure 24 directly and use abstraction instead. The file is supposed to be 25 ordered bottom-up and should not contain any code dependent on a 26 particular intermediate language (RTL or trees). 27 28 Available functionality: 29 - Initialization/deallocation 30 init_flow, clear_edges 31 - Low level basic block manipulation 32 alloc_block, expunge_block 33 - Edge manipulation 34 make_edge, make_single_succ_edge, cached_make_edge, remove_edge 35 - Low level edge redirection (without updating instruction chain) 36 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred 37 - Dumping and debugging 38 dump_flow_info, debug_flow_info, dump_edge_info 39 - Allocation of AUX fields for basic blocks 40 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block 41 */ 42 43#include "config.h" 44#include "system.h" 45#include "tree.h" 46#include "rtl.h" 47#include "hard-reg-set.h" 48#include "basic-block.h" 49#include "regs.h" 50#include "flags.h" 51#include "output.h" 52#include "function.h" 53#include "except.h" 54#include "toplev.h" 55#include "tm_p.h" 56#include "obstack.h" 57 58/* The obstack on which the flow graph components are allocated. */ 59 60struct obstack flow_obstack; 61static char *flow_firstobj; 62 63/* Number of basic blocks in the current function. */ 64 65int n_basic_blocks; 66 67/* Number of edges in the current function. */ 68 69int n_edges; 70 71/* First edge in the deleted edges chain. */ 72 73edge first_deleted_edge; 74static basic_block first_deleted_block; 75 76/* The basic block array. */ 77 78varray_type basic_block_info; 79 80/* The special entry and exit blocks. */ 81 82struct basic_block_def entry_exit_blocks[2] 83= {{NULL, /* head */ 84 NULL, /* end */ 85 NULL, /* head_tree */ 86 NULL, /* end_tree */ 87 NULL, /* pred */ 88 NULL, /* succ */ 89 NULL, /* local_set */ 90 NULL, /* cond_local_set */ 91 NULL, /* global_live_at_start */ 92 NULL, /* global_live_at_end */ 93 NULL, /* aux */ 94 ENTRY_BLOCK, /* index */ 95 0, /* loop_depth */ 96 0, /* count */ 97 0, /* frequency */ 98 0 /* flags */ 99 }, 100 { 101 NULL, /* head */ 102 NULL, /* end */ 103 NULL, /* head_tree */ 104 NULL, /* end_tree */ 105 NULL, /* pred */ 106 NULL, /* succ */ 107 NULL, /* local_set */ 108 NULL, /* cond_local_set */ 109 NULL, /* global_live_at_start */ 110 NULL, /* global_live_at_end */ 111 NULL, /* aux */ 112 EXIT_BLOCK, /* index */ 113 0, /* loop_depth */ 114 0, /* count */ 115 0, /* frequency */ 116 0 /* flags */ 117 } 118}; 119 120void debug_flow_info PARAMS ((void)); 121static void free_edge PARAMS ((edge)); 122 123/* Called once at initialization time. */ 124 125void 126init_flow () 127{ 128 static int initialized; 129 130 first_deleted_edge = 0; 131 first_deleted_block = 0; 132 n_edges = 0; 133 134 if (!initialized) 135 { 136 gcc_obstack_init (&flow_obstack); 137 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0); 138 initialized = 1; 139 } 140 else 141 { 142 obstack_free (&flow_obstack, flow_firstobj); 143 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0); 144 } 145} 146 147/* Helper function for remove_edge and clear_edges. Frees edge structure 148 without actually unlinking it from the pred/succ lists. */ 149 150static void 151free_edge (e) 152 edge e; 153{ 154 n_edges--; 155 memset (e, 0, sizeof *e); 156 e->succ_next = first_deleted_edge; 157 first_deleted_edge = e; 158} 159 160/* Free the memory associated with the edge structures. */ 161 162void 163clear_edges () 164{ 165 int i; 166 edge e; 167 168 for (i = 0; i < n_basic_blocks; ++i) 169 { 170 basic_block bb = BASIC_BLOCK (i); 171 edge e = bb->succ; 172 173 while (e) 174 { 175 edge next = e->succ_next; 176 177 free_edge (e); 178 e = next; 179 } 180 181 bb->succ = NULL; 182 bb->pred = NULL; 183 } 184 185 e = ENTRY_BLOCK_PTR->succ; 186 while (e) 187 { 188 edge next = e->succ_next; 189 190 free_edge (e); 191 e = next; 192 } 193 194 EXIT_BLOCK_PTR->pred = NULL; 195 ENTRY_BLOCK_PTR->succ = NULL; 196 197 if (n_edges) 198 abort (); 199} 200 201/* Allocate memory for basic_block. */ 202 203basic_block 204alloc_block () 205{ 206 basic_block bb; 207 208 if (first_deleted_block) 209 { 210 bb = first_deleted_block; 211 first_deleted_block = (basic_block) bb->succ; 212 bb->succ = NULL; 213 } 214 else 215 { 216 bb = (basic_block) obstack_alloc (&flow_obstack, sizeof *bb); 217 memset (bb, 0, sizeof *bb); 218 } 219 return bb; 220} 221 222/* Remove block B from the basic block array and compact behind it. */ 223 224void 225expunge_block_nocompact (b) 226 basic_block b; 227{ 228 /* Invalidate data to make bughunting easier. */ 229 memset (b, 0, sizeof *b); 230 b->index = -3; 231 b->succ = (edge) first_deleted_block; 232 first_deleted_block = (basic_block) b; 233} 234 235void 236expunge_block (b) 237 basic_block b; 238{ 239 int i, n = n_basic_blocks; 240 241 for (i = b->index; i + 1 < n; ++i) 242 { 243 basic_block x = BASIC_BLOCK (i + 1); 244 BASIC_BLOCK (i) = x; 245 x->index = i; 246 } 247 248 n_basic_blocks--; 249 basic_block_info->num_elements--; 250 251 expunge_block_nocompact (b); 252} 253 254/* Create an edge connecting SRC and DST with FLAGS optionally using 255 edge cache CACHE. Return the new edge, NULL if already exist. */ 256 257edge 258cached_make_edge (edge_cache, src, dst, flags) 259 sbitmap *edge_cache; 260 basic_block src, dst; 261 int flags; 262{ 263 int use_edge_cache; 264 edge e; 265 266 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that 267 many edges to them, or we didn't allocate memory for it. */ 268 use_edge_cache = (edge_cache 269 && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR); 270 271 /* Make sure we don't add duplicate edges. */ 272 switch (use_edge_cache) 273 { 274 default: 275 /* Quick test for non-existence of the edge. */ 276 if (! TEST_BIT (edge_cache[src->index], dst->index)) 277 break; 278 279 /* The edge exists; early exit if no work to do. */ 280 if (flags == 0) 281 return NULL; 282 283 /* FALLTHRU */ 284 case 0: 285 for (e = src->succ; e; e = e->succ_next) 286 if (e->dest == dst) 287 { 288 e->flags |= flags; 289 return NULL; 290 } 291 break; 292 } 293 294 if (first_deleted_edge) 295 { 296 e = first_deleted_edge; 297 first_deleted_edge = e->succ_next; 298 } 299 else 300 { 301 e = (edge) obstack_alloc (&flow_obstack, sizeof *e); 302 memset (e, 0, sizeof *e); 303 } 304 n_edges++; 305 306 e->succ_next = src->succ; 307 e->pred_next = dst->pred; 308 e->src = src; 309 e->dest = dst; 310 e->flags = flags; 311 312 src->succ = e; 313 dst->pred = e; 314 315 if (use_edge_cache) 316 SET_BIT (edge_cache[src->index], dst->index); 317 318 return e; 319} 320 321/* Create an edge connecting SRC and DEST with flags FLAGS. Return newly 322 created edge or NULL if already exist. */ 323 324edge 325make_edge (src, dest, flags) 326 basic_block src, dest; 327 int flags; 328{ 329 return cached_make_edge (NULL, src, dest, flags); 330} 331 332/* Create an edge connecting SRC to DEST and set probability by knowing 333 that it is the single edge leaving SRC. */ 334 335edge 336make_single_succ_edge (src, dest, flags) 337 basic_block src, dest; 338 int flags; 339{ 340 edge e = make_edge (src, dest, flags); 341 342 e->probability = REG_BR_PROB_BASE; 343 e->count = src->count; 344 return e; 345} 346 347/* This function will remove an edge from the flow graph. */ 348 349void 350remove_edge (e) 351 edge e; 352{ 353 edge last_pred = NULL; 354 edge last_succ = NULL; 355 edge tmp; 356 basic_block src, dest; 357 358 src = e->src; 359 dest = e->dest; 360 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next) 361 last_succ = tmp; 362 363 if (!tmp) 364 abort (); 365 if (last_succ) 366 last_succ->succ_next = e->succ_next; 367 else 368 src->succ = e->succ_next; 369 370 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next) 371 last_pred = tmp; 372 373 if (!tmp) 374 abort (); 375 if (last_pred) 376 last_pred->pred_next = e->pred_next; 377 else 378 dest->pred = e->pred_next; 379 380 free_edge (e); 381} 382 383/* Redirect an edge's successor from one block to another. */ 384 385void 386redirect_edge_succ (e, new_succ) 387 edge e; 388 basic_block new_succ; 389{ 390 edge *pe; 391 392 /* Disconnect the edge from the old successor block. */ 393 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next) 394 continue; 395 *pe = (*pe)->pred_next; 396 397 /* Reconnect the edge to the new successor block. */ 398 e->pred_next = new_succ->pred; 399 new_succ->pred = e; 400 e->dest = new_succ; 401} 402 403/* Like previous but avoid possible duplicate edge. */ 404 405edge 406redirect_edge_succ_nodup (e, new_succ) 407 edge e; 408 basic_block new_succ; 409{ 410 edge s; 411 412 /* Check whether the edge is already present. */ 413 for (s = e->src->succ; s; s = s->succ_next) 414 if (s->dest == new_succ && s != e) 415 break; 416 417 if (s) 418 { 419 s->flags |= e->flags; 420 s->probability += e->probability; 421 s->count += e->count; 422 remove_edge (e); 423 e = s; 424 } 425 else 426 redirect_edge_succ (e, new_succ); 427 428 return e; 429} 430 431/* Redirect an edge's predecessor from one block to another. */ 432 433void 434redirect_edge_pred (e, new_pred) 435 edge e; 436 basic_block new_pred; 437{ 438 edge *pe; 439 440 /* Disconnect the edge from the old predecessor block. */ 441 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next) 442 continue; 443 444 *pe = (*pe)->succ_next; 445 446 /* Reconnect the edge to the new predecessor block. */ 447 e->succ_next = new_pred->succ; 448 new_pred->succ = e; 449 e->src = new_pred; 450} 451 452void 453dump_flow_info (file) 454 FILE *file; 455{ 456 int i; 457 static const char * const reg_class_names[] = REG_CLASS_NAMES; 458 459 fprintf (file, "%d registers.\n", max_regno); 460 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 461 if (REG_N_REFS (i)) 462 { 463 enum reg_class class, altclass; 464 465 fprintf (file, "\nRegister %d used %d times across %d insns", 466 i, REG_N_REFS (i), REG_LIVE_LENGTH (i)); 467 if (REG_BASIC_BLOCK (i) >= 0) 468 fprintf (file, " in block %d", REG_BASIC_BLOCK (i)); 469 if (REG_N_SETS (i)) 470 fprintf (file, "; set %d time%s", REG_N_SETS (i), 471 (REG_N_SETS (i) == 1) ? "" : "s"); 472 if (REG_USERVAR_P (regno_reg_rtx[i])) 473 fprintf (file, "; user var"); 474 if (REG_N_DEATHS (i) != 1) 475 fprintf (file, "; dies in %d places", REG_N_DEATHS (i)); 476 if (REG_N_CALLS_CROSSED (i) == 1) 477 fprintf (file, "; crosses 1 call"); 478 else if (REG_N_CALLS_CROSSED (i)) 479 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i)); 480 if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD) 481 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i)); 482 483 class = reg_preferred_class (i); 484 altclass = reg_alternate_class (i); 485 if (class != GENERAL_REGS || altclass != ALL_REGS) 486 { 487 if (altclass == ALL_REGS || class == ALL_REGS) 488 fprintf (file, "; pref %s", reg_class_names[(int) class]); 489 else if (altclass == NO_REGS) 490 fprintf (file, "; %s or none", reg_class_names[(int) class]); 491 else 492 fprintf (file, "; pref %s, else %s", 493 reg_class_names[(int) class], 494 reg_class_names[(int) altclass]); 495 } 496 497 if (REG_POINTER (regno_reg_rtx[i])) 498 fprintf (file, "; pointer"); 499 fprintf (file, ".\n"); 500 } 501 502 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges); 503 for (i = 0; i < n_basic_blocks; i++) 504 { 505 basic_block bb = BASIC_BLOCK (i); 506 edge e; 507 508 fprintf (file, "\nBasic block %d: first insn %d, last %d, ", 509 i, INSN_UID (bb->head), INSN_UID (bb->end)); 510 fprintf (file, "loop_depth %d, count ", bb->loop_depth); 511 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count); 512 fprintf (file, ", freq %i.\n", bb->frequency); 513 514 fprintf (file, "Predecessors: "); 515 for (e = bb->pred; e; e = e->pred_next) 516 dump_edge_info (file, e, 0); 517 518 fprintf (file, "\nSuccessors: "); 519 for (e = bb->succ; e; e = e->succ_next) 520 dump_edge_info (file, e, 1); 521 522 fprintf (file, "\nRegisters live at start:"); 523 dump_regset (bb->global_live_at_start, file); 524 525 fprintf (file, "\nRegisters live at end:"); 526 dump_regset (bb->global_live_at_end, file); 527 528 putc ('\n', file); 529 } 530 531 putc ('\n', file); 532} 533 534void 535debug_flow_info () 536{ 537 dump_flow_info (stderr); 538} 539 540void 541dump_edge_info (file, e, do_succ) 542 FILE *file; 543 edge e; 544 int do_succ; 545{ 546 basic_block side = (do_succ ? e->dest : e->src); 547 548 if (side == ENTRY_BLOCK_PTR) 549 fputs (" ENTRY", file); 550 else if (side == EXIT_BLOCK_PTR) 551 fputs (" EXIT", file); 552 else 553 fprintf (file, " %d", side->index); 554 555 if (e->probability) 556 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE); 557 558 if (e->count) 559 { 560 fprintf (file, " count:"); 561 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count); 562 } 563 564 if (e->flags) 565 { 566 static const char * const bitnames[] 567 = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back"}; 568 int comma = 0; 569 int i, flags = e->flags; 570 571 fputs (" (", file); 572 for (i = 0; flags; i++) 573 if (flags & (1 << i)) 574 { 575 flags &= ~(1 << i); 576 577 if (comma) 578 fputc (',', file); 579 if (i < (int) ARRAY_SIZE (bitnames)) 580 fputs (bitnames[i], file); 581 else 582 fprintf (file, "%d", i); 583 comma = 1; 584 } 585 586 fputc (')', file); 587 } 588} 589 590/* Simple routines to easily allocate AUX fields of basic blocks. */ 591 592static struct obstack block_aux_obstack; 593static void *first_block_aux_obj = 0; 594static struct obstack edge_aux_obstack; 595static void *first_edge_aux_obj = 0; 596 597/* Allocate an memory block of SIZE as BB->aux. The obstack must 598 be first initialized by alloc_aux_for_blocks. */ 599 600inline void 601alloc_aux_for_block (bb, size) 602 basic_block bb; 603 int size; 604{ 605 /* Verify that aux field is clear. */ 606 if (bb->aux || !first_block_aux_obj) 607 abort (); 608 bb->aux = obstack_alloc (&block_aux_obstack, size); 609 memset (bb->aux, 0, size); 610} 611 612/* Initialize the block_aux_obstack and if SIZE is nonzero, call 613 alloc_aux_for_block for each basic block. */ 614 615void 616alloc_aux_for_blocks (size) 617 int size; 618{ 619 static int initialized; 620 621 if (!initialized) 622 { 623 gcc_obstack_init (&block_aux_obstack); 624 initialized = 1; 625 } 626 627 /* Check whether AUX data are still allocated. */ 628 else if (first_block_aux_obj) 629 abort (); 630 first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0); 631 if (size) 632 { 633 int i; 634 635 for (i = 0; i < n_basic_blocks; i++) 636 alloc_aux_for_block (BASIC_BLOCK (i), size); 637 638 alloc_aux_for_block (ENTRY_BLOCK_PTR, size); 639 alloc_aux_for_block (EXIT_BLOCK_PTR, size); 640 } 641} 642 643/* Clear AUX pointers of all blocks. */ 644 645void 646clear_aux_for_blocks () 647{ 648 int i; 649 650 for (i = 0; i < n_basic_blocks; i++) 651 BASIC_BLOCK (i)->aux = NULL; 652 653 ENTRY_BLOCK_PTR->aux = NULL; 654 EXIT_BLOCK_PTR->aux = NULL; 655} 656 657/* Free data allocated in block_aux_obstack and clear AUX pointers 658 of all blocks. */ 659 660void 661free_aux_for_blocks () 662{ 663 if (!first_block_aux_obj) 664 abort (); 665 obstack_free (&block_aux_obstack, first_block_aux_obj); 666 first_block_aux_obj = NULL; 667 668 clear_aux_for_blocks (); 669} 670 671/* Allocate an memory edge of SIZE as BB->aux. The obstack must 672 be first initialized by alloc_aux_for_edges. */ 673 674inline void 675alloc_aux_for_edge (e, size) 676 edge e; 677 int size; 678{ 679 /* Verify that aux field is clear. */ 680 if (e->aux || !first_edge_aux_obj) 681 abort (); 682 e->aux = obstack_alloc (&edge_aux_obstack, size); 683 memset (e->aux, 0, size); 684} 685 686/* Initialize the edge_aux_obstack and if SIZE is nonzero, call 687 alloc_aux_for_edge for each basic edge. */ 688 689void 690alloc_aux_for_edges (size) 691 int size; 692{ 693 static int initialized; 694 695 if (!initialized) 696 { 697 gcc_obstack_init (&edge_aux_obstack); 698 initialized = 1; 699 } 700 701 /* Check whether AUX data are still allocated. */ 702 else if (first_edge_aux_obj) 703 abort (); 704 705 first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0); 706 if (size) 707 { 708 int i; 709 for (i = -1; i < n_basic_blocks; i++) 710 { 711 basic_block bb; 712 edge e; 713 714 if (i >= 0) 715 bb = BASIC_BLOCK (i); 716 else 717 bb = ENTRY_BLOCK_PTR; 718 719 for (e = bb->succ; e; e = e->succ_next) 720 alloc_aux_for_edge (e, size); 721 } 722 } 723} 724 725/* Clear AUX pointers of all edges. */ 726 727void 728clear_aux_for_edges () 729{ 730 int i; 731 732 for (i = -1; i < n_basic_blocks; i++) 733 { 734 basic_block bb; 735 edge e; 736 737 if (i >= 0) 738 bb = BASIC_BLOCK (i); 739 else 740 bb = ENTRY_BLOCK_PTR; 741 742 for (e = bb->succ; e; e = e->succ_next) 743 e->aux = NULL; 744 } 745} 746 747/* Free data allocated in edge_aux_obstack and clear AUX pointers 748 of all edges. */ 749 750void 751free_aux_for_edges () 752{ 753 if (!first_edge_aux_obj) 754 abort (); 755 obstack_free (&edge_aux_obstack, first_edge_aux_obj); 756 first_edge_aux_obj = NULL; 757 758 clear_aux_for_edges (); 759} 760