LCOV - code coverage report
Current view: top level - gcc - tracer.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 178 179 99.4 %
Date: 2020-04-04 11:58:09 Functions: 11 11 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* The tracer pass for the GNU compiler.
       2                 :            :    Contributed by Jan Hubicka, SuSE Labs.
       3                 :            :    Adapted to work on GIMPLE instead of RTL by Robert Kidd, UIUC.
       4                 :            :    Copyright (C) 2001-2020 Free Software Foundation, Inc.
       5                 :            : 
       6                 :            :    This file is part of GCC.
       7                 :            : 
       8                 :            :    GCC is free software; you can redistribute it and/or modify it
       9                 :            :    under the terms of the GNU General Public License as published by
      10                 :            :    the Free Software Foundation; either version 3, or (at your option)
      11                 :            :    any later version.
      12                 :            : 
      13                 :            :    GCC is distributed in the hope that it will be useful, but WITHOUT
      14                 :            :    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
      15                 :            :    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
      16                 :            :    License for more details.
      17                 :            : 
      18                 :            :    You should have received a copy of the GNU General Public License
      19                 :            :    along with GCC; see the file COPYING3.  If not see
      20                 :            :    <http://www.gnu.org/licenses/>.  */
      21                 :            : 
      22                 :            : /* This pass performs the tail duplication needed for superblock formation.
      23                 :            :    For more information see:
      24                 :            : 
      25                 :            :      Design and Analysis of Profile-Based Optimization in Compaq's
      26                 :            :      Compilation Tools for Alpha; Journal of Instruction-Level
      27                 :            :      Parallelism 3 (2000) 1-25
      28                 :            : 
      29                 :            :    Unlike Compaq's implementation we don't do the loop peeling as most
      30                 :            :    probably a better job can be done by a special pass and we don't
      31                 :            :    need to worry too much about the code size implications as the tail
      32                 :            :    duplicates are crossjumped again if optimizations are not
      33                 :            :    performed.  */
      34                 :            : 
      35                 :            : 
      36                 :            : #include "config.h"
      37                 :            : #include "system.h"
      38                 :            : #include "coretypes.h"
      39                 :            : #include "backend.h"
      40                 :            : #include "rtl.h"
      41                 :            : #include "tree.h"
      42                 :            : #include "gimple.h"
      43                 :            : #include "cfghooks.h"
      44                 :            : #include "tree-pass.h"
      45                 :            : #include "profile.h"
      46                 :            : #include "cfganal.h"
      47                 :            : #include "gimple-iterator.h"
      48                 :            : #include "tree-cfg.h"
      49                 :            : #include "tree-ssa.h"
      50                 :            : #include "tree-inline.h"
      51                 :            : #include "cfgloop.h"
      52                 :            : #include "alloc-pool.h"
      53                 :            : #include "fibonacci_heap.h"
      54                 :            : #include "tracer.h"
      55                 :            : 
      56                 :            : static int count_insns (basic_block);
      57                 :            : static bool better_p (const_edge, const_edge);
      58                 :            : static edge find_best_successor (basic_block);
      59                 :            : static edge find_best_predecessor (basic_block);
      60                 :            : static int find_trace (basic_block, basic_block *);
      61                 :            : 
      62                 :            : /* Minimal outgoing edge probability considered for superblock formation.  */
      63                 :            : static int probability_cutoff;
      64                 :            : static int branch_ratio_cutoff;
      65                 :            : 
      66                 :            : /* A bit BB->index is set if BB has already been seen, i.e. it is
      67                 :            :    connected to some trace already.  */
      68                 :            : static sbitmap bb_seen;
      69                 :            : 
      70                 :            : static inline void
      71                 :            : mark_bb_seen (basic_block bb)
      72                 :            : {
      73                 :            :   unsigned int size = SBITMAP_SIZE (bb_seen);
      74                 :            : 
      75                 :            :   if ((unsigned int)bb->index >= size)
      76                 :            :     bb_seen = sbitmap_resize (bb_seen, size * 2, 0);
      77                 :            : 
      78                 :            :   bitmap_set_bit (bb_seen, bb->index);
      79                 :            : }
      80                 :            : 
      81                 :            : static inline bool
      82                 :     128097 : bb_seen_p (basic_block bb)
      83                 :            : {
      84                 :     256194 :   return bitmap_bit_p (bb_seen, bb->index);
      85                 :            : }
      86                 :            : 
      87                 :            : /* Return true if we should ignore the basic block for purposes of tracing.  */
      88                 :            : bool
      89                 :     493466 : ignore_bb_p (const_basic_block bb)
      90                 :            : {
      91                 :     493466 :   if (bb->index < NUM_FIXED_BLOCKS)
      92                 :            :     return true;
      93                 :     483609 :   if (optimize_bb_for_size_p (bb))
      94                 :            :     return true;
      95                 :            : 
      96                 :     444026 :   if (gimple *g = last_stmt (CONST_CAST_BB (bb)))
      97                 :            :     {
      98                 :            :       /* A transaction is a single entry multiple exit region.  It
      99                 :            :          must be duplicated in its entirety or not at all.  */
     100                 :     397028 :       if (gimple_code (g) == GIMPLE_TRANSACTION)
     101                 :            :         return true;
     102                 :            : 
     103                 :            :       /* An IFN_UNIQUE call must be duplicated as part of its group,
     104                 :            :          or not at all.  */
     105                 :     397028 :       if (is_gimple_call (g)
     106                 :      12358 :           && gimple_call_internal_p (g)
     107                 :     397133 :           && gimple_call_internal_unique_p (g))
     108                 :          0 :         return true;
     109                 :            :     }
     110                 :            : 
     111                 :            :   return false;
     112                 :            : }
     113                 :            : 
     114                 :            : /* Return number of instructions in the block.  */
     115                 :            : 
     116                 :            : static int
     117                 :     162636 : count_insns (basic_block bb)
     118                 :            : {
     119                 :     162636 :   gimple_stmt_iterator gsi;
     120                 :     162636 :   gimple *stmt;
     121                 :     162636 :   int n = 0;
     122                 :            : 
     123                 :    1182300 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     124                 :            :     {
     125                 :     857025 :       stmt = gsi_stmt (gsi);
     126                 :     857025 :       n += estimate_num_insns (stmt, &eni_size_weights);
     127                 :            :     }
     128                 :     162636 :   return n;
     129                 :            : }
     130                 :            : 
     131                 :            : /* Return true if E1 is more frequent than E2.  */
     132                 :            : static bool
     133                 :     137853 : better_p (const_edge e1, const_edge e2)
     134                 :            : {
     135                 :     137853 :   if ((e1->count () > e2->count ()) || (e1->count () < e2->count ()))
     136                 :     126752 :     return e1->count () > e2->count ();
     137                 :            :   /* This is needed to avoid changes in the decision after
     138                 :            :      CFG is modified.  */
     139                 :      11101 :   if (e1->src != e2->src)
     140                 :       3754 :     return e1->src->index > e2->src->index;
     141                 :       7347 :   return e1->dest->index > e2->dest->index;
     142                 :            : }
     143                 :            : 
     144                 :            : /* Return most frequent successor of basic block BB.  */
     145                 :            : 
     146                 :            : static edge
     147                 :     109466 : find_best_successor (basic_block bb)
     148                 :            : {
     149                 :     109466 :   edge e;
     150                 :     109466 :   edge best = NULL;
     151                 :     109466 :   edge_iterator ei;
     152                 :            : 
     153                 :     302397 :   FOR_EACH_EDGE (e, ei, bb->succs)
     154                 :            :     {
     155                 :     192993 :       if (!e->count ().initialized_p ())
     156                 :            :         return NULL;
     157                 :     192931 :       if (!best || better_p (e, best))
     158                 :     176124 :         best = e;
     159                 :            :     }
     160                 :     109404 :   if (!best || ignore_bb_p (best->dest))
     161                 :       6776 :     return NULL;
     162                 :     102628 :   if (!best->probability.initialized_p ()
     163                 :     102628 :       || best->probability.to_reg_br_prob_base () <= probability_cutoff)
     164                 :       6989 :     return NULL;
     165                 :            :   return best;
     166                 :            : }
     167                 :            : 
     168                 :            : /* Return most frequent predecessor of basic block BB.  */
     169                 :            : 
     170                 :            : static edge
     171                 :     106556 : find_best_predecessor (basic_block bb)
     172                 :            : {
     173                 :     106556 :   edge e;
     174                 :     106556 :   edge best = NULL;
     175                 :     106556 :   edge_iterator ei;
     176                 :            : 
     177                 :     267217 :   FOR_EACH_EDGE (e, ei, bb->preds)
     178                 :            :     {
     179                 :     160724 :       if (!e->count ().initialized_p ())
     180                 :            :         return NULL;
     181                 :     160661 :       if (!best || better_p (e, best))
     182                 :     131180 :         best = e;
     183                 :            :     }
     184                 :     106493 :   if (!best || ignore_bb_p (best->src))
     185                 :       6608 :     return NULL;
     186                 :      99885 :   if (bb->count.initialized_p ()
     187                 :     199397 :       && (best->count ().to_frequency (cfun) * REG_BR_PROB_BASE
     188                 :      99884 :           < bb->count.to_frequency (cfun) * branch_ratio_cutoff))
     189                 :        372 :     return NULL;
     190                 :            :   return best;
     191                 :            : }
     192                 :            : 
     193                 :            : /* Find the trace using bb and record it in the TRACE array.
     194                 :            :    Return number of basic blocks recorded.  */
     195                 :            : 
     196                 :            : static int
     197                 :      20640 : find_trace (basic_block bb, basic_block *trace)
     198                 :            : {
     199                 :      20640 :   int i = 0;
     200                 :      20640 :   edge e;
     201                 :            : 
     202                 :      20640 :   if (dump_file)
     203                 :         17 :     fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->count.to_frequency (cfun));
     204                 :            : 
     205                 :      36270 :   while ((e = find_best_predecessor (bb)) != NULL)
     206                 :            :     {
     207                 :      29272 :       basic_block bb2 = e->src;
     208                 :      56867 :       if (bb_seen_p (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
     209                 :      49814 :           || find_best_successor (bb2) != e)
     210                 :            :         break;
     211                 :      15630 :       if (dump_file)
     212                 :         15 :         fprintf (dump_file, ",%i [%i]", bb->index, bb->count.to_frequency (cfun));
     213                 :            :       bb = bb2;
     214                 :            :     }
     215                 :      20640 :   if (dump_file)
     216                 :         17 :     fprintf (dump_file, " forward %i [%i]", bb->index, bb->count.to_frequency (cfun));
     217                 :      20640 :   trace[i++] = bb;
     218                 :            : 
     219                 :            :   /* Follow the trace in forward direction.  */
     220                 :      88924 :   while ((e = find_best_successor (bb)) != NULL)
     221                 :            :     {
     222                 :      78185 :       bb = e->dest;
     223                 :     156310 :       if (bb_seen_p (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
     224                 :     148471 :           || find_best_predecessor (bb) != e)
     225                 :            :         break;
     226                 :      68284 :       if (dump_file)
     227                 :         28 :         fprintf (dump_file, ",%i [%i]", bb->index, bb->count.to_frequency (cfun));
     228                 :      68284 :       trace[i++] = bb;
     229                 :            :     }
     230                 :      20640 :   if (dump_file)
     231                 :         17 :     fprintf (dump_file, "\n");
     232                 :      20640 :   return i;
     233                 :            : }
     234                 :            : 
     235                 :            : /* Duplicate block BB2, placing it after BB in the CFG.  Return the
     236                 :            :    newly created block.  */
     237                 :            : basic_block
     238                 :      18587 : transform_duplicate (basic_block bb, basic_block bb2)
     239                 :            : {
     240                 :      18587 :   edge e;
     241                 :      18587 :   basic_block copy;
     242                 :            : 
     243                 :      18587 :   e = find_edge (bb, bb2);
     244                 :            : 
     245                 :      18587 :   copy = duplicate_block (bb2, e, bb);
     246                 :      18587 :   flush_pending_stmts (e);
     247                 :            : 
     248                 :      18587 :   add_phi_args_after_copy (&copy, 1, NULL);
     249                 :            : 
     250                 :      18587 :   return (copy);
     251                 :            : }
     252                 :            : 
     253                 :            : /* Look for basic blocks in frequency order, construct traces and tail duplicate
     254                 :            :    if profitable.  */
     255                 :            : 
     256                 :            : static bool
     257                 :       7944 : tail_duplicate (void)
     258                 :            : {
     259                 :       7944 :   auto_vec<fibonacci_node<long, basic_block_def>*> blocks;
     260                 :       7944 :   blocks.safe_grow_cleared (last_basic_block_for_fn (cfun));
     261                 :            : 
     262                 :       7944 :   basic_block *trace = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
     263                 :       7944 :   int *counts = XNEWVEC (int, last_basic_block_for_fn (cfun));
     264                 :       7944 :   int ninsns = 0, nduplicated = 0;
     265                 :       7944 :   gcov_type weighted_insns = 0, traced_insns = 0;
     266                 :      15888 :   fibonacci_heap<long, basic_block_def> heap (LONG_MIN);
     267                 :       7944 :   gcov_type cover_insns;
     268                 :       7944 :   int max_dup_insns;
     269                 :       7944 :   basic_block bb;
     270                 :       7944 :   bool changed = false;
     271                 :            : 
     272                 :            :   /* Create an oversized sbitmap to reduce the chance that we need to
     273                 :            :      resize it.  */
     274                 :       7944 :   bb_seen = sbitmap_alloc (last_basic_block_for_fn (cfun) * 2);
     275                 :       7944 :   bitmap_clear (bb_seen);
     276                 :       7944 :   initialize_original_copy_tables ();
     277                 :            : 
     278                 :       7944 :   if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ)
     279                 :        135 :     probability_cutoff = param_tracer_min_branch_probability_feedback;
     280                 :            :   else
     281                 :       7809 :     probability_cutoff = param_tracer_min_branch_probability;
     282                 :       7944 :   probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
     283                 :            : 
     284                 :       7944 :   branch_ratio_cutoff =
     285                 :       7944 :     (REG_BR_PROB_BASE / 100 * param_tracer_min_branch_ratio);
     286                 :            : 
     287                 :     170580 :   FOR_EACH_BB_FN (bb, cfun)
     288                 :            :     {
     289                 :     162636 :       int n = count_insns (bb);
     290                 :     162636 :       if (!ignore_bb_p (bb))
     291                 :     127716 :         blocks[bb->index] = heap.insert (-bb->count.to_frequency (cfun), bb);
     292                 :            : 
     293                 :     162636 :       counts [bb->index] = n;
     294                 :     162636 :       ninsns += n;
     295                 :     162636 :       weighted_insns += n * bb->count.to_frequency (cfun);
     296                 :            :     }
     297                 :            : 
     298                 :       7944 :   if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ)
     299                 :        135 :     cover_insns = param_tracer_dynamic_coverage_feedback;
     300                 :            :   else
     301                 :       7809 :     cover_insns = param_tracer_dynamic_coverage;
     302                 :       7944 :   cover_insns = (weighted_insns * cover_insns + 50) / 100;
     303                 :       7944 :   max_dup_insns = (ninsns * param_tracer_max_code_growth + 50) / 100;
     304                 :            : 
     305                 :      29140 :   while (traced_insns < cover_insns && nduplicated < max_dup_insns
     306                 :      29140 :          && !heap.empty ())
     307                 :            :     {
     308                 :      21196 :       basic_block bb = heap.extract_min ();
     309                 :      21196 :       int n, pos;
     310                 :            : 
     311                 :      21196 :       if (!bb)
     312                 :            :         break;
     313                 :            : 
     314                 :      21196 :       blocks[bb->index] = NULL;
     315                 :            : 
     316                 :      21196 :       if (ignore_bb_p (bb))
     317                 :        556 :         continue;
     318                 :      20640 :       gcc_assert (!bb_seen_p (bb));
     319                 :            : 
     320                 :      20640 :       n = find_trace (bb, trace);
     321                 :            : 
     322                 :      20640 :       bb = trace[0];
     323                 :      20640 :       traced_insns += bb->count.to_frequency (cfun) * counts [bb->index];
     324                 :      20640 :       if (blocks[bb->index])
     325                 :            :         {
     326                 :       4380 :           heap.delete_node (blocks[bb->index]);
     327                 :       4380 :           blocks[bb->index] = NULL;
     328                 :            :         }
     329                 :            : 
     330                 :      79320 :       for (pos = 1; pos < n; pos++)
     331                 :            :         {
     332                 :      59358 :           basic_block bb2 = trace[pos];
     333                 :            : 
     334                 :      59358 :           if (blocks[bb2->index])
     335                 :            :             {
     336                 :      55046 :               heap.delete_node (blocks[bb2->index]);
     337                 :      55046 :               blocks[bb2->index] = NULL;
     338                 :            :             }
     339                 :      59358 :           traced_insns += bb2->count.to_frequency (cfun) * counts [bb2->index];
     340                 :      59358 :           if (EDGE_COUNT (bb2->preds) > 1
     341                 :      19271 :               && can_duplicate_block_p (bb2)
     342                 :            :               /* We have the tendency to duplicate the loop header
     343                 :            :                  of all do { } while loops.  Do not do that - it is
     344                 :            :                  not profitable and it might create a loop with multiple
     345                 :            :                  entries or at least rotate the loop.  */
     346                 :      78629 :               && bb2->loop_father->header != bb2)
     347                 :            :             {
     348                 :      17698 :               nduplicated += counts [bb2->index];
     349                 :      17698 :               basic_block copy = transform_duplicate (bb, bb2);
     350                 :            : 
     351                 :            :               /* Reconsider the original copy of block we've duplicated.
     352                 :            :                  Removing the most common predecessor may make it to be
     353                 :            :                  head.  */
     354                 :      17698 :               blocks[bb2->index] = heap.insert (-bb2->count.to_frequency (cfun), bb2);
     355                 :            : 
     356                 :      17698 :               if (dump_file)
     357                 :         11 :                 fprintf (dump_file, "Duplicated %i as %i [%i]\n",
     358                 :            :                          bb2->index, copy->index, copy->count.to_frequency (cfun));
     359                 :            : 
     360                 :            :               bb2 = copy;
     361                 :            :               changed = true;
     362                 :            :             }
     363                 :      59358 :           mark_bb_seen (bb2);
     364                 :      59358 :           bb = bb2;
     365                 :            :           /* In case the trace became infrequent, stop duplicating.  */
     366                 :      59358 :           if (ignore_bb_p (bb))
     367                 :            :             break;
     368                 :            :         }
     369                 :      20640 :       if (dump_file)
     370                 :         17 :         fprintf (dump_file, " covered now %.1f\n\n",
     371                 :         17 :                  traced_insns * 100.0 / weighted_insns);
     372                 :            :     }
     373                 :       7944 :   if (dump_file)
     374                 :         10 :     fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
     375                 :         10 :              nduplicated * 100 / ninsns);
     376                 :            : 
     377                 :       7944 :   free_original_copy_tables ();
     378                 :       7944 :   sbitmap_free (bb_seen);
     379                 :       7944 :   free (trace);
     380                 :       7944 :   free (counts);
     381                 :            : 
     382                 :       7944 :   return changed;
     383                 :            : }
     384                 :            : 
     385                 :            : namespace {
     386                 :            : 
     387                 :            : const pass_data pass_data_tracer =
     388                 :            : {
     389                 :            :   GIMPLE_PASS, /* type */
     390                 :            :   "tracer", /* name */
     391                 :            :   OPTGROUP_NONE, /* optinfo_flags */
     392                 :            :   TV_TRACER, /* tv_id */
     393                 :            :   0, /* properties_required */
     394                 :            :   0, /* properties_provided */
     395                 :            :   0, /* properties_destroyed */
     396                 :            :   0, /* todo_flags_start */
     397                 :            :   TODO_update_ssa, /* todo_flags_finish */
     398                 :            : };
     399                 :            : 
     400                 :            : class pass_tracer : public gimple_opt_pass
     401                 :            : {
     402                 :            : public:
     403                 :     200773 :   pass_tracer (gcc::context *ctxt)
     404                 :     401546 :     : gimple_opt_pass (pass_data_tracer, ctxt)
     405                 :            :   {}
     406                 :            : 
     407                 :            :   /* opt_pass methods: */
     408                 :     686787 :   virtual bool gate (function *)
     409                 :            :     {
     410                 :     686787 :       return (optimize > 0 && flag_tracer && flag_reorder_blocks);
     411                 :            :     }
     412                 :            : 
     413                 :            :   virtual unsigned int execute (function *);
     414                 :            : 
     415                 :            : }; // class pass_tracer
     416                 :            : 
     417                 :            : unsigned int
     418                 :      13964 : pass_tracer::execute (function *fun)
     419                 :            : {
     420                 :      13964 :   bool changed;
     421                 :            : 
     422                 :      13964 :   if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1)
     423                 :            :     return 0;
     424                 :            : 
     425                 :       7944 :   mark_dfs_back_edges ();
     426                 :       7944 :   if (dump_file)
     427                 :         10 :     brief_dump_cfg (dump_file, dump_flags);
     428                 :            : 
     429                 :            :   /* Trace formation is done on the fly inside tail_duplicate */
     430                 :       7944 :   changed = tail_duplicate ();
     431                 :       7944 :   if (changed)
     432                 :            :     {
     433                 :       2987 :       free_dominance_info (CDI_DOMINATORS);
     434                 :            :       /* If we changed the CFG schedule loops for fixup by cleanup_cfg.  */
     435                 :       2987 :       loops_state_set (LOOPS_NEED_FIXUP);
     436                 :            :     }
     437                 :            : 
     438                 :       7944 :   if (dump_file)
     439                 :         10 :     brief_dump_cfg (dump_file, dump_flags);
     440                 :            : 
     441                 :       7944 :   return changed ? TODO_cleanup_cfg : 0;
     442                 :            : }
     443                 :            : } // anon namespace
     444                 :            : 
     445                 :            : gimple_opt_pass *
     446                 :     200773 : make_pass_tracer (gcc::context *ctxt)
     447                 :            : {
     448                 :     200773 :   return new pass_tracer (ctxt);
     449                 :            : }

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.