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