1 /* Support routines for value ranges. 2 Copyright (C) 2019-2022 Free Software Foundation, Inc. 3 Contributed by Aldy Hernandez <aldyh (at) redhat.com> and 4 Andrew Macleod <amacleod (at) redhat.com>. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 GCC is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 #ifndef GCC_VALUE_RANGE_H 23 #define GCC_VALUE_RANGE_H 24 25 // Types of value ranges. 26 enum value_range_kind 27 { 28 /* Empty range. */ 29 VR_UNDEFINED, 30 /* Range spans the entire domain. */ 31 VR_VARYING, 32 /* Range is [MIN, MAX]. */ 33 VR_RANGE, 34 /* Range is ~[MIN, MAX]. */ 35 VR_ANTI_RANGE, 36 /* Range is a nice guy. */ 37 VR_LAST 38 }; 39 40 // Range of values that can be associated with an SSA_NAME. 41 // 42 // This is the base class without any storage. 43 44 class GTY((user)) irange 45 { 46 friend class irange_allocator; 47 public: 48 // In-place setters. 49 void set (tree, tree, value_range_kind = VR_RANGE); 50 void set_nonzero (tree); 51 void set_zero (tree); 52 void set_varying (tree type); 53 void set_undefined (); 54 55 // Range types. 56 static bool supports_type_p (tree); 57 tree type () const; 58 59 // Iteration over sub-ranges. 60 unsigned num_pairs () const; 61 wide_int lower_bound (unsigned = 0) const; 62 wide_int upper_bound (unsigned) const; 63 wide_int upper_bound () const; 64 65 // Predicates. 66 bool zero_p () const; 67 bool nonzero_p () const; 68 bool undefined_p () const; 69 bool varying_p () const; 70 bool singleton_p (tree *result = NULL) const; 71 bool contains_p (tree) const; 72 73 // In-place operators. 74 void union_ (const irange &); 75 void intersect (const irange &); 76 void intersect (const wide_int& lb, const wide_int& ub); 77 void invert (); 78 79 // Operator overloads. 80 irange& operator= (const irange &); 81 bool operator== (const irange &) const; 82 bool operator!= (const irange &r) const { return !(*this == r); } 83 84 // Misc methods. 85 bool fits_p (const irange &r) { return m_max_ranges >= r.num_pairs (); } 86 void dump (FILE * = stderr) const; 87 void debug () const; 88 89 // Deprecated legacy public methods. 90 enum value_range_kind kind () const; // DEPRECATED 91 tree min () const; // DEPRECATED 92 tree max () const; // DEPRECATED 93 bool symbolic_p () const; // DEPRECATED 94 bool constant_p () const; // DEPRECATED 95 void normalize_symbolics (); // DEPRECATED 96 void normalize_addresses (); // DEPRECATED 97 bool may_contain_p (tree) const; // DEPRECATED 98 void set (tree); // DEPRECATED 99 bool equal_p (const irange &) const; // DEPRECATED 100 void union_ (const class irange *); // DEPRECATED 101 void intersect (const irange *); // DEPRECATED 102 103 protected: 104 irange (tree *, unsigned); 105 // potential promotion to public? 106 tree tree_lower_bound (unsigned = 0) const; 107 tree tree_upper_bound (unsigned) const; 108 tree tree_upper_bound () const; 109 110 // In-place operators. 111 void irange_union (const irange &); 112 void irange_intersect (const irange &); 113 void irange_set (tree, tree); 114 void irange_set_anti_range (tree, tree); 115 116 void normalize_kind (); 117 118 bool legacy_mode_p () const; 119 bool legacy_equal_p (const irange &) const; 120 void legacy_union (irange *, const irange *); 121 void legacy_intersect (irange *, const irange *); 122 void verify_range (); 123 wide_int legacy_lower_bound (unsigned = 0) const; 124 wide_int legacy_upper_bound (unsigned) const; 125 int value_inside_range (tree) const; 126 bool maybe_anti_range () const; 127 void copy_to_legacy (const irange &); 128 void copy_legacy_to_multi_range (const irange &); 129 130 private: 131 friend void gt_ggc_mx (irange *); 132 friend void gt_pch_nx (irange *); 133 friend void gt_pch_nx (irange *, gt_pointer_operator, void *); 134 135 void irange_set_1bit_anti_range (tree, tree); 136 bool varying_compatible_p () const; 137 138 unsigned char m_num_ranges; 139 unsigned char m_max_ranges; 140 ENUM_BITFIELD(value_range_kind) m_kind : 8; 141 tree *m_base; 142 }; 143 144 // Here we describe an irange with N pairs of ranges. The storage for 145 // the pairs is embedded in the class as an array. 146 147 template<unsigned N> 148 class GTY((user)) int_range : public irange 149 { 150 public: 151 int_range (); 152 int_range (tree, tree, value_range_kind = VR_RANGE); 153 int_range (tree type, const wide_int &, const wide_int &, 154 value_range_kind = VR_RANGE); 155 int_range (tree type); 156 int_range (const int_range &); 157 int_range (const irange &); 158 int_range& operator= (const int_range &); 159 private: 160 template <unsigned X> friend void gt_ggc_mx (int_range<X> *); 161 template <unsigned X> friend void gt_pch_nx (int_range<X> *); 162 template <unsigned X> friend void gt_pch_nx (int_range<X> *, 163 gt_pointer_operator, void *); 164 165 // ?? These stubs are for ipa-prop.cc which use a value_range in a 166 // hash_traits. hash-traits.h defines an extern of gt_ggc_mx (T &) 167 // instead of picking up the gt_ggc_mx (T *) version. 168 friend void gt_ggc_mx (int_range<1> *&); 169 friend void gt_pch_nx (int_range<1> *&); 170 171 tree m_ranges[N*2]; 172 }; 173 174 // This is a special int_range<1> with only one pair, plus 175 // VR_ANTI_RANGE magic to describe slightly more than can be described 176 // in one pair. It is described in the code as a "legacy range" (as 177 // opposed to multi-ranges which have multiple sub-ranges). It is 178 // provided for backward compatibility with code that has not been 179 // converted to multi-range irange's. 180 // 181 // There are copy operators to seamlessly copy to/fro multi-ranges. 182 typedef int_range<1> value_range; 183 184 // This is an "infinite" precision irange for use in temporary 185 // calculations. 186 typedef int_range<255> int_range_max; 187 188 // Returns true for an old-school value_range as described above. 189 inline bool 190 irange::legacy_mode_p () const 191 { 192 return m_max_ranges == 1; 193 } 194 195 extern bool range_has_numeric_bounds_p (const irange *); 196 extern bool ranges_from_anti_range (const value_range *, 197 value_range *, value_range *); 198 extern void dump_value_range (FILE *, const irange *); 199 extern bool vrp_val_is_min (const_tree); 200 extern bool vrp_val_is_max (const_tree); 201 extern bool vrp_operand_equal_p (const_tree, const_tree); 202 203 inline value_range_kind 204 irange::kind () const 205 { 206 return m_kind; 207 } 208 209 // Number of sub-ranges in a range. 210 211 inline unsigned 212 irange::num_pairs () const 213 { 214 if (m_kind == VR_ANTI_RANGE) 215 return constant_p () ? 2 : 1; 216 else 217 return m_num_ranges; 218 } 219 220 inline tree 221 irange::type () const 222 { 223 gcc_checking_assert (m_num_ranges > 0); 224 return TREE_TYPE (m_base[0]); 225 } 226 227 // Return the lower bound of a sub-range expressed as a tree. PAIR is 228 // the sub-range in question. 229 230 inline tree 231 irange::tree_lower_bound (unsigned pair) const 232 { 233 return m_base[pair * 2]; 234 } 235 236 // Return the upper bound of a sub-range expressed as a tree. PAIR is 237 // the sub-range in question. 238 239 inline tree 240 irange::tree_upper_bound (unsigned pair) const 241 { 242 return m_base[pair * 2 + 1]; 243 } 244 245 // Return the highest bound of a range expressed as a tree. 246 247 inline tree 248 irange::tree_upper_bound () const 249 { 250 gcc_checking_assert (m_num_ranges); 251 return tree_upper_bound (m_num_ranges - 1); 252 } 253 254 inline tree 255 irange::min () const 256 { 257 return tree_lower_bound (0); 258 } 259 260 inline tree 261 irange::max () const 262 { 263 if (m_num_ranges) 264 return tree_upper_bound (); 265 else 266 return NULL; 267 } 268 269 inline bool 270 irange::varying_compatible_p () const 271 { 272 if (m_num_ranges != 1) 273 return false; 274 275 tree l = m_base[0]; 276 tree u = m_base[1]; 277 tree t = TREE_TYPE (l); 278 279 if (m_kind == VR_VARYING && t == error_mark_node) 280 return true; 281 282 unsigned prec = TYPE_PRECISION (t); 283 signop sign = TYPE_SIGN (t); 284 if (INTEGRAL_TYPE_P (t)) 285 return (wi::to_wide (l) == wi::min_value (prec, sign) 286 && wi::to_wide (u) == wi::max_value (prec, sign)); 287 if (POINTER_TYPE_P (t)) 288 return (wi::to_wide (l) == 0 289 && wi::to_wide (u) == wi::max_value (prec, sign)); 290 return true; 291 } 292 293 inline bool 294 irange::varying_p () const 295 { 296 return m_kind == VR_VARYING; 297 } 298 299 inline bool 300 irange::undefined_p () const 301 { 302 return m_kind == VR_UNDEFINED; 303 } 304 305 inline bool 306 irange::zero_p () const 307 { 308 return (m_kind == VR_RANGE && m_num_ranges == 1 309 && integer_zerop (tree_lower_bound (0)) 310 && integer_zerop (tree_upper_bound (0))); 311 } 312 313 inline bool 314 irange::nonzero_p () const 315 { 316 if (undefined_p ()) 317 return false; 318 319 tree zero = build_zero_cst (type ()); 320 return *this == int_range<1> (zero, zero, VR_ANTI_RANGE); 321 } 322 323 inline bool 324 irange::supports_type_p (tree type) 325 { 326 if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))) 327 return type; 328 return false; 329 } 330 331 inline bool 332 range_includes_zero_p (const irange *vr) 333 { 334 if (vr->undefined_p ()) 335 return false; 336 337 if (vr->varying_p ()) 338 return true; 339 340 return vr->may_contain_p (build_zero_cst (vr->type ())); 341 } 342 343 inline void 344 gt_ggc_mx (irange *x) 345 { 346 for (unsigned i = 0; i < x->m_num_ranges; ++i) 347 { 348 gt_ggc_mx (x->m_base[i * 2]); 349 gt_ggc_mx (x->m_base[i * 2 + 1]); 350 } 351 } 352 353 inline void 354 gt_pch_nx (irange *x) 355 { 356 for (unsigned i = 0; i < x->m_num_ranges; ++i) 357 { 358 gt_pch_nx (x->m_base[i * 2]); 359 gt_pch_nx (x->m_base[i * 2 + 1]); 360 } 361 } 362 363 inline void 364 gt_pch_nx (irange *x, gt_pointer_operator op, void *cookie) 365 { 366 for (unsigned i = 0; i < x->m_num_ranges; ++i) 367 { 368 op (&x->m_base[i * 2], NULL, cookie); 369 op (&x->m_base[i * 2 + 1], NULL, cookie); 370 } 371 } 372 373 template<unsigned N> 374 inline void 375 gt_ggc_mx (int_range<N> *x) 376 { 377 gt_ggc_mx ((irange *) x); 378 } 379 380 template<unsigned N> 381 inline void 382 gt_pch_nx (int_range<N> *x) 383 { 384 gt_pch_nx ((irange *) x); 385 } 386 387 template<unsigned N> 388 inline void 389 gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie) 390 { 391 gt_pch_nx ((irange *) x, op, cookie); 392 } 393 394 // Constructors for irange 395 396 inline 397 irange::irange (tree *base, unsigned nranges) 398 { 399 m_base = base; 400 m_num_ranges = 0; 401 m_max_ranges = nranges; 402 m_kind = VR_UNDEFINED; 403 } 404 405 // Constructors for int_range<>. 406 407 template<unsigned N> 408 inline 409 int_range<N>::int_range () 410 : irange (m_ranges, N) 411 { 412 } 413 414 template<unsigned N> 415 int_range<N>::int_range (const int_range &other) 416 : irange (m_ranges, N) 417 { 418 irange::operator= (other); 419 } 420 421 template<unsigned N> 422 int_range<N>::int_range (tree min, tree max, value_range_kind kind) 423 : irange (m_ranges, N) 424 { 425 irange::set (min, max, kind); 426 } 427 428 template<unsigned N> 429 int_range<N>::int_range (tree type) 430 : irange (m_ranges, N) 431 { 432 set_varying (type); 433 } 434 435 template<unsigned N> 436 int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax, 437 value_range_kind kind) 438 : irange (m_ranges, N) 439 { 440 tree min = wide_int_to_tree (type, wmin); 441 tree max = wide_int_to_tree (type, wmax); 442 set (min, max, kind); 443 } 444 445 template<unsigned N> 446 int_range<N>::int_range (const irange &other) 447 : irange (m_ranges, N) 448 { 449 irange::operator= (other); 450 } 451 452 template<unsigned N> 453 int_range<N>& 454 int_range<N>::operator= (const int_range &src) 455 { 456 irange::operator= (src); 457 return *this; 458 } 459 460 inline void 461 irange::set (tree val) 462 { 463 set (val, val); 464 } 465 466 inline void 467 irange::set_undefined () 468 { 469 m_kind = VR_UNDEFINED; 470 m_num_ranges = 0; 471 } 472 473 inline void 474 irange::set_varying (tree type) 475 { 476 m_kind = VR_VARYING; 477 m_num_ranges = 1; 478 479 if (INTEGRAL_TYPE_P (type)) 480 { 481 // Strict enum's require varying to be not TYPE_MIN/MAX, but rather 482 // min_value and max_value. 483 wide_int min = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)); 484 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); 485 if (wi::eq_p (max, wi::to_wide (TYPE_MAX_VALUE (type))) 486 && wi::eq_p (min, wi::to_wide (TYPE_MIN_VALUE (type)))) 487 { 488 m_base[0] = TYPE_MIN_VALUE (type); 489 m_base[1] = TYPE_MAX_VALUE (type); 490 } 491 else 492 { 493 m_base[0] = wide_int_to_tree (type, min); 494 m_base[1] = wide_int_to_tree (type, max); 495 } 496 } 497 else if (POINTER_TYPE_P (type)) 498 { 499 m_base[0] = build_int_cst (type, 0); 500 m_base[1] = build_int_cst (type, -1); 501 } 502 else 503 m_base[0] = m_base[1] = error_mark_node; 504 } 505 506 inline bool 507 irange::operator== (const irange &r) const 508 { 509 return equal_p (r); 510 } 511 512 // Return the lower bound of a sub-range. PAIR is the sub-range in 513 // question. 514 515 inline wide_int 516 irange::lower_bound (unsigned pair) const 517 { 518 if (legacy_mode_p ()) 519 return legacy_lower_bound (pair); 520 gcc_checking_assert (m_num_ranges > 0); 521 gcc_checking_assert (pair + 1 <= num_pairs ()); 522 return wi::to_wide (tree_lower_bound (pair)); 523 } 524 525 // Return the upper bound of a sub-range. PAIR is the sub-range in 526 // question. 527 528 inline wide_int 529 irange::upper_bound (unsigned pair) const 530 { 531 if (legacy_mode_p ()) 532 return legacy_upper_bound (pair); 533 gcc_checking_assert (m_num_ranges > 0); 534 gcc_checking_assert (pair + 1 <= num_pairs ()); 535 return wi::to_wide (tree_upper_bound (pair)); 536 } 537 538 // Return the highest bound of a range. 539 540 inline wide_int 541 irange::upper_bound () const 542 { 543 unsigned pairs = num_pairs (); 544 gcc_checking_assert (pairs > 0); 545 return upper_bound (pairs - 1); 546 } 547 548 inline void 549 irange::union_ (const irange &r) 550 { 551 dump_flags_t m_flags = dump_flags; 552 dump_flags &= ~TDF_DETAILS; 553 irange::union_ (&r); 554 dump_flags = m_flags; 555 } 556 557 inline void 558 irange::intersect (const irange &r) 559 { 560 dump_flags_t m_flags = dump_flags; 561 dump_flags &= ~TDF_DETAILS; 562 irange::intersect (&r); 563 dump_flags = m_flags; 564 } 565 566 // Set value range VR to a nonzero range of type TYPE. 567 568 inline void 569 irange::set_nonzero (tree type) 570 { 571 tree zero = build_int_cst (type, 0); 572 if (legacy_mode_p ()) 573 set (zero, zero, VR_ANTI_RANGE); 574 else 575 irange_set_anti_range (zero, zero); 576 } 577 578 // Set value range VR to a ZERO range of type TYPE. 579 580 inline void 581 irange::set_zero (tree type) 582 { 583 tree z = build_int_cst (type, 0); 584 if (legacy_mode_p ()) 585 set (z); 586 else 587 irange_set (z, z); 588 } 589 590 // Normalize a range to VARYING or UNDEFINED if possible. 591 592 inline void 593 irange::normalize_kind () 594 { 595 if (m_num_ranges == 0) 596 m_kind = VR_UNDEFINED; 597 else if (varying_compatible_p ()) 598 { 599 if (m_kind == VR_RANGE) 600 m_kind = VR_VARYING; 601 else if (m_kind == VR_ANTI_RANGE) 602 set_undefined (); 603 else 604 gcc_unreachable (); 605 } 606 } 607 608 inline bool 609 contains_zero_p (const irange &r) 610 { 611 if (r.undefined_p ()) 612 return false; 613 614 tree zero = build_zero_cst (r.type ()); 615 return r.contains_p (zero); 616 } 617 618 // Return the maximum value for TYPE. 619 620 inline tree 621 vrp_val_max (const_tree type) 622 { 623 if (INTEGRAL_TYPE_P (type)) 624 return TYPE_MAX_VALUE (type); 625 if (POINTER_TYPE_P (type)) 626 { 627 wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); 628 return wide_int_to_tree (const_cast<tree> (type), max); 629 } 630 return NULL_TREE; 631 } 632 633 // Return the minimum value for TYPE. 634 635 inline tree 636 vrp_val_min (const_tree type) 637 { 638 if (INTEGRAL_TYPE_P (type)) 639 return TYPE_MIN_VALUE (type); 640 if (POINTER_TYPE_P (type)) 641 return build_zero_cst (const_cast<tree> (type)); 642 return NULL_TREE; 643 } 644 645 // This is the irange storage class. It is used to allocate the 646 // minimum amount of storage needed for a given irange. Storage is 647 // automatically freed at destruction of the storage class. 648 // 649 // It is meant for long term storage, as opposed to int_range_max 650 // which is meant for intermediate temporary results on the stack. 651 // 652 // The newly allocated irange is initialized to the empty set 653 // (undefined_p() is true). 654 655 class irange_allocator 656 { 657 public: 658 irange_allocator (); 659 ~irange_allocator (); 660 // Return a new range with NUM_PAIRS. 661 irange *allocate (unsigned num_pairs); 662 // Return a copy of SRC with the minimum amount of sub-ranges needed 663 // to represent it. 664 irange *allocate (const irange &src); 665 void *get_memory (unsigned num_bytes); 666 private: 667 DISABLE_COPY_AND_ASSIGN (irange_allocator); 668 struct obstack m_obstack; 669 }; 670 671 inline 672 irange_allocator::irange_allocator () 673 { 674 obstack_init (&m_obstack); 675 } 676 677 inline 678 irange_allocator::~irange_allocator () 679 { 680 obstack_free (&m_obstack, NULL); 681 } 682 683 // Provide a hunk of memory from the obstack. 684 inline void * 685 irange_allocator::get_memory (unsigned num_bytes) 686 { 687 void *r = obstack_alloc (&m_obstack, num_bytes); 688 return r; 689 } 690 691 // Return a new range with NUM_PAIRS. 692 693 inline irange * 694 irange_allocator::allocate (unsigned num_pairs) 695 { 696 // Never allocate 0 pairs. 697 // Don't allocate 1 either, or we get legacy value_range's. 698 if (num_pairs < 2) 699 num_pairs = 2; 700 701 size_t nbytes = sizeof (tree) * 2 * num_pairs; 702 703 // Allocate the irange and required memory for the vector. 704 void *r = obstack_alloc (&m_obstack, sizeof (irange)); 705 tree *mem = (tree *) obstack_alloc (&m_obstack, nbytes); 706 return new (r) irange (mem, num_pairs); 707 } 708 709 inline irange * 710 irange_allocator::allocate (const irange &src) 711 { 712 irange *r = allocate (src.num_pairs ()); 713 *r = src; 714 return r; 715 } 716 717 #endif // GCC_VALUE_RANGE_H 718
Indexes created Tue Feb 24 01:34:59 UTC 2026