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