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 class range_operator
50 {
51 friend class range_op_table;
52 public:
53 range_operator () : m_code (ERROR_MARK) { }
54 // Perform an operation between 2 ranges and return it.
55 virtual bool fold_range (irange &r, tree type,
56 const irange &lh,
57 const irange &rh,
58 relation_trio = TRIO_VARYING) const;
59
60 // Return the range for op[12] in the general case. LHS is the range for
61 // the LHS of the expression, OP[12]is the range for the other
62 //
63 // The operand and the result is returned in R.
64 //
65 // TYPE is the expected type of the range.
66 //
67 // Return TRUE if the operation is performed and a valid range is available.
68 //
69 // i.e. [LHS] = ??? + OP2
70 // is re-formed as R = [LHS] - OP2.
71 virtual bool op1_range (irange &r, tree type,
72 const irange &lhs,
73 const irange &op2,
74 relation_trio = TRIO_VARYING) const;
75 virtual bool op2_range (irange &r, tree type,
76 const irange &lhs,
77 const irange &op1,
78 relation_trio = TRIO_VARYING) const;
79
80 // The following routines are used to represent relations between the
81 // various operations. If the caller knows where the symbolics are,
82 // it can query for relationships between them given known ranges.
83 // the optional relation passed in is the relation between op1 and op2.
84 virtual relation_kind lhs_op1_relation (const irange &lhs,
85 const irange &op1,
86 const irange &op2,
87 relation_kind = VREL_VARYING) const;
88 virtual relation_kind lhs_op2_relation (const irange &lhs,
89 const irange &op1,
90 const irange &op2,
91 relation_kind = VREL_VARYING) const;
92 virtual relation_kind op1_op2_relation (const irange &lhs) const;
93 protected:
94 // Perform an integral operation between 2 sub-ranges and return it.
95 virtual void wi_fold (irange &r, tree type,
96 const wide_int &lh_lb,
97 const wide_int &lh_ub,
98 const wide_int &rh_lb,
99 const wide_int &rh_ub) const;
100 // Effect of relation for generic fold_range clients.
101 virtual bool op1_op2_relation_effect (irange &lhs_range, tree type,
102 const irange &op1_range,
103 const irange &op2_range,
104 relation_kind rel) const;
105 // Called by fold range to split small subranges into parts.
106 void wi_fold_in_parts (irange &r, tree type,
107 const wide_int &lh_lb,
108 const wide_int &lh_ub,
109 const wide_int &rh_lb,
110 const wide_int &rh_ub) const;
111
112 // Called by fold range to split small subranges into parts when op1 == op2
113 void wi_fold_in_parts_equiv (irange &r, tree type,
114 const wide_int &lb,
115 const wide_int &ub,
116 unsigned limit) const;
117
118 // Tree code of the range operator or ERROR_MARK if unknown.
119 tree_code m_code;
120 };
121
122 // Like range_operator above, but for floating point operators.
123
124 class range_operator_float
125 {
126 public:
127 virtual bool fold_range (frange &r, tree type,
128 const frange &lh,
129 const frange &rh,
130 relation_trio = TRIO_VARYING) const;
131 virtual void rv_fold (REAL_VALUE_TYPE &lb, REAL_VALUE_TYPE &ub,
132 bool &maybe_nan,
133 tree type,
134 const REAL_VALUE_TYPE &lh_lb,
135 const REAL_VALUE_TYPE &lh_ub,
136 const REAL_VALUE_TYPE &rh_lb,
137 const REAL_VALUE_TYPE &rh_ub,
138 relation_kind) const;
139 // Unary operations have the range of the LHS as op2.
140 virtual bool fold_range (irange &r, tree type,
141 const frange &lh,
142 const irange &rh,
143 relation_trio = TRIO_VARYING) const;
144 virtual bool fold_range (irange &r, tree type,
145 const frange &lh,
146 const frange &rh,
147 relation_trio = TRIO_VARYING) const;
148 virtual bool op1_range (frange &r, tree type,
149 const frange &lhs,
150 const frange &op2,
151 relation_trio = TRIO_VARYING) const;
152 virtual bool op1_range (frange &r, tree type,
153 const irange &lhs,
154 const frange &op2,
155 relation_trio = TRIO_VARYING) const;
156 virtual bool op2_range (frange &r, tree type,
157 const frange &lhs,
158 const frange &op1,
159 relation_trio = TRIO_VARYING) const;
160 virtual bool op2_range (frange &r, tree type,
161 const irange &lhs,
162 const frange &op1,
163 relation_trio = TRIO_VARYING) const;
164
165 virtual relation_kind lhs_op1_relation (const frange &lhs,
166 const frange &op1,
167 const frange &op2,
168 relation_kind = VREL_VARYING) const;
169 virtual relation_kind lhs_op1_relation (const irange &lhs,
170 const frange &op1,
171 const frange &op2,
172 relation_kind = VREL_VARYING) const;
173 virtual relation_kind lhs_op2_relation (const frange &lhs,
174 const frange &op1,
175 const frange &op2,
176 relation_kind = VREL_VARYING) const;
177 virtual relation_kind lhs_op2_relation (const irange &lhs,
178 const frange &op1,
179 const frange &op2,
180 relation_kind = VREL_VARYING) const;
181 virtual relation_kind op1_op2_relation (const irange &lhs) const;
182 virtual relation_kind op1_op2_relation (const frange &lhs) const;
183 };
184
185 class range_op_handler
186 {
187 public:
188 range_op_handler ();
189 range_op_handler (enum tree_code code, tree type);
190 inline operator bool () const { return m_valid; }
191
192 bool fold_range (vrange &r, tree type,
193 const vrange &lh,
194 const vrange &rh,
195 relation_trio = TRIO_VARYING) const;
196 bool op1_range (vrange &r, tree type,
197 const vrange &lhs,
198 const vrange &op2,
199 relation_trio = TRIO_VARYING) const;
200 bool op2_range (vrange &r, tree type,
201 const vrange &lhs,
202 const vrange &op1,
203 relation_trio = TRIO_VARYING) const;
204 relation_kind lhs_op1_relation (const vrange &lhs,
205 const vrange &op1,
206 const vrange &op2,
207 relation_kind = VREL_VARYING) const;
208 relation_kind lhs_op2_relation (const vrange &lhs,
209 const vrange &op1,
210 const vrange &op2,
211 relation_kind = VREL_VARYING) const;
212 relation_kind op1_op2_relation (const vrange &lhs) const;
213 protected:
214 void set_op_handler (enum tree_code code, tree type);
215 bool m_valid;
216 range_operator *m_int;
217 range_operator_float *m_float;
218 };
219
220 extern bool range_cast (vrange &, tree type);
221 extern void wi_set_zero_nonzero_bits (tree type,
222 const wide_int &, const wide_int &,
223 wide_int &maybe_nonzero,
224 wide_int &mustbe_nonzero);
225
226 // op1_op2_relation methods that are the same across irange and frange.
227 relation_kind equal_op1_op2_relation (const irange &lhs);
228 relation_kind not_equal_op1_op2_relation (const irange &lhs);
229 relation_kind lt_op1_op2_relation (const irange &lhs);
230 relation_kind le_op1_op2_relation (const irange &lhs);
231 relation_kind gt_op1_op2_relation (const irange &lhs);
232 relation_kind ge_op1_op2_relation (const irange &lhs);
233
234 enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL };
235 bool_range_state get_bool_state (vrange &r, const vrange &lhs, tree val_type);
236
237 // If the range of either op1 or op2 is undefined, set the result to
238 // varying and return TRUE. If the caller truly cares about a result,
239 // they should pass in a varying if it has an undefined that it wants
240 // treated as a varying.
241
242 inline bool
243 empty_range_varying (vrange &r, tree type,
244 const vrange &op1, const vrange & op2)
245 {
246 if (op1.undefined_p () || op2.undefined_p ())
247 {
248 r.set_varying (type);
249 return true;
250 }
251 else
252 return false;
253 }
254
255 // For relation opcodes, first try to see if the supplied relation
256 // forces a true or false result, and return that.
257 // Then check for undefined operands. If none of this applies,
258 // return false.
259
260 inline bool
261 relop_early_resolve (irange &r, tree type, const vrange &op1,
262 const vrange &op2, relation_trio trio,
263 relation_kind my_rel)
264 {
265 relation_kind rel = trio.op1_op2 ();
266 // If known relation is a complete subset of this relation, always true.
267 if (relation_union (rel, my_rel) == my_rel)
268 {
269 r = range_true (type);
270 return true;
271 }
272
273 // If known relation has no subset of this relation, always false.
274 if (relation_intersect (rel, my_rel) == VREL_UNDEFINED)
275 {
276 r = range_false (type);
277 return true;
278 }
279
280 // If either operand is undefined, return VARYING.
281 if (empty_range_varying (r, type, op1, op2))
282 return true;
283
284 return false;
285 }
286
287 // This implements the range operator tables as local objects.
288
289 class range_op_table
290 {
291 public:
292 range_operator *operator[] (enum tree_code code);
293 protected:
294 void set (enum tree_code code, range_operator &op);
295 private:
296 range_operator *m_range_tree[MAX_TREE_CODES];
297 };
298
299 // Like above, but for floating point operators.
300
301 class floating_op_table
302 {
303 public:
304 floating_op_table ();
305 range_operator_float *operator[] (enum tree_code code);
306 private:
307 void set (enum tree_code code, range_operator_float &op);
308 range_operator_float *m_range_tree[MAX_TREE_CODES];
309 };
310
311 // This holds the range op table for floating point operations.
312 extern floating_op_table *floating_tree_table;
313
314 extern range_operator *ptr_op_widen_mult_signed;
315 extern range_operator *ptr_op_widen_mult_unsigned;
316 extern range_operator *ptr_op_widen_plus_signed;
317 extern range_operator *ptr_op_widen_plus_unsigned;
318 #endif // GCC_RANGE_OP_H