cfg.c revision 90075
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 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 (b) 226 basic_block b; 227{ 228 int i, n = n_basic_blocks; 229 230 for (i = b->index; i + 1 < n; ++i) 231 { 232 basic_block x = BASIC_BLOCK (i + 1); 233 BASIC_BLOCK (i) = x; 234 x->index = i; 235 } 236 237 /* Invalidate data to make bughunting easier. */ 238 memset (b, 0, sizeof *b); 239 b->index = -3; 240 basic_block_info->num_elements--; 241 n_basic_blocks--; 242 b->succ = (edge) first_deleted_block; 243 first_deleted_block = (basic_block) b; 244} 245 246/* Create an edge connecting SRC and DST with FLAGS optionally using 247 edge cache CACHE. Return the new edge, NULL if already exist. */ 248 249edge 250cached_make_edge (edge_cache, src, dst, flags) 251 sbitmap *edge_cache; 252 basic_block src, dst; 253 int flags; 254{ 255 int use_edge_cache; 256 edge e; 257 258 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that 259 many edges to them, or we didn't allocate memory for it. */ 260 use_edge_cache = (edge_cache 261 && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR); 262 263 /* Make sure we don't add duplicate edges. */ 264 switch (use_edge_cache) 265 { 266 default: 267 /* Quick test for non-existence of the edge. */ 268 if (! TEST_BIT (edge_cache[src->index], dst->index)) 269 break; 270 271 /* The edge exists; early exit if no work to do. */ 272 if (flags == 0) 273 return NULL; 274 275 /* FALLTHRU */ 276 case 0: 277 for (e = src->succ; e; e = e->succ_next) 278 if (e->dest == dst) 279 { 280 e->flags |= flags; 281 return NULL; 282 } 283 break; 284 } 285 286 if (first_deleted_edge) 287 { 288 e = first_deleted_edge; 289 first_deleted_edge = e->succ_next; 290 } 291 else 292 { 293 e = (edge) obstack_alloc (&flow_obstack, sizeof *e); 294 memset (e, 0, sizeof *e); 295 } 296 n_edges++; 297 298 e->succ_next = src->succ; 299 e->pred_next = dst->pred; 300 e->src = src; 301 e->dest = dst; 302 e->flags = flags; 303 304 src->succ = e; 305 dst->pred = e; 306 307 if (use_edge_cache) 308 SET_BIT (edge_cache[src->index], dst->index); 309 310 return e; 311} 312 313/* Create an edge connecting SRC and DEST with flags FLAGS. Return newly 314 created edge or NULL if already exist. */ 315 316edge 317make_edge (src, dest, flags) 318 basic_block src, dest; 319 int flags; 320{ 321 return cached_make_edge (NULL, src, dest, flags); 322} 323 324/* Create an edge connecting SRC to DEST and set probability by knowing 325 that it is the single edge leaving SRC. */ 326 327edge 328make_single_succ_edge (src, dest, flags) 329 basic_block src, dest; 330 int flags; 331{ 332 edge e = make_edge (src, dest, flags); 333 334 e->probability = REG_BR_PROB_BASE; 335 e->count = src->count; 336 return e; 337} 338 339/* This function will remove an edge from the flow graph. */ 340 341void 342remove_edge (e) 343 edge e; 344{ 345 edge last_pred = NULL; 346 edge last_succ = NULL; 347 edge tmp; 348 basic_block src, dest; 349 350 src = e->src; 351 dest = e->dest; 352 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next) 353 last_succ = tmp; 354 355 if (!tmp) 356 abort (); 357 if (last_succ) 358 last_succ->succ_next = e->succ_next; 359 else 360 src->succ = e->succ_next; 361 362 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next) 363 last_pred = tmp; 364 365 if (!tmp) 366 abort (); 367 if (last_pred) 368 last_pred->pred_next = e->pred_next; 369 else 370 dest->pred = e->pred_next; 371 372 free_edge (e); 373} 374 375/* Redirect an edge's successor from one block to another. */ 376 377void 378redirect_edge_succ (e, new_succ) 379 edge e; 380 basic_block new_succ; 381{ 382 edge *pe; 383 384 /* Disconnect the edge from the old successor block. */ 385 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next) 386 continue; 387 *pe = (*pe)->pred_next; 388 389 /* Reconnect the edge to the new successor block. */ 390 e->pred_next = new_succ->pred; 391 new_succ->pred = e; 392 e->dest = new_succ; 393} 394 395/* Like previous but avoid possible duplicate edge. */ 396 397edge 398redirect_edge_succ_nodup (e, new_succ) 399 edge e; 400 basic_block new_succ; 401{ 402 edge s; 403 404 /* Check whether the edge is already present. */ 405 for (s = e->src->succ; s; s = s->succ_next) 406 if (s->dest == new_succ && s != e) 407 break; 408 409 if (s) 410 { 411 s->flags |= e->flags; 412 s->probability += e->probability; 413 s->count += e->count; 414 remove_edge (e); 415 e = s; 416 } 417 else 418 redirect_edge_succ (e, new_succ); 419 420 return e; 421} 422 423/* Redirect an edge's predecessor from one block to another. */ 424 425void 426redirect_edge_pred (e, new_pred) 427 edge e; 428 basic_block new_pred; 429{ 430 edge *pe; 431 432 /* Disconnect the edge from the old predecessor block. */ 433 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next) 434 continue; 435 436 *pe = (*pe)->succ_next; 437 438 /* Reconnect the edge to the new predecessor block. */ 439 e->succ_next = new_pred->succ; 440 new_pred->succ = e; 441 e->src = new_pred; 442} 443 444void 445dump_flow_info (file) 446 FILE *file; 447{ 448 int i; 449 static const char * const reg_class_names[] = REG_CLASS_NAMES; 450 451 fprintf (file, "%d registers.\n", max_regno); 452 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 453 if (REG_N_REFS (i)) 454 { 455 enum reg_class class, altclass; 456 457 fprintf (file, "\nRegister %d used %d times across %d insns", 458 i, REG_N_REFS (i), REG_LIVE_LENGTH (i)); 459 if (REG_BASIC_BLOCK (i) >= 0) 460 fprintf (file, " in block %d", REG_BASIC_BLOCK (i)); 461 if (REG_N_SETS (i)) 462 fprintf (file, "; set %d time%s", REG_N_SETS (i), 463 (REG_N_SETS (i) == 1) ? "" : "s"); 464 if (REG_USERVAR_P (regno_reg_rtx[i])) 465 fprintf (file, "; user var"); 466 if (REG_N_DEATHS (i) != 1) 467 fprintf (file, "; dies in %d places", REG_N_DEATHS (i)); 468 if (REG_N_CALLS_CROSSED (i) == 1) 469 fprintf (file, "; crosses 1 call"); 470 else if (REG_N_CALLS_CROSSED (i)) 471 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i)); 472 if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD) 473 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i)); 474 475 class = reg_preferred_class (i); 476 altclass = reg_alternate_class (i); 477 if (class != GENERAL_REGS || altclass != ALL_REGS) 478 { 479 if (altclass == ALL_REGS || class == ALL_REGS) 480 fprintf (file, "; pref %s", reg_class_names[(int) class]); 481 else if (altclass == NO_REGS) 482 fprintf (file, "; %s or none", reg_class_names[(int) class]); 483 else 484 fprintf (file, "; pref %s, else %s", 485 reg_class_names[(int) class], 486 reg_class_names[(int) altclass]); 487 } 488 489 if (REG_POINTER (regno_reg_rtx[i])) 490 fprintf (file, "; pointer"); 491 fprintf (file, ".\n"); 492 } 493 494 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges); 495 for (i = 0; i < n_basic_blocks; i++) 496 { 497 basic_block bb = BASIC_BLOCK (i); 498 edge e; 499 500 fprintf (file, "\nBasic block %d: first insn %d, last %d, ", 501 i, INSN_UID (bb->head), INSN_UID (bb->end)); 502 fprintf (file, "loop_depth %d, count ", bb->loop_depth); 503 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count); 504 fprintf (file, ", freq %i.\n", bb->frequency); 505 506 fprintf (file, "Predecessors: "); 507 for (e = bb->pred; e; e = e->pred_next) 508 dump_edge_info (file, e, 0); 509 510 fprintf (file, "\nSuccessors: "); 511 for (e = bb->succ; e; e = e->succ_next) 512 dump_edge_info (file, e, 1); 513 514 fprintf (file, "\nRegisters live at start:"); 515 dump_regset (bb->global_live_at_start, file); 516 517 fprintf (file, "\nRegisters live at end:"); 518 dump_regset (bb->global_live_at_end, file); 519 520 putc ('\n', file); 521 } 522 523 putc ('\n', file); 524} 525 526void 527debug_flow_info () 528{ 529 dump_flow_info (stderr); 530} 531 532void 533dump_edge_info (file, e, do_succ) 534 FILE *file; 535 edge e; 536 int do_succ; 537{ 538 basic_block side = (do_succ ? e->dest : e->src); 539 540 if (side == ENTRY_BLOCK_PTR) 541 fputs (" ENTRY", file); 542 else if (side == EXIT_BLOCK_PTR) 543 fputs (" EXIT", file); 544 else 545 fprintf (file, " %d", side->index); 546 547 if (e->probability) 548 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE); 549 550 if (e->count) 551 { 552 fprintf (file, " count:"); 553 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count); 554 } 555 556 if (e->flags) 557 { 558 static const char * const bitnames[] 559 = {"fallthru", "ab", "abcall", "eh", "fake", "dfs_back"}; 560 int comma = 0; 561 int i, flags = e->flags; 562 563 fputs (" (", file); 564 for (i = 0; flags; i++) 565 if (flags & (1 << i)) 566 { 567 flags &= ~(1 << i); 568 569 if (comma) 570 fputc (',', file); 571 if (i < (int) ARRAY_SIZE (bitnames)) 572 fputs (bitnames[i], file); 573 else 574 fprintf (file, "%d", i); 575 comma = 1; 576 } 577 578 fputc (')', file); 579 } 580} 581 582/* Simple routines to easily allocate AUX fields of basic blocks. */ 583 584static struct obstack block_aux_obstack; 585static void *first_block_aux_obj = 0; 586static struct obstack edge_aux_obstack; 587static void *first_edge_aux_obj = 0; 588 589/* Allocate an memory block of SIZE as BB->aux. The obstack must 590 be first initialized by alloc_aux_for_blocks. */ 591 592inline void 593alloc_aux_for_block (bb, size) 594 basic_block bb; 595 int size; 596{ 597 /* Verify that aux field is clear. */ 598 if (bb->aux || !first_block_aux_obj) 599 abort (); 600 bb->aux = obstack_alloc (&block_aux_obstack, size); 601 memset (bb->aux, 0, size); 602} 603 604/* Initialize the block_aux_obstack and if SIZE is nonzero, call 605 alloc_aux_for_block for each basic block. */ 606 607void 608alloc_aux_for_blocks (size) 609 int size; 610{ 611 static int initialized; 612 613 if (!initialized) 614 { 615 gcc_obstack_init (&block_aux_obstack); 616 initialized = 1; 617 } 618 619 /* Check whether AUX data are still allocated. */ 620 else if (first_block_aux_obj) 621 abort (); 622 first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0); 623 if (size) 624 { 625 int i; 626 627 for (i = 0; i < n_basic_blocks; i++) 628 alloc_aux_for_block (BASIC_BLOCK (i), size); 629 630 alloc_aux_for_block (ENTRY_BLOCK_PTR, size); 631 alloc_aux_for_block (EXIT_BLOCK_PTR, size); 632 } 633} 634 635/* Clear AUX pointers of all blocks. */ 636 637void 638clear_aux_for_blocks () 639{ 640 int i; 641 642 for (i = 0; i < n_basic_blocks; i++) 643 BASIC_BLOCK (i)->aux = NULL; 644 645 ENTRY_BLOCK_PTR->aux = NULL; 646 EXIT_BLOCK_PTR->aux = NULL; 647} 648 649/* Free data allocated in block_aux_obstack and clear AUX pointers 650 of all blocks. */ 651 652void 653free_aux_for_blocks () 654{ 655 if (!first_block_aux_obj) 656 abort (); 657 obstack_free (&block_aux_obstack, first_block_aux_obj); 658 first_block_aux_obj = NULL; 659 660 clear_aux_for_blocks (); 661} 662 663/* Allocate an memory edge of SIZE as BB->aux. The obstack must 664 be first initialized by alloc_aux_for_edges. */ 665 666inline void 667alloc_aux_for_edge (e, size) 668 edge e; 669 int size; 670{ 671 /* Verify that aux field is clear. */ 672 if (e->aux || !first_edge_aux_obj) 673 abort (); 674 e->aux = obstack_alloc (&edge_aux_obstack, size); 675 memset (e->aux, 0, size); 676} 677 678/* Initialize the edge_aux_obstack and if SIZE is nonzero, call 679 alloc_aux_for_edge for each basic edge. */ 680 681void 682alloc_aux_for_edges (size) 683 int size; 684{ 685 static int initialized; 686 687 if (!initialized) 688 { 689 gcc_obstack_init (&edge_aux_obstack); 690 initialized = 1; 691 } 692 693 /* Check whether AUX data are still allocated. */ 694 else if (first_edge_aux_obj) 695 abort (); 696 697 first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0); 698 if (size) 699 { 700 int i; 701 for (i = -1; i < n_basic_blocks; i++) 702 { 703 basic_block bb; 704 edge e; 705 706 if (i >= 0) 707 bb = BASIC_BLOCK (i); 708 else 709 bb = ENTRY_BLOCK_PTR; 710 711 for (e = bb->succ; e; e = e->succ_next) 712 alloc_aux_for_edge (e, size); 713 } 714 } 715} 716 717/* Clear AUX pointers of all edges. */ 718 719void 720clear_aux_for_edges () 721{ 722 int i; 723 724 for (i = -1; i < n_basic_blocks; i++) 725 { 726 basic_block bb; 727 edge e; 728 729 if (i >= 0) 730 bb = BASIC_BLOCK (i); 731 else 732 bb = ENTRY_BLOCK_PTR; 733 734 for (e = bb->succ; e; e = e->succ_next) 735 e->aux = NULL; 736 } 737} 738 739/* Free data allocated in edge_aux_obstack and clear AUX pointers 740 of all edges. */ 741 742void 743free_aux_for_edges () 744{ 745 if (!first_edge_aux_obj) 746 abort (); 747 obstack_free (&edge_aux_obstack, first_edge_aux_obj); 748 first_edge_aux_obj = NULL; 749 750 clear_aux_for_edges (); 751} 752