1/* Context-aware pointer equivalence tracker.
2 Copyright (C) 2020-2023 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
53class ssa_equiv_stack
54{
55public:
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
62private:
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
68ssa_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
75void
76ssa_equiv_stack::enter (basic_block)
77{
78 m_stack.safe_push (obj: m_marker);
79}
80
81// Pops the stack to the last marker, while performing replacements
82// along the way.
83
84void
85ssa_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
98void
99ssa_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 (obj: std::make_pair (x&: name, y&: old));
109}
110
111// Return the equivalence of NAME.
112
113tree
114ssa_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
124pointer_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
131pointer_equiv_analyzer::~pointer_equiv_analyzer ()
132{
133 delete m_cond_points;
134}
135
136// Set the global pointer equivalency for SSA to POINTEE.
137
138void
139pointer_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
151void
152pointer_equiv_analyzer::set_cond_equiv (tree ssa, tree pointee)
153{
154 m_cond_points->push_replacement (name: ssa, replacement: 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
161tree
162pointer_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 (name: ssa);
173}
174
175// Method to be called on entry to a BB.
176
177void
178pointer_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 (i: iter);
184 gsi_next (i: &iter))
185 {
186 gphi *phi = iter.phi ();
187 tree lhs = gimple_phi_result (gs: phi);
188 if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
189 continue;
190 tree arg0 = gimple_phi_arg_def (gs: phi, index: 0);
191 if (TREE_CODE (arg0) == SSA_NAME && !is_gimple_min_invariant (arg0))
192 arg0 = get_equiv (ssa: 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 (gs: phi); ++i)
200 {
201 tree argi = gimple_phi_arg_def (gs: phi, index: i);
202 if (TREE_CODE (argi) == SSA_NAME
203 && !is_gimple_min_invariant (argi))
204 argi = get_equiv (ssa: argi);
205 if (!argi || !operand_equal_p (arg0, argi))
206 return;
207 }
208 set_global_equiv (ssa: lhs, pointee: arg0);
209 }
210 }
211
212 edge pred = single_pred_edge_ignoring_loop_edges (bb, false);
213 if (pred)
214 visit_edge (e: pred);
215}
216
217// Method to be called on exit from a BB.
218
219void
220pointer_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
231tree
232pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr)
233{
234 if (code == SSA_NAME)
235 return get_equiv (ssa: 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.
245static 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.
253static tree
254pta_valueize (tree name)
255{
256 tree ret
257 = x_fold_context.m_ranger->value_of_expr (expr: name, x_fold_context.m_stmt);
258
259 if (!ret && supported_pointer_equiv_p (expr: name))
260 ret = x_fold_context.m_pta->get_equiv (ssa: name);
261
262 return ret ? ret : name;
263}
264
265// Method to be called on gimple statements during traversal of the IL.
266
267void
268pointer_equiv_analyzer::visit_stmt (gimple *stmt)
269{
270 if (gimple_code (g: stmt) != GIMPLE_ASSIGN)
271 return;
272
273 tree lhs = gimple_assign_lhs (gs: stmt);
274 if (!supported_pointer_equiv_p (expr: lhs))
275 return;
276
277 tree rhs = gimple_assign_rhs1 (gs: stmt);
278 rhs = get_equiv_expr (code: gimple_assign_rhs_code (gs: stmt), expr: rhs);
279 if (rhs)
280 {
281 set_global_equiv (ssa: lhs, pointee: rhs);
282 return;
283 }
284
285 // If we couldn't find anything, try fold.
286 x_fold_context = { .m_stmt: stmt, .m_ranger: m_ranger, .m_pta: 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), expr: rhs);
291 if (rhs)
292 {
293 set_global_equiv (ssa: lhs, pointee: 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
302void
303pointer_equiv_analyzer::visit_edge (edge e)
304{
305 gcond *stmt = safe_dyn_cast <gcond *> (p: *gsi_last_bb (bb: e->src));
306 tree lhs;
307 // Recognize: x_13 [==,!=] &foo.
308 if (stmt
309 && ((lhs = gimple_cond_lhs (gs: stmt)), true)
310 && TREE_CODE (lhs) == SSA_NAME
311 && POINTER_TYPE_P (TREE_TYPE (lhs))
312 && TREE_CODE (gimple_cond_rhs (stmt)) == ADDR_EXPR)
313 {
314 tree_code code = gimple_cond_code (gs: stmt);
315 if ((code == EQ_EXPR && e->flags & EDGE_TRUE_VALUE)
316 || ((code == NE_EXPR && e->flags & EDGE_FALSE_VALUE)))
317 set_cond_equiv (ssa: lhs, pointee: gimple_cond_rhs (gs: stmt));
318 }
319}
320

source code of gcc/value-pointer-equiv.cc