Line data Source code
1 : /* Tree SCC value numbering
2 : Copyright (C) 2007-2026 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 338168118 : sizeof_vn_nary_op (unsigned int length)
73 : {
74 338168118 : 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 26312058 : vn_ref_op_align_unit (vn_reference_op_t op)
128 : {
129 26312058 : 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 62008147 : vn_hash_type (tree type)
173 : {
174 62008147 : return (INTEGRAL_TYPE_P (type)
175 62008147 : + (INTEGRAL_TYPE_P (type)
176 62008147 : ? 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 11771760 : vn_hash_constant_with_type (tree constant)
184 : {
185 11771760 : inchash::hash hstate;
186 11771760 : inchash::add_expr (constant, hstate);
187 11771760 : hstate.merge_hash (vn_hash_type (TREE_TYPE (constant)));
188 11771760 : 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 6855842 : vn_constant_eq_with_type (tree c1, tree c2)
196 : {
197 6855842 : return (expressions_equal_p (c1, c2)
198 6855842 : && 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 : bool vn_pp_nary_for_addr (const vec<vn_reference_op_s>&, tree[2]);
259 : tree vn_nary_op_lookup_stmt (gimple *, vn_nary_op_t *);
260 : tree vn_nary_op_lookup_pieces (unsigned int, enum tree_code,
261 : tree, tree *, vn_nary_op_t *);
262 : vn_nary_op_t vn_nary_op_insert_pieces (unsigned int, enum tree_code,
263 : tree, tree *, tree, unsigned int);
264 : bool ao_ref_init_from_vn_reference (ao_ref *, alias_set_type, alias_set_type,
265 : tree, const vec<vn_reference_op_s> &);
266 : vec<vn_reference_op_s> vn_reference_operands_for_lookup (tree);
267 : tree vn_reference_lookup_pieces (tree, alias_set_type, alias_set_type, tree,
268 : vec<vn_reference_op_s> ,
269 : vn_reference_t *, vn_lookup_kind);
270 : tree vn_reference_lookup (tree, tree, vn_lookup_kind, vn_reference_t *, bool,
271 : tree * = NULL, tree = NULL_TREE, bool = false);
272 : void vn_reference_lookup_call (gcall *, vn_reference_t *, vn_reference_t);
273 : vn_reference_t vn_reference_insert_pieces (tree, alias_set_type, alias_set_type,
274 : poly_int64, poly_int64,
275 : tree, vec<vn_reference_op_s>,
276 : tree, unsigned int);
277 : void print_vn_reference_ops (FILE *, const vec<vn_reference_op_s>);
278 :
279 : bool vn_nary_op_eq (const_vn_nary_op_t const vno1,
280 : const_vn_nary_op_t const vno2);
281 : bool vn_nary_may_trap (vn_nary_op_t);
282 : bool vn_reference_may_trap (vn_reference_t);
283 : bool vn_reference_eq (const_vn_reference_t const, const_vn_reference_t const);
284 :
285 : unsigned int get_max_value_id (void);
286 : unsigned int get_max_constant_value_id (void);
287 : unsigned int get_next_value_id (void);
288 : unsigned int get_next_constant_value_id (void);
289 : unsigned int get_constant_value_id (tree);
290 : unsigned int get_or_alloc_constant_value_id (tree);
291 :
292 : /* Return true if V is a value id for a constant. */
293 : inline bool
294 466437947 : value_id_constant_p (unsigned int v)
295 : {
296 466437947 : return (int)v < 0;
297 : }
298 :
299 : tree fully_constant_vn_reference_p (vn_reference_t);
300 : tree vn_nary_simplify (vn_nary_op_t);
301 :
302 : unsigned do_rpo_vn (function *, edge, bitmap,
303 : /* iterate */ bool = false,
304 : /* eliminate */ bool = true,
305 : /* skip_entry_phis */ bool = false,
306 : vn_lookup_kind = VN_WALKREWRITE);
307 :
308 : /* Private interface for PRE. */
309 : void run_rpo_vn (vn_lookup_kind);
310 : unsigned eliminate_with_rpo_vn (bitmap);
311 : void free_rpo_vn (void);
312 :
313 : /* Valueize NAME if it is an SSA name, otherwise just return it. This hook
314 : is initialized by run_scc_vn. */
315 : extern tree (*vn_valueize) (tree);
316 :
317 : /* Context that valueization should operate on. */
318 : extern basic_block vn_context_bb;
319 :
320 :
321 : #endif /* TREE_SSA_SCCVN_H */
|
