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