cfg.c revision 132718
178189Sbrian/* Control flow graph manipulation code for GNU compiler. 278189Sbrian Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 378189Sbrian 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 478189Sbrian 578189SbrianThis file is part of GCC. 66059Samurai 778189SbrianGCC is free software; you can redistribute it and/or modify it under 878189Sbrianthe terms of the GNU General Public License as published by the Free 978189SbrianSoftware Foundation; either version 2, or (at your option) any later 1078189Sbrianversion. 1178189Sbrian 1278189SbrianGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1378189SbrianWARRANTY; without even the implied warranty of MERCHANTABILITY or 1478189SbrianFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 156059Samuraifor more details. 1678189Sbrian 1778189SbrianYou should have received a copy of the GNU General Public License 1878189Sbrianalong with GCC; see the file COPYING. If not, write to the Free 1978189SbrianSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2078189Sbrian02111-1307, USA. */ 2178189Sbrian 2278189Sbrian/* This file contains low level functions to manipulate the CFG and 2378189Sbrian analyze it. All other modules should not transform the data structure 2478189Sbrian directly and use abstraction instead. The file is supposed to be 2578189Sbrian ordered bottom-up and should not contain any code dependent on a 2678189Sbrian particular intermediate language (RTL or trees). 276059Samurai 2850479Speter Available functionality: 296059Samurai - Initialization/deallocation 306059Samurai init_flow, clear_edges 3149140Sbrian - Low level basic block manipulation 326059Samurai alloc_block, expunge_block 336059Samurai - Edge manipulation 346059Samurai make_edge, make_single_succ_edge, cached_make_edge, remove_edge 3549140Sbrian - Low level edge redirection (without updating instruction chain) 366059Samurai redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred 3747648Sbrian - Dumping and debugging 3847648Sbrian dump_flow_info, debug_flow_info, dump_edge_info 3947648Sbrian - Allocation of AUX fields for basic blocks 4081634Sbrian alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block 4181634Sbrian - clear_bb_flags 4281634Sbrian - Consistency checking 4381634Sbrian verify_flow_info 4481634Sbrian - Dumping and debugging 4547648Sbrian print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n 4649140Sbrian */ 4749140Sbrian 4849140Sbrian#include "config.h" 4949140Sbrian#include "system.h" 5049140Sbrian#include "coretypes.h" 5149140Sbrian#include "tm.h" 5249140Sbrian#include "tree.h" 5349140Sbrian#include "rtl.h" 5449140Sbrian#include "hard-reg-set.h" 556059Samurai#include "basic-block.h" 5681634Sbrian#include "regs.h" 5781634Sbrian#include "flags.h" 5849140Sbrian#include "output.h" 5949140Sbrian#include "function.h" 6058073Sbrian#include "except.h" 6158073Sbrian#include "toplev.h" 6249140Sbrian#include "tm_p.h" 6349140Sbrian#include "obstack.h" 6449140Sbrian#include "alloc-pool.h" 6549140Sbrian 6681634Sbrian/* The obstack on which the flow graph components are allocated. */ 6781634Sbrian 6849140Sbrianstruct obstack flow_obstack; 6949140Sbrianstatic char *flow_firstobj; 7062977Sbrian 716059Samurai/* Basic block object pool. */ 726059Samurai 7349140Sbrianstatic alloc_pool bb_pool; 746059Samurai 7549140Sbrian/* Edge object pool. */ 7649140Sbrian 7749140Sbrianstatic alloc_pool edge_pool; 7849140Sbrian 7949140Sbrian/* Number of basic blocks in the current function. */ 8036285Sbrian 8136285Sbrianint n_basic_blocks; 8236285Sbrian 8336285Sbrian/* First free basic block number. */ 8436285Sbrian 8536285Sbrianint last_basic_block; 8636285Sbrian 8749140Sbrian/* Number of edges in the current function. */ 887001Samurai 897001Samuraiint n_edges; 907001Samurai 917001Samurai/* The basic block array. */ 926059Samurai 9336285Sbrianvarray_type basic_block_info; 9436285Sbrian 9530715Sbrian/* The special entry and exit blocks. */ 9636285Sbrian 9736285Sbrianstruct basic_block_def entry_exit_blocks[2] 98134789Sbrian= {{NULL, /* head */ 99134789Sbrian NULL, /* end */ 10081634Sbrian NULL, /* head_tree */ 10181634Sbrian NULL, /* end_tree */ 102 NULL, /* pred */ 103 NULL, /* succ */ 104 NULL, /* local_set */ 105 NULL, /* cond_local_set */ 106 NULL, /* global_live_at_start */ 107 NULL, /* global_live_at_end */ 108 NULL, /* aux */ 109 ENTRY_BLOCK, /* index */ 110 NULL, /* prev_bb */ 111 EXIT_BLOCK_PTR, /* next_bb */ 112 0, /* loop_depth */ 113 NULL, /* loop_father */ 114 { NULL, NULL }, /* dom */ 115 0, /* count */ 116 0, /* frequency */ 117 0, /* flags */ 118 NULL /* rbi */ 119 }, 120 { 121 NULL, /* head */ 122 NULL, /* end */ 123 NULL, /* head_tree */ 124 NULL, /* end_tree */ 125 NULL, /* pred */ 126 NULL, /* succ */ 127 NULL, /* local_set */ 128 NULL, /* cond_local_set */ 129 NULL, /* global_live_at_start */ 130 NULL, /* global_live_at_end */ 131 NULL, /* aux */ 132 EXIT_BLOCK, /* index */ 133 ENTRY_BLOCK_PTR, /* prev_bb */ 134 NULL, /* next_bb */ 135 0, /* loop_depth */ 136 NULL, /* loop_father */ 137 { NULL, NULL }, /* dom */ 138 0, /* count */ 139 0, /* frequency */ 140 0, /* flags */ 141 NULL /* rbi */ 142 } 143}; 144 145void debug_flow_info (void); 146static void free_edge (edge); 147 148/* Called once at initialization time. */ 149 150void 151init_flow (void) 152{ 153 static int initialized; 154 155 n_edges = 0; 156 157 if (!initialized) 158 { 159 gcc_obstack_init (&flow_obstack); 160 flow_firstobj = obstack_alloc (&flow_obstack, 0); 161 initialized = 1; 162 } 163 else 164 { 165 free_alloc_pool (bb_pool); 166 free_alloc_pool (edge_pool); 167 obstack_free (&flow_obstack, flow_firstobj); 168 flow_firstobj = obstack_alloc (&flow_obstack, 0); 169 } 170 bb_pool = create_alloc_pool ("Basic block pool", 171 sizeof (struct basic_block_def), 100); 172 edge_pool = create_alloc_pool ("Edge pool", 173 sizeof (struct edge_def), 100); 174} 175 176/* Helper function for remove_edge and clear_edges. Frees edge structure 177 without actually unlinking it from the pred/succ lists. */ 178 179static void 180free_edge (edge e) 181{ 182 n_edges--; 183 pool_free (edge_pool, e); 184} 185 186/* Free the memory associated with the edge structures. */ 187 188void 189clear_edges (void) 190{ 191 basic_block bb; 192 edge e; 193 194 FOR_EACH_BB (bb) 195 { 196 edge e = bb->succ; 197 198 while (e) 199 { 200 edge next = e->succ_next; 201 202 free_edge (e); 203 e = next; 204 } 205 206 bb->succ = NULL; 207 bb->pred = NULL; 208 } 209 210 e = ENTRY_BLOCK_PTR->succ; 211 while (e) 212 { 213 edge next = e->succ_next; 214 215 free_edge (e); 216 e = next; 217 } 218 219 EXIT_BLOCK_PTR->pred = NULL; 220 ENTRY_BLOCK_PTR->succ = NULL; 221 222 if (n_edges) 223 abort (); 224} 225 226/* Allocate memory for basic_block. */ 227 228basic_block 229alloc_block (void) 230{ 231 basic_block bb; 232 bb = pool_alloc (bb_pool); 233 memset (bb, 0, sizeof (*bb)); 234 return bb; 235} 236 237/* Link block B to chain after AFTER. */ 238void 239link_block (basic_block b, basic_block after) 240{ 241 b->next_bb = after->next_bb; 242 b->prev_bb = after; 243 after->next_bb = b; 244 b->next_bb->prev_bb = b; 245} 246 247/* Unlink block B from chain. */ 248void 249unlink_block (basic_block b) 250{ 251 b->next_bb->prev_bb = b->prev_bb; 252 b->prev_bb->next_bb = b->next_bb; 253} 254 255/* Sequentially order blocks and compact the arrays. */ 256void 257compact_blocks (void) 258{ 259 int i; 260 basic_block bb; 261 262 i = 0; 263 FOR_EACH_BB (bb) 264 { 265 BASIC_BLOCK (i) = bb; 266 bb->index = i; 267 i++; 268 } 269 270 if (i != n_basic_blocks) 271 abort (); 272 273 last_basic_block = n_basic_blocks; 274} 275 276/* Remove block B from the basic block array. */ 277 278void 279expunge_block (basic_block b) 280{ 281 unlink_block (b); 282 BASIC_BLOCK (b->index) = NULL; 283 n_basic_blocks--; 284 pool_free (bb_pool, b); 285} 286 287/* Create an edge connecting SRC and DEST with flags FLAGS. Return newly 288 created edge. Use this only if you are sure that this edge can't 289 possibly already exist. */ 290 291edge 292unchecked_make_edge (basic_block src, basic_block dst, int flags) 293{ 294 edge e; 295 e = pool_alloc (edge_pool); 296 memset (e, 0, sizeof (*e)); 297 n_edges++; 298 299 e->succ_next = src->succ; 300 e->pred_next = dst->pred; 301 e->src = src; 302 e->dest = dst; 303 e->flags = flags; 304 305 src->succ = e; 306 dst->pred = e; 307 308 return e; 309} 310 311/* Create an edge connecting SRC and DST with FLAGS optionally using 312 edge cache CACHE. Return the new edge, NULL if already exist. */ 313 314edge 315cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags) 316{ 317 int use_edge_cache; 318 edge e; 319 320 /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that 321 many edges to them, or we didn't allocate memory for it. */ 322 use_edge_cache = (edge_cache 323 && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR); 324 325 /* Make sure we don't add duplicate edges. */ 326 switch (use_edge_cache) 327 { 328 default: 329 /* Quick test for non-existence of the edge. */ 330 if (! TEST_BIT (edge_cache[src->index], dst->index)) 331 break; 332 333 /* The edge exists; early exit if no work to do. */ 334 if (flags == 0) 335 return NULL; 336 337 /* Fall through. */ 338 case 0: 339 for (e = src->succ; e; e = e->succ_next) 340 if (e->dest == dst) 341 { 342 e->flags |= flags; 343 return NULL; 344 } 345 break; 346 } 347 348 e = unchecked_make_edge (src, dst, flags); 349 350 if (use_edge_cache) 351 SET_BIT (edge_cache[src->index], dst->index); 352 353 return e; 354} 355 356/* Create an edge connecting SRC and DEST with flags FLAGS. Return newly 357 created edge or NULL if already exist. */ 358 359edge 360make_edge (basic_block src, basic_block dest, int flags) 361{ 362 return cached_make_edge (NULL, src, dest, flags); 363} 364 365/* Create an edge connecting SRC to DEST and set probability by knowing 366 that it is the single edge leaving SRC. */ 367 368edge 369make_single_succ_edge (basic_block src, basic_block dest, int flags) 370{ 371 edge e = make_edge (src, dest, flags); 372 373 e->probability = REG_BR_PROB_BASE; 374 e->count = src->count; 375 return e; 376} 377 378/* This function will remove an edge from the flow graph. */ 379 380void 381remove_edge (edge e) 382{ 383 edge last_pred = NULL; 384 edge last_succ = NULL; 385 edge tmp; 386 basic_block src, dest; 387 388 src = e->src; 389 dest = e->dest; 390 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next) 391 last_succ = tmp; 392 393 if (!tmp) 394 abort (); 395 if (last_succ) 396 last_succ->succ_next = e->succ_next; 397 else 398 src->succ = e->succ_next; 399 400 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next) 401 last_pred = tmp; 402 403 if (!tmp) 404 abort (); 405 if (last_pred) 406 last_pred->pred_next = e->pred_next; 407 else 408 dest->pred = e->pred_next; 409 410 free_edge (e); 411} 412 413/* Redirect an edge's successor from one block to another. */ 414 415void 416redirect_edge_succ (edge e, basic_block new_succ) 417{ 418 edge *pe; 419 420 /* Disconnect the edge from the old successor block. */ 421 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next) 422 continue; 423 *pe = (*pe)->pred_next; 424 425 /* Reconnect the edge to the new successor block. */ 426 e->pred_next = new_succ->pred; 427 new_succ->pred = e; 428 e->dest = new_succ; 429} 430 431/* Like previous but avoid possible duplicate edge. */ 432 433edge 434redirect_edge_succ_nodup (edge e, basic_block new_succ) 435{ 436 edge s; 437 438 /* Check whether the edge is already present. */ 439 for (s = e->src->succ; s; s = s->succ_next) 440 if (s->dest == new_succ && s != e) 441 break; 442 443 if (s) 444 { 445 s->flags |= e->flags; 446 s->probability += e->probability; 447 if (s->probability > REG_BR_PROB_BASE) 448 s->probability = REG_BR_PROB_BASE; 449 s->count += e->count; 450 remove_edge (e); 451 e = s; 452 } 453 else 454 redirect_edge_succ (e, new_succ); 455 456 return e; 457} 458 459/* Redirect an edge's predecessor from one block to another. */ 460 461void 462redirect_edge_pred (edge e, basic_block new_pred) 463{ 464 edge *pe; 465 466 /* Disconnect the edge from the old predecessor block. */ 467 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next) 468 continue; 469 470 *pe = (*pe)->succ_next; 471 472 /* Reconnect the edge to the new predecessor block. */ 473 e->succ_next = new_pred->succ; 474 new_pred->succ = e; 475 e->src = new_pred; 476} 477 478void 479clear_bb_flags (void) 480{ 481 basic_block bb; 482 483 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 484 bb->flags = 0; 485} 486 487void 488dump_flow_info (FILE *file) 489{ 490 int i; 491 int max_regno = max_reg_num (); 492 basic_block bb; 493 static const char * const reg_class_names[] = REG_CLASS_NAMES; 494 495 fprintf (file, "%d registers.\n", max_regno); 496 if (reg_n_info) 497 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 498 if (REG_N_REFS (i)) 499 { 500 enum reg_class class, altclass; 501 502 fprintf (file, "\nRegister %d used %d times across %d insns", 503 i, REG_N_REFS (i), REG_LIVE_LENGTH (i)); 504 if (REG_BASIC_BLOCK (i) >= 0) 505 fprintf (file, " in block %d", REG_BASIC_BLOCK (i)); 506 if (REG_N_SETS (i)) 507 fprintf (file, "; set %d time%s", REG_N_SETS (i), 508 (REG_N_SETS (i) == 1) ? "" : "s"); 509 if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i])) 510 fprintf (file, "; user var"); 511 if (REG_N_DEATHS (i) != 1) 512 fprintf (file, "; dies in %d places", REG_N_DEATHS (i)); 513 if (REG_N_CALLS_CROSSED (i) == 1) 514 fprintf (file, "; crosses 1 call"); 515 else if (REG_N_CALLS_CROSSED (i)) 516 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i)); 517 if (regno_reg_rtx[i] != NULL 518 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD) 519 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i)); 520 521 class = reg_preferred_class (i); 522 altclass = reg_alternate_class (i); 523 if (class != GENERAL_REGS || altclass != ALL_REGS) 524 { 525 if (altclass == ALL_REGS || class == ALL_REGS) 526 fprintf (file, "; pref %s", reg_class_names[(int) class]); 527 else if (altclass == NO_REGS) 528 fprintf (file, "; %s or none", reg_class_names[(int) class]); 529 else 530 fprintf (file, "; pref %s, else %s", 531 reg_class_names[(int) class], 532 reg_class_names[(int) altclass]); 533 } 534 535 if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i])) 536 fprintf (file, "; pointer"); 537 fprintf (file, ".\n"); 538 } 539 540 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges); 541 FOR_EACH_BB (bb) 542 { 543 edge e; 544 int sum; 545 gcov_type lsum; 546 547 fprintf (file, "\nBasic block %d: first insn %d, last %d, ", 548 bb->index, INSN_UID (BB_HEAD (bb)), INSN_UID (BB_END (bb))); 549 fprintf (file, "prev %d, next %d, ", 550 bb->prev_bb->index, bb->next_bb->index); 551 fprintf (file, "loop_depth %d, count ", bb->loop_depth); 552 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count); 553 fprintf (file, ", freq %i", bb->frequency); 554 if (maybe_hot_bb_p (bb)) 555 fprintf (file, ", maybe hot"); 556 if (probably_never_executed_bb_p (bb)) 557 fprintf (file, ", probably never executed"); 558 fprintf (file, ".\n"); 559 560 fprintf (file, "Predecessors: "); 561 for (e = bb->pred; e; e = e->pred_next) 562 dump_edge_info (file, e, 0); 563 564 fprintf (file, "\nSuccessors: "); 565 for (e = bb->succ; e; e = e->succ_next) 566 dump_edge_info (file, e, 1); 567 568 fprintf (file, "\nRegisters live at start:"); 569 dump_regset (bb->global_live_at_start, file); 570 571 fprintf (file, "\nRegisters live at end:"); 572 dump_regset (bb->global_live_at_end, file); 573 574 putc ('\n', file); 575 576 /* Check the consistency of profile information. We can't do that 577 in verify_flow_info, as the counts may get invalid for incompletely 578 solved graphs, later eliminating of conditionals or roundoff errors. 579 It is still practical to have them reported for debugging of simple 580 testcases. */ 581 sum = 0; 582 for (e = bb->succ; e; e = e->succ_next) 583 sum += e->probability; 584 if (bb->succ && abs (sum - REG_BR_PROB_BASE) > 100) 585 fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n", 586 sum * 100.0 / REG_BR_PROB_BASE); 587 sum = 0; 588 for (e = bb->pred; e; e = e->pred_next) 589 sum += EDGE_FREQUENCY (e); 590 if (abs (sum - bb->frequency) > 100) 591 fprintf (file, 592 "Invalid sum of incomming frequencies %i, should be %i\n", 593 sum, bb->frequency); 594 lsum = 0; 595 for (e = bb->pred; e; e = e->pred_next) 596 lsum += e->count; 597 if (lsum - bb->count > 100 || lsum - bb->count < -100) 598 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n", 599 (int)lsum, (int)bb->count); 600 lsum = 0; 601 for (e = bb->succ; e; e = e->succ_next) 602 lsum += e->count; 603 if (bb->succ && (lsum - bb->count > 100 || lsum - bb->count < -100)) 604 fprintf (file, "Invalid sum of incomming counts %i, should be %i\n", 605 (int)lsum, (int)bb->count); 606 } 607 608 putc ('\n', file); 609} 610 611void 612debug_flow_info (void) 613{ 614 dump_flow_info (stderr); 615} 616 617void 618dump_edge_info (FILE *file, edge e, int do_succ) 619{ 620 basic_block side = (do_succ ? e->dest : e->src); 621 622 if (side == ENTRY_BLOCK_PTR) 623 fputs (" ENTRY", file); 624 else if (side == EXIT_BLOCK_PTR) 625 fputs (" EXIT", file); 626 else 627 fprintf (file, " %d", side->index); 628 629 if (e->probability) 630 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE); 631 632 if (e->count) 633 { 634 fprintf (file, " count:"); 635 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count); 636 } 637 638 if (e->flags) 639 { 640 static const char * const bitnames[] = { 641 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back", 642 "can_fallthru", "irreducible", "sibcall", "loop_exit" 643 }; 644 int comma = 0; 645 int i, flags = e->flags; 646 647 fputs (" (", file); 648 for (i = 0; flags; i++) 649 if (flags & (1 << i)) 650 { 651 flags &= ~(1 << i); 652 653 if (comma) 654 fputc (',', file); 655 if (i < (int) ARRAY_SIZE (bitnames)) 656 fputs (bitnames[i], file); 657 else 658 fprintf (file, "%d", i); 659 comma = 1; 660 } 661 662 fputc (')', file); 663 } 664} 665 666/* Simple routines to easily allocate AUX fields of basic blocks. */ 667 668static struct obstack block_aux_obstack; 669static void *first_block_aux_obj = 0; 670static struct obstack edge_aux_obstack; 671static void *first_edge_aux_obj = 0; 672 673/* Allocate a memory block of SIZE as BB->aux. The obstack must 674 be first initialized by alloc_aux_for_blocks. */ 675 676inline void 677alloc_aux_for_block (basic_block bb, int size) 678{ 679 /* Verify that aux field is clear. */ 680 if (bb->aux || !first_block_aux_obj) 681 abort (); 682 bb->aux = obstack_alloc (&block_aux_obstack, size); 683 memset (bb->aux, 0, size); 684} 685 686/* Initialize the block_aux_obstack and if SIZE is nonzero, call 687 alloc_aux_for_block for each basic block. */ 688 689void 690alloc_aux_for_blocks (int size) 691{ 692 static int initialized; 693 694 if (!initialized) 695 { 696 gcc_obstack_init (&block_aux_obstack); 697 initialized = 1; 698 } 699 700 /* Check whether AUX data are still allocated. */ 701 else if (first_block_aux_obj) 702 abort (); 703 first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0); 704 if (size) 705 { 706 basic_block bb; 707 708 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 709 alloc_aux_for_block (bb, size); 710 } 711} 712 713/* Clear AUX pointers of all blocks. */ 714 715void 716clear_aux_for_blocks (void) 717{ 718 basic_block bb; 719 720 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 721 bb->aux = NULL; 722} 723 724/* Free data allocated in block_aux_obstack and clear AUX pointers 725 of all blocks. */ 726 727void 728free_aux_for_blocks (void) 729{ 730 if (!first_block_aux_obj) 731 abort (); 732 obstack_free (&block_aux_obstack, first_block_aux_obj); 733 first_block_aux_obj = NULL; 734 735 clear_aux_for_blocks (); 736} 737 738/* Allocate a memory edge of SIZE as BB->aux. The obstack must 739 be first initialized by alloc_aux_for_edges. */ 740 741inline void 742alloc_aux_for_edge (edge e, int size) 743{ 744 /* Verify that aux field is clear. */ 745 if (e->aux || !first_edge_aux_obj) 746 abort (); 747 e->aux = obstack_alloc (&edge_aux_obstack, size); 748 memset (e->aux, 0, size); 749} 750 751/* Initialize the edge_aux_obstack and if SIZE is nonzero, call 752 alloc_aux_for_edge for each basic edge. */ 753 754void 755alloc_aux_for_edges (int size) 756{ 757 static int initialized; 758 759 if (!initialized) 760 { 761 gcc_obstack_init (&edge_aux_obstack); 762 initialized = 1; 763 } 764 765 /* Check whether AUX data are still allocated. */ 766 else if (first_edge_aux_obj) 767 abort (); 768 769 first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0); 770 if (size) 771 { 772 basic_block bb; 773 774 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 775 { 776 edge e; 777 778 for (e = bb->succ; e; e = e->succ_next) 779 alloc_aux_for_edge (e, size); 780 } 781 } 782} 783 784/* Clear AUX pointers of all edges. */ 785 786void 787clear_aux_for_edges (void) 788{ 789 basic_block bb; 790 edge e; 791 792 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 793 { 794 for (e = bb->succ; e; e = e->succ_next) 795 e->aux = NULL; 796 } 797} 798 799/* Free data allocated in edge_aux_obstack and clear AUX pointers 800 of all edges. */ 801 802void 803free_aux_for_edges (void) 804{ 805 if (!first_edge_aux_obj) 806 abort (); 807 obstack_free (&edge_aux_obstack, first_edge_aux_obj); 808 first_edge_aux_obj = NULL; 809 810 clear_aux_for_edges (); 811} 812 813/* Verify the CFG consistency. 814 815 Currently it does following checks edge and basic block list correctness 816 and calls into IL dependent checking then. */ 817void 818verify_flow_info (void) 819{ 820 size_t *edge_checksum; 821 int num_bb_notes, err = 0; 822 basic_block bb, last_bb_seen; 823 basic_block *last_visited; 824 825 last_visited = xcalloc (last_basic_block + 2, sizeof (basic_block)); 826 edge_checksum = xcalloc (last_basic_block + 2, sizeof (size_t)); 827 828 /* Check bb chain & numbers. */ 829 last_bb_seen = ENTRY_BLOCK_PTR; 830 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) 831 { 832 if (bb != EXIT_BLOCK_PTR 833 && bb != BASIC_BLOCK (bb->index)) 834 { 835 error ("bb %d on wrong place", bb->index); 836 err = 1; 837 } 838 839 if (bb->prev_bb != last_bb_seen) 840 { 841 error ("prev_bb of %d should be %d, not %d", 842 bb->index, last_bb_seen->index, bb->prev_bb->index); 843 err = 1; 844 } 845 846 last_bb_seen = bb; 847 } 848 849 /* Now check the basic blocks (boundaries etc.) */ 850 FOR_EACH_BB_REVERSE (bb) 851 { 852 int n_fallthru = 0; 853 edge e; 854 855 if (bb->count < 0) 856 { 857 error ("verify_flow_info: Wrong count of block %i %i", 858 bb->index, (int)bb->count); 859 err = 1; 860 } 861 if (bb->frequency < 0) 862 { 863 error ("verify_flow_info: Wrong frequency of block %i %i", 864 bb->index, bb->frequency); 865 err = 1; 866 } 867 for (e = bb->succ; e; e = e->succ_next) 868 { 869 if (last_visited [e->dest->index + 2] == bb) 870 { 871 error ("verify_flow_info: Duplicate edge %i->%i", 872 e->src->index, e->dest->index); 873 err = 1; 874 } 875 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE) 876 { 877 error ("verify_flow_info: Wrong probability of edge %i->%i %i", 878 e->src->index, e->dest->index, e->probability); 879 err = 1; 880 } 881 if (e->count < 0) 882 { 883 error ("verify_flow_info: Wrong count of edge %i->%i %i", 884 e->src->index, e->dest->index, (int)e->count); 885 err = 1; 886 } 887 888 last_visited [e->dest->index + 2] = bb; 889 890 if (e->flags & EDGE_FALLTHRU) 891 n_fallthru++; 892 893 if (e->src != bb) 894 { 895 error ("verify_flow_info: Basic block %d succ edge is corrupted", 896 bb->index); 897 fprintf (stderr, "Predecessor: "); 898 dump_edge_info (stderr, e, 0); 899 fprintf (stderr, "\nSuccessor: "); 900 dump_edge_info (stderr, e, 1); 901 fprintf (stderr, "\n"); 902 err = 1; 903 } 904 905 edge_checksum[e->dest->index + 2] += (size_t) e; 906 } 907 if (n_fallthru > 1) 908 { 909 error ("Wrong amount of branch edges after unconditional jump %i", bb->index); 910 err = 1; 911 } 912 913 for (e = bb->pred; e; e = e->pred_next) 914 { 915 if (e->dest != bb) 916 { 917 error ("basic block %d pred edge is corrupted", bb->index); 918 fputs ("Predecessor: ", stderr); 919 dump_edge_info (stderr, e, 0); 920 fputs ("\nSuccessor: ", stderr); 921 dump_edge_info (stderr, e, 1); 922 fputc ('\n', stderr); 923 err = 1; 924 } 925 edge_checksum[e->dest->index + 2] -= (size_t) e; 926 } 927 } 928 929 /* Complete edge checksumming for ENTRY and EXIT. */ 930 { 931 edge e; 932 933 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next) 934 edge_checksum[e->dest->index + 2] += (size_t) e; 935 936 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next) 937 edge_checksum[e->dest->index + 2] -= (size_t) e; 938 } 939 940 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 941 if (edge_checksum[bb->index + 2]) 942 { 943 error ("basic block %i edge lists are corrupted", bb->index); 944 err = 1; 945 } 946 947 num_bb_notes = 0; 948 last_bb_seen = ENTRY_BLOCK_PTR; 949 950 /* Clean up. */ 951 free (last_visited); 952 free (edge_checksum); 953 err |= cfg_hooks->cfgh_verify_flow_info (); 954 if (err) 955 internal_error ("verify_flow_info failed"); 956} 957 958/* Print out one basic block with live information at start and end. */ 959 960void 961dump_bb (basic_block bb, FILE *outf) 962{ 963 edge e; 964 965 fprintf (outf, ";; Basic block %d, loop depth %d, count ", 966 bb->index, bb->loop_depth); 967 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count); 968 putc ('\n', outf); 969 fputs (";; Predecessors: ", outf); 970 for (e = bb->pred; e; e = e->pred_next) 971 dump_edge_info (outf, e, 0); 972 putc ('\n', outf); 973 974 cfg_hooks->dump_bb (bb, outf); 975 976 fputs (";; Successors: ", outf); 977 for (e = bb->succ; e; e = e->succ_next) 978 dump_edge_info (outf, e, 1); 979 putc ('\n', outf); 980} 981 982void 983debug_bb (basic_block bb) 984{ 985 dump_bb (bb, stderr); 986} 987 988basic_block 989debug_bb_n (int n) 990{ 991 basic_block bb = BASIC_BLOCK (n); 992 dump_bb (bb, stderr); 993 return bb; 994} 995