190075Sobrien/* Calculate branch probabilities, and basic block execution counts. 290075Sobrien Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999, 3169689Skan 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 450397Sobrien Contributed by James E. Wilson, UC Berkeley/Cygnus Support; 550397Sobrien based on some ideas from Dain Samples of UC Berkeley. 650397Sobrien Further mangling by Bob Manson, Cygnus Support. 750397Sobrien 890075SobrienThis file is part of GCC. 950397Sobrien 1090075SobrienGCC is free software; you can redistribute it and/or modify it under 1190075Sobrienthe terms of the GNU General Public License as published by the Free 1290075SobrienSoftware Foundation; either version 2, or (at your option) any later 1390075Sobrienversion. 1450397Sobrien 1590075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1690075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1790075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1890075Sobrienfor more details. 1950397Sobrien 2050397SobrienYou should have received a copy of the GNU General Public License 2190075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 22169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 23169689Skan02110-1301, USA. */ 2450397Sobrien 25117395Skan/* Generate basic block profile instrumentation and auxiliary files. 26117395Skan Profile generation is optimized, so that not all arcs in the basic 27117395Skan block graph need instrumenting. First, the BB graph is closed with 28117395Skan one entry (function start), and one exit (function exit). Any 29117395Skan ABNORMAL_EDGE cannot be instrumented (because there is no control 30117395Skan path to place the code). We close the graph by inserting fake 31117395Skan EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal 32117395Skan edges that do not go to the exit_block. We ignore such abnormal 33117395Skan edges. Naturally these fake edges are never directly traversed, 34117395Skan and so *cannot* be directly instrumented. Some other graph 35117395Skan massaging is done. To optimize the instrumentation we generate the 36117395Skan BB minimal span tree, only edges that are not on the span tree 37117395Skan (plus the entry point) need instrumenting. From that information 38117395Skan all other edge counts can be deduced. By construction all fake 39117395Skan edges must be on the spanning tree. We also attempt to place 40117395Skan EDGE_CRITICAL edges on the spanning tree. 41117395Skan 42169689Skan The auxiliary files generated are <dumpbase>.gcno (at compile time) 43169689Skan and <dumpbase>.gcda (at run time). The format is 44132718Skan described in full in gcov-io.h. */ 45117395Skan 4650397Sobrien/* ??? Register allocation should use basic block execution counts to 4750397Sobrien give preference to the most commonly executed blocks. */ 4850397Sobrien 4950397Sobrien/* ??? Should calculate branch probabilities before instrumenting code, since 5050397Sobrien then we can use arc counts to help decide which arcs to instrument. */ 5150397Sobrien 5250397Sobrien#include "config.h" 5350397Sobrien#include "system.h" 54132718Skan#include "coretypes.h" 55132718Skan#include "tm.h" 5650397Sobrien#include "rtl.h" 5750397Sobrien#include "flags.h" 5850397Sobrien#include "output.h" 5950397Sobrien#include "regs.h" 6090075Sobrien#include "expr.h" 6190075Sobrien#include "function.h" 6290075Sobrien#include "toplev.h" 63132718Skan#include "coverage.h" 64132718Skan#include "value-prof.h" 65132718Skan#include "tree.h" 66169689Skan#include "cfghooks.h" 67169689Skan#include "tree-flow.h" 68169689Skan#include "timevar.h" 69169689Skan#include "cfgloop.h" 70169689Skan#include "tree-pass.h" 7150397Sobrien 72169689Skan/* Hooks for profiling. */ 73169689Skanstatic struct profile_hooks* profile_hooks; 74169689Skan 7590075Sobrien/* Additional information about the edges we need. */ 76117395Skanstruct edge_info { 77117395Skan unsigned int count_valid : 1; 78132718Skan 79117395Skan /* Is on the spanning tree. */ 80117395Skan unsigned int on_tree : 1; 81132718Skan 82117395Skan /* Pretend this edge does not exist (it is abnormal and we've 83117395Skan inserted a fake to compensate). */ 84117395Skan unsigned int ignore : 1; 85117395Skan}; 8650397Sobrien 87117395Skanstruct bb_info { 88117395Skan unsigned int count_valid : 1; 89117395Skan 90117395Skan /* Number of successor and predecessor edges. */ 91117395Skan gcov_type succ_count; 92117395Skan gcov_type pred_count; 93117395Skan}; 94117395Skan 9590075Sobrien#define EDGE_INFO(e) ((struct edge_info *) (e)->aux) 9690075Sobrien#define BB_INFO(b) ((struct bb_info *) (b)->aux) 9750397Sobrien 98132718Skan/* Counter summary from the last set of coverage counts read. */ 9950397Sobrien 100132718Skanconst struct gcov_ctr_summary *profile_info; 101117395Skan 10250397Sobrien/* Collect statistics on the performance of this pass for the entire source 10350397Sobrien file. */ 10450397Sobrien 10550397Sobrienstatic int total_num_blocks; 10690075Sobrienstatic int total_num_edges; 10790075Sobrienstatic int total_num_edges_ignored; 10890075Sobrienstatic int total_num_edges_instrumented; 10950397Sobrienstatic int total_num_blocks_created; 11050397Sobrienstatic int total_num_passes; 11150397Sobrienstatic int total_num_times_called; 11250397Sobrienstatic int total_hist_br_prob[20]; 11350397Sobrienstatic int total_num_never_executed; 11450397Sobrienstatic int total_num_branches; 11550397Sobrien 11650397Sobrien/* Forward declarations. */ 117132718Skanstatic void find_spanning_tree (struct edge_list *); 118132718Skanstatic unsigned instrument_edges (struct edge_list *); 119169689Skanstatic void instrument_values (histogram_values); 120132718Skanstatic void compute_branch_probabilities (void); 121169689Skanstatic void compute_value_histograms (histogram_values); 122132718Skanstatic gcov_type * get_exec_counts (void); 123132718Skanstatic basic_block find_group (basic_block); 124132718Skanstatic void union_groups (basic_block, basic_block); 12550397Sobrien 12650397Sobrien 12790075Sobrien/* Add edge instrumentation code to the entire insn chain. 12850397Sobrien 12950397Sobrien F is the first insn of the chain. 13090075Sobrien NUM_BLOCKS is the number of basic blocks found in F. */ 13150397Sobrien 132132718Skanstatic unsigned 133132718Skaninstrument_edges (struct edge_list *el) 13450397Sobrien{ 135132718Skan unsigned num_instr_edges = 0; 13690075Sobrien int num_edges = NUM_EDGES (el); 137117395Skan basic_block bb; 138132718Skan 139117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 14090075Sobrien { 141132718Skan edge e; 142169689Skan edge_iterator ei; 143132718Skan 144169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 14550397Sobrien { 14690075Sobrien struct edge_info *inf = EDGE_INFO (e); 147132718Skan 14890075Sobrien if (!inf->ignore && !inf->on_tree) 14950397Sobrien { 150169689Skan gcc_assert (!(e->flags & EDGE_ABNORMAL)); 151169689Skan if (dump_file) 152169689Skan fprintf (dump_file, "Edge %d to %d instrumented%s\n", 15390075Sobrien e->src->index, e->dest->index, 15490075Sobrien EDGE_CRITICAL_P (e) ? " (and split)" : ""); 155169689Skan (profile_hooks->gen_edge_profiler) (num_instr_edges++, e); 15650397Sobrien } 15790075Sobrien } 15890075Sobrien } 15950397Sobrien 16090075Sobrien total_num_blocks_created += num_edges; 161169689Skan if (dump_file) 162169689Skan fprintf (dump_file, "%d edges instrumented\n", num_instr_edges); 163132718Skan return num_instr_edges; 16450397Sobrien} 16550397Sobrien 166169689Skan/* Add code to measure histograms for values in list VALUES. */ 16750397Sobrienstatic void 168169689Skaninstrument_values (histogram_values values) 16950397Sobrien{ 170132718Skan unsigned i, t; 17190075Sobrien 172132718Skan /* Emit code to generate the histograms before the insns. */ 17350397Sobrien 174169689Skan for (i = 0; i < VEC_length (histogram_value, values); i++) 17550397Sobrien { 176169689Skan histogram_value hist = VEC_index (histogram_value, values, i); 177169689Skan switch (hist->type) 178117395Skan { 179132718Skan case HIST_TYPE_INTERVAL: 180132718Skan t = GCOV_COUNTER_V_INTERVAL; 181117395Skan break; 182117395Skan 183132718Skan case HIST_TYPE_POW2: 184132718Skan t = GCOV_COUNTER_V_POW2; 185117395Skan break; 186117395Skan 187132718Skan case HIST_TYPE_SINGLE_VALUE: 188132718Skan t = GCOV_COUNTER_V_SINGLE; 189117395Skan break; 190117395Skan 191132718Skan case HIST_TYPE_CONST_DELTA: 192132718Skan t = GCOV_COUNTER_V_DELTA; 193132718Skan break; 194117395Skan 195132718Skan default: 196169689Skan gcc_unreachable (); 197132718Skan } 198169689Skan if (!coverage_counter_alloc (t, hist->n_counters)) 199132718Skan continue; 200117395Skan 201169689Skan switch (hist->type) 202117395Skan { 203132718Skan case HIST_TYPE_INTERVAL: 204169689Skan (profile_hooks->gen_interval_profiler) (hist, t, 0); 205132718Skan break; 206117395Skan 207132718Skan case HIST_TYPE_POW2: 208169689Skan (profile_hooks->gen_pow2_profiler) (hist, t, 0); 209132718Skan break; 210117395Skan 211132718Skan case HIST_TYPE_SINGLE_VALUE: 212169689Skan (profile_hooks->gen_one_value_profiler) (hist, t, 0); 213132718Skan break; 214117395Skan 215132718Skan case HIST_TYPE_CONST_DELTA: 216169689Skan (profile_hooks->gen_const_delta_profiler) (hist, t, 0); 217132718Skan break; 218117395Skan 219132718Skan default: 220169689Skan gcc_unreachable (); 221117395Skan } 222117395Skan } 223132718Skan} 224132718Skan 225117395Skan 226132718Skan/* Computes hybrid profile for all matching entries in da_file. */ 227117395Skan 228132718Skanstatic gcov_type * 229132718Skanget_exec_counts (void) 230132718Skan{ 231132718Skan unsigned num_edges = 0; 232132718Skan basic_block bb; 233132718Skan gcov_type *counts; 234132718Skan 235132718Skan /* Count the edges to be (possibly) instrumented. */ 236132718Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 237117395Skan { 238132718Skan edge e; 239169689Skan edge_iterator ei; 240169689Skan 241169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 242132718Skan if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) 243132718Skan num_edges++; 244117395Skan } 245117395Skan 246132718Skan counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, &profile_info); 247132718Skan if (!counts) 248132718Skan return NULL; 249132718Skan 250169689Skan if (dump_file && profile_info) 251169689Skan fprintf(dump_file, "Merged %u profiles with maximal count %u.\n", 252132718Skan profile_info->runs, (unsigned) profile_info->sum_max); 253132718Skan 254132718Skan return counts; 255117395Skan} 256117395Skan 257117395Skan 25890075Sobrien/* Compute the branch probabilities for the various branches. 25990075Sobrien Annotate them accordingly. */ 26050397Sobrien 26190075Sobrienstatic void 262132718Skancompute_branch_probabilities (void) 26350397Sobrien{ 264117395Skan basic_block bb; 26590075Sobrien int i; 26690075Sobrien int num_edges = 0; 26790075Sobrien int changes; 26890075Sobrien int passes; 26990075Sobrien int hist_br_prob[20]; 27090075Sobrien int num_never_executed; 27190075Sobrien int num_branches; 272117395Skan gcov_type *exec_counts = get_exec_counts (); 273117395Skan int exec_counts_pos = 0; 27450397Sobrien 275132718Skan /* Very simple sanity checks so we catch bugs in our profiling code. */ 276132718Skan if (profile_info) 277132718Skan { 278132718Skan if (profile_info->run_max * profile_info->runs < profile_info->sum_max) 279132718Skan { 280132718Skan error ("corrupted profile info: run_max * runs < sum_max"); 281132718Skan exec_counts = NULL; 282132718Skan } 283132718Skan 284132718Skan if (profile_info->sum_all < profile_info->sum_max) 285132718Skan { 286132718Skan error ("corrupted profile info: sum_all is smaller than sum_max"); 287132718Skan exec_counts = NULL; 288132718Skan } 289132718Skan } 290132718Skan 29190075Sobrien /* Attach extra info block to each bb. */ 29250397Sobrien 29390075Sobrien alloc_aux_for_blocks (sizeof (struct bb_info)); 294117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 29590075Sobrien { 29690075Sobrien edge e; 297169689Skan edge_iterator ei; 29850397Sobrien 299169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 30090075Sobrien if (!EDGE_INFO (e)->ignore) 30190075Sobrien BB_INFO (bb)->succ_count++; 302169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 30390075Sobrien if (!EDGE_INFO (e)->ignore) 30490075Sobrien BB_INFO (bb)->pred_count++; 30590075Sobrien } 30650397Sobrien 30790075Sobrien /* Avoid predicting entry on exit nodes. */ 30890075Sobrien BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2; 30990075Sobrien BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2; 31050397Sobrien 31190075Sobrien /* For each edge not on the spanning tree, set its execution count from 31290075Sobrien the .da file. */ 31350397Sobrien 31490075Sobrien /* The first count in the .da file is the number of times that the function 31590075Sobrien was entered. This is the exec_count for block zero. */ 31650397Sobrien 317117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 31890075Sobrien { 31990075Sobrien edge e; 320169689Skan edge_iterator ei; 321169689Skan 322169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 32390075Sobrien if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) 32450397Sobrien { 32590075Sobrien num_edges++; 326117395Skan if (exec_counts) 32750397Sobrien { 328117395Skan e->count = exec_counts[exec_counts_pos++]; 329132718Skan if (e->count > profile_info->sum_max) 330132718Skan { 331132718Skan error ("corrupted profile info: edge from %i to %i exceeds maximal count", 332132718Skan bb->index, e->dest->index); 333132718Skan } 33450397Sobrien } 33550397Sobrien else 33690075Sobrien e->count = 0; 337117395Skan 33890075Sobrien EDGE_INFO (e)->count_valid = 1; 33990075Sobrien BB_INFO (bb)->succ_count--; 34090075Sobrien BB_INFO (e->dest)->pred_count--; 341169689Skan if (dump_file) 34250397Sobrien { 343169689Skan fprintf (dump_file, "\nRead edge from %i to %i, count:", 34490075Sobrien bb->index, e->dest->index); 345169689Skan fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, 34690075Sobrien (HOST_WIDEST_INT) e->count); 34750397Sobrien } 34850397Sobrien } 34950397Sobrien } 35050397Sobrien 351169689Skan if (dump_file) 352169689Skan fprintf (dump_file, "\n%d edge counts read\n", num_edges); 35350397Sobrien 35450397Sobrien /* For every block in the file, 35590075Sobrien - if every exit/entrance edge has a known count, then set the block count 35690075Sobrien - if the block count is known, and every exit/entrance edge but one has 35790075Sobrien a known execution count, then set the count of the remaining edge 35850397Sobrien 35990075Sobrien As edge counts are set, decrement the succ/pred count, but don't delete 36090075Sobrien the edge, that way we can easily tell when all edges are known, or only 36190075Sobrien one edge is unknown. */ 36250397Sobrien 36350397Sobrien /* The order that the basic blocks are iterated through is important. 36450397Sobrien Since the code that finds spanning trees starts with block 0, low numbered 36590075Sobrien edges are put on the spanning tree in preference to high numbered edges. 36690075Sobrien Hence, most instrumented edges are at the end. Graph solving works much 36750397Sobrien faster if we propagate numbers from the end to the start. 36890075Sobrien 36950397Sobrien This takes an average of slightly more than 3 passes. */ 37050397Sobrien 37150397Sobrien changes = 1; 37250397Sobrien passes = 0; 37350397Sobrien while (changes) 37450397Sobrien { 37550397Sobrien passes++; 37650397Sobrien changes = 0; 377117395Skan FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb) 37850397Sobrien { 37990075Sobrien struct bb_info *bi = BB_INFO (bb); 38090075Sobrien if (! bi->count_valid) 38150397Sobrien { 38290075Sobrien if (bi->succ_count == 0) 38350397Sobrien { 38490075Sobrien edge e; 385169689Skan edge_iterator ei; 38690075Sobrien gcov_type total = 0; 38790075Sobrien 388169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 38990075Sobrien total += e->count; 39090075Sobrien bb->count = total; 39190075Sobrien bi->count_valid = 1; 39250397Sobrien changes = 1; 39350397Sobrien } 39490075Sobrien else if (bi->pred_count == 0) 39550397Sobrien { 39690075Sobrien edge e; 397169689Skan edge_iterator ei; 39890075Sobrien gcov_type total = 0; 39990075Sobrien 400169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 40190075Sobrien total += e->count; 40290075Sobrien bb->count = total; 40390075Sobrien bi->count_valid = 1; 40450397Sobrien changes = 1; 40550397Sobrien } 40650397Sobrien } 40790075Sobrien if (bi->count_valid) 40850397Sobrien { 40990075Sobrien if (bi->succ_count == 1) 41050397Sobrien { 41190075Sobrien edge e; 412169689Skan edge_iterator ei; 41390075Sobrien gcov_type total = 0; 41490075Sobrien 41550397Sobrien /* One of the counts will be invalid, but it is zero, 41650397Sobrien so adding it in also doesn't hurt. */ 417169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 41890075Sobrien total += e->count; 41990075Sobrien 42090075Sobrien /* Seedgeh for the invalid edge, and set its count. */ 421169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 42290075Sobrien if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) 42350397Sobrien break; 42490075Sobrien 42590075Sobrien /* Calculate count for remaining edge by conservation. */ 42690075Sobrien total = bb->count - total; 42790075Sobrien 428169689Skan gcc_assert (e); 42990075Sobrien EDGE_INFO (e)->count_valid = 1; 43090075Sobrien e->count = total; 43190075Sobrien bi->succ_count--; 43290075Sobrien 43390075Sobrien BB_INFO (e->dest)->pred_count--; 43450397Sobrien changes = 1; 43550397Sobrien } 43690075Sobrien if (bi->pred_count == 1) 43750397Sobrien { 43890075Sobrien edge e; 439169689Skan edge_iterator ei; 44090075Sobrien gcov_type total = 0; 44190075Sobrien 44250397Sobrien /* One of the counts will be invalid, but it is zero, 44350397Sobrien so adding it in also doesn't hurt. */ 444169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 44590075Sobrien total += e->count; 44690075Sobrien 447132718Skan /* Search for the invalid edge, and set its count. */ 448169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 449132718Skan if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore) 45050397Sobrien break; 45190075Sobrien 45290075Sobrien /* Calculate count for remaining edge by conservation. */ 45390075Sobrien total = bb->count - total + e->count; 45490075Sobrien 455169689Skan gcc_assert (e); 45690075Sobrien EDGE_INFO (e)->count_valid = 1; 45790075Sobrien e->count = total; 45890075Sobrien bi->pred_count--; 45990075Sobrien 46090075Sobrien BB_INFO (e->src)->succ_count--; 46150397Sobrien changes = 1; 46250397Sobrien } 46350397Sobrien } 46450397Sobrien } 46550397Sobrien } 466169689Skan if (dump_file) 467169689Skan dump_flow_info (dump_file, dump_flags); 46850397Sobrien 46950397Sobrien total_num_passes += passes; 470169689Skan if (dump_file) 471169689Skan fprintf (dump_file, "Graph solving took %d passes.\n\n", passes); 47250397Sobrien 47350397Sobrien /* If the graph has been correctly solved, every block will have a 47450397Sobrien succ and pred count of zero. */ 475117395Skan FOR_EACH_BB (bb) 47650397Sobrien { 477169689Skan gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count); 47850397Sobrien } 47950397Sobrien 48090075Sobrien /* For every edge, calculate its branch probability and add a reg_note 48150397Sobrien to the branch insn to indicate this. */ 48250397Sobrien 48350397Sobrien for (i = 0; i < 20; i++) 48450397Sobrien hist_br_prob[i] = 0; 48550397Sobrien num_never_executed = 0; 48650397Sobrien num_branches = 0; 48750397Sobrien 488117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 48950397Sobrien { 49090075Sobrien edge e; 491169689Skan edge_iterator ei; 49250397Sobrien 493132718Skan if (bb->count < 0) 49450397Sobrien { 495132718Skan error ("corrupted profile info: number of iterations for basic block %d thought to be %i", 496132718Skan bb->index, (int)bb->count); 497132718Skan bb->count = 0; 498132718Skan } 499169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 500132718Skan { 501132718Skan /* Function may return twice in the cased the called function is 502132718Skan setjmp or calls fork, but we can't represent this by extra 503132718Skan edge from the entry, since extra edge from the exit is 504132718Skan already present. We get negative frequency from the entry 505132718Skan point. */ 506132718Skan if ((e->count < 0 507132718Skan && e->dest == EXIT_BLOCK_PTR) 508132718Skan || (e->count > bb->count 509132718Skan && e->dest != EXIT_BLOCK_PTR)) 51050397Sobrien { 511169689Skan if (block_ends_with_call_p (bb)) 512132718Skan e->count = e->count < 0 ? 0 : bb->count; 51390075Sobrien } 514132718Skan if (e->count < 0 || e->count > bb->count) 515132718Skan { 516132718Skan error ("corrupted profile info: number of executions for edge %d-%d thought to be %i", 517132718Skan e->src->index, e->dest->index, 518132718Skan (int)e->count); 519132718Skan e->count = bb->count / 2; 520132718Skan } 521132718Skan } 522132718Skan if (bb->count) 523132718Skan { 524169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 525132718Skan e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count; 526169689Skan if (bb->index >= NUM_FIXED_BLOCKS 527169689Skan && block_ends_with_condjump_p (bb) 528169689Skan && EDGE_COUNT (bb->succs) >= 2) 52990075Sobrien { 53090075Sobrien int prob; 53190075Sobrien edge e; 53290075Sobrien int index; 53350397Sobrien 53490075Sobrien /* Find the branch edge. It is possible that we do have fake 53590075Sobrien edges here. */ 536169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 537169689Skan if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU))) 538169689Skan break; 53950397Sobrien 54090075Sobrien prob = e->probability; 54190075Sobrien index = prob * 20 / REG_BR_PROB_BASE; 54250397Sobrien 54390075Sobrien if (index == 20) 54490075Sobrien index = 19; 54590075Sobrien hist_br_prob[index]++; 54690075Sobrien 54750397Sobrien num_branches++; 54850397Sobrien } 54950397Sobrien } 550169689Skan /* As a last resort, distribute the probabilities evenly. 551169689Skan Use simple heuristics that if there are normal edges, 552132718Skan give all abnormals frequency of 0, otherwise distribute the 553132718Skan frequency over abnormals (this is the case of noreturn 554132718Skan calls). */ 555169689Skan else if (profile_status == PROFILE_ABSENT) 55650397Sobrien { 557132718Skan int total = 0; 558132718Skan 559169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 56090075Sobrien if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 56190075Sobrien total ++; 56290075Sobrien if (total) 56390075Sobrien { 564169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 56590075Sobrien if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 56690075Sobrien e->probability = REG_BR_PROB_BASE / total; 56790075Sobrien else 56890075Sobrien e->probability = 0; 56990075Sobrien } 57090075Sobrien else 57190075Sobrien { 572169689Skan total += EDGE_COUNT (bb->succs); 573169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 57490075Sobrien e->probability = REG_BR_PROB_BASE / total; 57590075Sobrien } 576169689Skan if (bb->index >= NUM_FIXED_BLOCKS 577169689Skan && block_ends_with_condjump_p (bb) 578169689Skan && EDGE_COUNT (bb->succs) >= 2) 57990075Sobrien num_branches++, num_never_executed; 58050397Sobrien } 58150397Sobrien } 582169689Skan counts_to_freqs (); 58350397Sobrien 584169689Skan if (dump_file) 58550397Sobrien { 586169689Skan fprintf (dump_file, "%d branches\n", num_branches); 587169689Skan fprintf (dump_file, "%d branches never executed\n", 58850397Sobrien num_never_executed); 58950397Sobrien if (num_branches) 59050397Sobrien for (i = 0; i < 10; i++) 591169689Skan fprintf (dump_file, "%d%% branches in range %d-%d%%\n", 59290075Sobrien (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches, 59390075Sobrien 5 * i, 5 * i + 5); 59450397Sobrien 59550397Sobrien total_num_branches += num_branches; 59650397Sobrien total_num_never_executed += num_never_executed; 59750397Sobrien for (i = 0; i < 20; i++) 59850397Sobrien total_hist_br_prob[i] += hist_br_prob[i]; 59990075Sobrien 600169689Skan fputc ('\n', dump_file); 601169689Skan fputc ('\n', dump_file); 60250397Sobrien } 60350397Sobrien 60490075Sobrien free_aux_for_blocks (); 60550397Sobrien} 60650397Sobrien 607169689Skan/* Load value histograms values whose description is stored in VALUES array 608169689Skan from .gcda file. */ 609169689Skan 610132718Skanstatic void 611169689Skancompute_value_histograms (histogram_values values) 612132718Skan{ 613132718Skan unsigned i, j, t, any; 614132718Skan unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS]; 615132718Skan gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS]; 616132718Skan gcov_type *act_count[GCOV_N_VALUE_COUNTERS]; 617132718Skan gcov_type *aact_count; 618132718Skan 619132718Skan for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) 620132718Skan n_histogram_counters[t] = 0; 621117395Skan 622169689Skan for (i = 0; i < VEC_length (histogram_value, values); i++) 623169689Skan { 624169689Skan histogram_value hist = VEC_index (histogram_value, values, i); 625169689Skan n_histogram_counters[(int) hist->type] += hist->n_counters; 626169689Skan } 627117395Skan 628132718Skan any = 0; 629132718Skan for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) 630117395Skan { 631132718Skan if (!n_histogram_counters[t]) 632117395Skan { 633132718Skan histogram_counts[t] = NULL; 634132718Skan continue; 635117395Skan } 636117395Skan 637132718Skan histogram_counts[t] = 638132718Skan get_coverage_counts (COUNTER_FOR_HIST_TYPE (t), 639132718Skan n_histogram_counters[t], NULL); 640132718Skan if (histogram_counts[t]) 641132718Skan any = 1; 642132718Skan act_count[t] = histogram_counts[t]; 643117395Skan } 644132718Skan if (!any) 645132718Skan return; 646117395Skan 647169689Skan for (i = 0; i < VEC_length (histogram_value, values); i++) 648132718Skan { 649169689Skan histogram_value hist = VEC_index (histogram_value, values, i); 650169689Skan tree stmt = hist->hvalue.stmt; 651169689Skan stmt_ann_t ann = get_stmt_ann (stmt); 652132718Skan 653169689Skan t = (int) hist->type; 654169689Skan 655132718Skan aact_count = act_count[t]; 656169689Skan act_count[t] += hist->n_counters; 657169689Skan 658169689Skan hist->hvalue.next = ann->histograms; 659169689Skan ann->histograms = hist; 660169689Skan hist->hvalue.counters = XNEWVEC (gcov_type, hist->n_counters); 661169689Skan for (j = 0; j < hist->n_counters; j++) 662169689Skan hist->hvalue.counters[j] = aact_count[j]; 663132718Skan } 664132718Skan 665132718Skan for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++) 666132718Skan if (histogram_counts[t]) 667132718Skan free (histogram_counts[t]); 668117395Skan} 669117395Skan 670169689Skan/* The entry basic block will be moved around so that it has index=1, 671169689Skan there is nothing at index 0 and the exit is at n_basic_block. */ 672169689Skan#define BB_TO_GCOV_INDEX(bb) ((bb)->index - 1) 673169689Skan/* When passed NULL as file_name, initialize. 674169689Skan When passed something else, output the necessary commands to change 675169689Skan line to LINE and offset to FILE_NAME. */ 676169689Skanstatic void 677169689Skanoutput_location (char const *file_name, int line, 678169689Skan gcov_position_t *offset, basic_block bb) 679169689Skan{ 680169689Skan static char const *prev_file_name; 681169689Skan static int prev_line; 682169689Skan bool name_differs, line_differs; 683169689Skan 684169689Skan if (!file_name) 685169689Skan { 686169689Skan prev_file_name = NULL; 687169689Skan prev_line = -1; 688169689Skan return; 689169689Skan } 690169689Skan 691169689Skan name_differs = !prev_file_name || strcmp (file_name, prev_file_name); 692169689Skan line_differs = prev_line != line; 693169689Skan 694169689Skan if (name_differs || line_differs) 695169689Skan { 696169689Skan if (!*offset) 697169689Skan { 698169689Skan *offset = gcov_write_tag (GCOV_TAG_LINES); 699169689Skan gcov_write_unsigned (BB_TO_GCOV_INDEX (bb)); 700169689Skan name_differs = line_differs=true; 701169689Skan } 702169689Skan 703169689Skan /* If this is a new source file, then output the 704169689Skan file's name to the .bb file. */ 705169689Skan if (name_differs) 706169689Skan { 707169689Skan prev_file_name = file_name; 708169689Skan gcov_write_unsigned (0); 709169689Skan gcov_write_string (prev_file_name); 710169689Skan } 711169689Skan if (line_differs) 712169689Skan { 713169689Skan gcov_write_unsigned (line); 714169689Skan prev_line = line; 715169689Skan } 716169689Skan } 717169689Skan} 718169689Skan 71990075Sobrien/* Instrument and/or analyze program behavior based on program flow graph. 72090075Sobrien In either case, this function builds a flow graph for the function being 72190075Sobrien compiled. The flow graph is stored in BB_GRAPH. 72250397Sobrien 72390075Sobrien When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in 72490075Sobrien the flow graph that are needed to reconstruct the dynamic behavior of the 72590075Sobrien flow graph. 72650397Sobrien 72790075Sobrien When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary 72890075Sobrien information from a data file containing edge count information from previous 72990075Sobrien executions of the function being compiled. In this case, the flow graph is 73090075Sobrien annotated with actual execution counts, which are later propagated into the 73190075Sobrien rtl for optimization purposes. 73250397Sobrien 73390075Sobrien Main entry point of this file. */ 73450397Sobrien 73590075Sobrienvoid 736132718Skanbranch_prob (void) 73750397Sobrien{ 738117395Skan basic_block bb; 739132718Skan unsigned i; 740132718Skan unsigned num_edges, ignored_edges; 741132718Skan unsigned num_instrumented; 74290075Sobrien struct edge_list *el; 743169689Skan histogram_values values = NULL; 74450397Sobrien 74590075Sobrien total_num_times_called++; 74650397Sobrien 74790075Sobrien flow_call_edges_add (NULL); 74890075Sobrien add_noreturn_fake_exit_edges (); 74990075Sobrien 75090075Sobrien /* We can't handle cyclic regions constructed using abnormal edges. 75190075Sobrien To avoid these we replace every source of abnormal edge by a fake 75290075Sobrien edge from entry node and every destination by fake edge to exit. 75390075Sobrien This keeps graph acyclic and our calculation exact for all normal 75490075Sobrien edges except for exit and entrance ones. 75590075Sobrien 75690075Sobrien We also add fake exit edges for each call and asm statement in the 75790075Sobrien basic, since it may not return. */ 75890075Sobrien 759117395Skan FOR_EACH_BB (bb) 76050397Sobrien { 76190075Sobrien int need_exit_edge = 0, need_entry_edge = 0; 76290075Sobrien int have_exit_edge = 0, have_entry_edge = 0; 76390075Sobrien edge e; 764169689Skan edge_iterator ei; 76550397Sobrien 766132718Skan /* Functions returning multiple times are not handled by extra edges. 767132718Skan Instead we simply allow negative counts on edges from exit to the 768132718Skan block past call and corresponding probabilities. We can't go 769132718Skan with the extra edges because that would result in flowgraph that 770132718Skan needs to have fake edges outside the spanning tree. */ 77190075Sobrien 772169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 77390075Sobrien { 774169689Skan block_stmt_iterator bsi; 775169689Skan tree last = NULL; 776169689Skan 777169689Skan /* It may happen that there are compiler generated statements 778169689Skan without a locus at all. Go through the basic block from the 779169689Skan last to the first statement looking for a locus. */ 780169689Skan for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 781169689Skan { 782169689Skan last = bsi_stmt (bsi); 783169689Skan if (EXPR_LOCUS (last)) 784169689Skan break; 785169689Skan } 786169689Skan 787169689Skan /* Edge with goto locus might get wrong coverage info unless 788169689Skan it is the only edge out of BB. 789169689Skan Don't do that when the locuses match, so 790169689Skan if (blah) goto something; 791169689Skan is not computed twice. */ 792169689Skan if (last && EXPR_LOCUS (last) 793169689Skan && e->goto_locus 794169689Skan && !single_succ_p (bb) 795169689Skan#ifdef USE_MAPPED_LOCATION 796169689Skan && (LOCATION_FILE (e->goto_locus) 797169689Skan != LOCATION_FILE (EXPR_LOCATION (last)) 798169689Skan || (LOCATION_LINE (e->goto_locus) 799169689Skan != LOCATION_LINE (EXPR_LOCATION (last))))) 800169689Skan#else 801169689Skan && (e->goto_locus->file != EXPR_LOCUS (last)->file 802169689Skan || (e->goto_locus->line != EXPR_LOCUS (last)->line))) 803169689Skan#endif 804169689Skan { 805169689Skan basic_block new = split_edge (e); 806169689Skan single_succ_edge (new)->goto_locus = e->goto_locus; 807169689Skan } 80890075Sobrien if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 80990075Sobrien && e->dest != EXIT_BLOCK_PTR) 81090075Sobrien need_exit_edge = 1; 81190075Sobrien if (e->dest == EXIT_BLOCK_PTR) 81290075Sobrien have_exit_edge = 1; 81390075Sobrien } 814169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 81590075Sobrien { 81690075Sobrien if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 81790075Sobrien && e->src != ENTRY_BLOCK_PTR) 81890075Sobrien need_entry_edge = 1; 81990075Sobrien if (e->src == ENTRY_BLOCK_PTR) 82090075Sobrien have_entry_edge = 1; 82190075Sobrien } 82290075Sobrien 82390075Sobrien if (need_exit_edge && !have_exit_edge) 82490075Sobrien { 825169689Skan if (dump_file) 826169689Skan fprintf (dump_file, "Adding fake exit edge to bb %i\n", 82790075Sobrien bb->index); 828117395Skan make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 82990075Sobrien } 83090075Sobrien if (need_entry_edge && !have_entry_edge) 83190075Sobrien { 832169689Skan if (dump_file) 833169689Skan fprintf (dump_file, "Adding fake entry edge to bb %i\n", 83490075Sobrien bb->index); 835117395Skan make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE); 83690075Sobrien } 83750397Sobrien } 83850397Sobrien 83990075Sobrien el = create_edge_list (); 84090075Sobrien num_edges = NUM_EDGES (el); 84190075Sobrien alloc_aux_for_edges (sizeof (struct edge_info)); 84250397Sobrien 843117395Skan /* The basic blocks are expected to be numbered sequentially. */ 844117395Skan compact_blocks (); 845117395Skan 84690075Sobrien ignored_edges = 0; 84790075Sobrien for (i = 0 ; i < num_edges ; i++) 84890075Sobrien { 84990075Sobrien edge e = INDEX_EDGE (el, i); 85090075Sobrien e->count = 0; 85150397Sobrien 85290075Sobrien /* Mark edges we've replaced by fake edges above as ignored. */ 85390075Sobrien if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 85490075Sobrien && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR) 855117395Skan { 85690075Sobrien EDGE_INFO (e)->ignore = 1; 85790075Sobrien ignored_edges++; 858117395Skan } 85990075Sobrien } 86090075Sobrien 86190075Sobrien /* Create spanning tree from basic block graph, mark each edge that is 86290075Sobrien on the spanning tree. We insert as many abnormal and critical edges 86390075Sobrien as possible to minimize number of edge splits necessary. */ 86490075Sobrien 86590075Sobrien find_spanning_tree (el); 86690075Sobrien 86790075Sobrien /* Fake edges that are not on the tree will not be instrumented, so 86890075Sobrien mark them ignored. */ 869132718Skan for (num_instrumented = i = 0; i < num_edges; i++) 87090075Sobrien { 87190075Sobrien edge e = INDEX_EDGE (el, i); 87290075Sobrien struct edge_info *inf = EDGE_INFO (e); 873132718Skan 874132718Skan if (inf->ignore || inf->on_tree) 875132718Skan /*NOP*/; 876132718Skan else if (e->flags & EDGE_FAKE) 877117395Skan { 878117395Skan inf->ignore = 1; 879117395Skan ignored_edges++; 880117395Skan } 881132718Skan else 882132718Skan num_instrumented++; 88390075Sobrien } 88490075Sobrien 885169689Skan total_num_blocks += n_basic_blocks; 886169689Skan if (dump_file) 887169689Skan fprintf (dump_file, "%d basic blocks\n", n_basic_blocks); 88890075Sobrien 88990075Sobrien total_num_edges += num_edges; 890169689Skan if (dump_file) 891169689Skan fprintf (dump_file, "%d edges\n", num_edges); 89290075Sobrien 89390075Sobrien total_num_edges_ignored += ignored_edges; 894169689Skan if (dump_file) 895169689Skan fprintf (dump_file, "%d ignored edges\n", ignored_edges); 89690075Sobrien 897132718Skan /* Write the data from which gcov can reconstruct the basic block 898132718Skan graph. */ 89990075Sobrien 900132718Skan /* Basic block flags */ 901132718Skan if (coverage_begin_output ()) 90290075Sobrien { 903132718Skan gcov_position_t offset; 90490075Sobrien 905132718Skan offset = gcov_write_tag (GCOV_TAG_BLOCKS); 906169689Skan for (i = 0; i != (unsigned) (n_basic_blocks); i++) 907132718Skan gcov_write_unsigned (0); 908132718Skan gcov_write_length (offset); 909132718Skan } 910117395Skan 911132718Skan /* Keep all basic block indexes nonnegative in the gcov output. 912132718Skan Index 0 is used for entry block, last index is for exit block. 913132718Skan */ 914169689Skan ENTRY_BLOCK_PTR->index = 1; 915132718Skan EXIT_BLOCK_PTR->index = last_basic_block; 916117395Skan 917132718Skan /* Arcs */ 918132718Skan if (coverage_begin_output ()) 919132718Skan { 920132718Skan gcov_position_t offset; 92190075Sobrien 922117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 92350397Sobrien { 92490075Sobrien edge e; 925169689Skan edge_iterator ei; 92690075Sobrien 927132718Skan offset = gcov_write_tag (GCOV_TAG_ARCS); 928132718Skan gcov_write_unsigned (BB_TO_GCOV_INDEX (bb)); 92990075Sobrien 930169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 93190075Sobrien { 93290075Sobrien struct edge_info *i = EDGE_INFO (e); 93390075Sobrien if (!i->ignore) 93490075Sobrien { 935132718Skan unsigned flag_bits = 0; 936132718Skan 93790075Sobrien if (i->on_tree) 938132718Skan flag_bits |= GCOV_ARC_ON_TREE; 93990075Sobrien if (e->flags & EDGE_FAKE) 940132718Skan flag_bits |= GCOV_ARC_FAKE; 94190075Sobrien if (e->flags & EDGE_FALLTHRU) 942132718Skan flag_bits |= GCOV_ARC_FALLTHROUGH; 943169689Skan /* On trees we don't have fallthru flags, but we can 944169689Skan recompute them from CFG shape. */ 945169689Skan if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE) 946169689Skan && e->src->next_bb == e->dest) 947169689Skan flag_bits |= GCOV_ARC_FALLTHROUGH; 94890075Sobrien 949132718Skan gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest)); 950132718Skan gcov_write_unsigned (flag_bits); 95190075Sobrien } 95290075Sobrien } 953132718Skan 954132718Skan gcov_write_length (offset); 95550397Sobrien } 956132718Skan } 95790075Sobrien 958132718Skan /* Line numbers. */ 959132718Skan if (coverage_begin_output ()) 960132718Skan { 961132718Skan gcov_position_t offset; 962132718Skan 963169689Skan /* Initialize the output. */ 964169689Skan output_location (NULL, 0, NULL, NULL); 965169689Skan 966132718Skan FOR_EACH_BB (bb) 967132718Skan { 968169689Skan block_stmt_iterator bsi; 969132718Skan 970132718Skan offset = 0; 971132718Skan 972169689Skan if (bb == ENTRY_BLOCK_PTR->next_bb) 973169689Skan { 974169689Skan expanded_location curr_location = 975169689Skan expand_location (DECL_SOURCE_LOCATION (current_function_decl)); 976169689Skan output_location (curr_location.file, curr_location.line, 977169689Skan &offset, bb); 978169689Skan } 979132718Skan 980169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 981132718Skan { 982169689Skan tree stmt = bsi_stmt (bsi); 983169689Skan if (EXPR_HAS_LOCATION (stmt)) 984169689Skan output_location (EXPR_FILENAME (stmt), EXPR_LINENO (stmt), 985169689Skan &offset, bb); 986169689Skan } 987132718Skan 988169689Skan /* Notice GOTO expressions we eliminated while constructing the 989169689Skan CFG. */ 990169689Skan if (single_succ_p (bb) && single_succ_edge (bb)->goto_locus) 991169689Skan { 992169689Skan /* ??? source_locus type is marked deprecated in input.h. */ 993169689Skan source_locus curr_location = single_succ_edge (bb)->goto_locus; 994169689Skan /* ??? The FILE/LINE API is inconsistent for these cases. */ 995169689Skan#ifdef USE_MAPPED_LOCATION 996169689Skan output_location (LOCATION_FILE (curr_location), 997169689Skan LOCATION_LINE (curr_location), &offset, bb); 998169689Skan#else 999169689Skan output_location (curr_location->file, curr_location->line, 1000169689Skan &offset, bb); 1001169689Skan#endif 1002132718Skan } 1003132718Skan 1004132718Skan if (offset) 1005132718Skan { 1006132718Skan /* A file of NULL indicates the end of run. */ 1007132718Skan gcov_write_unsigned (0); 1008132718Skan gcov_write_string (NULL); 1009132718Skan gcov_write_length (offset); 1010132718Skan } 1011132718Skan } 101290075Sobrien } 1013169689Skan 1014132718Skan ENTRY_BLOCK_PTR->index = ENTRY_BLOCK; 1015132718Skan EXIT_BLOCK_PTR->index = EXIT_BLOCK; 1016132718Skan#undef BB_TO_GCOV_INDEX 101790075Sobrien 1018132718Skan if (flag_profile_values) 1019169689Skan find_values_to_profile (&values); 1020132718Skan 102190075Sobrien if (flag_branch_probabilities) 1022132718Skan { 1023132718Skan compute_branch_probabilities (); 1024132718Skan if (flag_profile_values) 1025169689Skan compute_value_histograms (values); 1026132718Skan } 102790075Sobrien 1028169689Skan remove_fake_edges (); 1029169689Skan 1030169689Skan /* For each edge not on the spanning tree, add counting code. */ 1031132718Skan if (profile_arc_flag 1032132718Skan && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented)) 1033132718Skan { 1034169689Skan unsigned n_instrumented; 103590075Sobrien 1036169689Skan profile_hooks->init_edge_profiler (); 1037132718Skan 1038169689Skan n_instrumented = instrument_edges (el); 1039169689Skan 1040169689Skan gcc_assert (n_instrumented == num_instrumented); 1041169689Skan 1042132718Skan if (flag_profile_values) 1043169689Skan instrument_values (values); 1044132718Skan 1045132718Skan /* Commit changes done by instrumentation. */ 1046169689Skan bsi_commit_edge_inserts (); 104790075Sobrien } 104890075Sobrien 1049132718Skan free_aux_for_edges (); 105090075Sobrien 1051169689Skan VEC_free (histogram_value, heap, values); 105290075Sobrien free_edge_list (el); 1053169689Skan if (flag_branch_probabilities) 1054169689Skan profile_status = PROFILE_READ; 1055169689Skan coverage_end_function (); 105650397Sobrien} 105790075Sobrien 105890075Sobrien/* Union find algorithm implementation for the basic blocks using 105990075Sobrien aux fields. */ 106050397Sobrien 106190075Sobrienstatic basic_block 1062132718Skanfind_group (basic_block bb) 106390075Sobrien{ 106490075Sobrien basic_block group = bb, bb1; 106550397Sobrien 106690075Sobrien while ((basic_block) group->aux != group) 106790075Sobrien group = (basic_block) group->aux; 106890075Sobrien 106990075Sobrien /* Compress path. */ 107090075Sobrien while ((basic_block) bb->aux != group) 107190075Sobrien { 107290075Sobrien bb1 = (basic_block) bb->aux; 107390075Sobrien bb->aux = (void *) group; 107490075Sobrien bb = bb1; 107590075Sobrien } 107690075Sobrien return group; 107790075Sobrien} 107890075Sobrien 107950397Sobrienstatic void 1080132718Skanunion_groups (basic_block bb1, basic_block bb2) 108150397Sobrien{ 108290075Sobrien basic_block bb1g = find_group (bb1); 108390075Sobrien basic_block bb2g = find_group (bb2); 108450397Sobrien 108590075Sobrien /* ??? I don't have a place for the rank field. OK. Lets go w/o it, 108690075Sobrien this code is unlikely going to be performance problem anyway. */ 1087169689Skan gcc_assert (bb1g != bb2g); 108890075Sobrien 108990075Sobrien bb1g->aux = bb2g; 109050397Sobrien} 109190075Sobrien 109290075Sobrien/* This function searches all of the edges in the program flow graph, and puts 109390075Sobrien as many bad edges as possible onto the spanning tree. Bad edges include 109490075Sobrien abnormals edges, which can't be instrumented at the moment. Since it is 1095117395Skan possible for fake edges to form a cycle, we will have to develop some 109690075Sobrien better way in the future. Also put critical edges to the tree, since they 109790075Sobrien are more expensive to instrument. */ 109850397Sobrien 109950397Sobrienstatic void 1100132718Skanfind_spanning_tree (struct edge_list *el) 110150397Sobrien{ 110290075Sobrien int i; 110390075Sobrien int num_edges = NUM_EDGES (el); 1104117395Skan basic_block bb; 110550397Sobrien 110690075Sobrien /* We use aux field for standard union-find algorithm. */ 1107117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1108117395Skan bb->aux = bb; 110950397Sobrien 111090075Sobrien /* Add fake edge exit to entry we can't instrument. */ 111190075Sobrien union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR); 111290075Sobrien 1113117395Skan /* First add all abnormal edges to the tree unless they form a cycle. Also 1114117395Skan add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind 1115117395Skan setting return value from function. */ 111690075Sobrien for (i = 0; i < num_edges; i++) 111790075Sobrien { 111890075Sobrien edge e = INDEX_EDGE (el, i); 1119117395Skan if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE)) 1120132718Skan || e->dest == EXIT_BLOCK_PTR) 112190075Sobrien && !EDGE_INFO (e)->ignore 112290075Sobrien && (find_group (e->src) != find_group (e->dest))) 112390075Sobrien { 1124169689Skan if (dump_file) 1125169689Skan fprintf (dump_file, "Abnormal edge %d to %d put to tree\n", 1126117395Skan e->src->index, e->dest->index); 112790075Sobrien EDGE_INFO (e)->on_tree = 1; 112890075Sobrien union_groups (e->src, e->dest); 112990075Sobrien } 113090075Sobrien } 113190075Sobrien 1132117395Skan /* Now insert all critical edges to the tree unless they form a cycle. */ 113390075Sobrien for (i = 0; i < num_edges; i++) 113490075Sobrien { 113590075Sobrien edge e = INDEX_EDGE (el, i); 1136132718Skan if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore 1137132718Skan && find_group (e->src) != find_group (e->dest)) 113890075Sobrien { 1139169689Skan if (dump_file) 1140169689Skan fprintf (dump_file, "Critical edge %d to %d put to tree\n", 1141117395Skan e->src->index, e->dest->index); 114290075Sobrien EDGE_INFO (e)->on_tree = 1; 114390075Sobrien union_groups (e->src, e->dest); 114490075Sobrien } 114590075Sobrien } 114690075Sobrien 114790075Sobrien /* And now the rest. */ 114890075Sobrien for (i = 0; i < num_edges; i++) 114990075Sobrien { 115090075Sobrien edge e = INDEX_EDGE (el, i); 1151132718Skan if (!EDGE_INFO (e)->ignore 1152132718Skan && find_group (e->src) != find_group (e->dest)) 115390075Sobrien { 1154169689Skan if (dump_file) 1155169689Skan fprintf (dump_file, "Normal edge %d to %d put to tree\n", 1156117395Skan e->src->index, e->dest->index); 115790075Sobrien EDGE_INFO (e)->on_tree = 1; 115890075Sobrien union_groups (e->src, e->dest); 115990075Sobrien } 116090075Sobrien } 116190075Sobrien 1162117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1163117395Skan bb->aux = NULL; 116450397Sobrien} 116550397Sobrien 116650397Sobrien/* Perform file-level initialization for branch-prob processing. */ 116750397Sobrien 116850397Sobrienvoid 1169132718Skaninit_branch_prob (void) 117050397Sobrien{ 117150397Sobrien int i; 117250397Sobrien 117350397Sobrien total_num_blocks = 0; 117490075Sobrien total_num_edges = 0; 117590075Sobrien total_num_edges_ignored = 0; 117690075Sobrien total_num_edges_instrumented = 0; 117750397Sobrien total_num_blocks_created = 0; 117850397Sobrien total_num_passes = 0; 117950397Sobrien total_num_times_called = 0; 118050397Sobrien total_num_branches = 0; 118150397Sobrien total_num_never_executed = 0; 118250397Sobrien for (i = 0; i < 20; i++) 118350397Sobrien total_hist_br_prob[i] = 0; 118450397Sobrien} 118550397Sobrien 118650397Sobrien/* Performs file-level cleanup after branch-prob processing 118750397Sobrien is completed. */ 118850397Sobrien 118950397Sobrienvoid 1190132718Skanend_branch_prob (void) 119150397Sobrien{ 1192169689Skan if (dump_file) 119350397Sobrien { 1194169689Skan fprintf (dump_file, "\n"); 1195169689Skan fprintf (dump_file, "Total number of blocks: %d\n", 119690075Sobrien total_num_blocks); 1197169689Skan fprintf (dump_file, "Total number of edges: %d\n", total_num_edges); 1198169689Skan fprintf (dump_file, "Total number of ignored edges: %d\n", 119990075Sobrien total_num_edges_ignored); 1200169689Skan fprintf (dump_file, "Total number of instrumented edges: %d\n", 120190075Sobrien total_num_edges_instrumented); 1202169689Skan fprintf (dump_file, "Total number of blocks created: %d\n", 120350397Sobrien total_num_blocks_created); 1204169689Skan fprintf (dump_file, "Total number of graph solution passes: %d\n", 120550397Sobrien total_num_passes); 120650397Sobrien if (total_num_times_called != 0) 1207169689Skan fprintf (dump_file, "Average number of graph solution passes: %d\n", 120850397Sobrien (total_num_passes + (total_num_times_called >> 1)) 120950397Sobrien / total_num_times_called); 1210169689Skan fprintf (dump_file, "Total number of branches: %d\n", 121190075Sobrien total_num_branches); 1212169689Skan fprintf (dump_file, "Total number of branches never executed: %d\n", 121350397Sobrien total_num_never_executed); 121450397Sobrien if (total_num_branches) 121550397Sobrien { 121650397Sobrien int i; 121750397Sobrien 121850397Sobrien for (i = 0; i < 10; i++) 1219169689Skan fprintf (dump_file, "%d%% branches in range %d-%d%%\n", 122050397Sobrien (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100 122150397Sobrien / total_num_branches, 5*i, 5*i+5); 122250397Sobrien } 122350397Sobrien } 122450397Sobrien} 1225132718Skan 1226169689Skan/* Set up hooks to enable tree-based profiling. */ 122750397Sobrien 1228169689Skanvoid 1229169689Skantree_register_profile_hooks (void) 1230132718Skan{ 1231169689Skan gcc_assert (ir_type ()); 1232169689Skan profile_hooks = &tree_profile_hooks; 1233132718Skan} 1234132718Skan 1235