gcc/profile.c

   1 /* Calculate branch probabilities, and basic block execution counts.
   2    Copyright (C) 1990-2013 Free Software Foundation, Inc.
   3    Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
   4    based on some ideas from Dain Samples of UC Berkeley.
   5    Further mangling by Bob Manson, Cygnus Support.
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 3, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  22
  23 /* Generate basic block profile instrumentation and auxiliary files.
  24    Profile generation is optimized, so that not all arcs in the basic
  25    block graph need instrumenting. First, the BB graph is closed with
  26    one entry (function start), and one exit (function exit).  Any
  27    ABNORMAL_EDGE cannot be instrumented (because there is no control
  28    path to place the code). We close the graph by inserting fake
  29    EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
  30    edges that do not go to the exit_block. We ignore such abnormal
  31    edges.  Naturally these fake edges are never directly traversed,
  32    and so *cannot* be directly instrumented.  Some other graph
  33    massaging is done. To optimize the instrumentation we generate the
  34    BB minimal span tree, only edges that are not on the span tree
  35    (plus the entry point) need instrumenting. From that information
  36    all other edge counts can be deduced.  By construction all fake
  37    edges must be on the spanning tree. We also attempt to place
  38    EDGE_CRITICAL edges on the spanning tree.
  39
  40    The auxiliary files generated are <dumpbase>.gcno (at compile time)
  41    and <dumpbase>.gcda (at run time).  The format is
  42    described in full in gcov-io.h.  */
  43
  44 /* ??? Register allocation should use basic block execution counts to
  45    give preference to the most commonly executed blocks.  */
  46
  47 /* ??? Should calculate branch probabilities before instrumenting code, since
  48    then we can use arc counts to help decide which arcs to instrument.  */
  49
  50 #include "config.h"
  51 #include "system.h"
  52 #include "coretypes.h"
  53 #include "tm.h"
  54 #include "rtl.h"
  55 #include "flags.h"
  56 #include "regs.h"
  57 #include "expr.h"
  58 #include "function.h"
  59 #include "basic-block.h"
  60 #include "diagnostic-core.h"
  61 #include "coverage.h"
  62 #include "value-prof.h"
  63 #include "tree.h"
  64 #include "tree-flow.h"
  65 #include "cfgloop.h"
  66 #include "dumpfile.h"
  67
  68 #include "profile.h"
  69
  70 struct bb_info {
  71   unsigned int count_valid : 1;
  72
  73   /* Number of successor and predecessor edges.  */
  74   gcov_type succ_count;
  75   gcov_type pred_count;
  76 };
  77
  78 #define BB_INFO(b)  ((struct bb_info *) (b)->aux)
  79
  80
  81 /* Counter summary from the last set of coverage counts read.  */
  82
  83 const struct gcov_ctr_summary *profile_info;
  84
  85 /* Counter working set information computed from the current counter
  86    summary. Not initialized unless profile_info summary is non-NULL.  */
  87 static gcov_working_set_t gcov_working_sets[NUM_GCOV_WORKING_SETS];
  88
  89 /* Collect statistics on the performance of this pass for the entire source
  90    file.  */
  91
  92 static int total_num_blocks;
  93 static int total_num_edges;
  94 static int total_num_edges_ignored;
  95 static int total_num_edges_instrumented;
  96 static int total_num_blocks_created;
  97 static int total_num_passes;
  98 static int total_num_times_called;
  99 static int total_hist_br_prob[20];
 100 static int total_num_branches;
 101
 102 /* Forward declarations.  */
 103 static void find_spanning_tree (struct edge_list *);
 104
 105 /* Add edge instrumentation code to the entire insn chain.
 106
 107    F is the first insn of the chain.
 108    NUM_BLOCKS is the number of basic blocks found in F.  */
 109
 110 static unsigned
 111 instrument_edges (struct edge_list *el)
 112 {
 113   unsigned num_instr_edges = 0;
 114   int num_edges = NUM_EDGES (el);
 115   basic_block bb;
 116
 117   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 118     {
 119       edge e;
 120       edge_iterator ei;
 121
 122       FOR_EACH_EDGE (e, ei, bb->succs)
 123         {
 124           struct edge_info *inf = EDGE_INFO (e);
 125
 126           if (!inf->ignore && !inf->on_tree)
 127             {
 128               gcc_assert (!(e->flags & EDGE_ABNORMAL));
 129               if (dump_file)
 130                 fprintf (dump_file, "Edge %d to %d instrumented%s\n",
 131                          e->src->index, e->dest->index,
 132                          EDGE_CRITICAL_P (e) ? " (and split)" : "");
 133               gimple_gen_edge_profiler (num_instr_edges++, e);
 134             }
 135         }
 136     }
 137
 138   total_num_blocks_created += num_edges;
 139   if (dump_file)
 140     fprintf (dump_file, "%d edges instrumented\n", num_instr_edges);
 141   return num_instr_edges;
 142 }
 143
 144 /* Add code to measure histograms for values in list VALUES.  */
 145 static void
 146 instrument_values (histogram_values values)
 147 {
 148   unsigned i;
 149
 150   /* Emit code to generate the histograms before the insns.  */
 151
 152   for (i = 0; i < values.length (); i++)
 153     {
 154       histogram_value hist = values[i];
 155       unsigned t = COUNTER_FOR_HIST_TYPE (hist->type);
 156
 157       if (!coverage_counter_alloc (t, hist->n_counters))
 158         continue;
 159
 160       switch (hist->type)
 161         {
 162         case HIST_TYPE_INTERVAL:
 163           gimple_gen_interval_profiler (hist, t, 0);
 164           break;
 165
 166         case HIST_TYPE_POW2:
 167           gimple_gen_pow2_profiler (hist, t, 0);
 168           break;
 169
 170         case HIST_TYPE_SINGLE_VALUE:
 171           gimple_gen_one_value_profiler (hist, t, 0);
 172           break;
 173
 174         case HIST_TYPE_CONST_DELTA:
 175           gimple_gen_const_delta_profiler (hist, t, 0);
 176           break;
 177
 178         case HIST_TYPE_INDIR_CALL:
 179           gimple_gen_ic_profiler (hist, t, 0);
 180           break;
 181
 182         case HIST_TYPE_AVERAGE:
 183           gimple_gen_average_profiler (hist, t, 0);
 184           break;
 185
 186         case HIST_TYPE_IOR:
 187           gimple_gen_ior_profiler (hist, t, 0);
 188           break;
 189
 190         default:
 191           gcc_unreachable ();
 192         }
 193     }
 194 }
 195 \f
 196
 197 /* Fill the working set information into the profile_info structure.  */
 198
 199 void
 200 get_working_sets (void)
 201 {
 202   unsigned ws_ix, pctinc, pct;
 203   gcov_working_set_t *ws_info;
 204
 205   if (!profile_info)
 206     return;
 207
 208   compute_working_sets (profile_info, gcov_working_sets);
 209
 210   if (dump_file)
 211     {
 212       fprintf (dump_file, "Counter working sets:\n");
 213       /* Multiply the percentage by 100 to avoid float.  */
 214       pctinc = 100 * 100 / NUM_GCOV_WORKING_SETS;
 215       for (ws_ix = 0, pct = pctinc; ws_ix < NUM_GCOV_WORKING_SETS;
 216            ws_ix++, pct += pctinc)
 217         {
 218           if (ws_ix == NUM_GCOV_WORKING_SETS - 1)
 219             pct = 9990;
 220           ws_info = &gcov_working_sets[ws_ix];
 221           /* Print out the percentage using int arithmatic to avoid float.  */
 222           fprintf (dump_file, "\t\t%u.%02u%%: num counts=%u, min counter="
 223                    HOST_WIDEST_INT_PRINT_DEC "\n",
 224                    pct / 100, pct - (pct / 100 * 100),
 225                    ws_info->num_counters,
 226                    (HOST_WIDEST_INT)ws_info->min_counter);
 227         }
 228     }
 229 }
 230
 231 /* Given a the desired percentage of the full profile (sum_all from the
 232    summary), multiplied by 10 to avoid float in PCT_TIMES_10, returns
 233    the corresponding working set information. If an exact match for
 234    the percentage isn't found, the closest value is used.  */
 235
 236 gcov_working_set_t *
 237 find_working_set (unsigned pct_times_10)
 238 {
 239   unsigned i;
 240   if (!profile_info)
 241     return NULL;
 242   gcc_assert (pct_times_10 <= 1000);
 243   if (pct_times_10 >= 999)
 244     return &gcov_working_sets[NUM_GCOV_WORKING_SETS - 1];
 245   i = pct_times_10 * NUM_GCOV_WORKING_SETS / 1000;
 246   if (!i)
 247     return &gcov_working_sets[0];
 248   return &gcov_working_sets[i - 1];
 249 }
 250
 251 /* Computes hybrid profile for all matching entries in da_file.
 252
 253    CFG_CHECKSUM is the precomputed checksum for the CFG.  */
 254
 255 static gcov_type *
 256 get_exec_counts (unsigned cfg_checksum, unsigned lineno_checksum)
 257 {
 258   unsigned num_edges = 0;
 259   basic_block bb;
 260   gcov_type *counts;
 261
 262   /* Count the edges to be (possibly) instrumented.  */
 263   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 264     {
 265       edge e;
 266       edge_iterator ei;
 267
 268       FOR_EACH_EDGE (e, ei, bb->succs)
 269         if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
 270           num_edges++;
 271     }
 272
 273   counts = get_coverage_counts (GCOV_COUNTER_ARCS, num_edges, cfg_checksum,
 274                                 lineno_checksum, &profile_info);
 275   if (!counts)
 276     return NULL;
 277
 278   get_working_sets();
 279
 280   if (dump_file && profile_info)
 281     fprintf(dump_file, "Merged %u profiles with maximal count %u.\n",
 282             profile_info->runs, (unsigned) profile_info->sum_max);
 283
 284   return counts;
 285 }
 286
 287
 288 static bool
 289 is_edge_inconsistent (vec<edge, va_gc> *edges)
 290 {
 291   edge e;
 292   edge_iterator ei;
 293   FOR_EACH_EDGE (e, ei, edges)
 294     {
 295       if (!EDGE_INFO (e)->ignore)
 296         {
 297           if (e->count < 0
 298               && (!(e->flags & EDGE_FAKE)
 299                   || !block_ends_with_call_p (e->src)))
 300             {
 301               if (dump_file)
 302                 {
 303                   fprintf (dump_file,
 304                            "Edge %i->%i is inconsistent, count"HOST_WIDEST_INT_PRINT_DEC,
 305                            e->src->index, e->dest->index, e->count);
 306                   dump_bb (dump_file, e->src, 0, TDF_DETAILS);
 307                   dump_bb (dump_file, e->dest, 0, TDF_DETAILS);
 308                 }
 309               return true;
 310             }
 311         }
 312     }
 313   return false;
 314 }
 315
 316 static void
 317 correct_negative_edge_counts (void)
 318 {
 319   basic_block bb;
 320   edge e;
 321   edge_iterator ei;
 322
 323   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 324     {
 325       FOR_EACH_EDGE (e, ei, bb->succs)
 326         {
 327            if (e->count < 0)
 328              e->count = 0;
 329         }
 330     }
 331 }
 332
 333 /* Check consistency.
 334    Return true if inconsistency is found.  */
 335 static bool
 336 is_inconsistent (void)
 337 {
 338   basic_block bb;
 339   bool inconsistent = false;
 340   FOR_EACH_BB (bb)
 341     {
 342       inconsistent |= is_edge_inconsistent (bb->preds);
 343       if (!dump_file && inconsistent)
 344         return true;
 345       inconsistent |= is_edge_inconsistent (bb->succs);
 346       if (!dump_file && inconsistent)
 347         return true;
 348       if (bb->count < 0)
 349         {
 350           if (dump_file)
 351             {
 352               fprintf (dump_file, "BB %i count is negative "
 353                        HOST_WIDEST_INT_PRINT_DEC,
 354                        bb->index,
 355                        bb->count);
 356               dump_bb (dump_file, bb, 0, TDF_DETAILS);
 357             }
 358           inconsistent = true;
 359         }
 360       if (bb->count != sum_edge_counts (bb->preds))
 361         {
 362           if (dump_file)
 363             {
 364               fprintf (dump_file, "BB %i count does not match sum of incoming edges "
 365                        HOST_WIDEST_INT_PRINT_DEC" should be " HOST_WIDEST_INT_PRINT_DEC,
 366                        bb->index,
 367                        bb->count,
 368                        sum_edge_counts (bb->preds));
 369               dump_bb (dump_file, bb, 0, TDF_DETAILS);
 370             }
 371           inconsistent = true;
 372         }
 373       if (bb->count != sum_edge_counts (bb->succs) &&
 374           ! (find_edge (bb, EXIT_BLOCK_PTR) != NULL && block_ends_with_call_p (bb)))
 375         {
 376           if (dump_file)
 377             {
 378               fprintf (dump_file, "BB %i count does not match sum of outgoing edges "
 379                        HOST_WIDEST_INT_PRINT_DEC" should be " HOST_WIDEST_INT_PRINT_DEC,
 380                        bb->index,
 381                        bb->count,
 382                        sum_edge_counts (bb->succs));
 383               dump_bb (dump_file, bb, 0, TDF_DETAILS);
 384             }
 385           inconsistent = true;
 386         }
 387       if (!dump_file && inconsistent)
 388         return true;
 389     }
 390
 391   return inconsistent;
 392 }
 393
 394 /* Set each basic block count to the sum of its outgoing edge counts */
 395 static void
 396 set_bb_counts (void)
 397 {
 398   basic_block bb;
 399   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 400     {
 401       bb->count = sum_edge_counts (bb->succs);
 402       gcc_assert (bb->count >= 0);
 403     }
 404 }
 405
 406 /* Reads profile data and returns total number of edge counts read */
 407 static int
 408 read_profile_edge_counts (gcov_type *exec_counts)
 409 {
 410   basic_block bb;
 411   int num_edges = 0;
 412   int exec_counts_pos = 0;
 413   /* For each edge not on the spanning tree, set its execution count from
 414      the .da file.  */
 415   /* The first count in the .da file is the number of times that the function
 416      was entered.  This is the exec_count for block zero.  */
 417
 418   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 419     {
 420       edge e;
 421       edge_iterator ei;
 422
 423       FOR_EACH_EDGE (e, ei, bb->succs)
 424         if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
 425           {
 426             num_edges++;
 427             if (exec_counts)
 428               {
 429                 e->count = exec_counts[exec_counts_pos++];
 430                 if (e->count > profile_info->sum_max)
 431                   {
 432                     if (flag_profile_correction)
 433                       {
 434                         static bool informed = 0;
 435                         if (!informed)
 436                           inform (input_location,
 437                                   "corrupted profile info: edge count exceeds maximal count");
 438                         informed = 1;
 439                       }
 440                     else
 441                       error ("corrupted profile info: edge from %i to %i exceeds maximal count",
 442                              bb->index, e->dest->index);
 443                   }
 444               }
 445             else
 446               e->count = 0;
 447
 448             EDGE_INFO (e)->count_valid = 1;
 449             BB_INFO (bb)->succ_count--;
 450             BB_INFO (e->dest)->pred_count--;
 451             if (dump_file)
 452               {
 453                 fprintf (dump_file, "\nRead edge from %i to %i, count:",
 454                          bb->index, e->dest->index);
 455                 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
 456                          (HOST_WIDEST_INT) e->count);
 457               }
 458           }
 459     }
 460
 461     return num_edges;
 462 }
 463
 464 #define OVERLAP_BASE 10000
 465
 466 /* Compare the static estimated profile to the actual profile, and
 467    return the "degree of overlap" measure between them.
 468
 469    Degree of overlap is a number between 0 and OVERLAP_BASE. It is
 470    the sum of each basic block's minimum relative weights between
 471    two profiles. And overlap of OVERLAP_BASE means two profiles are
 472    identical.  */
 473
 474 static int
 475 compute_frequency_overlap (void)
 476 {
 477   gcov_type count_total = 0, freq_total = 0;
 478   int overlap = 0;
 479   basic_block bb;
 480
 481   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 482     {
 483       count_total += bb->count;
 484       freq_total += bb->frequency;
 485     }
 486
 487   if (count_total == 0 || freq_total == 0)
 488     return 0;
 489
 490   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 491     overlap += MIN (bb->count * OVERLAP_BASE / count_total,
 492                     bb->frequency * OVERLAP_BASE / freq_total);
 493
 494   return overlap;
 495 }
 496
 497 /* Compute the branch probabilities for the various branches.
 498    Annotate them accordingly.
 499
 500    CFG_CHECKSUM is the precomputed checksum for the CFG.  */
 501
 502 static void
 503 compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
 504 {
 505   basic_block bb;
 506   int i;
 507   int num_edges = 0;
 508   int changes;
 509   int passes;
 510   int hist_br_prob[20];
 511   int num_branches;
 512   gcov_type *exec_counts = get_exec_counts (cfg_checksum, lineno_checksum);
 513   int inconsistent = 0;
 514
 515   /* Very simple sanity checks so we catch bugs in our profiling code.  */
 516   if (!profile_info)
 517     return;
 518   if (profile_info->run_max * profile_info->runs < profile_info->sum_max)
 519     {
 520       error ("corrupted profile info: run_max * runs < sum_max");
 521       exec_counts = NULL;
 522     }
 523
 524   if (profile_info->sum_all < profile_info->sum_max)
 525     {
 526       error ("corrupted profile info: sum_all is smaller than sum_max");
 527       exec_counts = NULL;
 528     }
 529
 530   /* Attach extra info block to each bb.  */
 531   alloc_aux_for_blocks (sizeof (struct bb_info));
 532   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 533     {
 534       edge e;
 535       edge_iterator ei;
 536
 537       FOR_EACH_EDGE (e, ei, bb->succs)
 538         if (!EDGE_INFO (e)->ignore)
 539           BB_INFO (bb)->succ_count++;
 540       FOR_EACH_EDGE (e, ei, bb->preds)
 541         if (!EDGE_INFO (e)->ignore)
 542           BB_INFO (bb)->pred_count++;
 543     }
 544
 545   /* Avoid predicting entry on exit nodes.  */
 546   BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
 547   BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
 548
 549   num_edges = read_profile_edge_counts (exec_counts);
 550
 551   if (dump_file)
 552     fprintf (dump_file, "\n%d edge counts read\n", num_edges);
 553
 554   /* For every block in the file,
 555      - if every exit/entrance edge has a known count, then set the block count
 556      - if the block count is known, and every exit/entrance edge but one has
 557      a known execution count, then set the count of the remaining edge
 558
 559      As edge counts are set, decrement the succ/pred count, but don't delete
 560      the edge, that way we can easily tell when all edges are known, or only
 561      one edge is unknown.  */
 562
 563   /* The order that the basic blocks are iterated through is important.
 564      Since the code that finds spanning trees starts with block 0, low numbered
 565      edges are put on the spanning tree in preference to high numbered edges.
 566      Hence, most instrumented edges are at the end.  Graph solving works much
 567      faster if we propagate numbers from the end to the start.
 568
 569      This takes an average of slightly more than 3 passes.  */
 570
 571   changes = 1;
 572   passes = 0;
 573   while (changes)
 574     {
 575       passes++;
 576       changes = 0;
 577       FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
 578         {
 579           struct bb_info *bi = BB_INFO (bb);
 580           if (! bi->count_valid)
 581             {
 582               if (bi->succ_count == 0)
 583                 {
 584                   edge e;
 585                   edge_iterator ei;
 586                   gcov_type total = 0;
 587
 588                   FOR_EACH_EDGE (e, ei, bb->succs)
 589                     total += e->count;
 590                   bb->count = total;
 591                   bi->count_valid = 1;
 592                   changes = 1;
 593                 }
 594               else if (bi->pred_count == 0)
 595                 {
 596                   edge e;
 597                   edge_iterator ei;
 598                   gcov_type total = 0;
 599
 600                   FOR_EACH_EDGE (e, ei, bb->preds)
 601                     total += e->count;
 602                   bb->count = total;
 603                   bi->count_valid = 1;
 604                   changes = 1;
 605                 }
 606             }
 607           if (bi->count_valid)
 608             {
 609               if (bi->succ_count == 1)
 610                 {
 611                   edge e;
 612                   edge_iterator ei;
 613                   gcov_type total = 0;
 614
 615                   /* One of the counts will be invalid, but it is zero,
 616                      so adding it in also doesn't hurt.  */
 617                   FOR_EACH_EDGE (e, ei, bb->succs)
 618                     total += e->count;
 619
 620                   /* Search for the invalid edge, and set its count.  */
 621                   FOR_EACH_EDGE (e, ei, bb->succs)
 622                     if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
 623                       break;
 624
 625                   /* Calculate count for remaining edge by conservation.  */
 626                   total = bb->count - total;
 627
 628                   gcc_assert (e);
 629                   EDGE_INFO (e)->count_valid = 1;
 630                   e->count = total;
 631                   bi->succ_count--;
 632
 633                   BB_INFO (e->dest)->pred_count--;
 634                   changes = 1;
 635                 }
 636               if (bi->pred_count == 1)
 637                 {
 638                   edge e;
 639                   edge_iterator ei;
 640                   gcov_type total = 0;
 641
 642                   /* One of the counts will be invalid, but it is zero,
 643                      so adding it in also doesn't hurt.  */
 644                   FOR_EACH_EDGE (e, ei, bb->preds)
 645                     total += e->count;
 646
 647                   /* Search for the invalid edge, and set its count.  */
 648                   FOR_EACH_EDGE (e, ei, bb->preds)
 649                     if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore)
 650                       break;
 651
 652                   /* Calculate count for remaining edge by conservation.  */
 653                   total = bb->count - total + e->count;
 654
 655                   gcc_assert (e);
 656                   EDGE_INFO (e)->count_valid = 1;
 657                   e->count = total;
 658                   bi->pred_count--;
 659
 660                   BB_INFO (e->src)->succ_count--;
 661                   changes = 1;
 662                 }
 663             }
 664         }
 665     }
 666   if (dump_file)
 667     {
 668       int overlap = compute_frequency_overlap ();
 669       gimple_dump_cfg (dump_file, dump_flags);
 670       fprintf (dump_file, "Static profile overlap: %d.%d%%\n",
 671                overlap / (OVERLAP_BASE / 100),
 672                overlap % (OVERLAP_BASE / 100));
 673     }
 674
 675   total_num_passes += passes;
 676   if (dump_file)
 677     fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
 678
 679   /* If the graph has been correctly solved, every block will have a
 680      succ and pred count of zero.  */
 681   FOR_EACH_BB (bb)
 682     {
 683       gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count);
 684     }
 685
 686   /* Check for inconsistent basic block counts */
 687   inconsistent = is_inconsistent ();
 688
 689   if (inconsistent)
 690    {
 691      if (flag_profile_correction)
 692        {
 693          /* Inconsistency detected. Make it flow-consistent. */
 694          static int informed = 0;
 695          if (informed == 0)
 696            {
 697              informed = 1;
 698              inform (input_location, "correcting inconsistent profile data");
 699            }
 700          correct_negative_edge_counts ();
 701          /* Set bb counts to the sum of the outgoing edge counts */
 702          set_bb_counts ();
 703          if (dump_file)
 704            fprintf (dump_file, "\nCalling mcf_smooth_cfg\n");
 705          mcf_smooth_cfg ();
 706        }
 707      else
 708        error ("corrupted profile info: profile data is not flow-consistent");
 709    }
 710
 711   /* For every edge, calculate its branch probability and add a reg_note
 712      to the branch insn to indicate this.  */
 713
 714   for (i = 0; i < 20; i++)
 715     hist_br_prob[i] = 0;
 716   num_branches = 0;
 717
 718   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 719     {
 720       edge e;
 721       edge_iterator ei;
 722
 723       if (bb->count < 0)
 724         {
 725           error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
 726                  bb->index, (int)bb->count);
 727           bb->count = 0;
 728         }
 729       FOR_EACH_EDGE (e, ei, bb->succs)
 730         {
 731           /* Function may return twice in the cased the called function is
 732              setjmp or calls fork, but we can't represent this by extra
 733              edge from the entry, since extra edge from the exit is
 734              already present.  We get negative frequency from the entry
 735              point.  */
 736           if ((e->count < 0
 737                && e->dest == EXIT_BLOCK_PTR)
 738               || (e->count > bb->count
 739                   && e->dest != EXIT_BLOCK_PTR))
 740             {
 741               if (block_ends_with_call_p (bb))
 742                 e->count = e->count < 0 ? 0 : bb->count;
 743             }
 744           if (e->count < 0 || e->count > bb->count)
 745             {
 746               error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
 747                      e->src->index, e->dest->index,
 748                      (int)e->count);
 749               e->count = bb->count / 2;
 750             }
 751         }
 752       if (bb->count)
 753         {
 754           FOR_EACH_EDGE (e, ei, bb->succs)
 755             e->probability = GCOV_COMPUTE_SCALE (e->count, bb->count);
 756           if (bb->index >= NUM_FIXED_BLOCKS
 757               && block_ends_with_condjump_p (bb)
 758               && EDGE_COUNT (bb->succs) >= 2)
 759             {
 760               int prob;
 761               edge e;
 762               int index;
 763
 764               /* Find the branch edge.  It is possible that we do have fake
 765                  edges here.  */
 766               FOR_EACH_EDGE (e, ei, bb->succs)
 767                 if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU)))
 768                   break;
 769
 770               prob = e->probability;
 771               index = prob * 20 / REG_BR_PROB_BASE;
 772
 773               if (index == 20)
 774                 index = 19;
 775               hist_br_prob[index]++;
 776
 777               num_branches++;
 778             }
 779         }
 780       /* As a last resort, distribute the probabilities evenly.
 781          Use simple heuristics that if there are normal edges,
 782          give all abnormals frequency of 0, otherwise distribute the
 783          frequency over abnormals (this is the case of noreturn
 784          calls).  */
 785       else if (profile_status == PROFILE_ABSENT)
 786         {
 787           int total = 0;
 788
 789           FOR_EACH_EDGE (e, ei, bb->succs)
 790             if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
 791               total ++;
 792           if (total)
 793             {
 794               FOR_EACH_EDGE (e, ei, bb->succs)
 795                 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
 796                   e->probability = REG_BR_PROB_BASE / total;
 797                 else
 798                   e->probability = 0;
 799             }
 800           else
 801             {
 802               total += EDGE_COUNT (bb->succs);
 803               FOR_EACH_EDGE (e, ei, bb->succs)
 804                 e->probability = REG_BR_PROB_BASE / total;
 805             }
 806           if (bb->index >= NUM_FIXED_BLOCKS
 807               && block_ends_with_condjump_p (bb)
 808               && EDGE_COUNT (bb->succs) >= 2)
 809             num_branches++;
 810         }
 811     }
 812   counts_to_freqs ();
 813   profile_status = PROFILE_READ;
 814   compute_function_frequency ();
 815
 816   if (dump_file)
 817     {
 818       fprintf (dump_file, "%d branches\n", num_branches);
 819       if (num_branches)
 820         for (i = 0; i < 10; i++)
 821           fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
 822                    (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
 823                    5 * i, 5 * i + 5);
 824
 825       total_num_branches += num_branches;
 826       for (i = 0; i < 20; i++)
 827         total_hist_br_prob[i] += hist_br_prob[i];
 828
 829       fputc ('\n', dump_file);
 830       fputc ('\n', dump_file);
 831     }
 832
 833   free_aux_for_blocks ();
 834 }
 835
 836 /* Load value histograms values whose description is stored in VALUES array
 837    from .gcda file.
 838
 839    CFG_CHECKSUM is the precomputed checksum for the CFG.  */
 840
 841 static void
 842 compute_value_histograms (histogram_values values, unsigned cfg_checksum,
 843                           unsigned lineno_checksum)
 844 {
 845   unsigned i, j, t, any;
 846   unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
 847   gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
 848   gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
 849   gcov_type *aact_count;
 850
 851   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 852     n_histogram_counters[t] = 0;
 853
 854   for (i = 0; i < values.length (); i++)
 855     {
 856       histogram_value hist = values[i];
 857       n_histogram_counters[(int) hist->type] += hist->n_counters;
 858     }
 859
 860   any = 0;
 861   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 862     {
 863       if (!n_histogram_counters[t])
 864         {
 865           histogram_counts[t] = NULL;
 866           continue;
 867         }
 868
 869       histogram_counts[t] =
 870         get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
 871                              n_histogram_counters[t], cfg_checksum,
 872                              lineno_checksum, NULL);
 873       if (histogram_counts[t])
 874         any = 1;
 875       act_count[t] = histogram_counts[t];
 876     }
 877   if (!any)
 878     return;
 879
 880   for (i = 0; i < values.length (); i++)
 881     {
 882       histogram_value hist = values[i];
 883       gimple stmt = hist->hvalue.stmt;
 884
 885       t = (int) hist->type;
 886
 887       aact_count = act_count[t];
 888       act_count[t] += hist->n_counters;
 889
 890       gimple_add_histogram_value (cfun, stmt, hist);
 891       hist->hvalue.counters =  XNEWVEC (gcov_type, hist->n_counters);
 892       for (j = 0; j < hist->n_counters; j++)
 893         hist->hvalue.counters[j] = aact_count[j];
 894     }
 895
 896   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
 897     free (histogram_counts[t]);
 898 }
 899
 900 /* When passed NULL as file_name, initialize.
 901    When passed something else, output the necessary commands to change
 902    line to LINE and offset to FILE_NAME.  */
 903 static void
 904 output_location (char const *file_name, int line,
 905                  gcov_position_t *offset, basic_block bb)
 906 {
 907   static char const *prev_file_name;
 908   static int prev_line;
 909   bool name_differs, line_differs;
 910
 911   if (!file_name)
 912     {
 913       prev_file_name = NULL;
 914       prev_line = -1;
 915       return;
 916     }
 917
 918   name_differs = !prev_file_name || filename_cmp (file_name, prev_file_name);
 919   line_differs = prev_line != line;
 920
 921   if (name_differs || line_differs)
 922     {
 923       if (!*offset)
 924         {
 925           *offset = gcov_write_tag (GCOV_TAG_LINES);
 926           gcov_write_unsigned (bb->index);
 927           name_differs = line_differs=true;
 928         }
 929
 930       /* If this is a new source file, then output the
 931          file's name to the .bb file.  */
 932       if (name_differs)
 933         {
 934           prev_file_name = file_name;
 935           gcov_write_unsigned (0);
 936           gcov_write_string (prev_file_name);
 937         }
 938       if (line_differs)
 939         {
 940           gcov_write_unsigned (line);
 941           prev_line = line;
 942         }
 943      }
 944 }
 945
 946 /* Instrument and/or analyze program behavior based on program the CFG.
 947
 948    This function creates a representation of the control flow graph (of
 949    the function being compiled) that is suitable for the instrumentation
 950    of edges and/or converting measured edge counts to counts on the
 951    complete CFG.
 952
 953    When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
 954    the flow graph that are needed to reconstruct the dynamic behavior of the
 955    flow graph.  This data is written to the gcno file for gcov.
 956
 957    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
 958    information from the gcda file containing edge count information from
 959    previous executions of the function being compiled.  In this case, the
 960    control flow graph is annotated with actual execution counts by
 961    compute_branch_probabilities().
 962
 963    Main entry point of this file.  */
 964
 965 void
 966 branch_prob (void)
 967 {
 968   basic_block bb;
 969   unsigned i;
 970   unsigned num_edges, ignored_edges;
 971   unsigned num_instrumented;
 972   struct edge_list *el;
 973   histogram_values values = histogram_values();
 974   unsigned cfg_checksum, lineno_checksum;
 975
 976   total_num_times_called++;
 977
 978   flow_call_edges_add (NULL);
 979   add_noreturn_fake_exit_edges ();
 980
 981   /* We can't handle cyclic regions constructed using abnormal edges.
 982      To avoid these we replace every source of abnormal edge by a fake
 983      edge from entry node and every destination by fake edge to exit.
 984      This keeps graph acyclic and our calculation exact for all normal
 985      edges except for exit and entrance ones.
 986
 987      We also add fake exit edges for each call and asm statement in the
 988      basic, since it may not return.  */
 989
 990   FOR_EACH_BB (bb)
 991     {
 992       int need_exit_edge = 0, need_entry_edge = 0;
 993       int have_exit_edge = 0, have_entry_edge = 0;
 994       edge e;
 995       edge_iterator ei;
 996
 997       /* Functions returning multiple times are not handled by extra edges.
 998          Instead we simply allow negative counts on edges from exit to the
 999          block past call and corresponding probabilities.  We can't go
1000          with the extra edges because that would result in flowgraph that
1001          needs to have fake edges outside the spanning tree.  */
1002
1003       FOR_EACH_EDGE (e, ei, bb->succs)
1004         {
1005           gimple_stmt_iterator gsi;
1006           gimple last = NULL;
1007
1008           /* It may happen that there are compiler generated statements
1009              without a locus at all.  Go through the basic block from the
1010              last to the first statement looking for a locus.  */
1011           for (gsi = gsi_last_nondebug_bb (bb);
1012                !gsi_end_p (gsi);
1013                gsi_prev_nondebug (&gsi))
1014             {
1015               last = gsi_stmt (gsi);
1016               if (gimple_has_location (last))
1017                 break;
1018             }
1019
1020           /* Edge with goto locus might get wrong coverage info unless
1021              it is the only edge out of BB.
1022              Don't do that when the locuses match, so
1023              if (blah) goto something;
1024              is not computed twice.  */
1025           if (last
1026               && gimple_has_location (last)
1027               && LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
1028               && !single_succ_p (bb)
1029               && (LOCATION_FILE (e->goto_locus)
1030                   != LOCATION_FILE (gimple_location (last))
1031                   || (LOCATION_LINE (e->goto_locus)
1032                       != LOCATION_LINE (gimple_location (last)))))
1033             {
1034               basic_block new_bb = split_edge (e);
1035               edge ne = single_succ_edge (new_bb);
1036               ne->goto_locus = e->goto_locus;
1037             }
1038           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1039                && e->dest != EXIT_BLOCK_PTR)
1040             need_exit_edge = 1;
1041           if (e->dest == EXIT_BLOCK_PTR)
1042             have_exit_edge = 1;
1043         }
1044       FOR_EACH_EDGE (e, ei, bb->preds)
1045         {
1046           if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1047                && e->src != ENTRY_BLOCK_PTR)
1048             need_entry_edge = 1;
1049           if (e->src == ENTRY_BLOCK_PTR)
1050             have_entry_edge = 1;
1051         }
1052
1053       if (need_exit_edge && !have_exit_edge)
1054         {
1055           if (dump_file)
1056             fprintf (dump_file, "Adding fake exit edge to bb %i\n",
1057                      bb->index);
1058           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
1059         }
1060       if (need_entry_edge && !have_entry_edge)
1061         {
1062           if (dump_file)
1063             fprintf (dump_file, "Adding fake entry edge to bb %i\n",
1064                      bb->index);
1065           make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
1066           /* Avoid bbs that have both fake entry edge and also some
1067              exit edge.  One of those edges wouldn't be added to the
1068              spanning tree, but we can't instrument any of them.  */
1069           if (have_exit_edge || need_exit_edge)
1070             {
1071               gimple_stmt_iterator gsi;
1072               gimple first;
1073               tree fndecl;
1074
1075               gsi = gsi_after_labels (bb);
1076               gcc_checking_assert (!gsi_end_p (gsi));
1077               first = gsi_stmt (gsi);
1078               if (is_gimple_debug (first))
1079                 {
1080                   gsi_next_nondebug (&gsi);
1081                   gcc_checking_assert (!gsi_end_p (gsi));
1082                   first = gsi_stmt (gsi);
1083                 }
1084               /* Don't split the bbs containing __builtin_setjmp_receiver
1085                  or __builtin_setjmp_dispatcher calls.  These are very
1086                  special and don't expect anything to be inserted before
1087                  them.  */
1088               if (!is_gimple_call (first)
1089                   || (fndecl = gimple_call_fndecl (first)) == NULL
1090                   || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL
1091                   || (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_SETJMP_RECEIVER
1092                       && (DECL_FUNCTION_CODE (fndecl)
1093                           != BUILT_IN_SETJMP_DISPATCHER)))
1094                 {
1095                   if (dump_file)
1096                     fprintf (dump_file, "Splitting bb %i after labels\n",
1097                              bb->index);
1098                   split_block_after_labels (bb);
1099                 }
1100             }
1101         }
1102     }
1103
1104   el = create_edge_list ();
1105   num_edges = NUM_EDGES (el);
1106   alloc_aux_for_edges (sizeof (struct edge_info));
1107
1108   /* The basic blocks are expected to be numbered sequentially.  */
1109   compact_blocks ();
1110
1111   ignored_edges = 0;
1112   for (i = 0 ; i < num_edges ; i++)
1113     {
1114       edge e = INDEX_EDGE (el, i);
1115       e->count = 0;
1116
1117       /* Mark edges we've replaced by fake edges above as ignored.  */
1118       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
1119           && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
1120         {
1121           EDGE_INFO (e)->ignore = 1;
1122           ignored_edges++;
1123         }
1124     }
1125
1126   /* Create spanning tree from basic block graph, mark each edge that is
1127      on the spanning tree.  We insert as many abnormal and critical edges
1128      as possible to minimize number of edge splits necessary.  */
1129
1130   find_spanning_tree (el);
1131
1132   /* Fake edges that are not on the tree will not be instrumented, so
1133      mark them ignored.  */
1134   for (num_instrumented = i = 0; i < num_edges; i++)
1135     {
1136       edge e = INDEX_EDGE (el, i);
1137       struct edge_info *inf = EDGE_INFO (e);
1138
1139       if (inf->ignore || inf->on_tree)
1140         /*NOP*/;
1141       else if (e->flags & EDGE_FAKE)
1142         {
1143           inf->ignore = 1;
1144           ignored_edges++;
1145         }
1146       else
1147         num_instrumented++;
1148     }
1149
1150   total_num_blocks += n_basic_blocks;
1151   if (dump_file)
1152     fprintf (dump_file, "%d basic blocks\n", n_basic_blocks);
1153
1154   total_num_edges += num_edges;
1155   if (dump_file)
1156     fprintf (dump_file, "%d edges\n", num_edges);
1157
1158   total_num_edges_ignored += ignored_edges;
1159   if (dump_file)
1160     fprintf (dump_file, "%d ignored edges\n", ignored_edges);
1161
1162   total_num_edges_instrumented += num_instrumented;
1163   if (dump_file)
1164     fprintf (dump_file, "%d instrumentation edges\n", num_instrumented);
1165
1166   /* Compute two different checksums. Note that we want to compute
1167      the checksum in only once place, since it depends on the shape
1168      of the control flow which can change during
1169      various transformations.  */
1170   cfg_checksum = coverage_compute_cfg_checksum ();
1171   lineno_checksum = coverage_compute_lineno_checksum ();
1172
1173   /* Write the data from which gcov can reconstruct the basic block
1174      graph and function line numbers (the gcno file).  */
1175   if (coverage_begin_function (lineno_checksum, cfg_checksum))
1176     {
1177       gcov_position_t offset;
1178
1179       /* Basic block flags */
1180       offset = gcov_write_tag (GCOV_TAG_BLOCKS);
1181       for (i = 0; i != (unsigned) (n_basic_blocks); i++)
1182         gcov_write_unsigned (0);
1183       gcov_write_length (offset);
1184
1185       /* Arcs */
1186       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1187         {
1188           edge e;
1189           edge_iterator ei;
1190
1191           offset = gcov_write_tag (GCOV_TAG_ARCS);
1192           gcov_write_unsigned (bb->index);
1193
1194           FOR_EACH_EDGE (e, ei, bb->succs)
1195             {
1196               struct edge_info *i = EDGE_INFO (e);
1197               if (!i->ignore)
1198                 {
1199                   unsigned flag_bits = 0;
1200
1201                   if (i->on_tree)
1202                     flag_bits |= GCOV_ARC_ON_TREE;
1203                   if (e->flags & EDGE_FAKE)
1204                     flag_bits |= GCOV_ARC_FAKE;
1205                   if (e->flags & EDGE_FALLTHRU)
1206                     flag_bits |= GCOV_ARC_FALLTHROUGH;
1207                   /* On trees we don't have fallthru flags, but we can
1208                      recompute them from CFG shape.  */
1209                   if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
1210                       && e->src->next_bb == e->dest)
1211                     flag_bits |= GCOV_ARC_FALLTHROUGH;
1212
1213                   gcov_write_unsigned (e->dest->index);
1214                   gcov_write_unsigned (flag_bits);
1215                 }
1216             }
1217
1218           gcov_write_length (offset);
1219         }
1220
1221       /* Line numbers.  */
1222       /* Initialize the output.  */
1223       output_location (NULL, 0, NULL, NULL);
1224
1225       FOR_EACH_BB (bb)
1226         {
1227           gimple_stmt_iterator gsi;
1228           gcov_position_t offset = 0;
1229
1230           if (bb == ENTRY_BLOCK_PTR->next_bb)
1231             {
1232               expanded_location curr_location =
1233                 expand_location (DECL_SOURCE_LOCATION (current_function_decl));
1234               output_location (curr_location.file, curr_location.line,
1235                                &offset, bb);
1236             }
1237
1238           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1239             {
1240               gimple stmt = gsi_stmt (gsi);
1241               if (gimple_has_location (stmt))
1242                 output_location (gimple_filename (stmt), gimple_lineno (stmt),
1243                                  &offset, bb);
1244             }
1245
1246           /* Notice GOTO expressions eliminated while constructing the CFG.  */
1247           if (single_succ_p (bb)
1248               && LOCATION_LOCUS (single_succ_edge (bb)->goto_locus)
1249                  != UNKNOWN_LOCATION)
1250             {
1251               expanded_location curr_location
1252                 = expand_location (single_succ_edge (bb)->goto_locus);
1253               output_location (curr_location.file, curr_location.line,
1254                                &offset, bb);
1255             }
1256
1257           if (offset)
1258             {
1259               /* A file of NULL indicates the end of run.  */
1260               gcov_write_unsigned (0);
1261               gcov_write_string (NULL);
1262               gcov_write_length (offset);
1263             }
1264         }
1265     }
1266
1267   if (flag_profile_values)
1268     gimple_find_values_to_profile (&values);
1269
1270   if (flag_branch_probabilities)
1271     {
1272       compute_branch_probabilities (cfg_checksum, lineno_checksum);
1273       if (flag_profile_values)
1274         compute_value_histograms (values, cfg_checksum, lineno_checksum);
1275     }
1276
1277   remove_fake_edges ();
1278
1279   /* For each edge not on the spanning tree, add counting code.  */
1280   if (profile_arc_flag
1281       && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
1282     {
1283       unsigned n_instrumented;
1284
1285       gimple_init_edge_profiler ();
1286
1287       n_instrumented = instrument_edges (el);
1288
1289       gcc_assert (n_instrumented == num_instrumented);
1290
1291       if (flag_profile_values)
1292         instrument_values (values);
1293
1294       /* Commit changes done by instrumentation.  */
1295       gsi_commit_edge_inserts ();
1296     }
1297
1298   free_aux_for_edges ();
1299
1300   values.release ();
1301   free_edge_list (el);
1302   coverage_end_function (lineno_checksum, cfg_checksum);
1303 }
1304 \f
1305 /* Union find algorithm implementation for the basic blocks using
1306    aux fields.  */
1307
1308 static basic_block
1309 find_group (basic_block bb)
1310 {
1311   basic_block group = bb, bb1;
1312
1313   while ((basic_block) group->aux != group)
1314     group = (basic_block) group->aux;
1315
1316   /* Compress path.  */
1317   while ((basic_block) bb->aux != group)
1318     {
1319       bb1 = (basic_block) bb->aux;
1320       bb->aux = (void *) group;
1321       bb = bb1;
1322     }
1323   return group;
1324 }
1325
1326 static void
1327 union_groups (basic_block bb1, basic_block bb2)
1328 {
1329   basic_block bb1g = find_group (bb1);
1330   basic_block bb2g = find_group (bb2);
1331
1332   /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
1333      this code is unlikely going to be performance problem anyway.  */
1334   gcc_assert (bb1g != bb2g);
1335
1336   bb1g->aux = bb2g;
1337 }
1338 \f
1339 /* This function searches all of the edges in the program flow graph, and puts
1340    as many bad edges as possible onto the spanning tree.  Bad edges include
1341    abnormals edges, which can't be instrumented at the moment.  Since it is
1342    possible for fake edges to form a cycle, we will have to develop some
1343    better way in the future.  Also put critical edges to the tree, since they
1344    are more expensive to instrument.  */
1345
1346 static void
1347 find_spanning_tree (struct edge_list *el)
1348 {
1349   int i;
1350   int num_edges = NUM_EDGES (el);
1351   basic_block bb;
1352
1353   /* We use aux field for standard union-find algorithm.  */
1354   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1355     bb->aux = bb;
1356
1357   /* Add fake edge exit to entry we can't instrument.  */
1358   union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
1359
1360   /* First add all abnormal edges to the tree unless they form a cycle. Also
1361      add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1362      setting return value from function.  */
1363   for (i = 0; i < num_edges; i++)
1364     {
1365       edge e = INDEX_EDGE (el, i);
1366       if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1367            || e->dest == EXIT_BLOCK_PTR)
1368           && !EDGE_INFO (e)->ignore
1369           && (find_group (e->src) != find_group (e->dest)))
1370         {
1371           if (dump_file)
1372             fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
1373                      e->src->index, e->dest->index);
1374           EDGE_INFO (e)->on_tree = 1;
1375           union_groups (e->src, e->dest);
1376         }
1377     }
1378
1379   /* Now insert all critical edges to the tree unless they form a cycle.  */
1380   for (i = 0; i < num_edges; i++)
1381     {
1382       edge e = INDEX_EDGE (el, i);
1383       if (EDGE_CRITICAL_P (e) && !EDGE_INFO (e)->ignore
1384           && find_group (e->src) != find_group (e->dest))
1385         {
1386           if (dump_file)
1387             fprintf (dump_file, "Critical edge %d to %d put to tree\n",
1388                      e->src->index, e->dest->index);
1389           EDGE_INFO (e)->on_tree = 1;
1390           union_groups (e->src, e->dest);
1391         }
1392     }
1393
1394   /* And now the rest.  */
1395   for (i = 0; i < num_edges; i++)
1396     {
1397       edge e = INDEX_EDGE (el, i);
1398       if (!EDGE_INFO (e)->ignore
1399           && find_group (e->src) != find_group (e->dest))
1400         {
1401           if (dump_file)
1402             fprintf (dump_file, "Normal edge %d to %d put to tree\n",
1403                      e->src->index, e->dest->index);
1404           EDGE_INFO (e)->on_tree = 1;
1405           union_groups (e->src, e->dest);
1406         }
1407     }
1408
1409   clear_aux_for_blocks ();
1410 }
1411 \f
1412 /* Perform file-level initialization for branch-prob processing.  */
1413
1414 void
1415 init_branch_prob (void)
1416 {
1417   int i;
1418
1419   total_num_blocks = 0;
1420   total_num_edges = 0;
1421   total_num_edges_ignored = 0;
1422   total_num_edges_instrumented = 0;
1423   total_num_blocks_created = 0;
1424   total_num_passes = 0;
1425   total_num_times_called = 0;
1426   total_num_branches = 0;
1427   for (i = 0; i < 20; i++)
1428     total_hist_br_prob[i] = 0;
1429 }
1430
1431 /* Performs file-level cleanup after branch-prob processing
1432    is completed.  */
1433
1434 void
1435 end_branch_prob (void)
1436 {
1437   if (dump_file)
1438     {
1439       fprintf (dump_file, "\n");
1440       fprintf (dump_file, "Total number of blocks: %d\n",
1441                total_num_blocks);
1442       fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
1443       fprintf (dump_file, "Total number of ignored edges: %d\n",
1444                total_num_edges_ignored);
1445       fprintf (dump_file, "Total number of instrumented edges: %d\n",
1446                total_num_edges_instrumented);
1447       fprintf (dump_file, "Total number of blocks created: %d\n",
1448                total_num_blocks_created);
1449       fprintf (dump_file, "Total number of graph solution passes: %d\n",
1450                total_num_passes);
1451       if (total_num_times_called != 0)
1452         fprintf (dump_file, "Average number of graph solution passes: %d\n",
1453                  (total_num_passes + (total_num_times_called  >> 1))
1454                  / total_num_times_called);
1455       fprintf (dump_file, "Total number of branches: %d\n",
1456                total_num_branches);
1457       if (total_num_branches)
1458         {
1459           int i;
1460
1461           for (i = 0; i < 10; i++)
1462             fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1463                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1464                      / total_num_branches, 5*i, 5*i+5);
1465         }
1466     }
1467 }