Fix typo in t-dimode
[official-gcc.git] / gcc / value-pointer-equiv.cc
blob5eb9558598d6365a2dc938c211c8d476cc94a21f
1 /* Context-aware pointer equivalence tracker.
2 Copyright (C) 2020-2021 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com>
5 This file is part of GCC.
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.
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.
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/>. */
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"
44 #include "gimple-range.h"
45 #include "fold-const.h"
46 #include "value-pointer-equiv.h"
48 // Unwindable SSA equivalence table for pointers.
50 // The main query point is get_replacement() which returns what a
51 // given SSA can be replaced with in the current scope.
53 class ssa_equiv_stack
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);
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);
68 ssa_equiv_stack::ssa_equiv_stack ()
70 m_replacements.safe_grow_cleared (num_ssa_names + 1);
73 // Pushes a marker at the given point.
75 void
76 ssa_equiv_stack::enter (basic_block)
78 m_stack.safe_push (m_marker);
81 // Pops the stack to the last marker, while performing replacements
82 // along the way.
84 void
85 ssa_equiv_stack::leave (basic_block)
87 gcc_checking_assert (!m_stack.is_empty ());
88 while (m_stack.last () != m_marker)
90 std::pair<tree, tree> e = m_stack.pop ();
91 m_replacements[SSA_NAME_VERSION (e.first)] = e.second;
93 m_stack.pop ();
96 // Set the equivalence of NAME to REPLACEMENT.
98 void
99 ssa_equiv_stack::push_replacement (tree name, tree replacement)
101 unsigned v = SSA_NAME_VERSION (name);
103 if (v >= m_replacements.length ())
104 m_replacements.safe_grow_cleared (num_ssa_names + 1);
106 tree old = m_replacements[v];
107 m_replacements[v] = replacement;
108 m_stack.safe_push (std::make_pair (name, old));
111 // Return the equivalence of NAME.
113 tree
114 ssa_equiv_stack::get_replacement (tree name)
116 unsigned v = SSA_NAME_VERSION (name);
118 if (v >= m_replacements.length ())
119 m_replacements.safe_grow_cleared (num_ssa_names + 1);
121 return m_replacements[v];
124 pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r)
126 m_ranger = r;
127 m_global_points.safe_grow_cleared (num_ssa_names + 1);
128 m_cond_points = new ssa_equiv_stack;
131 pointer_equiv_analyzer::~pointer_equiv_analyzer ()
133 delete m_cond_points;
136 // Set the global pointer equivalency for SSA to POINTEE.
138 void
139 pointer_equiv_analyzer::set_global_equiv (tree ssa, tree pointee)
141 unsigned v = SSA_NAME_VERSION (ssa);
143 if (v >= m_global_points.length ())
144 m_global_points.safe_grow_cleared (num_ssa_names + 1);
146 m_global_points[v] = pointee;
149 // Set the conditional pointer equivalency for SSA to POINTEE.
151 void
152 pointer_equiv_analyzer::set_cond_equiv (tree ssa, tree pointee)
154 m_cond_points->push_replacement (ssa, pointee);
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.
161 tree
162 pointer_equiv_analyzer::get_equiv (tree ssa)
164 unsigned v = SSA_NAME_VERSION (ssa);
166 if (v >= m_global_points.length ())
167 m_global_points.safe_grow_cleared (num_ssa_names + 1);
169 tree ret = m_global_points[v];
170 if (ret)
171 return ret;
172 return m_cond_points->get_replacement (ssa);
175 // Method to be called on entry to a BB.
177 void
178 pointer_equiv_analyzer::enter (basic_block bb)
180 m_cond_points->enter (bb);
182 for (gphi_iterator iter = gsi_start_phis (bb);
183 !gsi_end_p (iter);
184 gsi_next (&iter))
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))
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)
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;
208 set_global_equiv (lhs, arg0);
212 edge pred = single_pred_edge_ignoring_loop_edges (bb, false);
213 if (pred)
214 visit_edge (pred);
217 // Method to be called on exit from a BB.
219 void
220 pointer_equiv_analyzer::leave (basic_block bb)
222 m_cond_points->leave (bb);
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.
231 tree
232 pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr)
234 if (code == SSA_NAME)
235 return get_equiv (expr);
237 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
238 && is_gimple_min_invariant (expr))
239 return expr;
241 return NULL;
244 // Hack to provide context to the gimple fold callback.
245 static struct
247 gimple *m_stmt;
248 gimple_ranger *m_ranger;
249 pointer_equiv_analyzer *m_pta;
250 } x_fold_context;
252 // Gimple fold callback.
253 static tree
254 pta_valueize (tree name)
256 tree ret
257 = x_fold_context.m_ranger->value_of_expr (name, x_fold_context.m_stmt);
259 if (!ret && supported_pointer_equiv_p (name))
260 ret = x_fold_context.m_pta->get_equiv (name);
262 return ret ? ret : name;
265 // Method to be called on gimple statements during traversal of the IL.
267 void
268 pointer_equiv_analyzer::visit_stmt (gimple *stmt)
270 if (gimple_code (stmt) != GIMPLE_ASSIGN)
271 return;
273 tree lhs = gimple_assign_lhs (stmt);
274 if (!supported_pointer_equiv_p (lhs))
275 return;
277 tree rhs = gimple_assign_rhs1 (stmt);
278 rhs = get_equiv_expr (gimple_assign_rhs_code (stmt), rhs);
279 if (rhs)
281 set_global_equiv (lhs, rhs);
282 return;
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)
290 rhs = get_equiv_expr (TREE_CODE (rhs), rhs);
291 if (rhs)
293 set_global_equiv (lhs, rhs);
294 return;
299 // If the edge in E is a conditional that sets a pointer equality, set the
300 // conditional pointer equivalency information.
302 void
303 pointer_equiv_analyzer::visit_edge (edge e)
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)
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));