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