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) const;
  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);
  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   tree old = m_replacements[SSA_NAME_VERSION (name)];
 103   m_replacements[SSA_NAME_VERSION (name)] = replacement;
 104   m_stack.safe_push (std::make_pair (name, old));
 105 }
 106
 107 // Return the equivalence of NAME.
 108
 109 tree
 110 ssa_equiv_stack::get_replacement (tree name) const
 111 {
 112   return m_replacements[SSA_NAME_VERSION (name)];
 113 }
 114
 115 pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r)
 116 {
 117   m_ranger = r;
 118   m_global_points = new tree[num_ssa_names] ();
 119   m_cond_points = new ssa_equiv_stack;
 120 }
 121
 122 pointer_equiv_analyzer::~pointer_equiv_analyzer ()
 123 {
 124   delete[] m_global_points;
 125   delete m_cond_points;
 126 }
 127
 128 // Set the global pointer equivalency for SSA to POINTEE.
 129
 130 void
 131 pointer_equiv_analyzer::set_global_equiv (tree ssa, tree pointee)
 132 {
 133   m_global_points[SSA_NAME_VERSION (ssa)] = pointee;
 134 }
 135
 136 // Set the conditional pointer equivalency for SSA to POINTEE.
 137
 138 void
 139 pointer_equiv_analyzer::set_cond_equiv (tree ssa, tree pointee)
 140 {
 141   m_cond_points->push_replacement (ssa, pointee);
 142 }
 143
 144 // Return the current pointer equivalency info for SSA, or NULL if
 145 // none is available.  Note that global info takes priority over
 146 // conditional info.
 147
 148 tree
 149 pointer_equiv_analyzer::get_equiv (tree ssa) const
 150 {
 151   tree ret = m_global_points[SSA_NAME_VERSION (ssa)];
 152   if (ret)
 153     return ret;
 154   return m_cond_points->get_replacement (ssa);
 155 }
 156
 157 // Method to be called on entry to a BB.
 158
 159 void
 160 pointer_equiv_analyzer::enter (basic_block bb)
 161 {
 162   m_cond_points->enter (bb);
 163
 164   for (gphi_iterator iter = gsi_start_phis (bb);
 165        !gsi_end_p (iter);
 166        gsi_next (&iter))
 167     {
 168       gphi *phi = iter.phi ();
 169       tree lhs = gimple_phi_result (phi);
 170       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
 171         continue;
 172       tree arg0 = gimple_phi_arg_def (phi, 0);
 173       if (TREE_CODE (arg0) == SSA_NAME && !is_gimple_min_invariant (arg0))
 174         arg0 = get_equiv (arg0);
 175       if (arg0 && is_gimple_min_invariant (arg0))
 176         {
 177           // If all the PHI args point to the same place, set the
 178           // pointer equivalency info for the PHI result.  This can
 179           // happen for passes that create redundant PHIs like
 180           // PHI<&foo, &foo> or PHI<&foo>.
 181           for (size_t i = 1; i < gimple_phi_num_args (phi); ++i)
 182             {
 183               tree argi = gimple_phi_arg_def (phi, i);
 184               if (TREE_CODE (argi) == SSA_NAME
 185                   && !is_gimple_min_invariant (argi))
 186                 argi = get_equiv (argi);
 187               if (!argi || !operand_equal_p (arg0, argi))
 188                 return;
 189             }
 190           set_global_equiv (lhs, arg0);
 191         }
 192     }
 193
 194   edge pred = single_pred_edge_ignoring_loop_edges (bb, false);
 195   if (pred)
 196     visit_edge (pred);
 197 }
 198
 199 // Method to be called on exit from a BB.
 200
 201 void
 202 pointer_equiv_analyzer::leave (basic_block bb)
 203 {
 204   m_cond_points->leave (bb);
 205 }
 206
 207 // Helper function to return the pointer equivalency information for
 208 // EXPR from a gimple statement with CODE.  This returns either the
 209 // cached pointer equivalency info for an SSA, or an invariant in case
 210 // EXPR is one (i.e. &foo).  Returns NULL if EXPR is neither an SSA
 211 // nor an invariant.
 212
 213 tree
 214 pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr) const
 215 {
 216   if (code == SSA_NAME)
 217     return get_equiv (expr);
 218
 219   if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
 220       && is_gimple_min_invariant (expr))
 221     return expr;
 222
 223   return NULL;
 224 }
 225
 226 // Hack to provide context to the gimple fold callback.
 227 static struct
 228 {
 229   gimple *m_stmt;
 230   gimple_ranger *m_ranger;
 231   pointer_equiv_analyzer *m_pta;
 232 } x_fold_context;
 233
 234 // Gimple fold callback.
 235 static tree
 236 pta_valueize (tree name)
 237 {
 238   tree ret
 239     = x_fold_context.m_ranger->value_of_expr (name, x_fold_context.m_stmt);
 240
 241   if (!ret && supported_pointer_equiv_p (name))
 242     ret = x_fold_context.m_pta->get_equiv (name);
 243
 244   return ret ? ret : name;
 245 }
 246
 247 // Method to be called on gimple statements during traversal of the IL.
 248
 249 void
 250 pointer_equiv_analyzer::visit_stmt (gimple *stmt)
 251 {
 252   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 253     return;
 254
 255   tree lhs = gimple_assign_lhs (stmt);
 256   if (!supported_pointer_equiv_p (lhs))
 257     return;
 258
 259   tree rhs = gimple_assign_rhs1 (stmt);
 260   rhs = get_equiv_expr (gimple_assign_rhs_code (stmt), rhs);
 261   if (rhs)
 262     {
 263       set_global_equiv (lhs, rhs);
 264       return;
 265     }
 266
 267   // If we couldn't find anything, try fold.
 268   x_fold_context = { stmt, m_ranger, this};
 269   rhs = gimple_fold_stmt_to_constant_1 (stmt, pta_valueize, pta_valueize);
 270   if (rhs)
 271     {
 272       rhs = get_equiv_expr (TREE_CODE (rhs), rhs);
 273       if (rhs)
 274         {
 275           set_global_equiv (lhs, rhs);
 276           return;
 277         }
 278     }
 279 }
 280
 281 // If the edge in E is a conditional that sets a pointer equality, set the
 282 // conditional pointer equivalency information.
 283
 284 void
 285 pointer_equiv_analyzer::visit_edge (edge e)
 286 {
 287   gimple *stmt = last_stmt (e->src);
 288   tree lhs;
 289   // Recognize: x_13 [==,!=] &foo.
 290   if (stmt
 291       && gimple_code (stmt) == GIMPLE_COND
 292       && (lhs = gimple_cond_lhs (stmt))
 293       && TREE_CODE (lhs) == SSA_NAME
 294       && POINTER_TYPE_P (TREE_TYPE (lhs))
 295       && TREE_CODE (gimple_cond_rhs (stmt)) == ADDR_EXPR)
 296     {
 297       tree_code code = gimple_cond_code (stmt);
 298       if ((code == EQ_EXPR && e->flags & EDGE_TRUE_VALUE)
 299           || ((code == NE_EXPR && e->flags & EDGE_FALSE_VALUE)))
 300         set_cond_equiv (lhs, gimple_cond_rhs (stmt));
 301     }
 302 }