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 : : enum range_op_dispatch_type
26 : : {
27 : : DISPATCH_FOLD_RANGE,
28 : : DISPATCH_OP1_RANGE,
29 : : DISPATCH_OP2_RANGE,
30 : : DISPATCH_LHS_OP1_RELATION,
31 : : DISPATCH_LHS_OP2_RELATION,
32 : : DISPATCH_OP1_OP2_RELATION
33 : : };
34 : :
35 : : // This class is implemented for each kind of operator supported by
36 : : // the range generator. It serves various purposes.
37 : : //
38 : : // 1 - Generates range information for the specific operation between
39 : : // two ranges. This provides the ability to fold ranges for an
40 : : // expression.
41 : : //
42 : : // 2 - Performs range algebra on the expression such that a range can be
43 : : // adjusted in terms of one of the operands:
44 : : //
45 : : // def = op1 + op2
46 : : //
47 : : // Given a range for def, we can adjust the range so that it is in
48 : : // terms of either operand.
49 : : //
50 : : // op1_range (def_range, op2) will adjust the range in place so it
51 : : // is in terms of op1. Since op1 = def - op2, it will subtract
52 : : // op2 from each element of the range.
53 : : //
54 : : // 3 - Creates a range for an operand based on whether the result is 0 or
55 : : // non-zero. This is mostly for logical true false, but can serve other
56 : : // purposes.
57 : : // ie 0 = op1 - op2 implies op2 has the same range as op1.
58 : : //
59 : : // 4 - All supported range combinations are explicitly specified.
60 : : // Any desired combinations should be implemented for each operator.
61 : : // When new range classes are added, new matching prototypes should be
62 : : // added.
63 : :
64 : : class range_operator
65 : : {
66 : : friend class range_op_table;
67 : : public:
68 : : // Perform an operation between 2 ranges and return it.
69 : : virtual bool fold_range (irange &r, tree type,
70 : : const irange &lh,
71 : : const irange &rh,
72 : : relation_trio = TRIO_VARYING) const;
73 : : virtual bool fold_range (frange &r, tree type,
74 : : const frange &lh,
75 : : const frange &rh,
76 : : relation_trio = TRIO_VARYING) const;
77 : : virtual bool fold_range (irange &r, tree type,
78 : : const frange &lh,
79 : : const irange &rh,
80 : : relation_trio = TRIO_VARYING) const;
81 : : virtual bool fold_range (irange &r, tree type,
82 : : const frange &lh,
83 : : const frange &rh,
84 : : relation_trio = TRIO_VARYING) const;
85 : : virtual bool fold_range (frange &r, tree type,
86 : : const irange &lh,
87 : : const irange &rh,
88 : : relation_trio = TRIO_VARYING) const;
89 : : virtual bool fold_range (prange &r, tree type,
90 : : const prange &lh,
91 : : const prange &rh,
92 : : relation_trio = TRIO_VARYING) const;
93 : : virtual bool fold_range (prange &r, tree type,
94 : : const prange &lh,
95 : : const irange &rh,
96 : : relation_trio = TRIO_VARYING) const;
97 : : virtual bool fold_range (irange &r, tree type,
98 : : const prange &lh,
99 : : const prange &rh,
100 : : relation_trio = TRIO_VARYING) const;
101 : : virtual bool fold_range (prange &r, tree type,
102 : : const irange &lh,
103 : : const prange &rh,
104 : : relation_trio = TRIO_VARYING) const;
105 : : virtual bool fold_range (irange &r, tree type,
106 : : const prange &lh,
107 : : const irange &rh,
108 : : relation_trio = TRIO_VARYING) const;
109 : :
110 : : // Return the range for op[12] in the general case. LHS is the range for
111 : : // the LHS of the expression, OP[12]is the range for the other
112 : : //
113 : : // The operand and the result is returned in R.
114 : : //
115 : : // TYPE is the expected type of the range.
116 : : //
117 : : // Return TRUE if the operation is performed and a valid range is available.
118 : : //
119 : : // i.e. [LHS] = ??? + OP2
120 : : // is re-formed as R = [LHS] - OP2.
121 : : virtual bool op1_range (irange &r, tree type,
122 : : const irange &lhs,
123 : : const irange &op2,
124 : : relation_trio = TRIO_VARYING) const;
125 : : virtual bool op1_range (prange &r, tree type,
126 : : const prange &lhs,
127 : : const prange &op2,
128 : : relation_trio = TRIO_VARYING) const;
129 : : virtual bool op1_range (prange &r, tree type,
130 : : const irange &lhs,
131 : : const prange &op2,
132 : : relation_trio = TRIO_VARYING) const;
133 : : virtual bool op1_range (prange &r, tree type,
134 : : const prange &lhs,
135 : : const irange &op2,
136 : : relation_trio = TRIO_VARYING) const;
137 : : virtual bool op1_range (irange &r, tree type,
138 : : const prange &lhs,
139 : : const irange &op2,
140 : : relation_trio = TRIO_VARYING) const;
141 : : virtual bool op1_range (frange &r, tree type,
142 : : const frange &lhs,
143 : : const frange &op2,
144 : : relation_trio = TRIO_VARYING) const;
145 : : virtual bool op1_range (frange &r, tree type,
146 : : const irange &lhs,
147 : : const frange &op2,
148 : : relation_trio = TRIO_VARYING) const;
149 : :
150 : :
151 : : virtual bool op2_range (irange &r, tree type,
152 : : const irange &lhs,
153 : : const irange &op1,
154 : : relation_trio = TRIO_VARYING) const;
155 : : virtual bool op2_range (prange &r, tree type,
156 : : const irange &lhs,
157 : : const prange &op1,
158 : : relation_trio = TRIO_VARYING) const;
159 : : virtual bool op2_range (irange &r, tree type,
160 : : const prange &lhs,
161 : : const prange &op1,
162 : : relation_trio = TRIO_VARYING) const;
163 : : virtual bool op2_range (frange &r, tree type,
164 : : const frange &lhs,
165 : : const frange &op1,
166 : : relation_trio = TRIO_VARYING) const;
167 : : virtual bool op2_range (frange &r, tree type,
168 : : const irange &lhs,
169 : : const frange &op1,
170 : : relation_trio = TRIO_VARYING) const;
171 : :
172 : : // The following routines are used to represent relations between the
173 : : // various operations. If the caller knows where the symbolics are,
174 : : // it can query for relationships between them given known ranges.
175 : : // the optional relation passed in is the relation between op1 and op2.
176 : : virtual relation_kind lhs_op1_relation (const irange &lhs,
177 : : const irange &op1,
178 : : const irange &op2,
179 : : relation_kind = VREL_VARYING) const;
180 : : virtual relation_kind lhs_op1_relation (const prange &lhs,
181 : : const prange &op1,
182 : : const prange &op2,
183 : : relation_kind = VREL_VARYING) const;
184 : : virtual relation_kind lhs_op1_relation (const prange &lhs,
185 : : const irange &op1,
186 : : const irange &op2,
187 : : relation_kind = VREL_VARYING) const;
188 : : virtual relation_kind lhs_op1_relation (const irange &lhs,
189 : : const prange &op1,
190 : : const prange &op2,
191 : : relation_kind = VREL_VARYING) const;
192 : : virtual relation_kind lhs_op1_relation (const frange &lhs,
193 : : const frange &op1,
194 : : const frange &op2,
195 : : relation_kind = VREL_VARYING) const;
196 : : virtual relation_kind lhs_op1_relation (const irange &lhs,
197 : : const frange &op1,
198 : : const frange &op2,
199 : : relation_kind = VREL_VARYING) const;
200 : :
201 : : virtual relation_kind lhs_op2_relation (const irange &lhs,
202 : : const irange &op1,
203 : : const irange &op2,
204 : : relation_kind = VREL_VARYING) const;
205 : : virtual relation_kind lhs_op2_relation (const frange &lhs,
206 : : const frange &op1,
207 : : const frange &op2,
208 : : relation_kind = VREL_VARYING) const;
209 : : virtual relation_kind lhs_op2_relation (const irange &lhs,
210 : : const frange &op1,
211 : : const frange &op2,
212 : : relation_kind = VREL_VARYING) const;
213 : :
214 : : virtual relation_kind op1_op2_relation (const irange &lhs,
215 : : const irange &op1,
216 : : const irange &op2) const;
217 : : virtual relation_kind op1_op2_relation (const irange &lhs,
218 : : const prange &op1,
219 : : const prange &op2) const;
220 : : virtual relation_kind op1_op2_relation (const irange &lhs,
221 : : const frange &op1,
222 : : const frange &op2) const;
223 : : virtual relation_kind op1_op2_relation (const frange &lhs,
224 : : const frange &op1,
225 : : const frange &op2) const;
226 : :
227 : : virtual bool overflow_free_p (const irange &lh, const irange &rh,
228 : : relation_trio = TRIO_VARYING) const;
229 : :
230 : : // Compatability check for operands.
231 : : virtual bool operand_check_p (tree, tree, tree) const;
232 : :
233 : : protected:
234 : : // Perform an integral operation between 2 sub-ranges and return it.
235 : : virtual void wi_fold (irange &r, tree type,
236 : : const wide_int &lh_lb,
237 : : const wide_int &lh_ub,
238 : : const wide_int &rh_lb,
239 : : const wide_int &rh_ub) const;
240 : : // Effect of relation for generic fold_range clients.
241 : : virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
242 : : const irange &op1_range,
243 : : const irange &op2_range,
244 : : relation_kind rel) const;
245 : : virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
246 : : const prange &op1_range,
247 : : const prange &op2_range,
248 : : relation_kind rel) const;
249 : : virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
250 : : const prange &op1_range,
251 : : const irange &op2_range,
252 : : relation_kind rel) const;
253 : : virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
254 : : const prange &op1_range,
255 : : const prange &op2_range,
256 : : relation_kind rel) const;
257 : : virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
258 : : const irange &op1_range,
259 : : const prange &op2_range,
260 : : relation_kind rel) const;
261 : : virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
262 : : const prange &op1_range,
263 : : const irange &op2_range,
264 : : relation_kind rel) const;
265 : : // Called by fold range to split small subranges into parts.
266 : : void wi_fold_in_parts (irange &r, tree type,
267 : : const wide_int &lh_lb,
268 : : const wide_int &lh_ub,
269 : : const wide_int &rh_lb,
270 : : const wide_int &rh_ub) const;
271 : :
272 : : // Called by fold range to split small subranges into parts when op1 == op2
273 : : void wi_fold_in_parts_equiv (irange &r, tree type,
274 : : const wide_int &lb,
275 : : const wide_int &ub,
276 : : unsigned limit) const;
277 : : // Apply any bitmasks implied by these ranges.
278 : : virtual void update_bitmask (irange &, const irange &, const irange &) const;
279 : : virtual void update_bitmask (irange &, const prange &, const prange &) const;
280 : :
281 : : // Perform an float operation between 2 ranges and return it.
282 : : virtual void rv_fold (frange &r, tree type,
283 : : const REAL_VALUE_TYPE &lh_lb,
284 : : const REAL_VALUE_TYPE &lh_ub,
285 : : const REAL_VALUE_TYPE &rh_lb,
286 : : const REAL_VALUE_TYPE &rh_ub,
287 : : relation_kind) const;
288 : : };
289 : :
290 : : class range_op_handler
291 : : {
292 : : public:
293 : : range_op_handler ();
294 : : range_op_handler (unsigned);
295 : : operator bool () const;
296 : : range_operator *range_op () const;
297 : :
298 : : bool fold_range (vrange &r, tree type,
299 : : const vrange &lh,
300 : : const vrange &rh,
301 : : relation_trio = TRIO_VARYING) const;
302 : : bool op1_range (vrange &r, tree type,
303 : : const vrange &lhs,
304 : : const vrange &op2,
305 : : relation_trio = TRIO_VARYING) const;
306 : : bool op2_range (vrange &r, tree type,
307 : : const vrange &lhs,
308 : : const vrange &op1,
309 : : relation_trio = TRIO_VARYING) const;
310 : : relation_kind lhs_op1_relation (const vrange &lhs,
311 : : const vrange &op1,
312 : : const vrange &op2,
313 : : relation_kind = VREL_VARYING) const;
314 : : relation_kind lhs_op2_relation (const vrange &lhs,
315 : : const vrange &op1,
316 : : const vrange &op2,
317 : : relation_kind = VREL_VARYING) const;
318 : : relation_kind op1_op2_relation (const vrange &lhs,
319 : : const vrange &op1,
320 : : const vrange &op2) const;
321 : : bool overflow_free_p (const vrange &lh, const vrange &rh,
322 : : relation_trio = TRIO_VARYING) const;
323 : : bool operand_check_p (tree, tree, tree) const;
324 : : protected:
325 : : unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
326 : : const vrange& op2) const;
327 : : void discriminator_fail (const vrange &,
328 : : const vrange &,
329 : : const vrange &) const;
330 : : range_operator *m_operator;
331 : : };
332 : :
333 : : // Cast the range in R to TYPE if R supports TYPE.
334 : :
335 : : inline bool
336 : 19953822 : range_cast (vrange &r, tree type)
337 : : {
338 : 19953822 : gcc_checking_assert (r.supports_type_p (type));
339 : 19953822 : value_range tmp (r);
340 : 19953822 : value_range varying (type);
341 : 19953822 : varying.set_varying (type);
342 : : // Call op_convert, if it fails, the result is varying.
343 : 19953822 : if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
344 : : {
345 : 0 : r.set_varying (type);
346 : 0 : return false;
347 : : }
348 : : return true;
349 : 19953822 : }
350 : :
351 : : // Range cast which is capable of switching range kinds.
352 : : // ie for float to int.
353 : :
354 : : inline bool
355 : 5136902 : range_cast (value_range &r, tree type)
356 : : {
357 : 5136902 : value_range tmp (r);
358 : 5136902 : value_range varying (type);
359 : 5136902 : varying.set_varying (type);
360 : :
361 : : // Ensure we are in the correct mode for the call to fold.
362 : 5136902 : r.set_type (type);
363 : :
364 : : // Call op_convert, if it fails, the result is varying.
365 : 5136902 : if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
366 : : {
367 : 0 : r.set_varying (type);
368 : 0 : return false;
369 : : }
370 : : return true;
371 : 5136902 : }
372 : :
373 : :
374 : : extern void wi_set_zero_nonzero_bits (tree type,
375 : : const wide_int &, const wide_int &,
376 : : wide_int &maybe_nonzero,
377 : : wide_int &mustbe_nonzero);
378 : :
379 : : // These are extra operators that do not fit in the normal scheme of things.
380 : : // Add them to the end of the tree-code vector, and provide a name for
381 : : // each allowing for easy access when required.
382 : :
383 : : #define OP_WIDEN_MULT_SIGNED ((unsigned) MAX_TREE_CODES)
384 : : #define OP_WIDEN_MULT_UNSIGNED ((unsigned) MAX_TREE_CODES + 1)
385 : : #define OP_WIDEN_PLUS_SIGNED ((unsigned) MAX_TREE_CODES + 2)
386 : : #define OP_WIDEN_PLUS_UNSIGNED ((unsigned) MAX_TREE_CODES + 3)
387 : : #define RANGE_OP_TABLE_SIZE ((unsigned) MAX_TREE_CODES + 4)
388 : :
389 : : // This implements the range operator tables as local objects.
390 : :
391 : : class range_op_table
392 : : {
393 : : public:
394 : : range_op_table ();
395 : 1634633348 : inline range_operator *operator[] (unsigned code)
396 : : {
397 : 1634633348 : gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
398 : 1634633348 : return m_range_tree[code];
399 : : }
400 : : protected:
401 : 15069348 : inline void set (unsigned code, range_operator &op)
402 : : {
403 : 15069348 : gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
404 : 15069348 : gcc_checking_assert (m_range_tree[code] == NULL);
405 : 15069348 : m_range_tree[code] = &op;
406 : 15069348 : }
407 : : range_operator *m_range_tree[RANGE_OP_TABLE_SIZE];
408 : : void initialize_integral_ops ();
409 : : void initialize_pointer_ops ();
410 : : void initialize_float_ops ();
411 : : };
412 : :
413 : : #endif // GCC_RANGE_OP_H
|
