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 (unsigned, struct histogram_value *);
 123 static void compute_branch_probabilities (void);
 124 static void compute_value_histograms (unsigned, struct histogram_value *);
 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   remove_fake_edges ();
 143
 144   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 145     {
 146       edge e;
 147
 148       for (e = bb->succ; e; e = e->succ_next)
 149         {
 150           struct edge_info *inf = EDGE_INFO (e);
 151
 152           if (!inf->ignore && !inf->on_tree)
 153             {
 154               if (e->flags & EDGE_ABNORMAL)
 155                 abort ();
 156               if (dump_file)
 157                 fprintf (dump_file, "Edge %d to %d instrumented%s\n",
 158                          e->src->index, e->dest->index,
 159                          EDGE_CRITICAL_P (e) ? " (and split)" : "");
 160               (profile_hooks->gen_edge_profiler) (num_instr_edges++, e);
 161             }
 162         }
 163     }
 164
 165   total_num_blocks_created += num_edges;
 166   if (dump_file)
 167     fprintf (dump_file, "%d edges instrumented\n", num_instr_edges);
 168   return num_instr_edges;
 169 }
 170
 171 /* Add code to measure histograms list of VALUES of length N_VALUES.  */
 172 static void
 173 instrument_values (unsigned n_values, struct histogram_value *values)
 174 {
 175   unsigned i, t;
 176
 177   /* Emit code to generate the histograms before the insns.  */
 178
 179   for (i = 0; i < n_values; i++)
 180     {
 181       switch (values[i].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, values[i].n_counters))
 203         continue;
 204
 205       switch (values[i].type)
 206         {
 207         case HIST_TYPE_INTERVAL:
 208           (profile_hooks->gen_interval_profiler) (values + i, t, 0);
 209           break;
 210
 211         case HIST_TYPE_POW2:
 212           (profile_hooks->gen_pow2_profiler) (values + i, t, 0);
 213           break;
 214
 215         case HIST_TYPE_SINGLE_VALUE:
 216           (profile_hooks->gen_one_value_profiler) (values + i, t, 0);
 217           break;
 218
 219         case HIST_TYPE_CONST_DELTA:
 220           (profile_hooks->gen_const_delta_profiler) (values + i, 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       for (e = bb->succ; e; e = e->succ_next)
 244         if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
 245           num_edges++;
 246     }
 247
 248   counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, &profile_info);
 249   if (!counts)
 250     return NULL;
 251
 252   if (dump_file && profile_info)
 253     fprintf(dump_file, "Merged %u profiles with maximal count %u.\n",
 254             profile_info->runs, (unsigned) profile_info->sum_max);
 255
 256   return counts;
 257 }
 258 \f
 259
 260 /* Compute the branch probabilities for the various branches.
 261    Annotate them accordingly.  */
 262
 263 static void
 264 compute_branch_probabilities (void)
 265 {
 266   basic_block bb;
 267   int i;
 268   int num_edges = 0;
 269   int changes;
 270   int passes;
 271   int hist_br_prob[20];
 272   int num_never_executed;
 273   int num_branches;
 274   gcov_type *exec_counts = get_exec_counts ();
 275   int exec_counts_pos = 0;
 276
 277   /* Very simple sanity checks so we catch bugs in our profiling code.  */
 278   if (profile_info)
 279     {
 280       if (profile_info->run_max * profile_info->runs < profile_info->sum_max)
 281         {
 282           error ("corrupted profile info: run_max * runs < sum_max");
 283           exec_counts = NULL;
 284         }
 285
 286       if (profile_info->sum_all < profile_info->sum_max)
 287         {
 288           error ("corrupted profile info: sum_all is smaller than sum_max");
 289           exec_counts = NULL;
 290         }
 291     }
 292
 293   /* Attach extra info block to each bb.  */
 294
 295   alloc_aux_for_blocks (sizeof (struct bb_info));
 296   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 297     {
 298       edge e;
 299
 300       for (e = bb->succ; e; e = e->succ_next)
 301         if (!EDGE_INFO (e)->ignore)
 302           BB_INFO (bb)->succ_count++;
 303       for (e = bb->pred; e; e = e->pred_next)
 304         if (!EDGE_INFO (e)->ignore)
 305           BB_INFO (bb)->pred_count++;
 306     }
 307
 308   /* Avoid predicting entry on exit nodes.  */
 309   BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
 310   BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
 311
 312   /* For each edge not on the spanning tree, set its execution count from
 313      the .da file.  */
 314
 315   /* The first count in the .da file is the number of times that the function
 316      was entered.  This is the exec_count for block zero.  */
 317
 318   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 319     {
 320       edge e;
 321       for (e = bb->succ; e; e = e->succ_next)
 322         if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
 323           {
 324             num_edges++;
 325             if (exec_counts)
 326               {
 327                 e->count = exec_counts[exec_counts_pos++];
 328                 if (e->count > profile_info->sum_max)
 329                   {
 330                     error ("corrupted profile info: edge from %i to %i exceeds maximal count",
 331                            bb->index, e->dest->index);
 332                   }
 333               }
 334             else
 335               e->count = 0;
 336
 337             EDGE_INFO (e)->count_valid = 1;
 338             BB_INFO (bb)->succ_count--;
 339             BB_INFO (e->dest)->pred_count--;
 340             if (dump_file)
 341               {
 342                 fprintf (dump_file, "\nRead edge from %i to %i, count:",
 343                          bb->index, e->dest->index);
 344                 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
 345                          (HOST_WIDEST_INT) e->count);
 346               }
 347           }
 348     }
 349
 350   if (dump_file)
 351     fprintf (dump_file, "\n%d edge counts read\n", num_edges);
 352
 353   /* For every block in the file,
 354      - if every exit/entrance edge has a known count, then set the block count
 355      - if the block count is known, and every exit/entrance edge but one has
 356      a known execution count, then set the count of the remaining edge
 357
 358      As edge counts are set, decrement the succ/pred count, but don't delete
 359      the edge, that way we can easily tell when all edges are known, or only
 360      one edge is unknown.  */
 361
 362   /* The order that the basic blocks are iterated through is important.
 363      Since the code that finds spanning trees starts with block 0, low numbered
 364      edges are put on the spanning tree in preference to high numbered edges.
 365      Hence, most instrumented edges are at the end.  Graph solving works much
 366      faster if we propagate numbers from the end to the start.
 367
 368      This takes an average of slightly more than 3 passes.  */
 369
 370   changes = 1;
 371   passes = 0;
 372   while (changes)
 373     {
 374       passes++;
 375       changes = 0;
 376       FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
 377         {
 378           struct bb_info *bi = BB_INFO (bb);
 379           if (! bi->count_valid)
 380             {
 381               if (bi->succ_count == 0)
 382                 {
 383                   edge e;
 384                   gcov_type total = 0;
 385
 386                   for (e = bb->succ; e; e = e->succ_next)
 387                     total += e->count;
 388                   bb->count = total;
 389                   bi->count_valid = 1;
 390                   changes = 1;
 391                 }
 392               else if (bi->pred_count == 0)
 393                 {
 394                   edge e;
 395                   gcov_type total = 0;
 396
 397                   for (e = bb->pred; e; e = e->pred_next)
 398                     total += e->count;
 399                   bb->count = total;
 400                   bi->count_valid = 1;
 401                   changes = 1;
 402                 }
 403             }
 404           if (bi->count_valid)
 405             {
 406               if (bi->succ_count == 1)
 407                 {
 408                   edge e;
 409                   gcov_type total = 0;
 410
 411                   /* One of the counts will be invalid, but it is zero,
 412                      so adding it in also doesn't hurt.  */
 413                   for (e = bb->succ; e; e = e->succ_next)
 414                     total += e->count;
 415
 416                   /* Seedgeh for the invalid edge, and set its count.  */
 417                   for (e = bb->succ; e; e = e->succ_next)
 418                     if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
 419                       break;
 420
 421                   /* Calculate count for remaining edge by conservation.  */
 422                   total = bb->count - total;
 423
 424                   if (! e)
 425                     abort ();
 426                   EDGE_INFO (e)->count_valid = 1;
 427                   e->count = total;
 428                   bi->succ_count--;
 429
 430                   BB_INFO (e->dest)->pred_count--;
 431                   changes = 1;
 432                 }
 433               if (bi->pred_count == 1)
 434                 {
 435                   edge e;
 436                   gcov_type total = 0;
 437
 438                   /* One of the counts will be invalid, but it is zero,
 439                      so adding it in also doesn't hurt.  */
 440                   for (e = bb->pred; e; e = e->pred_next)
 441                     total += e->count;
 442
 443                   /* Search for the invalid edge, and set its count.  */
 444                   for (e = bb->pred; e; e = e->pred_next)
 445                     if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore)
 446                       break;
 447
 448                   /* Calculate count for remaining edge by conservation.  */
 449                   total = bb->count - total + e->count;
 450
 451                   if (! e)
 452                     abort ();
 453                   EDGE_INFO (e)->count_valid = 1;
 454                   e->count = total;
 455                   bi->pred_count--;
 456
 457                   BB_INFO (e->src)->succ_count--;
 458                   changes = 1;
 459                 }
 460             }
 461         }
 462     }
 463   if (dump_file)
 464     dump_flow_info (dump_file);
 465
 466   total_num_passes += passes;
 467   if (dump_file)
 468     fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
 469
 470   /* If the graph has been correctly solved, every block will have a
 471      succ and pred count of zero.  */
 472   FOR_EACH_BB (bb)
 473     {
 474       if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count)
 475         abort ();
 476     }
 477
 478   /* For every edge, calculate its branch probability and add a reg_note
 479      to the branch insn to indicate this.  */
 480
 481   for (i = 0; i < 20; i++)
 482     hist_br_prob[i] = 0;
 483   num_never_executed = 0;
 484   num_branches = 0;
 485
 486   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 487     {
 488       edge e;
 489       rtx note;
 490
 491       if (bb->count < 0)
 492         {
 493           error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
 494                  bb->index, (int)bb->count);
 495           bb->count = 0;
 496         }
 497       for (e = bb->succ; e; e = e->succ_next)
 498         {
 499           /* Function may return twice in the cased the called function is
 500              setjmp or calls fork, but we can't represent this by extra
 501              edge from the entry, since extra edge from the exit is
 502              already present.  We get negative frequency from the entry
 503              point.  */
 504           if ((e->count < 0
 505                && e->dest == EXIT_BLOCK_PTR)
 506               || (e->count > bb->count
 507                   && e->dest != EXIT_BLOCK_PTR))
 508             {
 509               if (block_ends_with_call_p (bb))
 510                 e->count = e->count < 0 ? 0 : bb->count;
 511             }
 512           if (e->count < 0 || e->count > bb->count)
 513             {
 514               error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
 515                      e->src->index, e->dest->index,
 516                      (int)e->count);
 517               e->count = bb->count / 2;
 518             }
 519         }
 520       if (bb->count)
 521         {
 522           for (e = bb->succ; e; e = e->succ_next)
 523             e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count;
 524           if (bb->index >= 0
 525               && block_ends_with_condjump_p (bb)
 526               && bb->succ->succ_next)
 527             {
 528               int prob;
 529               edge e;
 530               int index;
 531
 532               /* Find the branch edge.  It is possible that we do have fake
 533                  edges here.  */
 534               for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU);
 535                    e = e->succ_next)
 536                 continue; /* Loop body has been intentionally left blank.  */
 537
 538               prob = e->probability;
 539               index = prob * 20 / REG_BR_PROB_BASE;
 540
 541               if (index == 20)
 542                 index = 19;
 543               hist_br_prob[index]++;
 544
 545               /* Do this for RTL only.  */
 546               if (!ir_type ())
 547                 {
 548                   note = find_reg_note (BB_END (bb), REG_BR_PROB, 0);
 549                   /* There may be already note put by some other pass, such
 550                      as builtin_expect expander.  */
 551                   if (note)
 552                     XEXP (note, 0) = GEN_INT (prob);
 553                   else
 554                     REG_NOTES (BB_END (bb))
 555                       = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 556                                            REG_NOTES (BB_END (bb)));
 557                 }
 558               num_branches++;
 559             }
 560         }
 561       /* Otherwise distribute the probabilities evenly so we get sane
 562          sum.  Use simple heuristics that if there are normal edges,
 563          give all abnormals frequency of 0, otherwise distribute the
 564          frequency over abnormals (this is the case of noreturn
 565          calls).  */
 566       else
 567         {
 568           int total = 0;
 569
 570           for (e = bb->succ; e; e = e->succ_next)
 571             if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
 572               total ++;
 573           if (total)
 574             {
 575               for (e = bb->succ; e; e = e->succ_next)
 576                 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
 577                   e->probability = REG_BR_PROB_BASE / total;
 578                 else
 579                   e->probability = 0;
 580             }
 581           else
 582             {
 583               for (e = bb->succ; e; e = e->succ_next)
 584                 total ++;
 585               for (e = bb->succ; e; e = e->succ_next)
 586                 e->probability = REG_BR_PROB_BASE / total;
 587             }
 588           if (bb->index >= 0
 589               && block_ends_with_condjump_p (bb)
 590               && bb->succ->succ_next)
 591             num_branches++, num_never_executed;
 592         }
 593     }
 594
 595   if (dump_file)
 596     {
 597       fprintf (dump_file, "%d branches\n", num_branches);
 598       fprintf (dump_file, "%d branches never executed\n",
 599                num_never_executed);
 600       if (num_branches)
 601         for (i = 0; i < 10; i++)
 602           fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
 603                    (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
 604                    5 * i, 5 * i + 5);
 605
 606       total_num_branches += num_branches;
 607       total_num_never_executed += num_never_executed;
 608       for (i = 0; i < 20; i++)
 609         total_hist_br_prob[i] += hist_br_prob[i];
 610
 611       fputc ('\n', dump_file);
 612       fputc ('\n', dump_file);
 613     }
 614
 615   free_aux_for_blocks ();
 616 }
 617
 618 /* Load value histograms for N_VALUES values whose description is stored
 619    in VALUES array from .da file.  */
 620 static void
 621 compute_value_histograms (unsigned n_values, struct histogram_value *values)
 622 {
 623   unsigned i, j, t, any;
 624   unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
 625   gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
 626   gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
 627   gcov_type *aact_count;
 628
 629   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 630     n_histogram_counters[t] = 0;
 631
 632   for (i = 0; i < n_values; i++)
 633     n_histogram_counters[(int) (values[i].type)] += values[i].n_counters;
 634
 635   any = 0;
 636   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 637     {
 638       if (!n_histogram_counters[t])
 639         {
 640           histogram_counts[t] = NULL;
 641           continue;
 642         }
 643
 644       histogram_counts[t] =
 645         get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
 646                              n_histogram_counters[t], NULL);
 647       if (histogram_counts[t])
 648         any = 1;
 649       act_count[t] = histogram_counts[t];
 650     }
 651   if (!any)
 652     return;
 653
 654   for (i = 0; i < n_values; i++)
 655     {
 656       rtx hist_list = NULL_RTX;
 657       t = (int) (values[i].type);
 658
 659       /* FIXME: make this work for trees.  */
 660       if (!ir_type ())
 661         {
 662           aact_count = act_count[t];
 663           act_count[t] += values[i].n_counters;
 664           for (j = values[i].n_counters; j > 0; j--)
 665             hist_list = alloc_EXPR_LIST (0, GEN_INT (aact_count[j - 1]),
 666                                         hist_list);
 667               hist_list = alloc_EXPR_LIST (0,
 668                             copy_rtx ((rtx)values[i].value), hist_list);
 669           hist_list = alloc_EXPR_LIST (0, GEN_INT (values[i].type), hist_list);
 670               REG_NOTES ((rtx)values[i].insn) =
 671                   alloc_EXPR_LIST (REG_VALUE_PROFILE, hist_list,
 672                                        REG_NOTES ((rtx)values[i].insn));
 673         }
 674     }
 675
 676   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 677     if (histogram_counts[t])
 678       free (histogram_counts[t]);
 679 }
 680
 681 /* Instrument and/or analyze program behavior based on program flow graph.
 682    In either case, this function builds a flow graph for the function being
 683    compiled.  The flow graph is stored in BB_GRAPH.
 684
 685    When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
 686    the flow graph that are needed to reconstruct the dynamic behavior of the
 687    flow graph.
 688
 689    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
 690    information from a data file containing edge count information from previous
 691    executions of the function being compiled.  In this case, the flow graph is
 692    annotated with actual execution counts, which are later propagated into the
 693    rtl for optimization purposes.
 694
 695    Main entry point of this file.  */
 696
 697 void
 698 branch_prob (void)
 699 {
 700   basic_block bb;
 701   unsigned i;
 702   unsigned num_edges, ignored_edges;
 703   unsigned num_instrumented;
 704   struct edge_list *el;
 705   unsigned n_values = 0;
 706   struct histogram_value *values = NULL;
 707
 708   total_num_times_called++;
 709
 710   flow_call_edges_add (NULL);
 711   add_noreturn_fake_exit_edges ();
 712
 713   /* We can't handle cyclic regions constructed using abnormal edges.
 714      To avoid these we replace every source of abnormal edge by a fake
 715      edge from entry node and every destination by fake edge to exit.
 716      This keeps graph acyclic and our calculation exact for all normal
 717      edges except for exit and entrance ones.
 718
 719      We also add fake exit edges for each call and asm statement in the
 720      basic, since it may not return.  */
 721
 722   FOR_EACH_BB (bb)
 723     {
 724       int need_exit_edge = 0, need_entry_edge = 0;
 725       int have_exit_edge = 0, have_entry_edge = 0;
 726       edge e;
 727
 728       /* Functions returning multiple times are not handled by extra edges.
 729          Instead we simply allow negative counts on edges from exit to the
 730          block past call and corresponding probabilities.  We can't go
 731          with the extra edges because that would result in flowgraph that
 732          needs to have fake edges outside the spanning tree.  */
 733
 734       for (e = bb->succ; e; e = e->succ_next)
 735         {
 736           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 737                && e->dest != EXIT_BLOCK_PTR)
 738             need_exit_edge = 1;
 739           if (e->dest == EXIT_BLOCK_PTR)
 740             have_exit_edge = 1;
 741         }
 742       for (e = bb->pred; e; e = e->pred_next)
 743         {
 744           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 745                && e->src != ENTRY_BLOCK_PTR)
 746             need_entry_edge = 1;
 747           if (e->src == ENTRY_BLOCK_PTR)
 748             have_entry_edge = 1;
 749         }
 750
 751       if (need_exit_edge && !have_exit_edge)
 752         {
 753           if (dump_file)
 754             fprintf (dump_file, "Adding fake exit edge to bb %i\n",
 755                      bb->index);
 756           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 757         }
 758       if (need_entry_edge && !have_entry_edge)
 759         {
 760           if (dump_file)
 761             fprintf (dump_file, "Adding fake entry edge to bb %i\n",
 762                      bb->index);
 763           make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
 764         }
 765     }
 766
 767   el = create_edge_list ();
 768   num_edges = NUM_EDGES (el);
 769   alloc_aux_for_edges (sizeof (struct edge_info));
 770
 771   /* The basic blocks are expected to be numbered sequentially.  */
 772   compact_blocks ();
 773
 774   ignored_edges = 0;
 775   for (i = 0 ; i < num_edges ; i++)
 776     {
 777       edge e = INDEX_EDGE (el, i);
 778       e->count = 0;
 779
 780       /* Mark edges we've replaced by fake edges above as ignored.  */
 781       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 782           && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
 783         {
 784           EDGE_INFO (e)->ignore = 1;
 785           ignored_edges++;
 786         }
 787     }
 788
 789 #ifdef ENABLE_CHECKING
 790   verify_flow_info ();
 791 #endif
 792
 793   /* Create spanning tree from basic block graph, mark each edge that is
 794      on the spanning tree.  We insert as many abnormal and critical edges
 795      as possible to minimize number of edge splits necessary.  */
 796
 797   find_spanning_tree (el);
 798
 799   /* Fake edges that are not on the tree will not be instrumented, so
 800      mark them ignored.  */
 801   for (num_instrumented = i = 0; i < num_edges; i++)
 802     {
 803       edge e = INDEX_EDGE (el, i);
 804       struct edge_info *inf = EDGE_INFO (e);
 805
 806       if (inf->ignore || inf->on_tree)
 807         /*NOP*/;
 808       else if (e->flags & EDGE_FAKE)
 809         {
 810           inf->ignore = 1;
 811           ignored_edges++;
 812         }
 813       else
 814         num_instrumented++;
 815     }
 816
 817   total_num_blocks += n_basic_blocks + 2;
 818   if (dump_file)
 819     fprintf (dump_file, "%d basic blocks\n", n_basic_blocks);
 820
 821   total_num_edges += num_edges;
 822   if (dump_file)
 823     fprintf (dump_file, "%d edges\n", num_edges);
 824
 825   total_num_edges_ignored += ignored_edges;
 826   if (dump_file)
 827     fprintf (dump_file, "%d ignored edges\n", ignored_edges);
 828
 829   /* Write the data from which gcov can reconstruct the basic block
 830      graph.  */
 831
 832   /* Basic block flags */
 833   if (coverage_begin_output ())
 834     {
 835       gcov_position_t offset;
 836
 837       offset = gcov_write_tag (GCOV_TAG_BLOCKS);
 838       for (i = 0; i != (unsigned) (n_basic_blocks + 2); i++)
 839         gcov_write_unsigned (0);
 840       gcov_write_length (offset);
 841     }
 842
 843    /* Keep all basic block indexes nonnegative in the gcov output.
 844       Index 0 is used for entry block, last index is for exit block.
 845       */
 846   ENTRY_BLOCK_PTR->index = -1;
 847   EXIT_BLOCK_PTR->index = last_basic_block;
 848 #define BB_TO_GCOV_INDEX(bb)  ((bb)->index + 1)
 849
 850   /* Arcs */
 851   if (coverage_begin_output ())
 852     {
 853       gcov_position_t offset;
 854
 855       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 856         {
 857           edge e;
 858
 859           offset = gcov_write_tag (GCOV_TAG_ARCS);
 860           gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
 861
 862           for (e = bb->succ; e; e = e->succ_next)
 863             {
 864               struct edge_info *i = EDGE_INFO (e);
 865               if (!i->ignore)
 866                 {
 867                   unsigned flag_bits = 0;
 868
 869                   if (i->on_tree)
 870                     flag_bits |= GCOV_ARC_ON_TREE;
 871                   if (e->flags & EDGE_FAKE)
 872                     flag_bits |= GCOV_ARC_FAKE;
 873                   if (e->flags & EDGE_FALLTHRU)
 874                     flag_bits |= GCOV_ARC_FALLTHROUGH;
 875
 876                   gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest));
 877                   gcov_write_unsigned (flag_bits);
 878                 }
 879             }
 880
 881           gcov_write_length (offset);
 882         }
 883     }
 884
 885   /* Line numbers.  */
 886   /* FIXME:  make this work for trees.  (Line numbers are in location_t
 887      objects, but aren't always attached to the obvious tree...) */
 888   if (coverage_begin_output () && !ir_type ())
 889     {
 890       char const *prev_file_name = NULL;
 891       gcov_position_t offset;
 892
 893       FOR_EACH_BB (bb)
 894         {
 895           rtx insn = BB_HEAD (bb);
 896           int ignore_next_note = 0;
 897
 898           offset = 0;
 899
 900           /* We are looking for line number notes.  Search backward
 901              before basic block to find correct ones.  */
 902           insn = prev_nonnote_insn (insn);
 903           if (!insn)
 904             insn = get_insns ();
 905           else
 906             insn = NEXT_INSN (insn);
 907
 908           while (insn != BB_END (bb))
 909             {
 910               if (GET_CODE (insn) == NOTE)
 911                 {
 912                   /* Must ignore the line number notes that
 913                      immediately follow the end of an inline function
 914                      to avoid counting it twice.  There is a note
 915                      before the call, and one after the call.  */
 916                   if (NOTE_LINE_NUMBER (insn)
 917                       == NOTE_INSN_REPEATED_LINE_NUMBER)
 918                     ignore_next_note = 1;
 919                   else if (NOTE_LINE_NUMBER (insn) <= 0)
 920                     /*NOP*/;
 921                   else if (ignore_next_note)
 922                     ignore_next_note = 0;
 923                   else
 924                     {
 925                       expanded_location s;
 926
 927                       if (!offset)
 928                         {
 929                           offset = gcov_write_tag (GCOV_TAG_LINES);
 930                           gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
 931                         }
 932
 933                       NOTE_EXPANDED_LOCATION (s, insn);
 934
 935                       /* If this is a new source file, then output the
 936                          file's name to the .bb file.  */
 937                       if (!prev_file_name
 938                           || strcmp (s.file, prev_file_name))
 939                         {
 940                           prev_file_name = s.file;
 941                           gcov_write_unsigned (0);
 942                           gcov_write_string (prev_file_name);
 943                         }
 944                       gcov_write_unsigned (s.line);
 945                     }
 946                 }
 947               insn = NEXT_INSN (insn);
 948             }
 949
 950           if (offset)
 951             {
 952               /* A file of NULL indicates the end of run.  */
 953               gcov_write_unsigned (0);
 954               gcov_write_string (NULL);
 955               gcov_write_length (offset);
 956             }
 957         }
 958     }
 959
 960   ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
 961   EXIT_BLOCK_PTR->index = EXIT_BLOCK;
 962 #undef BB_TO_GCOV_INDEX
 963
 964   if (flag_profile_values)
 965     find_values_to_profile (&n_values, &values);
 966
 967   if (flag_branch_probabilities)
 968     {
 969       compute_branch_probabilities ();
 970       if (flag_profile_values)
 971         compute_value_histograms (n_values, values);
 972     }
 973
 974   /* For each edge not on the spanning tree, add counting code.  */
 975   if (profile_arc_flag
 976       && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
 977     {
 978       unsigned n_instrumented = instrument_edges (el);
 979
 980       if (n_instrumented != num_instrumented)
 981         abort ();
 982
 983       if (flag_profile_values)
 984         instrument_values (n_values, values);
 985
 986       /* Commit changes done by instrumentation.  */
 987       if (ir_type ())
 988         bsi_commit_edge_inserts ((int *)NULL);
 989       else
 990         {
 991           commit_edge_insertions_watch_calls ();
 992           allocate_reg_info (max_reg_num (), FALSE, FALSE);
 993         }
 994     }
 995
 996   remove_fake_edges ();
 997   free_aux_for_edges ();
 998
 999   if (!ir_type ())
1000     {
1001       /* Re-merge split basic blocks and the mess introduced by
1002          insert_insn_on_edge.  */
1003       cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
1004       if (profile_dump_file())
1005         dump_flow_info (profile_dump_file());
1006     }
1007
1008   free_edge_list (el);
1009 }
1010 \f
1011 /* Union find algorithm implementation for the basic blocks using
1012    aux fields.  */
1013
1014 static basic_block
1015 find_group (basic_block bb)
1016 {
1017   basic_block group = bb, bb1;
1018
1019   while ((basic_block) group->aux != group)
1020     group = (basic_block) group->aux;
1021
1022   /* Compress path.  */
1023   while ((basic_block) bb->aux != group)
1024     {
1025       bb1 = (basic_block) bb->aux;
1026       bb->aux = (void *) group;
1027       bb = bb1;
1028     }
1029   return group;
1030 }
1031
1032 static void
1033 union_groups (basic_block bb1, basic_block bb2)
1034 {
1035   basic_block bb1g = find_group (bb1);
1036   basic_block bb2g = find_group (bb2);
1037
1038   /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
1039      this code is unlikely going to be performance problem anyway.  */
1040   if (bb1g == bb2g)
1041     abort ();
1042
1043   bb1g->aux = bb2g;
1044 }
1045 \f
1046 /* This function searches all of the edges in the program flow graph, and puts
1047    as many bad edges as possible onto the spanning tree.  Bad edges include
1048    abnormals edges, which can't be instrumented at the moment.  Since it is
1049    possible for fake edges to form a cycle, we will have to develop some
1050    better way in the future.  Also put critical edges to the tree, since they
1051    are more expensive to instrument.  */
1052
1053 static void
1054 find_spanning_tree (struct edge_list *el)
1055 {
1056   int i;
1057   int num_edges = NUM_EDGES (el);
1058   basic_block bb;
1059
1060   /* We use aux field for standard union-find algorithm.  */
1061   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1062     bb->aux = bb;
1063
1064   /* Add fake edge exit to entry we can't instrument.  */
1065   union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1066
1067   /* First add all abnormal edges to the tree unless they form a cycle. Also
1068      add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1069      setting return value from function.  */
1070   for (i = 0; i < num_edges; i++)
1071     {
1072       edge e = INDEX_EDGE (el, i);
1073       if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1074            || e->dest == EXIT_BLOCK_PTR)
1075           && !EDGE_INFO (e)->ignore
1076           && (find_group (e->src) != find_group (e->dest)))
1077         {
1078           if (dump_file)
1079             fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1080                      e->src->index, e->dest->index);
1081           EDGE_INFO (e)->on_tree = 1;
1082           union_groups (e->src, e->dest);
1083         }
1084     }
1085
1086   /* Now insert all critical edges to the tree unless they form a cycle.  */
1087   for (i = 0; i < num_edges; i++)
1088     {
1089       edge e = INDEX_EDGE (el, i);
1090       if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore
1091           && find_group (e->src) != find_group (e->dest))
1092         {
1093           if (dump_file)
1094             fprintf (dump_file, "Critical edge %d to %d put to tree\n",
1095                      e->src->index, e->dest->index);
1096           EDGE_INFO (e)->on_tree = 1;
1097           union_groups (e->src, e->dest);
1098         }
1099     }
1100
1101   /* And now the rest.  */
1102   for (i = 0; i < num_edges; i++)
1103     {
1104       edge e = INDEX_EDGE (el, i);
1105       if (!EDGE_INFO (e)->ignore
1106           && find_group (e->src) != find_group (e->dest))
1107         {
1108           if (dump_file)
1109             fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1110                      e->src->index, e->dest->index);
1111           EDGE_INFO (e)->on_tree = 1;
1112           union_groups (e->src, e->dest);
1113         }
1114     }
1115
1116   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1117     bb->aux = NULL;
1118 }
1119 \f
1120 /* Perform file-level initialization for branch-prob processing.  */
1121
1122 void
1123 init_branch_prob (void)
1124 {
1125   int i;
1126
1127   total_num_blocks = 0;
1128   total_num_edges = 0;
1129   total_num_edges_ignored = 0;
1130   total_num_edges_instrumented = 0;
1131   total_num_blocks_created = 0;
1132   total_num_passes = 0;
1133   total_num_times_called = 0;
1134   total_num_branches = 0;
1135   total_num_never_executed = 0;
1136   for (i = 0; i < 20; i++)
1137     total_hist_br_prob[i] = 0;
1138 }
1139
1140 /* Performs file-level cleanup after branch-prob processing
1141    is completed.  */
1142
1143 void
1144 end_branch_prob (void)
1145 {
1146   if (dump_file)
1147     {
1148       fprintf (dump_file, "\n");
1149       fprintf (dump_file, "Total number of blocks: %d\n",
1150                total_num_blocks);
1151       fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1152       fprintf (dump_file, "Total number of ignored edges: %d\n",
1153                total_num_edges_ignored);
1154       fprintf (dump_file, "Total number of instrumented edges: %d\n",
1155                total_num_edges_instrumented);
1156       fprintf (dump_file, "Total number of blocks created: %d\n",
1157                total_num_blocks_created);
1158       fprintf (dump_file, "Total number of graph solution passes: %d\n",
1159                total_num_passes);
1160       if (total_num_times_called != 0)
1161         fprintf (dump_file, "Average number of graph solution passes: %d\n",
1162                  (total_num_passes + (total_num_times_called  >> 1))
1163                  / total_num_times_called);
1164       fprintf (dump_file, "Total number of branches: %d\n",
1165                total_num_branches);
1166       fprintf (dump_file, "Total number of branches never executed: %d\n",
1167                total_num_never_executed);
1168       if (total_num_branches)
1169         {
1170           int i;
1171
1172           for (i = 0; i < 10; i++)
1173             fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1174                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1175                      / total_num_branches, 5*i, 5*i+5);
1176         }
1177     }
1178 }
1179
1180 /* Set up hooks to enable tree-based profiling.  */
1181
1182 void
1183 tree_register_profile_hooks (void)
1184 {
1185   profile_hooks = &tree_profile_hooks;
1186   if (!ir_type ())
1187     abort ();
1188 }
1189
1190 /* Set up hooks to enable RTL-based profiling.  */
1191
1192 void
1193 rtl_register_profile_hooks (void)
1194 {
1195   profile_hooks = &rtl_profile_hooks;
1196   if (ir_type ())
1197     abort ();
1198 }