LCOV - code coverage report
Current view: top level - gcc - value-pointer-equiv.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.6 % 119 115
Test Date: 2024-03-23 14:05:01 Functions: 100.0 % 16 16
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Context-aware pointer equivalence tracker.
       2                 :             :    Copyright (C) 2020-2024 Free Software Foundation, Inc.
       3                 :             :    Contributed by Aldy Hernandez <aldyh@redhat.com>
       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                 :             : #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 "tree-pass.h"
      28                 :             : #include "ssa.h"
      29                 :             : #include "gimple-pretty-print.h"
      30                 :             : #include "cfganal.h"
      31                 :             : #include "gimple-iterator.h"
      32                 :             : #include "gimple-fold.h"
      33                 :             : #include "tree-eh.h"
      34                 :             : #include "tree-cfg.h"
      35                 :             : #include "tree-ssa-loop-manip.h"
      36                 :             : #include "tree-ssa-loop.h"
      37                 :             : #include "cfgloop.h"
      38                 :             : #include "tree-scalar-evolution.h"
      39                 :             : #include "tree-ssa-propagate.h"
      40                 :             : #include "alloc-pool.h"
      41                 :             : #include "domwalk.h"
      42                 :             : #include "tree-cfgcleanup.h"
      43                 :             : #include "vr-values.h"
      44                 :             : #include "gimple-range.h"
      45                 :             : #include "fold-const.h"
      46                 :             : #include "value-pointer-equiv.h"
      47                 :             : 
      48                 :             : // Unwindable SSA equivalence table for pointers.
      49                 :             : //
      50                 :             : // The main query point is get_replacement() which returns what a
      51                 :             : // given SSA can be replaced with in the current scope.
      52                 :             : 
      53                 :     3887644 : class ssa_equiv_stack
      54                 :             : {
      55                 :             : public:
      56                 :             :   ssa_equiv_stack ();
      57                 :             :   void enter (basic_block);
      58                 :             :   void leave (basic_block);
      59                 :             :   void push_replacement (tree name, tree replacement);
      60                 :             :   tree get_replacement (tree name);
      61                 :             : 
      62                 :             : private:
      63                 :             :   auto_vec<std::pair <tree, tree>> m_stack;
      64                 :             :   auto_vec<tree> m_replacements;
      65                 :     3887644 :   const std::pair <tree, tree> m_marker = std::make_pair (NULL, NULL);
      66                 :             : };
      67                 :             : 
      68                 :     3887644 : ssa_equiv_stack::ssa_equiv_stack ()
      69                 :             : {
      70                 :     7775288 :   m_replacements.safe_grow_cleared (num_ssa_names + 1);
      71                 :     3887644 : }
      72                 :             : 
      73                 :             : // Pushes a marker at the given point.
      74                 :             : 
      75                 :             : void
      76                 :    33277663 : ssa_equiv_stack::enter (basic_block)
      77                 :             : {
      78                 :    33277663 :   m_stack.safe_push (m_marker);
      79                 :    33277663 : }
      80                 :             : 
      81                 :             : // Pops the stack to the last marker, while performing replacements
      82                 :             : // along the way.
      83                 :             : 
      84                 :             : void
      85                 :    33277663 : ssa_equiv_stack::leave (basic_block)
      86                 :             : {
      87                 :    33277663 :   gcc_checking_assert (!m_stack.is_empty ());
      88                 :    33393042 :   while (m_stack.last () != m_marker)
      89                 :             :     {
      90                 :      115379 :       std::pair<tree, tree> e = m_stack.pop ();
      91                 :      115379 :       m_replacements[SSA_NAME_VERSION (e.first)] = e.second;
      92                 :             :     }
      93                 :    33277663 :   m_stack.pop ();
      94                 :    33277663 : }
      95                 :             : 
      96                 :             : // Set the equivalence of NAME to REPLACEMENT.
      97                 :             : 
      98                 :             : void
      99                 :      115379 : ssa_equiv_stack::push_replacement (tree name, tree replacement)
     100                 :             : {
     101                 :      115379 :   unsigned v = SSA_NAME_VERSION (name);
     102                 :             : 
     103                 :      230758 :   if (v >= m_replacements.length ())
     104                 :           0 :     m_replacements.safe_grow_cleared (num_ssa_names + 1);
     105                 :             : 
     106                 :      115379 :   tree old = m_replacements[v];
     107                 :      115379 :   m_replacements[v] = replacement;
     108                 :      115379 :   m_stack.safe_push (std::make_pair (name, old));
     109                 :      115379 : }
     110                 :             : 
     111                 :             : // Return the equivalence of NAME.
     112                 :             : 
     113                 :             : tree
     114                 :    63586956 : ssa_equiv_stack::get_replacement (tree name)
     115                 :             : {
     116                 :    63586956 :   unsigned v = SSA_NAME_VERSION (name);
     117                 :             : 
     118                 :   127173912 :   if (v >= m_replacements.length ())
     119                 :           0 :     m_replacements.safe_grow_cleared (num_ssa_names + 1);
     120                 :             : 
     121                 :    63586956 :   return m_replacements[v];
     122                 :             : }
     123                 :             : 
     124                 :     3887644 : pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r)
     125                 :             : {
     126                 :     3887644 :   m_ranger = r;
     127                 :     7775288 :   m_global_points.safe_grow_cleared (num_ssa_names + 1);
     128                 :     3887644 :   m_cond_points = new ssa_equiv_stack;
     129                 :     3887644 : }
     130                 :             : 
     131                 :     3887644 : pointer_equiv_analyzer::~pointer_equiv_analyzer ()
     132                 :             : {
     133                 :     7775288 :   delete m_cond_points;
     134                 :     3887644 : }
     135                 :             : 
     136                 :             : // Set the global pointer equivalency for SSA to POINTEE.
     137                 :             : 
     138                 :             : void
     139                 :       47286 : pointer_equiv_analyzer::set_global_equiv (tree ssa, tree pointee)
     140                 :             : {
     141                 :       47286 :   unsigned v = SSA_NAME_VERSION (ssa);
     142                 :             : 
     143                 :       94572 :   if (v >= m_global_points.length ())
     144                 :           0 :     m_global_points.safe_grow_cleared (num_ssa_names + 1);
     145                 :             : 
     146                 :       47286 :   m_global_points[v] = pointee;
     147                 :       47286 : }
     148                 :             : 
     149                 :             : // Set the conditional pointer equivalency for SSA to POINTEE.
     150                 :             : 
     151                 :             : void
     152                 :      115379 : pointer_equiv_analyzer::set_cond_equiv (tree ssa, tree pointee)
     153                 :             : {
     154                 :      115379 :   m_cond_points->push_replacement (ssa, pointee);
     155                 :      115379 : }
     156                 :             : 
     157                 :             : // Return the current pointer equivalency info for SSA, or NULL if
     158                 :             : // none is available.  Note that global info takes priority over
     159                 :             : // conditional info.
     160                 :             : 
     161                 :             : tree
     162                 :    63625377 : pointer_equiv_analyzer::get_equiv (tree ssa)
     163                 :             : {
     164                 :    63625377 :   unsigned v = SSA_NAME_VERSION (ssa);
     165                 :             : 
     166                 :   127250754 :   if (v >= m_global_points.length ())
     167                 :           0 :     m_global_points.safe_grow_cleared (num_ssa_names + 1);
     168                 :             : 
     169                 :    63625377 :   tree ret = m_global_points[v];
     170                 :    63625377 :   if (ret)
     171                 :             :     return ret;
     172                 :    63586956 :   return m_cond_points->get_replacement (ssa);
     173                 :             : }
     174                 :             : 
     175                 :             : // Method to be called on entry to a BB.
     176                 :             : 
     177                 :             : void
     178                 :    33277663 : pointer_equiv_analyzer::enter (basic_block bb)
     179                 :             : {
     180                 :    33277663 :   m_cond_points->enter (bb);
     181                 :             : 
     182                 :    33277663 :   for (gphi_iterator iter = gsi_start_phis (bb);
     183                 :    46253605 :        !gsi_end_p (iter);
     184                 :    12975942 :        gsi_next (&iter))
     185                 :             :     {
     186                 :    13172063 :       gphi *phi = iter.phi ();
     187                 :    13172063 :       tree lhs = gimple_phi_result (phi);
     188                 :    13172063 :       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
     189                 :    11545638 :         continue;
     190                 :     1626425 :       tree arg0 = gimple_phi_arg_def (phi, 0);
     191                 :     1626425 :       if (TREE_CODE (arg0) == SSA_NAME && !is_gimple_min_invariant (arg0))
     192                 :     1391794 :         arg0 = get_equiv (arg0);
     193                 :     1626425 :       if (arg0 && is_gimple_min_invariant (arg0))
     194                 :             :         {
     195                 :             :           // If all the PHI args point to the same place, set the
     196                 :             :           // pointer equivalency info for the PHI result.  This can
     197                 :             :           // happen for passes that create redundant PHIs like
     198                 :             :           // PHI<&foo, &foo> or PHI<&foo>.
     199                 :      259249 :           for (size_t i = 1; i < gimple_phi_num_args (phi); ++i)
     200                 :             :             {
     201                 :      220735 :               tree argi = gimple_phi_arg_def (phi, i);
     202                 :      220735 :               if (TREE_CODE (argi) == SSA_NAME
     203                 :      220735 :                   && !is_gimple_min_invariant (argi))
     204                 :      155768 :                 argi = get_equiv (argi);
     205                 :      220735 :               if (!argi || !operand_equal_p (arg0, argi))
     206                 :      196121 :                 return;
     207                 :             :             }
     208                 :       38514 :           set_global_equiv (lhs, arg0);
     209                 :             :         }
     210                 :             :     }
     211                 :             : 
     212                 :    33081542 :   edge pred = single_pred_edge_ignoring_loop_edges (bb, false);
     213                 :    33081542 :   if (pred)
     214                 :    24208951 :     visit_edge (pred);
     215                 :             : }
     216                 :             : 
     217                 :             : // Method to be called on exit from a BB.
     218                 :             : 
     219                 :             : void
     220                 :    33277663 : pointer_equiv_analyzer::leave (basic_block bb)
     221                 :             : {
     222                 :    33277663 :   m_cond_points->leave (bb);
     223                 :    33277663 : }
     224                 :             : 
     225                 :             : // Helper function to return the pointer equivalency information for
     226                 :             : // EXPR from a gimple statement with CODE.  This returns either the
     227                 :             : // cached pointer equivalency info for an SSA, or an invariant in case
     228                 :             : // EXPR is one (i.e. &foo).  Returns NULL if EXPR is neither an SSA
     229                 :             : // nor an invariant.
     230                 :             : 
     231                 :             : tree
     232                 :    11771813 : pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr)
     233                 :             : {
     234                 :    11771813 :   if (code == SSA_NAME)
     235                 :       18339 :     return get_equiv (expr);
     236                 :             : 
     237                 :    11753474 :   if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
     238                 :    11753474 :       && is_gimple_min_invariant (expr))
     239                 :             :     return expr;
     240                 :             : 
     241                 :             :   return NULL;
     242                 :             : }
     243                 :             : 
     244                 :             : // Hack to provide context to the gimple fold callback.
     245                 :             : static struct
     246                 :             : {
     247                 :             :   gimple *m_stmt;
     248                 :             :   gimple_ranger *m_ranger;
     249                 :             :   pointer_equiv_analyzer *m_pta;
     250                 :             : } x_fold_context;
     251                 :             : 
     252                 :             : // Gimple fold callback.
     253                 :             : static tree
     254                 :    29510511 : pta_valueize (tree name)
     255                 :             : {
     256                 :    29510511 :   tree ret
     257                 :    29510511 :     = x_fold_context.m_ranger->value_of_expr (name, x_fold_context.m_stmt);
     258                 :             : 
     259                 :    29510511 :   if (!ret && supported_pointer_equiv_p (name))
     260                 :    11620870 :     ret = x_fold_context.m_pta->get_equiv (name);
     261                 :             : 
     262                 :    29510511 :   return ret ? ret : name;
     263                 :             : }
     264                 :             : 
     265                 :             : // Method to be called on gimple statements during traversal of the IL.
     266                 :             : 
     267                 :             : void
     268                 :   194585228 : pointer_equiv_analyzer::visit_stmt (gimple *stmt)
     269                 :             : {
     270                 :   194585228 :   if (gimple_code (stmt) != GIMPLE_ASSIGN)
     271                 :             :     return;
     272                 :             : 
     273                 :    60487991 :   tree lhs = gimple_assign_lhs (stmt);
     274                 :    60487991 :   if (!supported_pointer_equiv_p (lhs))
     275                 :             :     return;
     276                 :             : 
     277                 :    10435109 :   tree rhs = gimple_assign_rhs1 (stmt);
     278                 :    10435109 :   rhs = get_equiv_expr (gimple_assign_rhs_code (stmt), rhs);
     279                 :    10435109 :   if (rhs)
     280                 :             :     {
     281                 :        3838 :       set_global_equiv (lhs, rhs);
     282                 :        3838 :       return;
     283                 :             :     }
     284                 :             : 
     285                 :             :   // If we couldn't find anything, try fold.
     286                 :    10431271 :   x_fold_context = { stmt, m_ranger, this};
     287                 :    10431271 :   rhs = gimple_fold_stmt_to_constant_1 (stmt, pta_valueize, pta_valueize);
     288                 :    10431271 :   if (rhs)
     289                 :             :     {
     290                 :     1336704 :       rhs = get_equiv_expr (TREE_CODE (rhs), rhs);
     291                 :     1336704 :       if (rhs)
     292                 :             :         {
     293                 :        4934 :           set_global_equiv (lhs, rhs);
     294                 :        4934 :           return;
     295                 :             :         }
     296                 :             :     }
     297                 :             : }
     298                 :             : 
     299                 :             : // If the edge in E is a conditional that sets a pointer equality, set the
     300                 :             : // conditional pointer equivalency information.
     301                 :             : 
     302                 :             : void
     303                 :    24208951 : pointer_equiv_analyzer::visit_edge (edge e)
     304                 :             : {
     305                 :    48417902 :   gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (e->src));
     306                 :    15001989 :   tree lhs;
     307                 :             :   // Recognize: x_13 [==,!=] &foo.
     308                 :    15001989 :   if (stmt
     309                 :    15001989 :       && ((lhs = gimple_cond_lhs (stmt)), true)
     310                 :    15001989 :       && TREE_CODE (lhs) == SSA_NAME
     311                 :    14526184 :       && POINTER_TYPE_P (TREE_TYPE (lhs))
     312                 :     2370126 :       && TREE_CODE (gimple_cond_rhs (stmt)) == ADDR_EXPR)
     313                 :             :     {
     314                 :      299535 :       tree_code code = gimple_cond_code (stmt);
     315                 :      299535 :       if ((code == EQ_EXPR && e->flags & EDGE_TRUE_VALUE)
     316                 :      260617 :           || ((code == NE_EXPR && e->flags & EDGE_FALSE_VALUE)))
     317                 :      115379 :         set_cond_equiv (lhs, gimple_cond_rhs (stmt));
     318                 :             :     }
     319                 :    24208951 : }
        

Generated by: LCOV version 2.0-1

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.