gcc/profile.c

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