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