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, 2008
   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               && (LOCATION_FILE (e->goto_locus)
 818                   != LOCATION_FILE (EXPR_LOCATION  (last))
 819                   || (LOCATION_LINE (e->goto_locus)
 820                       != LOCATION_LINE (EXPR_LOCATION  (last)))))
 821             {
 822               basic_block new = split_edge (e);
 823               single_succ_edge (new)->goto_locus = e->goto_locus;
 824             }
 825           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 826                && e->dest != EXIT_BLOCK_PTR)
 827             need_exit_edge = 1;
 828           if (e->dest == EXIT_BLOCK_PTR)
 829             have_exit_edge = 1;
 830         }
 831       FOR_EACH_EDGE (e, ei, bb->preds)
 832         {
 833           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 834                && e->src != ENTRY_BLOCK_PTR)
 835             need_entry_edge = 1;
 836           if (e->src == ENTRY_BLOCK_PTR)
 837             have_entry_edge = 1;
 838         }
 839
 840       if (need_exit_edge && !have_exit_edge)
 841         {
 842           if (dump_file)
 843             fprintf (dump_file, "Adding fake exit edge to bb %i\n",
 844                      bb->index);
 845           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 846         }
 847       if (need_entry_edge && !have_entry_edge)
 848         {
 849           if (dump_file)
 850             fprintf (dump_file, "Adding fake entry edge to bb %i\n",
 851                      bb->index);
 852           make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
 853         }
 854     }
 855
 856   el = create_edge_list ();
 857   num_edges = NUM_EDGES (el);
 858   alloc_aux_for_edges (sizeof (struct edge_info));
 859
 860   /* The basic blocks are expected to be numbered sequentially.  */
 861   compact_blocks ();
 862
 863   ignored_edges = 0;
 864   for (i = 0 ; i < num_edges ; i++)
 865     {
 866       edge e = INDEX_EDGE (el, i);
 867       e->count = 0;
 868
 869       /* Mark edges we've replaced by fake edges above as ignored.  */
 870       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 871           && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
 872         {
 873           EDGE_INFO (e)->ignore = 1;
 874           ignored_edges++;
 875         }
 876     }
 877
 878   /* Create spanning tree from basic block graph, mark each edge that is
 879      on the spanning tree.  We insert as many abnormal and critical edges
 880      as possible to minimize number of edge splits necessary.  */
 881
 882   find_spanning_tree (el);
 883
 884   /* Fake edges that are not on the tree will not be instrumented, so
 885      mark them ignored.  */
 886   for (num_instrumented = i = 0; i < num_edges; i++)
 887     {
 888       edge e = INDEX_EDGE (el, i);
 889       struct edge_info *inf = EDGE_INFO (e);
 890
 891       if (inf->ignore || inf->on_tree)
 892         /*NOP*/;
 893       else if (e->flags & EDGE_FAKE)
 894         {
 895           inf->ignore = 1;
 896           ignored_edges++;
 897         }
 898       else
 899         num_instrumented++;
 900     }
 901
 902   total_num_blocks += n_basic_blocks;
 903   if (dump_file)
 904     fprintf (dump_file, "%d basic blocks\n", n_basic_blocks);
 905
 906   total_num_edges += num_edges;
 907   if (dump_file)
 908     fprintf (dump_file, "%d edges\n", num_edges);
 909
 910   total_num_edges_ignored += ignored_edges;
 911   if (dump_file)
 912     fprintf (dump_file, "%d ignored edges\n", ignored_edges);
 913
 914   /* Write the data from which gcov can reconstruct the basic block
 915      graph.  */
 916
 917   /* Basic block flags */
 918   if (coverage_begin_output ())
 919     {
 920       gcov_position_t offset;
 921
 922       offset = gcov_write_tag (GCOV_TAG_BLOCKS);
 923       for (i = 0; i != (unsigned) (n_basic_blocks); i++)
 924         gcov_write_unsigned (0);
 925       gcov_write_length (offset);
 926     }
 927
 928    /* Keep all basic block indexes nonnegative in the gcov output.
 929       Index 0 is used for entry block, last index is for exit block.
 930       */
 931   ENTRY_BLOCK_PTR->index = 1;
 932   EXIT_BLOCK_PTR->index = last_basic_block;
 933
 934   /* Arcs */
 935   if (coverage_begin_output ())
 936     {
 937       gcov_position_t offset;
 938
 939       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 940         {
 941           edge e;
 942           edge_iterator ei;
 943
 944           offset = gcov_write_tag (GCOV_TAG_ARCS);
 945           gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
 946
 947           FOR_EACH_EDGE (e, ei, bb->succs)
 948             {
 949               struct edge_info *i = EDGE_INFO (e);
 950               if (!i->ignore)
 951                 {
 952                   unsigned flag_bits = 0;
 953
 954                   if (i->on_tree)
 955                     flag_bits |= GCOV_ARC_ON_TREE;
 956                   if (e->flags & EDGE_FAKE)
 957                     flag_bits |= GCOV_ARC_FAKE;
 958                   if (e->flags & EDGE_FALLTHRU)
 959                     flag_bits |= GCOV_ARC_FALLTHROUGH;
 960                   /* On trees we don't have fallthru flags, but we can
 961                      recompute them from CFG shape.  */
 962                   if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
 963                       && e->src->next_bb == e->dest)
 964                     flag_bits |= GCOV_ARC_FALLTHROUGH;
 965
 966                   gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest));
 967                   gcov_write_unsigned (flag_bits);
 968                 }
 969             }
 970
 971           gcov_write_length (offset);
 972         }
 973     }
 974
 975   /* Line numbers.  */
 976   if (coverage_begin_output ())
 977     {
 978       gcov_position_t offset;
 979
 980       /* Initialize the output.  */
 981       output_location (NULL, 0, NULL, NULL);
 982
 983       FOR_EACH_BB (bb)
 984         {
 985           block_stmt_iterator bsi;
 986
 987           offset = 0;
 988
 989           if (bb == ENTRY_BLOCK_PTR->next_bb)
 990             {
 991               expanded_location curr_location =
 992                 expand_location (DECL_SOURCE_LOCATION (current_function_decl));
 993               output_location (curr_location.file, curr_location.line,
 994                                &offset, bb);
 995             }
 996
 997           for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 998             {
 999               tree stmt = bsi_stmt (bsi);
1000               if (EXPR_HAS_LOCATION (stmt))
1001                 output_location (EXPR_FILENAME (stmt), EXPR_LINENO (stmt),
1002                                  &offset, bb);
1003               /* Take into account modify statements nested in return
1004                  produced by C++ NRV transformation.  */
1005               if (TREE_CODE (stmt) == RETURN_EXPR
1006                   && TREE_OPERAND (stmt, 0)
1007                   && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR
1008                   && EXPR_HAS_LOCATION (TREE_OPERAND (stmt, 0)))
1009                 output_location (EXPR_FILENAME (TREE_OPERAND (stmt, 0)),
1010                                  EXPR_LINENO (TREE_OPERAND (stmt, 0)),
1011                                  &offset, bb);
1012             }
1013
1014           /* Notice GOTO expressions we eliminated while constructing the
1015              CFG.  */
1016           if (single_succ_p (bb) && single_succ_edge (bb)->goto_locus)
1017             {
1018               location_t curr_location = single_succ_edge (bb)->goto_locus;
1019               /* ??? The FILE/LINE API is inconsistent for these cases.  */
1020               output_location (LOCATION_FILE (curr_location),
1021                                LOCATION_LINE (curr_location), &offset, bb);
1022             }
1023
1024           if (offset)
1025             {
1026               /* A file of NULL indicates the end of run.  */
1027               gcov_write_unsigned (0);
1028               gcov_write_string (NULL);
1029               gcov_write_length (offset);
1030             }
1031         }
1032     }
1033
1034   ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
1035   EXIT_BLOCK_PTR->index = EXIT_BLOCK;
1036 #undef BB_TO_GCOV_INDEX
1037
1038   if (flag_profile_values)
1039     find_values_to_profile (&values);
1040
1041   if (flag_branch_probabilities)
1042     {
1043       compute_branch_probabilities ();
1044       if (flag_profile_values)
1045         compute_value_histograms (values);
1046     }
1047
1048   remove_fake_edges ();
1049
1050   /* For each edge not on the spanning tree, add counting code.  */
1051   if (profile_arc_flag
1052       && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1053     {
1054       unsigned n_instrumented;
1055
1056       profile_hooks->init_edge_profiler ();
1057
1058       n_instrumented = instrument_edges (el);
1059
1060       gcc_assert (n_instrumented == num_instrumented);
1061
1062       if (flag_profile_values)
1063         instrument_values (values);
1064
1065       /* Commit changes done by instrumentation.  */
1066       bsi_commit_edge_inserts ();
1067     }
1068
1069   free_aux_for_edges ();
1070
1071   VEC_free (histogram_value, heap, values);
1072   free_edge_list (el);
1073   if (flag_branch_probabilities)
1074     profile_status = PROFILE_READ;
1075   coverage_end_function ();
1076 }
1077 \f
1078 /* Union find algorithm implementation for the basic blocks using
1079    aux fields.  */
1080
1081 static basic_block
1082 find_group (basic_block bb)
1083 {
1084   basic_block group = bb, bb1;
1085
1086   while ((basic_block) group->aux != group)
1087     group = (basic_block) group->aux;
1088
1089   /* Compress path.  */
1090   while ((basic_block) bb->aux != group)
1091     {
1092       bb1 = (basic_block) bb->aux;
1093       bb->aux = (void *) group;
1094       bb = bb1;
1095     }
1096   return group;
1097 }
1098
1099 static void
1100 union_groups (basic_block bb1, basic_block bb2)
1101 {
1102   basic_block bb1g = find_group (bb1);
1103   basic_block bb2g = find_group (bb2);
1104
1105   /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
1106      this code is unlikely going to be performance problem anyway.  */
1107   gcc_assert (bb1g != bb2g);
1108
1109   bb1g->aux = bb2g;
1110 }
1111 \f
1112 /* This function searches all of the edges in the program flow graph, and puts
1113    as many bad edges as possible onto the spanning tree.  Bad edges include
1114    abnormals edges, which can't be instrumented at the moment.  Since it is
1115    possible for fake edges to form a cycle, we will have to develop some
1116    better way in the future.  Also put critical edges to the tree, since they
1117    are more expensive to instrument.  */
1118
1119 static void
1120 find_spanning_tree (struct edge_list *el)
1121 {
1122   int i;
1123   int num_edges = NUM_EDGES (el);
1124   basic_block bb;
1125
1126   /* We use aux field for standard union-find algorithm.  */
1127   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1128     bb->aux = bb;
1129
1130   /* Add fake edge exit to entry we can't instrument.  */
1131   union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1132
1133   /* First add all abnormal edges to the tree unless they form a cycle. Also
1134      add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1135      setting return value from function.  */
1136   for (i = 0; i < num_edges; i++)
1137     {
1138       edge e = INDEX_EDGE (el, i);
1139       if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1140            || e->dest == EXIT_BLOCK_PTR)
1141           && !EDGE_INFO (e)->ignore
1142           && (find_group (e->src) != find_group (e->dest)))
1143         {
1144           if (dump_file)
1145             fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1146                      e->src->index, e->dest->index);
1147           EDGE_INFO (e)->on_tree = 1;
1148           union_groups (e->src, e->dest);
1149         }
1150     }
1151
1152   /* Now insert all critical edges to the tree unless they form a cycle.  */
1153   for (i = 0; i < num_edges; i++)
1154     {
1155       edge e = INDEX_EDGE (el, i);
1156       if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore
1157           && find_group (e->src) != find_group (e->dest))
1158         {
1159           if (dump_file)
1160             fprintf (dump_file, "Critical edge %d to %d put to tree\n",
1161                      e->src->index, e->dest->index);
1162           EDGE_INFO (e)->on_tree = 1;
1163           union_groups (e->src, e->dest);
1164         }
1165     }
1166
1167   /* And now the rest.  */
1168   for (i = 0; i < num_edges; i++)
1169     {
1170       edge e = INDEX_EDGE (el, i);
1171       if (!EDGE_INFO (e)->ignore
1172           && find_group (e->src) != find_group (e->dest))
1173         {
1174           if (dump_file)
1175             fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1176                      e->src->index, e->dest->index);
1177           EDGE_INFO (e)->on_tree = 1;
1178           union_groups (e->src, e->dest);
1179         }
1180     }
1181
1182   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1183     bb->aux = NULL;
1184 }
1185 \f
1186 /* Perform file-level initialization for branch-prob processing.  */
1187
1188 void
1189 init_branch_prob (void)
1190 {
1191   int i;
1192
1193   total_num_blocks = 0;
1194   total_num_edges = 0;
1195   total_num_edges_ignored = 0;
1196   total_num_edges_instrumented = 0;
1197   total_num_blocks_created = 0;
1198   total_num_passes = 0;
1199   total_num_times_called = 0;
1200   total_num_branches = 0;
1201   total_num_never_executed = 0;
1202   for (i = 0; i < 20; i++)
1203     total_hist_br_prob[i] = 0;
1204 }
1205
1206 /* Performs file-level cleanup after branch-prob processing
1207    is completed.  */
1208
1209 void
1210 end_branch_prob (void)
1211 {
1212   if (dump_file)
1213     {
1214       fprintf (dump_file, "\n");
1215       fprintf (dump_file, "Total number of blocks: %d\n",
1216                total_num_blocks);
1217       fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1218       fprintf (dump_file, "Total number of ignored edges: %d\n",
1219                total_num_edges_ignored);
1220       fprintf (dump_file, "Total number of instrumented edges: %d\n",
1221                total_num_edges_instrumented);
1222       fprintf (dump_file, "Total number of blocks created: %d\n",
1223                total_num_blocks_created);
1224       fprintf (dump_file, "Total number of graph solution passes: %d\n",
1225                total_num_passes);
1226       if (total_num_times_called != 0)
1227         fprintf (dump_file, "Average number of graph solution passes: %d\n",
1228                  (total_num_passes + (total_num_times_called  >> 1))
1229                  / total_num_times_called);
1230       fprintf (dump_file, "Total number of branches: %d\n",
1231                total_num_branches);
1232       fprintf (dump_file, "Total number of branches never executed: %d\n",
1233                total_num_never_executed);
1234       if (total_num_branches)
1235         {
1236           int i;
1237
1238           for (i = 0; i < 10; i++)
1239             fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1240                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1241                      / total_num_branches, 5*i, 5*i+5);
1242         }
1243     }
1244 }
1245
1246 /* Set up hooks to enable tree-based profiling.  */
1247
1248 void
1249 tree_register_profile_hooks (void)
1250 {
1251   gcc_assert (current_ir_type () == IR_GIMPLE);
1252   profile_hooks = &tree_profile_hooks;
1253 }
1254