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