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