gcc/profile.c

   1 /* Calculate branch probabilities, and basic block execution counts.
   2    Copyright (C) 1990, 91-94, 96-99, 2000 Free Software Foundation, Inc.
   3    Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
   4    based on some ideas from Dain Samples of UC Berkeley.
   5    Further mangling by Bob Manson, Cygnus Support.
   6
   7 This file is part of GNU CC.
   8
   9 GNU CC is free software; you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation; either version 2, or (at your option)
  12 any later version.
  13
  14 GNU CC is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GNU CC; see the file COPYING.  If not, write to
  21 the Free Software Foundation, 59 Temple Place - Suite 330,
  22 Boston, MA 02111-1307, USA.  */
  23
  24 /* ??? Register allocation should use basic block execution counts to
  25    give preference to the most commonly executed blocks.  */
  26
  27 /* ??? The .da files are not safe.  Changing the program after creating .da
  28    files or using different options when compiling with -fbranch-probabilities
  29    can result the arc data not matching the program.  Maybe add instrumented
  30    arc count to .bbg file?  Maybe check whether PFG matches the .bbg file?  */
  31
  32 /* ??? Should calculate branch probabilities before instrumenting code, since
  33    then we can use arc counts to help decide which arcs to instrument.  */
  34
  35 #include "config.h"
  36 #include "system.h"
  37 #include "rtl.h"
  38 #include "tree.h"
  39 #include "flags.h"
  40 #include "insn-flags.h"
  41 #include "insn-config.h"
  42 #include "output.h"
  43 #include "regs.h"
  44 #include "expr.h"
  45 #include "function.h"
  46 #include "gcov-io.h"
  47 #include "toplev.h"
  48 #include "ggc.h"
  49 #include "basic-block.h"
  50
  51
  52 /* Additional information about the edges we need.  */
  53 struct edge_info
  54   {
  55     unsigned int count_valid : 1;
  56     unsigned int on_tree : 1;
  57     unsigned int ignore : 1;
  58   };
  59 struct bb_info
  60   {
  61     unsigned int count_valid : 1;
  62     int succ_count;
  63     int pred_count;
  64   };
  65
  66 #define EDGE_INFO(e)  ((struct edge_info *) (e)->aux)
  67 #define BB_INFO(b)  ((struct bb_info *) (b)->aux)
  68
  69 /* Keep all basic block indexes nonnegative in the gcov output.  Index 0
  70    is used for entry block, last block exit block.   */
  71 #define GCOV_INDEX_TO_BB(i)  ((i) == 0 ? ENTRY_BLOCK_PTR                \
  72                               : (((i) == n_basic_blocks + 1)            \
  73                                  ? EXIT_BLOCK_PTR : BASIC_BLOCK ((i)-1)))
  74 #define BB_TO_GCOV_INDEX(bb)  ((bb) == ENTRY_BLOCK_PTR ? 0              \
  75                                : ((bb) == EXIT_BLOCK_PTR                \
  76                                   ? n_basic_blocks + 1 : (bb)->index + 1))
  77
  78 /* Name and file pointer of the output file for the basic block graph.  */
  79
  80 static FILE *bbg_file;
  81
  82 /* Name and file pointer of the input file for the arc count data.  */
  83
  84 static FILE *da_file;
  85
  86 /* Pointer of the output file for the basic block/line number map. */
  87 static FILE *bb_file;
  88
  89 /* Last source file name written to bb_file. */
  90
  91 static char *last_bb_file_name;
  92
  93 /* Used by final, for allocating the proper amount of storage for the
  94    instrumented arc execution counts.  */
  95
  96 int count_instrumented_edges;
  97
  98 /* Collect statistics on the performance of this pass for the entire source
  99    file.  */
 100
 101 static int total_num_blocks;
 102 static int total_num_edges;
 103 static int total_num_edges_instrumented;
 104 static int total_num_blocks_created;
 105 static int total_num_passes;
 106 static int total_num_times_called;
 107 static int total_hist_br_prob[20];
 108 static int total_num_never_executed;
 109 static int total_num_branches;
 110
 111 /* Forward declarations.  */
 112 static void find_spanning_tree PARAMS ((struct edge_list *));
 113 static void init_edge_profiler PARAMS ((void));
 114 static rtx gen_edge_profiler PARAMS ((int));
 115 static void instrument_edges PARAMS ((struct edge_list *));
 116 static void output_gcov_string PARAMS ((const char *, long));
 117 static void compute_branch_probabilities PARAMS ((void));
 118 static basic_block find_group PARAMS ((basic_block));
 119 static void union_groups PARAMS ((basic_block, basic_block));
 120
 121 #ifndef LONG_TYPE_SIZE
 122 #define LONG_TYPE_SIZE BITS_PER_WORD
 123 #endif
 124
 125 /* If non-zero, we need to output a constructor to set up the
 126    per-object-file data. */
 127 static int need_func_profiler = 0;
 128 \f
 129 /* Add edge instrumentation code to the entire insn chain.
 130
 131    F is the first insn of the chain.
 132    NUM_BLOCKS is the number of basic blocks found in F.  */
 133
 134 static void
 135 instrument_edges (el)
 136      struct edge_list *el;
 137 {
 138   int i;
 139   int num_instr_edges = 0;
 140   int num_edges = NUM_EDGES (el);
 141   remove_fake_edges ();
 142
 143   for (i = 0; i < n_basic_blocks + 2; i++)
 144     {
 145       basic_block bb = GCOV_INDEX_TO_BB (i);
 146       edge e = bb->succ;
 147       while (e)
 148         {
 149           struct edge_info *inf = EDGE_INFO (e);
 150           if (!inf->ignore && !inf->on_tree)
 151             {
 152               if (e->flags & EDGE_ABNORMAL)
 153                 abort ();
 154               if (rtl_dump_file)
 155                 fprintf (rtl_dump_file, "Edge %d to %d instrumented%s\n",
 156                          e->src->index, e->dest->index,
 157                          e->flags & EDGE_CRITICAL ? " (and split)" : "");
 158               need_func_profiler = 1;
 159               insert_insn_on_edge (
 160                          gen_edge_profiler (total_num_edges_instrumented
 161                                             + num_instr_edges++), e);
 162             }
 163           e = e->succ_next;
 164         }
 165     }
 166
 167   total_num_edges_instrumented += num_instr_edges;
 168   count_instrumented_edges = total_num_edges_instrumented;
 169
 170   total_num_blocks_created += num_edges;
 171   if (rtl_dump_file)
 172     fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges);
 173
 174   commit_edge_insertions ();
 175 }
 176
 177 /* Output STRING to bb_file, surrounded by DELIMITER.  */
 178
 179 static void
 180 output_gcov_string (string, delimiter)
 181      const char *string;
 182      long delimiter;
 183 {
 184   long temp;
 185
 186   /* Write a delimiter to indicate that a file name follows.  */
 187   __write_long (delimiter, bb_file, 4);
 188
 189   /* Write the string.  */
 190   temp = strlen (string) + 1;
 191   fwrite (string, temp, 1, bb_file);
 192
 193   /* Append a few zeros, to align the output to a 4 byte boundary.  */
 194   temp = temp & 0x3;
 195   if (temp)
 196     {
 197       char c[4];
 198
 199       c[0] = c[1] = c[2] = c[3] = 0;
 200       fwrite (c, sizeof (char), 4 - temp, bb_file);
 201     }
 202
 203   /* Store another delimiter in the .bb file, just to make it easy to find
 204      the end of the file name.  */
 205   __write_long (delimiter, bb_file, 4);
 206 }
 207 \f
 208
 209 /* Compute the branch probabilities for the various branches.
 210    Annotate them accordingly.  */
 211
 212 static void
 213 compute_branch_probabilities ()
 214 {
 215   int i;
 216   int num_edges = 0;
 217   int changes;
 218   int passes;
 219   int hist_br_prob[20];
 220   int num_never_executed;
 221   int num_branches;
 222   int bad_counts = 0;
 223   struct bb_info *bb_infos;
 224
 225   /* Attach extra info block to each bb.  */
 226
 227   bb_infos = (struct bb_info *)
 228     xcalloc (n_basic_blocks + 2, sizeof (struct bb_info));
 229   for (i = 0; i < n_basic_blocks + 2; i++)
 230     {
 231       basic_block bb = GCOV_INDEX_TO_BB (i);
 232       edge e;
 233
 234       bb->aux = &bb_infos[i];
 235       for (e = bb->succ; e; e = e->succ_next)
 236         if (!EDGE_INFO (e)->ignore)
 237           BB_INFO (bb)->succ_count++;
 238       for (e = bb->pred; e; e = e->pred_next)
 239         if (!EDGE_INFO (e)->ignore)
 240           BB_INFO (bb)->pred_count++;
 241     }
 242
 243   /* Avoid predicting entry on exit nodes.  */
 244   BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
 245   BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
 246
 247   /* For each edge not on the spanning tree, set its execution count from
 248      the .da file.  */
 249
 250   /* The first count in the .da file is the number of times that the function
 251      was entered.  This is the exec_count for block zero.  */
 252
 253   for (i = 0; i < n_basic_blocks + 2; i++)
 254     {
 255       basic_block bb = GCOV_INDEX_TO_BB (i);
 256       edge e;
 257       for (e = bb->succ; e; e = e->succ_next)
 258         if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
 259           {
 260             num_edges++;
 261             if (da_file)
 262               {
 263                 long value;
 264                 __read_long (&value, da_file, 8);
 265                 e->count = value;
 266               }
 267             else
 268               e->count = 0;
 269             EDGE_INFO (e)->count_valid = 1;
 270             BB_INFO (bb)->succ_count--;
 271             BB_INFO (e->dest)->pred_count--;
 272           }
 273     }
 274
 275   if (rtl_dump_file)
 276     fprintf (rtl_dump_file, "%d edge counts read\n", num_edges);
 277
 278   /* For every block in the file,
 279      - if every exit/entrance edge has a known count, then set the block count
 280      - if the block count is known, and every exit/entrance edge but one has
 281      a known execution count, then set the count of the remaining edge
 282
 283      As edge counts are set, decrement the succ/pred count, but don't delete
 284      the edge, that way we can easily tell when all edges are known, or only
 285      one edge is unknown.  */
 286
 287   /* The order that the basic blocks are iterated through is important.
 288      Since the code that finds spanning trees starts with block 0, low numbered
 289      edges are put on the spanning tree in preference to high numbered edges.
 290      Hence, most instrumented edges are at the end.  Graph solving works much
 291      faster if we propagate numbers from the end to the start.
 292
 293      This takes an average of slightly more than 3 passes.  */
 294
 295   changes = 1;
 296   passes = 0;
 297   while (changes)
 298     {
 299       passes++;
 300       changes = 0;
 301       for (i = n_basic_blocks + 1; i >= 0; i--)
 302         {
 303           basic_block bb = GCOV_INDEX_TO_BB (i);
 304           struct bb_info *bi = BB_INFO (bb);
 305           if (! bi->count_valid)
 306             {
 307               if (bi->succ_count == 0)
 308                 {
 309                   edge e;
 310                   int total = 0;
 311
 312                   for (e = bb->succ; e; e = e->succ_next)
 313                     total += e->count;
 314                   bb->count = total;
 315                   bi->count_valid = 1;
 316                   changes = 1;
 317                 }
 318               else if (bi->pred_count == 0)
 319                 {
 320                   edge e;
 321                   int total = 0;
 322
 323                   for (e = bb->pred; e; e = e->pred_next)
 324                     total += e->count;
 325                   bb->count = total;
 326                   bi->count_valid = 1;
 327                   changes = 1;
 328                 }
 329             }
 330           if (bi->count_valid)
 331             {
 332               if (bi->succ_count == 1)
 333                 {
 334                   edge e;
 335                   int total = 0;
 336
 337                   /* One of the counts will be invalid, but it is zero,
 338                      so adding it in also doesn't hurt.  */
 339                   for (e = bb->succ; e; e = e->succ_next)
 340                     total += e->count;
 341
 342                   /* Seedgeh for the invalid edge, and set its count.  */
 343                   for (e = bb->succ; e; e = e->succ_next)
 344                     if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
 345                       break;
 346
 347                   /* Calculate count for remaining edge by conservation.  */
 348                   total = bb->count - total;
 349
 350                   if (! e)
 351                     abort ();
 352                   EDGE_INFO (e)->count_valid = 1;
 353                   e->count = total;
 354                   bi->succ_count--;
 355
 356                   BB_INFO (e->dest)->pred_count--;
 357                   changes = 1;
 358                 }
 359               if (bi->pred_count == 1)
 360                 {
 361                   edge e;
 362                   int total = 0;
 363
 364                   /* One of the counts will be invalid, but it is zero,
 365                      so adding it in also doesn't hurt.  */
 366                   for (e = bb->pred; e; e = e->pred_next)
 367                     total += e->count;
 368
 369                   /* Seedgeh for the invalid edge, and set its count.  */
 370                   for (e = bb->pred; e; e = e->pred_next)
 371                     if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
 372                       break;
 373
 374                   /* Calculate count for remaining edge by conservation.  */
 375                   total = bb->count - total + e->count;
 376
 377                   if (! e)
 378                     abort ();
 379                   EDGE_INFO (e)->count_valid = 1;
 380                   e->count = total;
 381                   bi->pred_count--;
 382
 383                   BB_INFO (e->src)->succ_count--;
 384                   changes = 1;
 385                 }
 386             }
 387         }
 388     }
 389   if (rtl_dump_file)
 390     dump_flow_info (rtl_dump_file);
 391
 392   total_num_passes += passes;
 393   if (rtl_dump_file)
 394     fprintf (rtl_dump_file, "Graph solving took %d passes.\n\n", passes);
 395
 396   /* If the graph has been correctly solved, every block will have a
 397      succ and pred count of zero.  */
 398   for (i = 0; i < n_basic_blocks; i++)
 399     {
 400       basic_block bb = BASIC_BLOCK (i);
 401       if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count)
 402         abort ();
 403     }
 404
 405   /* For every edge, calculate its branch probability and add a reg_note
 406      to the branch insn to indicate this.  */
 407
 408   for (i = 0; i < 20; i++)
 409     hist_br_prob[i] = 0;
 410   num_never_executed = 0;
 411   num_branches = 0;
 412
 413   for (i = 0; i < n_basic_blocks; i++)
 414     {
 415       basic_block bb = BASIC_BLOCK (i);
 416       edge e;
 417       rtx insn;
 418       int total;
 419       rtx note;
 420
 421       total = bb->count;
 422       if (!total)
 423         continue;
 424       for (e = bb->succ; e; e = e->succ_next)
 425         {
 426           if (any_condjump_p (e->src->end)
 427               && !EDGE_INFO (e)->ignore
 428               && !(e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE)))
 429             {
 430               int prob;
 431               /* This calculates the branch probability as an integer between
 432                  0 and REG_BR_PROB_BASE, properly rounded to the nearest
 433                  integer.  Perform the arithmetic in double to avoid
 434                  overflowing the range of ints.  */
 435               if (total == 0)
 436                 prob = -1;
 437               else
 438                 {
 439                   prob = (((double)e->count * REG_BR_PROB_BASE)
 440                           + (total >> 1)) / total;
 441                   if (prob < 0 || prob > REG_BR_PROB_BASE)
 442                     {
 443                       if (rtl_dump_file)
 444                         fprintf (rtl_dump_file, "bad count: prob for %d-%d thought to be %d (forcibly normalized)\n",
 445                                  e->src->index, e->dest->index, prob);
 446
 447                       bad_counts = 1;
 448                       prob = REG_BR_PROB_BASE / 2;
 449                     }
 450
 451                   /* Match up probability with JUMP pattern.  */
 452                   if (e->flags & EDGE_FALLTHRU)
 453                     prob = REG_BR_PROB_BASE - prob;
 454                 }
 455
 456               if (prob == -1)
 457                 num_never_executed++;
 458               else
 459                 {
 460                   int index = prob * 20 / REG_BR_PROB_BASE;
 461                   if (index == 20)
 462                     index = 19;
 463                   hist_br_prob[index]++;
 464                 }
 465               num_branches++;
 466
 467               note = find_reg_note (e->src->end, REG_BR_PROB, 0);
 468               /* There may be already note put by some other pass, such
 469                  as builtin_expect expander.  */
 470               if (note)
 471                 XEXP (note, 0) = GEN_INT (prob);
 472               else
 473                 REG_NOTES (e->src->end)
 474                   = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 475                                        REG_NOTES (e->src->end));
 476             }
 477         }
 478
 479       /* Add a REG_EXEC_COUNT note to the first instruction of this block.  */
 480       insn = next_nonnote_insn (bb->head);
 481
 482       if (GET_CODE (bb->head) == CODE_LABEL)
 483         insn = next_nonnote_insn (insn);
 484
 485       /* Avoid crash on empty basic blocks.  */
 486       if (insn && INSN_P (insn))
 487         REG_NOTES (insn)
 488           = gen_rtx_EXPR_LIST (REG_EXEC_COUNT, GEN_INT (total),
 489                                REG_NOTES (insn));
 490     }
 491
 492   /* This should never happen.  */
 493   if (bad_counts)
 494     warning ("Arc profiling: some edge counts were bad.");
 495
 496   if (rtl_dump_file)
 497     {
 498       fprintf (rtl_dump_file, "%d branches\n", num_branches);
 499       fprintf (rtl_dump_file, "%d branches never executed\n",
 500                num_never_executed);
 501       if (num_branches)
 502         for (i = 0; i < 10; i++)
 503           fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
 504                    (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
 505                    5 * i, 5 * i + 5);
 506
 507       total_num_branches += num_branches;
 508       total_num_never_executed += num_never_executed;
 509       for (i = 0; i < 20; i++)
 510         total_hist_br_prob[i] += hist_br_prob[i];
 511
 512       fputc ('\n', rtl_dump_file);
 513       fputc ('\n', rtl_dump_file);
 514     }
 515
 516   free (bb_infos);
 517 }
 518
 519 /* Instrument and/or analyze program behavior based on program flow graph.
 520    In either case, this function builds a flow graph for the function being
 521    compiled.  The flow graph is stored in BB_GRAPH.
 522
 523    When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
 524    the flow graph that are needed to reconstruct the dynamic behavior of the
 525    flow graph.
 526
 527    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
 528    information from a data file containing edge count information from previous
 529    executions of the function being compiled.  In this case, the flow graph is
 530    annotated with actual execution counts, which are later propagated into the
 531    rtl for optimization purposes.
 532
 533    Main entry point of this file.  */
 534
 535 void
 536 branch_prob ()
 537 {
 538   int i;
 539   int num_edges;
 540   struct edge_info *edge_infos;
 541   struct edge_list *el;
 542
 543   /* Start of a function.  */
 544   if (flag_test_coverage)
 545     output_gcov_string (current_function_name, (long) -2);
 546
 547   total_num_times_called++;
 548
 549   /* We can't handle cyclic regions constructed using abnormal edges.
 550      To avoid these we replace every source of abnormal edge by a fake
 551      edge from entry node and every destination by fake edge to exit.
 552      This keeps graph acyclic and our calculation exact for all normal
 553      edges except for exit and entrance ones.
 554
 555      We also add fake exit edges for each call and asm statement in the
 556      basic, since it may not return.  */
 557
 558   for (i = 0; i < n_basic_blocks ; i++)
 559     {
 560       rtx insn;
 561       int need_exit_edge = 0, need_entry_edge = 0;
 562       int have_exit_edge = 0, have_entry_edge = 0;
 563       basic_block bb = BASIC_BLOCK (i);
 564       edge e;
 565
 566       for (e = bb->succ; e; e = e->succ_next)
 567         {
 568           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 569                && e->dest != EXIT_BLOCK_PTR)
 570             need_exit_edge = 1;
 571           if (e->dest == EXIT_BLOCK_PTR)
 572             have_exit_edge = 1;
 573         }
 574       for (e = bb->pred; e; e = e->pred_next)
 575         {
 576           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 577                && e->src != ENTRY_BLOCK_PTR)
 578             need_entry_edge = 1;
 579           if (e->src == ENTRY_BLOCK_PTR)
 580             have_entry_edge = 1;
 581         }
 582
 583       /* ??? Not strictly needed unless flag_test_coverage, but adding
 584          them anyway keeps the .da file consistent.  */
 585       /* ??? Currently inexact for basic blocks with multiple calls.
 586          We need to split blocks here.  */
 587       for (insn = bb->head;
 588            insn != NEXT_INSN (bb->end);
 589            insn = NEXT_INSN (insn))
 590         {
 591           rtx set;
 592           if (GET_CODE (insn) == CALL_INSN && !CONST_CALL_P (insn))
 593             need_exit_edge = 1;
 594           else if (GET_CODE (insn) == INSN)
 595             {
 596               set = PATTERN (insn);
 597               if (GET_CODE (set) == PARALLEL)
 598                 set = XVECEXP (set, 0, 0);
 599               if ((GET_CODE (set) == ASM_OPERANDS && MEM_VOLATILE_P (set))
 600                   || GET_CODE (set) == ASM_INPUT)
 601                 need_exit_edge = 1;
 602             }
 603         }
 604
 605       if (need_exit_edge && !have_exit_edge)
 606         {
 607           if (rtl_dump_file)
 608             fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n",
 609                      bb->index);
 610           make_edge (NULL, bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 611         }
 612       if (need_entry_edge && !have_entry_edge)
 613         {
 614           if (rtl_dump_file)
 615             fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n",
 616                      bb->index);
 617           make_edge (NULL, ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
 618         }
 619     }
 620
 621   el = create_edge_list ();
 622   num_edges = NUM_EDGES (el);
 623   edge_infos = (struct edge_info *)
 624     xcalloc (num_edges, sizeof (struct edge_info));
 625
 626   for (i = 0 ; i < num_edges ; i++)
 627     {
 628       edge e = INDEX_EDGE (el, i);
 629       e->count = 0;
 630       e->aux = &edge_infos[i];
 631
 632       /* Mark edges we've replaced by fake edges above as ignored.  */
 633       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 634           && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
 635         EDGE_INFO (e)->ignore = 1;
 636     }
 637
 638   total_num_blocks += n_basic_blocks + 2;
 639   if (rtl_dump_file)
 640     fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
 641
 642   total_num_edges += num_edges;
 643   if (rtl_dump_file)
 644     fprintf (rtl_dump_file, "%d edges\n", num_edges);
 645
 646 #ifdef ENABLE_CHECKING
 647   verify_flow_info ();
 648 #endif
 649
 650   /* Output line number information about each basic block for
 651      GCOV utility.  */
 652   if (flag_test_coverage)
 653     {
 654       int i = 0;
 655       for (i = 0 ; i < n_basic_blocks; i++)
 656         {
 657           basic_block bb = BASIC_BLOCK (i);
 658           rtx insn = bb->head;
 659           static int ignore_next_note = 0;
 660
 661           /* We are looking for line number notes.  Search backward before
 662              basic block to find correct ones.  */
 663           insn = prev_nonnote_insn (insn);
 664           if (!insn)
 665             insn = get_insns ();
 666           else
 667             insn = NEXT_INSN (insn);
 668
 669           /* Output a zero to the .bb file to indicate that a new
 670              block list is starting.  */
 671           __write_long (0, bb_file, 4);
 672
 673           while (insn != bb->end)
 674             {
 675               if (GET_CODE (insn) == NOTE)
 676                 {
 677                   /* Must ignore the line number notes that immediately
 678                      follow the end of an inline function to avoid counting
 679                      it twice.  There is a note before the call, and one
 680                      after the call.  */
 681                   if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER)
 682                     ignore_next_note = 1;
 683                   else if (NOTE_LINE_NUMBER (insn) > 0)
 684                     {
 685                       if (ignore_next_note)
 686                         ignore_next_note = 0;
 687                       else
 688                         {
 689                           /* If this is a new source file, then output the
 690                              file's name to the .bb file.  */
 691                           if (! last_bb_file_name
 692                               || strcmp (NOTE_SOURCE_FILE (insn),
 693                                          last_bb_file_name))
 694                             {
 695                               if (last_bb_file_name)
 696                                 free (last_bb_file_name);
 697                               last_bb_file_name
 698                                 = xstrdup (NOTE_SOURCE_FILE (insn));
 699                               output_gcov_string (NOTE_SOURCE_FILE (insn),
 700                                                   (long)-1);
 701                             }
 702                           /* Output the line number to the .bb file.  Must be
 703                              done after the output_bb_profile_data() call, and
 704                              after the file name is written, to ensure that it
 705                              is correctly handled by gcov.  */
 706                           __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
 707                         }
 708                     }
 709                 }
 710               insn = NEXT_INSN (insn);
 711             }
 712         }
 713       __write_long (0, bb_file, 4);
 714     }
 715
 716   /* Create spanning tree from basic block graph, mark each edge that is
 717      on the spanning tree.  We insert as many abnormal and critical edges
 718      as possible to minimize number of edge splits necesary. */
 719
 720   find_spanning_tree (el);
 721
 722   /* Create a .bbg file from which gcov can reconstruct the basic block
 723      graph.  First output the number of basic blocks, and then for every
 724      edge output the source and target basic block numbers.
 725      NOTE: The format of this file must be compatible with gcov.  */
 726
 727   if (flag_test_coverage)
 728     {
 729       int flag_bits;
 730
 731       /* The plus 2 stands for entry and exit block.  */
 732       __write_long (n_basic_blocks + 2, bbg_file, 4);
 733       __write_long (num_edges + 1, bbg_file, 4);
 734
 735       for (i = 0; i < n_basic_blocks + 1; i++)
 736         {
 737           basic_block bb = GCOV_INDEX_TO_BB (i);
 738           edge e;
 739           long count = 0;
 740
 741           for (e = bb->succ; e; e = e->succ_next)
 742             if (!EDGE_INFO (e)->ignore)
 743               count++;
 744           __write_long (count, bbg_file, 4);
 745
 746           for (e = bb->succ; e; e = e->succ_next)
 747             {
 748               struct edge_info *i = EDGE_INFO (e);
 749               if (!i->ignore)
 750                 {
 751                   flag_bits = 0;
 752                   if (i->on_tree)
 753                     flag_bits |= 0x1;
 754                   if (e->flags & EDGE_ABNORMAL)
 755                     flag_bits |= 0x2;
 756                   if (e->flags & EDGE_FALLTHRU)
 757                     flag_bits |= 0x4;
 758
 759                   __write_long (BB_TO_GCOV_INDEX (e->dest), bbg_file, 4);
 760                   __write_long (flag_bits, bbg_file, 4);
 761                 }
 762             }
 763         }
 764       /* Emit fake loopback edge for EXIT block to maitain compatibility with
 765          old gcov format.  */
 766       __write_long (1, bbg_file, 4);
 767       __write_long (0, bbg_file, 4);
 768       __write_long (0x1, bbg_file, 4);
 769
 770       /* Emit a -1 to separate the list of all edges from the list of
 771          loop back edges that follows.  */
 772       __write_long (-1, bbg_file, 4);
 773     }
 774
 775   if (flag_branch_probabilities)
 776     compute_branch_probabilities ();
 777
 778   /* For each edge not on the spanning tree, add counting code as rtl.  */
 779
 780   if (profile_arc_flag)
 781     {
 782       instrument_edges (el);
 783       allocate_reg_info (max_reg_num (), FALSE, FALSE);
 784     }
 785
 786   remove_fake_edges ();
 787   free (edge_infos);
 788   free_edge_list (el);
 789 }
 790 \f
 791 /* Union find algorithm implementation for the basic blocks using
 792    aux fields. */
 793
 794 static basic_block
 795 find_group (bb)
 796      basic_block bb;
 797 {
 798   basic_block group = bb, bb1;
 799
 800   while ((basic_block) group->aux != group)
 801     group = (basic_block) group->aux;
 802
 803   /* Compress path.  */
 804   while ((basic_block) bb->aux != group)
 805     {
 806       bb1 = (basic_block) bb->aux;
 807       bb->aux = (void *) group;
 808       bb = bb1;
 809     }
 810   return group;
 811 }
 812
 813 static void
 814 union_groups (bb1, bb2)
 815      basic_block bb1, bb2;
 816 {
 817   basic_block bb1g = find_group (bb1);
 818   basic_block bb2g = find_group (bb2);
 819
 820   /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
 821      this code is unlikely going to be performance problem anyway.  */
 822   if (bb1g == bb2g)
 823     abort ();
 824
 825   bb1g->aux = bb2g;
 826 }
 827 \f
 828 /* This function searches all of the edges in the program flow graph, and puts
 829    as many bad edges as possible onto the spanning tree.  Bad edges include
 830    abnormals edges, which can't be instrumented at the moment.  Since it is
 831    possible for fake edges to form an cycle, we will have to develop some
 832    better way in the future.  Also put critical edges to the tree, since they
 833    are more expensive to instrument.  */
 834
 835 static void
 836 find_spanning_tree (el)
 837      struct edge_list *el;
 838 {
 839   int i;
 840   int num_edges = NUM_EDGES (el);
 841
 842   /* We use aux field for standard union-find algorithm.  */
 843   EXIT_BLOCK_PTR->aux = EXIT_BLOCK_PTR;
 844   ENTRY_BLOCK_PTR->aux = ENTRY_BLOCK_PTR;
 845   for (i = 0; i < n_basic_blocks; i++)
 846     BASIC_BLOCK (i)->aux = BASIC_BLOCK (i);
 847
 848   /* Add fake edge exit to entry we can't instrument.  */
 849   union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
 850
 851   /* First add all abnormal edges to the tree unless they form an cycle.  */
 852   for (i = 0; i < num_edges; i++)
 853     {
 854       edge e = INDEX_EDGE (el, i);
 855       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
 856           && !EDGE_INFO (e)->ignore
 857           && (find_group (e->src) != find_group (e->dest)))
 858         {
 859           EDGE_INFO (e)->on_tree = 1;
 860           union_groups (e->src, e->dest);
 861         }
 862     }
 863
 864   /* Now insert all critical edges to the tree unless they form an cycle.  */
 865   for (i = 0; i < num_edges; i++)
 866     {
 867       edge e = INDEX_EDGE (el, i);
 868       if ((e->flags & EDGE_CRITICAL)
 869           && !EDGE_INFO (e)->ignore
 870           && (find_group (e->src) != find_group (e->dest)))
 871         {
 872           EDGE_INFO (e)->on_tree = 1;
 873           union_groups (e->src, e->dest);
 874         }
 875     }
 876
 877   /* And now the rest.  */
 878   for (i = 0; i < num_edges; i++)
 879     {
 880       edge e = INDEX_EDGE (el, i);
 881       if (find_group (e->src) != find_group (e->dest)
 882           && !EDGE_INFO (e)->ignore)
 883         {
 884           EDGE_INFO (e)->on_tree = 1;
 885           union_groups (e->src, e->dest);
 886         }
 887     }
 888 }
 889 \f
 890 /* Perform file-level initialization for branch-prob processing.  */
 891
 892 void
 893 init_branch_prob (filename)
 894   const char *filename;
 895 {
 896   long len;
 897   int i;
 898
 899   if (flag_test_coverage)
 900     {
 901       int len = strlen (filename);
 902       char *data_file, *bbg_file_name;
 903
 904       /* Open an output file for the basic block/line number map.  */
 905       data_file = (char *) alloca (len + 4);
 906       strcpy (data_file, filename);
 907       strip_off_ending (data_file, len);
 908       strcat (data_file, ".bb");
 909       if ((bb_file = fopen (data_file, "wb")) == 0)
 910         pfatal_with_name (data_file);
 911
 912       /* Open an output file for the program flow graph.  */
 913       bbg_file_name = (char *) alloca (len + 5);
 914       strcpy (bbg_file_name, filename);
 915       strip_off_ending (bbg_file_name, len);
 916       strcat (bbg_file_name, ".bbg");
 917       if ((bbg_file = fopen (bbg_file_name, "wb")) == 0)
 918         pfatal_with_name (bbg_file_name);
 919
 920       /* Initialize to zero, to ensure that the first file name will be
 921          written to the .bb file.  */
 922       last_bb_file_name = 0;
 923     }
 924
 925   if (flag_branch_probabilities)
 926     {
 927       char *da_file_name;
 928
 929       len = strlen (filename);
 930       da_file_name = (char *) alloca (len + 4);
 931       strcpy (da_file_name, filename);
 932       strip_off_ending (da_file_name, len);
 933       strcat (da_file_name, ".da");
 934       if ((da_file = fopen (da_file_name, "rb")) == 0)
 935         warning ("file %s not found, execution counts assumed to be zero.",
 936                  da_file_name);
 937
 938       /* The first word in the .da file gives the number of instrumented
 939          edges, which is not needed for our purposes.  */
 940
 941       if (da_file)
 942         __read_long (&len, da_file, 8);
 943     }
 944
 945   if (profile_arc_flag)
 946     init_edge_profiler ();
 947
 948   total_num_blocks = 0;
 949   total_num_edges = 0;
 950   total_num_edges_instrumented = 0;
 951   total_num_blocks_created = 0;
 952   total_num_passes = 0;
 953   total_num_times_called = 0;
 954   total_num_branches = 0;
 955   total_num_never_executed = 0;
 956   for (i = 0; i < 20; i++)
 957     total_hist_br_prob[i] = 0;
 958 }
 959
 960 /* Performs file-level cleanup after branch-prob processing
 961    is completed.  */
 962
 963 void
 964 end_branch_prob ()
 965 {
 966   if (flag_test_coverage)
 967     {
 968       fclose (bb_file);
 969       fclose (bbg_file);
 970     }
 971
 972   if (flag_branch_probabilities)
 973     {
 974       if (da_file)
 975         {
 976           long temp;
 977           /* This seems slightly dangerous, as it presumes the EOF
 978              flag will not be set until an attempt is made to read
 979              past the end of the file. */
 980           if (feof (da_file))
 981             warning (".da file contents exhausted too early\n");
 982           /* Should be at end of file now.  */
 983           if (__read_long (&temp, da_file, 8) == 0)
 984             warning (".da file contents not exhausted\n");
 985           fclose (da_file);
 986         }
 987     }
 988
 989   if (rtl_dump_file)
 990     {
 991       fprintf (rtl_dump_file, "\n");
 992       fprintf (rtl_dump_file, "Total number of blocks: %d\n",
 993                total_num_blocks);
 994       fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
 995       fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
 996                total_num_edges_instrumented);
 997       fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
 998                total_num_blocks_created);
 999       fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
