1/* Header file for range operator class.
2 Copyright (C) 2017-2023 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
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
54class range_operator
55{
56 friend class range_op_table;
57public:
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;
160protected:
161 // Perform an integral operation between 2 sub-ranges and return it.
162 virtual void wi_fold (irange &r, tree type,
163 const wide_int &lh_lb,
164 const wide_int &lh_ub,
165 const wide_int &rh_lb,
166 const wide_int &rh_ub) const;
167 // Effect of relation for generic fold_range clients.
168 virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
169 const irange &op1_range,
170 const irange &op2_range,
171 relation_kind rel) const;
172 // Called by fold range to split small subranges into parts.
173 void wi_fold_in_parts (irange &r, tree type,
174 const wide_int &lh_lb,
175 const wide_int &lh_ub,
176 const wide_int &rh_lb,
177 const wide_int &rh_ub) const;
178
179 // Called by fold range to split small subranges into parts when op1 == op2
180 void wi_fold_in_parts_equiv (irange &r, tree type,
181 const wide_int &lb,
182 const wide_int &ub,
183 unsigned limit) const;
184 // Apply any bitmasks implied by these ranges.
185 virtual void update_bitmask (irange &, const irange &, const irange &) const;
186
187 // Perform an float operation between 2 ranges and return it.
188 virtual void rv_fold (frange &r, tree type,
189 const REAL_VALUE_TYPE &lh_lb,
190 const REAL_VALUE_TYPE &lh_ub,
191 const REAL_VALUE_TYPE &rh_lb,
192 const REAL_VALUE_TYPE &rh_ub,
193 relation_kind) const;
194};
195
196class range_op_handler
197{
198public:
199 range_op_handler ();
200 range_op_handler (unsigned);
201 operator bool () const;
202 range_operator *range_op () const;
203
204 bool fold_range (vrange &r, tree type,
205 const vrange &lh,
206 const vrange &rh,
207 relation_trio = TRIO_VARYING) const;
208 bool op1_range (vrange &r, tree type,
209 const vrange &lhs,
210 const vrange &op2,
211 relation_trio = TRIO_VARYING) const;
212 bool op2_range (vrange &r, tree type,
213 const vrange &lhs,
214 const vrange &op1,
215 relation_trio = TRIO_VARYING) const;
216 relation_kind lhs_op1_relation (const vrange &lhs,
217 const vrange &op1,
218 const vrange &op2,
219 relation_kind = VREL_VARYING) const;
220 relation_kind lhs_op2_relation (const vrange &lhs,
221 const vrange &op1,
222 const vrange &op2,
223 relation_kind = VREL_VARYING) const;
224 relation_kind op1_op2_relation (const vrange &lhs,
225 const vrange &op1,
226 const vrange &op2) const;
227 bool overflow_free_p (const vrange &lh, const vrange &rh,
228 relation_trio = TRIO_VARYING) const;
229protected:
230 unsigned dispatch_kind (const vrange &lhs, const vrange &op1,
231 const vrange& op2) const;
232 range_operator *m_operator;
233};
234
235// Cast the range in R to TYPE if R supports TYPE.
236
237inline bool
238range_cast (vrange &r, tree type)
239{
240 gcc_checking_assert (r.supports_type_p (type));
241 Value_Range tmp (r);
242 Value_Range varying (type);
243 varying.set_varying (type);
244 // Call op_convert, if it fails, the result is varying.
245 if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, lh: tmp, rh: varying))
246 {
247 r.set_varying (type);
248 return false;
249 }
250 return true;
251}
252
253// Range cast which is capable of switching range kinds.
254// ie for float to int.
255
256inline bool
257range_cast (Value_Range &r, tree type)
258{
259 Value_Range tmp (r);
260 Value_Range varying (type);
261 varying.set_varying (type);
262
263 // Ensure we are in the correct mode for the call to fold.
264 r.set_type (type);
265
266 // Call op_convert, if it fails, the result is varying.
267 if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, lh: tmp, rh: varying))
268 {
269 r.set_varying (type);
270 return false;
271 }
272 return true;
273}
274
275
276extern void wi_set_zero_nonzero_bits (tree type,
277 const wide_int &, const wide_int &,
278 wide_int &maybe_nonzero,
279 wide_int &mustbe_nonzero);
280
281// These are extra operators that do not fit in the normal scheme of things.
282// Add them to the end of the tree-code vector, and provide a name for
283// each allowing for easy access when required.
284
285#define OP_WIDEN_MULT_SIGNED ((unsigned) MAX_TREE_CODES)
286#define OP_WIDEN_MULT_UNSIGNED ((unsigned) MAX_TREE_CODES + 1)
287#define OP_WIDEN_PLUS_SIGNED ((unsigned) MAX_TREE_CODES + 2)
288#define OP_WIDEN_PLUS_UNSIGNED ((unsigned) MAX_TREE_CODES + 3)
289#define RANGE_OP_TABLE_SIZE ((unsigned) MAX_TREE_CODES + 4)
290
291// This implements the range operator tables as local objects.
292
293class range_op_table
294{
295public:
296 range_op_table ();
297 inline range_operator *operator[] (unsigned code)
298 {
299 gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
300 return m_range_tree[code];
301 }
302protected:
303 inline void set (unsigned code, range_operator &op)
304 {
305 gcc_checking_assert (code < RANGE_OP_TABLE_SIZE);
306 gcc_checking_assert (m_range_tree[code] == NULL);
307 m_range_tree[code] = &op;
308 }
309 range_operator *m_range_tree[RANGE_OP_TABLE_SIZE];
310 void initialize_integral_ops ();
311 void initialize_pointer_ops ();
312 void initialize_float_ops ();
313};
314#endif // GCC_RANGE_OP_H
315

source code of gcc/range-op.h