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