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