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