LCOV - code coverage report
Current view: top level - gcc - profile.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 654 754 86.7 %
Date: 2020-04-04 11:58:09 Functions: 18 22 81.8 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Calculate branch probabilities, and basic block execution counts.
       2                 :            :    Copyright (C) 1990-2020 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 "backend.h"
      54                 :            : #include "rtl.h"
      55                 :            : #include "tree.h"
      56                 :            : #include "gimple.h"
      57                 :            : #include "cfghooks.h"
      58                 :            : #include "cgraph.h"
      59                 :            : #include "coverage.h"
      60                 :            : #include "diagnostic-core.h"
      61                 :            : #include "cfganal.h"
      62                 :            : #include "value-prof.h"
      63                 :            : #include "gimple-iterator.h"
      64                 :            : #include "tree-cfg.h"
      65                 :            : #include "dumpfile.h"
      66                 :            : #include "cfgloop.h"
      67                 :            : 
      68                 :            : #include "profile.h"
      69                 :            : 
      70                 :            : /* Map from BBs/edges to gcov counters.  */
      71                 :            : vec<gcov_type> bb_gcov_counts;
      72                 :            : hash_map<edge,gcov_type> *edge_gcov_counts;
      73                 :            : 
      74                 :            : struct bb_profile_info {
      75                 :            :   unsigned int count_valid : 1;
      76                 :            : 
      77                 :            :   /* Number of successor and predecessor edges.  */
      78                 :            :   gcov_type succ_count;
      79                 :            :   gcov_type pred_count;
      80                 :            : };
      81                 :            : 
      82                 :            : #define BB_INFO(b)  ((struct bb_profile_info *) (b)->aux)
      83                 :            : 
      84                 :            : 
      85                 :            : /* Counter summary from the last set of coverage counts read.  */
      86                 :            : 
      87                 :            : gcov_summary *profile_info;
      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                 :       1565 : instrument_edges (struct edge_list *el)
     112                 :            : {
     113                 :       1565 :   unsigned num_instr_edges = 0;
     114                 :       1565 :   int num_edges = NUM_EDGES (el);
     115                 :       1565 :   basic_block bb;
     116                 :            : 
     117                 :      12044 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
     118                 :            :     {
     119                 :      10479 :       edge e;
     120                 :      10479 :       edge_iterator ei;
     121                 :            : 
     122                 :      20814 :       FOR_EACH_EDGE (e, ei, bb->succs)
     123                 :            :         {
     124                 :      10335 :           struct edge_profile_info *inf = EDGE_INFO (e);
     125                 :            : 
     126                 :      10335 :           if (!inf->ignore && !inf->on_tree)
     127                 :            :             {
     128                 :       5640 :               gcc_assert (!(e->flags & EDGE_ABNORMAL));
     129                 :       5640 :               if (dump_file)
     130                 :        525 :                 fprintf (dump_file, "Edge %d to %d instrumented%s\n",
     131                 :        175 :                          e->src->index, e->dest->index,
     132                 :        244 :                          EDGE_CRITICAL_P (e) ? " (and split)" : "");
     133                 :       5640 :               gimple_gen_edge_profiler (num_instr_edges++, e);
     134                 :            :             }
     135                 :            :         }
     136                 :            :     }
     137                 :            : 
     138                 :       1565 :   total_num_blocks_created += num_edges;
     139                 :       1565 :   if (dump_file)
     140                 :         68 :     fprintf (dump_file, "%d edges instrumented\n", num_instr_edges);
     141                 :       1565 :   return num_instr_edges;
     142                 :            : }
     143                 :            : 
     144                 :            : /* Add code to measure histograms for values in list VALUES.  */
     145                 :            : static void
     146                 :        487 : instrument_values (histogram_values values)
     147                 :            : {
     148                 :        487 :   unsigned i;
     149                 :            : 
     150                 :            :   /* Emit code to generate the histograms before the insns.  */
     151                 :            : 
     152                 :       2220 :   for (i = 0; i < values.length (); i++)
     153                 :            :     {
     154                 :        623 :       histogram_value hist = values[i];
     155                 :        623 :       unsigned t = COUNTER_FOR_HIST_TYPE (hist->type);
     156                 :            : 
     157                 :        623 :       if (!coverage_counter_alloc (t, hist->n_counters))
     158                 :          0 :         continue;
     159                 :            : 
     160                 :        623 :       switch (hist->type)
     161                 :            :         {
     162                 :          5 :         case HIST_TYPE_INTERVAL:
     163                 :          5 :           gimple_gen_interval_profiler (hist, t);
     164                 :          5 :           break;
     165                 :            : 
     166                 :          5 :         case HIST_TYPE_POW2:
     167                 :          5 :           gimple_gen_pow2_profiler (hist, t);
     168                 :          5 :           break;
     169                 :            : 
     170                 :         39 :         case HIST_TYPE_TOPN_VALUES:
     171                 :         39 :           gimple_gen_topn_values_profiler (hist, t);
     172                 :         39 :           break;
     173                 :            : 
     174                 :         35 :         case HIST_TYPE_INDIR_CALL:
     175                 :         35 :           gimple_gen_ic_profiler (hist, t);
     176                 :         35 :           break;
     177                 :            : 
     178                 :         26 :         case HIST_TYPE_AVERAGE:
     179                 :         26 :           gimple_gen_average_profiler (hist, t);
     180                 :         26 :           break;
     181                 :            : 
     182                 :         26 :         case HIST_TYPE_IOR:
     183                 :         26 :           gimple_gen_ior_profiler (hist, t);
     184                 :         26 :           break;
     185                 :            : 
     186                 :        487 :         case HIST_TYPE_TIME_PROFILE:
     187                 :        487 :           gimple_gen_time_profiler (t);
     188                 :        487 :           break;
     189                 :            : 
     190                 :          0 :         default:
     191                 :          0 :           gcc_unreachable ();
     192                 :            :         }
     193                 :            :     }
     194                 :        487 : }
     195                 :            : 
     196                 :            : 
     197                 :            : /* Computes hybrid profile for all matching entries in da_file.  
     198                 :            :    
     199                 :            :    CFG_CHECKSUM is the precomputed checksum for the CFG.  */
     200                 :            : 
     201                 :            : static gcov_type *
     202                 :        475 : get_exec_counts (unsigned cfg_checksum, unsigned lineno_checksum)
     203                 :            : {
     204                 :        475 :   unsigned num_edges = 0;
     205                 :        475 :   basic_block bb;
     206                 :        475 :   gcov_type *counts;
     207                 :            : 
     208                 :            :   /* Count the edges to be (possibly) instrumented.  */
     209                 :       3834 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
     210                 :            :     {
     211                 :       3359 :       edge e;
     212                 :       3359 :       edge_iterator ei;
     213                 :            : 
     214                 :       7477 :       FOR_EACH_EDGE (e, ei, bb->succs)
     215                 :       4118 :         if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
     216                 :       1692 :           num_edges++;
     217                 :            :     }
     218                 :            : 
     219                 :        475 :   counts = get_coverage_counts (GCOV_COUNTER_ARCS, cfg_checksum,
     220                 :            :                                 lineno_checksum, num_edges);
     221                 :        475 :   if (!counts)
     222                 :         67 :     return NULL;
     223                 :            : 
     224                 :            :   return counts;
     225                 :            : }
     226                 :            : 
     227                 :            : static bool
     228                 :       4542 : is_edge_inconsistent (vec<edge, va_gc> *edges)
     229                 :            : {
     230                 :       4542 :   edge e;
     231                 :       4542 :   edge_iterator ei;
     232                 :      10914 :   FOR_EACH_EDGE (e, ei, edges)
     233                 :            :     {
     234                 :       6372 :       if (!EDGE_INFO (e)->ignore)
     235                 :            :         {
     236                 :       6340 :           if (edge_gcov_count (e) < 0
     237                 :       6340 :               && (!(e->flags & EDGE_FAKE)
     238                 :          1 :                   || !block_ends_with_call_p (e->src)))
     239                 :            :             {
     240                 :          0 :               if (dump_file)
     241                 :            :                 {
     242                 :          0 :                   fprintf (dump_file,
     243                 :            :                            "Edge %i->%i is inconsistent, count%" PRId64,
     244                 :          0 :                            e->src->index, e->dest->index, edge_gcov_count (e));
     245                 :          0 :                   dump_bb (dump_file, e->src, 0, TDF_DETAILS);
     246                 :          0 :                   dump_bb (dump_file, e->dest, 0, TDF_DETAILS);
     247                 :            :                 }
     248                 :          0 :               return true;
     249                 :            :             }
     250                 :            :         }
     251                 :            :     }
     252                 :            :   return false;
     253                 :            : }
     254                 :            : 
     255                 :            : static void
     256                 :          0 : correct_negative_edge_counts (void)
     257                 :            : {
     258                 :          0 :   basic_block bb;
     259                 :          0 :   edge e;
     260                 :          0 :   edge_iterator ei;
     261                 :            : 
     262                 :          0 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
     263                 :            :     {
     264                 :          0 :       FOR_EACH_EDGE (e, ei, bb->succs)
     265                 :            :         {
     266                 :          0 :            if (edge_gcov_count (e) < 0)
     267                 :          0 :              edge_gcov_count (e) = 0;
     268                 :            :         }
     269                 :            :     }
     270                 :          0 : }
     271                 :            : 
     272                 :            : /* Check consistency.
     273                 :            :    Return true if inconsistency is found.  */
     274                 :            : static bool
     275                 :        410 : is_inconsistent (void)
     276                 :            : {
     277                 :        410 :   basic_block bb;
     278                 :        410 :   bool inconsistent = false;
     279                 :       2681 :   FOR_EACH_BB_FN (bb, cfun)
     280                 :            :     {
     281                 :       2271 :       inconsistent |= is_edge_inconsistent (bb->preds);
     282                 :       2271 :       if (!dump_file && inconsistent)
     283                 :            :         return true;
     284                 :       2271 :       inconsistent |= is_edge_inconsistent (bb->succs);
     285                 :       2271 :       if (!dump_file && inconsistent)
     286                 :            :         return true;
     287                 :       2271 :       if (bb_gcov_count (bb) < 0)
     288                 :            :         {
     289                 :          0 :           if (dump_file)
     290                 :            :             {
     291                 :          0 :               fprintf (dump_file, "BB %i count is negative "
     292                 :            :                        "%" PRId64,
     293                 :            :                        bb->index,
     294                 :          0 :                        bb_gcov_count (bb));
     295                 :          0 :               dump_bb (dump_file, bb, 0, TDF_DETAILS);
     296                 :            :             }
     297                 :            :           inconsistent = true;
     298                 :            :         }
     299                 :       2271 :       if (bb_gcov_count (bb) != sum_edge_counts (bb->preds))
     300                 :            :         {
     301                 :          0 :           if (dump_file)
     302                 :            :             {
     303                 :          0 :               fprintf (dump_file, "BB %i count does not match sum of incoming edges "
     304                 :            :                        "%" PRId64" should be %" PRId64,
     305                 :            :                        bb->index,
     306                 :          0 :                        bb_gcov_count (bb),
     307                 :            :                        sum_edge_counts (bb->preds));
     308                 :          0 :               dump_bb (dump_file, bb, 0, TDF_DETAILS);
     309                 :            :             }
     310                 :            :           inconsistent = true;
     311                 :            :         }
     312                 :       2271 :       if (bb_gcov_count (bb) != sum_edge_counts (bb->succs) &&
     313                 :          0 :           ! (find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun)) != NULL
     314                 :          0 :              && block_ends_with_call_p (bb)))
     315                 :            :         {
     316                 :          0 :           if (dump_file)
     317                 :            :             {
     318                 :          0 :               fprintf (dump_file, "BB %i count does not match sum of outgoing edges "
     319                 :            :                        "%" PRId64" should be %" PRId64,
     320                 :            :                        bb->index,
     321                 :          0 :                        bb_gcov_count (bb),
     322                 :            :                        sum_edge_counts (bb->succs));
     323                 :          0 :               dump_bb (dump_file, bb, 0, TDF_DETAILS);
     324                 :            :             }
     325                 :            :           inconsistent = true;
     326                 :            :         }
     327                 :       2271 :       if (!dump_file && inconsistent)
     328                 :            :         return true;
     329                 :            :     }
     330                 :            : 
     331                 :            :   return inconsistent;
     332                 :            : }
     333                 :            : 
     334                 :            : /* Set each basic block count to the sum of its outgoing edge counts */
     335                 :            : static void
     336                 :          0 : set_bb_counts (void)
     337                 :            : {
     338                 :          0 :   basic_block bb;
     339                 :          0 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
     340                 :            :     {
     341                 :          0 :       bb_gcov_count (bb) = sum_edge_counts (bb->succs);
     342                 :          0 :       gcc_assert (bb_gcov_count (bb) >= 0);
     343                 :            :     }
     344                 :          0 : }
     345                 :            : 
     346                 :            : /* Reads profile data and returns total number of edge counts read */
     347                 :            : static int
     348                 :        410 : read_profile_edge_counts (gcov_type *exec_counts)
     349                 :            : {
     350                 :        410 :   basic_block bb;
     351                 :        410 :   int num_edges = 0;
     352                 :        410 :   int exec_counts_pos = 0;
     353                 :            :   /* For each edge not on the spanning tree, set its execution count from
     354                 :            :      the .da file.  */
     355                 :            :   /* The first count in the .da file is the number of times that the function
     356                 :            :      was entered.  This is the exec_count for block zero.  */
     357                 :            : 
     358                 :       3501 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
     359                 :            :     {
     360                 :       3091 :       edge e;
     361                 :       3091 :       edge_iterator ei;
     362                 :            : 
     363                 :       6959 :       FOR_EACH_EDGE (e, ei, bb->succs)
     364                 :       3868 :         if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
     365                 :            :           {
     366                 :       1580 :             num_edges++;
     367                 :       1580 :             if (exec_counts)
     368                 :       3146 :               edge_gcov_count (e) = exec_counts[exec_counts_pos++];
     369                 :            :             else
     370                 :          7 :               edge_gcov_count (e) = 0;
     371                 :            : 
     372                 :       1580 :             EDGE_INFO (e)->count_valid = 1;
     373                 :       1580 :             BB_INFO (bb)->succ_count--;
     374                 :       1580 :             BB_INFO (e->dest)->pred_count--;
     375                 :       1580 :             if (dump_file)
     376                 :            :               {
     377                 :        177 :                 fprintf (dump_file, "\nRead edge from %i to %i, count:",
     378                 :            :                          bb->index, e->dest->index);
     379                 :        354 :                 fprintf (dump_file, "%" PRId64,
     380                 :        354 :                          (int64_t) edge_gcov_count (e));
     381                 :            :               }
     382                 :            :           }
     383                 :            :     }
     384                 :            : 
     385                 :        410 :     return num_edges;
     386                 :            : }
     387                 :            : 
     388                 :            : 
     389                 :            : /* Compute the branch probabilities for the various branches.
     390                 :            :    Annotate them accordingly.  
     391                 :            : 
     392                 :            :    CFG_CHECKSUM is the precomputed checksum for the CFG.  */
     393                 :            : 
     394                 :            : static void
     395                 :        475 : compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
     396                 :            : {
     397                 :        475 :   basic_block bb;
     398                 :        475 :   int i;
     399                 :        475 :   int num_edges = 0;
     400                 :        475 :   int changes;
     401                 :        475 :   int passes;
     402                 :        475 :   int hist_br_prob[20];
     403                 :        475 :   int num_branches;
     404                 :        475 :   gcov_type *exec_counts = get_exec_counts (cfg_checksum, lineno_checksum);
     405                 :        475 :   int inconsistent = 0;
     406                 :            : 
     407                 :            :   /* Very simple sanity checks so we catch bugs in our profiling code.  */
     408                 :        475 :   if (!profile_info)
     409                 :            :     {
     410                 :         65 :       if (dump_file)
     411                 :          0 :         fprintf (dump_file, "Profile info is missing; giving up\n");
     412                 :         65 :       return;
     413                 :            :     }
     414                 :            : 
     415                 :        410 :   bb_gcov_counts.safe_grow_cleared (last_basic_block_for_fn (cfun));
     416                 :        410 :   edge_gcov_counts = new hash_map<edge,gcov_type>;
     417                 :            : 
     418                 :            :   /* Attach extra info block to each bb.  */
     419                 :        410 :   alloc_aux_for_blocks (sizeof (struct bb_profile_info));
     420                 :       3501 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
     421                 :            :     {
     422                 :       3091 :       edge e;
     423                 :       3091 :       edge_iterator ei;
     424                 :            : 
     425                 :       6959 :       FOR_EACH_EDGE (e, ei, bb->succs)
     426                 :       3868 :         if (!EDGE_INFO (e)->ignore)
     427                 :       3851 :           BB_INFO (bb)->succ_count++;
     428                 :       6959 :       FOR_EACH_EDGE (e, ei, bb->preds)
     429                 :       3868 :         if (!EDGE_INFO (e)->ignore)
     430                 :       3851 :           BB_INFO (bb)->pred_count++;
     431                 :            :     }
     432                 :            : 
     433                 :            :   /* Avoid predicting entry on exit nodes.  */
     434                 :        410 :   BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun))->succ_count = 2;
     435                 :        410 :   BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun))->pred_count = 2;
     436                 :            : 
     437                 :        410 :   num_edges = read_profile_edge_counts (exec_counts);
     438                 :            : 
     439                 :        410 :   if (dump_file)
     440                 :         69 :     fprintf (dump_file, "\n%d edge counts read\n", num_edges);
     441                 :            : 
     442                 :            :   /* For every block in the file,
     443                 :            :      - if every exit/entrance edge has a known count, then set the block count
     444                 :            :      - if the block count is known, and every exit/entrance edge but one has
     445                 :            :      a known execution count, then set the count of the remaining edge
     446                 :            : 
     447                 :            :      As edge counts are set, decrement the succ/pred count, but don't delete
     448                 :            :      the edge, that way we can easily tell when all edges are known, or only
     449                 :            :      one edge is unknown.  */
     450                 :            : 
     451                 :            :   /* The order that the basic blocks are iterated through is important.
     452                 :            :      Since the code that finds spanning trees starts with block 0, low numbered
     453                 :            :      edges are put on the spanning tree in preference to high numbered edges.
     454                 :            :      Hence, most instrumented edges are at the end.  Graph solving works much
     455                 :            :      faster if we propagate numbers from the end to the start.
     456                 :            : 
     457                 :            :      This takes an average of slightly more than 3 passes.  */
     458                 :            : 
     459                 :            :   changes = 1;
     460                 :            :   passes = 0;
     461                 :       2138 :   while (changes)
     462                 :            :     {
     463                 :       1728 :       passes++;
     464                 :       1728 :       changes = 0;
     465                 :      17754 :       FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), NULL, prev_bb)
     466                 :            :         {
     467                 :      16026 :           struct bb_profile_info *bi = BB_INFO (bb);
     468                 :      16026 :           if (! bi->count_valid)
     469                 :            :             {
     470                 :       5491 :               if (bi->succ_count == 0)
     471                 :            :                 {
     472                 :        722 :                   edge e;
     473                 :        722 :                   edge_iterator ei;
     474                 :        722 :                   gcov_type total = 0;
     475                 :            : 
     476                 :       1695 :                   FOR_EACH_EDGE (e, ei, bb->succs)
     477                 :       1946 :                     total += edge_gcov_count (e);
     478                 :        722 :                   bb_gcov_count (bb) = total;
     479                 :        722 :                   bi->count_valid = 1;
     480                 :        722 :                   changes = 1;
     481                 :            :                 }
     482                 :       4769 :               else if (bi->pred_count == 0)
     483                 :            :                 {
     484                 :       2369 :                   edge e;
     485                 :       2369 :                   edge_iterator ei;
     486                 :       2369 :                   gcov_type total = 0;
     487                 :            : 
     488                 :       5771 :                   FOR_EACH_EDGE (e, ei, bb->preds)
     489                 :       6804 :                     total += edge_gcov_count (e);
     490                 :       2369 :                   bb_gcov_count (bb) = total;
     491                 :       2369 :                   bi->count_valid = 1;
     492                 :       2369 :                   changes = 1;
     493                 :            :                 }
     494                 :            :             }
     495                 :      16026 :           if (bi->count_valid)
     496                 :            :             {
     497                 :      13626 :               if (bi->succ_count == 1)
     498                 :            :                 {
     499                 :       1959 :                   edge e;
     500                 :       1959 :                   edge_iterator ei;
     501                 :       1959 :                   gcov_type total = 0;
     502                 :            : 
     503                 :            :                   /* One of the counts will be invalid, but it is zero,
     504                 :            :                      so adding it in also doesn't hurt.  */
     505                 :       4854 :                   FOR_EACH_EDGE (e, ei, bb->succs)
     506                 :       5790 :                     total += edge_gcov_count (e);
     507                 :            : 
     508                 :            :                   /* Search for the invalid edge, and set its count.  */
     509                 :       2743 :                   FOR_EACH_EDGE (e, ei, bb->succs)
     510                 :       2743 :                     if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
     511                 :            :                       break;
     512                 :            : 
     513                 :            :                   /* Calculate count for remaining edge by conservation.  */
     514                 :       1959 :                   total = bb_gcov_count (bb) - total;
     515                 :            : 
     516                 :       1959 :                   gcc_assert (e);
     517                 :       1959 :                   EDGE_INFO (e)->count_valid = 1;
     518                 :       1959 :                   edge_gcov_count (e) = total;
     519                 :       1959 :                   bi->succ_count--;
     520                 :            : 
     521                 :       1959 :                   BB_INFO (e->dest)->pred_count--;
     522                 :       1959 :                   changes = 1;
     523                 :            :                 }
     524                 :      13626 :               if (bi->pred_count == 1)
     525                 :            :                 {
     526                 :        312 :                   edge e;
     527                 :        312 :                   edge_iterator ei;
     528                 :        312 :                   gcov_type total = 0;
     529                 :            : 
     530                 :            :                   /* One of the counts will be invalid, but it is zero,
     531                 :            :                      so adding it in also doesn't hurt.  */
     532                 :        778 :                   FOR_EACH_EDGE (e, ei, bb->preds)
     533                 :        932 :                     total += edge_gcov_count (e);
     534                 :            : 
     535                 :            :                   /* Search for the invalid edge, and set its count.  */
     536                 :        372 :                   FOR_EACH_EDGE (e, ei, bb->preds)
     537                 :        372 :                     if (!EDGE_INFO (e)->count_valid && !EDGE_INFO (e)->ignore)
     538                 :            :                       break;
     539                 :            : 
     540                 :            :                   /* Calculate count for remaining edge by conservation.  */
     541                 :        312 :                   total = bb_gcov_count (bb) - total + edge_gcov_count (e);
     542                 :            : 
     543                 :        312 :                   gcc_assert (e);
     544                 :        312 :                   EDGE_INFO (e)->count_valid = 1;
     545                 :        312 :                   edge_gcov_count (e) = total;
     546                 :        312 :                   bi->pred_count--;
     547                 :            : 
     548                 :        312 :                   BB_INFO (e->src)->succ_count--;
     549                 :        312 :                   changes = 1;
     550                 :            :                 }
     551                 :            :             }
     552                 :            :         }
     553                 :            :     }
     554                 :            : 
     555                 :        410 :   total_num_passes += passes;
     556                 :        410 :   if (dump_file)
     557                 :         69 :     fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
     558                 :            : 
     559                 :            :   /* If the graph has been correctly solved, every block will have a
     560                 :            :      succ and pred count of zero.  */
     561                 :       2681 :   FOR_EACH_BB_FN (bb, cfun)
     562                 :            :     {
     563                 :       2271 :       gcc_assert (!BB_INFO (bb)->succ_count && !BB_INFO (bb)->pred_count);
     564                 :            :     }
     565                 :            : 
     566                 :            :   /* Check for inconsistent basic block counts */
     567                 :        410 :   inconsistent = is_inconsistent ();
     568                 :            : 
     569                 :        410 :   if (inconsistent)
     570                 :            :    {
     571                 :          0 :      if (flag_profile_correction)
     572                 :            :        {
     573                 :            :          /* Inconsistency detected. Make it flow-consistent. */
     574                 :          0 :          static int informed = 0;
     575                 :          0 :          if (dump_enabled_p () && informed == 0)
     576                 :            :            {
     577                 :          0 :              informed = 1;
     578                 :          0 :              dump_printf_loc (MSG_NOTE,
     579                 :          0 :                               dump_user_location_t::from_location_t (input_location),
     580                 :            :                               "correcting inconsistent profile data\n");
     581                 :            :            }
     582                 :          0 :          correct_negative_edge_counts ();
     583                 :            :          /* Set bb counts to the sum of the outgoing edge counts */
     584                 :          0 :          set_bb_counts ();
     585                 :          0 :          if (dump_file)
     586                 :          0 :            fprintf (dump_file, "\nCalling mcf_smooth_cfg\n");
     587                 :          0 :          mcf_smooth_cfg ();
     588                 :            :        }
     589                 :            :      else
     590                 :          0 :        error ("corrupted profile info: profile data is not flow-consistent");
     591                 :            :    }
     592                 :            : 
     593                 :            :   /* For every edge, calculate its branch probability and add a reg_note
     594                 :            :      to the branch insn to indicate this.  */
     595                 :            : 
     596                 :       8610 :   for (i = 0; i < 20; i++)
     597                 :       8200 :     hist_br_prob[i] = 0;
     598                 :        410 :   num_branches = 0;
     599                 :            : 
     600                 :       3501 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
     601                 :            :     {
     602                 :       3091 :       edge e;
     603                 :       3091 :       edge_iterator ei;
     604                 :            : 
     605                 :       3091 :       if (bb_gcov_count (bb) < 0)
     606                 :            :         {
     607                 :          0 :           error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
     608                 :          0 :                  bb->index, (int)bb_gcov_count (bb));
     609                 :          0 :           bb_gcov_count (bb) = 0;
     610                 :            :         }
     611                 :       6959 :       FOR_EACH_EDGE (e, ei, bb->succs)
     612                 :            :         {
     613                 :            :           /* Function may return twice in the cased the called function is
     614                 :            :              setjmp or calls fork, but we can't represent this by extra
     615                 :            :              edge from the entry, since extra edge from the exit is
     616                 :            :              already present.  We get negative frequency from the entry
     617                 :            :              point.  */
     618                 :       3868 :           if ((edge_gcov_count (e) < 0
     619                 :          1 :                && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
     620                 :       7735 :               || (edge_gcov_count (e) > bb_gcov_count (bb)
     621                 :          1 :                   && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)))
     622                 :            :             {
     623                 :          2 :               if (block_ends_with_call_p (bb))
     624                 :          4 :                 edge_gcov_count (e) = edge_gcov_count (e) < 0
     625                 :          2 :                                       ? 0 : bb_gcov_count (bb);
     626                 :            :             }
     627                 :       3868 :           if (edge_gcov_count (e) < 0
     628                 :       7736 :               || edge_gcov_count (e) > bb_gcov_count (bb))
     629                 :            :             {
     630                 :          0 :               error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
     631                 :          0 :                      e->src->index, e->dest->index,
     632                 :          0 :                      (int)edge_gcov_count (e));
     633                 :          0 :               edge_gcov_count (e) = bb_gcov_count (bb) / 2;
     634                 :            :             }
     635                 :            :         }
     636                 :       3091 :       if (bb_gcov_count (bb))
     637                 :            :         {
     638                 :       2230 :           bool set_to_guessed = false;
     639                 :       5087 :           FOR_EACH_EDGE (e, ei, bb->succs)
     640                 :            :             {
     641                 :       2857 :               bool prev_never = e->probability == profile_probability::never ();
     642                 :       5714 :               e->probability = profile_probability::probability_in_gcov_type
     643                 :       5714 :                   (edge_gcov_count (e), bb_gcov_count (bb));
     644                 :       2857 :               if (e->probability == profile_probability::never ()
     645                 :        647 :                   && !prev_never
     646                 :        509 :                   && flag_profile_partial_training)
     647                 :            :                 set_to_guessed = true;
     648                 :            :             }
     649                 :       2230 :           if (set_to_guessed)
     650                 :          0 :             FOR_EACH_EDGE (e, ei, bb->succs)
     651                 :          0 :               e->probability = e->probability.guessed ();
     652                 :       2230 :           if (bb->index >= NUM_FIXED_BLOCKS
     653                 :       1620 :               && block_ends_with_condjump_p (bb)
     654                 :       2685 :               && EDGE_COUNT (bb->succs) >= 2)
     655                 :            :             {
     656                 :        455 :               int prob;
     657                 :        455 :               edge e;
     658                 :        455 :               int index;
     659                 :            : 
     660                 :            :               /* Find the branch edge.  It is possible that we do have fake
     661                 :            :                  edges here.  */
     662                 :        455 :               FOR_EACH_EDGE (e, ei, bb->succs)
     663                 :        455 :                 if (!(e->flags & (EDGE_FAKE | EDGE_FALLTHRU)))
     664                 :            :                   break;
     665                 :            : 
     666                 :        455 :               prob = e->probability.to_reg_br_prob_base ();
     667                 :        455 :               index = prob * 20 / REG_BR_PROB_BASE;
     668                 :            : 
     669                 :        455 :               if (index == 20)
     670                 :         46 :                 index = 19;
     671                 :        455 :               hist_br_prob[index]++;
     672                 :            : 
     673                 :        455 :               num_branches++;
     674                 :            :             }
     675                 :            :         }
     676                 :            :       /* As a last resort, distribute the probabilities evenly.
     677                 :            :          Use simple heuristics that if there are normal edges,
     678                 :            :          give all abnormals frequency of 0, otherwise distribute the
     679                 :            :          frequency over abnormals (this is the case of noreturn
     680                 :            :          calls).  */
     681                 :        861 :       else if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
     682                 :            :         {
     683                 :         16 :           int total = 0;
     684                 :            : 
     685                 :         34 :           FOR_EACH_EDGE (e, ei, bb->succs)
     686                 :         18 :             if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
     687                 :         11 :               total ++;
     688                 :         16 :           if (total)
     689                 :            :             {
     690                 :         22 :               FOR_EACH_EDGE (e, ei, bb->succs)
     691                 :         11 :                 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
     692                 :         11 :                   e->probability
     693                 :         11 :                     = profile_probability::guessed_always ().apply_scale (1, total);
     694                 :            :                 else
     695                 :          0 :                   e->probability = profile_probability::never ();
     696                 :            :             }
     697                 :            :           else
     698                 :            :             {
     699                 :          5 :               total += EDGE_COUNT (bb->succs);
     700                 :         12 :               FOR_EACH_EDGE (e, ei, bb->succs)
     701                 :          7 :                 e->probability
     702                 :          7 :                  = profile_probability::guessed_always ().apply_scale (1, total);
     703                 :            :             }
     704                 :         16 :           if (bb->index >= NUM_FIXED_BLOCKS
     705                 :         16 :               && block_ends_with_condjump_p (bb)
     706                 :       3107 :               && EDGE_COUNT (bb->succs) >= 2)
     707                 :          0 :             num_branches++;
     708                 :            :         }
     709                 :            :     }
     710                 :            : 
     711                 :        410 :   if (exec_counts
     712                 :        410 :       && (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun))
     713                 :        103 :           || !flag_profile_partial_training))
     714                 :        408 :     profile_status_for_fn (cfun) = PROFILE_READ;
     715                 :            : 
     716                 :            :   /* If we have real data, use them!  */
     717                 :        410 :   if (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun))
     718                 :        410 :       || !flag_guess_branch_prob)
     719                 :       2747 :     FOR_ALL_BB_FN (bb, cfun)
     720                 :       2442 :       if (bb_gcov_count (bb) || !flag_profile_partial_training)
     721                 :       2442 :         bb->count = profile_count::from_gcov_type (bb_gcov_count (bb));
     722                 :            :       else
     723                 :          0 :         bb->count = profile_count::guessed_zero ();
     724                 :            :   /* If function was not trained, preserve local estimates including statically
     725                 :            :      determined zero counts.  */
     726                 :        105 :   else if (profile_status_for_fn (cfun) == PROFILE_READ
     727                 :        103 :            && !flag_profile_partial_training)
     728                 :        741 :     FOR_ALL_BB_FN (bb, cfun)
     729                 :        644 :       if (!(bb->count == profile_count::zero ()))
     730                 :       1264 :         bb->count = bb->count.global0 ();
     731                 :            : 
     732                 :        410 :   bb_gcov_counts.release ();
     733                 :        820 :   delete edge_gcov_counts;
     734                 :        410 :   edge_gcov_counts = NULL;
     735                 :            : 
     736                 :        410 :   update_max_bb_count ();
     737                 :            : 
     738                 :        410 :   if (dump_file)
     739                 :            :     {
     740                 :         69 :       fprintf (dump_file, " Profile feedback for function");
     741                 :         71 :       fprintf (dump_file, ((profile_status_for_fn (cfun) == PROFILE_READ)
     742                 :            :                            ? " is available \n"
     743                 :            :                            : " is not available \n"));
     744                 :            : 
     745                 :         69 :       fprintf (dump_file, "%d branches\n", num_branches);
     746                 :         69 :       if (num_branches)
     747                 :        242 :         for (i = 0; i < 10; i++)
     748                 :        220 :           fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
     749                 :        220 :                    (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
     750                 :        220 :                    5 * i, 5 * i + 5);
     751                 :            : 
     752                 :         69 :       total_num_branches += num_branches;
     753                 :       1449 :       for (i = 0; i < 20; i++)
     754                 :       1380 :         total_hist_br_prob[i] += hist_br_prob[i];
     755                 :            : 
     756                 :         69 :       fputc ('\n', dump_file);
     757                 :         69 :       fputc ('\n', dump_file);
     758                 :            :     }
     759                 :            : 
     760                 :        410 :   free_aux_for_blocks ();
     761                 :            : }
     762                 :            : 
     763                 :            : /* Sort the histogram value and count for TOPN and INDIR_CALL type.  */
     764                 :            : 
     765                 :            : static void
     766                 :         62 : sort_hist_values (histogram_value hist)
     767                 :            : {
     768                 :            :   /* counters[2] equal to -1 means that all counters are invalidated.  */
     769                 :         62 :   if (hist->hvalue.counters[2] == -1)
     770                 :            :     return;
     771                 :            : 
     772                 :         62 :   gcc_assert (hist->type == HIST_TYPE_TOPN_VALUES
     773                 :            :               || hist->type == HIST_TYPE_INDIR_CALL);
     774                 :            : 
     775                 :         62 :   gcc_assert (hist->n_counters == GCOV_TOPN_VALUES_COUNTERS);
     776                 :            : 
     777                 :            :   /* Hist value is organized as:
     778                 :            :      [total_executions, value1, counter1, ..., value4, counter4]
     779                 :            :      Use decrease bubble sort to rearrange it.  The sort starts from <value1,
     780                 :            :      counter1> and compares counter first.  If counter is same, compares the
     781                 :            :      value, exchange it if small to keep stable.  */
     782                 :        225 :   for (unsigned i = 0; i < GCOV_TOPN_VALUES - 1; i++)
     783                 :            :     {
     784                 :            :       bool swapped = false;
     785                 :        533 :       for (unsigned j = 0; j < GCOV_TOPN_VALUES - 1 - i; j++)
     786                 :            :         {
     787                 :        357 :           gcov_type *p = &hist->hvalue.counters[2 * j + 1];
     788                 :        357 :           if (p[1] < p[3] || (p[1] == p[3] && p[0] < p[2]))
     789                 :            :             {
     790                 :        176 :               std::swap (p[0], p[2]);
     791                 :        176 :               std::swap (p[1], p[3]);
     792                 :        176 :               swapped = true;
     793                 :            :             }
     794                 :            :         }
     795                 :        176 :       if (!swapped)
     796                 :            :         break;
     797                 :            :     }
     798                 :            : }
     799                 :            : /* Load value histograms values whose description is stored in VALUES array
     800                 :            :    from .gcda file.  
     801                 :            : 
     802                 :            :    CFG_CHECKSUM is the precomputed checksum for the CFG.  */
     803                 :            : 
     804                 :            : static void
     805                 :        332 : compute_value_histograms (histogram_values values, unsigned cfg_checksum,
     806                 :            :                           unsigned lineno_checksum)
     807                 :            : {
     808                 :        332 :   unsigned i, j, t, any;
     809                 :        332 :   unsigned n_histogram_counters[GCOV_N_VALUE_COUNTERS];
     810                 :        332 :   gcov_type *histogram_counts[GCOV_N_VALUE_COUNTERS];
     811                 :        332 :   gcov_type *act_count[GCOV_N_VALUE_COUNTERS];
     812                 :        332 :   gcov_type *aact_count;
     813                 :        332 :   struct cgraph_node *node;
     814                 :            : 
     815                 :       2656 :   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
     816                 :       2324 :     n_histogram_counters[t] = 0;
     817                 :            : 
     818                 :       1558 :   for (i = 0; i < values.length (); i++)
     819                 :            :     {
     820                 :        447 :       histogram_value hist = values[i];
     821                 :        447 :       n_histogram_counters[(int) hist->type] += hist->n_counters;
     822                 :            :     }
     823                 :            : 
     824                 :            :   any = 0;
     825                 :       2656 :   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
     826                 :            :     {
     827                 :       2324 :       if (!n_histogram_counters[t])
     828                 :            :         {
     829                 :       1881 :           histogram_counts[t] = NULL;
     830                 :       1881 :           continue;
     831                 :            :         }
     832                 :            : 
     833                 :        443 :       histogram_counts[t] = get_coverage_counts (COUNTER_FOR_HIST_TYPE (t),
     834                 :            :                                                  cfg_checksum,
     835                 :            :                                                  lineno_checksum,
     836                 :            :                                                  n_histogram_counters[t]);
     837                 :        443 :       if (histogram_counts[t])
     838                 :        353 :         any = 1;
     839                 :        443 :       act_count[t] = histogram_counts[t];
     840                 :            :     }
     841                 :        332 :   if (!any)
     842                 :         84 :     return;
     843                 :            : 
     844                 :       1208 :   for (i = 0; i < values.length (); i++)
     845                 :            :     {
     846                 :        356 :       histogram_value hist = values[i];
     847                 :        356 :       gimple *stmt = hist->hvalue.stmt;
     848                 :            : 
     849                 :        356 :       t = (int) hist->type;
     850                 :            : 
     851                 :        356 :       aact_count = act_count[t];
     852                 :            : 
     853                 :        356 :       if (act_count[t])
     854                 :        356 :         act_count[t] += hist->n_counters;
     855                 :            : 
     856                 :        356 :       gimple_add_histogram_value (cfun, stmt, hist);
     857                 :        356 :       hist->hvalue.counters =  XNEWVEC (gcov_type, hist->n_counters);
     858                 :       1246 :       for (j = 0; j < hist->n_counters; j++)
     859                 :        890 :         if (aact_count)
     860                 :        890 :           hist->hvalue.counters[j] = aact_count[j];
     861                 :            :         else
     862                 :          0 :           hist->hvalue.counters[j] = 0;
     863                 :            : 
     864                 :        356 :       if (hist->type == HIST_TYPE_TOPN_VALUES
     865                 :        356 :           || hist->type == HIST_TYPE_INDIR_CALL)
     866                 :            :         {
     867                 :            :           /* Each count value is multiplied by GCOV_TOPN_VALUES.  */
     868                 :         62 :           if (hist->hvalue.counters[2] != -1)
     869                 :        310 :             for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
     870                 :        248 :               hist->hvalue.counters[2 * i + 2]
     871                 :        248 :                 = RDIV (hist->hvalue.counters[2 * i + 2], GCOV_TOPN_VALUES);
     872                 :            : 
     873                 :         62 :           sort_hist_values (hist);
     874                 :            :         }
     875                 :            : 
     876                 :            :       /* Time profiler counter is not related to any statement,
     877                 :            :          so that we have to read the counter and set the value to
     878                 :            :          the corresponding call graph node.  */
     879                 :        356 :       if (hist->type == HIST_TYPE_TIME_PROFILE)
     880                 :            :         {
     881                 :        248 :           node = cgraph_node::get (hist->fun->decl);
     882                 :        248 :           if (hist->hvalue.counters[0] >= 0
     883                 :        248 :               && hist->hvalue.counters[0] < INT_MAX / 2)
     884                 :        248 :             node->tp_first_run = hist->hvalue.counters[0];
     885                 :            :           else
     886                 :            :             {
     887                 :          0 :               if (flag_profile_correction)
     888                 :          0 :                 error ("corrupted profile info: invalid time profile");
     889                 :          0 :               node->tp_first_run = 0;
     890                 :            :             }
     891                 :            : 
     892                 :        248 :           if (dump_file)
     893                 :         67 :             fprintf (dump_file, "Read tp_first_run: %d\n", node->tp_first_run);
     894                 :            :         }
     895                 :            :     }
     896                 :            : 
     897                 :       1984 :   for (t = 0; t < GCOV_N_VALUE_COUNTERS; t++)
     898                 :       1736 :     free (histogram_counts[t]);
     899                 :            : }
     900                 :            : 
     901                 :            : /* Location triplet which records a location.  */
     902                 :            : struct location_triplet
     903                 :            : {
     904                 :            :   const char *filename;
     905                 :            :   int lineno;
     906                 :            :   int bb_index;
     907                 :            : };
     908                 :            : 
     909                 :            : /* Traits class for streamed_locations hash set below.  */
     910                 :            : 
     911                 :            : struct location_triplet_hash : typed_noop_remove <location_triplet>
     912                 :            : {
     913                 :            :   typedef location_triplet value_type;
     914                 :            :   typedef location_triplet compare_type;
     915                 :            : 
     916                 :            :   static hashval_t
     917                 :      23829 :   hash (const location_triplet &ref)
     918                 :            :   {
     919                 :      23829 :     inchash::hash hstate (0);
     920                 :      23829 :     if (ref.filename)
     921                 :      22973 :       hstate.add_int (strlen (ref.filename));
     922                 :      23829 :     hstate.add_int (ref.lineno);
     923                 :      23829 :     hstate.add_int (ref.bb_index);
     924                 :      23829 :     return hstate.end ();
     925                 :            :   }
     926                 :            : 
     927                 :            :   static bool
     928                 :      19144 :   equal (const location_triplet &ref1, const location_triplet &ref2)
     929                 :            :   {
     930                 :      19144 :     return ref1.lineno == ref2.lineno
     931                 :      19144 :       && ref1.bb_index == ref2.bb_index
     932                 :       1538 :       && ref1.filename != NULL
     933                 :       1538 :       && ref2.filename != NULL
     934                 :      20682 :       && strcmp (ref1.filename, ref2.filename) == 0;
     935                 :            :   }
     936                 :            : 
     937                 :            :   static void
     938                 :            :   mark_deleted (location_triplet &ref)
     939                 :            :   {
     940                 :            :     ref.lineno = -1;
     941                 :            :   }
     942                 :            : 
     943                 :            :   static const bool empty_zero_p = false;
     944                 :            : 
     945                 :            :   static void
     946                 :      31803 :   mark_empty (location_triplet &ref)
     947                 :            :   {
     948                 :      31803 :     ref.lineno = -2;
     949                 :            :   }
     950                 :            : 
     951                 :            :   static bool
     952                 :      22169 :   is_deleted (const location_triplet &ref)
     953                 :            :   {
     954                 :      22169 :     return ref.lineno == -1;
     955                 :            :   }
     956                 :            : 
     957                 :            :   static bool
     958                 :     115338 :   is_empty (const location_triplet &ref)
     959                 :            :   {
     960                 :     115338 :     return ref.lineno == -2;
     961                 :            :   }
     962                 :            : };
     963                 :            : 
     964                 :            : 
     965                 :            : 
     966                 :            : 
     967                 :            : /* When passed NULL as file_name, initialize.
     968                 :            :    When passed something else, output the necessary commands to change
     969                 :            :    line to LINE and offset to FILE_NAME.  */
     970                 :            : static void
     971                 :       6539 : output_location (hash_set<location_triplet_hash> *streamed_locations,
     972                 :            :                  char const *file_name, int line,
     973                 :            :                  gcov_position_t *offset, basic_block bb)
     974                 :            : {
     975                 :       6539 :   static char const *prev_file_name;
     976                 :       6539 :   static int prev_line;
     977                 :       6539 :   bool name_differs, line_differs;
     978                 :            : 
     979                 :       6539 :   location_triplet triplet;
     980                 :       6539 :   triplet.filename = file_name;
     981                 :       6539 :   triplet.lineno = line;
     982                 :       6539 :   triplet.bb_index = bb ? bb->index : 0;
     983                 :            : 
     984                 :       6539 :   if (streamed_locations->add (triplet))
     985                 :       2265 :     return;
     986                 :            : 
     987                 :       5001 :   if (!file_name)
     988                 :            :     {
     989                 :        727 :       prev_file_name = NULL;
     990                 :        727 :       prev_line = -1;
     991                 :        727 :       return;
     992                 :            :     }
     993                 :            : 
     994                 :       4274 :   name_differs = !prev_file_name || filename_cmp (file_name, prev_file_name);
     995                 :       4274 :   line_differs = prev_line != line;
     996                 :            : 
     997                 :       4274 :   if (!*offset)
     998                 :            :     {
     999                 :       3089 :       *offset = gcov_write_tag (GCOV_TAG_LINES);
    1000                 :       3089 :       gcov_write_unsigned (bb->index);
    1001                 :       3089 :       name_differs = line_differs = true;
    1002                 :            :     }
    1003                 :            : 
    1004                 :            :   /* If this is a new source file, then output the
    1005                 :            :      file's name to the .bb file.  */
    1006                 :       4274 :   if (name_differs)
    1007                 :            :     {
    1008                 :       3097 :       prev_file_name = file_name;
    1009                 :       3097 :       gcov_write_unsigned (0);
    1010                 :       3097 :       gcov_write_filename (prev_file_name);
    1011                 :            :     }
    1012                 :       4274 :   if (line_differs)
    1013                 :            :     {
    1014                 :       4274 :       gcov_write_unsigned (line);
    1015                 :       4274 :       prev_line = line;
    1016                 :            :     }
    1017                 :            : }
    1018                 :            : 
    1019                 :            : /* Helper for qsort so edges get sorted from highest frequency to smallest.
    1020                 :            :    This controls the weight for minimal spanning tree algorithm  */
    1021                 :            : static int
    1022                 :     294808 : compare_freqs (const void *p1, const void *p2)
    1023                 :            : {
    1024                 :     294808 :   const_edge e1 = *(const const_edge *)p1;
    1025                 :     294808 :   const_edge e2 = *(const const_edge *)p2;
    1026                 :            : 
    1027                 :            :   /* Critical edges needs to be split which introduce extra control flow.
    1028                 :            :      Make them more heavy.  */
    1029                 :     294808 :   int m1 = EDGE_CRITICAL_P (e1) ? 2 : 1;
    1030                 :     294808 :   int m2 = EDGE_CRITICAL_P (e2) ? 2 : 1;
    1031                 :            : 
    1032                 :     294808 :   if (EDGE_FREQUENCY (e1) * m1 + m1 != EDGE_FREQUENCY (e2) * m2 + m2)
    1033                 :     132669 :     return EDGE_FREQUENCY (e2) * m2 + m2 - EDGE_FREQUENCY (e1) * m1 - m1;
    1034                 :            :   /* Stabilize sort.  */
    1035                 :     162139 :   if (e1->src->index != e2->src->index)
    1036                 :     157005 :     return e2->src->index - e1->src->index;
    1037                 :       5134 :   return e2->dest->index - e1->dest->index;
    1038                 :            : }
    1039                 :            : 
    1040                 :            : /* Only read execution count for thunks.  */
    1041                 :            : 
    1042                 :            : void
    1043                 :          7 : read_thunk_profile (struct cgraph_node *node)
    1044                 :            : {
    1045                 :          7 :   tree old = current_function_decl;
    1046                 :          7 :   current_function_decl = node->decl;
    1047                 :          7 :   gcov_type *counts = get_coverage_counts (GCOV_COUNTER_ARCS, 0, 0, 1);
    1048                 :          7 :   if (counts)
    1049                 :            :     {
    1050                 :         14 :       node->callees->count = node->count
    1051                 :          7 :          = profile_count::from_gcov_type (counts[0]);
    1052                 :          7 :       free (counts);
    1053                 :            :     }
    1054                 :          7 :   current_function_decl = old;
    1055                 :          7 :   return;
    1056                 :            : }
    1057                 :            : 
    1058                 :            : 
    1059                 :            : /* Instrument and/or analyze program behavior based on program the CFG.
    1060                 :            : 
    1061                 :            :    This function creates a representation of the control flow graph (of
    1062                 :            :    the function being compiled) that is suitable for the instrumentation
    1063                 :            :    of edges and/or converting measured edge counts to counts on the
    1064                 :            :    complete CFG.
    1065                 :            : 
    1066                 :            :    When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
    1067                 :            :    the flow graph that are needed to reconstruct the dynamic behavior of the
    1068                 :            :    flow graph.  This data is written to the gcno file for gcov.
    1069                 :            : 
    1070                 :            :    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
    1071                 :            :    information from the gcda file containing edge count information from
    1072                 :            :    previous executions of the function being compiled.  In this case, the
    1073                 :            :    control flow graph is annotated with actual execution counts by
    1074                 :            :    compute_branch_probabilities().
    1075                 :            : 
    1076                 :            :    Main entry point of this file.  */
    1077                 :            : 
    1078                 :            : void
    1079                 :       2054 : branch_prob (bool thunk)
    1080                 :            : {
    1081                 :       2054 :   basic_block bb;
    1082                 :       2054 :   unsigned i;
    1083                 :       2054 :   unsigned num_edges, ignored_edges;
    1084                 :       2054 :   unsigned num_instrumented;
    1085                 :       2054 :   struct edge_list *el;
    1086                 :       2054 :   histogram_values values = histogram_values ();
    1087                 :       2054 :   unsigned cfg_checksum, lineno_checksum;
    1088                 :            : 
    1089                 :       2054 :   total_num_times_called++;
    1090                 :            : 
    1091                 :       2054 :   flow_call_edges_add (NULL);
    1092                 :       2054 :   add_noreturn_fake_exit_edges ();
    1093                 :            : 
    1094                 :       2054 :   hash_set <location_triplet_hash> streamed_locations;
    1095                 :            : 
    1096                 :       2054 :   if (!thunk)
    1097                 :            :     {
    1098                 :            :       /* We can't handle cyclic regions constructed using abnormal edges.
    1099                 :            :          To avoid these we replace every source of abnormal edge by a fake
    1100                 :            :          edge from entry node and every destination by fake edge to exit.
    1101                 :            :          This keeps graph acyclic and our calculation exact for all normal
    1102                 :            :          edges except for exit and entrance ones.
    1103                 :            : 
    1104                 :            :          We also add fake exit edges for each call and asm statement in the
    1105                 :            :          basic, since it may not return.  */
    1106                 :            : 
    1107                 :      11818 :       FOR_EACH_BB_FN (bb, cfun)
    1108                 :            :         {
    1109                 :       9771 :           int need_exit_edge = 0, need_entry_edge = 0;
    1110                 :       9771 :           int have_exit_edge = 0, have_entry_edge = 0;
    1111                 :       9771 :           edge e;
    1112                 :       9771 :           edge_iterator ei;
    1113                 :            : 
    1114                 :            :           /* Functions returning multiple times are not handled by extra edges.
    1115                 :            :              Instead we simply allow negative counts on edges from exit to the
    1116                 :            :              block past call and corresponding probabilities.  We can't go
    1117                 :            :              with the extra edges because that would result in flowgraph that
    1118                 :            :              needs to have fake edges outside the spanning tree.  */
    1119                 :            : 
    1120                 :      24854 :           FOR_EACH_EDGE (e, ei, bb->succs)
    1121                 :            :             {
    1122                 :      15083 :               gimple_stmt_iterator gsi;
    1123                 :      15083 :               gimple *last = NULL;
    1124                 :            : 
    1125                 :            :               /* It may happen that there are compiler generated statements
    1126                 :            :                  without a locus at all.  Go through the basic block from the
    1127                 :            :                  last to the first statement looking for a locus.  */
    1128                 :      15083 :               for (gsi = gsi_last_nondebug_bb (bb);
    1129                 :      16479 :                    !gsi_end_p (gsi);
    1130                 :      17886 :                    gsi_prev_nondebug (&gsi))
    1131                 :            :                 {
    1132                 :      15085 :                   last = gsi_stmt (gsi);
    1133                 :      15085 :                   if (!RESERVED_LOCATION_P (gimple_location (last)))
    1134                 :            :                     break;
    1135                 :            :                 }
    1136                 :            : 
    1137                 :            :               /* Edge with goto locus might get wrong coverage info unless
    1138                 :            :                  it is the only edge out of BB.
    1139                 :            :                  Don't do that when the locuses match, so
    1140                 :            :                  if (blah) goto something;
    1141                 :            :                  is not computed twice.  */
    1142                 :      15083 :               if (last
    1143                 :      14520 :                   && gimple_has_location (last)
    1144                 :      13720 :                   && !RESERVED_LOCATION_P (e->goto_locus)
    1145                 :       2579 :                   && !single_succ_p (bb)
    1146                 :      15217 :                   && (LOCATION_FILE (e->goto_locus)
    1147                 :        134 :                       != LOCATION_FILE (gimple_location (last))
    1148                 :        133 :                       || (LOCATION_LINE (e->goto_locus)
    1149                 :      15082 :                           != LOCATION_LINE (gimple_location (last)))))
    1150                 :            :                 {
    1151                 :         62 :                   basic_block new_bb = split_edge (e);
    1152                 :         62 :                   edge ne = single_succ_edge (new_bb);
    1153                 :         62 :                   ne->goto_locus = e->goto_locus;
    1154                 :            :                 }
    1155                 :      15083 :               if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
    1156                 :         47 :                    && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1157                 :         47 :                 need_exit_edge = 1;
    1158                 :      15083 :               if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1159                 :       5223 :                 have_exit_edge = 1;
    1160                 :            :             }
    1161                 :      21680 :           FOR_EACH_EDGE (e, ei, bb->preds)
    1162                 :            :             {
    1163                 :      11909 :               if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
    1164                 :         47 :                    && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1165                 :         47 :                 need_entry_edge = 1;
    1166                 :      11909 :               if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1167                 :       2047 :                 have_entry_edge = 1;
    1168                 :            :             }
    1169                 :            : 
    1170                 :       9771 :           if (need_exit_edge && !have_exit_edge)
    1171                 :            :             {
    1172                 :         14 :               if (dump_file)
    1173                 :          0 :                 fprintf (dump_file, "Adding fake exit edge to bb %i\n",
    1174                 :            :                          bb->index);
    1175                 :         14 :               make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
    1176                 :            :             }
    1177                 :       9771 :           if (need_entry_edge && !have_entry_edge)
    1178                 :            :             {
    1179                 :         31 :               if (dump_file)
    1180                 :          0 :                 fprintf (dump_file, "Adding fake entry edge to bb %i\n",
    1181                 :            :                          bb->index);
    1182                 :         31 :               make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, EDGE_FAKE);
    1183                 :            :               /* Avoid bbs that have both fake entry edge and also some
    1184                 :            :                  exit edge.  One of those edges wouldn't be added to the
    1185                 :            :                  spanning tree, but we can't instrument any of them.  */
    1186                 :         31 :               if (have_exit_edge || need_exit_edge)
    1187                 :            :                 {
    1188                 :         12 :                   gimple_stmt_iterator gsi;
    1189                 :         12 :                   gimple *first;
    1190                 :            : 
    1191                 :         12 :                   gsi = gsi_start_nondebug_after_labels_bb (bb);
    1192                 :         12 :                   gcc_checking_assert (!gsi_end_p (gsi));
    1193                 :         12 :                   first = gsi_stmt (gsi);
    1194                 :            :                   /* Don't split the bbs containing __builtin_setjmp_receiver
    1195                 :            :                      or ABNORMAL_DISPATCHER calls.  These are very
    1196                 :            :                      special and don't expect anything to be inserted before
    1197                 :            :                      them.  */
    1198                 :         12 :                   if (is_gimple_call (first)
    1199                 :         12 :                       && (gimple_call_builtin_p (first, BUILT_IN_SETJMP_RECEIVER)
    1200                 :          8 :                           || (gimple_call_flags (first) & ECF_RETURNS_TWICE)
    1201                 :          8 :                           || (gimple_call_internal_p (first)
    1202                 :          8 :                               && (gimple_call_internal_fn (first)
    1203                 :            :                                   == IFN_ABNORMAL_DISPATCHER))))
    1204                 :          8 :                     continue;
    1205                 :            : 
    1206                 :          4 :                   if (dump_file)
    1207                 :          0 :                     fprintf (dump_file, "Splitting bb %i after labels\n",
    1208                 :            :                              bb->index);
    1209                 :          4 :                   split_block_after_labels (bb);
    1210                 :            :                 }
    1211                 :            :             }
    1212                 :            :         }
    1213                 :            :     }
    1214                 :            : 
    1215                 :       2054 :   el = create_edge_list ();
    1216                 :       2054 :   num_edges = NUM_EDGES (el);
    1217                 :       2054 :   qsort (el->index_to_edge, num_edges, sizeof (edge), compare_freqs);
    1218                 :       2054 :   alloc_aux_for_edges (sizeof (struct edge_profile_info));
    1219                 :            : 
    1220                 :            :   /* The basic blocks are expected to be numbered sequentially.  */
    1221                 :       2054 :   compact_blocks ();
    1222                 :            : 
    1223                 :       2054 :   ignored_edges = 0;
    1224                 :      19255 :   for (i = 0 ; i < num_edges ; i++)
    1225                 :            :     {
    1226                 :      17201 :       edge e = INDEX_EDGE (el, i);
    1227                 :            : 
    1228                 :            :       /* Mark edges we've replaced by fake edges above as ignored.  */
    1229                 :      17201 :       if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
    1230                 :         47 :           && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
    1231                 :         47 :           && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1232                 :            :         {
    1233                 :         47 :           EDGE_INFO (e)->ignore = 1;
    1234                 :         47 :           ignored_edges++;
    1235                 :            :         }
    1236                 :            :     }
    1237                 :            : 
    1238                 :            :   /* Create spanning tree from basic block graph, mark each edge that is
    1239                 :            :      on the spanning tree.  We insert as many abnormal and critical edges
    1240                 :            :      as possible to minimize number of edge splits necessary.  */
    1241                 :            : 
    1242                 :       2054 :   if (!thunk)
    1243                 :       2047 :     find_spanning_tree (el);
    1244                 :            :   else
    1245                 :            :     {
    1246                 :          7 :       edge e;
    1247                 :          7 :       edge_iterator ei;
    1248                 :            :       /* Keep only edge from entry block to be instrumented.  */
    1249                 :         21 :       FOR_EACH_BB_FN (bb, cfun)
    1250                 :         35 :         FOR_EACH_EDGE (e, ei, bb->succs)
    1251                 :         21 :           EDGE_INFO (e)->ignore = true;
    1252                 :            :     }
    1253                 :            : 
    1254                 :            : 
    1255                 :            :   /* Fake edges that are not on the tree will not be instrumented, so
    1256                 :            :      mark them ignored.  */
    1257                 :      19255 :   for (num_instrumented = i = 0; i < num_edges; i++)
    1258                 :            :     {
    1259                 :      17201 :       edge e = INDEX_EDGE (el, i);
    1260                 :      17201 :       struct edge_profile_info *inf = EDGE_INFO (e);
    1261                 :            : 
    1262                 :      17201 :       if (inf->ignore || inf->on_tree)
    1263                 :            :         /*NOP*/;
    1264                 :       7362 :       else if (e->flags & EDGE_FAKE)
    1265                 :            :         {
    1266                 :          8 :           inf->ignore = 1;
    1267                 :          8 :           ignored_edges++;
    1268                 :            :         }
    1269                 :            :       else
    1270                 :       7354 :         num_instrumented++;
    1271                 :            :     }
    1272                 :            : 
    1273                 :       2054 :   total_num_blocks += n_basic_blocks_for_fn (cfun);
    1274                 :       2054 :   if (dump_file)
    1275                 :        137 :     fprintf (dump_file, "%d basic blocks\n", n_basic_blocks_for_fn (cfun));
    1276                 :            : 
    1277                 :       2054 :   total_num_edges += num_edges;
    1278                 :       2054 :   if (dump_file)
    1279                 :        137 :     fprintf (dump_file, "%d edges\n", num_edges);
    1280                 :            : 
    1281                 :       2054 :   total_num_edges_ignored += ignored_edges;
    1282                 :       2054 :   if (dump_file)
    1283                 :        137 :     fprintf (dump_file, "%d ignored edges\n", ignored_edges);
    1284                 :            : 
    1285                 :       2054 :   total_num_edges_instrumented += num_instrumented;
    1286                 :       2054 :   if (dump_file)
    1287                 :        137 :     fprintf (dump_file, "%d instrumentation edges\n", num_instrumented);
    1288                 :            : 
    1289                 :            :   /* Compute two different checksums. Note that we want to compute
    1290                 :            :      the checksum in only once place, since it depends on the shape
    1291                 :            :      of the control flow which can change during 
    1292                 :            :      various transformations.  */
    1293                 :       2054 :   if (thunk)
    1294                 :            :     {
    1295                 :            :       /* At stream in time we do not have CFG, so we cannot do checksums.  */
    1296                 :            :       cfg_checksum = 0;
    1297                 :            :       lineno_checksum = 0;
    1298                 :            :     }
    1299                 :            :   else
    1300                 :            :     {
    1301                 :       2047 :       cfg_checksum = coverage_compute_cfg_checksum (cfun);
    1302                 :       2047 :       lineno_checksum = coverage_compute_lineno_checksum ();
    1303                 :            :     }
    1304                 :            : 
    1305                 :            :   /* Write the data from which gcov can reconstruct the basic block
    1306                 :            :      graph and function line numbers (the gcno file).  */
    1307                 :       2054 :   if (coverage_begin_function (lineno_checksum, cfg_checksum))
    1308                 :            :     {
    1309                 :        727 :       gcov_position_t offset;
    1310                 :            : 
    1311                 :            :       /* Basic block flags */
    1312                 :        727 :       offset = gcov_write_tag (GCOV_TAG_BLOCKS);
    1313                 :        727 :       gcov_write_unsigned (n_basic_blocks_for_fn (cfun));
    1314                 :        727 :       gcov_write_length (offset);
    1315                 :            : 
    1316                 :            :       /* Arcs */
    1317                 :       4769 :       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
    1318                 :            :                       EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
    1319                 :            :         {
    1320                 :       4042 :           edge e;
    1321                 :       4042 :           edge_iterator ei;
    1322                 :            : 
    1323                 :       4042 :           offset = gcov_write_tag (GCOV_TAG_ARCS);
    1324                 :       4042 :           gcov_write_unsigned (bb->index);
    1325                 :            : 
    1326                 :       9922 :           FOR_EACH_EDGE (e, ei, bb->succs)
    1327                 :            :             {
    1328                 :       5880 :               struct edge_profile_info *i = EDGE_INFO (e);
    1329                 :       5880 :               if (!i->ignore)
    1330                 :            :                 {
    1331                 :       5866 :                   unsigned flag_bits = 0;
    1332                 :            : 
    1333                 :       5866 :                   if (i->on_tree)
    1334                 :       3315 :                     flag_bits |= GCOV_ARC_ON_TREE;
    1335                 :       5866 :                   if (e->flags & EDGE_FAKE)
    1336                 :       1360 :                     flag_bits |= GCOV_ARC_FAKE;
    1337                 :       5866 :                   if (e->flags & EDGE_FALLTHRU)
    1338                 :       2701 :                     flag_bits |= GCOV_ARC_FALLTHROUGH;
    1339                 :            :                   /* On trees we don't have fallthru flags, but we can
    1340                 :            :                      recompute them from CFG shape.  */
    1341                 :       5866 :                   if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
    1342                 :        882 :                       && e->src->next_bb == e->dest)
    1343                 :        441 :                     flag_bits |= GCOV_ARC_FALLTHROUGH;
    1344                 :            : 
    1345                 :       5866 :                   gcov_write_unsigned (e->dest->index);
    1346                 :       5866 :                   gcov_write_unsigned (flag_bits);
    1347                 :            :                 }
    1348                 :            :             }
    1349                 :            : 
    1350                 :       4042 :           gcov_write_length (offset);
    1351                 :            :         }
    1352                 :            : 
    1353                 :            :       /* Line numbers.  */
    1354                 :            :       /* Initialize the output.  */
    1355                 :        727 :       output_location (&streamed_locations, NULL, 0, NULL, NULL);
    1356                 :            : 
    1357                 :       1454 :       hash_set<int_hash <location_t, 0, 2> > seen_locations;
    1358                 :            : 
    1359                 :       4042 :       FOR_EACH_BB_FN (bb, cfun)
    1360                 :            :         {
    1361                 :       3315 :           gimple_stmt_iterator gsi;
    1362                 :       3315 :           gcov_position_t offset = 0;
    1363                 :            : 
    1364                 :       3315 :           if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
    1365                 :            :             {
    1366                 :        727 :               location_t loc = DECL_SOURCE_LOCATION (current_function_decl);
    1367                 :        727 :               seen_locations.add (loc);
    1368                 :        727 :               expanded_location curr_location = expand_location (loc);
    1369                 :        727 :               output_location (&streamed_locations, curr_location.file,
    1370                 :            :                                curr_location.line, &offset, bb);
    1371                 :            :             }
    1372                 :            : 
    1373                 :      12470 :           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1374                 :            :             {
    1375                 :       5840 :               gimple *stmt = gsi_stmt (gsi);
    1376                 :       5840 :               location_t loc = gimple_location (stmt);
    1377                 :       5840 :               if (!RESERVED_LOCATION_P (loc))
    1378                 :            :                 {
    1379                 :       4996 :                   seen_locations.add (loc);
    1380                 :       4996 :                   output_location (&streamed_locations, gimple_filename (stmt),
    1381                 :            :                                    gimple_lineno (stmt), &offset, bb);
    1382                 :            :                 }
    1383                 :            :             }
    1384                 :            : 
    1385                 :            :           /* Notice GOTO expressions eliminated while constructing the CFG.
    1386                 :            :              It's hard to distinguish such expression, but goto_locus should
    1387                 :            :              not be any of already seen location.  */
    1388                 :       3315 :           location_t loc;
    1389                 :       3315 :           if (single_succ_p (bb)
    1390                 :       1593 :               && (loc = single_succ_edge (bb)->goto_locus)
    1391                 :       1093 :               && !RESERVED_LOCATION_P (loc)
    1392                 :       4381 :               && !seen_locations.contains (loc))
    1393                 :            :             {
    1394                 :         89 :               expanded_location curr_location = expand_location (loc);
    1395                 :         89 :               output_location (&streamed_locations, curr_location.file,
    1396                 :            :                                curr_location.line, &offset, bb);
    1397                 :            :             }
    1398                 :            : 
    1399                 :       3315 :           if (offset)
    1400                 :            :             {
    1401                 :            :               /* A file of NULL indicates the end of run.  */
    1402                 :       3089 :               gcov_write_unsigned (0);
    1403                 :       3089 :               gcov_write_string (NULL);
    1404                 :       3089 :               gcov_write_length (offset);
    1405                 :            :             }
    1406                 :            :         }
    1407                 :            :     }
    1408                 :            : 
    1409                 :       2054 :   if (flag_profile_values)
    1410                 :        818 :     gimple_find_values_to_profile (&values);
    1411                 :            : 
    1412                 :       2054 :   if (flag_branch_probabilities)
    1413                 :            :     {
    1414                 :        475 :       compute_branch_probabilities (cfg_checksum, lineno_checksum);
    1415                 :        475 :       if (flag_profile_values)
    1416                 :        332 :         compute_value_histograms (values, cfg_checksum, lineno_checksum);
    1417                 :            :     }
    1418                 :            : 
    1419                 :       2054 :   remove_fake_edges ();
    1420                 :            : 
    1421                 :            :   /* For each edge not on the spanning tree, add counting code.  */
    1422                 :       2054 :   if (profile_arc_flag
    1423                 :       2054 :       && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
    1424                 :            :     {
    1425                 :       1565 :       unsigned n_instrumented;
    1426                 :            : 
    1427                 :       1565 :       gimple_init_gcov_profiler ();
    1428                 :            : 
    1429                 :       1565 :       n_instrumented = instrument_edges (el);
    1430                 :            : 
    1431                 :       1565 :       gcc_assert (n_instrumented == num_instrumented);
    1432                 :            : 
    1433                 :       1565 :       if (flag_profile_values)
    1434                 :        487 :         instrument_values (values);
    1435                 :            : 
    1436                 :            :       /* Commit changes done by instrumentation.  */
    1437                 :       1565 :       gsi_commit_edge_inserts ();
    1438                 :            :     }
    1439                 :            : 
    1440                 :       2054 :   free_aux_for_edges ();
    1441                 :            : 
    1442                 :       2054 :   values.release ();
    1443                 :       2054 :   free_edge_list (el);
    1444                 :       2054 :   coverage_end_function (lineno_checksum, cfg_checksum);
    1445                 :       2054 :   if (flag_branch_probabilities
    1446                 :        475 :       && (profile_status_for_fn (cfun) == PROFILE_READ))
    1447                 :            :     {
    1448                 :        408 :       class loop *loop;
    1449                 :        408 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1450                 :          5 :         report_predictor_hitrates ();
    1451                 :            : 
    1452                 :            :       /* At this moment we have precise loop iteration count estimates.
    1453                 :            :          Record them to loop structure before the profile gets out of date. */
    1454                 :        601 :       FOR_EACH_LOOP (loop, 0)
    1455                 :        193 :         if (loop->header->count > 0 && loop->header->count.reliable_p ())
    1456                 :            :           {
    1457                 :        164 :             gcov_type nit = expected_loop_iterations_unbounded (loop);
    1458                 :        164 :             widest_int bound = gcov_type_to_wide_int (nit);
    1459                 :        164 :             loop->any_estimate = false;
    1460                 :        164 :             record_niter_bound (loop, bound, true, false);
    1461                 :            :           }
    1462                 :        408 :       compute_function_frequency ();
    1463                 :            :     }
    1464                 :       2054 : }
    1465                 :            : 
    1466                 :            : /* Union find algorithm implementation for the basic blocks using
    1467                 :            :    aux fields.  */
    1468                 :            : 
    1469                 :            : static basic_block
    1470                 :      56598 : find_group (basic_block bb)
    1471                 :            : {
    1472                 :          0 :   basic_block group = bb, bb1;
    1473                 :            : 
    1474                 :      92079 :   while ((basic_block) group->aux != group)
    1475                 :            :     group = (basic_block) group->aux;
    1476                 :            : 
    1477                 :            :   /* Compress path.  */
    1478                 :      71888 :   while ((basic_block) bb->aux != group)
    1479                 :            :     {
    1480                 :       3472 :       bb1 = (basic_block) bb->aux;
    1481                 :       3472 :       bb->aux = (void *) group;
    1482                 :       3472 :       bb = bb1;
    1483                 :            :     }
    1484                 :      56598 :   return group;
    1485                 :            : }
    1486                 :            : 
    1487                 :            : static void
    1488                 :      11818 : union_groups (basic_block bb1, basic_block bb2)
    1489                 :            : {
    1490                 :      11818 :   basic_block bb1g = find_group (bb1);
    1491                 :      20226 :   basic_block bb2g = find_group (bb2);
    1492                 :            : 
    1493                 :            :   /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
    1494                 :            :      this code is unlikely going to be performance problem anyway.  */
    1495                 :      11818 :   gcc_assert (bb1g != bb2g);
    1496                 :            : 
    1497                 :      11818 :   bb1g->aux = bb2g;
    1498                 :      11818 : }
    1499                 :            : 
    1500                 :            : /* This function searches all of the edges in the program flow graph, and puts
    1501                 :            :    as many bad edges as possible onto the spanning tree.  Bad edges include
    1502                 :            :    abnormals edges, which can't be instrumented at the moment.  Since it is
    1503                 :            :    possible for fake edges to form a cycle, we will have to develop some
    1504                 :            :    better way in the future.  Also put critical edges to the tree, since they
    1505                 :            :    are more expensive to instrument.  */
    1506                 :            : 
    1507                 :            : static void
    1508                 :       2047 : find_spanning_tree (struct edge_list *el)
    1509                 :            : {
    1510                 :       2047 :   int i;
    1511                 :       2047 :   int num_edges = NUM_EDGES (el);
    1512                 :       2047 :   basic_block bb;
    1513                 :            : 
    1514                 :            :   /* We use aux field for standard union-find algorithm.  */
    1515                 :      15912 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
    1516                 :      13865 :     bb->aux = bb;
    1517                 :            : 
    1518                 :            :   /* Add fake edge exit to entry we can't instrument.  */
    1519                 :       2047 :   union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun), ENTRY_BLOCK_PTR_FOR_FN (cfun));
    1520                 :            : 
    1521                 :            :   /* First add all abnormal edges to the tree unless they form a cycle. Also
    1522                 :            :      add all edges to the exit block to avoid inserting profiling code behind
    1523                 :            :      setting return value from function.  */
    1524                 :      19220 :   for (i = 0; i < num_edges; i++)
    1525                 :            :     {
    1526                 :      17173 :       edge e = INDEX_EDGE (el, i);
    1527                 :      17173 :       if (((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
    1528                 :      13834 :            || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1529                 :       5311 :           && !EDGE_INFO (e)->ignore
    1530                 :      32965 :           && (find_group (e->src) != find_group (e->dest)))
    1531                 :            :         {
    1532                 :       5256 :           if (dump_file)
    1533                 :        232 :             fprintf (dump_file, "Abnormal edge %d to %d put to tree\n",
    1534                 :            :                      e->src->index, e->dest->index);
    1535                 :       5256 :           EDGE_INFO (e)->on_tree = 1;
    1536                 :       5256 :           union_groups (e->src, e->dest);
    1537                 :            :         }
    1538                 :            :     }
    1539                 :            : 
    1540                 :            :   /* And now the rest.  Edge list is sorted according to frequencies and
    1541                 :            :      thus we will produce minimal spanning tree.  */
    1542                 :      19220 :   for (i = 0; i < num_edges; i++)
    1543                 :            :     {
    1544                 :      17173 :       edge e = INDEX_EDGE (el, i);
    1545                 :      17173 :       if (!EDGE_INFO (e)->ignore
    1546                 :      51425 :           && find_group (e->src) != find_group (e->dest))
    1547                 :            :         {
    1548                 :       4515 :           if (dump_file)
    1549                 :        270 :             fprintf (dump_file, "Normal edge %d to %d put to tree\n",
    1550                 :            :                      e->src->index, e->dest->index);
    1551                 :       4515 :           EDGE_INFO (e)->on_tree = 1;
    1552                 :       4515 :           union_groups (e->src, e->dest);
    1553                 :            :         }
    1554                 :            :     }
    1555                 :            : 
    1556                 :       2047 :   clear_aux_for_blocks ();
    1557                 :       2047 : }
    1558                 :            : 
    1559                 :            : /* Perform file-level initialization for branch-prob processing.  */
    1560                 :            : 
    1561                 :            : void
    1562                 :          0 : init_branch_prob (void)
    1563                 :            : {
    1564                 :          0 :   int i;
    1565                 :            : 
    1566                 :          0 :   total_num_blocks = 0;
    1567                 :          0 :   total_num_edges = 0;
    1568                 :          0 :   total_num_edges_ignored = 0;
    1569                 :          0 :   total_num_edges_instrumented = 0;
    1570                 :          0 :   total_num_blocks_created = 0;
    1571                 :          0 :   total_num_passes = 0;
    1572                 :          0 :   total_num_times_called = 0;
    1573                 :          0 :   total_num_branches = 0;
    1574                 :          0 :   for (i = 0; i < 20; i++)
    1575                 :          0 :     total_hist_br_prob[i] = 0;
    1576                 :          0 : }
    1577                 :            : 
    1578                 :            : /* Performs file-level cleanup after branch-prob processing
    1579                 :            :    is completed.  */
    1580                 :            : 
    1581                 :            : void
    1582                 :        564 : end_branch_prob (void)
    1583                 :            : {
    1584                 :        564 :   if (dump_file)
    1585                 :            :     {
    1586                 :          0 :       fprintf (dump_file, "\n");
    1587                 :          0 :       fprintf (dump_file, "Total number of blocks: %d\n",
    1588                 :            :                total_num_blocks);
    1589                 :          0 :       fprintf (dump_file, "Total number of edges: %d\n", total_num_edges);
    1590                 :          0 :       fprintf (dump_file, "Total number of ignored edges: %d\n",
    1591                 :            :                total_num_edges_ignored);
    1592                 :          0 :       fprintf (dump_file, "Total number of instrumented edges: %d\n",
    1593                 :            :                total_num_edges_instrumented);
    1594                 :          0 :       fprintf (dump_file, "Total number of blocks created: %d\n",
    1595                 :            :                total_num_blocks_created);
    1596                 :          0 :       fprintf (dump_file, "Total number of graph solution passes: %d\n",
    1597                 :            :                total_num_passes);
    1598                 :          0 :       if (total_num_times_called != 0)
    1599                 :          0 :         fprintf (dump_file, "Average number of graph solution passes: %d\n",
    1600                 :          0 :                  (total_num_passes + (total_num_times_called  >> 1))
    1601                 :            :                  / total_num_times_called);
    1602                 :          0 :       fprintf (dump_file, "Total number of branches: %d\n",
    1603                 :            :                total_num_branches);
    1604                 :          0 :       if (total_num_branches)
    1605                 :            :         {
    1606                 :            :           int i;
    1607                 :            : 
    1608                 :          0 :           for (i = 0; i < 10; i++)
    1609                 :          0 :             fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
    1610                 :          0 :                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
    1611                 :          0 :                      / total_num_branches, 5*i, 5*i+5);
    1612                 :            :         }
    1613                 :            :     }
    1614                 :        564 : }

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.