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