1 | /* Context-aware pointer equivalence tracker. |
2 | Copyright (C) 2020-2023 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 | 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 | |
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 |
76 | ssa_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 | |
84 | void |
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 |
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 (obj: std::make_pair (x&: name, y&: old)); |
109 | } |
110 | |
111 | // Return the equivalence of NAME. |
112 | |
113 | tree |
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 | |
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 | |
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 |
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 |
152 | pointer_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 | |
161 | tree |
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 (name: ssa); |
173 | } |
174 | |
175 | // Method to be called on entry to a BB. |
176 | |
177 | void |
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 (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 | |
219 | void |
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 |
232 | pointer_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. |
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 | pta_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 | |
267 | void |
268 | pointer_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 | |
302 | void |
303 | pointer_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 | |