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