1 | /* Tree SCC value numbering |
2 | Copyright (C) 2007-2023 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 | tree type; |
149 | unsigned punned : 1; |
150 | vec<vn_reference_op_s> operands; |
151 | tree result; |
152 | tree result_vdef; |
153 | } *vn_reference_t; |
154 | typedef const struct vn_reference_s *const_vn_reference_t; |
155 | |
156 | typedef struct vn_constant_s |
157 | { |
158 | unsigned int value_id; |
159 | hashval_t hashcode; |
160 | tree constant; |
161 | } *vn_constant_t; |
162 | |
163 | enum vn_kind { VN_NONE, VN_CONSTANT, VN_NARY, VN_REFERENCE, VN_PHI }; |
164 | enum vn_kind vn_get_stmt_kind (gimple *); |
165 | |
166 | /* Hash the type TYPE using bits that distinguishes it in the |
167 | types_compatible_p sense. */ |
168 | |
169 | inline hashval_t |
170 | vn_hash_type (tree type) |
171 | { |
172 | return (INTEGRAL_TYPE_P (type) |
173 | + (INTEGRAL_TYPE_P (type) |
174 | ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0)); |
175 | } |
176 | |
177 | /* Hash the constant CONSTANT with distinguishing type incompatible |
178 | constants in the types_compatible_p sense. */ |
179 | |
180 | inline hashval_t |
181 | vn_hash_constant_with_type (tree constant) |
182 | { |
183 | inchash::hash hstate; |
184 | inchash::add_expr (constant, hstate); |
185 | hstate.merge_hash (other: vn_hash_type (TREE_TYPE (constant))); |
186 | return hstate.end (); |
187 | } |
188 | |
189 | /* Compare the constants C1 and C2 with distinguishing type incompatible |
190 | constants in the types_compatible_p sense. */ |
191 | |
192 | inline bool |
193 | vn_constant_eq_with_type (tree c1, tree c2) |
194 | { |
195 | return (expressions_equal_p (c1, c2) |
196 | && types_compatible_p (TREE_TYPE (c1), TREE_TYPE (c2))); |
197 | } |
198 | |
199 | /* Instead of having a local availability lattice for each basic-block |
200 | and availability at X defined as union of the local availabilities |
201 | at X and its dominators we're turning this upside down and track |
202 | availability per value given values are usually made available at very |
203 | few points. |
204 | So we have a chain of LOCATION, LEADER entries where LOCATION is |
205 | specifying the basic-block LEADER is made available for VALUE. |
206 | We prepend to this chain in RPO order thus for iteration we can simply |
207 | remove the last entries. |
208 | LOCATION is the basic-block index and LEADER is its SSA name version. */ |
209 | struct vn_avail |
210 | { |
211 | vn_avail *next; |
212 | /* The basic-block LEADER is made available. */ |
213 | int location; |
214 | /* The LEADER for the value we are chained on. */ |
215 | int leader; |
216 | /* The previous value we pushed a avail record to. */ |
217 | struct vn_ssa_aux *next_undo; |
218 | }; |
219 | |
220 | typedef struct vn_ssa_aux |
221 | { |
222 | /* SSA name this vn_ssa_aux is associated with in the lattice. */ |
223 | tree name; |
224 | /* Value number. This may be an SSA name or a constant. */ |
225 | tree valnum; |
226 | /* Statements to insert if needs_insertion is true. */ |
227 | gimple_seq expr; |
228 | |
229 | /* AVAIL entries, last in RPO order is first. This is only tracked |
230 | for SSA names also serving as values (NAME == VALNUM). */ |
231 | vn_avail *avail; |
232 | |
233 | /* Unique identifier that all expressions with the same value have. */ |
234 | unsigned int value_id; |
235 | |
236 | /* Whether the SSA_NAME has been processed at least once. */ |
237 | unsigned visited : 1; |
238 | |
239 | /* Whether the SSA_NAME has no defining statement and thus an |
240 | insertion of such with EXPR as definition is required before |
241 | a use can be created of it. */ |
242 | unsigned needs_insertion : 1; |
243 | } *vn_ssa_aux_t; |
244 | |
245 | enum vn_lookup_kind { VN_NOWALK, VN_WALK, VN_WALKREWRITE }; |
246 | |
247 | /* Return the value numbering info for an SSA_NAME. */ |
248 | bool has_VN_INFO (tree); |
249 | extern vn_ssa_aux_t VN_INFO (tree); |
250 | tree vn_get_expr_for (tree); |
251 | void scc_vn_restore_ssa_info (void); |
252 | vn_nary_op_t alloc_vn_nary_op_noinit (unsigned int, struct obstack *); |
253 | unsigned int vn_nary_length_from_stmt (gimple *); |
254 | void init_vn_nary_op_from_stmt (vn_nary_op_t, gassign *); |
255 | hashval_t vn_nary_op_compute_hash (const vn_nary_op_t); |
256 | tree vn_nary_op_lookup_stmt (gimple *, vn_nary_op_t *); |
257 | tree vn_nary_op_lookup_pieces (unsigned int, enum tree_code, |
258 | tree, tree *, vn_nary_op_t *); |
259 | vn_nary_op_t vn_nary_op_insert_pieces (unsigned int, enum tree_code, |
260 | tree, tree *, tree, unsigned int); |
261 | bool ao_ref_init_from_vn_reference (ao_ref *, alias_set_type, alias_set_type, |
262 | tree, const vec<vn_reference_op_s> &); |
263 | vec<vn_reference_op_s> vn_reference_operands_for_lookup (tree); |
264 | tree vn_reference_lookup_pieces (tree, alias_set_type, alias_set_type, tree, |
265 | vec<vn_reference_op_s> , |
266 | vn_reference_t *, vn_lookup_kind); |
267 | tree vn_reference_lookup (tree, tree, vn_lookup_kind, vn_reference_t *, bool, |
268 | tree * = NULL, tree = NULL_TREE, bool = false); |
269 | void vn_reference_lookup_call (gcall *, vn_reference_t *, vn_reference_t); |
270 | vn_reference_t vn_reference_insert_pieces (tree, alias_set_type, alias_set_type, |
271 | tree, vec<vn_reference_op_s>, |
272 | tree, unsigned int); |
273 | void print_vn_reference_ops (FILE *, const vec<vn_reference_op_s>); |
274 | |
275 | bool vn_nary_op_eq (const_vn_nary_op_t const vno1, |
276 | const_vn_nary_op_t const vno2); |
277 | bool vn_nary_may_trap (vn_nary_op_t); |
278 | bool vn_reference_may_trap (vn_reference_t); |
279 | bool vn_reference_eq (const_vn_reference_t const, const_vn_reference_t const); |
280 | |
281 | unsigned int get_max_value_id (void); |
282 | unsigned int get_max_constant_value_id (void); |
283 | unsigned int get_next_value_id (void); |
284 | unsigned int get_next_constant_value_id (void); |
285 | unsigned int get_constant_value_id (tree); |
286 | unsigned int get_or_alloc_constant_value_id (tree); |
287 | |
288 | /* Return true if V is a value id for a constant. */ |
289 | inline bool |
290 | value_id_constant_p (unsigned int v) |
291 | { |
292 | return (int)v < 0; |
293 | } |
294 | |
295 | tree fully_constant_vn_reference_p (vn_reference_t); |
296 | tree vn_nary_simplify (vn_nary_op_t); |
297 | |
298 | unsigned do_rpo_vn (function *, edge, bitmap, |
299 | /* iterate */ bool = false, |
300 | /* eliminate */ bool = true, |
301 | vn_lookup_kind = VN_WALKREWRITE); |
302 | |
303 | /* Private interface for PRE. */ |
304 | void run_rpo_vn (vn_lookup_kind); |
305 | unsigned eliminate_with_rpo_vn (bitmap); |
306 | void free_rpo_vn (void); |
307 | |
308 | /* Valueize NAME if it is an SSA name, otherwise just return it. This hook |
309 | is initialized by run_scc_vn. */ |
310 | extern tree (*vn_valueize) (tree); |
311 | |
312 | /* Context that valueization should operate on. */ |
313 | extern basic_block vn_context_bb; |
314 | |
315 | |
316 | #endif /* TREE_SSA_SCCVN_H */ |
317 | |