1/* Calculate branch probabilities, and basic block execution counts. 2 Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999, 3 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 4 Contributed by James E. Wilson, UC Berkeley/Cygnus Support; 5 based on some ideas from Dain Samples of UC Berkeley. 6 Further mangling by Bob Manson, Cygnus Support. 7 8This file is part of GCC. 9 10GCC is free software; you can redistribute it and/or modify it under 11the terms of the GNU General Public License as published by the Free 12Software Foundation; either version 2, or (at your option) any later 13version. 14 15GCC is distributed in the hope that it will be useful, but WITHOUT ANY 16WARRANTY; without even the implied warranty of MERCHANTABILITY or 17FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18for more details. 19 20You should have received a copy of the GNU General Public License 21along with GCC; see the file COPYING. If not, write to the Free 22Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2302110-1301, USA. */ 24 25/* Generate basic block profile instrumentation and auxiliary files. 26 Profile generation is optimized, so that not all arcs in the basic 27 block graph need instrumenting. First, the BB graph is closed with 28 one entry (function start), and one exit (function exit). Any 29 ABNORMAL_EDGE cannot be instrumented (because there is no control 30 path to place the code). We close the graph by inserting fake 31 EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal 32 edges that do not go to the exit_block. We ignore such abnormal 33 edges. Naturally these fake edges are never directly traversed, 34 and so *cannot* be directly instrumented. Some other graph 35 massaging is done. To optimize the instrumentation we generate the 36 BB minimal span tree, only edges that are not on the span tree 37 (plus the entry point) need instrumenting. From that information 38 all other edge counts can be deduced. By construction all fake 39 edges must be on the spanning tree. We also attempt to place 40 EDGE_CRITICAL edges on the spanning tree. 41 42 The auxiliary files generated are <dumpbase>.gcno (at compile time) 43 and <dumpbase>.gcda (at run time). The format is 44 described in full in gcov-io.h. */ 45 46/* ??? Register allocation should use basic block execution counts to 47 give preference to the most commonly executed blocks. */ 48 49/* ??? Should calculate branch probabilities before instrumenting code, since 50 then we can use arc counts to help decide which arcs to instrument. */ 51 52#include "config.h" 53#include "system.h" 54#include "coretypes.h" 55#include "tm.h" 56#include "rtl.h" 57#include "flags.h" 58#include "output.h" 59#include "regs.h" 60#include "expr.h" 61#include "function.h" 62#include "toplev.h" 63#include "coverage.h" 64#include "value-prof.h" 65#include "tree.h" 66#include "cfghooks.h" 67#include "tree-flow.h" 68#include "timevar.h" 69#include "cfgloop.h" 70#include "tree-pass.h" 71 72/* Hooks for profiling. */ 73static struct profile_hooks* profile_hooks; 74 75/* Additional information about the edges we need. */ 76struct edge_info { 77 unsigned int count_valid : 1; 78 79 /* Is on the spanning tree. */ 80 unsigned int on_tree : 1; 81 82 /* Pretend this edge does not exist (it is abnormal and we've 83 inserted a fake to compensate). */ 84 unsigned int ignore : 1; 85}; 86 87struct bb_info { 88 unsigned int count_valid : 1; 89 90 /* Number of successor and predecessor edges. */ 91 gcov_type succ_count; 92 gcov_type pred_count; 93}; 94 95#define EDGE_INFO(e) ((struct edge_info *) (e)->aux) 96#define BB_INFO(b) ((struct bb_info *) (b)->aux) 97 98/* Counter summary from the last set of coverage counts read. */ 99 100const struct gcov_ctr_summary *profile_info; 101 102/* Collect statistics on the performance of this pass for the entire source 103 file. */ 104 105static int total_num_blocks; 106static int total_num_edges; 107static int total_num_edges_ignored; 108static int total_num_edges_instrumented; 109static int total_num_blocks_created; 110static int total_num_passes; 111static int total_num_times_called; 112static int total_hist_br_prob[20]; 113static int total_num_never_executed; 114static int total_num_branches; 115 116/* Forward declarations. */ 117static void find_spanning_tree (struct edge_list *); 118static unsigned instrument_edges (struct edge_list *); 119static void instrument_values (histogram_values); 120static void compute_branch_probabilities (void); 121static void compute_value_histograms (histogram_values); 122static gcov_type * get_exec_counts (void); 123static basic_block find_group (basic_block); 124static void union_groups (basic_block, basic_block); 125 126 127/* Add edge instrumentation code to the entire insn chain. 128 129 F is the first insn of the chain. 130 NUM_BLOCKS is the number of basic blocks found in F. */ 131 132static unsigned 133instrument_edges (struct edge_list *el) 134{ 135 unsigned num_instr_edges = 0; 136 int num_edges = NUM_EDGES (el); 137 basic_block bb; 138 139 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 140 { 141 edge e; 142 edge_iterator ei; 143 144 FOR_EACH_EDGE (e, ei, bb->succs) 145 { 146 struct edge_info *inf = EDGE_INFO (e); 147 148 if (!inf->ignore && !inf->on_tree) 149 { 150 gcc_assert (!(e->flags & EDGE_ABNORMAL)); 151 if (dump_file) 152 fprintf (dump_file, "Edge %d to %d instrumented%s\n", 153 e->src->index, e->dest->index, 154 EDGE_CRITICAL_P (e) ? " (and split)" : ""); 155 (profile_hooks->gen_edge_profiler) (num_instr_edges++, e); 156 } 157 } 158 } 159 160 total_num_blocks_created += num_edges; 161 if (dump_file) 162 fprintf (dump_file, "%d edges instrumented\n", num_instr_edges); 163 return num_instr_edges; 164} 165 166/* Add code to measure histograms for values in list VALUES. */ 167static void 168instrument_values (histogram_values values) 169{ 170 unsigned i, t; 171 172 /* Emit code to generate the histograms before the insns. */ 173 174 for (i = 0; i < VEC_length (histogram_value, values); i++) 175 { 176 histogram_value hist = VEC_index (histogram_value, values, i); 177 switch (hist->type) 178 { 179 case HIST_TYPE_INTERVAL: 180 t = GCOV_COUNTER_V_INTERVAL; 181 break; 182 183 case HIST_TYPE_POW2: 184 t = GCOV_COUNTER_V_POW2; 185 break; 186 187 case HIST_TYPE_SINGLE_VALUE: 188 t = GCOV_COUNTER_V_SINGLE; 189 break; 190 191 case HIST_TYPE_CONST_DELTA: 192 t = GCOV_COUNTER_V_DELTA; 193 break; 194 195 default: 196 gcc_unreachable (); 197 } 198 if (!coverage_counter_alloc (t, hist->n_counters)) 199 continue; 200 201 switch (hist->type) 202 { 203 case HIST_TYPE_INTERVAL: 204 (profile_hooks->gen_interval_profiler) (hist, t, 0); 205 break; 206 207 case HIST_TYPE_POW2: 208 (profile_hooks->gen_pow2_profiler) (hist, t, 0); 209 break; 210 211 case HIST_TYPE_SINGLE_VALUE: 212 (profile_hooks->gen_one_value_profiler) (hist, t, 0); 213 break; 214 215 case HIST_TYPE_CONST_DELTA: 216 (profile_hooks->gen_const_delta_profiler) (hist, t, 0); 217 break; 218 219 default: 220 gcc_unreachable (); 221 } 222 } 223} 224 225 226/* Computes hybrid profile for all matching entries in da_file. */ 227 228static gcov_type * 229get_exec_counts (void) 230{ 231 unsigned num_edges = 0; 232 basic_block bb; 233 gcov_type *counts; 234 235 /* Count the edges to be (possibly) instrumented. */ 236 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 237 { 238 edge e; 239 edge_iterator ei; 240 241 FOR_EACH_EDGE (e, ei, bb->succs) 242 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) 243 num_edges++; 244 } 245 246 counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, &profile_info); 247 if (!counts) 248 return NULL; 249 250 if (dump_file && profile_info) 251 fprintf(dump_file, "Merged %u profiles with maximal count %u.\n", 252 profile_info->runs, (unsigned) profile_info->sum_max); 253 254 return counts; 255} 256 257 258/* Compute the branch probabilities for the various branches. 259 Annotate them accordingly. */ 260 261static void 262compute_branch_probabilities (void) 263{ 264 basic_block bb; 265 int i; 266 int num_edges = 0; 267 int changes; 268 int passes; 269 int hist_br_prob[20]; 270 int num_never_executed; 271 int num_branches; 272 gcov_type *exec_counts = get_exec_counts (); 273 int exec_counts_pos = 0; 274 275 /* Very simple sanity checks so we catch bugs in our profiling code. */ 276 if (profile_info) 277 { 278 if (profile_info->run_max * profile_info->runs < profile_info->sum_max) 279 { 280 error ("corrupted profile info: run_max * runs < sum_max"); 281 exec_counts = NULL; 282 } 283 284 if (profile_info->sum_all < profile_info->sum_max) 285 { 286 error ("corrupted profile info: sum_all is smaller than sum_max"); 287 exec_counts = NULL; 288 } 289 } 290 291 /* Attach extra info block to each bb. */ 292 293 alloc_aux_for_blocks (sizeof (struct bb_info)); 294 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 295 { 296 edge e; 297 edge_iterator ei; 298 299 FOR_EACH_EDGE (e, ei, bb->succs) 300 if (!EDGE_INFO (e)->ignore) 301 BB_INFO (bb)->succ_count++; 302 FOR_EACH_EDGE (e, ei, bb->preds) 303 if (!EDGE_INFO (e)->ignore) 304 BB_INFO (bb)->pred_count++; 305 } 306 307 /* Avoid predicting entry on exit nodes. */ 308 BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2; 309 BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2; 310 311 /* For each edge not on the spanning tree, set its execution count from 312 the .da file. */ 313 314 /* The first count in the .da file is the number of times that the function 315 was entered. This is the exec_count for block zero. */ 316 317 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 318 { 319 edge e; 320 edge_iterator ei; 321 322 FOR_EACH_EDGE (e, ei, bb->succs) 323 if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) 324 { 325 num_edges++; 326 if (exec_counts) 327 { 328 e->count = exec_counts[exec_counts_pos++]; 329 if (e->count > profile_info->sum_max) 330 { 331 error ("corrupted profile info: edge from %i to %i exceeds maximal count", 332 bb->index, e->dest->index); 333 } 334 } 335 else 336 e->count = 0; 337 338 EDGE_INFO (e)->count_valid = 1; 339 BB_INFO (bb)->succ_count--; 340 BB_INFO (e->dest)->pred_count--; 341 if (dump_file) 342 { 343 fprintf (dump_file, "\nRead edge from %i to %i, count:", 344 bb->index, e->dest->index); 345 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, 346 (HOST_WIDEST_INT) e->count); 347 } 348 } 349 } 350 351 if (dump_file) 352 fprintf (dump_file, "\n%d edge counts read\n", num_edges); 353 354 /* For every block in the file, 355 - if every exit/entrance edge has a known count, then set the block count 356 - if the block count is known, and every exit/entrance edge but one has 357 a known execution count, then set the count of the remaining edge 358 359 As edge counts are set, decrement the succ/pred count, but don't delete 360 the edge, that way we can easily tell when all edges are known, or only 361 one edge is unknown. */ 362 363 /* The order that the basic blocks are iterated through is important. 364 Since the code that finds spanning trees starts with block 0, low numbered 365 edges are put on the spanning tree in preference to high numbered edges. 366 Hence, most instrumented edges are at the end. Graph solving works much 367 faster if we propagate numbers from the end to the start. 368 369 This takes an average of slightly more than 3 passes. */ 370 371 changes = 1; 372 passes = 0; 373 while (changes) 374 { 375 passes++; 376 changes = 0; 377 FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb) 378 { 379 struct bb_info *bi = BB_INFO (bb); 380 if (! bi->count_valid) 381 { 382 if (bi->succ_count == 0) 383 { 384 edge e; 385 edge_iterator ei; 386 gcov_type total = 0; 387 388 FOR_EACH_EDGE (e, ei, bb->succs) 389 total += e->count; 390 bb->count = total; 391 bi->count_valid = 1; 392 changes = 1; 393 } 394 else if (bi->pred_count == 0) 395 { 396 edge e; 397 edge_iterator ei; 398 gcov_type total = 0; 399 400 FOR_EACH_EDGE (e, ei, bb->preds) 401 total += e->count; 402 bb->count = total; 403 bi->count_valid = 1; 404 changes = 1; 405 } 406 } 407 if (bi->count_valid) 408 { 409 if (bi->succ_count == 1) 410 { 411 edge e; 412 edge_iterator ei; 413 gcov_type total = 0; 414 415 /* One of the counts will be invalid, but it is zero, 416 so adding it in also doesn't hurt. */ 417 FOR_EACH_EDGE (e, ei, bb->succs) 418 total += e->count; 419 420 /* Seedgeh for the invalid edge, and set its count. */ 421 FOR_EACH_EDGE (e, ei, bb->succs) 422 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) 423 break; 424 425 /* Calculate count for remaining edge by conservation. */ 426 total = bb->count - total; 427 428 gcc_assert (e); 429 EDGE_INFO (e)->count_valid = 1; 430 e->count = total; 431 bi->succ_count--; 432 433 BB_INFO (e->dest)->pred_count--; 434 changes = 1; 435 } 436 if (bi->pred_count == 1) 437 { 438 edge e; 439 edge_iterator ei; 440 gcov_type total = 0; 441 442 /* One of the counts will be invalid, but it is zero, 443 so adding it in also doesn't hurt. */ 444 FOR_EACH_EDGE (e, ei, bb->preds) 445 total += e->count; 446 447 /* Search for the invalid edge, and set its count. */ 448 FOR_EACH_EDGE (e, ei, bb->preds) 449 if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore) 450 break; 451 452 /* Calculate count for remaining edge by conservation. */ 453 total = bb->count - total + e->count; 454 455 gcc_assert (e); 456 EDGE_INFO (e)->count_valid = 1; 457 e->count = total; 458 bi->pred_count--; 459 460 BB_INFO (e->src)->succ_count--; 461 changes = 1; 462 } 463 } 464 } 465 } 466 if (dump_file) 467 dump_flow_info (dump_file, dump_flags); 468 469 total_num_passes += passes; 470 if (dump_file) 471 fprintf (dump_file, "Graph solving took %d passes.\n\n", passes); 472 473 /* If the graph has been correctly solved, every block will have a 474 succ and pred count of zero. */ 475 FOR_EACH_BB (bb) 476 { 477 gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count); 478 } 479 480 /* For every edge, calculate its branch probability and add a reg_note 481 to the branch insn to indicate this. */ 482 483 for (i = 0; i < 20; i++) 484 hist_br_prob[i] = 0; 485 num_never_executed = 0; 486 num_branches = 0; 487 488 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 489 { 490 edge e; 491 edge_iterator ei; 492 493 if (bb->count < 0) 494 { 495 error ("corrupted profile info: number of iterations for basic block %d thought to be %i", 496 bb->index, (int)bb->count); 497 bb->count = 0; 498 } 499 FOR_EACH_EDGE (e, ei, bb->succs) 500 { 501 /* Function may return twice in the cased the called function is 502 setjmp or calls fork, but we can't represent this by extra 503 edge from the entry, since extra edge from the exit is 504 already present. We get negative frequency from the entry 505 point. */ 506 if ((e->count < 0 507 && e->dest == EXIT_BLOCK_PTR) 508 || (e->count > bb->count 509 && e->dest != EXIT_BLOCK_PTR)) 510 { 511 if (block_ends_with_call_p (bb)) 512 e->count = e->count < 0 ? 0 : bb->count; 513 } 514 if (e->count < 0 || e->count > bb->count) 515 { 516 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i", 517 e->src->index, e->dest->index, 518 (int)e->count); 519 e->count = bb->count / 2; 520 } 521 } 522 if (bb->count) 523 { 524 FOR_EACH_EDGE (e, ei, bb->succs) 525 e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count; 526 if (bb->index >= NUM_FIXED_BLOCKS 527 && block_ends_with_condjump_p (bb) 528 && EDGE_COUNT (bb->succs) >= 2) 529 { 530 int prob; 531 edge e; 532 int index; 533 534 /* Find the branch edge. It is possible that we do have fake 535 edges here. */ 536 FOR_EACH_EDGE (e, ei, bb->succs) 537 if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU))) 538 break; 539 540 prob = e->probability; 541 index = prob * 20 / REG_BR_PROB_BASE; 542 543 if (index == 20) 544 index = 19; 545 hist_br_prob[index]++; 546 547 num_branches++; 548 } 549 } 550 /* As a last resort, distribute the probabilities evenly. 551 Use simple heuristics that if there are normal edges, 552 give all abnormals frequency of 0, otherwise distribute the 553 frequency over abnormals (this is the case of noreturn 554 calls). */ 555 else if (profile_status == PROFILE_ABSENT) 556 { 557 int total = 0; 558 559 FOR_EACH_EDGE (e, ei, bb->succs) 560 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 561 total ++; 562 if (total) 563 { 564 FOR_EACH_EDGE (e, ei, bb->succs) 565 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 566 e->probability = REG_BR_PROB_BASE / total; 567 else 568 e->probability = 0; 569 } 570 else 571 { 572 total += EDGE_COUNT (bb->succs); 573 FOR_EACH_EDGE (e, ei, bb->succs) 574 e->probability = REG_BR_PROB_BASE / total; 575 } 576 if (bb->index >= NUM_FIXED_BLOCKS 577 && block_ends_with_condjump_p (bb) 578 && EDGE_COUNT (bb->succs) >= 2) 579 num_branches++, num_never_executed; 580 } 581 } 582 counts_to_freqs (); 583 584 if (dump_file) 585 { 586 fprintf (dump_file, "%d branches\n", num_branches); 587 fprintf (dump_file, "%d branches never executed\n", 588 num_never_executed); 589 if (num_branches) 590 for (i = 0; i < 10; i++) 591 fprintf (dump_file, "%d%% branches in range %d-%d%%\n", 592 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches, 593 5 * i, 5 * i + 5); 594 595 total_num_branches += num_branches; 596 total_num_never_executed += num_never_executed; 597 for (i = 0; i < 20; i++) 598 total_hist_br_prob[i] += hist_br_prob[i]; 599 600 fputc ('\n', dump_file); 601 fputc ('\n', dump_file); 602 } 603 604 free_aux_for_blocks (); 605} 606 607/* Load value histograms values whose description is stored in VALUES array 608 from .gcda file. */ 609 610static void 611compute_value_histograms (histogram_values values) 612{ 613 unsigned i, j, t, any; 614 unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS]; 615 gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS]; 616 gcov_type *act_count[GCOV_N_VALUE_COUNTERS]; 617 gcov_type *aact_count; 618 619 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) 620 n_histogram_counters[t] = 0; 621 622 for (i = 0; i < VEC_length (histogram_value, values); i++) 623 { 624 histogram_value hist = VEC_index (histogram_value, values, i); 625 n_histogram_counters[(int) hist->type] += hist->n_counters; 626 } 627 628 any = 0; 629 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) 630 { 631 if (!n_histogram_counters[t]) 632 { 633 histogram_counts[t] = NULL; 634 continue; 635 } 636 637 histogram_counts[t] = 638 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t), 639 n_histogram_counters[t], NULL); 640 if (histogram_counts[t]) 641 any = 1; 642 act_count[t] = histogram_counts[t]; 643 } 644 if (!any) 645 return; 646 647 for (i = 0; i < VEC_length (histogram_value, values); i++) 648 { 649 histogram_value hist = VEC_index (histogram_value, values, i); 650 tree stmt = hist->hvalue.stmt; 651 stmt_ann_t ann = get_stmt_ann (stmt); 652 653 t = (int) hist->type; 654 655 aact_count = act_count[t]; 656 act_count[t] += hist->n_counters; 657 658 hist->hvalue.next = ann->histograms; 659 ann->histograms = hist; 660 hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); 661 for (j = 0; j < hist->n_counters; j++) 662 hist->hvalue.counters[j] = aact_count[j]; 663 } 664 665 for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) 666 if (histogram_counts[t]) 667 free (histogram_counts[t]); 668} 669 670/* The entry basic block will be moved around so that it has index=1, 671 there is nothing at index 0 and the exit is at n_basic_block. */ 672#define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1) 673/* When passed NULL as file_name, initialize. 674 When passed something else, output the necessary commands to change 675 line to LINE and offset to FILE_NAME. */ 676static void 677output_location (char const *file_name, int line, 678 gcov_position_t *offset, basic_block bb) 679{ 680 static char const *prev_file_name; 681 static int prev_line; 682 bool name_differs, line_differs; 683 684 if (!file_name) 685 { 686 prev_file_name = NULL; 687 prev_line = -1; 688 return; 689 } 690 691 name_differs = !prev_file_name || strcmp (file_name, prev_file_name); 692 line_differs = prev_line != line; 693 694 if (name_differs || line_differs) 695 { 696 if (!*offset) 697 { 698 *offset = gcov_write_tag (GCOV_TAG_LINES); 699 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb)); 700 name_differs = line_differs=true; 701 } 702 703 /* If this is a new source file, then output the 704 file's name to the .bb file. */ 705 if (name_differs) 706 { 707 prev_file_name = file_name; 708 gcov_write_unsigned (0); 709 gcov_write_string (prev_file_name); 710 } 711 if (line_differs) 712 { 713 gcov_write_unsigned (line); 714 prev_line = line; 715 } 716 } 717} 718 719/* Instrument and/or analyze program behavior based on program flow graph. 720 In either case, this function builds a flow graph for the function being 721 compiled. The flow graph is stored in BB_GRAPH. 722 723 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in 724 the flow graph that are needed to reconstruct the dynamic behavior of the 725 flow graph. 726 727 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary 728 information from a data file containing edge count information from previous 729 executions of the function being compiled. In this case, the flow graph is 730 annotated with actual execution counts, which are later propagated into the 731 rtl for optimization purposes. 732 733 Main entry point of this file. */ 734 735void 736branch_prob (void) 737{ 738 basic_block bb; 739 unsigned i; 740 unsigned num_edges, ignored_edges; 741 unsigned num_instrumented; 742 struct edge_list *el; 743 histogram_values values = NULL; 744 745 total_num_times_called++; 746 747 flow_call_edges_add (NULL); 748 add_noreturn_fake_exit_edges (); 749 750 /* We can't handle cyclic regions constructed using abnormal edges. 751 To avoid these we replace every source of abnormal edge by a fake 752 edge from entry node and every destination by fake edge to exit. 753 This keeps graph acyclic and our calculation exact for all normal 754 edges except for exit and entrance ones. 755 756 We also add fake exit edges for each call and asm statement in the 757 basic, since it may not return. */ 758 759 FOR_EACH_BB (bb) 760 { 761 int need_exit_edge = 0, need_entry_edge = 0; 762 int have_exit_edge = 0, have_entry_edge = 0; 763 edge e; 764 edge_iterator ei; 765 766 /* Functions returning multiple times are not handled by extra edges. 767 Instead we simply allow negative counts on edges from exit to the 768 block past call and corresponding probabilities. We can't go 769 with the extra edges because that would result in flowgraph that 770 needs to have fake edges outside the spanning tree. */ 771 772 FOR_EACH_EDGE (e, ei, bb->succs) 773 { 774 block_stmt_iterator bsi; 775 tree last = NULL; 776 777 /* It may happen that there are compiler generated statements 778 without a locus at all. Go through the basic block from the 779 last to the first statement looking for a locus. */ 780 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 781 { 782 last = bsi_stmt (bsi); 783 if (EXPR_LOCUS (last)) 784 break; 785 } 786 787 /* Edge with goto locus might get wrong coverage info unless 788 it is the only edge out of BB. 789 Don't do that when the locuses match, so 790 if (blah) goto something; 791 is not computed twice. */ 792 if (last && EXPR_LOCUS (last) 793 && e->goto_locus 794 && !single_succ_p (bb) 795#ifdef USE_MAPPED_LOCATION 796 && (LOCATION_FILE (e->goto_locus) 797 != LOCATION_FILE (EXPR_LOCATION (last)) 798 || (LOCATION_LINE (e->goto_locus) 799 != LOCATION_LINE (EXPR_LOCATION (last))))) 800#else 801 && (e->goto_locus->file != EXPR_LOCUS (last)->file 802 || (e->goto_locus->line != EXPR_LOCUS (last)->line))) 803#endif 804 { 805 basic_block new = split_edge (e); 806 single_succ_edge (new)->goto_locus = e->goto_locus; 807 } 808 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 809 && e->dest != EXIT_BLOCK_PTR) 810 need_exit_edge = 1; 811 if (e->dest == EXIT_BLOCK_PTR) 812 have_exit_edge = 1; 813 } 814 FOR_EACH_EDGE (e, ei, bb->preds) 815 { 816 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 817 && e->src != ENTRY_BLOCK_PTR) 818 need_entry_edge = 1; 819 if (e->src == ENTRY_BLOCK_PTR) 820 have_entry_edge = 1; 821 } 822 823 if (need_exit_edge && !have_exit_edge) 824 { 825 if (dump_file) 826 fprintf (dump_file, "Adding fake exit edge to bb %i\n", 827 bb->index); 828 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 829 } 830 if (need_entry_edge && !have_entry_edge) 831 { 832 if (dump_file) 833 fprintf (dump_file, "Adding fake entry edge to bb %i\n", 834 bb->index); 835 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE); 836 } 837 } 838 839 el = create_edge_list (); 840 num_edges = NUM_EDGES (el); 841 alloc_aux_for_edges (sizeof (struct edge_info)); 842 843 /* The basic blocks are expected to be numbered sequentially. */ 844 compact_blocks (); 845 846 ignored_edges = 0; 847 for (i = 0 ; i < num_edges ; i++) 848 { 849 edge e = INDEX_EDGE (el, i); 850 e->count = 0; 851 852 /* Mark edges we've replaced by fake edges above as ignored. */ 853 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 854 && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR) 855 { 856 EDGE_INFO (e)->ignore = 1; 857 ignored_edges++; 858 } 859 } 860 861 /* Create spanning tree from basic block graph, mark each edge that is 862 on the spanning tree. We insert as many abnormal and critical edges 863 as possible to minimize number of edge splits necessary. */ 864 865 find_spanning_tree (el); 866 867 /* Fake edges that are not on the tree will not be instrumented, so 868 mark them ignored. */ 869 for (num_instrumented = i = 0; i < num_edges; i++) 870 { 871 edge e = INDEX_EDGE (el, i); 872 struct edge_info *inf = EDGE_INFO (e); 873 874 if (inf->ignore || inf->on_tree) 875 /*NOP*/; 876 else if (e->flags & EDGE_FAKE) 877 { 878 inf->ignore = 1; 879 ignored_edges++; 880 } 881 else 882 num_instrumented++; 883 } 884 885 total_num_blocks += n_basic_blocks; 886 if (dump_file) 887 fprintf (dump_file, "%d basic blocks\n", n_basic_blocks); 888 889 total_num_edges += num_edges; 890 if (dump_file) 891 fprintf (dump_file, "%d edges\n", num_edges); 892 893 total_num_edges_ignored += ignored_edges; 894 if (dump_file) 895 fprintf (dump_file, "%d ignored edges\n", ignored_edges); 896 897 /* Write the data from which gcov can reconstruct the basic block 898 graph. */ 899 900 /* Basic block flags */ 901 if (coverage_begin_output ()) 902 { 903 gcov_position_t offset; 904 905 offset = gcov_write_tag (GCOV_TAG_BLOCKS); 906 for (i = 0; i != (unsigned) (n_basic_blocks); i++) 907 gcov_write_unsigned (0); 908 gcov_write_length (offset); 909 } 910 911 /* Keep all basic block indexes nonnegative in the gcov output. 912 Index 0 is used for entry block, last index is for exit block. 913 */ 914 ENTRY_BLOCK_PTR->index = 1; 915 EXIT_BLOCK_PTR->index = last_basic_block; 916 917 /* Arcs */ 918 if (coverage_begin_output ()) 919 { 920 gcov_position_t offset; 921 922 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 923 { 924 edge e; 925 edge_iterator ei; 926 927 offset = gcov_write_tag (GCOV_TAG_ARCS); 928 gcov_write_unsigned (BB_TO_GCOV_INDEX (bb)); 929 930 FOR_EACH_EDGE (e, ei, bb->succs) 931 { 932 struct edge_info *i = EDGE_INFO (e); 933 if (!i->ignore) 934 { 935 unsigned flag_bits = 0; 936 937 if (i->on_tree) 938 flag_bits |= GCOV_ARC_ON_TREE; 939 if (e->flags & EDGE_FAKE) 940 flag_bits |= GCOV_ARC_FAKE; 941 if (e->flags & EDGE_FALLTHRU) 942 flag_bits |= GCOV_ARC_FALLTHROUGH; 943 /* On trees we don't have fallthru flags, but we can 944 recompute them from CFG shape. */ 945 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE) 946 && e->src->next_bb == e->dest) 947 flag_bits |= GCOV_ARC_FALLTHROUGH; 948 949 gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest)); 950 gcov_write_unsigned (flag_bits); 951 } 952 } 953 954 gcov_write_length (offset); 955 } 956 } 957 958 /* Line numbers. */ 959 if (coverage_begin_output ()) 960 { 961 gcov_position_t offset; 962 963 /* Initialize the output. */ 964 output_location (NULL, 0, NULL, NULL); 965 966 FOR_EACH_BB (bb) 967 { 968 block_stmt_iterator bsi; 969 970 offset = 0; 971 972 if (bb == ENTRY_BLOCK_PTR->next_bb) 973 { 974 expanded_location curr_location = 975 expand_location (DECL_SOURCE_LOCATION (current_function_decl)); 976 output_location (curr_location.file, curr_location.line, 977 &offset, bb); 978 } 979 980 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 981 { 982 tree stmt = bsi_stmt (bsi); 983 if (EXPR_HAS_LOCATION (stmt)) 984 output_location (EXPR_FILENAME (stmt), EXPR_LINENO (stmt), 985 &offset, bb); 986 } 987 988 /* Notice GOTO expressions we eliminated while constructing the 989 CFG. */ 990 if (single_succ_p (bb) && single_succ_edge (bb)->goto_locus) 991 { 992 /* ??? source_locus type is marked deprecated in input.h. */ 993 source_locus curr_location = single_succ_edge (bb)->goto_locus; 994 /* ??? The FILE/LINE API is inconsistent for these cases. */ 995#ifdef USE_MAPPED_LOCATION 996 output_location (LOCATION_FILE (curr_location), 997 LOCATION_LINE (curr_location), &offset, bb); 998#else 999 output_location (curr_location->file, curr_location->line, 1000 &offset, bb); 1001#endif 1002 } 1003 1004 if (offset) 1005 { 1006 /* A file of NULL indicates the end of run. */ 1007 gcov_write_unsigned (0); 1008 gcov_write_string (NULL); 1009 gcov_write_length (offset); 1010 } 1011 } 1012 } 1013 1014 ENTRY_BLOCK_PTR->index = ENTRY_BLOCK; 1015 EXIT_BLOCK_PTR->index = EXIT_BLOCK; 1016#undef BB_TO_GCOV_INDEX 1017 1018 if (flag_profile_values) 1019 find_values_to_profile (&values); 1020 1021 if (flag_branch_probabilities) 1022 { 1023 compute_branch_probabilities (); 1024 if (flag_profile_values) 1025 compute_value_histograms (values); 1026 } 1027 1028 remove_fake_edges (); 1029 1030 /* For each edge not on the spanning tree, add counting code. */ 1031 if (profile_arc_flag 1032 && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented)) 1033 { 1034 unsigned n_instrumented; 1035 1036 profile_hooks->init_edge_profiler (); 1037 1038 n_instrumented = instrument_edges (el); 1039 1040 gcc_assert (n_instrumented == num_instrumented); 1041 1042 if (flag_profile_values) 1043 instrument_values (values); 1044 1045 /* Commit changes done by instrumentation. */ 1046 bsi_commit_edge_inserts (); 1047 } 1048 1049 free_aux_for_edges (); 1050 1051 VEC_free (histogram_value, heap, values); 1052 free_edge_list (el); 1053 if (flag_branch_probabilities) 1054 profile_status = PROFILE_READ; 1055 coverage_end_function (); 1056} 1057 1058/* Union find algorithm implementation for the basic blocks using 1059 aux fields. */ 1060 1061static basic_block 1062find_group (basic_block bb) 1063{ 1064 basic_block group = bb, bb1; 1065 1066 while ((basic_block) group->aux != group) 1067 group = (basic_block) group->aux; 1068 1069 /* Compress path. */ 1070 while ((basic_block) bb->aux != group) 1071 { 1072 bb1 = (basic_block) bb->aux; 1073 bb->aux = (void *) group; 1074 bb = bb1; 1075 } 1076 return group; 1077} 1078 1079static void 1080union_groups (basic_block bb1, basic_block bb2) 1081{ 1082 basic_block bb1g = find_group (bb1); 1083 basic_block bb2g = find_group (bb2); 1084 1085 /* ??? I don't have a place for the rank field. OK. Lets go w/o it, 1086 this code is unlikely going to be performance problem anyway. */ 1087 gcc_assert (bb1g != bb2g); 1088 1089 bb1g->aux = bb2g; 1090} 1091 1092/* This function searches all of the edges in the program flow graph, and puts 1093 as many bad edges as possible onto the spanning tree. Bad edges include 1094 abnormals edges, which can't be instrumented at the moment. Since it is 1095 possible for fake edges to form a cycle, we will have to develop some 1096 better way in the future. Also put critical edges to the tree, since they 1097 are more expensive to instrument. */ 1098 1099static void 1100find_spanning_tree (struct edge_list *el) 1101{ 1102 int i; 1103 int num_edges = NUM_EDGES (el); 1104 basic_block bb; 1105 1106 /* We use aux field for standard union-find algorithm. */ 1107 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1108 bb->aux = bb; 1109 1110 /* Add fake edge exit to entry we can't instrument. */ 1111 union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR); 1112 1113 /* First add all abnormal edges to the tree unless they form a cycle. Also 1114 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind 1115 setting return value from function. */ 1116 for (i = 0; i < num_edges; i++) 1117 { 1118 edge e = INDEX_EDGE (el, i); 1119 if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE)) 1120 || e->dest == EXIT_BLOCK_PTR) 1121 && !EDGE_INFO (e)->ignore 1122 && (find_group (e->src) != find_group (e->dest))) 1123 { 1124 if (dump_file) 1125 fprintf (dump_file, "Abnormal edge %d to %d put to tree\n", 1126 e->src->index, e->dest->index); 1127 EDGE_INFO (e)->on_tree = 1; 1128 union_groups (e->src, e->dest); 1129 } 1130 } 1131 1132 /* Now insert all critical edges to the tree unless they form a cycle. */ 1133 for (i = 0; i < num_edges; i++) 1134 { 1135 edge e = INDEX_EDGE (el, i); 1136 if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore 1137 && find_group (e->src) != find_group (e->dest)) 1138 { 1139 if (dump_file) 1140 fprintf (dump_file, "Critical edge %d to %d put to tree\n", 1141 e->src->index, e->dest->index); 1142 EDGE_INFO (e)->on_tree = 1; 1143 union_groups (e->src, e->dest); 1144 } 1145 } 1146 1147 /* And now the rest. */ 1148 for (i = 0; i < num_edges; i++) 1149 { 1150 edge e = INDEX_EDGE (el, i); 1151 if (!EDGE_INFO (e)->ignore 1152 && find_group (e->src) != find_group (e->dest)) 1153 { 1154 if (dump_file) 1155 fprintf (dump_file, "Normal edge %d to %d put to tree\n", 1156 e->src->index, e->dest->index); 1157 EDGE_INFO (e)->on_tree = 1; 1158 union_groups (e->src, e->dest); 1159 } 1160 } 1161 1162 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1163 bb->aux = NULL; 1164} 1165 1166/* Perform file-level initialization for branch-prob processing. */ 1167 1168void 1169init_branch_prob (void) 1170{ 1171 int i; 1172 1173 total_num_blocks = 0; 1174 total_num_edges = 0; 1175 total_num_edges_ignored = 0; 1176 total_num_edges_instrumented = 0; 1177 total_num_blocks_created = 0; 1178 total_num_passes = 0; 1179 total_num_times_called = 0; 1180 total_num_branches = 0; 1181 total_num_never_executed = 0; 1182 for (i = 0; i < 20; i++) 1183 total_hist_br_prob[i] = 0; 1184} 1185 1186/* Performs file-level cleanup after branch-prob processing 1187 is completed. */ 1188 1189void 1190end_branch_prob (void) 1191{ 1192 if (dump_file) 1193 { 1194 fprintf (dump_file, "\n"); 1195 fprintf (dump_file, "Total number of blocks: %d\n", 1196 total_num_blocks); 1197 fprintf (dump_file, "Total number of edges: %d\n", total_num_edges); 1198 fprintf (dump_file, "Total number of ignored edges: %d\n", 1199 total_num_edges_ignored); 1200 fprintf (dump_file, "Total number of instrumented edges: %d\n", 1201 total_num_edges_instrumented); 1202 fprintf (dump_file, "Total number of blocks created: %d\n", 1203 total_num_blocks_created); 1204 fprintf (dump_file, "Total number of graph solution passes: %d\n", 1205 total_num_passes); 1206 if (total_num_times_called != 0) 1207 fprintf (dump_file, "Average number of graph solution passes: %d\n", 1208 (total_num_passes + (total_num_times_called >> 1)) 1209 / total_num_times_called); 1210 fprintf (dump_file, "Total number of branches: %d\n", 1211 total_num_branches); 1212 fprintf (dump_file, "Total number of branches never executed: %d\n", 1213 total_num_never_executed); 1214 if (total_num_branches) 1215 { 1216 int i; 1217 1218 for (i = 0; i < 10; i++) 1219 fprintf (dump_file, "%d%% branches in range %d-%d%%\n", 1220 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100 1221 / total_num_branches, 5*i, 5*i+5); 1222 } 1223 } 1224} 1225 1226/* Set up hooks to enable tree-based profiling. */ 1227 1228void 1229tree_register_profile_hooks (void) 1230{ 1231 gcc_assert (ir_type ()); 1232 profile_hooks = &tree_profile_hooks; 1233} 1234 1235