1000                total_num_passes);
1001       if (total_num_times_called != 0)
1002         fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
1003                  (total_num_passes + (total_num_times_called  >> 1))
1004                  / total_num_times_called);
1005       fprintf (rtl_dump_file, "Total number of branches: %d\n",
1006                total_num_branches);
1007       fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
1008                total_num_never_executed);
1009       if (total_num_branches)
1010         {
1011           int i;
1012
1013           for (i = 0; i < 10; i++)
1014             fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
1015                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1016                      / total_num_branches, 5*i, 5*i+5);
1017         }
1018     }
1019 }
1020 \f
1021 /* The label used by the edge profiling code.  */
1022
1023 static rtx profiler_label;
1024
1025 /* Initialize the profiler_label.  */
1026
1027 static void
1028 init_edge_profiler ()
1029 {
1030   /* Generate and save a copy of this so it can be shared.  */
1031   char *name = ggc_alloc_string (NULL, 20);
1032   ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 2);
1033   profiler_label = gen_rtx_SYMBOL_REF (Pmode, name);
1034   ggc_add_rtx_root (&profiler_label, 1);
1035 }
1036
1037 /* Output instructions as RTL to increment the edge execution count.  */
1038
1039 static rtx
1040 gen_edge_profiler (edgeno)
1041      int edgeno;
1042 {
1043   enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0);
1044   rtx mem_ref, tmp;
1045   rtx sequence;
1046
1047   start_sequence ();
1048
1049   tmp = force_reg (Pmode, profiler_label);
1050   tmp = plus_constant (tmp, LONG_TYPE_SIZE / BITS_PER_UNIT * edgeno);
1051   mem_ref = validize_mem (gen_rtx_MEM (mode, tmp));
1052
1053   tmp = expand_binop (mode, add_optab, mem_ref, const1_rtx,
1054                       mem_ref, 0, OPTAB_WIDEN);
1055
1056   if (tmp != mem_ref)
1057     emit_move_insn (copy_rtx (mem_ref), tmp);
1058
1059   sequence = gen_sequence ();
1060   end_sequence ();
1061   return sequence;
1062 }
1063
1064 /* Output code for a constructor that will invoke __bb_init_func, if
1065    this has not already been done. */
1066
1067 void
1068 output_func_start_profiler ()
1069 {
1070   tree fnname, fndecl;
1071   char *name, *cfnname;
1072   rtx table_address;
1073   enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0);
1074   int save_flag_inline_functions = flag_inline_functions;
1075   int save_flag_test_coverage = flag_test_coverage;
1076   int save_profile_arc_flag = profile_arc_flag;
1077   int save_flag_branch_probabilities = flag_branch_probabilities;
1078
1079   /* It's either already been output, or we don't need it because we're
1080      not doing profile-edges. */
1081   if (! need_func_profiler)
1082     return;
1083
1084   need_func_profiler = 0;
1085
1086   /* Synthesize a constructor function to invoke __bb_init_func with a
1087      pointer to this object file's profile block. */
1088
1089   /* Try and make a unique name given the "file function name".
1090
1091      And no, I don't like this either. */
1092
1093   fnname = get_file_function_name ('I');
1094   cfnname = IDENTIFIER_POINTER (fnname);
1095   name = xmalloc (strlen (cfnname) + 5);
1096   sprintf (name, "%sGCOV",cfnname);
1097   fnname = get_identifier (name);
1098   free (name);
1099
1100   fndecl = build_decl (FUNCTION_DECL, fnname,
1101                        build_function_type (void_type_node, NULL_TREE));
1102   DECL_EXTERNAL (fndecl) = 0;
1103
1104 #if defined(ASM_OUTPUT_CONSTRUCTOR) && defined(ASM_OUTPUT_DESTRUCTOR)
1105   /* It can be a static function as long as collect2 does not have
1106      to scan the object file to find its ctor/dtor routine.  */
1107   TREE_PUBLIC (fndecl) = 0;
1108 #else
1109   TREE_PUBLIC (fndecl) = 1;
1110 #endif
1111
1112   DECL_ASSEMBLER_NAME (fndecl) = fnname;
1113   DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1114
1115   fndecl = pushdecl (fndecl);
1116   rest_of_decl_compilation (fndecl, 0, 1, 0);
1117   announce_function (fndecl);
1118   current_function_decl = fndecl;
1119   DECL_INITIAL (fndecl) = error_mark_node;
1120   temporary_allocation ();
1121   make_function_rtl (fndecl);
1122   init_function_start (fndecl, input_filename, lineno);
1123   pushlevel (0);
1124   expand_function_start (fndecl, 0);
1125
1126   /* Actually generate the code to call __bb_init_func. */
1127   name = ggc_alloc_string (NULL, 20);
1128   ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 0);
1129   table_address = force_reg (Pmode, gen_rtx_SYMBOL_REF (Pmode, name));
1130   emit_library_call (gen_rtx_SYMBOL_REF
1131                      (Pmode, ggc_alloc_string ("__bb_init_func", 14)), 0,
1132                      mode, 1, table_address, Pmode);
1133
1134   expand_function_end (input_filename, lineno, 0);
1135   poplevel (1, 0, 1);
1136
1137   /* Since fndecl isn't in the list of globals, it would never be emitted
1138      when it's considered to be 'safe' for inlining, so turn off
1139      flag_inline_functions.  */
1140   flag_inline_functions = 0;
1141
1142   /* Don't instrument the function that turns on instrumentation.  Which
1143      is also handy since we'd get silly warnings about not consuming all
1144      of our da_file input.  */
1145   flag_test_coverage = 0;
1146   profile_arc_flag = 0;
1147   flag_branch_probabilities = 0;
1148
1149   rest_of_compilation (fndecl);
1150
1151   /* Reset flag_inline_functions to its original value.  */
1152   flag_inline_functions = save_flag_inline_functions;
1153   flag_test_coverage = save_flag_test_coverage;
1154   profile_arc_flag = save_profile_arc_flag;
1155   flag_branch_probabilities = save_flag_branch_probabilities;
1156
1157   if (! quiet_flag)
1158     fflush (asm_out_file);
1159   current_function_decl = NULL_TREE;
1160
1161   assemble_constructor (IDENTIFIER_POINTER (DECL_NAME (fndecl)));
1162 }