xref: /netbsd-src/external/gpl3/gcc/dist/gcc/value-pointer-equiv.cc (revision b1e838363e3c6fc78a55519254d99869742dd33c)
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-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-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 
ssa_equiv_stack()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
enter(basic_block)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
leave(basic_block)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
push_replacement(tree name,tree replacement)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
get_replacement(tree name)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 
pointer_equiv_analyzer(gimple_ranger * r)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 
~pointer_equiv_analyzer()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
set_global_equiv(tree ssa,tree pointee)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
set_cond_equiv(tree ssa,tree pointee)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
get_equiv(tree ssa)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
enter(basic_block bb)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
leave(basic_block bb)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
get_equiv_expr(tree_code code,tree expr)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
pta_valueize(tree name)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
visit_stmt(gimple * stmt)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
visit_edge(edge e)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 }
321