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, 2003, 2004, 2005 4 Free Software Foundation, Inc. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 2, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING. If not, write to the Free 20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21 02110-1301, USA. */ 22 23 /* This file contains low level functions to manipulate the CFG and 24 analyze it. All other modules should not transform the data structure 25 directly and use abstraction instead. The file is supposed to be 26 ordered bottom-up and should not contain any code dependent on a 27 particular intermediate language (RTL or trees). 28 29 Available functionality: 30 - Initialization/deallocation 31 init_flow, clear_edges 32 - Low level basic block manipulation 33 alloc_block, expunge_block 34 - Edge manipulation 35 make_edge, make_single_succ_edge, cached_make_edge, remove_edge 36 - Low level edge redirection (without updating instruction chain) 37 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred 38 - Dumping and debugging 39 dump_flow_info, debug_flow_info, dump_edge_info 40 - Allocation of AUX fields for basic blocks 41 alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block 42 - clear_bb_flags 43 - Consistency checking 44 verify_flow_info 45 - Dumping and debugging 46 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n 47 */ 48 49 #include "config.h" 50 #include "system.h" 51 #include "coretypes.h" 52 #include "tm.h" 53 #include "tree.h" 54 #include "rtl.h" 55 #include "hard-reg-set.h" 56 #include "regs.h" 57 #include "flags.h" 58 #include "output.h" 59 #include "function.h" 60 #include "except.h" 61 #include "toplev.h" 62 #include "tm_p.h" 63 #include "obstack.h" 64 #include "timevar.h" 65 #include "tree-pass.h" 66 #include "ggc.h" 67 #include "hashtab.h" 68 #include "alloc-pool.h" 69 70 /* The obstack on which the flow graph components are allocated. */ 71 72 struct bitmap_obstack reg_obstack; 73 74 void debug_flow_info (void); 75 static void free_edge (edge); 76 77 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y)) 78 79 /* Called once at initialization time. */ 80 81 void 82 init_flow (void) 83 { 84 if (!cfun->cfg) 85 cfun->cfg = ggc_alloc_cleared (sizeof (struct control_flow_graph)); 86 n_edges = 0; 87 ENTRY_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def)); 88 ENTRY_BLOCK_PTR->index = ENTRY_BLOCK; 89 EXIT_BLOCK_PTR = ggc_alloc_cleared (sizeof (struct basic_block_def)); 90 EXIT_BLOCK_PTR->index = EXIT_BLOCK; 91 ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR; 92 EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR; 93 } 94 95 /* Helper function for remove_edge and clear_edges. Frees edge structure 96 without actually unlinking it from the pred/succ lists. */ 97 98 static void 99 free_edge (edge e ATTRIBUTE_UNUSED) 100 { 101 n_edges--; 102 ggc_free (e); 103 } 104 105 /* Free the memory associated with the edge structures. */ 106 107 void 108 clear_edges (void) 109 { 110 basic_block bb; 111 edge e; 112 edge_iterator ei; 113 114 FOR_EACH_BB (bb) 115 { 116 FOR_EACH_EDGE (e, ei, bb->succs) 117 free_edge (e); 118 VEC_truncate (edge, bb->succs, 0); 119 VEC_truncate (edge, bb->preds, 0); 120 } 121 122 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 123 free_edge (e); 124 VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0); 125 VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0); 126 127 gcc_assert (!n_edges); 128 } 129 130 /* Allocate memory for basic_block. */ 131 132 basic_block 133 alloc_block (void) 134 { 135 basic_block bb; 136 bb = ggc_alloc_cleared (sizeof (*bb)); 137 return bb; 138 } 139 140 /* Link block B to chain after AFTER. */ 141 void 142 link_block (basic_block b, basic_block after) 143 { 144 b->next_bb = after->next_bb; 145 b->prev_bb = after; 146 after->next_bb = b; 147 b->next_bb->prev_bb = b; 148 } 149 150 /* Unlink block B from chain. */ 151 void 152 unlink_block (basic_block b) 153 { 154 b->next_bb->prev_bb = b->prev_bb; 155 b->prev_bb->next_bb = b->next_bb; 156 b->prev_bb = NULL; 157 b->next_bb = NULL; 158 } 159 160 /* Sequentially order blocks and compact the arrays. */ 161 void 162 compact_blocks (void) 163 { 164 int i; 165 basic_block bb; 166 167 SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR); 168 SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR); 169 170 i = NUM_FIXED_BLOCKS; 171 FOR_EACH_BB (bb) 172 { 173 SET_BASIC_BLOCK (i, bb); 174 bb->index = i; 175 i++; 176 } 177 178 gcc_assert (i == n_basic_blocks); 179 180 for (; i < last_basic_block; i++) 181 SET_BASIC_BLOCK (i, NULL); 182 183 last_basic_block = n_basic_blocks; 184 } 185 186 /* Remove block B from the basic block array. */ 187 188 void 189 expunge_block (basic_block b) 190 { 191 unlink_block (b); 192 SET_BASIC_BLOCK (b->index, NULL); 193 n_basic_blocks--; 194 /* We should be able to ggc_free here, but we are not. 195 The dead SSA_NAMES are left pointing to dead statements that are pointing 196 to dead basic blocks making garbage collector to die. 197 We should be able to release all dead SSA_NAMES and at the same time we should 198 clear out BB pointer of dead statements consistently. */ 199 } 200 201 /* Connect E to E->src. */ 202 203 static inline void 204 connect_src (edge e) 205 { 206 VEC_safe_push (edge, gc, e->src->succs, e); 207 } 208 209 /* Connect E to E->dest. */ 210 211 static inline void 212 connect_dest (edge e) 213 { 214 basic_block dest = e->dest; 215 VEC_safe_push (edge, gc, dest->preds, e); 216 e->dest_idx = EDGE_COUNT (dest->preds) - 1; 217 } 218 219 /* Disconnect edge E from E->src. */ 220 221 static inline void 222 disconnect_src (edge e) 223 { 224 basic_block src = e->src; 225 edge_iterator ei; 226 edge tmp; 227 228 for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); ) 229 { 230 if (tmp == e) 231 { 232 VEC_unordered_remove (edge, src->succs, ei.index); 233 return; 234 } 235 else 236 ei_next (&ei); 237 } 238 239 gcc_unreachable (); 240 } 241 242 /* Disconnect edge E from E->dest. */ 243 244 static inline void 245 disconnect_dest (edge e) 246 { 247 basic_block dest = e->dest; 248 unsigned int dest_idx = e->dest_idx; 249 250 VEC_unordered_remove (edge, dest->preds, dest_idx); 251 252 /* If we removed an edge in the middle of the edge vector, we need 253 to update dest_idx of the edge that moved into the "hole". */ 254 if (dest_idx < EDGE_COUNT (dest->preds)) 255 EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx; 256 } 257 258 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly 259 created edge. Use this only if you are sure that this edge can't 260 possibly already exist. */ 261 262 edge 263 unchecked_make_edge (basic_block src, basic_block dst, int flags) 264 { 265 edge e; 266 e = ggc_alloc_cleared (sizeof (*e)); 267 n_edges++; 268 269 e->src = src; 270 e->dest = dst; 271 e->flags = flags; 272 273 connect_src (e); 274 connect_dest (e); 275 276 execute_on_growing_pred (e); 277 278 return e; 279 } 280 281 /* Create an edge connecting SRC and DST with FLAGS optionally using 282 edge cache CACHE. Return the new edge, NULL if already exist. */ 283 284 edge 285 cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags) 286 { 287 if (edge_cache == NULL 288 || src == ENTRY_BLOCK_PTR 289 || dst == EXIT_BLOCK_PTR) 290 return make_edge (src, dst, flags); 291 292 /* Does the requested edge already exist? */ 293 if (! TEST_BIT (edge_cache, dst->index)) 294 { 295 /* The edge does not exist. Create one and update the 296 cache. */ 297 SET_BIT (edge_cache, dst->index); 298 return unchecked_make_edge (src, dst, flags); 299 } 300 301 /* At this point, we know that the requested edge exists. Adjust 302 flags if necessary. */ 303 if (flags) 304 { 305 edge e = find_edge (src, dst); 306 e->flags |= flags; 307 } 308 309 return NULL; 310 } 311 312 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly 313 created edge or NULL if already exist. */ 314 315 edge 316 make_edge (basic_block src, basic_block dest, int flags) 317 { 318 edge e = find_edge (src, dest); 319 320 /* Make sure we don't add duplicate edges. */ 321 if (e) 322 { 323 e->flags |= flags; 324 return NULL; 325 } 326 327 return unchecked_make_edge (src, dest, flags); 328 } 329 330 /* Create an edge connecting SRC to DEST and set probability by knowing 331 that it is the single edge leaving SRC. */ 332 333 edge 334 make_single_succ_edge (basic_block src, basic_block dest, int flags) 335 { 336 edge e = make_edge (src, dest, flags); 337 338 e->probability = REG_BR_PROB_BASE; 339 e->count = src->count; 340 return e; 341 } 342 343 /* This function will remove an edge from the flow graph. */ 344 345 void 346 remove_edge (edge e) 347 { 348 remove_predictions_associated_with_edge (e); 349 execute_on_shrinking_pred (e); 350 351 disconnect_src (e); 352 disconnect_dest (e); 353 354 free_edge (e); 355 } 356 357 /* Redirect an edge's successor from one block to another. */ 358 359 void 360 redirect_edge_succ (edge e, basic_block new_succ) 361 { 362 execute_on_shrinking_pred (e); 363 364 disconnect_dest (e); 365 366 e->dest = new_succ; 367 368 /* Reconnect the edge to the new successor block. */ 369 connect_dest (e); 370 371 execute_on_growing_pred (e); 372 } 373 374 /* Like previous but avoid possible duplicate edge. */ 375 376 edge 377 redirect_edge_succ_nodup (edge e, basic_block new_succ) 378 { 379 edge s; 380 381 s = find_edge (e->src, new_succ); 382 if (s && s != e) 383 { 384 s->flags |= e->flags; 385 s->probability += e->probability; 386 if (s->probability > REG_BR_PROB_BASE) 387 s->probability = REG_BR_PROB_BASE; 388 s->count += e->count; 389 remove_edge (e); 390 e = s; 391 } 392 else 393 redirect_edge_succ (e, new_succ); 394 395 return e; 396 } 397 398 /* Redirect an edge's predecessor from one block to another. */ 399 400 void 401 redirect_edge_pred (edge e, basic_block new_pred) 402 { 403 disconnect_src (e); 404 405 e->src = new_pred; 406 407 /* Reconnect the edge to the new predecessor block. */ 408 connect_src (e); 409 } 410 411 /* Clear all basic block flags, with the exception of partitioning. */ 412 void 413 clear_bb_flags (void) 414 { 415 basic_block bb; 416 417 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 418 bb->flags = (BB_PARTITION (bb) | (bb->flags & BB_DISABLE_SCHEDULE) 419 | (bb->flags & BB_RTL)); 420 } 421 422 /* Check the consistency of profile information. We can't do that 423 in verify_flow_info, as the counts may get invalid for incompletely 424 solved graphs, later eliminating of conditionals or roundoff errors. 425 It is still practical to have them reported for debugging of simple 426 testcases. */ 427 void 428 check_bb_profile (basic_block bb, FILE * file) 429 { 430 edge e; 431 int sum = 0; 432 gcov_type lsum; 433 edge_iterator ei; 434 435 if (profile_status == PROFILE_ABSENT) 436 return; 437 438 if (bb != EXIT_BLOCK_PTR) 439 { 440 FOR_EACH_EDGE (e, ei, bb->succs) 441 sum += e->probability; 442 if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100) 443 fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n", 444 sum * 100.0 / REG_BR_PROB_BASE); 445 lsum = 0; 446 FOR_EACH_EDGE (e, ei, bb->succs) 447 lsum += e->count; 448 if (EDGE_COUNT (bb->succs) 449 && (lsum - bb->count > 100 || lsum - bb->count < -100)) 450 fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n", 451 (int) lsum, (int) bb->count); 452 } 453 if (bb != ENTRY_BLOCK_PTR) 454 { 455 sum = 0; 456 FOR_EACH_EDGE (e, ei, bb->preds) 457 sum += EDGE_FREQUENCY (e); 458 if (abs (sum - bb->frequency) > 100) 459 fprintf (file, 460 "Invalid sum of incoming frequencies %i, should be %i\n", 461 sum, bb->frequency); 462 lsum = 0; 463 FOR_EACH_EDGE (e, ei, bb->preds) 464 lsum += e->count; 465 if (lsum - bb->count > 100 || lsum - bb->count < -100) 466 fprintf (file, "Invalid sum of incoming counts %i, should be %i\n", 467 (int) lsum, (int) bb->count); 468 } 469 } 470 471 /* Emit basic block information for BB. HEADER is true if the user wants 472 the generic information and the predecessors, FOOTER is true if they want 473 the successors. FLAGS is the dump flags of interest; TDF_DETAILS emit 474 global register liveness information. PREFIX is put in front of every 475 line. The output is emitted to FILE. */ 476 void 477 dump_bb_info (basic_block bb, bool header, bool footer, int flags, 478 const char *prefix, FILE *file) 479 { 480 edge e; 481 edge_iterator ei; 482 483 if (header) 484 { 485 fprintf (file, "\n%sBasic block %d ", prefix, bb->index); 486 if (bb->prev_bb) 487 fprintf (file, ", prev %d", bb->prev_bb->index); 488 if (bb->next_bb) 489 fprintf (file, ", next %d", bb->next_bb->index); 490 fprintf (file, ", loop_depth %d, count ", bb->loop_depth); 491 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count); 492 fprintf (file, ", freq %i", bb->frequency); 493 if (maybe_hot_bb_p (bb)) 494 fprintf (file, ", maybe hot"); 495 if (probably_never_executed_bb_p (bb)) 496 fprintf (file, ", probably never executed"); 497 fprintf (file, ".\n"); 498 499 fprintf (file, "%sPredecessors: ", prefix); 500 FOR_EACH_EDGE (e, ei, bb->preds) 501 dump_edge_info (file, e, 0); 502 } 503 504 if (footer) 505 { 506 fprintf (file, "\n%sSuccessors: ", prefix); 507 FOR_EACH_EDGE (e, ei, bb->succs) 508 dump_edge_info (file, e, 1); 509 } 510 511 if ((flags & TDF_DETAILS) 512 && (bb->flags & BB_RTL)) 513 { 514 if (bb->il.rtl->global_live_at_start && header) 515 { 516 fprintf (file, "\n%sRegisters live at start:", prefix); 517 dump_regset (bb->il.rtl->global_live_at_start, file); 518 } 519 520 if (bb->il.rtl->global_live_at_end && footer) 521 { 522 fprintf (file, "\n%sRegisters live at end:", prefix); 523 dump_regset (bb->il.rtl->global_live_at_end, file); 524 } 525 } 526 527 putc ('\n', file); 528 } 529 530 void 531 dump_flow_info (FILE *file, int flags) 532 { 533 basic_block bb; 534 535 /* There are no pseudo registers after reload. Don't dump them. */ 536 if (reg_n_info && !reload_completed 537 && (flags & TDF_DETAILS) != 0) 538 { 539 unsigned int i, max = max_reg_num (); 540 fprintf (file, "%d registers.\n", max); 541 for (i = FIRST_PSEUDO_REGISTER; i < max; i++) 542 if (REG_N_REFS (i)) 543 { 544 enum reg_class class, altclass; 545 546 fprintf (file, "\nRegister %d used %d times across %d insns", 547 i, REG_N_REFS (i), REG_LIVE_LENGTH (i)); 548 if (REG_BASIC_BLOCK (i) >= 0) 549 fprintf (file, " in block %d", REG_BASIC_BLOCK (i)); 550 if (REG_N_SETS (i)) 551 fprintf (file, "; set %d time%s", REG_N_SETS (i), 552 (REG_N_SETS (i) == 1) ? "" : "s"); 553 if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i])) 554 fprintf (file, "; user var"); 555 if (REG_N_DEATHS (i) != 1) 556 fprintf (file, "; dies in %d places", REG_N_DEATHS (i)); 557 if (REG_N_CALLS_CROSSED (i) == 1) 558 fprintf (file, "; crosses 1 call"); 559 else if (REG_N_CALLS_CROSSED (i)) 560 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i)); 561 if (regno_reg_rtx[i] != NULL 562 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD) 563 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i)); 564 565 class = reg_preferred_class (i); 566 altclass = reg_alternate_class (i); 567 if (class != GENERAL_REGS || altclass != ALL_REGS) 568 { 569 if (altclass == ALL_REGS || class == ALL_REGS) 570 fprintf (file, "; pref %s", reg_class_names[(int) class]); 571 else if (altclass == NO_REGS) 572 fprintf (file, "; %s or none", reg_class_names[(int) class]); 573 else 574 fprintf (file, "; pref %s, else %s", 575 reg_class_names[(int) class], 576 reg_class_names[(int) altclass]); 577 } 578 579 if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i])) 580 fprintf (file, "; pointer"); 581 fprintf (file, ".\n"); 582 } 583 } 584 585 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges); 586 FOR_EACH_BB (bb) 587 { 588 dump_bb_info (bb, true, true, flags, "", file); 589 check_bb_profile (bb, file); 590 } 591 592 putc ('\n', file); 593 } 594 595 void 596 debug_flow_info (void) 597 { 598 dump_flow_info (stderr, TDF_DETAILS); 599 } 600 601 void 602 dump_edge_info (FILE *file, edge e, int do_succ) 603 { 604 basic_block side = (do_succ ? e->dest : e->src); 605 606 if (side == ENTRY_BLOCK_PTR) 607 fputs (" ENTRY", file); 608 else if (side == EXIT_BLOCK_PTR) 609 fputs (" EXIT", file); 610 else 611 fprintf (file, " %d", side->index); 612 613 if (e->probability) 614 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE); 615 616 if (e->count) 617 { 618 fprintf (file, " count:"); 619 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count); 620 } 621 622 if (e->flags) 623 { 624 static const char * const bitnames[] = { 625 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back", 626 "can_fallthru", "irreducible", "sibcall", "loop_exit", 627 "true", "false", "exec" 628 }; 629 int comma = 0; 630 int i, flags = e->flags; 631 632 fputs (" (", file); 633 for (i = 0; flags; i++) 634 if (flags & (1 << i)) 635 { 636 flags &= ~(1 << i); 637 638 if (comma) 639 fputc (',', file); 640 if (i < (int) ARRAY_SIZE (bitnames)) 641 fputs (bitnames[i], file); 642 else 643 fprintf (file, "%d", i); 644 comma = 1; 645 } 646 647 fputc (')', file); 648 } 649 } 650 651 /* Simple routines to easily allocate AUX fields of basic blocks. */ 652 653 static struct obstack block_aux_obstack; 654 static void *first_block_aux_obj = 0; 655 static struct obstack edge_aux_obstack; 656 static void *first_edge_aux_obj = 0; 657 658 /* Allocate a memory block of SIZE as BB->aux. The obstack must 659 be first initialized by alloc_aux_for_blocks. */ 660 661 inline void 662 alloc_aux_for_block (basic_block bb, int size) 663 { 664 /* Verify that aux field is clear. */ 665 gcc_assert (!bb->aux && first_block_aux_obj); 666 bb->aux = obstack_alloc (&block_aux_obstack, size); 667 memset (bb->aux, 0, size); 668 } 669 670 /* Initialize the block_aux_obstack and if SIZE is nonzero, call 671 alloc_aux_for_block for each basic block. */ 672 673 void 674 alloc_aux_for_blocks (int size) 675 { 676 static int initialized; 677 678 if (!initialized) 679 { 680 gcc_obstack_init (&block_aux_obstack); 681 initialized = 1; 682 } 683 else 684 /* Check whether AUX data are still allocated. */ 685 gcc_assert (!first_block_aux_obj); 686 687 first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0); 688 if (size) 689 { 690 basic_block bb; 691 692 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 693 alloc_aux_for_block (bb, size); 694 } 695 } 696 697 /* Clear AUX pointers of all blocks. */ 698 699 void 700 clear_aux_for_blocks (void) 701 { 702 basic_block bb; 703 704 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 705 bb->aux = NULL; 706 } 707 708 /* Free data allocated in block_aux_obstack and clear AUX pointers 709 of all blocks. */ 710 711 void 712 free_aux_for_blocks (void) 713 { 714 gcc_assert (first_block_aux_obj); 715 obstack_free (&block_aux_obstack, first_block_aux_obj); 716 first_block_aux_obj = NULL; 717 718 clear_aux_for_blocks (); 719 } 720 721 /* Allocate a memory edge of SIZE as BB->aux. The obstack must 722 be first initialized by alloc_aux_for_edges. */ 723 724 inline void 725 alloc_aux_for_edge (edge e, int size) 726 { 727 /* Verify that aux field is clear. */ 728 gcc_assert (!e->aux && first_edge_aux_obj); 729 e->aux = obstack_alloc (&edge_aux_obstack, size); 730 memset (e->aux, 0, size); 731 } 732 733 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call 734 alloc_aux_for_edge for each basic edge. */ 735 736 void 737 alloc_aux_for_edges (int size) 738 { 739 static int initialized; 740 741 if (!initialized) 742 { 743 gcc_obstack_init (&edge_aux_obstack); 744 initialized = 1; 745 } 746 else 747 /* Check whether AUX data are still allocated. */ 748 gcc_assert (!first_edge_aux_obj); 749 750 first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0); 751 if (size) 752 { 753 basic_block bb; 754 755 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 756 { 757 edge e; 758 edge_iterator ei; 759 760 FOR_EACH_EDGE (e, ei, bb->succs) 761 alloc_aux_for_edge (e, size); 762 } 763 } 764 } 765 766 /* Clear AUX pointers of all edges. */ 767 768 void 769 clear_aux_for_edges (void) 770 { 771 basic_block bb; 772 edge e; 773 774 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 775 { 776 edge_iterator ei; 777 FOR_EACH_EDGE (e, ei, bb->succs) 778 e->aux = NULL; 779 } 780 } 781 782 /* Free data allocated in edge_aux_obstack and clear AUX pointers 783 of all edges. */ 784 785 void 786 free_aux_for_edges (void) 787 { 788 gcc_assert (first_edge_aux_obj); 789 obstack_free (&edge_aux_obstack, first_edge_aux_obj); 790 first_edge_aux_obj = NULL; 791 792 clear_aux_for_edges (); 793 } 794 795 void 796 debug_bb (basic_block bb) 797 { 798 dump_bb (bb, stderr, 0); 799 } 800 801 basic_block 802 debug_bb_n (int n) 803 { 804 basic_block bb = BASIC_BLOCK (n); 805 dump_bb (bb, stderr, 0); 806 return bb; 807 } 808 809 /* Dumps cfg related information about basic block BB to FILE. */ 810 811 static void 812 dump_cfg_bb_info (FILE *file, basic_block bb) 813 { 814 unsigned i; 815 edge_iterator ei; 816 bool first = true; 817 static const char * const bb_bitnames[] = 818 { 819 "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock" 820 }; 821 const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *); 822 edge e; 823 824 fprintf (file, "Basic block %d", bb->index); 825 for (i = 0; i < n_bitnames; i++) 826 if (bb->flags & (1 << i)) 827 { 828 if (first) 829 fprintf (file, " ("); 830 else 831 fprintf (file, ", "); 832 first = false; 833 fprintf (file, bb_bitnames[i]); 834 } 835 if (!first) 836 fprintf (file, ")"); 837 fprintf (file, "\n"); 838 839 fprintf (file, "Predecessors: "); 840 FOR_EACH_EDGE (e, ei, bb->preds) 841 dump_edge_info (file, e, 0); 842 843 fprintf (file, "\nSuccessors: "); 844 FOR_EACH_EDGE (e, ei, bb->succs) 845 dump_edge_info (file, e, 1); 846 fprintf (file, "\n\n"); 847 } 848 849 /* Dumps a brief description of cfg to FILE. */ 850 851 void 852 brief_dump_cfg (FILE *file) 853 { 854 basic_block bb; 855 856 FOR_EACH_BB (bb) 857 { 858 dump_cfg_bb_info (file, bb); 859 } 860 } 861 862 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to 863 leave the block by TAKEN_EDGE. Update profile of BB such that edge E can be 864 redirected to destination of TAKEN_EDGE. 865 866 This function may leave the profile inconsistent in the case TAKEN_EDGE 867 frequency or count is believed to be lower than FREQUENCY or COUNT 868 respectively. */ 869 void 870 update_bb_profile_for_threading (basic_block bb, int edge_frequency, 871 gcov_type count, edge taken_edge) 872 { 873 edge c; 874 int prob; 875 edge_iterator ei; 876 877 bb->count -= count; 878 if (bb->count < 0) 879 { 880 if (dump_file) 881 fprintf (dump_file, "bb %i count became negative after threading", 882 bb->index); 883 bb->count = 0; 884 } 885 886 /* Compute the probability of TAKEN_EDGE being reached via threaded edge. 887 Watch for overflows. */ 888 if (bb->frequency) 889 prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency; 890 else 891 prob = 0; 892 if (prob > taken_edge->probability) 893 { 894 if (dump_file) 895 fprintf (dump_file, "Jump threading proved probability of edge " 896 "%i->%i too small (it is %i, should be %i).\n", 897 taken_edge->src->index, taken_edge->dest->index, 898 taken_edge->probability, prob); 899 prob = taken_edge->probability; 900 } 901 902 /* Now rescale the probabilities. */ 903 taken_edge->probability -= prob; 904 prob = REG_BR_PROB_BASE - prob; 905 bb->frequency -= edge_frequency; 906 if (bb->frequency < 0) 907 bb->frequency = 0; 908 if (prob <= 0) 909 { 910 if (dump_file) 911 fprintf (dump_file, "Edge frequencies of bb %i has been reset, " 912 "frequency of block should end up being 0, it is %i\n", 913 bb->index, bb->frequency); 914 EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; 915 ei = ei_start (bb->succs); 916 ei_next (&ei); 917 for (; (c = ei_safe_edge (ei)); ei_next (&ei)) 918 c->probability = 0; 919 } 920 else if (prob != REG_BR_PROB_BASE) 921 { 922 int scale = RDIV (65536 * REG_BR_PROB_BASE, prob); 923 924 FOR_EACH_EDGE (c, ei, bb->succs) 925 { 926 c->probability = RDIV (c->probability * scale, 65536); 927 if (c->probability > REG_BR_PROB_BASE) 928 c->probability = REG_BR_PROB_BASE; 929 } 930 } 931 932 gcc_assert (bb == taken_edge->src); 933 taken_edge->count -= count; 934 if (taken_edge->count < 0) 935 { 936 if (dump_file) 937 fprintf (dump_file, "edge %i->%i count became negative after threading", 938 taken_edge->src->index, taken_edge->dest->index); 939 taken_edge->count = 0; 940 } 941 } 942 943 /* Multiply all frequencies of basic blocks in array BBS of length NBBS 944 by NUM/DEN, in int arithmetic. May lose some accuracy. */ 945 void 946 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den) 947 { 948 int i; 949 edge e; 950 if (num < 0) 951 num = 0; 952 if (num > den) 953 return; 954 /* Assume that the users are producing the fraction from frequencies 955 that never grow far enough to risk arithmetic overflow. */ 956 gcc_assert (num < 65536); 957 for (i = 0; i < nbbs; i++) 958 { 959 edge_iterator ei; 960 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den); 961 bbs[i]->count = RDIV (bbs[i]->count * num, den); 962 FOR_EACH_EDGE (e, ei, bbs[i]->succs) 963 e->count = RDIV (e->count * num, den); 964 } 965 } 966 967 /* numbers smaller than this value are safe to multiply without getting 968 64bit overflow. */ 969 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1)) 970 971 /* Multiply all frequencies of basic blocks in array BBS of length NBBS 972 by NUM/DEN, in gcov_type arithmetic. More accurate than previous 973 function but considerably slower. */ 974 void 975 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num, 976 gcov_type den) 977 { 978 int i; 979 edge e; 980 gcov_type fraction = RDIV (num * 65536, den); 981 982 gcc_assert (fraction >= 0); 983 984 if (num < MAX_SAFE_MULTIPLIER) 985 for (i = 0; i < nbbs; i++) 986 { 987 edge_iterator ei; 988 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den); 989 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER) 990 bbs[i]->count = RDIV (bbs[i]->count * num, den); 991 else 992 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536); 993 FOR_EACH_EDGE (e, ei, bbs[i]->succs) 994 if (bbs[i]->count <= MAX_SAFE_MULTIPLIER) 995 e->count = RDIV (e->count * num, den); 996 else 997 e->count = RDIV (e->count * fraction, 65536); 998 } 999 else 1000 for (i = 0; i < nbbs; i++) 1001 { 1002 edge_iterator ei; 1003 if (sizeof (gcov_type) > sizeof (int)) 1004 bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den); 1005 else 1006 bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536); 1007 bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536); 1008 FOR_EACH_EDGE (e, ei, bbs[i]->succs) 1009 e->count = RDIV (e->count * fraction, 65536); 1010 } 1011 } 1012 1013 /* Data structures used to maintain mapping between basic blocks and 1014 copies. */ 1015 static htab_t bb_original; 1016 static htab_t bb_copy; 1017 static alloc_pool original_copy_bb_pool; 1018 1019 struct htab_bb_copy_original_entry 1020 { 1021 /* Block we are attaching info to. */ 1022 int index1; 1023 /* Index of original or copy (depending on the hashtable) */ 1024 int index2; 1025 }; 1026 1027 static hashval_t 1028 bb_copy_original_hash (const void *p) 1029 { 1030 struct htab_bb_copy_original_entry *data 1031 = ((struct htab_bb_copy_original_entry *)p); 1032 1033 return data->index1; 1034 } 1035 static int 1036 bb_copy_original_eq (const void *p, const void *q) 1037 { 1038 struct htab_bb_copy_original_entry *data 1039 = ((struct htab_bb_copy_original_entry *)p); 1040 struct htab_bb_copy_original_entry *data2 1041 = ((struct htab_bb_copy_original_entry *)q); 1042 1043 return data->index1 == data2->index1; 1044 } 1045 1046 /* Initialize the data structures to maintain mapping between blocks 1047 and its copies. */ 1048 void 1049 initialize_original_copy_tables (void) 1050 { 1051 gcc_assert (!original_copy_bb_pool); 1052 original_copy_bb_pool 1053 = create_alloc_pool ("original_copy", 1054 sizeof (struct htab_bb_copy_original_entry), 10); 1055 bb_original = htab_create (10, bb_copy_original_hash, 1056 bb_copy_original_eq, NULL); 1057 bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL); 1058 } 1059 1060 /* Free the data structures to maintain mapping between blocks and 1061 its copies. */ 1062 void 1063 free_original_copy_tables (void) 1064 { 1065 gcc_assert (original_copy_bb_pool); 1066 htab_delete (bb_copy); 1067 htab_delete (bb_original); 1068 free_alloc_pool (original_copy_bb_pool); 1069 bb_copy = NULL; 1070 bb_original = NULL; 1071 original_copy_bb_pool = NULL; 1072 } 1073 1074 /* Set original for basic block. Do nothing when data structures are not 1075 initialized so passes not needing this don't need to care. */ 1076 void 1077 set_bb_original (basic_block bb, basic_block original) 1078 { 1079 if (original_copy_bb_pool) 1080 { 1081 struct htab_bb_copy_original_entry **slot; 1082 struct htab_bb_copy_original_entry key; 1083 1084 key.index1 = bb->index; 1085 slot = 1086 (struct htab_bb_copy_original_entry **) htab_find_slot (bb_original, 1087 &key, INSERT); 1088 if (*slot) 1089 (*slot)->index2 = original->index; 1090 else 1091 { 1092 *slot = pool_alloc (original_copy_bb_pool); 1093 (*slot)->index1 = bb->index; 1094 (*slot)->index2 = original->index; 1095 } 1096 } 1097 } 1098 1099 /* Get the original basic block. */ 1100 basic_block 1101 get_bb_original (basic_block bb) 1102 { 1103 struct htab_bb_copy_original_entry *entry; 1104 struct htab_bb_copy_original_entry key; 1105 1106 gcc_assert (original_copy_bb_pool); 1107 1108 key.index1 = bb->index; 1109 entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key); 1110 if (entry) 1111 return BASIC_BLOCK (entry->index2); 1112 else 1113 return NULL; 1114 } 1115 1116 /* Set copy for basic block. Do nothing when data structures are not 1117 initialized so passes not needing this don't need to care. */ 1118 void 1119 set_bb_copy (basic_block bb, basic_block copy) 1120 { 1121 if (original_copy_bb_pool) 1122 { 1123 struct htab_bb_copy_original_entry **slot; 1124 struct htab_bb_copy_original_entry key; 1125 1126 key.index1 = bb->index; 1127 slot = 1128 (struct htab_bb_copy_original_entry **) htab_find_slot (bb_copy, 1129 &key, INSERT); 1130 if (*slot) 1131 (*slot)->index2 = copy->index; 1132 else 1133 { 1134 *slot = pool_alloc (original_copy_bb_pool); 1135 (*slot)->index1 = bb->index; 1136 (*slot)->index2 = copy->index; 1137 } 1138 } 1139 } 1140 1141 /* Get the copy of basic block. */ 1142 basic_block 1143 get_bb_copy (basic_block bb) 1144 { 1145 struct htab_bb_copy_original_entry *entry; 1146 struct htab_bb_copy_original_entry key; 1147 1148 gcc_assert (original_copy_bb_pool); 1149 1150 key.index1 = bb->index; 1151 entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key); 1152 if (entry) 1153 return BASIC_BLOCK (entry->index2); 1154 else 1155 return NULL; 1156 } 1157