contrib/gcc-4.0/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.  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 .da 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   histogram_value hist;
 655
 656   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 657     n_histogram_counters[t] = 0;
 658
 659   for (i = 0; i < VEC_length (histogram_value, values); i++)
 660     {
 661       hist = VEC_index (histogram_value, values, i);
 662       n_histogram_counters[(int) hist->type] += hist->n_counters;
 663     }
 664
 665   any = 0;
 666   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 667     {
 668       if (!n_histogram_counters[t])
 669         {
 670           histogram_counts[t] = NULL;
 671           continue;
 672         }
 673
 674       histogram_counts[t] =
 675         get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
 676                              n_histogram_counters[t], NULL);
 677       if (histogram_counts[t])
 678         any = 1;
 679       act_count[t] = histogram_counts[t];
 680     }
 681   if (!any)
 682     return;
 683
 684   for (i = 0; i < VEC_length (histogram_value, values); i++)
 685     {
 686       rtx hist_list = NULL_RTX;
 687
 688       hist = VEC_index (histogram_value, values, i);
 689       t = (int) hist->type;
 690
 691       /* FIXME: make this work for trees.  */
 692       if (!ir_type ())
 693         {
 694           aact_count = act_count[t];
 695           act_count[t] += hist->n_counters;
 696           for (j = hist->n_counters; j > 0; j--)
 697             hist_list = alloc_EXPR_LIST (0, GEN_INT (aact_count[j - 1]),
 698                                         hist_list);
 699               hist_list = alloc_EXPR_LIST (0,
 700                             copy_rtx ((rtx) hist->value), hist_list);
 701           hist_list = alloc_EXPR_LIST (0, GEN_INT (hist->type), hist_list);
 702               REG_NOTES ((rtx) hist->insn) =
 703                   alloc_EXPR_LIST (REG_VALUE_PROFILE, hist_list,
 704                                    REG_NOTES ((rtx) hist->insn));
 705         }
 706     }
 707
 708   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 709     if (histogram_counts[t])
 710       free (histogram_counts[t]);
 711 }
 712
 713 #define BB_TO_GCOV_INDEX(bb)  ((bb)->index + 1)
 714 /* When passed NULL as file_name, initialize.
 715    When passed something else, output the necessary commands to change
 716    line to LINE and offset to FILE_NAME.  */
 717 static void
 718 output_location (char const *file_name, int line,
 719                  gcov_position_t *offset, basic_block bb)
 720 {
 721   static char const *prev_file_name;
 722   static int prev_line;
 723   bool name_differs, line_differs;
 724
 725   if (!file_name)
 726     {
 727       prev_file_name = NULL;
 728       prev_line = -1;
 729       return;
 730     }
 731
 732   name_differs = !prev_file_name || strcmp (file_name, prev_file_name);
 733   line_differs = prev_line != line;
 734
 735   if (name_differs || line_differs)
 736     {
 737       if (!*offset)
 738         {
 739           *offset = gcov_write_tag (GCOV_TAG_LINES);
 740           gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
 741           name_differs = line_differs=true;
 742         }
 743
 744       /* If this is a new source file, then output the
 745          file's name to the .bb file.  */
 746       if (name_differs)
 747         {
 748           prev_file_name = file_name;
 749           gcov_write_unsigned (0);
 750           gcov_write_string (prev_file_name);
 751         }
 752       if (line_differs)
 753         {
 754           gcov_write_unsigned (line);
 755           prev_line = line;
 756         }
 757      }
 758 }
 759
 760 /* Instrument and/or analyze program behavior based on program flow graph.
 761    In either case, this function builds a flow graph for the function being
 762    compiled.  The flow graph is stored in BB_GRAPH.
 763
 764    When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
 765    the flow graph that are needed to reconstruct the dynamic behavior of the
 766    flow graph.
 767
 768    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
 769    information from a data file containing edge count information from previous
 770    executions of the function being compiled.  In this case, the flow graph is
 771    annotated with actual execution counts, which are later propagated into the
 772    rtl for optimization purposes.
 773
 774    Main entry point of this file.  */
 775
 776 void
 777 branch_prob (void)
 778 {
 779   basic_block bb;
 780   unsigned i;
 781   unsigned num_edges, ignored_edges;
 782   unsigned num_instrumented;
 783   struct edge_list *el;
 784   histogram_values values = NULL;
 785
 786   total_num_times_called++;
 787
 788   flow_call_edges_add (NULL);
 789   add_noreturn_fake_exit_edges ();
 790
 791   /* We can't handle cyclic regions constructed using abnormal edges.
 792      To avoid these we replace every source of abnormal edge by a fake
 793      edge from entry node and every destination by fake edge to exit.
 794      This keeps graph acyclic and our calculation exact for all normal
 795      edges except for exit and entrance ones.
 796
 797      We also add fake exit edges for each call and asm statement in the
 798      basic, since it may not return.  */
 799
 800   FOR_EACH_BB (bb)
 801     {
 802       int need_exit_edge = 0, need_entry_edge = 0;
 803       int have_exit_edge = 0, have_entry_edge = 0;
 804       edge e;
 805       edge_iterator ei;
 806
 807       /* Functions returning multiple times are not handled by extra edges.
 808          Instead we simply allow negative counts on edges from exit to the
 809          block past call and corresponding probabilities.  We can't go
 810          with the extra edges because that would result in flowgraph that
 811          needs to have fake edges outside the spanning tree.  */
 812
 813       FOR_EACH_EDGE (e, ei, bb->succs)
 814         {
 815           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 816                && e->dest != EXIT_BLOCK_PTR)
 817             need_exit_edge = 1;
 818           if (e->dest == EXIT_BLOCK_PTR)
 819             have_exit_edge = 1;
 820         }
 821       FOR_EACH_EDGE (e, ei, bb->preds)
 822         {
 823           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 824                && e->src != ENTRY_BLOCK_PTR)
 825             need_entry_edge = 1;
 826           if (e->src == ENTRY_BLOCK_PTR)
 827             have_entry_edge = 1;
 828         }
 829
 830       if (need_exit_edge && !have_exit_edge)
 831         {
 832           if (dump_file)
 833             fprintf (dump_file, "Adding fake exit edge to bb %i\n",
 834                      bb->index);
 835           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 836         }
 837       if (need_entry_edge && !have_entry_edge)
 838         {
 839           if (dump_file)
 840             fprintf (dump_file, "Adding fake entry edge to bb %i\n",
 841                      bb->index);
 842           make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
 843         }
 844     }
 845
 846   el = create_edge_list ();
 847   num_edges = NUM_EDGES (el);
 848   alloc_aux_for_edges (sizeof (struct edge_info));
 849
 850   /* The basic blocks are expected to be numbered sequentially.  */
 851   compact_blocks ();
 852
 853   ignored_edges = 0;
 854   for (i = 0 ; i < num_edges ; i++)
 855     {
 856       edge e = INDEX_EDGE (el, i);
 857       e->count = 0;
 858
 859       /* Mark edges we've replaced by fake edges above as ignored.  */
 860       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 861           && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
 862         {
 863           EDGE_INFO (e)->ignore = 1;
 864           ignored_edges++;
 865         }
 866     }
 867
 868   /* Create spanning tree from basic block graph, mark each edge that is
 869      on the spanning tree.  We insert as many abnormal and critical edges
 870      as possible to minimize number of edge splits necessary.  */
 871
 872   find_spanning_tree (el);
 873
 874   /* Fake edges that are not on the tree will not be instrumented, so
 875      mark them ignored.  */
 876   for (num_instrumented = i = 0; i < num_edges; i++)
 877     {
 878       edge e = INDEX_EDGE (el, i);
 879       struct edge_info *inf = EDGE_INFO (e);
 880
 881       if (inf->ignore || inf->on_tree)
 882         /*NOP*/;
 883       else if (e->flags & EDGE_FAKE)
 884         {
 885           inf->ignore = 1;
 886           ignored_edges++;
 887         }
 888       else
 889         num_instrumented++;
 890     }
 891
 892   total_num_blocks += n_basic_blocks + 2;
 893   if (dump_file)
 894     fprintf (dump_file, "%d basic blocks\n", n_basic_blocks);
 895
 896   total_num_edges += num_edges;
 897   if (dump_file)
 898     fprintf (dump_file, "%d edges\n", num_edges);
 899
 900   total_num_edges_ignored += ignored_edges;
 901   if (dump_file)
 902     fprintf (dump_file, "%d ignored edges\n", ignored_edges);
 903
 904   /* Write the data from which gcov can reconstruct the basic block
 905      graph.  */
 906
 907   /* Basic block flags */
 908   if (coverage_begin_output ())
 909     {
 910       gcov_position_t offset;
 911
 912       offset = gcov_write_tag (GCOV_TAG_BLOCKS);
 913       for (i = 0; i != (unsigned) (n_basic_blocks + 2); i++)
 914         gcov_write_unsigned (0);
 915       gcov_write_length (offset);
 916     }
 917
 918    /* Keep all basic block indexes nonnegative in the gcov output.
 919       Index 0 is used for entry block, last index is for exit block.
 920       */
 921   ENTRY_BLOCK_PTR->index = -1;
 922   EXIT_BLOCK_PTR->index = last_basic_block;
 923
 924   /* Arcs */
 925   if (coverage_begin_output ())
 926     {
 927       gcov_position_t offset;
 928
 929       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 930         {
 931           edge e;
 932           edge_iterator ei;
 933
 934           offset = gcov_write_tag (GCOV_TAG_ARCS);
 935           gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
 936
 937           FOR_EACH_EDGE (e, ei, bb->succs)
 938             {
 939               struct edge_info *i = EDGE_INFO (e);
 940               if (!i->ignore)
 941                 {
 942                   unsigned flag_bits = 0;
 943
 944                   if (i->on_tree)
 945                     flag_bits |= GCOV_ARC_ON_TREE;
 946                   if (e->flags & EDGE_FAKE)
 947                     flag_bits |= GCOV_ARC_FAKE;
 948                   if (e->flags & EDGE_FALLTHRU)
 949                     flag_bits |= GCOV_ARC_FALLTHROUGH;
 950                   /* On trees we don't have fallthru flags, but we can
 951                      recompute them from CFG shape.  */
 952                   if (ir_type ()
 953                       && e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
 954                       && e->src->next_bb == e->dest)
 955                     flag_bits |= GCOV_ARC_FALLTHROUGH;
 956
 957                   gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest));
 958                   gcov_write_unsigned (flag_bits);
 959                 }
 960             }
 961
 962           gcov_write_length (offset);
 963         }
 964     }
 965
 966   /* Line numbers.  */
 967   if (coverage_begin_output ())
 968     {
 969       /* Initialize the output.  */
 970       output_location (NULL, 0, NULL, NULL);
 971
 972       if (!ir_type ())
 973         {
 974           gcov_position_t offset;
 975
 976           FOR_EACH_BB (bb)
 977             {
 978               rtx insn = BB_HEAD (bb);
 979               int ignore_next_note = 0;
 980
 981               offset = 0;
 982
 983               /* We are looking for line number notes.  Search backward
 984                  before basic block to find correct ones.  */
 985               insn = prev_nonnote_insn (insn);
 986               if (!insn)
 987                 insn = get_insns ();
 988               else
 989                 insn = NEXT_INSN (insn);
 990
 991               while (insn != BB_END (bb))
 992                 {
 993                   if (NOTE_P (insn))
 994                     {
 995                       /* Must ignore the line number notes that
 996                          immediately follow the end of an inline function
 997                          to avoid counting it twice.  There is a note
 998                          before the call, and one after the call.  */
 999                       if (NOTE_LINE_NUMBER (insn)
1000                           == NOTE_INSN_REPEATED_LINE_NUMBER)
1001                         ignore_next_note = 1;
1002                       else if (NOTE_LINE_NUMBER (insn) <= 0)
1003                         /*NOP*/;
1004                       else if (ignore_next_note)
1005                         ignore_next_note = 0;
1006                       else
1007                         {
1008                           expanded_location s;
1009                           NOTE_EXPANDED_LOCATION (s, insn);
1010                           output_location (s.file, s.line, &offset, bb);
1011                         }
1012                     }
1013                   insn = NEXT_INSN (insn);
1014                 }
1015
1016               if (offset)
1017                 {
1018                   /* A file of NULL indicates the end of run.  */
1019                   gcov_write_unsigned (0);
1020                   gcov_write_string (NULL);
1021                   gcov_write_length (offset);
1022                 }
1023             }
1024         }
1025       else
1026         {
1027           gcov_position_t offset;
1028
1029           FOR_EACH_BB (bb)
1030             {
1031               block_stmt_iterator bsi;
1032
1033               offset = 0;
1034
1035               if (bb == ENTRY_BLOCK_PTR->next_bb)
1036                 {
1037                   expanded_location curr_location =
1038                     expand_location (DECL_SOURCE_LOCATION
1039                                      (current_function_decl));
1040                   output_location (curr_location.file, curr_location.line,
1041                                    &offset, bb);
1042                 }
1043
1044               for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1045                 {
1046                   tree stmt = bsi_stmt (bsi);
1047                   if (EXPR_HAS_LOCATION (stmt))
1048                     output_location (EXPR_FILENAME (stmt),
1049                                      EXPR_LINENO (stmt),
1050                                      &offset, bb);
1051                 }
1052
1053               /* Notice GOTO expressions we eliminated while constructing the
1054                  CFG.  */
1055               if (EDGE_COUNT (bb->succs) == 1 && EDGE_SUCC (bb, 0)->goto_locus)
1056                 {
1057                   /* ??? source_locus type is marked deprecated in input.h.  */
1058                   source_locus curr_location = EDGE_SUCC (bb, 0)->goto_locus;
1059                   /* ??? The FILE/LINE API is inconsistent for these cases.  */
1060 #ifdef USE_MAPPED_LOCATION
1061                   output_location (LOCATION_FILE (curr_location),
1062                                    LOCATION_LINE (curr_location),
1063                                    &offset, bb);
1064 #else
1065                   output_location (curr_location->file, curr_location->line,
1066                                    &offset, bb);
1067 #endif
1068                 }
1069
1070               if (offset)
1071                 {
1072                   /* A file of NULL indicates the end of run.  */
1073                   gcov_write_unsigned (0);
1074                   gcov_write_string (NULL);
1075                   gcov_write_length (offset);
1076                 }
1077             }
1078          }
1079     }
1080
1081   ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
1082   EXIT_BLOCK_PTR->index = EXIT_BLOCK;
1083 #undef BB_TO_GCOV_INDEX
1084
1085   if (flag_profile_values)
1086     find_values_to_profile (&values);
1087
1088   if (flag_branch_probabilities)
1089     {
1090       compute_branch_probabilities ();
1091       if (flag_profile_values)
1092         compute_value_histograms (values);
1093     }
1094
1095   remove_fake_edges ();
1096
1097   /* For each edge not on the spanning tree, add counting code.  */
1098   if (profile_arc_flag
1099       && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1100     {
1101       unsigned n_instrumented;
1102
1103       profile_hooks->init_edge_profiler ();
1104
1105       n_instrumented = instrument_edges (el);
1106
1107       if (n_instrumented != num_instrumented)
1108         abort ();
1109
1110       if (flag_profile_values)
1111         instrument_values (values);
1112
1113       /* Commit changes done by instrumentation.  */
1114       if (ir_type ())
1115         bsi_commit_edge_inserts ();
1116       else
1117         {
1118           commit_edge_insertions_watch_calls ();
1119           allocate_reg_info (max_reg_num (), FALSE, FALSE);
1120         }
1121     }
1122
1123   free_aux_for_edges ();
1124
1125   if (!ir_type ())
1126     {
1127       /* Re-merge split basic blocks and the mess introduced by
1128          insert_insn_on_edge.  */
1129       cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
1130       if (profile_dump_file())
1131         dump_flow_info (profile_dump_file());
1132     }
1133
1134   free_edge_list (el);
1135   if (flag_branch_probabilities)
1136     profile_status = PROFILE_READ;
1137 }
1138 \f
1139 /* Union find algorithm implementation for the basic blocks using
1140    aux fields.  */
1141
1142 static basic_block
1143 find_group (basic_block bb)
1144 {
1145   basic_block group = bb, bb1;
1146
1147   while ((basic_block) group->aux != group)
1148     group = (basic_block) group->aux;
1149
1150   /* Compress path.  */
1151   while ((basic_block) bb->aux != group)
1152     {
1153       bb1 = (basic_block) bb->aux;
1154       bb->aux = (void *) group;
1155       bb = bb1;
1156     }
1157   return group;
1158 }
1159
1160 static void
1161 union_groups (basic_block bb1, basic_block bb2)
1162 {
1163   basic_block bb1g = find_group (bb1);
1164   basic_block bb2g = find_group (bb2);
1165
1166   /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
1167      this code is unlikely going to be performance problem anyway.  */
1168   if (bb1g == bb2g)
1169     abort ();
1170
1171   bb1g->aux = bb2g;
1172 }
1173 \f
1174 /* This function searches all of the edges in the program flow graph, and puts
1175    as many bad edges as possible onto the spanning tree.  Bad edges include
1176    abnormals edges, which can't be instrumented at the moment.  Since it is
1177    possible for fake edges to form a cycle, we will have to develop some
1178    better way in the future.  Also put critical edges to the tree, since they
1179    are more expensive to instrument.  */
1180
1181 static void
1182 find_spanning_tree (struct edge_list *el)
1183 {
1184   int i;
1185   int num_edges = NUM_EDGES (el);
1186   basic_block bb;
1187
1188   /* We use aux field for standard union-find algorithm.  */
1189   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1190     bb->aux = bb;
1191
1192   /* Add fake edge exit to entry we can't instrument.  */
1193   union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1194
1195   /* First add all abnormal edges to the tree unless they form a cycle. Also
1196      add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1197      setting return value from function.  */
1198   for (i = 0; i < num_edges; i++)
1199     {
1200       edge e = INDEX_EDGE (el, i);
1201       if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1202            || e->dest == EXIT_BLOCK_PTR)
1203           && !EDGE_INFO (e)->ignore
1204           && (find_group (e->src) != find_group (e->dest)))
1205         {
1206           if (dump_file)
1207             fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1208                      e->src->index, e->dest->index);
1209           EDGE_INFO (e)->on_tree = 1;
1210           union_groups (e->src, e->dest);
1211         }
1212     }
1213
1214   /* Now insert all critical edges to the tree unless they form a cycle.  */
1215   for (i = 0; i < num_edges; i++)
1216     {
1217       edge e = INDEX_EDGE (el, i);
1218       if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore
1219           && find_group (e->src) != find_group (e->dest))
1220         {
1221           if (dump_file)
1222             fprintf (dump_file, "Critical edge %d to %d put to tree\n",
1223                      e->src->index, e->dest->index);
1224           EDGE_INFO (e)->on_tree = 1;
1225           union_groups (e->src, e->dest);
1226         }
1227     }
1228
1229   /* And now the rest.  */
1230   for (i = 0; i < num_edges; i++)
1231     {
1232       edge e = INDEX_EDGE (el, i);
1233       if (!EDGE_INFO (e)->ignore
1234           && find_group (e->src) != find_group (e->dest))
1235         {
1236           if (dump_file)
1237             fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1238                      e->src->index, e->dest->index);
1239           EDGE_INFO (e)->on_tree = 1;
1240           union_groups (e->src, e->dest);
1241         }
1242     }
1243
1244   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1245     bb->aux = NULL;
1246 }
1247 \f
1248 /* Perform file-level initialization for branch-prob processing.  */
1249
1250 void
1251 init_branch_prob (void)
1252 {
1253   int i;
1254
1255   total_num_blocks = 0;
1256   total_num_edges = 0;
1257   total_num_edges_ignored = 0;
1258   total_num_edges_instrumented = 0;
1259   total_num_blocks_created = 0;
1260   total_num_passes = 0;
1261   total_num_times_called = 0;
1262   total_num_branches = 0;
1263   total_num_never_executed = 0;
1264   for (i = 0; i < 20; i++)
1265     total_hist_br_prob[i] = 0;
1266 }
1267
1268 /* Performs file-level cleanup after branch-prob processing
1269    is completed.  */
1270
1271 void
1272 end_branch_prob (void)
1273 {
1274   if (dump_file)
1275     {
1276       fprintf (dump_file, "\n");
1277       fprintf (dump_file, "Total number of blocks: %d\n",
1278                total_num_blocks);
1279       fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1280       fprintf (dump_file, "Total number of ignored edges: %d\n",
1281                total_num_edges_ignored);
1282       fprintf (dump_file, "Total number of instrumented edges: %d\n",
1283                total_num_edges_instrumented);
1284       fprintf (dump_file, "Total number of blocks created: %d\n",
1285                total_num_blocks_created);
1286       fprintf (dump_file, "Total number of graph solution passes: %d\n",
1287                total_num_passes);
1288       if (total_num_times_called != 0)
1289         fprintf (dump_file, "Average number of graph solution passes: %d\n",
1290                  (total_num_passes + (total_num_times_called  >> 1))
1291                  / total_num_times_called);
1292       fprintf (dump_file, "Total number of branches: %d\n",
1293                total_num_branches);
1294       fprintf (dump_file, "Total number of branches never executed: %d\n",
1295                total_num_never_executed);
1296       if (total_num_branches)
1297         {
1298           int i;
1299
1300           for (i = 0; i < 10; i++)
1301             fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1302                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1303                      / total_num_branches, 5*i, 5*i+5);
1304         }
1305     }
1306 }
1307
1308 /* Set up hooks to enable tree-based profiling.  */
1309
1310 void
1311 tree_register_profile_hooks (void)
1312 {
1313   profile_hooks = &tree_profile_hooks;
1314   if (!ir_type ())
1315     abort ();
1316 }
1317
1318 /* Set up hooks to enable RTL-based profiling.  */
1319
1320 void
1321 rtl_register_profile_hooks (void)
1322 {
1323   profile_hooks = &rtl_profile_hooks;
1324   if (ir_type ())
1325     abort ();
1326 }