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   compute_function_frequency ();
 752
 753   if (dump_file)
 754     {
 755       fprintf (dump_file, "%d branches\n", num_branches);
 756       if (num_branches)
 757         for (i = 0; i < 10; i++)
 758           fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
 759                    (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
 760                    5 * i, 5 * i + 5);
 761
 762       total_num_branches += num_branches;
 763       for (i = 0; i < 20; i++)
 764         total_hist_br_prob[i] += hist_br_prob[i];
 765
 766       fputc ('\n', dump_file);
 767       fputc ('\n', dump_file);
 768     }
 769
 770   free_aux_for_blocks ();
 771 }
 772
 773 /* Load value histograms values whose description is stored in VALUES array
 774    from .gcda file.
 775
 776    CFG_CHECKSUM is the precomputed checksum for the CFG.  */
 777
 778 static void
 779 compute_value_histograms (histogram_values values, unsigned cfg_checksum,
 780                           unsigned lineno_checksum)
 781 {
 782   unsigned i, j, t, any;
 783   unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
 784   gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
 785   gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
 786   gcov_type *aact_count;
 787
 788   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 789     n_histogram_counters[t] = 0;
 790
 791   for (i = 0; i < VEC_length (histogram_value, values); i++)
 792     {
 793       histogram_value hist = VEC_index (histogram_value, values, i);
 794       n_histogram_counters[(int) hist->type] += hist->n_counters;
 795     }
 796
 797   any = 0;
 798   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 799     {
 800       if (!n_histogram_counters[t])
 801         {
 802           histogram_counts[t] = NULL;
 803           continue;
 804         }
 805
 806       histogram_counts[t] =
 807         get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
 808                              n_histogram_counters[t], cfg_checksum,
 809                              lineno_checksum, NULL);
 810       if (histogram_counts[t])
 811         any = 1;
 812       act_count[t] = histogram_counts[t];
 813     }
 814   if (!any)
 815     return;
 816
 817   for (i = 0; i < VEC_length (histogram_value, values); i++)
 818     {
 819       histogram_value hist = VEC_index (histogram_value, values, i);
 820       gimple stmt = hist->hvalue.stmt;
 821
 822       t = (int) hist->type;
 823
 824       aact_count = act_count[t];
 825       act_count[t] += hist->n_counters;
 826
 827       gimple_add_histogram_value (cfun, stmt, hist);
 828       hist->hvalue.counters =  XNEWVEC (gcov_type, hist->n_counters);
 829       for (j = 0; j < hist->n_counters; j++)
 830         hist->hvalue.counters[j] = aact_count[j];
 831     }
 832
 833   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 834     free (histogram_counts[t]);
 835 }
 836
 837 /* The entry basic block will be moved around so that it has index=1,
 838    there is nothing at index 0 and the exit is at n_basic_block.  */
 839 #define BB_TO_GCOV_INDEX(bb)  ((bb)->index - 1)
 840 /* When passed NULL as file_name, initialize.
 841    When passed something else, output the necessary commands to change
 842    line to LINE and offset to FILE_NAME.  */
 843 static void
 844 output_location (char const *file_name, int line,
 845                  gcov_position_t *offset, basic_block bb)
 846 {
 847   static char const *prev_file_name;
 848   static int prev_line;
 849   bool name_differs, line_differs;
 850
 851   if (!file_name)
 852     {
 853       prev_file_name = NULL;
 854       prev_line = -1;
 855       return;
 856     }
 857
 858   name_differs = !prev_file_name || filename_cmp (file_name, prev_file_name);
 859   line_differs = prev_line != line;
 860
 861   if (name_differs || line_differs)
 862     {
 863       if (!*offset)
 864         {
 865           *offset = gcov_write_tag (GCOV_TAG_LINES);
 866           gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
 867           name_differs = line_differs=true;
 868         }
 869
 870       /* If this is a new source file, then output the
 871          file's name to the .bb file.  */
 872       if (name_differs)
 873         {
 874           prev_file_name = file_name;
 875           gcov_write_unsigned (0);
 876           gcov_write_string (prev_file_name);
 877         }
 878       if (line_differs)
 879         {
 880           gcov_write_unsigned (line);
 881           prev_line = line;
 882         }
 883      }
 884 }
 885
 886 /* Instrument and/or analyze program behavior based on program flow graph.
 887    In either case, this function builds a flow graph for the function being
 888    compiled.  The flow graph is stored in BB_GRAPH.
 889
 890    When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
 891    the flow graph that are needed to reconstruct the dynamic behavior of the
 892    flow graph.
 893
 894    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
 895    information from a data file containing edge count information from previous
 896    executions of the function being compiled.  In this case, the flow graph is
 897    annotated with actual execution counts, which are later propagated into the
 898    rtl for optimization purposes.
 899
 900    Main entry point of this file.  */
 901
 902 void
 903 branch_prob (void)
 904 {
 905   basic_block bb;
 906   unsigned i;
 907   unsigned num_edges, ignored_edges;
 908   unsigned num_instrumented;
 909   struct edge_list *el;
 910   histogram_values values = NULL;
 911   unsigned cfg_checksum, lineno_checksum;
 912
 913   total_num_times_called++;
 914
 915   flow_call_edges_add (NULL);
 916   add_noreturn_fake_exit_edges ();
 917
 918   /* We can't handle cyclic regions constructed using abnormal edges.
 919      To avoid these we replace every source of abnormal edge by a fake
 920      edge from entry node and every destination by fake edge to exit.
 921      This keeps graph acyclic and our calculation exact for all normal
 922      edges except for exit and entrance ones.
 923
 924      We also add fake exit edges for each call and asm statement in the
 925      basic, since it may not return.  */
 926
 927   FOR_EACH_BB (bb)
 928     {
 929       int need_exit_edge = 0, need_entry_edge = 0;
 930       int have_exit_edge = 0, have_entry_edge = 0;
 931       edge e;
 932       edge_iterator ei;
 933
 934       /* Functions returning multiple times are not handled by extra edges.
 935          Instead we simply allow negative counts on edges from exit to the
 936          block past call and corresponding probabilities.  We can't go
 937          with the extra edges because that would result in flowgraph that
 938          needs to have fake edges outside the spanning tree.  */
 939
 940       FOR_EACH_EDGE (e, ei, bb->succs)
 941         {
 942           gimple_stmt_iterator gsi;
 943           gimple last = NULL;
 944
 945           /* It may happen that there are compiler generated statements
 946              without a locus at all.  Go through the basic block from the
 947              last to the first statement looking for a locus.  */
 948           for (gsi = gsi_last_nondebug_bb (bb);
 949                !gsi_end_p (gsi);
 950                gsi_prev_nondebug (&gsi))
 951             {
 952               last = gsi_stmt (gsi);
 953               if (gimple_has_location (last))
 954                 break;
 955             }
 956
 957           /* Edge with goto locus might get wrong coverage info unless
 958              it is the only edge out of BB.
 959              Don't do that when the locuses match, so
 960              if (blah) goto something;
 961              is not computed twice.  */
 962           if (last
 963               && gimple_has_location (last)
 964               && e->goto_locus != UNKNOWN_LOCATION
 965               && !single_succ_p (bb)
 966               && (LOCATION_FILE (e->goto_locus)
 967                   != LOCATION_FILE (gimple_location (last))
 968                   || (LOCATION_LINE (e->goto_locus)
 969                       != LOCATION_LINE (gimple_location (last)))))
 970             {
 971               basic_block new_bb = split_edge (e);
 972               edge ne = single_succ_edge (new_bb);
 973               ne->goto_locus = e->goto_locus;
 974               ne->goto_block = e->goto_block;
 975             }
 976           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 977                && e->dest != EXIT_BLOCK_PTR)
 978             need_exit_edge = 1;
 979           if (e->dest == EXIT_BLOCK_PTR)
 980             have_exit_edge = 1;
 981         }
 982       FOR_EACH_EDGE (e, ei, bb->preds)
 983         {
 984           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 985                && e->src != ENTRY_BLOCK_PTR)
 986             need_entry_edge = 1;
 987           if (e->src == ENTRY_BLOCK_PTR)
 988             have_entry_edge = 1;
 989         }
 990
 991       if (need_exit_edge && !have_exit_edge)
 992         {
 993           if (dump_file)
 994             fprintf (dump_file, "Adding fake exit edge to bb %i\n",
 995                      bb->index);
 996           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 997         }
 998       if (need_entry_edge && !have_entry_edge)
 999         {
1000           if (dump_file)
1001             fprintf (dump_file, "Adding fake entry edge to bb %i\n",
1002                      bb->index);
1003           make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
1004         }
1005     }
1006
1007   el = create_edge_list ();
1008   num_edges = NUM_EDGES (el);
1009   alloc_aux_for_edges (sizeof (struct edge_info));
1010
1011   /* The basic blocks are expected to be numbered sequentially.  */
1012   compact_blocks ();
1013
1014   ignored_edges = 0;
1015   for (i = 0 ; i < num_edges ; i++)
1016     {
1017       edge e = INDEX_EDGE (el, i);
1018       e->count = 0;
1019
1020       /* Mark edges we've replaced by fake edges above as ignored.  */
1021       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1022           && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
1023         {
1024           EDGE_INFO (e)->ignore = 1;
1025           ignored_edges++;
1026         }
1027     }
1028
1029   /* Create spanning tree from basic block graph, mark each edge that is
1030      on the spanning tree.  We insert as many abnormal and critical edges
1031      as possible to minimize number of edge splits necessary.  */
1032
1033   find_spanning_tree (el);
1034
1035   /* Fake edges that are not on the tree will not be instrumented, so
1036      mark them ignored.  */
1037   for (num_instrumented = i = 0; i < num_edges; i++)
1038     {
1039       edge e = INDEX_EDGE (el, i);
1040       struct edge_info *inf = EDGE_INFO (e);
1041
1042       if (inf->ignore || inf->on_tree)
1043         /*NOP*/;
1044       else if (e->flags & EDGE_FAKE)
1045         {
1046           inf->ignore = 1;
1047           ignored_edges++;
1048         }
1049       else
1050         num_instrumented++;
1051     }
1052
1053   total_num_blocks += n_basic_blocks;
1054   if (dump_file)
1055     fprintf (dump_file, "%d basic blocks\n", n_basic_blocks);
1056
1057   total_num_edges += num_edges;
1058   if (dump_file)
1059     fprintf (dump_file, "%d edges\n", num_edges);
1060
1061   total_num_edges_ignored += ignored_edges;
1062   if (dump_file)
1063     fprintf (dump_file, "%d ignored edges\n", ignored_edges);
1064
1065
1066   /* Compute two different checksums. Note that we want to compute
1067      the checksum in only once place, since it depends on the shape
1068      of the control flow which can change during
1069      various transformations.  */
1070   cfg_checksum = coverage_compute_cfg_checksum ();
1071   lineno_checksum = coverage_compute_lineno_checksum ();
1072
1073   /* Write the data from which gcov can reconstruct the basic block
1074      graph.  */
1075
1076   /* Basic block flags */
1077   if (coverage_begin_output (lineno_checksum, cfg_checksum))
1078     {
1079       gcov_position_t offset;
1080
1081       offset = gcov_write_tag (GCOV_TAG_BLOCKS);
1082       for (i = 0; i != (unsigned) (n_basic_blocks); i++)
1083         gcov_write_unsigned (0);
1084       gcov_write_length (offset);
1085     }
1086
1087    /* Keep all basic block indexes nonnegative in the gcov output.
1088       Index 0 is used for entry block, last index is for exit block.
1089       */
1090   ENTRY_BLOCK_PTR->index = 1;
1091   EXIT_BLOCK_PTR->index = last_basic_block;
1092
1093   /* Arcs */
1094   if (coverage_begin_output (lineno_checksum, cfg_checksum))
1095     {
1096       gcov_position_t offset;
1097
1098       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1099         {
1100           edge e;
1101           edge_iterator ei;
1102
1103           offset = gcov_write_tag (GCOV_TAG_ARCS);
1104           gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
1105
1106           FOR_EACH_EDGE (e, ei, bb->succs)
1107             {
1108               struct edge_info *i = EDGE_INFO (e);
1109               if (!i->ignore)
1110                 {
1111                   unsigned flag_bits = 0;
1112
1113                   if (i->on_tree)
1114                     flag_bits |= GCOV_ARC_ON_TREE;
1115                   if (e->flags & EDGE_FAKE)
1116                     flag_bits |= GCOV_ARC_FAKE;
1117                   if (e->flags & EDGE_FALLTHRU)
1118                     flag_bits |= GCOV_ARC_FALLTHROUGH;
1119                   /* On trees we don't have fallthru flags, but we can
1120                      recompute them from CFG shape.  */
1121                   if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
1122                       && e->src->next_bb == e->dest)
1123                     flag_bits |= GCOV_ARC_FALLTHROUGH;
1124
1125                   gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest));
1126                   gcov_write_unsigned (flag_bits);
1127                 }
1128             }
1129
1130           gcov_write_length (offset);
1131         }
1132     }
1133
1134   /* Line numbers.  */
1135   if (coverage_begin_output (lineno_checksum, cfg_checksum))
1136     {
1137       /* Initialize the output.  */
1138       output_location (NULL, 0, NULL, NULL);
1139
1140       FOR_EACH_BB (bb)
1141         {
1142           gimple_stmt_iterator gsi;
1143           gcov_position_t offset = 0;
1144
1145           if (bb == ENTRY_BLOCK_PTR->next_bb)
1146             {
1147               expanded_location curr_location =
1148                 expand_location (DECL_SOURCE_LOCATION (current_function_decl));
1149               output_location (curr_location.file, curr_location.line,
1150                                &offset, bb);
1151             }
1152
1153           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1154             {
1155               gimple stmt = gsi_stmt (gsi);
1156               if (gimple_has_location (stmt))
1157                 output_location (gimple_filename (stmt), gimple_lineno (stmt),
1158                                  &offset, bb);
1159             }
1160
1161           /* Notice GOTO expressions eliminated while constructing the CFG.  */
1162           if (single_succ_p (bb)
1163               && single_succ_edge (bb)->goto_locus != UNKNOWN_LOCATION)
1164             {
1165               expanded_location curr_location
1166                 = expand_location (single_succ_edge (bb)->goto_locus);
1167               output_location (curr_location.file, curr_location.line,
1168                                &offset, bb);
1169             }
1170
1171           if (offset)
1172             {
1173               /* A file of NULL indicates the end of run.  */
1174               gcov_write_unsigned (0);
1175               gcov_write_string (NULL);
1176               gcov_write_length (offset);
1177             }
1178         }
1179     }
1180
1181   ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
1182   EXIT_BLOCK_PTR->index = EXIT_BLOCK;
1183 #undef BB_TO_GCOV_INDEX
1184
1185   if (flag_profile_values)
1186     gimple_find_values_to_profile (&values);
1187
1188   if (flag_branch_probabilities)
1189     {
1190       compute_branch_probabilities (cfg_checksum, lineno_checksum);
1191       if (flag_profile_values)
1192         compute_value_histograms (values, cfg_checksum, lineno_checksum);
1193     }
1194
1195   remove_fake_edges ();
1196
1197   /* For each edge not on the spanning tree, add counting code.  */
1198   if (profile_arc_flag
1199       && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1200     {
1201       unsigned n_instrumented;
1202
1203       gimple_init_edge_profiler ();
1204
1205       n_instrumented = instrument_edges (el);
1206
1207       gcc_assert (n_instrumented == num_instrumented);
1208
1209       if (flag_profile_values)
1210         instrument_values (values);
1211
1212       /* Commit changes done by instrumentation.  */
1213       gsi_commit_edge_inserts ();
1214     }
1215
1216   free_aux_for_edges ();
1217
1218   VEC_free (histogram_value, heap, values);
1219   free_edge_list (el);
1220   coverage_end_function (lineno_checksum, cfg_checksum);
1221 }
1222 \f
1223 /* Union find algorithm implementation for the basic blocks using
1224    aux fields.  */
1225
1226 static basic_block
1227 find_group (basic_block bb)
1228 {
1229   basic_block group = bb, bb1;
1230
1231   while ((basic_block) group->aux != group)
1232     group = (basic_block) group->aux;
1233
1234   /* Compress path.  */
1235   while ((basic_block) bb->aux != group)
1236     {
1237       bb1 = (basic_block) bb->aux;
1238       bb->aux = (void *) group;
1239       bb = bb1;
1240     }
1241   return group;
1242 }
1243
1244 static void
1245 union_groups (basic_block bb1, basic_block bb2)
1246 {
1247   basic_block bb1g = find_group (bb1);
1248   basic_block bb2g = find_group (bb2);
1249
1250   /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
1251      this code is unlikely going to be performance problem anyway.  */
1252   gcc_assert (bb1g != bb2g);
1253
1254   bb1g->aux = bb2g;
1255 }
1256 \f
1257 /* This function searches all of the edges in the program flow graph, and puts
1258    as many bad edges as possible onto the spanning tree.  Bad edges include
1259    abnormals edges, which can't be instrumented at the moment.  Since it is
1260    possible for fake edges to form a cycle, we will have to develop some
1261    better way in the future.  Also put critical edges to the tree, since they
1262    are more expensive to instrument.  */
1263
1264 static void
1265 find_spanning_tree (struct edge_list *el)
1266 {
1267   int i;
1268   int num_edges = NUM_EDGES (el);
1269   basic_block bb;
1270
1271   /* We use aux field for standard union-find algorithm.  */
1272   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1273     bb->aux = bb;
1274
1275   /* Add fake edge exit to entry we can't instrument.  */
1276   union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1277
1278   /* First add all abnormal edges to the tree unless they form a cycle. Also
1279      add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1280      setting return value from function.  */
1281   for (i = 0; i < num_edges; i++)
1282     {
1283       edge e = INDEX_EDGE (el, i);
1284       if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1285            || e->dest == EXIT_BLOCK_PTR)
1286           && !EDGE_INFO (e)->ignore
1287           && (find_group (e->src) != find_group (e->dest)))
1288         {
1289           if (dump_file)
1290             fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1291                      e->src->index, e->dest->index);
1292           EDGE_INFO (e)->on_tree = 1;
1293           union_groups (e->src, e->dest);
1294         }
1295     }
1296
1297   /* Now insert all critical edges to the tree unless they form a cycle.  */
1298   for (i = 0; i < num_edges; i++)
1299     {
1300       edge e = INDEX_EDGE (el, i);
1301       if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore
1302           && find_group (e->src) != find_group (e->dest))
1303         {
1304           if (dump_file)
1305             fprintf (dump_file, "Critical edge %d to %d put to tree\n",
1306                      e->src->index, e->dest->index);
1307           EDGE_INFO (e)->on_tree = 1;
1308           union_groups (e->src, e->dest);
1309         }
1310     }
1311
1312   /* And now the rest.  */
1313   for (i = 0; i < num_edges; i++)
1314     {
1315       edge e = INDEX_EDGE (el, i);
1316       if (!EDGE_INFO (e)->ignore
1317           && find_group (e->src) != find_group (e->dest))
1318         {
1319           if (dump_file)
1320             fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1321                      e->src->index, e->dest->index);
1322           EDGE_INFO (e)->on_tree = 1;
1323           union_groups (e->src, e->dest);
1324         }
1325     }
1326
1327   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1328     bb->aux = NULL;
1329 }
1330 \f
1331 /* Perform file-level initialization for branch-prob processing.  */
1332
1333 void
1334 init_branch_prob (void)
1335 {
1336   int i;
1337
1338   total_num_blocks = 0;
1339   total_num_edges = 0;
1340   total_num_edges_ignored = 0;
1341   total_num_edges_instrumented = 0;
1342   total_num_blocks_created = 0;
1343   total_num_passes = 0;
1344   total_num_times_called = 0;
1345   total_num_branches = 0;
1346   for (i = 0; i < 20; i++)
1347     total_hist_br_prob[i] = 0;
1348 }
1349
1350 /* Performs file-level cleanup after branch-prob processing
1351    is completed.  */
1352
1353 void
1354 end_branch_prob (void)
1355 {
1356   if (dump_file)
1357     {
1358       fprintf (dump_file, "\n");
1359       fprintf (dump_file, "Total number of blocks: %d\n",
1360                total_num_blocks);
1361       fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1362       fprintf (dump_file, "Total number of ignored edges: %d\n",
1363                total_num_edges_ignored);
1364       fprintf (dump_file, "Total number of instrumented edges: %d\n",
1365                total_num_edges_instrumented);
1366       fprintf (dump_file, "Total number of blocks created: %d\n",
1367                total_num_blocks_created);
1368       fprintf (dump_file, "Total number of graph solution passes: %d\n",
1369                total_num_passes);
1370       if (total_num_times_called != 0)
1371         fprintf (dump_file, "Average number of graph solution passes: %d\n",
1372                  (total_num_passes + (total_num_times_called  >> 1))
1373                  / total_num_times_called);
1374       fprintf (dump_file, "Total number of branches: %d\n",
1375                total_num_branches);
1376       if (total_num_branches)
1377         {
1378           int i;
1379
1380           for (i = 0; i < 10; i++)
1381             fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1382                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1383                      / total_num_branches, 5*i, 5*i+5);
1384         }
1385     }
1386 }