1 /* Context-aware pointer equivalence tracker.
2 Copyright (C) 2020-2022 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
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
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/>. */
23 #include "coretypes.h"
27 #include "tree-pass.h"
29 #include "gimple-pretty-print.h"
31 #include "gimple-fold.h"
33 #include "gimple-iterator.h"
35 #include "tree-ssa-loop-manip.h"
36 #include "tree-ssa-loop.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-ssa-propagate.h"
40 #include "alloc-pool.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.
57 void enter (basic_block
);
58 void leave (basic_block
);
59 void push_replacement (tree name
, tree replacement
);
60 tree
get_replacement (tree name
);
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.
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
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
;
96 // Set the equivalence of NAME to REPLACEMENT.
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.
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
)
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.
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.
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
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
];
172 return m_cond_points
->get_replacement (ssa
);
175 // Method to be called on entry to a BB.
178 pointer_equiv_analyzer::enter (basic_block bb
)
180 m_cond_points
->enter (bb
);
182 for (gphi_iterator iter
= gsi_start_phis (bb
);
186 gphi
*phi
= iter
.phi ();
187 tree lhs
= gimple_phi_result (phi
);
188 if (!POINTER_TYPE_P (TREE_TYPE (lhs
)))
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
))
208 set_global_equiv (lhs
, arg0
);
212 edge pred
= single_pred_edge_ignoring_loop_edges (bb
, false);
217 // Method to be called on exit from a BB.
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
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
))
244 // Hack to provide context to the gimple fold callback.
248 gimple_ranger
*m_ranger
;
249 pointer_equiv_analyzer
*m_pta
;
252 // Gimple fold callback.
254 pta_valueize (tree name
)
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.
268 pointer_equiv_analyzer::visit_stmt (gimple
*stmt
)
270 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
273 tree lhs
= gimple_assign_lhs (stmt
);
274 if (!supported_pointer_equiv_p (lhs
))
277 tree rhs
= gimple_assign_rhs1 (stmt
);
278 rhs
= get_equiv_expr (gimple_assign_rhs_code (stmt
), rhs
);
281 set_global_equiv (lhs
, rhs
);
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
);
290 rhs
= get_equiv_expr (TREE_CODE (rhs
), rhs
);
293 set_global_equiv (lhs
, rhs
);
299 // If the edge in E is a conditional that sets a pointer equality, set the
300 // conditional pointer equivalency information.
303 pointer_equiv_analyzer::visit_edge (edge e
)
305 gimple
*stmt
= last_stmt (e
->src
);
307 // Recognize: x_13 [==,!=] &foo.
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
));