]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/tree-ssa-sccvn.h
Correct a function pre/postcondition [PR102403].
[thirdparty/gcc.git] / gcc / tree-ssa-sccvn.h
CommitLineData
89fb70a3 1/* Tree SCC value numbering
99dee823 2 Copyright (C) 2007-2021 Free Software Foundation, Inc.
89fb70a3
DB
3 Contributed by Daniel Berlin <dberlin@dberlin.org>
4
9dcd6f09
NC
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/>. */
89fb70a3
DB
20
21#ifndef TREE_SSA_SCCVN_H
22#define TREE_SSA_SCCVN_H
23
b2ad0284
BRF
24/* In tree-ssa-sccvn.c */
25bool expressions_equal_p (tree, tree);
26
27
89fb70a3
DB
28/* TOP of the VN lattice. */
29extern tree VN_TOP;
30
78ea9abc
RB
31/* A predicated value. */
32struct 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
c9145754
DB
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
48typedef struct vn_nary_op_s
49{
b89ffb98 50 vn_nary_op_s *next;
78ea9abc 51 vn_nary_op_s *unwind_to;
c9145754
DB
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;
78ea9abc
RB
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;
c9145754 64 tree type;
5a7d7f9c 65 tree op[1];
c9145754
DB
66} *vn_nary_op_t;
67typedef const struct vn_nary_op_s *const_vn_nary_op_t;
68
5a7d7f9c
RG
69/* Return the size of a vn_nary_op_t with LENGTH operands. */
70
71static inline size_t
72sizeof_vn_nary_op (unsigned int length)
73{
91af9dc9 74 return sizeof (struct vn_nary_op_s) + sizeof (tree) * length - sizeof (tree);
5a7d7f9c
RG
75}
76
c9145754
DB
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
83typedef struct vn_phi_s
84{
b89ffb98 85 vn_phi_s *next;
c9145754
DB
86 /* Unique identifier that all expressions with the same value have. */
87 unsigned int value_id;
88 hashval_t hashcode;
c9145754 89 basic_block block;
8ee1b0a0
RB
90 /* Controlling condition lhs/rhs. */
91 tree cclhs;
92 tree ccrhs;
24d63016 93 tree type;
c9145754 94 tree result;
851fd366
RB
95 /* The number of args is determined by EDGE_COUT (block->preds). */
96 tree phiargs[1];
c9145754
DB
97} *vn_phi_t;
98typedef 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
106typedef struct vn_reference_op_struct
107{
d5e254e1 108 ENUM_BITFIELD(tree_code) opcode : 16;
1fefbb66
RB
109 /* Dependence info, used for [TARGET_]MEM_REF only. */
110 unsigned short clique;
111 unsigned short base;
cef5388d
RB
112 unsigned reverse : 1;
113 /* For storing TYPE_ALIGN for array ref element size computation. */
114 unsigned align : 6;
70f34814 115 /* Constant offset this op adds or -1 if it is variable. */
b9c25734 116 poly_int64_pod off;
c9145754
DB
117 tree type;
118 tree op0;
119 tree op1;
120 tree op2;
121} vn_reference_op_s;
122typedef vn_reference_op_s *vn_reference_op_t;
123typedef const vn_reference_op_s *const_vn_reference_op_t;
124
cef5388d
RB
125inline unsigned
126vn_ref_op_align_unit (vn_reference_op_t op)
127{
128 return op->align ? ((unsigned)1 << (op->align - 1)) / BITS_PER_UNIT : 0;
129}
c9145754 130
5006671f
RG
131/* A reference operation in the hashtable is representation as
132 the vuse, representing the memory state at the time of
c9145754
DB
133 the operation, and a collection of operands that make up the
134 addressing calculation. If two vn_reference_t's have the same set
135 of operands, they access the same memory location. We also store
5006671f 136 the resulting value number, and the hashcode. */
c9145754
DB
137
138typedef struct vn_reference_s
139{
b89ffb98 140 vn_reference_s *next;
c9145754
DB
141 /* Unique identifier that all expressions with the same value have. */
142 unsigned int value_id;
143 hashval_t hashcode;
5006671f 144 tree vuse;
b45d2719 145 alias_set_type set;
3d6fd7ce 146 alias_set_type base_set;
b45d2719 147 tree type;
1af5cdd7 148 unsigned punned : 1;
9771b263 149 vec<vn_reference_op_s> operands;
c9145754 150 tree result;
00115921 151 tree result_vdef;
c9145754
DB
152} *vn_reference_t;
153typedef const struct vn_reference_s *const_vn_reference_t;
154
155typedef struct vn_constant_s
156{
157 unsigned int value_id;
158 hashval_t hashcode;
159 tree constant;
160} *vn_constant_t;
726a989a 161
17742d62 162enum vn_kind { VN_NONE, VN_CONSTANT, VN_NARY, VN_REFERENCE, VN_PHI };
355fe088 163enum vn_kind vn_get_stmt_kind (gimple *);
17742d62 164
24d63016
RB
165/* Hash the type TYPE using bits that distinguishes it in the
166 types_compatible_p sense. */
167
168static inline hashval_t
169vn_hash_type (tree type)
170{
171 return (INTEGRAL_TYPE_P (type)
172 + (INTEGRAL_TYPE_P (type)
173 ? TYPE_PRECISION (type) + TYPE_UNSIGNED (type) : 0));
174}
175
726a989a
RB
176/* Hash the constant CONSTANT with distinguishing type incompatible
177 constants in the types_compatible_p sense. */
178
179static inline hashval_t
180vn_hash_constant_with_type (tree constant)
181{
4e44a6e8
AK
182 inchash::hash hstate;
183 inchash::add_expr (constant, hstate);
184 hstate.merge_hash (vn_hash_type (TREE_TYPE (constant)));
185 return hstate.end ();
726a989a
RB
186}
187
188/* Compare the constants C1 and C2 with distinguishing type incompatible
189 constants in the types_compatible_p sense. */
190
191static inline bool
192vn_constant_eq_with_type (tree c1, tree c2)
193{
194 return (expressions_equal_p (c1, c2)
195 && types_compatible_p (TREE_TYPE (c1), TREE_TYPE (c2)));
196}
197
390c0dd6
RB
198/* Instead of having a local availability lattice for each basic-block
199 and availability at X defined as union of the local availabilities
200 at X and its dominators we're turning this upside down and track
201 availability per value given values are usually made available at very
202 few points.
203 So we have a chain of LOCATION, LEADER entries where LOCATION is
204 specifying the basic-block LEADER is made available for VALUE.
205 We prepend to this chain in RPO order thus for iteration we can simply
206 remove the last entries.
207 LOCATION is the basic-block index and LEADER is its SSA name version. */
208struct vn_avail
209{
210 vn_avail *next;
211 /* The basic-block LEADER is made available. */
212 int location;
213 /* The LEADER for the value we are chained on. */
214 int leader;
396cc313
RB
215 /* The previous value we pushed a avail record to. */
216 struct vn_ssa_aux *next_undo;
390c0dd6
RB
217};
218
89fb70a3
DB
219typedef struct vn_ssa_aux
220{
78ea9abc
RB
221 /* SSA name this vn_ssa_aux is associated with in the lattice. */
222 tree name;
89fb70a3
DB
223 /* Value number. This may be an SSA name or a constant. */
224 tree valnum;
34050b6b
RB
225 /* Statements to insert if needs_insertion is true. */
226 gimple_seq expr;
71ae8557 227
390c0dd6
RB
228 /* AVAIL entries, last in RPO order is first. This is only tracked
229 for SSA names also serving as values (NAME == VALNUM). */
230 vn_avail *avail;
231
c9145754
DB
232 /* Unique identifier that all expressions with the same value have. */
233 unsigned int value_id;
234
78ea9abc 235 /* Whether the SSA_NAME has been processed at least once. */
71ae8557 236 unsigned visited : 1;
3d45dd59
RG
237
238 /* Whether the SSA_NAME has no defining statement and thus an
239 insertion of such with EXPR as definition is required before
240 a use can be created of it. */
241 unsigned needs_insertion : 1;
89fb70a3
DB
242} *vn_ssa_aux_t;
243
a79683d5 244enum vn_lookup_kind { VN_NOWALK, VN_WALK, VN_WALKREWRITE };
1ec87690 245
89fb70a3 246/* Return the value numbering info for an SSA_NAME. */
7af1c0ad 247bool has_VN_INFO (tree);
89fb70a3 248extern vn_ssa_aux_t VN_INFO (tree);
726a989a 249tree vn_get_expr_for (tree);
65f52ee9 250void scc_vn_restore_ssa_info (void);
355fe088 251tree vn_nary_op_lookup_stmt (gimple *, vn_nary_op_t *);
c9145754 252tree vn_nary_op_lookup_pieces (unsigned int, enum tree_code,
5a7d7f9c 253 tree, tree *, vn_nary_op_t *);
c9145754 254vn_nary_op_t vn_nary_op_insert_pieces (unsigned int, enum tree_code,
5a7d7f9c 255 tree, tree *, tree, unsigned int);
3d6fd7ce 256bool ao_ref_init_from_vn_reference (ao_ref *, alias_set_type, alias_set_type,
00dcc88a 257 tree, const vec<vn_reference_op_s> &);
3c5b29f5 258vec<vn_reference_op_s> vn_reference_operands_for_lookup (tree);
3d6fd7ce 259tree vn_reference_lookup_pieces (tree, alias_set_type, alias_set_type, tree,
9771b263 260 vec<vn_reference_op_s> ,
3bc27de7 261 vn_reference_t *, vn_lookup_kind);
ee7904e9 262tree vn_reference_lookup (tree, tree, vn_lookup_kind, vn_reference_t *, bool,
b07e4e7c 263 tree * = NULL, tree = NULL_TREE);
538dd0b7 264void vn_reference_lookup_call (gcall *, vn_reference_t *, vn_reference_t);
3d6fd7ce
RB
265vn_reference_t vn_reference_insert_pieces (tree, alias_set_type, alias_set_type,
266 tree, vec<vn_reference_op_s>,
c9145754 267 tree, unsigned int);
6eaf7ac6 268void print_vn_reference_ops (FILE *, const vec<vn_reference_op_s>);
c9145754 269
bf190e8d
LC
270bool vn_nary_op_eq (const_vn_nary_op_t const vno1,
271 const_vn_nary_op_t const vno2);
890065bf 272bool vn_nary_may_trap (vn_nary_op_t);
3bab7385 273bool vn_reference_may_trap (vn_reference_t);
bf190e8d 274bool vn_reference_eq (const_vn_reference_t const, const_vn_reference_t const);
d3989492 275
c9145754 276unsigned int get_max_value_id (void);
d3989492 277unsigned int get_max_constant_value_id (void);
c9145754 278unsigned int get_next_value_id (void);
d3989492 279unsigned int get_next_constant_value_id (void);
bb9e4199 280unsigned int get_constant_value_id (tree);
c9145754 281unsigned int get_or_alloc_constant_value_id (tree);
d3989492
RB
282
283/* Return true if V is a value id for a constant. */
284static inline bool
285value_id_constant_p (unsigned int v)
286{
287 return (int)v < 0;
288}
289
12bd5a1e 290tree fully_constant_vn_reference_p (vn_reference_t);
351168fe 291tree vn_nary_simplify (vn_nary_op_t);
c9e93168 292
78ea9abc
RB
293unsigned do_rpo_vn (function *, edge, bitmap);
294void run_rpo_vn (vn_lookup_kind);
295unsigned eliminate_with_rpo_vn (bitmap);
296void free_rpo_vn (void);
c9e93168 297
78ea9abc
RB
298/* Valueize NAME if it is an SSA name, otherwise just return it. This hook
299 is initialized by run_scc_vn. */
300extern tree (*vn_valueize) (tree);
dd6f2cf9 301
78ea9abc
RB
302/* Context that valueization should operate on. */
303extern basic_block vn_context_bb;
dd6f2cf9 304
dd6f2cf9 305
89fb70a3 306#endif /* TREE_SSA_SCCVN_H */