Branch data Line data Source code
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 : 312519123 : sizeof_vn_nary_op (unsigned int length)
73 : : {
74 : 312519123 : 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 : 26166979 : vn_ref_op_align_unit (vn_reference_op_t op)
128 : : {
129 : 26166979 : 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 : 58077116 : vn_hash_type (tree type)
173 : : {
174 : 58077116 : return (INTEGRAL_TYPE_P (type)
175 : 58077116 : + (INTEGRAL_TYPE_P (type)
176 : 58077116 : ? 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 : 10908291 : vn_hash_constant_with_type (tree constant)
184 : : {
185 : 10908291 : inchash::hash hstate;
186 : 10908291 : inchash::add_expr (constant, hstate);
187 : 10908291 : hstate.merge_hash (vn_hash_type (TREE_TYPE (constant)));
188 : 10908291 : 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 : 6354734 : vn_constant_eq_with_type (tree c1, tree c2)
196 : : {
197 : 6354734 : return (expressions_equal_p (c1, c2)
198 : 6354734 : && 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 : 428290635 : value_id_constant_p (unsigned int v)
294 : : {
295 : 428290635 : 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 */
|
