gcc/value-pointer-equiv.cc

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