Line data Source code
1 : /* Header file for range operator class.
2 : Copyright (C) 2017-2026 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 (frange &r, tree type,
90 : const irange &lh,
91 : const frange &rh,
92 : relation_trio = TRIO_VARYING) const;
93 : virtual bool fold_range (prange &r, tree type,
94 : const prange &lh,
95 : const prange &rh,
96 : relation_trio = TRIO_VARYING) const;
97 : virtual bool fold_range (prange &r, tree type,
98 : const prange &lh,
99 : const irange &rh,
100 : relation_trio = TRIO_VARYING) const;
101 : virtual bool fold_range (irange &r, tree type,
102 : const prange &lh,
103 : const prange &rh,
104 : relation_trio = TRIO_VARYING) const;
105 : virtual bool fold_range (prange &r, tree type,
106 : const irange &lh,
107 : const prange &rh,
108 : relation_trio = TRIO_VARYING) const;
109 : virtual bool fold_range (irange &r, tree type,
110 : const prange &lh,
111 : const irange &rh,
112 : relation_trio = TRIO_VARYING) const;
113 :
114 : // Return the range for op[12] in the general case. LHS is the range for
115 : // the LHS of the expression, OP[12]is the range for the other
116 : //
117 : // The operand and the result is returned in R.
118 : //
119 : // TYPE is the expected type of the range.
120 : //
121 : // Return TRUE if the operation is performed and a valid range is available.
122 : //
123 : // i.e. [LHS] = ??? + OP2
124 : // is re-formed as R = [LHS] - OP2.
125 : virtual bool op1_range (irange &r, tree type,
126 : const irange &lhs,
127 : const irange &op2,
128 : relation_trio = TRIO_VARYING) const;
129 : virtual bool op1_range (prange &r, tree type,
130 : const prange &lhs,
131 : const prange &op2,
132 : relation_trio = TRIO_VARYING) const;
133 : virtual bool op1_range (prange &r, tree type,
134 : const irange &lhs,
135 : const prange &op2,
136 : relation_trio = TRIO_VARYING) const;
137 : virtual bool op1_range (prange &r, tree type,
138 : const prange &lhs,
139 : const irange &op2,
140 : relation_trio = TRIO_VARYING) const;
141 : virtual bool op1_range (irange &r, tree type,
142 : const prange &lhs,
143 : const irange &op2,
144 : relation_trio = TRIO_VARYING) const;
145 : virtual bool op1_range (frange &r, tree type,
146 : const frange &lhs,
147 : const frange &op2,
148 : relation_trio = TRIO_VARYING) const;
149 : virtual bool op1_range (frange &r, tree type,
150 : const irange &lhs,
151 : const frange &op2,
152 : relation_trio = TRIO_VARYING) const;
153 : virtual bool op1_range (irange &r, tree type,
154 : const frange &lhs,
155 : const irange &op2,
156 : relation_trio = TRIO_VARYING) const;
157 :
158 : virtual bool op2_range (irange &r, tree type,
159 : const irange &lhs,
160 : const irange &op1,
161 : relation_trio = TRIO_VARYING) const;
162 : virtual bool op2_range (prange &r, tree type,
163 : const irange &lhs,
164 : const prange &op1,
165 : relation_trio = TRIO_VARYING) const;
166 : virtual bool op2_range (irange &r, tree type,
167 : const prange &lhs,
168 : const prange &op1,
169 : relation_trio = TRIO_VARYING) const;
170 : virtual bool op2_range (frange &r, tree type,
171 : const frange &lhs,
172 : const frange &op1,
173 : relation_trio = TRIO_VARYING) const;
174 : virtual bool op2_range (frange &r, tree type,
175 : const irange &lhs,
176 : const frange &op1,
177 : relation_trio = TRIO_VARYING) const;
178 :
179 : // The following routines are used to represent relations between the
180 : // various operations. If the caller knows where the symbolics are,
181 : // it can query for relationships between them given known ranges.
182 : // the optional relation passed in is the relation between op1 and op2.
183 : virtual relation_kind lhs_op1_relation (const irange &lhs,
184 : const irange &op1,
185 : const irange &op2,
186 : relation_kind = VREL_VARYING) const;
187 : virtual relation_kind lhs_op1_relation (const prange &lhs,
188 : const prange &op1,
189 : const prange &op2,
190 : relation_kind = VREL_VARYING) const;
191 : virtual relation_kind lhs_op1_relation (const prange &lhs,
192 : const irange &op1,
193 : const irange &op2,
194 : relation_kind = VREL_VARYING) const;
195 : virtual relation_kind lhs_op1_relation (const irange &lhs,
196 : const prange &op1,
197 : const prange &op2,
198 : relation_kind = VREL_VARYING) const;
199 : virtual relation_kind lhs_op1_relation (const prange &lhs,
200 : const prange &op1,
201 : const irange &op2,
202 : relation_kind = VREL_VARYING) const;
203 : virtual relation_kind lhs_op1_relation (const frange &lhs,
204 : const frange &op1,
205 : const frange &op2,
206 : relation_kind = VREL_VARYING) const;
207 : virtual relation_kind lhs_op1_relation (const irange &lhs,
208 : const frange &op1,
209 : const frange &op2,
210 : relation_kind = VREL_VARYING) const;
211 :
212 : virtual relation_kind lhs_op2_relation (const irange &lhs,
213 : const irange &op1,
214 : const irange &op2,
215 : relation_kind = VREL_VARYING) const;
216 : virtual relation_kind lhs_op2_relation (const frange &lhs,
217 : const frange &op1,
218 : const frange &op2,
219 : relation_kind = VREL_VARYING) const;
220 : virtual relation_kind lhs_op2_relation (const irange &lhs,
221 : const frange &op1,
222 : const frange &op2,
223 : relation_kind = VREL_VARYING) const;
224 :
225 : virtual relation_kind op1_op2_relation (const irange &lhs,
226 : const irange &op1,
227 : const irange &op2) const;
228 : virtual relation_kind op1_op2_relation (const irange &lhs,
229 : const prange &op1,
230 : const prange &op2) const;
231 : virtual relation_kind op1_op2_relation (const irange &lhs,
232 : const frange &op1,
233 : const frange &op2) const;
234 : virtual relation_kind op1_op2_relation (const frange &lhs,
235 : const frange &op1,
236 : const frange &op2) const;
237 :
238 : virtual bool overflow_free_p (const irange &lh, const irange &rh,
239 : relation_trio = TRIO_VARYING) const;
240 :
241 : // Compatability check for operands.
242 : virtual bool operand_check_p (tree, tree, tree) const;
243 :
244 : protected:
245 : // Perform an integral operation between 2 sub-ranges and return it.
246 : virtual void wi_fold (irange &r, tree type,
247 : const wide_int &lh_lb,
248 : const wide_int &lh_ub,
249 : const wide_int &rh_lb,
250 : const wide_int &rh_ub) const;
251 : // Effect of relation for generic fold_range clients.
252 : virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
253 : const irange &op1_range,
254 : const irange &op2_range,
255 : relation_kind rel) const;
256 : virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
257 : const prange &op1_range,
258 : const prange &op2_range,
259 : relation_kind rel) const;
260 : virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
261 : const prange &op1_range,
262 : const irange &op2_range,
263 : relation_kind rel) const;
264 : virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
265 : const prange &op1_range,
266 : const prange &op2_range,
267 : relation_kind rel) const;
268 : virtual bool op1_op2_relation_effect (prange &lhs_range, tree type,
269 : const irange &op1_range,
270 : const prange &op2_range,
271 : relation_kind rel) const;
272 : virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
273 : const prange &op1_range,
274 : const irange &op2_range,
275 : relation_kind rel) const;
276 : // Called by fold range to split small subranges into parts.
277 : void wi_fold_in_parts (irange &r, tree type,
278 : const wide_int &lh_lb,
279 : const wide_int &lh_ub,
280 : const wide_int &rh_lb,
281 : const wide_int &rh_ub) const;
282 :
283 : // Called by fold range to split small subranges into parts when op1 == op2
284 : void wi_fold_in_parts_equiv (irange &r, tree type,
285 : const wide_int &lb,
286 : const wide_int &ub,
287 : unsigned limit) const;
288 : // Apply any bitmasks implied by these ranges.
289 : virtual void update_bitmask (irange &, const irange &, const irange &) const;
290 : virtual void update_bitmask (irange &, const prange &, const prange &) const;
291 :
292 : // Perform an float operation between 2 ranges and return it.
293 : virtual void rv_fold (frange &r, tree type,
294 : const REAL_VALUE_TYPE &lh_lb,
295 : const REAL_VALUE_TYPE &lh_ub,
296 : const REAL_VALUE_TYPE &rh_lb,
297 : const REAL_VALUE_TYPE &rh_ub,
298 : relation_kind) const;
299 : };
300 :
301 : class range_op_handler
302 : {
303 : public:
304 : range_op_handler ();
305 : range_op_handler (unsigned);
306 : operator bool () const;
307 : range_operator *range_op () const;
308 :
309 : bool fold_range (vrange &r, tree type,
310 : const vrange &lh,
311 : const vrange &rh,
312 : relation_trio = TRIO_VARYING) const;
313 : bool op1_range (vrange &r, tree type,
314 : const vrange &lhs,
315 : const vrange &op2,
316 : relation_trio = TRIO_VARYING) const;
317 : bool op2_range (vrange &r, tree type,
318 : const vrange &lhs,
319 : const vrange &op1,
320 : relation_trio = TRIO_VARYING) const;
321 : relation_kind lhs_op1_relation (const vrange &lhs,
322 : const vrange &op1,
323 : const vrange &op2,
324 : relation_kind = VREL_VARYING) const;
325 : relation_kind lhs_op2_relation (const vrange &lhs,
326 : const vrange &op1,
327 : const vrange &op2,
328 : relation_kind = VREL_VARYING) const;
329 : relation_kind op1_op2_relation (const vrange &lhs,
330 : const vrange &op1,
331 : const vrange &op2) const;
332 : bool overflow_free_p (const vrange &lh, const vrange &rh,
333 : relation_trio = TRIO_VARYING) const;
334 : bool operand_check_p (tree, tree, tree) const;
335 : protected:
336 : unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
337 : const vrange& op2) const;
338 : void discriminator_fail (const vrange &,
339 : const vrange &,
340 : const vrange &) const;
341 : range_operator *m_operator;
342 : };
343 :
344 : // Cast the range in R to TYPE if R supports TYPE.
345 :
346 : inline bool
347 24702518 : range_cast (vrange &r, tree type)
348 : {
349 24702518 : gcc_checking_assert (r.supports_type_p (type));
350 24702518 : value_range tmp (r);
351 24702518 : value_range varying (type);
352 24702518 : varying.set_varying (type);
353 : // Call op_convert, if it fails, the result is varying.
354 24702518 : if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
355 : {
356 0 : r.set_varying (type);
357 0 : return false;
358 : }
359 : return true;
360 24702518 : }
361 :
362 : // Range cast which is capable of switching range kinds.
363 : // ie for float to int.
364 :
365 : inline bool
366 5899955 : range_cast (value_range &r, tree type)
367 : {
368 5899955 : value_range tmp (r);
369 5899955 : value_range varying (type);
370 5899955 : varying.set_varying (type);
371 :
372 : // Ensure we are in the correct mode for the call to fold.
373 5899955 : r.set_type (type);
374 :
375 : // Call op_convert, if it fails, the result is varying.
376 5899955 : if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
377 : {
378 0 : r.set_varying (type);
379 0 : return false;
380 : }
381 : return true;
382 5899955 : }
383 :
384 :
385 : extern void wi_set_zero_nonzero_bits (tree type,
386 : const wide_int &, const wide_int &,
387 : wide_int &maybe_nonzero,
388 : wide_int &mustbe_nonzero);
389 :
390 : // These are extra operators that do not fit in the normal scheme of things.
391 : // Add them to the end of the tree-code vector, and provide a name for
392 : // each allowing for easy access when required.
393 :
394 : #define OP_WIDEN_MULT_SIGNED ((unsigned) MAX_TREE_CODES)
395 : #define OP_WIDEN_MULT_UNSIGNED ((unsigned) MAX_TREE_CODES + 1)
396 : #define OP_WIDEN_MULT_SIGNED_UNSIGNED ((unsigned) MAX_TREE_CODES + 2)
397 : #define OP_WIDEN_PLUS_SIGNED ((unsigned) MAX_TREE_CODES + 3)
398 : #define OP_WIDEN_PLUS_UNSIGNED ((unsigned) MAX_TREE_CODES + 4)
399 : #define RANGE_OP_TABLE_SIZE ((unsigned) MAX_TREE_CODES + 5)
400 :
401 : // This implements the range operator tables as local objects.
402 :
403 : class range_op_table
404 : {
405 : public:
406 : range_op_table ();
407 4078624931 : inline range_operator *operator[] (unsigned code)
408 : {
409 4078624931 : gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
410 4078624931 : return m_range_tree[code];
411 : }
412 : protected:
413 16506278 : inline void set (unsigned code, range_operator &op)
414 : {
415 16506278 : gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
416 16506278 : gcc_checking_assert (m_range_tree[code] == NULL);
417 16506278 : m_range_tree[code] = &op;
418 16506278 : }
419 : range_operator *m_range_tree[RANGE_OP_TABLE_SIZE];
420 : void initialize_integral_ops ();
421 : void initialize_pointer_ops ();
422 : void initialize_float_ops ();
423 : };
424 :
425 : #endif // GCC_RANGE_OP_H
|
