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