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, 2002, 2003  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 /* Generate basic block profile instrumentation and auxiliary files.
  26    Profile generation is optimized, so that not all arcs in the basic
  27    block graph need instrumenting. First, the BB graph is closed with
  28    one entry (function start), and one exit (function exit).  Any
  29    ABNORMAL_EDGE cannot be instrumented (because there is no control
  30    path to place the code). We close the graph by inserting fake
  31    EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
  32    edges that do not go to the exit_block. We ignore such abnormal
  33    edges.  Naturally these fake edges are never directly traversed,
  34    and so *cannot* be directly instrumented.  Some other graph
  35    massaging is done. To optimize the instrumentation we generate the
  36    BB minimal span tree, only edges that are not on the span tree
  37    (plus the entry point) need instrumenting. From that information
  38    all other edge counts can be deduced.  By construction all fake
  39    edges must be on the spanning tree. We also attempt to place
  40    EDGE_CRITICAL edges on the spanning tree.
  41
  42    The auxiliary file generated is <dumpbase>.bbg. The format is
  43    described in full in gcov-io.h.  */
  44
  45 /* ??? Register allocation should use basic block execution counts to
  46    give preference to the most commonly executed blocks.  */
  47
  48 /* ??? Should calculate branch probabilities before instrumenting code, since
  49    then we can use arc counts to help decide which arcs to instrument.  */
  50
  51 #include "config.h"
  52 #include "system.h"
  53 #include "coretypes.h"
  54 #include "tm.h"
  55 #include "rtl.h"
  56 #include "flags.h"
  57 #include "output.h"
  58 #include "regs.h"
  59 #include "expr.h"
  60 #include "function.h"
  61 #include "toplev.h"
  62 #include "coverage.h"
  63
  64 /* Additional information about the edges we need.  */
  65 struct edge_info {
  66   unsigned int count_valid : 1;
  67
  68   /* Is on the spanning tree.  */
  69   unsigned int on_tree : 1;
  70
  71   /* Pretend this edge does not exist (it is abnormal and we've
  72      inserted a fake to compensate).  */
  73   unsigned int ignore : 1;
  74 };
  75
  76 struct bb_info {
  77   unsigned int count_valid : 1;
  78
  79   /* Number of successor and predecessor edges.  */
  80   gcov_type succ_count;
  81   gcov_type pred_count;
  82 };
  83
  84 /* Counts information for a function.  */
  85 typedef struct counts_entry
  86 {
  87   /* We hash by  */
  88   char *function_name;
  89   unsigned section;
  90
  91   /* Store  */
  92   unsigned checksum;
  93   unsigned n_counts;
  94   gcov_type *counts;
  95   unsigned merged;
  96   gcov_type max_counter;
  97   gcov_type max_counter_sum;
  98
  99   /* Workspace */
 100   struct counts_entry *chain;
 101
 102 } counts_entry_t;
 103
 104 #define EDGE_INFO(e)  ((struct edge_info *) (e)->aux)
 105 #define BB_INFO(b)  ((struct bb_info *) (b)->aux)
 106
 107 /* Keep all basic block indexes nonnegative in the gcov output.  Index 0
 108    is used for entry block, last block exit block.  */
 109 #define BB_TO_GCOV_INDEX(bb)  ((bb) == ENTRY_BLOCK_PTR ? 0              \
 110                                : ((bb) == EXIT_BLOCK_PTR                \
 111                                   ? last_basic_block + 1 : (bb)->index + 1))
 112
 113 /* Collect statistics on the performance of this pass for the entire source
 114    file.  */
 115
 116 static int total_num_blocks;
 117 static int total_num_edges;
 118 static int total_num_edges_ignored;
 119 static int total_num_edges_instrumented;
 120 static int total_num_blocks_created;
 121 static int total_num_passes;
 122 static int total_num_times_called;
 123 static int total_hist_br_prob[20];
 124 static int total_num_never_executed;
 125 static int total_num_branches;
 126
 127 /* Forward declarations.  */
 128 static void find_spanning_tree PARAMS ((struct edge_list *));
 129 static rtx gen_edge_profiler PARAMS ((int));
 130 static void instrument_edges PARAMS ((struct edge_list *));
 131 static void compute_branch_probabilities PARAMS ((void));
 132 static gcov_type * get_exec_counts PARAMS ((void));
 133 static basic_block find_group PARAMS ((basic_block));
 134 static void union_groups PARAMS ((basic_block, basic_block));
 135
 136 \f
 137 /* Add edge instrumentation code to the entire insn chain.
 138
 139    F is the first insn of the chain.
 140    NUM_BLOCKS is the number of basic blocks found in F.  */
 141
 142 static void
 143 instrument_edges (el)
 144      struct edge_list *el;
 145 {
 146   int num_instr_edges = 0;
 147   int num_edges = NUM_EDGES (el);
 148   basic_block bb;
 149   remove_fake_edges ();
 150
 151   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 152     {
 153       edge e = bb->succ;
 154       while (e)
 155         {
 156           struct edge_info *inf = EDGE_INFO (e);
 157           if (!inf->ignore && !inf->on_tree)
 158             {
 159               if (e->flags & EDGE_ABNORMAL)
 160                 abort ();
 161               if (rtl_dump_file)
 162                 fprintf (rtl_dump_file, "Edge %d to %d instrumented%s\n",
 163                          e->src->index, e->dest->index,
 164                          EDGE_CRITICAL_P (e) ? " (and split)" : "");
 165               insert_insn_on_edge (
 166                          gen_edge_profiler (num_instr_edges++), e);
 167               rebuild_jump_labels (e->insns);
 168             }
 169           e = e->succ_next;
 170         }
 171     }
 172
 173   total_num_blocks_created += num_edges;
 174   if (rtl_dump_file)
 175     fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges);
 176 }
 177 \f
 178
 179 /* Computes hybrid profile for all matching entries in da_file.
 180    Sets max_counter_in_program as a side effect.  */
 181
 182 static gcov_type *
 183 get_exec_counts ()
 184 {
 185   unsigned num_edges = 0;
 186   basic_block bb;
 187   gcov_type *counts;
 188
 189   /* Count the edges to be (possibly) instrumented.  */
 190   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 191     {
 192       edge e;
 193       for (e = bb->succ; e; e = e->succ_next)
 194         if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
 195           num_edges++;
 196     }
 197
 198   counts = get_coverage_counts (GCOV_TAG_ARC_COUNTS, num_edges);
 199   if (!counts)
 200     return NULL;
 201
 202   if (rtl_dump_file)
 203     {
 204       fprintf(rtl_dump_file, "Merged %i profiles with maximal count %i.\n",
 205               profile_info.count_profiles_merged,
 206               (int)profile_info.max_counter_in_program);
 207     }
 208
 209   return counts;
 210 }
 211 \f
 212
 213 /* Compute the branch probabilities for the various branches.
 214    Annotate them accordingly.  */
 215
 216 static void
 217 compute_branch_probabilities ()
 218 {
 219   basic_block bb;
 220   int i;
 221   int num_edges = 0;
 222   int changes;
 223   int passes;
 224   int hist_br_prob[20];
 225   int num_never_executed;
 226   int num_branches;
 227   gcov_type *exec_counts = get_exec_counts ();
 228   int exec_counts_pos = 0;
 229
 230   /* Attach extra info block to each bb.  */
 231
 232   alloc_aux_for_blocks (sizeof (struct bb_info));
 233   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 234     {
 235       edge e;
 236
 237       for (e = bb->succ; e; e = e->succ_next)
 238         if (!EDGE_INFO (e)->ignore)
 239           BB_INFO (bb)->succ_count++;
 240       for (e = bb->pred; e; e = e->pred_next)
 241         if (!EDGE_INFO (e)->ignore)
 242           BB_INFO (bb)->pred_count++;
 243     }
 244
 245   /* Avoid predicting entry on exit nodes.  */
 246   BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
 247   BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
 248
 249   /* For each edge not on the spanning tree, set its execution count from
 250      the .da file.  */
 251
 252   /* The first count in the .da file is the number of times that the function
 253      was entered.  This is the exec_count for block zero.  */
 254
 255   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 256     {
 257       edge e;
 258       for (e = bb->succ; e; e = e->succ_next)
 259         if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
 260           {
 261             num_edges++;
 262             if (exec_counts)
 263               {
 264                 e->count = exec_counts[exec_counts_pos++];
 265               }
 266             else
 267               e->count = 0;
 268
 269             EDGE_INFO (e)->count_valid = 1;
 270             BB_INFO (bb)->succ_count--;
 271             BB_INFO (e->dest)->pred_count--;
 272             if (rtl_dump_file)
 273               {
 274                 fprintf (rtl_dump_file, "\nRead edge from %i to %i, count:",
 275                          bb->index, e->dest->index);
 276                 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
 277                          (HOST_WIDEST_INT) e->count);
 278               }
 279           }
 280     }
 281
 282   if (rtl_dump_file)
 283     fprintf (rtl_dump_file, "\n%d edge counts read\n", num_edges);
 284
 285   /* For every block in the file,
 286      - if every exit/entrance edge has a known count, then set the block count
 287      - if the block count is known, and every exit/entrance edge but one has
 288      a known execution count, then set the count of the remaining edge
 289
 290      As edge counts are set, decrement the succ/pred count, but don't delete
 291      the edge, that way we can easily tell when all edges are known, or only
 292      one edge is unknown.  */
 293
 294   /* The order that the basic blocks are iterated through is important.
 295      Since the code that finds spanning trees starts with block 0, low numbered
 296      edges are put on the spanning tree in preference to high numbered edges.
 297      Hence, most instrumented edges are at the end.  Graph solving works much
 298      faster if we propagate numbers from the end to the start.
 299
 300      This takes an average of slightly more than 3 passes.  */
 301
 302   changes = 1;
 303   passes = 0;
 304   while (changes)
 305     {
 306       passes++;
 307       changes = 0;
 308       FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
 309         {
 310           struct bb_info *bi = BB_INFO (bb);
 311           if (! bi->count_valid)
 312             {
 313               if (bi->succ_count == 0)
 314                 {
 315                   edge e;
 316                   gcov_type total = 0;
 317
 318                   for (e = bb->succ; e; e = e->succ_next)
 319                     total += e->count;
 320                   bb->count = total;
 321                   bi->count_valid = 1;
 322                   changes = 1;
 323                 }
 324               else if (bi->pred_count == 0)
 325                 {
 326                   edge e;
 327                   gcov_type total = 0;
 328
 329                   for (e = bb->pred; e; e = e->pred_next)
 330                     total += e->count;
 331                   bb->count = total;
 332                   bi->count_valid = 1;
 333                   changes = 1;
 334                 }
 335             }
 336           if (bi->count_valid)
 337             {
 338               if (bi->succ_count == 1)
 339                 {
 340                   edge e;
 341                   gcov_type total = 0;
 342
 343                   /* One of the counts will be invalid, but it is zero,
 344                      so adding it in also doesn't hurt.  */
 345                   for (e = bb->succ; e; e = e->succ_next)
 346                     total += e->count;
 347
 348                   /* Seedgeh for the invalid edge, and set its count.  */
 349                   for (e = bb->succ; e; e = e->succ_next)
 350                     if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
 351                       break;
 352
 353                   /* Calculate count for remaining edge by conservation.  */
 354                   total = bb->count - total;
 355
 356                   if (! e)
 357                     abort ();
 358                   EDGE_INFO (e)->count_valid = 1;
 359                   e->count = total;
 360                   bi->succ_count--;
 361
 362                   BB_INFO (e->dest)->pred_count--;
 363                   changes = 1;
 364                 }
 365               if (bi->pred_count == 1)
 366                 {
 367                   edge e;
 368                   gcov_type total = 0;
 369
 370                   /* One of the counts will be invalid, but it is zero,
 371                      so adding it in also doesn't hurt.  */
 372                   for (e = bb->pred; e; e = e->pred_next)
 373                     total += e->count;
 374
 375                   /* Seedgeh for the invalid edge, and set its count.  */
 376                   for (e = bb->pred; e; e = e->pred_next)
 377                     if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
 378                       break;
 379
 380                   /* Calculate count for remaining edge by conservation.  */
 381                   total = bb->count - total + e->count;
 382
 383                   if (! e)
 384                     abort ();
 385                   EDGE_INFO (e)->count_valid = 1;
 386                   e->count = total;
 387                   bi->pred_count--;
 388
 389                   BB_INFO (e->src)->succ_count--;
 390                   changes = 1;
 391                 }
 392             }
 393         }
 394     }
 395   if (rtl_dump_file)
 396     dump_flow_info (rtl_dump_file);
 397
 398   total_num_passes += passes;
 399   if (rtl_dump_file)
 400     fprintf (rtl_dump_file, "Graph solving took %d passes.\n\n", passes);
 401
 402   /* If the graph has been correctly solved, every block will have a
 403      succ and pred count of zero.  */
 404   FOR_EACH_BB (bb)
 405     {
 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_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 419     {
 420       edge e;
 421       rtx note;
 422
 423       if (bb->count < 0)
 424         {
 425           error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
 426                  bb->index, (int)bb->count);
 427           bb->count = 0;
 428         }
 429       for (e = bb->succ; e; e = e->succ_next)
 430         {
 431           /* Function may return twice in the cased the called fucntion is
 432              setjmp or calls fork, but we can't represent this by extra
 433              edge from the entry, since extra edge from the exit is
 434              already present.  We get negative frequency from the entry
 435              point.  */
 436           if ((e->count < 0
 437                && e->dest == EXIT_BLOCK_PTR)
 438               || (e->count > bb->count
 439                   && e->dest != EXIT_BLOCK_PTR))
 440             {
 441               rtx insn = bb->end;
 442
 443               while (GET_CODE (insn) != CALL_INSN
 444                      && insn != bb->head
 445                      && keep_with_call_p (insn))
 446                 insn = PREV_INSN (insn);
 447               if (GET_CODE (insn) == CALL_INSN)
 448                 e->count = e->count < 0 ? 0 : bb->count;
 449             }
 450           if (e->count < 0 || e->count > bb->count)
 451             {
 452               error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
 453                      e->src->index, e->dest->index,
 454                      (int)e->count);
 455               e->count = bb->count / 2;
 456             }
 457         }
 458       if (bb->count)
 459         {
 460           for (e = bb->succ; e; e = e->succ_next)
 461             e->probability = (e->count * REG_BR_PROB_BASE + bb->count / 2) / bb->count;
 462           if (bb->index >= 0
 463               && any_condjump_p (bb->end)
 464               && bb->succ->succ_next)
 465             {
 466               int prob;
 467               edge e;
 468               int index;
 469
 470               /* Find the branch edge.  It is possible that we do have fake
 471                  edges here.  */
 472               for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU);
 473                    e = e->succ_next)
 474                 continue; /* Loop body has been intentionally left blank.  */
 475
 476               prob = e->probability;
 477               index = prob * 20 / REG_BR_PROB_BASE;
 478
 479               if (index == 20)
 480                 index = 19;
 481               hist_br_prob[index]++;
 482
 483               note = find_reg_note (bb->end, REG_BR_PROB, 0);
 484               /* There may be already note put by some other pass, such
 485                  as builtin_expect expander.  */
 486               if (note)
 487                 XEXP (note, 0) = GEN_INT (prob);
 488               else
 489                 REG_NOTES (bb->end)
 490                   = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 491                                        REG_NOTES (bb->end));
 492               num_branches++;
 493             }
 494         }
 495       /* Otherwise distribute the probabilities evenly so we get sane
 496          sum.  Use simple heuristics that if there are normal edges,
 497          give all abnormals frequency of 0, otherwise distribute the
 498          frequency over abnormals (this is the case of noreturn
 499          calls).  */
 500       else
 501         {
 502           int total = 0;
 503
 504           for (e = bb->succ; e; e = e->succ_next)
 505             if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
 506               total ++;
 507           if (total)
 508             {
 509               for (e = bb->succ; e; e = e->succ_next)
 510                 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
 511                   e->probability = REG_BR_PROB_BASE / total;
 512                 else
 513                   e->probability = 0;
 514             }
 515           else
 516             {
 517               for (e = bb->succ; e; e = e->succ_next)
 518                 total ++;
 519               for (e = bb->succ; e; e = e->succ_next)
 520                 e->probability = REG_BR_PROB_BASE / total;
 521             }
 522           if (bb->index >= 0
 523               && any_condjump_p (bb->end)
 524               && bb->succ->succ_next)
 525             num_branches++, num_never_executed;
 526         }
 527     }
 528
 529   if (rtl_dump_file)
 530     {
 531       fprintf (rtl_dump_file, "%d branches\n", num_branches);
 532       fprintf (rtl_dump_file, "%d branches never executed\n",
 533                num_never_executed);
 534       if (num_branches)
 535         for (i = 0; i < 10; i++)
 536           fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
 537                    (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
 538                    5 * i, 5 * i + 5);
 539
 540       total_num_branches += num_branches;
 541       total_num_never_executed += num_never_executed;
 542       for (i = 0; i < 20; i++)
 543         total_hist_br_prob[i] += hist_br_prob[i];
 544
 545       fputc ('\n', rtl_dump_file);
 546       fputc ('\n', rtl_dump_file);
 547     }
 548
 549   free_aux_for_blocks ();
 550   find_counters_section (GCOV_TAG_ARC_COUNTS)->present = 1;
 551 }
 552
 553 /* Instrument and/or analyze program behavior based on program flow graph.
 554    In either case, this function builds a flow graph for the function being
 555    compiled.  The flow graph is stored in BB_GRAPH.
 556
 557    When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
 558    the flow graph that are needed to reconstruct the dynamic behavior of the
 559    flow graph.
 560
 561    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
 562    information from a data file containing edge count information from previous
 563    executions of the function being compiled.  In this case, the flow graph is
 564    annotated with actual execution counts, which are later propagated into the
 565    rtl for optimization purposes.
 566
 567    Main entry point of this file.  */
 568
 569 void
 570 branch_prob ()
 571 {
 572   basic_block bb;
 573   unsigned i;
 574   unsigned num_edges, ignored_edges;
 575   struct edge_list *el;
 576
 577   total_num_times_called++;
 578
 579   flow_call_edges_add (NULL);
 580   add_noreturn_fake_exit_edges ();
 581
 582   /* We can't handle cyclic regions constructed using abnormal edges.
 583      To avoid these we replace every source of abnormal edge by a fake
 584      edge from entry node and every destination by fake edge to exit.
 585      This keeps graph acyclic and our calculation exact for all normal
 586      edges except for exit and entrance ones.
 587
 588      We also add fake exit edges for each call and asm statement in the
 589      basic, since it may not return.  */
 590
 591   FOR_EACH_BB (bb)
 592     {
 593       int need_exit_edge = 0, need_entry_edge = 0;
 594       int have_exit_edge = 0, have_entry_edge = 0;
 595       edge e;
 596
 597       /* Functions returning multiple times are not handled by extra edges.
 598          Instead we simply allow negative counts on edges from exit to the
 599          block past call and corresponding probabilities.  We can't go
 600          with the extra edges because that would result in flowgraph that
 601          needs to have fake edges outside the spanning tree.  */
 602
 603       for (e = bb->succ; e; e = e->succ_next)
 604         {
 605           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 606                && e->dest != EXIT_BLOCK_PTR)
 607             need_exit_edge = 1;
 608           if (e->dest == EXIT_BLOCK_PTR)
 609             have_exit_edge = 1;
 610         }
 611       for (e = bb->pred; e; e = e->pred_next)
 612         {
 613           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 614                && e->src != ENTRY_BLOCK_PTR)
 615             need_entry_edge = 1;
 616           if (e->src == ENTRY_BLOCK_PTR)
 617             have_entry_edge = 1;
 618         }
 619
 620       if (need_exit_edge && !have_exit_edge)
 621         {
 622           if (rtl_dump_file)
 623             fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n",
 624                      bb->index);
 625           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 626         }
 627       if (need_entry_edge && !have_entry_edge)
 628         {
 629           if (rtl_dump_file)
 630             fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n",
 631                      bb->index);
 632           make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
 633         }
 634     }
 635
 636   el = create_edge_list ();
 637   num_edges = NUM_EDGES (el);
 638   alloc_aux_for_edges (sizeof (struct edge_info));
 639
 640   /* The basic blocks are expected to be numbered sequentially.  */
 641   compact_blocks ();
 642
 643   ignored_edges = 0;
 644   for (i = 0 ; i < num_edges ; i++)
 645     {
 646       edge e = INDEX_EDGE (el, i);
 647       e->count = 0;
 648
 649       /* Mark edges we've replaced by fake edges above as ignored.  */
 650       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
 651           && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
 652         {
 653           EDGE_INFO (e)->ignore = 1;
 654           ignored_edges++;
 655         }
 656     }
 657
 658 #ifdef ENABLE_CHECKING
 659   verify_flow_info ();
 660 #endif
 661
 662   /* Create spanning tree from basic block graph, mark each edge that is
 663      on the spanning tree.  We insert as many abnormal and critical edges
 664      as possible to minimize number of edge splits necessary.  */
 665
 666   find_spanning_tree (el);
 667
 668   /* Fake edges that are not on the tree will not be instrumented, so
 669      mark them ignored.  */
 670   for (i = 0; i < num_edges; i++)
 671     {
 672       edge e = INDEX_EDGE (el, i);
 673       struct edge_info *inf = EDGE_INFO (e);
 674       if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree)
 675         {
 676           inf->ignore = 1;
 677           ignored_edges++;
 678         }
 679     }
 680
 681   total_num_blocks += n_basic_blocks + 2;
 682   if (rtl_dump_file)
 683     fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
 684
 685   total_num_edges += num_edges;
 686   if (rtl_dump_file)
 687     fprintf (rtl_dump_file, "%d edges\n", num_edges);
 688
 689   total_num_edges_ignored += ignored_edges;
 690   if (rtl_dump_file)
 691     fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges);
 692
 693   /* Write the .bbg data from which gcov can reconstruct the basic block
 694      graph.  First output the number of basic blocks, and then for every
 695      edge output the source and target basic block numbers.
 696      NOTE: The format of this file must be compatible with gcov.  */
 697
 698   if (coverage_begin_output ())
 699     {
 700       long offset;
 701
 702       /* Basic block flags */
 703       offset = gcov_write_tag (GCOV_TAG_BLOCKS);
 704       for (i = 0; i != (unsigned) (n_basic_blocks + 2); i++)
 705         gcov_write_unsigned (0);
 706       gcov_write_length (offset);
 707
 708       /* Arcs */
 709       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 710         {
 711           edge e;
 712
 713           offset = gcov_write_tag (GCOV_TAG_ARCS);
 714           gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
 715
 716           for (e = bb->succ; e; e = e->succ_next)
 717             {
 718               struct edge_info *i = EDGE_INFO (e);
 719               if (!i->ignore)
 720                 {
 721                   unsigned flag_bits = 0;
 722
 723                   if (i->on_tree)
 724                     flag_bits |= GCOV_ARC_ON_TREE;
 725                   if (e->flags & EDGE_FAKE)
 726                     flag_bits |= GCOV_ARC_FAKE;
 727                   if (e->flags & EDGE_FALLTHRU)
 728                     flag_bits |= GCOV_ARC_FALLTHROUGH;
 729
 730                   gcov_write_unsigned (BB_TO_GCOV_INDEX (e->dest));
 731                   gcov_write_unsigned (flag_bits);
 732                 }
 733             }
 734
 735           gcov_write_length (offset);
 736         }
 737     }
 738
 739   /* Output line number information about each basic block for GCOV
 740      utility.  */
 741   if (coverage_begin_output ())
 742     {
 743       char const *prev_file_name = NULL;
 744       long offset;
 745
 746       FOR_EACH_BB (bb)
 747         {
 748           rtx insn = bb->head;
 749           int ignore_next_note = 0;
 750
 751           offset = 0;
 752
 753           /* We are looking for line number notes.  Search backward
 754              before basic block to find correct ones.  */
 755           insn = prev_nonnote_insn (insn);
 756           if (!insn)
 757             insn = get_insns ();
 758           else
 759             insn = NEXT_INSN (insn);
 760
 761           while (insn != bb->end)
 762             {
 763               if (GET_CODE (insn) == NOTE)
 764                 {
 765                   /* Must ignore the line number notes that
 766                      immediately follow the end of an inline function
 767                      to avoid counting it twice.  There is a note
 768                      before the call, and one after the call.  */
 769                   if (NOTE_LINE_NUMBER (insn)
 770                       == NOTE_INSN_REPEATED_LINE_NUMBER)
 771                     ignore_next_note = 1;
 772                   else if (NOTE_LINE_NUMBER (insn) <= 0)
 773                     /*NOP*/;
 774                   else if (ignore_next_note)
 775                     ignore_next_note = 0;
 776                   else
 777                     {
 778                       if (!offset)
 779                         {
 780                           offset = gcov_write_tag (GCOV_TAG_LINES);
 781                           gcov_write_unsigned (BB_TO_GCOV_INDEX (bb));
 782                         }
 783
 784                       /* If this is a new source file, then output the
 785                          file's name to the .bb file.  */
 786                       if (!prev_file_name
 787                           || strcmp (NOTE_SOURCE_FILE (insn),
 788                                      prev_file_name))
 789                         {
 790                           prev_file_name = NOTE_SOURCE_FILE (insn);
 791                           gcov_write_unsigned (0);
 792                           gcov_write_string (prev_file_name);
 793                         }
 794                       gcov_write_unsigned (NOTE_LINE_NUMBER (insn));
 795                     }
 796                 }
 797               insn = NEXT_INSN (insn);
 798             }
 799
 800           if (offset)
 801             {
 802               /* A file of NULL indicates the end of run.  */
 803               gcov_write_unsigned (0);
 804               gcov_write_string (NULL);
 805               gcov_write_length (offset);
 806             }
 807         }
 808     }
 809
 810   if (flag_branch_probabilities)
 811     compute_branch_probabilities ();
 812
 813   /* For each edge not on the spanning tree, add counting code as rtl.  */
 814
 815   if (cfun->arc_profile && profile_arc_flag)
 816     {
 817       instrument_edges (el);
 818
 819       /* Commit changes done by instrumentation.  */
 820       commit_edge_insertions_watch_calls ();
 821       allocate_reg_info (max_reg_num (), FALSE, FALSE);
 822     }
 823
 824   remove_fake_edges ();
 825   free_aux_for_edges ();
 826   /* Re-merge split basic blocks and the mess introduced by
 827      insert_insn_on_edge.  */
 828   cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
 829   if (rtl_dump_file)
 830     dump_flow_info (rtl_dump_file);
 831
 832   free_edge_list (el);
 833 }
 834 \f
 835 /* Union find algorithm implementation for the basic blocks using
 836    aux fields.  */
 837
 838 static basic_block
 839 find_group (bb)
 840      basic_block bb;
 841 {
 842   basic_block group = bb, bb1;
 843
 844   while ((basic_block) group->aux != group)
 845     group = (basic_block) group->aux;
 846
 847   /* Compress path.  */
 848   while ((basic_block) bb->aux != group)
 849     {
 850       bb1 = (basic_block) bb->aux;
 851       bb->aux = (void *) group;
 852       bb = bb1;
 853     }
 854   return group;
 855 }
 856
 857 static void
 858 union_groups (bb1, bb2)
 859      basic_block bb1, bb2;
 860 {
 861   basic_block bb1g = find_group (bb1);
 862   basic_block bb2g = find_group (bb2);
 863
 864   /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
 865      this code is unlikely going to be performance problem anyway.  */
 866   if (bb1g == bb2g)
 867     abort ();
 868
 869   bb1g->aux = bb2g;
 870 }
 871 \f
 872 /* This function searches all of the edges in the program flow graph, and puts
 873    as many bad edges as possible onto the spanning tree.  Bad edges include
 874    abnormals edges, which can't be instrumented at the moment.  Since it is
 875    possible for fake edges to form a cycle, we will have to develop some
 876    better way in the future.  Also put critical edges to the tree, since they
 877    are more expensive to instrument.  */
 878
 879 static void
 880 find_spanning_tree (el)
 881      struct edge_list *el;
 882 {
 883   int i;
 884   int num_edges = NUM_EDGES (el);
 885   basic_block bb;
 886
 887   /* We use aux field for standard union-find algorithm.  */
 888   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 889     bb->aux = bb;
 890
 891   /* Add fake edge exit to entry we can't instrument.  */
 892   union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
 893
 894   /* First add all abnormal edges to the tree unless they form a cycle. Also
 895      add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
 896      setting return value from function.  */
 897   for (i = 0; i < num_edges; i++)
 898     {
 899       edge e = INDEX_EDGE (el, i);
 900       if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
 901            || e->dest == EXIT_BLOCK_PTR
 902            )
 903           && !EDGE_INFO (e)->ignore
 904           && (find_group (e->src) != find_group (e->dest)))
 905         {
 906           if (rtl_dump_file)
 907             fprintf (rtl_dump_file, "Abnormal edge %d to %d put to tree\n",
 908                      e->src->index, e->dest->index);
 909           EDGE_INFO (e)->on_tree = 1;
 910           union_groups (e->src, e->dest);
 911         }
 912     }
 913
 914   /* Now insert all critical edges to the tree unless they form a cycle.  */
 915   for (i = 0; i < num_edges; i++)
 916     {
 917       edge e = INDEX_EDGE (el, i);
 918       if ((EDGE_CRITICAL_P (e))
 919           && !EDGE_INFO (e)->ignore
 920           && (find_group (e->src) != find_group (e->dest)))
 921         {
 922           if (rtl_dump_file)
 923             fprintf (rtl_dump_file, "Critical edge %d to %d put to tree\n",
 924                      e->src->index, e->dest->index);
 925           EDGE_INFO (e)->on_tree = 1;
 926           union_groups (e->src, e->dest);
 927         }
 928     }
 929
 930   /* And now the rest.  */
 931   for (i = 0; i < num_edges; i++)
 932     {
 933       edge e = INDEX_EDGE (el, i);
 934       if (find_group (e->src) != find_group (e->dest)
 935           && !EDGE_INFO (e)->ignore)
 936         {
 937           if (rtl_dump_file)
 938             fprintf (rtl_dump_file, "Normal edge %d to %d put to tree\n",
 939                      e->src->index, e->dest->index);
 940           EDGE_INFO (e)->on_tree = 1;
 941           union_groups (e->src, e->dest);
 942         }
 943     }
 944
 945   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 946     bb->aux = NULL;
 947 }
 948 \f
 949 /* Perform file-level initialization for branch-prob processing.  */
 950
 951 void
 952 init_branch_prob ()
 953 {
 954   int i;
 955
 956   total_num_blocks = 0;
 957   total_num_edges = 0;
 958   total_num_edges_ignored = 0;
 959   total_num_edges_instrumented = 0;
 960   total_num_blocks_created = 0;
 961   total_num_passes = 0;
 962   total_num_times_called = 0;
 963   total_num_branches = 0;
 964   total_num_never_executed = 0;
 965   for (i = 0; i < 20; i++)
 966     total_hist_br_prob[i] = 0;
 967 }
 968
 969 /* Performs file-level cleanup after branch-prob processing
 970    is completed.  */
 971
 972 void
 973 end_branch_prob ()
 974 {
 975   if (rtl_dump_file)
 976     {
 977       fprintf (rtl_dump_file, "\n");
 978       fprintf (rtl_dump_file, "Total number of blocks: %d\n",
 979                total_num_blocks);
 980       fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
 981       fprintf (rtl_dump_file, "Total number of ignored edges: %d\n",
 982                total_num_edges_ignored);
 983       fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
 984                total_num_edges_instrumented);
 985       fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
 986                total_num_blocks_created);
 987       fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
 988                total_num_passes);
 989       if (total_num_times_called != 0)
 990         fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
 991                  (total_num_passes + (total_num_times_called  >> 1))
 992                  / total_num_times_called);
 993       fprintf (rtl_dump_file, "Total number of branches: %d\n",
 994                total_num_branches);
 995       fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
 996                total_num_never_executed);
 997       if (total_num_branches)
 998         {
 999           int i;
1000
1001           for (i = 0; i < 10; i++)
1002             fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
1003                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1004                      / total_num_branches, 5*i, 5*i+5);
1005         }
1006     }
1007 }
1008
1009 \f
1010 /* Output instructions as RTL to increment the edge execution count.  */
1011
1012 static rtx
1013 gen_edge_profiler (edgeno)
1014      int edgeno;
1015 {
1016   rtx ref = coverage_counter_ref (GCOV_TAG_ARC_COUNTS, edgeno);
1017   rtx tmp;
1018   enum machine_mode mode = GET_MODE (ref);
1019   rtx sequence;
1020
1021   start_sequence ();
1022   ref = validize_mem (ref);
1023
1024   tmp = expand_simple_binop (mode, PLUS, ref, const1_rtx,
1025                              ref, 0, OPTAB_WIDEN);
1026
1027   if (tmp != ref)
1028     emit_move_insn (copy_rtx (ref), tmp);
1029
1030   sequence = get_insns ();
1031   end_sequence ();
1032   return sequence;
1033 }