1234949Sbapt/* Calculate branch probabilities, and basic block execution counts. 2234949Sbapt Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999, 3234949Sbapt 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 4234949Sbapt Contributed by James E. Wilson, UC Berkeley/Cygnus Support; 5234949Sbapt based on some ideas from Dain Samples of UC Berkeley. 6234949Sbapt Further mangling by Bob Manson, Cygnus Support. 7234949Sbapt 8234949SbaptThis file is part of GCC. 9234949Sbapt 10234949SbaptGCC is free software; you can redistribute it and/or modify it under 11234949Sbaptthe terms of the GNU General Public License as published by the Free 12234949SbaptSoftware Foundation; either version 2, or (at your option) any later 13234949Sbaptversion. 14234949Sbapt 15234949SbaptGCC is distributed in the hope that it will be useful, but WITHOUT ANY 16234949SbaptWARRANTY; without even the implied warranty of MERCHANTABILITY or 17234949SbaptFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18234949Sbaptfor more details. 19234949Sbapt 20234949SbaptYou should have received a copy of the GNU General Public License 21234949Sbaptalong with GCC; see the file COPYING. If not, write to the Free 22234949SbaptSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 23234949Sbapt02110-1301, USA. */ 24234949Sbapt 25234949Sbapt/* Generate basic block profile instrumentation and auxiliary files. 26234949Sbapt Profile generation is optimized, so that not all arcs in the basic 27234949Sbapt block graph need instrumenting. First, the BB graph is closed with 28234949Sbapt one entry (function start), and one exit (function exit). Any 29234949Sbapt ABNORMAL_EDGE cannot be instrumented (because there is no control 30234949Sbapt path to place the code). We close the graph by inserting fake 31234949Sbapt EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal 32234949Sbapt edges that do not go to the exit_block. We ignore such abnormal 33234949Sbapt edges. Naturally these fake edges are never directly traversed, 34234949Sbapt and so *cannot* be directly instrumented. Some other graph 35234949Sbapt massaging is done. To optimize the instrumentation we generate the 36234949Sbapt BB minimal span tree, only edges that are not on the span tree 37234949Sbapt (plus the entry point) need instrumenting. From that information 38234949Sbapt all other edge counts can be deduced. By construction all fake 39234949Sbapt edges must be on the spanning tree. We also attempt to place 40234949Sbapt EDGE_CRITICAL edges on the spanning tree. 41234949Sbapt 42234949Sbapt The auxiliary files generated are <dumpbase>.gcno (at compile time) 43234949Sbapt and <dumpbase>.gcda (at run time). The format is 44234949Sbapt described in full in gcov-io.h. */ 45234949Sbapt 46234949Sbapt/* ??? Register allocation should use basic block execution counts to 47234949Sbapt give preference to the most commonly executed blocks. */ 48234949Sbapt 49234949Sbapt/* ??? Should calculate branch probabilities before instrumenting code, since 50234949Sbapt then we can use arc counts to help decide which arcs to instrument. */ 51234949Sbapt 52234949Sbapt#include "config.h" 53234949Sbapt#include "system.h" 54234949Sbapt#include "coretypes.h" 55234949Sbapt#include "tm.h" 56234949Sbapt#include "rtl.h" 57234949Sbapt#include "flags.h" 58234949Sbapt#include "output.h" 59234949Sbapt#include "regs.h" 60234949Sbapt#include "expr.h" 61234949Sbapt#include "function.h" 62234949Sbapt#include "toplev.h" 63234949Sbapt#include "coverage.h" 64234949Sbapt#include "value-prof.h" 65234949Sbapt#include "tree.h" 66234949Sbapt#include "cfghooks.h" 67234949Sbapt#include "tree-flow.h" 68234949Sbapt#include "timevar.h" 69234949Sbapt#include "cfgloop.h" 70234949Sbapt#include "tree-pass.h" 71234949Sbapt 72234949Sbapt/* Hooks for profiling. */ 73234949Sbaptstatic struct profile_hooks* profile_hooks; 74234949Sbapt 75234949Sbapt/* Additional information about the edges we need. */ 76234949Sbaptstruct edge_info { 77234949Sbapt unsigned int count_valid : 1; 78234949Sbapt 79234949Sbapt /* Is on the spanning tree. */ 80234949Sbapt unsigned int on_tree : 1; 81234949Sbapt 82234949Sbapt /* Pretend this edge does not exist (it is abnormal and we've 83234949Sbapt inserted a fake to compensate). */ 84234949Sbapt unsigned int ignore : 1; 85234949Sbapt}; 86234949Sbapt 87234949Sbaptstruct bb_info { 88234949Sbapt unsigned int count_valid : 1; 89234949Sbapt 90234949Sbapt /* Number of successor and predecessor edges. */ 91234949Sbapt gcov_type succ_count; 92234949Sbapt gcov_type pred_count; 93234949Sbapt}; 94234949Sbapt 95234949Sbapt#define EDGE_INFO(e) ((struct edge_info *) (e)->aux) 96234949Sbapt#define BB_INFO(b) ((struct bb_info *) (b)->aux) 97234949Sbapt 98234949Sbapt/* Counter summary from the last set of coverage counts read. */ 99234949Sbapt 100234949Sbaptconst struct gcov_ctr_summary *profile_info; 101234949Sbapt 102234949Sbapt/* Collect statistics on the performance of this pass for the entire source 103234949Sbapt file. */ 104234949Sbapt 105234949Sbaptstatic int total_num_blocks; 106234949Sbaptstatic int total_num_edges; 107234949Sbaptstatic int total_num_edges_ignored; 108234949Sbaptstatic int total_num_edges_instrumented; 109234949Sbaptstatic int total_num_blocks_created; 110234949Sbaptstatic int total_num_passes; 111234949Sbaptstatic int total_num_times_called; 112234949Sbaptstatic int total_hist_br_prob[20]; 113234949Sbaptstatic int total_num_never_executed; 114234949Sbaptstatic int total_num_branches; 115234949Sbapt 116234949Sbapt/* Forward declarations. */ 117234949Sbaptstatic void find_spanning_tree (struct edge_list *); 118234949Sbaptstatic unsigned instrument_edges (struct edge_list *); 119234949Sbaptstatic void instrument_values (histogram_values); 120234949Sbaptstatic void compute_branch_probabilities (void); 121234949Sbaptstatic void compute_value_histograms (histogram_values); 122234949Sbaptstatic gcov_type * get_exec_counts (void); 123234949Sbaptstatic basic_block find_group (basic_block); 124234949Sbaptstatic void union_groups (basic_block, basic_block); 125234949Sbapt 126234949Sbapt 127234949Sbapt/* Add edge instrumentation code to the entire insn chain. 128234949Sbapt 129234949Sbapt F is the first insn of the chain. 130234949Sbapt NUM_BLOCKS is the number of basic blocks found in F. */ 131234949Sbapt 132234949Sbaptstatic unsigned 133234949Sbaptinstrument_edges (struct edge_list *el) 134234949Sbapt{ 135234949Sbapt unsigned num_instr_edges = 0; 136234949Sbapt int num_edges = NUM_EDGES (el); 137234949Sbapt basic_block bb; 138234949Sbapt 139234949Sbapt FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 140234949Sbapt { 141234949Sbapt edge e; 142234949Sbapt edge_iterator ei; 143234949Sbapt 144234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 145234949Sbapt { 146234949Sbapt struct edge_info *inf = EDGE_INFO (e); 147234949Sbapt 148234949Sbapt if (!inf->ignore && !inf->on_tree) 149234949Sbapt { 150234949Sbapt gcc_assert (!(e->flags & EDGE_ABNORMAL)); 151234949Sbapt if (dump_file) 152234949Sbapt fprintf (dump_file, "Edge %d to %d instrumented%s\n", 153234949Sbapt e->src->index, e->dest->index, 154234949Sbapt EDGE_CRITICAL_P (e) ? " (and split)" : ""); 155234949Sbapt (profile_hooks->gen_edge_profiler) (num_instr_edges++, e); 156234949Sbapt } 157234949Sbapt } 158234949Sbapt } 159234949Sbapt 160234949Sbapt total_num_blocks_created += num_edges; 161234949Sbapt if (dump_file) 162234949Sbapt fprintf (dump_file, "%d edges instrumented\n", num_instr_edges); 163234949Sbapt return num_instr_edges; 164234949Sbapt} 165234949Sbapt 166234949Sbapt/* Add code to measure histograms for values in list VALUES. */ 167234949Sbaptstatic void 168234949Sbaptinstrument_values (histogram_values values) 169234949Sbapt{ 170234949Sbapt unsigned i, t; 171234949Sbapt 172234949Sbapt /* Emit code to generate the histograms before the insns. */ 173234949Sbapt 174234949Sbapt for (i = 0; i < VEC_length (histogram_value, values); i++) 175234949Sbapt { 176234949Sbapt histogram_value hist = VEC_index (histogram_value, values, i); 177234949Sbapt switch (hist->type) 178234949Sbapt { 179234949Sbapt case HIST_TYPE_INTERVAL: 180234949Sbapt t = GCOV_COUNTER_V_INTERVAL; 181234949Sbapt break; 182234949Sbapt 183234949Sbapt case HIST_TYPE_POW2: 184234949Sbapt t = GCOV_COUNTER_V_POW2; 185234949Sbapt break; 186234949Sbapt 187234949Sbapt case HIST_TYPE_SINGLE_VALUE: 188234949Sbapt t = GCOV_COUNTER_V_SINGLE; 189234949Sbapt break; 190234949Sbapt 191234949Sbapt case HIST_TYPE_CONST_DELTA: 192234949Sbapt t = GCOV_COUNTER_V_DELTA; 193234949Sbapt break; 194234949Sbapt 195234949Sbapt default: 196234949Sbapt gcc_unreachable (); 197234949Sbapt } 198234949Sbapt if (!coverage_counter_alloc (t, hist->n_counters)) 199234949Sbapt continue; 200234949Sbapt 201234949Sbapt switch (hist->type) 202234949Sbapt { 203234949Sbapt case HIST_TYPE_INTERVAL: 204234949Sbapt (profile_hooks->gen_interval_profiler) (hist, t, 0); 205234949Sbapt break; 206234949Sbapt 207234949Sbapt case HIST_TYPE_POW2: 208234949Sbapt (profile_hooks->gen_pow2_profiler) (hist, t, 0); 209234949Sbapt break; 210234949Sbapt 211234949Sbapt case HIST_TYPE_SINGLE_VALUE: 212234949Sbapt (profile_hooks->gen_one_value_profiler) (hist, t, 0); 213234949Sbapt break; 214234949Sbapt 215234949Sbapt case HIST_TYPE_CONST_DELTA: 216234949Sbapt (profile_hooks->gen_const_delta_profiler) (hist, t, 0); 217234949Sbapt break; 218234949Sbapt 219234949Sbapt default: 220234949Sbapt gcc_unreachable (); 221234949Sbapt } 222234949Sbapt } 223234949Sbapt} 224234949Sbapt 225234949Sbapt 226234949Sbapt/* Computes hybrid profile for all matching entries in da_file. */ 227234949Sbapt 228234949Sbaptstatic gcov_type * 229234949Sbaptget_exec_counts (void) 230234949Sbapt{ 231234949Sbapt unsigned num_edges = 0; 232234949Sbapt basic_block bb; 233234949Sbapt gcov_type *counts; 234234949Sbapt 235234949Sbapt /* Count the edges to be (possibly) instrumented. */ 236234949Sbapt FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 237234949Sbapt { 238234949Sbapt edge e; 239234949Sbapt edge_iterator ei; 240234949Sbapt 241234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 242234949Sbapt if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) 243234949Sbapt num_edges++; 244234949Sbapt } 245234949Sbapt 246234949Sbapt counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, &profile_info); 247234949Sbapt if (!counts) 248234949Sbapt return NULL; 249234949Sbapt 250234949Sbapt if (dump_file && profile_info) 251234949Sbapt fprintf(dump_file, "Merged %u profiles with maximal count %u.\n", 252234949Sbapt profile_info->runs, (unsigned) profile_info->sum_max); 253234949Sbapt 254234949Sbapt return counts; 255234949Sbapt} 256234949Sbapt 257234949Sbapt 258234949Sbapt/* Compute the branch probabilities for the various branches. 259234949Sbapt Annotate them accordingly. */ 260234949Sbapt 261234949Sbaptstatic void 262234949Sbaptcompute_branch_probabilities (void) 263234949Sbapt{ 264234949Sbapt basic_block bb; 265234949Sbapt int i; 266234949Sbapt int num_edges = 0; 267234949Sbapt int changes; 268234949Sbapt int passes; 269234949Sbapt int hist_br_prob[20]; 270234949Sbapt int num_never_executed; 271234949Sbapt int num_branches; 272234949Sbapt gcov_type *exec_counts = get_exec_counts (); 273234949Sbapt int exec_counts_pos = 0; 274234949Sbapt 275234949Sbapt /* Very simple sanity checks so we catch bugs in our profiling code. */ 276234949Sbapt if (profile_info) 277234949Sbapt { 278234949Sbapt if (profile_info->run_max * profile_info->runs < profile_info->sum_max) 279234949Sbapt { 280234949Sbapt error ("corrupted profile info: run_max * runs < sum_max"); 281234949Sbapt exec_counts = NULL; 282234949Sbapt } 283234949Sbapt 284234949Sbapt if (profile_info->sum_all < profile_info->sum_max) 285234949Sbapt { 286234949Sbapt error ("corrupted profile info: sum_all is smaller than sum_max"); 287234949Sbapt exec_counts = NULL; 288234949Sbapt } 289234949Sbapt } 290234949Sbapt 291234949Sbapt /* Attach extra info block to each bb. */ 292234949Sbapt 293234949Sbapt alloc_aux_for_blocks (sizeof (struct bb_info)); 294234949Sbapt FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 295234949Sbapt { 296234949Sbapt edge e; 297234949Sbapt edge_iterator ei; 298234949Sbapt 299234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 300234949Sbapt if (!EDGE_INFO (e)->ignore) 301234949Sbapt BB_INFO (bb)->succ_count++; 302234949Sbapt FOR_EACH_EDGE (e, ei, bb->preds) 303234949Sbapt if (!EDGE_INFO (e)->ignore) 304234949Sbapt BB_INFO (bb)->pred_count++; 305234949Sbapt } 306234949Sbapt 307234949Sbapt /* Avoid predicting entry on exit nodes. */ 308234949Sbapt BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2; 309234949Sbapt BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2; 310234949Sbapt 311234949Sbapt /* For each edge not on the spanning tree, set its execution count from 312234949Sbapt the .da file. */ 313234949Sbapt 314234949Sbapt /* The first count in the .da file is the number of times that the function 315234949Sbapt was entered. This is the exec_count for block zero. */ 316234949Sbapt 317234949Sbapt FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 318234949Sbapt { 319234949Sbapt edge e; 320234949Sbapt edge_iterator ei; 321234949Sbapt 322234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 323234949Sbapt if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) 324234949Sbapt { 325234949Sbapt num_edges++; 326234949Sbapt if (exec_counts) 327234949Sbapt { 328234949Sbapt e->count = exec_counts[exec_counts_pos++]; 329234949Sbapt if (e->count > profile_info->sum_max) 330234949Sbapt { 331234949Sbapt error ("corrupted profile info: edge from %i to %i exceeds maximal count", 332234949Sbapt bb->index, e->dest->index); 333234949Sbapt } 334234949Sbapt } 335234949Sbapt else 336234949Sbapt e->count = 0; 337234949Sbapt 338234949Sbapt EDGE_INFO (e)->count_valid = 1; 339234949Sbapt BB_INFO (bb)->succ_count--; 340234949Sbapt BB_INFO (e->dest)->pred_count--; 341234949Sbapt if (dump_file) 342234949Sbapt { 343234949Sbapt fprintf (dump_file, "\nRead edge from %i to %i, count:", 344234949Sbapt bb->index, e->dest->index); 345234949Sbapt fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, 346234949Sbapt (HOST_WIDEST_INT) e->count); 347234949Sbapt } 348234949Sbapt } 349234949Sbapt } 350234949Sbapt 351234949Sbapt if (dump_file) 352234949Sbapt fprintf (dump_file, "\n%d edge counts read\n", num_edges); 353234949Sbapt 354234949Sbapt /* For every block in the file, 355234949Sbapt - if every exit/entrance edge has a known count, then set the block count 356234949Sbapt - if the block count is known, and every exit/entrance edge but one has 357234949Sbapt a known execution count, then set the count of the remaining edge 358234949Sbapt 359234949Sbapt As edge counts are set, decrement the succ/pred count, but don't delete 360234949Sbapt the edge, that way we can easily tell when all edges are known, or only 361234949Sbapt one edge is unknown. */ 362234949Sbapt 363234949Sbapt /* The order that the basic blocks are iterated through is important. 364234949Sbapt Since the code that finds spanning trees starts with block 0, low numbered 365234949Sbapt edges are put on the spanning tree in preference to high numbered edges. 366234949Sbapt Hence, most instrumented edges are at the end. Graph solving works much 367234949Sbapt faster if we propagate numbers from the end to the start. 368234949Sbapt 369234949Sbapt This takes an average of slightly more than 3 passes. */ 370234949Sbapt 371234949Sbapt changes = 1; 372234949Sbapt passes = 0; 373234949Sbapt while (changes) 374234949Sbapt { 375234949Sbapt passes++; 376234949Sbapt changes = 0; 377234949Sbapt FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb) 378234949Sbapt { 379234949Sbapt struct bb_info *bi = BB_INFO (bb); 380234949Sbapt if (! bi->count_valid) 381234949Sbapt { 382234949Sbapt if (bi->succ_count == 0) 383234949Sbapt { 384234949Sbapt edge e; 385234949Sbapt edge_iterator ei; 386234949Sbapt gcov_type total = 0; 387234949Sbapt 388234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 389234949Sbapt total += e->count; 390234949Sbapt bb->count = total; 391234949Sbapt bi->count_valid = 1; 392234949Sbapt changes = 1; 393234949Sbapt } 394234949Sbapt else if (bi->pred_count == 0) 395234949Sbapt { 396251143Sbapt edge e; 397234949Sbapt edge_iterator ei; 398234949Sbapt gcov_type total = 0; 399234949Sbapt 400234949Sbapt FOR_EACH_EDGE (e, ei, bb->preds) 401234949Sbapt total += e->count; 402234949Sbapt bb->count = total; 403234949Sbapt bi->count_valid = 1; 404234949Sbapt changes = 1; 405234949Sbapt } 406234949Sbapt } 407234949Sbapt if (bi->count_valid) 408234949Sbapt { 409234949Sbapt if (bi->succ_count == 1) 410234949Sbapt { 411234949Sbapt edge e; 412234949Sbapt edge_iterator ei; 413234949Sbapt gcov_type total = 0; 414234949Sbapt 415234949Sbapt /* One of the counts will be invalid, but it is zero, 416234949Sbapt so adding it in also doesn't hurt. */ 417234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 418234949Sbapt total += e->count; 419234949Sbapt 420234949Sbapt /* Seedgeh for the invalid edge, and set its count. */ 421234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 422234949Sbapt if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) 423234949Sbapt break; 424234949Sbapt 425234949Sbapt /* Calculate count for remaining edge by conservation. */ 426234949Sbapt total = bb->count - total; 427234949Sbapt 428234949Sbapt gcc_assert (e); 429234949Sbapt EDGE_INFO (e)->count_valid = 1; 430234949Sbapt e->count = total; 431234949Sbapt bi->succ_count--; 432234949Sbapt 433234949Sbapt BB_INFO (e->dest)->pred_count--; 434234949Sbapt changes = 1; 435234949Sbapt } 436234949Sbapt if (bi->pred_count == 1) 437234949Sbapt { 438234949Sbapt edge e; 439234949Sbapt edge_iterator ei; 440234949Sbapt gcov_type total = 0; 441234949Sbapt 442234949Sbapt /* One of the counts will be invalid, but it is zero, 443234949Sbapt so adding it in also doesn't hurt. */ 444234949Sbapt FOR_EACH_EDGE (e, ei, bb->preds) 445234949Sbapt total += e->count; 446234949Sbapt 447234949Sbapt /* Search for the invalid edge, and set its count. */ 448234949Sbapt FOR_EACH_EDGE (e, ei, bb->preds) 449234949Sbapt if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore) 450234949Sbapt break; 451234949Sbapt 452234949Sbapt /* Calculate count for remaining edge by conservation. */ 453234949Sbapt total = bb->count - total + e->count; 454234949Sbapt 455234949Sbapt gcc_assert (e); 456234949Sbapt EDGE_INFO (e)->count_valid = 1; 457234949Sbapt e->count = total; 458234949Sbapt bi->pred_count--; 459234949Sbapt 460234949Sbapt BB_INFO (e->src)->succ_count--; 461234949Sbapt changes = 1; 462234949Sbapt } 463234949Sbapt } 464234949Sbapt } 465234949Sbapt } 466234949Sbapt if (dump_file) 467234949Sbapt dump_flow_info (dump_file, dump_flags); 468234949Sbapt 469234949Sbapt total_num_passes += passes; 470234949Sbapt if (dump_file) 471234949Sbapt fprintf (dump_file, "Graph solving took %d passes.\n\n", passes); 472234949Sbapt 473234949Sbapt /* If the graph has been correctly solved, every block will have a 474234949Sbapt succ and pred count of zero. */ 475234949Sbapt FOR_EACH_BB (bb) 476234949Sbapt { 477234949Sbapt gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count); 478234949Sbapt } 479234949Sbapt 480234949Sbapt /* For every edge, calculate its branch probability and add a reg_note 481234949Sbapt to the branch insn to indicate this. */ 482234949Sbapt 483234949Sbapt for (i = 0; i < 20; i++) 484234949Sbapt hist_br_prob[i] = 0; 485234949Sbapt num_never_executed = 0; 486234949Sbapt num_branches = 0; 487234949Sbapt 488234949Sbapt FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 489234949Sbapt { 490234949Sbapt edge e; 491234949Sbapt edge_iterator ei; 492234949Sbapt 493234949Sbapt if (bb->count < 0) 494234949Sbapt { 495234949Sbapt error ("corrupted profile info: number of iterations for basic block %d thought to be %i", 496234949Sbapt bb->index, (int)bb->count); 497234949Sbapt bb->count = 0; 498234949Sbapt } 499234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 500234949Sbapt { 501234949Sbapt /* Function may return twice in the cased the called function is 502234949Sbapt setjmp or calls fork, but we can't represent this by extra 503234949Sbapt edge from the entry, since extra edge from the exit is 504234949Sbapt already present. We get negative frequency from the entry 505234949Sbapt point. */ 506234949Sbapt if ((e->count < 0 507234949Sbapt && e->dest == EXIT_BLOCK_PTR) 508234949Sbapt || (e->count > bb->count 509251143Sbapt && e->dest != EXIT_BLOCK_PTR)) 510234949Sbapt { 511234949Sbapt if (block_ends_with_call_p (bb)) 512234949Sbapt e->count = e->count < 0 ? 0 : bb->count; 513234949Sbapt } 514234949Sbapt if (e->count < 0 || e->count > bb->count) 515234949Sbapt { 516234949Sbapt error ("corrupted profile info: number of executions for edge %d-%d thought to be %i", 517234949Sbapt e->src->index, e->dest->index, 518234949Sbapt (int)e->count); 519234949Sbapt e->count = bb->count / 2; 520234949Sbapt } 521234949Sbapt } 522234949Sbapt if (bb->count) 523234949Sbapt { 524234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 525234949Sbapt e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count; 526234949Sbapt if (bb->index >= NUM_FIXED_BLOCKS 527234949Sbapt && block_ends_with_condjump_p (bb) 528234949Sbapt && EDGE_COUNT (bb->succs) >= 2) 529234949Sbapt { 530234949Sbapt int prob; 531234949Sbapt edge e; 532234949Sbapt int index; 533234949Sbapt 534234949Sbapt /* Find the branch edge. It is possible that we do have fake 535234949Sbapt edges here. */ 536234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 537234949Sbapt if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU))) 538234949Sbapt break; 539234949Sbapt 540234949Sbapt prob = e->probability; 541234949Sbapt index = prob * 20 / REG_BR_PROB_BASE; 542234949Sbapt 543234949Sbapt if (index == 20) 544234949Sbapt index = 19; 545234949Sbapt hist_br_prob[index]++; 546234949Sbapt 547234949Sbapt num_branches++; 548234949Sbapt } 549234949Sbapt } 550234949Sbapt /* As a last resort, distribute the probabilities evenly. 551234949Sbapt Use simple heuristics that if there are normal edges, 552234949Sbapt give all abnormals frequency of 0, otherwise distribute the 553234949Sbapt frequency over abnormals (this is the case of noreturn 554234949Sbapt calls). */ 555234949Sbapt else if (profile_status == PROFILE_ABSENT) 556234949Sbapt { 557234949Sbapt int total = 0; 558234949Sbapt 559234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 560234949Sbapt if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 561234949Sbapt total ++; 562234949Sbapt if (total) 563234949Sbapt { 564234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 565234949Sbapt if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 566234949Sbapt e->probability = REG_BR_PROB_BASE / total; 567234949Sbapt else 568234949Sbapt e->probability = 0; 569234949Sbapt } 570234949Sbapt else 571234949Sbapt { 572234949Sbapt total += EDGE_COUNT (bb->succs); 573234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 574234949Sbapt e->probability = REG_BR_PROB_BASE / total; 575234949Sbapt } 576234949Sbapt if (bb->index >= NUM_FIXED_BLOCKS 577234949Sbapt && block_ends_with_condjump_p (bb) 578234949Sbapt && EDGE_COUNT (bb->succs) >= 2) 579234949Sbapt num_branches++, num_never_executed; 580234949Sbapt } 581234949Sbapt } 582234949Sbapt counts_to_freqs (); 583234949Sbapt 584234949Sbapt if (dump_file) 585234949Sbapt { 586234949Sbapt fprintf (dump_file, "%d branches\n", num_branches); 587234949Sbapt fprintf (dump_file, "%d branches never executed\n", 588234949Sbapt num_never_executed); 589234949Sbapt if (num_branches) 590234949Sbapt for (i = 0; i < 10; i++) 591234949Sbapt fprintf (dump_file, "%d%% branches in range %d-%d%%\n", 592234949Sbapt (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches, 593234949Sbapt 5 * i, 5 * i + 5); 594234949Sbapt 595234949Sbapt total_num_branches += num_branches; 596234949Sbapt total_num_never_executed += num_never_executed; 597234949Sbapt for (i = 0; i < 20; i++) 598234949Sbapt total_hist_br_prob[i] += hist_br_prob[i]; 599234949Sbapt 600234949Sbapt fputc ('\n', dump_file); 601234949Sbapt fputc ('\n', dump_file); 602234949Sbapt } 603234949Sbapt 604234949Sbapt free_aux_for_blocks (); 605234949Sbapt} 606234949Sbapt 607234949Sbapt/* Load value histograms values whose description is stored in VALUES array 608234949Sbapt from .gcda file. */ 609234949Sbapt 610234949Sbaptstatic void 611234949Sbaptcompute_value_histograms (histogram_values values) 612234949Sbapt{ 613234949Sbapt unsigned i, j, t, any; 614234949Sbapt unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS]; 615234949Sbapt gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS]; 616234949Sbapt gcov_type *act_count[GCOV_N_VALUE_COUNTERS]; 617234949Sbapt gcov_type *aact_count; 618234949Sbapt 619234949Sbapt for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) 620234949Sbapt n_histogram_counters[t] = 0; 621234949Sbapt 622234949Sbapt for (i = 0; i < VEC_length (histogram_value, values); i++) 623234949Sbapt { 624234949Sbapt histogram_value hist = VEC_index (histogram_value, values, i); 625234949Sbapt n_histogram_counters[(int) hist->type] += hist->n_counters; 626234949Sbapt } 627234949Sbapt 628234949Sbapt any = 0; 629234949Sbapt for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) 630234949Sbapt { 631234949Sbapt if (!n_histogram_counters[t]) 632234949Sbapt { 633234949Sbapt histogram_counts[t] = NULL; 634234949Sbapt continue; 635234949Sbapt } 636234949Sbapt 637234949Sbapt histogram_counts[t] = 638234949Sbapt get_coverage_counts (COUNTER_FOR_HIST_TYPE (t), 639234949Sbapt n_histogram_counters[t], NULL); 640234949Sbapt if (histogram_counts[t]) 641234949Sbapt any = 1; 642234949Sbapt act_count[t] = histogram_counts[t]; 643234949Sbapt } 644234949Sbapt if (!any) 645234949Sbapt return; 646234949Sbapt 647234949Sbapt for (i = 0; i < VEC_length (histogram_value, values); i++) 648234949Sbapt { 649234949Sbapt histogram_value hist = VEC_index (histogram_value, values, i); 650234949Sbapt tree stmt = hist->hvalue.stmt; 651234949Sbapt stmt_ann_t ann = get_stmt_ann (stmt); 652234949Sbapt 653234949Sbapt t = (int) hist->type; 654234949Sbapt 655234949Sbapt aact_count = act_count[t]; 656234949Sbapt act_count[t] += hist->n_counters; 657234949Sbapt 658234949Sbapt hist->hvalue.next = ann->histograms; 659234949Sbapt ann->histograms = hist; 660234949Sbapt hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); 661234949Sbapt for (j = 0; j < hist->n_counters; j++) 662234949Sbapt hist->hvalue.counters[j] = aact_count[j]; 663234949Sbapt } 664234949Sbapt 665234949Sbapt for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) 666234949Sbapt if (histogram_counts[t]) 667234949Sbapt free (histogram_counts[t]); 668234949Sbapt} 669234949Sbapt 670234949Sbapt/* The entry basic block will be moved around so that it has index=1, 671234949Sbapt there is nothing at index 0 and the exit is at n_basic_block. */ 672234949Sbapt#define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1) 673234949Sbapt/* When passed NULL as file_name, initialize. 674234949Sbapt When passed something else, output the necessary commands to change 675234949Sbapt line to LINE and offset to FILE_NAME. */ 676234949Sbaptstatic void 677234949Sbaptoutput_location (char const *file_name, int line, 678234949Sbapt gcov_position_t *offset, basic_block bb) 679234949Sbapt{ 680234949Sbapt static char const *prev_file_name; 681234949Sbapt static int prev_line; 682234949Sbapt bool name_differs, line_differs; 683234949Sbapt 684234949Sbapt if (!file_name) 685234949Sbapt { 686234949Sbapt prev_file_name = NULL; 687234949Sbapt prev_line = -1; 688234949Sbapt return; 689234949Sbapt } 690234949Sbapt 691234949Sbapt name_differs = !prev_file_name || strcmp (file_name, prev_file_name); 692234949Sbapt line_differs = prev_line != line; 693234949Sbapt 694234949Sbapt if (name_differs || line_differs) 695234949Sbapt { 696234949Sbapt if (!*offset) 697234949Sbapt { 698234949Sbapt *offset = gcov_write_tag (GCOV_TAG_LINES); 699234949Sbapt gcov_write_unsigned (BB_TO_GCOV_INDEX (bb)); 700234949Sbapt name_differs = line_differs=true; 701234949Sbapt } 702234949Sbapt 703234949Sbapt /* If this is a new source file, then output the 704234949Sbapt file's name to the .bb file. */ 705234949Sbapt if (name_differs) 706234949Sbapt { 707234949Sbapt prev_file_name = file_name; 708234949Sbapt gcov_write_unsigned (0); 709234949Sbapt gcov_write_string (prev_file_name); 710234949Sbapt } 711234949Sbapt if (line_differs) 712234949Sbapt { 713234949Sbapt gcov_write_unsigned (line); 714234949Sbapt prev_line = line; 715234949Sbapt } 716234949Sbapt } 717234949Sbapt} 718234949Sbapt 719234949Sbapt/* Instrument and/or analyze program behavior based on program flow graph. 720234949Sbapt In either case, this function builds a flow graph for the function being 721234949Sbapt compiled. The flow graph is stored in BB_GRAPH. 722234949Sbapt 723234949Sbapt When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in 724234949Sbapt the flow graph that are needed to reconstruct the dynamic behavior of the 725234949Sbapt flow graph. 726234949Sbapt 727234949Sbapt When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary 728234949Sbapt information from a data file containing edge count information from previous 729234949Sbapt executions of the function being compiled. In this case, the flow graph is 730234949Sbapt annotated with actual execution counts, which are later propagated into the 731234949Sbapt rtl for optimization purposes. 732234949Sbapt 733234949Sbapt Main entry point of this file. */ 734234949Sbapt 735234949Sbaptvoid 736234949Sbaptbranch_prob (void) 737234949Sbapt{ 738234949Sbapt basic_block bb; 739234949Sbapt unsigned i; 740234949Sbapt unsigned num_edges, ignored_edges; 741234949Sbapt unsigned num_instrumented; 742234949Sbapt struct edge_list *el; 743234949Sbapt histogram_values values = NULL; 744234949Sbapt 745234949Sbapt total_num_times_called++; 746234949Sbapt 747234949Sbapt flow_call_edges_add (NULL); 748234949Sbapt add_noreturn_fake_exit_edges (); 749234949Sbapt 750234949Sbapt /* We can't handle cyclic regions constructed using abnormal edges. 751234949Sbapt To avoid these we replace every source of abnormal edge by a fake 752234949Sbapt edge from entry node and every destination by fake edge to exit. 753234949Sbapt This keeps graph acyclic and our calculation exact for all normal 754234949Sbapt edges except for exit and entrance ones. 755234949Sbapt 756234949Sbapt We also add fake exit edges for each call and asm statement in the 757234949Sbapt basic, since it may not return. */ 758234949Sbapt 759234949Sbapt FOR_EACH_BB (bb) 760234949Sbapt { 761234949Sbapt int need_exit_edge = 0, need_entry_edge = 0; 762234949Sbapt int have_exit_edge = 0, have_entry_edge = 0; 763234949Sbapt edge e; 764234949Sbapt edge_iterator ei; 765234949Sbapt 766234949Sbapt /* Functions returning multiple times are not handled by extra edges. 767234949Sbapt Instead we simply allow negative counts on edges from exit to the 768234949Sbapt block past call and corresponding probabilities. We can't go 769234949Sbapt with the extra edges because that would result in flowgraph that 770234949Sbapt needs to have fake edges outside the spanning tree. */ 771234949Sbapt 772234949Sbapt FOR_EACH_EDGE (e, ei, bb->succs) 773234949Sbapt { 774234949Sbapt block_stmt_iterator bsi; 775234949Sbapt tree last = NULL; 776234949Sbapt 777234949Sbapt /* It may happen that there are compiler generated statements 778234949Sbapt without a locus at all. Go through the basic block from the 779234949Sbapt last to the first statement looking for a locus. */ 780234949Sbapt for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 781234949Sbapt { 782234949Sbapt last = bsi_stmt (bsi); 783234949Sbapt if (EXPR_LOCUS (last)) 784234949Sbapt break; 785234949Sbapt } 786234949Sbapt 787234949Sbapt /* Edge with goto locus might get wrong coverage info unless 788234949Sbapt it is the only edge out of BB. 789234949Sbapt Don't do that when the locuses match, so 790234949Sbapt if (blah) goto something; 791234949Sbapt is not computed twice. */ 792234949Sbapt if (last && EXPR_LOCUS (last) 793234949Sbapt && e->goto_locus 794234949Sbapt && !single_succ_p (bb) 795234949Sbapt#ifdef USE_MAPPED_LOCATION 796234949Sbapt && (LOCATION_FILE (e->goto_locus) 797234949Sbapt != LOCATION_FILE (EXPR_LOCATION (last)) 798234949Sbapt || (LOCATION_LINE (e->goto_locus) 799234949Sbapt != LOCATION_LINE (EXPR_LOCATION (last))))) 800234949Sbapt#else 801234949Sbapt && (e->goto_locus->file != EXPR_LOCUS (last)->file 802234949Sbapt || (e->goto_locus->line != EXPR_LOCUS (last)->line))) 803234949Sbapt#endif 804234949Sbapt { 805234949Sbapt basic_block new = split_edge (e); 806234949Sbapt single_succ_edge (new)->goto_locus = e->goto_locus; 807234949Sbapt } 808234949Sbapt if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 809234949Sbapt && e->dest != EXIT_BLOCK_PTR) 810234949Sbapt need_exit_edge = 1; 811234949Sbapt if (e->dest == EXIT_BLOCK_PTR) 812234949Sbapt have_exit_edge = 1; 813234949Sbapt } 814234949Sbapt FOR_EACH_EDGE (e, ei, bb->preds) 815234949Sbapt { 816234949Sbapt if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 817234949Sbapt && e->src != ENTRY_BLOCK_PTR) 818234949Sbapt need_entry_edge = 1; 819234949Sbapt if (e->src == ENTRY_BLOCK_PTR) 820234949Sbapt have_entry_edge = 1; 821234949Sbapt } 822234949Sbapt 823234949Sbapt if (need_exit_edge && !have_exit_edge) 824234949Sbapt { 825234949Sbapt if (dump_file) 826234949Sbapt fprintf (dump_file, "Adding fake exit edge to bb %i\n", 827234949Sbapt bb->index); 828234949Sbapt make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 829234949Sbapt } 830234949Sbapt if (need_entry_edge && !have_entry_edge) 831234949Sbapt { 832234949Sbapt if (dump_file) 833234949Sbapt fprintf (dump_file, "Adding fake entry edge to bb %i\n", 834234949Sbapt bb->index); 835234949Sbapt make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE); 836234949Sbapt } 837234949Sbapt } 838234949Sbapt 839234949Sbapt el = create_edge_list (); 840234949Sbapt num_edges = NUM_EDGES (el); 841234949Sbapt alloc_aux_for_edges (sizeof (struct edge_info)); 842234949Sbapt 843234949Sbapt /* The basic blocks are expected to be numbered sequentially. */ 844234949Sbapt compact_blocks (); 845234949Sbapt 846234949Sbapt ignored_edges = 0; 847234949Sbapt for (i = 0 ; i < num_edges ; i++) 848234949Sbapt { 849234949Sbapt edge e = INDEX_EDGE (el, i); 850234949Sbapt e->count = 0; 851234949Sbapt 852234949Sbapt /* Mark edges we've replaced by fake edges above as ignored. */ 853234949Sbapt if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 854234949Sbapt && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR) 855234949Sbapt { 856234949Sbapt EDGE_INFO (e)->ignore = 1; 857234949Sbapt ignored_edges++; 858234949Sbapt } 859234949Sbapt } 860234949Sbapt 861234949Sbapt /* Create spanning tree from basic block graph, mark each edge that is 862234949Sbapt on the spanning tree. We insert as many abnormal and critical edges 863234949Sbapt as possible to minimize number of edge splits necessary. */ 864234949Sbapt 865234949Sbapt find_spanning_tree (el); 866234949Sbapt 867234949Sbapt /* Fake edges that are not on the tree will not be instrumented, so 868234949Sbapt mark them ignored. */ 869234949Sbapt for (num_instrumented = i = 0; i < num_edges; i++) 870234949Sbapt { 871234949Sbapt edge e = INDEX_EDGE (el, i); 872234949Sbapt struct edge_info *inf = EDGE_INFO (e); 873234949Sbapt 874234949Sbapt if (inf->ignore || inf->on_tree) 875234949Sbapt /*NOP*/; 876234949Sbapt else if (e->flags & EDGE_FAKE) 877234949Sbapt { 878234949Sbapt inf->ignore = 1; 879234949Sbapt ignored_edges++; 880234949Sbapt } 881234949Sbapt else 882234949Sbapt num_instrumented++; 883234949Sbapt } 884234949Sbapt 885234949Sbapt total_num_blocks += n_basic_blocks; 886234949Sbapt if (dump_file) 887234949Sbapt fprintf (dump_file, "%d basic blocks\n", n_basic_blocks); 888234949Sbapt 889234949Sbapt total_num_edges += num_edges; 890234949Sbapt if (dump_file) 891234949Sbapt fprintf (dump_file, "%d edges\n", num_edges); 892234949Sbapt 893234949Sbapt total_num_edges_ignored += ignored_edges; 894234949Sbapt if (dump_file) 895234949Sbapt fprintf (dump_file, "%d ignored edges\n", ignored_edges); 896234949Sbapt 897234949Sbapt /* Write the data from which gcov can reconstruct the basic block 898234949Sbapt graph. */ 899234949Sbapt 900234949Sbapt /* Basic block flags */ 901234949Sbapt if (coverage_begin_output ()) 902234949Sbapt { 903234949Sbapt gcov_position_t offset; 904234949Sbapt 905234949Sbapt offset = gcov_write_tag (GCOV_TAG_BLOCKS); 906234949Sbapt for (i = 0; i != (unsigned) (n_basic_blocks); i++) 907234949Sbapt gcov_write_unsigned (0); 908234949Sbapt gcov_write_length (offset); 909234949Sbapt } 910234949Sbapt 911234949Sbapt /* Keep all basic block indexes nonnegative in the gcov output. 912234949Sbapt Index 0 is used for entry block, last index is for exit block. 913234949Sbapt */ 914234949Sbapt ENTRY_BLOCK_PTR->index = 1; 915234949Sbapt 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