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 | |
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 | protected: |
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 | |
196 | class range_op_handler |
197 | { |
198 | public: |
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; |
229 | protected: |
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 | |
237 | inline bool |
238 | range_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 | |
256 | inline bool |
257 | range_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 | |
276 | extern 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 | |
293 | class range_op_table |
294 | { |
295 | public: |
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 | } |
302 | protected: |
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 | |