]>
Commit | Line | Data |
---|---|---|
924326b3 AH |
1 | /* Context-aware pointer equivalence tracker. |
2 | Copyright (C) 2020-2021 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" | |
924326b3 AH |
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); | |
bb27f5e9 | 60 | tree get_replacement (tree name); |
924326b3 AH |
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 | { | |
bb27f5e9 | 70 | m_replacements.safe_grow_cleared (num_ssa_names + 1); |
924326b3 AH |
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 (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 | { | |
bb27f5e9 AH |
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; | |
924326b3 AH |
108 | m_stack.safe_push (std::make_pair (name, old)); |
109 | } | |
110 | ||
111 | // Return the equivalence of NAME. | |
112 | ||
113 | tree | |
bb27f5e9 | 114 | ssa_equiv_stack::get_replacement (tree name) |
924326b3 | 115 | { |
bb27f5e9 AH |
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]; | |
924326b3 AH |
122 | } |
123 | ||
124 | pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r) | |
125 | { | |
126 | m_ranger = r; | |
bb27f5e9 | 127 | m_global_points.safe_grow_cleared (num_ssa_names + 1); |
924326b3 AH |
128 | m_cond_points = new ssa_equiv_stack; |
129 | } | |
130 | ||
131 | pointer_equiv_analyzer::~pointer_equiv_analyzer () | |
132 | { | |
924326b3 AH |
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 | { | |
bb27f5e9 AH |
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; | |
924326b3 AH |
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 (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 | |
bb27f5e9 | 162 | pointer_equiv_analyzer::get_equiv (tree ssa) |
924326b3 | 163 | { |
bb27f5e9 AH |
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]; | |
924326b3 AH |
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 | |
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 | |
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 | |
bb27f5e9 | 232 | pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr) |
924326b3 AH |
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 | |
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 | |
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 | |
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 | } |