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