145
|
1 /* Support routines for value ranges.
|
|
2 Copyright (C) 2019-2020 Free Software Foundation, Inc.
|
|
3
|
|
4 This file is part of GCC.
|
|
5
|
|
6 GCC is free software; you can redistribute it and/or modify
|
|
7 it under the terms of the GNU General Public License as published by
|
|
8 the Free Software Foundation; either version 3, or (at your option)
|
|
9 any later version.
|
|
10
|
|
11 GCC is distributed in the hope that it will be useful,
|
|
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
14 GNU General Public License for more details.
|
|
15
|
|
16 You should have received a copy of the GNU General Public License
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
19
|
|
20 #include "config.h"
|
|
21 #include "system.h"
|
|
22 #include "coretypes.h"
|
|
23 #include "backend.h"
|
|
24 #include "tree.h"
|
|
25 #include "gimple.h"
|
|
26 #include "ssa.h"
|
|
27 #include "tree-pretty-print.h"
|
|
28 #include "fold-const.h"
|
|
29
|
|
30 value_range::value_range (tree min, tree max, value_range_kind kind)
|
|
31 {
|
|
32 set (min, max, kind);
|
|
33 }
|
|
34
|
|
35 value_range::value_range (tree type)
|
|
36 {
|
|
37 set_varying (type);
|
|
38 }
|
|
39
|
|
40 value_range::value_range (tree type,
|
|
41 const wide_int &wmin, const wide_int &wmax,
|
|
42 enum value_range_kind kind)
|
|
43 {
|
|
44 tree min = wide_int_to_tree (type, wmin);
|
|
45 tree max = wide_int_to_tree (type, wmax);
|
|
46 gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
|
|
47 set (min, max, kind);
|
|
48 }
|
|
49
|
|
50 void
|
|
51 value_range::set_undefined ()
|
|
52 {
|
|
53 m_kind = VR_UNDEFINED;
|
|
54 m_min = m_max = NULL;
|
|
55 }
|
|
56
|
|
57 void
|
|
58 value_range::set_varying (tree type)
|
|
59 {
|
|
60 m_kind = VR_VARYING;
|
|
61 if (supports_type_p (type))
|
|
62 {
|
|
63 m_min = vrp_val_min (type);
|
|
64 m_max = vrp_val_max (type);
|
|
65 }
|
|
66 else
|
|
67 /* We can't do anything range-wise with these types. */
|
|
68 m_min = m_max = error_mark_node;
|
|
69 }
|
|
70
|
|
71 /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
|
|
72 This means adjusting VRTYPE, MIN and MAX representing the case of a
|
|
73 wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
|
|
74 as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
|
|
75 In corner cases where MAX+1 or MIN-1 wraps this will fall back
|
|
76 to varying.
|
|
77 This routine exists to ease canonicalization in the case where we
|
|
78 extract ranges from var + CST op limit. */
|
|
79
|
|
80 void
|
|
81 value_range::set (tree min, tree max, value_range_kind kind)
|
|
82 {
|
|
83 /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
|
|
84 if (kind == VR_UNDEFINED)
|
|
85 {
|
|
86 set_undefined ();
|
|
87 return;
|
|
88 }
|
|
89 else if (kind == VR_VARYING)
|
|
90 {
|
|
91 gcc_assert (TREE_TYPE (min) == TREE_TYPE (max));
|
|
92 tree typ = TREE_TYPE (min);
|
|
93 if (supports_type_p (typ))
|
|
94 {
|
|
95 gcc_assert (vrp_val_min (typ));
|
|
96 gcc_assert (vrp_val_max (typ));
|
|
97 }
|
|
98 set_varying (typ);
|
|
99 return;
|
|
100 }
|
|
101
|
|
102 /* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */
|
|
103 if (POLY_INT_CST_P (min))
|
|
104 {
|
|
105 tree type_min = vrp_val_min (TREE_TYPE (min));
|
|
106 widest_int lb
|
|
107 = constant_lower_bound_with_limit (wi::to_poly_widest (min),
|
|
108 wi::to_widest (type_min));
|
|
109 min = wide_int_to_tree (TREE_TYPE (min), lb);
|
|
110 }
|
|
111 if (POLY_INT_CST_P (max))
|
|
112 {
|
|
113 tree type_max = vrp_val_max (TREE_TYPE (max));
|
|
114 widest_int ub
|
|
115 = constant_upper_bound_with_limit (wi::to_poly_widest (max),
|
|
116 wi::to_widest (type_max));
|
|
117 max = wide_int_to_tree (TREE_TYPE (max), ub);
|
|
118 }
|
|
119
|
|
120 /* Nothing to canonicalize for symbolic ranges. */
|
|
121 if (TREE_CODE (min) != INTEGER_CST
|
|
122 || TREE_CODE (max) != INTEGER_CST)
|
|
123 {
|
|
124 m_kind = kind;
|
|
125 m_min = min;
|
|
126 m_max = max;
|
|
127 return;
|
|
128 }
|
|
129
|
|
130 /* Wrong order for min and max, to swap them and the VR type we need
|
|
131 to adjust them. */
|
|
132 if (tree_int_cst_lt (max, min))
|
|
133 {
|
|
134 tree one, tmp;
|
|
135
|
|
136 /* For one bit precision if max < min, then the swapped
|
|
137 range covers all values, so for VR_RANGE it is varying and
|
|
138 for VR_ANTI_RANGE empty range, so drop to varying as well. */
|
|
139 if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
|
|
140 {
|
|
141 set_varying (TREE_TYPE (min));
|
|
142 return;
|
|
143 }
|
|
144
|
|
145 one = build_int_cst (TREE_TYPE (min), 1);
|
|
146 tmp = int_const_binop (PLUS_EXPR, max, one);
|
|
147 max = int_const_binop (MINUS_EXPR, min, one);
|
|
148 min = tmp;
|
|
149
|
|
150 /* There's one corner case, if we had [C+1, C] before we now have
|
|
151 that again. But this represents an empty value range, so drop
|
|
152 to varying in this case. */
|
|
153 if (tree_int_cst_lt (max, min))
|
|
154 {
|
|
155 set_varying (TREE_TYPE (min));
|
|
156 return;
|
|
157 }
|
|
158
|
|
159 kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
|
|
160 }
|
|
161
|
|
162 tree type = TREE_TYPE (min);
|
|
163
|
|
164 /* Anti-ranges that can be represented as ranges should be so. */
|
|
165 if (kind == VR_ANTI_RANGE)
|
|
166 {
|
|
167 /* For -fstrict-enums we may receive out-of-range ranges so consider
|
|
168 values < -INF and values > INF as -INF/INF as well. */
|
|
169 bool is_min = vrp_val_is_min (min);
|
|
170 bool is_max = vrp_val_is_max (max);
|
|
171
|
|
172 if (is_min && is_max)
|
|
173 {
|
|
174 /* We cannot deal with empty ranges, drop to varying.
|
|
175 ??? This could be VR_UNDEFINED instead. */
|
|
176 set_varying (type);
|
|
177 return;
|
|
178 }
|
|
179 else if (TYPE_PRECISION (TREE_TYPE (min)) == 1
|
|
180 && (is_min || is_max))
|
|
181 {
|
|
182 /* Non-empty boolean ranges can always be represented
|
|
183 as a singleton range. */
|
|
184 if (is_min)
|
|
185 min = max = vrp_val_max (TREE_TYPE (min));
|
|
186 else
|
|
187 min = max = vrp_val_min (TREE_TYPE (min));
|
|
188 kind = VR_RANGE;
|
|
189 }
|
|
190 else if (is_min)
|
|
191 {
|
|
192 tree one = build_int_cst (TREE_TYPE (max), 1);
|
|
193 min = int_const_binop (PLUS_EXPR, max, one);
|
|
194 max = vrp_val_max (TREE_TYPE (max));
|
|
195 kind = VR_RANGE;
|
|
196 }
|
|
197 else if (is_max)
|
|
198 {
|
|
199 tree one = build_int_cst (TREE_TYPE (min), 1);
|
|
200 max = int_const_binop (MINUS_EXPR, min, one);
|
|
201 min = vrp_val_min (TREE_TYPE (min));
|
|
202 kind = VR_RANGE;
|
|
203 }
|
|
204 }
|
|
205
|
|
206 /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
|
|
207
|
|
208 Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
|
|
209 restrict those to a subset of what actually fits in the type.
|
|
210 Instead use the extremes of the type precision which will allow
|
|
211 compare_range_with_value() to check if a value is inside a range,
|
|
212 whereas if we used TYPE_*_VAL, said function would just punt
|
|
213 upon seeing a VARYING. */
|
|
214 unsigned prec = TYPE_PRECISION (type);
|
|
215 signop sign = TYPE_SIGN (type);
|
|
216 if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
|
|
217 && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
|
|
218 {
|
|
219 if (kind == VR_RANGE)
|
|
220 set_varying (type);
|
|
221 else if (kind == VR_ANTI_RANGE)
|
|
222 set_undefined ();
|
|
223 else
|
|
224 gcc_unreachable ();
|
|
225 return;
|
|
226 }
|
|
227
|
|
228 /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
|
|
229 to make sure VRP iteration terminates, otherwise we can get into
|
|
230 oscillations. */
|
|
231
|
|
232 m_kind = kind;
|
|
233 m_min = min;
|
|
234 m_max = max;
|
|
235 if (flag_checking)
|
|
236 check ();
|
|
237 }
|
|
238
|
|
239 void
|
|
240 value_range::set (tree val)
|
|
241 {
|
|
242 gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
|
|
243 if (TREE_OVERFLOW_P (val))
|
|
244 val = drop_tree_overflow (val);
|
|
245 set (val, val);
|
|
246 }
|
|
247
|
|
248 /* Set value range VR to a nonzero range of type TYPE. */
|
|
249
|
|
250 void
|
|
251 value_range::set_nonzero (tree type)
|
|
252 {
|
|
253 tree zero = build_int_cst (type, 0);
|
|
254 set (zero, zero, VR_ANTI_RANGE);
|
|
255 }
|
|
256
|
|
257 /* Set value range VR to a ZERO range of type TYPE. */
|
|
258
|
|
259 void
|
|
260 value_range::set_zero (tree type)
|
|
261 {
|
|
262 set (build_int_cst (type, 0));
|
|
263 }
|
|
264
|
|
265 /* Check the validity of the range. */
|
|
266
|
|
267 void
|
|
268 value_range::check ()
|
|
269 {
|
|
270 switch (m_kind)
|
|
271 {
|
|
272 case VR_RANGE:
|
|
273 case VR_ANTI_RANGE:
|
|
274 {
|
|
275 gcc_assert (m_min && m_max);
|
|
276 gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max));
|
|
277
|
|
278 /* Creating ~[-MIN, +MAX] is stupid because that would be
|
|
279 the empty set. */
|
|
280 if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE)
|
|
281 gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max));
|
|
282
|
|
283 int cmp = compare_values (m_min, m_max);
|
|
284 gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
|
|
285 break;
|
|
286 }
|
|
287 case VR_UNDEFINED:
|
|
288 gcc_assert (!min () && !max ());
|
|
289 break;
|
|
290 case VR_VARYING:
|
|
291 gcc_assert (m_min && m_max);
|
|
292 break;
|
|
293 default:
|
|
294 gcc_unreachable ();
|
|
295 }
|
|
296 }
|
|
297
|
|
298 /* Return the number of sub-ranges in a range. */
|
|
299
|
|
300 unsigned
|
|
301 value_range::num_pairs () const
|
|
302 {
|
|
303 if (undefined_p ())
|
|
304 return 0;
|
|
305 if (varying_p ())
|
|
306 return 1;
|
|
307 if (symbolic_p ())
|
|
308 {
|
|
309 value_range numeric_range (*this);
|
|
310 numeric_range.normalize_symbolics ();
|
|
311 return numeric_range.num_pairs ();
|
|
312 }
|
|
313 if (m_kind == VR_ANTI_RANGE)
|
|
314 {
|
|
315 // ~[MIN, X] has one sub-range of [X+1, MAX], and
|
|
316 // ~[X, MAX] has one sub-range of [MIN, X-1].
|
|
317 if (vrp_val_is_min (m_min) || vrp_val_is_max (m_max))
|
|
318 return 1;
|
|
319 return 2;
|
|
320 }
|
|
321 return 1;
|
|
322 }
|
|
323
|
|
324 /* Return the lower bound for a sub-range. PAIR is the sub-range in
|
|
325 question. */
|
|
326
|
|
327 wide_int
|
|
328 value_range::lower_bound (unsigned pair) const
|
|
329 {
|
|
330 if (symbolic_p ())
|
|
331 {
|
|
332 value_range numeric_range (*this);
|
|
333 numeric_range.normalize_symbolics ();
|
|
334 return numeric_range.lower_bound (pair);
|
|
335 }
|
|
336
|
|
337 gcc_checking_assert (!undefined_p ());
|
|
338 gcc_checking_assert (pair + 1 <= num_pairs ());
|
|
339 tree t = NULL;
|
|
340 if (m_kind == VR_ANTI_RANGE)
|
|
341 {
|
|
342 tree typ = type ();
|
|
343 if (pair == 1 || vrp_val_is_min (m_min))
|
|
344 t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1);
|
|
345 else
|
|
346 t = vrp_val_min (typ);
|
|
347 }
|
|
348 else
|
|
349 t = m_min;
|
|
350 return wi::to_wide (t);
|
|
351 }
|
|
352
|
|
353 /* Return the upper bound for a sub-range. PAIR is the sub-range in
|
|
354 question. */
|
|
355
|
|
356 wide_int
|
|
357 value_range::upper_bound (unsigned pair) const
|
|
358 {
|
|
359 if (symbolic_p ())
|
|
360 {
|
|
361 value_range numeric_range (*this);
|
|
362 numeric_range.normalize_symbolics ();
|
|
363 return numeric_range.upper_bound (pair);
|
|
364 }
|
|
365
|
|
366 gcc_checking_assert (!undefined_p ());
|
|
367 gcc_checking_assert (pair + 1 <= num_pairs ());
|
|
368 tree t = NULL;
|
|
369 if (m_kind == VR_ANTI_RANGE)
|
|
370 {
|
|
371 tree typ = type ();
|
|
372 if (pair == 1 || vrp_val_is_min (m_min))
|
|
373 t = vrp_val_max (typ);
|
|
374 else
|
|
375 t = wide_int_to_tree (typ, wi::to_wide (m_min) - 1);
|
|
376 }
|
|
377 else
|
|
378 t = m_max;
|
|
379 return wi::to_wide (t);
|
|
380 }
|
|
381
|
|
382 /* Return the highest bound in a range. */
|
|
383
|
|
384 wide_int
|
|
385 value_range::upper_bound () const
|
|
386 {
|
|
387 unsigned pairs = num_pairs ();
|
|
388 gcc_checking_assert (pairs > 0);
|
|
389 return upper_bound (pairs - 1);
|
|
390 }
|
|
391
|
|
392 bool
|
|
393 value_range::equal_p (const value_range &other) const
|
|
394 {
|
|
395 /* Ignore types for undefined. All undefines are equal. */
|
|
396 if (undefined_p ())
|
|
397 return m_kind == other.m_kind;
|
|
398
|
|
399 return (m_kind == other.m_kind
|
|
400 && vrp_operand_equal_p (m_min, other.m_min)
|
|
401 && vrp_operand_equal_p (m_max, other.m_max));
|
|
402 }
|
|
403
|
|
404 bool
|
|
405 value_range::operator== (const value_range &r) const
|
|
406 {
|
|
407 return equal_p (r);
|
|
408 }
|
|
409
|
|
410 /* If range is a singleton, place it in RESULT and return TRUE.
|
|
411 Note: A singleton can be any gimple invariant, not just constants.
|
|
412 So, [&x, &x] counts as a singleton. */
|
|
413 /* Return TRUE if this is a symbolic range. */
|
|
414
|
|
415 bool
|
|
416 value_range::symbolic_p () const
|
|
417 {
|
|
418 return (!varying_p ()
|
|
419 && !undefined_p ()
|
|
420 && (!is_gimple_min_invariant (m_min)
|
|
421 || !is_gimple_min_invariant (m_max)));
|
|
422 }
|
|
423
|
|
424 /* NOTE: This is not the inverse of symbolic_p because the range
|
|
425 could also be varying or undefined. Ideally they should be inverse
|
|
426 of each other, with varying only applying to symbolics. Varying of
|
|
427 constants would be represented as [-MIN, +MAX]. */
|
|
428
|
|
429 bool
|
|
430 value_range::constant_p () const
|
|
431 {
|
|
432 return (!varying_p ()
|
|
433 && !undefined_p ()
|
|
434 && TREE_CODE (m_min) == INTEGER_CST
|
|
435 && TREE_CODE (m_max) == INTEGER_CST);
|
|
436 }
|
|
437
|
|
438 bool
|
|
439 value_range::singleton_p (tree *result) const
|
|
440 {
|
|
441 if (m_kind == VR_ANTI_RANGE)
|
|
442 {
|
|
443 if (nonzero_p ())
|
|
444 {
|
|
445 if (TYPE_PRECISION (type ()) == 1)
|
|
446 {
|
|
447 if (result)
|
|
448 *result = m_max;
|
|
449 return true;
|
|
450 }
|
|
451 return false;
|
|
452 }
|
|
453 if (num_pairs () == 1)
|
|
454 {
|
|
455 value_range vr0, vr1;
|
|
456 ranges_from_anti_range (this, &vr0, &vr1);
|
|
457 return vr0.singleton_p (result);
|
|
458 }
|
|
459 }
|
|
460 if (m_kind == VR_RANGE
|
|
461 && vrp_operand_equal_p (min (), max ())
|
|
462 && is_gimple_min_invariant (min ()))
|
|
463 {
|
|
464 if (result)
|
|
465 *result = min ();
|
|
466 return true;
|
|
467 }
|
|
468 return false;
|
|
469 }
|
|
470
|
|
471 /* Return 1 if VAL is inside value range.
|
|
472 0 if VAL is not inside value range.
|
|
473 -2 if we cannot tell either way.
|
|
474
|
|
475 Benchmark compile/20001226-1.c compilation time after changing this
|
|
476 function. */
|
|
477
|
|
478 int
|
|
479 value_range::value_inside_range (tree val) const
|
|
480 {
|
|
481 int cmp1, cmp2;
|
|
482
|
|
483 if (varying_p ())
|
|
484 return 1;
|
|
485
|
|
486 if (undefined_p ())
|
|
487 return 0;
|
|
488
|
|
489 cmp1 = operand_less_p (val, m_min);
|
|
490 if (cmp1 == -2)
|
|
491 return -2;
|
|
492 if (cmp1 == 1)
|
|
493 return m_kind != VR_RANGE;
|
|
494
|
|
495 cmp2 = operand_less_p (m_max, val);
|
|
496 if (cmp2 == -2)
|
|
497 return -2;
|
|
498
|
|
499 if (m_kind == VR_RANGE)
|
|
500 return !cmp2;
|
|
501 else
|
|
502 return !!cmp2;
|
|
503 }
|
|
504
|
|
505 /* Return TRUE if it is possible that range contains VAL. */
|
|
506
|
|
507 bool
|
|
508 value_range::may_contain_p (tree val) const
|
|
509 {
|
|
510 return value_inside_range (val) != 0;
|
|
511 }
|
|
512
|
|
513 /* Return TRUE if range contains INTEGER_CST. */
|
|
514
|
|
515 bool
|
|
516 value_range::contains_p (tree cst) const
|
|
517 {
|
|
518 gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
|
|
519 if (symbolic_p ())
|
|
520 {
|
|
521 value_range numeric_range (*this);
|
|
522 numeric_range.normalize_symbolics ();
|
|
523 return numeric_range.contains_p (cst);
|
|
524 }
|
|
525 return value_inside_range (cst) == 1;
|
|
526 }
|
|
527
|
|
528 /* Normalize addresses into constants. */
|
|
529
|
|
530 void
|
|
531 value_range::normalize_addresses ()
|
|
532 {
|
|
533 if (undefined_p ())
|
|
534 return;
|
|
535
|
|
536 if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this))
|
|
537 return;
|
|
538
|
|
539 if (!range_includes_zero_p (this))
|
|
540 {
|
|
541 gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR
|
|
542 || TREE_CODE (m_max) == ADDR_EXPR);
|
|
543 set_nonzero (type ());
|
|
544 return;
|
|
545 }
|
|
546 set_varying (type ());
|
|
547 }
|
|
548
|
|
549 /* Normalize symbolics and addresses into constants. */
|
|
550
|
|
551 void
|
|
552 value_range::normalize_symbolics ()
|
|
553 {
|
|
554 if (varying_p () || undefined_p ())
|
|
555 return;
|
|
556
|
|
557 tree ttype = type ();
|
|
558 bool min_symbolic = !is_gimple_min_invariant (min ());
|
|
559 bool max_symbolic = !is_gimple_min_invariant (max ());
|
|
560 if (!min_symbolic && !max_symbolic)
|
|
561 {
|
|
562 normalize_addresses ();
|
|
563 return;
|
|
564 }
|
|
565
|
|
566 // [SYM, SYM] -> VARYING
|
|
567 if (min_symbolic && max_symbolic)
|
|
568 {
|
|
569 set_varying (ttype);
|
|
570 return;
|
|
571 }
|
|
572 if (kind () == VR_RANGE)
|
|
573 {
|
|
574 // [SYM, NUM] -> [-MIN, NUM]
|
|
575 if (min_symbolic)
|
|
576 {
|
|
577 set (vrp_val_min (ttype), max ());
|
|
578 return;
|
|
579 }
|
|
580 // [NUM, SYM] -> [NUM, +MAX]
|
|
581 set (min (), vrp_val_max (ttype));
|
|
582 return;
|
|
583 }
|
|
584 gcc_checking_assert (kind () == VR_ANTI_RANGE);
|
|
585 // ~[SYM, NUM] -> [NUM + 1, +MAX]
|
|
586 if (min_symbolic)
|
|
587 {
|
|
588 if (!vrp_val_is_max (max ()))
|
|
589 {
|
|
590 tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1);
|
|
591 set (n, vrp_val_max (ttype));
|
|
592 return;
|
|
593 }
|
|
594 set_varying (ttype);
|
|
595 return;
|
|
596 }
|
|
597 // ~[NUM, SYM] -> [-MIN, NUM - 1]
|
|
598 if (!vrp_val_is_min (min ()))
|
|
599 {
|
|
600 tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
|
|
601 set (vrp_val_min (ttype), n);
|
|
602 return;
|
|
603 }
|
|
604 set_varying (ttype);
|
|
605 }
|
|
606
|
|
607 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
|
|
608 { VR1TYPE, VR0MIN, VR0MAX } and store the result
|
|
609 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
|
|
610 possible such range. The resulting range is not canonicalized. */
|
|
611
|
|
612 static void
|
|
613 intersect_ranges (enum value_range_kind *vr0type,
|
|
614 tree *vr0min, tree *vr0max,
|
|
615 enum value_range_kind vr1type,
|
|
616 tree vr1min, tree vr1max)
|
|
617 {
|
|
618 bool mineq = vrp_operand_equal_p (*vr0min, vr1min);
|
|
619 bool maxeq = vrp_operand_equal_p (*vr0max, vr1max);
|
|
620
|
|
621 /* [] is vr0, () is vr1 in the following classification comments. */
|
|
622 if (mineq && maxeq)
|
|
623 {
|
|
624 /* [( )] */
|
|
625 if (*vr0type == vr1type)
|
|
626 /* Nothing to do for equal ranges. */
|
|
627 ;
|
|
628 else if ((*vr0type == VR_RANGE
|
|
629 && vr1type == VR_ANTI_RANGE)
|
|
630 || (*vr0type == VR_ANTI_RANGE
|
|
631 && vr1type == VR_RANGE))
|
|
632 {
|
|
633 /* For anti-range with range intersection the result is empty. */
|
|
634 *vr0type = VR_UNDEFINED;
|
|
635 *vr0min = NULL_TREE;
|
|
636 *vr0max = NULL_TREE;
|
|
637 }
|
|
638 else
|
|
639 gcc_unreachable ();
|
|
640 }
|
|
641 else if (operand_less_p (*vr0max, vr1min) == 1
|
|
642 || operand_less_p (vr1max, *vr0min) == 1)
|
|
643 {
|
|
644 /* [ ] ( ) or ( ) [ ]
|
|
645 If the ranges have an empty intersection, the result of the
|
|
646 intersect operation is the range for intersecting an
|
|
647 anti-range with a range or empty when intersecting two ranges. */
|
|
648 if (*vr0type == VR_RANGE
|
|
649 && vr1type == VR_ANTI_RANGE)
|
|
650 ;
|
|
651 else if (*vr0type == VR_ANTI_RANGE
|
|
652 && vr1type == VR_RANGE)
|
|
653 {
|
|
654 *vr0type = vr1type;
|
|
655 *vr0min = vr1min;
|
|
656 *vr0max = vr1max;
|
|
657 }
|
|
658 else if (*vr0type == VR_RANGE
|
|
659 && vr1type == VR_RANGE)
|
|
660 {
|
|
661 *vr0type = VR_UNDEFINED;
|
|
662 *vr0min = NULL_TREE;
|
|
663 *vr0max = NULL_TREE;
|
|
664 }
|
|
665 else if (*vr0type == VR_ANTI_RANGE
|
|
666 && vr1type == VR_ANTI_RANGE)
|
|
667 {
|
|
668 /* If the anti-ranges are adjacent to each other merge them. */
|
|
669 if (TREE_CODE (*vr0max) == INTEGER_CST
|
|
670 && TREE_CODE (vr1min) == INTEGER_CST
|
|
671 && operand_less_p (*vr0max, vr1min) == 1
|
|
672 && integer_onep (int_const_binop (MINUS_EXPR,
|
|
673 vr1min, *vr0max)))
|
|
674 *vr0max = vr1max;
|
|
675 else if (TREE_CODE (vr1max) == INTEGER_CST
|
|
676 && TREE_CODE (*vr0min) == INTEGER_CST
|
|
677 && operand_less_p (vr1max, *vr0min) == 1
|
|
678 && integer_onep (int_const_binop (MINUS_EXPR,
|
|
679 *vr0min, vr1max)))
|
|
680 *vr0min = vr1min;
|
|
681 /* Else arbitrarily take VR0. */
|
|
682 }
|
|
683 }
|
|
684 else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
|
|
685 && (mineq || operand_less_p (*vr0min, vr1min) == 1))
|
|
686 {
|
|
687 /* [ ( ) ] or [( ) ] or [ ( )] */
|
|
688 if (*vr0type == VR_RANGE
|
|
689 && vr1type == VR_RANGE)
|
|
690 {
|
|
691 /* If both are ranges the result is the inner one. */
|
|
692 *vr0type = vr1type;
|
|
693 *vr0min = vr1min;
|
|
694 *vr0max = vr1max;
|
|
695 }
|
|
696 else if (*vr0type == VR_RANGE
|
|
697 && vr1type == VR_ANTI_RANGE)
|
|
698 {
|
|
699 /* Choose the right gap if the left one is empty. */
|
|
700 if (mineq)
|
|
701 {
|
|
702 if (TREE_CODE (vr1max) != INTEGER_CST)
|
|
703 *vr0min = vr1max;
|
|
704 else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1
|
|
705 && !TYPE_UNSIGNED (TREE_TYPE (vr1max)))
|
|
706 *vr0min
|
|
707 = int_const_binop (MINUS_EXPR, vr1max,
|
|
708 build_int_cst (TREE_TYPE (vr1max), -1));
|
|
709 else
|
|
710 *vr0min
|
|
711 = int_const_binop (PLUS_EXPR, vr1max,
|
|
712 build_int_cst (TREE_TYPE (vr1max), 1));
|
|
713 }
|
|
714 /* Choose the left gap if the right one is empty. */
|
|
715 else if (maxeq)
|
|
716 {
|
|
717 if (TREE_CODE (vr1min) != INTEGER_CST)
|
|
718 *vr0max = vr1min;
|
|
719 else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1
|
|
720 && !TYPE_UNSIGNED (TREE_TYPE (vr1min)))
|
|
721 *vr0max
|
|
722 = int_const_binop (PLUS_EXPR, vr1min,
|
|
723 build_int_cst (TREE_TYPE (vr1min), -1));
|
|
724 else
|
|
725 *vr0max
|
|
726 = int_const_binop (MINUS_EXPR, vr1min,
|
|
727 build_int_cst (TREE_TYPE (vr1min), 1));
|
|
728 }
|
|
729 /* Choose the anti-range if the range is effectively varying. */
|
|
730 else if (vrp_val_is_min (*vr0min)
|
|
731 && vrp_val_is_max (*vr0max))
|
|
732 {
|
|
733 *vr0type = vr1type;
|
|
734 *vr0min = vr1min;
|
|
735 *vr0max = vr1max;
|
|
736 }
|
|
737 /* Else choose the range. */
|
|
738 }
|
|
739 else if (*vr0type == VR_ANTI_RANGE
|
|
740 && vr1type == VR_ANTI_RANGE)
|
|
741 /* If both are anti-ranges the result is the outer one. */
|
|
742 ;
|
|
743 else if (*vr0type == VR_ANTI_RANGE
|
|
744 && vr1type == VR_RANGE)
|
|
745 {
|
|
746 /* The intersection is empty. */
|
|
747 *vr0type = VR_UNDEFINED;
|
|
748 *vr0min = NULL_TREE;
|
|
749 *vr0max = NULL_TREE;
|
|
750 }
|
|
751 else
|
|
752 gcc_unreachable ();
|
|
753 }
|
|
754 else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
|
|
755 && (mineq || operand_less_p (vr1min, *vr0min) == 1))
|
|
756 {
|
|
757 /* ( [ ] ) or ([ ] ) or ( [ ]) */
|
|
758 if (*vr0type == VR_RANGE
|
|
759 && vr1type == VR_RANGE)
|
|
760 /* Choose the inner range. */
|
|
761 ;
|
|
762 else if (*vr0type == VR_ANTI_RANGE
|
|
763 && vr1type == VR_RANGE)
|
|
764 {
|
|
765 /* Choose the right gap if the left is empty. */
|
|
766 if (mineq)
|
|
767 {
|
|
768 *vr0type = VR_RANGE;
|
|
769 if (TREE_CODE (*vr0max) != INTEGER_CST)
|
|
770 *vr0min = *vr0max;
|
|
771 else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1
|
|
772 && !TYPE_UNSIGNED (TREE_TYPE (*vr0max)))
|
|
773 *vr0min
|
|
774 = int_const_binop (MINUS_EXPR, *vr0max,
|
|
775 build_int_cst (TREE_TYPE (*vr0max), -1));
|
|
776 else
|
|
777 *vr0min
|
|
778 = int_const_binop (PLUS_EXPR, *vr0max,
|
|
779 build_int_cst (TREE_TYPE (*vr0max), 1));
|
|
780 *vr0max = vr1max;
|
|
781 }
|
|
782 /* Choose the left gap if the right is empty. */
|
|
783 else if (maxeq)
|
|
784 {
|
|
785 *vr0type = VR_RANGE;
|
|
786 if (TREE_CODE (*vr0min) != INTEGER_CST)
|
|
787 *vr0max = *vr0min;
|
|
788 else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1
|
|
789 && !TYPE_UNSIGNED (TREE_TYPE (*vr0min)))
|
|
790 *vr0max
|
|
791 = int_const_binop (PLUS_EXPR, *vr0min,
|
|
792 build_int_cst (TREE_TYPE (*vr0min), -1));
|
|
793 else
|
|
794 *vr0max
|
|
795 = int_const_binop (MINUS_EXPR, *vr0min,
|
|
796 build_int_cst (TREE_TYPE (*vr0min), 1));
|
|
797 *vr0min = vr1min;
|
|
798 }
|
|
799 /* Choose the anti-range if the range is effectively varying. */
|
|
800 else if (vrp_val_is_min (vr1min)
|
|
801 && vrp_val_is_max (vr1max))
|
|
802 ;
|
|
803 /* Choose the anti-range if it is ~[0,0], that range is special
|
|
804 enough to special case when vr1's range is relatively wide.
|
|
805 At least for types bigger than int - this covers pointers
|
|
806 and arguments to functions like ctz. */
|
|
807 else if (*vr0min == *vr0max
|
|
808 && integer_zerop (*vr0min)
|
|
809 && ((TYPE_PRECISION (TREE_TYPE (*vr0min))
|
|
810 >= TYPE_PRECISION (integer_type_node))
|
|
811 || POINTER_TYPE_P (TREE_TYPE (*vr0min)))
|
|
812 && TREE_CODE (vr1max) == INTEGER_CST
|
|
813 && TREE_CODE (vr1min) == INTEGER_CST
|
|
814 && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min))
|
|
815 < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2))
|
|
816 ;
|
|
817 /* Else choose the range. */
|
|
818 else
|
|
819 {
|
|
820 *vr0type = vr1type;
|
|
821 *vr0min = vr1min;
|
|
822 *vr0max = vr1max;
|
|
823 }
|
|
824 }
|
|
825 else if (*vr0type == VR_ANTI_RANGE
|
|
826 && vr1type == VR_ANTI_RANGE)
|
|
827 {
|
|
828 /* If both are anti-ranges the result is the outer one. */
|
|
829 *vr0type = vr1type;
|
|
830 *vr0min = vr1min;
|
|
831 *vr0max = vr1max;
|
|
832 }
|
|
833 else if (vr1type == VR_ANTI_RANGE
|
|
834 && *vr0type == VR_RANGE)
|
|
835 {
|
|
836 /* The intersection is empty. */
|
|
837 *vr0type = VR_UNDEFINED;
|
|
838 *vr0min = NULL_TREE;
|
|
839 *vr0max = NULL_TREE;
|
|
840 }
|
|
841 else
|
|
842 gcc_unreachable ();
|
|
843 }
|
|
844 else if ((operand_less_p (vr1min, *vr0max) == 1
|
|
845 || operand_equal_p (vr1min, *vr0max, 0))
|
|
846 && operand_less_p (*vr0min, vr1min) == 1)
|
|
847 {
|
|
848 /* [ ( ] ) or [ ]( ) */
|
|
849 if (*vr0type == VR_ANTI_RANGE
|
|
850 && vr1type == VR_ANTI_RANGE)
|
|
851 *vr0max = vr1max;
|
|
852 else if (*vr0type == VR_RANGE
|
|
853 && vr1type == VR_RANGE)
|
|
854 *vr0min = vr1min;
|
|
855 else if (*vr0type == VR_RANGE
|
|
856 && vr1type == VR_ANTI_RANGE)
|
|
857 {
|
|
858 if (TREE_CODE (vr1min) == INTEGER_CST)
|
|
859 *vr0max = int_const_binop (MINUS_EXPR, vr1min,
|
|
860 build_int_cst (TREE_TYPE (vr1min), 1));
|
|
861 else
|
|
862 *vr0max = vr1min;
|
|
863 }
|
|
864 else if (*vr0type == VR_ANTI_RANGE
|
|
865 && vr1type == VR_RANGE)
|
|
866 {
|
|
867 *vr0type = VR_RANGE;
|
|
868 if (TREE_CODE (*vr0max) == INTEGER_CST)
|
|
869 *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
|
|
870 build_int_cst (TREE_TYPE (*vr0max), 1));
|
|
871 else
|
|
872 *vr0min = *vr0max;
|
|
873 *vr0max = vr1max;
|
|
874 }
|
|
875 else
|
|
876 gcc_unreachable ();
|
|
877 }
|
|
878 else if ((operand_less_p (*vr0min, vr1max) == 1
|
|
879 || operand_equal_p (*vr0min, vr1max, 0))
|
|
880 && operand_less_p (vr1min, *vr0min) == 1)
|
|
881 {
|
|
882 /* ( [ ) ] or ( )[ ] */
|
|
883 if (*vr0type == VR_ANTI_RANGE
|
|
884 && vr1type == VR_ANTI_RANGE)
|
|
885 *vr0min = vr1min;
|
|
886 else if (*vr0type == VR_RANGE
|
|
887 && vr1type == VR_RANGE)
|
|
888 *vr0max = vr1max;
|
|
889 else if (*vr0type == VR_RANGE
|
|
890 && vr1type == VR_ANTI_RANGE)
|
|
891 {
|
|
892 if (TREE_CODE (vr1max) == INTEGER_CST)
|
|
893 *vr0min = int_const_binop (PLUS_EXPR, vr1max,
|
|
894 build_int_cst (TREE_TYPE (vr1max), 1));
|
|
895 else
|
|
896 *vr0min = vr1max;
|
|
897 }
|
|
898 else if (*vr0type == VR_ANTI_RANGE
|
|
899 && vr1type == VR_RANGE)
|
|
900 {
|
|
901 *vr0type = VR_RANGE;
|
|
902 if (TREE_CODE (*vr0min) == INTEGER_CST)
|
|
903 *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
|
|
904 build_int_cst (TREE_TYPE (*vr0min), 1));
|
|
905 else
|
|
906 *vr0max = *vr0min;
|
|
907 *vr0min = vr1min;
|
|
908 }
|
|
909 else
|
|
910 gcc_unreachable ();
|
|
911 }
|
|
912
|
|
913 /* If we know the intersection is empty, there's no need to
|
|
914 conservatively add anything else to the set. */
|
|
915 if (*vr0type == VR_UNDEFINED)
|
|
916 return;
|
|
917
|
|
918 /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
|
|
919 result for the intersection. That's always a conservative
|
|
920 correct estimate unless VR1 is a constant singleton range
|
|
921 in which case we choose that. */
|
|
922 if (vr1type == VR_RANGE
|
|
923 && is_gimple_min_invariant (vr1min)
|
|
924 && vrp_operand_equal_p (vr1min, vr1max))
|
|
925 {
|
|
926 *vr0type = vr1type;
|
|
927 *vr0min = vr1min;
|
|
928 *vr0max = vr1max;
|
|
929 }
|
|
930 }
|
|
931
|
|
932 /* Helper for the intersection operation for value ranges. Given two
|
|
933 value ranges VR0 and VR1, return the intersection of the two
|
|
934 ranges. This may not be the smallest possible such range. */
|
|
935
|
|
936 value_range
|
|
937 value_range::intersect_helper (const value_range *vr0, const value_range *vr1)
|
|
938 {
|
|
939 /* If either range is VR_VARYING the other one wins. */
|
|
940 if (vr1->varying_p ())
|
|
941 return *vr0;
|
|
942 if (vr0->varying_p ())
|
|
943 return *vr1;
|
|
944
|
|
945 /* When either range is VR_UNDEFINED the resulting range is
|
|
946 VR_UNDEFINED, too. */
|
|
947 if (vr0->undefined_p ())
|
|
948 return *vr0;
|
|
949 if (vr1->undefined_p ())
|
|
950 return *vr1;
|
|
951
|
|
952 value_range_kind vr0kind = vr0->kind ();
|
|
953 tree vr0min = vr0->min ();
|
|
954 tree vr0max = vr0->max ();
|
|
955 intersect_ranges (&vr0kind, &vr0min, &vr0max,
|
|
956 vr1->kind (), vr1->min (), vr1->max ());
|
|
957 /* Make sure to canonicalize the result though as the inversion of a
|
|
958 VR_RANGE can still be a VR_RANGE. Work on a temporary so we can
|
|
959 fall back to vr0 when this turns things to varying. */
|
|
960 value_range tem;
|
|
961 if (vr0kind == VR_UNDEFINED)
|
|
962 tem.set_undefined ();
|
|
963 else if (vr0kind == VR_VARYING)
|
|
964 tem.set_varying (vr0->type ());
|
|
965 else
|
|
966 tem.set (vr0min, vr0max, vr0kind);
|
|
967 /* If that failed, use the saved original VR0. */
|
|
968 if (tem.varying_p ())
|
|
969 return *vr0;
|
|
970
|
|
971 return tem;
|
|
972 }
|
|
973
|
|
974 /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
|
|
975 { VR1TYPE, VR0MIN, VR0MAX } and store the result
|
|
976 in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
|
|
977 possible such range. The resulting range is not canonicalized. */
|
|
978
|
|
979 static void
|
|
980 union_ranges (enum value_range_kind *vr0type,
|
|
981 tree *vr0min, tree *vr0max,
|
|
982 enum value_range_kind vr1type,
|
|
983 tree vr1min, tree vr1max)
|
|
984 {
|
|
985 int cmpmin = compare_values (*vr0min, vr1min);
|
|
986 int cmpmax = compare_values (*vr0max, vr1max);
|
|
987 bool mineq = cmpmin == 0;
|
|
988 bool maxeq = cmpmax == 0;
|
|
989
|
|
990 /* [] is vr0, () is vr1 in the following classification comments. */
|
|
991 if (mineq && maxeq)
|
|
992 {
|
|
993 /* [( )] */
|
|
994 if (*vr0type == vr1type)
|
|
995 /* Nothing to do for equal ranges. */
|
|
996 ;
|
|
997 else if ((*vr0type == VR_RANGE
|
|
998 && vr1type == VR_ANTI_RANGE)
|
|
999 || (*vr0type == VR_ANTI_RANGE
|
|
1000 && vr1type == VR_RANGE))
|
|
1001 {
|
|
1002 /* For anti-range with range union the result is varying. */
|
|
1003 goto give_up;
|
|
1004 }
|
|
1005 else
|
|
1006 gcc_unreachable ();
|
|
1007 }
|
|
1008 else if (operand_less_p (*vr0max, vr1min) == 1
|
|
1009 || operand_less_p (vr1max, *vr0min) == 1)
|
|
1010 {
|
|
1011 /* [ ] ( ) or ( ) [ ]
|
|
1012 If the ranges have an empty intersection, result of the union
|
|
1013 operation is the anti-range or if both are anti-ranges
|
|
1014 it covers all. */
|
|
1015 if (*vr0type == VR_ANTI_RANGE
|
|
1016 && vr1type == VR_ANTI_RANGE)
|
|
1017 goto give_up;
|
|
1018 else if (*vr0type == VR_ANTI_RANGE
|
|
1019 && vr1type == VR_RANGE)
|
|
1020 ;
|
|
1021 else if (*vr0type == VR_RANGE
|
|
1022 && vr1type == VR_ANTI_RANGE)
|
|
1023 {
|
|
1024 *vr0type = vr1type;
|
|
1025 *vr0min = vr1min;
|
|
1026 *vr0max = vr1max;
|
|
1027 }
|
|
1028 else if (*vr0type == VR_RANGE
|
|
1029 && vr1type == VR_RANGE)
|
|
1030 {
|
|
1031 /* The result is the convex hull of both ranges. */
|
|
1032 if (operand_less_p (*vr0max, vr1min) == 1)
|
|
1033 {
|
|
1034 /* If the result can be an anti-range, create one. */
|
|
1035 if (TREE_CODE (*vr0max) == INTEGER_CST
|
|
1036 && TREE_CODE (vr1min) == INTEGER_CST
|
|
1037 && vrp_val_is_min (*vr0min)
|
|
1038 && vrp_val_is_max (vr1max))
|
|
1039 {
|
|
1040 tree min = int_const_binop (PLUS_EXPR,
|
|
1041 *vr0max,
|
|
1042 build_int_cst (TREE_TYPE (*vr0max), 1));
|
|
1043 tree max = int_const_binop (MINUS_EXPR,
|
|
1044 vr1min,
|
|
1045 build_int_cst (TREE_TYPE (vr1min), 1));
|
|
1046 if (!operand_less_p (max, min))
|
|
1047 {
|
|
1048 *vr0type = VR_ANTI_RANGE;
|
|
1049 *vr0min = min;
|
|
1050 *vr0max = max;
|
|
1051 }
|
|
1052 else
|
|
1053 *vr0max = vr1max;
|
|
1054 }
|
|
1055 else
|
|
1056 *vr0max = vr1max;
|
|
1057 }
|
|
1058 else
|
|
1059 {
|
|
1060 /* If the result can be an anti-range, create one. */
|
|
1061 if (TREE_CODE (vr1max) == INTEGER_CST
|
|
1062 && TREE_CODE (*vr0min) == INTEGER_CST
|
|
1063 && vrp_val_is_min (vr1min)
|
|
1064 && vrp_val_is_max (*vr0max))
|
|
1065 {
|
|
1066 tree min = int_const_binop (PLUS_EXPR,
|
|
1067 vr1max,
|
|
1068 build_int_cst (TREE_TYPE (vr1max), 1));
|
|
1069 tree max = int_const_binop (MINUS_EXPR,
|
|
1070 *vr0min,
|
|
1071 build_int_cst (TREE_TYPE (*vr0min), 1));
|
|
1072 if (!operand_less_p (max, min))
|
|
1073 {
|
|
1074 *vr0type = VR_ANTI_RANGE;
|
|
1075 *vr0min = min;
|
|
1076 *vr0max = max;
|
|
1077 }
|
|
1078 else
|
|
1079 *vr0min = vr1min;
|
|
1080 }
|
|
1081 else
|
|
1082 *vr0min = vr1min;
|
|
1083 }
|
|
1084 }
|
|
1085 else
|
|
1086 gcc_unreachable ();
|
|
1087 }
|
|
1088 else if ((maxeq || cmpmax == 1)
|
|
1089 && (mineq || cmpmin == -1))
|
|
1090 {
|
|
1091 /* [ ( ) ] or [( ) ] or [ ( )] */
|
|
1092 if (*vr0type == VR_RANGE
|
|
1093 && vr1type == VR_RANGE)
|
|
1094 ;
|
|
1095 else if (*vr0type == VR_ANTI_RANGE
|
|
1096 && vr1type == VR_ANTI_RANGE)
|
|
1097 {
|
|
1098 *vr0type = vr1type;
|
|
1099 *vr0min = vr1min;
|
|
1100 *vr0max = vr1max;
|
|
1101 }
|
|
1102 else if (*vr0type == VR_ANTI_RANGE
|
|
1103 && vr1type == VR_RANGE)
|
|
1104 {
|
|
1105 /* Arbitrarily choose the right or left gap. */
|
|
1106 if (!mineq && TREE_CODE (vr1min) == INTEGER_CST)
|
|
1107 *vr0max = int_const_binop (MINUS_EXPR, vr1min,
|
|
1108 build_int_cst (TREE_TYPE (vr1min), 1));
|
|
1109 else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST)
|
|
1110 *vr0min = int_const_binop (PLUS_EXPR, vr1max,
|
|
1111 build_int_cst (TREE_TYPE (vr1max), 1));
|
|
1112 else
|
|
1113 goto give_up;
|
|
1114 }
|
|
1115 else if (*vr0type == VR_RANGE
|
|
1116 && vr1type == VR_ANTI_RANGE)
|
|
1117 /* The result covers everything. */
|
|
1118 goto give_up;
|
|
1119 else
|
|
1120 gcc_unreachable ();
|
|
1121 }
|
|
1122 else if ((maxeq || cmpmax == -1)
|
|
1123 && (mineq || cmpmin == 1))
|
|
1124 {
|
|
1125 /* ( [ ] ) or ([ ] ) or ( [ ]) */
|
|
1126 if (*vr0type == VR_RANGE
|
|
1127 && vr1type == VR_RANGE)
|
|
1128 {
|
|
1129 *vr0type = vr1type;
|
|
1130 *vr0min = vr1min;
|
|
1131 *vr0max = vr1max;
|
|
1132 }
|
|
1133 else if (*vr0type == VR_ANTI_RANGE
|
|
1134 && vr1type == VR_ANTI_RANGE)
|
|
1135 ;
|
|
1136 else if (*vr0type == VR_RANGE
|
|
1137 && vr1type == VR_ANTI_RANGE)
|
|
1138 {
|
|
1139 *vr0type = VR_ANTI_RANGE;
|
|
1140 if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST)
|
|
1141 {
|
|
1142 *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
|
|
1143 build_int_cst (TREE_TYPE (*vr0min), 1));
|
|
1144 *vr0min = vr1min;
|
|
1145 }
|
|
1146 else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST)
|
|
1147 {
|
|
1148 *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
|
|
1149 build_int_cst (TREE_TYPE (*vr0max), 1));
|
|
1150 *vr0max = vr1max;
|
|
1151 }
|
|
1152 else
|
|
1153 goto give_up;
|
|
1154 }
|
|
1155 else if (*vr0type == VR_ANTI_RANGE
|
|
1156 && vr1type == VR_RANGE)
|
|
1157 /* The result covers everything. */
|
|
1158 goto give_up;
|
|
1159 else
|
|
1160 gcc_unreachable ();
|
|
1161 }
|
|
1162 else if (cmpmin == -1
|
|
1163 && cmpmax == -1
|
|
1164 && (operand_less_p (vr1min, *vr0max) == 1
|
|
1165 || operand_equal_p (vr1min, *vr0max, 0)))
|
|
1166 {
|
|
1167 /* [ ( ] ) or [ ]( ) */
|
|
1168 if (*vr0type == VR_RANGE
|
|
1169 && vr1type == VR_RANGE)
|
|
1170 *vr0max = vr1max;
|
|
1171 else if (*vr0type == VR_ANTI_RANGE
|
|
1172 && vr1type == VR_ANTI_RANGE)
|
|
1173 *vr0min = vr1min;
|
|
1174 else if (*vr0type == VR_ANTI_RANGE
|
|
1175 && vr1type == VR_RANGE)
|
|
1176 {
|
|
1177 if (TREE_CODE (vr1min) == INTEGER_CST)
|
|
1178 *vr0max = int_const_binop (MINUS_EXPR, vr1min,
|
|
1179 build_int_cst (TREE_TYPE (vr1min), 1));
|
|
1180 else
|
|
1181 goto give_up;
|
|
1182 }
|
|
1183 else if (*vr0type == VR_RANGE
|
|
1184 && vr1type == VR_ANTI_RANGE)
|
|
1185 {
|
|
1186 if (TREE_CODE (*vr0max) == INTEGER_CST)
|
|
1187 {
|
|
1188 *vr0type = vr1type;
|
|
1189 *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
|
|
1190 build_int_cst (TREE_TYPE (*vr0max), 1));
|
|
1191 *vr0max = vr1max;
|
|
1192 }
|
|
1193 else
|
|
1194 goto give_up;
|
|
1195 }
|
|
1196 else
|
|
1197 gcc_unreachable ();
|
|
1198 }
|
|
1199 else if (cmpmin == 1
|
|
1200 && cmpmax == 1
|
|
1201 && (operand_less_p (*vr0min, vr1max) == 1
|
|
1202 || operand_equal_p (*vr0min, vr1max, 0)))
|
|
1203 {
|
|
1204 /* ( [ ) ] or ( )[ ] */
|
|
1205 if (*vr0type == VR_RANGE
|
|
1206 && vr1type == VR_RANGE)
|
|
1207 *vr0min = vr1min;
|
|
1208 else if (*vr0type == VR_ANTI_RANGE
|
|
1209 && vr1type == VR_ANTI_RANGE)
|
|
1210 *vr0max = vr1max;
|
|
1211 else if (*vr0type == VR_ANTI_RANGE
|
|
1212 && vr1type == VR_RANGE)
|
|
1213 {
|
|
1214 if (TREE_CODE (vr1max) == INTEGER_CST)
|
|
1215 *vr0min = int_const_binop (PLUS_EXPR, vr1max,
|
|
1216 build_int_cst (TREE_TYPE (vr1max), 1));
|
|
1217 else
|
|
1218 goto give_up;
|
|
1219 }
|
|
1220 else if (*vr0type == VR_RANGE
|
|
1221 && vr1type == VR_ANTI_RANGE)
|
|
1222 {
|
|
1223 if (TREE_CODE (*vr0min) == INTEGER_CST)
|
|
1224 {
|
|
1225 *vr0type = vr1type;
|
|
1226 *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
|
|
1227 build_int_cst (TREE_TYPE (*vr0min), 1));
|
|
1228 *vr0min = vr1min;
|
|
1229 }
|
|
1230 else
|
|
1231 goto give_up;
|
|
1232 }
|
|
1233 else
|
|
1234 gcc_unreachable ();
|
|
1235 }
|
|
1236 else
|
|
1237 goto give_up;
|
|
1238
|
|
1239 return;
|
|
1240
|
|
1241 give_up:
|
|
1242 *vr0type = VR_VARYING;
|
|
1243 *vr0min = NULL_TREE;
|
|
1244 *vr0max = NULL_TREE;
|
|
1245 }
|
|
1246
|
|
1247 /* Helper for meet operation for value ranges. Given two value ranges VR0 and
|
|
1248 VR1, return a range that contains both VR0 and VR1. This may not be the
|
|
1249 smallest possible such range. */
|
|
1250
|
|
1251 value_range
|
|
1252 value_range::union_helper (const value_range *vr0, const value_range *vr1)
|
|
1253 {
|
|
1254 /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
|
|
1255 if (vr1->undefined_p ()
|
|
1256 || vr0->varying_p ())
|
|
1257 return *vr0;
|
|
1258
|
|
1259 /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
|
|
1260 if (vr0->undefined_p ()
|
|
1261 || vr1->varying_p ())
|
|
1262 return *vr1;
|
|
1263
|
|
1264 value_range_kind vr0kind = vr0->kind ();
|
|
1265 tree vr0min = vr0->min ();
|
|
1266 tree vr0max = vr0->max ();
|
|
1267 union_ranges (&vr0kind, &vr0min, &vr0max,
|
|
1268 vr1->kind (), vr1->min (), vr1->max ());
|
|
1269
|
|
1270 /* Work on a temporary so we can still use vr0 when union returns varying. */
|
|
1271 value_range tem;
|
|
1272 if (vr0kind == VR_UNDEFINED)
|
|
1273 tem.set_undefined ();
|
|
1274 else if (vr0kind == VR_VARYING)
|
|
1275 tem.set_varying (vr0->type ());
|
|
1276 else
|
|
1277 tem.set (vr0min, vr0max, vr0kind);
|
|
1278
|
|
1279 /* Failed to find an efficient meet. Before giving up and setting
|
|
1280 the result to VARYING, see if we can at least derive a useful
|
|
1281 anti-range. */
|
|
1282 if (tem.varying_p ()
|
|
1283 && range_includes_zero_p (vr0) == 0
|
|
1284 && range_includes_zero_p (vr1) == 0)
|
|
1285 {
|
|
1286 tem.set_nonzero (vr0->type ());
|
|
1287 return tem;
|
|
1288 }
|
|
1289
|
|
1290 return tem;
|
|
1291 }
|
|
1292
|
|
1293 /* Meet operation for value ranges. Given two value ranges VR0 and
|
|
1294 VR1, store in VR0 a range that contains both VR0 and VR1. This
|
|
1295 may not be the smallest possible such range. */
|
|
1296
|
|
1297 void
|
|
1298 value_range::union_ (const value_range *other)
|
|
1299 {
|
|
1300 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
1301 {
|
|
1302 fprintf (dump_file, "Meeting\n ");
|
|
1303 dump_value_range (dump_file, this);
|
|
1304 fprintf (dump_file, "\nand\n ");
|
|
1305 dump_value_range (dump_file, other);
|
|
1306 fprintf (dump_file, "\n");
|
|
1307 }
|
|
1308
|
|
1309 *this = union_helper (this, other);
|
|
1310
|
|
1311 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
1312 {
|
|
1313 fprintf (dump_file, "to\n ");
|
|
1314 dump_value_range (dump_file, this);
|
|
1315 fprintf (dump_file, "\n");
|
|
1316 }
|
|
1317 }
|
|
1318
|
|
1319 /* Range union, but for references. */
|
|
1320
|
|
1321 void
|
|
1322 value_range::union_ (const value_range &r)
|
|
1323 {
|
|
1324 /* Disable details for now, because it makes the ranger dump
|
|
1325 unnecessarily verbose. */
|
|
1326 bool details = dump_flags & TDF_DETAILS;
|
|
1327 if (details)
|
|
1328 dump_flags &= ~TDF_DETAILS;
|
|
1329 union_ (&r);
|
|
1330 if (details)
|
|
1331 dump_flags |= TDF_DETAILS;
|
|
1332 }
|
|
1333
|
|
1334 void
|
|
1335 value_range::intersect (const value_range *other)
|
|
1336 {
|
|
1337 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
1338 {
|
|
1339 fprintf (dump_file, "Intersecting\n ");
|
|
1340 dump_value_range (dump_file, this);
|
|
1341 fprintf (dump_file, "\nand\n ");
|
|
1342 dump_value_range (dump_file, other);
|
|
1343 fprintf (dump_file, "\n");
|
|
1344 }
|
|
1345
|
|
1346 *this = intersect_helper (this, other);
|
|
1347
|
|
1348 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
1349 {
|
|
1350 fprintf (dump_file, "to\n ");
|
|
1351 dump_value_range (dump_file, this);
|
|
1352 fprintf (dump_file, "\n");
|
|
1353 }
|
|
1354 }
|
|
1355
|
|
1356 /* Range intersect, but for references. */
|
|
1357
|
|
1358 void
|
|
1359 value_range::intersect (const value_range &r)
|
|
1360 {
|
|
1361 /* Disable details for now, because it makes the ranger dump
|
|
1362 unnecessarily verbose. */
|
|
1363 bool details = dump_flags & TDF_DETAILS;
|
|
1364 if (details)
|
|
1365 dump_flags &= ~TDF_DETAILS;
|
|
1366 intersect (&r);
|
|
1367 if (details)
|
|
1368 dump_flags |= TDF_DETAILS;
|
|
1369 }
|
|
1370
|
|
1371 /* Return the inverse of a range. */
|
|
1372
|
|
1373 void
|
|
1374 value_range::invert ()
|
|
1375 {
|
|
1376 /* We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
|
|
1377 create non-canonical ranges. Use the constructors instead. */
|
|
1378 if (m_kind == VR_RANGE)
|
|
1379 *this = value_range (m_min, m_max, VR_ANTI_RANGE);
|
|
1380 else if (m_kind == VR_ANTI_RANGE)
|
|
1381 *this = value_range (m_min, m_max);
|
|
1382 else
|
|
1383 gcc_unreachable ();
|
|
1384 }
|
|
1385
|
|
1386 void
|
|
1387 value_range::dump (FILE *file) const
|
|
1388 {
|
|
1389 if (undefined_p ())
|
|
1390 fprintf (file, "UNDEFINED");
|
|
1391 else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
|
|
1392 {
|
|
1393 tree ttype = type ();
|
|
1394
|
|
1395 print_generic_expr (file, ttype);
|
|
1396 fprintf (file, " ");
|
|
1397
|
|
1398 fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : "");
|
|
1399
|
|
1400 if (INTEGRAL_TYPE_P (ttype)
|
|
1401 && !TYPE_UNSIGNED (ttype)
|
|
1402 && vrp_val_is_min (min ())
|
|
1403 && TYPE_PRECISION (ttype) != 1)
|
|
1404 fprintf (file, "-INF");
|
|
1405 else
|
|
1406 print_generic_expr (file, min ());
|
|
1407
|
|
1408 fprintf (file, ", ");
|
|
1409
|
|
1410 if (supports_type_p (ttype)
|
|
1411 && vrp_val_is_max (max ())
|
|
1412 && TYPE_PRECISION (ttype) != 1)
|
|
1413 fprintf (file, "+INF");
|
|
1414 else
|
|
1415 print_generic_expr (file, max ());
|
|
1416
|
|
1417 fprintf (file, "]");
|
|
1418 }
|
|
1419 else if (varying_p ())
|
|
1420 {
|
|
1421 print_generic_expr (file, type ());
|
|
1422 fprintf (file, " VARYING");
|
|
1423 }
|
|
1424 else
|
|
1425 gcc_unreachable ();
|
|
1426 }
|
|
1427
|
|
1428 void
|
|
1429 value_range::dump () const
|
|
1430 {
|
|
1431 dump (stderr);
|
|
1432 }
|
|
1433
|
|
1434 void
|
|
1435 dump_value_range (FILE *file, const value_range *vr)
|
|
1436 {
|
|
1437 if (!vr)
|
|
1438 fprintf (file, "[]");
|
|
1439 else
|
|
1440 vr->dump (file);
|
|
1441 }
|
|
1442
|
|
1443 DEBUG_FUNCTION void
|
|
1444 debug (const value_range *vr)
|
|
1445 {
|
|
1446 dump_value_range (stderr, vr);
|
|
1447 }
|
|
1448
|
|
1449 DEBUG_FUNCTION void
|
|
1450 debug (const value_range &vr)
|
|
1451 {
|
|
1452 dump_value_range (stderr, &vr);
|
|
1453 }
|
|
1454
|
|
1455 /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
|
|
1456 so that *VR0 U *VR1 == *AR. Returns true if that is possible,
|
|
1457 false otherwise. If *AR can be represented with a single range
|
|
1458 *VR1 will be VR_UNDEFINED. */
|
|
1459
|
|
1460 bool
|
|
1461 ranges_from_anti_range (const value_range *ar,
|
|
1462 value_range *vr0, value_range *vr1)
|
|
1463 {
|
|
1464 tree type = ar->type ();
|
|
1465
|
|
1466 vr0->set_undefined ();
|
|
1467 vr1->set_undefined ();
|
|
1468
|
|
1469 /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
|
|
1470 [A+1, +INF]. Not sure if this helps in practice, though. */
|
|
1471
|
|
1472 if (ar->kind () != VR_ANTI_RANGE
|
|
1473 || TREE_CODE (ar->min ()) != INTEGER_CST
|
|
1474 || TREE_CODE (ar->max ()) != INTEGER_CST
|
|
1475 || !vrp_val_min (type)
|
|
1476 || !vrp_val_max (type))
|
|
1477 return false;
|
|
1478
|
|
1479 if (tree_int_cst_lt (vrp_val_min (type), ar->min ()))
|
|
1480 vr0->set (vrp_val_min (type),
|
|
1481 wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
|
|
1482 if (tree_int_cst_lt (ar->max (), vrp_val_max (type)))
|
|
1483 vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
|
|
1484 vrp_val_max (type));
|
|
1485 if (vr0->undefined_p ())
|
|
1486 {
|
|
1487 *vr0 = *vr1;
|
|
1488 vr1->set_undefined ();
|
|
1489 }
|
|
1490
|
|
1491 return !vr0->undefined_p ();
|
|
1492 }
|
|
1493
|
|
1494 bool
|
|
1495 range_has_numeric_bounds_p (const value_range *vr)
|
|
1496 {
|
|
1497 return (vr->min ()
|
|
1498 && TREE_CODE (vr->min ()) == INTEGER_CST
|
|
1499 && TREE_CODE (vr->max ()) == INTEGER_CST);
|
|
1500 }
|
|
1501
|
|
1502 /* Return the maximum value for TYPE. */
|
|
1503
|
|
1504 tree
|
|
1505 vrp_val_max (const_tree type)
|
|
1506 {
|
|
1507 if (INTEGRAL_TYPE_P (type))
|
|
1508 return TYPE_MAX_VALUE (type);
|
|
1509 if (POINTER_TYPE_P (type))
|
|
1510 {
|
|
1511 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
|
|
1512 return wide_int_to_tree (const_cast<tree> (type), max);
|
|
1513 }
|
|
1514 return NULL_TREE;
|
|
1515 }
|
|
1516
|
|
1517 /* Return the minimum value for TYPE. */
|
|
1518
|
|
1519 tree
|
|
1520 vrp_val_min (const_tree type)
|
|
1521 {
|
|
1522 if (INTEGRAL_TYPE_P (type))
|
|
1523 return TYPE_MIN_VALUE (type);
|
|
1524 if (POINTER_TYPE_P (type))
|
|
1525 return build_zero_cst (const_cast<tree> (type));
|
|
1526 return NULL_TREE;
|
|
1527 }
|
|
1528
|
|
1529 /* Return whether VAL is equal to the maximum value of its type.
|
|
1530 We can't do a simple equality comparison with TYPE_MAX_VALUE because
|
|
1531 C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
|
|
1532 is not == to the integer constant with the same value in the type. */
|
|
1533
|
|
1534 bool
|
|
1535 vrp_val_is_max (const_tree val)
|
|
1536 {
|
|
1537 tree type_max = vrp_val_max (TREE_TYPE (val));
|
|
1538 return (val == type_max
|
|
1539 || (type_max != NULL_TREE
|
|
1540 && operand_equal_p (val, type_max, 0)));
|
|
1541 }
|
|
1542
|
|
1543 /* Return whether VAL is equal to the minimum value of its type. */
|
|
1544
|
|
1545 bool
|
|
1546 vrp_val_is_min (const_tree val)
|
|
1547 {
|
|
1548 tree type_min = vrp_val_min (TREE_TYPE (val));
|
|
1549 return (val == type_min
|
|
1550 || (type_min != NULL_TREE
|
|
1551 && operand_equal_p (val, type_min, 0)));
|
|
1552 }
|
|
1553
|
|
1554 /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
|
|
1555
|
|
1556 bool
|
|
1557 vrp_operand_equal_p (const_tree val1, const_tree val2)
|
|
1558 {
|
|
1559 if (val1 == val2)
|
|
1560 return true;
|
|
1561 if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
|
|
1562 return false;
|
|
1563 return true;
|
|
1564 }
|