GCC Middle and Back End API Reference
range-op.h
Go to the documentation of this file.
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
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
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
65{
66 friend class range_op_table;
67public:
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,
73 virtual bool fold_range (frange &r, tree type,
74 const frange &lh,
75 const frange &rh,
77 virtual bool fold_range (irange &r, tree type,
78 const frange &lh,
79 const irange &rh,
81 virtual bool fold_range (irange &r, tree type,
82 const frange &lh,
83 const frange &rh,
85 virtual bool fold_range (frange &r, tree type,
86 const irange &lh,
87 const irange &rh,
89 virtual bool fold_range (prange &r, tree type,
90 const prange &lh,
91 const prange &rh,
93 virtual bool fold_range (prange &r, tree type,
94 const prange &lh,
95 const irange &rh,
97 virtual bool fold_range (irange &r, tree type,
98 const prange &lh,
99 const prange &rh,
101 virtual bool fold_range (prange &r, tree type,
102 const irange &lh,
103 const prange &rh,
105 virtual bool fold_range (irange &r, tree type,
106 const prange &lh,
107 const irange &rh,
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,
125 virtual bool op1_range (prange &r, tree type,
126 const prange &lhs,
127 const prange &op2,
129 virtual bool op1_range (prange &r, tree type,
130 const irange &lhs,
131 const prange &op2,
133 virtual bool op1_range (prange &r, tree type,
134 const prange &lhs,
135 const irange &op2,
137 virtual bool op1_range (irange &r, tree type,
138 const prange &lhs,
139 const irange &op2,
141 virtual bool op1_range (frange &r, tree type,
142 const frange &lhs,
143 const frange &op2,
145 virtual bool op1_range (frange &r, tree type,
146 const irange &lhs,
147 const frange &op2,
149
150
151 virtual bool op2_range (irange &r, tree type,
152 const irange &lhs,
153 const irange &op1,
155 virtual bool op2_range (prange &r, tree type,
156 const irange &lhs,
157 const prange &op1,
159 virtual bool op2_range (irange &r, tree type,
160 const prange &lhs,
161 const prange &op1,
163 virtual bool op2_range (frange &r, tree type,
164 const frange &lhs,
165 const frange &op1,
167 virtual bool op2_range (frange &r, tree type,
168 const irange &lhs,
169 const frange &op1,
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,
180 virtual relation_kind lhs_op1_relation (const prange &lhs,
181 const prange &op1,
182 const prange &op2,
184 virtual relation_kind lhs_op1_relation (const prange &lhs,
185 const irange &op1,
186 const irange &op2,
188 virtual relation_kind lhs_op1_relation (const irange &lhs,
189 const prange &op1,
190 const prange &op2,
192 virtual relation_kind lhs_op1_relation (const frange &lhs,
193 const frange &op1,
194 const frange &op2,
196 virtual relation_kind lhs_op1_relation (const irange &lhs,
197 const frange &op1,
198 const frange &op2,
200
201 virtual relation_kind lhs_op2_relation (const irange &lhs,
202 const irange &op1,
203 const irange &op2,
205 virtual relation_kind lhs_op2_relation (const frange &lhs,
206 const frange &op1,
207 const frange &op2,
209 virtual relation_kind lhs_op2_relation (const irange &lhs,
210 const frange &op1,
211 const frange &op2,
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,
229
230 // Compatability check for operands.
231 virtual bool operand_check_p (tree, tree, tree) const;
232
233protected:
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.
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
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
291{
292public:
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,
302 bool op1_range (vrange &r, tree type,
303 const vrange &lhs,
304 const vrange &op2,
306 bool op2_range (vrange &r, tree type,
307 const vrange &lhs,
308 const vrange &op1,
311 const vrange &op1,
312 const vrange &op2,
315 const vrange &op1,
316 const vrange &op2,
319 const vrange &op1,
320 const vrange &op2) const;
321 bool overflow_free_p (const vrange &lh, const vrange &rh,
323 bool operand_check_p (tree, tree, tree) const;
324protected:
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;
331};
332
333// Cast the range in R to TYPE if R supports TYPE.
334
335inline bool
337{
338 gcc_checking_assert (r.supports_type_p (type));
339 Value_Range tmp (r);
340 Value_Range varying (type);
341 varying.set_varying (type);
342 // Call op_convert, if it fails, the result is varying.
343 if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
344 {
345 r.set_varying (type);
346 return false;
347 }
348 return true;
349}
350
351// Range cast which is capable of switching range kinds.
352// ie for float to int.
353
354inline bool
356{
357 Value_Range tmp (r);
358 Value_Range varying (type);
359 varying.set_varying (type);
360
361 // Ensure we are in the correct mode for the call to fold.
362 r.set_type (type);
363
364 // Call op_convert, if it fails, the result is varying.
365 if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, tmp, varying))
366 {
367 r.set_varying (type);
368 return false;
369 }
370 return true;
371}
372
373
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
392{
393public:
395 inline range_operator *operator[] (unsigned code)
396 {
398 return m_range_tree[code];
399 }
400protected:
401 inline void set (unsigned code, range_operator &op)
402 {
405 m_range_tree[code] = &op;
406 }
410 void initialize_float_ops ();
411};
412
413#endif // GCC_RANGE_OP_H
Definition value-range.h:757
void set_varying(tree type)
Definition value-range.h:778
Definition value-range.h:527
Definition value-range.h:273
Definition value-range.h:384
Definition range-op.h:291
relation_kind lhs_op1_relation(const vrange &lhs, const vrange &op1, const vrange &op2, relation_kind=VREL_VARYING) const
Definition range-op.cc:369
bool op2_range(vrange &r, tree type, const vrange &lhs, const vrange &op1, relation_trio=TRIO_VARYING) const
Definition range-op.cc:327
range_operator * m_operator
Definition range-op.h:330
bool operand_check_p(tree, tree, tree) const
Definition range-op.cc:488
unsigned dispatch_kind(const vrange &lhs, const vrange &op1, const vrange &op2) const
Definition range-op.cc:184
range_op_handler()
Definition range-op.cc:120
bool overflow_free_p(const vrange &lh, const vrange &rh, relation_trio=TRIO_VARYING) const
Definition range-op.cc:471
bool fold_range(vrange &r, tree type, const vrange &lh, const vrange &rh, relation_trio=TRIO_VARYING) const
Definition range-op.cc:217
relation_kind lhs_op2_relation(const vrange &lhs, const vrange &op1, const vrange &op2, relation_kind=VREL_VARYING) const
Definition range-op.cc:409
range_operator * range_op() const
Definition range-op.cc:147
void discriminator_fail(const vrange &, const vrange &, const vrange &) const
Definition range-op.cc:192
relation_kind op1_op2_relation(const vrange &lhs, const vrange &op1, const vrange &op2) const
Definition range-op.cc:437
bool op1_range(vrange &r, tree type, const vrange &lhs, const vrange &op2, relation_trio=TRIO_VARYING) const
Definition range-op.cc:277
Definition range-op.h:392
void initialize_pointer_ops()
Definition range-op-ptr.cc:1683
range_operator * operator[](unsigned code)
Definition range-op.h:395
void set(unsigned code, range_operator &op)
Definition range-op.h:401
range_operator * m_range_tree[RANGE_OP_TABLE_SIZE]
Definition range-op.h:407
void initialize_float_ops()
Definition range-op-float.cc:2906
void initialize_integral_ops()
Definition range-op.cc:4510
range_op_table()
Definition range-op.cc:81
Definition range-op.h:65
virtual bool overflow_free_p(const irange &lh, const irange &rh, relation_trio=TRIO_VARYING) const
Definition range-op.cc:825
virtual bool op1_range(irange &r, tree type, const irange &lhs, const irange &op2, relation_trio=TRIO_VARYING) const
Definition range-op.cc:763
virtual bool op2_range(irange &r, tree type, const irange &lhs, const irange &op1, relation_trio=TRIO_VARYING) const
Definition range-op.cc:775
void wi_fold_in_parts_equiv(irange &r, tree type, const wide_int &lb, const wide_int &ub, unsigned limit) const
Definition range-op.cc:605
virtual bool fold_range(irange &r, tree type, const irange &lh, const irange &rh, relation_trio=TRIO_VARYING) const
Definition range-op.cc:690
virtual void update_bitmask(irange &, const irange &, const irange &) const
Definition range-op.cc:834
virtual relation_kind lhs_op2_relation(const irange &lhs, const irange &op1, const irange &op2, relation_kind=VREL_VARYING) const
Definition range-op.cc:796
virtual relation_kind lhs_op1_relation(const irange &lhs, const irange &op1, const irange &op2, relation_kind=VREL_VARYING) const
Definition range-op.cc:787
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
Definition range-op.cc:587
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
Definition range-op.cc:634
virtual relation_kind op1_op2_relation(const irange &lhs, const irange &op1, const irange &op2) const
Definition range-op.cc:805
virtual void rv_fold(frange &r, tree type, const REAL_VALUE_TYPE &lh_lb, const REAL_VALUE_TYPE &lh_ub, const REAL_VALUE_TYPE &rh_lb, const REAL_VALUE_TYPE &rh_ub, relation_kind) const
Definition range-op-float.cc:104
virtual bool operand_check_p(tree, tree, tree) const
Definition range-op.cc:842
virtual bool op1_op2_relation_effect(irange &lhs_range, tree type, const irange &op1_range, const irange &op2_range, relation_kind rel) const
Definition range-op.cc:815
Definition value-relation.h:328
Definition value-range.h:78
union tree_node * tree
Definition coretypes.h:97
poly_int< N, C > r
Definition poly-int.h:770
void wi_set_zero_nonzero_bits(tree type, const wide_int &, const wide_int &, wide_int &maybe_nonzero, wide_int &mustbe_nonzero)
Definition range-op.cc:3409
#define RANGE_OP_TABLE_SIZE
Definition range-op.h:387
bool range_cast(vrange &r, tree type)
Definition range-op.h:336
range_op_dispatch_type
Definition range-op.h:26
@ DISPATCH_OP1_OP2_RELATION
Definition range-op.h:32
@ DISPATCH_LHS_OP2_RELATION
Definition range-op.h:31
@ DISPATCH_OP1_RANGE
Definition range-op.h:28
@ DISPATCH_FOLD_RANGE
Definition range-op.h:27
@ DISPATCH_OP2_RANGE
Definition range-op.h:29
@ DISPATCH_LHS_OP1_RELATION
Definition range-op.h:30
#define REAL_VALUE_TYPE
Definition real.h:68
Definition gengtype.h:252
#define NULL
Definition system.h:50
#define bool
Definition system.h:893
#define gcc_checking_assert(EXPR)
Definition system.h:828
enum relation_kind_t relation_kind
@ VREL_VARYING
Definition value-relation.h:65
#define TRIO_VARYING
Definition value-relation.h:347