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