]>
Commit | Line | Data |
---|---|---|
cca78449 | 1 | /* Support routines for value ranges. |
8d9254fc | 2 | Copyright (C) 2019-2020 Free Software Foundation, Inc. |
4ba9fb0a AH |
3 | Major hacks by Aldy Hernandez <aldyh@redhat.com> and |
4 | Andrew MacLeod <amacleod@redhat.com>. | |
cca78449 AH |
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 "tree.h" | |
27 | #include "gimple.h" | |
28 | #include "ssa.h" | |
29 | #include "tree-pretty-print.h" | |
30 | #include "fold-const.h" | |
31 | ||
4ba9fb0a AH |
32 | // Here we copy between any two irange's. The ranges can be legacy or |
33 | // multi-ranges, and copying between any combination works correctly. | |
34 | ||
35 | irange & | |
36 | irange::operator= (const irange &src) | |
37 | { | |
38 | if (legacy_mode_p () != src.legacy_mode_p ()) | |
39 | { | |
40 | copy_legacy_range (src); | |
41 | return *this; | |
42 | } | |
43 | if (legacy_mode_p ()) | |
44 | { | |
45 | gcc_checking_assert (src.legacy_mode_p ()); | |
46 | m_num_ranges = src.m_num_ranges; | |
47 | m_base[0] = src.m_base[0]; | |
48 | m_base[1] = src.m_base[1]; | |
49 | m_kind = src.m_kind; | |
50 | return *this; | |
51 | } | |
52 | ||
53 | unsigned x; | |
54 | unsigned lim = src.m_num_ranges; | |
55 | if (lim > m_max_ranges) | |
56 | lim = m_max_ranges; | |
57 | ||
58 | for (x = 0; x < lim * 2; ++x) | |
59 | m_base[x] = src.m_base[x]; | |
60 | ||
61 | // If the range didn't fit, the last range should cover the rest. | |
62 | if (lim != src.m_num_ranges) | |
63 | m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1]; | |
64 | ||
65 | m_num_ranges = lim; | |
66 | return *this; | |
67 | } | |
68 | ||
69 | // Return TRUE if range is a multi-range that can be represented as a | |
70 | // VR_ANTI_RANGE. | |
71 | ||
72 | bool | |
73 | irange::maybe_anti_range () const | |
cca78449 | 74 | { |
4ba9fb0a AH |
75 | tree ttype = type (); |
76 | unsigned int precision = TYPE_PRECISION (ttype); | |
77 | signop sign = TYPE_SIGN (ttype); | |
78 | return (num_pairs () > 1 | |
79 | && precision > 1 | |
80 | && lower_bound () == wi::min_value (precision, sign) | |
81 | && upper_bound () == wi::max_value (precision, sign)); | |
cca78449 AH |
82 | } |
83 | ||
4ba9fb0a AH |
84 | // Copy between a legacy and a multi-range, or vice-versa. |
85 | ||
86 | void | |
87 | irange::copy_legacy_range (const irange &src) | |
cca78449 | 88 | { |
4ba9fb0a AH |
89 | gcc_checking_assert (src.legacy_mode_p () != legacy_mode_p ()); |
90 | if (src.undefined_p ()) | |
91 | set_undefined (); | |
92 | else if (src.varying_p ()) | |
93 | set_varying (src.type ()); | |
94 | else if (src.kind () == VR_ANTI_RANGE) | |
95 | set (src.min (), src.max (), VR_ANTI_RANGE); | |
96 | else if (legacy_mode_p () && src.maybe_anti_range ()) | |
97 | { | |
98 | int_range<3> tmp (src); | |
99 | tmp.invert (); | |
100 | set (tmp.min (), wide_int_to_tree (src.type (), tmp.upper_bound (0)), | |
101 | VR_ANTI_RANGE); | |
102 | } | |
103 | else | |
104 | set (src.min (), src.max (), VR_RANGE); | |
cca78449 AH |
105 | } |
106 | ||
4ba9fb0a AH |
107 | // Swap min/max if they are out of order. Return TRUE if further |
108 | // processing of the range is necessary, FALSE otherwise. | |
109 | ||
110 | bool | |
111 | irange::swap_out_of_order_endpoints (tree &min, tree &max, | |
112 | value_range_kind &kind) | |
cca78449 | 113 | { |
4ba9fb0a AH |
114 | /* Wrong order for min and max, to swap them and the VR type we need |
115 | to adjust them. */ | |
116 | if (tree_int_cst_lt (max, min)) | |
117 | { | |
118 | tree one, tmp; | |
119 | ||
120 | /* For one bit precision if max < min, then the swapped | |
121 | range covers all values, so for VR_RANGE it is varying and | |
122 | for VR_ANTI_RANGE empty range, so drop to varying as well. */ | |
123 | if (TYPE_PRECISION (TREE_TYPE (min)) == 1) | |
124 | { | |
125 | set_varying (TREE_TYPE (min)); | |
126 | return false; | |
127 | } | |
128 | ||
129 | one = build_int_cst (TREE_TYPE (min), 1); | |
130 | tmp = int_const_binop (PLUS_EXPR, max, one); | |
131 | max = int_const_binop (MINUS_EXPR, min, one); | |
132 | min = tmp; | |
133 | ||
134 | /* There's one corner case, if we had [C+1, C] before we now have | |
135 | that again. But this represents an empty value range, so drop | |
136 | to varying in this case. */ | |
137 | if (tree_int_cst_lt (max, min)) | |
138 | { | |
139 | set_varying (TREE_TYPE (min)); | |
140 | return false; | |
141 | } | |
142 | kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE; | |
143 | } | |
144 | return true; | |
cca78449 AH |
145 | } |
146 | ||
147 | void | |
4ba9fb0a | 148 | irange::irange_set (tree min, tree max) |
cca78449 | 149 | { |
4ba9fb0a AH |
150 | gcc_checking_assert (!POLY_INT_CST_P (min)); |
151 | gcc_checking_assert (!POLY_INT_CST_P (max)); | |
152 | ||
153 | m_base[0] = min; | |
154 | m_base[1] = max; | |
155 | m_num_ranges = 1; | |
156 | if (flag_checking) | |
157 | verify_range (); | |
cca78449 AH |
158 | } |
159 | ||
160 | void | |
4ba9fb0a | 161 | irange::irange_set_anti_range (tree min, tree max) |
cca78449 | 162 | { |
4ba9fb0a AH |
163 | gcc_checking_assert (!POLY_INT_CST_P (min)); |
164 | gcc_checking_assert (!POLY_INT_CST_P (max)); | |
165 | ||
166 | // set an anti-range | |
167 | tree type = TREE_TYPE (min); | |
168 | signop sign = TYPE_SIGN (type); | |
169 | int_range<2> type_range (type); | |
170 | // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX]. | |
171 | m_num_ranges = 0; | |
172 | wi::overflow_type ovf; | |
173 | ||
174 | wide_int w_min = wi::to_wide (min); | |
175 | if (wi::ne_p (w_min, type_range.lower_bound ())) | |
cca78449 | 176 | { |
4ba9fb0a AH |
177 | wide_int lim1 = wi::sub (w_min, 1, sign, &ovf); |
178 | gcc_checking_assert (ovf != wi::OVF_OVERFLOW); | |
179 | m_base[0] = type_range.tree_lower_bound (0); | |
180 | m_base[1] = wide_int_to_tree (type, lim1); | |
181 | m_num_ranges = 1; | |
cca78449 | 182 | } |
4ba9fb0a AH |
183 | wide_int w_max = wi::to_wide (max); |
184 | if (wi::ne_p (w_max, type_range.upper_bound ())) | |
185 | { | |
186 | wide_int lim2 = wi::add (w_max, 1, sign, &ovf); | |
187 | gcc_checking_assert (ovf != wi::OVF_OVERFLOW); | |
188 | m_base[m_num_ranges * 2] = wide_int_to_tree (type, lim2); | |
189 | m_base[m_num_ranges * 2 + 1] = type_range.tree_upper_bound (0); | |
190 | ++m_num_ranges; | |
191 | } | |
192 | if (flag_checking) | |
193 | verify_range (); | |
cca78449 AH |
194 | } |
195 | ||
196 | /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}. | |
197 | This means adjusting VRTYPE, MIN and MAX representing the case of a | |
198 | wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX] | |
199 | as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges. | |
200 | In corner cases where MAX+1 or MIN-1 wraps this will fall back | |
201 | to varying. | |
202 | This routine exists to ease canonicalization in the case where we | |
203 | extract ranges from var + CST op limit. */ | |
204 | ||
205 | void | |
4ba9fb0a | 206 | irange::set (tree min, tree max, value_range_kind kind) |
cca78449 | 207 | { |
4ba9fb0a AH |
208 | if (!legacy_mode_p ()) |
209 | { | |
210 | if (kind == VR_RANGE) | |
211 | irange_set (min, max); | |
212 | else | |
213 | { | |
214 | gcc_checking_assert (kind == VR_ANTI_RANGE); | |
215 | irange_set_anti_range (min, max); | |
216 | } | |
217 | return; | |
218 | } | |
cca78449 AH |
219 | if (kind == VR_UNDEFINED) |
220 | { | |
221 | set_undefined (); | |
222 | return; | |
223 | } | |
505032d9 RS |
224 | if (kind == VR_RANGE) |
225 | { | |
226 | /* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */ | |
227 | if (POLY_INT_CST_P (min)) | |
228 | { | |
229 | tree type_min = vrp_val_min (TREE_TYPE (min)); | |
230 | widest_int lb | |
231 | = constant_lower_bound_with_limit (wi::to_poly_widest (min), | |
232 | wi::to_widest (type_min)); | |
233 | min = wide_int_to_tree (TREE_TYPE (min), lb); | |
234 | } | |
235 | if (POLY_INT_CST_P (max)) | |
236 | { | |
237 | tree type_max = vrp_val_max (TREE_TYPE (max)); | |
238 | widest_int ub | |
239 | = constant_upper_bound_with_limit (wi::to_poly_widest (max), | |
240 | wi::to_widest (type_max)); | |
241 | max = wide_int_to_tree (TREE_TYPE (max), ub); | |
242 | } | |
243 | } | |
244 | else if (kind != VR_VARYING) | |
245 | { | |
4ba9fb0a AH |
246 | if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max)) |
247 | kind = VR_VARYING; | |
505032d9 | 248 | } |
505032d9 | 249 | if (kind == VR_VARYING) |
cca78449 | 250 | { |
4ba9fb0a | 251 | set_varying (TREE_TYPE (min)); |
cca78449 AH |
252 | return; |
253 | } | |
254 | ||
4ba9fb0a AH |
255 | tree type = TREE_TYPE (min); |
256 | // Nothing to canonicalize for symbolic ranges. | |
cca78449 AH |
257 | if (TREE_CODE (min) != INTEGER_CST |
258 | || TREE_CODE (max) != INTEGER_CST) | |
259 | { | |
260 | m_kind = kind; | |
4ba9fb0a AH |
261 | m_base[0] = min; |
262 | m_base[1] = max; | |
263 | m_num_ranges = 1; | |
cca78449 AH |
264 | return; |
265 | } | |
4ba9fb0a AH |
266 | if (!swap_out_of_order_endpoints (min, max, kind)) |
267 | goto cleanup_set; | |
cca78449 | 268 | |
4ba9fb0a | 269 | // Anti-ranges that can be represented as ranges should be so. |
cca78449 AH |
270 | if (kind == VR_ANTI_RANGE) |
271 | { | |
272 | /* For -fstrict-enums we may receive out-of-range ranges so consider | |
273 | values < -INF and values > INF as -INF/INF as well. */ | |
274 | bool is_min = vrp_val_is_min (min); | |
275 | bool is_max = vrp_val_is_max (max); | |
276 | ||
277 | if (is_min && is_max) | |
278 | { | |
279 | /* We cannot deal with empty ranges, drop to varying. | |
280 | ??? This could be VR_UNDEFINED instead. */ | |
281 | set_varying (type); | |
282 | return; | |
283 | } | |
284 | else if (TYPE_PRECISION (TREE_TYPE (min)) == 1 | |
285 | && (is_min || is_max)) | |
286 | { | |
287 | /* Non-empty boolean ranges can always be represented | |
288 | as a singleton range. */ | |
289 | if (is_min) | |
290 | min = max = vrp_val_max (TREE_TYPE (min)); | |
291 | else | |
292 | min = max = vrp_val_min (TREE_TYPE (min)); | |
293 | kind = VR_RANGE; | |
294 | } | |
295 | else if (is_min) | |
296 | { | |
297 | tree one = build_int_cst (TREE_TYPE (max), 1); | |
298 | min = int_const_binop (PLUS_EXPR, max, one); | |
299 | max = vrp_val_max (TREE_TYPE (max)); | |
300 | kind = VR_RANGE; | |
301 | } | |
302 | else if (is_max) | |
303 | { | |
304 | tree one = build_int_cst (TREE_TYPE (min), 1); | |
305 | max = int_const_binop (MINUS_EXPR, min, one); | |
306 | min = vrp_val_min (TREE_TYPE (min)); | |
307 | kind = VR_RANGE; | |
308 | } | |
309 | } | |
4ba9fb0a AH |
310 | else if (!swap_out_of_order_endpoints (min, max, kind)) |
311 | goto cleanup_set; | |
cca78449 | 312 | |
4ba9fb0a AH |
313 | /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky |
314 | to make sure VRP iteration terminates, otherwise we can get into | |
315 | oscillations. */ | |
316 | if (!normalize_min_max (type, min, max, kind)) | |
317 | { | |
318 | m_kind = kind; | |
319 | m_base[0] = min; | |
320 | m_base[1] = max; | |
321 | m_num_ranges = 1; | |
322 | if (flag_checking) | |
323 | verify_range (); | |
324 | } | |
cca78449 | 325 | |
4ba9fb0a AH |
326 | cleanup_set: |
327 | // Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can | |
328 | // restrict those to a subset of what actually fits in the type. | |
329 | // Instead use the extremes of the type precision | |
cca78449 AH |
330 | unsigned prec = TYPE_PRECISION (type); |
331 | signop sign = TYPE_SIGN (type); | |
332 | if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign)) | |
333 | && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign))) | |
4ba9fb0a AH |
334 | m_kind = VR_VARYING; |
335 | else if (undefined_p ()) | |
336 | m_kind = VR_UNDEFINED; | |
cca78449 | 337 | if (flag_checking) |
4ba9fb0a | 338 | verify_range (); |
cca78449 AH |
339 | } |
340 | ||
341 | /* Check the validity of the range. */ | |
342 | ||
343 | void | |
4ba9fb0a | 344 | irange::verify_range () |
cca78449 | 345 | { |
4ba9fb0a | 346 | if (!legacy_mode_p ()) |
cca78449 | 347 | { |
4ba9fb0a AH |
348 | gcc_checking_assert (m_kind == VR_RANGE); |
349 | for (unsigned i = 0; i < m_num_ranges; ++i) | |
350 | { | |
351 | tree lb = tree_lower_bound (i); | |
352 | tree ub = tree_upper_bound (i); | |
353 | int c = compare_values (lb, ub); | |
354 | gcc_assert (c == 0 || c == -1); | |
355 | } | |
356 | return; | |
357 | } | |
cca78449 | 358 | |
4ba9fb0a AH |
359 | switch (m_kind) |
360 | { | |
cca78449 | 361 | case VR_UNDEFINED: |
4ba9fb0a | 362 | gcc_assert (m_num_ranges == 0); |
cca78449 | 363 | break; |
4ba9fb0a | 364 | |
cca78449 | 365 | case VR_VARYING: |
4ba9fb0a | 366 | gcc_assert (m_num_ranges == 1); |
cca78449 | 367 | break; |
4ba9fb0a AH |
368 | |
369 | case VR_ANTI_RANGE: | |
370 | case VR_RANGE: | |
371 | { | |
372 | gcc_assert (m_num_ranges == 1); | |
373 | int cmp = compare_values (tree_lower_bound (0), tree_upper_bound (0)); | |
374 | gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); | |
375 | return; | |
376 | } | |
377 | ||
cca78449 AH |
378 | default: |
379 | gcc_unreachable (); | |
380 | } | |
381 | } | |
382 | ||
cca78449 | 383 | unsigned |
4ba9fb0a | 384 | irange::legacy_num_pairs () const |
cca78449 | 385 | { |
4ba9fb0a AH |
386 | gcc_checking_assert (legacy_mode_p ()); |
387 | ||
cca78449 AH |
388 | if (undefined_p ()) |
389 | return 0; | |
390 | if (varying_p ()) | |
391 | return 1; | |
4ba9fb0a AH |
392 | // Inlined symbolic_p for performance: |
393 | if (!is_gimple_min_invariant (min ()) || !is_gimple_min_invariant (max ())) | |
6ee86466 AH |
394 | { |
395 | value_range numeric_range (*this); | |
396 | numeric_range.normalize_symbolics (); | |
397 | return numeric_range.num_pairs (); | |
398 | } | |
cca78449 AH |
399 | if (m_kind == VR_ANTI_RANGE) |
400 | { | |
401 | // ~[MIN, X] has one sub-range of [X+1, MAX], and | |
402 | // ~[X, MAX] has one sub-range of [MIN, X-1]. | |
4ba9fb0a | 403 | if (vrp_val_is_min (min ()) || vrp_val_is_max (max ())) |
cca78449 AH |
404 | return 1; |
405 | return 2; | |
406 | } | |
4ba9fb0a | 407 | gcc_checking_assert (m_num_ranges == 1); |
cca78449 AH |
408 | return 1; |
409 | } | |
410 | ||
4ba9fb0a AH |
411 | // Return the lower bound for a sub-range. PAIR is the sub-range in |
412 | // question. | |
cca78449 AH |
413 | |
414 | wide_int | |
4ba9fb0a | 415 | irange::legacy_lower_bound (unsigned pair) const |
cca78449 | 416 | { |
4ba9fb0a | 417 | gcc_checking_assert (legacy_mode_p ()); |
cca78449 | 418 | if (symbolic_p ()) |
6ee86466 AH |
419 | { |
420 | value_range numeric_range (*this); | |
421 | numeric_range.normalize_symbolics (); | |
4ba9fb0a | 422 | return numeric_range.legacy_lower_bound (pair); |
6ee86466 | 423 | } |
cca78449 AH |
424 | gcc_checking_assert (!undefined_p ()); |
425 | gcc_checking_assert (pair + 1 <= num_pairs ()); | |
cca78449 AH |
426 | if (m_kind == VR_ANTI_RANGE) |
427 | { | |
4ba9fb0a AH |
428 | tree typ = type (), t; |
429 | if (pair == 1 || vrp_val_is_min (min ())) | |
430 | t = wide_int_to_tree (typ, wi::to_wide (max ()) + 1); | |
cca78449 AH |
431 | else |
432 | t = vrp_val_min (typ); | |
4ba9fb0a | 433 | return wi::to_wide (t); |
cca78449 | 434 | } |
4ba9fb0a | 435 | return wi::to_wide (tree_lower_bound (pair)); |
cca78449 AH |
436 | } |
437 | ||
4ba9fb0a AH |
438 | // Return the upper bound for a sub-range. PAIR is the sub-range in |
439 | // question. | |
cca78449 AH |
440 | |
441 | wide_int | |
4ba9fb0a | 442 | irange::legacy_upper_bound (unsigned pair) const |
cca78449 | 443 | { |
4ba9fb0a | 444 | gcc_checking_assert (legacy_mode_p ()); |
cca78449 | 445 | if (symbolic_p ()) |
6ee86466 AH |
446 | { |
447 | value_range numeric_range (*this); | |
448 | numeric_range.normalize_symbolics (); | |
4ba9fb0a | 449 | return numeric_range.legacy_upper_bound (pair); |
6ee86466 | 450 | } |
cca78449 AH |
451 | gcc_checking_assert (!undefined_p ()); |
452 | gcc_checking_assert (pair + 1 <= num_pairs ()); | |
cca78449 AH |
453 | if (m_kind == VR_ANTI_RANGE) |
454 | { | |
4ba9fb0a AH |
455 | tree typ = type (), t; |
456 | if (pair == 1 || vrp_val_is_min (min ())) | |
cca78449 AH |
457 | t = vrp_val_max (typ); |
458 | else | |
4ba9fb0a AH |
459 | t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1); |
460 | return wi::to_wide (t); | |
cca78449 | 461 | } |
4ba9fb0a | 462 | return wi::to_wide (tree_upper_bound (pair)); |
cca78449 AH |
463 | } |
464 | ||
465 | bool | |
4ba9fb0a | 466 | irange::legacy_equal_p (const irange &other) const |
cca78449 | 467 | { |
4ba9fb0a | 468 | gcc_checking_assert (legacy_mode_p () && other.legacy_mode_p ()); |
cca78449 | 469 | |
4ba9fb0a AH |
470 | if (m_kind != other.m_kind) |
471 | return false; | |
472 | if (m_kind == VR_UNDEFINED || m_kind == VR_VARYING) | |
473 | return true; | |
474 | return (vrp_operand_equal_p (tree_lower_bound (0), | |
475 | other.tree_lower_bound (0)) | |
476 | && vrp_operand_equal_p (tree_upper_bound (0), | |
477 | other.tree_upper_bound (0))); | |
cca78449 AH |
478 | } |
479 | ||
480 | bool | |
4ba9fb0a | 481 | irange::equal_p (const irange &other) const |
cca78449 | 482 | { |
4ba9fb0a AH |
483 | if (legacy_mode_p ()) |
484 | { | |
485 | if (other.legacy_mode_p ()) | |
486 | return legacy_equal_p (other); | |
487 | value_range tmp (other); | |
488 | return legacy_equal_p (tmp); | |
489 | } | |
490 | if (other.legacy_mode_p ()) | |
491 | { | |
492 | value_range tmp2 (*this); | |
493 | return tmp2.legacy_equal_p (other); | |
494 | } | |
495 | ||
496 | if (m_num_ranges != other.m_num_ranges) | |
497 | return false; | |
498 | ||
499 | for (unsigned i = 0; i < m_num_ranges; ++i) | |
500 | { | |
501 | tree lb = tree_lower_bound (i); | |
502 | tree ub = tree_upper_bound (i); | |
503 | tree lb_other = other.tree_lower_bound (i); | |
504 | tree ub_other = other.tree_upper_bound (i); | |
505 | if (!operand_equal_p (lb, lb_other, 0) | |
506 | || !operand_equal_p (ub, ub_other, 0)) | |
507 | return false; | |
508 | } | |
509 | return true; | |
cca78449 AH |
510 | } |
511 | ||
cca78449 AH |
512 | /* Return TRUE if this is a symbolic range. */ |
513 | ||
514 | bool | |
4ba9fb0a | 515 | irange::symbolic_p () const |
cca78449 AH |
516 | { |
517 | return (!varying_p () | |
518 | && !undefined_p () | |
4ba9fb0a AH |
519 | && (!is_gimple_min_invariant (min ()) |
520 | || !is_gimple_min_invariant (max ()))); | |
cca78449 AH |
521 | } |
522 | ||
523 | /* NOTE: This is not the inverse of symbolic_p because the range | |
524 | could also be varying or undefined. Ideally they should be inverse | |
525 | of each other, with varying only applying to symbolics. Varying of | |
526 | constants would be represented as [-MIN, +MAX]. */ | |
527 | ||
528 | bool | |
4ba9fb0a | 529 | irange::constant_p () const |
cca78449 AH |
530 | { |
531 | return (!varying_p () | |
532 | && !undefined_p () | |
4ba9fb0a AH |
533 | && TREE_CODE (min ()) == INTEGER_CST |
534 | && TREE_CODE (max ()) == INTEGER_CST); | |
cca78449 AH |
535 | } |
536 | ||
4ba9fb0a AH |
537 | /* If range is a singleton, place it in RESULT and return TRUE. |
538 | Note: A singleton can be any gimple invariant, not just constants. | |
539 | So, [&x, &x] counts as a singleton. */ | |
540 | ||
cca78449 | 541 | bool |
4ba9fb0a | 542 | irange::singleton_p (tree *result) const |
cca78449 | 543 | { |
4ba9fb0a AH |
544 | if (!legacy_mode_p ()) |
545 | { | |
546 | if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ()) | |
547 | == wi::to_wide (tree_upper_bound ()))) | |
548 | { | |
549 | if (result) | |
550 | *result = tree_lower_bound (); | |
551 | return true; | |
552 | } | |
553 | return false; | |
554 | } | |
cca78449 AH |
555 | if (m_kind == VR_ANTI_RANGE) |
556 | { | |
557 | if (nonzero_p ()) | |
558 | { | |
559 | if (TYPE_PRECISION (type ()) == 1) | |
560 | { | |
561 | if (result) | |
4ba9fb0a | 562 | *result = max (); |
cca78449 AH |
563 | return true; |
564 | } | |
565 | return false; | |
566 | } | |
567 | if (num_pairs () == 1) | |
568 | { | |
569 | value_range vr0, vr1; | |
4ba9fb0a | 570 | ranges_from_anti_range ((const value_range *) this, &vr0, &vr1); |
cca78449 AH |
571 | return vr0.singleton_p (result); |
572 | } | |
573 | } | |
4ba9fb0a | 574 | // Catches non-numeric extremes as well. |
cca78449 AH |
575 | if (m_kind == VR_RANGE |
576 | && vrp_operand_equal_p (min (), max ()) | |
577 | && is_gimple_min_invariant (min ())) | |
578 | { | |
579 | if (result) | |
580 | *result = min (); | |
581 | return true; | |
582 | } | |
583 | return false; | |
584 | } | |
585 | ||
586 | /* Return 1 if VAL is inside value range. | |
4ba9fb0a | 587 | 0 if VAL is not inside value range. |
cca78449 AH |
588 | -2 if we cannot tell either way. |
589 | ||
590 | Benchmark compile/20001226-1.c compilation time after changing this | |
591 | function. */ | |
592 | ||
593 | int | |
4ba9fb0a | 594 | irange::value_inside_range (tree val) const |
cca78449 | 595 | { |
cca78449 AH |
596 | if (varying_p ()) |
597 | return 1; | |
598 | ||
599 | if (undefined_p ()) | |
600 | return 0; | |
601 | ||
4ba9fb0a AH |
602 | if (!legacy_mode_p () && TREE_CODE (val) == INTEGER_CST) |
603 | return contains_p (val); | |
604 | ||
605 | int cmp1 = operand_less_p (val, min ()); | |
cca78449 AH |
606 | if (cmp1 == -2) |
607 | return -2; | |
608 | if (cmp1 == 1) | |
609 | return m_kind != VR_RANGE; | |
610 | ||
4ba9fb0a | 611 | int cmp2 = operand_less_p (max (), val); |
cca78449 AH |
612 | if (cmp2 == -2) |
613 | return -2; | |
614 | ||
615 | if (m_kind == VR_RANGE) | |
616 | return !cmp2; | |
617 | else | |
618 | return !!cmp2; | |
619 | } | |
620 | ||
621 | /* Return TRUE if it is possible that range contains VAL. */ | |
622 | ||
623 | bool | |
4ba9fb0a | 624 | irange::may_contain_p (tree val) const |
cca78449 AH |
625 | { |
626 | return value_inside_range (val) != 0; | |
627 | } | |
628 | ||
629 | /* Return TRUE if range contains INTEGER_CST. */ | |
4ba9fb0a AH |
630 | /* Return 1 if VAL is inside value range. |
631 | 0 if VAL is not inside value range. | |
632 | ||
633 | Benchmark compile/20001226-1.c compilation time after changing this | |
634 | function. */ | |
635 | ||
cca78449 AH |
636 | |
637 | bool | |
4ba9fb0a | 638 | irange::contains_p (tree cst) const |
cca78449 | 639 | { |
4ba9fb0a AH |
640 | if (undefined_p ()) |
641 | return false; | |
642 | ||
643 | if (legacy_mode_p ()) | |
644 | { | |
645 | gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST); | |
646 | if (symbolic_p ()) | |
647 | { | |
648 | value_range numeric_range (*this); | |
649 | numeric_range.normalize_symbolics (); | |
650 | return numeric_range.contains_p (cst); | |
651 | } | |
652 | return value_inside_range (cst) == 1; | |
653 | } | |
654 | ||
cca78449 | 655 | gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST); |
4ba9fb0a AH |
656 | signop sign = TYPE_SIGN (TREE_TYPE (cst)); |
657 | wide_int v = wi::to_wide (cst); | |
658 | for (unsigned r = 0; r < m_num_ranges; ++r) | |
6ee86466 | 659 | { |
4ba9fb0a AH |
660 | if (wi::lt_p (v, lower_bound (r), sign)) |
661 | return false; | |
662 | if (wi::le_p (v, upper_bound (r), sign)) | |
663 | return true; | |
6ee86466 | 664 | } |
4ba9fb0a AH |
665 | |
666 | return false; | |
cca78449 AH |
667 | } |
668 | ||
4ba9fb0a | 669 | |
cca78449 AH |
670 | /* Normalize addresses into constants. */ |
671 | ||
6ee86466 | 672 | void |
4ba9fb0a | 673 | irange::normalize_addresses () |
cca78449 AH |
674 | { |
675 | if (undefined_p ()) | |
6ee86466 | 676 | return; |
cca78449 AH |
677 | |
678 | if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this)) | |
6ee86466 | 679 | return; |
cca78449 AH |
680 | |
681 | if (!range_includes_zero_p (this)) | |
682 | { | |
4ba9fb0a AH |
683 | gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR |
684 | || TREE_CODE (max ()) == ADDR_EXPR); | |
6ee86466 AH |
685 | set_nonzero (type ()); |
686 | return; | |
cca78449 | 687 | } |
6ee86466 | 688 | set_varying (type ()); |
cca78449 AH |
689 | } |
690 | ||
691 | /* Normalize symbolics and addresses into constants. */ | |
692 | ||
6ee86466 | 693 | void |
4ba9fb0a | 694 | irange::normalize_symbolics () |
cca78449 AH |
695 | { |
696 | if (varying_p () || undefined_p ()) | |
6ee86466 AH |
697 | return; |
698 | ||
cca78449 AH |
699 | tree ttype = type (); |
700 | bool min_symbolic = !is_gimple_min_invariant (min ()); | |
701 | bool max_symbolic = !is_gimple_min_invariant (max ()); | |
702 | if (!min_symbolic && !max_symbolic) | |
6ee86466 AH |
703 | { |
704 | normalize_addresses (); | |
705 | return; | |
706 | } | |
cca78449 AH |
707 | |
708 | // [SYM, SYM] -> VARYING | |
709 | if (min_symbolic && max_symbolic) | |
710 | { | |
6ee86466 AH |
711 | set_varying (ttype); |
712 | return; | |
cca78449 AH |
713 | } |
714 | if (kind () == VR_RANGE) | |
715 | { | |
716 | // [SYM, NUM] -> [-MIN, NUM] | |
717 | if (min_symbolic) | |
6ee86466 AH |
718 | { |
719 | set (vrp_val_min (ttype), max ()); | |
720 | return; | |
721 | } | |
cca78449 | 722 | // [NUM, SYM] -> [NUM, +MAX] |
6ee86466 AH |
723 | set (min (), vrp_val_max (ttype)); |
724 | return; | |
cca78449 AH |
725 | } |
726 | gcc_checking_assert (kind () == VR_ANTI_RANGE); | |
727 | // ~[SYM, NUM] -> [NUM + 1, +MAX] | |
728 | if (min_symbolic) | |
729 | { | |
730 | if (!vrp_val_is_max (max ())) | |
731 | { | |
732 | tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1); | |
6ee86466 AH |
733 | set (n, vrp_val_max (ttype)); |
734 | return; | |
cca78449 | 735 | } |
6ee86466 AH |
736 | set_varying (ttype); |
737 | return; | |
cca78449 AH |
738 | } |
739 | // ~[NUM, SYM] -> [-MIN, NUM - 1] | |
740 | if (!vrp_val_is_min (min ())) | |
741 | { | |
742 | tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1); | |
6ee86466 AH |
743 | set (vrp_val_min (ttype), n); |
744 | return; | |
cca78449 | 745 | } |
6ee86466 | 746 | set_varying (ttype); |
cca78449 AH |
747 | } |
748 | ||
749 | /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and | |
750 | { VR1TYPE, VR0MIN, VR0MAX } and store the result | |
751 | in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest | |
752 | possible such range. The resulting range is not canonicalized. */ | |
753 | ||
754 | static void | |
755 | intersect_ranges (enum value_range_kind *vr0type, | |
756 | tree *vr0min, tree *vr0max, | |
757 | enum value_range_kind vr1type, | |
758 | tree vr1min, tree vr1max) | |
759 | { | |
760 | bool mineq = vrp_operand_equal_p (*vr0min, vr1min); | |
761 | bool maxeq = vrp_operand_equal_p (*vr0max, vr1max); | |
762 | ||
763 | /* [] is vr0, () is vr1 in the following classification comments. */ | |
764 | if (mineq && maxeq) | |
765 | { | |
766 | /* [( )] */ | |
767 | if (*vr0type == vr1type) | |
768 | /* Nothing to do for equal ranges. */ | |
769 | ; | |
770 | else if ((*vr0type == VR_RANGE | |
771 | && vr1type == VR_ANTI_RANGE) | |
772 | || (*vr0type == VR_ANTI_RANGE | |
773 | && vr1type == VR_RANGE)) | |
774 | { | |
775 | /* For anti-range with range intersection the result is empty. */ | |
776 | *vr0type = VR_UNDEFINED; | |
777 | *vr0min = NULL_TREE; | |
778 | *vr0max = NULL_TREE; | |
779 | } | |
780 | else | |
781 | gcc_unreachable (); | |
782 | } | |
783 | else if (operand_less_p (*vr0max, vr1min) == 1 | |
784 | || operand_less_p (vr1max, *vr0min) == 1) | |
785 | { | |
786 | /* [ ] ( ) or ( ) [ ] | |
787 | If the ranges have an empty intersection, the result of the | |
788 | intersect operation is the range for intersecting an | |
789 | anti-range with a range or empty when intersecting two ranges. */ | |
790 | if (*vr0type == VR_RANGE | |
791 | && vr1type == VR_ANTI_RANGE) | |
792 | ; | |
793 | else if (*vr0type == VR_ANTI_RANGE | |
794 | && vr1type == VR_RANGE) | |
795 | { | |
796 | *vr0type = vr1type; | |
797 | *vr0min = vr1min; | |
798 | *vr0max = vr1max; | |
799 | } | |
800 | else if (*vr0type == VR_RANGE | |
801 | && vr1type == VR_RANGE) | |
802 | { | |
803 | *vr0type = VR_UNDEFINED; | |
804 | *vr0min = NULL_TREE; | |
805 | *vr0max = NULL_TREE; | |
806 | } | |
807 | else if (*vr0type == VR_ANTI_RANGE | |
808 | && vr1type == VR_ANTI_RANGE) | |
809 | { | |
810 | /* If the anti-ranges are adjacent to each other merge them. */ | |
811 | if (TREE_CODE (*vr0max) == INTEGER_CST | |
812 | && TREE_CODE (vr1min) == INTEGER_CST | |
813 | && operand_less_p (*vr0max, vr1min) == 1 | |
814 | && integer_onep (int_const_binop (MINUS_EXPR, | |
815 | vr1min, *vr0max))) | |
816 | *vr0max = vr1max; | |
817 | else if (TREE_CODE (vr1max) == INTEGER_CST | |
818 | && TREE_CODE (*vr0min) == INTEGER_CST | |
819 | && operand_less_p (vr1max, *vr0min) == 1 | |
820 | && integer_onep (int_const_binop (MINUS_EXPR, | |
821 | *vr0min, vr1max))) | |
822 | *vr0min = vr1min; | |
823 | /* Else arbitrarily take VR0. */ | |
824 | } | |
825 | } | |
826 | else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1) | |
827 | && (mineq || operand_less_p (*vr0min, vr1min) == 1)) | |
828 | { | |
829 | /* [ ( ) ] or [( ) ] or [ ( )] */ | |
830 | if (*vr0type == VR_RANGE | |
831 | && vr1type == VR_RANGE) | |
832 | { | |
833 | /* If both are ranges the result is the inner one. */ | |
834 | *vr0type = vr1type; | |
835 | *vr0min = vr1min; | |
836 | *vr0max = vr1max; | |
837 | } | |
838 | else if (*vr0type == VR_RANGE | |
839 | && vr1type == VR_ANTI_RANGE) | |
840 | { | |
841 | /* Choose the right gap if the left one is empty. */ | |
842 | if (mineq) | |
843 | { | |
844 | if (TREE_CODE (vr1max) != INTEGER_CST) | |
845 | *vr0min = vr1max; | |
846 | else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1 | |
847 | && !TYPE_UNSIGNED (TREE_TYPE (vr1max))) | |
848 | *vr0min | |
849 | = int_const_binop (MINUS_EXPR, vr1max, | |
850 | build_int_cst (TREE_TYPE (vr1max), -1)); | |
851 | else | |
852 | *vr0min | |
853 | = int_const_binop (PLUS_EXPR, vr1max, | |
854 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
855 | } | |
856 | /* Choose the left gap if the right one is empty. */ | |
857 | else if (maxeq) | |
858 | { | |
859 | if (TREE_CODE (vr1min) != INTEGER_CST) | |
860 | *vr0max = vr1min; | |
861 | else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1 | |
862 | && !TYPE_UNSIGNED (TREE_TYPE (vr1min))) | |
863 | *vr0max | |
864 | = int_const_binop (PLUS_EXPR, vr1min, | |
865 | build_int_cst (TREE_TYPE (vr1min), -1)); | |
866 | else | |
867 | *vr0max | |
868 | = int_const_binop (MINUS_EXPR, vr1min, | |
869 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
870 | } | |
871 | /* Choose the anti-range if the range is effectively varying. */ | |
872 | else if (vrp_val_is_min (*vr0min) | |
873 | && vrp_val_is_max (*vr0max)) | |
874 | { | |
875 | *vr0type = vr1type; | |
876 | *vr0min = vr1min; | |
877 | *vr0max = vr1max; | |
878 | } | |
879 | /* Else choose the range. */ | |
880 | } | |
881 | else if (*vr0type == VR_ANTI_RANGE | |
882 | && vr1type == VR_ANTI_RANGE) | |
883 | /* If both are anti-ranges the result is the outer one. */ | |
884 | ; | |
885 | else if (*vr0type == VR_ANTI_RANGE | |
886 | && vr1type == VR_RANGE) | |
887 | { | |
888 | /* The intersection is empty. */ | |
889 | *vr0type = VR_UNDEFINED; | |
890 | *vr0min = NULL_TREE; | |
891 | *vr0max = NULL_TREE; | |
892 | } | |
893 | else | |
894 | gcc_unreachable (); | |
895 | } | |
896 | else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1) | |
897 | && (mineq || operand_less_p (vr1min, *vr0min) == 1)) | |
898 | { | |
899 | /* ( [ ] ) or ([ ] ) or ( [ ]) */ | |
900 | if (*vr0type == VR_RANGE | |
901 | && vr1type == VR_RANGE) | |
902 | /* Choose the inner range. */ | |
903 | ; | |
904 | else if (*vr0type == VR_ANTI_RANGE | |
905 | && vr1type == VR_RANGE) | |
906 | { | |
907 | /* Choose the right gap if the left is empty. */ | |
908 | if (mineq) | |
909 | { | |
910 | *vr0type = VR_RANGE; | |
911 | if (TREE_CODE (*vr0max) != INTEGER_CST) | |
912 | *vr0min = *vr0max; | |
913 | else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1 | |
914 | && !TYPE_UNSIGNED (TREE_TYPE (*vr0max))) | |
915 | *vr0min | |
916 | = int_const_binop (MINUS_EXPR, *vr0max, | |
917 | build_int_cst (TREE_TYPE (*vr0max), -1)); | |
918 | else | |
919 | *vr0min | |
920 | = int_const_binop (PLUS_EXPR, *vr0max, | |
921 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
922 | *vr0max = vr1max; | |
923 | } | |
924 | /* Choose the left gap if the right is empty. */ | |
925 | else if (maxeq) | |
926 | { | |
927 | *vr0type = VR_RANGE; | |
928 | if (TREE_CODE (*vr0min) != INTEGER_CST) | |
929 | *vr0max = *vr0min; | |
930 | else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1 | |
931 | && !TYPE_UNSIGNED (TREE_TYPE (*vr0min))) | |
932 | *vr0max | |
933 | = int_const_binop (PLUS_EXPR, *vr0min, | |
934 | build_int_cst (TREE_TYPE (*vr0min), -1)); | |
935 | else | |
936 | *vr0max | |
937 | = int_const_binop (MINUS_EXPR, *vr0min, | |
938 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
939 | *vr0min = vr1min; | |
940 | } | |
941 | /* Choose the anti-range if the range is effectively varying. */ | |
942 | else if (vrp_val_is_min (vr1min) | |
943 | && vrp_val_is_max (vr1max)) | |
944 | ; | |
945 | /* Choose the anti-range if it is ~[0,0], that range is special | |
946 | enough to special case when vr1's range is relatively wide. | |
947 | At least for types bigger than int - this covers pointers | |
948 | and arguments to functions like ctz. */ | |
949 | else if (*vr0min == *vr0max | |
950 | && integer_zerop (*vr0min) | |
951 | && ((TYPE_PRECISION (TREE_TYPE (*vr0min)) | |
952 | >= TYPE_PRECISION (integer_type_node)) | |
953 | || POINTER_TYPE_P (TREE_TYPE (*vr0min))) | |
954 | && TREE_CODE (vr1max) == INTEGER_CST | |
955 | && TREE_CODE (vr1min) == INTEGER_CST | |
956 | && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min)) | |
957 | < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2)) | |
958 | ; | |
959 | /* Else choose the range. */ | |
960 | else | |
961 | { | |
962 | *vr0type = vr1type; | |
963 | *vr0min = vr1min; | |
964 | *vr0max = vr1max; | |
965 | } | |
966 | } | |
967 | else if (*vr0type == VR_ANTI_RANGE | |
968 | && vr1type == VR_ANTI_RANGE) | |
969 | { | |
970 | /* If both are anti-ranges the result is the outer one. */ | |
971 | *vr0type = vr1type; | |
972 | *vr0min = vr1min; | |
973 | *vr0max = vr1max; | |
974 | } | |
975 | else if (vr1type == VR_ANTI_RANGE | |
976 | && *vr0type == VR_RANGE) | |
977 | { | |
978 | /* The intersection is empty. */ | |
979 | *vr0type = VR_UNDEFINED; | |
980 | *vr0min = NULL_TREE; | |
981 | *vr0max = NULL_TREE; | |
982 | } | |
983 | else | |
984 | gcc_unreachable (); | |
985 | } | |
986 | else if ((operand_less_p (vr1min, *vr0max) == 1 | |
987 | || operand_equal_p (vr1min, *vr0max, 0)) | |
988 | && operand_less_p (*vr0min, vr1min) == 1) | |
989 | { | |
990 | /* [ ( ] ) or [ ]( ) */ | |
991 | if (*vr0type == VR_ANTI_RANGE | |
992 | && vr1type == VR_ANTI_RANGE) | |
993 | *vr0max = vr1max; | |
994 | else if (*vr0type == VR_RANGE | |
995 | && vr1type == VR_RANGE) | |
996 | *vr0min = vr1min; | |
997 | else if (*vr0type == VR_RANGE | |
998 | && vr1type == VR_ANTI_RANGE) | |
999 | { | |
1000 | if (TREE_CODE (vr1min) == INTEGER_CST) | |
1001 | *vr0max = int_const_binop (MINUS_EXPR, vr1min, | |
1002 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
1003 | else | |
1004 | *vr0max = vr1min; | |
1005 | } | |
1006 | else if (*vr0type == VR_ANTI_RANGE | |
1007 | && vr1type == VR_RANGE) | |
1008 | { | |
1009 | *vr0type = VR_RANGE; | |
1010 | if (TREE_CODE (*vr0max) == INTEGER_CST) | |
1011 | *vr0min = int_const_binop (PLUS_EXPR, *vr0max, | |
1012 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
1013 | else | |
1014 | *vr0min = *vr0max; | |
1015 | *vr0max = vr1max; | |
1016 | } | |
1017 | else | |
1018 | gcc_unreachable (); | |
1019 | } | |
1020 | else if ((operand_less_p (*vr0min, vr1max) == 1 | |
1021 | || operand_equal_p (*vr0min, vr1max, 0)) | |
1022 | && operand_less_p (vr1min, *vr0min) == 1) | |
1023 | { | |
1024 | /* ( [ ) ] or ( )[ ] */ | |
1025 | if (*vr0type == VR_ANTI_RANGE | |
1026 | && vr1type == VR_ANTI_RANGE) | |
1027 | *vr0min = vr1min; | |
1028 | else if (*vr0type == VR_RANGE | |
1029 | && vr1type == VR_RANGE) | |
1030 | *vr0max = vr1max; | |
1031 | else if (*vr0type == VR_RANGE | |
1032 | && vr1type == VR_ANTI_RANGE) | |
1033 | { | |
1034 | if (TREE_CODE (vr1max) == INTEGER_CST) | |
1035 | *vr0min = int_const_binop (PLUS_EXPR, vr1max, | |
1036 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
1037 | else | |
1038 | *vr0min = vr1max; | |
1039 | } | |
1040 | else if (*vr0type == VR_ANTI_RANGE | |
1041 | && vr1type == VR_RANGE) | |
1042 | { | |
1043 | *vr0type = VR_RANGE; | |
1044 | if (TREE_CODE (*vr0min) == INTEGER_CST) | |
1045 | *vr0max = int_const_binop (MINUS_EXPR, *vr0min, | |
1046 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
1047 | else | |
1048 | *vr0max = *vr0min; | |
1049 | *vr0min = vr1min; | |
1050 | } | |
1051 | else | |
1052 | gcc_unreachable (); | |
1053 | } | |
1054 | ||
1055 | /* If we know the intersection is empty, there's no need to | |
1056 | conservatively add anything else to the set. */ | |
1057 | if (*vr0type == VR_UNDEFINED) | |
1058 | return; | |
1059 | ||
1060 | /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as | |
1061 | result for the intersection. That's always a conservative | |
1062 | correct estimate unless VR1 is a constant singleton range | |
1063 | in which case we choose that. */ | |
1064 | if (vr1type == VR_RANGE | |
1065 | && is_gimple_min_invariant (vr1min) | |
1066 | && vrp_operand_equal_p (vr1min, vr1max)) | |
1067 | { | |
1068 | *vr0type = vr1type; | |
1069 | *vr0min = vr1min; | |
1070 | *vr0max = vr1max; | |
1071 | } | |
1072 | } | |
1073 | ||
1074 | /* Helper for the intersection operation for value ranges. Given two | |
4ba9fb0a AH |
1075 | ranges VR0 and VR1, set VR0 to the intersection of both ranges. |
1076 | This may not be the smallest possible such range. */ | |
cca78449 | 1077 | |
4ba9fb0a AH |
1078 | void |
1079 | irange::legacy_intersect (irange *vr0, const irange *vr1) | |
cca78449 AH |
1080 | { |
1081 | /* If either range is VR_VARYING the other one wins. */ | |
1082 | if (vr1->varying_p ()) | |
4ba9fb0a | 1083 | return; |
cca78449 | 1084 | if (vr0->varying_p ()) |
4ba9fb0a AH |
1085 | { |
1086 | /* Avoid the full copy if we already know both sides are simple | |
1087 | and can be trivially copied. */ | |
1088 | if (vr1->legacy_mode_p ()) | |
1089 | { | |
1090 | vr0->set (vr1->min (), vr1->max (), vr1->kind ()); | |
1091 | return; | |
1092 | } | |
1093 | *vr0 = *vr1; | |
1094 | return; | |
1095 | } | |
cca78449 AH |
1096 | |
1097 | /* When either range is VR_UNDEFINED the resulting range is | |
1098 | VR_UNDEFINED, too. */ | |
1099 | if (vr0->undefined_p ()) | |
4ba9fb0a | 1100 | return; |
cca78449 | 1101 | if (vr1->undefined_p ()) |
4ba9fb0a AH |
1102 | { |
1103 | vr0->set_undefined (); | |
1104 | return; | |
1105 | } | |
cca78449 AH |
1106 | |
1107 | value_range_kind vr0kind = vr0->kind (); | |
1108 | tree vr0min = vr0->min (); | |
1109 | tree vr0max = vr0->max (); | |
4ba9fb0a AH |
1110 | /* Handle multi-ranges that can be represented as anti-ranges. */ |
1111 | if (!vr1->legacy_mode_p () && vr1->maybe_anti_range ()) | |
1112 | { | |
1113 | int_range<3> tmp (*vr1); | |
1114 | tmp.invert (); | |
1115 | intersect_ranges (&vr0kind, &vr0min, &vr0max, | |
1116 | VR_ANTI_RANGE, tmp.min (), tmp.max ()); | |
1117 | } | |
1118 | else | |
1119 | intersect_ranges (&vr0kind, &vr0min, &vr0max, | |
1120 | vr1->kind (), vr1->min (), vr1->max ()); | |
1121 | ||
cca78449 | 1122 | /* Make sure to canonicalize the result though as the inversion of a |
4ba9fb0a | 1123 | VR_RANGE can still be a VR_RANGE. */ |
cca78449 | 1124 | if (vr0kind == VR_UNDEFINED) |
4ba9fb0a | 1125 | vr0->set_undefined (); |
cca78449 | 1126 | else if (vr0kind == VR_VARYING) |
4ba9fb0a AH |
1127 | { |
1128 | /* If we failed, use the original VR0. */ | |
1129 | return; | |
1130 | } | |
cca78449 | 1131 | else |
4ba9fb0a | 1132 | vr0->set (vr0min, vr0max, vr0kind); |
cca78449 AH |
1133 | } |
1134 | ||
1135 | /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and | |
1136 | { VR1TYPE, VR0MIN, VR0MAX } and store the result | |
1137 | in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest | |
1138 | possible such range. The resulting range is not canonicalized. */ | |
1139 | ||
1140 | static void | |
1141 | union_ranges (enum value_range_kind *vr0type, | |
1142 | tree *vr0min, tree *vr0max, | |
1143 | enum value_range_kind vr1type, | |
1144 | tree vr1min, tree vr1max) | |
1145 | { | |
1146 | int cmpmin = compare_values (*vr0min, vr1min); | |
1147 | int cmpmax = compare_values (*vr0max, vr1max); | |
1148 | bool mineq = cmpmin == 0; | |
1149 | bool maxeq = cmpmax == 0; | |
1150 | ||
1151 | /* [] is vr0, () is vr1 in the following classification comments. */ | |
1152 | if (mineq && maxeq) | |
1153 | { | |
1154 | /* [( )] */ | |
1155 | if (*vr0type == vr1type) | |
1156 | /* Nothing to do for equal ranges. */ | |
1157 | ; | |
1158 | else if ((*vr0type == VR_RANGE | |
1159 | && vr1type == VR_ANTI_RANGE) | |
1160 | || (*vr0type == VR_ANTI_RANGE | |
1161 | && vr1type == VR_RANGE)) | |
1162 | { | |
1163 | /* For anti-range with range union the result is varying. */ | |
1164 | goto give_up; | |
1165 | } | |
1166 | else | |
1167 | gcc_unreachable (); | |
1168 | } | |
1169 | else if (operand_less_p (*vr0max, vr1min) == 1 | |
1170 | || operand_less_p (vr1max, *vr0min) == 1) | |
1171 | { | |
1172 | /* [ ] ( ) or ( ) [ ] | |
1173 | If the ranges have an empty intersection, result of the union | |
1174 | operation is the anti-range or if both are anti-ranges | |
1175 | it covers all. */ | |
1176 | if (*vr0type == VR_ANTI_RANGE | |
1177 | && vr1type == VR_ANTI_RANGE) | |
1178 | goto give_up; | |
1179 | else if (*vr0type == VR_ANTI_RANGE | |
1180 | && vr1type == VR_RANGE) | |
1181 | ; | |
1182 | else if (*vr0type == VR_RANGE | |
1183 | && vr1type == VR_ANTI_RANGE) | |
1184 | { | |
1185 | *vr0type = vr1type; | |
1186 | *vr0min = vr1min; | |
1187 | *vr0max = vr1max; | |
1188 | } | |
1189 | else if (*vr0type == VR_RANGE | |
1190 | && vr1type == VR_RANGE) | |
1191 | { | |
1192 | /* The result is the convex hull of both ranges. */ | |
1193 | if (operand_less_p (*vr0max, vr1min) == 1) | |
1194 | { | |
1195 | /* If the result can be an anti-range, create one. */ | |
1196 | if (TREE_CODE (*vr0max) == INTEGER_CST | |
1197 | && TREE_CODE (vr1min) == INTEGER_CST | |
1198 | && vrp_val_is_min (*vr0min) | |
1199 | && vrp_val_is_max (vr1max)) | |
1200 | { | |
1201 | tree min = int_const_binop (PLUS_EXPR, | |
1202 | *vr0max, | |
1203 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
1204 | tree max = int_const_binop (MINUS_EXPR, | |
1205 | vr1min, | |
1206 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
1207 | if (!operand_less_p (max, min)) | |
1208 | { | |
1209 | *vr0type = VR_ANTI_RANGE; | |
1210 | *vr0min = min; | |
1211 | *vr0max = max; | |
1212 | } | |
1213 | else | |
1214 | *vr0max = vr1max; | |
1215 | } | |
1216 | else | |
1217 | *vr0max = vr1max; | |
1218 | } | |
1219 | else | |
1220 | { | |
1221 | /* If the result can be an anti-range, create one. */ | |
1222 | if (TREE_CODE (vr1max) == INTEGER_CST | |
1223 | && TREE_CODE (*vr0min) == INTEGER_CST | |
1224 | && vrp_val_is_min (vr1min) | |
1225 | && vrp_val_is_max (*vr0max)) | |
1226 | { | |
1227 | tree min = int_const_binop (PLUS_EXPR, | |
1228 | vr1max, | |
1229 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
1230 | tree max = int_const_binop (MINUS_EXPR, | |
1231 | *vr0min, | |
1232 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
1233 | if (!operand_less_p (max, min)) | |
1234 | { | |
1235 | *vr0type = VR_ANTI_RANGE; | |
1236 | *vr0min = min; | |
1237 | *vr0max = max; | |
1238 | } | |
1239 | else | |
1240 | *vr0min = vr1min; | |
1241 | } | |
1242 | else | |
1243 | *vr0min = vr1min; | |
1244 | } | |
1245 | } | |
1246 | else | |
1247 | gcc_unreachable (); | |
1248 | } | |
1249 | else if ((maxeq || cmpmax == 1) | |
1250 | && (mineq || cmpmin == -1)) | |
1251 | { | |
1252 | /* [ ( ) ] or [( ) ] or [ ( )] */ | |
1253 | if (*vr0type == VR_RANGE | |
1254 | && vr1type == VR_RANGE) | |
1255 | ; | |
1256 | else if (*vr0type == VR_ANTI_RANGE | |
1257 | && vr1type == VR_ANTI_RANGE) | |
1258 | { | |
1259 | *vr0type = vr1type; | |
1260 | *vr0min = vr1min; | |
1261 | *vr0max = vr1max; | |
1262 | } | |
1263 | else if (*vr0type == VR_ANTI_RANGE | |
1264 | && vr1type == VR_RANGE) | |
1265 | { | |
1266 | /* Arbitrarily choose the right or left gap. */ | |
1267 | if (!mineq && TREE_CODE (vr1min) == INTEGER_CST) | |
1268 | *vr0max = int_const_binop (MINUS_EXPR, vr1min, | |
1269 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
1270 | else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST) | |
1271 | *vr0min = int_const_binop (PLUS_EXPR, vr1max, | |
1272 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
1273 | else | |
1274 | goto give_up; | |
1275 | } | |
1276 | else if (*vr0type == VR_RANGE | |
1277 | && vr1type == VR_ANTI_RANGE) | |
1278 | /* The result covers everything. */ | |
1279 | goto give_up; | |
1280 | else | |
1281 | gcc_unreachable (); | |
1282 | } | |
1283 | else if ((maxeq || cmpmax == -1) | |
1284 | && (mineq || cmpmin == 1)) | |
1285 | { | |
1286 | /* ( [ ] ) or ([ ] ) or ( [ ]) */ | |
1287 | if (*vr0type == VR_RANGE | |
1288 | && vr1type == VR_RANGE) | |
1289 | { | |
1290 | *vr0type = vr1type; | |
1291 | *vr0min = vr1min; | |
1292 | *vr0max = vr1max; | |
1293 | } | |
1294 | else if (*vr0type == VR_ANTI_RANGE | |
1295 | && vr1type == VR_ANTI_RANGE) | |
1296 | ; | |
1297 | else if (*vr0type == VR_RANGE | |
1298 | && vr1type == VR_ANTI_RANGE) | |
1299 | { | |
1300 | *vr0type = VR_ANTI_RANGE; | |
1301 | if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST) | |
1302 | { | |
1303 | *vr0max = int_const_binop (MINUS_EXPR, *vr0min, | |
1304 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
1305 | *vr0min = vr1min; | |
1306 | } | |
1307 | else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST) | |
1308 | { | |
1309 | *vr0min = int_const_binop (PLUS_EXPR, *vr0max, | |
1310 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
1311 | *vr0max = vr1max; | |
1312 | } | |
1313 | else | |
1314 | goto give_up; | |
1315 | } | |
1316 | else if (*vr0type == VR_ANTI_RANGE | |
1317 | && vr1type == VR_RANGE) | |
1318 | /* The result covers everything. */ | |
1319 | goto give_up; | |
1320 | else | |
1321 | gcc_unreachable (); | |
1322 | } | |
1323 | else if (cmpmin == -1 | |
1324 | && cmpmax == -1 | |
1325 | && (operand_less_p (vr1min, *vr0max) == 1 | |
1326 | || operand_equal_p (vr1min, *vr0max, 0))) | |
1327 | { | |
1328 | /* [ ( ] ) or [ ]( ) */ | |
1329 | if (*vr0type == VR_RANGE | |
1330 | && vr1type == VR_RANGE) | |
1331 | *vr0max = vr1max; | |
1332 | else if (*vr0type == VR_ANTI_RANGE | |
1333 | && vr1type == VR_ANTI_RANGE) | |
1334 | *vr0min = vr1min; | |
1335 | else if (*vr0type == VR_ANTI_RANGE | |
1336 | && vr1type == VR_RANGE) | |
1337 | { | |
1338 | if (TREE_CODE (vr1min) == INTEGER_CST) | |
1339 | *vr0max = int_const_binop (MINUS_EXPR, vr1min, | |
1340 | build_int_cst (TREE_TYPE (vr1min), 1)); | |
1341 | else | |
1342 | goto give_up; | |
1343 | } | |
1344 | else if (*vr0type == VR_RANGE | |
1345 | && vr1type == VR_ANTI_RANGE) | |
1346 | { | |
1347 | if (TREE_CODE (*vr0max) == INTEGER_CST) | |
1348 | { | |
1349 | *vr0type = vr1type; | |
1350 | *vr0min = int_const_binop (PLUS_EXPR, *vr0max, | |
1351 | build_int_cst (TREE_TYPE (*vr0max), 1)); | |
1352 | *vr0max = vr1max; | |
1353 | } | |
1354 | else | |
1355 | goto give_up; | |
1356 | } | |
1357 | else | |
1358 | gcc_unreachable (); | |
1359 | } | |
1360 | else if (cmpmin == 1 | |
1361 | && cmpmax == 1 | |
1362 | && (operand_less_p (*vr0min, vr1max) == 1 | |
1363 | || operand_equal_p (*vr0min, vr1max, 0))) | |
1364 | { | |
1365 | /* ( [ ) ] or ( )[ ] */ | |
1366 | if (*vr0type == VR_RANGE | |
1367 | && vr1type == VR_RANGE) | |
1368 | *vr0min = vr1min; | |
1369 | else if (*vr0type == VR_ANTI_RANGE | |
1370 | && vr1type == VR_ANTI_RANGE) | |
1371 | *vr0max = vr1max; | |
1372 | else if (*vr0type == VR_ANTI_RANGE | |
1373 | && vr1type == VR_RANGE) | |
1374 | { | |
1375 | if (TREE_CODE (vr1max) == INTEGER_CST) | |
1376 | *vr0min = int_const_binop (PLUS_EXPR, vr1max, | |
1377 | build_int_cst (TREE_TYPE (vr1max), 1)); | |
1378 | else | |
1379 | goto give_up; | |
1380 | } | |
1381 | else if (*vr0type == VR_RANGE | |
1382 | && vr1type == VR_ANTI_RANGE) | |
1383 | { | |
1384 | if (TREE_CODE (*vr0min) == INTEGER_CST) | |
1385 | { | |
1386 | *vr0type = vr1type; | |
1387 | *vr0max = int_const_binop (MINUS_EXPR, *vr0min, | |
1388 | build_int_cst (TREE_TYPE (*vr0min), 1)); | |
1389 | *vr0min = vr1min; | |
1390 | } | |
1391 | else | |
1392 | goto give_up; | |
1393 | } | |
1394 | else | |
1395 | gcc_unreachable (); | |
1396 | } | |
1397 | else | |
1398 | goto give_up; | |
1399 | ||
1400 | return; | |
1401 | ||
1402 | give_up: | |
1403 | *vr0type = VR_VARYING; | |
1404 | *vr0min = NULL_TREE; | |
1405 | *vr0max = NULL_TREE; | |
1406 | } | |
1407 | ||
4ba9fb0a AH |
1408 | /* Helper for meet operation for value ranges. Given two ranges VR0 |
1409 | and VR1, set VR0 to the union of both ranges. This may not be the | |
cca78449 AH |
1410 | smallest possible such range. */ |
1411 | ||
4ba9fb0a AH |
1412 | void |
1413 | irange::legacy_union (irange *vr0, const irange *vr1) | |
cca78449 AH |
1414 | { |
1415 | /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */ | |
1416 | if (vr1->undefined_p () | |
1417 | || vr0->varying_p ()) | |
4ba9fb0a | 1418 | return; |
cca78449 AH |
1419 | |
1420 | /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */ | |
4ba9fb0a AH |
1421 | if (vr0->undefined_p ()) |
1422 | { | |
1423 | /* Avoid the full copy if we already know both sides are simple | |
1424 | and can be trivially copied. */ | |
1425 | if (vr1->legacy_mode_p ()) | |
1426 | { | |
1427 | vr0->set (vr1->min (), vr1->max (), vr1->kind ()); | |
1428 | return; | |
1429 | } | |
1430 | *vr0 = *vr1; | |
1431 | return; | |
1432 | } | |
1433 | if (vr1->varying_p ()) | |
1434 | { | |
1435 | vr0->set_varying (vr1->type ()); | |
1436 | return; | |
1437 | } | |
cca78449 AH |
1438 | |
1439 | value_range_kind vr0kind = vr0->kind (); | |
1440 | tree vr0min = vr0->min (); | |
1441 | tree vr0max = vr0->max (); | |
4ba9fb0a AH |
1442 | /* Handle multi-ranges that can be represented as anti-ranges. */ |
1443 | if (!vr1->legacy_mode_p () && vr1->maybe_anti_range ()) | |
1444 | { | |
1445 | int_range<3> tmp (*vr1); | |
1446 | tmp.invert (); | |
1447 | union_ranges (&vr0kind, &vr0min, &vr0max, | |
1448 | VR_ANTI_RANGE, tmp.min (), tmp.max ()); | |
1449 | } | |
1450 | else | |
1451 | union_ranges (&vr0kind, &vr0min, &vr0max, | |
1452 | vr1->kind (), vr1->min (), vr1->max ()); | |
cca78449 | 1453 | |
cca78449 | 1454 | if (vr0kind == VR_UNDEFINED) |
4ba9fb0a | 1455 | vr0->set_undefined (); |
cca78449 | 1456 | else if (vr0kind == VR_VARYING) |
cca78449 | 1457 | { |
4ba9fb0a AH |
1458 | /* Failed to find an efficient meet. Before giving up and |
1459 | setting the result to VARYING, see if we can at least derive | |
1460 | a non-zero range. */ | |
1461 | if (range_includes_zero_p (vr0) == 0 | |
1462 | && range_includes_zero_p (vr1) == 0) | |
1463 | vr0->set_nonzero (vr0->type ()); | |
1464 | else | |
1465 | vr0->set_varying (vr0->type ()); | |
cca78449 | 1466 | } |
4ba9fb0a AH |
1467 | else |
1468 | vr0->set (vr0min, vr0max, vr0kind); | |
cca78449 AH |
1469 | } |
1470 | ||
1471 | /* Meet operation for value ranges. Given two value ranges VR0 and | |
1472 | VR1, store in VR0 a range that contains both VR0 and VR1. This | |
1473 | may not be the smallest possible such range. */ | |
1474 | ||
1475 | void | |
4ba9fb0a | 1476 | irange::union_ (const irange *other) |
cca78449 | 1477 | { |
4ba9fb0a | 1478 | if (legacy_mode_p ()) |
cca78449 | 1479 | { |
4ba9fb0a AH |
1480 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1481 | { | |
1482 | fprintf (dump_file, "Meeting\n "); | |
1483 | dump_value_range (dump_file, this); | |
1484 | fprintf (dump_file, "\nand\n "); | |
1485 | dump_value_range (dump_file, other); | |
1486 | fprintf (dump_file, "\n"); | |
1487 | } | |
cca78449 | 1488 | |
4ba9fb0a | 1489 | legacy_union (this, other); |
cca78449 | 1490 | |
4ba9fb0a AH |
1491 | if (dump_file && (dump_flags & TDF_DETAILS)) |
1492 | { | |
1493 | fprintf (dump_file, "to\n "); | |
1494 | dump_value_range (dump_file, this); | |
1495 | fprintf (dump_file, "\n"); | |
1496 | } | |
1497 | return; | |
1498 | } | |
1499 | ||
1500 | if (other->legacy_mode_p ()) | |
cca78449 | 1501 | { |
4ba9fb0a AH |
1502 | int_range<2> wider; |
1503 | wider = *other; | |
1504 | irange_union (wider); | |
cca78449 | 1505 | } |
4ba9fb0a AH |
1506 | else |
1507 | irange_union (*other); | |
cca78449 AH |
1508 | } |
1509 | ||
cca78449 | 1510 | void |
4ba9fb0a | 1511 | irange::intersect (const irange *other) |
cca78449 | 1512 | { |
4ba9fb0a AH |
1513 | if (legacy_mode_p ()) |
1514 | { | |
1515 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1516 | { | |
1517 | fprintf (dump_file, "Intersecting\n "); | |
1518 | dump_value_range (dump_file, this); | |
1519 | fprintf (dump_file, "\nand\n "); | |
1520 | dump_value_range (dump_file, other); | |
1521 | fprintf (dump_file, "\n"); | |
1522 | } | |
1523 | ||
1524 | legacy_intersect (this, other); | |
1525 | ||
1526 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1527 | { | |
1528 | fprintf (dump_file, "to\n "); | |
1529 | dump_value_range (dump_file, this); | |
1530 | fprintf (dump_file, "\n"); | |
1531 | } | |
1532 | return; | |
1533 | } | |
1534 | ||
1535 | if (other->legacy_mode_p ()) | |
1536 | { | |
1537 | int_range<2> wider; | |
1538 | wider = *other; | |
1539 | irange_intersect (wider); | |
1540 | } | |
1541 | else | |
1542 | irange_intersect (*other); | |
cca78449 AH |
1543 | } |
1544 | ||
4ba9fb0a AH |
1545 | // union_ for multi-ranges. |
1546 | ||
cca78449 | 1547 | void |
4ba9fb0a | 1548 | irange::irange_union (const irange &r) |
cca78449 | 1549 | { |
4ba9fb0a AH |
1550 | gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); |
1551 | ||
1552 | if (r.undefined_p () || varying_p ()) | |
1553 | return; | |
1554 | ||
1555 | if (undefined_p () || r.varying_p ()) | |
cca78449 | 1556 | { |
4ba9fb0a AH |
1557 | operator= (r); |
1558 | return; | |
cca78449 AH |
1559 | } |
1560 | ||
4ba9fb0a AH |
1561 | // Do not worry about merging and such by reserving twice as many |
1562 | // pairs as needed, and then simply sort the 2 ranges into this | |
1563 | // intermediate form. | |
1564 | // | |
1565 | // The intermediate result will have the property that the beginning | |
1566 | // of each range is <= the beginning of the next range. There may | |
1567 | // be overlapping ranges at this point. I.e. this would be valid | |
1568 | // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this | |
1569 | // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r, | |
1570 | // the merge is performed. | |
1571 | // | |
1572 | // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp] | |
1573 | tree ttype = r.type (); | |
1574 | signop sign = TYPE_SIGN (ttype); | |
1575 | ||
1576 | auto_vec<tree, 20> res; | |
1577 | wide_int u1 ; | |
1578 | wi::overflow_type ovf; | |
1579 | unsigned i = 0, j = 0, k = 0; | |
1580 | ||
1581 | while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2) | |
1582 | { | |
1583 | // lower of Xi and Xj is the lowest point. | |
1584 | if (wi::le_p (wi::to_wide (m_base[i]), wi::to_wide (r.m_base[j]), sign)) | |
1585 | { | |
1586 | res.safe_push (m_base[i]); | |
1587 | res.safe_push (m_base[i + 1]); | |
1588 | k += 2; | |
1589 | i += 2; | |
1590 | } | |
1591 | else | |
1592 | { | |
1593 | res.safe_push (r.m_base[j]); | |
1594 | res.safe_push (r.m_base[j + 1]); | |
1595 | k += 2; | |
1596 | j += 2; | |
1597 | } | |
1598 | } | |
1599 | for ( ; i < m_num_ranges * 2; i += 2) | |
1600 | { | |
1601 | res.safe_push (m_base[i]); | |
1602 | res.safe_push (m_base[i + 1]); | |
1603 | k += 2; | |
1604 | } | |
1605 | for ( ; j < r.m_num_ranges * 2; j += 2) | |
1606 | { | |
1607 | res.safe_push (r.m_base[j]); | |
1608 | res.safe_push (r.m_base[j + 1]); | |
1609 | k += 2; | |
1610 | } | |
cca78449 | 1611 | |
4ba9fb0a AH |
1612 | // Now normalize the vector removing any overlaps. |
1613 | i = 2; | |
1614 | int prec = TYPE_PRECISION (ttype); | |
1615 | wide_int max_val = wi::max_value (prec, sign); | |
1616 | for (j = 2; j < k ; j += 2) | |
cca78449 | 1617 | { |
4ba9fb0a AH |
1618 | wide_int val_im1 = wi::to_wide (res[i - 1]); |
1619 | if (val_im1 == max_val) | |
1620 | break; | |
1621 | u1 = wi::add (val_im1, 1, sign, &ovf); | |
1622 | ||
1623 | // Overflow indicates we are at MAX already. | |
1624 | // A wide int bug requires the previous max_val check | |
1625 | // trigger: gcc.c-torture/compile/pr80443.c with -O3 | |
1626 | if (ovf == wi::OVF_OVERFLOW) | |
1627 | break; | |
1628 | ||
1629 | wide_int val_j = wi::to_wide (res[j]); | |
1630 | wide_int val_jp1 = wi::to_wide (res[j+1]); | |
1631 | // Current upper+1 is >= lower bound next pair, then we merge ranges. | |
1632 | if (wi::ge_p (u1, val_j, sign)) | |
1633 | { | |
1634 | // New upper bounds is greater of current or the next one. | |
1635 | if (wi::gt_p (val_jp1, val_im1, sign)) | |
1636 | res [i - 1] = res[j + 1]; | |
1637 | } | |
1638 | else | |
1639 | { | |
1640 | // This is a new distinct range, but no point in copying it | |
1641 | // if it is already in the right place. | |
1642 | if (i != j) | |
1643 | { | |
1644 | res[i++] = res[j]; | |
1645 | res[i++] = res[j + 1]; | |
1646 | } | |
1647 | else | |
1648 | i += 2; | |
1649 | } | |
cca78449 | 1650 | } |
4ba9fb0a AH |
1651 | |
1652 | // At this point, the vector should have i ranges, none overlapping. | |
1653 | // Now it simply needs to be copied, and if there are too many | |
1654 | // ranges, merge some. We wont do any analysis as to what the | |
1655 | // "best" merges are, simply combine the final ranges into one. | |
1656 | if (i > m_max_ranges * 2) | |
1657 | { | |
1658 | res[m_max_ranges * 2 - 1] = res[i - 1]; | |
1659 | i = m_max_ranges * 2; | |
1660 | } | |
1661 | ||
1662 | for (j = 0; j < i ; j++) | |
1663 | m_base[j] = res [j]; | |
1664 | m_num_ranges = i / 2; | |
1665 | ||
1666 | if (flag_checking) | |
1667 | verify_range (); | |
cca78449 AH |
1668 | } |
1669 | ||
4ba9fb0a | 1670 | // intersect for multi-ranges. |
cca78449 AH |
1671 | |
1672 | void | |
4ba9fb0a AH |
1673 | irange::irange_intersect (const irange &r) |
1674 | { | |
1675 | gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); | |
1676 | ||
1677 | if (undefined_p () || r.varying_p ()) | |
1678 | return; | |
1679 | if (r.undefined_p ()) | |
1680 | { | |
1681 | set_undefined (); | |
1682 | return; | |
1683 | } | |
1684 | if (varying_p ()) | |
1685 | { | |
1686 | operator= (r); | |
1687 | return; | |
1688 | } | |
1689 | ||
1690 | signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); | |
1691 | unsigned bld_pair = 0; | |
1692 | unsigned bld_lim = m_max_ranges; | |
1693 | widest_irange r2 (*this); | |
1694 | unsigned r2_lim = r2.num_pairs (); | |
1695 | unsigned i2 = 0; | |
1696 | for (unsigned i = 0; i < r.num_pairs (); ) | |
1697 | { | |
1698 | // If r1's upper is < r2's lower, we can skip r1's pair. | |
1699 | tree ru = r.m_base[i * 2 + 1]; | |
1700 | tree r2l = r2.m_base[i2 * 2]; | |
1701 | if (wi::lt_p (wi::to_wide (ru), wi::to_wide (r2l), sign)) | |
1702 | { | |
1703 | i++; | |
1704 | continue; | |
1705 | } | |
1706 | // Likewise, skip r2's pair if its excluded. | |
1707 | tree r2u = r2.m_base[i2 * 2 + 1]; | |
1708 | tree rl = r.m_base[i * 2]; | |
1709 | if (wi::lt_p (wi::to_wide (r2u), wi::to_wide (rl), sign)) | |
1710 | { | |
1711 | i2++; | |
1712 | if (i2 < r2_lim) | |
1713 | continue; | |
1714 | // No more r2, break. | |
1715 | break; | |
1716 | } | |
1717 | ||
1718 | // Must be some overlap. Find the highest of the lower bounds, | |
1719 | // and set it, unless the build limits lower bounds is already | |
1720 | // set. | |
1721 | if (bld_pair < bld_lim) | |
1722 | { | |
1723 | if (wi::ge_p (wi::to_wide (rl), wi::to_wide (r2l), sign)) | |
1724 | m_base[bld_pair * 2] = rl; | |
1725 | else | |
1726 | m_base[bld_pair * 2] = r2l; | |
1727 | } | |
1728 | else | |
1729 | // Decrease and set a new upper. | |
1730 | bld_pair--; | |
1731 | ||
1732 | // ...and choose the lower of the upper bounds. | |
1733 | if (wi::le_p (wi::to_wide (ru), wi::to_wide (r2u), sign)) | |
1734 | { | |
1735 | m_base[bld_pair * 2 + 1] = ru; | |
1736 | bld_pair++; | |
1737 | // Move past the r1 pair and keep trying. | |
1738 | i++; | |
1739 | continue; | |
1740 | } | |
1741 | else | |
1742 | { | |
1743 | m_base[bld_pair * 2 + 1] = r2u; | |
1744 | bld_pair++; | |
1745 | i2++; | |
1746 | if (i2 < r2_lim) | |
1747 | continue; | |
1748 | // No more r2, break. | |
1749 | break; | |
1750 | } | |
1751 | // r2 has the higher lower bound. | |
1752 | } | |
1753 | ||
1754 | // At the exit of this loop, it is one of 2 things: | |
1755 | // ran out of r1, or r2, but either means we are done. | |
1756 | m_num_ranges = bld_pair; | |
1757 | if (flag_checking) | |
1758 | verify_range (); | |
1759 | } | |
1760 | ||
1761 | static wide_int inline | |
1762 | subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow) | |
cca78449 | 1763 | { |
4ba9fb0a AH |
1764 | // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1 |
1765 | // overflows, since +1 is unrepresentable. This is why we have an | |
1766 | // addition of -1 here. | |
1767 | if (TYPE_SIGN (type) == SIGNED) | |
1768 | return wi::add (x, -1 , SIGNED, &overflow); | |
1769 | else | |
1770 | return wi::sub (x, 1, UNSIGNED, &overflow); | |
cca78449 AH |
1771 | } |
1772 | ||
1773 | /* Return the inverse of a range. */ | |
1774 | ||
1775 | void | |
4ba9fb0a | 1776 | irange::invert () |
cca78449 | 1777 | { |
4ba9fb0a AH |
1778 | if (legacy_mode_p ()) |
1779 | { | |
1780 | // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may | |
1781 | // create non-canonical ranges. Use the constructors instead. | |
1782 | if (m_kind == VR_RANGE) | |
1783 | *this = value_range (min (), max (), VR_ANTI_RANGE); | |
1784 | else if (m_kind == VR_ANTI_RANGE) | |
1785 | *this = value_range (min (), max ()); | |
1786 | else | |
1787 | gcc_unreachable (); | |
1788 | return; | |
1789 | } | |
1790 | ||
1791 | gcc_assert (!undefined_p () && !varying_p ()); | |
1792 | ||
1793 | // We always need one more set of bounds to represent an inverse, so | |
1794 | // if we're at the limit, we can't properly represent things. | |
1795 | // | |
1796 | // For instance, to represent the inverse of a 2 sub-range set | |
1797 | // [5, 10][20, 30], we would need a 3 sub-range set | |
1798 | // [-MIN, 4][11, 19][31, MAX]. | |
1799 | // | |
1800 | // In this case, return the most conservative thing. | |
1801 | // | |
1802 | // However, if any of the extremes of the range are -MIN/+MAX, we | |
1803 | // know we will not need an extra bound. For example: | |
1804 | // | |
1805 | // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX] | |
1806 | // INVERT([-MIN,20][30,MAX]) => [21,29] | |
1807 | tree ttype = type (); | |
1808 | unsigned prec = TYPE_PRECISION (ttype); | |
1809 | signop sign = TYPE_SIGN (ttype); | |
1810 | wide_int type_min = wi::min_value (prec, sign); | |
1811 | wide_int type_max = wi::max_value (prec, sign); | |
1812 | if (m_num_ranges == m_max_ranges | |
1813 | && lower_bound () != type_min | |
1814 | && upper_bound () != type_max) | |
1815 | { | |
1816 | m_base[1] = wide_int_to_tree (ttype, type_max); | |
1817 | m_num_ranges = 1; | |
1818 | return; | |
1819 | } | |
1820 | // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we | |
1821 | // generate [-MIN, a-1][b+1, c-1][d+1, MAX]. | |
1822 | // | |
1823 | // If there is an over/underflow in the calculation for any | |
1824 | // sub-range, we eliminate that subrange. This allows us to easily | |
1825 | // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since | |
1826 | // we eliminate the underflow, only [6, MAX] remains. | |
1827 | unsigned i = 0; | |
1828 | wi::overflow_type ovf; | |
1829 | // Construct leftmost range. | |
1830 | widest_irange orig_range (*this); | |
1831 | unsigned nitems = 0; | |
1832 | wide_int tmp; | |
1833 | // If this is going to underflow on the MINUS 1, don't even bother | |
1834 | // checking. This also handles subtracting one from an unsigned 0, | |
1835 | // which doesn't set the underflow bit. | |
1836 | if (type_min != orig_range.lower_bound ()) | |
1837 | { | |
1838 | m_base[nitems++] = wide_int_to_tree (ttype, type_min); | |
1839 | tmp = subtract_one (orig_range.lower_bound (), ttype, ovf); | |
1840 | m_base[nitems++] = wide_int_to_tree (ttype, tmp); | |
1841 | if (ovf) | |
1842 | nitems = 0; | |
1843 | } | |
1844 | i++; | |
1845 | // Construct middle ranges if applicable. | |
1846 | if (orig_range.num_pairs () > 1) | |
1847 | { | |
1848 | unsigned j = i; | |
1849 | for (; j < (orig_range.num_pairs () * 2) - 1; j += 2) | |
1850 | { | |
1851 | // The middle ranges cannot have MAX/MIN, so there's no need | |
1852 | // to check for unsigned overflow on the +1 and -1 here. | |
1853 | tmp = wi::add (wi::to_wide (orig_range.m_base[j]), 1, sign, &ovf); | |
1854 | m_base[nitems++] = wide_int_to_tree (ttype, tmp); | |
1855 | tmp = subtract_one (wi::to_wide (orig_range.m_base[j + 1]), | |
1856 | ttype, ovf); | |
1857 | m_base[nitems++] = wide_int_to_tree (ttype, tmp); | |
1858 | if (ovf) | |
1859 | nitems -= 2; | |
1860 | } | |
1861 | i = j; | |
1862 | } | |
1863 | // Construct rightmost range. | |
1864 | // | |
1865 | // However, if this will overflow on the PLUS 1, don't even bother. | |
1866 | // This also handles adding one to an unsigned MAX, which doesn't | |
1867 | // set the overflow bit. | |
1868 | if (type_max != wi::to_wide (orig_range.m_base[i])) | |
1869 | { | |
1870 | tmp = wi::add (wi::to_wide (orig_range.m_base[i]), 1, sign, &ovf); | |
1871 | m_base[nitems++] = wide_int_to_tree (ttype, tmp); | |
1872 | m_base[nitems++] = wide_int_to_tree (ttype, type_max); | |
1873 | if (ovf) | |
1874 | nitems -= 2; | |
1875 | } | |
1876 | m_num_ranges = nitems / 2; | |
1877 | ||
1878 | if (flag_checking) | |
1879 | verify_range (); | |
1880 | } | |
1881 | ||
1882 | static void | |
1883 | dump_bound_with_infinite_markers (FILE *file, tree bound) | |
1884 | { | |
1885 | tree type = TREE_TYPE (bound); | |
1886 | if (INTEGRAL_TYPE_P (type) | |
1887 | && !TYPE_UNSIGNED (type) | |
1888 | && vrp_val_is_min (bound) | |
1889 | && TYPE_PRECISION (type) != 1) | |
1890 | fprintf (file, "-INF"); | |
1891 | else if (vrp_val_is_max (bound) | |
1892 | && TYPE_PRECISION (type) != 1) | |
1893 | fprintf (file, "+INF"); | |
cca78449 | 1894 | else |
4ba9fb0a | 1895 | print_generic_expr (file, bound); |
cca78449 AH |
1896 | } |
1897 | ||
1898 | void | |
4ba9fb0a | 1899 | irange::dump (FILE *file) const |
cca78449 AH |
1900 | { |
1901 | if (undefined_p ()) | |
cca78449 | 1902 | { |
4ba9fb0a AH |
1903 | fprintf (file, "UNDEFINED"); |
1904 | return; | |
1905 | } | |
1906 | print_generic_expr (file, type ()); | |
1907 | fprintf (file, " "); | |
1908 | if (varying_p ()) | |
1909 | { | |
1910 | fprintf (file, "VARYING"); | |
1911 | return; | |
1912 | } | |
1913 | if (legacy_mode_p ()) | |
1914 | { | |
cca78449 | 1915 | fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : ""); |
4ba9fb0a | 1916 | dump_bound_with_infinite_markers (file, min ()); |
cca78449 | 1917 | fprintf (file, ", "); |
4ba9fb0a | 1918 | dump_bound_with_infinite_markers (file, max ()); |
cca78449 | 1919 | fprintf (file, "]"); |
4ba9fb0a | 1920 | return; |
cca78449 | 1921 | } |
4ba9fb0a | 1922 | for (unsigned i = 0; i < m_num_ranges; ++i) |
cca78449 | 1923 | { |
4ba9fb0a AH |
1924 | tree lb = m_base[i * 2]; |
1925 | tree ub = m_base[i * 2 + 1]; | |
1926 | fprintf (file, "["); | |
1927 | dump_bound_with_infinite_markers (file, lb); | |
1928 | fprintf (file, ", "); | |
1929 | dump_bound_with_infinite_markers (file, ub); | |
1930 | fprintf (file, "]"); | |
cca78449 | 1931 | } |
cca78449 AH |
1932 | } |
1933 | ||
1934 | void | |
4ba9fb0a | 1935 | dump_value_range (FILE *file, const irange *vr) |
cca78449 | 1936 | { |
4ba9fb0a | 1937 | vr->dump (file); |
cca78449 AH |
1938 | } |
1939 | ||
4ba9fb0a AH |
1940 | DEBUG_FUNCTION void |
1941 | debug (const irange *vr) | |
cca78449 | 1942 | { |
4ba9fb0a AH |
1943 | dump_value_range (stderr, vr); |
1944 | fprintf (stderr, "\n"); | |
1945 | } | |
1946 | ||
1947 | DEBUG_FUNCTION void | |
1948 | debug (const irange &vr) | |
1949 | { | |
1950 | debug (&vr); | |
cca78449 AH |
1951 | } |
1952 | ||
1953 | DEBUG_FUNCTION void | |
1954 | debug (const value_range *vr) | |
1955 | { | |
1956 | dump_value_range (stderr, vr); | |
4ba9fb0a | 1957 | fprintf (stderr, "\n"); |
cca78449 AH |
1958 | } |
1959 | ||
1960 | DEBUG_FUNCTION void | |
1961 | debug (const value_range &vr) | |
1962 | { | |
1963 | dump_value_range (stderr, &vr); | |
4ba9fb0a | 1964 | fprintf (stderr, "\n"); |
cca78449 AH |
1965 | } |
1966 | ||
1967 | /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR | |
1968 | so that *VR0 U *VR1 == *AR. Returns true if that is possible, | |
1969 | false otherwise. If *AR can be represented with a single range | |
1970 | *VR1 will be VR_UNDEFINED. */ | |
1971 | ||
1972 | bool | |
1973 | ranges_from_anti_range (const value_range *ar, | |
1974 | value_range *vr0, value_range *vr1) | |
1975 | { | |
1976 | tree type = ar->type (); | |
1977 | ||
1978 | vr0->set_undefined (); | |
1979 | vr1->set_undefined (); | |
1980 | ||
1981 | /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U | |
1982 | [A+1, +INF]. Not sure if this helps in practice, though. */ | |
1983 | ||
1984 | if (ar->kind () != VR_ANTI_RANGE | |
1985 | || TREE_CODE (ar->min ()) != INTEGER_CST | |
1986 | || TREE_CODE (ar->max ()) != INTEGER_CST | |
1987 | || !vrp_val_min (type) | |
1988 | || !vrp_val_max (type)) | |
1989 | return false; | |
1990 | ||
1991 | if (tree_int_cst_lt (vrp_val_min (type), ar->min ())) | |
1992 | vr0->set (vrp_val_min (type), | |
1993 | wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1)); | |
1994 | if (tree_int_cst_lt (ar->max (), vrp_val_max (type))) | |
1995 | vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1), | |
1996 | vrp_val_max (type)); | |
1997 | if (vr0->undefined_p ()) | |
1998 | { | |
1999 | *vr0 = *vr1; | |
2000 | vr1->set_undefined (); | |
2001 | } | |
2002 | ||
2003 | return !vr0->undefined_p (); | |
2004 | } | |
2005 | ||
2006 | bool | |
4ba9fb0a | 2007 | range_has_numeric_bounds_p (const irange *vr) |
cca78449 | 2008 | { |
4ba9fb0a | 2009 | return (!vr->undefined_p () |
cca78449 AH |
2010 | && TREE_CODE (vr->min ()) == INTEGER_CST |
2011 | && TREE_CODE (vr->max ()) == INTEGER_CST); | |
2012 | } | |
2013 | ||
cca78449 AH |
2014 | /* Return whether VAL is equal to the maximum value of its type. |
2015 | We can't do a simple equality comparison with TYPE_MAX_VALUE because | |
2016 | C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE | |
2017 | is not == to the integer constant with the same value in the type. */ | |
2018 | ||
2019 | bool | |
2020 | vrp_val_is_max (const_tree val) | |
2021 | { | |
2022 | tree type_max = vrp_val_max (TREE_TYPE (val)); | |
2023 | return (val == type_max | |
2024 | || (type_max != NULL_TREE | |
2025 | && operand_equal_p (val, type_max, 0))); | |
2026 | } | |
2027 | ||
2028 | /* Return whether VAL is equal to the minimum value of its type. */ | |
2029 | ||
2030 | bool | |
2031 | vrp_val_is_min (const_tree val) | |
2032 | { | |
2033 | tree type_min = vrp_val_min (TREE_TYPE (val)); | |
2034 | return (val == type_min | |
2035 | || (type_min != NULL_TREE | |
2036 | && operand_equal_p (val, type_min, 0))); | |
2037 | } | |
2038 | ||
2039 | /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ | |
2040 | ||
2041 | bool | |
2042 | vrp_operand_equal_p (const_tree val1, const_tree val2) | |
2043 | { | |
2044 | if (val1 == val2) | |
2045 | return true; | |
2046 | if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) | |
2047 | return false; | |
2048 | return true; | |
2049 | } | |
4ba9fb0a AH |
2050 | |
2051 | #define DEFINE_INT_RANGE_GC_STUBS(N) \ | |
2052 | void \ | |
2053 | gt_pch_nx (int_range<N> *&x) \ | |
2054 | { \ | |
2055 | for (unsigned i = 0; i < N; ++i) \ | |
2056 | { \ | |
2057 | gt_pch_nx (x->m_ranges[i * 2]); \ | |
2058 | gt_pch_nx (x->m_ranges[i * 2 + 1]); \ | |
2059 | } \ | |
2060 | } \ | |
2061 | \ | |
2062 | void \ | |
2063 | gt_ggc_mx (int_range<N> *&x) \ | |
2064 | { \ | |
2065 | for (unsigned i = 0; i < N; ++i) \ | |
2066 | { \ | |
2067 | gt_ggc_mx (x->m_ranges[i * 2]); \ | |
2068 | gt_ggc_mx (x->m_ranges[i * 2 + 1]); \ | |
2069 | } \ | |
2070 | } | |
2071 | ||
2072 | #define DEFINE_INT_RANGE_INSTANCE(N) \ | |
2073 | template int_range<N>::int_range(tree, tree, value_range_kind); \ | |
2074 | template int_range<N>::int_range(tree_node *, \ | |
2075 | const wide_int &, \ | |
2076 | const wide_int &, \ | |
2077 | value_range_kind); \ | |
2078 | template int_range<N>::int_range(tree); \ | |
2079 | template int_range<N>::int_range(const irange &); \ | |
2080 | template int_range<N>::int_range(const int_range &); \ | |
2081 | template int_range<N>& int_range<N>::operator= (const int_range &); | |
2082 | ||
2083 | DEFINE_INT_RANGE_INSTANCE(1) | |
2084 | DEFINE_INT_RANGE_INSTANCE(2) | |
2085 | DEFINE_INT_RANGE_INSTANCE(3) | |
2086 | DEFINE_INT_RANGE_INSTANCE(255) | |
2087 | DEFINE_INT_RANGE_GC_STUBS(1) |