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   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       gcov_type total;
 421       rtx note;
 422
 423       total = bb->count;
 424       if (total)
 425         for (e = bb->succ; e; e = e->succ_next)
 426           {
 427               e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total;
 428               if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
 429                 {
 430                   error ("Corrupted profile info: prob for %d-%d thought to be %d\n",
 431                          e->src->index, e->dest->index, e->probability);
 432                   e->probability = REG_BR_PROB_BASE / 2;
 433                 }
 434           }
 435       if (any_condjump_p (bb->end)
 436           && bb->succ->succ_next)
 437         {
 438           int prob;
 439           edge e;
 440
 441           if (total == 0)
 442             prob = -1;
 443           else
 444           if (total == -1)
 445             num_never_executed++;
 446           else
 447             {
 448               int index;
 449
 450               /* Find the branch edge.  It is possible that we do have fake
 451                  edges here.  */
 452               for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU);
 453                    e = e->succ_next)
 454                 continue; /* Loop body has been intentionally left blank.  */
 455
 456               prob = e->probability;
 457               index = prob * 20 / REG_BR_PROB_BASE;
 458
 459               if (index == 20)
 460                 index = 19;
 461               hist_br_prob[index]++;
 462
 463               note = find_reg_note (bb->end, REG_BR_PROB, 0);
 464               /* There may be already note put by some other pass, such
 465                  as builtin_expect expander.  */
 466               if (note)
 467                 XEXP (note, 0) = GEN_INT (prob);
 468               else
 469                 REG_NOTES (bb->end)
 470                   = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 471                                        REG_NOTES (bb->end));
 472             }
 473           num_branches++;
 474
 475         }
 476     }
 477
 478   if (rtl_dump_file)
 479     {
 480       fprintf (rtl_dump_file, "%d branches\n", num_branches);
 481       fprintf (rtl_dump_file, "%d branches never executed\n",
 482                num_never_executed);
 483       if (num_branches)
 484         for (i = 0; i < 10; i++)
 485           fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
 486                    (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
 487                    5 * i, 5 * i + 5);
 488
 489       total_num_branches += num_branches;
 490       total_num_never_executed += num_never_executed;
 491       for (i = 0; i < 20; i++)
 492         total_hist_br_prob[i] += hist_br_prob[i];
 493
 494       fputc ('\n', rtl_dump_file);
 495       fputc ('\n', rtl_dump_file);
 496     }
 497
 498   free (bb_infos);
 499 }
 500
 501 /* Instrument and/or analyze program behavior based on program flow graph.
 502    In either case, this function builds a flow graph for the function being
 503    compiled.  The flow graph is stored in BB_GRAPH.
 504
 505    When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
 506    the flow graph that are needed to reconstruct the dynamic behavior of the
 507    flow graph.
 508
 509    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
 510    information from a data file containing edge count information from previous
 511    executions of the function being compiled.  In this case, the flow graph is
 512    annotated with actual execution counts, which are later propagated into the
 513    rtl for optimization purposes.
 514
 515    Main entry point of this file.  */
 516
 517 void
 518 branch_prob ()
 519 {
 520   int i;
 521   int num_edges, ignored_edges;
 522   struct edge_info *edge_infos;
 523   struct edge_list *el;
 524
 525   /* Start of a function.  */
 526   if (flag_test_coverage)
 527     output_gcov_string (current_function_name, (long) -2);
 528
 529   total_num_times_called++;
 530
 531   /* We can't handle cyclic regions constructed using abnormal edges.
 532      To avoid these we replace every source of abnormal edge by a fake
 533      edge from entry node and every destination by fake edge to exit.
 534      This keeps graph acyclic and our calculation exact for all normal
 535      edges except for exit and entrance ones.
 536
 537      We also add fake exit edges for each call and asm statement in the
 538      basic, since it may not return.  */
 539
 540   for (i = 0; i < n_basic_blocks ; i++)
 541     {
 542       rtx insn;
 543       int need_exit_edge = 0, need_entry_edge = 0;
 544       int have_exit_edge = 0, have_entry_edge = 0;
 545       basic_block bb = BASIC_BLOCK (i);
 546       edge e;
 547
 548       for (e = bb->succ; e; e = e->succ_next)
 549         {
 550           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 551                && e->dest != EXIT_BLOCK_PTR)
 552             need_exit_edge = 1;
 553           if (e->dest == EXIT_BLOCK_PTR)
 554             have_exit_edge = 1;
 555         }
 556       for (e = bb->pred; e; e = e->pred_next)
 557         {
 558           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 559                && e->src != ENTRY_BLOCK_PTR)
 560             need_entry_edge = 1;
 561           if (e->src == ENTRY_BLOCK_PTR)
 562             have_entry_edge = 1;
 563         }
 564
 565       /* ??? Not strictly needed unless flag_test_coverage, but adding
 566          them anyway keeps the .da file consistent.  */
 567       /* ??? Currently inexact for basic blocks with multiple calls.
 568          We need to split blocks here.  */
 569       for (insn = bb->head;
 570            insn != NEXT_INSN (bb->end);
 571            insn = NEXT_INSN (insn))
 572         {
 573           rtx set;
 574           if (GET_CODE (insn) == CALL_INSN && !CONST_CALL_P (insn))
 575             need_exit_edge = 1;
 576           else if (GET_CODE (insn) == INSN)
 577             {
 578               set = PATTERN (insn);
 579               if (GET_CODE (set) == PARALLEL)
 580                 set = XVECEXP (set, 0, 0);
 581               if ((GET_CODE (set) == ASM_OPERANDS && MEM_VOLATILE_P (set))
 582                   || GET_CODE (set) == ASM_INPUT)
 583                 need_exit_edge = 1;
 584             }
 585         }
 586
 587       if (need_exit_edge && !have_exit_edge)
 588         {
 589           if (rtl_dump_file)
 590             fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n",
 591                      bb->index);
 592           make_edge (NULL, bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 593         }
 594       if (need_entry_edge && !have_entry_edge)
 595         {
 596           if (rtl_dump_file)
 597             fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n",
 598                      bb->index);
 599           make_edge (NULL, ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
 600         }
 601     }
 602
 603   el = create_edge_list ();
 604   num_edges = NUM_EDGES (el);
 605   edge_infos = (struct edge_info *)
 606     xcalloc (num_edges, sizeof (struct edge_info));
 607
 608   ignored_edges = 0;
 609   for (i = 0 ; i < num_edges ; i++)
 610     {
 611       edge e = INDEX_EDGE (el, i);
 612       e->count = 0;
 613       e->aux = &edge_infos[i];
 614
 615       /* Mark edges we've replaced by fake edges above as ignored.  */
 616       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 617           && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
 618         {
 619           EDGE_INFO (e)->ignore = 1;
 620           ignored_edges++;
 621         }
 622     }
 623
 624 #ifdef ENABLE_CHECKING
 625   verify_flow_info ();
 626 #endif
 627
 628   /* Output line number information about each basic block for
 629      GCOV utility.  */
 630   if (flag_test_coverage)
 631     {
 632       int i = 0;
 633       for (i = 0 ; i < n_basic_blocks; i++)
 634         {
 635           basic_block bb = BASIC_BLOCK (i);
 636           rtx insn = bb->head;
 637           static int ignore_next_note = 0;
 638
 639           /* We are looking for line number notes.  Search backward before
 640              basic block to find correct ones.  */
 641           insn = prev_nonnote_insn (insn);
 642           if (!insn)
 643             insn = get_insns ();
 644           else
 645             insn = NEXT_INSN (insn);
 646
 647           /* Output a zero to the .bb file to indicate that a new
 648              block list is starting.  */
 649           __write_long (0, bb_file, 4);
 650
 651           while (insn != bb->end)
 652             {
 653               if (GET_CODE (insn) == NOTE)
 654                 {
 655                   /* Must ignore the line number notes that immediately
 656                      follow the end of an inline function to avoid counting
 657                      it twice.  There is a note before the call, and one
 658                      after the call.  */
 659                   if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER)
 660                     ignore_next_note = 1;
 661                   else if (NOTE_LINE_NUMBER (insn) > 0)
 662                     {
 663                       if (ignore_next_note)
 664                         ignore_next_note = 0;
 665                       else
 666                         {
 667                           /* If this is a new source file, then output the
 668                              file's name to the .bb file.  */
 669                           if (! last_bb_file_name
 670                               || strcmp (NOTE_SOURCE_FILE (insn),
 671                                          last_bb_file_name))
 672                             {
 673                               if (last_bb_file_name)
 674                                 free (last_bb_file_name);
 675                               last_bb_file_name
 676                                 = xstrdup (NOTE_SOURCE_FILE (insn));
 677                               output_gcov_string (NOTE_SOURCE_FILE (insn),
 678                                                   (long)-1);
 679                             }
 680                           /* Output the line number to the .bb file.  Must be
 681                              done after the output_bb_profile_data() call, and
 682                              after the file name is written, to ensure that it
 683                              is correctly handled by gcov.  */
 684                           __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
 685                         }
 686                     }
 687                 }
 688               insn = NEXT_INSN (insn);
 689             }
 690         }
 691       __write_long (0, bb_file, 4);
 692     }
 693
 694   /* Create spanning tree from basic block graph, mark each edge that is
 695      on the spanning tree.  We insert as many abnormal and critical edges
 696      as possible to minimize number of edge splits necesary. */
 697
 698   find_spanning_tree (el);
 699
 700   /* Fake edges that are not on the tree will not be instrumented, so
 701      mark them ignored. */
 702   for (i = 0; i < num_edges; i++)
 703     {
 704       edge e = INDEX_EDGE (el, i);
 705       struct edge_info *inf = EDGE_INFO (e);
 706       if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree)
 707         {
 708           inf->ignore = 1;
 709           ignored_edges++;
 710         }
 711     }
 712
 713   total_num_blocks += n_basic_blocks + 2;
 714   if (rtl_dump_file)
 715     fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
 716
 717   total_num_edges += num_edges;
 718   if (rtl_dump_file)
 719     fprintf (rtl_dump_file, "%d edges\n", num_edges);
 720
 721   total_num_edges_ignored += ignored_edges;
 722   if (rtl_dump_file)
 723     fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges);
 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 - ignored_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_FAKE)
 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_ignored = 0;
 954   total_num_edges_instrumented = 0;
 955   total_num_blocks_created = 0;
 956   total_num_passes = 0;
 957   total_num_times_called = 0;
 958   total_num_branches = 0;
 959   total_num_never_executed = 0;
 960   for (i = 0; i < 20; i++)
 961     total_hist_br_prob[i] = 0;
 962 }
 963
 964 /* Performs file-level cleanup after branch-prob processing
 965    is completed.  */
 966
 967 void
 968 end_branch_prob ()
 969 {
 970   if (flag_test_coverage)
 971     {
 972       fclose (bb_file);
 973       fclose (bbg_file);
 974     }
 975
 976   if (flag_branch_probabilities)
 977     {
 978       if (da_file)
 979         {
 980           long temp;
 981           /* This seems slightly dangerous, as it presumes the EOF
 982              flag will not be set until an attempt is made to read
 983              past the end of the file. */
 984           if (feof (da_file))
 985             error (".da file contents exhausted too early");
 986           /* Should be at end of file now.  */
 987           if (__read_long (&temp, da_file, 8) == 0)
 988             error (".da file contents not exhausted");
 989           fclose (da_file);
 990         }
 991     }
 992
 993   if (rtl_dump_file)
 994     {
 995       fprintf (rtl_dump_file, "\n");
 996       fprintf (rtl_dump_file, "Total number of blocks: %d\n",
 997                total_num_blocks);
 998       fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
 999       fprintf (rtl_dump_file, "Total number of ignored edges: %d\n",
1000                total_num_edges_ignored);
1001       fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
1002                total_num_edges_instrumented);
1003       fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
1004                total_num_blocks_created);
1005       fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
1006                total_num_passes);
1007       if (total_num_times_called != 0)
1008         fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
1009                  (total_num_passes + (total_num_times_called  >> 1))
1010                  / total_num_times_called);
1011       fprintf (rtl_dump_file, "Total number of branches: %d\n",
1012                total_num_branches);
1013       fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
1014                total_num_never_executed);
1015       if (total_num_branches)
1016         {
1017           int i;
1018
1019           for (i = 0; i < 10; i++)
1020             fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
1021                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1022                      / total_num_branches, 5*i, 5*i+5);
1023         }
1024     }
1025 }
1026 \f
1027 /* The label used by the edge profiling code.  */
1028
1029 static rtx profiler_label;
1030
1031 /* Initialize the profiler_label.  */
1032
1033 static void
1034 init_edge_profiler ()
1035 {
1036   /* Generate and save a copy of this so it can be shared.  */
1037   char buf[20];
1038   ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2);
1039   profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf));
1040   ggc_add_rtx_root (&profiler_label, 1);
1041 }
1042
1043 /* Output instructions as RTL to increment the edge execution count.  */
1044
1045 static rtx
1046 gen_edge_profiler (edgeno)
1047      int edgeno;
1048 {
1049   enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1050   rtx mem_ref, tmp;
1051   rtx sequence;
1052
1053   start_sequence ();
1054
1055   tmp = force_reg (Pmode, profiler_label);
1056   tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno);
1057   mem_ref = validize_mem (gen_rtx_MEM (mode, tmp));
1058
1059   tmp = expand_binop (mode, add_optab, mem_ref, const1_rtx,
1060                       mem_ref, 0, OPTAB_WIDEN);
1061
1062   if (tmp != mem_ref)
1063     emit_move_insn (copy_rtx (mem_ref), tmp);
1064
1065   sequence = gen_sequence ();
1066   end_sequence ();
1067   return sequence;
1068 }
1069
1070 /* Output code for a constructor that will invoke __bb_init_func, if
1071    this has not already been done. */
1072
1073 void
1074 output_func_start_profiler ()
1075 {
1076   tree fnname, fndecl;
1077   char *name;
1078   char buf[20];
1079   const char *cfnname;
1080   rtx table_address;
1081   enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1082   int save_flag_inline_functions = flag_inline_functions;
1083   int save_flag_test_coverage = flag_test_coverage;
1084   int save_profile_arc_flag = profile_arc_flag;
1085   int save_flag_branch_probabilities = flag_branch_probabilities;
1086
1087   /* It's either already been output, or we don't need it because we're
1088      not doing profile-edges. */
1089   if (! need_func_profiler)
1090     return;
1091
1092   need_func_profiler = 0;
1093
1094   /* Synthesize a constructor function to invoke __bb_init_func with a
1095      pointer to this object file's profile block. */
1096
1097   /* Try and make a unique name given the "file function name".
1098
1099      And no, I don't like this either. */
1100
1101   fnname = get_file_function_name ('I');
1102   cfnname = IDENTIFIER_POINTER (fnname);
1103   name = concat (cfnname, "GCOV", NULL);
1104   fnname = get_identifier (name);
1105   free (name);
1106
1107   fndecl = build_decl (FUNCTION_DECL, fnname,
1108                        build_function_type (void_type_node, NULL_TREE));
1109   DECL_EXTERNAL (fndecl) = 0;
1110
1111 #if defined(ASM_OUTPUT_CONSTRUCTOR) && defined(ASM_OUTPUT_DESTRUCTOR)
1112   /* It can be a static function as long as collect2 does not have
1113      to scan the object file to find its ctor/dtor routine.  */
1114   TREE_PUBLIC (fndecl) = 0;
1115 #else
1116   TREE_PUBLIC (fndecl) = 1;
1117 #endif
1118
1119   DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1120
1121   fndecl = pushdecl (fndecl);
1122   rest_of_decl_compilation (fndecl, 0, 1, 0);
1123   announce_function (fndecl);
1124   current_function_decl = fndecl;
1125   DECL_INITIAL (fndecl) = error_mark_node;
1126   make_decl_rtl (fndecl, NULL);
1127   init_function_start (fndecl, input_filename, lineno);
1128   pushlevel (0);
1129   expand_function_start (fndecl, 0);
1130
1131   /* Actually generate the code to call __bb_init_func. */
1132   ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 0);
1133   table_address = force_reg (Pmode,
1134                              gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf)));
1135   emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), 0,
1136                      mode, 1, table_address, Pmode);
1137
1138   expand_function_end (input_filename, lineno, 0);
1139   poplevel (1, 0, 1);
1140
1141   /* Since fndecl isn't in the list of globals, it would never be emitted
1142      when it's considered to be 'safe' for inlining, so turn off
1143      flag_inline_functions.  */
1144   flag_inline_functions = 0;
1145
1146   /* Don't instrument the function that turns on instrumentation.  Which
1147      is also handy since we'd get silly warnings about not consuming all
1148      of our da_file input.  */
1149   flag_test_coverage = 0;
1150   profile_arc_flag = 0;
1151   flag_branch_probabilities = 0;
1152
1153   rest_of_compilation (fndecl);
1154
1155   /* Reset flag_inline_functions to its original value.  */
1156   flag_inline_functions = save_flag_inline_functions;
1157   flag_test_coverage = save_flag_test_coverage;
1158   profile_arc_flag = save_profile_arc_flag;
1159   flag_branch_probabilities = save_flag_branch_probabilities;
1160
1161   if (! quiet_flag)
1162     fflush (asm_out_file);
1163   current_function_decl = NULL_TREE;
1164
1165   assemble_constructor (IDENTIFIER_POINTER (DECL_NAME (fndecl)));
1166 }