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