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