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   flow_call_edges_add (NULL);
 532
 533   /* We can't handle cyclic regions constructed using abnormal edges.
 534      To avoid these we replace every source of abnormal edge by a fake
 535      edge from entry node and every destination by fake edge to exit.
 536      This keeps graph acyclic and our calculation exact for all normal
 537      edges except for exit and entrance ones.
 538
 539      We also add fake exit edges for each call and asm statement in the
 540      basic, since it may not return.  */
 541
 542   for (i = 0; i < n_basic_blocks ; i++)
 543     {
 544       rtx insn;
 545       int need_exit_edge = 0, need_entry_edge = 0;
 546       int have_exit_edge = 0, have_entry_edge = 0;
 547       basic_block bb = BASIC_BLOCK (i);
 548       edge e;
 549
 550       for (e = bb->succ; e; e = e->succ_next)
 551         {
 552           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 553                && e->dest != EXIT_BLOCK_PTR)
 554             need_exit_edge = 1;
 555           if (e->dest == EXIT_BLOCK_PTR)
 556             have_exit_edge = 1;
 557         }
 558       for (e = bb->pred; e; e = e->pred_next)
 559         {
 560           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 561                && e->src != ENTRY_BLOCK_PTR)
 562             need_entry_edge = 1;
 563           if (e->src == ENTRY_BLOCK_PTR)
 564             have_entry_edge = 1;
 565         }
 566
 567       if (need_exit_edge && !have_exit_edge)
 568         {
 569           if (rtl_dump_file)
 570             fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n",
 571                      bb->index);
 572           make_edge (NULL, bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 573         }
 574       if (need_entry_edge && !have_entry_edge)
 575         {
 576           if (rtl_dump_file)
 577             fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n",
 578                      bb->index);
 579           make_edge (NULL, ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
 580         }
 581     }
 582
 583   el = create_edge_list ();
 584   num_edges = NUM_EDGES (el);
 585   edge_infos = (struct edge_info *)
 586     xcalloc (num_edges, sizeof (struct edge_info));
 587
 588   ignored_edges = 0;
 589   for (i = 0 ; i < num_edges ; i++)
 590     {
 591       edge e = INDEX_EDGE (el, i);
 592       e->count = 0;
 593       e->aux = &edge_infos[i];
 594
 595       /* Mark edges we've replaced by fake edges above as ignored.  */
 596       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 597           && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
 598         {
 599           EDGE_INFO (e)->ignore = 1;
 600           ignored_edges++;
 601         }
 602     }
 603
 604 #ifdef ENABLE_CHECKING
 605   verify_flow_info ();
 606 #endif
 607
 608   /* Output line number information about each basic block for
 609      GCOV utility.  */
 610   if (flag_test_coverage)
 611     {
 612       int i = 0;
 613       for (i = 0 ; i < n_basic_blocks; i++)
 614         {
 615           basic_block bb = BASIC_BLOCK (i);
 616           rtx insn = bb->head;
 617           static int ignore_next_note = 0;
 618
 619           /* We are looking for line number notes.  Search backward before
 620              basic block to find correct ones.  */
 621           insn = prev_nonnote_insn (insn);
 622           if (!insn)
 623             insn = get_insns ();
 624           else
 625             insn = NEXT_INSN (insn);
 626
 627           /* Output a zero to the .bb file to indicate that a new
 628              block list is starting.  */
 629           __write_long (0, bb_file, 4);
 630
 631           while (insn != bb->end)
 632             {
 633               if (GET_CODE (insn) == NOTE)
 634                 {
 635                   /* Must ignore the line number notes that immediately
 636                      follow the end of an inline function to avoid counting
 637                      it twice.  There is a note before the call, and one
 638                      after the call.  */
 639                   if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER)
 640                     ignore_next_note = 1;
 641                   else if (NOTE_LINE_NUMBER (insn) > 0)
 642                     {
 643                       if (ignore_next_note)
 644                         ignore_next_note = 0;
 645                       else
 646                         {
 647                           /* If this is a new source file, then output the
 648                              file's name to the .bb file.  */
 649                           if (! last_bb_file_name
 650                               || strcmp (NOTE_SOURCE_FILE (insn),
 651                                          last_bb_file_name))
 652                             {
 653                               if (last_bb_file_name)
 654                                 free (last_bb_file_name);
 655                               last_bb_file_name
 656                                 = xstrdup (NOTE_SOURCE_FILE (insn));
 657                               output_gcov_string (NOTE_SOURCE_FILE (insn),
 658                                                   (long)-1);
 659                             }
 660                           /* Output the line number to the .bb file.  Must be
 661                              done after the output_bb_profile_data() call, and
 662                              after the file name is written, to ensure that it
 663                              is correctly handled by gcov.  */
 664                           __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
 665                         }
 666                     }
 667                 }
 668               insn = NEXT_INSN (insn);
 669             }
 670         }
 671       __write_long (0, bb_file, 4);
 672     }
 673
 674   /* Create spanning tree from basic block graph, mark each edge that is
 675      on the spanning tree.  We insert as many abnormal and critical edges
 676      as possible to minimize number of edge splits necesary. */
 677
 678   find_spanning_tree (el);
 679
 680   /* Fake edges that are not on the tree will not be instrumented, so
 681      mark them ignored. */
 682   for (i = 0; i < num_edges; i++)
 683     {
 684       edge e = INDEX_EDGE (el, i);
 685       struct edge_info *inf = EDGE_INFO (e);
 686       if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree)
 687         {
 688           inf->ignore = 1;
 689           ignored_edges++;
 690         }
 691     }
 692
 693   total_num_blocks += n_basic_blocks + 2;
 694   if (rtl_dump_file)
 695     fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
 696
 697   total_num_edges += num_edges;
 698   if (rtl_dump_file)
 699     fprintf (rtl_dump_file, "%d edges\n", num_edges);
 700
 701   total_num_edges_ignored += ignored_edges;
 702   if (rtl_dump_file)
 703     fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges);
 704
 705   /* Create a .bbg file from which gcov can reconstruct the basic block
 706      graph.  First output the number of basic blocks, and then for every
 707      edge output the source and target basic block numbers.
 708      NOTE: The format of this file must be compatible with gcov.  */
 709
 710   if (flag_test_coverage)
 711     {
 712       int flag_bits;
 713
 714       /* The plus 2 stands for entry and exit block.  */
 715       __write_long (n_basic_blocks + 2, bbg_file, 4);
 716       __write_long (num_edges - ignored_edges + 1, bbg_file, 4);
 717
 718       for (i = 0; i < n_basic_blocks + 1; i++)
 719         {
 720           basic_block bb = GCOV_INDEX_TO_BB (i);
 721           edge e;
 722           long count = 0;
 723
 724           for (e = bb->succ; e; e = e->succ_next)
 725             if (!EDGE_INFO (e)->ignore)
 726               count++;
 727           __write_long (count, bbg_file, 4);
 728
 729           for (e = bb->succ; e; e = e->succ_next)
 730             {
 731               struct edge_info *i = EDGE_INFO (e);
 732               if (!i->ignore)
 733                 {
 734                   flag_bits = 0;
 735                   if (i->on_tree)
 736                     flag_bits |= 0x1;
 737                   if (e->flags & EDGE_FAKE)
 738                     flag_bits |= 0x2;
 739                   if (e->flags & EDGE_FALLTHRU)
 740                     flag_bits |= 0x4;
 741
 742                   __write_long (BB_TO_GCOV_INDEX (e->dest), bbg_file, 4);
 743                   __write_long (flag_bits, bbg_file, 4);
 744                 }
 745             }
 746         }
 747       /* Emit fake loopback edge for EXIT block to maitain compatibility with
 748          old gcov format.  */
 749       __write_long (1, bbg_file, 4);
 750       __write_long (0, bbg_file, 4);
 751       __write_long (0x1, bbg_file, 4);
 752
 753       /* Emit a -1 to separate the list of all edges from the list of
 754          loop back edges that follows.  */
 755       __write_long (-1, bbg_file, 4);
 756     }
 757
 758   if (flag_branch_probabilities)
 759     compute_branch_probabilities ();
 760
 761   /* For each edge not on the spanning tree, add counting code as rtl.  */
 762
 763   if (profile_arc_flag)
 764     {
 765       instrument_edges (el);
 766       allocate_reg_info (max_reg_num (), FALSE, FALSE);
 767     }
 768
 769   remove_fake_edges ();
 770   /* Re-merge split basic blocks and the mess introduced by
 771      insert_insn_on_edge.  */
 772   cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
 773   if (rtl_dump_file)
 774     dump_flow_info (rtl_dump_file);
 775
 776   free (edge_infos);
 777   free_edge_list (el);
 778 }
 779 \f
 780 /* Union find algorithm implementation for the basic blocks using
 781    aux fields. */
 782
 783 static basic_block
 784 find_group (bb)
 785      basic_block bb;
 786 {
 787   basic_block group = bb, bb1;
 788
 789   while ((basic_block) group->aux != group)
 790     group = (basic_block) group->aux;
 791
 792   /* Compress path.  */
 793   while ((basic_block) bb->aux != group)
 794     {
 795       bb1 = (basic_block) bb->aux;
 796       bb->aux = (void *) group;
 797       bb = bb1;
 798     }
 799   return group;
 800 }
 801
 802 static void
 803 union_groups (bb1, bb2)
 804      basic_block bb1, bb2;
 805 {
 806   basic_block bb1g = find_group (bb1);
 807   basic_block bb2g = find_group (bb2);
 808
 809   /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
 810      this code is unlikely going to be performance problem anyway.  */
 811   if (bb1g == bb2g)
 812     abort ();
 813
 814   bb1g->aux = bb2g;
 815 }
 816 \f
 817 /* This function searches all of the edges in the program flow graph, and puts
 818    as many bad edges as possible onto the spanning tree.  Bad edges include
 819    abnormals edges, which can't be instrumented at the moment.  Since it is
 820    possible for fake edges to form an cycle, we will have to develop some
 821    better way in the future.  Also put critical edges to the tree, since they
 822    are more expensive to instrument.  */
 823
 824 static void
 825 find_spanning_tree (el)
 826      struct edge_list *el;
 827 {
 828   int i;
 829   int num_edges = NUM_EDGES (el);
 830
 831   /* We use aux field for standard union-find algorithm.  */
 832   EXIT_BLOCK_PTR->aux = EXIT_BLOCK_PTR;
 833   ENTRY_BLOCK_PTR->aux = ENTRY_BLOCK_PTR;
 834   for (i = 0; i < n_basic_blocks; i++)
 835     BASIC_BLOCK (i)->aux = BASIC_BLOCK (i);
 836
 837   /* Add fake edge exit to entry we can't instrument.  */
 838   union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
 839
 840   /* First add all abnormal edges to the tree unless they form an cycle.  */
 841   for (i = 0; i < num_edges; i++)
 842     {
 843       edge e = INDEX_EDGE (el, i);
 844       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
 845           && !EDGE_INFO (e)->ignore
 846           && (find_group (e->src) != find_group (e->dest)))
 847         {
 848           EDGE_INFO (e)->on_tree = 1;
 849           union_groups (e->src, e->dest);
 850         }
 851     }
 852
 853   /* Now insert all critical edges to the tree unless they form an cycle.  */
 854   for (i = 0; i < num_edges; i++)
 855     {
 856       edge e = INDEX_EDGE (el, i);
 857       if ((e->flags & EDGE_CRITICAL)
 858           && !EDGE_INFO (e)->ignore
 859           && (find_group (e->src) != find_group (e->dest)))
 860         {
 861           EDGE_INFO (e)->on_tree = 1;
 862           union_groups (e->src, e->dest);
 863         }
 864     }
 865
 866   /* And now the rest.  */
 867   for (i = 0; i < num_edges; i++)
 868     {
 869       edge e = INDEX_EDGE (el, i);
 870       if (find_group (e->src) != find_group (e->dest)
 871           && !EDGE_INFO (e)->ignore)
 872         {
 873           EDGE_INFO (e)->on_tree = 1;
 874           union_groups (e->src, e->dest);
 875         }
 876     }
 877 }
 878 \f
 879 /* Perform file-level initialization for branch-prob processing.  */
 880
 881 void
 882 init_branch_prob (filename)
 883   const char *filename;
 884 {
 885   long len;
 886   int i;
 887
 888   if (flag_test_coverage)
 889     {
 890       int len = strlen (filename);
 891       char *data_file, *bbg_file_name;
 892
 893       /* Open an output file for the basic block/line number map.  */
 894       data_file = (char *) alloca (len + 4);
 895       strcpy (data_file, filename);
 896       strip_off_ending (data_file, len);
 897       strcat (data_file, ".bb");
 898       if ((bb_file = fopen (data_file, "wb")) == 0)
 899         fatal_io_error ("can't open %s", data_file);
 900
 901       /* Open an output file for the program flow graph.  */
 902       bbg_file_name = (char *) alloca (len + 5);
 903       strcpy (bbg_file_name, filename);
 904       strip_off_ending (bbg_file_name, len);
 905       strcat (bbg_file_name, ".bbg");
 906       if ((bbg_file = fopen (bbg_file_name, "wb")) == 0)
 907         fatal_io_error ("can't open %s", bbg_file_name);
 908
 909       /* Initialize to zero, to ensure that the first file name will be
 910          written to the .bb file.  */
 911       last_bb_file_name = 0;
 912     }
 913
 914   if (flag_branch_probabilities)
 915     {
 916       char *da_file_name;
 917
 918       len = strlen (filename);
 919       da_file_name = (char *) alloca (len + 4);
 920       strcpy (da_file_name, filename);
 921       strip_off_ending (da_file_name, len);
 922       strcat (da_file_name, ".da");
 923       if ((da_file = fopen (da_file_name, "rb")) == 0)
 924         warning ("file %s not found, execution counts assumed to be zero.",
 925                  da_file_name);
 926
 927       /* The first word in the .da file gives the number of instrumented
 928          edges, which is not needed for our purposes.  */
 929
 930       if (da_file)
 931         __read_long (&len, da_file, 8);
 932     }
 933
 934   if (profile_arc_flag)
 935     init_edge_profiler ();
 936
 937   total_num_blocks = 0;
 938   total_num_edges = 0;
 939   total_num_edges_ignored = 0;
 940   total_num_edges_instrumented = 0;
 941   total_num_blocks_created = 0;
 942   total_num_passes = 0;
 943   total_num_times_called = 0;
 944   total_num_branches = 0;
 945   total_num_never_executed = 0;
 946   for (i = 0; i < 20; i++)
 947     total_hist_br_prob[i] = 0;
 948 }
 949
 950 /* Performs file-level cleanup after branch-prob processing
 951    is completed.  */
 952
 953 void
 954 end_branch_prob ()
 955 {
 956   if (flag_test_coverage)
 957     {
 958       fclose (bb_file);
 959       fclose (bbg_file);
 960     }
 961
 962   if (flag_branch_probabilities)
 963     {
 964       if (da_file)
 965         {
 966           long temp;
 967           /* This seems slightly dangerous, as it presumes the EOF
 968              flag will not be set until an attempt is made to read
 969              past the end of the file. */
 970           if (feof (da_file))
 971             error (".da file contents exhausted too early");
 972           /* Should be at end of file now.  */
 973           if (__read_long (&temp, da_file, 8) == 0)
 974             error (".da file contents not exhausted");
 975           fclose (da_file);
 976         }
 977     }
 978
 979   if (rtl_dump_file)
 980     {
 981       fprintf (rtl_dump_file, "\n");
 982       fprintf (rtl_dump_file, "Total number of blocks: %d\n",
 983                total_num_blocks);
 984       fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
 985       fprintf (rtl_dump_file, "Total number of ignored edges: %d\n",
 986                total_num_edges_ignored);
 987       fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
 988                total_num_edges_instrumented);
 989       fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
 990                total_num_blocks_created);
 991       fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
 992                total_num_passes);
 993       if (total_num_times_called != 0)
 994         fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
 995                  (total_num_passes + (total_num_times_called  >> 1))
 996                  / total_num_times_called);
 997       fprintf (rtl_dump_file, "Total number of branches: %d\n",
 998                total_num_branches);
 999       fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
