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