LCOV - code coverage report
Current view: top level - gcc - gimple-ssa-sccopy.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 95.6 % 225 215
Test Date: 2024-12-14 13:15:07 Functions: 100.0 % 15 15
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Strongly-connected copy propagation pass for the GNU compiler.
       2                 :             :    Copyright (C) 2023-2024 Free Software Foundation, Inc.
       3                 :             :    Contributed by Filip Kastl <fkastl@suse.cz>
       4                 :             : 
       5                 :             : This file is part of GCC.
       6                 :             : 
       7                 :             : GCC is free software; you can redistribute it and/or modify it under
       8                 :             : the terms of the GNU General Public License as published by the Free
       9                 :             : Software Foundation; either version 3, or (at your option) any later
      10                 :             : version.
      11                 :             : 
      12                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :             : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :             : 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                 :             : #define INCLUDE_ALGORITHM
      22                 :             : #include "config.h"
      23                 :             : #include "system.h"
      24                 :             : #include "coretypes.h"
      25                 :             : #include "backend.h"
      26                 :             : #include "tree.h"
      27                 :             : #include "gimple.h"
      28                 :             : #include "tree-pass.h"
      29                 :             : #include "ssa.h"
      30                 :             : #include "gimple-iterator.h"
      31                 :             : #include "vec.h"
      32                 :             : #include "hash-set.h"
      33                 :             : #include "ssa-iterators.h"
      34                 :             : #include "gimple-fold.h"
      35                 :             : #include "gimplify.h"
      36                 :             : #include "tree-cfg.h"
      37                 :             : #include "tree-eh.h"
      38                 :             : #include "builtins.h"
      39                 :             : #include "tree-ssa-dce.h"
      40                 :             : #include "fold-const.h"
      41                 :             : 
      42                 :             : /* Strongly connected copy propagation pass.
      43                 :             : 
      44                 :             :    This is a lightweight copy propagation pass that is also able to eliminate
      45                 :             :    redundant PHI statements.  The pass considers the following types of copy
      46                 :             :    statements:
      47                 :             : 
      48                 :             :    1 An assignment statement with a single argument.
      49                 :             : 
      50                 :             :    _3 = _2;
      51                 :             :    _4 = 5;
      52                 :             : 
      53                 :             :    2 A degenerate PHI statement.  A degenerate PHI is a PHI that only refers to
      54                 :             :      itself or one other value.
      55                 :             : 
      56                 :             :    _5 = PHI <_1>;
      57                 :             :    _6 = PHI <_6, _6, _1, _1>;
      58                 :             :    _7 = PHI <16, _7>;
      59                 :             : 
      60                 :             :    3 A set of PHI statements that only refer to each other or to one other
      61                 :             :      value.
      62                 :             : 
      63                 :             :    _8 = PHI <_9, _10>;
      64                 :             :    _9 = PHI <_8, _10>;
      65                 :             :    _10 = PHI <_8, _9, _1>;
      66                 :             : 
      67                 :             :    All of these statements produce copies and can be eliminated from the
      68                 :             :    program.  For a copy statement we identify the value it creates a copy of
      69                 :             :    and replace references to the statement with the value -- we propagate the
      70                 :             :    copy.
      71                 :             : 
      72                 :             :    _3 = _2; // Replace all occurences of _3 by _2
      73                 :             : 
      74                 :             :    _8 = PHI <_9, _10>;
      75                 :             :    _9 = PHI <_8, _10>;
      76                 :             :    _10 = PHI <_8, _9, _1>; // Replace all occurences of _8, _9 and _10 by _1
      77                 :             : 
      78                 :             :    To find all three types of copy statements we use an algorithm based on
      79                 :             :    strongly-connected components (SCCs) in dataflow graph.  The algorithm was
      80                 :             :    introduced in an article from 2013[1]. We describe the algorithm bellow.
      81                 :             : 
      82                 :             :    To identify SCCs we implement the Robert Tarjan's SCC algorithm.  For the
      83                 :             :    SCC computation we wrap potential copy statements in the 'vertex' struct.
      84                 :             :    To each of these statements we also assign a vertex number ('vxnum'). Since
      85                 :             :    the main algorithm has to be able to compute SCCs of subgraphs of the whole
      86                 :             :    dataflow graph we use GIMPLE stmt flags to prevent Tarjan's algorithm from
      87                 :             :    leaving the subgraph.
      88                 :             : 
      89                 :             :    References:
      90                 :             : 
      91                 :             :      [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
      92                 :             :      Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
      93                 :             :      Section 3.2.  */
      94                 :             : 
      95                 :             : namespace {
      96                 :             : 
      97                 :             : /* State of vertex during SCC discovery.
      98                 :             : 
      99                 :             :    unvisited  Vertex hasn't yet been popped from worklist.
     100                 :             :    vopen      DFS has visited vertex for the first time.  Vertex has been put
     101                 :             :               on Tarjan stack.
     102                 :             :    closed     DFS has backtracked through vertex.  At this point, vertex
     103                 :             :               doesn't have any unvisited neighbors.
     104                 :             :    in_scc     Vertex has been popped from Tarjan stack.  */
     105                 :             : 
     106                 :             : enum vstate
     107                 :             : {
     108                 :             :   unvisited,
     109                 :             :   vopen,
     110                 :             :   closed,
     111                 :             :   in_scc
     112                 :             : };
     113                 :             : 
     114                 :             : /* Information about a vertex.  Used by SCC discovery.  */
     115                 :             : 
     116                 :             : struct vertex
     117                 :             : {
     118                 :             :   bool active; /* scc_discovery::compute_sccs () only considers a subgraph of
     119                 :             :                   the whole dataflow graph.  It uses this flag so that it knows
     120                 :             :                   which vertices are part of this subgraph.  */
     121                 :             :   vstate state;
     122                 :             :   unsigned index;
     123                 :             :   unsigned lowlink;
     124                 :             : };
     125                 :             : 
     126                 :             : /* SCC discovery.
     127                 :             : 
     128                 :             :    Used to find SCCs in a dataflow graph.  Implements Tarjan's SCC
     129                 :             :    algorithm.  */
     130                 :             : 
     131                 :             : class scc_discovery
     132                 :             : {
     133                 :             : public:
     134                 :             :   scc_discovery ();
     135                 :             :   ~scc_discovery ();
     136                 :             :   auto_vec<vec<gimple *>> compute_sccs (vec<gimple *> &stmts);
     137                 :             : 
     138                 :             : private:
     139                 :             :   vertex* vertices; /* Indexed by SSA_NAME_VERSION.  */
     140                 :             :   auto_vec<unsigned> worklist; /* DFS stack.  */
     141                 :             :   auto_vec<unsigned> stack; /* Tarjan stack.  */
     142                 :             : 
     143                 :             :   void visit_neighbor (tree neigh_tree, unsigned parent_vxnum);
     144                 :             : };
     145                 :             : 
     146                 :     3222266 : scc_discovery::scc_discovery ()
     147                 :             : {
     148                 :             :   /* Create vertex struct for each SSA name.  */
     149                 :     6444532 :   vertices = XNEWVEC (struct vertex, num_ssa_names);
     150                 :     3222266 :   unsigned i = 0;
     151                 :   120768999 :   for (i = 0; i < num_ssa_names; i++)
     152                 :   117546733 :     vertices[i].active = false;
     153                 :     3222266 : }
     154                 :             : 
     155                 :     3222266 : scc_discovery::~scc_discovery ()
     156                 :             : {
     157                 :     3222266 :   XDELETEVEC (vertices);
     158                 :     3222266 : }
     159                 :             : 
     160                 :             : /* Part of 'scc_discovery::compute_sccs ()'.  */
     161                 :             : 
     162                 :             : void
     163                 :    41828706 : scc_discovery::visit_neighbor (tree neigh_tree, unsigned parent_version)
     164                 :             : {
     165                 :    41828706 :   if (TREE_CODE (neigh_tree) != SSA_NAME)
     166                 :    32054795 :     return; /* Skip any neighbor that isn't an SSA name.  */
     167                 :    37685225 :   unsigned neigh_version = SSA_NAME_VERSION (neigh_tree);
     168                 :             : 
     169                 :             :   /* Skip neighbors outside the subgraph that Tarjan currently works
     170                 :             :      with.  */
     171                 :    37685225 :   if (!vertices[neigh_version].active)
     172                 :             :     return;
     173                 :             : 
     174                 :     9773911 :   vstate neigh_state = vertices[neigh_version].state;
     175                 :     9773911 :   vstate parent_state = vertices[parent_version].state;
     176                 :     9773911 :   if (parent_state == vopen) /* We're currently opening parent.  */
     177                 :             :     {
     178                 :             :       /* Put unvisited neighbors on worklist.  Update lowlink of parent
     179                 :             :          vertex according to indices of neighbors present on stack.  */
     180                 :     3652771 :       switch (neigh_state)
     181                 :             :         {
     182                 :     2561030 :         case unvisited:
     183                 :     2561030 :           worklist.safe_push (neigh_version);
     184                 :     2561030 :           break;
     185                 :      536533 :         case vopen:
     186                 :      536533 :         case closed:
     187                 :      536533 :           vertices[parent_version].lowlink
     188                 :      536533 :             = std::min (vertices[parent_version].lowlink,
     189                 :             :                         vertices[neigh_version].index);
     190                 :      536533 :           break;
     191                 :             :         case in_scc:
     192                 :             :           /* Ignore these edges.  */
     193                 :             :           break;
     194                 :             :         }
     195                 :             :     }
     196                 :     6121140 :   else if (parent_state == closed) /* We're currently closing parent.  */
     197                 :             :     {
     198                 :             :       /* Update lowlink of parent vertex according to lowlinks of
     199                 :             :          children of parent (in terms of DFS tree).  */
     200                 :     3824675 :       if (neigh_state == closed)
     201                 :             :         {
     202                 :      721463 :           vertices[parent_version].lowlink
     203                 :      721463 :             = std::min (vertices[parent_version].lowlink,
     204                 :             :                         vertices[neigh_version].lowlink);
     205                 :             :         }
     206                 :             :     }
     207                 :             : }
     208                 :             : 
     209                 :             : /* Compute SCCs in dataflow graph on given statements 'stmts'.  Ignore
     210                 :             :    statements outside 'stmts'.  Return the SCCs in a reverse topological
     211                 :             :    order.
     212                 :             : 
     213                 :             :    stmt_may_generate_copy () must be true for all statements from 'stmts'!  */
     214                 :             : 
     215                 :             : auto_vec<vec<gimple *>>
     216                 :     9813338 : scc_discovery::compute_sccs (vec<gimple *> &stmts)
     217                 :             : {
     218                 :     9813338 :   auto_vec<vec<gimple *>> sccs;
     219                 :             : 
     220                 :    19448650 :   for (gimple *stmt : stmts)
     221                 :             :     {
     222                 :     7449362 :       unsigned i;
     223                 :     7449362 :       switch (gimple_code (stmt))
     224                 :             :         {
     225                 :       22504 :           case GIMPLE_ASSIGN:
     226                 :       22504 :             i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
     227                 :       22504 :             break;
     228                 :     7426858 :           case GIMPLE_PHI:
     229                 :     7426858 :             i = SSA_NAME_VERSION (gimple_phi_result (stmt));
     230                 :     7426858 :             break;
     231                 :           0 :           default:
     232                 :           0 :             gcc_unreachable ();
     233                 :             :         }
     234                 :             : 
     235                 :     7449362 :       vertices[i].index = 0;
     236                 :     7449362 :       vertices[i].lowlink = 0;
     237                 :     7449362 :       vertices[i].state = unvisited;
     238                 :     7449362 :       vertices[i].active = true; /* Mark the subgraph we'll be working on so
     239                 :             :                                     that we don't leave it.  */
     240                 :             : 
     241                 :     7449362 :       worklist.safe_push (i);
     242                 :             :     }
     243                 :             : 
     244                 :             :   /* Worklist loop.  */
     245                 :             :   unsigned curr_index = 0;
     246                 :    27273092 :   while (!worklist.is_empty ())
     247                 :             :     {
     248                 :    17459754 :       unsigned i = worklist.pop ();
     249                 :    17459754 :       gimple *stmt = SSA_NAME_DEF_STMT (ssa_name (i));
     250                 :    17459754 :       vstate state = vertices[i].state;
     251                 :             : 
     252                 :    17459754 :       if (state == unvisited)
     253                 :             :         {
     254                 :     7449362 :           vertices[i].state = vopen;
     255                 :             : 
     256                 :             :           /* Assign index to this vertex.  */
     257                 :     7449362 :           vertices[i].index = curr_index;
     258                 :     7449362 :           vertices[i].lowlink = curr_index;
     259                 :     7449362 :           curr_index++;
     260                 :             : 
     261                 :             :           /* Put vertex on stack and also on worklist to be closed later.  */
     262                 :     7449362 :           stack.safe_push (i);
     263                 :     7449362 :           worklist.safe_push (i);
     264                 :             :         }
     265                 :    10010392 :       else if (state == vopen)
     266                 :     7449362 :         vertices[i].state = closed;
     267                 :             : 
     268                 :             :       /* Visit neighbors of this vertex.  */
     269                 :    17459754 :       tree op;
     270                 :    17459754 :       gphi *phi;
     271                 :    17459754 :       switch (gimple_code (stmt))
     272                 :             :         {
     273                 :    17413855 :           case GIMPLE_PHI:
     274                 :    17413855 :             phi = as_a <gphi *> (stmt);
     275                 :    17413855 :             unsigned j;
     276                 :    76610517 :             for (j = 0; j < gimple_phi_num_args (phi); j++)
     277                 :             :               {
     278                 :    41782807 :                 op = gimple_phi_arg_def (phi, j);
     279                 :    41782807 :                 visit_neighbor (op, i);
     280                 :             :               }
     281                 :             :             break;
     282                 :       45899 :           case GIMPLE_ASSIGN:
     283                 :       45899 :             op = gimple_assign_rhs1 (stmt);
     284                 :       45899 :             visit_neighbor (op, i);
     285                 :       45899 :             break;
     286                 :           0 :           default:
     287                 :           0 :             gcc_unreachable ();
     288                 :             :         }
     289                 :             : 
     290                 :             :       /* If we've just closed a root vertex of an scc, pop scc from stack.  */
     291                 :    17459754 :       if (state == vopen && vertices[i].lowlink == vertices[i].index)
     292                 :             :         {
     293                 :     6998015 :           vec<gimple *> scc = vNULL;
     294                 :             : 
     295                 :     7449362 :           unsigned j;
     296                 :     7449362 :           do
     297                 :             :             {
     298                 :     7449362 :               j = stack.pop ();
     299                 :     7449362 :               scc.safe_push (SSA_NAME_DEF_STMT (ssa_name (j)));
     300                 :     7449362 :               vertices[j].state = in_scc;
     301                 :             :             }
     302                 :     7449362 :           while (j != i);
     303                 :             : 
     304                 :     6998015 :           sccs.safe_push (scc);
     305                 :             :         }
     306                 :             :     }
     307                 :             : 
     308                 :     9813338 :   if (!stack.is_empty ())
     309                 :           0 :     gcc_unreachable ();
     310                 :             : 
     311                 :             :   /* Clear 'active' flags.  */
     312                 :    19448650 :   for (gimple *stmt : stmts)
     313                 :             :     {
     314                 :     7449362 :       unsigned i;
     315                 :     7449362 :       switch (gimple_code (stmt))
     316                 :             :         {
     317                 :       22504 :           case GIMPLE_ASSIGN:
     318                 :       22504 :             i = SSA_NAME_VERSION (gimple_assign_lhs (stmt));
     319                 :       22504 :             break;
     320                 :     7426858 :           case GIMPLE_PHI:
     321                 :     7426858 :             i = SSA_NAME_VERSION (gimple_phi_result (stmt));
     322                 :     7426858 :             break;
     323                 :           0 :           default:
     324                 :           0 :             gcc_unreachable ();
     325                 :             :         }
     326                 :             : 
     327                 :     7449362 :       vertices[i].active = false;
     328                 :             :     }
     329                 :             : 
     330                 :     9813338 :   return sccs;
     331                 :             : }
     332                 :             : 
     333                 :             : } // anon namespace
     334                 :             : 
     335                 :             : /* Could this statement potentially be a copy statement?
     336                 :             : 
     337                 :             :    This pass only considers statements for which this function returns 'true'.
     338                 :             :    Those are basically PHI functions and assignment statements similar to
     339                 :             : 
     340                 :             :    _2 = _1;
     341                 :             :    or
     342                 :             :    _2 = 5;  */
     343                 :             : 
     344                 :             : static bool
     345                 :   138654549 : stmt_may_generate_copy (gimple *stmt)
     346                 :             : {
     347                 :             :   /* A PHI may generate a copy.  */
     348                 :   138654549 :   if (gimple_code (stmt) == GIMPLE_PHI)
     349                 :             :     {
     350                 :     7592099 :       gphi *phi = as_a <gphi *> (stmt);
     351                 :             : 
     352                 :             :       /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs.  */
     353                 :     7592099 :       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi)))
     354                 :             :         return false;
     355                 :             : 
     356                 :             :       unsigned i;
     357                 :    26087107 :       for (i = 0; i < gimple_phi_num_args (phi); i++)
     358                 :             :         {
     359                 :    18506620 :           tree op = gimple_phi_arg_def (phi, i);
     360                 :    18506620 :           if (TREE_CODE (op) == SSA_NAME
     361                 :    18506620 :               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
     362                 :             :             return false;
     363                 :             :         }
     364                 :             : 
     365                 :             :       /* If PHI has more than one unique non-SSA arguments, it won't generate a
     366                 :             :          copy.  */
     367                 :             :       tree const_op = NULL_TREE;
     368                 :    25420614 :       for (i = 0; i < gimple_phi_num_args (phi); i++)
     369                 :             :         {
     370                 :    18142320 :           tree op = gimple_phi_arg_def (phi, i);
     371                 :    18142320 :           if (TREE_CODE (op) != SSA_NAME)
     372                 :             :             {
     373                 :     2440865 :               if (const_op && !operand_equal_p (op, const_op))
     374                 :             :                 return false;
     375                 :             :               const_op = op;
     376                 :             :             }
     377                 :             :         }
     378                 :             : 
     379                 :             :       return true;
     380                 :             :     }
     381                 :             : 
     382                 :             :   /* Or a statement of type _2 = _1; OR _2 = 5; may generate a copy.  */
     383                 :             : 
     384                 :   131062450 :   if (!gimple_assign_single_p (stmt))
     385                 :             :     return false;
     386                 :             : 
     387                 :    27589841 :   tree lhs = gimple_assign_lhs (stmt);
     388                 :    27589841 :   tree rhs = gimple_assign_rhs1 (stmt);
     389                 :             : 
     390                 :    27589841 :   if (TREE_CODE (lhs) != SSA_NAME)
     391                 :             :     return false;
     392                 :             : 
     393                 :             :   /* lhs shouldn't flow through any abnormal edges.  */
     394                 :    12645787 :   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
     395                 :             :     return false;
     396                 :             : 
     397                 :    12645129 :   if (is_gimple_min_invariant (rhs))
     398                 :             :     return true;  /* A statement of type _2 = 5;.  */
     399                 :             : 
     400                 :    12639627 :   if (TREE_CODE (rhs) != SSA_NAME)
     401                 :             :     return false;
     402                 :             : 
     403                 :             :   /* rhs shouldn't flow through any abnormal edges.  */
     404                 :       28754 :   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
     405                 :             :     return false;
     406                 :             : 
     407                 :             :   /* It is possible that lhs has more alignment or value range information.  By
     408                 :             :      propagating we would lose this information.  So in the case that alignment
     409                 :             :      or value range information differs, we are conservative and do not
     410                 :             :      propagate.
     411                 :             : 
     412                 :             :      FIXME: Propagate alignment and value range info the same way copy-prop
     413                 :             :      does.  */
     414                 :       53263 :   if (POINTER_TYPE_P (TREE_TYPE (lhs))
     415                 :        2177 :       && POINTER_TYPE_P (TREE_TYPE (rhs))
     416                 :       29895 :       && SSA_NAME_PTR_INFO (lhs) != SSA_NAME_PTR_INFO (rhs))
     417                 :             :     return false;
     418                 :       51262 :   if (!POINTER_TYPE_P (TREE_TYPE (lhs))
     419                 :       25541 :       && !POINTER_TYPE_P (TREE_TYPE (rhs))
     420                 :       51262 :       && SSA_NAME_RANGE_INFO (lhs) != SSA_NAME_RANGE_INFO (rhs))
     421                 :             :     return false;
     422                 :             : 
     423                 :             :   return true;  /* A statement of type _2 = _1;.  */
     424                 :             : }
     425                 :             : 
     426                 :             : /* Return all statements in cfun that could generate copies.  All statements
     427                 :             :    for which stmt_may_generate_copy returns 'true'.  */
     428                 :             : 
     429                 :             : static auto_vec<gimple *>
     430                 :     3222266 : get_all_stmt_may_generate_copy (void)
     431                 :             : {
     432                 :     3222266 :   auto_vec<gimple *> result;
     433                 :             : 
     434                 :     3222266 :   basic_block bb;
     435                 :    23001333 :   FOR_EACH_BB_FN (bb, cfun)
     436                 :             :     {
     437                 :    19779067 :       gimple_stmt_iterator gsi;
     438                 :   170620584 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     439                 :             :         {
     440                 :   131062450 :           gimple *s = gsi_stmt (gsi);
     441                 :   131062450 :           if (stmt_may_generate_copy (s))
     442                 :       22504 :             result.safe_push (s);
     443                 :             :         }
     444                 :             : 
     445                 :    19779067 :       gphi_iterator pi;
     446                 :    27371166 :       for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
     447                 :             :         {
     448                 :     7592099 :           gimple *s = pi.phi ();
     449                 :     7592099 :           if (stmt_may_generate_copy (s))
     450                 :     7278294 :             result.safe_push (s);
     451                 :             :         }
     452                 :             :     }
     453                 :             : 
     454                 :     3222266 :   return result;
     455                 :             : }
     456                 :             : 
     457                 :             : /* SCC copy propagation
     458                 :             : 
     459                 :             :    'scc_copy_prop::propagate ()' is the main function of this pass.  */
     460                 :             : 
     461                 :             : class scc_copy_prop
     462                 :             : {
     463                 :             : public:
     464                 :             :   scc_copy_prop ();
     465                 :             :   ~scc_copy_prop ();
     466                 :             :   void propagate ();
     467                 :             : 
     468                 :             : private:
     469                 :             :   /* Bitmap tracking statements which were propagated so that they can be
     470                 :             :      removed at the end of the pass.  */
     471                 :             :   bitmap dead_stmts;
     472                 :             : 
     473                 :             :   void visit_op (tree op, hash_set<tree> &outer_ops,
     474                 :             :                                 hash_set<gimple *> &scc_set, bool &is_inner,
     475                 :             :                                 tree &last_outer_op);
     476                 :             :   void replace_scc_by_value (vec<gimple *> scc, tree val);
     477                 :             : };
     478                 :             : 
     479                 :             : /* For each statement from given SCC, replace its usages by value
     480                 :             :    VAL.  */
     481                 :             : 
     482                 :             : void
     483                 :      406943 : scc_copy_prop::replace_scc_by_value (vec<gimple *> scc, tree val)
     484                 :             : {
     485                 :     1632282 :   for (gimple *stmt : scc)
     486                 :             :     {
     487                 :      411453 :       tree name = gimple_get_lhs (stmt);
     488                 :      411453 :       replace_uses_by (name, val);
     489                 :      411453 :       bitmap_set_bit (dead_stmts, SSA_NAME_VERSION (name));
     490                 :             :     }
     491                 :             : 
     492                 :      406943 :   if (dump_file)
     493                 :          56 :     fprintf (dump_file, "Replacing SCC of size %d\n", scc.length ());
     494                 :      406943 : }
     495                 :             : 
     496                 :             : /* Part of 'scc_copy_prop::propagate ()'.  */
     497                 :             : 
     498                 :             : void
     499                 :    17820464 : scc_copy_prop::visit_op (tree op, hash_set<tree> &outer_ops,
     500                 :             :                          hash_set<gimple *> &scc_set, bool &is_inner,
     501                 :             :                          tree &last_outer_op)
     502                 :             : {
     503                 :    17820464 :   bool op_in_scc = false;
     504                 :             : 
     505                 :    17820464 :   if (TREE_CODE (op) == SSA_NAME)
     506                 :             :     {
     507                 :    15994154 :       gimple *op_stmt = SSA_NAME_DEF_STMT (op);
     508                 :    15994154 :       if (scc_set.contains (op_stmt))
     509                 :     1093765 :         op_in_scc = true;
     510                 :             :     }
     511                 :             : 
     512                 :    15994154 :   if (!op_in_scc)
     513                 :             :     {
     514                 :    16726699 :       outer_ops.add (op);
     515                 :    16726699 :       last_outer_op = op;
     516                 :    16726699 :       is_inner = false;
     517                 :             :     }
     518                 :    17820464 : }
     519                 :             : 
     520                 :             : /* Main function of this pass.  Find and propagate all three types of copy
     521                 :             :    statements (see pass description above).
     522                 :             : 
     523                 :             :    This is an implementation of an algorithm from the paper Simple and
     524                 :             :    Efficient Construction of Static Single Assignmemnt Form[1].  It is based
     525                 :             :    on strongly-connected components (SCCs) in dataflow graph.  The original
     526                 :             :    algorithm only considers PHI statements.  We extend it to also consider
     527                 :             :    assignment statements of type _2 = _1;.
     528                 :             : 
     529                 :             :    The algorithm is based on this definition of a set of redundant PHIs[1]:
     530                 :             : 
     531                 :             :      A non-empty set P of PHI functions is redundant iff the PHI functions just
     532                 :             :      reference each other or one other value
     533                 :             : 
     534                 :             :    It uses this lemma[1]:
     535                 :             : 
     536                 :             :      Let P be a redundant set of PHI functions.  Then there is a
     537                 :             :      strongly-connected component S subset of P that is also redundant.
     538                 :             : 
     539                 :             :    The algorithm works in this way:
     540                 :             : 
     541                 :             :      1 Find SCCs
     542                 :             :      2 For each SCC S in topological order:
     543                 :             :      3   Construct set 'inner' of statements that only have other statements
     544                 :             :          from S on their right hand side
     545                 :             :      4   Construct set 'outer' of values that originate outside S and appear on
     546                 :             :          right hand side of some statement from S
     547                 :             :      5   If |outer| = 1, outer only contains a value v.  Statements in S only
     548                 :             :          refer to each other or to v -- they are redundant.  Propagate v.
     549                 :             :          Else, recurse on statements in inner.
     550                 :             : 
     551                 :             :    The implementation is non-recursive.
     552                 :             : 
     553                 :             :    References:
     554                 :             : 
     555                 :             :      [1] Simple and Efficient Construction of Static Single Assignmemnt Form,
     556                 :             :      Braun, Buchwald, Hack, Leissa, Mallon, Zwinkau, 2013, LNCS vol. 7791,
     557                 :             :      Section 3.2.  */
     558                 :             : 
     559                 :             : void
     560                 :     3222266 : scc_copy_prop::propagate ()
     561                 :             : {
     562                 :     3222266 :   auto_vec<gimple *> useful_stmts = get_all_stmt_may_generate_copy ();
     563                 :     3222266 :   scc_discovery discovery;
     564                 :             : 
     565                 :     3222266 :   auto_vec<vec<gimple *>> worklist = discovery.compute_sccs (useful_stmts);
     566                 :             : 
     567                 :    14460410 :   while (!worklist.is_empty ())
     568                 :             :     {
     569                 :     6998015 :       vec<gimple *> scc = worklist.pop ();
     570                 :             : 
     571                 :     6998015 :       auto_vec<gimple *> inner;
     572                 :     6998015 :       hash_set<tree> outer_ops;
     573                 :     6998015 :       tree last_outer_op = NULL_TREE;
     574                 :             : 
     575                 :             :       /* Prepare hash set of PHIs in scc to query later.  */
     576                 :     6998015 :       hash_set<gimple *> scc_set;
     577                 :    21445392 :       for (gimple *stmt : scc)
     578                 :     7449362 :         scc_set.add (stmt);
     579                 :             : 
     580                 :    21445392 :       for (gimple *stmt : scc)
     581                 :             :         {
     582                 :     7449362 :           bool is_inner = true;
     583                 :             : 
     584                 :     7449362 :           gphi *phi;
     585                 :     7449362 :           tree op;
     586                 :             : 
     587                 :     7449362 :           switch (gimple_code (stmt))
     588                 :             :             {
     589                 :     7426858 :               case GIMPLE_PHI:
     590                 :     7426858 :                 phi = as_a <gphi *> (stmt);
     591                 :     7426858 :                 unsigned j;
     592                 :    32651676 :                 for (j = 0; j < gimple_phi_num_args (phi); j++)
     593                 :             :                   {
     594                 :    17797960 :                     op = gimple_phi_arg_def (phi, j);
     595                 :    17797960 :                     visit_op (op, outer_ops, scc_set, is_inner, last_outer_op);
     596                 :             :                   }
     597                 :             :                 break;
     598                 :       22504 :               case GIMPLE_ASSIGN:
     599                 :       22504 :                 op = gimple_assign_rhs1 (stmt);
     600                 :       22504 :                 visit_op (op, outer_ops, scc_set, is_inner, last_outer_op);
     601                 :       22504 :                 break;
     602                 :           0 :               default:
     603                 :           0 :                 gcc_unreachable ();
     604                 :             :             }
     605                 :             : 
     606                 :     7449362 :           if (is_inner)
     607                 :      152497 :             inner.safe_push (stmt);
     608                 :             :         }
     609                 :             : 
     610                 :     6998015 :       if (outer_ops.elements () == 1)
     611                 :             :         {
     612                 :             :           /* The only operand in outer_ops.  */
     613                 :      406943 :           tree outer_op = last_outer_op;
     614                 :      406943 :           replace_scc_by_value (scc, outer_op);
     615                 :             :         }
     616                 :     6591072 :       else if (outer_ops.elements () > 1)
     617                 :             :         {
     618                 :             :           /* Add inner sccs to worklist.  */
     619                 :     6591072 :           auto_vec<vec<gimple *>> inner_sccs
     620                 :     6591072 :             = discovery.compute_sccs (inner);
     621                 :     6862726 :           for (vec<gimple *> inner_scc : inner_sccs)
     622                 :      121430 :             worklist.safe_push (inner_scc);
     623                 :     6591072 :         }
     624                 :             :       else
     625                 :           0 :         gcc_unreachable ();
     626                 :             : 
     627                 :     6998015 :       scc.release ();
     628                 :     6998015 :     }
     629                 :     3222266 : }
     630                 :             : 
     631                 :     3222266 : scc_copy_prop::scc_copy_prop ()
     632                 :             : {
     633                 :             :   /* For propagated statements.  */
     634                 :     3222266 :   dead_stmts = BITMAP_ALLOC (NULL);
     635                 :     3222266 : }
     636                 :             : 
     637                 :     3222266 : scc_copy_prop::~scc_copy_prop ()
     638                 :             : {
     639                 :             :   /* Remove all propagated statements.  */
     640                 :     3222266 :   simple_dce_from_worklist (dead_stmts);
     641                 :     3222266 :   BITMAP_FREE (dead_stmts);
     642                 :             : 
     643                 :             :   /* Propagating a constant may create dead eh edges.  */
     644                 :     3222266 :   basic_block bb;
     645                 :    23001333 :   FOR_EACH_BB_FN (bb, cfun)
     646                 :    19779067 :     gimple_purge_dead_eh_edges (bb);
     647                 :     3222266 : }
     648                 :             : 
     649                 :             : namespace {
     650                 :             : 
     651                 :             : const pass_data pass_data_sccopy =
     652                 :             : {
     653                 :             :   GIMPLE_PASS, /* type */
     654                 :             :   "sccopy", /* name */
     655                 :             :   OPTGROUP_NONE, /* optinfo_flags */
     656                 :             :   TV_NONE, /* tv_id */
     657                 :             :   ( PROP_cfg | PROP_ssa ), /* properties_required */
     658                 :             :   0, /* properties_provided */
     659                 :             :   0, /* properties_destroyed */
     660                 :             :   0, /* todo_flags_start */
     661                 :             :   TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
     662                 :             : };
     663                 :             : 
     664                 :             : class pass_sccopy : public gimple_opt_pass
     665                 :             : {
     666                 :             : public:
     667                 :      554512 :   pass_sccopy (gcc::context *ctxt)
     668                 :     1109024 :     : gimple_opt_pass (pass_data_sccopy, ctxt)
     669                 :             :   {}
     670                 :             : 
     671                 :             :   /* opt_pass methods: */
     672                 :     3222338 :   virtual bool gate (function *) { return true; }
     673                 :             :   virtual unsigned int execute (function *);
     674                 :      277256 :   opt_pass * clone () final override { return new pass_sccopy (m_ctxt); }
     675                 :             : }; // class pass_sccopy
     676                 :             : 
     677                 :             : unsigned
     678                 :     3222266 : pass_sccopy::execute (function *)
     679                 :             : {
     680                 :     3222266 :   scc_copy_prop sccopy;
     681                 :     3222266 :   sccopy.propagate ();
     682                 :     6444532 :   return 0;
     683                 :     3222266 : }
     684                 :             : 
     685                 :             : } // anon namespace
     686                 :             : 
     687                 :             : gimple_opt_pass *
     688                 :      277256 : make_pass_sccopy (gcc::context *ctxt)
     689                 :             : {
     690                 :      277256 :   return new pass_sccopy (ctxt);
     691                 :             : }
        

Generated by: LCOV version 2.1-beta

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.