1 | /* Tree SCC value numbering |
2 | Copyright (C) 2007-2024 Free Software Foundation, Inc. |
3 | Contributed by Daniel Berlin <dberlin@dberlin.org> |
4 | |
5 | This file is part of GCC. |
6 | |
7 | GCC is free software; you can redistribute it and/or modify |
8 | under the terms of the GNU General Public License as published by |
9 | the Free Software Foundation; either version 3 of the License, or |
10 | (at your option) any later version. |
11 | |
12 | GCC is distributed in the hope that it will be useful, |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
15 | GNU General Public License 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 | #ifndef TREE_SSA_SCCVN_H |
22 | #define TREE_SSA_SCCVN_H |
23 | |
24 | /* In tree-ssa-sccvn.cc */ |
25 | bool expressions_equal_p (tree, tree, bool = true); |
26 | |
27 | |
28 | /* TOP of the VN lattice. */ |
29 | extern tree VN_TOP; |
30 | |
31 | /* A predicated value. */ |
32 | struct vn_pval |
33 | { |
34 | vn_pval *next; |
35 | /* The value of the expression this is attached to is RESULT in |
36 | case the expression is computed dominated by one of the blocks |
37 | in valid_dominated_by_p. */ |
38 | tree result; |
39 | unsigned n; |
40 | int valid_dominated_by_p[1]; |
41 | }; |
42 | |
43 | /* N-ary operations in the hashtable consist of length operands, an |
44 | opcode, and a type. Result is the value number of the operation, |
45 | and hashcode is stored to avoid having to calculate it |
46 | repeatedly. */ |
47 | |
48 | typedef struct vn_nary_op_s |
49 | { |
50 | vn_nary_op_s *next; |
51 | vn_nary_op_s *unwind_to; |
52 | /* Unique identify that all expressions with the same value have. */ |
53 | unsigned int value_id; |
54 | ENUM_BITFIELD(tree_code) opcode : 16; |
55 | unsigned length : 16; |
56 | hashval_t hashcode; |
57 | unsigned predicated_values : 1; |
58 | union { |
59 | /* If ! predicated_values this is the value of the expression. */ |
60 | tree result; |
61 | /* If predicated_values this is a list of values of the expression. */ |
62 | vn_pval *values; |
63 | } u; |
64 | tree type; |
65 | tree op[1]; |
66 | } *vn_nary_op_t; |
67 | typedef const struct vn_nary_op_s *const_vn_nary_op_t; |
68 | |
69 | /* Return the size of a vn_nary_op_t with LENGTH operands. */ |
70 | |
71 | inline size_t |
72 | sizeof_vn_nary_op (unsigned int length) |
73 | { |
74 | return sizeof (struct vn_nary_op_s) + sizeof (tree) * length - sizeof (tree); |
75 | } |
76 | |
77 | /* Phi nodes in the hashtable consist of their non-VN_TOP phi |
78 | arguments, and the basic block the phi is in. Result is the value |
79 | number of the operation, and hashcode is stored to avoid having to |
80 | calculate it repeatedly. Phi nodes not in the same block are never |
81 | considered equivalent. */ |
82 | |
83 | typedef struct vn_phi_s |
84 | { |
85 | vn_phi_s *next; |
86 | /* Unique identifier that all expressions with the same value have. */ |
87 | unsigned int value_id; |
88 | hashval_t hashcode; |
89 | basic_block block; |
90 | /* Controlling condition lhs/rhs. */ |
91 | tree cclhs; |
92 | tree ccrhs; |
93 | tree type; |
94 | tree result; |
95 | /* The number of args is determined by EDGE_COUT (block->preds). */ |
96 | tree phiargs[1]; |
97 | } *vn_phi_t; |
98 | typedef const struct vn_phi_s *const_vn_phi_t; |
99 | |
100 | /* Reference operands only exist in reference operations structures. |
101 | They consist of an opcode, type, and some number of operands. For |
102 | a given opcode, some, all, or none of the operands may be used. |
103 | The operands are there to store the information that makes up the |
104 | portion of the addressing calculation that opcode performs. */ |
105 | |
106 | typedef struct vn_reference_op_struct |
107 | { |
108 | ENUM_BITFIELD(tree_code) opcode : 16; |
109 | /* Dependence info, used for [TARGET_]MEM_REF only. For internal |
110 | function calls clique is also used for the internal function code. */ |
111 | unsigned short clique; |
112 | unsigned short base; |
113 | unsigned reverse : 1; |
114 | /* For storing TYPE_ALIGN for array ref element size computation. */ |
115 | unsigned align : 6; |
116 | /* Constant offset this op adds or -1 if it is variable. */ |
117 | poly_int64 off; |
118 | tree type; |
119 | tree op0; |
120 | tree op1; |
121 | tree op2; |
122 | } vn_reference_op_s; |
123 | typedef vn_reference_op_s *vn_reference_op_t; |
124 | typedef const vn_reference_op_s *const_vn_reference_op_t; |
125 | |
126 | inline unsigned |
127 | vn_ref_op_align_unit (vn_reference_op_t op) |
128 | { |
129 | return op->align ? ((unsigned)1 << (op->align - 1)) / BITS_PER_UNIT : 0; |
130 | } |
131 | |
132 | /* A reference operation in the hashtable is representation as |
133 | the vuse, representing the memory state at the time of |
134 | the operation, and a collection of operands that make up the |
135 | addressing calculation. If two vn_reference_t's have the same set |
136 | of operands, they access the same memory location. We also store |
137 | the resulting value number, and the hashcode. */ |
138 | |
139 | typedef struct vn_reference_s |
140 | { |
141 | vn_reference_s *next; |
142 | /* Unique identifier that all expressions with the same value have. */ |
143 | unsigned int value_id; |
144 | hashval_t hashcode; |
145 | tree vuse; |
146 | alias_set_type set; |
147 | alias_set_type base_set; |
148 | poly_int64 offset; |
149 | poly_int64 max_size; |
150 | tree type; |
151 | unsigned punned : 1; |
152 | vec<vn_reference_op_s> operands; |
153 | tree result; |
154 | tree result_vdef; |
155 | } *vn_reference_t; |
156 | typedef const struct vn_reference_s *const_vn_reference_t; |
157 | |
158 | typedef struct vn_constant_s |
159 | { |
160 | unsigned int value_id; |
161 | hashval_t hashcode; |
162 | tree constant; |
163 | } *vn_constant_t; |
164 | |
165 | enum vn_kind { VN_NONE, VN_CONSTANT, VN_NARY, VN_REFERENCE, VN_PHI }; |
166 | enum vn_kind vn_get_stmt_kind (gimple *); |
167 | |
168 | /* Hash the type TYPE using bits that distinguishes it in the |
169 | types_compatible_p sense. */ |
170 | |
171 | inline hashval_t |
172 | vn_hash_type (tree type) |
173 | { |
174 | return (INTEGRAL_TYPE_P (type) |
175 | + (INTEGRAL_TYPE_P (type) |
176 | ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0)); |
177 | } |
178 | |
179 | /* Hash the constant CONSTANT with distinguishing type incompatible |
180 | constants in the types_compatible_p sense. */ |
181 | |
182 | inline hashval_t |
183 | vn_hash_constant_with_type (tree constant) |
184 | { |
185 | inchash::hash hstate; |
186 | inchash::add_expr (constant, hstate); |
187 | hstate.merge_hash (other: vn_hash_type (TREE_TYPE (constant))); |
188 | return hstate.end (); |
189 | } |
190 | |
191 | /* Compare the constants C1 and C2 with distinguishing type incompatible |
192 | constants in the types_compatible_p sense. */ |
193 | |
194 | inline bool |
195 | vn_constant_eq_with_type (tree c1, tree c2) |
196 | { |
197 | return (expressions_equal_p (c1, c2) |
198 | && types_compatible_p (TREE_TYPE (c1), TREE_TYPE (c2))); |
199 | } |
200 | |
201 | /* Instead of having a local availability lattice for each basic-block |
202 | and availability at X defined as union of the local availabilities |
203 | at X and its dominators we're turning this upside down and track |
204 | availability per value given values are usually made available at very |
205 | few points. |
206 | So we have a chain of LOCATION, LEADER entries where LOCATION is |
207 | specifying the basic-block LEADER is made available for VALUE. |
208 | We prepend to this chain in RPO order thus for iteration we can simply |
209 | remove the last entries. |
210 | LOCATION is the basic-block index and LEADER is its SSA name version. */ |
211 | struct vn_avail |
212 | { |
213 | vn_avail *next; |
214 | /* The basic-block LEADER is made available. */ |
215 | int location; |
216 | /* The LEADER for the value we are chained on. */ |
217 | int leader; |
218 | /* The previous value we pushed a avail record to. */ |
219 | struct vn_ssa_aux *next_undo; |
220 | }; |
221 | |
222 | typedef struct vn_ssa_aux |
223 | { |
224 | /* SSA name this vn_ssa_aux is associated with in the lattice. */ |
225 | tree name; |
226 | /* Value number. This may be an SSA name or a constant. */ |
227 | tree valnum; |
228 | /* Statements to insert if needs_insertion is true. */ |
229 | gimple_seq expr; |
230 | |
231 | /* AVAIL entries, last in RPO order is first. This is only tracked |
232 | for SSA names also serving as values (NAME == VALNUM). */ |
233 | vn_avail *avail; |
234 | |
235 | /* Unique identifier that all expressions with the same value have. */ |
236 | unsigned int value_id; |
237 | |
238 | /* Whether the SSA_NAME has been processed at least once. */ |
239 | unsigned visited : 1; |
240 | |
241 | /* Whether the SSA_NAME has no defining statement and thus an |
242 | insertion of such with EXPR as definition is required before |
243 | a use can be created of it. */ |
244 | unsigned needs_insertion : 1; |
245 | } *vn_ssa_aux_t; |
246 | |
247 | enum vn_lookup_kind { VN_NOWALK, VN_WALK, VN_WALKREWRITE }; |
248 | |
249 | /* Return the value numbering info for an SSA_NAME. */ |
250 | bool has_VN_INFO (tree); |
251 | extern vn_ssa_aux_t VN_INFO (tree); |
252 | tree vn_get_expr_for (tree); |
253 | void scc_vn_restore_ssa_info (void); |
254 | vn_nary_op_t alloc_vn_nary_op_noinit (unsigned int, struct obstack *); |
255 | unsigned int vn_nary_length_from_stmt (gimple *); |
256 | void init_vn_nary_op_from_stmt (vn_nary_op_t, gassign *); |
257 | hashval_t vn_nary_op_compute_hash (const vn_nary_op_t); |
258 | tree vn_nary_op_lookup_stmt (gimple *, vn_nary_op_t *); |
259 | tree vn_nary_op_lookup_pieces (unsigned int, enum tree_code, |
260 | tree, tree *, vn_nary_op_t *); |
261 | vn_nary_op_t vn_nary_op_insert_pieces (unsigned int, enum tree_code, |
262 | tree, tree *, tree, unsigned int); |
263 | bool ao_ref_init_from_vn_reference (ao_ref *, alias_set_type, alias_set_type, |
264 | tree, const vec<vn_reference_op_s> &); |
265 | vec<vn_reference_op_s> vn_reference_operands_for_lookup (tree); |
266 | tree vn_reference_lookup_pieces (tree, alias_set_type, alias_set_type, tree, |
267 | vec<vn_reference_op_s> , |
268 | vn_reference_t *, vn_lookup_kind); |
269 | tree vn_reference_lookup (tree, tree, vn_lookup_kind, vn_reference_t *, bool, |
270 | tree * = NULL, tree = NULL_TREE, bool = false); |
271 | void vn_reference_lookup_call (gcall *, vn_reference_t *, vn_reference_t); |
272 | vn_reference_t vn_reference_insert_pieces (tree, alias_set_type, alias_set_type, |
273 | poly_int64, poly_int64, |
274 | tree, vec<vn_reference_op_s>, |
275 | tree, unsigned int); |
276 | void print_vn_reference_ops (FILE *, const vec<vn_reference_op_s>); |
277 | |
278 | bool vn_nary_op_eq (const_vn_nary_op_t const vno1, |
279 | const_vn_nary_op_t const vno2); |
280 | bool vn_nary_may_trap (vn_nary_op_t); |
281 | bool vn_reference_may_trap (vn_reference_t); |
282 | bool vn_reference_eq (const_vn_reference_t const, const_vn_reference_t const); |
283 | |
284 | unsigned int get_max_value_id (void); |
285 | unsigned int get_max_constant_value_id (void); |
286 | unsigned int get_next_value_id (void); |
287 | unsigned int get_next_constant_value_id (void); |
288 | unsigned int get_constant_value_id (tree); |
289 | unsigned int get_or_alloc_constant_value_id (tree); |
290 | |
291 | /* Return true if V is a value id for a constant. */ |
292 | inline bool |
293 | value_id_constant_p (unsigned int v) |
294 | { |
295 | return (int)v < 0; |
296 | } |
297 | |
298 | tree fully_constant_vn_reference_p (vn_reference_t); |
299 | tree vn_nary_simplify (vn_nary_op_t); |
300 | |
301 | unsigned do_rpo_vn (function *, edge, bitmap, |
302 | /* iterate */ bool = false, |
303 | /* eliminate */ bool = true, |
304 | /* skip_entry_phis */ bool = false, |
305 | vn_lookup_kind = VN_WALKREWRITE); |
306 | |
307 | /* Private interface for PRE. */ |
308 | void run_rpo_vn (vn_lookup_kind); |
309 | unsigned eliminate_with_rpo_vn (bitmap); |
310 | void free_rpo_vn (void); |
311 | |
312 | /* Valueize NAME if it is an SSA name, otherwise just return it. This hook |
313 | is initialized by run_scc_vn. */ |
314 | extern tree (*vn_valueize) (tree); |
315 | |
316 | /* Context that valueization should operate on. */ |
317 | extern basic_block vn_context_bb; |
318 | |
319 | |
320 | #endif /* TREE_SSA_SCCVN_H */ |
321 | |