Branch data Line data Source code
1 : : /* Header file for range operator class.
2 : : Copyright (C) 2017-2024 Free Software Foundation, Inc.
3 : : Contributed by Andrew MacLeod <amacleod@redhat.com>
4 : : and Aldy Hernandez <aldyh@redhat.com>.
5 : :
6 : : This file is part of GCC.
7 : :
8 : : GCC is free software; you can redistribute it and/or modify it under
9 : : the terms of the GNU General Public License as published by the Free
10 : : Software Foundation; either version 3, or (at your option) any later
11 : : version.
12 : :
13 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 : : for more details.
17 : :
18 : : You should have received a copy of the GNU General Public License
19 : : along with GCC; see the file COPYING3. If not see
20 : : <http://www.gnu.org/licenses/>. */
21 : :
22 : : #ifndef GCC_RANGE_OP_H
23 : : #define GCC_RANGE_OP_H
24 : :
25 : : // This class is implemented for each kind of operator supported by
26 : : // the range generator. It serves various purposes.
27 : : //
28 : : // 1 - Generates range information for the specific operation between
29 : : // two ranges. This provides the ability to fold ranges for an
30 : : // expression.
31 : : //
32 : : // 2 - Performs range algebra on the expression such that a range can be
33 : : // adjusted in terms of one of the operands:
34 : : //
35 : : // def = op1 + op2
36 : : //
37 : : // Given a range for def, we can adjust the range so that it is in
38 : : // terms of either operand.
39 : : //
40 : : // op1_range (def_range, op2) will adjust the range in place so it
41 : : // is in terms of op1. Since op1 = def - op2, it will subtract
42 : : // op2 from each element of the range.
43 : : //
44 : : // 3 - Creates a range for an operand based on whether the result is 0 or
45 : : // non-zero. This is mostly for logical true false, but can serve other
46 : : // purposes.
47 : : // ie 0 = op1 - op2 implies op2 has the same range as op1.
48 : : //
49 : : // 4 - All supported range combinations are explicitly specified.
50 : : // Any desired combinations should be implemented for each operator.
51 : : // When new range classes are added, new matching prototypes should be
52 : : // added.
53 : :
54 : : class range_operator
55 : : {
56 : : friend class range_op_table;
57 : : public:
58 : : // Perform an operation between 2 ranges and return it.
59 : : virtual bool fold_range (irange &r, tree type,
60 : : const irange &lh,
61 : : const irange &rh,
62 : : relation_trio = TRIO_VARYING) const;
63 : : virtual bool fold_range (frange &r, tree type,
64 : : const frange &lh,
65 : : const frange &rh,
66 : : relation_trio = TRIO_VARYING) const;
67 : : virtual bool fold_range (irange &r, tree type,
68 : : const frange &lh,
69 : : const irange &rh,
70 : : relation_trio = TRIO_VARYING) const;
71 : : virtual bool fold_range (irange &r, tree type,
72 : : const frange &lh,
73 : : const frange &rh,
74 : : relation_trio = TRIO_VARYING) const;
75 : : virtual bool fold_range (frange &r, tree type,
76 : : const irange &lh,
77 : : const irange &rh,
78 : : relation_trio = TRIO_VARYING) const;
79 : :
80 : : // Return the range for op[12] in the general case. LHS is the range for
81 : : // the LHS of the expression, OP[12]is the range for the other
82 : : //
83 : : // The operand and the result is returned in R.
84 : : //
85 : : // TYPE is the expected type of the range.
86 : : //
87 : : // Return TRUE if the operation is performed and a valid range is available.
88 : : //
89 : : // i.e. [LHS] = ??? + OP2
90 : : // is re-formed as R = [LHS] - OP2.
91 : : virtual bool op1_range (irange &r, tree type,
92 : : const irange &lhs,
93 : : const irange &op2,
94 : : relation_trio = TRIO_VARYING) const;
95 : : virtual bool op1_range (frange &r, tree type,
96 : : const frange &lhs,
97 : : const frange &op2,
98 : : relation_trio = TRIO_VARYING) const;
99 : : virtual bool op1_range (frange &r, tree type,
100 : : const irange &lhs,
101 : : const frange &op2,
102 : : relation_trio = TRIO_VARYING) const;
103 : :
104 : :
105 : : virtual bool op2_range (irange &r, tree type,
106 : : const irange &lhs,
107 : : const irange &op1,
108 : : relation_trio = TRIO_VARYING) const;
109 : : virtual bool op2_range (frange &r, tree type,
110 : : const frange &lhs,
111 : : const frange &op1,
112 : : relation_trio = TRIO_VARYING) const;
113 : : virtual bool op2_range (frange &r, tree type,
114 : : const irange &lhs,
115 : : const frange &op1,
116 : : relation_trio = TRIO_VARYING) const;
117 : :
118 : : // The following routines are used to represent relations between the
119 : : // various operations. If the caller knows where the symbolics are,
120 : : // it can query for relationships between them given known ranges.
121 : : // the optional relation passed in is the relation between op1 and op2.
122 : : virtual relation_kind lhs_op1_relation (const irange &lhs,
123 : : const irange &op1,
124 : : const irange &op2,
125 : : relation_kind = VREL_VARYING) const;
126 : : virtual relation_kind lhs_op1_relation (const frange &lhs,
127 : : const frange &op1,
128 : : const frange &op2,
129 : : relation_kind = VREL_VARYING) const;
130 : : virtual relation_kind lhs_op1_relation (const irange &lhs,
131 : : const frange &op1,
132 : : const frange &op2,
133 : : relation_kind = VREL_VARYING) const;
134 : :
135 : : virtual relation_kind lhs_op2_relation (const irange &lhs,
136 : : const irange &op1,
137 : : const irange &op2,
138 : : relation_kind = VREL_VARYING) const;
139 : : virtual relation_kind lhs_op2_relation (const frange &lhs,
140 : : const frange &op1,
141 : : const frange &op2,
142 : : relation_kind = VREL_VARYING) const;
143 : : virtual relation_kind lhs_op2_relation (const irange &lhs,
144 : : const frange &op1,
145 : : const frange &op2,
146 : : relation_kind = VREL_VARYING) const;
147 : :
148 : : virtual relation_kind op1_op2_relation (const irange &lhs,
149 : : const irange &op1,
150 : : const irange &op2) const;
151 : : virtual relation_kind op1_op2_relation (const irange &lhs,
152 : : const frange &op1,
153 : : const frange &op2) const;
154 : : virtual relation_kind op1_op2_relation (const frange &lhs,
155 : : const frange &op1,
156 : : const frange &op2) const;
157 : :
158 : : virtual bool overflow_free_p (const irange &lh, const irange &rh,
159 : : relation_trio = TRIO_VARYING) const;
160 : :
161 : : // Compatability check for operands.
162 : : virtual bool operand_check_p (tree, tree, tree) const;
163 : :
164 : : protected:
165 : : // Perform an integral operation between 2 sub-ranges and return it.
166 : : virtual void wi_fold (irange &r, tree type,
167 : : const wide_int &lh_lb,
168 : : const wide_int &lh_ub,
169 : : const wide_int &rh_lb,
170 : : const wide_int &rh_ub) const;
171 : : // Effect of relation for generic fold_range clients.
172 : : virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
173 : : const irange &op1_range,
174 : : const irange &op2_range,
175 : : relation_kind rel) const;
176 : : // Called by fold range to split small subranges into parts.
177 : : void wi_fold_in_parts (irange &r, tree type,
178 : : const wide_int &lh_lb,
179 : : const wide_int &lh_ub,
180 : : const wide_int &rh_lb,
181 : : const wide_int &rh_ub) const;
182 : :
183 : : // Called by fold range to split small subranges into parts when op1 == op2
184 : : void wi_fold_in_parts_equiv (irange &r, tree type,
185 : : const wide_int &lb,
186 : : const wide_int &ub,
187 : : unsigned limit) const;
188 : : // Apply any bitmasks implied by these ranges.
189 : : virtual void update_bitmask (irange &, const irange &, const irange &) const;
190 : :
191 : : // Perform an float operation between 2 ranges and return it.
192 : : virtual void rv_fold (frange &r, tree type,
193 : : const REAL_VALUE_TYPE &lh_lb,
194 : : const REAL_VALUE_TYPE &lh_ub,
195 : : const REAL_VALUE_TYPE &rh_lb,
196 : : const REAL_VALUE_TYPE &rh_ub,
197 : : relation_kind) const;
198 : : };
199 : :
200 : : class range_op_handler
201 : : {
202 : : public:
203 : : range_op_handler ();
204 : : range_op_handler (unsigned);
205 : : operator bool () const;
206 : : range_operator *range_op () const;
207 : :
208 : : bool fold_range (vrange &r, tree type,
209 : : const vrange &lh,
210 : : const vrange &rh,
211 : : relation_trio = TRIO_VARYING) const;
212 : : bool op1_range (vrange &r, tree type,
213 : : const vrange &lhs,
214 : : const vrange &op2,
215 : : relation_trio = TRIO_VARYING) const;
216 : : bool op2_range (vrange &r, tree type,
217 : : const vrange &lhs,
218 : : const vrange &op1,
219 : : relation_trio = TRIO_VARYING) const;
220 : : relation_kind lhs_op1_relation (const vrange &lhs,
221 : : const vrange &op1,
222 : : const vrange &op2,
223 : : relation_kind = VREL_VARYING) const;
224 : : relation_kind lhs_op2_relation (const vrange &lhs,
225 : : const vrange &op1,
226 : : const vrange &op2,
227 : : relation_kind = VREL_VARYING) const;
228 : : relation_kind op1_op2_relation (const vrange &lhs,
229 : : const vrange &op1,
230 : : const vrange &op2) const;
231 : : bool overflow_free_p (const vrange &lh, const vrange &rh,
232 : : relation_trio = TRIO_VARYING) const;
233 : : bool operand_check_p (tree, tree, tree) const;
234 : : protected:
235 : : unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
236 : : const vrange& op2) const;
237 : : range_operator *m_operator;
238 : : };
239 : :
240 : : // Cast the range in R to TYPE if R supports TYPE.
241 : :
242 : : inline bool
243 : 14378703 : range_cast (vrange &r, tree type)
244 : : {
245 : 14378703 : gcc_checking_assert (r.supports_type_p (type));
246 : 14378703 : Value_Range tmp (r);
247 : 14378703 : Value_Range varying (type);
248 : 14378703 : varying.set_varying (type);
249 : : // Call op_convert, if it fails, the result is varying.
250 : 14378703 : if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
251 : : {
252 : 0 : r.set_varying (type);
253 : 0 : return false;
254 : : }
255 : : return true;
256 : 14378703 : }
257 : :
258 : : // Range cast which is capable of switching range kinds.
259 : : // ie for float to int.
260 : :
261 : : inline bool
262 : 4950952 : range_cast (Value_Range &r, tree type)
263 : : {
264 : 4950952 : Value_Range tmp (r);
265 : 4950952 : Value_Range varying (type);
266 : 4950952 : varying.set_varying (type);
267 : :
268 : : // Ensure we are in the correct mode for the call to fold.
269 : 4950952 : r.set_type (type);
270 : :
271 : : // Call op_convert, if it fails, the result is varying.
272 : 4950952 : if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
273 : : {
274 : 0 : r.set_varying (type);
275 : 0 : return false;
276 : : }
277 : : return true;
278 : 4950952 : }
279 : :
280 : :
281 : : extern void wi_set_zero_nonzero_bits (tree type,
282 : : const wide_int &, const wide_int &,
283 : : wide_int &maybe_nonzero,
284 : : wide_int &mustbe_nonzero);
285 : :
286 : : // These are extra operators that do not fit in the normal scheme of things.
287 : : // Add them to the end of the tree-code vector, and provide a name for
288 : : // each allowing for easy access when required.
289 : :
290 : : #define OP_WIDEN_MULT_SIGNED ((unsigned) MAX_TREE_CODES)
291 : : #define OP_WIDEN_MULT_UNSIGNED ((unsigned) MAX_TREE_CODES + 1)
292 : : #define OP_WIDEN_PLUS_SIGNED ((unsigned) MAX_TREE_CODES + 2)
293 : : #define OP_WIDEN_PLUS_UNSIGNED ((unsigned) MAX_TREE_CODES + 3)
294 : : #define RANGE_OP_TABLE_SIZE ((unsigned) MAX_TREE_CODES + 4)
295 : :
296 : : // This implements the range operator tables as local objects.
297 : :
298 : : class range_op_table
299 : : {
300 : : public:
301 : : range_op_table ();
302 : 1535323357 : inline range_operator *operator[] (unsigned code)
303 : : {
304 : 1535323357 : gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
305 : 1535323357 : return m_range_tree[code];
306 : : }
307 : : protected:
308 : 15169302 : inline void set (unsigned code, range_operator &op)
309 : : {
310 : 15169302 : gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
311 : 15169302 : gcc_checking_assert (m_range_tree[code] == NULL);
312 : 15169302 : m_range_tree[code] = &op;
313 : 15169302 : }
314 : : range_operator *m_range_tree[RANGE_OP_TABLE_SIZE];
315 : : void initialize_integral_ops ();
316 : : void initialize_pointer_ops ();
317 : : void initialize_float_ops ();
318 : : };
319 : : #endif // GCC_RANGE_OP_H
|