gcc/profile.c

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