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