LCOV - code coverage report
Current view: top level - gcc - tree-ssa-sink.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 224 224 100.0 %
Date: 2020-03-28 11:57:23 Functions: 9 9 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Code sinking for trees
       2                 :            :    Copyright (C) 2001-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Daniel Berlin <dan@dberlin.org>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify
       8                 :            : it under the terms of the GNU General Public License as published by
       9                 :            : the Free Software Foundation; either version 3, or (at your option)
      10                 :            : any later version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful,
      13                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            : GNU General Public License for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "backend.h"
      25                 :            : #include "tree.h"
      26                 :            : #include "gimple.h"
      27                 :            : #include "cfghooks.h"
      28                 :            : #include "tree-pass.h"
      29                 :            : #include "ssa.h"
      30                 :            : #include "gimple-pretty-print.h"
      31                 :            : #include "fold-const.h"
      32                 :            : #include "stor-layout.h"
      33                 :            : #include "cfganal.h"
      34                 :            : #include "gimple-iterator.h"
      35                 :            : #include "tree-cfg.h"
      36                 :            : #include "cfgloop.h"
      37                 :            : 
      38                 :            : /* TODO:
      39                 :            :    1. Sinking store only using scalar promotion (IE without moving the RHS):
      40                 :            : 
      41                 :            :    *q = p;
      42                 :            :    p = p + 1;
      43                 :            :    if (something)
      44                 :            :      *q = <not p>;
      45                 :            :    else
      46                 :            :      y = *q;
      47                 :            : 
      48                 :            : 
      49                 :            :    should become
      50                 :            :    sinktemp = p;
      51                 :            :    p = p + 1;
      52                 :            :    if (something)
      53                 :            :      *q = <not p>;
      54                 :            :    else
      55                 :            :    {
      56                 :            :      *q = sinktemp;
      57                 :            :      y = *q
      58                 :            :    }
      59                 :            :    Store copy propagation will take care of the store elimination above.
      60                 :            : 
      61                 :            : 
      62                 :            :    2. Sinking using Partial Dead Code Elimination.  */
      63                 :            : 
      64                 :            : 
      65                 :            : static struct
      66                 :            : {
      67                 :            :   /* The number of statements sunk down the flowgraph by code sinking.  */
      68                 :            :   int sunk;
      69                 :            : 
      70                 :            : } sink_stats;
      71                 :            : 
      72                 :            : 
      73                 :            : /* Given a PHI, and one of its arguments (DEF), find the edge for
      74                 :            :    that argument and return it.  If the argument occurs twice in the PHI node,
      75                 :            :    we return NULL.  */
      76                 :            : 
      77                 :            : static basic_block
      78                 :     128998 : find_bb_for_arg (gphi *phi, tree def)
      79                 :            : {
      80                 :     128998 :   size_t i;
      81                 :     128998 :   bool foundone = false;
      82                 :     128998 :   basic_block result = NULL;
      83                 :     407823 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
      84                 :     283270 :     if (PHI_ARG_DEF (phi, i) == def)
      85                 :            :       {
      86                 :     133443 :         if (foundone)
      87                 :            :           return NULL;
      88                 :     128998 :         foundone = true;
      89                 :     128998 :         result = gimple_phi_arg_edge (phi, i)->src;
      90                 :            :       }
      91                 :            :   return result;
      92                 :            : }
      93                 :            : 
      94                 :            : /* When the first immediate use is in a statement, then return true if all
      95                 :            :    immediate uses in IMM are in the same statement.
      96                 :            :    We could also do the case where  the first immediate use is in a phi node,
      97                 :            :    and all the other uses are in phis in the same basic block, but this
      98                 :            :    requires some expensive checking later (you have to make sure no def/vdef
      99                 :            :    in the statement occurs for multiple edges in the various phi nodes it's
     100                 :            :    used in, so that you only have one place you can sink it to.  */
     101                 :            : 
     102                 :            : static bool
     103                 :    3676100 : all_immediate_uses_same_place (def_operand_p def_p)
     104                 :            : {
     105                 :    3676100 :   tree var = DEF_FROM_PTR (def_p);
     106                 :    3676100 :   imm_use_iterator imm_iter;
     107                 :    3676100 :   use_operand_p use_p;
     108                 :            : 
     109                 :    3676100 :   gimple *firstuse = NULL;
     110                 :    7996320 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
     111                 :            :     {
     112                 :    5329100 :       if (is_gimple_debug (USE_STMT (use_p)))
     113                 :     620451 :         continue;
     114                 :    4708650 :       if (firstuse == NULL)
     115                 :            :         firstuse = USE_STMT (use_p);
     116                 :            :       else
     117                 :    1032550 :         if (firstuse != USE_STMT (use_p))
     118                 :            :           return false;
     119                 :            :     }
     120                 :            : 
     121                 :            :   return true;
     122                 :            : }
     123                 :            : 
     124                 :            : /* Find the nearest common dominator of all of the immediate uses in IMM.  */
     125                 :            : 
     126                 :            : static basic_block
     127                 :    3672310 : nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
     128                 :            : {
     129                 :    3672310 :   tree var = DEF_FROM_PTR (def_p);
     130                 :    3672310 :   auto_bitmap blocks;
     131                 :    3672310 :   basic_block commondom;
     132                 :    3672310 :   unsigned int j;
     133                 :    3672310 :   bitmap_iterator bi;
     134                 :    3672310 :   imm_use_iterator imm_iter;
     135                 :    3672310 :   use_operand_p use_p;
     136                 :            : 
     137                 :   12809500 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
     138                 :            :     {
     139                 :    9137180 :       gimple *usestmt = USE_STMT (use_p);
     140                 :    9137180 :       basic_block useblock;
     141                 :            : 
     142                 :    9137180 :       if (gphi *phi = dyn_cast <gphi *> (usestmt))
     143                 :            :         {
     144                 :     941887 :           int idx = PHI_ARG_INDEX_FROM_USE (use_p);
     145                 :            : 
     146                 :     941887 :           useblock = gimple_phi_arg_edge (phi, idx)->src;
     147                 :            :         }
     148                 :    8195300 :       else if (is_gimple_debug (usestmt))
     149                 :            :         {
     150                 :    1916620 :           *debug_stmts = true;
     151                 :    1916620 :           continue;
     152                 :            :         }
     153                 :            :       else
     154                 :            :         {
     155                 :    6278680 :           useblock = gimple_bb (usestmt);
     156                 :            :         }
     157                 :            : 
     158                 :            :       /* Short circuit. Nothing dominates the entry block.  */
     159                 :    7220560 :       if (useblock == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     160                 :            :         return NULL;
     161                 :            : 
     162                 :    7220560 :       bitmap_set_bit (blocks, useblock->index);
     163                 :            :     }
     164                 :    3672310 :   commondom = BASIC_BLOCK_FOR_FN (cfun, bitmap_first_set_bit (blocks));
     165                 :   10020600 :   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
     166                 :    6348310 :     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
     167                 :    6348310 :                                           BASIC_BLOCK_FOR_FN (cfun, j));
     168                 :            :   return commondom;
     169                 :            : }
     170                 :            : 
     171                 :            : /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
     172                 :            :    tree, return the best basic block between them (inclusive) to place
     173                 :            :    statements.
     174                 :            : 
     175                 :            :    We want the most control dependent block in the shallowest loop nest.
     176                 :            : 
     177                 :            :    If the resulting block is in a shallower loop nest, then use it.  Else
     178                 :            :    only use the resulting block if it has significantly lower execution
     179                 :            :    frequency than EARLY_BB to avoid gratuitous statement movement.  We
     180                 :            :    consider statements with VOPS more desirable to move.
     181                 :            : 
     182                 :            :    This pass would obviously benefit from PDO as it utilizes block
     183                 :            :    frequencies.  It would also benefit from recomputing frequencies
     184                 :            :    if profile data is not available since frequencies often get out
     185                 :            :    of sync with reality.  */
     186                 :            : 
     187                 :            : static basic_block
     188                 :    2946070 : select_best_block (basic_block early_bb,
     189                 :            :                    basic_block late_bb,
     190                 :            :                    gimple *stmt)
     191                 :            : {
     192                 :    2946070 :   basic_block best_bb = late_bb;
     193                 :    2946070 :   basic_block temp_bb = late_bb;
     194                 :    3761120 :   int threshold;
     195                 :            : 
     196                 :    3761120 :   while (temp_bb != early_bb)
     197                 :            :     {
     198                 :            :       /* If we've moved into a lower loop nest, then that becomes
     199                 :            :          our best block.  */
     200                 :     815049 :       if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
     201                 :      34632 :         best_bb = temp_bb;
     202                 :            : 
     203                 :            :       /* Walk up the dominator tree, hopefully we'll find a shallower
     204                 :            :          loop nest.  */
     205                 :     815049 :       temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
     206                 :            :     }
     207                 :            : 
     208                 :            :   /* If we found a shallower loop nest, then we always consider that
     209                 :            :      a win.  This will always give us the most control dependent block
     210                 :            :      within that loop nest.  */
     211                 :    2946070 :   if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb))
     212                 :            :     return best_bb;
     213                 :            : 
     214                 :            :   /* Get the sinking threshold.  If the statement to be moved has memory
     215                 :            :      operands, then increase the threshold by 7% as those are even more
     216                 :            :      profitable to avoid, clamping at 100%.  */
     217                 :    2933930 :   threshold = param_sink_frequency_threshold;
     218                 :    8577830 :   if (gimple_vuse (stmt) || gimple_vdef (stmt))
     219                 :            :     {
     220                 :     223954 :       threshold += 7;
     221                 :     223954 :       if (threshold > 100)
     222                 :            :         threshold = 100;
     223                 :            :     }
     224                 :            : 
     225                 :            :   /* If BEST_BB is at the same nesting level, then require it to have
     226                 :            :      significantly lower execution frequency to avoid gratuitous movement.  */
     227                 :    2933930 :   if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
     228                 :            :       /* If result of comparsion is unknown, prefer EARLY_BB.
     229                 :            :          Thus use !(...>=..) rather than (...<...)  */
     230                 :    8626220 :       && !(best_bb->count.apply_scale (100, 1)
     231                 :    8415990 :            >= early_bb->count.apply_scale (threshold, 1)))
     232                 :     210234 :     return best_bb;
     233                 :            : 
     234                 :            :   /* No better block found, so return EARLY_BB, which happens to be the
     235                 :            :      statement's original block.  */
     236                 :            :   return early_bb;
     237                 :            : }
     238                 :            : 
     239                 :            : /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
     240                 :            :    determine the location to sink the statement to, if any.
     241                 :            :    Returns true if there is such location; in that case, TOGSI points to the
     242                 :            :    statement before that STMT should be moved.  */
     243                 :            : 
     244                 :            : static bool
     245                 :   36802700 : statement_sink_location (gimple *stmt, basic_block frombb,
     246                 :            :                          gimple_stmt_iterator *togsi, bool *zero_uses_p)
     247                 :            : {
     248                 :   36802700 :   gimple *use;
     249                 :   36802700 :   use_operand_p one_use = NULL_USE_OPERAND_P;
     250                 :   36802700 :   basic_block sinkbb;
     251                 :   36802700 :   use_operand_p use_p;
     252                 :   36802700 :   def_operand_p def_p;
     253                 :   36802700 :   ssa_op_iter iter;
     254                 :   36802700 :   imm_use_iterator imm_iter;
     255                 :            : 
     256                 :   36802700 :   *zero_uses_p = false;
     257                 :            : 
     258                 :            :   /* We only can sink assignments and non-looping const/pure calls.  */
     259                 :   36802700 :   int cf;
     260                 :   36802700 :   if (!is_gimple_assign (stmt)
     261                 :   36802700 :       && (!is_gimple_call (stmt)
     262                 :    1805900 :           || !((cf = gimple_call_flags (stmt)) & (ECF_CONST|ECF_PURE))
     263                 :     243797 :           || (cf & ECF_LOOPING_CONST_OR_PURE)))
     264                 :   26457500 :     return false;
     265                 :            : 
     266                 :            :   /* We only can sink stmts with a single definition.  */
     267                 :   10345200 :   def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
     268                 :   10345200 :   if (def_p == NULL_DEF_OPERAND_P)
     269                 :            :     return false;
     270                 :            : 
     271                 :            :   /* There are a few classes of things we can't or don't move, some because we
     272                 :            :      don't have code to handle it, some because it's not profitable and some
     273                 :            :      because it's not legal.
     274                 :            : 
     275                 :            :      We can't sink things that may be global stores, at least not without
     276                 :            :      calculating a lot more information, because we may cause it to no longer
     277                 :            :      be seen by an external routine that needs it depending on where it gets
     278                 :            :      moved to.
     279                 :            : 
     280                 :            :      We can't sink statements that end basic blocks without splitting the
     281                 :            :      incoming edge for the sink location to place it there.
     282                 :            : 
     283                 :            :      We can't sink statements that have volatile operands.
     284                 :            : 
     285                 :            :      We don't want to sink dead code, so anything with 0 immediate uses is not
     286                 :            :      sunk.
     287                 :            : 
     288                 :            :      Don't sink BLKmode assignments if current function has any local explicit
     289                 :            :      register variables, as BLKmode assignments may involve memcpy or memset
     290                 :            :      calls or, on some targets, inline expansion thereof that sometimes need
     291                 :            :      to use specific hard registers.
     292                 :            : 
     293                 :            :   */
     294                 :   10345200 :   if (stmt_ends_bb_p (stmt)
     295                 :   10273200 :       || gimple_has_side_effects (stmt)
     296                 :   10345200 :       || (cfun->has_local_explicit_reg_vars
     297                 :    9383160 :           && TYPE_MODE (TREE_TYPE (gimple_get_lhs (stmt))) == BLKmode))
     298                 :     962050 :     return false;
     299                 :            : 
     300                 :            :   /* Return if there are no immediate uses of this stmt.  */
     301                 :    9383160 :   if (has_zero_uses (DEF_FROM_PTR (def_p)))
     302                 :            :     {
     303                 :      72294 :       *zero_uses_p = true;
     304                 :      72294 :       return false;
     305                 :            :     }
     306                 :            : 
     307                 :    9310870 :   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
     308                 :            :     return false;
     309                 :            : 
     310                 :   22775200 :   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
     311                 :            :     {
     312                 :   13465100 :       tree use = USE_FROM_PTR (use_p);
     313                 :   13465100 :       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
     314                 :            :         return false;
     315                 :            :     }
     316                 :            : 
     317                 :    9310050 :   use = NULL;
     318                 :            : 
     319                 :            :   /* If stmt is a store the one and only use needs to be the VOP
     320                 :            :      merging PHI node.  */
     321                 :   18620100 :   if (virtual_operand_p (DEF_FROM_PTR (def_p)))
     322                 :            :     {
     323                 :    3260380 :       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
     324                 :            :         {
     325                 :    3231240 :           gimple *use_stmt = USE_STMT (use_p);
     326                 :            : 
     327                 :            :           /* A killing definition is not a use.  */
     328                 :    3231240 :           if ((gimple_has_lhs (use_stmt)
     329                 :    2588570 :                && operand_equal_p (gimple_get_lhs (stmt),
     330                 :    2588570 :                                    gimple_get_lhs (use_stmt), 0))
     331                 :    3454760 :               || stmt_kills_ref_p (use_stmt, gimple_get_lhs (stmt)))
     332                 :            :             {
     333                 :            :               /* If use_stmt is or might be a nop assignment then USE_STMT
     334                 :            :                  acts as a use as well as definition.  */
     335                 :       9407 :               if (stmt != use_stmt
     336                 :       9407 :                   && ref_maybe_used_by_stmt_p (use_stmt,
     337                 :            :                                                gimple_get_lhs (stmt)))
     338                 :            :                 return false;
     339                 :       9361 :               continue;
     340                 :            :             }
     341                 :            : 
     342                 :    3221840 :           if (gimple_code (use_stmt) != GIMPLE_PHI)
     343                 :            :             return false;
     344                 :            : 
     345                 :     397883 :           if (use
     346                 :     397883 :               && use != use_stmt)
     347                 :            :             return false;
     348                 :            : 
     349                 :            :           use = use_stmt;
     350                 :            :         }
     351                 :      29140 :       if (!use)
     352                 :            :         return false;
     353                 :            :     }
     354                 :            :   /* If all the immediate uses are not in the same place, find the nearest
     355                 :            :      common dominator of all the immediate uses.  For PHI nodes, we have to
     356                 :            :      find the nearest common dominator of all of the predecessor blocks, since
     357                 :            :      that is where insertion would have to take place.  */
     358                 :    6339530 :   else if (gimple_vuse (stmt)
     359                 :    6339530 :            || !all_immediate_uses_same_place (def_p))
     360                 :            :     {
     361                 :    3672310 :       bool debug_stmts = false;
     362                 :    3672310 :       basic_block commondom = nearest_common_dominator_of_uses (def_p,
     363                 :            :                                                                 &debug_stmts);
     364                 :            : 
     365                 :    3672310 :       if (commondom == frombb)
     366                 :            :         return false;
     367                 :            : 
     368                 :            :       /* If this is a load then do not sink past any stores.
     369                 :            :          ???  This is overly simple but cheap.  We basically look
     370                 :            :          for an existing load with the same VUSE in the path to one
     371                 :            :          of the sink candidate blocks and we adjust commondom to the
     372                 :            :          nearest to commondom.  */
     373                 :     790398 :       if (gimple_vuse (stmt))
     374                 :            :         {
     375                 :            :           /* Do not sink loads from hard registers.  */
     376                 :     678971 :           if (gimple_assign_single_p (stmt)
     377                 :     338977 :               && TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
     378                 :       7668 :               && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
     379                 :     139387 :             return false;
     380                 :            : 
     381                 :     339993 :           imm_use_iterator imm_iter;
     382                 :     339993 :           use_operand_p use_p;
     383                 :     339993 :           basic_block found = NULL;
     384                 :    1959120 :           FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vuse (stmt))
     385                 :            :             {
     386                 :    1778580 :               gimple *use_stmt = USE_STMT (use_p);
     387                 :    1778580 :               basic_block bb = gimple_bb (use_stmt);
     388                 :            :               /* For PHI nodes the block we know sth about
     389                 :            :                  is the incoming block with the use.  */
     390                 :    1778580 :               if (gimple_code (use_stmt) == GIMPLE_PHI)
     391                 :     296372 :                 bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src;
     392                 :            :               /* Any dominator of commondom would be ok with
     393                 :            :                  adjusting commondom to that block.  */
     394                 :    1778580 :               bb = nearest_common_dominator (CDI_DOMINATORS, bb, commondom);
     395                 :    1778580 :               if (!found)
     396                 :            :                 found = bb;
     397                 :    1438580 :               else if (dominated_by_p (CDI_DOMINATORS, bb, found))
     398                 :    1086740 :                 found = bb;
     399                 :            :               /* If we can't improve, stop.  */
     400                 :    1778580 :               if (found == commondom)
     401                 :            :                 break;
     402                 :            :             }
     403                 :     339993 :           commondom = found;
     404                 :     339993 :           if (commondom == frombb)
     405                 :            :             return false;
     406                 :            :         }
     407                 :            : 
     408                 :            :       /* Our common dominator has to be dominated by frombb in order to be a
     409                 :            :          trivially safe place to put this statement, since it has multiple
     410                 :            :          uses.  */
     411                 :     255812 :       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
     412                 :            :         return false;
     413                 :            : 
     414                 :     255812 :       commondom = select_best_block (frombb, commondom, stmt);
     415                 :            : 
     416                 :     255812 :       if (commondom == frombb)
     417                 :            :         return false;   
     418                 :            : 
     419                 :     118519 :       *togsi = gsi_after_labels (commondom);
     420                 :            : 
     421                 :     118519 :       return true;
     422                 :            :     }
     423                 :            :   else
     424                 :            :     {
     425                 :    2812890 :       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
     426                 :            :         {
     427                 :    2812890 :           if (is_gimple_debug (USE_STMT (one_use)))
     428                 :     145669 :             continue;
     429                 :            :           break;
     430                 :            :         }
     431                 :    2667220 :       use = USE_STMT (one_use);
     432                 :            : 
     433                 :    2667220 :       if (gimple_code (use) != GIMPLE_PHI)
     434                 :            :         {
     435                 :    2565710 :           sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
     436                 :            : 
     437                 :    2565710 :           if (sinkbb == frombb)
     438                 :            :             return false;
     439                 :            : 
     440                 :      83358 :           if (sinkbb == gimple_bb (use))
     441                 :      82138 :             *togsi = gsi_for_stmt (use);
     442                 :            :           else
     443                 :       2440 :             *togsi = gsi_after_labels (sinkbb);
     444                 :            : 
     445                 :      83358 :           return true;
     446                 :            :         }
     447                 :            :     }
     448                 :            : 
     449                 :     128998 :   sinkbb = find_bb_for_arg (as_a <gphi *> (use), DEF_FROM_PTR (def_p));
     450                 :            : 
     451                 :            :   /* This can happen if there are multiple uses in a PHI.  */
     452                 :     128998 :   if (!sinkbb)
     453                 :            :     return false;
     454                 :            :   
     455                 :     124553 :   sinkbb = select_best_block (frombb, sinkbb, stmt);
     456                 :     124553 :   if (!sinkbb || sinkbb == frombb)
     457                 :            :     return false;
     458                 :            : 
     459                 :            :   /* If the latch block is empty, don't make it non-empty by sinking
     460                 :            :      something into it.  */
     461                 :      20168 :   if (sinkbb == frombb->loop_father->latch
     462                 :      20168 :       && empty_block_p (sinkbb))
     463                 :            :     return false;
     464                 :            : 
     465                 :      14918 :   *togsi = gsi_after_labels (sinkbb);
     466                 :            : 
     467                 :      14918 :   return true;
     468                 :            : }
     469                 :            : 
     470                 :            : /* Perform code sinking on BB */
     471                 :            : 
     472                 :            : static void
     473                 :    9623350 : sink_code_in_bb (basic_block bb)
     474                 :            : {
     475                 :    9623350 :   basic_block son;
     476                 :    9623350 :   gimple_stmt_iterator gsi;
     477                 :    9623350 :   edge_iterator ei;
     478                 :    9623350 :   edge e;
     479                 :    9623350 :   bool last = true;
     480                 :            : 
     481                 :            :   /* If this block doesn't dominate anything, there can't be any place to sink
     482                 :            :      the statements to.  */
     483                 :    9623350 :   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
     484                 :    5905590 :     goto earlyout;
     485                 :            : 
     486                 :            :   /* We can't move things across abnormal edges, so don't try.  */
     487                 :   10620000 :   FOR_EACH_EDGE (e, ei, bb->succs)
     488                 :    6906080 :     if (e->flags & EDGE_ABNORMAL)
     489                 :       3819 :       goto earlyout;
     490                 :            : 
     491                 :   44230600 :   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
     492                 :            :     {
     493                 :   36802700 :       gimple *stmt = gsi_stmt (gsi);
     494                 :   36802700 :       gimple_stmt_iterator togsi;
     495                 :   36802700 :       bool zero_uses_p;
     496                 :            : 
     497                 :   36802700 :       if (!statement_sink_location (stmt, bb, &togsi, &zero_uses_p))
     498                 :            :         {
     499                 :   36585900 :           gimple_stmt_iterator saved = gsi;
     500                 :   36585900 :           if (!gsi_end_p (gsi))
     501                 :   36585900 :             gsi_prev (&gsi);
     502                 :            :           /* If we face a dead stmt remove it as it possibly blocks
     503                 :            :              sinking of uses.  */
     504                 :   36585900 :           if (zero_uses_p
     505                 :   36658200 :               && ! gimple_vdef (stmt))
     506                 :            :             {
     507                 :      70510 :               gsi_remove (&saved, true);
     508                 :      70510 :               release_defs (stmt);
     509                 :            :             }
     510                 :            :           else
     511                 :            :             last = false;
     512                 :   36585900 :           continue;
     513                 :            :         }
     514                 :     216795 :       if (dump_file)
     515                 :            :         {
     516                 :         14 :           fprintf (dump_file, "Sinking ");
     517                 :         14 :           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
     518                 :         14 :           fprintf (dump_file, " from bb %d to bb %d\n",
     519                 :         14 :                    bb->index, (gsi_bb (togsi))->index);
     520                 :            :         }
     521                 :            : 
     522                 :            :       /* Update virtual operands of statements in the path we
     523                 :            :          do not sink to.  */
     524                 :     433590 :       if (gimple_vdef (stmt))
     525                 :            :         {
     526                 :       3782 :           imm_use_iterator iter;
     527                 :       3782 :           use_operand_p use_p;
     528                 :       3782 :           gimple *vuse_stmt;
     529                 :            : 
     530                 :      11522 :           FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
     531                 :       7740 :             if (gimple_code (vuse_stmt) != GIMPLE_PHI)
     532                 :      15832 :               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
     533                 :       7916 :                 SET_USE (use_p, gimple_vuse (stmt));
     534                 :            :         }
     535                 :            : 
     536                 :            :       /* If this is the end of the basic block, we need to insert at the end
     537                 :            :          of the basic block.  */
     538                 :     216795 :       if (gsi_end_p (togsi))
     539                 :      18007 :         gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
     540                 :            :       else
     541                 :     198788 :         gsi_move_before (&gsi, &togsi);
     542                 :            : 
     543                 :     216795 :       sink_stats.sunk++;
     544                 :            : 
     545                 :            :       /* If we've just removed the last statement of the BB, the
     546                 :            :          gsi_end_p() test below would fail, but gsi_prev() would have
     547                 :            :          succeeded, and we want it to succeed.  So we keep track of
     548                 :            :          whether we're at the last statement and pick up the new last
     549                 :            :          statement.  */
     550                 :     216795 :       if (last)
     551                 :            :         {
     552                 :        109 :           gsi = gsi_last_bb (bb);
     553                 :        109 :           continue;
     554                 :            :         }
     555                 :            : 
     556                 :     216686 :       last = false;
     557                 :     216686 :       if (!gsi_end_p (gsi))
     558                 :     433372 :         gsi_prev (&gsi);
     559                 :            : 
     560                 :            :     }
     561                 :    3713940 :  earlyout:
     562                 :    9623350 :   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
     563                 :   18561100 :        son;
     564                 :    8937720 :        son = next_dom_son (CDI_POST_DOMINATORS, son))
     565                 :            :     {
     566                 :    8937720 :       sink_code_in_bb (son);
     567                 :            :     }
     568                 :    9623350 : }
     569                 :            : 
     570                 :            : /* Perform code sinking.
     571                 :            :    This moves code down the flowgraph when we know it would be
     572                 :            :    profitable to do so, or it wouldn't increase the number of
     573                 :            :    executions of the statement.
     574                 :            : 
     575                 :            :    IE given
     576                 :            : 
     577                 :            :    a_1 = b + c;
     578                 :            :    if (<something>)
     579                 :            :    {
     580                 :            :    }
     581                 :            :    else
     582                 :            :    {
     583                 :            :      foo (&b, &c);
     584                 :            :      a_5 = b + c;
     585                 :            :    }
     586                 :            :    a_6 = PHI (a_5, a_1);
     587                 :            :    USE a_6.
     588                 :            : 
     589                 :            :    we'll transform this into:
     590                 :            : 
     591                 :            :    if (<something>)
     592                 :            :    {
     593                 :            :       a_1 = b + c;
     594                 :            :    }
     595                 :            :    else
     596                 :            :    {
     597                 :            :       foo (&b, &c);
     598                 :            :       a_5 = b + c;
     599                 :            :    }
     600                 :            :    a_6 = PHI (a_5, a_1);
     601                 :            :    USE a_6.
     602                 :            : 
     603                 :            :    Note that this reduces the number of computations of a = b + c to 1
     604                 :            :    when we take the else edge, instead of 2.
     605                 :            : */
     606                 :            : namespace {
     607                 :            : 
     608                 :            : const pass_data pass_data_sink_code =
     609                 :            : {
     610                 :            :   GIMPLE_PASS, /* type */
     611                 :            :   "sink", /* name */
     612                 :            :   OPTGROUP_NONE, /* optinfo_flags */
     613                 :            :   TV_TREE_SINK, /* tv_id */
     614                 :            :   /* PROP_no_crit_edges is ensured by running split_edges_for_insertion in
     615                 :            :      pass_data_sink_code::execute ().  */
     616                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
     617                 :            :   0, /* properties_provided */
     618                 :            :   0, /* properties_destroyed */
     619                 :            :   0, /* todo_flags_start */
     620                 :            :   TODO_update_ssa, /* todo_flags_finish */
     621                 :            : };
     622                 :            : 
     623                 :            : class pass_sink_code : public gimple_opt_pass
     624                 :            : {
     625                 :            : public:
     626                 :     200540 :   pass_sink_code (gcc::context *ctxt)
     627                 :     401080 :     : gimple_opt_pass (pass_data_sink_code, ctxt)
     628                 :            :   {}
     629                 :            : 
     630                 :            :   /* opt_pass methods: */
     631                 :     685664 :   virtual bool gate (function *) { return flag_tree_sink != 0; }
     632                 :            :   virtual unsigned int execute (function *);
     633                 :            : 
     634                 :            : }; // class pass_sink_code
     635                 :            : 
     636                 :            : unsigned int
     637                 :     685624 : pass_sink_code::execute (function *fun)
     638                 :            : {
     639                 :     685624 :   loop_optimizer_init (LOOPS_NORMAL);
     640                 :     685624 :   split_edges_for_insertion ();
     641                 :     685624 :   connect_infinite_loops_to_exit ();
     642                 :     685624 :   memset (&sink_stats, 0, sizeof (sink_stats));
     643                 :     685624 :   calculate_dominance_info (CDI_DOMINATORS);
     644                 :     685624 :   calculate_dominance_info (CDI_POST_DOMINATORS);
     645                 :     685624 :   sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun));
     646                 :     685624 :   statistics_counter_event (fun, "Sunk statements", sink_stats.sunk);
     647                 :     685624 :   free_dominance_info (CDI_POST_DOMINATORS);
     648                 :     685624 :   remove_fake_exit_edges ();
     649                 :     685624 :   loop_optimizer_finalize ();
     650                 :            : 
     651                 :     685624 :   return 0;
     652                 :            : }
     653                 :            : 
     654                 :            : } // anon namespace
     655                 :            : 
     656                 :            : gimple_opt_pass *
     657                 :     200540 : make_pass_sink_code (gcc::context *ctxt)
     658                 :            : {
     659                 :     200540 :   return new pass_sink_code (ctxt);
     660                 :            : }

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.