gcc/value-pointer-equiv.cc

   1 /* Context-aware pointer equivalence tracker.
   2    Copyright (C) 2020-2022 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 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   const std::pair <tree, tree> m_marker = std::make_pair (NULL, NULL);
  66 };
  67
  68 ssa_equiv_stack::ssa_equiv_stack ()
  69 {
  70   m_replacements.safe_grow_cleared (num_ssa_names + 1);
  71 }
  72
  73 // Pushes a marker at the given point.
  74
  75 void
  76 ssa_equiv_stack::enter (basic_block)
  77 {
  78   m_stack.safe_push (m_marker);
  79 }
  80
  81 // Pops the stack to the last marker, while performing replacements
  82 // along the way.
  83
  84 void
  85 ssa_equiv_stack::leave (basic_block)
  86 {
  87   gcc_checking_assert (!m_stack.is_empty ());
  88   while (m_stack.last () != m_marker)
  89     {
  90       std::pair<tree, tree> e = m_stack.pop ();
  91       m_replacements[SSA_NAME_VERSION (e.first)] = e.second;
  92     }
  93   m_stack.pop ();
  94 }
  95
  96 // Set the equivalence of NAME to REPLACEMENT.
  97
  98 void
  99 ssa_equiv_stack::push_replacement (tree name, tree replacement)
 100 {
 101   unsigned v = SSA_NAME_VERSION (name);
 102
 103   if (v >= m_replacements.length ())
 104     m_replacements.safe_grow_cleared (num_ssa_names + 1);
 105
 106   tree old = m_replacements[v];
 107   m_replacements[v] = replacement;
 108   m_stack.safe_push (std::make_pair (name, old));
 109 }
 110
 111 // Return the equivalence of NAME.
 112
 113 tree
 114 ssa_equiv_stack::get_replacement (tree name)
 115 {
 116   unsigned v = SSA_NAME_VERSION (name);
 117
 118   if (v >= m_replacements.length ())
 119     m_replacements.safe_grow_cleared (num_ssa_names + 1);
 120
 121   return m_replacements[v];
 122 }
 123
 124 pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r)
 125 {
 126   m_ranger = r;
 127   m_global_points.safe_grow_cleared (num_ssa_names + 1);
 128   m_cond_points = new ssa_equiv_stack;
 129 }
 130
 131 pointer_equiv_analyzer::~pointer_equiv_analyzer ()
 132 {
 133   delete m_cond_points;
 134 }
 135
 136 // Set the global pointer equivalency for SSA to POINTEE.
 137
 138 void
 139 pointer_equiv_analyzer::set_global_equiv (tree ssa, tree pointee)
 140 {
 141   unsigned v = SSA_NAME_VERSION (ssa);
 142
 143   if (v >= m_global_points.length ())
 144     m_global_points.safe_grow_cleared (num_ssa_names + 1);
 145
 146   m_global_points[v] = pointee;
 147 }
 148
 149 // Set the conditional pointer equivalency for SSA to POINTEE.
 150
 151 void
 152 pointer_equiv_analyzer::set_cond_equiv (tree ssa, tree pointee)
 153 {
 154   m_cond_points->push_replacement (ssa, pointee);
 155 }
 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 pointer_equiv_analyzer::get_equiv (tree ssa)
 163 {
 164   unsigned v = SSA_NAME_VERSION (ssa);
 165
 166   if (v >= m_global_points.length ())
 167     m_global_points.safe_grow_cleared (num_ssa_names + 1);
 168
 169   tree ret = m_global_points[v];
 170   if (ret)
 171     return ret;
 172   return m_cond_points->get_replacement (ssa);
 173 }
 174
 175 // Method to be called on entry to a BB.
 176
 177 void
 178 pointer_equiv_analyzer::enter (basic_block bb)
 179 {
 180   m_cond_points->enter (bb);
 181
 182   for (gphi_iterator iter = gsi_start_phis (bb);
 183        !gsi_end_p (iter);
 184        gsi_next (&iter))
 185     {
 186       gphi *phi = iter.phi ();
 187       tree lhs = gimple_phi_result (phi);
 188       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
 189         continue;
 190       tree arg0 = gimple_phi_arg_def (phi, 0);
 191       if (TREE_CODE (arg0) == SSA_NAME && !is_gimple_min_invariant (arg0))
 192         arg0 = get_equiv (arg0);
 193       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           for (size_t i = 1; i < gimple_phi_num_args (phi); ++i)
 200             {
 201               tree argi = gimple_phi_arg_def (phi, i);
 202               if (TREE_CODE (argi) == SSA_NAME
 203                   && !is_gimple_min_invariant (argi))
 204                 argi = get_equiv (argi);
 205               if (!argi || !operand_equal_p (arg0, argi))
 206                 return;
 207             }
 208           set_global_equiv (lhs, arg0);
 209         }
 210     }
 211
 212   edge pred = single_pred_edge_ignoring_loop_edges (bb, false);
 213   if (pred)
 214     visit_edge (pred);
 215 }
 216
 217 // Method to be called on exit from a BB.
 218
 219 void
 220 pointer_equiv_analyzer::leave (basic_block bb)
 221 {
 222   m_cond_points->leave (bb);
 223 }
 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 pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr)
 233 {
 234   if (code == SSA_NAME)
 235     return get_equiv (expr);
 236
 237   if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
 238       && 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 pta_valueize (tree name)
 255 {
 256   tree ret
 257     = x_fold_context.m_ranger->value_of_expr (name, x_fold_context.m_stmt);
 258
 259   if (!ret && supported_pointer_equiv_p (name))
 260     ret = x_fold_context.m_pta->get_equiv (name);
 261
 262   return ret ? ret : name;
 263 }
 264
 265 // Method to be called on gimple statements during traversal of the IL.
 266
 267 void
 268 pointer_equiv_analyzer::visit_stmt (gimple *stmt)
 269 {
 270   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 271     return;
 272
 273   tree lhs = gimple_assign_lhs (stmt);
 274   if (!supported_pointer_equiv_p (lhs))
 275     return;
 276
 277   tree rhs = gimple_assign_rhs1 (stmt);
 278   rhs = get_equiv_expr (gimple_assign_rhs_code (stmt), rhs);
 279   if (rhs)
 280     {
 281       set_global_equiv (lhs, rhs);
 282       return;
 283     }
 284
 285   // If we couldn't find anything, try fold.
 286   x_fold_context = { stmt, m_ranger, this};
 287   rhs = gimple_fold_stmt_to_constant_1 (stmt, pta_valueize, pta_valueize);
 288   if (rhs)
 289     {
 290       rhs = get_equiv_expr (TREE_CODE (rhs), rhs);
 291       if (rhs)
 292         {
 293           set_global_equiv (lhs, rhs);
 294           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 pointer_equiv_analyzer::visit_edge (edge e)
 304 {
 305   gimple *stmt = last_stmt (e->src);
 306   tree lhs;
 307   // Recognize: x_13 [==,!=] &foo.
 308   if (stmt
 309       && gimple_code (stmt) == GIMPLE_COND
 310       && (lhs = gimple_cond_lhs (stmt))
 311       && TREE_CODE (lhs) == SSA_NAME
 312       && POINTER_TYPE_P (TREE_TYPE (lhs))
 313       && TREE_CODE (gimple_cond_rhs (stmt)) == ADDR_EXPR)
 314     {
 315       tree_code code = gimple_cond_code (stmt);
 316       if ((code == EQ_EXPR && e->flags & EDGE_TRUE_VALUE)
 317           || ((code == NE_EXPR && e->flags & EDGE_FALSE_VALUE)))
 318         set_cond_equiv (lhs, gimple_cond_rhs (stmt));
 319     }
 320 }