]>
Commit | Line | Data |
---|---|---|
38a73435 | 1 | /* Code for range operators. |
99dee823 | 2 | Copyright (C) 2017-2021 Free Software Foundation, Inc. |
38a73435 AH |
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 | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License 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 | #include "config.h" | |
23 | #include "system.h" | |
24 | #include "coretypes.h" | |
25 | #include "backend.h" | |
26 | #include "insn-codes.h" | |
27 | #include "rtl.h" | |
28 | #include "tree.h" | |
29 | #include "gimple.h" | |
30 | #include "cfghooks.h" | |
31 | #include "tree-pass.h" | |
32 | #include "ssa.h" | |
33 | #include "optabs-tree.h" | |
34 | #include "gimple-pretty-print.h" | |
35 | #include "diagnostic-core.h" | |
36 | #include "flags.h" | |
37 | #include "fold-const.h" | |
38 | #include "stor-layout.h" | |
39 | #include "calls.h" | |
40 | #include "cfganal.h" | |
41 | #include "gimple-fold.h" | |
42 | #include "tree-eh.h" | |
43 | #include "gimple-iterator.h" | |
44 | #include "gimple-walk.h" | |
45 | #include "tree-cfg.h" | |
46 | #include "wide-int.h" | |
80dd13f5 | 47 | #include "value-relation.h" |
38a73435 AH |
48 | #include "range-op.h" |
49 | ||
50 | // Return the upper limit for a type. | |
51 | ||
52 | static inline wide_int | |
53 | max_limit (const_tree type) | |
54 | { | |
55 | return wi::max_value (TYPE_PRECISION (type) , TYPE_SIGN (type)); | |
56 | } | |
57 | ||
58 | // Return the lower limit for a type. | |
59 | ||
60 | static inline wide_int | |
61 | min_limit (const_tree type) | |
62 | { | |
63 | return wi::min_value (TYPE_PRECISION (type) , TYPE_SIGN (type)); | |
64 | } | |
65 | ||
66 | // If the range of either op1 or op2 is undefined, set the result to | |
4ba9fb0a AH |
67 | // varying and return TRUE. If the caller truely cares about a result, |
68 | // they should pass in a varying if it has an undefined that it wants | |
69 | // treated as a varying. | |
38a73435 AH |
70 | |
71 | inline bool | |
4ba9fb0a AH |
72 | empty_range_varying (irange &r, tree type, |
73 | const irange &op1, const irange & op2) | |
38a73435 AH |
74 | { |
75 | if (op1.undefined_p () || op2.undefined_p ()) | |
76 | { | |
4ba9fb0a | 77 | r.set_varying (type); |
38a73435 AH |
78 | return true; |
79 | } | |
80 | else | |
81 | return false; | |
82 | } | |
83 | ||
d0d8b5d8 AM |
84 | // Return false if shifting by OP is undefined behavior. Otherwise, return |
85 | // true and the range it is to be shifted by. This allows trimming out of | |
86 | // undefined ranges, leaving only valid ranges if there are any. | |
38a73435 AH |
87 | |
88 | static inline bool | |
d0d8b5d8 | 89 | get_shift_range (irange &r, tree type, const irange &op) |
38a73435 AH |
90 | { |
91 | if (op.undefined_p ()) | |
d0d8b5d8 | 92 | return false; |
38a73435 | 93 | |
d0d8b5d8 AM |
94 | // Build valid range and intersect it with the shift range. |
95 | r = value_range (build_int_cst_type (op.type (), 0), | |
96 | build_int_cst_type (op.type (), TYPE_PRECISION (type) - 1)); | |
97 | r.intersect (op); | |
98 | ||
99 | // If there are no valid ranges in the shift range, returned false. | |
100 | if (r.undefined_p ()) | |
101 | return false; | |
102 | return true; | |
38a73435 AH |
103 | } |
104 | ||
105 | // Return TRUE if 0 is within [WMIN, WMAX]. | |
106 | ||
107 | static inline bool | |
108 | wi_includes_zero_p (tree type, const wide_int &wmin, const wide_int &wmax) | |
109 | { | |
110 | signop sign = TYPE_SIGN (type); | |
111 | return wi::le_p (wmin, 0, sign) && wi::ge_p (wmax, 0, sign); | |
112 | } | |
113 | ||
114 | // Return TRUE if [WMIN, WMAX] is the singleton 0. | |
115 | ||
116 | static inline bool | |
117 | wi_zero_p (tree type, const wide_int &wmin, const wide_int &wmax) | |
118 | { | |
119 | unsigned prec = TYPE_PRECISION (type); | |
120 | return wmin == wmax && wi::eq_p (wmin, wi::zero (prec)); | |
121 | } | |
122 | ||
123 | // Default wide_int fold operation returns [MIN, MAX]. | |
124 | ||
bb74ef9e | 125 | void |
4ba9fb0a | 126 | range_operator::wi_fold (irange &r, tree type, |
38a73435 AH |
127 | const wide_int &lh_lb ATTRIBUTE_UNUSED, |
128 | const wide_int &lh_ub ATTRIBUTE_UNUSED, | |
129 | const wide_int &rh_lb ATTRIBUTE_UNUSED, | |
130 | const wide_int &rh_ub ATTRIBUTE_UNUSED) const | |
131 | { | |
4ba9fb0a AH |
132 | gcc_checking_assert (irange::supports_type_p (type)); |
133 | r.set_varying (type); | |
38a73435 AH |
134 | } |
135 | ||
704e8a82 AM |
136 | // Call wi_fold, except further split small subranges into constants. |
137 | // This can provide better precision. For something 8 >> [0,1] | |
138 | // Instead of [8, 16], we will produce [8,8][16,16] | |
139 | ||
140 | void | |
141 | range_operator::wi_fold_in_parts (irange &r, tree type, | |
142 | const wide_int &lh_lb, | |
143 | const wide_int &lh_ub, | |
144 | const wide_int &rh_lb, | |
145 | const wide_int &rh_ub) const | |
146 | { | |
147 | wi::overflow_type ov_rh, ov_lh; | |
148 | int_range_max tmp; | |
149 | wide_int rh_range = wi::sub (rh_ub, rh_lb, TYPE_SIGN (type), &ov_rh); | |
150 | wide_int lh_range = wi::sub (lh_ub, lh_lb, TYPE_SIGN (type), &ov_lh); | |
151 | signop sign = TYPE_SIGN (type);; | |
152 | // If there are 2, 3, or 4 values in the RH range, do them separately. | |
153 | // Call wi_fold_in_parts to check the RH side. | |
154 | if (wi::gt_p (rh_range, 0, sign) && wi::lt_p (rh_range, 4, sign) | |
155 | && ov_rh == wi::OVF_NONE) | |
156 | { | |
157 | wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb); | |
158 | if (wi::gt_p (rh_range, 1, sign)) | |
159 | { | |
160 | wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1); | |
161 | r.union_ (tmp); | |
162 | if (wi::eq_p (rh_range, 3)) | |
163 | { | |
164 | wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2); | |
165 | r.union_ (tmp); | |
166 | } | |
167 | } | |
168 | wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub); | |
169 | r.union_ (tmp); | |
170 | } | |
171 | // Otherise check for 2, 3, or 4 values in the LH range and split them up. | |
172 | // The RH side has been checked, so no recursion needed. | |
173 | else if (wi::gt_p (lh_range, 0, sign) && wi::lt_p (lh_range, 4, sign) | |
174 | && ov_lh == wi::OVF_NONE) | |
175 | { | |
176 | wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub); | |
177 | if (wi::gt_p (lh_range, 1, sign)) | |
178 | { | |
179 | wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub); | |
180 | r.union_ (tmp); | |
181 | if (wi::eq_p (lh_range, 3)) | |
182 | { | |
183 | wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub); | |
184 | r.union_ (tmp); | |
185 | } | |
186 | } | |
187 | wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub); | |
188 | r.union_ (tmp); | |
189 | } | |
190 | // Otherwise just call wi_fold. | |
191 | else | |
192 | wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub); | |
193 | } | |
194 | ||
38a73435 AH |
195 | // The default for fold is to break all ranges into sub-ranges and |
196 | // invoke the wi_fold method on each sub-range pair. | |
197 | ||
f674b4a7 | 198 | bool |
4ba9fb0a AH |
199 | range_operator::fold_range (irange &r, tree type, |
200 | const irange &lh, | |
80dd13f5 AM |
201 | const irange &rh, |
202 | relation_kind rel) const | |
38a73435 | 203 | { |
4ba9fb0a AH |
204 | gcc_checking_assert (irange::supports_type_p (type)); |
205 | if (empty_range_varying (r, type, lh, rh)) | |
f674b4a7 | 206 | return true; |
38a73435 | 207 | |
4ba9fb0a AH |
208 | unsigned num_lh = lh.num_pairs (); |
209 | unsigned num_rh = rh.num_pairs (); | |
210 | ||
211 | // If both ranges are single pairs, fold directly into the result range. | |
212 | if (num_lh == 1 && num_rh == 1) | |
213 | { | |
704e8a82 AM |
214 | wi_fold_in_parts (r, type, lh.lower_bound (0), lh.upper_bound (0), |
215 | rh.lower_bound (0), rh.upper_bound (0)); | |
80dd13f5 | 216 | op1_op2_relation_effect (r, type, lh, rh, rel); |
4ba9fb0a AH |
217 | return true; |
218 | } | |
219 | ||
c5a6c223 | 220 | int_range_max tmp; |
bbc85eb9 | 221 | r.set_undefined (); |
4ba9fb0a AH |
222 | for (unsigned x = 0; x < num_lh; ++x) |
223 | for (unsigned y = 0; y < num_rh; ++y) | |
38a73435 AH |
224 | { |
225 | wide_int lh_lb = lh.lower_bound (x); | |
226 | wide_int lh_ub = lh.upper_bound (x); | |
227 | wide_int rh_lb = rh.lower_bound (y); | |
228 | wide_int rh_ub = rh.upper_bound (y); | |
704e8a82 | 229 | wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub); |
bb74ef9e | 230 | r.union_ (tmp); |
38a73435 | 231 | if (r.varying_p ()) |
80dd13f5 AM |
232 | { |
233 | op1_op2_relation_effect (r, type, lh, rh, rel); | |
234 | return true; | |
235 | } | |
38a73435 | 236 | } |
80dd13f5 | 237 | op1_op2_relation_effect (r, type, lh, rh, rel); |
f674b4a7 | 238 | return true; |
38a73435 AH |
239 | } |
240 | ||
241 | // The default for op1_range is to return false. | |
242 | ||
243 | bool | |
4ba9fb0a | 244 | range_operator::op1_range (irange &r ATTRIBUTE_UNUSED, |
38a73435 | 245 | tree type ATTRIBUTE_UNUSED, |
4ba9fb0a | 246 | const irange &lhs ATTRIBUTE_UNUSED, |
80dd13f5 AM |
247 | const irange &op2 ATTRIBUTE_UNUSED, |
248 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
249 | { |
250 | return false; | |
251 | } | |
252 | ||
253 | // The default for op2_range is to return false. | |
254 | ||
255 | bool | |
4ba9fb0a | 256 | range_operator::op2_range (irange &r ATTRIBUTE_UNUSED, |
38a73435 | 257 | tree type ATTRIBUTE_UNUSED, |
4ba9fb0a | 258 | const irange &lhs ATTRIBUTE_UNUSED, |
80dd13f5 AM |
259 | const irange &op1 ATTRIBUTE_UNUSED, |
260 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
261 | { |
262 | return false; | |
263 | } | |
264 | ||
80dd13f5 AM |
265 | // The default relation routines return VREL_NONE. |
266 | ||
267 | enum tree_code | |
268 | range_operator::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED, | |
269 | const irange &op1 ATTRIBUTE_UNUSED, | |
270 | const irange &op2 ATTRIBUTE_UNUSED) const | |
271 | { | |
272 | return VREL_NONE; | |
273 | } | |
274 | ||
275 | enum tree_code | |
276 | range_operator::lhs_op2_relation (const irange &lhs ATTRIBUTE_UNUSED, | |
277 | const irange &op1 ATTRIBUTE_UNUSED, | |
278 | const irange &op2 ATTRIBUTE_UNUSED) const | |
279 | { | |
280 | return VREL_NONE; | |
281 | } | |
282 | ||
283 | enum tree_code | |
284 | range_operator::op1_op2_relation (const irange &lhs ATTRIBUTE_UNUSED) const | |
285 | { | |
286 | return VREL_NONE; | |
287 | } | |
288 | ||
289 | // Default is no relation affects the LHS. | |
290 | ||
291 | bool | |
292 | range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED, | |
293 | tree type ATTRIBUTE_UNUSED, | |
294 | const irange &op1_range ATTRIBUTE_UNUSED, | |
295 | const irange &op2_range ATTRIBUTE_UNUSED, | |
296 | relation_kind rel ATTRIBUTE_UNUSED) const | |
297 | { | |
298 | return false; | |
299 | } | |
38a73435 | 300 | |
3d203d01 AH |
301 | // Create and return a range from a pair of wide-ints that are known |
302 | // to have overflowed (or underflowed). | |
38a73435 | 303 | |
bb74ef9e | 304 | static void |
4ba9fb0a | 305 | value_range_from_overflowed_bounds (irange &r, tree type, |
3d203d01 AH |
306 | const wide_int &wmin, |
307 | const wide_int &wmax) | |
38a73435 AH |
308 | { |
309 | const signop sgn = TYPE_SIGN (type); | |
310 | const unsigned int prec = TYPE_PRECISION (type); | |
311 | ||
312 | wide_int tmin = wide_int::from (wmin, prec, sgn); | |
313 | wide_int tmax = wide_int::from (wmax, prec, sgn); | |
314 | ||
315 | bool covers = false; | |
316 | wide_int tem = tmin; | |
317 | tmin = tmax + 1; | |
318 | if (wi::cmp (tmin, tmax, sgn) < 0) | |
319 | covers = true; | |
320 | tmax = tem - 1; | |
321 | if (wi::cmp (tmax, tem, sgn) > 0) | |
322 | covers = true; | |
323 | ||
324 | // If the anti-range would cover nothing, drop to varying. | |
325 | // Likewise if the anti-range bounds are outside of the types | |
326 | // values. | |
327 | if (covers || wi::cmp (tmin, tmax, sgn) > 0) | |
4ba9fb0a | 328 | r.set_varying (type); |
bb74ef9e | 329 | else |
4ba9fb0a AH |
330 | { |
331 | tree tree_min = wide_int_to_tree (type, tmin); | |
332 | tree tree_max = wide_int_to_tree (type, tmax); | |
333 | r.set (tree_min, tree_max, VR_ANTI_RANGE); | |
334 | } | |
38a73435 AH |
335 | } |
336 | ||
3d203d01 AH |
337 | // Create and return a range from a pair of wide-ints. MIN_OVF and |
338 | // MAX_OVF describe any overflow that might have occurred while | |
339 | // calculating WMIN and WMAX respectively. | |
38a73435 | 340 | |
bb74ef9e | 341 | static void |
4ba9fb0a | 342 | value_range_with_overflow (irange &r, tree type, |
3d203d01 AH |
343 | const wide_int &wmin, const wide_int &wmax, |
344 | wi::overflow_type min_ovf = wi::OVF_NONE, | |
345 | wi::overflow_type max_ovf = wi::OVF_NONE) | |
38a73435 AH |
346 | { |
347 | const signop sgn = TYPE_SIGN (type); | |
348 | const unsigned int prec = TYPE_PRECISION (type); | |
349 | const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type); | |
350 | ||
351 | // For one bit precision if max != min, then the range covers all | |
352 | // values. | |
353 | if (prec == 1 && wi::ne_p (wmax, wmin)) | |
bb74ef9e | 354 | { |
4ba9fb0a | 355 | r.set_varying (type); |
bb74ef9e AM |
356 | return; |
357 | } | |
38a73435 AH |
358 | |
359 | if (overflow_wraps) | |
360 | { | |
361 | // If overflow wraps, truncate the values and adjust the range, | |
362 | // kind, and bounds appropriately. | |
363 | if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE)) | |
364 | { | |
365 | wide_int tmin = wide_int::from (wmin, prec, sgn); | |
366 | wide_int tmax = wide_int::from (wmax, prec, sgn); | |
367 | // If the limits are swapped, we wrapped around and cover | |
368 | // the entire range. | |
369 | if (wi::gt_p (tmin, tmax, sgn)) | |
4ba9fb0a | 370 | r.set_varying (type); |
bb74ef9e AM |
371 | else |
372 | // No overflow or both overflow or underflow. The range | |
373 | // kind stays normal. | |
4ba9fb0a AH |
374 | r.set (wide_int_to_tree (type, tmin), |
375 | wide_int_to_tree (type, tmax)); | |
bb74ef9e | 376 | return; |
38a73435 AH |
377 | } |
378 | ||
379 | if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE) | |
380 | || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE)) | |
bb74ef9e AM |
381 | value_range_from_overflowed_bounds (r, type, wmin, wmax); |
382 | else | |
383 | // Other underflow and/or overflow, drop to VR_VARYING. | |
4ba9fb0a | 384 | r.set_varying (type); |
38a73435 AH |
385 | } |
386 | else | |
387 | { | |
91ae6930 AH |
388 | // If both bounds either underflowed or overflowed, then the result |
389 | // is undefined. | |
390 | if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW) | |
391 | || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW)) | |
392 | { | |
393 | r.set_undefined (); | |
394 | return; | |
395 | } | |
396 | ||
38a73435 AH |
397 | // If overflow does not wrap, saturate to [MIN, MAX]. |
398 | wide_int new_lb, new_ub; | |
399 | if (min_ovf == wi::OVF_UNDERFLOW) | |
400 | new_lb = wi::min_value (prec, sgn); | |
401 | else if (min_ovf == wi::OVF_OVERFLOW) | |
402 | new_lb = wi::max_value (prec, sgn); | |
403 | else | |
404 | new_lb = wmin; | |
405 | ||
406 | if (max_ovf == wi::OVF_UNDERFLOW) | |
407 | new_ub = wi::min_value (prec, sgn); | |
408 | else if (max_ovf == wi::OVF_OVERFLOW) | |
409 | new_ub = wi::max_value (prec, sgn); | |
410 | else | |
411 | new_ub = wmax; | |
412 | ||
4ba9fb0a AH |
413 | r.set (wide_int_to_tree (type, new_lb), |
414 | wide_int_to_tree (type, new_ub)); | |
38a73435 AH |
415 | } |
416 | } | |
417 | ||
3d203d01 AH |
418 | // Create and return a range from a pair of wide-ints. Canonicalize |
419 | // the case where the bounds are swapped. In which case, we transform | |
420 | // [10,5] into [MIN,5][10,MAX]. | |
38a73435 | 421 | |
bb74ef9e | 422 | static inline void |
4ba9fb0a | 423 | create_possibly_reversed_range (irange &r, tree type, |
38a73435 AH |
424 | const wide_int &new_lb, const wide_int &new_ub) |
425 | { | |
426 | signop s = TYPE_SIGN (type); | |
427 | // If the bounds are swapped, treat the result as if an overflow occured. | |
428 | if (wi::gt_p (new_lb, new_ub, s)) | |
bb74ef9e AM |
429 | value_range_from_overflowed_bounds (r, type, new_lb, new_ub); |
430 | else | |
4ba9fb0a AH |
431 | // Otherwise it's just a normal range. |
432 | r.set (wide_int_to_tree (type, new_lb), wide_int_to_tree (type, new_ub)); | |
38a73435 AH |
433 | } |
434 | ||
4ba9fb0a | 435 | // Return an irange instance that is a boolean TRUE. |
38a73435 | 436 | |
4ba9fb0a | 437 | static inline int_range<1> |
38a73435 AH |
438 | range_true (tree type) |
439 | { | |
440 | unsigned prec = TYPE_PRECISION (type); | |
4ba9fb0a | 441 | return int_range<1> (type, wi::one (prec), wi::one (prec)); |
38a73435 AH |
442 | } |
443 | ||
4ba9fb0a | 444 | // Return an irange instance that is a boolean FALSE. |
38a73435 | 445 | |
4ba9fb0a | 446 | static inline int_range<1> |
38a73435 AH |
447 | range_false (tree type) |
448 | { | |
449 | unsigned prec = TYPE_PRECISION (type); | |
4ba9fb0a | 450 | return int_range<1> (type, wi::zero (prec), wi::zero (prec)); |
38a73435 AH |
451 | } |
452 | ||
4ba9fb0a | 453 | // Return an irange that covers both true and false. |
38a73435 | 454 | |
4ba9fb0a | 455 | static inline int_range<1> |
38a73435 AH |
456 | range_true_and_false (tree type) |
457 | { | |
458 | unsigned prec = TYPE_PRECISION (type); | |
4ba9fb0a | 459 | return int_range<1> (type, wi::zero (prec), wi::one (prec)); |
38a73435 AH |
460 | } |
461 | ||
462 | enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL }; | |
463 | ||
ead233e6 EB |
464 | // Return the summary information about boolean range LHS. If EMPTY/FULL, |
465 | // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing. | |
38a73435 AH |
466 | |
467 | static bool_range_state | |
4ba9fb0a | 468 | get_bool_state (irange &r, const irange &lhs, tree val_type) |
38a73435 AH |
469 | { |
470 | // If there is no result, then this is unexecutable. | |
471 | if (lhs.undefined_p ()) | |
472 | { | |
473 | r.set_undefined (); | |
474 | return BRS_EMPTY; | |
475 | } | |
476 | ||
4ba9fb0a AH |
477 | if (lhs.zero_p ()) |
478 | return BRS_FALSE; | |
479 | ||
480 | // For TRUE, we can't just test for [1,1] because Ada can have | |
481 | // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc. | |
482 | if (lhs.contains_p (build_zero_cst (lhs.type ()))) | |
38a73435 AH |
483 | { |
484 | r.set_varying (val_type); | |
485 | return BRS_FULL; | |
486 | } | |
ead233e6 | 487 | |
38a73435 AH |
488 | return BRS_TRUE; |
489 | } | |
490 | ||
80dd13f5 AM |
491 | // For relation opcodes, first try to see if the supplied relation |
492 | // forces a true or false result, and return that. | |
493 | // Then check for undefined operands. If none of this applies, | |
494 | // return false. | |
495 | ||
496 | static inline bool | |
497 | relop_early_resolve (irange &r, tree type, const irange &op1, | |
498 | const irange &op2, relation_kind rel, | |
499 | relation_kind my_rel) | |
500 | { | |
501 | // If known relation is a complete subset of this relation, always true. | |
502 | if (relation_union (rel, my_rel) == my_rel) | |
503 | { | |
504 | r = range_true (type); | |
505 | return true; | |
506 | } | |
507 | ||
508 | // If known relation has no subset of this relation, always false. | |
509 | if (relation_intersect (rel, my_rel) == VREL_EMPTY) | |
510 | { | |
511 | r = range_false (type); | |
512 | return true; | |
513 | } | |
514 | ||
515 | // If either operand is undefined, return VARYING. | |
516 | if (empty_range_varying (r, type, op1, op2)) | |
517 | return true; | |
518 | ||
519 | return false; | |
520 | } | |
521 | ||
38a73435 AH |
522 | |
523 | class operator_equal : public range_operator | |
524 | { | |
525 | public: | |
4ba9fb0a AH |
526 | virtual bool fold_range (irange &r, tree type, |
527 | const irange &op1, | |
80dd13f5 AM |
528 | const irange &op2, |
529 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
530 | virtual bool op1_range (irange &r, tree type, |
531 | const irange &lhs, | |
80dd13f5 AM |
532 | const irange &val, |
533 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
534 | virtual bool op2_range (irange &r, tree type, |
535 | const irange &lhs, | |
80dd13f5 AM |
536 | const irange &val, |
537 | relation_kind rel = VREL_NONE) const; | |
538 | virtual enum tree_code op1_op2_relation (const irange &lhs) const; | |
38a73435 AH |
539 | } op_equal; |
540 | ||
80dd13f5 AM |
541 | // Check if the LHS range indicates a relation between OP1 and OP2. |
542 | ||
543 | enum tree_code | |
544 | operator_equal::op1_op2_relation (const irange &lhs) const | |
545 | { | |
546 | if (lhs.undefined_p ()) | |
547 | return VREL_EMPTY; | |
548 | ||
549 | // FALSE = op1 == op2 indicates NE_EXPR. | |
550 | if (lhs.zero_p ()) | |
551 | return NE_EXPR; | |
552 | ||
553 | // TRUE = op1 == op2 indicates EQ_EXPR. | |
554 | if (!lhs.contains_p (build_zero_cst (lhs.type ()))) | |
555 | return EQ_EXPR; | |
556 | return VREL_NONE; | |
557 | } | |
558 | ||
559 | ||
f674b4a7 | 560 | bool |
4ba9fb0a AH |
561 | operator_equal::fold_range (irange &r, tree type, |
562 | const irange &op1, | |
80dd13f5 AM |
563 | const irange &op2, |
564 | relation_kind rel) const | |
38a73435 | 565 | { |
80dd13f5 | 566 | if (relop_early_resolve (r, type, op1, op2, rel, EQ_EXPR)) |
f674b4a7 | 567 | return true; |
38a73435 AH |
568 | |
569 | // We can be sure the values are always equal or not if both ranges | |
570 | // consist of a single value, and then compare them. | |
571 | if (wi::eq_p (op1.lower_bound (), op1.upper_bound ()) | |
572 | && wi::eq_p (op2.lower_bound (), op2.upper_bound ())) | |
573 | { | |
574 | if (wi::eq_p (op1.lower_bound (), op2.upper_bound())) | |
575 | r = range_true (type); | |
576 | else | |
577 | r = range_false (type); | |
578 | } | |
579 | else | |
580 | { | |
581 | // If ranges do not intersect, we know the range is not equal, | |
582 | // otherwise we don't know anything for sure. | |
22984f3f AM |
583 | int_range_max tmp = op1; |
584 | tmp.intersect (op2); | |
585 | if (tmp.undefined_p ()) | |
38a73435 AH |
586 | r = range_false (type); |
587 | else | |
588 | r = range_true_and_false (type); | |
589 | } | |
f674b4a7 | 590 | return true; |
38a73435 AH |
591 | } |
592 | ||
593 | bool | |
4ba9fb0a AH |
594 | operator_equal::op1_range (irange &r, tree type, |
595 | const irange &lhs, | |
80dd13f5 AM |
596 | const irange &op2, |
597 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
598 | { |
599 | switch (get_bool_state (r, lhs, type)) | |
600 | { | |
601 | case BRS_FALSE: | |
602 | // If the result is false, the only time we know anything is | |
603 | // if OP2 is a constant. | |
604 | if (wi::eq_p (op2.lower_bound(), op2.upper_bound())) | |
fae08a05 AH |
605 | { |
606 | r = op2; | |
607 | r.invert (); | |
608 | } | |
38a73435 AH |
609 | else |
610 | r.set_varying (type); | |
611 | break; | |
612 | ||
613 | case BRS_TRUE: | |
614 | // If it's true, the result is the same as OP2. | |
615 | r = op2; | |
616 | break; | |
617 | ||
618 | default: | |
619 | break; | |
620 | } | |
621 | return true; | |
622 | } | |
623 | ||
624 | bool | |
4ba9fb0a AH |
625 | operator_equal::op2_range (irange &r, tree type, |
626 | const irange &lhs, | |
80dd13f5 AM |
627 | const irange &op1, |
628 | relation_kind rel) const | |
38a73435 | 629 | { |
80dd13f5 | 630 | return operator_equal::op1_range (r, type, lhs, op1, rel); |
38a73435 AH |
631 | } |
632 | ||
38a73435 AH |
633 | class operator_not_equal : public range_operator |
634 | { | |
635 | public: | |
4ba9fb0a AH |
636 | virtual bool fold_range (irange &r, tree type, |
637 | const irange &op1, | |
80dd13f5 AM |
638 | const irange &op2, |
639 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
640 | virtual bool op1_range (irange &r, tree type, |
641 | const irange &lhs, | |
80dd13f5 AM |
642 | const irange &op2, |
643 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
644 | virtual bool op2_range (irange &r, tree type, |
645 | const irange &lhs, | |
80dd13f5 AM |
646 | const irange &op1, |
647 | relation_kind rel = VREL_NONE) const; | |
648 | virtual enum tree_code op1_op2_relation (const irange &lhs) const; | |
38a73435 AH |
649 | } op_not_equal; |
650 | ||
80dd13f5 AM |
651 | // Check if the LHS range indicates a relation between OP1 and OP2. |
652 | ||
653 | enum tree_code | |
654 | operator_not_equal::op1_op2_relation (const irange &lhs) const | |
655 | { | |
656 | if (lhs.undefined_p ()) | |
657 | return VREL_EMPTY; | |
658 | ||
659 | // FALSE = op1 != op2 indicates EQ_EXPR. | |
660 | if (lhs.zero_p ()) | |
661 | return EQ_EXPR; | |
662 | ||
663 | // TRUE = op1 != op2 indicates NE_EXPR. | |
664 | if (!lhs.contains_p (build_zero_cst (lhs.type ()))) | |
665 | return NE_EXPR; | |
666 | return VREL_NONE; | |
667 | } | |
668 | ||
f674b4a7 | 669 | bool |
4ba9fb0a AH |
670 | operator_not_equal::fold_range (irange &r, tree type, |
671 | const irange &op1, | |
80dd13f5 AM |
672 | const irange &op2, |
673 | relation_kind rel) const | |
38a73435 | 674 | { |
80dd13f5 | 675 | if (relop_early_resolve (r, type, op1, op2, rel, NE_EXPR)) |
f674b4a7 | 676 | return true; |
38a73435 AH |
677 | |
678 | // We can be sure the values are always equal or not if both ranges | |
679 | // consist of a single value, and then compare them. | |
680 | if (wi::eq_p (op1.lower_bound (), op1.upper_bound ()) | |
681 | && wi::eq_p (op2.lower_bound (), op2.upper_bound ())) | |
682 | { | |
683 | if (wi::ne_p (op1.lower_bound (), op2.upper_bound())) | |
684 | r = range_true (type); | |
685 | else | |
686 | r = range_false (type); | |
687 | } | |
688 | else | |
689 | { | |
690 | // If ranges do not intersect, we know the range is not equal, | |
691 | // otherwise we don't know anything for sure. | |
22984f3f AM |
692 | int_range_max tmp = op1; |
693 | tmp.intersect (op2); | |
694 | if (tmp.undefined_p ()) | |
38a73435 AH |
695 | r = range_true (type); |
696 | else | |
697 | r = range_true_and_false (type); | |
698 | } | |
f674b4a7 | 699 | return true; |
38a73435 AH |
700 | } |
701 | ||
702 | bool | |
4ba9fb0a AH |
703 | operator_not_equal::op1_range (irange &r, tree type, |
704 | const irange &lhs, | |
80dd13f5 AM |
705 | const irange &op2, |
706 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
707 | { |
708 | switch (get_bool_state (r, lhs, type)) | |
709 | { | |
710 | case BRS_TRUE: | |
711 | // If the result is true, the only time we know anything is if | |
712 | // OP2 is a constant. | |
713 | if (wi::eq_p (op2.lower_bound(), op2.upper_bound())) | |
fae08a05 AH |
714 | { |
715 | r = op2; | |
716 | r.invert (); | |
717 | } | |
38a73435 AH |
718 | else |
719 | r.set_varying (type); | |
720 | break; | |
721 | ||
722 | case BRS_FALSE: | |
ead233e6 | 723 | // If it's false, the result is the same as OP2. |
38a73435 AH |
724 | r = op2; |
725 | break; | |
726 | ||
727 | default: | |
728 | break; | |
729 | } | |
730 | return true; | |
731 | } | |
732 | ||
733 | ||
734 | bool | |
4ba9fb0a AH |
735 | operator_not_equal::op2_range (irange &r, tree type, |
736 | const irange &lhs, | |
80dd13f5 AM |
737 | const irange &op1, |
738 | relation_kind rel) const | |
38a73435 | 739 | { |
80dd13f5 | 740 | return operator_not_equal::op1_range (r, type, lhs, op1, rel); |
38a73435 AH |
741 | } |
742 | ||
743 | // (X < VAL) produces the range of [MIN, VAL - 1]. | |
744 | ||
745 | static void | |
4ba9fb0a | 746 | build_lt (irange &r, tree type, const wide_int &val) |
38a73435 AH |
747 | { |
748 | wi::overflow_type ov; | |
84f7bab8 AM |
749 | wide_int lim; |
750 | signop sgn = TYPE_SIGN (type); | |
751 | ||
752 | // Signed 1 bit cannot represent 1 for subtraction. | |
753 | if (sgn == SIGNED) | |
754 | lim = wi::add (val, -1, sgn, &ov); | |
755 | else | |
756 | lim = wi::sub (val, 1, sgn, &ov); | |
38a73435 AH |
757 | |
758 | // If val - 1 underflows, check if X < MIN, which is an empty range. | |
759 | if (ov) | |
760 | r.set_undefined (); | |
761 | else | |
4ba9fb0a | 762 | r = int_range<1> (type, min_limit (type), lim); |
38a73435 AH |
763 | } |
764 | ||
765 | // (X <= VAL) produces the range of [MIN, VAL]. | |
766 | ||
767 | static void | |
4ba9fb0a | 768 | build_le (irange &r, tree type, const wide_int &val) |
38a73435 | 769 | { |
4ba9fb0a | 770 | r = int_range<1> (type, min_limit (type), val); |
38a73435 AH |
771 | } |
772 | ||
773 | // (X > VAL) produces the range of [VAL + 1, MAX]. | |
774 | ||
775 | static void | |
4ba9fb0a | 776 | build_gt (irange &r, tree type, const wide_int &val) |
38a73435 AH |
777 | { |
778 | wi::overflow_type ov; | |
84f7bab8 AM |
779 | wide_int lim; |
780 | signop sgn = TYPE_SIGN (type); | |
781 | ||
782 | // Signed 1 bit cannot represent 1 for addition. | |
783 | if (sgn == SIGNED) | |
784 | lim = wi::sub (val, -1, sgn, &ov); | |
785 | else | |
786 | lim = wi::add (val, 1, sgn, &ov); | |
38a73435 AH |
787 | // If val + 1 overflows, check is for X > MAX, which is an empty range. |
788 | if (ov) | |
789 | r.set_undefined (); | |
790 | else | |
4ba9fb0a | 791 | r = int_range<1> (type, lim, max_limit (type)); |
38a73435 AH |
792 | } |
793 | ||
794 | // (X >= val) produces the range of [VAL, MAX]. | |
795 | ||
796 | static void | |
4ba9fb0a | 797 | build_ge (irange &r, tree type, const wide_int &val) |
38a73435 | 798 | { |
4ba9fb0a | 799 | r = int_range<1> (type, val, max_limit (type)); |
38a73435 AH |
800 | } |
801 | ||
802 | ||
803 | class operator_lt : public range_operator | |
804 | { | |
805 | public: | |
4ba9fb0a AH |
806 | virtual bool fold_range (irange &r, tree type, |
807 | const irange &op1, | |
80dd13f5 AM |
808 | const irange &op2, |
809 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
810 | virtual bool op1_range (irange &r, tree type, |
811 | const irange &lhs, | |
80dd13f5 AM |
812 | const irange &op2, |
813 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
814 | virtual bool op2_range (irange &r, tree type, |
815 | const irange &lhs, | |
80dd13f5 AM |
816 | const irange &op1, |
817 | relation_kind rel = VREL_NONE) const; | |
818 | virtual enum tree_code op1_op2_relation (const irange &lhs) const; | |
38a73435 AH |
819 | } op_lt; |
820 | ||
80dd13f5 AM |
821 | // Check if the LHS range indicates a relation between OP1 and OP2. |
822 | ||
823 | enum tree_code | |
824 | operator_lt::op1_op2_relation (const irange &lhs) const | |
825 | { | |
826 | if (lhs.undefined_p ()) | |
827 | return VREL_EMPTY; | |
828 | ||
829 | // FALSE = op1 < op2 indicates GE_EXPR. | |
830 | if (lhs.zero_p ()) | |
831 | return GE_EXPR; | |
832 | ||
833 | // TRUE = op1 < op2 indicates LT_EXPR. | |
834 | if (!lhs.contains_p (build_zero_cst (lhs.type ()))) | |
835 | return LT_EXPR; | |
836 | return VREL_NONE; | |
837 | } | |
838 | ||
f674b4a7 | 839 | bool |
4ba9fb0a AH |
840 | operator_lt::fold_range (irange &r, tree type, |
841 | const irange &op1, | |
80dd13f5 AM |
842 | const irange &op2, |
843 | relation_kind rel) const | |
38a73435 | 844 | { |
80dd13f5 | 845 | if (relop_early_resolve (r, type, op1, op2, rel, LT_EXPR)) |
f674b4a7 | 846 | return true; |
38a73435 AH |
847 | |
848 | signop sign = TYPE_SIGN (op1.type ()); | |
849 | gcc_checking_assert (sign == TYPE_SIGN (op2.type ())); | |
850 | ||
851 | if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign)) | |
852 | r = range_true (type); | |
853 | else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign)) | |
854 | r = range_false (type); | |
855 | else | |
856 | r = range_true_and_false (type); | |
f674b4a7 | 857 | return true; |
38a73435 AH |
858 | } |
859 | ||
860 | bool | |
4ba9fb0a AH |
861 | operator_lt::op1_range (irange &r, tree type, |
862 | const irange &lhs, | |
80dd13f5 AM |
863 | const irange &op2, |
864 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
865 | { |
866 | switch (get_bool_state (r, lhs, type)) | |
867 | { | |
868 | case BRS_TRUE: | |
869 | build_lt (r, type, op2.upper_bound ()); | |
870 | break; | |
871 | ||
872 | case BRS_FALSE: | |
873 | build_ge (r, type, op2.lower_bound ()); | |
874 | break; | |
875 | ||
876 | default: | |
877 | break; | |
878 | } | |
879 | return true; | |
880 | } | |
881 | ||
882 | bool | |
4ba9fb0a AH |
883 | operator_lt::op2_range (irange &r, tree type, |
884 | const irange &lhs, | |
80dd13f5 AM |
885 | const irange &op1, |
886 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
887 | { |
888 | switch (get_bool_state (r, lhs, type)) | |
889 | { | |
890 | case BRS_FALSE: | |
891 | build_le (r, type, op1.upper_bound ()); | |
892 | break; | |
893 | ||
894 | case BRS_TRUE: | |
895 | build_gt (r, type, op1.lower_bound ()); | |
896 | break; | |
897 | ||
898 | default: | |
899 | break; | |
900 | } | |
901 | return true; | |
902 | } | |
903 | ||
904 | ||
905 | class operator_le : public range_operator | |
906 | { | |
907 | public: | |
4ba9fb0a AH |
908 | virtual bool fold_range (irange &r, tree type, |
909 | const irange &op1, | |
80dd13f5 AM |
910 | const irange &op2, |
911 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
912 | virtual bool op1_range (irange &r, tree type, |
913 | const irange &lhs, | |
80dd13f5 AM |
914 | const irange &op2, |
915 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
916 | virtual bool op2_range (irange &r, tree type, |
917 | const irange &lhs, | |
80dd13f5 AM |
918 | const irange &op1, |
919 | relation_kind rel = VREL_NONE) const; | |
920 | virtual enum tree_code op1_op2_relation (const irange &lhs) const; | |
38a73435 AH |
921 | } op_le; |
922 | ||
80dd13f5 AM |
923 | // Check if the LHS range indicates a relation between OP1 and OP2. |
924 | ||
925 | enum tree_code | |
926 | operator_le::op1_op2_relation (const irange &lhs) const | |
927 | { | |
928 | if (lhs.undefined_p ()) | |
929 | return VREL_EMPTY; | |
930 | ||
931 | // FALSE = op1 <= op2 indicates GT_EXPR. | |
932 | if (lhs.zero_p ()) | |
933 | return GT_EXPR; | |
934 | ||
935 | // TRUE = op1 <= op2 indicates LE_EXPR. | |
936 | if (!lhs.contains_p (build_zero_cst (lhs.type ()))) | |
937 | return LE_EXPR; | |
938 | return VREL_NONE; | |
939 | } | |
940 | ||
f674b4a7 | 941 | bool |
4ba9fb0a AH |
942 | operator_le::fold_range (irange &r, tree type, |
943 | const irange &op1, | |
80dd13f5 AM |
944 | const irange &op2, |
945 | relation_kind rel) const | |
38a73435 | 946 | { |
80dd13f5 | 947 | if (relop_early_resolve (r, type, op1, op2, rel, LE_EXPR)) |
f674b4a7 | 948 | return true; |
38a73435 AH |
949 | |
950 | signop sign = TYPE_SIGN (op1.type ()); | |
951 | gcc_checking_assert (sign == TYPE_SIGN (op2.type ())); | |
952 | ||
953 | if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign)) | |
954 | r = range_true (type); | |
955 | else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign)) | |
956 | r = range_false (type); | |
957 | else | |
958 | r = range_true_and_false (type); | |
f674b4a7 | 959 | return true; |
38a73435 AH |
960 | } |
961 | ||
962 | bool | |
4ba9fb0a AH |
963 | operator_le::op1_range (irange &r, tree type, |
964 | const irange &lhs, | |
80dd13f5 AM |
965 | const irange &op2, |
966 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
967 | { |
968 | switch (get_bool_state (r, lhs, type)) | |
969 | { | |
970 | case BRS_TRUE: | |
971 | build_le (r, type, op2.upper_bound ()); | |
972 | break; | |
973 | ||
974 | case BRS_FALSE: | |
975 | build_gt (r, type, op2.lower_bound ()); | |
976 | break; | |
977 | ||
978 | default: | |
979 | break; | |
980 | } | |
981 | return true; | |
982 | } | |
983 | ||
984 | bool | |
4ba9fb0a AH |
985 | operator_le::op2_range (irange &r, tree type, |
986 | const irange &lhs, | |
80dd13f5 AM |
987 | const irange &op1, |
988 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
989 | { |
990 | switch (get_bool_state (r, lhs, type)) | |
991 | { | |
992 | case BRS_FALSE: | |
993 | build_lt (r, type, op1.upper_bound ()); | |
994 | break; | |
995 | ||
996 | case BRS_TRUE: | |
997 | build_ge (r, type, op1.lower_bound ()); | |
998 | break; | |
999 | ||
1000 | default: | |
1001 | break; | |
1002 | } | |
1003 | return true; | |
1004 | } | |
1005 | ||
1006 | ||
1007 | class operator_gt : public range_operator | |
1008 | { | |
1009 | public: | |
4ba9fb0a AH |
1010 | virtual bool fold_range (irange &r, tree type, |
1011 | const irange &op1, | |
80dd13f5 AM |
1012 | const irange &op2, |
1013 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
1014 | virtual bool op1_range (irange &r, tree type, |
1015 | const irange &lhs, | |
80dd13f5 AM |
1016 | const irange &op2, |
1017 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
1018 | virtual bool op2_range (irange &r, tree type, |
1019 | const irange &lhs, | |
80dd13f5 AM |
1020 | const irange &op1, |
1021 | relation_kind rel = VREL_NONE) const; | |
1022 | virtual enum tree_code op1_op2_relation (const irange &lhs) const; | |
38a73435 AH |
1023 | } op_gt; |
1024 | ||
80dd13f5 AM |
1025 | // Check if the LHS range indicates a relation between OP1 and OP2. |
1026 | ||
1027 | enum tree_code | |
1028 | operator_gt::op1_op2_relation (const irange &lhs) const | |
1029 | { | |
1030 | if (lhs.undefined_p ()) | |
1031 | return VREL_EMPTY; | |
1032 | ||
1033 | // FALSE = op1 > op2 indicates LE_EXPR. | |
1034 | if (lhs.zero_p ()) | |
1035 | return LE_EXPR; | |
1036 | ||
1037 | // TRUE = op1 > op2 indicates GT_EXPR. | |
1038 | if (!lhs.contains_p (build_zero_cst (lhs.type ()))) | |
1039 | return GT_EXPR; | |
1040 | return VREL_NONE; | |
1041 | } | |
1042 | ||
1043 | ||
f674b4a7 | 1044 | bool |
4ba9fb0a | 1045 | operator_gt::fold_range (irange &r, tree type, |
80dd13f5 AM |
1046 | const irange &op1, const irange &op2, |
1047 | relation_kind rel) const | |
38a73435 | 1048 | { |
80dd13f5 | 1049 | if (relop_early_resolve (r, type, op1, op2, rel, GT_EXPR)) |
f674b4a7 | 1050 | return true; |
38a73435 AH |
1051 | |
1052 | signop sign = TYPE_SIGN (op1.type ()); | |
1053 | gcc_checking_assert (sign == TYPE_SIGN (op2.type ())); | |
1054 | ||
1055 | if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign)) | |
1056 | r = range_true (type); | |
1057 | else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign)) | |
1058 | r = range_false (type); | |
1059 | else | |
1060 | r = range_true_and_false (type); | |
f674b4a7 | 1061 | return true; |
38a73435 AH |
1062 | } |
1063 | ||
1064 | bool | |
4ba9fb0a | 1065 | operator_gt::op1_range (irange &r, tree type, |
80dd13f5 AM |
1066 | const irange &lhs, const irange &op2, |
1067 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
1068 | { |
1069 | switch (get_bool_state (r, lhs, type)) | |
1070 | { | |
1071 | case BRS_TRUE: | |
1072 | build_gt (r, type, op2.lower_bound ()); | |
1073 | break; | |
1074 | ||
1075 | case BRS_FALSE: | |
1076 | build_le (r, type, op2.upper_bound ()); | |
1077 | break; | |
1078 | ||
1079 | default: | |
1080 | break; | |
1081 | } | |
1082 | return true; | |
1083 | } | |
1084 | ||
1085 | bool | |
4ba9fb0a AH |
1086 | operator_gt::op2_range (irange &r, tree type, |
1087 | const irange &lhs, | |
80dd13f5 AM |
1088 | const irange &op1, |
1089 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
1090 | { |
1091 | switch (get_bool_state (r, lhs, type)) | |
1092 | { | |
1093 | case BRS_FALSE: | |
1094 | build_ge (r, type, op1.lower_bound ()); | |
1095 | break; | |
1096 | ||
1097 | case BRS_TRUE: | |
1098 | build_lt (r, type, op1.upper_bound ()); | |
1099 | break; | |
1100 | ||
1101 | default: | |
1102 | break; | |
1103 | } | |
1104 | return true; | |
1105 | } | |
1106 | ||
1107 | ||
1108 | class operator_ge : public range_operator | |
1109 | { | |
1110 | public: | |
4ba9fb0a AH |
1111 | virtual bool fold_range (irange &r, tree type, |
1112 | const irange &op1, | |
80dd13f5 AM |
1113 | const irange &op2, |
1114 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
1115 | virtual bool op1_range (irange &r, tree type, |
1116 | const irange &lhs, | |
80dd13f5 AM |
1117 | const irange &op2, |
1118 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
1119 | virtual bool op2_range (irange &r, tree type, |
1120 | const irange &lhs, | |
80dd13f5 AM |
1121 | const irange &op1, |
1122 | relation_kind rel = VREL_NONE) const; | |
1123 | virtual enum tree_code op1_op2_relation (const irange &lhs) const; | |
38a73435 AH |
1124 | } op_ge; |
1125 | ||
80dd13f5 AM |
1126 | // Check if the LHS range indicates a relation between OP1 and OP2. |
1127 | ||
1128 | enum tree_code | |
1129 | operator_ge::op1_op2_relation (const irange &lhs) const | |
1130 | { | |
1131 | if (lhs.undefined_p ()) | |
1132 | return VREL_EMPTY; | |
1133 | ||
1134 | // FALSE = op1 >= op2 indicates LT_EXPR. | |
1135 | if (lhs.zero_p ()) | |
1136 | return LT_EXPR; | |
1137 | ||
1138 | // TRUE = op1 >= op2 indicates GE_EXPR. | |
1139 | if (!lhs.contains_p (build_zero_cst (lhs.type ()))) | |
1140 | return GE_EXPR; | |
1141 | return VREL_NONE; | |
1142 | } | |
1143 | ||
f674b4a7 | 1144 | bool |
4ba9fb0a AH |
1145 | operator_ge::fold_range (irange &r, tree type, |
1146 | const irange &op1, | |
80dd13f5 AM |
1147 | const irange &op2, |
1148 | relation_kind rel) const | |
38a73435 | 1149 | { |
80dd13f5 | 1150 | if (relop_early_resolve (r, type, op1, op2, rel, GE_EXPR)) |
f674b4a7 | 1151 | return true; |
38a73435 AH |
1152 | |
1153 | signop sign = TYPE_SIGN (op1.type ()); | |
1154 | gcc_checking_assert (sign == TYPE_SIGN (op2.type ())); | |
1155 | ||
1156 | if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign)) | |
1157 | r = range_true (type); | |
1158 | else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign)) | |
1159 | r = range_false (type); | |
1160 | else | |
1161 | r = range_true_and_false (type); | |
f674b4a7 | 1162 | return true; |
38a73435 AH |
1163 | } |
1164 | ||
1165 | bool | |
4ba9fb0a AH |
1166 | operator_ge::op1_range (irange &r, tree type, |
1167 | const irange &lhs, | |
80dd13f5 AM |
1168 | const irange &op2, |
1169 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
1170 | { |
1171 | switch (get_bool_state (r, lhs, type)) | |
1172 | { | |
1173 | case BRS_TRUE: | |
1174 | build_ge (r, type, op2.lower_bound ()); | |
1175 | break; | |
1176 | ||
1177 | case BRS_FALSE: | |
1178 | build_lt (r, type, op2.upper_bound ()); | |
1179 | break; | |
1180 | ||
1181 | default: | |
1182 | break; | |
1183 | } | |
1184 | return true; | |
1185 | } | |
1186 | ||
1187 | bool | |
4ba9fb0a AH |
1188 | operator_ge::op2_range (irange &r, tree type, |
1189 | const irange &lhs, | |
80dd13f5 AM |
1190 | const irange &op1, |
1191 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
1192 | { |
1193 | switch (get_bool_state (r, lhs, type)) | |
1194 | { | |
1195 | case BRS_FALSE: | |
1196 | build_gt (r, type, op1.lower_bound ()); | |
1197 | break; | |
1198 | ||
1199 | case BRS_TRUE: | |
1200 | build_le (r, type, op1.upper_bound ()); | |
1201 | break; | |
1202 | ||
1203 | default: | |
1204 | break; | |
1205 | } | |
1206 | return true; | |
1207 | } | |
1208 | ||
1209 | ||
1210 | class operator_plus : public range_operator | |
1211 | { | |
1212 | public: | |
4ba9fb0a AH |
1213 | virtual bool op1_range (irange &r, tree type, |
1214 | const irange &lhs, | |
80dd13f5 AM |
1215 | const irange &op2, |
1216 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
4ba9fb0a AH |
1217 | virtual bool op2_range (irange &r, tree type, |
1218 | const irange &lhs, | |
80dd13f5 AM |
1219 | const irange &op1, |
1220 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
4ba9fb0a | 1221 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
1222 | const wide_int &lh_lb, |
1223 | const wide_int &lh_ub, | |
1224 | const wide_int &rh_lb, | |
1225 | const wide_int &rh_ub) const; | |
c526de3f AM |
1226 | virtual enum tree_code lhs_op1_relation (const irange &lhs, const irange &op1, |
1227 | const irange &op2) const; | |
1228 | virtual enum tree_code lhs_op2_relation (const irange &lhs, const irange &op1, | |
1229 | const irange &op2) const; | |
38a73435 AH |
1230 | } op_plus; |
1231 | ||
c526de3f AM |
1232 | // Check to see if the range of OP2 indicates anything about the relation |
1233 | // between LHS and OP1. | |
1234 | ||
1235 | enum tree_code | |
1236 | operator_plus::lhs_op1_relation (const irange &lhs, | |
1237 | const irange &op1, | |
1238 | const irange &op2) const | |
1239 | { | |
1240 | if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ()) | |
1241 | return VREL_NONE; | |
1242 | ||
1243 | tree type = lhs.type (); | |
1244 | unsigned prec = TYPE_PRECISION (type); | |
1245 | wi::overflow_type ovf1, ovf2; | |
1246 | signop sign = TYPE_SIGN (type); | |
1247 | ||
1248 | // LHS = OP1 + 0 indicates LHS == OP1. | |
1249 | if (op2.zero_p ()) | |
1250 | return EQ_EXPR; | |
1251 | ||
1252 | if (TYPE_OVERFLOW_WRAPS (type)) | |
1253 | { | |
1254 | wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1); | |
1255 | wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2); | |
1256 | } | |
1257 | else | |
1258 | ovf1 = ovf2 = wi::OVF_NONE; | |
1259 | ||
1260 | // Never wrapping additions. | |
1261 | if (!ovf1 && !ovf2) | |
1262 | { | |
1263 | // Positive op2 means lhs > op1. | |
1264 | if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign)) | |
1265 | return GT_EXPR; | |
1266 | if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign)) | |
1267 | return GE_EXPR; | |
1268 | ||
1269 | // Negative op2 means lhs < op1. | |
1270 | if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign)) | |
1271 | return LT_EXPR; | |
1272 | if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign)) | |
1273 | return LE_EXPR; | |
1274 | } | |
1275 | // Always wrapping additions. | |
1276 | else if (ovf1 && ovf1 == ovf2) | |
1277 | { | |
1278 | // Positive op2 means lhs < op1. | |
1279 | if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign)) | |
1280 | return LT_EXPR; | |
1281 | if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign)) | |
1282 | return LE_EXPR; | |
1283 | ||
1284 | // Negative op2 means lhs > op1. | |
1285 | if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign)) | |
1286 | return GT_EXPR; | |
1287 | if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign)) | |
1288 | return GE_EXPR; | |
1289 | } | |
1290 | ||
1291 | // If op2 does not contain 0, then LHS and OP1 can never be equal. | |
1292 | if (!range_includes_zero_p (&op2)) | |
1293 | return NE_EXPR; | |
1294 | ||
1295 | return VREL_NONE; | |
1296 | } | |
1297 | ||
1298 | // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed | |
1299 | // operands. | |
1300 | ||
1301 | enum tree_code | |
1302 | operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1, | |
1303 | const irange &op2) const | |
1304 | { | |
1305 | return lhs_op1_relation (lhs, op2, op1); | |
1306 | } | |
1307 | ||
bb74ef9e | 1308 | void |
4ba9fb0a | 1309 | operator_plus::wi_fold (irange &r, tree type, |
38a73435 AH |
1310 | const wide_int &lh_lb, const wide_int &lh_ub, |
1311 | const wide_int &rh_lb, const wide_int &rh_ub) const | |
1312 | { | |
1313 | wi::overflow_type ov_lb, ov_ub; | |
1314 | signop s = TYPE_SIGN (type); | |
1315 | wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb); | |
1316 | wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub); | |
bb74ef9e | 1317 | value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub); |
38a73435 AH |
1318 | } |
1319 | ||
1320 | bool | |
4ba9fb0a AH |
1321 | operator_plus::op1_range (irange &r, tree type, |
1322 | const irange &lhs, | |
80dd13f5 AM |
1323 | const irange &op2, |
1324 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 1325 | { |
f674b4a7 | 1326 | return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op2); |
38a73435 AH |
1327 | } |
1328 | ||
1329 | bool | |
4ba9fb0a AH |
1330 | operator_plus::op2_range (irange &r, tree type, |
1331 | const irange &lhs, | |
80dd13f5 AM |
1332 | const irange &op1, |
1333 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 1334 | { |
f674b4a7 | 1335 | return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op1); |
38a73435 AH |
1336 | } |
1337 | ||
1338 | ||
1339 | class operator_minus : public range_operator | |
1340 | { | |
1341 | public: | |
4ba9fb0a AH |
1342 | virtual bool op1_range (irange &r, tree type, |
1343 | const irange &lhs, | |
80dd13f5 AM |
1344 | const irange &op2, |
1345 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
4ba9fb0a AH |
1346 | virtual bool op2_range (irange &r, tree type, |
1347 | const irange &lhs, | |
80dd13f5 AM |
1348 | const irange &op1, |
1349 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
4ba9fb0a | 1350 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
1351 | const wide_int &lh_lb, |
1352 | const wide_int &lh_ub, | |
1353 | const wide_int &rh_lb, | |
1354 | const wide_int &rh_ub) const; | |
ae6b830f AM |
1355 | virtual bool op1_op2_relation_effect (irange &lhs_range, |
1356 | tree type, | |
1357 | const irange &op1_range, | |
1358 | const irange &op2_range, | |
1359 | relation_kind rel) const; | |
38a73435 AH |
1360 | } op_minus; |
1361 | ||
bb74ef9e | 1362 | void |
4ba9fb0a | 1363 | operator_minus::wi_fold (irange &r, tree type, |
38a73435 AH |
1364 | const wide_int &lh_lb, const wide_int &lh_ub, |
1365 | const wide_int &rh_lb, const wide_int &rh_ub) const | |
1366 | { | |
1367 | wi::overflow_type ov_lb, ov_ub; | |
1368 | signop s = TYPE_SIGN (type); | |
1369 | wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb); | |
1370 | wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub); | |
bb74ef9e | 1371 | value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub); |
38a73435 AH |
1372 | } |
1373 | ||
ae6b830f | 1374 | // Check to see if the relation REL between OP1 and OP2 has any effect on the |
8af8abfb AH |
1375 | // LHS of the expression. If so, apply it to LHS_RANGE. This is a helper |
1376 | // function for both MINUS_EXPR and POINTER_DIFF_EXPR. | |
ae6b830f | 1377 | |
8af8abfb AH |
1378 | static bool |
1379 | minus_op1_op2_relation_effect (irange &lhs_range, tree type, | |
1380 | const irange &op1_range ATTRIBUTE_UNUSED, | |
1381 | const irange &op2_range ATTRIBUTE_UNUSED, | |
1382 | relation_kind rel) | |
ae6b830f AM |
1383 | { |
1384 | if (rel == VREL_NONE) | |
1385 | return false; | |
1386 | ||
1387 | int_range<2> rel_range; | |
1388 | unsigned prec = TYPE_PRECISION (type); | |
1389 | signop sgn = TYPE_SIGN (type); | |
1390 | ||
a96d8d67 AM |
1391 | // == and != produce [0,0] and ~[0,0] regardless of wrapping. |
1392 | if (rel == EQ_EXPR) | |
1393 | rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec)); | |
1394 | else if (rel == NE_EXPR) | |
1395 | rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec), | |
1396 | VR_ANTI_RANGE); | |
1397 | else if (TYPE_OVERFLOW_WRAPS (type)) | |
ae6b830f | 1398 | { |
a96d8d67 AM |
1399 | switch (rel) |
1400 | { | |
1401 | // For wrapping signed values and unsigned, if op1 > op2 or | |
1402 | // op1 < op2, then op1 - op2 can be restricted to ~[0, 0]. | |
1403 | case GT_EXPR: | |
1404 | case LT_EXPR: | |
1405 | rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec), | |
1406 | VR_ANTI_RANGE); | |
1407 | break; | |
1408 | default: | |
1409 | return false; | |
1410 | } | |
1411 | } | |
1412 | else | |
1413 | { | |
1414 | switch (rel) | |
1415 | { | |
1416 | // op1 > op2, op1 - op2 can be restricted to [1, +INF] | |
1417 | case GT_EXPR: | |
1418 | rel_range = int_range<2> (type, wi::one (prec), | |
1419 | wi::max_value (prec, sgn)); | |
1420 | break; | |
1421 | // op1 >= op2, op1 - op2 can be restricted to [0, +INF] | |
1422 | case GE_EXPR: | |
1423 | rel_range = int_range<2> (type, wi::zero (prec), | |
1424 | wi::max_value (prec, sgn)); | |
1425 | break; | |
1426 | // op1 < op2, op1 - op2 can be restricted to [-INF, -1] | |
1427 | case LT_EXPR: | |
1428 | rel_range = int_range<2> (type, wi::min_value (prec, sgn), | |
1429 | wi::minus_one (prec)); | |
1430 | break; | |
1431 | // op1 <= op2, op1 - op2 can be restricted to [-INF, 0] | |
1432 | case LE_EXPR: | |
1433 | rel_range = int_range<2> (type, wi::min_value (prec, sgn), | |
1434 | wi::zero (prec)); | |
1435 | break; | |
1436 | default: | |
1437 | return false; | |
1438 | } | |
ae6b830f AM |
1439 | } |
1440 | lhs_range.intersect (rel_range); | |
1441 | return true; | |
1442 | } | |
1443 | ||
8af8abfb AH |
1444 | bool |
1445 | operator_minus::op1_op2_relation_effect (irange &lhs_range, tree type, | |
1446 | const irange &op1_range, | |
1447 | const irange &op2_range, | |
1448 | relation_kind rel) const | |
1449 | { | |
1450 | return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range, | |
1451 | rel); | |
1452 | } | |
1453 | ||
38a73435 | 1454 | bool |
4ba9fb0a AH |
1455 | operator_minus::op1_range (irange &r, tree type, |
1456 | const irange &lhs, | |
80dd13f5 AM |
1457 | const irange &op2, |
1458 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 1459 | { |
f674b4a7 | 1460 | return range_op_handler (PLUS_EXPR, type)->fold_range (r, type, lhs, op2); |
38a73435 AH |
1461 | } |
1462 | ||
1463 | bool | |
4ba9fb0a AH |
1464 | operator_minus::op2_range (irange &r, tree type, |
1465 | const irange &lhs, | |
80dd13f5 AM |
1466 | const irange &op1, |
1467 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 1468 | { |
f674b4a7 | 1469 | return fold_range (r, type, op1, lhs); |
38a73435 AH |
1470 | } |
1471 | ||
1472 | ||
8af8abfb AH |
1473 | class operator_pointer_diff : public range_operator |
1474 | { | |
1475 | virtual bool op1_op2_relation_effect (irange &lhs_range, | |
1476 | tree type, | |
1477 | const irange &op1_range, | |
1478 | const irange &op2_range, | |
1479 | relation_kind rel) const; | |
1480 | } op_pointer_diff; | |
1481 | ||
1482 | bool | |
1483 | operator_pointer_diff::op1_op2_relation_effect (irange &lhs_range, tree type, | |
1484 | const irange &op1_range, | |
1485 | const irange &op2_range, | |
1486 | relation_kind rel) const | |
1487 | { | |
1488 | return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range, | |
1489 | rel); | |
1490 | } | |
1491 | ||
1492 | ||
38a73435 AH |
1493 | class operator_min : public range_operator |
1494 | { | |
1495 | public: | |
4ba9fb0a | 1496 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
1497 | const wide_int &lh_lb, |
1498 | const wide_int &lh_ub, | |
1499 | const wide_int &rh_lb, | |
1500 | const wide_int &rh_ub) const; | |
38a73435 AH |
1501 | } op_min; |
1502 | ||
bb74ef9e | 1503 | void |
4ba9fb0a | 1504 | operator_min::wi_fold (irange &r, tree type, |
38a73435 AH |
1505 | const wide_int &lh_lb, const wide_int &lh_ub, |
1506 | const wide_int &rh_lb, const wide_int &rh_ub) const | |
1507 | { | |
1508 | signop s = TYPE_SIGN (type); | |
1509 | wide_int new_lb = wi::min (lh_lb, rh_lb, s); | |
1510 | wide_int new_ub = wi::min (lh_ub, rh_ub, s); | |
bb74ef9e | 1511 | value_range_with_overflow (r, type, new_lb, new_ub); |
38a73435 AH |
1512 | } |
1513 | ||
1514 | ||
1515 | class operator_max : public range_operator | |
1516 | { | |
1517 | public: | |
4ba9fb0a | 1518 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
1519 | const wide_int &lh_lb, |
1520 | const wide_int &lh_ub, | |
1521 | const wide_int &rh_lb, | |
1522 | const wide_int &rh_ub) const; | |
38a73435 AH |
1523 | } op_max; |
1524 | ||
bb74ef9e | 1525 | void |
4ba9fb0a | 1526 | operator_max::wi_fold (irange &r, tree type, |
38a73435 AH |
1527 | const wide_int &lh_lb, const wide_int &lh_ub, |
1528 | const wide_int &rh_lb, const wide_int &rh_ub) const | |
1529 | { | |
1530 | signop s = TYPE_SIGN (type); | |
1531 | wide_int new_lb = wi::max (lh_lb, rh_lb, s); | |
1532 | wide_int new_ub = wi::max (lh_ub, rh_ub, s); | |
bb74ef9e | 1533 | value_range_with_overflow (r, type, new_lb, new_ub); |
38a73435 AH |
1534 | } |
1535 | ||
1536 | ||
1537 | class cross_product_operator : public range_operator | |
1538 | { | |
1539 | public: | |
1540 | // Perform an operation between two wide-ints and place the result | |
1541 | // in R. Return true if the operation overflowed. | |
1542 | virtual bool wi_op_overflows (wide_int &r, | |
1543 | tree type, | |
1544 | const wide_int &, | |
1545 | const wide_int &) const = 0; | |
1546 | ||
1547 | // Calculate the cross product of two sets of sub-ranges and return it. | |
4ba9fb0a | 1548 | void wi_cross_product (irange &r, tree type, |
bb74ef9e AM |
1549 | const wide_int &lh_lb, |
1550 | const wide_int &lh_ub, | |
1551 | const wide_int &rh_lb, | |
1552 | const wide_int &rh_ub) const; | |
38a73435 AH |
1553 | }; |
1554 | ||
1555 | // Calculate the cross product of two sets of ranges and return it. | |
1556 | // | |
1557 | // Multiplications, divisions and shifts are a bit tricky to handle, | |
1558 | // depending on the mix of signs we have in the two ranges, we need to | |
1559 | // operate on different values to get the minimum and maximum values | |
1560 | // for the new range. One approach is to figure out all the | |
1561 | // variations of range combinations and do the operations. | |
1562 | // | |
1563 | // However, this involves several calls to compare_values and it is | |
1564 | // pretty convoluted. It's simpler to do the 4 operations (MIN0 OP | |
1565 | // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then | |
1566 | // figure the smallest and largest values to form the new range. | |
1567 | ||
bb74ef9e | 1568 | void |
4ba9fb0a | 1569 | cross_product_operator::wi_cross_product (irange &r, tree type, |
38a73435 AH |
1570 | const wide_int &lh_lb, |
1571 | const wide_int &lh_ub, | |
1572 | const wide_int &rh_lb, | |
1573 | const wide_int &rh_ub) const | |
1574 | { | |
1575 | wide_int cp1, cp2, cp3, cp4; | |
bb74ef9e | 1576 | // Default to varying. |
4ba9fb0a | 1577 | r.set_varying (type); |
38a73435 AH |
1578 | |
1579 | // Compute the 4 cross operations, bailing if we get an overflow we | |
1580 | // can't handle. | |
1581 | if (wi_op_overflows (cp1, type, lh_lb, rh_lb)) | |
bb74ef9e | 1582 | return; |
38a73435 AH |
1583 | if (wi::eq_p (lh_lb, lh_ub)) |
1584 | cp3 = cp1; | |
1585 | else if (wi_op_overflows (cp3, type, lh_ub, rh_lb)) | |
bb74ef9e | 1586 | return; |
38a73435 AH |
1587 | if (wi::eq_p (rh_lb, rh_ub)) |
1588 | cp2 = cp1; | |
1589 | else if (wi_op_overflows (cp2, type, lh_lb, rh_ub)) | |
bb74ef9e | 1590 | return; |
38a73435 AH |
1591 | if (wi::eq_p (lh_lb, lh_ub)) |
1592 | cp4 = cp2; | |
1593 | else if (wi_op_overflows (cp4, type, lh_ub, rh_ub)) | |
bb74ef9e | 1594 | return; |
38a73435 AH |
1595 | |
1596 | // Order pairs. | |
1597 | signop sign = TYPE_SIGN (type); | |
1598 | if (wi::gt_p (cp1, cp2, sign)) | |
1599 | std::swap (cp1, cp2); | |
1600 | if (wi::gt_p (cp3, cp4, sign)) | |
1601 | std::swap (cp3, cp4); | |
1602 | ||
1603 | // Choose min and max from the ordered pairs. | |
1604 | wide_int res_lb = wi::min (cp1, cp3, sign); | |
1605 | wide_int res_ub = wi::max (cp2, cp4, sign); | |
bb74ef9e | 1606 | value_range_with_overflow (r, type, res_lb, res_ub); |
38a73435 AH |
1607 | } |
1608 | ||
1609 | ||
1610 | class operator_mult : public cross_product_operator | |
1611 | { | |
1612 | public: | |
4ba9fb0a | 1613 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
1614 | const wide_int &lh_lb, |
1615 | const wide_int &lh_ub, | |
1616 | const wide_int &rh_lb, | |
1617 | const wide_int &rh_ub) const; | |
028d81b1 AH |
1618 | virtual bool wi_op_overflows (wide_int &res, tree type, |
1619 | const wide_int &w0, const wide_int &w1) const; | |
4ba9fb0a AH |
1620 | virtual bool op1_range (irange &r, tree type, |
1621 | const irange &lhs, | |
80dd13f5 AM |
1622 | const irange &op2, |
1623 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
4ba9fb0a AH |
1624 | virtual bool op2_range (irange &r, tree type, |
1625 | const irange &lhs, | |
80dd13f5 AM |
1626 | const irange &op1, |
1627 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
38a73435 AH |
1628 | } op_mult; |
1629 | ||
4ba9fb0a AH |
1630 | bool |
1631 | operator_mult::op1_range (irange &r, tree type, | |
80dd13f5 AM |
1632 | const irange &lhs, const irange &op2, |
1633 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
1634 | { |
1635 | tree offset; | |
1636 | ||
1637 | // We can't solve 0 = OP1 * N by dividing by N with a wrapping type. | |
1638 | // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas | |
1639 | // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit) | |
1640 | if (TYPE_OVERFLOW_WRAPS (type)) | |
1641 | return false; | |
1642 | ||
1643 | if (op2.singleton_p (&offset) && !integer_zerop (offset)) | |
1644 | return range_op_handler (TRUNC_DIV_EXPR, type)->fold_range (r, type, | |
1645 | lhs, op2); | |
1646 | return false; | |
1647 | } | |
1648 | ||
1649 | bool | |
1650 | operator_mult::op2_range (irange &r, tree type, | |
80dd13f5 AM |
1651 | const irange &lhs, const irange &op1, |
1652 | relation_kind rel) const | |
4ba9fb0a | 1653 | { |
80dd13f5 | 1654 | return operator_mult::op1_range (r, type, lhs, op1, rel); |
4ba9fb0a AH |
1655 | } |
1656 | ||
38a73435 | 1657 | bool |
028d81b1 AH |
1658 | operator_mult::wi_op_overflows (wide_int &res, tree type, |
1659 | const wide_int &w0, const wide_int &w1) const | |
38a73435 AH |
1660 | { |
1661 | wi::overflow_type overflow = wi::OVF_NONE; | |
1662 | signop sign = TYPE_SIGN (type); | |
1663 | res = wi::mul (w0, w1, sign, &overflow); | |
1664 | if (overflow && TYPE_OVERFLOW_UNDEFINED (type)) | |
1665 | { | |
1666 | // For multiplication, the sign of the overflow is given | |
1667 | // by the comparison of the signs of the operands. | |
1668 | if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ()) | |
1669 | res = wi::max_value (w0.get_precision (), sign); | |
1670 | else | |
1671 | res = wi::min_value (w0.get_precision (), sign); | |
1672 | return false; | |
1673 | } | |
1674 | return overflow; | |
1675 | } | |
1676 | ||
bb74ef9e | 1677 | void |
4ba9fb0a | 1678 | operator_mult::wi_fold (irange &r, tree type, |
38a73435 AH |
1679 | const wide_int &lh_lb, const wide_int &lh_ub, |
1680 | const wide_int &rh_lb, const wide_int &rh_ub) const | |
1681 | { | |
1682 | if (TYPE_OVERFLOW_UNDEFINED (type)) | |
bb74ef9e AM |
1683 | { |
1684 | wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub); | |
1685 | return; | |
1686 | } | |
38a73435 AH |
1687 | |
1688 | // Multiply the ranges when overflow wraps. This is basically fancy | |
1689 | // code so we don't drop to varying with an unsigned | |
1690 | // [-3,-1]*[-3,-1]. | |
1691 | // | |
1692 | // This test requires 2*prec bits if both operands are signed and | |
1693 | // 2*prec + 2 bits if either is not. Therefore, extend the values | |
1694 | // using the sign of the result to PREC2. From here on out, | |
1695 | // everthing is just signed math no matter what the input types | |
1696 | // were. | |
1697 | ||
1698 | signop sign = TYPE_SIGN (type); | |
1699 | unsigned prec = TYPE_PRECISION (type); | |
1700 | widest2_int min0 = widest2_int::from (lh_lb, sign); | |
1701 | widest2_int max0 = widest2_int::from (lh_ub, sign); | |
1702 | widest2_int min1 = widest2_int::from (rh_lb, sign); | |
1703 | widest2_int max1 = widest2_int::from (rh_ub, sign); | |
1704 | widest2_int sizem1 = wi::mask <widest2_int> (prec, false); | |
1705 | widest2_int size = sizem1 + 1; | |
1706 | ||
1707 | // Canonicalize the intervals. | |
1708 | if (sign == UNSIGNED) | |
1709 | { | |
1710 | if (wi::ltu_p (size, min0 + max0)) | |
1711 | { | |
1712 | min0 -= size; | |
1713 | max0 -= size; | |
1714 | } | |
1715 | if (wi::ltu_p (size, min1 + max1)) | |
1716 | { | |
1717 | min1 -= size; | |
1718 | max1 -= size; | |
1719 | } | |
1720 | } | |
1721 | ||
1722 | // Sort the 4 products so that min is in prod0 and max is in | |
1723 | // prod3. | |
1724 | widest2_int prod0 = min0 * min1; | |
1725 | widest2_int prod1 = min0 * max1; | |
1726 | widest2_int prod2 = max0 * min1; | |
1727 | widest2_int prod3 = max0 * max1; | |
1728 | ||
1729 | // min0min1 > max0max1 | |
1730 | if (prod0 > prod3) | |
1731 | std::swap (prod0, prod3); | |
1732 | ||
1733 | // min0max1 > max0min1 | |
1734 | if (prod1 > prod2) | |
1735 | std::swap (prod1, prod2); | |
1736 | ||
1737 | if (prod0 > prod1) | |
1738 | std::swap (prod0, prod1); | |
1739 | ||
1740 | if (prod2 > prod3) | |
1741 | std::swap (prod2, prod3); | |
1742 | ||
1743 | // diff = max - min | |
1744 | prod2 = prod3 - prod0; | |
1745 | if (wi::geu_p (prod2, sizem1)) | |
1746 | // The range covers all values. | |
4ba9fb0a | 1747 | r.set_varying (type); |
bb74ef9e AM |
1748 | else |
1749 | { | |
1750 | wide_int new_lb = wide_int::from (prod0, prec, sign); | |
1751 | wide_int new_ub = wide_int::from (prod3, prec, sign); | |
1752 | create_possibly_reversed_range (r, type, new_lb, new_ub); | |
1753 | } | |
38a73435 AH |
1754 | } |
1755 | ||
1756 | ||
1757 | class operator_div : public cross_product_operator | |
1758 | { | |
1759 | public: | |
1760 | operator_div (enum tree_code c) { code = c; } | |
4ba9fb0a | 1761 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
1762 | const wide_int &lh_lb, |
1763 | const wide_int &lh_ub, | |
1764 | const wide_int &rh_lb, | |
1765 | const wide_int &rh_ub) const; | |
028d81b1 AH |
1766 | virtual bool wi_op_overflows (wide_int &res, tree type, |
1767 | const wide_int &, const wide_int &) const; | |
38a73435 AH |
1768 | private: |
1769 | enum tree_code code; | |
1770 | }; | |
1771 | ||
1772 | bool | |
028d81b1 AH |
1773 | operator_div::wi_op_overflows (wide_int &res, tree type, |
1774 | const wide_int &w0, const wide_int &w1) const | |
38a73435 AH |
1775 | { |
1776 | if (w1 == 0) | |
1777 | return true; | |
1778 | ||
1779 | wi::overflow_type overflow = wi::OVF_NONE; | |
1780 | signop sign = TYPE_SIGN (type); | |
1781 | ||
1782 | switch (code) | |
1783 | { | |
1784 | case EXACT_DIV_EXPR: | |
1785 | // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in | |
1786 | // operator_exact_divide. No need to handle it here. | |
1787 | gcc_unreachable (); | |
1788 | break; | |
1789 | case TRUNC_DIV_EXPR: | |
1790 | res = wi::div_trunc (w0, w1, sign, &overflow); | |
1791 | break; | |
1792 | case FLOOR_DIV_EXPR: | |
1793 | res = wi::div_floor (w0, w1, sign, &overflow); | |
1794 | break; | |
1795 | case ROUND_DIV_EXPR: | |
1796 | res = wi::div_round (w0, w1, sign, &overflow); | |
1797 | break; | |
1798 | case CEIL_DIV_EXPR: | |
1799 | res = wi::div_ceil (w0, w1, sign, &overflow); | |
1800 | break; | |
1801 | default: | |
1802 | gcc_unreachable (); | |
1803 | } | |
1804 | ||
1805 | if (overflow && TYPE_OVERFLOW_UNDEFINED (type)) | |
1806 | { | |
1807 | // For division, the only case is -INF / -1 = +INF. | |
1808 | res = wi::max_value (w0.get_precision (), sign); | |
1809 | return false; | |
1810 | } | |
1811 | return overflow; | |
1812 | } | |
1813 | ||
bb74ef9e | 1814 | void |
4ba9fb0a | 1815 | operator_div::wi_fold (irange &r, tree type, |
38a73435 AH |
1816 | const wide_int &lh_lb, const wide_int &lh_ub, |
1817 | const wide_int &rh_lb, const wide_int &rh_ub) const | |
1818 | { | |
38a73435 AH |
1819 | const wide_int dividend_min = lh_lb; |
1820 | const wide_int dividend_max = lh_ub; | |
1821 | const wide_int divisor_min = rh_lb; | |
1822 | const wide_int divisor_max = rh_ub; | |
1823 | signop sign = TYPE_SIGN (type); | |
1824 | unsigned prec = TYPE_PRECISION (type); | |
1825 | wide_int extra_min, extra_max; | |
1826 | ||
1827 | // If we know we won't divide by zero, just do the division. | |
1828 | if (!wi_includes_zero_p (type, divisor_min, divisor_max)) | |
bb74ef9e AM |
1829 | { |
1830 | wi_cross_product (r, type, dividend_min, dividend_max, | |
1831 | divisor_min, divisor_max); | |
1832 | return; | |
1833 | } | |
38a73435 AH |
1834 | |
1835 | // If flag_non_call_exceptions, we must not eliminate a division by zero. | |
1836 | if (cfun->can_throw_non_call_exceptions) | |
bb74ef9e | 1837 | { |
4ba9fb0a | 1838 | r.set_varying (type); |
bb74ef9e AM |
1839 | return; |
1840 | } | |
38a73435 AH |
1841 | |
1842 | // If we're definitely dividing by zero, there's nothing to do. | |
1843 | if (wi_zero_p (type, divisor_min, divisor_max)) | |
bb74ef9e | 1844 | { |
ebbcdd7f | 1845 | r.set_undefined (); |
bb74ef9e AM |
1846 | return; |
1847 | } | |
38a73435 AH |
1848 | |
1849 | // Perform the division in 2 parts, [LB, -1] and [1, UB], which will | |
1850 | // skip any division by zero. | |
1851 | ||
1852 | // First divide by the negative numbers, if any. | |
38a73435 | 1853 | if (wi::neg_p (divisor_min, sign)) |
bb74ef9e AM |
1854 | wi_cross_product (r, type, dividend_min, dividend_max, |
1855 | divisor_min, wi::minus_one (prec)); | |
1856 | else | |
4ba9fb0a | 1857 | r.set_undefined (); |
bb74ef9e | 1858 | |
38a73435 AH |
1859 | // Then divide by the non-zero positive numbers, if any. |
1860 | if (wi::gt_p (divisor_max, wi::zero (prec), sign)) | |
1861 | { | |
c5a6c223 | 1862 | int_range_max tmp; |
bb74ef9e AM |
1863 | wi_cross_product (tmp, type, dividend_min, dividend_max, |
1864 | wi::one (prec), divisor_max); | |
38a73435 AH |
1865 | r.union_ (tmp); |
1866 | } | |
bb74ef9e AM |
1867 | // We shouldn't still have undefined here. |
1868 | gcc_checking_assert (!r.undefined_p ()); | |
38a73435 AH |
1869 | } |
1870 | ||
1871 | operator_div op_trunc_div (TRUNC_DIV_EXPR); | |
bb74ef9e | 1872 | operator_div op_floor_div (FLOOR_DIV_EXPR); |
38a73435 AH |
1873 | operator_div op_round_div (ROUND_DIV_EXPR); |
1874 | operator_div op_ceil_div (CEIL_DIV_EXPR); | |
1875 | ||
1876 | ||
1877 | class operator_exact_divide : public operator_div | |
1878 | { | |
1879 | public: | |
1880 | operator_exact_divide () : operator_div (TRUNC_DIV_EXPR) { } | |
4ba9fb0a AH |
1881 | virtual bool op1_range (irange &r, tree type, |
1882 | const irange &lhs, | |
80dd13f5 AM |
1883 | const irange &op2, |
1884 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
38a73435 AH |
1885 | |
1886 | } op_exact_div; | |
1887 | ||
1888 | bool | |
4ba9fb0a AH |
1889 | operator_exact_divide::op1_range (irange &r, tree type, |
1890 | const irange &lhs, | |
80dd13f5 AM |
1891 | const irange &op2, |
1892 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
1893 | { |
1894 | tree offset; | |
1895 | // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about | |
1896 | // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12]. | |
1897 | // We wont bother trying to enumerate all the in between stuff :-P | |
1898 | // TRUE accuraacy is [6,6][9,9][12,12]. This is unlikely to matter most of | |
1899 | // the time however. | |
1900 | // If op2 is a multiple of 2, we would be able to set some non-zero bits. | |
1901 | if (op2.singleton_p (&offset) | |
1902 | && !integer_zerop (offset)) | |
f674b4a7 | 1903 | return range_op_handler (MULT_EXPR, type)->fold_range (r, type, lhs, op2); |
38a73435 AH |
1904 | return false; |
1905 | } | |
1906 | ||
1907 | ||
1908 | class operator_lshift : public cross_product_operator | |
1909 | { | |
1910 | public: | |
4ba9fb0a AH |
1911 | virtual bool op1_range (irange &r, tree type, |
1912 | const irange &lhs, | |
80dd13f5 AM |
1913 | const irange &op2, |
1914 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
1915 | virtual bool fold_range (irange &r, tree type, |
1916 | const irange &op1, | |
80dd13f5 AM |
1917 | const irange &op2, |
1918 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
1919 | |
1920 | virtual void wi_fold (irange &r, tree type, | |
bb74ef9e AM |
1921 | const wide_int &lh_lb, const wide_int &lh_ub, |
1922 | const wide_int &rh_lb, const wide_int &rh_ub) const; | |
38a73435 AH |
1923 | virtual bool wi_op_overflows (wide_int &res, |
1924 | tree type, | |
1925 | const wide_int &, | |
1926 | const wide_int &) const; | |
1927 | } op_lshift; | |
1928 | ||
bd431d26 AH |
1929 | class operator_rshift : public cross_product_operator |
1930 | { | |
1931 | public: | |
1932 | virtual bool fold_range (irange &r, tree type, | |
1933 | const irange &op1, | |
80dd13f5 AM |
1934 | const irange &op2, |
1935 | relation_kind rel = VREL_NONE) const; | |
bd431d26 AH |
1936 | virtual void wi_fold (irange &r, tree type, |
1937 | const wide_int &lh_lb, | |
1938 | const wide_int &lh_ub, | |
1939 | const wide_int &rh_lb, | |
1940 | const wide_int &rh_ub) const; | |
1941 | virtual bool wi_op_overflows (wide_int &res, | |
1942 | tree type, | |
1943 | const wide_int &w0, | |
1944 | const wide_int &w1) const; | |
1945 | virtual bool op1_range (irange &, tree type, | |
1946 | const irange &lhs, | |
80dd13f5 AM |
1947 | const irange &op2, |
1948 | relation_kind rel = VREL_NONE) const; | |
bd431d26 AH |
1949 | } op_rshift; |
1950 | ||
1951 | ||
f674b4a7 | 1952 | bool |
4ba9fb0a AH |
1953 | operator_lshift::fold_range (irange &r, tree type, |
1954 | const irange &op1, | |
80dd13f5 | 1955 | const irange &op2, |
3cb72ac1 | 1956 | relation_kind rel) const |
38a73435 | 1957 | { |
d0d8b5d8 AM |
1958 | int_range_max shift_range; |
1959 | if (!get_shift_range (shift_range, type, op2)) | |
1960 | { | |
1961 | if (op2.undefined_p ()) | |
1962 | r.set_undefined (); | |
1963 | else | |
1964 | r.set_varying (type); | |
1965 | return true; | |
1966 | } | |
38a73435 AH |
1967 | |
1968 | // Transform left shifts by constants into multiplies. | |
d0d8b5d8 | 1969 | if (shift_range.singleton_p ()) |
38a73435 | 1970 | { |
d0d8b5d8 | 1971 | unsigned shift = shift_range.lower_bound ().to_uhwi (); |
38a73435 | 1972 | wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type)); |
4ba9fb0a | 1973 | int_range<1> mult (type, tmp, tmp); |
38a73435 AH |
1974 | |
1975 | // Force wrapping multiplication. | |
1976 | bool saved_flag_wrapv = flag_wrapv; | |
1977 | bool saved_flag_wrapv_pointer = flag_wrapv_pointer; | |
1978 | flag_wrapv = 1; | |
1979 | flag_wrapv_pointer = 1; | |
4ba9fb0a | 1980 | bool b = op_mult.fold_range (r, type, op1, mult); |
38a73435 AH |
1981 | flag_wrapv = saved_flag_wrapv; |
1982 | flag_wrapv_pointer = saved_flag_wrapv_pointer; | |
f674b4a7 | 1983 | return b; |
38a73435 | 1984 | } |
f674b4a7 AM |
1985 | else |
1986 | // Otherwise, invoke the generic fold routine. | |
3cb72ac1 | 1987 | return range_operator::fold_range (r, type, op1, shift_range, rel); |
38a73435 AH |
1988 | } |
1989 | ||
bb74ef9e | 1990 | void |
4ba9fb0a | 1991 | operator_lshift::wi_fold (irange &r, tree type, |
38a73435 AH |
1992 | const wide_int &lh_lb, const wide_int &lh_ub, |
1993 | const wide_int &rh_lb, const wide_int &rh_ub) const | |
1994 | { | |
1995 | signop sign = TYPE_SIGN (type); | |
1996 | unsigned prec = TYPE_PRECISION (type); | |
1997 | int overflow_pos = sign == SIGNED ? prec - 1 : prec; | |
1998 | int bound_shift = overflow_pos - rh_ub.to_shwi (); | |
1999 | // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can | |
2000 | // overflow. However, for that to happen, rh.max needs to be zero, | |
704e8a82 AM |
2001 | // which means rh is a singleton range of zero, which means we simply return |
2002 | // [lh_lb, lh_ub] as the range. | |
2003 | if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0)) | |
2004 | { | |
2005 | r = int_range<2> (type, lh_lb, lh_ub); | |
2006 | return; | |
2007 | } | |
2008 | ||
38a73435 AH |
2009 | wide_int bound = wi::set_bit_in_zero (bound_shift, prec); |
2010 | wide_int complement = ~(bound - 1); | |
2011 | wide_int low_bound, high_bound; | |
2012 | bool in_bounds = false; | |
2013 | ||
2014 | if (sign == UNSIGNED) | |
2015 | { | |
2016 | low_bound = bound; | |
2017 | high_bound = complement; | |
2018 | if (wi::ltu_p (lh_ub, low_bound)) | |
2019 | { | |
2020 | // [5, 6] << [1, 2] == [10, 24]. | |
2021 | // We're shifting out only zeroes, the value increases | |
2022 | // monotonically. | |
2023 | in_bounds = true; | |
2024 | } | |
2025 | else if (wi::ltu_p (high_bound, lh_lb)) | |
2026 | { | |
2027 | // [0xffffff00, 0xffffffff] << [1, 2] | |
2028 | // == [0xfffffc00, 0xfffffffe]. | |
2029 | // We're shifting out only ones, the value decreases | |
2030 | // monotonically. | |
2031 | in_bounds = true; | |
2032 | } | |
2033 | } | |
2034 | else | |
2035 | { | |
2036 | // [-1, 1] << [1, 2] == [-4, 4] | |
2037 | low_bound = complement; | |
2038 | high_bound = bound; | |
2039 | if (wi::lts_p (lh_ub, high_bound) | |
2040 | && wi::lts_p (low_bound, lh_lb)) | |
2041 | { | |
2042 | // For non-negative numbers, we're shifting out only zeroes, | |
2043 | // the value increases monotonically. For negative numbers, | |
2044 | // we're shifting out only ones, the value decreases | |
2045 | // monotonically. | |
2046 | in_bounds = true; | |
2047 | } | |
2048 | } | |
2049 | ||
2050 | if (in_bounds) | |
bb74ef9e AM |
2051 | wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub); |
2052 | else | |
4ba9fb0a | 2053 | r.set_varying (type); |
38a73435 AH |
2054 | } |
2055 | ||
2056 | bool | |
028d81b1 AH |
2057 | operator_lshift::wi_op_overflows (wide_int &res, tree type, |
2058 | const wide_int &w0, const wide_int &w1) const | |
38a73435 AH |
2059 | { |
2060 | signop sign = TYPE_SIGN (type); | |
2061 | if (wi::neg_p (w1)) | |
2062 | { | |
2063 | // It's unclear from the C standard whether shifts can overflow. | |
2064 | // The following code ignores overflow; perhaps a C standard | |
2065 | // interpretation ruling is needed. | |
2066 | res = wi::rshift (w0, -w1, sign); | |
2067 | } | |
2068 | else | |
2069 | res = wi::lshift (w0, w1); | |
2070 | return false; | |
2071 | } | |
2072 | ||
4ba9fb0a AH |
2073 | bool |
2074 | operator_lshift::op1_range (irange &r, | |
2075 | tree type, | |
2076 | const irange &lhs, | |
80dd13f5 AM |
2077 | const irange &op2, |
2078 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
2079 | { |
2080 | tree shift_amount; | |
2081 | if (op2.singleton_p (&shift_amount)) | |
2082 | { | |
bd431d26 | 2083 | wide_int shift = wi::to_wide (shift_amount); |
4a135bd9 AM |
2084 | if (wi::lt_p (shift, 0, SIGNED)) |
2085 | return false; | |
2d2f4ffc AH |
2086 | if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type), |
2087 | TYPE_PRECISION (op2.type ())), | |
2088 | UNSIGNED)) | |
2089 | return false; | |
5b80069c AH |
2090 | if (shift == 0) |
2091 | { | |
2092 | r = lhs; | |
2093 | return true; | |
2094 | } | |
bd431d26 AH |
2095 | |
2096 | // Work completely in unsigned mode to start. | |
2097 | tree utype = type; | |
2098 | if (TYPE_SIGN (type) == SIGNED) | |
4ba9fb0a | 2099 | { |
bd431d26 AH |
2100 | int_range_max tmp = lhs; |
2101 | utype = unsigned_type_for (type); | |
2102 | range_cast (tmp, utype); | |
2103 | op_rshift.fold_range (r, utype, tmp, op2); | |
4ba9fb0a | 2104 | } |
bd431d26 AH |
2105 | else |
2106 | op_rshift.fold_range (r, utype, lhs, op2); | |
2107 | ||
2108 | // Start with ranges which can produce the LHS by right shifting the | |
2109 | // result by the shift amount. | |
2110 | // ie [0x08, 0xF0] = op1 << 2 will start with | |
2111 | // [00001000, 11110000] = op1 << 2 | |
2112 | // [0x02, 0x4C] aka [00000010, 00111100] | |
2113 | ||
2114 | // Then create a range from the LB with the least significant upper bit | |
2115 | // set, to the upper bound with all the bits set. | |
2116 | // This would be [0x42, 0xFC] aka [01000010, 11111100]. | |
2117 | ||
2118 | // Ideally we do this for each subrange, but just lump them all for now. | |
2119 | unsigned low_bits = TYPE_PRECISION (utype) | |
2120 | - TREE_INT_CST_LOW (shift_amount); | |
2121 | wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype)); | |
2122 | wide_int new_ub = wi::bit_or (up_mask, r.upper_bound ()); | |
2123 | wide_int new_lb = wi::set_bit (r.lower_bound (), low_bits); | |
2124 | int_range<2> fill_range (utype, new_lb, new_ub); | |
2125 | r.union_ (fill_range); | |
2126 | ||
2127 | if (utype != type) | |
2128 | range_cast (r, type); | |
4ba9fb0a AH |
2129 | return true; |
2130 | } | |
2131 | return false; | |
2132 | } | |
2133 | ||
4ba9fb0a AH |
2134 | bool |
2135 | operator_rshift::op1_range (irange &r, | |
2136 | tree type, | |
2137 | const irange &lhs, | |
80dd13f5 AM |
2138 | const irange &op2, |
2139 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
2140 | { |
2141 | tree shift; | |
2142 | if (op2.singleton_p (&shift)) | |
2143 | { | |
e1b4fbfe AH |
2144 | // Ignore nonsensical shifts. |
2145 | unsigned prec = TYPE_PRECISION (type); | |
2146 | if (wi::ge_p (wi::to_wide (shift), | |
2147 | wi::uhwi (prec, TYPE_PRECISION (TREE_TYPE (shift))), | |
2148 | UNSIGNED)) | |
2149 | return false; | |
f0c0f124 AH |
2150 | if (wi::to_wide (shift) == 0) |
2151 | { | |
2152 | r = lhs; | |
2153 | return true; | |
2154 | } | |
e1b4fbfe | 2155 | |
4ba9fb0a AH |
2156 | // Folding the original operation may discard some impossible |
2157 | // ranges from the LHS. | |
c5a6c223 | 2158 | int_range_max lhs_refined; |
4ba9fb0a AH |
2159 | op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2); |
2160 | lhs_refined.intersect (lhs); | |
2161 | if (lhs_refined.undefined_p ()) | |
2162 | { | |
2163 | r.set_undefined (); | |
2164 | return true; | |
2165 | } | |
c5a6c223 AH |
2166 | int_range_max shift_range (shift, shift); |
2167 | int_range_max lb, ub; | |
4ba9fb0a AH |
2168 | op_lshift.fold_range (lb, type, lhs_refined, shift_range); |
2169 | // LHS | |
2170 | // 0000 0111 = OP1 >> 3 | |
2171 | // | |
2172 | // OP1 is anything from 0011 1000 to 0011 1111. That is, a | |
2173 | // range from LHS<<3 plus a mask of the 3 bits we shifted on the | |
2174 | // right hand side (0x07). | |
2175 | tree mask = fold_build1 (BIT_NOT_EXPR, type, | |
2176 | fold_build2 (LSHIFT_EXPR, type, | |
2177 | build_minus_one_cst (type), | |
2178 | shift)); | |
c5a6c223 | 2179 | int_range_max mask_range (build_zero_cst (type), mask); |
4ba9fb0a AH |
2180 | op_plus.fold_range (ub, type, lb, mask_range); |
2181 | r = lb; | |
2182 | r.union_ (ub); | |
2183 | if (!lhs_refined.contains_p (build_zero_cst (type))) | |
2184 | { | |
2185 | mask_range.invert (); | |
2186 | r.intersect (mask_range); | |
2187 | } | |
2188 | return true; | |
2189 | } | |
2190 | return false; | |
2191 | } | |
2192 | ||
38a73435 AH |
2193 | bool |
2194 | operator_rshift::wi_op_overflows (wide_int &res, | |
2195 | tree type, | |
2196 | const wide_int &w0, | |
2197 | const wide_int &w1) const | |
2198 | { | |
2199 | signop sign = TYPE_SIGN (type); | |
2200 | if (wi::neg_p (w1)) | |
2201 | res = wi::lshift (w0, -w1); | |
2202 | else | |
2203 | { | |
2204 | // It's unclear from the C standard whether shifts can overflow. | |
2205 | // The following code ignores overflow; perhaps a C standard | |
2206 | // interpretation ruling is needed. | |
2207 | res = wi::rshift (w0, w1, sign); | |
2208 | } | |
2209 | return false; | |
2210 | } | |
2211 | ||
f674b4a7 | 2212 | bool |
4ba9fb0a AH |
2213 | operator_rshift::fold_range (irange &r, tree type, |
2214 | const irange &op1, | |
80dd13f5 | 2215 | const irange &op2, |
3cb72ac1 | 2216 | relation_kind rel) const |
38a73435 | 2217 | { |
d0d8b5d8 AM |
2218 | int_range_max shift; |
2219 | if (!get_shift_range (shift, type, op2)) | |
2220 | { | |
2221 | if (op2.undefined_p ()) | |
2222 | r.set_undefined (); | |
2223 | else | |
2224 | r.set_varying (type); | |
2225 | return true; | |
2226 | } | |
38a73435 | 2227 | |
3cb72ac1 | 2228 | return range_operator::fold_range (r, type, op1, shift, rel); |
38a73435 AH |
2229 | } |
2230 | ||
bb74ef9e | 2231 | void |
4ba9fb0a | 2232 | operator_rshift::wi_fold (irange &r, tree type, |
38a73435 AH |
2233 | const wide_int &lh_lb, const wide_int &lh_ub, |
2234 | const wide_int &rh_lb, const wide_int &rh_ub) const | |
2235 | { | |
bb74ef9e | 2236 | wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub); |
38a73435 AH |
2237 | } |
2238 | ||
2239 | ||
2240 | class operator_cast: public range_operator | |
2241 | { | |
2242 | public: | |
4ba9fb0a AH |
2243 | virtual bool fold_range (irange &r, tree type, |
2244 | const irange &op1, | |
80dd13f5 AM |
2245 | const irange &op2, |
2246 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
2247 | virtual bool op1_range (irange &r, tree type, |
2248 | const irange &lhs, | |
80dd13f5 AM |
2249 | const irange &op2, |
2250 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
2251 | private: |
2252 | bool truncating_cast_p (const irange &inner, const irange &outer) const; | |
2253 | bool inside_domain_p (const wide_int &min, const wide_int &max, | |
2254 | const irange &outer) const; | |
2255 | void fold_pair (irange &r, unsigned index, const irange &inner, | |
2256 | const irange &outer) const; | |
38a73435 AH |
2257 | } op_convert; |
2258 | ||
4ba9fb0a AH |
2259 | // Return TRUE if casting from INNER to OUTER is a truncating cast. |
2260 | ||
2261 | inline bool | |
2262 | operator_cast::truncating_cast_p (const irange &inner, | |
2263 | const irange &outer) const | |
2264 | { | |
2265 | return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ()); | |
2266 | } | |
2267 | ||
2268 | // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type. | |
2269 | ||
f674b4a7 | 2270 | bool |
4ba9fb0a AH |
2271 | operator_cast::inside_domain_p (const wide_int &min, |
2272 | const wide_int &max, | |
2273 | const irange &range) const | |
38a73435 | 2274 | { |
4ba9fb0a AH |
2275 | wide_int domain_min = wi::to_wide (vrp_val_min (range.type ())); |
2276 | wide_int domain_max = wi::to_wide (vrp_val_max (range.type ())); | |
2277 | signop domain_sign = TYPE_SIGN (range.type ()); | |
2278 | return (wi::le_p (min, domain_max, domain_sign) | |
2279 | && wi::le_p (max, domain_max, domain_sign) | |
2280 | && wi::ge_p (min, domain_min, domain_sign) | |
2281 | && wi::ge_p (max, domain_min, domain_sign)); | |
2282 | } | |
2283 | ||
2284 | ||
2285 | // Helper for fold_range which work on a pair at a time. | |
2286 | ||
2287 | void | |
2288 | operator_cast::fold_pair (irange &r, unsigned index, | |
2289 | const irange &inner, | |
2290 | const irange &outer) const | |
2291 | { | |
2292 | tree inner_type = inner.type (); | |
2293 | tree outer_type = outer.type (); | |
2294 | signop inner_sign = TYPE_SIGN (inner_type); | |
2295 | unsigned outer_prec = TYPE_PRECISION (outer_type); | |
2296 | ||
2297 | // check to see if casting from INNER to OUTER is a conversion that | |
2298 | // fits in the resulting OUTER type. | |
2299 | wide_int inner_lb = inner.lower_bound (index); | |
2300 | wide_int inner_ub = inner.upper_bound (index); | |
2301 | if (truncating_cast_p (inner, outer)) | |
2302 | { | |
2303 | // We may be able to accomodate a truncating cast if the | |
2304 | // resulting range can be represented in the target type... | |
2305 | if (wi::rshift (wi::sub (inner_ub, inner_lb), | |
2306 | wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())), | |
2307 | inner_sign) != 0) | |
38a73435 | 2308 | { |
4ba9fb0a AH |
2309 | r.set_varying (outer_type); |
2310 | return; | |
38a73435 | 2311 | } |
4ba9fb0a AH |
2312 | } |
2313 | // ...but we must still verify that the final range fits in the | |
2314 | // domain. This catches -fstrict-enum restrictions where the domain | |
2315 | // range is smaller than what fits in the underlying type. | |
2316 | wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign); | |
2317 | wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign); | |
2318 | if (inside_domain_p (min, max, outer)) | |
2319 | create_possibly_reversed_range (r, outer_type, min, max); | |
2320 | else | |
2321 | r.set_varying (outer_type); | |
2322 | } | |
2323 | ||
2324 | ||
2325 | bool | |
2326 | operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, | |
2327 | const irange &inner, | |
80dd13f5 AM |
2328 | const irange &outer, |
2329 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
2330 | { |
2331 | if (empty_range_varying (r, type, inner, outer)) | |
2332 | return true; | |
2333 | ||
2334 | gcc_checking_assert (outer.varying_p ()); | |
2335 | gcc_checking_assert (inner.num_pairs () > 0); | |
2336 | ||
2337 | // Avoid a temporary by folding the first pair directly into the result. | |
2338 | fold_pair (r, 0, inner, outer); | |
2339 | ||
2340 | // Then process any additonal pairs by unioning with their results. | |
2341 | for (unsigned x = 1; x < inner.num_pairs (); ++x) | |
2342 | { | |
c5a6c223 | 2343 | int_range_max tmp; |
4ba9fb0a AH |
2344 | fold_pair (tmp, x, inner, outer); |
2345 | r.union_ (tmp); | |
2346 | if (r.varying_p ()) | |
2347 | return true; | |
38a73435 | 2348 | } |
f674b4a7 | 2349 | return true; |
38a73435 AH |
2350 | } |
2351 | ||
2352 | bool | |
4ba9fb0a AH |
2353 | operator_cast::op1_range (irange &r, tree type, |
2354 | const irange &lhs, | |
80dd13f5 AM |
2355 | const irange &op2, |
2356 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
2357 | { |
2358 | tree lhs_type = lhs.type (); | |
2359 | gcc_checking_assert (types_compatible_p (op2.type(), type)); | |
2360 | ||
c25b5046 AM |
2361 | // If we are calculating a pointer, shortcut to what we really care about. |
2362 | if (POINTER_TYPE_P (type)) | |
2363 | { | |
2364 | // Conversion from other pointers or a constant (including 0/NULL) | |
2365 | // are straightforward. | |
2366 | if (POINTER_TYPE_P (lhs.type ()) | |
2367 | || (lhs.singleton_p () | |
2368 | && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type))) | |
2369 | { | |
2370 | r = lhs; | |
2371 | range_cast (r, type); | |
2372 | } | |
2373 | else | |
2374 | { | |
2375 | // If the LHS is not a pointer nor a singleton, then it is | |
2376 | // either VARYING or non-zero. | |
2377 | if (!lhs.contains_p (build_zero_cst (lhs.type ()))) | |
2378 | r.set_nonzero (type); | |
2379 | else | |
2380 | r.set_varying (type); | |
2381 | } | |
2382 | r.intersect (op2); | |
2383 | return true; | |
2384 | } | |
2385 | ||
4ba9fb0a AH |
2386 | if (truncating_cast_p (op2, lhs)) |
2387 | { | |
2388 | if (lhs.varying_p ()) | |
2389 | r.set_varying (type); | |
2390 | else | |
38a73435 | 2391 | { |
4ba9fb0a AH |
2392 | // We want to insert the LHS as an unsigned value since it |
2393 | // would not trigger the signed bit of the larger type. | |
c5a6c223 | 2394 | int_range_max converted_lhs = lhs; |
4ba9fb0a AH |
2395 | range_cast (converted_lhs, unsigned_type_for (lhs_type)); |
2396 | range_cast (converted_lhs, type); | |
2397 | // Start by building the positive signed outer range for the type. | |
2398 | wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type), | |
2399 | TYPE_PRECISION (type)); | |
2400 | r = int_range<1> (type, lim, wi::max_value (TYPE_PRECISION (type), | |
2401 | SIGNED)); | |
2402 | // For the signed part, we need to simply union the 2 ranges now. | |
2403 | r.union_ (converted_lhs); | |
2404 | ||
2405 | // Create maximal negative number outside of LHS bits. | |
2406 | lim = wi::mask (TYPE_PRECISION (lhs_type), true, | |
2407 | TYPE_PRECISION (type)); | |
2408 | // Add this to the unsigned LHS range(s). | |
c5a6c223 AH |
2409 | int_range_max lim_range (type, lim, lim); |
2410 | int_range_max lhs_neg; | |
4ba9fb0a AH |
2411 | range_op_handler (PLUS_EXPR, type)->fold_range (lhs_neg, |
2412 | type, | |
2413 | converted_lhs, | |
2414 | lim_range); | |
1cde5d85 AM |
2415 | // lhs_neg now has all the negative versions of the LHS. |
2416 | // Now union in all the values from SIGNED MIN (0x80000) to | |
2417 | // lim-1 in order to fill in all the ranges with the upper | |
2418 | // bits set. | |
2419 | ||
2420 | // PR 97317. If the lhs has only 1 bit less precision than the rhs, | |
2421 | // we don't need to create a range from min to lim-1 | |
2422 | // calculate neg range traps trying to create [lim, lim - 1]. | |
2423 | wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED); | |
2424 | if (lim != min_val) | |
2425 | { | |
2426 | int_range_max neg (type, | |
2427 | wi::min_value (TYPE_PRECISION (type), | |
2428 | SIGNED), | |
2429 | lim - 1); | |
2430 | lhs_neg.union_ (neg); | |
2431 | } | |
4ba9fb0a | 2432 | // And finally, munge the signed and unsigned portions. |
1cde5d85 | 2433 | r.union_ (lhs_neg); |
38a73435 | 2434 | } |
4ba9fb0a AH |
2435 | // And intersect with any known value passed in the extra operand. |
2436 | r.intersect (op2); | |
38a73435 AH |
2437 | return true; |
2438 | } | |
2439 | ||
c5a6c223 | 2440 | int_range_max tmp; |
4ba9fb0a AH |
2441 | if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type)) |
2442 | tmp = lhs; | |
2443 | else | |
38a73435 | 2444 | { |
4ba9fb0a AH |
2445 | // The cast is not truncating, and the range is restricted to |
2446 | // the range of the RHS by this assignment. | |
2447 | // | |
38a73435 | 2448 | // Cast the range of the RHS to the type of the LHS. |
4ba9fb0a AH |
2449 | fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type)); |
2450 | // Intersect this with the LHS range will produce the range, | |
2451 | // which will be cast to the RHS type before returning. | |
bb74ef9e | 2452 | tmp.intersect (lhs); |
38a73435 | 2453 | } |
38a73435 AH |
2454 | |
2455 | // Cast the calculated range to the type of the RHS. | |
4ba9fb0a | 2456 | fold_range (r, type, tmp, int_range<1> (type)); |
38a73435 AH |
2457 | return true; |
2458 | } | |
2459 | ||
2460 | ||
2461 | class operator_logical_and : public range_operator | |
2462 | { | |
2463 | public: | |
4ba9fb0a AH |
2464 | virtual bool fold_range (irange &r, tree type, |
2465 | const irange &lh, | |
80dd13f5 AM |
2466 | const irange &rh, |
2467 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
2468 | virtual bool op1_range (irange &r, tree type, |
2469 | const irange &lhs, | |
80dd13f5 AM |
2470 | const irange &op2, |
2471 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
2472 | virtual bool op2_range (irange &r, tree type, |
2473 | const irange &lhs, | |
80dd13f5 AM |
2474 | const irange &op1, |
2475 | relation_kind rel = VREL_NONE) const; | |
38a73435 AH |
2476 | } op_logical_and; |
2477 | ||
2478 | ||
f674b4a7 | 2479 | bool |
4ba9fb0a AH |
2480 | operator_logical_and::fold_range (irange &r, tree type, |
2481 | const irange &lh, | |
80dd13f5 AM |
2482 | const irange &rh, |
2483 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 2484 | { |
4ba9fb0a | 2485 | if (empty_range_varying (r, type, lh, rh)) |
f674b4a7 | 2486 | return true; |
38a73435 AH |
2487 | |
2488 | // 0 && anything is 0. | |
2489 | if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0)) | |
2490 | || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0))) | |
bb74ef9e AM |
2491 | r = range_false (type); |
2492 | else if (lh.contains_p (build_zero_cst (lh.type ())) | |
2493 | || rh.contains_p (build_zero_cst (rh.type ()))) | |
2494 | // To reach this point, there must be a logical 1 on each side, and | |
2495 | // the only remaining question is whether there is a zero or not. | |
2496 | r = range_true_and_false (type); | |
2497 | else | |
2498 | r = range_true (type); | |
f674b4a7 | 2499 | return true; |
38a73435 AH |
2500 | } |
2501 | ||
2502 | bool | |
4ba9fb0a AH |
2503 | operator_logical_and::op1_range (irange &r, tree type, |
2504 | const irange &lhs, | |
80dd13f5 AM |
2505 | const irange &op2 ATTRIBUTE_UNUSED, |
2506 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
2507 | { |
2508 | switch (get_bool_state (r, lhs, type)) | |
2509 | { | |
2510 | case BRS_TRUE: | |
2511 | // A true result means both sides of the AND must be true. | |
2512 | r = range_true (type); | |
2513 | break; | |
2514 | default: | |
2515 | // Any other result means only one side has to be false, the | |
2516 | // other side can be anything. So we cannott be sure of any | |
2517 | // result here. | |
2518 | r = range_true_and_false (type); | |
2519 | break; | |
2520 | } | |
2521 | return true; | |
2522 | } | |
2523 | ||
2524 | bool | |
4ba9fb0a AH |
2525 | operator_logical_and::op2_range (irange &r, tree type, |
2526 | const irange &lhs, | |
80dd13f5 AM |
2527 | const irange &op1, |
2528 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
2529 | { |
2530 | return operator_logical_and::op1_range (r, type, lhs, op1); | |
2531 | } | |
2532 | ||
2533 | ||
2534 | class operator_bitwise_and : public range_operator | |
2535 | { | |
2536 | public: | |
4ba9fb0a AH |
2537 | virtual bool fold_range (irange &r, tree type, |
2538 | const irange &lh, | |
80dd13f5 AM |
2539 | const irange &rh, |
2540 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
2541 | virtual bool op1_range (irange &r, tree type, |
2542 | const irange &lhs, | |
80dd13f5 AM |
2543 | const irange &op2, |
2544 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
2545 | virtual bool op2_range (irange &r, tree type, |
2546 | const irange &lhs, | |
80dd13f5 AM |
2547 | const irange &op1, |
2548 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a | 2549 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
2550 | const wide_int &lh_lb, |
2551 | const wide_int &lh_ub, | |
2552 | const wide_int &rh_lb, | |
2553 | const wide_int &rh_ub) const; | |
4ba9fb0a AH |
2554 | private: |
2555 | void simple_op1_range_solver (irange &r, tree type, | |
2556 | const irange &lhs, | |
2557 | const irange &op2) const; | |
2558 | void remove_impossible_ranges (irange &r, const irange &rh) const; | |
38a73435 AH |
2559 | } op_bitwise_and; |
2560 | ||
4ba9fb0a AH |
2561 | static bool |
2562 | unsigned_singleton_p (const irange &op) | |
2563 | { | |
2564 | tree mask; | |
2565 | if (op.singleton_p (&mask)) | |
2566 | { | |
2567 | wide_int x = wi::to_wide (mask); | |
2568 | return wi::ge_p (x, 0, TYPE_SIGN (op.type ())); | |
2569 | } | |
2570 | return false; | |
2571 | } | |
2572 | ||
2573 | // Remove any ranges from R that are known to be impossible when an | |
2574 | // range is ANDed with MASK. | |
2575 | ||
2576 | void | |
2577 | operator_bitwise_and::remove_impossible_ranges (irange &r, | |
2578 | const irange &rmask) const | |
2579 | { | |
2580 | if (r.undefined_p () || !unsigned_singleton_p (rmask)) | |
2581 | return; | |
2582 | ||
2583 | wide_int mask = rmask.lower_bound (); | |
2584 | tree type = r.type (); | |
2585 | int prec = TYPE_PRECISION (type); | |
2586 | int leading_zeros = wi::clz (mask); | |
c5a6c223 | 2587 | int_range_max impossible_ranges; |
4ba9fb0a AH |
2588 | |
2589 | /* We know that starting at the most significant bit, any 0 in the | |
2590 | mask means the resulting range cannot contain a 1 in that same | |
2591 | position. This means the following ranges are impossible: | |
2592 | ||
2593 | x & 0b1001 1010 | |
2594 | IMPOSSIBLE RANGES | |
2595 | 01xx xxxx [0100 0000, 0111 1111] | |
2596 | 001x xxxx [0010 0000, 0011 1111] | |
2597 | 0000 01xx [0000 0100, 0000 0111] | |
2598 | 0000 0001 [0000 0001, 0000 0001] | |
2599 | */ | |
2600 | wide_int one = wi::one (prec); | |
2601 | for (int i = 0; i < prec - leading_zeros - 1; ++i) | |
2602 | if (wi::bit_and (mask, wi::lshift (one, wi::uhwi (i, prec))) == 0) | |
2603 | { | |
2604 | tree lb = fold_build2 (LSHIFT_EXPR, type, | |
2605 | build_one_cst (type), | |
2606 | build_int_cst (type, i)); | |
2607 | tree ub_left = fold_build1 (BIT_NOT_EXPR, type, | |
2608 | fold_build2 (LSHIFT_EXPR, type, | |
2609 | build_minus_one_cst (type), | |
2610 | build_int_cst (type, i))); | |
2611 | tree ub_right = fold_build2 (LSHIFT_EXPR, type, | |
2612 | build_one_cst (type), | |
2613 | build_int_cst (type, i)); | |
2614 | tree ub = fold_build2 (BIT_IOR_EXPR, type, ub_left, ub_right); | |
2615 | impossible_ranges.union_ (int_range<1> (lb, ub)); | |
2616 | } | |
2617 | if (!impossible_ranges.undefined_p ()) | |
2618 | { | |
2619 | impossible_ranges.invert (); | |
2620 | r.intersect (impossible_ranges); | |
2621 | } | |
2622 | } | |
2623 | ||
2624 | bool | |
2625 | operator_bitwise_and::fold_range (irange &r, tree type, | |
2626 | const irange &lh, | |
80dd13f5 AM |
2627 | const irange &rh, |
2628 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
2629 | { |
2630 | if (range_operator::fold_range (r, type, lh, rh)) | |
2631 | { | |
2632 | // FIXME: This is temporarily disabled because, though it | |
2633 | // generates better ranges, it's noticeably slower for evrp. | |
2634 | // remove_impossible_ranges (r, rh); | |
2635 | return true; | |
2636 | } | |
2637 | return false; | |
2638 | } | |
2639 | ||
2640 | ||
38a73435 AH |
2641 | // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if |
2642 | // possible. Basically, see if we can optimize: | |
2643 | // | |
2644 | // [LB, UB] op Z | |
2645 | // into: | |
2646 | // [LB op Z, UB op Z] | |
2647 | // | |
2648 | // If the optimization was successful, accumulate the range in R and | |
2649 | // return TRUE. | |
2650 | ||
2651 | static bool | |
4ba9fb0a | 2652 | wi_optimize_and_or (irange &r, |
38a73435 AH |
2653 | enum tree_code code, |
2654 | tree type, | |
2655 | const wide_int &lh_lb, const wide_int &lh_ub, | |
2656 | const wide_int &rh_lb, const wide_int &rh_ub) | |
2657 | { | |
2658 | // Calculate the singleton mask among the ranges, if any. | |
2659 | wide_int lower_bound, upper_bound, mask; | |
2660 | if (wi::eq_p (rh_lb, rh_ub)) | |
2661 | { | |
2662 | mask = rh_lb; | |
2663 | lower_bound = lh_lb; | |
2664 | upper_bound = lh_ub; | |
2665 | } | |
2666 | else if (wi::eq_p (lh_lb, lh_ub)) | |
2667 | { | |
2668 | mask = lh_lb; | |
2669 | lower_bound = rh_lb; | |
2670 | upper_bound = rh_ub; | |
2671 | } | |
2672 | else | |
2673 | return false; | |
2674 | ||
2675 | // If Z is a constant which (for op | its bitwise not) has n | |
2676 | // consecutive least significant bits cleared followed by m 1 | |
2677 | // consecutive bits set immediately above it and either | |
2678 | // m + n == precision, or (x >> (m + n)) == (y >> (m + n)). | |
2679 | // | |
2680 | // The least significant n bits of all the values in the range are | |
2681 | // cleared or set, the m bits above it are preserved and any bits | |
2682 | // above these are required to be the same for all values in the | |
2683 | // range. | |
2684 | wide_int w = mask; | |
2685 | int m = 0, n = 0; | |
2686 | if (code == BIT_IOR_EXPR) | |
2687 | w = ~w; | |
2688 | if (wi::eq_p (w, 0)) | |
2689 | n = w.get_precision (); | |
2690 | else | |
2691 | { | |
2692 | n = wi::ctz (w); | |
2693 | w = ~(w | wi::mask (n, false, w.get_precision ())); | |
2694 | if (wi::eq_p (w, 0)) | |
2695 | m = w.get_precision () - n; | |
2696 | else | |
2697 | m = wi::ctz (w) - n; | |
2698 | } | |
2699 | wide_int new_mask = wi::mask (m + n, true, w.get_precision ()); | |
2700 | if ((new_mask & lower_bound) != (new_mask & upper_bound)) | |
2701 | return false; | |
2702 | ||
2703 | wide_int res_lb, res_ub; | |
2704 | if (code == BIT_AND_EXPR) | |
2705 | { | |
2706 | res_lb = wi::bit_and (lower_bound, mask); | |
2707 | res_ub = wi::bit_and (upper_bound, mask); | |
2708 | } | |
2709 | else if (code == BIT_IOR_EXPR) | |
2710 | { | |
2711 | res_lb = wi::bit_or (lower_bound, mask); | |
2712 | res_ub = wi::bit_or (upper_bound, mask); | |
2713 | } | |
2714 | else | |
2715 | gcc_unreachable (); | |
bb74ef9e | 2716 | value_range_with_overflow (r, type, res_lb, res_ub); |
a5f9c27b AM |
2717 | |
2718 | // Furthermore, if the mask is non-zero, an IOR cannot contain zero. | |
2719 | if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0)) | |
2720 | { | |
2721 | int_range<2> tmp; | |
2722 | tmp.set_nonzero (type); | |
2723 | r.intersect (tmp); | |
2724 | } | |
38a73435 AH |
2725 | return true; |
2726 | } | |
2727 | ||
2728 | // For range [LB, UB] compute two wide_int bit masks. | |
2729 | // | |
2730 | // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that | |
2731 | // for all numbers in the range the bit is 0, otherwise it might be 0 | |
2732 | // or 1. | |
2733 | // | |
2734 | // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that | |
2735 | // for all numbers in the range the bit is 1, otherwise it might be 0 | |
2736 | // or 1. | |
2737 | ||
8f119c55 | 2738 | void |
38a73435 AH |
2739 | wi_set_zero_nonzero_bits (tree type, |
2740 | const wide_int &lb, const wide_int &ub, | |
2741 | wide_int &maybe_nonzero, | |
2742 | wide_int &mustbe_nonzero) | |
2743 | { | |
2744 | signop sign = TYPE_SIGN (type); | |
2745 | ||
2746 | if (wi::eq_p (lb, ub)) | |
2747 | maybe_nonzero = mustbe_nonzero = lb; | |
2748 | else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign)) | |
2749 | { | |
2750 | wide_int xor_mask = lb ^ ub; | |
2751 | maybe_nonzero = lb | ub; | |
2752 | mustbe_nonzero = lb & ub; | |
2753 | if (xor_mask != 0) | |
2754 | { | |
2755 | wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false, | |
2756 | maybe_nonzero.get_precision ()); | |
2757 | maybe_nonzero = maybe_nonzero | mask; | |
2758 | mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask); | |
2759 | } | |
2760 | } | |
2761 | else | |
2762 | { | |
2763 | maybe_nonzero = wi::minus_one (lb.get_precision ()); | |
2764 | mustbe_nonzero = wi::zero (lb.get_precision ()); | |
2765 | } | |
2766 | } | |
2767 | ||
bb74ef9e | 2768 | void |
4ba9fb0a | 2769 | operator_bitwise_and::wi_fold (irange &r, tree type, |
38a73435 AH |
2770 | const wide_int &lh_lb, |
2771 | const wide_int &lh_ub, | |
2772 | const wide_int &rh_lb, | |
2773 | const wide_int &rh_ub) const | |
2774 | { | |
38a73435 | 2775 | if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub)) |
bb74ef9e | 2776 | return; |
38a73435 AH |
2777 | |
2778 | wide_int maybe_nonzero_lh, mustbe_nonzero_lh; | |
2779 | wide_int maybe_nonzero_rh, mustbe_nonzero_rh; | |
2780 | wi_set_zero_nonzero_bits (type, lh_lb, lh_ub, | |
2781 | maybe_nonzero_lh, mustbe_nonzero_lh); | |
2782 | wi_set_zero_nonzero_bits (type, rh_lb, rh_ub, | |
2783 | maybe_nonzero_rh, mustbe_nonzero_rh); | |
2784 | ||
2785 | wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh; | |
2786 | wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh; | |
2787 | signop sign = TYPE_SIGN (type); | |
2788 | unsigned prec = TYPE_PRECISION (type); | |
2789 | // If both input ranges contain only negative values, we can | |
2790 | // truncate the result range maximum to the minimum of the | |
2791 | // input range maxima. | |
2792 | if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign)) | |
2793 | { | |
2794 | new_ub = wi::min (new_ub, lh_ub, sign); | |
2795 | new_ub = wi::min (new_ub, rh_ub, sign); | |
2796 | } | |
2797 | // If either input range contains only non-negative values | |
2798 | // we can truncate the result range maximum to the respective | |
2799 | // maximum of the input range. | |
2800 | if (wi::ge_p (lh_lb, 0, sign)) | |
2801 | new_ub = wi::min (new_ub, lh_ub, sign); | |
2802 | if (wi::ge_p (rh_lb, 0, sign)) | |
2803 | new_ub = wi::min (new_ub, rh_ub, sign); | |
2804 | // PR68217: In case of signed & sign-bit-CST should | |
2805 | // result in [-INF, 0] instead of [-INF, INF]. | |
2806 | if (wi::gt_p (new_lb, new_ub, sign)) | |
2807 | { | |
2808 | wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec); | |
2809 | if (sign == SIGNED | |
2810 | && ((wi::eq_p (lh_lb, lh_ub) | |
2811 | && !wi::cmps (lh_lb, sign_bit)) | |
2812 | || (wi::eq_p (rh_lb, rh_ub) | |
2813 | && !wi::cmps (rh_lb, sign_bit)))) | |
2814 | { | |
2815 | new_lb = wi::min_value (prec, sign); | |
2816 | new_ub = wi::zero (prec); | |
2817 | } | |
2818 | } | |
2819 | // If the limits got swapped around, return varying. | |
2820 | if (wi::gt_p (new_lb, new_ub,sign)) | |
4ba9fb0a | 2821 | r.set_varying (type); |
bb74ef9e AM |
2822 | else |
2823 | value_range_with_overflow (r, type, new_lb, new_ub); | |
38a73435 AH |
2824 | } |
2825 | ||
4ba9fb0a AH |
2826 | static void |
2827 | set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs) | |
2828 | { | |
2829 | if (!lhs.contains_p (build_zero_cst (type))) | |
2830 | r = range_nonzero (type); | |
2831 | else | |
2832 | r.set_varying (type); | |
2833 | } | |
2834 | ||
2835 | // This was shamelessly stolen from register_edge_assert_for_2 and | |
2836 | // adjusted to work with iranges. | |
2837 | ||
2838 | void | |
2839 | operator_bitwise_and::simple_op1_range_solver (irange &r, tree type, | |
2840 | const irange &lhs, | |
2841 | const irange &op2) const | |
2842 | { | |
2843 | if (!op2.singleton_p ()) | |
2844 | { | |
2845 | set_nonzero_range_from_mask (r, type, lhs); | |
2846 | return; | |
2847 | } | |
2848 | unsigned int nprec = TYPE_PRECISION (type); | |
2849 | wide_int cst2v = op2.lower_bound (); | |
2850 | bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type)); | |
2851 | wide_int sgnbit; | |
2852 | if (cst2n) | |
2853 | sgnbit = wi::set_bit_in_zero (nprec - 1, nprec); | |
2854 | else | |
2855 | sgnbit = wi::zero (nprec); | |
2856 | ||
2857 | // Solve [lhs.lower_bound (), +INF] = x & MASK. | |
2858 | // | |
2859 | // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and | |
2860 | // maximum unsigned value is ~0. For signed comparison, if CST2 | |
2861 | // doesn't have the most significant bit set, handle it similarly. If | |
2862 | // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2. | |
2863 | wide_int valv = lhs.lower_bound (); | |
2864 | wide_int minv = valv & cst2v, maxv; | |
2865 | bool we_know_nothing = false; | |
2866 | if (minv != valv) | |
2867 | { | |
2868 | // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL. | |
2869 | minv = masked_increment (valv, cst2v, sgnbit, nprec); | |
2870 | if (minv == valv) | |
2871 | { | |
2872 | // If we can't determine anything on this bound, fall | |
2873 | // through and conservatively solve for the other end point. | |
2874 | we_know_nothing = true; | |
2875 | } | |
2876 | } | |
2877 | maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec); | |
2878 | if (we_know_nothing) | |
2879 | r.set_varying (type); | |
2880 | else | |
2881 | r = int_range<1> (type, minv, maxv); | |
2882 | ||
2883 | // Solve [-INF, lhs.upper_bound ()] = x & MASK. | |
2884 | // | |
2885 | // Minimum unsigned value for <= is 0 and maximum unsigned value is | |
2886 | // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest | |
2887 | // VAL2 where | |
2888 | // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2 | |
2889 | // as maximum. | |
2890 | // For signed comparison, if CST2 doesn't have most significant bit | |
2891 | // set, handle it similarly. If CST2 has MSB set, the maximum is | |
2892 | // the same and minimum is INT_MIN. | |
2893 | valv = lhs.upper_bound (); | |
2894 | minv = valv & cst2v; | |
2895 | if (minv == valv) | |
2896 | maxv = valv; | |
2897 | else | |
2898 | { | |
2899 | maxv = masked_increment (valv, cst2v, sgnbit, nprec); | |
2900 | if (maxv == valv) | |
2901 | { | |
2902 | // If we couldn't determine anything on either bound, return | |
2903 | // undefined. | |
2904 | if (we_know_nothing) | |
2905 | r.set_undefined (); | |
2906 | return; | |
2907 | } | |
2908 | maxv -= 1; | |
2909 | } | |
2910 | maxv |= ~cst2v; | |
2911 | minv = sgnbit; | |
2912 | int_range<1> upper_bits (type, minv, maxv); | |
2913 | r.intersect (upper_bits); | |
2914 | } | |
2915 | ||
38a73435 | 2916 | bool |
4ba9fb0a AH |
2917 | operator_bitwise_and::op1_range (irange &r, tree type, |
2918 | const irange &lhs, | |
80dd13f5 AM |
2919 | const irange &op2, |
2920 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 2921 | { |
38a73435 AH |
2922 | if (types_compatible_p (type, boolean_type_node)) |
2923 | return op_logical_and.op1_range (r, type, lhs, op2); | |
2924 | ||
4ba9fb0a AH |
2925 | r.set_undefined (); |
2926 | for (unsigned i = 0; i < lhs.num_pairs (); ++i) | |
2927 | { | |
c5a6c223 | 2928 | int_range_max chunk (lhs.type (), |
4ba9fb0a AH |
2929 | lhs.lower_bound (i), |
2930 | lhs.upper_bound (i)); | |
c5a6c223 | 2931 | int_range_max res; |
4ba9fb0a AH |
2932 | simple_op1_range_solver (res, type, chunk, op2); |
2933 | r.union_ (res); | |
2934 | } | |
2935 | if (r.undefined_p ()) | |
2936 | set_nonzero_range_from_mask (r, type, lhs); | |
38a73435 AH |
2937 | return true; |
2938 | } | |
2939 | ||
2940 | bool | |
4ba9fb0a AH |
2941 | operator_bitwise_and::op2_range (irange &r, tree type, |
2942 | const irange &lhs, | |
80dd13f5 AM |
2943 | const irange &op1, |
2944 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
2945 | { |
2946 | return operator_bitwise_and::op1_range (r, type, lhs, op1); | |
2947 | } | |
2948 | ||
2949 | ||
2950 | class operator_logical_or : public range_operator | |
2951 | { | |
2952 | public: | |
4ba9fb0a AH |
2953 | virtual bool fold_range (irange &r, tree type, |
2954 | const irange &lh, | |
80dd13f5 AM |
2955 | const irange &rh, |
2956 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
2957 | virtual bool op1_range (irange &r, tree type, |
2958 | const irange &lhs, | |
80dd13f5 AM |
2959 | const irange &op2, |
2960 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
2961 | virtual bool op2_range (irange &r, tree type, |
2962 | const irange &lhs, | |
80dd13f5 AM |
2963 | const irange &op1, |
2964 | relation_kind rel = VREL_NONE) const; | |
38a73435 AH |
2965 | } op_logical_or; |
2966 | ||
f674b4a7 | 2967 | bool |
4ba9fb0a AH |
2968 | operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, |
2969 | const irange &lh, | |
80dd13f5 AM |
2970 | const irange &rh, |
2971 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 2972 | { |
4ba9fb0a | 2973 | if (empty_range_varying (r, type, lh, rh)) |
f674b4a7 | 2974 | return true; |
38a73435 | 2975 | |
fae08a05 AH |
2976 | r = lh; |
2977 | r.union_ (rh); | |
f674b4a7 | 2978 | return true; |
38a73435 AH |
2979 | } |
2980 | ||
2981 | bool | |
4ba9fb0a AH |
2982 | operator_logical_or::op1_range (irange &r, tree type, |
2983 | const irange &lhs, | |
80dd13f5 AM |
2984 | const irange &op2 ATTRIBUTE_UNUSED, |
2985 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
2986 | { |
2987 | switch (get_bool_state (r, lhs, type)) | |
2988 | { | |
2989 | case BRS_FALSE: | |
2990 | // A false result means both sides of the OR must be false. | |
2991 | r = range_false (type); | |
2992 | break; | |
2993 | default: | |
2994 | // Any other result means only one side has to be true, the | |
2995 | // other side can be anything. so we can't be sure of any result | |
2996 | // here. | |
2997 | r = range_true_and_false (type); | |
2998 | break; | |
2999 | } | |
3000 | return true; | |
3001 | } | |
3002 | ||
3003 | bool | |
4ba9fb0a AH |
3004 | operator_logical_or::op2_range (irange &r, tree type, |
3005 | const irange &lhs, | |
80dd13f5 AM |
3006 | const irange &op1, |
3007 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
3008 | { |
3009 | return operator_logical_or::op1_range (r, type, lhs, op1); | |
3010 | } | |
3011 | ||
3012 | ||
3013 | class operator_bitwise_or : public range_operator | |
3014 | { | |
3015 | public: | |
4ba9fb0a AH |
3016 | virtual bool op1_range (irange &r, tree type, |
3017 | const irange &lhs, | |
80dd13f5 AM |
3018 | const irange &op2, |
3019 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
3020 | virtual bool op2_range (irange &r, tree type, |
3021 | const irange &lhs, | |
80dd13f5 AM |
3022 | const irange &op1, |
3023 | relation_kind rel= VREL_NONE) const; | |
4ba9fb0a | 3024 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
3025 | const wide_int &lh_lb, |
3026 | const wide_int &lh_ub, | |
3027 | const wide_int &rh_lb, | |
3028 | const wide_int &rh_ub) const; | |
38a73435 AH |
3029 | } op_bitwise_or; |
3030 | ||
bb74ef9e | 3031 | void |
4ba9fb0a | 3032 | operator_bitwise_or::wi_fold (irange &r, tree type, |
38a73435 AH |
3033 | const wide_int &lh_lb, |
3034 | const wide_int &lh_ub, | |
3035 | const wide_int &rh_lb, | |
3036 | const wide_int &rh_ub) const | |
3037 | { | |
38a73435 | 3038 | if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub)) |
bb74ef9e | 3039 | return; |
38a73435 AH |
3040 | |
3041 | wide_int maybe_nonzero_lh, mustbe_nonzero_lh; | |
3042 | wide_int maybe_nonzero_rh, mustbe_nonzero_rh; | |
3043 | wi_set_zero_nonzero_bits (type, lh_lb, lh_ub, | |
3044 | maybe_nonzero_lh, mustbe_nonzero_lh); | |
3045 | wi_set_zero_nonzero_bits (type, rh_lb, rh_ub, | |
3046 | maybe_nonzero_rh, mustbe_nonzero_rh); | |
3047 | wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh; | |
3048 | wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh; | |
3049 | signop sign = TYPE_SIGN (type); | |
3050 | // If the input ranges contain only positive values we can | |
3051 | // truncate the minimum of the result range to the maximum | |
3052 | // of the input range minima. | |
3053 | if (wi::ge_p (lh_lb, 0, sign) | |
3054 | && wi::ge_p (rh_lb, 0, sign)) | |
3055 | { | |
3056 | new_lb = wi::max (new_lb, lh_lb, sign); | |
3057 | new_lb = wi::max (new_lb, rh_lb, sign); | |
3058 | } | |
3059 | // If either input range contains only negative values | |
3060 | // we can truncate the minimum of the result range to the | |
3061 | // respective minimum range. | |
3062 | if (wi::lt_p (lh_ub, 0, sign)) | |
3063 | new_lb = wi::max (new_lb, lh_lb, sign); | |
3064 | if (wi::lt_p (rh_ub, 0, sign)) | |
3065 | new_lb = wi::max (new_lb, rh_lb, sign); | |
46027143 AH |
3066 | // If the limits got swapped around, return a conservative range. |
3067 | if (wi::gt_p (new_lb, new_ub, sign)) | |
3068 | { | |
3069 | // Make sure that nonzero|X is nonzero. | |
3070 | if (wi::gt_p (lh_lb, 0, sign) | |
3071 | || wi::gt_p (rh_lb, 0, sign) | |
3072 | || wi::lt_p (lh_ub, 0, sign) | |
3073 | || wi::lt_p (rh_ub, 0, sign)) | |
3074 | r.set_nonzero (type); | |
3075 | else | |
3076 | r.set_varying (type); | |
3077 | return; | |
3078 | } | |
3079 | value_range_with_overflow (r, type, new_lb, new_ub); | |
38a73435 AH |
3080 | } |
3081 | ||
3082 | bool | |
4ba9fb0a AH |
3083 | operator_bitwise_or::op1_range (irange &r, tree type, |
3084 | const irange &lhs, | |
80dd13f5 AM |
3085 | const irange &op2, |
3086 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
3087 | { |
3088 | // If this is really a logical wi_fold, call that. | |
3089 | if (types_compatible_p (type, boolean_type_node)) | |
3090 | return op_logical_or.op1_range (r, type, lhs, op2); | |
3091 | ||
4ba9fb0a AH |
3092 | if (lhs.zero_p ()) |
3093 | { | |
3094 | tree zero = build_zero_cst (type); | |
3095 | r = int_range<1> (zero, zero); | |
3096 | return true; | |
3097 | } | |
38a73435 AH |
3098 | r.set_varying (type); |
3099 | return true; | |
3100 | } | |
3101 | ||
3102 | bool | |
4ba9fb0a AH |
3103 | operator_bitwise_or::op2_range (irange &r, tree type, |
3104 | const irange &lhs, | |
80dd13f5 AM |
3105 | const irange &op1, |
3106 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
3107 | { |
3108 | return operator_bitwise_or::op1_range (r, type, lhs, op1); | |
3109 | } | |
3110 | ||
3111 | ||
3112 | class operator_bitwise_xor : public range_operator | |
3113 | { | |
3114 | public: | |
4ba9fb0a | 3115 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
3116 | const wide_int &lh_lb, |
3117 | const wide_int &lh_ub, | |
3118 | const wide_int &rh_lb, | |
3119 | const wide_int &rh_ub) const; | |
4ba9fb0a AH |
3120 | virtual bool op1_range (irange &r, tree type, |
3121 | const irange &lhs, | |
80dd13f5 AM |
3122 | const irange &op2, |
3123 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
3124 | virtual bool op2_range (irange &r, tree type, |
3125 | const irange &lhs, | |
80dd13f5 AM |
3126 | const irange &op1, |
3127 | relation_kind rel = VREL_NONE) const; | |
f384e2f5 AH |
3128 | virtual bool op1_op2_relation_effect (irange &lhs_range, |
3129 | tree type, | |
3130 | const irange &op1_range, | |
3131 | const irange &op2_range, | |
3132 | relation_kind rel) const; | |
38a73435 AH |
3133 | } op_bitwise_xor; |
3134 | ||
bb74ef9e | 3135 | void |
4ba9fb0a | 3136 | operator_bitwise_xor::wi_fold (irange &r, tree type, |
38a73435 AH |
3137 | const wide_int &lh_lb, |
3138 | const wide_int &lh_ub, | |
3139 | const wide_int &rh_lb, | |
3140 | const wide_int &rh_ub) const | |
3141 | { | |
3142 | signop sign = TYPE_SIGN (type); | |
3143 | wide_int maybe_nonzero_lh, mustbe_nonzero_lh; | |
3144 | wide_int maybe_nonzero_rh, mustbe_nonzero_rh; | |
3145 | wi_set_zero_nonzero_bits (type, lh_lb, lh_ub, | |
3146 | maybe_nonzero_lh, mustbe_nonzero_lh); | |
3147 | wi_set_zero_nonzero_bits (type, rh_lb, rh_ub, | |
3148 | maybe_nonzero_rh, mustbe_nonzero_rh); | |
3149 | ||
3150 | wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh) | |
3151 | | ~(maybe_nonzero_lh | maybe_nonzero_rh)); | |
3152 | wide_int result_one_bits | |
3153 | = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh) | |
3154 | | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh)); | |
3155 | wide_int new_ub = ~result_zero_bits; | |
3156 | wide_int new_lb = result_one_bits; | |
3157 | ||
3158 | // If the range has all positive or all negative values, the result | |
3159 | // is better than VARYING. | |
3160 | if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign)) | |
bb74ef9e AM |
3161 | value_range_with_overflow (r, type, new_lb, new_ub); |
3162 | else | |
4ba9fb0a AH |
3163 | r.set_varying (type); |
3164 | } | |
3165 | ||
f384e2f5 AH |
3166 | bool |
3167 | operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range, | |
3168 | tree type, | |
3169 | const irange &, | |
3170 | const irange &, | |
3171 | relation_kind rel) const | |
3172 | { | |
3173 | if (rel == VREL_NONE) | |
3174 | return false; | |
3175 | ||
3176 | int_range<2> rel_range; | |
3177 | ||
3178 | switch (rel) | |
3179 | { | |
3180 | case EQ_EXPR: | |
3181 | rel_range.set_zero (type); | |
3182 | break; | |
3183 | case NE_EXPR: | |
3184 | rel_range.set_nonzero (type); | |
3185 | break; | |
3186 | default: | |
3187 | return false; | |
3188 | } | |
3189 | ||
3190 | lhs_range.intersect (rel_range); | |
3191 | return true; | |
3192 | } | |
3193 | ||
4ba9fb0a AH |
3194 | bool |
3195 | operator_bitwise_xor::op1_range (irange &r, tree type, | |
3196 | const irange &lhs, | |
80dd13f5 AM |
3197 | const irange &op2, |
3198 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
3199 | { |
3200 | if (lhs.undefined_p () || lhs.varying_p ()) | |
3201 | { | |
3202 | r = lhs; | |
3203 | return true; | |
3204 | } | |
3205 | if (types_compatible_p (type, boolean_type_node)) | |
3206 | { | |
3207 | switch (get_bool_state (r, lhs, type)) | |
3208 | { | |
3209 | case BRS_TRUE: | |
3210 | if (op2.varying_p ()) | |
3211 | r.set_varying (type); | |
3212 | else if (op2.zero_p ()) | |
3213 | r = range_true (type); | |
3214 | else | |
3215 | r = range_false (type); | |
3216 | break; | |
3217 | case BRS_FALSE: | |
3218 | r = op2; | |
3219 | break; | |
3220 | default: | |
ead233e6 | 3221 | break; |
4ba9fb0a AH |
3222 | } |
3223 | return true; | |
3224 | } | |
3225 | r.set_varying (type); | |
3226 | return true; | |
38a73435 AH |
3227 | } |
3228 | ||
4ba9fb0a AH |
3229 | bool |
3230 | operator_bitwise_xor::op2_range (irange &r, tree type, | |
3231 | const irange &lhs, | |
80dd13f5 AM |
3232 | const irange &op1, |
3233 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
3234 | { |
3235 | return operator_bitwise_xor::op1_range (r, type, lhs, op1); | |
3236 | } | |
38a73435 AH |
3237 | |
3238 | class operator_trunc_mod : public range_operator | |
3239 | { | |
3240 | public: | |
4ba9fb0a | 3241 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
3242 | const wide_int &lh_lb, |
3243 | const wide_int &lh_ub, | |
3244 | const wide_int &rh_lb, | |
3245 | const wide_int &rh_ub) const; | |
1e27e7a5 AM |
3246 | virtual bool op1_range (irange &r, tree type, |
3247 | const irange &lhs, | |
80dd13f5 AM |
3248 | const irange &op2, |
3249 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
d3f29334 JJ |
3250 | virtual bool op2_range (irange &r, tree type, |
3251 | const irange &lhs, | |
80dd13f5 AM |
3252 | const irange &op1, |
3253 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
38a73435 AH |
3254 | } op_trunc_mod; |
3255 | ||
bb74ef9e | 3256 | void |
4ba9fb0a | 3257 | operator_trunc_mod::wi_fold (irange &r, tree type, |
38a73435 AH |
3258 | const wide_int &lh_lb, |
3259 | const wide_int &lh_ub, | |
3260 | const wide_int &rh_lb, | |
3261 | const wide_int &rh_ub) const | |
3262 | { | |
3263 | wide_int new_lb, new_ub, tmp; | |
3264 | signop sign = TYPE_SIGN (type); | |
3265 | unsigned prec = TYPE_PRECISION (type); | |
3266 | ||
82118acc | 3267 | // Mod 0 is undefined. |
38a73435 | 3268 | if (wi_zero_p (type, rh_lb, rh_ub)) |
bb74ef9e | 3269 | { |
156054e8 | 3270 | r.set_undefined (); |
bb74ef9e AM |
3271 | return; |
3272 | } | |
38a73435 | 3273 | |
145bc41d AM |
3274 | // Check for constant and try to fold. |
3275 | if (lh_lb == lh_ub && rh_lb == rh_ub) | |
3276 | { | |
3277 | wi::overflow_type ov = wi::OVF_NONE; | |
3278 | tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov); | |
3279 | if (ov == wi::OVF_NONE) | |
3280 | { | |
3281 | r = int_range<2> (type, tmp, tmp); | |
3282 | return; | |
3283 | } | |
3284 | } | |
3285 | ||
38a73435 AH |
3286 | // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0. |
3287 | new_ub = rh_ub - 1; | |
3288 | if (sign == SIGNED) | |
3289 | { | |
3290 | tmp = -1 - rh_lb; | |
3291 | new_ub = wi::smax (new_ub, tmp); | |
3292 | } | |
3293 | ||
3294 | if (sign == UNSIGNED) | |
3295 | new_lb = wi::zero (prec); | |
3296 | else | |
3297 | { | |
3298 | new_lb = -new_ub; | |
3299 | tmp = lh_lb; | |
3300 | if (wi::gts_p (tmp, 0)) | |
3301 | tmp = wi::zero (prec); | |
3302 | new_lb = wi::smax (new_lb, tmp); | |
3303 | } | |
3304 | tmp = lh_ub; | |
3305 | if (sign == SIGNED && wi::neg_p (tmp)) | |
3306 | tmp = wi::zero (prec); | |
3307 | new_ub = wi::min (new_ub, tmp, sign); | |
3308 | ||
bb74ef9e | 3309 | value_range_with_overflow (r, type, new_lb, new_ub); |
38a73435 AH |
3310 | } |
3311 | ||
1e27e7a5 AM |
3312 | bool |
3313 | operator_trunc_mod::op1_range (irange &r, tree type, | |
3314 | const irange &lhs, | |
80dd13f5 AM |
3315 | const irange &, |
3316 | relation_kind rel ATTRIBUTE_UNUSED) const | |
1e27e7a5 | 3317 | { |
d3f29334 JJ |
3318 | // PR 91029. |
3319 | signop sign = TYPE_SIGN (type); | |
3320 | unsigned prec = TYPE_PRECISION (type); | |
3321 | // (a % b) >= x && x > 0 , then a >= x. | |
3322 | if (wi::gt_p (lhs.lower_bound (), 0, sign)) | |
1e27e7a5 | 3323 | { |
d3f29334 JJ |
3324 | r = value_range (type, lhs.lower_bound (), wi::max_value (prec, sign)); |
3325 | return true; | |
3326 | } | |
3327 | // (a % b) <= x && x < 0 , then a <= x. | |
3328 | if (wi::lt_p (lhs.upper_bound (), 0, sign)) | |
3329 | { | |
3330 | r = value_range (type, wi::min_value (prec, sign), lhs.upper_bound ()); | |
3331 | return true; | |
3332 | } | |
3333 | return false; | |
3334 | } | |
3335 | ||
3336 | bool | |
3337 | operator_trunc_mod::op2_range (irange &r, tree type, | |
3338 | const irange &lhs, | |
80dd13f5 AM |
3339 | const irange &, |
3340 | relation_kind rel ATTRIBUTE_UNUSED) const | |
d3f29334 JJ |
3341 | { |
3342 | // PR 91029. | |
3343 | signop sign = TYPE_SIGN (type); | |
3344 | unsigned prec = TYPE_PRECISION (type); | |
3345 | // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed | |
3346 | // or b > x for unsigned. | |
3347 | if (wi::gt_p (lhs.lower_bound (), 0, sign)) | |
3348 | { | |
3349 | if (sign == SIGNED) | |
3350 | r = value_range (type, wi::neg (lhs.lower_bound ()), | |
3351 | lhs.lower_bound (), VR_ANTI_RANGE); | |
3352 | else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign), | |
3353 | sign)) | |
3354 | r = value_range (type, lhs.lower_bound () + 1, | |
3355 | wi::max_value (prec, sign)); | |
3356 | else | |
3357 | return false; | |
3358 | return true; | |
3359 | } | |
3360 | // (a % b) <= x && x < 0 , then b is in ~[x, -x]. | |
3361 | if (wi::lt_p (lhs.upper_bound (), 0, sign)) | |
3362 | { | |
3363 | if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign)) | |
3364 | r = value_range (type, lhs.upper_bound (), | |
3365 | wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE); | |
3366 | else | |
3367 | return false; | |
3368 | return true; | |
1e27e7a5 AM |
3369 | } |
3370 | return false; | |
3371 | } | |
3372 | ||
38a73435 AH |
3373 | |
3374 | class operator_logical_not : public range_operator | |
3375 | { | |
3376 | public: | |
4ba9fb0a AH |
3377 | virtual bool fold_range (irange &r, tree type, |
3378 | const irange &lh, | |
80dd13f5 AM |
3379 | const irange &rh, |
3380 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
3381 | virtual bool op1_range (irange &r, tree type, |
3382 | const irange &lhs, | |
80dd13f5 AM |
3383 | const irange &op2, |
3384 | relation_kind rel = VREL_NONE) const; | |
38a73435 AH |
3385 | } op_logical_not; |
3386 | ||
3387 | // Folding a logical NOT, oddly enough, involves doing nothing on the | |
3388 | // forward pass through. During the initial walk backwards, the | |
3389 | // logical NOT reversed the desired outcome on the way back, so on the | |
3390 | // way forward all we do is pass the range forward. | |
3391 | // | |
3392 | // b_2 = x_1 < 20 | |
3393 | // b_3 = !b_2 | |
3394 | // if (b_3) | |
3395 | // to determine the TRUE branch, walking backward | |
3396 | // if (b_3) if ([1,1]) | |
3397 | // b_3 = !b_2 [1,1] = ![0,0] | |
3398 | // b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255] | |
3399 | // which is the result we are looking for.. so.. pass it through. | |
3400 | ||
f674b4a7 | 3401 | bool |
4ba9fb0a AH |
3402 | operator_logical_not::fold_range (irange &r, tree type, |
3403 | const irange &lh, | |
80dd13f5 AM |
3404 | const irange &rh ATTRIBUTE_UNUSED, |
3405 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3406 | { |
4ba9fb0a | 3407 | if (empty_range_varying (r, type, lh, rh)) |
f674b4a7 | 3408 | return true; |
38a73435 | 3409 | |
61dd8dab EB |
3410 | r = lh; |
3411 | if (!lh.varying_p () && !lh.undefined_p ()) | |
3412 | r.invert (); | |
3413 | ||
f674b4a7 | 3414 | return true; |
38a73435 AH |
3415 | } |
3416 | ||
3417 | bool | |
4ba9fb0a | 3418 | operator_logical_not::op1_range (irange &r, |
61dd8dab | 3419 | tree type, |
4ba9fb0a | 3420 | const irange &lhs, |
80dd13f5 AM |
3421 | const irange &op2, |
3422 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3423 | { |
61dd8dab EB |
3424 | // Logical NOT is involutary...do it again. |
3425 | return fold_range (r, type, lhs, op2); | |
38a73435 AH |
3426 | } |
3427 | ||
3428 | ||
3429 | class operator_bitwise_not : public range_operator | |
3430 | { | |
3431 | public: | |
4ba9fb0a AH |
3432 | virtual bool fold_range (irange &r, tree type, |
3433 | const irange &lh, | |
80dd13f5 AM |
3434 | const irange &rh, |
3435 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
3436 | virtual bool op1_range (irange &r, tree type, |
3437 | const irange &lhs, | |
80dd13f5 AM |
3438 | const irange &op2, |
3439 | relation_kind rel = VREL_NONE) const; | |
38a73435 AH |
3440 | } op_bitwise_not; |
3441 | ||
f674b4a7 | 3442 | bool |
4ba9fb0a AH |
3443 | operator_bitwise_not::fold_range (irange &r, tree type, |
3444 | const irange &lh, | |
80dd13f5 AM |
3445 | const irange &rh, |
3446 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3447 | { |
4ba9fb0a | 3448 | if (empty_range_varying (r, type, lh, rh)) |
f674b4a7 | 3449 | return true; |
38a73435 | 3450 | |
61dd8dab EB |
3451 | if (types_compatible_p (type, boolean_type_node)) |
3452 | return op_logical_not.fold_range (r, type, lh, rh); | |
3453 | ||
38a73435 | 3454 | // ~X is simply -1 - X. |
4ba9fb0a AH |
3455 | int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)), |
3456 | wi::minus_one (TYPE_PRECISION (type))); | |
f674b4a7 AM |
3457 | return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, minusone, |
3458 | lh); | |
38a73435 AH |
3459 | } |
3460 | ||
3461 | bool | |
4ba9fb0a AH |
3462 | operator_bitwise_not::op1_range (irange &r, tree type, |
3463 | const irange &lhs, | |
80dd13f5 AM |
3464 | const irange &op2, |
3465 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3466 | { |
61dd8dab EB |
3467 | if (types_compatible_p (type, boolean_type_node)) |
3468 | return op_logical_not.op1_range (r, type, lhs, op2); | |
3469 | ||
38a73435 | 3470 | // ~X is -1 - X and since bitwise NOT is involutary...do it again. |
f674b4a7 | 3471 | return fold_range (r, type, lhs, op2); |
38a73435 AH |
3472 | } |
3473 | ||
3474 | ||
3475 | class operator_cst : public range_operator | |
3476 | { | |
3477 | public: | |
4ba9fb0a AH |
3478 | virtual bool fold_range (irange &r, tree type, |
3479 | const irange &op1, | |
80dd13f5 AM |
3480 | const irange &op2, |
3481 | relation_kind rel = VREL_NONE) const; | |
38a73435 AH |
3482 | } op_integer_cst; |
3483 | ||
f674b4a7 | 3484 | bool |
4ba9fb0a AH |
3485 | operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, |
3486 | const irange &lh, | |
80dd13f5 AM |
3487 | const irange &rh ATTRIBUTE_UNUSED, |
3488 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3489 | { |
bb74ef9e | 3490 | r = lh; |
f674b4a7 | 3491 | return true; |
38a73435 AH |
3492 | } |
3493 | ||
3494 | ||
3495 | class operator_identity : public range_operator | |
3496 | { | |
3497 | public: | |
4ba9fb0a AH |
3498 | virtual bool fold_range (irange &r, tree type, |
3499 | const irange &op1, | |
80dd13f5 AM |
3500 | const irange &op2, |
3501 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
3502 | virtual bool op1_range (irange &r, tree type, |
3503 | const irange &lhs, | |
80dd13f5 AM |
3504 | const irange &op2, |
3505 | relation_kind rel = VREL_NONE) const; | |
0f7ccc06 AM |
3506 | virtual enum tree_code lhs_op1_relation (const irange &lhs, |
3507 | const irange &op1, | |
3508 | const irange &op2) const; | |
38a73435 AH |
3509 | } op_identity; |
3510 | ||
0f7ccc06 AM |
3511 | // Determine if there is a relationship between LHS and OP1. |
3512 | ||
3513 | enum tree_code | |
3514 | operator_identity::lhs_op1_relation (const irange &lhs, | |
3515 | const irange &op1 ATTRIBUTE_UNUSED, | |
3516 | const irange &op2 ATTRIBUTE_UNUSED) const | |
3517 | { | |
3518 | if (lhs.undefined_p ()) | |
3519 | return VREL_NONE; | |
3520 | // Simply a copy, so they are equivalent. | |
3521 | return EQ_EXPR; | |
3522 | } | |
3523 | ||
f674b4a7 | 3524 | bool |
4ba9fb0a AH |
3525 | operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, |
3526 | const irange &lh, | |
80dd13f5 AM |
3527 | const irange &rh ATTRIBUTE_UNUSED, |
3528 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3529 | { |
bb74ef9e | 3530 | r = lh; |
f674b4a7 | 3531 | return true; |
38a73435 AH |
3532 | } |
3533 | ||
3534 | bool | |
4ba9fb0a AH |
3535 | operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED, |
3536 | const irange &lhs, | |
80dd13f5 AM |
3537 | const irange &op2 ATTRIBUTE_UNUSED, |
3538 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
3539 | { |
3540 | r = lhs; | |
3541 | return true; | |
3542 | } | |
3543 | ||
3544 | ||
4ba9fb0a AH |
3545 | class operator_unknown : public range_operator |
3546 | { | |
3547 | public: | |
3548 | virtual bool fold_range (irange &r, tree type, | |
3549 | const irange &op1, | |
80dd13f5 AM |
3550 | const irange &op2, |
3551 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
3552 | } op_unknown; |
3553 | ||
3554 | bool | |
3555 | operator_unknown::fold_range (irange &r, tree type, | |
3556 | const irange &lh ATTRIBUTE_UNUSED, | |
80dd13f5 AM |
3557 | const irange &rh ATTRIBUTE_UNUSED, |
3558 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
3559 | { |
3560 | r.set_varying (type); | |
3561 | return true; | |
3562 | } | |
3563 | ||
3564 | ||
38a73435 AH |
3565 | class operator_abs : public range_operator |
3566 | { | |
3567 | public: | |
4ba9fb0a | 3568 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
3569 | const wide_int &lh_lb, |
3570 | const wide_int &lh_ub, | |
3571 | const wide_int &rh_lb, | |
3572 | const wide_int &rh_ub) const; | |
4ba9fb0a AH |
3573 | virtual bool op1_range (irange &r, tree type, |
3574 | const irange &lhs, | |
80dd13f5 AM |
3575 | const irange &op2, |
3576 | relation_kind rel ATTRIBUTE_UNUSED) const; | |
38a73435 AH |
3577 | } op_abs; |
3578 | ||
bb74ef9e | 3579 | void |
4ba9fb0a | 3580 | operator_abs::wi_fold (irange &r, tree type, |
38a73435 AH |
3581 | const wide_int &lh_lb, const wide_int &lh_ub, |
3582 | const wide_int &rh_lb ATTRIBUTE_UNUSED, | |
3583 | const wide_int &rh_ub ATTRIBUTE_UNUSED) const | |
3584 | { | |
3585 | wide_int min, max; | |
3586 | signop sign = TYPE_SIGN (type); | |
3587 | unsigned prec = TYPE_PRECISION (type); | |
3588 | ||
3589 | // Pass through LH for the easy cases. | |
3590 | if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign)) | |
bb74ef9e | 3591 | { |
4ba9fb0a | 3592 | r = int_range<1> (type, lh_lb, lh_ub); |
bb74ef9e AM |
3593 | return; |
3594 | } | |
38a73435 AH |
3595 | |
3596 | // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get | |
3597 | // a useful range. | |
3598 | wide_int min_value = wi::min_value (prec, sign); | |
3599 | wide_int max_value = wi::max_value (prec, sign); | |
3600 | if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value)) | |
bb74ef9e | 3601 | { |
4ba9fb0a | 3602 | r.set_varying (type); |
bb74ef9e AM |
3603 | return; |
3604 | } | |
38a73435 AH |
3605 | |
3606 | // ABS_EXPR may flip the range around, if the original range | |
3607 | // included negative values. | |
3608 | if (wi::eq_p (lh_lb, min_value)) | |
bd431d26 AH |
3609 | { |
3610 | // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally | |
3611 | // returned [-MIN,-MIN] so this preserves that behaviour. PR37078 | |
3612 | if (wi::eq_p (lh_ub, min_value)) | |
3613 | { | |
3614 | r = int_range<1> (type, min_value, min_value); | |
3615 | return; | |
3616 | } | |
3617 | min = max_value; | |
3618 | } | |
38a73435 AH |
3619 | else |
3620 | min = wi::abs (lh_lb); | |
bd431d26 | 3621 | |
38a73435 AH |
3622 | if (wi::eq_p (lh_ub, min_value)) |
3623 | max = max_value; | |
3624 | else | |
3625 | max = wi::abs (lh_ub); | |
3626 | ||
3627 | // If the range contains zero then we know that the minimum value in the | |
3628 | // range will be zero. | |
3629 | if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign)) | |
3630 | { | |
3631 | if (wi::gt_p (min, max, sign)) | |
3632 | max = min; | |
3633 | min = wi::zero (prec); | |
3634 | } | |
3635 | else | |
3636 | { | |
3637 | // If the range was reversed, swap MIN and MAX. | |
3638 | if (wi::gt_p (min, max, sign)) | |
3639 | std::swap (min, max); | |
3640 | } | |
3641 | ||
3642 | // If the new range has its limits swapped around (MIN > MAX), then | |
3643 | // the operation caused one of them to wrap around. The only thing | |
3644 | // we know is that the result is positive. | |
3645 | if (wi::gt_p (min, max, sign)) | |
3646 | { | |
3647 | min = wi::zero (prec); | |
3648 | max = max_value; | |
3649 | } | |
4ba9fb0a | 3650 | r = int_range<1> (type, min, max); |
38a73435 AH |
3651 | } |
3652 | ||
3653 | bool | |
4ba9fb0a AH |
3654 | operator_abs::op1_range (irange &r, tree type, |
3655 | const irange &lhs, | |
80dd13f5 AM |
3656 | const irange &op2, |
3657 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3658 | { |
4ba9fb0a | 3659 | if (empty_range_varying (r, type, lhs, op2)) |
38a73435 AH |
3660 | return true; |
3661 | if (TYPE_UNSIGNED (type)) | |
3662 | { | |
3663 | r = lhs; | |
3664 | return true; | |
3665 | } | |
3666 | // Start with the positives because negatives are an impossible result. | |
c5a6c223 | 3667 | int_range_max positives = range_positives (type); |
38a73435 AH |
3668 | positives.intersect (lhs); |
3669 | r = positives; | |
3670 | // Then add the negative of each pair: | |
3671 | // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20]. | |
3672 | for (unsigned i = 0; i < positives.num_pairs (); ++i) | |
4ba9fb0a AH |
3673 | r.union_ (int_range<1> (type, |
3674 | -positives.upper_bound (i), | |
3675 | -positives.lower_bound (i))); | |
891bdbf2 AM |
3676 | // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is |
3677 | // unrepresentable. Add -TYPE_MIN_VALUE in this case. | |
3678 | wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); | |
3679 | wide_int lb = lhs.lower_bound (); | |
3680 | if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value)) | |
3681 | r.union_ (int_range<2> (type, lb, lb)); | |
38a73435 AH |
3682 | return true; |
3683 | } | |
3684 | ||
3685 | ||
3686 | class operator_absu : public range_operator | |
3687 | { | |
3688 | public: | |
4ba9fb0a | 3689 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
3690 | const wide_int &lh_lb, const wide_int &lh_ub, |
3691 | const wide_int &rh_lb, const wide_int &rh_ub) const; | |
38a73435 AH |
3692 | } op_absu; |
3693 | ||
bb74ef9e | 3694 | void |
4ba9fb0a | 3695 | operator_absu::wi_fold (irange &r, tree type, |
38a73435 AH |
3696 | const wide_int &lh_lb, const wide_int &lh_ub, |
3697 | const wide_int &rh_lb ATTRIBUTE_UNUSED, | |
3698 | const wide_int &rh_ub ATTRIBUTE_UNUSED) const | |
3699 | { | |
3700 | wide_int new_lb, new_ub; | |
3701 | ||
3702 | // Pass through VR0 the easy cases. | |
3703 | if (wi::ges_p (lh_lb, 0)) | |
3704 | { | |
3705 | new_lb = lh_lb; | |
3706 | new_ub = lh_ub; | |
3707 | } | |
3708 | else | |
3709 | { | |
3710 | new_lb = wi::abs (lh_lb); | |
3711 | new_ub = wi::abs (lh_ub); | |
3712 | ||
3713 | // If the range contains zero then we know that the minimum | |
3714 | // value in the range will be zero. | |
3715 | if (wi::ges_p (lh_ub, 0)) | |
3716 | { | |
3717 | if (wi::gtu_p (new_lb, new_ub)) | |
3718 | new_ub = new_lb; | |
3719 | new_lb = wi::zero (TYPE_PRECISION (type)); | |
3720 | } | |
3721 | else | |
3722 | std::swap (new_lb, new_ub); | |
3723 | } | |
3724 | ||
3725 | gcc_checking_assert (TYPE_UNSIGNED (type)); | |
4ba9fb0a | 3726 | r = int_range<1> (type, new_lb, new_ub); |
38a73435 AH |
3727 | } |
3728 | ||
3729 | ||
3730 | class operator_negate : public range_operator | |
3731 | { | |
3732 | public: | |
4ba9fb0a AH |
3733 | virtual bool fold_range (irange &r, tree type, |
3734 | const irange &op1, | |
80dd13f5 AM |
3735 | const irange &op2, |
3736 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
3737 | virtual bool op1_range (irange &r, tree type, |
3738 | const irange &lhs, | |
80dd13f5 AM |
3739 | const irange &op2, |
3740 | relation_kind rel = VREL_NONE) const; | |
38a73435 AH |
3741 | } op_negate; |
3742 | ||
f674b4a7 | 3743 | bool |
4ba9fb0a AH |
3744 | operator_negate::fold_range (irange &r, tree type, |
3745 | const irange &lh, | |
80dd13f5 AM |
3746 | const irange &rh, |
3747 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3748 | { |
4ba9fb0a | 3749 | if (empty_range_varying (r, type, lh, rh)) |
f674b4a7 | 3750 | return true; |
38a73435 | 3751 | // -X is simply 0 - X. |
f674b4a7 AM |
3752 | return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, |
3753 | range_zero (type), | |
3754 | lh); | |
38a73435 AH |
3755 | } |
3756 | ||
3757 | bool | |
4ba9fb0a AH |
3758 | operator_negate::op1_range (irange &r, tree type, |
3759 | const irange &lhs, | |
80dd13f5 AM |
3760 | const irange &op2, |
3761 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 AH |
3762 | { |
3763 | // NEGATE is involutory. | |
f674b4a7 | 3764 | return fold_range (r, type, lhs, op2); |
38a73435 AH |
3765 | } |
3766 | ||
3767 | ||
3768 | class operator_addr_expr : public range_operator | |
3769 | { | |
3770 | public: | |
4ba9fb0a AH |
3771 | virtual bool fold_range (irange &r, tree type, |
3772 | const irange &op1, | |
80dd13f5 AM |
3773 | const irange &op2, |
3774 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
3775 | virtual bool op1_range (irange &r, tree type, |
3776 | const irange &lhs, | |
80dd13f5 AM |
3777 | const irange &op2, |
3778 | relation_kind rel = VREL_NONE) const; | |
38a73435 AH |
3779 | } op_addr; |
3780 | ||
f674b4a7 | 3781 | bool |
4ba9fb0a AH |
3782 | operator_addr_expr::fold_range (irange &r, tree type, |
3783 | const irange &lh, | |
80dd13f5 AM |
3784 | const irange &rh, |
3785 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3786 | { |
4ba9fb0a | 3787 | if (empty_range_varying (r, type, lh, rh)) |
f674b4a7 | 3788 | return true; |
38a73435 AH |
3789 | |
3790 | // Return a non-null pointer of the LHS type (passed in op2). | |
3791 | if (lh.zero_p ()) | |
bb74ef9e AM |
3792 | r = range_zero (type); |
3793 | else if (!lh.contains_p (build_zero_cst (lh.type ()))) | |
3794 | r = range_nonzero (type); | |
3795 | else | |
4ba9fb0a | 3796 | r.set_varying (type); |
f674b4a7 | 3797 | return true; |
38a73435 AH |
3798 | } |
3799 | ||
3800 | bool | |
4ba9fb0a AH |
3801 | operator_addr_expr::op1_range (irange &r, tree type, |
3802 | const irange &lhs, | |
80dd13f5 AM |
3803 | const irange &op2, |
3804 | relation_kind rel ATTRIBUTE_UNUSED) const | |
38a73435 | 3805 | { |
f674b4a7 | 3806 | return operator_addr_expr::fold_range (r, type, lhs, op2); |
38a73435 AH |
3807 | } |
3808 | ||
3809 | ||
3810 | class pointer_plus_operator : public range_operator | |
3811 | { | |
3812 | public: | |
4ba9fb0a | 3813 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
3814 | const wide_int &lh_lb, |
3815 | const wide_int &lh_ub, | |
3816 | const wide_int &rh_lb, | |
3817 | const wide_int &rh_ub) const; | |
38a73435 AH |
3818 | } op_pointer_plus; |
3819 | ||
bb74ef9e | 3820 | void |
4ba9fb0a | 3821 | pointer_plus_operator::wi_fold (irange &r, tree type, |
38a73435 AH |
3822 | const wide_int &lh_lb, |
3823 | const wide_int &lh_ub, | |
3824 | const wide_int &rh_lb, | |
3825 | const wide_int &rh_ub) const | |
3826 | { | |
58492575 AM |
3827 | // Check for [0,0] + const, and simply return the const. |
3828 | if (lh_lb == 0 && lh_ub == 0 && rh_lb == rh_ub) | |
3829 | { | |
3830 | tree val = wide_int_to_tree (type, rh_lb); | |
3831 | r.set (val, val); | |
3832 | return; | |
3833 | } | |
3834 | ||
38a73435 AH |
3835 | // For pointer types, we are really only interested in asserting |
3836 | // whether the expression evaluates to non-NULL. | |
3837 | // | |
3838 | // With -fno-delete-null-pointer-checks we need to be more | |
3839 | // conservative. As some object might reside at address 0, | |
3840 | // then some offset could be added to it and the same offset | |
3841 | // subtracted again and the result would be NULL. | |
3842 | // E.g. | |
3843 | // static int a[12]; where &a[0] is NULL and | |
3844 | // ptr = &a[6]; | |
3845 | // ptr -= 6; | |
3846 | // ptr will be NULL here, even when there is POINTER_PLUS_EXPR | |
3847 | // where the first range doesn't include zero and the second one | |
3848 | // doesn't either. As the second operand is sizetype (unsigned), | |
3849 | // consider all ranges where the MSB could be set as possible | |
3850 | // subtractions where the result might be NULL. | |
3851 | if ((!wi_includes_zero_p (type, lh_lb, lh_ub) | |
3852 | || !wi_includes_zero_p (type, rh_lb, rh_ub)) | |
3853 | && !TYPE_OVERFLOW_WRAPS (type) | |
3854 | && (flag_delete_null_pointer_checks | |
3855 | || !wi::sign_mask (rh_ub))) | |
bb74ef9e AM |
3856 | r = range_nonzero (type); |
3857 | else if (lh_lb == lh_ub && lh_lb == 0 | |
3858 | && rh_lb == rh_ub && rh_lb == 0) | |
3859 | r = range_zero (type); | |
3860 | else | |
4ba9fb0a | 3861 | r.set_varying (type); |
38a73435 AH |
3862 | } |
3863 | ||
3864 | ||
3865 | class pointer_min_max_operator : public range_operator | |
3866 | { | |
3867 | public: | |
4ba9fb0a | 3868 | virtual void wi_fold (irange & r, tree type, |
bb74ef9e AM |
3869 | const wide_int &lh_lb, const wide_int &lh_ub, |
3870 | const wide_int &rh_lb, const wide_int &rh_ub) const; | |
38a73435 AH |
3871 | } op_ptr_min_max; |
3872 | ||
bb74ef9e | 3873 | void |
4ba9fb0a | 3874 | pointer_min_max_operator::wi_fold (irange &r, tree type, |
38a73435 AH |
3875 | const wide_int &lh_lb, |
3876 | const wide_int &lh_ub, | |
3877 | const wide_int &rh_lb, | |
3878 | const wide_int &rh_ub) const | |
3879 | { | |
3880 | // For MIN/MAX expressions with pointers, we only care about | |
3881 | // nullness. If both are non null, then the result is nonnull. | |
3882 | // If both are null, then the result is null. Otherwise they | |
3883 | // are varying. | |
3884 | if (!wi_includes_zero_p (type, lh_lb, lh_ub) | |
3885 | && !wi_includes_zero_p (type, rh_lb, rh_ub)) | |
bb74ef9e AM |
3886 | r = range_nonzero (type); |
3887 | else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub)) | |
3888 | r = range_zero (type); | |
3889 | else | |
4ba9fb0a | 3890 | r.set_varying (type); |
38a73435 AH |
3891 | } |
3892 | ||
3893 | ||
3894 | class pointer_and_operator : public range_operator | |
3895 | { | |
3896 | public: | |
4ba9fb0a | 3897 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
3898 | const wide_int &lh_lb, const wide_int &lh_ub, |
3899 | const wide_int &rh_lb, const wide_int &rh_ub) const; | |
38a73435 AH |
3900 | } op_pointer_and; |
3901 | ||
bb74ef9e | 3902 | void |
4ba9fb0a | 3903 | pointer_and_operator::wi_fold (irange &r, tree type, |
38a73435 AH |
3904 | const wide_int &lh_lb, |
3905 | const wide_int &lh_ub, | |
3906 | const wide_int &rh_lb ATTRIBUTE_UNUSED, | |
3907 | const wide_int &rh_ub ATTRIBUTE_UNUSED) const | |
3908 | { | |
3909 | // For pointer types, we are really only interested in asserting | |
3910 | // whether the expression evaluates to non-NULL. | |
3911 | if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub)) | |
bb74ef9e AM |
3912 | r = range_zero (type); |
3913 | else | |
4ba9fb0a | 3914 | r.set_varying (type); |
38a73435 AH |
3915 | } |
3916 | ||
3917 | ||
3918 | class pointer_or_operator : public range_operator | |
3919 | { | |
3920 | public: | |
4ba9fb0a AH |
3921 | virtual bool op1_range (irange &r, tree type, |
3922 | const irange &lhs, | |
80dd13f5 AM |
3923 | const irange &op2, |
3924 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a AH |
3925 | virtual bool op2_range (irange &r, tree type, |
3926 | const irange &lhs, | |
80dd13f5 AM |
3927 | const irange &op1, |
3928 | relation_kind rel = VREL_NONE) const; | |
4ba9fb0a | 3929 | virtual void wi_fold (irange &r, tree type, |
bb74ef9e AM |
3930 | const wide_int &lh_lb, const wide_int &lh_ub, |
3931 | const wide_int &rh_lb, const wide_int &rh_ub) const; | |
38a73435 AH |
3932 | } op_pointer_or; |
3933 | ||
4ba9fb0a AH |
3934 | bool |
3935 | pointer_or_operator::op1_range (irange &r, tree type, | |
3936 | const irange &lhs, | |
80dd13f5 AM |
3937 | const irange &op2 ATTRIBUTE_UNUSED, |
3938 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
3939 | { |
3940 | if (lhs.zero_p ()) | |
3941 | { | |
3942 | tree zero = build_zero_cst (type); | |
3943 | r = int_range<1> (zero, zero); | |
3944 | return true; | |
3945 | } | |
3946 | r.set_varying (type); | |
3947 | return true; | |
3948 | } | |
3949 | ||
3950 | bool | |
3951 | pointer_or_operator::op2_range (irange &r, tree type, | |
3952 | const irange &lhs, | |
80dd13f5 AM |
3953 | const irange &op1, |
3954 | relation_kind rel ATTRIBUTE_UNUSED) const | |
4ba9fb0a AH |
3955 | { |
3956 | return pointer_or_operator::op1_range (r, type, lhs, op1); | |
3957 | } | |
3958 | ||
bb74ef9e | 3959 | void |
4ba9fb0a | 3960 | pointer_or_operator::wi_fold (irange &r, tree type, |
38a73435 AH |
3961 | const wide_int &lh_lb, |
3962 | const wide_int &lh_ub, | |
3963 | const wide_int &rh_lb, | |
3964 | const wide_int &rh_ub) const | |
3965 | { | |
3966 | // For pointer types, we are really only interested in asserting | |
3967 | // whether the expression evaluates to non-NULL. | |
3968 | if (!wi_includes_zero_p (type, lh_lb, lh_ub) | |
3969 | && !wi_includes_zero_p (type, rh_lb, rh_ub)) | |
bb74ef9e AM |
3970 | r = range_nonzero (type); |
3971 | else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub)) | |
3972 | r = range_zero (type); | |
3973 | else | |
4ba9fb0a | 3974 | r.set_varying (type); |
38a73435 AH |
3975 | } |
3976 | \f | |
3977 | // This implements the range operator tables as local objects in this file. | |
3978 | ||
3979 | class range_op_table | |
3980 | { | |
3981 | public: | |
3982 | inline range_operator *operator[] (enum tree_code code); | |
3983 | protected: | |
3984 | void set (enum tree_code code, range_operator &op); | |
3985 | private: | |
3986 | range_operator *m_range_tree[MAX_TREE_CODES]; | |
3987 | }; | |
3988 | ||
3989 | // Return a pointer to the range_operator instance, if there is one | |
3990 | // associated with tree_code CODE. | |
3991 | ||
3992 | range_operator * | |
3993 | range_op_table::operator[] (enum tree_code code) | |
3994 | { | |
3995 | gcc_checking_assert (code > 0 && code < MAX_TREE_CODES); | |
3996 | return m_range_tree[code]; | |
3997 | } | |
3998 | ||
3999 | // Add OP to the handler table for CODE. | |
4000 | ||
4001 | void | |
4002 | range_op_table::set (enum tree_code code, range_operator &op) | |
4003 | { | |
4004 | gcc_checking_assert (m_range_tree[code] == NULL); | |
4005 | m_range_tree[code] = &op; | |
4006 | } | |
4007 | ||
4008 | // Instantiate a range op table for integral operations. | |
4009 | ||
4010 | class integral_table : public range_op_table | |
4011 | { | |
4012 | public: | |
4013 | integral_table (); | |
4014 | } integral_tree_table; | |
4015 | ||
4016 | integral_table::integral_table () | |
4017 | { | |
4018 | set (EQ_EXPR, op_equal); | |
4019 | set (NE_EXPR, op_not_equal); | |
4020 | set (LT_EXPR, op_lt); | |
4021 | set (LE_EXPR, op_le); | |
4022 | set (GT_EXPR, op_gt); | |
4023 | set (GE_EXPR, op_ge); | |
4024 | set (PLUS_EXPR, op_plus); | |
4025 | set (MINUS_EXPR, op_minus); | |
4026 | set (MIN_EXPR, op_min); | |
4027 | set (MAX_EXPR, op_max); | |
4028 | set (MULT_EXPR, op_mult); | |
4029 | set (TRUNC_DIV_EXPR, op_trunc_div); | |
4030 | set (FLOOR_DIV_EXPR, op_floor_div); | |
4031 | set (ROUND_DIV_EXPR, op_round_div); | |
4032 | set (CEIL_DIV_EXPR, op_ceil_div); | |
4033 | set (EXACT_DIV_EXPR, op_exact_div); | |
4034 | set (LSHIFT_EXPR, op_lshift); | |
4035 | set (RSHIFT_EXPR, op_rshift); | |
4036 | set (NOP_EXPR, op_convert); | |
4037 | set (CONVERT_EXPR, op_convert); | |
4038 | set (TRUTH_AND_EXPR, op_logical_and); | |
4039 | set (BIT_AND_EXPR, op_bitwise_and); | |
4040 | set (TRUTH_OR_EXPR, op_logical_or); | |
4041 | set (BIT_IOR_EXPR, op_bitwise_or); | |
4042 | set (BIT_XOR_EXPR, op_bitwise_xor); | |
4043 | set (TRUNC_MOD_EXPR, op_trunc_mod); | |
4044 | set (TRUTH_NOT_EXPR, op_logical_not); | |
4045 | set (BIT_NOT_EXPR, op_bitwise_not); | |
4046 | set (INTEGER_CST, op_integer_cst); | |
4047 | set (SSA_NAME, op_identity); | |
4048 | set (PAREN_EXPR, op_identity); | |
4049 | set (OBJ_TYPE_REF, op_identity); | |
4ba9fb0a | 4050 | set (IMAGPART_EXPR, op_unknown); |
bccf4b88 | 4051 | set (REALPART_EXPR, op_unknown); |
8af8abfb | 4052 | set (POINTER_DIFF_EXPR, op_pointer_diff); |
38a73435 AH |
4053 | set (ABS_EXPR, op_abs); |
4054 | set (ABSU_EXPR, op_absu); | |
4055 | set (NEGATE_EXPR, op_negate); | |
4056 | set (ADDR_EXPR, op_addr); | |
4057 | } | |
4058 | ||
4059 | // Instantiate a range op table for pointer operations. | |
4060 | ||
4061 | class pointer_table : public range_op_table | |
4062 | { | |
4063 | public: | |
4064 | pointer_table (); | |
4065 | } pointer_tree_table; | |
4066 | ||
4067 | pointer_table::pointer_table () | |
4068 | { | |
4069 | set (BIT_AND_EXPR, op_pointer_and); | |
4070 | set (BIT_IOR_EXPR, op_pointer_or); | |
4071 | set (MIN_EXPR, op_ptr_min_max); | |
4072 | set (MAX_EXPR, op_ptr_min_max); | |
4073 | set (POINTER_PLUS_EXPR, op_pointer_plus); | |
4074 | ||
4075 | set (EQ_EXPR, op_equal); | |
4076 | set (NE_EXPR, op_not_equal); | |
4077 | set (LT_EXPR, op_lt); | |
4078 | set (LE_EXPR, op_le); | |
4079 | set (GT_EXPR, op_gt); | |
4080 | set (GE_EXPR, op_ge); | |
4081 | set (SSA_NAME, op_identity); | |
47923622 | 4082 | set (INTEGER_CST, op_integer_cst); |
38a73435 AH |
4083 | set (ADDR_EXPR, op_addr); |
4084 | set (NOP_EXPR, op_convert); | |
4085 | set (CONVERT_EXPR, op_convert); | |
4086 | ||
4087 | set (BIT_NOT_EXPR, op_bitwise_not); | |
4088 | set (BIT_XOR_EXPR, op_bitwise_xor); | |
4089 | } | |
4090 | ||
4091 | // The tables are hidden and accessed via a simple extern function. | |
4092 | ||
4093 | range_operator * | |
4094 | range_op_handler (enum tree_code code, tree type) | |
4095 | { | |
ee24da1b | 4096 | // First check if there is a pointer specialization. |
38a73435 AH |
4097 | if (POINTER_TYPE_P (type)) |
4098 | return pointer_tree_table[code]; | |
ee24da1b AM |
4099 | if (INTEGRAL_TYPE_P (type)) |
4100 | return integral_tree_table[code]; | |
4101 | return NULL; | |
38a73435 AH |
4102 | } |
4103 | ||
4104 | // Cast the range in R to TYPE. | |
4105 | ||
4106 | void | |
4ba9fb0a | 4107 | range_cast (irange &r, tree type) |
38a73435 | 4108 | { |
c5a6c223 | 4109 | int_range_max tmp = r; |
38a73435 | 4110 | range_operator *op = range_op_handler (CONVERT_EXPR, type); |
f674b4a7 | 4111 | // Call op_convert, if it fails, the result is varying. |
4ba9fb0a AH |
4112 | if (!op->fold_range (r, type, tmp, int_range<1> (type))) |
4113 | r.set_varying (type); | |
38a73435 AH |
4114 | } |
4115 | ||
4116 | #if CHECKING_P | |
4117 | #include "selftest.h" | |
38a73435 | 4118 | |
f1471317 AH |
4119 | namespace selftest |
4120 | { | |
38a73435 AH |
4121 | #define INT(N) build_int_cst (integer_type_node, (N)) |
4122 | #define UINT(N) build_int_cstu (unsigned_type_node, (N)) | |
4123 | #define INT16(N) build_int_cst (short_integer_type_node, (N)) | |
4124 | #define UINT16(N) build_int_cstu (short_unsigned_type_node, (N)) | |
38a73435 | 4125 | #define SCHAR(N) build_int_cst (signed_char_type_node, (N)) |
b5cff0db | 4126 | #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N)) |
4ba9fb0a AH |
4127 | |
4128 | static void | |
b5cff0db | 4129 | range_op_cast_tests () |
38a73435 | 4130 | { |
b5cff0db | 4131 | int_range<1> r0, r1, r2, rold; |
38a73435 | 4132 | r0.set_varying (integer_type_node); |
38a73435 AH |
4133 | tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ()); |
4134 | ||
b5cff0db AH |
4135 | // If a range is in any way outside of the range for the converted |
4136 | // to range, default to the range for the new type. | |
38a73435 AH |
4137 | r0.set_varying (short_integer_type_node); |
4138 | tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ()); | |
4139 | tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ()); | |
82de69ff JL |
4140 | if (TYPE_PRECISION (TREE_TYPE (maxint)) |
4141 | > TYPE_PRECISION (short_integer_type_node)) | |
4142 | { | |
4ba9fb0a | 4143 | r1 = int_range<1> (integer_zero_node, maxint); |
82de69ff JL |
4144 | range_cast (r1, short_integer_type_node); |
4145 | ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort) | |
4146 | && r1.upper_bound() == wi::to_wide (maxshort)); | |
4147 | } | |
38a73435 AH |
4148 | |
4149 | // (unsigned char)[-5,-1] => [251,255]. | |
4ba9fb0a | 4150 | r0 = rold = int_range<1> (SCHAR (-5), SCHAR (-1)); |
38a73435 | 4151 | range_cast (r0, unsigned_char_type_node); |
4ba9fb0a | 4152 | ASSERT_TRUE (r0 == int_range<1> (UCHAR (251), UCHAR (255))); |
38a73435 AH |
4153 | range_cast (r0, signed_char_type_node); |
4154 | ASSERT_TRUE (r0 == rold); | |
4155 | ||
4156 | // (signed char)[15, 150] => [-128,-106][15,127]. | |
4ba9fb0a | 4157 | r0 = rold = int_range<1> (UCHAR (15), UCHAR (150)); |
38a73435 | 4158 | range_cast (r0, signed_char_type_node); |
4ba9fb0a AH |
4159 | r1 = int_range<1> (SCHAR (15), SCHAR (127)); |
4160 | r2 = int_range<1> (SCHAR (-128), SCHAR (-106)); | |
38a73435 AH |
4161 | r1.union_ (r2); |
4162 | ASSERT_TRUE (r1 == r0); | |
4163 | range_cast (r0, unsigned_char_type_node); | |
4164 | ASSERT_TRUE (r0 == rold); | |
4165 | ||
4166 | // (unsigned char)[-5, 5] => [0,5][251,255]. | |
4ba9fb0a | 4167 | r0 = rold = int_range<1> (SCHAR (-5), SCHAR (5)); |
38a73435 | 4168 | range_cast (r0, unsigned_char_type_node); |
4ba9fb0a AH |
4169 | r1 = int_range<1> (UCHAR (251), UCHAR (255)); |
4170 | r2 = int_range<1> (UCHAR (0), UCHAR (5)); | |
38a73435 AH |
4171 | r1.union_ (r2); |
4172 | ASSERT_TRUE (r0 == r1); | |
4173 | range_cast (r0, signed_char_type_node); | |
4174 | ASSERT_TRUE (r0 == rold); | |
4175 | ||
4176 | // (unsigned char)[-5,5] => [0,5][251,255]. | |
4ba9fb0a | 4177 | r0 = int_range<1> (INT (-5), INT (5)); |
38a73435 | 4178 | range_cast (r0, unsigned_char_type_node); |
4ba9fb0a AH |
4179 | r1 = int_range<1> (UCHAR (0), UCHAR (5)); |
4180 | r1.union_ (int_range<1> (UCHAR (251), UCHAR (255))); | |
38a73435 AH |
4181 | ASSERT_TRUE (r0 == r1); |
4182 | ||
4183 | // (unsigned char)[5U,1974U] => [0,255]. | |
4ba9fb0a | 4184 | r0 = int_range<1> (UINT (5), UINT (1974)); |
38a73435 | 4185 | range_cast (r0, unsigned_char_type_node); |
4ba9fb0a | 4186 | ASSERT_TRUE (r0 == int_range<1> (UCHAR (0), UCHAR (255))); |
38a73435 AH |
4187 | range_cast (r0, integer_type_node); |
4188 | // Going to a wider range should not sign extend. | |
4ba9fb0a | 4189 | ASSERT_TRUE (r0 == int_range<1> (INT (0), INT (255))); |
38a73435 AH |
4190 | |
4191 | // (unsigned char)[-350,15] => [0,255]. | |
4ba9fb0a | 4192 | r0 = int_range<1> (INT (-350), INT (15)); |
38a73435 | 4193 | range_cast (r0, unsigned_char_type_node); |
4ba9fb0a | 4194 | ASSERT_TRUE (r0 == (int_range<1> |
38a73435 AH |
4195 | (TYPE_MIN_VALUE (unsigned_char_type_node), |
4196 | TYPE_MAX_VALUE (unsigned_char_type_node)))); | |
4197 | ||
4198 | // Casting [-120,20] from signed char to unsigned short. | |
4199 | // => [0, 20][0xff88, 0xffff]. | |
4ba9fb0a | 4200 | r0 = int_range<1> (SCHAR (-120), SCHAR (20)); |
38a73435 | 4201 | range_cast (r0, short_unsigned_type_node); |
4ba9fb0a AH |
4202 | r1 = int_range<1> (UINT16 (0), UINT16 (20)); |
4203 | r2 = int_range<1> (UINT16 (0xff88), UINT16 (0xffff)); | |
38a73435 AH |
4204 | r1.union_ (r2); |
4205 | ASSERT_TRUE (r0 == r1); | |
4206 | // A truncating cast back to signed char will work because [-120, 20] | |
4207 | // is representable in signed char. | |
4208 | range_cast (r0, signed_char_type_node); | |
4ba9fb0a | 4209 | ASSERT_TRUE (r0 == int_range<1> (SCHAR (-120), SCHAR (20))); |
38a73435 AH |
4210 | |
4211 | // unsigned char -> signed short | |
4212 | // (signed short)[(unsigned char)25, (unsigned char)250] | |
4213 | // => [(signed short)25, (signed short)250] | |
4ba9fb0a | 4214 | r0 = rold = int_range<1> (UCHAR (25), UCHAR (250)); |
38a73435 | 4215 | range_cast (r0, short_integer_type_node); |
4ba9fb0a | 4216 | r1 = int_range<1> (INT16 (25), INT16 (250)); |
38a73435 AH |
4217 | ASSERT_TRUE (r0 == r1); |
4218 | range_cast (r0, unsigned_char_type_node); | |
4219 | ASSERT_TRUE (r0 == rold); | |
4220 | ||
4221 | // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned. | |
4ba9fb0a | 4222 | r0 = int_range<1> (TYPE_MIN_VALUE (long_long_integer_type_node), |
38a73435 AH |
4223 | TYPE_MAX_VALUE (long_long_integer_type_node)); |
4224 | range_cast (r0, short_unsigned_type_node); | |
4ba9fb0a | 4225 | r1 = int_range<1> (TYPE_MIN_VALUE (short_unsigned_type_node), |
38a73435 AH |
4226 | TYPE_MAX_VALUE (short_unsigned_type_node)); |
4227 | ASSERT_TRUE (r0 == r1); | |
4228 | ||
38a73435 AH |
4229 | // Casting NONZERO to a narrower type will wrap/overflow so |
4230 | // it's just the entire range for the narrower type. | |
4231 | // | |
4232 | // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is | |
4233 | // is outside of the range of a smaller range, return the full | |
4234 | // smaller range. | |
82de69ff JL |
4235 | if (TYPE_PRECISION (integer_type_node) |
4236 | > TYPE_PRECISION (short_integer_type_node)) | |
4237 | { | |
4238 | r0 = range_nonzero (integer_type_node); | |
4239 | range_cast (r0, short_integer_type_node); | |
4ba9fb0a AH |
4240 | r1 = int_range<1> (TYPE_MIN_VALUE (short_integer_type_node), |
4241 | TYPE_MAX_VALUE (short_integer_type_node)); | |
82de69ff JL |
4242 | ASSERT_TRUE (r0 == r1); |
4243 | } | |
38a73435 AH |
4244 | |
4245 | // Casting NONZERO from a narrower signed to a wider signed. | |
4246 | // | |
4247 | // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16]. | |
4248 | // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16]. | |
4249 | r0 = range_nonzero (short_integer_type_node); | |
4250 | range_cast (r0, integer_type_node); | |
4ba9fb0a AH |
4251 | r1 = int_range<1> (INT (-32768), INT (-1)); |
4252 | r2 = int_range<1> (INT (1), INT (32767)); | |
38a73435 AH |
4253 | r1.union_ (r2); |
4254 | ASSERT_TRUE (r0 == r1); | |
b5cff0db | 4255 | } |
38a73435 | 4256 | |
b5cff0db AH |
4257 | static void |
4258 | range_op_lshift_tests () | |
4259 | { | |
4260 | // Test that 0x808.... & 0x8.... still contains 0x8.... | |
4261 | // for a large set of numbers. | |
4262 | { | |
4263 | int_range_max res; | |
4264 | tree big_type = long_long_unsigned_type_node; | |
4265 | // big_num = 0x808,0000,0000,0000 | |
4266 | tree big_num = fold_build2 (LSHIFT_EXPR, big_type, | |
4267 | build_int_cst (big_type, 0x808), | |
4268 | build_int_cst (big_type, 48)); | |
4269 | op_bitwise_and.fold_range (res, big_type, | |
4270 | int_range <1> (big_type), | |
4271 | int_range <1> (big_num, big_num)); | |
4272 | // val = 0x8,0000,0000,0000 | |
4273 | tree val = fold_build2 (LSHIFT_EXPR, big_type, | |
4274 | build_int_cst (big_type, 0x8), | |
4275 | build_int_cst (big_type, 48)); | |
4276 | ASSERT_TRUE (res.contains_p (val)); | |
4277 | } | |
38a73435 | 4278 | |
b5cff0db AH |
4279 | if (TYPE_PRECISION (unsigned_type_node) > 31) |
4280 | { | |
4281 | // unsigned VARYING = op1 << 1 should be VARYING. | |
4282 | int_range<2> lhs (unsigned_type_node); | |
4283 | int_range<2> shift (INT (1), INT (1)); | |
4284 | int_range_max op1; | |
4285 | op_lshift.op1_range (op1, unsigned_type_node, lhs, shift); | |
4286 | ASSERT_TRUE (op1.varying_p ()); | |
4287 | ||
4288 | // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000]. | |
4289 | int_range<2> zero (UINT (0), UINT (0)); | |
4290 | op_lshift.op1_range (op1, unsigned_type_node, zero, shift); | |
4291 | ASSERT_TRUE (op1.num_pairs () == 2); | |
4292 | // Remove the [0,0] range. | |
4293 | op1.intersect (zero); | |
4294 | ASSERT_TRUE (op1.num_pairs () == 1); | |
4295 | // op1 << 1 should be [0x8000,0x8000] << 1, | |
4296 | // which should result in [0,0]. | |
4297 | int_range_max result; | |
4298 | op_lshift.fold_range (result, unsigned_type_node, op1, shift); | |
4299 | ASSERT_TRUE (result == zero); | |
4300 | } | |
4301 | // signed VARYING = op1 << 1 should be VARYING. | |
4302 | if (TYPE_PRECISION (integer_type_node) > 31) | |
4303 | { | |
4304 | // unsigned VARYING = op1 << 1 hould be VARYING. | |
4305 | int_range<2> lhs (integer_type_node); | |
4306 | int_range<2> shift (INT (1), INT (1)); | |
4307 | int_range_max op1; | |
4308 | op_lshift.op1_range (op1, integer_type_node, lhs, shift); | |
4309 | ASSERT_TRUE (op1.varying_p ()); | |
4310 | ||
4311 | // 0 = op1 << 1 should be [0,0], [0x8000000, 0x8000000]. | |
4312 | int_range<2> zero (INT (0), INT (0)); | |
4313 | op_lshift.op1_range (op1, integer_type_node, zero, shift); | |
4314 | ASSERT_TRUE (op1.num_pairs () == 2); | |
4315 | // Remove the [0,0] range. | |
4316 | op1.intersect (zero); | |
4317 | ASSERT_TRUE (op1.num_pairs () == 1); | |
4318 | // op1 << 1 shuould be [0x8000,0x8000] << 1, | |
4319 | // which should result in [0,0]. | |
4320 | int_range_max result; | |
4321 | op_lshift.fold_range (result, unsigned_type_node, op1, shift); | |
4322 | ASSERT_TRUE (result == zero); | |
4323 | } | |
4324 | } | |
4325 | ||
4326 | static void | |
4327 | range_op_rshift_tests () | |
4328 | { | |
4329 | // unsigned: [3, MAX] = OP1 >> 1 | |
4330 | { | |
4331 | int_range_max lhs (build_int_cst (unsigned_type_node, 3), | |
4332 | TYPE_MAX_VALUE (unsigned_type_node)); | |
4333 | int_range_max one (build_one_cst (unsigned_type_node), | |
4334 | build_one_cst (unsigned_type_node)); | |
4335 | int_range_max op1; | |
4336 | op_rshift.op1_range (op1, unsigned_type_node, lhs, one); | |
4337 | ASSERT_FALSE (op1.contains_p (UINT (3))); | |
4338 | } | |
4339 | ||
4340 | // signed: [3, MAX] = OP1 >> 1 | |
4341 | { | |
4342 | int_range_max lhs (INT (3), TYPE_MAX_VALUE (integer_type_node)); | |
4343 | int_range_max one (INT (1), INT (1)); | |
4344 | int_range_max op1; | |
4345 | op_rshift.op1_range (op1, integer_type_node, lhs, one); | |
4346 | ASSERT_FALSE (op1.contains_p (INT (-2))); | |
4347 | } | |
4348 | ||
4349 | // This is impossible, so OP1 should be []. | |
4350 | // signed: [MIN, MIN] = OP1 >> 1 | |
4351 | { | |
4352 | int_range_max lhs (TYPE_MIN_VALUE (integer_type_node), | |
4353 | TYPE_MIN_VALUE (integer_type_node)); | |
4354 | int_range_max one (INT (1), INT (1)); | |
4355 | int_range_max op1; | |
4356 | op_rshift.op1_range (op1, integer_type_node, lhs, one); | |
4357 | ASSERT_TRUE (op1.undefined_p ()); | |
4358 | } | |
4359 | ||
4360 | // signed: ~[-1] = OP1 >> 31 | |
4361 | if (TYPE_PRECISION (integer_type_node) > 31) | |
4362 | { | |
4363 | int_range_max lhs (INT (-1), INT (-1), VR_ANTI_RANGE); | |
4364 | int_range_max shift (INT (31), INT (31)); | |
4365 | int_range_max op1; | |
4366 | op_rshift.op1_range (op1, integer_type_node, lhs, shift); | |
4367 | int_range_max negatives = range_negatives (integer_type_node); | |
4368 | negatives.intersect (op1); | |
4369 | ASSERT_TRUE (negatives.undefined_p ()); | |
4370 | } | |
4371 | } | |
4372 | ||
4373 | static void | |
4374 | range_op_bitwise_and_tests () | |
4375 | { | |
4376 | int_range_max res; | |
4377 | tree min = vrp_val_min (integer_type_node); | |
4378 | tree max = vrp_val_max (integer_type_node); | |
4379 | tree tiny = fold_build2 (PLUS_EXPR, integer_type_node, min, | |
4380 | build_one_cst (integer_type_node)); | |
4381 | int_range_max i1 (tiny, max); | |
4382 | int_range_max i2 (build_int_cst (integer_type_node, 255), | |
4383 | build_int_cst (integer_type_node, 255)); | |
4384 | ||
4385 | // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING | |
4386 | op_bitwise_and.op1_range (res, integer_type_node, i1, i2); | |
4387 | ASSERT_TRUE (res == int_range<1> (integer_type_node)); | |
4388 | ||
4389 | // VARYING = OP1 & 255: OP1 is VARYING | |
4390 | i1 = int_range<1> (integer_type_node); | |
4391 | op_bitwise_and.op1_range (res, integer_type_node, i1, i2); | |
4392 | ASSERT_TRUE (res == int_range<1> (integer_type_node)); | |
46027143 AH |
4393 | |
4394 | // (NONZERO | X) is nonzero. | |
4395 | i1.set_nonzero (integer_type_node); | |
4396 | i2.set_varying (integer_type_node); | |
4397 | op_bitwise_or.fold_range (res, integer_type_node, i1, i2); | |
4398 | ASSERT_TRUE (res.nonzero_p ()); | |
4399 | ||
4400 | // (NEGATIVE | X) is nonzero. | |
4401 | i1 = int_range<1> (INT (-5), INT (-3)); | |
4402 | i2.set_varying (integer_type_node); | |
4403 | op_bitwise_or.fold_range (res, integer_type_node, i1, i2); | |
4404 | ASSERT_FALSE (res.contains_p (INT (0))); | |
b5cff0db AH |
4405 | } |
4406 | ||
ca1f9f22 AM |
4407 | static void |
4408 | range_relational_tests () | |
4409 | { | |
4410 | int_range<2> lhs (unsigned_char_type_node); | |
4411 | int_range<2> op1 (UCHAR (8), UCHAR (10)); | |
4412 | int_range<2> op2 (UCHAR (20), UCHAR (20)); | |
4413 | ||
4414 | // Never wrapping additions mean LHS > OP1. | |
4415 | tree_code code = op_plus.lhs_op1_relation (lhs, op1, op2); | |
4416 | ASSERT_TRUE (code == GT_EXPR); | |
4417 | ||
4418 | // Most wrapping additions mean nothing... | |
4419 | op1 = int_range<2> (UCHAR (8), UCHAR (10)); | |
4420 | op2 = int_range<2> (UCHAR (0), UCHAR (255)); | |
4421 | code = op_plus.lhs_op1_relation (lhs, op1, op2); | |
4422 | ASSERT_TRUE (code == VREL_NONE); | |
4423 | ||
4424 | // However, always wrapping additions mean LHS < OP1. | |
4425 | op1 = int_range<2> (UCHAR (1), UCHAR (255)); | |
4426 | op2 = int_range<2> (UCHAR (255), UCHAR (255)); | |
4427 | code = op_plus.lhs_op1_relation (lhs, op1, op2); | |
4428 | ASSERT_TRUE (code == LT_EXPR); | |
4429 | } | |
4430 | ||
b5cff0db AH |
4431 | void |
4432 | range_op_tests () | |
4433 | { | |
4434 | range_op_rshift_tests (); | |
4435 | range_op_lshift_tests (); | |
4436 | range_op_bitwise_and_tests (); | |
4437 | range_op_cast_tests (); | |
ca1f9f22 | 4438 | range_relational_tests (); |
38a73435 | 4439 | } |
f1471317 AH |
4440 | |
4441 | } // namespace selftest | |
4442 | ||
38a73435 | 4443 | #endif // CHECKING_P |