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 | range_cast (vrange &r, tree type) |
244 | { |
245 | gcc_checking_assert (r.supports_type_p (type)); |
246 | Value_Range tmp (r); |
247 | Value_Range varying (type); |
248 | varying.set_varying (type); |
249 | // Call op_convert, if it fails, the result is varying. |
250 | if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, lh: tmp, rh: varying)) |
251 | { |
252 | r.set_varying (type); |
253 | return false; |
254 | } |
255 | return true; |
256 | } |
257 | |
258 | // Range cast which is capable of switching range kinds. |
259 | // ie for float to int. |
260 | |
261 | inline bool |
262 | range_cast (Value_Range &r, tree type) |
263 | { |
264 | Value_Range tmp (r); |
265 | Value_Range varying (type); |
266 | varying.set_varying (type); |
267 | |
268 | // Ensure we are in the correct mode for the call to fold. |
269 | r.set_type (type); |
270 | |
271 | // Call op_convert, if it fails, the result is varying. |
272 | if (!range_op_handler (CONVERT_EXPR).fold_range (r, type, lh: tmp, rh: varying)) |
273 | { |
274 | r.set_varying (type); |
275 | return false; |
276 | } |
277 | return true; |
278 | } |
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 | inline range_operator *operator[] (unsigned code) |
303 | { |
304 | gcc_checking_assert (code < RANGE_OP_TABLE_SIZE); |
305 | return m_range_tree[code]; |
306 | } |
307 | protected: |
308 | inline void set (unsigned code, range_operator &op) |
309 | { |
310 | gcc_checking_assert (code < RANGE_OP_TABLE_SIZE); |
311 | gcc_checking_assert (m_range_tree[code] == NULL); |
312 | m_range_tree[code] = &op; |
313 | } |
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 |
320 | |