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