1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
|
/* Support routines for Value Range Propagation (VRP).
Copyright (C) 2016-2019 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#ifndef GCC_TREE_VRP_H
#define GCC_TREE_VRP_H
/* Types of value ranges. */
enum value_range_kind
{
/* Empty range. */
VR_UNDEFINED,
/* Range spans the entire domain. */
VR_VARYING,
/* Range is [MIN, MAX]. */
VR_RANGE,
/* Range is ~[MIN, MAX]. */
VR_ANTI_RANGE,
/* Range is a nice guy. */
VR_LAST
};
/* Range of values that can be associated with an SSA_NAME after VRP
has executed. */
class GTY((for_user)) value_range
{
friend void range_tests ();
public:
value_range ();
value_range (value_range_kind, tree, tree);
value_range (tree, tree);
value_range (value_range_kind,
tree type, const wide_int &, const wide_int &);
value_range (tree type, const wide_int &, const wide_int &);
value_range (tree type);
void set (value_range_kind, tree, tree);
void set (tree);
void set_nonzero (tree);
void set_zero (tree);
enum value_range_kind kind () const;
tree min () const;
tree max () const;
/* Types of value ranges. */
bool symbolic_p () const;
bool constant_p () const;
bool undefined_p () const;
bool varying_p () const;
void set_varying (tree type);
void set_undefined ();
void union_ (const value_range *);
void intersect (const value_range *);
void union_ (const value_range &);
void intersect (const value_range &);
bool operator== (const value_range &) const;
bool operator!= (const value_range &) const /* = delete */;
bool equal_p (const value_range &) const;
/* Misc methods. */
tree type () const;
bool may_contain_p (tree) const;
bool zero_p () const;
bool nonzero_p () const;
bool singleton_p (tree *result = NULL) const;
void dump (FILE *) const;
void dump () const;
static bool supports_type_p (tree);
value_range normalize_symbolics () const;
value_range normalize_addresses () const;
static const unsigned int m_max_pairs = 2;
bool contains_p (tree) const;
unsigned num_pairs () const;
wide_int lower_bound (unsigned = 0) const;
wide_int upper_bound (unsigned) const;
wide_int upper_bound () const;
void invert ();
protected:
void check ();
static value_range union_helper (const value_range *, const value_range *);
static value_range intersect_helper (const value_range *,
const value_range *);
enum value_range_kind m_kind;
tree m_min;
tree m_max;
friend void gt_ggc_mx_value_range (void *);
friend void gt_pch_p_11value_range (void *, void *,
gt_pointer_operator, void *);
friend void gt_pch_nx_value_range (void *);
friend void gt_ggc_mx (value_range &);
friend void gt_ggc_mx (value_range *&);
friend void gt_pch_nx (value_range &);
friend void gt_pch_nx (value_range *, gt_pointer_operator, void *);
private:
int value_inside_range (tree) const;
};
/* Note value_range_equiv cannot currently be used with GC memory,
only value_range is fully set up for this. */
class GTY((user)) value_range_equiv : public value_range
{
public:
value_range_equiv ();
value_range_equiv (const value_range &);
/* Deep-copies equiv bitmap argument. */
value_range_equiv (value_range_kind, tree, tree, bitmap = NULL);
/* Shallow-copies equiv bitmap. */
value_range_equiv (const value_range_equiv &) /* = delete */;
/* Shallow-copies equiv bitmap. */
value_range_equiv& operator=(const value_range_equiv &) /* = delete */;
/* Move equiv bitmap from source range. */
void move (value_range_equiv *);
/* Leaves equiv bitmap alone. */
void update (value_range_kind, tree, tree);
/* Deep-copies equiv bitmap argument. */
void set (value_range_kind, tree, tree, bitmap = NULL);
void set (tree);
bool operator== (const value_range_equiv &) const /* = delete */;
bool operator!= (const value_range_equiv &) const /* = delete */;
void intersect (const value_range_equiv *);
void union_ (const value_range_equiv *);
bool equal_p (const value_range_equiv &, bool ignore_equivs) const;
/* Types of value ranges. */
void set_undefined ();
void set_varying (tree);
/* Equivalence bitmap methods. */
bitmap equiv () const;
void equiv_clear ();
void equiv_add (const_tree, const value_range_equiv *,
bitmap_obstack * = NULL);
/* Misc methods. */
void deep_copy (const value_range_equiv *);
void dump (FILE *) const;
void dump () const;
private:
/* Deep-copies bitmap argument. */
void set_equiv (bitmap);
void check ();
/* Set of SSA names whose value ranges are equivalent to this one.
This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */
bitmap m_equiv;
};
inline
value_range::value_range ()
{
m_kind = VR_UNDEFINED;
m_min = m_max = NULL;
}
inline
value_range_equiv::value_range_equiv ()
: value_range ()
{
m_equiv = NULL;
}
/* Return the kind of this range. */
inline value_range_kind
value_range::kind () const
{
return m_kind;
}
inline bitmap
value_range_equiv::equiv () const
{
return m_equiv;
}
/* Return the lower bound. */
inline tree
value_range::min () const
{
return m_min;
}
/* Return the upper bound. */
inline tree
value_range::max () const
{
return m_max;
}
/* Return TRUE if range spans the entire possible domain. */
inline bool
value_range::varying_p () const
{
return m_kind == VR_VARYING;
}
/* Return TRUE if range is undefined (essentially the empty set). */
inline bool
value_range::undefined_p () const
{
return m_kind == VR_UNDEFINED;
}
/* Return TRUE if range is the constant zero. */
inline bool
value_range::zero_p () const
{
return (m_kind == VR_RANGE
&& integer_zerop (m_min)
&& integer_zerop (m_max));
}
extern void dump_value_range (FILE *, const value_range_equiv *);
extern void dump_value_range (FILE *, const value_range *);
struct assert_info
{
/* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
enum tree_code comp_code;
/* Name to register the assert for. */
tree name;
/* Value being compared against. */
tree val;
/* Expression to compare. */
tree expr;
};
// Return true if TYPE is a valid type for value_range to operate on.
// Otherwise return FALSE.
inline bool
value_range::supports_type_p (tree type)
{
if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type)))
return type;
return false;
}
extern void register_edge_assert_for (tree, edge, enum tree_code,
tree, tree, vec<assert_info> &);
extern bool stmt_interesting_for_vrp (gimple *);
extern bool infer_value_range (gimple *, tree, tree_code *, tree *);
extern bool range_int_cst_p (const value_range *);
extern int compare_values (tree, tree);
extern int compare_values_warnv (tree, tree, bool *);
extern int operand_less_p (tree, tree);
extern bool vrp_val_is_min (const_tree);
extern bool vrp_val_is_max (const_tree);
extern tree vrp_val_min (const_tree);
extern tree vrp_val_max (const_tree);
void range_fold_unary_expr (value_range *, enum tree_code, tree type,
const value_range *, tree op0_type);
void range_fold_binary_expr (value_range *, enum tree_code, tree type,
const value_range *,
const value_range *);
extern bool vrp_operand_equal_p (const_tree, const_tree);
extern enum value_range_kind intersect_range_with_nonzero_bits
(enum value_range_kind, wide_int *, wide_int *, const wide_int &, signop);
extern bool find_case_label_range (gswitch *, tree, tree, size_t *, size_t *);
extern bool find_case_label_index (gswitch *, size_t, tree, size_t *);
extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *);
extern tree get_single_symbol (tree, bool *, tree *);
extern void maybe_set_nonzero_bits (edge, tree);
extern value_range_kind determine_value_range (tree, wide_int *, wide_int *);
/* Return TRUE if range is nonzero. */
inline bool
value_range::nonzero_p () const
{
if (m_kind == VR_ANTI_RANGE
&& !TYPE_UNSIGNED (type ())
&& integer_zerop (m_min)
&& integer_zerop (m_max))
return true;
return (m_kind == VR_RANGE
&& TYPE_UNSIGNED (type ())
&& integer_onep (m_min)
&& vrp_val_is_max (m_max));
}
/* Return TRUE if *VR includes the value zero. */
inline bool
range_includes_zero_p (const value_range *vr)
{
if (vr->undefined_p ())
return false;
if (vr->varying_p ())
return true;
return vr->may_contain_p (build_zero_cst (vr->type ()));
}
#endif /* GCC_TREE_VRP_H */
|