gcc/profile.c

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