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