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
|
/* Header file for range operator class.
Copyright (C) 2017-2022 Free Software Foundation, Inc.
Contributed by Andrew MacLeod <amacleod@redhat.com>
and Aldy Hernandez <aldyh@redhat.com>.
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_RANGE_OP_H
#define GCC_RANGE_OP_H
// This class is implemented for each kind of operator supported by
// the range generator. It serves various purposes.
//
// 1 - Generates range information for the specific operation between
// two ranges. This provides the ability to fold ranges for an
// expression.
//
// 2 - Performs range algebra on the expression such that a range can be
// adjusted in terms of one of the operands:
//
// def = op1 + op2
//
// Given a range for def, we can adjust the range so that it is in
// terms of either operand.
//
// op1_range (def_range, op2) will adjust the range in place so it
// is in terms of op1. Since op1 = def - op2, it will subtract
// op2 from each element of the range.
//
// 3 - Creates a range for an operand based on whether the result is 0 or
// non-zero. This is mostly for logical true false, but can serve other
// purposes.
// ie 0 = op1 - op2 implies op2 has the same range as op1.
class range_operator
{
public:
// Perform an operation between 2 ranges and return it.
virtual bool fold_range (irange &r, tree type,
const irange &lh,
const irange &rh,
relation_kind rel = VREL_VARYING) const;
// Return the range for op[12] in the general case. LHS is the range for
// the LHS of the expression, OP[12]is the range for the other
//
// The operand and the result is returned in R.
//
// TYPE is the expected type of the range.
//
// Return TRUE if the operation is performed and a valid range is available.
//
// i.e. [LHS] = ??? + OP2
// is re-formed as R = [LHS] - OP2.
virtual bool op1_range (irange &r, tree type,
const irange &lhs,
const irange &op2,
relation_kind rel = VREL_VARYING) const;
virtual bool op2_range (irange &r, tree type,
const irange &lhs,
const irange &op1,
relation_kind rel = VREL_VARYING) const;
// The following routines are used to represent relations between the
// various operations. If the caller knows where the symbolics are,
// it can query for relationships between them given known ranges.
// the optional relation passed in is the relation between op1 and op2.
virtual relation_kind lhs_op1_relation (const irange &lhs,
const irange &op1,
const irange &op2,
relation_kind = VREL_VARYING) const;
virtual relation_kind lhs_op2_relation (const irange &lhs,
const irange &op1,
const irange &op2,
relation_kind = VREL_VARYING) const;
virtual relation_kind op1_op2_relation (const irange &lhs) const;
protected:
// Perform an integral operation between 2 sub-ranges and return it.
virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
// Side effect of relation for generic fold_range clients.
virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
const irange &op1_range,
const irange &op2_range,
relation_kind rel) const;
// Called by fold range to split small subranges into parts.
void wi_fold_in_parts (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
};
extern range_operator *range_op_handler (enum tree_code code, tree type);
extern void range_cast (irange &, tree type);
extern void wi_set_zero_nonzero_bits (tree type,
const wide_int &, const wide_int &,
wide_int &maybe_nonzero,
wide_int &mustbe_nonzero);
// op1_op2_relation methods that are the same across irange and frange.
relation_kind equal_op1_op2_relation (const irange &lhs);
relation_kind not_equal_op1_op2_relation (const irange &lhs);
relation_kind lt_op1_op2_relation (const irange &lhs);
relation_kind le_op1_op2_relation (const irange &lhs);
relation_kind gt_op1_op2_relation (const irange &lhs);
relation_kind ge_op1_op2_relation (const irange &lhs);
enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL };
bool_range_state get_bool_state (irange &r, const irange &lhs, tree val_type);
// If the range of either op1 or op2 is undefined, set the result to
// varying and return TRUE. If the caller truely cares about a result,
// they should pass in a varying if it has an undefined that it wants
// treated as a varying.
inline bool
empty_range_varying (irange &r, tree type,
const irange &op1, const irange & op2)
{
if (op1.undefined_p () || op2.undefined_p ())
{
r.set_varying (type);
return true;
}
else
return false;
}
// For relation opcodes, first try to see if the supplied relation
// forces a true or false result, and return that.
// Then check for undefined operands. If none of this applies,
// return false.
inline bool
relop_early_resolve (irange &r, tree type, const irange &op1,
const irange &op2, relation_kind rel,
relation_kind my_rel)
{
// If known relation is a complete subset of this relation, always true.
if (relation_union (rel, my_rel) == my_rel)
{
r = range_true (type);
return true;
}
// If known relation has no subset of this relation, always false.
if (relation_intersect (rel, my_rel) == VREL_UNDEFINED)
{
r = range_false (type);
return true;
}
// If either operand is undefined, return VARYING.
if (empty_range_varying (r, type, op1, op2))
return true;
return false;
}
// This implements the range operator tables as local objects.
class range_op_table
{
public:
range_operator *operator[] (enum tree_code code);
protected:
void set (enum tree_code code, range_operator &op);
private:
range_operator *m_range_tree[MAX_TREE_CODES];
};
#endif // GCC_RANGE_OP_H
|
