gcc/profile.c

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