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