1 /* Tree SCC value numbering
2 Copyright (C) 2007-2017 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
5 This file is part of GCC.
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.
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.
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/>. */
21 #ifndef TREE_SSA_SCCVN_H
22 #define TREE_SSA_SCCVN_H
24 /* In tree-ssa-sccvn.c */
25 bool expressions_equal_p (tree
, tree
);
28 /* TOP of the VN lattice. */
31 /* N-ary operations in the hashtable consist of length operands, an
32 opcode, and a type. Result is the value number of the operation,
33 and hashcode is stored to avoid having to calculate it
36 typedef struct vn_nary_op_s
38 /* Unique identify that all expressions with the same value have. */
39 unsigned int value_id
;
40 ENUM_BITFIELD(tree_code
) opcode
: 16;
47 typedef const struct vn_nary_op_s
*const_vn_nary_op_t
;
49 /* Return the size of a vn_nary_op_t with LENGTH operands. */
52 sizeof_vn_nary_op (unsigned int length
)
54 return sizeof (struct vn_nary_op_s
) + sizeof (tree
) * length
- sizeof (tree
);
57 /* Phi nodes in the hashtable consist of their non-VN_TOP phi
58 arguments, and the basic block the phi is in. Result is the value
59 number of the operation, and hashcode is stored to avoid having to
60 calculate it repeatedly. Phi nodes not in the same block are never
61 considered equivalent. */
63 typedef struct vn_phi_s
65 /* Unique identifier that all expressions with the same value have. */
66 unsigned int value_id
;
70 /* Controlling condition lhs/rhs. */
76 typedef const struct vn_phi_s
*const_vn_phi_t
;
78 /* Reference operands only exist in reference operations structures.
79 They consist of an opcode, type, and some number of operands. For
80 a given opcode, some, all, or none of the operands may be used.
81 The operands are there to store the information that makes up the
82 portion of the addressing calculation that opcode performs. */
84 typedef struct vn_reference_op_struct
86 ENUM_BITFIELD(tree_code
) opcode
: 16;
87 /* Dependence info, used for [TARGET_]MEM_REF only. */
88 unsigned short clique
;
90 /* 1 for instrumented calls. */
91 unsigned with_bounds
: 1;
93 /* For storing TYPE_ALIGN for array ref element size computation. */
95 /* Constant offset this op adds or -1 if it is variable. */
102 typedef vn_reference_op_s
*vn_reference_op_t
;
103 typedef const vn_reference_op_s
*const_vn_reference_op_t
;
106 vn_ref_op_align_unit (vn_reference_op_t op
)
108 return op
->align
? ((unsigned)1 << (op
->align
- 1)) / BITS_PER_UNIT
: 0;
111 /* A reference operation in the hashtable is representation as
112 the vuse, representing the memory state at the time of
113 the operation, and a collection of operands that make up the
114 addressing calculation. If two vn_reference_t's have the same set
115 of operands, they access the same memory location. We also store
116 the resulting value number, and the hashcode. */
118 typedef struct vn_reference_s
120 /* Unique identifier that all expressions with the same value have. */
121 unsigned int value_id
;
126 vec
<vn_reference_op_s
> operands
;
130 typedef const struct vn_reference_s
*const_vn_reference_t
;
132 typedef struct vn_constant_s
134 unsigned int value_id
;
139 enum vn_kind
{ VN_NONE
, VN_CONSTANT
, VN_NARY
, VN_REFERENCE
, VN_PHI
};
140 enum vn_kind
vn_get_stmt_kind (gimple
*);
142 /* Hash the type TYPE using bits that distinguishes it in the
143 types_compatible_p sense. */
145 static inline hashval_t
146 vn_hash_type (tree type
)
148 return (INTEGRAL_TYPE_P (type
)
149 + (INTEGRAL_TYPE_P (type
)
150 ? TYPE_PRECISION (type
) + TYPE_UNSIGNED (type
) : 0));
153 /* Hash the constant CONSTANT with distinguishing type incompatible
154 constants in the types_compatible_p sense. */
156 static inline hashval_t
157 vn_hash_constant_with_type (tree constant
)
159 inchash::hash hstate
;
160 inchash::add_expr (constant
, hstate
);
161 hstate
.merge_hash (vn_hash_type (TREE_TYPE (constant
)));
162 return hstate
.end ();
165 /* Compare the constants C1 and C2 with distinguishing type incompatible
166 constants in the types_compatible_p sense. */
169 vn_constant_eq_with_type (tree c1
, tree c2
)
171 return (expressions_equal_p (c1
, c2
)
172 && types_compatible_p (TREE_TYPE (c1
), TREE_TYPE (c2
)));
175 typedef struct vn_ssa_aux
177 /* Value number. This may be an SSA name or a constant. */
179 /* Statements to insert if needs_insertion is true. */
182 /* Saved SSA name info. */
183 tree_ssa_name::ssa_name_info_type info
;
185 /* Unique identifier that all expressions with the same value have. */
186 unsigned int value_id
;
188 /* SCC information. */
191 unsigned visited
: 1;
192 unsigned on_sccstack
: 1;
194 /* Whether the SSA_NAME has been value numbered already. This is
195 only saying whether visit_use has been called on it at least
196 once. It cannot be used to avoid visitation for SSA_NAME's
197 involved in non-singleton SCC's. */
198 unsigned use_processed
: 1;
200 /* Whether the SSA_NAME has no defining statement and thus an
201 insertion of such with EXPR as definition is required before
202 a use can be created of it. */
203 unsigned needs_insertion
: 1;
205 /* Whether range-info is anti-range. */
206 unsigned range_info_anti_range_p
: 1;
209 enum vn_lookup_kind
{ VN_NOWALK
, VN_WALK
, VN_WALKREWRITE
};
211 /* Return the value numbering info for an SSA_NAME. */
212 extern vn_ssa_aux_t
VN_INFO (tree
);
213 extern vn_ssa_aux_t
VN_INFO_GET (tree
);
214 tree
vn_get_expr_for (tree
);
215 void run_scc_vn (vn_lookup_kind
);
216 void free_scc_vn (void);
217 void scc_vn_restore_ssa_info (void);
218 tree
vn_nary_op_lookup (tree
, vn_nary_op_t
*);
219 tree
vn_nary_op_lookup_stmt (gimple
*, vn_nary_op_t
*);
220 tree
vn_nary_op_lookup_pieces (unsigned int, enum tree_code
,
221 tree
, tree
*, vn_nary_op_t
*);
222 vn_nary_op_t
vn_nary_op_insert (tree
, tree
);
223 vn_nary_op_t
vn_nary_op_insert_pieces (unsigned int, enum tree_code
,
224 tree
, tree
*, tree
, unsigned int);
225 bool ao_ref_init_from_vn_reference (ao_ref
*, alias_set_type
, tree
,
226 vec
<vn_reference_op_s
> );
227 vec
<vn_reference_op_s
> vn_reference_operands_for_lookup (tree
);
228 tree
vn_reference_lookup_pieces (tree
, alias_set_type
, tree
,
229 vec
<vn_reference_op_s
> ,
230 vn_reference_t
*, vn_lookup_kind
);
231 tree
vn_reference_lookup (tree
, tree
, vn_lookup_kind
, vn_reference_t
*, bool);
232 void vn_reference_lookup_call (gcall
*, vn_reference_t
*, vn_reference_t
);
233 vn_reference_t
vn_reference_insert_pieces (tree
, alias_set_type
, tree
,
234 vec
<vn_reference_op_s
> ,
237 bool vn_nary_op_eq (const_vn_nary_op_t
const vno1
,
238 const_vn_nary_op_t
const vno2
);
239 bool vn_nary_may_trap (vn_nary_op_t
);
240 bool vn_reference_eq (const_vn_reference_t
const, const_vn_reference_t
const);
241 unsigned int get_max_value_id (void);
242 unsigned int get_next_value_id (void);
243 unsigned int get_constant_value_id (tree
);
244 unsigned int get_or_alloc_constant_value_id (tree
);
245 bool value_id_constant_p (unsigned int);
246 tree
fully_constant_vn_reference_p (vn_reference_t
);
247 tree
vn_nary_simplify (vn_nary_op_t
);
249 /* Valueize NAME if it is an SSA name, otherwise just return it. */
252 vn_valueize (tree name
)
254 if (TREE_CODE (name
) == SSA_NAME
)
256 tree tem
= VN_INFO (name
)->valnum
;
257 return tem
== VN_TOP
? name
: tem
;
262 /* Get at the original range info for NAME. */
264 inline range_info_def
*
265 VN_INFO_RANGE_INFO (tree name
)
267 return (VN_INFO (name
)->info
.range_info
268 ? VN_INFO (name
)->info
.range_info
269 : SSA_NAME_RANGE_INFO (name
));
272 /* Whether the original range info of NAME is an anti-range. */
275 VN_INFO_ANTI_RANGE_P (tree name
)
277 return (VN_INFO (name
)->info
.range_info
278 ? VN_INFO (name
)->range_info_anti_range_p
279 : SSA_NAME_ANTI_RANGE_P (name
));
282 /* Get at the original range info kind for NAME. */
284 inline value_range_type
285 VN_INFO_RANGE_TYPE (tree name
)
287 return VN_INFO_ANTI_RANGE_P (name
) ? VR_ANTI_RANGE
: VR_RANGE
;
290 /* Get at the original pointer info for NAME. */
292 inline ptr_info_def
*
293 VN_INFO_PTR_INFO (tree name
)
295 return (VN_INFO (name
)->info
.ptr_info
296 ? VN_INFO (name
)->info
.ptr_info
297 : SSA_NAME_PTR_INFO (name
));
300 #endif /* TREE_SSA_SCCVN_H */