1000                total_num_never_executed);
1001       if (total_num_branches)
1002         {
1003           int i;
1004
1005           for (i = 0; i < 10; i++)
1006             fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
1007                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1008                      / total_num_branches, 5*i, 5*i+5);
1009         }
1010     }
1011 }
1012 \f
1013 /* The label used by the edge profiling code.  */
1014
1015 static rtx profiler_label;
1016
1017 /* Initialize the profiler_label.  */
1018
1019 static void
1020 init_edge_profiler ()
1021 {
1022   /* Generate and save a copy of this so it can be shared.  */
1023   char buf[20];
1024   ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2);
1025   profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf));
1026   ggc_add_rtx_root (&profiler_label, 1);
1027 }
1028
1029 /* Output instructions as RTL to increment the edge execution count.  */
1030
1031 static rtx
1032 gen_edge_profiler (edgeno)
1033      int edgeno;
1034 {
1035   enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1036   rtx mem_ref, tmp;
1037   rtx sequence;
1038
1039   start_sequence ();
1040
1041   tmp = force_reg (Pmode, profiler_label);
1042   tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno);
1043   mem_ref = validize_mem (gen_rtx_MEM (mode, tmp));
1044
1045   tmp = expand_binop (mode, add_optab, mem_ref, const1_rtx,
1046                       mem_ref, 0, OPTAB_WIDEN);
1047
1048   if (tmp != mem_ref)
1049     emit_move_insn (copy_rtx (mem_ref), tmp);
1050
1051   sequence = gen_sequence ();
1052   end_sequence ();
1053   return sequence;
1054 }
1055
1056 /* Output code for a constructor that will invoke __bb_init_func, if
1057    this has not already been done. */
1058
1059 void
1060 output_func_start_profiler ()
1061 {
1062   tree fnname, fndecl;
1063   char *name;
1064   char buf[20];
1065   const char *cfnname;
1066   rtx table_address;
1067   enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
1068   int save_flag_inline_functions = flag_inline_functions;
1069   int save_flag_test_coverage = flag_test_coverage;
1070   int save_profile_arc_flag = profile_arc_flag;
1071   int save_flag_branch_probabilities = flag_branch_probabilities;
1072
1073   /* It's either already been output, or we don't need it because we're
1074      not doing profile-edges. */
1075   if (! need_func_profiler)
1076     return;
1077
1078   need_func_profiler = 0;
1079
1080   /* Synthesize a constructor function to invoke __bb_init_func with a
1081      pointer to this object file's profile block. */
1082
1083   /* Try and make a unique name given the "file function name".
1084
1085      And no, I don't like this either. */
1086
1087   fnname = get_file_function_name ('I');
1088   cfnname = IDENTIFIER_POINTER (fnname);
1089   name = concat (cfnname, "GCOV", NULL);
1090   fnname = get_identifier (name);
1091   free (name);
1092
1093   fndecl = build_decl (FUNCTION_DECL, fnname,
1094                        build_function_type (void_type_node, NULL_TREE));
1095   DECL_EXTERNAL (fndecl) = 0;
1096
1097 #if defined(ASM_OUTPUT_CONSTRUCTOR) && defined(ASM_OUTPUT_DESTRUCTOR)
1098   /* It can be a static function as long as collect2 does not have
1099      to scan the object file to find its ctor/dtor routine.  */
1100   TREE_PUBLIC (fndecl) = 0;
1101 #else
1102   TREE_PUBLIC (fndecl) = 1;
1103 #endif
1104
1105   DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1106
1107   fndecl = pushdecl (fndecl);
1108   rest_of_decl_compilation (fndecl, 0, 1, 0);
1109   announce_function (fndecl);
1110   current_function_decl = fndecl;
1111   DECL_INITIAL (fndecl) = error_mark_node;
1112   make_decl_rtl (fndecl, NULL);
1113   init_function_start (fndecl, input_filename, lineno);
1114   pushlevel (0);
1115   expand_function_start (fndecl, 0);
1116
1117   /* Actually generate the code to call __bb_init_func. */
1118   ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 0);
1119   table_address = force_reg (Pmode,
1120                              gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf)));
1121   emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), 0,
1122                      mode, 1, table_address, Pmode);
1123
1124   expand_function_end (input_filename, lineno, 0);
1125   poplevel (1, 0, 1);
1126
1127   /* Since fndecl isn't in the list of globals, it would never be emitted
1128      when it's considered to be 'safe' for inlining, so turn off
1129      flag_inline_functions.  */
1130   flag_inline_functions = 0;
1131
1132   /* Don't instrument the function that turns on instrumentation.  Which
1133      is also handy since we'd get silly warnings about not consuming all
1134      of our da_file input.  */
1135   flag_test_coverage = 0;
1136   profile_arc_flag = 0;
1137   flag_branch_probabilities = 0;
1138
1139   rest_of_compilation (fndecl);
1140
1141   /* Reset flag_inline_functions to its original value.  */
1142   flag_inline_functions = save_flag_inline_functions;
1143   flag_test_coverage = save_flag_test_coverage;
1144   profile_arc_flag = save_profile_arc_flag;
1145   flag_branch_probabilities = save_flag_branch_probabilities;
1146
1147   if (! quiet_flag)
1148     fflush (asm_out_file);
1149   current_function_decl = NULL_TREE;
1150
1151   assemble_constructor (IDENTIFIER_POINTER (DECL_NAME (fndecl)));
1152 }