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