gcc/profile.c

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