gcc/profile.c

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