range-op.cc revision 1.1.1.1
1/* Code for range operators. 2 Copyright (C) 2017-2020 Free Software Foundation, Inc. 3 Contributed by Andrew MacLeod <amacleod@redhat.com> 4 and Aldy Hernandez <aldyh@redhat.com>. 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify 9it under the terms of the GNU General Public License as published by 10the Free Software Foundation; either version 3, or (at your option) 11any later version. 12 13GCC is distributed in the hope that it will be useful, 14but WITHOUT ANY WARRANTY; without even the implied warranty of 15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16GNU General Public License for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING3. If not see 20<http://www.gnu.org/licenses/>. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "backend.h" 26#include "insn-codes.h" 27#include "rtl.h" 28#include "tree.h" 29#include "gimple.h" 30#include "cfghooks.h" 31#include "tree-pass.h" 32#include "ssa.h" 33#include "optabs-tree.h" 34#include "gimple-pretty-print.h" 35#include "diagnostic-core.h" 36#include "flags.h" 37#include "fold-const.h" 38#include "stor-layout.h" 39#include "calls.h" 40#include "cfganal.h" 41#include "gimple-fold.h" 42#include "tree-eh.h" 43#include "gimple-iterator.h" 44#include "gimple-walk.h" 45#include "tree-cfg.h" 46#include "wide-int.h" 47#include "range-op.h" 48 49// Return the upper limit for a type. 50 51static inline wide_int 52max_limit (const_tree type) 53{ 54 return wi::max_value (TYPE_PRECISION (type) , TYPE_SIGN (type)); 55} 56 57// Return the lower limit for a type. 58 59static inline wide_int 60min_limit (const_tree type) 61{ 62 return wi::min_value (TYPE_PRECISION (type) , TYPE_SIGN (type)); 63} 64 65// If the range of either op1 or op2 is undefined, set the result to 66// undefined and return TRUE. 67 68inline bool 69empty_range_check (value_range &r, 70 const value_range &op1, const value_range & op2) 71{ 72 if (op1.undefined_p () || op2.undefined_p ()) 73 { 74 r.set_undefined (); 75 return true; 76 } 77 else 78 return false; 79} 80 81// Return TRUE if shifting by OP is undefined behavior, and set R to 82// the appropriate range. 83 84static inline bool 85undefined_shift_range_check (value_range &r, tree type, const value_range op) 86{ 87 if (op.undefined_p ()) 88 { 89 r = value_range (); 90 return true; 91 } 92 93 // Shifting by any values outside [0..prec-1], gets undefined 94 // behavior from the shift operation. We cannot even trust 95 // SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl 96 // shifts, and the operation at the tree level may be widened. 97 if (wi::lt_p (op.lower_bound (), 0, TYPE_SIGN (op.type ())) 98 || wi::ge_p (op.upper_bound (), 99 TYPE_PRECISION (type), TYPE_SIGN (op.type ()))) 100 { 101 r = value_range (type); 102 return true; 103 } 104 return false; 105} 106 107// Return TRUE if 0 is within [WMIN, WMAX]. 108 109static inline bool 110wi_includes_zero_p (tree type, const wide_int &wmin, const wide_int &wmax) 111{ 112 signop sign = TYPE_SIGN (type); 113 return wi::le_p (wmin, 0, sign) && wi::ge_p (wmax, 0, sign); 114} 115 116// Return TRUE if [WMIN, WMAX] is the singleton 0. 117 118static inline bool 119wi_zero_p (tree type, const wide_int &wmin, const wide_int &wmax) 120{ 121 unsigned prec = TYPE_PRECISION (type); 122 return wmin == wmax && wi::eq_p (wmin, wi::zero (prec)); 123} 124 125// Default wide_int fold operation returns [MIN, MAX]. 126 127void 128range_operator::wi_fold (value_range &r, tree type, 129 const wide_int &lh_lb ATTRIBUTE_UNUSED, 130 const wide_int &lh_ub ATTRIBUTE_UNUSED, 131 const wide_int &rh_lb ATTRIBUTE_UNUSED, 132 const wide_int &rh_ub ATTRIBUTE_UNUSED) const 133{ 134 gcc_checking_assert (value_range::supports_type_p (type)); 135 r = value_range (type); 136} 137 138// The default for fold is to break all ranges into sub-ranges and 139// invoke the wi_fold method on each sub-range pair. 140 141bool 142range_operator::fold_range (value_range &r, tree type, 143 const value_range &lh, 144 const value_range &rh) const 145{ 146 gcc_checking_assert (value_range::supports_type_p (type)); 147 if (empty_range_check (r, lh, rh)) 148 return true; 149 150 value_range tmp; 151 r.set_undefined (); 152 for (unsigned x = 0; x < lh.num_pairs (); ++x) 153 for (unsigned y = 0; y < rh.num_pairs (); ++y) 154 { 155 wide_int lh_lb = lh.lower_bound (x); 156 wide_int lh_ub = lh.upper_bound (x); 157 wide_int rh_lb = rh.lower_bound (y); 158 wide_int rh_ub = rh.upper_bound (y); 159 wi_fold (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub); 160 r.union_ (tmp); 161 if (r.varying_p ()) 162 return true; 163 } 164 return true; 165} 166 167// The default for op1_range is to return false. 168 169bool 170range_operator::op1_range (value_range &r ATTRIBUTE_UNUSED, 171 tree type ATTRIBUTE_UNUSED, 172 const value_range &lhs ATTRIBUTE_UNUSED, 173 const value_range &op2 ATTRIBUTE_UNUSED) const 174{ 175 return false; 176} 177 178// The default for op2_range is to return false. 179 180bool 181range_operator::op2_range (value_range &r ATTRIBUTE_UNUSED, 182 tree type ATTRIBUTE_UNUSED, 183 const value_range &lhs ATTRIBUTE_UNUSED, 184 const value_range &op1 ATTRIBUTE_UNUSED) const 185{ 186 return false; 187} 188 189 190// Create and return a range from a pair of wide-ints that are known 191// to have overflowed (or underflowed). 192 193static void 194value_range_from_overflowed_bounds (value_range &r, tree type, 195 const wide_int &wmin, 196 const wide_int &wmax) 197{ 198 const signop sgn = TYPE_SIGN (type); 199 const unsigned int prec = TYPE_PRECISION (type); 200 201 wide_int tmin = wide_int::from (wmin, prec, sgn); 202 wide_int tmax = wide_int::from (wmax, prec, sgn); 203 204 bool covers = false; 205 wide_int tem = tmin; 206 tmin = tmax + 1; 207 if (wi::cmp (tmin, tmax, sgn) < 0) 208 covers = true; 209 tmax = tem - 1; 210 if (wi::cmp (tmax, tem, sgn) > 0) 211 covers = true; 212 213 // If the anti-range would cover nothing, drop to varying. 214 // Likewise if the anti-range bounds are outside of the types 215 // values. 216 if (covers || wi::cmp (tmin, tmax, sgn) > 0) 217 r = value_range (type); 218 else 219 r = value_range (type, tmin, tmax, VR_ANTI_RANGE); 220} 221 222// Create and return a range from a pair of wide-ints. MIN_OVF and 223// MAX_OVF describe any overflow that might have occurred while 224// calculating WMIN and WMAX respectively. 225 226static void 227value_range_with_overflow (value_range &r, tree type, 228 const wide_int &wmin, const wide_int &wmax, 229 wi::overflow_type min_ovf = wi::OVF_NONE, 230 wi::overflow_type max_ovf = wi::OVF_NONE) 231{ 232 const signop sgn = TYPE_SIGN (type); 233 const unsigned int prec = TYPE_PRECISION (type); 234 const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type); 235 236 // For one bit precision if max != min, then the range covers all 237 // values. 238 if (prec == 1 && wi::ne_p (wmax, wmin)) 239 { 240 r = value_range (type); 241 return; 242 } 243 244 if (overflow_wraps) 245 { 246 // If overflow wraps, truncate the values and adjust the range, 247 // kind, and bounds appropriately. 248 if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE)) 249 { 250 wide_int tmin = wide_int::from (wmin, prec, sgn); 251 wide_int tmax = wide_int::from (wmax, prec, sgn); 252 // If the limits are swapped, we wrapped around and cover 253 // the entire range. 254 if (wi::gt_p (tmin, tmax, sgn)) 255 r = value_range (type); 256 else 257 // No overflow or both overflow or underflow. The range 258 // kind stays normal. 259 r = value_range (type, tmin, tmax); 260 return; 261 } 262 263 if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE) 264 || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE)) 265 value_range_from_overflowed_bounds (r, type, wmin, wmax); 266 else 267 // Other underflow and/or overflow, drop to VR_VARYING. 268 r = value_range (type); 269 } 270 else 271 { 272 // If overflow does not wrap, saturate to [MIN, MAX]. 273 wide_int new_lb, new_ub; 274 if (min_ovf == wi::OVF_UNDERFLOW) 275 new_lb = wi::min_value (prec, sgn); 276 else if (min_ovf == wi::OVF_OVERFLOW) 277 new_lb = wi::max_value (prec, sgn); 278 else 279 new_lb = wmin; 280 281 if (max_ovf == wi::OVF_UNDERFLOW) 282 new_ub = wi::min_value (prec, sgn); 283 else if (max_ovf == wi::OVF_OVERFLOW) 284 new_ub = wi::max_value (prec, sgn); 285 else 286 new_ub = wmax; 287 288 r = value_range (type, new_lb, new_ub); 289 } 290} 291 292// Create and return a range from a pair of wide-ints. Canonicalize 293// the case where the bounds are swapped. In which case, we transform 294// [10,5] into [MIN,5][10,MAX]. 295 296static inline void 297create_possibly_reversed_range (value_range &r, tree type, 298 const wide_int &new_lb, const wide_int &new_ub) 299{ 300 signop s = TYPE_SIGN (type); 301 // If the bounds are swapped, treat the result as if an overflow occured. 302 if (wi::gt_p (new_lb, new_ub, s)) 303 value_range_from_overflowed_bounds (r, type, new_lb, new_ub); 304 else 305 // Otherwise its just a normal range. 306 r = value_range (type, new_lb, new_ub); 307} 308 309// Return a value_range instance that is a boolean TRUE. 310 311static inline value_range 312range_true (tree type) 313{ 314 unsigned prec = TYPE_PRECISION (type); 315 return value_range (type, wi::one (prec), wi::one (prec)); 316} 317 318// Return a value_range instance that is a boolean FALSE. 319 320static inline value_range 321range_false (tree type) 322{ 323 unsigned prec = TYPE_PRECISION (type); 324 return value_range (type, wi::zero (prec), wi::zero (prec)); 325} 326 327// Return a value_range that covers both true and false. 328 329static inline value_range 330range_true_and_false (tree type) 331{ 332 unsigned prec = TYPE_PRECISION (type); 333 return value_range (type, wi::zero (prec), wi::one (prec)); 334} 335 336enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL }; 337 338// Return the summary information about boolean range LHS. Return an 339// "interesting" range in R. For EMPTY or FULL, return the equivalent 340// range for TYPE, for BRS_TRUE and BRS false, return the negation of 341// the bool range. 342 343static bool_range_state 344get_bool_state (value_range &r, const value_range &lhs, tree val_type) 345{ 346 // If there is no result, then this is unexecutable. 347 if (lhs.undefined_p ()) 348 { 349 r.set_undefined (); 350 return BRS_EMPTY; 351 } 352 353 // If the bounds aren't the same, then it's not a constant. 354 if (!wi::eq_p (lhs.upper_bound (), lhs.lower_bound ())) 355 { 356 r.set_varying (val_type); 357 return BRS_FULL; 358 } 359 360 if (lhs.zero_p ()) 361 return BRS_FALSE; 362 363 return BRS_TRUE; 364} 365 366 367class operator_equal : public range_operator 368{ 369public: 370 virtual bool fold_range (value_range &r, tree type, 371 const value_range &op1, 372 const value_range &op2) const; 373 virtual bool op1_range (value_range &r, tree type, 374 const value_range &lhs, 375 const value_range &val) const; 376 virtual bool op2_range (value_range &r, tree type, 377 const value_range &lhs, 378 const value_range &val) const; 379} op_equal; 380 381bool 382operator_equal::fold_range (value_range &r, tree type, 383 const value_range &op1, 384 const value_range &op2) const 385{ 386 if (empty_range_check (r, op1, op2)) 387 return true; 388 389 // We can be sure the values are always equal or not if both ranges 390 // consist of a single value, and then compare them. 391 if (wi::eq_p (op1.lower_bound (), op1.upper_bound ()) 392 && wi::eq_p (op2.lower_bound (), op2.upper_bound ())) 393 { 394 if (wi::eq_p (op1.lower_bound (), op2.upper_bound())) 395 r = range_true (type); 396 else 397 r = range_false (type); 398 } 399 else 400 { 401 // If ranges do not intersect, we know the range is not equal, 402 // otherwise we don't know anything for sure. 403 r = op1; 404 r.intersect (op2); 405 if (r.undefined_p ()) 406 r = range_false (type); 407 else 408 r = range_true_and_false (type); 409 } 410 return true; 411} 412 413bool 414operator_equal::op1_range (value_range &r, tree type, 415 const value_range &lhs, 416 const value_range &op2) const 417{ 418 switch (get_bool_state (r, lhs, type)) 419 { 420 case BRS_FALSE: 421 // If the result is false, the only time we know anything is 422 // if OP2 is a constant. 423 if (wi::eq_p (op2.lower_bound(), op2.upper_bound())) 424 { 425 r = op2; 426 r.invert (); 427 } 428 else 429 r.set_varying (type); 430 break; 431 432 case BRS_TRUE: 433 // If it's true, the result is the same as OP2. 434 r = op2; 435 break; 436 437 default: 438 break; 439 } 440 return true; 441} 442 443bool 444operator_equal::op2_range (value_range &r, tree type, 445 const value_range &lhs, 446 const value_range &op1) const 447{ 448 return operator_equal::op1_range (r, type, lhs, op1); 449} 450 451 452class operator_not_equal : public range_operator 453{ 454public: 455 virtual bool fold_range (value_range &r, tree type, 456 const value_range &op1, 457 const value_range &op2) const; 458 virtual bool op1_range (value_range &r, tree type, 459 const value_range &lhs, 460 const value_range &op2) const; 461 virtual bool op2_range (value_range &r, tree type, 462 const value_range &lhs, 463 const value_range &op1) const; 464} op_not_equal; 465 466bool 467operator_not_equal::fold_range (value_range &r, tree type, 468 const value_range &op1, 469 const value_range &op2) const 470{ 471 if (empty_range_check (r, op1, op2)) 472 return true; 473 474 // We can be sure the values are always equal or not if both ranges 475 // consist of a single value, and then compare them. 476 if (wi::eq_p (op1.lower_bound (), op1.upper_bound ()) 477 && wi::eq_p (op2.lower_bound (), op2.upper_bound ())) 478 { 479 if (wi::ne_p (op1.lower_bound (), op2.upper_bound())) 480 r = range_true (type); 481 else 482 r = range_false (type); 483 } 484 else 485 { 486 // If ranges do not intersect, we know the range is not equal, 487 // otherwise we don't know anything for sure. 488 r = op1; 489 r.intersect (op2); 490 if (r.undefined_p ()) 491 r = range_true (type); 492 else 493 r = range_true_and_false (type); 494 } 495 return true; 496} 497 498bool 499operator_not_equal::op1_range (value_range &r, tree type, 500 const value_range &lhs, 501 const value_range &op2) const 502{ 503 switch (get_bool_state (r, lhs, type)) 504 { 505 case BRS_TRUE: 506 // If the result is true, the only time we know anything is if 507 // OP2 is a constant. 508 if (wi::eq_p (op2.lower_bound(), op2.upper_bound())) 509 { 510 r = op2; 511 r.invert (); 512 } 513 else 514 r.set_varying (type); 515 break; 516 517 case BRS_FALSE: 518 // If its true, the result is the same as OP2. 519 r = op2; 520 break; 521 522 default: 523 break; 524 } 525 return true; 526} 527 528 529bool 530operator_not_equal::op2_range (value_range &r, tree type, 531 const value_range &lhs, 532 const value_range &op1) const 533{ 534 return operator_not_equal::op1_range (r, type, lhs, op1); 535} 536 537// (X < VAL) produces the range of [MIN, VAL - 1]. 538 539static void 540build_lt (value_range &r, tree type, const wide_int &val) 541{ 542 wi::overflow_type ov; 543 wide_int lim = wi::sub (val, 1, TYPE_SIGN (type), &ov); 544 545 // If val - 1 underflows, check if X < MIN, which is an empty range. 546 if (ov) 547 r.set_undefined (); 548 else 549 r = value_range (type, min_limit (type), lim); 550} 551 552// (X <= VAL) produces the range of [MIN, VAL]. 553 554static void 555build_le (value_range &r, tree type, const wide_int &val) 556{ 557 r = value_range (type, min_limit (type), val); 558} 559 560// (X > VAL) produces the range of [VAL + 1, MAX]. 561 562static void 563build_gt (value_range &r, tree type, const wide_int &val) 564{ 565 wi::overflow_type ov; 566 wide_int lim = wi::add (val, 1, TYPE_SIGN (type), &ov); 567 // If val + 1 overflows, check is for X > MAX, which is an empty range. 568 if (ov) 569 r.set_undefined (); 570 else 571 r = value_range (type, lim, max_limit (type)); 572} 573 574// (X >= val) produces the range of [VAL, MAX]. 575 576static void 577build_ge (value_range &r, tree type, const wide_int &val) 578{ 579 r = value_range (type, val, max_limit (type)); 580} 581 582 583class operator_lt : public range_operator 584{ 585public: 586 virtual bool fold_range (value_range &r, tree type, 587 const value_range &op1, 588 const value_range &op2) const; 589 virtual bool op1_range (value_range &r, tree type, 590 const value_range &lhs, 591 const value_range &op2) const; 592 virtual bool op2_range (value_range &r, tree type, 593 const value_range &lhs, 594 const value_range &op1) const; 595} op_lt; 596 597bool 598operator_lt::fold_range (value_range &r, tree type, 599 const value_range &op1, 600 const value_range &op2) const 601{ 602 if (empty_range_check (r, op1, op2)) 603 return true; 604 605 signop sign = TYPE_SIGN (op1.type ()); 606 gcc_checking_assert (sign == TYPE_SIGN (op2.type ())); 607 608 if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign)) 609 r = range_true (type); 610 else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign)) 611 r = range_false (type); 612 else 613 r = range_true_and_false (type); 614 return true; 615} 616 617bool 618operator_lt::op1_range (value_range &r, tree type, 619 const value_range &lhs, 620 const value_range &op2) const 621{ 622 switch (get_bool_state (r, lhs, type)) 623 { 624 case BRS_TRUE: 625 build_lt (r, type, op2.upper_bound ()); 626 break; 627 628 case BRS_FALSE: 629 build_ge (r, type, op2.lower_bound ()); 630 break; 631 632 default: 633 break; 634 } 635 return true; 636} 637 638bool 639operator_lt::op2_range (value_range &r, tree type, 640 const value_range &lhs, 641 const value_range &op1) const 642{ 643 switch (get_bool_state (r, lhs, type)) 644 { 645 case BRS_FALSE: 646 build_le (r, type, op1.upper_bound ()); 647 break; 648 649 case BRS_TRUE: 650 build_gt (r, type, op1.lower_bound ()); 651 break; 652 653 default: 654 break; 655 } 656 return true; 657} 658 659 660class operator_le : public range_operator 661{ 662public: 663 virtual bool fold_range (value_range &r, tree type, 664 const value_range &op1, 665 const value_range &op2) const; 666 virtual bool op1_range (value_range &r, tree type, 667 const value_range &lhs, 668 const value_range &op2) const; 669 virtual bool op2_range (value_range &r, tree type, 670 const value_range &lhs, 671 const value_range &op1) const; 672} op_le; 673 674bool 675operator_le::fold_range (value_range &r, tree type, 676 const value_range &op1, 677 const value_range &op2) const 678{ 679 if (empty_range_check (r, op1, op2)) 680 return true; 681 682 signop sign = TYPE_SIGN (op1.type ()); 683 gcc_checking_assert (sign == TYPE_SIGN (op2.type ())); 684 685 if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign)) 686 r = range_true (type); 687 else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign)) 688 r = range_false (type); 689 else 690 r = range_true_and_false (type); 691 return true; 692} 693 694bool 695operator_le::op1_range (value_range &r, tree type, 696 const value_range &lhs, 697 const value_range &op2) const 698{ 699 switch (get_bool_state (r, lhs, type)) 700 { 701 case BRS_TRUE: 702 build_le (r, type, op2.upper_bound ()); 703 break; 704 705 case BRS_FALSE: 706 build_gt (r, type, op2.lower_bound ()); 707 break; 708 709 default: 710 break; 711 } 712 return true; 713} 714 715bool 716operator_le::op2_range (value_range &r, tree type, 717 const value_range &lhs, 718 const value_range &op1) const 719{ 720 switch (get_bool_state (r, lhs, type)) 721 { 722 case BRS_FALSE: 723 build_lt (r, type, op1.upper_bound ()); 724 break; 725 726 case BRS_TRUE: 727 build_ge (r, type, op1.lower_bound ()); 728 break; 729 730 default: 731 break; 732 } 733 return true; 734} 735 736 737class operator_gt : public range_operator 738{ 739public: 740 virtual bool fold_range (value_range &r, tree type, 741 const value_range &op1, 742 const value_range &op2) const; 743 virtual bool op1_range (value_range &r, tree type, 744 const value_range &lhs, 745 const value_range &op2) const; 746 virtual bool op2_range (value_range &r, tree type, 747 const value_range &lhs, 748 const value_range &op1) const; 749} op_gt; 750 751bool 752operator_gt::fold_range (value_range &r, tree type, 753 const value_range &op1, const value_range &op2) const 754{ 755 if (empty_range_check (r, op1, op2)) 756 return true; 757 758 signop sign = TYPE_SIGN (op1.type ()); 759 gcc_checking_assert (sign == TYPE_SIGN (op2.type ())); 760 761 if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign)) 762 r = range_true (type); 763 else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign)) 764 r = range_false (type); 765 else 766 r = range_true_and_false (type); 767 return true; 768} 769 770bool 771operator_gt::op1_range (value_range &r, tree type, 772 const value_range &lhs, const value_range &op2) const 773{ 774 switch (get_bool_state (r, lhs, type)) 775 { 776 case BRS_TRUE: 777 build_gt (r, type, op2.lower_bound ()); 778 break; 779 780 case BRS_FALSE: 781 build_le (r, type, op2.upper_bound ()); 782 break; 783 784 default: 785 break; 786 } 787 return true; 788} 789 790bool 791operator_gt::op2_range (value_range &r, tree type, 792 const value_range &lhs, 793 const value_range &op1) const 794{ 795 switch (get_bool_state (r, lhs, type)) 796 { 797 case BRS_FALSE: 798 build_ge (r, type, op1.lower_bound ()); 799 break; 800 801 case BRS_TRUE: 802 build_lt (r, type, op1.upper_bound ()); 803 break; 804 805 default: 806 break; 807 } 808 return true; 809} 810 811 812class operator_ge : public range_operator 813{ 814public: 815 virtual bool fold_range (value_range &r, tree type, 816 const value_range &op1, 817 const value_range &op2) const; 818 virtual bool op1_range (value_range &r, tree type, 819 const value_range &lhs, 820 const value_range &op2) const; 821 virtual bool op2_range (value_range &r, tree type, 822 const value_range &lhs, 823 const value_range &op1) const; 824} op_ge; 825 826bool 827operator_ge::fold_range (value_range &r, tree type, 828 const value_range &op1, 829 const value_range &op2) const 830{ 831 if (empty_range_check (r, op1, op2)) 832 return true; 833 834 signop sign = TYPE_SIGN (op1.type ()); 835 gcc_checking_assert (sign == TYPE_SIGN (op2.type ())); 836 837 if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign)) 838 r = range_true (type); 839 else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign)) 840 r = range_false (type); 841 else 842 r = range_true_and_false (type); 843 return true; 844} 845 846bool 847operator_ge::op1_range (value_range &r, tree type, 848 const value_range &lhs, 849 const value_range &op2) const 850{ 851 switch (get_bool_state (r, lhs, type)) 852 { 853 case BRS_TRUE: 854 build_ge (r, type, op2.lower_bound ()); 855 break; 856 857 case BRS_FALSE: 858 build_lt (r, type, op2.upper_bound ()); 859 break; 860 861 default: 862 break; 863 } 864 return true; 865} 866 867bool 868operator_ge::op2_range (value_range &r, tree type, 869 const value_range &lhs, 870 const value_range &op1) const 871{ 872 switch (get_bool_state (r, lhs, type)) 873 { 874 case BRS_FALSE: 875 build_gt (r, type, op1.lower_bound ()); 876 break; 877 878 case BRS_TRUE: 879 build_le (r, type, op1.upper_bound ()); 880 break; 881 882 default: 883 break; 884 } 885 return true; 886} 887 888 889class operator_plus : public range_operator 890{ 891public: 892 virtual bool op1_range (value_range &r, tree type, 893 const value_range &lhs, 894 const value_range &op2) const; 895 virtual bool op2_range (value_range &r, tree type, 896 const value_range &lhs, 897 const value_range &op1) const; 898 virtual void wi_fold (value_range &r, tree type, 899 const wide_int &lh_lb, 900 const wide_int &lh_ub, 901 const wide_int &rh_lb, 902 const wide_int &rh_ub) const; 903} op_plus; 904 905void 906operator_plus::wi_fold (value_range &r, tree type, 907 const wide_int &lh_lb, const wide_int &lh_ub, 908 const wide_int &rh_lb, const wide_int &rh_ub) const 909{ 910 wi::overflow_type ov_lb, ov_ub; 911 signop s = TYPE_SIGN (type); 912 wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb); 913 wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub); 914 value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub); 915} 916 917bool 918operator_plus::op1_range (value_range &r, tree type, 919 const value_range &lhs, 920 const value_range &op2) const 921{ 922 return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op2); 923} 924 925bool 926operator_plus::op2_range (value_range &r, tree type, 927 const value_range &lhs, 928 const value_range &op1) const 929{ 930 return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op1); 931} 932 933 934class operator_minus : public range_operator 935{ 936public: 937 virtual bool op1_range (value_range &r, tree type, 938 const value_range &lhs, 939 const value_range &op2) const; 940 virtual bool op2_range (value_range &r, tree type, 941 const value_range &lhs, 942 const value_range &op1) const; 943 virtual void wi_fold (value_range &r, tree type, 944 const wide_int &lh_lb, 945 const wide_int &lh_ub, 946 const wide_int &rh_lb, 947 const wide_int &rh_ub) const; 948} op_minus; 949 950void 951operator_minus::wi_fold (value_range &r, tree type, 952 const wide_int &lh_lb, const wide_int &lh_ub, 953 const wide_int &rh_lb, const wide_int &rh_ub) const 954{ 955 wi::overflow_type ov_lb, ov_ub; 956 signop s = TYPE_SIGN (type); 957 wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb); 958 wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub); 959 value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub); 960} 961 962bool 963operator_minus::op1_range (value_range &r, tree type, 964 const value_range &lhs, 965 const value_range &op2) const 966{ 967 return range_op_handler (PLUS_EXPR, type)->fold_range (r, type, lhs, op2); 968} 969 970bool 971operator_minus::op2_range (value_range &r, tree type, 972 const value_range &lhs, 973 const value_range &op1) const 974{ 975 return fold_range (r, type, op1, lhs); 976} 977 978 979class operator_min : public range_operator 980{ 981public: 982 virtual void wi_fold (value_range &r, tree type, 983 const wide_int &lh_lb, 984 const wide_int &lh_ub, 985 const wide_int &rh_lb, 986 const wide_int &rh_ub) const; 987} op_min; 988 989void 990operator_min::wi_fold (value_range &r, tree type, 991 const wide_int &lh_lb, const wide_int &lh_ub, 992 const wide_int &rh_lb, const wide_int &rh_ub) const 993{ 994 signop s = TYPE_SIGN (type); 995 wide_int new_lb = wi::min (lh_lb, rh_lb, s); 996 wide_int new_ub = wi::min (lh_ub, rh_ub, s); 997 value_range_with_overflow (r, type, new_lb, new_ub); 998} 999 1000 1001class operator_max : public range_operator 1002{ 1003public: 1004 virtual void wi_fold (value_range &r, tree type, 1005 const wide_int &lh_lb, 1006 const wide_int &lh_ub, 1007 const wide_int &rh_lb, 1008 const wide_int &rh_ub) const; 1009} op_max; 1010 1011void 1012operator_max::wi_fold (value_range &r, tree type, 1013 const wide_int &lh_lb, const wide_int &lh_ub, 1014 const wide_int &rh_lb, const wide_int &rh_ub) const 1015{ 1016 signop s = TYPE_SIGN (type); 1017 wide_int new_lb = wi::max (lh_lb, rh_lb, s); 1018 wide_int new_ub = wi::max (lh_ub, rh_ub, s); 1019 value_range_with_overflow (r, type, new_lb, new_ub); 1020} 1021 1022 1023class cross_product_operator : public range_operator 1024{ 1025public: 1026 // Perform an operation between two wide-ints and place the result 1027 // in R. Return true if the operation overflowed. 1028 virtual bool wi_op_overflows (wide_int &r, 1029 tree type, 1030 const wide_int &, 1031 const wide_int &) const = 0; 1032 1033 // Calculate the cross product of two sets of sub-ranges and return it. 1034 void wi_cross_product (value_range &r, tree type, 1035 const wide_int &lh_lb, 1036 const wide_int &lh_ub, 1037 const wide_int &rh_lb, 1038 const wide_int &rh_ub) const; 1039}; 1040 1041// Calculate the cross product of two sets of ranges and return it. 1042// 1043// Multiplications, divisions and shifts are a bit tricky to handle, 1044// depending on the mix of signs we have in the two ranges, we need to 1045// operate on different values to get the minimum and maximum values 1046// for the new range. One approach is to figure out all the 1047// variations of range combinations and do the operations. 1048// 1049// However, this involves several calls to compare_values and it is 1050// pretty convoluted. It's simpler to do the 4 operations (MIN0 OP 1051// MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then 1052// figure the smallest and largest values to form the new range. 1053 1054void 1055cross_product_operator::wi_cross_product (value_range &r, tree type, 1056 const wide_int &lh_lb, 1057 const wide_int &lh_ub, 1058 const wide_int &rh_lb, 1059 const wide_int &rh_ub) const 1060{ 1061 wide_int cp1, cp2, cp3, cp4; 1062 // Default to varying. 1063 r = value_range (type); 1064 1065 // Compute the 4 cross operations, bailing if we get an overflow we 1066 // can't handle. 1067 if (wi_op_overflows (cp1, type, lh_lb, rh_lb)) 1068 return; 1069 if (wi::eq_p (lh_lb, lh_ub)) 1070 cp3 = cp1; 1071 else if (wi_op_overflows (cp3, type, lh_ub, rh_lb)) 1072 return; 1073 if (wi::eq_p (rh_lb, rh_ub)) 1074 cp2 = cp1; 1075 else if (wi_op_overflows (cp2, type, lh_lb, rh_ub)) 1076 return; 1077 if (wi::eq_p (lh_lb, lh_ub)) 1078 cp4 = cp2; 1079 else if (wi_op_overflows (cp4, type, lh_ub, rh_ub)) 1080 return; 1081 1082 // Order pairs. 1083 signop sign = TYPE_SIGN (type); 1084 if (wi::gt_p (cp1, cp2, sign)) 1085 std::swap (cp1, cp2); 1086 if (wi::gt_p (cp3, cp4, sign)) 1087 std::swap (cp3, cp4); 1088 1089 // Choose min and max from the ordered pairs. 1090 wide_int res_lb = wi::min (cp1, cp3, sign); 1091 wide_int res_ub = wi::max (cp2, cp4, sign); 1092 value_range_with_overflow (r, type, res_lb, res_ub); 1093} 1094 1095 1096class operator_mult : public cross_product_operator 1097{ 1098public: 1099 virtual void wi_fold (value_range &r, tree type, 1100 const wide_int &lh_lb, 1101 const wide_int &lh_ub, 1102 const wide_int &rh_lb, 1103 const wide_int &rh_ub) const; 1104 virtual bool wi_op_overflows (wide_int &res, tree type, 1105 const wide_int &w0, const wide_int &w1) const; 1106} op_mult; 1107 1108bool 1109operator_mult::wi_op_overflows (wide_int &res, tree type, 1110 const wide_int &w0, const wide_int &w1) const 1111{ 1112 wi::overflow_type overflow = wi::OVF_NONE; 1113 signop sign = TYPE_SIGN (type); 1114 res = wi::mul (w0, w1, sign, &overflow); 1115 if (overflow && TYPE_OVERFLOW_UNDEFINED (type)) 1116 { 1117 // For multiplication, the sign of the overflow is given 1118 // by the comparison of the signs of the operands. 1119 if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ()) 1120 res = wi::max_value (w0.get_precision (), sign); 1121 else 1122 res = wi::min_value (w0.get_precision (), sign); 1123 return false; 1124 } 1125 return overflow; 1126} 1127 1128void 1129operator_mult::wi_fold (value_range &r, tree type, 1130 const wide_int &lh_lb, const wide_int &lh_ub, 1131 const wide_int &rh_lb, const wide_int &rh_ub) const 1132{ 1133 if (TYPE_OVERFLOW_UNDEFINED (type)) 1134 { 1135 wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub); 1136 return; 1137 } 1138 1139 // Multiply the ranges when overflow wraps. This is basically fancy 1140 // code so we don't drop to varying with an unsigned 1141 // [-3,-1]*[-3,-1]. 1142 // 1143 // This test requires 2*prec bits if both operands are signed and 1144 // 2*prec + 2 bits if either is not. Therefore, extend the values 1145 // using the sign of the result to PREC2. From here on out, 1146 // everthing is just signed math no matter what the input types 1147 // were. 1148 1149 signop sign = TYPE_SIGN (type); 1150 unsigned prec = TYPE_PRECISION (type); 1151 widest2_int min0 = widest2_int::from (lh_lb, sign); 1152 widest2_int max0 = widest2_int::from (lh_ub, sign); 1153 widest2_int min1 = widest2_int::from (rh_lb, sign); 1154 widest2_int max1 = widest2_int::from (rh_ub, sign); 1155 widest2_int sizem1 = wi::mask <widest2_int> (prec, false); 1156 widest2_int size = sizem1 + 1; 1157 1158 // Canonicalize the intervals. 1159 if (sign == UNSIGNED) 1160 { 1161 if (wi::ltu_p (size, min0 + max0)) 1162 { 1163 min0 -= size; 1164 max0 -= size; 1165 } 1166 if (wi::ltu_p (size, min1 + max1)) 1167 { 1168 min1 -= size; 1169 max1 -= size; 1170 } 1171 } 1172 1173 // Sort the 4 products so that min is in prod0 and max is in 1174 // prod3. 1175 widest2_int prod0 = min0 * min1; 1176 widest2_int prod1 = min0 * max1; 1177 widest2_int prod2 = max0 * min1; 1178 widest2_int prod3 = max0 * max1; 1179 1180 // min0min1 > max0max1 1181 if (prod0 > prod3) 1182 std::swap (prod0, prod3); 1183 1184 // min0max1 > max0min1 1185 if (prod1 > prod2) 1186 std::swap (prod1, prod2); 1187 1188 if (prod0 > prod1) 1189 std::swap (prod0, prod1); 1190 1191 if (prod2 > prod3) 1192 std::swap (prod2, prod3); 1193 1194 // diff = max - min 1195 prod2 = prod3 - prod0; 1196 if (wi::geu_p (prod2, sizem1)) 1197 // The range covers all values. 1198 r = value_range (type); 1199 else 1200 { 1201 wide_int new_lb = wide_int::from (prod0, prec, sign); 1202 wide_int new_ub = wide_int::from (prod3, prec, sign); 1203 create_possibly_reversed_range (r, type, new_lb, new_ub); 1204 } 1205} 1206 1207 1208class operator_div : public cross_product_operator 1209{ 1210public: 1211 operator_div (enum tree_code c) { code = c; } 1212 virtual void wi_fold (value_range &r, tree type, 1213 const wide_int &lh_lb, 1214 const wide_int &lh_ub, 1215 const wide_int &rh_lb, 1216 const wide_int &rh_ub) const; 1217 virtual bool wi_op_overflows (wide_int &res, tree type, 1218 const wide_int &, const wide_int &) const; 1219private: 1220 enum tree_code code; 1221}; 1222 1223bool 1224operator_div::wi_op_overflows (wide_int &res, tree type, 1225 const wide_int &w0, const wide_int &w1) const 1226{ 1227 if (w1 == 0) 1228 return true; 1229 1230 wi::overflow_type overflow = wi::OVF_NONE; 1231 signop sign = TYPE_SIGN (type); 1232 1233 switch (code) 1234 { 1235 case EXACT_DIV_EXPR: 1236 // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in 1237 // operator_exact_divide. No need to handle it here. 1238 gcc_unreachable (); 1239 break; 1240 case TRUNC_DIV_EXPR: 1241 res = wi::div_trunc (w0, w1, sign, &overflow); 1242 break; 1243 case FLOOR_DIV_EXPR: 1244 res = wi::div_floor (w0, w1, sign, &overflow); 1245 break; 1246 case ROUND_DIV_EXPR: 1247 res = wi::div_round (w0, w1, sign, &overflow); 1248 break; 1249 case CEIL_DIV_EXPR: 1250 res = wi::div_ceil (w0, w1, sign, &overflow); 1251 break; 1252 default: 1253 gcc_unreachable (); 1254 } 1255 1256 if (overflow && TYPE_OVERFLOW_UNDEFINED (type)) 1257 { 1258 // For division, the only case is -INF / -1 = +INF. 1259 res = wi::max_value (w0.get_precision (), sign); 1260 return false; 1261 } 1262 return overflow; 1263} 1264 1265void 1266operator_div::wi_fold (value_range &r, tree type, 1267 const wide_int &lh_lb, const wide_int &lh_ub, 1268 const wide_int &rh_lb, const wide_int &rh_ub) const 1269{ 1270 // If we know we will divide by zero, return undefined. 1271 if (rh_lb == 0 && rh_ub == 0) 1272 { 1273 r = value_range (); 1274 return; 1275 } 1276 1277 const wide_int dividend_min = lh_lb; 1278 const wide_int dividend_max = lh_ub; 1279 const wide_int divisor_min = rh_lb; 1280 const wide_int divisor_max = rh_ub; 1281 signop sign = TYPE_SIGN (type); 1282 unsigned prec = TYPE_PRECISION (type); 1283 wide_int extra_min, extra_max; 1284 1285 // If we know we won't divide by zero, just do the division. 1286 if (!wi_includes_zero_p (type, divisor_min, divisor_max)) 1287 { 1288 wi_cross_product (r, type, dividend_min, dividend_max, 1289 divisor_min, divisor_max); 1290 return; 1291 } 1292 1293 // If flag_non_call_exceptions, we must not eliminate a division by zero. 1294 if (cfun->can_throw_non_call_exceptions) 1295 { 1296 r = value_range (type); 1297 return; 1298 } 1299 1300 // If we're definitely dividing by zero, there's nothing to do. 1301 if (wi_zero_p (type, divisor_min, divisor_max)) 1302 { 1303 r = value_range (); 1304 return; 1305 } 1306 1307 // Perform the division in 2 parts, [LB, -1] and [1, UB], which will 1308 // skip any division by zero. 1309 1310 // First divide by the negative numbers, if any. 1311 if (wi::neg_p (divisor_min, sign)) 1312 wi_cross_product (r, type, dividend_min, dividend_max, 1313 divisor_min, wi::minus_one (prec)); 1314 else 1315 r = value_range (); 1316 1317 // Then divide by the non-zero positive numbers, if any. 1318 if (wi::gt_p (divisor_max, wi::zero (prec), sign)) 1319 { 1320 value_range tmp; 1321 wi_cross_product (tmp, type, dividend_min, dividend_max, 1322 wi::one (prec), divisor_max); 1323 r.union_ (tmp); 1324 } 1325 // We shouldn't still have undefined here. 1326 gcc_checking_assert (!r.undefined_p ()); 1327} 1328 1329operator_div op_trunc_div (TRUNC_DIV_EXPR); 1330operator_div op_floor_div (FLOOR_DIV_EXPR); 1331operator_div op_round_div (ROUND_DIV_EXPR); 1332operator_div op_ceil_div (CEIL_DIV_EXPR); 1333 1334 1335class operator_exact_divide : public operator_div 1336{ 1337public: 1338 operator_exact_divide () : operator_div (TRUNC_DIV_EXPR) { } 1339 virtual bool op1_range (value_range &r, tree type, 1340 const value_range &lhs, 1341 const value_range &op2) const; 1342 1343} op_exact_div; 1344 1345bool 1346operator_exact_divide::op1_range (value_range &r, tree type, 1347 const value_range &lhs, 1348 const value_range &op2) const 1349{ 1350 tree offset; 1351 // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about 1352 // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12]. 1353 // We wont bother trying to enumerate all the in between stuff :-P 1354 // TRUE accuraacy is [6,6][9,9][12,12]. This is unlikely to matter most of 1355 // the time however. 1356 // If op2 is a multiple of 2, we would be able to set some non-zero bits. 1357 if (op2.singleton_p (&offset) 1358 && !integer_zerop (offset)) 1359 return range_op_handler (MULT_EXPR, type)->fold_range (r, type, lhs, op2); 1360 return false; 1361} 1362 1363 1364class operator_lshift : public cross_product_operator 1365{ 1366public: 1367 virtual bool fold_range (value_range &r, tree type, 1368 const value_range &op1, 1369 const value_range &op2) const; 1370 1371 virtual void wi_fold (value_range &r, tree type, 1372 const wide_int &lh_lb, const wide_int &lh_ub, 1373 const wide_int &rh_lb, const wide_int &rh_ub) const; 1374 virtual bool wi_op_overflows (wide_int &res, 1375 tree type, 1376 const wide_int &, 1377 const wide_int &) const; 1378} op_lshift; 1379 1380bool 1381operator_lshift::fold_range (value_range &r, tree type, 1382 const value_range &op1, 1383 const value_range &op2) const 1384{ 1385 if (undefined_shift_range_check (r, type, op2)) 1386 return true; 1387 1388 // Transform left shifts by constants into multiplies. 1389 if (op2.singleton_p ()) 1390 { 1391 unsigned shift = op2.lower_bound ().to_uhwi (); 1392 wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type)); 1393 value_range mult (type, tmp, tmp); 1394 1395 // Force wrapping multiplication. 1396 bool saved_flag_wrapv = flag_wrapv; 1397 bool saved_flag_wrapv_pointer = flag_wrapv_pointer; 1398 flag_wrapv = 1; 1399 flag_wrapv_pointer = 1; 1400 bool b = range_op_handler (MULT_EXPR, type)->fold_range (r, type, op1, 1401 mult); 1402 flag_wrapv = saved_flag_wrapv; 1403 flag_wrapv_pointer = saved_flag_wrapv_pointer; 1404 return b; 1405 } 1406 else 1407 // Otherwise, invoke the generic fold routine. 1408 return range_operator::fold_range (r, type, op1, op2); 1409} 1410 1411void 1412operator_lshift::wi_fold (value_range &r, tree type, 1413 const wide_int &lh_lb, const wide_int &lh_ub, 1414 const wide_int &rh_lb, const wide_int &rh_ub) const 1415{ 1416 signop sign = TYPE_SIGN (type); 1417 unsigned prec = TYPE_PRECISION (type); 1418 int overflow_pos = sign == SIGNED ? prec - 1 : prec; 1419 int bound_shift = overflow_pos - rh_ub.to_shwi (); 1420 // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can 1421 // overflow. However, for that to happen, rh.max needs to be zero, 1422 // which means rh is a singleton range of zero, which means it 1423 // should be handled by the lshift fold_range above. 1424 wide_int bound = wi::set_bit_in_zero (bound_shift, prec); 1425 wide_int complement = ~(bound - 1); 1426 wide_int low_bound, high_bound; 1427 bool in_bounds = false; 1428 1429 if (sign == UNSIGNED) 1430 { 1431 low_bound = bound; 1432 high_bound = complement; 1433 if (wi::ltu_p (lh_ub, low_bound)) 1434 { 1435 // [5, 6] << [1, 2] == [10, 24]. 1436 // We're shifting out only zeroes, the value increases 1437 // monotonically. 1438 in_bounds = true; 1439 } 1440 else if (wi::ltu_p (high_bound, lh_lb)) 1441 { 1442 // [0xffffff00, 0xffffffff] << [1, 2] 1443 // == [0xfffffc00, 0xfffffffe]. 1444 // We're shifting out only ones, the value decreases 1445 // monotonically. 1446 in_bounds = true; 1447 } 1448 } 1449 else 1450 { 1451 // [-1, 1] << [1, 2] == [-4, 4] 1452 low_bound = complement; 1453 high_bound = bound; 1454 if (wi::lts_p (lh_ub, high_bound) 1455 && wi::lts_p (low_bound, lh_lb)) 1456 { 1457 // For non-negative numbers, we're shifting out only zeroes, 1458 // the value increases monotonically. For negative numbers, 1459 // we're shifting out only ones, the value decreases 1460 // monotonically. 1461 in_bounds = true; 1462 } 1463 } 1464 1465 if (in_bounds) 1466 wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub); 1467 else 1468 r = value_range (type); 1469} 1470 1471bool 1472operator_lshift::wi_op_overflows (wide_int &res, tree type, 1473 const wide_int &w0, const wide_int &w1) const 1474{ 1475 signop sign = TYPE_SIGN (type); 1476 if (wi::neg_p (w1)) 1477 { 1478 // It's unclear from the C standard whether shifts can overflow. 1479 // The following code ignores overflow; perhaps a C standard 1480 // interpretation ruling is needed. 1481 res = wi::rshift (w0, -w1, sign); 1482 } 1483 else 1484 res = wi::lshift (w0, w1); 1485 return false; 1486} 1487 1488 1489class operator_rshift : public cross_product_operator 1490{ 1491public: 1492 virtual bool fold_range (value_range &r, tree type, 1493 const value_range &op1, 1494 const value_range &op2) const; 1495 virtual void wi_fold (value_range &r, tree type, 1496 const wide_int &lh_lb, 1497 const wide_int &lh_ub, 1498 const wide_int &rh_lb, 1499 const wide_int &rh_ub) const; 1500 virtual bool wi_op_overflows (wide_int &res, 1501 tree type, 1502 const wide_int &w0, 1503 const wide_int &w1) const; 1504} op_rshift; 1505 1506bool 1507operator_rshift::wi_op_overflows (wide_int &res, 1508 tree type, 1509 const wide_int &w0, 1510 const wide_int &w1) const 1511{ 1512 signop sign = TYPE_SIGN (type); 1513 if (wi::neg_p (w1)) 1514 res = wi::lshift (w0, -w1); 1515 else 1516 { 1517 // It's unclear from the C standard whether shifts can overflow. 1518 // The following code ignores overflow; perhaps a C standard 1519 // interpretation ruling is needed. 1520 res = wi::rshift (w0, w1, sign); 1521 } 1522 return false; 1523} 1524 1525bool 1526operator_rshift::fold_range (value_range &r, tree type, 1527 const value_range &op1, 1528 const value_range &op2) const 1529{ 1530 // Invoke the generic fold routine if not undefined.. 1531 if (undefined_shift_range_check (r, type, op2)) 1532 return true; 1533 1534 return range_operator::fold_range (r, type, op1, op2); 1535} 1536 1537void 1538operator_rshift::wi_fold (value_range &r, tree type, 1539 const wide_int &lh_lb, const wide_int &lh_ub, 1540 const wide_int &rh_lb, const wide_int &rh_ub) const 1541{ 1542 wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub); 1543} 1544 1545 1546class operator_cast: public range_operator 1547{ 1548public: 1549 virtual bool fold_range (value_range &r, tree type, 1550 const value_range &op1, 1551 const value_range &op2) const; 1552 virtual bool op1_range (value_range &r, tree type, 1553 const value_range &lhs, 1554 const value_range &op2) const; 1555 1556} op_convert; 1557 1558bool 1559operator_cast::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, 1560 const value_range &lh, 1561 const value_range &rh) const 1562{ 1563 if (empty_range_check (r, lh, rh)) 1564 return true; 1565 1566 tree inner = lh.type (); 1567 tree outer = rh.type (); 1568 gcc_checking_assert (rh.varying_p ()); 1569 gcc_checking_assert (types_compatible_p (outer, type)); 1570 signop inner_sign = TYPE_SIGN (inner); 1571 signop outer_sign = TYPE_SIGN (outer); 1572 unsigned inner_prec = TYPE_PRECISION (inner); 1573 unsigned outer_prec = TYPE_PRECISION (outer); 1574 1575 // Start with an empty range and add subranges. 1576 r = value_range (); 1577 for (unsigned x = 0; x < lh.num_pairs (); ++x) 1578 { 1579 wide_int lh_lb = lh.lower_bound (x); 1580 wide_int lh_ub = lh.upper_bound (x); 1581 1582 // If the conversion is not truncating we can convert the min 1583 // and max values and canonicalize the resulting range. 1584 // Otherwise, we can do the conversion if the size of the range 1585 // is less than what the precision of the target type can 1586 // represent. 1587 if (outer_prec >= inner_prec 1588 || wi::rshift (wi::sub (lh_ub, lh_lb), 1589 wi::uhwi (outer_prec, inner_prec), 1590 inner_sign) == 0) 1591 { 1592 wide_int min = wide_int::from (lh_lb, outer_prec, inner_sign); 1593 wide_int max = wide_int::from (lh_ub, outer_prec, inner_sign); 1594 if (!wi::eq_p (min, wi::min_value (outer_prec, outer_sign)) 1595 || !wi::eq_p (max, wi::max_value (outer_prec, outer_sign))) 1596 { 1597 value_range tmp; 1598 create_possibly_reversed_range (tmp, type, min, max); 1599 r.union_ (tmp); 1600 continue; 1601 } 1602 } 1603 r = value_range (type); 1604 break; 1605 } 1606 return true; 1607} 1608 1609bool 1610operator_cast::op1_range (value_range &r, tree type, 1611 const value_range &lhs, 1612 const value_range &op2) const 1613{ 1614 tree lhs_type = lhs.type (); 1615 value_range tmp; 1616 gcc_checking_assert (types_compatible_p (op2.type(), type)); 1617 1618 // If the precision of the LHS is smaller than the precision of the 1619 // RHS, then there would be truncation of the value on the RHS, and 1620 // so we can tell nothing about it. 1621 if (TYPE_PRECISION (lhs_type) < TYPE_PRECISION (type)) 1622 { 1623 // If we've been passed an actual value for the RHS rather than 1624 // the type, see if it fits the LHS, and if so, then we can allow 1625 // it. 1626 fold_range (r, lhs_type, op2, value_range (lhs_type)); 1627 fold_range (tmp, type, r, value_range (type)); 1628 if (tmp == op2) 1629 { 1630 // We know the value of the RHS fits in the LHS type, so 1631 // convert the LHS and remove any values that arent in OP2. 1632 fold_range (r, type, lhs, value_range (type)); 1633 r.intersect (op2); 1634 return true; 1635 } 1636 // Special case if the LHS is a boolean. A 0 means the RHS is 1637 // zero, and a 1 means the RHS is non-zero. 1638 if (TREE_CODE (lhs_type) == BOOLEAN_TYPE) 1639 { 1640 // If the LHS is unknown, the result is whatever op2 already is. 1641 if (!lhs.singleton_p ()) 1642 { 1643 r = op2; 1644 return true; 1645 } 1646 // Boolean casts are weird in GCC. It's actually an implied 1647 // mask with 0x01, so all that is known is whether the 1648 // rightmost bit is 0 or 1, which implies the only value 1649 // *not* in the RHS is 0 or -1. 1650 unsigned prec = TYPE_PRECISION (type); 1651 if (lhs.zero_p ()) 1652 r = value_range (type, wi::minus_one (prec), wi::minus_one (prec), 1653 VR_ANTI_RANGE); 1654 else 1655 r = value_range (type, wi::zero (prec), wi::zero (prec), 1656 VR_ANTI_RANGE); 1657 // And intersect it with what we know about op2. 1658 r.intersect (op2); 1659 } 1660 else 1661 // Otherwise we'll have to assume it's whatever we know about op2. 1662 r = op2; 1663 return true; 1664 } 1665 1666 // If the LHS precision is greater than the rhs precision, the LHS 1667 // range is restricted to the range of the RHS by this 1668 // assignment. 1669 if (TYPE_PRECISION (lhs_type) > TYPE_PRECISION (type)) 1670 { 1671 // Cast the range of the RHS to the type of the LHS. 1672 fold_range (tmp, lhs_type, value_range (type), value_range (lhs_type)); 1673 // Intersect this with the LHS range will produce the range, which 1674 // will be cast to the RHS type before returning. 1675 tmp.intersect (lhs); 1676 } 1677 else 1678 tmp = lhs; 1679 1680 // Cast the calculated range to the type of the RHS. 1681 fold_range (r, type, tmp, value_range (type)); 1682 return true; 1683} 1684 1685 1686class operator_logical_and : public range_operator 1687{ 1688public: 1689 virtual bool fold_range (value_range &r, tree type, 1690 const value_range &lh, 1691 const value_range &rh) const; 1692 virtual bool op1_range (value_range &r, tree type, 1693 const value_range &lhs, 1694 const value_range &op2) const; 1695 virtual bool op2_range (value_range &r, tree type, 1696 const value_range &lhs, 1697 const value_range &op1) const; 1698} op_logical_and; 1699 1700 1701bool 1702operator_logical_and::fold_range (value_range &r, tree type, 1703 const value_range &lh, 1704 const value_range &rh) const 1705{ 1706 if (empty_range_check (r, lh, rh)) 1707 return true; 1708 1709 // 0 && anything is 0. 1710 if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0)) 1711 || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0))) 1712 r = range_false (type); 1713 else if (lh.contains_p (build_zero_cst (lh.type ())) 1714 || rh.contains_p (build_zero_cst (rh.type ()))) 1715 // To reach this point, there must be a logical 1 on each side, and 1716 // the only remaining question is whether there is a zero or not. 1717 r = range_true_and_false (type); 1718 else 1719 r = range_true (type); 1720 return true; 1721} 1722 1723bool 1724operator_logical_and::op1_range (value_range &r, tree type, 1725 const value_range &lhs, 1726 const value_range &op2 ATTRIBUTE_UNUSED) const 1727{ 1728 switch (get_bool_state (r, lhs, type)) 1729 { 1730 case BRS_TRUE: 1731 // A true result means both sides of the AND must be true. 1732 r = range_true (type); 1733 break; 1734 default: 1735 // Any other result means only one side has to be false, the 1736 // other side can be anything. So we cannott be sure of any 1737 // result here. 1738 r = range_true_and_false (type); 1739 break; 1740 } 1741 return true; 1742} 1743 1744bool 1745operator_logical_and::op2_range (value_range &r, tree type, 1746 const value_range &lhs, 1747 const value_range &op1) const 1748{ 1749 return operator_logical_and::op1_range (r, type, lhs, op1); 1750} 1751 1752 1753class operator_bitwise_and : public range_operator 1754{ 1755public: 1756 virtual bool op1_range (value_range &r, tree type, 1757 const value_range &lhs, 1758 const value_range &op2) const; 1759 virtual bool op2_range (value_range &r, tree type, 1760 const value_range &lhs, 1761 const value_range &op1) const; 1762 virtual void wi_fold (value_range &r, tree type, 1763 const wide_int &lh_lb, 1764 const wide_int &lh_ub, 1765 const wide_int &rh_lb, 1766 const wide_int &rh_ub) const; 1767} op_bitwise_and; 1768 1769// Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if 1770// possible. Basically, see if we can optimize: 1771// 1772// [LB, UB] op Z 1773// into: 1774// [LB op Z, UB op Z] 1775// 1776// If the optimization was successful, accumulate the range in R and 1777// return TRUE. 1778 1779static bool 1780wi_optimize_and_or (value_range &r, 1781 enum tree_code code, 1782 tree type, 1783 const wide_int &lh_lb, const wide_int &lh_ub, 1784 const wide_int &rh_lb, const wide_int &rh_ub) 1785{ 1786 // Calculate the singleton mask among the ranges, if any. 1787 wide_int lower_bound, upper_bound, mask; 1788 if (wi::eq_p (rh_lb, rh_ub)) 1789 { 1790 mask = rh_lb; 1791 lower_bound = lh_lb; 1792 upper_bound = lh_ub; 1793 } 1794 else if (wi::eq_p (lh_lb, lh_ub)) 1795 { 1796 mask = lh_lb; 1797 lower_bound = rh_lb; 1798 upper_bound = rh_ub; 1799 } 1800 else 1801 return false; 1802 1803 // If Z is a constant which (for op | its bitwise not) has n 1804 // consecutive least significant bits cleared followed by m 1 1805 // consecutive bits set immediately above it and either 1806 // m + n == precision, or (x >> (m + n)) == (y >> (m + n)). 1807 // 1808 // The least significant n bits of all the values in the range are 1809 // cleared or set, the m bits above it are preserved and any bits 1810 // above these are required to be the same for all values in the 1811 // range. 1812 wide_int w = mask; 1813 int m = 0, n = 0; 1814 if (code == BIT_IOR_EXPR) 1815 w = ~w; 1816 if (wi::eq_p (w, 0)) 1817 n = w.get_precision (); 1818 else 1819 { 1820 n = wi::ctz (w); 1821 w = ~(w | wi::mask (n, false, w.get_precision ())); 1822 if (wi::eq_p (w, 0)) 1823 m = w.get_precision () - n; 1824 else 1825 m = wi::ctz (w) - n; 1826 } 1827 wide_int new_mask = wi::mask (m + n, true, w.get_precision ()); 1828 if ((new_mask & lower_bound) != (new_mask & upper_bound)) 1829 return false; 1830 1831 wide_int res_lb, res_ub; 1832 if (code == BIT_AND_EXPR) 1833 { 1834 res_lb = wi::bit_and (lower_bound, mask); 1835 res_ub = wi::bit_and (upper_bound, mask); 1836 } 1837 else if (code == BIT_IOR_EXPR) 1838 { 1839 res_lb = wi::bit_or (lower_bound, mask); 1840 res_ub = wi::bit_or (upper_bound, mask); 1841 } 1842 else 1843 gcc_unreachable (); 1844 value_range_with_overflow (r, type, res_lb, res_ub); 1845 return true; 1846} 1847 1848// For range [LB, UB] compute two wide_int bit masks. 1849// 1850// In the MAYBE_NONZERO bit mask, if some bit is unset, it means that 1851// for all numbers in the range the bit is 0, otherwise it might be 0 1852// or 1. 1853// 1854// In the MUSTBE_NONZERO bit mask, if some bit is set, it means that 1855// for all numbers in the range the bit is 1, otherwise it might be 0 1856// or 1. 1857 1858void 1859wi_set_zero_nonzero_bits (tree type, 1860 const wide_int &lb, const wide_int &ub, 1861 wide_int &maybe_nonzero, 1862 wide_int &mustbe_nonzero) 1863{ 1864 signop sign = TYPE_SIGN (type); 1865 1866 if (wi::eq_p (lb, ub)) 1867 maybe_nonzero = mustbe_nonzero = lb; 1868 else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign)) 1869 { 1870 wide_int xor_mask = lb ^ ub; 1871 maybe_nonzero = lb | ub; 1872 mustbe_nonzero = lb & ub; 1873 if (xor_mask != 0) 1874 { 1875 wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false, 1876 maybe_nonzero.get_precision ()); 1877 maybe_nonzero = maybe_nonzero | mask; 1878 mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask); 1879 } 1880 } 1881 else 1882 { 1883 maybe_nonzero = wi::minus_one (lb.get_precision ()); 1884 mustbe_nonzero = wi::zero (lb.get_precision ()); 1885 } 1886} 1887 1888void 1889operator_bitwise_and::wi_fold (value_range &r, tree type, 1890 const wide_int &lh_lb, 1891 const wide_int &lh_ub, 1892 const wide_int &rh_lb, 1893 const wide_int &rh_ub) const 1894{ 1895 if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub)) 1896 return; 1897 1898 wide_int maybe_nonzero_lh, mustbe_nonzero_lh; 1899 wide_int maybe_nonzero_rh, mustbe_nonzero_rh; 1900 wi_set_zero_nonzero_bits (type, lh_lb, lh_ub, 1901 maybe_nonzero_lh, mustbe_nonzero_lh); 1902 wi_set_zero_nonzero_bits (type, rh_lb, rh_ub, 1903 maybe_nonzero_rh, mustbe_nonzero_rh); 1904 1905 wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh; 1906 wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh; 1907 signop sign = TYPE_SIGN (type); 1908 unsigned prec = TYPE_PRECISION (type); 1909 // If both input ranges contain only negative values, we can 1910 // truncate the result range maximum to the minimum of the 1911 // input range maxima. 1912 if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign)) 1913 { 1914 new_ub = wi::min (new_ub, lh_ub, sign); 1915 new_ub = wi::min (new_ub, rh_ub, sign); 1916 } 1917 // If either input range contains only non-negative values 1918 // we can truncate the result range maximum to the respective 1919 // maximum of the input range. 1920 if (wi::ge_p (lh_lb, 0, sign)) 1921 new_ub = wi::min (new_ub, lh_ub, sign); 1922 if (wi::ge_p (rh_lb, 0, sign)) 1923 new_ub = wi::min (new_ub, rh_ub, sign); 1924 // PR68217: In case of signed & sign-bit-CST should 1925 // result in [-INF, 0] instead of [-INF, INF]. 1926 if (wi::gt_p (new_lb, new_ub, sign)) 1927 { 1928 wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec); 1929 if (sign == SIGNED 1930 && ((wi::eq_p (lh_lb, lh_ub) 1931 && !wi::cmps (lh_lb, sign_bit)) 1932 || (wi::eq_p (rh_lb, rh_ub) 1933 && !wi::cmps (rh_lb, sign_bit)))) 1934 { 1935 new_lb = wi::min_value (prec, sign); 1936 new_ub = wi::zero (prec); 1937 } 1938 } 1939 // If the limits got swapped around, return varying. 1940 if (wi::gt_p (new_lb, new_ub,sign)) 1941 r = value_range (type); 1942 else 1943 value_range_with_overflow (r, type, new_lb, new_ub); 1944} 1945 1946bool 1947operator_bitwise_and::op1_range (value_range &r, tree type, 1948 const value_range &lhs, 1949 const value_range &op2) const 1950{ 1951 // If this is really a logical wi_fold, call that. 1952 if (types_compatible_p (type, boolean_type_node)) 1953 return op_logical_and.op1_range (r, type, lhs, op2); 1954 1955 // For now do nothing with bitwise AND of value_range's. 1956 r.set_varying (type); 1957 return true; 1958} 1959 1960bool 1961operator_bitwise_and::op2_range (value_range &r, tree type, 1962 const value_range &lhs, 1963 const value_range &op1) const 1964{ 1965 return operator_bitwise_and::op1_range (r, type, lhs, op1); 1966} 1967 1968 1969class operator_logical_or : public range_operator 1970{ 1971public: 1972 virtual bool fold_range (value_range &r, tree type, 1973 const value_range &lh, 1974 const value_range &rh) const; 1975 virtual bool op1_range (value_range &r, tree type, 1976 const value_range &lhs, 1977 const value_range &op2) const; 1978 virtual bool op2_range (value_range &r, tree type, 1979 const value_range &lhs, 1980 const value_range &op1) const; 1981} op_logical_or; 1982 1983bool 1984operator_logical_or::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, 1985 const value_range &lh, 1986 const value_range &rh) const 1987{ 1988 if (empty_range_check (r, lh, rh)) 1989 return true; 1990 1991 r = lh; 1992 r.union_ (rh); 1993 return true; 1994} 1995 1996bool 1997operator_logical_or::op1_range (value_range &r, tree type, 1998 const value_range &lhs, 1999 const value_range &op2 ATTRIBUTE_UNUSED) const 2000{ 2001 switch (get_bool_state (r, lhs, type)) 2002 { 2003 case BRS_FALSE: 2004 // A false result means both sides of the OR must be false. 2005 r = range_false (type); 2006 break; 2007 default: 2008 // Any other result means only one side has to be true, the 2009 // other side can be anything. so we can't be sure of any result 2010 // here. 2011 r = range_true_and_false (type); 2012 break; 2013 } 2014 return true; 2015} 2016 2017bool 2018operator_logical_or::op2_range (value_range &r, tree type, 2019 const value_range &lhs, 2020 const value_range &op1) const 2021{ 2022 return operator_logical_or::op1_range (r, type, lhs, op1); 2023} 2024 2025 2026class operator_bitwise_or : public range_operator 2027{ 2028public: 2029 virtual bool op1_range (value_range &r, tree type, 2030 const value_range &lhs, 2031 const value_range &op2) const; 2032 virtual bool op2_range (value_range &r, tree type, 2033 const value_range &lhs, 2034 const value_range &op1) const; 2035 virtual void wi_fold (value_range &r, tree type, 2036 const wide_int &lh_lb, 2037 const wide_int &lh_ub, 2038 const wide_int &rh_lb, 2039 const wide_int &rh_ub) const; 2040} op_bitwise_or; 2041 2042void 2043operator_bitwise_or::wi_fold (value_range &r, tree type, 2044 const wide_int &lh_lb, 2045 const wide_int &lh_ub, 2046 const wide_int &rh_lb, 2047 const wide_int &rh_ub) const 2048{ 2049 if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub)) 2050 return; 2051 2052 wide_int maybe_nonzero_lh, mustbe_nonzero_lh; 2053 wide_int maybe_nonzero_rh, mustbe_nonzero_rh; 2054 wi_set_zero_nonzero_bits (type, lh_lb, lh_ub, 2055 maybe_nonzero_lh, mustbe_nonzero_lh); 2056 wi_set_zero_nonzero_bits (type, rh_lb, rh_ub, 2057 maybe_nonzero_rh, mustbe_nonzero_rh); 2058 wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh; 2059 wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh; 2060 signop sign = TYPE_SIGN (type); 2061 // If the input ranges contain only positive values we can 2062 // truncate the minimum of the result range to the maximum 2063 // of the input range minima. 2064 if (wi::ge_p (lh_lb, 0, sign) 2065 && wi::ge_p (rh_lb, 0, sign)) 2066 { 2067 new_lb = wi::max (new_lb, lh_lb, sign); 2068 new_lb = wi::max (new_lb, rh_lb, sign); 2069 } 2070 // If either input range contains only negative values 2071 // we can truncate the minimum of the result range to the 2072 // respective minimum range. 2073 if (wi::lt_p (lh_ub, 0, sign)) 2074 new_lb = wi::max (new_lb, lh_lb, sign); 2075 if (wi::lt_p (rh_ub, 0, sign)) 2076 new_lb = wi::max (new_lb, rh_lb, sign); 2077 // If the limits got swapped around, return varying. 2078 if (wi::gt_p (new_lb, new_ub,sign)) 2079 r = value_range (type); 2080 else 2081 value_range_with_overflow (r, type, new_lb, new_ub); 2082} 2083 2084bool 2085operator_bitwise_or::op1_range (value_range &r, tree type, 2086 const value_range &lhs, 2087 const value_range &op2) const 2088{ 2089 // If this is really a logical wi_fold, call that. 2090 if (types_compatible_p (type, boolean_type_node)) 2091 return op_logical_or.op1_range (r, type, lhs, op2); 2092 2093 // For now do nothing with bitwise OR of value_range's. 2094 r.set_varying (type); 2095 return true; 2096} 2097 2098bool 2099operator_bitwise_or::op2_range (value_range &r, tree type, 2100 const value_range &lhs, 2101 const value_range &op1) const 2102{ 2103 return operator_bitwise_or::op1_range (r, type, lhs, op1); 2104} 2105 2106 2107class operator_bitwise_xor : public range_operator 2108{ 2109public: 2110 virtual void wi_fold (value_range &r, tree type, 2111 const wide_int &lh_lb, 2112 const wide_int &lh_ub, 2113 const wide_int &rh_lb, 2114 const wide_int &rh_ub) const; 2115} op_bitwise_xor; 2116 2117void 2118operator_bitwise_xor::wi_fold (value_range &r, tree type, 2119 const wide_int &lh_lb, 2120 const wide_int &lh_ub, 2121 const wide_int &rh_lb, 2122 const wide_int &rh_ub) const 2123{ 2124 signop sign = TYPE_SIGN (type); 2125 wide_int maybe_nonzero_lh, mustbe_nonzero_lh; 2126 wide_int maybe_nonzero_rh, mustbe_nonzero_rh; 2127 wi_set_zero_nonzero_bits (type, lh_lb, lh_ub, 2128 maybe_nonzero_lh, mustbe_nonzero_lh); 2129 wi_set_zero_nonzero_bits (type, rh_lb, rh_ub, 2130 maybe_nonzero_rh, mustbe_nonzero_rh); 2131 2132 wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh) 2133 | ~(maybe_nonzero_lh | maybe_nonzero_rh)); 2134 wide_int result_one_bits 2135 = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh) 2136 | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh)); 2137 wide_int new_ub = ~result_zero_bits; 2138 wide_int new_lb = result_one_bits; 2139 2140 // If the range has all positive or all negative values, the result 2141 // is better than VARYING. 2142 if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign)) 2143 value_range_with_overflow (r, type, new_lb, new_ub); 2144 else 2145 r = value_range (type); 2146} 2147 2148 2149class operator_trunc_mod : public range_operator 2150{ 2151public: 2152 virtual void wi_fold (value_range &r, tree type, 2153 const wide_int &lh_lb, 2154 const wide_int &lh_ub, 2155 const wide_int &rh_lb, 2156 const wide_int &rh_ub) const; 2157} op_trunc_mod; 2158 2159void 2160operator_trunc_mod::wi_fold (value_range &r, tree type, 2161 const wide_int &lh_lb, 2162 const wide_int &lh_ub, 2163 const wide_int &rh_lb, 2164 const wide_int &rh_ub) const 2165{ 2166 wide_int new_lb, new_ub, tmp; 2167 signop sign = TYPE_SIGN (type); 2168 unsigned prec = TYPE_PRECISION (type); 2169 2170 // Mod 0 is undefined. Return undefined. 2171 if (wi_zero_p (type, rh_lb, rh_ub)) 2172 { 2173 r = value_range (); 2174 return; 2175 } 2176 2177 // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0. 2178 new_ub = rh_ub - 1; 2179 if (sign == SIGNED) 2180 { 2181 tmp = -1 - rh_lb; 2182 new_ub = wi::smax (new_ub, tmp); 2183 } 2184 2185 if (sign == UNSIGNED) 2186 new_lb = wi::zero (prec); 2187 else 2188 { 2189 new_lb = -new_ub; 2190 tmp = lh_lb; 2191 if (wi::gts_p (tmp, 0)) 2192 tmp = wi::zero (prec); 2193 new_lb = wi::smax (new_lb, tmp); 2194 } 2195 tmp = lh_ub; 2196 if (sign == SIGNED && wi::neg_p (tmp)) 2197 tmp = wi::zero (prec); 2198 new_ub = wi::min (new_ub, tmp, sign); 2199 2200 value_range_with_overflow (r, type, new_lb, new_ub); 2201} 2202 2203 2204class operator_logical_not : public range_operator 2205{ 2206public: 2207 virtual bool fold_range (value_range &r, tree type, 2208 const value_range &lh, 2209 const value_range &rh) const; 2210 virtual bool op1_range (value_range &r, tree type, 2211 const value_range &lhs, 2212 const value_range &op2) const; 2213} op_logical_not; 2214 2215// Folding a logical NOT, oddly enough, involves doing nothing on the 2216// forward pass through. During the initial walk backwards, the 2217// logical NOT reversed the desired outcome on the way back, so on the 2218// way forward all we do is pass the range forward. 2219// 2220// b_2 = x_1 < 20 2221// b_3 = !b_2 2222// if (b_3) 2223// to determine the TRUE branch, walking backward 2224// if (b_3) if ([1,1]) 2225// b_3 = !b_2 [1,1] = ![0,0] 2226// b_2 = x_1 < 20 [0,0] = x_1 < 20, false, so x_1 == [20, 255] 2227// which is the result we are looking for.. so.. pass it through. 2228 2229bool 2230operator_logical_not::fold_range (value_range &r, tree type, 2231 const value_range &lh, 2232 const value_range &rh ATTRIBUTE_UNUSED) const 2233{ 2234 if (empty_range_check (r, lh, rh)) 2235 return true; 2236 2237 if (lh.varying_p () || lh.undefined_p ()) 2238 r = lh; 2239 else 2240 { 2241 r = lh; 2242 r.invert (); 2243 } 2244 gcc_checking_assert (lh.type() == type); 2245 return true; 2246} 2247 2248bool 2249operator_logical_not::op1_range (value_range &r, 2250 tree type ATTRIBUTE_UNUSED, 2251 const value_range &lhs, 2252 const value_range &op2 ATTRIBUTE_UNUSED) const 2253{ 2254 r = lhs; 2255 if (!lhs.varying_p () && !lhs.undefined_p ()) 2256 r.invert (); 2257 return true; 2258} 2259 2260 2261class operator_bitwise_not : public range_operator 2262{ 2263public: 2264 virtual bool fold_range (value_range &r, tree type, 2265 const value_range &lh, 2266 const value_range &rh) const; 2267 virtual bool op1_range (value_range &r, tree type, 2268 const value_range &lhs, 2269 const value_range &op2) const; 2270} op_bitwise_not; 2271 2272bool 2273operator_bitwise_not::fold_range (value_range &r, tree type, 2274 const value_range &lh, 2275 const value_range &rh) const 2276{ 2277 if (empty_range_check (r, lh, rh)) 2278 return true; 2279 2280 // ~X is simply -1 - X. 2281 value_range minusone (type, wi::minus_one (TYPE_PRECISION (type)), 2282 wi::minus_one (TYPE_PRECISION (type))); 2283 return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, minusone, 2284 lh); 2285} 2286 2287bool 2288operator_bitwise_not::op1_range (value_range &r, tree type, 2289 const value_range &lhs, 2290 const value_range &op2) const 2291{ 2292 // ~X is -1 - X and since bitwise NOT is involutary...do it again. 2293 return fold_range (r, type, lhs, op2); 2294} 2295 2296 2297class operator_cst : public range_operator 2298{ 2299public: 2300 virtual bool fold_range (value_range &r, tree type, 2301 const value_range &op1, 2302 const value_range &op2) const; 2303} op_integer_cst; 2304 2305bool 2306operator_cst::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, 2307 const value_range &lh, 2308 const value_range &rh ATTRIBUTE_UNUSED) const 2309{ 2310 r = lh; 2311 return true; 2312} 2313 2314 2315class operator_identity : public range_operator 2316{ 2317public: 2318 virtual bool fold_range (value_range &r, tree type, 2319 const value_range &op1, 2320 const value_range &op2) const; 2321 virtual bool op1_range (value_range &r, tree type, 2322 const value_range &lhs, 2323 const value_range &op2) const; 2324} op_identity; 2325 2326bool 2327operator_identity::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, 2328 const value_range &lh, 2329 const value_range &rh ATTRIBUTE_UNUSED) const 2330{ 2331 r = lh; 2332 return true; 2333} 2334 2335bool 2336operator_identity::op1_range (value_range &r, tree type ATTRIBUTE_UNUSED, 2337 const value_range &lhs, 2338 const value_range &op2 ATTRIBUTE_UNUSED) const 2339{ 2340 r = lhs; 2341 return true; 2342} 2343 2344 2345class operator_abs : public range_operator 2346{ 2347 public: 2348 virtual void wi_fold (value_range &r, tree type, 2349 const wide_int &lh_lb, 2350 const wide_int &lh_ub, 2351 const wide_int &rh_lb, 2352 const wide_int &rh_ub) const; 2353 virtual bool op1_range (value_range &r, tree type, 2354 const value_range &lhs, 2355 const value_range &op2) const; 2356} op_abs; 2357 2358void 2359operator_abs::wi_fold (value_range &r, tree type, 2360 const wide_int &lh_lb, const wide_int &lh_ub, 2361 const wide_int &rh_lb ATTRIBUTE_UNUSED, 2362 const wide_int &rh_ub ATTRIBUTE_UNUSED) const 2363{ 2364 wide_int min, max; 2365 signop sign = TYPE_SIGN (type); 2366 unsigned prec = TYPE_PRECISION (type); 2367 2368 // Pass through LH for the easy cases. 2369 if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign)) 2370 { 2371 r = value_range (type, lh_lb, lh_ub); 2372 return; 2373 } 2374 2375 // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get 2376 // a useful range. 2377 wide_int min_value = wi::min_value (prec, sign); 2378 wide_int max_value = wi::max_value (prec, sign); 2379 if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value)) 2380 { 2381 r = value_range (type); 2382 return; 2383 } 2384 2385 // ABS_EXPR may flip the range around, if the original range 2386 // included negative values. 2387 if (wi::eq_p (lh_lb, min_value)) 2388 min = max_value; 2389 else 2390 min = wi::abs (lh_lb); 2391 if (wi::eq_p (lh_ub, min_value)) 2392 max = max_value; 2393 else 2394 max = wi::abs (lh_ub); 2395 2396 // If the range contains zero then we know that the minimum value in the 2397 // range will be zero. 2398 if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign)) 2399 { 2400 if (wi::gt_p (min, max, sign)) 2401 max = min; 2402 min = wi::zero (prec); 2403 } 2404 else 2405 { 2406 // If the range was reversed, swap MIN and MAX. 2407 if (wi::gt_p (min, max, sign)) 2408 std::swap (min, max); 2409 } 2410 2411 // If the new range has its limits swapped around (MIN > MAX), then 2412 // the operation caused one of them to wrap around. The only thing 2413 // we know is that the result is positive. 2414 if (wi::gt_p (min, max, sign)) 2415 { 2416 min = wi::zero (prec); 2417 max = max_value; 2418 } 2419 r = value_range (type, min, max); 2420} 2421 2422bool 2423operator_abs::op1_range (value_range &r, tree type, 2424 const value_range &lhs, 2425 const value_range &op2) const 2426{ 2427 if (empty_range_check (r, lhs, op2)) 2428 return true; 2429 if (TYPE_UNSIGNED (type)) 2430 { 2431 r = lhs; 2432 return true; 2433 } 2434 // Start with the positives because negatives are an impossible result. 2435 value_range positives = range_positives (type); 2436 positives.intersect (lhs); 2437 r = positives; 2438 // Then add the negative of each pair: 2439 // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20]. 2440 for (unsigned i = 0; i < positives.num_pairs (); ++i) 2441 r.union_ (value_range (type, 2442 -positives.upper_bound (i), 2443 -positives.lower_bound (i))); 2444 return true; 2445} 2446 2447 2448class operator_absu : public range_operator 2449{ 2450 public: 2451 virtual void wi_fold (value_range &r, tree type, 2452 const wide_int &lh_lb, const wide_int &lh_ub, 2453 const wide_int &rh_lb, const wide_int &rh_ub) const; 2454} op_absu; 2455 2456void 2457operator_absu::wi_fold (value_range &r, tree type, 2458 const wide_int &lh_lb, const wide_int &lh_ub, 2459 const wide_int &rh_lb ATTRIBUTE_UNUSED, 2460 const wide_int &rh_ub ATTRIBUTE_UNUSED) const 2461{ 2462 wide_int new_lb, new_ub; 2463 2464 // Pass through VR0 the easy cases. 2465 if (wi::ges_p (lh_lb, 0)) 2466 { 2467 new_lb = lh_lb; 2468 new_ub = lh_ub; 2469 } 2470 else 2471 { 2472 new_lb = wi::abs (lh_lb); 2473 new_ub = wi::abs (lh_ub); 2474 2475 // If the range contains zero then we know that the minimum 2476 // value in the range will be zero. 2477 if (wi::ges_p (lh_ub, 0)) 2478 { 2479 if (wi::gtu_p (new_lb, new_ub)) 2480 new_ub = new_lb; 2481 new_lb = wi::zero (TYPE_PRECISION (type)); 2482 } 2483 else 2484 std::swap (new_lb, new_ub); 2485 } 2486 2487 gcc_checking_assert (TYPE_UNSIGNED (type)); 2488 r = value_range (type, new_lb, new_ub); 2489} 2490 2491 2492class operator_negate : public range_operator 2493{ 2494 public: 2495 virtual bool fold_range (value_range &r, tree type, 2496 const value_range &op1, 2497 const value_range &op2) const; 2498 virtual bool op1_range (value_range &r, tree type, 2499 const value_range &lhs, 2500 const value_range &op2) const; 2501} op_negate; 2502 2503bool 2504operator_negate::fold_range (value_range &r, tree type, 2505 const value_range &lh, 2506 const value_range &rh) const 2507{ 2508 if (empty_range_check (r, lh, rh)) 2509 return true; 2510 // -X is simply 0 - X. 2511 return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, 2512 range_zero (type), 2513 lh); 2514} 2515 2516bool 2517operator_negate::op1_range (value_range &r, tree type, 2518 const value_range &lhs, 2519 const value_range &op2) const 2520{ 2521 // NEGATE is involutory. 2522 return fold_range (r, type, lhs, op2); 2523} 2524 2525 2526class operator_addr_expr : public range_operator 2527{ 2528public: 2529 virtual bool fold_range (value_range &r, tree type, 2530 const value_range &op1, 2531 const value_range &op2) const; 2532 virtual bool op1_range (value_range &r, tree type, 2533 const value_range &lhs, 2534 const value_range &op2) const; 2535} op_addr; 2536 2537bool 2538operator_addr_expr::fold_range (value_range &r, tree type, 2539 const value_range &lh, 2540 const value_range &rh) const 2541{ 2542 if (empty_range_check (r, lh, rh)) 2543 return true; 2544 2545 // Return a non-null pointer of the LHS type (passed in op2). 2546 if (lh.zero_p ()) 2547 r = range_zero (type); 2548 else if (!lh.contains_p (build_zero_cst (lh.type ()))) 2549 r = range_nonzero (type); 2550 else 2551 r = value_range (type); 2552 return true; 2553} 2554 2555bool 2556operator_addr_expr::op1_range (value_range &r, tree type, 2557 const value_range &lhs, 2558 const value_range &op2) const 2559{ 2560 return operator_addr_expr::fold_range (r, type, lhs, op2); 2561} 2562 2563 2564class pointer_plus_operator : public range_operator 2565{ 2566public: 2567 virtual void wi_fold (value_range &r, tree type, 2568 const wide_int &lh_lb, 2569 const wide_int &lh_ub, 2570 const wide_int &rh_lb, 2571 const wide_int &rh_ub) const; 2572} op_pointer_plus; 2573 2574void 2575pointer_plus_operator::wi_fold (value_range &r, tree type, 2576 const wide_int &lh_lb, 2577 const wide_int &lh_ub, 2578 const wide_int &rh_lb, 2579 const wide_int &rh_ub) const 2580{ 2581 // For pointer types, we are really only interested in asserting 2582 // whether the expression evaluates to non-NULL. 2583 // 2584 // With -fno-delete-null-pointer-checks we need to be more 2585 // conservative. As some object might reside at address 0, 2586 // then some offset could be added to it and the same offset 2587 // subtracted again and the result would be NULL. 2588 // E.g. 2589 // static int a[12]; where &a[0] is NULL and 2590 // ptr = &a[6]; 2591 // ptr -= 6; 2592 // ptr will be NULL here, even when there is POINTER_PLUS_EXPR 2593 // where the first range doesn't include zero and the second one 2594 // doesn't either. As the second operand is sizetype (unsigned), 2595 // consider all ranges where the MSB could be set as possible 2596 // subtractions where the result might be NULL. 2597 if ((!wi_includes_zero_p (type, lh_lb, lh_ub) 2598 || !wi_includes_zero_p (type, rh_lb, rh_ub)) 2599 && !TYPE_OVERFLOW_WRAPS (type) 2600 && (flag_delete_null_pointer_checks 2601 || !wi::sign_mask (rh_ub))) 2602 r = range_nonzero (type); 2603 else if (lh_lb == lh_ub && lh_lb == 0 2604 && rh_lb == rh_ub && rh_lb == 0) 2605 r = range_zero (type); 2606 else 2607 r = value_range (type); 2608} 2609 2610 2611class pointer_min_max_operator : public range_operator 2612{ 2613public: 2614 virtual void wi_fold (value_range & r, tree type, 2615 const wide_int &lh_lb, const wide_int &lh_ub, 2616 const wide_int &rh_lb, const wide_int &rh_ub) const; 2617} op_ptr_min_max; 2618 2619void 2620pointer_min_max_operator::wi_fold (value_range &r, tree type, 2621 const wide_int &lh_lb, 2622 const wide_int &lh_ub, 2623 const wide_int &rh_lb, 2624 const wide_int &rh_ub) const 2625{ 2626 // For MIN/MAX expressions with pointers, we only care about 2627 // nullness. If both are non null, then the result is nonnull. 2628 // If both are null, then the result is null. Otherwise they 2629 // are varying. 2630 if (!wi_includes_zero_p (type, lh_lb, lh_ub) 2631 && !wi_includes_zero_p (type, rh_lb, rh_ub)) 2632 r = range_nonzero (type); 2633 else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub)) 2634 r = range_zero (type); 2635 else 2636 r = value_range (type); 2637} 2638 2639 2640class pointer_and_operator : public range_operator 2641{ 2642public: 2643 virtual void wi_fold (value_range &r, tree type, 2644 const wide_int &lh_lb, const wide_int &lh_ub, 2645 const wide_int &rh_lb, const wide_int &rh_ub) const; 2646} op_pointer_and; 2647 2648void 2649pointer_and_operator::wi_fold (value_range &r, tree type, 2650 const wide_int &lh_lb, 2651 const wide_int &lh_ub, 2652 const wide_int &rh_lb ATTRIBUTE_UNUSED, 2653 const wide_int &rh_ub ATTRIBUTE_UNUSED) const 2654{ 2655 // For pointer types, we are really only interested in asserting 2656 // whether the expression evaluates to non-NULL. 2657 if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub)) 2658 r = range_zero (type); 2659 else 2660 r = value_range (type); 2661} 2662 2663 2664class pointer_or_operator : public range_operator 2665{ 2666public: 2667 virtual void wi_fold (value_range &r, tree type, 2668 const wide_int &lh_lb, const wide_int &lh_ub, 2669 const wide_int &rh_lb, const wide_int &rh_ub) const; 2670} op_pointer_or; 2671 2672void 2673pointer_or_operator::wi_fold (value_range &r, tree type, 2674 const wide_int &lh_lb, 2675 const wide_int &lh_ub, 2676 const wide_int &rh_lb, 2677 const wide_int &rh_ub) const 2678{ 2679 // For pointer types, we are really only interested in asserting 2680 // whether the expression evaluates to non-NULL. 2681 if (!wi_includes_zero_p (type, lh_lb, lh_ub) 2682 && !wi_includes_zero_p (type, rh_lb, rh_ub)) 2683 r = range_nonzero (type); 2684 else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub)) 2685 r = range_zero (type); 2686 else 2687 r = value_range (type); 2688} 2689 2690// This implements the range operator tables as local objects in this file. 2691 2692class range_op_table 2693{ 2694public: 2695 inline range_operator *operator[] (enum tree_code code); 2696protected: 2697 void set (enum tree_code code, range_operator &op); 2698private: 2699 range_operator *m_range_tree[MAX_TREE_CODES]; 2700}; 2701 2702// Return a pointer to the range_operator instance, if there is one 2703// associated with tree_code CODE. 2704 2705range_operator * 2706range_op_table::operator[] (enum tree_code code) 2707{ 2708 gcc_checking_assert (code > 0 && code < MAX_TREE_CODES); 2709 return m_range_tree[code]; 2710} 2711 2712// Add OP to the handler table for CODE. 2713 2714void 2715range_op_table::set (enum tree_code code, range_operator &op) 2716{ 2717 gcc_checking_assert (m_range_tree[code] == NULL); 2718 m_range_tree[code] = &op; 2719} 2720 2721// Instantiate a range op table for integral operations. 2722 2723class integral_table : public range_op_table 2724{ 2725public: 2726 integral_table (); 2727} integral_tree_table; 2728 2729integral_table::integral_table () 2730{ 2731 set (EQ_EXPR, op_equal); 2732 set (NE_EXPR, op_not_equal); 2733 set (LT_EXPR, op_lt); 2734 set (LE_EXPR, op_le); 2735 set (GT_EXPR, op_gt); 2736 set (GE_EXPR, op_ge); 2737 set (PLUS_EXPR, op_plus); 2738 set (MINUS_EXPR, op_minus); 2739 set (MIN_EXPR, op_min); 2740 set (MAX_EXPR, op_max); 2741 set (MULT_EXPR, op_mult); 2742 set (TRUNC_DIV_EXPR, op_trunc_div); 2743 set (FLOOR_DIV_EXPR, op_floor_div); 2744 set (ROUND_DIV_EXPR, op_round_div); 2745 set (CEIL_DIV_EXPR, op_ceil_div); 2746 set (EXACT_DIV_EXPR, op_exact_div); 2747 set (LSHIFT_EXPR, op_lshift); 2748 set (RSHIFT_EXPR, op_rshift); 2749 set (NOP_EXPR, op_convert); 2750 set (CONVERT_EXPR, op_convert); 2751 set (TRUTH_AND_EXPR, op_logical_and); 2752 set (BIT_AND_EXPR, op_bitwise_and); 2753 set (TRUTH_OR_EXPR, op_logical_or); 2754 set (BIT_IOR_EXPR, op_bitwise_or); 2755 set (BIT_XOR_EXPR, op_bitwise_xor); 2756 set (TRUNC_MOD_EXPR, op_trunc_mod); 2757 set (TRUTH_NOT_EXPR, op_logical_not); 2758 set (BIT_NOT_EXPR, op_bitwise_not); 2759 set (INTEGER_CST, op_integer_cst); 2760 set (SSA_NAME, op_identity); 2761 set (PAREN_EXPR, op_identity); 2762 set (OBJ_TYPE_REF, op_identity); 2763 set (ABS_EXPR, op_abs); 2764 set (ABSU_EXPR, op_absu); 2765 set (NEGATE_EXPR, op_negate); 2766 set (ADDR_EXPR, op_addr); 2767} 2768 2769// Instantiate a range op table for pointer operations. 2770 2771class pointer_table : public range_op_table 2772{ 2773public: 2774 pointer_table (); 2775} pointer_tree_table; 2776 2777pointer_table::pointer_table () 2778{ 2779 set (BIT_AND_EXPR, op_pointer_and); 2780 set (BIT_IOR_EXPR, op_pointer_or); 2781 set (MIN_EXPR, op_ptr_min_max); 2782 set (MAX_EXPR, op_ptr_min_max); 2783 set (POINTER_PLUS_EXPR, op_pointer_plus); 2784 2785 set (EQ_EXPR, op_equal); 2786 set (NE_EXPR, op_not_equal); 2787 set (LT_EXPR, op_lt); 2788 set (LE_EXPR, op_le); 2789 set (GT_EXPR, op_gt); 2790 set (GE_EXPR, op_ge); 2791 set (SSA_NAME, op_identity); 2792 set (ADDR_EXPR, op_addr); 2793 set (NOP_EXPR, op_convert); 2794 set (CONVERT_EXPR, op_convert); 2795 2796 set (BIT_NOT_EXPR, op_bitwise_not); 2797 set (BIT_XOR_EXPR, op_bitwise_xor); 2798} 2799 2800// The tables are hidden and accessed via a simple extern function. 2801 2802range_operator * 2803range_op_handler (enum tree_code code, tree type) 2804{ 2805 // First check if there is apointer specialization. 2806 if (POINTER_TYPE_P (type)) 2807 return pointer_tree_table[code]; 2808 return integral_tree_table[code]; 2809} 2810 2811// Cast the range in R to TYPE. 2812 2813void 2814range_cast (value_range &r, tree type) 2815{ 2816 value_range tmp = r; 2817 range_operator *op = range_op_handler (CONVERT_EXPR, type); 2818 // Call op_convert, if it fails, the result is varying. 2819 if (!op->fold_range (r, type, tmp, value_range (type))) 2820 r = value_range (type); 2821} 2822 2823#if CHECKING_P 2824#include "selftest.h" 2825#include "stor-layout.h" 2826 2827namespace selftest 2828{ 2829#define INT(N) build_int_cst (integer_type_node, (N)) 2830#define UINT(N) build_int_cstu (unsigned_type_node, (N)) 2831#define INT16(N) build_int_cst (short_integer_type_node, (N)) 2832#define UINT16(N) build_int_cstu (short_unsigned_type_node, (N)) 2833#define INT64(N) build_int_cstu (long_long_integer_type_node, (N)) 2834#define UINT64(N) build_int_cstu (long_long_unsigned_type_node, (N)) 2835#define UINT128(N) build_int_cstu (u128_type, (N)) 2836#define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N)) 2837#define SCHAR(N) build_int_cst (signed_char_type_node, (N)) 2838 2839// Run all of the selftests within this file. 2840 2841void 2842range_tests () 2843{ 2844 tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1); 2845 value_range i1, i2, i3; 2846 value_range r0, r1, rold; 2847 2848 // Test that NOT(255) is [0..254] in 8-bit land. 2849 value_range not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE); 2850 ASSERT_TRUE (not_255 == value_range (UCHAR (0), UCHAR (254))); 2851 2852 // Test that NOT(0) is [1..255] in 8-bit land. 2853 value_range not_zero = range_nonzero (unsigned_char_type_node); 2854 ASSERT_TRUE (not_zero == value_range (UCHAR (1), UCHAR (255))); 2855 2856 // Check that [0,127][0x..ffffff80,0x..ffffff] 2857 // => ~[128, 0x..ffffff7f]. 2858 r0 = value_range (UINT128 (0), UINT128 (127)); 2859 tree high = build_minus_one_cst (u128_type); 2860 // low = -1 - 127 => 0x..ffffff80. 2861 tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127)); 2862 r1 = value_range (low, high); // [0x..ffffff80, 0x..ffffffff] 2863 // r0 = [0,127][0x..ffffff80,0x..fffffff]. 2864 r0.union_ (r1); 2865 // r1 = [128, 0x..ffffff7f]. 2866 r1 = value_range (UINT128(128), 2867 fold_build2 (MINUS_EXPR, u128_type, 2868 build_minus_one_cst (u128_type), 2869 UINT128(128))); 2870 r0.invert (); 2871 ASSERT_TRUE (r0 == r1); 2872 2873 r0.set_varying (integer_type_node); 2874 tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ()); 2875 tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ()); 2876 2877 r0.set_varying (short_integer_type_node); 2878 tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ()); 2879 tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ()); 2880 2881 r0.set_varying (unsigned_type_node); 2882 tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ()); 2883 2884 // Check that ~[0,5] => [6,MAX] for unsigned int. 2885 r0 = value_range (UINT (0), UINT (5)); 2886 r0.invert (); 2887 ASSERT_TRUE (r0 == value_range (UINT(6), maxuint)); 2888 2889 // Check that ~[10,MAX] => [0,9] for unsigned int. 2890 r0 = value_range (UINT(10), maxuint); 2891 r0.invert (); 2892 ASSERT_TRUE (r0 == value_range (UINT (0), UINT (9))); 2893 2894 // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers. 2895 r0 = value_range (UINT128 (0), UINT128 (5), VR_ANTI_RANGE); 2896 r1 = value_range (UINT128(6), build_minus_one_cst (u128_type)); 2897 ASSERT_TRUE (r0 == r1); 2898 2899 // Check that [~5] is really [-MIN,4][6,MAX]. 2900 r0 = value_range (INT (5), INT (5), VR_ANTI_RANGE); 2901 r1 = value_range (minint, INT (4)); 2902 r1.union_ (value_range (INT (6), maxint)); 2903 ASSERT_FALSE (r1.undefined_p ()); 2904 ASSERT_TRUE (r0 == r1); 2905 2906 r1 = value_range (INT (5), INT (5)); 2907 value_range r2 (r1); 2908 ASSERT_TRUE (r1 == r2); 2909 2910 r1 = value_range (INT (5), INT (10)); 2911 2912 r1 = value_range (integer_type_node, 2913 wi::to_wide (INT (5)), wi::to_wide (INT (10))); 2914 ASSERT_TRUE (r1.contains_p (INT (7))); 2915 2916 r1 = value_range (SCHAR (0), SCHAR (20)); 2917 ASSERT_TRUE (r1.contains_p (SCHAR(15))); 2918 ASSERT_FALSE (r1.contains_p (SCHAR(300))); 2919 2920 // If a range is in any way outside of the range for the converted 2921 // to range, default to the range for the new type. 2922 if (TYPE_PRECISION (TREE_TYPE (maxint)) 2923 > TYPE_PRECISION (short_integer_type_node)) 2924 { 2925 r1 = value_range (integer_zero_node, maxint); 2926 range_cast (r1, short_integer_type_node); 2927 ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort) 2928 && r1.upper_bound() == wi::to_wide (maxshort)); 2929 } 2930 2931 // (unsigned char)[-5,-1] => [251,255]. 2932 r0 = rold = value_range (SCHAR (-5), SCHAR (-1)); 2933 range_cast (r0, unsigned_char_type_node); 2934 ASSERT_TRUE (r0 == value_range (UCHAR (251), UCHAR (255))); 2935 range_cast (r0, signed_char_type_node); 2936 ASSERT_TRUE (r0 == rold); 2937 2938 // (signed char)[15, 150] => [-128,-106][15,127]. 2939 r0 = rold = value_range (UCHAR (15), UCHAR (150)); 2940 range_cast (r0, signed_char_type_node); 2941 r1 = value_range (SCHAR (15), SCHAR (127)); 2942 r2 = value_range (SCHAR (-128), SCHAR (-106)); 2943 r1.union_ (r2); 2944 ASSERT_TRUE (r1 == r0); 2945 range_cast (r0, unsigned_char_type_node); 2946 ASSERT_TRUE (r0 == rold); 2947 2948 // (unsigned char)[-5, 5] => [0,5][251,255]. 2949 r0 = rold = value_range (SCHAR (-5), SCHAR (5)); 2950 range_cast (r0, unsigned_char_type_node); 2951 r1 = value_range (UCHAR (251), UCHAR (255)); 2952 r2 = value_range (UCHAR (0), UCHAR (5)); 2953 r1.union_ (r2); 2954 ASSERT_TRUE (r0 == r1); 2955 range_cast (r0, signed_char_type_node); 2956 ASSERT_TRUE (r0 == rold); 2957 2958 // (unsigned char)[-5,5] => [0,5][251,255]. 2959 r0 = value_range (INT (-5), INT (5)); 2960 range_cast (r0, unsigned_char_type_node); 2961 r1 = value_range (UCHAR (0), UCHAR (5)); 2962 r1.union_ (value_range (UCHAR (251), UCHAR (255))); 2963 ASSERT_TRUE (r0 == r1); 2964 2965 // (unsigned char)[5U,1974U] => [0,255]. 2966 r0 = value_range (UINT (5), UINT (1974)); 2967 range_cast (r0, unsigned_char_type_node); 2968 ASSERT_TRUE (r0 == value_range (UCHAR (0), UCHAR (255))); 2969 range_cast (r0, integer_type_node); 2970 // Going to a wider range should not sign extend. 2971 ASSERT_TRUE (r0 == value_range (INT (0), INT (255))); 2972 2973 // (unsigned char)[-350,15] => [0,255]. 2974 r0 = value_range (INT (-350), INT (15)); 2975 range_cast (r0, unsigned_char_type_node); 2976 ASSERT_TRUE (r0 == (value_range 2977 (TYPE_MIN_VALUE (unsigned_char_type_node), 2978 TYPE_MAX_VALUE (unsigned_char_type_node)))); 2979 2980 // Casting [-120,20] from signed char to unsigned short. 2981 // => [0, 20][0xff88, 0xffff]. 2982 r0 = value_range (SCHAR (-120), SCHAR (20)); 2983 range_cast (r0, short_unsigned_type_node); 2984 r1 = value_range (UINT16 (0), UINT16 (20)); 2985 r2 = value_range (UINT16 (0xff88), UINT16 (0xffff)); 2986 r1.union_ (r2); 2987 ASSERT_TRUE (r0 == r1); 2988 // A truncating cast back to signed char will work because [-120, 20] 2989 // is representable in signed char. 2990 range_cast (r0, signed_char_type_node); 2991 ASSERT_TRUE (r0 == value_range (SCHAR (-120), SCHAR (20))); 2992 2993 // unsigned char -> signed short 2994 // (signed short)[(unsigned char)25, (unsigned char)250] 2995 // => [(signed short)25, (signed short)250] 2996 r0 = rold = value_range (UCHAR (25), UCHAR (250)); 2997 range_cast (r0, short_integer_type_node); 2998 r1 = value_range (INT16 (25), INT16 (250)); 2999 ASSERT_TRUE (r0 == r1); 3000 range_cast (r0, unsigned_char_type_node); 3001 ASSERT_TRUE (r0 == rold); 3002 3003 // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned. 3004 r0 = value_range (TYPE_MIN_VALUE (long_long_integer_type_node), 3005 TYPE_MAX_VALUE (long_long_integer_type_node)); 3006 range_cast (r0, short_unsigned_type_node); 3007 r1 = value_range (TYPE_MIN_VALUE (short_unsigned_type_node), 3008 TYPE_MAX_VALUE (short_unsigned_type_node)); 3009 ASSERT_TRUE (r0 == r1); 3010 3011 // NOT([10,20]) ==> [-MIN,9][21,MAX]. 3012 r0 = r1 = value_range (INT (10), INT (20)); 3013 r2 = value_range (minint, INT(9)); 3014 r2.union_ (value_range (INT(21), maxint)); 3015 ASSERT_FALSE (r2.undefined_p ()); 3016 r1.invert (); 3017 ASSERT_TRUE (r1 == r2); 3018 // Test that NOT(NOT(x)) == x. 3019 r2.invert (); 3020 ASSERT_TRUE (r0 == r2); 3021 3022 // Test that booleans and their inverse work as expected. 3023 r0 = range_zero (boolean_type_node); 3024 ASSERT_TRUE (r0 == value_range (build_zero_cst (boolean_type_node), 3025 build_zero_cst (boolean_type_node))); 3026 r0.invert (); 3027 ASSERT_TRUE (r0 == value_range (build_one_cst (boolean_type_node), 3028 build_one_cst (boolean_type_node))); 3029 3030 // Casting NONZERO to a narrower type will wrap/overflow so 3031 // it's just the entire range for the narrower type. 3032 // 3033 // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32]. This is 3034 // is outside of the range of a smaller range, return the full 3035 // smaller range. 3036 if (TYPE_PRECISION (integer_type_node) 3037 > TYPE_PRECISION (short_integer_type_node)) 3038 { 3039 r0 = range_nonzero (integer_type_node); 3040 range_cast (r0, short_integer_type_node); 3041 r1 = value_range (TYPE_MIN_VALUE (short_integer_type_node), 3042 TYPE_MAX_VALUE (short_integer_type_node)); 3043 ASSERT_TRUE (r0 == r1); 3044 } 3045 3046 // Casting NONZERO from a narrower signed to a wider signed. 3047 // 3048 // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16]. 3049 // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16]. 3050 r0 = range_nonzero (short_integer_type_node); 3051 range_cast (r0, integer_type_node); 3052 r1 = value_range (INT (-32768), INT (-1)); 3053 r2 = value_range (INT (1), INT (32767)); 3054 r1.union_ (r2); 3055 ASSERT_TRUE (r0 == r1); 3056 3057 // Make sure NULL and non-NULL of pointer types work, and that 3058 // inverses of them are consistent. 3059 tree voidp = build_pointer_type (void_type_node); 3060 r0 = range_zero (voidp); 3061 r1 = r0; 3062 r0.invert (); 3063 r0.invert (); 3064 ASSERT_TRUE (r0 == r1); 3065 3066 // [10,20] U [15, 30] => [10, 30]. 3067 r0 = value_range (INT (10), INT (20)); 3068 r1 = value_range (INT (15), INT (30)); 3069 r0.union_ (r1); 3070 ASSERT_TRUE (r0 == value_range (INT (10), INT (30))); 3071 3072 // [15,40] U [] => [15,40]. 3073 r0 = value_range (INT (15), INT (40)); 3074 r1.set_undefined (); 3075 r0.union_ (r1); 3076 ASSERT_TRUE (r0 == value_range (INT (15), INT (40))); 3077 3078 // [10,20] U [10,10] => [10,20]. 3079 r0 = value_range (INT (10), INT (20)); 3080 r1 = value_range (INT (10), INT (10)); 3081 r0.union_ (r1); 3082 ASSERT_TRUE (r0 == value_range (INT (10), INT (20))); 3083 3084 // [10,20] U [9,9] => [9,20]. 3085 r0 = value_range (INT (10), INT (20)); 3086 r1 = value_range (INT (9), INT (9)); 3087 r0.union_ (r1); 3088 ASSERT_TRUE (r0 == value_range (INT (9), INT (20))); 3089 3090 // [10,20] ^ [15,30] => [15,20]. 3091 r0 = value_range (INT (10), INT (20)); 3092 r1 = value_range (INT (15), INT (30)); 3093 r0.intersect (r1); 3094 ASSERT_TRUE (r0 == value_range (INT (15), INT (20))); 3095 3096 // Test the internal sanity of wide_int's wrt HWIs. 3097 ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node), 3098 TYPE_SIGN (boolean_type_node)) 3099 == wi::uhwi (1, TYPE_PRECISION (boolean_type_node))); 3100 3101 // Test zero_p(). 3102 r0 = value_range (INT (0), INT (0)); 3103 ASSERT_TRUE (r0.zero_p ()); 3104 3105 // Test nonzero_p(). 3106 r0 = value_range (INT (0), INT (0)); 3107 r0.invert (); 3108 ASSERT_TRUE (r0.nonzero_p ()); 3109} 3110 3111} // namespace selftest 3112 3113#endif // CHECKING_P 3114