LCOV - code coverage report
Current view: top level - gcc - value-range.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 93.2 % 2305 2148
Test Date: 2026-11-14 16:39:50 Functions: 83.3 % 156 130
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Support routines for value ranges.
       2              :    Copyright (C) 2019-2026 Free Software Foundation, Inc.
       3              :    Major hacks by Aldy Hernandez <aldyh@redhat.com> and
       4              :    Andrew MacLeod <amacleod@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              : #include "config.h"
      23              : #include "system.h"
      24              : #include "coretypes.h"
      25              : #include "backend.h"
      26              : #include "tree.h"
      27              : #include "gimple.h"
      28              : #include "ssa.h"
      29              : #include "pretty-print.h"
      30              : #include "value-range-pretty-print.h"
      31              : #include "value-range-storage.h"
      32              : #include "fold-const.h"
      33              : #include "gimple-range.h"
      34              : #include "tree-dfa.h"
      35              : #include "tree-affine.h"
      36              : 
      37              : // Return the bitmask inherent in a range :   TYPE [MIN, MAX].
      38              : // This used to be get_bitmask_from_range ().
      39              : 
      40   1401671098 : irange_bitmask::irange_bitmask (tree type,
      41   1401671098 :                                 const wide_int &min, const wide_int &max)
      42              : {
      43   1401671098 :   unsigned prec = TYPE_PRECISION (type);
      44              :   // All the bits of a singleton are known.
      45   1401671098 :   if (min == max)
      46              :     {
      47    192240787 :       m_mask = wi::zero (prec);
      48    192240787 :       m_value = min;
      49              :     }
      50              :   else
      51              :     {
      52   1209430311 :       wide_int xorv = min ^ max;
      53              :       // Mask will have leading zeros for all leading bits that are
      54              :       // common, both zeros and ones.
      55   1209430311 :       m_mask = wi::mask (prec - wi::clz (xorv), false, prec);
      56              :       // Now set value to those bits which are known, and zero the rest.
      57   1209579617 :       m_value = ~m_mask & min;
      58   1209430311 :     }
      59   1401671098 : }
      60              : 
      61              : // Return a range in R of TYPE for this bitmask which encompasses
      62              : // a set of valid values which are allowable for this bitmask/value
      63              : // combination.  If false is returned, no range was set.
      64              : 
      65              : bool
      66    150499577 : irange_bitmask::range_from_mask (irange &r, tree type) const
      67              : {
      68    150499577 :   if (unknown_p ())
      69              :     return false;
      70              : 
      71    300675875 :   gcc_checking_assert ((value () & mask ()) == 0);
      72    150337284 :   unsigned popcount = wi::popcount (mask ());
      73              : 
      74              :   // For 0, 1 or 2 bits set, create a range with only the allowed values.
      75    150337284 :   if (popcount <= 2)
      76              :     {
      77              :       // VALUE is always a valid range.
      78     28746250 :       r.set (type, value (), value ());
      79              :       // If there are bits in mask, (VALUE | MASK) is also valid.
      80     28746207 :       if (popcount >= 1)
      81     12834555 :         r.union_ (int_range<1> (type, value () | mask (), value () | mask ()));
      82              :       // If there are 2 bits set, add the other 2 possible values.
      83     12834475 :       if (popcount == 2)
      84              :         {
      85              :           // Extract the two 1-bit masks into lb and ub.
      86      5395112 :           wide_int lb = mask () & -mask ();         // Lowest set bit.
      87      5395112 :           wide_int ub = mask () & (mask () - 1);    // The other bit.
      88      5395112 :           r.union_ (int_range<1> (type, value () | lb, value () | lb));
      89      5395112 :           r.union_ (int_range<1> (type, value () | ub, value () | ub));
      90      5395112 :         }
      91              :       return true;
      92              :     }
      93              : 
      94              :   // Otherwise, calculate the valid range allowed by the bitmask.
      95    121591077 :   int prec = TYPE_PRECISION (type);
      96    121592341 :   wide_int ub = mask () | value ();
      97    121591077 :   wide_int sign_bit = wi::one (prec) << (prec - 1);
      98    121591077 :   wide_int sign_mask = mask () & sign_bit;
      99    121591077 :   wide_int sign_value = value () & sign_bit;
     100              :   // Create a lower and upper bound.
     101              :   // If unsigned, or the sign is known to be positive, create [lb, ub]
     102    121591077 :   if (TYPE_SIGN (type) == UNSIGNED || (sign_mask == 0 && sign_value == 0))
     103    111739672 :     r.set (type, value (), mask () | value ());
     104              :   // If the sign bit is KNOWN to be 1, we have a completely negative range.
     105      9856285 :   else if (sign_mask == 0 && sign_value != 0)
     106      1024630 :     r.set (type, value (), value () | (mask () & ~sign_bit));
     107              :   else
     108              :     {
     109              :       // Otherwise there are 2 ranges, a negative and positive interval.
     110      8831685 :       wide_int neg_base = value () | sign_bit;
     111      8831724 :       wide_int pos_mask = mask () & ~sign_bit;
     112      8831685 :       r.set  (type, neg_base , neg_base | pos_mask);
     113      8831802 :       r.union_ (int_range<1> (type, value (), value () | pos_mask));
     114      8831724 :     }
     115              : 
     116              :   // If the mask doesn't have a trailing zero, there is nothing else to filter.
     117    121591077 :   int z = wi::ctz (mask ());
     118    121591077 :   if (z == 0)
     119              :     return true;
     120              : 
     121              :   // Remove the [0, X] values which the trailing-zero mask rules out.
     122              :   // For example, if z == 4, the mask is 0xFFF0, and the lowest 4 bits
     123              :   // define the range [0, 15]. Only (value & low_mask) is allowed.
     124     38729559 :   ub = (wi::one (prec) << z) - 1;  // Upper bound of range.
     125     38729261 :   int_range<4> mask_range (type, wi::zero (prec), ub);
     126              :   // Remove the valid value from the excluded range and form an anti-range.
     127     38729261 :   wide_int allow = value () & ub;
     128     38729261 :   mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
     129     38729261 :   bool res = mask_range.invert ();
     130     38729261 :   gcc_checking_assert (res);
     131     38729261 :   r.intersect (mask_range);
     132              : 
     133     38729261 :   if (TYPE_SIGN (type) == SIGNED)
     134              :     {
     135              :       // For signed negative values, find the lowest value with trailing zeros.
     136              :       // This forms a range such as [-512, -1] for z=9.
     137     15742928 :       wide_int lb = -(wi::one (prec) << z);
     138     15742928 :       int_range<4> mask_range (type, lb, wi::minus_one (prec));
     139              :       // Remove the one allowed value from that set.
     140     15742928 :       wide_int allow = value () | lb;
     141     15742928 :       mask_range.intersect (int_range<2> (type, allow, allow, VR_ANTI_RANGE));
     142     15742928 :       res = mask_range.invert ();
     143     15742928 :       gcc_checking_assert (res);
     144     15742928 :       r.intersect (mask_range);
     145     15743217 :     }
     146     38729261 :   return true;
     147    160324130 : }
     148              : 
     149              : 
     150              : void
     151        40783 : irange::accept (const vrange_visitor &v) const
     152              : {
     153        40783 :   v.visit (*this);
     154        40783 : }
     155              : 
     156              : void
     157        24145 : value_range::dump (FILE *out) const
     158              : {
     159        24145 :   if (m_vrange)
     160        24145 :     m_vrange->dump (out);
     161              :   else
     162            0 :     fprintf (out, "NULL");
     163        24145 : }
     164              : 
     165              : void
     166         1866 : value_range::print (pretty_printer *pp) const
     167              : {
     168         1866 :   if (m_vrange)
     169              :     {
     170         1866 :       vrange_printer vrange_pp (pp);
     171         1866 :       m_vrange->accept (vrange_pp);
     172              :     }
     173              :   else
     174            0 :     pp_string (pp, "NULL");
     175         1866 : }
     176              : 
     177              : DEBUG_FUNCTION void
     178            0 : debug (const value_range &r)
     179              : {
     180            0 :   r.dump (stderr);
     181            0 :   fprintf (stderr, "\n");
     182            0 : }
     183              : 
     184              : DEBUG_FUNCTION void
     185            0 : debug (const irange_bitmask &bm)
     186              : {
     187            0 :   bm.dump (stderr);
     188            0 :   fprintf (stderr, "\n");
     189            0 : }
     190              : 
     191              : // Definitions for unsupported_range.
     192              : 
     193              : void
     194          603 : unsupported_range::accept (const vrange_visitor &v) const
     195              : {
     196          603 :   v.visit (*this);
     197          603 : }
     198              : 
     199              : void
     200           37 : vrange::update_bitmask (const class irange_bitmask &)
     201              : {
     202           37 : }
     203              : 
     204              : irange_bitmask
     205            0 : vrange::get_bitmask () const
     206              : {
     207              :   // Return all unknown bits for the given precision.
     208            0 :   return irange_bitmask (TYPE_PRECISION (type ()));
     209              : }
     210              : 
     211              : bool
     212            0 : unsupported_range::contains_p (tree) const
     213              : {
     214            0 :   return varying_p ();
     215              : }
     216              : 
     217              : bool
     218      1317610 : unsupported_range::singleton_p (tree *) const
     219              : {
     220      1317610 :   return false;
     221              : }
     222              : 
     223              : void
     224            0 : unsupported_range::set (tree min, tree, value_range_kind)
     225              : {
     226            0 :   set_varying (TREE_TYPE (min));
     227            0 : }
     228              : 
     229              : tree
     230            0 : unsupported_range::type () const
     231              : {
     232            0 :   return void_type_node;
     233              : }
     234              : 
     235              : bool
     236     20937682 : unsupported_range::supports_type_p (const_tree) const
     237              : {
     238     20937682 :   return false;
     239              : }
     240              : 
     241              : void
     242    115055185 : unsupported_range::set_undefined ()
     243              : {
     244    115055185 :   m_kind = VR_UNDEFINED;
     245    115055185 : }
     246              : 
     247              : void
     248      3618236 : unsupported_range::set_varying (tree)
     249              : {
     250      3618236 :   m_kind = VR_VARYING;
     251      3618236 : }
     252              : 
     253              : bool
     254            0 : unsupported_range::union_ (const vrange &v)
     255              : {
     256            0 :   const unsupported_range &r = as_a <unsupported_range> (v);
     257              : 
     258            0 :   if (r.undefined_p () || varying_p ())
     259              :     return false;
     260            0 :   if (undefined_p () || r.varying_p ())
     261              :     {
     262            0 :       operator= (r);
     263            0 :       return true;
     264              :     }
     265            0 :   gcc_unreachable ();
     266              :   return false;
     267              : }
     268              : 
     269              : bool
     270            0 : unsupported_range::intersect (const vrange &v)
     271              : {
     272            0 :   const unsupported_range &r = as_a <unsupported_range> (v);
     273              : 
     274            0 :   if (undefined_p () || r.varying_p ())
     275              :     return false;
     276            0 :   if (r.undefined_p ())
     277              :     {
     278            0 :       set_undefined ();
     279            0 :       return true;
     280              :     }
     281            0 :   if (varying_p ())
     282              :     {
     283            0 :       operator= (r);
     284            0 :       return true;
     285              :     }
     286            0 :   gcc_unreachable ();
     287              :   return false;
     288              : }
     289              : 
     290              : bool
     291            0 : unsupported_range::zero_p () const
     292              : {
     293            0 :   return false;
     294              : }
     295              : 
     296              : bool
     297            0 : unsupported_range::contains_zero_p () const
     298              : {
     299            0 :   return varying_p ();
     300              : }
     301              : 
     302              : void
     303            0 : unsupported_range::set_nonzero (tree type)
     304              : {
     305            0 :   set_varying (type);
     306            0 : }
     307              : 
     308              : void
     309            0 : unsupported_range::set_zero (tree type)
     310              : {
     311            0 :   set_varying (type);
     312            0 : }
     313              : 
     314              : void
     315            0 : unsupported_range::set_nonnegative (tree type)
     316              : {
     317            0 :   set_varying (type);
     318            0 : }
     319              : 
     320              : bool
     321            0 : unsupported_range::fits_p (const vrange &) const
     322              : {
     323            0 :   return true;
     324              : }
     325              : 
     326              : unsupported_range &
     327       656269 : unsupported_range::operator= (const unsupported_range &r)
     328              : {
     329       656269 :   if (r.undefined_p ())
     330       656269 :     set_undefined ();
     331            0 :   else if (r.varying_p ())
     332            0 :     set_varying (void_type_node);
     333              :   else
     334            0 :     gcc_unreachable ();
     335       656269 :   return *this;
     336              : }
     337              : 
     338              : tree
     339            0 : unsupported_range::lbound () const
     340              : {
     341            0 :   return NULL;
     342              : }
     343              : 
     344              : tree
     345            0 : unsupported_range::ubound () const
     346              : {
     347            0 :   return NULL;
     348              : }
     349              : 
     350              : // Assignment operator for generic ranges.  Copying incompatible types
     351              : // is not allowed.
     352              : 
     353              : vrange &
     354     15371002 : vrange::operator= (const vrange &src)
     355              : {
     356     15371002 :   if (is_a <irange> (src))
     357     13679293 :     as_a <irange> (*this) = as_a <irange> (src);
     358      1691709 :   else if (is_a <prange> (src))
     359      1244656 :     as_a <prange> (*this) = as_a <prange> (src);
     360       447053 :   else if (is_a <frange> (src))
     361       447053 :     as_a <frange> (*this) = as_a <frange> (src);
     362              :   else
     363              :     {
     364            0 :       gcc_checking_assert (is_a <unsupported_range> (src));
     365            0 :       m_kind = src.m_kind;
     366              :     }
     367     15371002 :   return *this;
     368              : }
     369              : 
     370              : // Equality operator for generic ranges.
     371              : 
     372              : bool
     373     42241748 : vrange::operator== (const vrange &src) const
     374              : {
     375     42241748 :   if (is_a <irange> (src))
     376     35873350 :     return as_a <irange> (*this) == as_a <irange> (src);
     377      6368398 :   if (is_a <prange> (src))
     378      6309046 :     return as_a <prange> (*this) == as_a <prange> (src);
     379        59352 :   if (is_a <frange> (src))
     380        59352 :     return as_a <frange> (*this) == as_a <frange> (src);
     381            0 :   gcc_unreachable ();
     382              : }
     383              : 
     384              : // Wrapper for vrange_printer to dump a range to a file.
     385              : 
     386              : void
     387        38636 : vrange::dump (FILE *file) const
     388              : {
     389        38636 :   pretty_printer pp;
     390        38636 :   pp_needs_newline (&pp) = true;
     391        38636 :   pp.set_output_stream (file);
     392        38636 :   vrange_printer vrange_pp (&pp);
     393        38636 :   this->accept (vrange_pp);
     394        38636 :   pp_flush (&pp);
     395        38636 : }
     396              : 
     397              : void
     398            0 : irange_bitmask::dump (FILE *file) const
     399              : {
     400            0 :   char buf[WIDE_INT_PRINT_BUFFER_SIZE], *p;
     401            0 :   pretty_printer pp;
     402              : 
     403            0 :   pp_needs_newline (&pp) = true;
     404            0 :   pp.set_output_stream (file);
     405            0 :   pp_string (&pp, "MASK ");
     406            0 :   unsigned len_mask, len_val;
     407            0 :   if (print_hex_buf_size (m_mask, &len_mask)
     408            0 :       | print_hex_buf_size (m_value, &len_val))
     409            0 :     p = XALLOCAVEC (char, MAX (len_mask, len_val));
     410              :   else
     411              :     p = buf;
     412            0 :   print_hex (m_mask, p);
     413            0 :   pp_string (&pp, p);
     414            0 :   pp_string (&pp, " VALUE ");
     415            0 :   print_hex (m_value, p);
     416            0 :   pp_string (&pp, p);
     417            0 :   pp_flush (&pp);
     418            0 : }
     419              : 
     420              : namespace inchash
     421              : {
     422              : 
     423              : void
     424     28702650 : add_vrange (const vrange &v, inchash::hash &hstate,
     425              :              unsigned int)
     426              : {
     427     28702650 :   if (v.undefined_p ())
     428              :     {
     429            0 :       hstate.add_int (VR_UNDEFINED);
     430            0 :       return;
     431              :     }
     432              :   // Types are ignored throughout to inhibit two ranges being equal
     433              :   // but having different hash values.  This can happen when two
     434              :   // ranges are equal and their types are different (but
     435              :   // types_compatible_p is true).
     436     28702650 :   if (is_a <irange> (v))
     437              :     {
     438     12473743 :       const irange &r = as_a <irange> (v);
     439     12473743 :       if (r.varying_p ())
     440            0 :         hstate.add_int (VR_VARYING);
     441              :       else
     442     12473743 :         hstate.add_int (VR_RANGE);
     443     26561834 :       for (unsigned i = 0; i < r.num_pairs (); ++i)
     444              :         {
     445     14088091 :           hstate.add_wide_int (r.lower_bound (i));
     446     14088686 :           hstate.add_wide_int (r.upper_bound (i));
     447              :         }
     448     12473743 :       irange_bitmask bm = r.get_bitmask ();
     449     12473743 :       hstate.add_wide_int (bm.value ());
     450     12473743 :       hstate.add_wide_int (bm.mask ());
     451     12473743 :       return;
     452     12473743 :     }
     453     16228907 :   if (is_a <prange> (v))
     454              :     {
     455     16139489 :       const prange &r = as_a <prange> (v);
     456     16139489 :       if (r.varying_p ())
     457          519 :         hstate.add_int (VR_VARYING);
     458              :       else
     459              :         {
     460     16138970 :           hstate.add_int (VR_RANGE);
     461     16138970 :           hstate.add_wide_int (r.lower_bound ());
     462     16138970 :           hstate.add_wide_int (r.upper_bound ());
     463     16138970 :           irange_bitmask bm = r.get_bitmask ();
     464     16138970 :           hstate.add_wide_int (bm.value ());
     465     16138970 :           hstate.add_wide_int (bm.mask ());
     466     16138970 :           bool flag = false;
     467     16138970 :           tree tmp = r.addr_known ();
     468              :           if (tmp)
     469              :             flag = true;
     470              :           else
     471      2938603 :             tmp = r.addr_excluded ();
     472     16138970 :           hstate.add_ptr (tmp);
     473     16138970 :           hstate.add_flag (flag);
     474     16138970 :         }
     475              :       return;
     476              :     }
     477        89418 :   if (is_a <frange> (v))
     478              :     {
     479        89418 :       const frange &r = as_a <frange> (v);
     480        89418 :       if (r.known_isnan ())
     481          279 :         hstate.add_int (VR_NAN);
     482              :       else
     483              :         {
     484        89139 :           hstate.add_int (r.varying_p () ? VR_VARYING : VR_RANGE);
     485        89139 :           hstate.add_real_value (r.lower_bound ());
     486        89139 :           hstate.add_real_value (r.upper_bound ());
     487              :         }
     488        89418 :       nan_state nan = r.get_nan_state ();
     489        89418 :       hstate.add_int (nan.pos_p ());
     490        89418 :       hstate.add_int (nan.neg_p ());
     491        89418 :       return;
     492              :     }
     493            0 :   gcc_unreachable ();
     494              : }
     495              : 
     496              : } //namespace inchash
     497              : 
     498              : bool
     499     12143952 : irange::nonnegative_p () const
     500              : {
     501     12143952 :   return wi::ge_p (lower_bound (), 0, TYPE_SIGN (type ()));
     502              : }
     503              : 
     504              : bool
     505      6370583 : irange::nonpositive_p () const
     506              : {
     507      6370583 :   return wi::le_p (upper_bound (), 0, TYPE_SIGN (type ()));
     508              : }
     509              : 
     510              : bool
     511    837080064 : irange::supports_type_p (const_tree type) const
     512              : {
     513    837080064 :   return supports_p (type);
     514              : }
     515              : 
     516              : // Return TRUE if R fits in THIS.
     517              : 
     518              : bool
     519            0 : irange::fits_p (const vrange &r) const
     520              : {
     521            0 :   return m_max_ranges >= as_a <irange> (r).num_pairs ();
     522              : }
     523              : 
     524              : void
     525        43633 : irange::set_nonnegative (tree type)
     526              : {
     527        43633 :   set (type,
     528        87266 :        wi::zero (TYPE_PRECISION (type)),
     529        43633 :        wi::to_wide (TYPE_MAX_VALUE (type)));
     530        43633 : }
     531              : 
     532              : 
     533              : // Set the address info to EXPR if possible.  KNOWN_P is TRUE if this range
     534              : // is known to be EXPR, and FALSE if it is known to exclude EXPR.
     535              : 
     536              : void
     537     15430064 : prange::set_addr (tree expr, bool known_p)
     538              : {
     539     15430064 :   gcc_checking_assert (m_kind != VR_UNDEFINED);
     540     15430064 :   gcc_checking_assert (!expr || TREE_CODE (expr) != SSA_NAME);
     541              : 
     542     15430064 :   m_addr = NULL_TREE;
     543     15430064 :   m_known_p = false;
     544              : 
     545              :   // A zero range means no address info.
     546     15430064 :   if (zero_p ())
     547      3644395 :     return;
     548              : 
     549              :   // No address initially may make this VARYING.
     550     15430025 :   if (varying_compatible_p ())
     551      1406061 :     set_varying (type ());
     552              :   else
     553     14023964 :     m_kind = VR_RANGE;
     554              : 
     555     15430025 :   if (!expr)
     556              :     return;
     557              : 
     558     15430025 :   gcc_checking_assert (TREE_CODE (expr) == ADDR_EXPR);
     559              : 
     560              :   // Ensure only constants get through for now.
     561     15430025 :   if (!is_gimple_min_invariant (expr))
     562              :     return;
     563              : 
     564     11785669 :   aff_tree offset;
     565     11785669 :   poly_widest_int size;
     566     11785669 :   tree obj = TREE_OPERAND (expr, 0);
     567     11785669 :   tree base = get_inner_reference_aff (obj, &offset, &size);
     568              : 
     569     11785669 :   if (!base)
     570            0 :     return;
     571     11785669 :   if (!offset.offset.is_constant ())
     572              :     return;
     573     11785669 :   if (!size.is_constant ())
     574              :     return;
     575              : 
     576     11785669 :   m_addr = expr;
     577     11785669 :   m_known_p = known_p;
     578     11785669 :   m_kind = VR_RANGE;
     579     11785669 : }
     580              : 
     581              : 
     582              : // If addr is present and is an address that is local to its function,
     583              : // clear it and return TRUE.  otherwise do nothing and retiurn false.
     584              : 
     585              : bool
     586     10147266 : prange::clear_function_local_addr ()
     587              : {
     588     10147266 :   if (!m_addr)
     589              :     return false;
     590              : 
     591              :   /* is_gimple_ip_invariant () accepts the address of a LABEL_DECL, but
     592              :      inlining and cloning could remap it, so remove it as well.  */
     593      2054786 :   if (!is_gimple_ip_invariant (m_addr)
     594      2054786 :       || TREE_CODE (TREE_OPERAND (m_addr, 0)) == LABEL_DECL)
     595              :     {
     596      1051464 :       set_addr_unknown ();
     597      1051464 :       return true;
     598              :     }
     599              :   return false;
     600              : }
     601              : 
     602              : // Return object/allocation the pointer refers into, otherwise NULL_TREE.
     603              : 
     604              : tree
     605          258 : prange::addr_base () const
     606              : {
     607          258 :   if (!m_addr || !m_known_p)
     608              :     return NULL_TREE;
     609              : 
     610          258 :   aff_tree off;
     611          258 :   poly_widest_int sz;
     612              : 
     613          258 :   gcc_checking_assert (m_addr);
     614          258 :   return get_inner_reference_aff (m_addr, &off, &sz);
     615          258 : }
     616              : 
     617              : // Return possible byte offset range from BASE.
     618              : 
     619              : void
     620          258 : prange::addr_offset (irange &r) const
     621              : {
     622          258 :   aff_tree off;
     623          258 :   poly_widest_int sz;
     624              : 
     625          258 :   gcc_checking_assert (m_addr);
     626          258 :   gcc_checking_assert (m_known_p);
     627              : 
     628          258 :   get_inner_reference_aff (m_addr, &off, &sz);
     629          258 :   gcc_checking_assert (off.offset.is_constant ());
     630              : 
     631          258 :   widest_int w = off.offset.coeffs[0];
     632          258 :   wide_int w2 = wi::to_wide (wide_int_to_tree (sizetype, w));
     633          258 :   r.set (sizetype, w2, w2);
     634          258 : }
     635              : 
     636              : // Return possible size range of the referenced object.
     637              : 
     638              : void
     639          258 : prange::addr_size (irange &r) const
     640              : {
     641          258 :   aff_tree off;
     642          258 :   poly_widest_int sz;
     643              : 
     644          258 :   gcc_checking_assert (m_addr);
     645          258 :   gcc_checking_assert (m_known_p);
     646              : 
     647          258 :   get_inner_reference_aff (m_addr, &off, &sz);
     648          258 :   gcc_checking_assert (sz.is_constant ());
     649              : 
     650          258 :   widest_int w = sz.coeffs[0];
     651          258 :   wide_int w2 = wi::to_wide (wide_int_to_tree (sizetype, w));
     652          258 :   r.set (sizetype, w2, w2);
     653          258 : }
     654              : // Prange implementation.
     655              : 
     656              : void
     657         1935 : prange::accept (const vrange_visitor &v) const
     658              : {
     659         1935 :   v.visit (*this);
     660         1935 : }
     661              : 
     662              : void
     663            0 : prange::set_nonnegative (tree type)
     664              : {
     665            0 :   set (type,
     666            0 :        wi::zero (TYPE_PRECISION (type)),
     667            0 :        wi::max_value (TYPE_PRECISION (type), UNSIGNED));
     668            0 : }
     669              : 
     670              : void
     671     14370737 : prange::set (tree min, tree max, value_range_kind kind)
     672              : {
     673     14370737 :   return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
     674              : }
     675              : 
     676              : void
     677     41986679 : prange::set (tree type, const wide_int &min, const wide_int &max,
     678              :              value_range_kind kind)
     679              : {
     680     41986679 :   if (kind == VR_UNDEFINED)
     681              :     {
     682            0 :       set_undefined ();
     683            0 :       return;
     684              :     }
     685     41986679 :   if (kind == VR_VARYING)
     686              :     {
     687            0 :       set_varying (type);
     688            0 :       return;
     689              :     }
     690     41986679 :   if (kind == VR_ANTI_RANGE)
     691              :     {
     692            0 :       gcc_checking_assert (min == 0 && max == 0);
     693            0 :       set_nonzero (type);
     694            0 :       return;
     695              :     }
     696     41986679 :   m_type = type;
     697     41986679 :   m_min = min;
     698     41986679 :   m_max = max;
     699              : 
     700     41986679 :   if (m_min == 0 && m_max == -1)
     701              :     {
     702      5212873 :       m_kind = VR_VARYING;
     703      5212873 :       m_bitmask.set_unknown (TYPE_PRECISION (type));
     704      5212873 :       set_addr_unknown ();
     705      5212873 :       if (flag_checking)
     706      5212873 :         verify_range ();
     707              :       return;
     708              :     }
     709              : 
     710     36773806 :   m_kind = VR_RANGE;
     711     36773806 :   m_bitmask = irange_bitmask (type, min, max);
     712     36773806 :   set_addr_unknown ();
     713     36773806 :   if (flag_checking)
     714     36773794 :     verify_range ();
     715              : }
     716              : 
     717              : bool
     718     30844148 : prange::contains_p (const wide_int &w) const
     719              : {
     720     30844148 :   if (undefined_p ())
     721              :     return false;
     722              : 
     723     30844148 :   if (varying_p ())
     724              :     return true;
     725              : 
     726     19552872 :   return (wi::le_p (lower_bound (), w, UNSIGNED)
     727     10283725 :           && wi::ge_p (upper_bound (), w, UNSIGNED));
     728              : }
     729              : 
     730              : bool
     731    258617722 : prange::singleton_p (tree *result) const
     732              : {
     733    359823615 :   if (m_kind == VR_RANGE && lower_bound () == upper_bound ())
     734              :     {
     735       345014 :       if (result)
     736       152528 :         *result = wide_int_to_tree (type (), m_min);
     737              :       return true;
     738              :     }
     739              :   return false;
     740              : }
     741              : 
     742              : tree
     743      4928061 : prange::lbound () const
     744              : {
     745      4928061 :   return wide_int_to_tree (type (), m_min);
     746              : }
     747              : 
     748              : tree
     749       811683 : prange::ubound () const
     750              : {
     751       811683 :   return wide_int_to_tree (type (), m_max);
     752              : }
     753              : 
     754              : bool
     755     16593686 : prange::union_ (const vrange &v)
     756              : {
     757     16593686 :   const prange &r = as_a <prange> (v);
     758              : 
     759     16593686 :   if (r.undefined_p ())
     760              :     return false;
     761     16449138 :   if (undefined_p ())
     762              :     {
     763      8235786 :       *this = r;
     764      8235786 :       if (flag_checking)
     765      8235786 :         verify_range ();
     766              :       return true;
     767              :     }
     768      8213352 :   if (varying_p ())
     769              :     return false;
     770      4911069 :   if (r.varying_p ())
     771              :     {
     772       926005 :       set_varying (type ());
     773       926005 :       return true;
     774              :     }
     775              : 
     776      3985064 :   wide_int new_lb = wi::min (r.lower_bound (), lower_bound (), UNSIGNED);
     777      3985064 :   wide_int new_ub = wi::max (r.upper_bound (), upper_bound (), UNSIGNED);
     778      3985064 :   prange new_range (type (), new_lb, new_ub);
     779      3985064 :   new_range.m_bitmask.union_ (m_bitmask);
     780      3985064 :   new_range.m_bitmask.union_ (r.m_bitmask);
     781              : 
     782              :   // Keep it simple, either both name the same address or both do not,
     783              :   // or we drop the address info.
     784      3985064 :   if (addr_equal_p (r))
     785      3327825 :     new_range.set_addr (*this);
     786              : 
     787      3985064 :   if (new_range.varying_compatible_p ())
     788              :     {
     789       504224 :       set_varying (type ());
     790       504224 :       return true;
     791              :     }
     792      3480840 :   if (flag_checking)
     793      3480840 :     new_range.verify_range ();
     794      3480840 :   if (new_range == *this)
     795              :     return false;
     796       383765 :   *this = new_range;
     797       383765 :   return true;
     798      3985064 : }
     799              : 
     800              : bool
     801    204867737 : prange::intersect (const vrange &v)
     802              : {
     803    204867737 :   const prange &r = as_a <prange> (v);
     804    204867737 :   gcc_checking_assert (undefined_p () || r.undefined_p ()
     805              :                        || range_compatible_p (type (), r.type ()));
     806              : 
     807    204867737 :   if (undefined_p ())
     808              :     return false;
     809    204747486 :   if (r.undefined_p ())
     810              :     {
     811        43700 :       set_undefined ();
     812        43700 :       return true;
     813              :     }
     814    204703786 :   if (r.varying_p ())
     815              :     return false;
     816    126106693 :   if (varying_p ())
     817              :     {
     818     47678437 :       *this = r;
     819     47678437 :       return true;
     820              :     }
     821              : 
     822              :   // If one knows the address and the other excludes it, the result is
     823              :   // undefined.
     824     78428256 :   if (addr_inverted_p (r))
     825              :     {
     826          654 :       set_undefined ();
     827          654 :       return true;
     828              :     }
     829              : 
     830     78427602 :   prange save = *this;
     831     78427602 :   m_min = wi::max (r.lower_bound (), lower_bound (), UNSIGNED);
     832     78427602 :   m_max = wi::min (r.upper_bound (), upper_bound (), UNSIGNED);
     833     78427602 :   if (wi::gt_p (m_min, m_max, UNSIGNED))
     834              :     {
     835       385381 :       set_undefined ();
     836       385381 :       return true;
     837              :     }
     838              : 
     839              :   // Intersect all bitmasks: the old one, the new one, and the other operand's.
     840     78042221 :   irange_bitmask new_bitmask (m_type, m_min, m_max);
     841     78042221 :   if (!m_bitmask.intersect (new_bitmask))
     842           12 :     set_undefined ();
     843     78042209 :   else if (!m_bitmask.intersect (r.m_bitmask))
     844           63 :     set_undefined ();
     845              :   // If only one has an address, that is the intersection.
     846     78042146 :   else if (addr_unknown_p () && !r.addr_unknown_p ())
     847       952293 :     set_addr (r);
     848     77089853 :   else if (!addr_unknown_p () && !r.addr_unknown_p ())
     849              :     {
     850              :       // If both have an address, we want to be careful.  Without aliasing
     851              :       // 2 different values can name the same address, so UNDEFINED is
     852              :       // not appropriate, but we want to keep the rule that intersection
     853              :       // never becomes larger.
     854              :       // If the other operand knows an address and this one only excludes
     855              :       // one, use the known one.  Otherwise leave the range as is.
     856      1286132 :       if (addr_excluded () && r.addr_known ())
     857       259883 :         set_addr (r);
     858              :     }
     859              : 
     860              :   //  If this evolves to zero, clear all address info.
     861     78042221 :   if (zero_p () && !addr_unknown_p ())
     862        41354 :     set_addr_unknown ();
     863              : 
     864     78042221 :   if (varying_compatible_p ())
     865              :     {
     866            0 :       set_varying (type ());
     867            0 :       return true;
     868              :     }
     869              : 
     870     78042221 :   if (flag_checking)
     871     78042095 :     verify_range ();
     872     78042221 :   if (*this == save)
     873     73183165 :     return false;
     874              :   return true;
     875     78427602 : }
     876              : 
     877              : prange &
     878    215233018 : prange::operator= (const prange &src)
     879              : {
     880    215233018 :   m_type = src.m_type;
     881    215233018 :   m_kind = src.m_kind;
     882    215233018 :   m_min = src.m_min;
     883    215233018 :   m_max = src.m_max;
     884    215233018 :   m_bitmask = src.m_bitmask;
     885    215233018 :   set_addr (src);
     886    215233018 :   if (flag_checking)
     887    215232844 :     verify_range ();
     888    215233018 :   return *this;
     889              : }
     890              : 
     891              : bool
     892     87832111 : prange::operator== (const prange &src) const
     893              : {
     894     87832111 :   if (m_kind == src.m_kind)
     895              :     {
     896     87274401 :       if (undefined_p ())
     897              :         return true;
     898              : 
     899     87266267 :       if (varying_p ())
     900       877746 :         return types_compatible_p (type (), src.type ());
     901              : 
     902     86388521 :       if (!addr_equal_p (src))
     903              :         return false;
     904              : 
     905    167313381 :       return (m_min == src.m_min && m_max == src.m_max
     906    166596596 :               && m_bitmask == src.m_bitmask);
     907              :     }
     908              :   return false;
     909              : }
     910              : 
     911              : 
     912              : // Return the inverse of a range.  Return false if thre is no invert
     913              : // calculatable.
     914              : 
     915              : bool
     916      2775444 : prange::invert ()
     917              : {
     918      2775444 :   if (undefined_p () || varying_p ())
     919              :     return false;
     920              : 
     921              :   // Invert the points_to object. If that worked, this is done.
     922      2775444 :   if (addr_invert ())
     923            0 :     return true;
     924              :   else
     925      2775444 :     set_addr_unknown ();
     926              : 
     927      2775444 :   wide_int new_lb, new_ub;
     928      2775444 :   unsigned prec = TYPE_PRECISION (type ());
     929      2775444 :   wide_int type_min = wi::zero (prec);
     930      2775444 :   wide_int type_max = wi::max_value (prec, UNSIGNED);
     931      2775444 :   wi::overflow_type ovf;
     932              : 
     933      2775444 :   if (lower_bound () == type_min)
     934              :     {
     935      2768043 :       new_lb = wi::add (upper_bound (), 1, UNSIGNED, &ovf);
     936      2768043 :       if (ovf)
     937            0 :         new_lb = type_min;
     938      2768043 :       new_ub = type_max;
     939      2768043 :       set (type (), new_lb, new_ub);
     940              :     }
     941         7401 :   else if (upper_bound () == type_max)
     942              :     {
     943         3057 :       wi::overflow_type ovf;
     944         3057 :       new_lb = type_min;
     945         3057 :       new_ub = wi::sub (lower_bound (), 1, UNSIGNED, &ovf);
     946         3057 :       if (ovf)
     947            0 :         new_ub = type_max;
     948         3057 :       set (type (), new_lb, new_ub);
     949              :     }
     950              :   else
     951         4344 :     set_varying (type ());
     952      2775444 :   return true;
     953      2775444 : }
     954              : 
     955              : void
     956   1658615216 : prange::verify_range () const
     957              : {
     958   1658615216 :   gcc_checking_assert (m_discriminator == VR_PRANGE);
     959              : 
     960   1658615216 :   if (m_kind == VR_UNDEFINED)
     961              :     {
     962        66900 :       gcc_checking_assert (addr_unknown_p ());
     963              :       return;
     964              :     }
     965              : 
     966   1658548316 :   gcc_checking_assert (supports_p (type ()));
     967              : 
     968   1658548316 :   if (m_kind == VR_VARYING)
     969              :     {
     970    716245312 :       gcc_checking_assert (varying_compatible_p ());
     971              :       return;
     972              :     }
     973    942303004 :   gcc_checking_assert (!varying_compatible_p ());
     974    942303004 :   gcc_checking_assert (m_kind == VR_RANGE);
     975    942303004 :   if (!addr_unknown_p ())
     976              :     {
     977     32702750 :       gcc_checking_assert (!varying_p ());
     978     32702750 :       gcc_checking_assert (!undefined_p ());
     979     32702750 :       gcc_checking_assert (!zero_p ());
     980              :     }
     981              : }
     982              : 
     983              : void
     984     31211999 : prange::update_bitmask (const irange_bitmask &bm)
     985              : {
     986     31211999 :   gcc_checking_assert (!undefined_p ());
     987              : 
     988              :   // If all the bits are known, this is a singleton.
     989     31211999 :   if (bm.mask () == 0)
     990              :     {
     991       187984 :       set (type (), bm.value (), bm.value ());
     992       187984 :       return;
     993              :     }
     994              : 
     995              :   // Drop VARYINGs with known bits to a plain range.
     996     39882614 :   if (m_kind == VR_VARYING && !bm.unknown_p ())
     997      1963984 :     m_kind = VR_RANGE;
     998              : 
     999     31024015 :   m_bitmask = bm;
    1000     31024015 :   if (varying_compatible_p ())
    1001      6894615 :     m_kind = VR_VARYING;
    1002              : 
    1003     31024015 :   if (flag_checking)
    1004     31024015 :     verify_range ();
    1005              : }
    1006              : 
    1007              : 
    1008              : // Frange implementation.
    1009              : 
    1010              : void
    1011          259 : frange::accept (const vrange_visitor &v) const
    1012              : {
    1013          259 :   v.visit (*this);
    1014          259 : }
    1015              : 
    1016              : bool
    1017            0 : frange::fits_p (const vrange &) const
    1018              : {
    1019            0 :   return true;
    1020              : }
    1021              : 
    1022              : // Compare two range endpoints.
    1023              : //
    1024              : // In IEEE -0.0 and +0.0 equal for comparison purposes, but as endpoints they
    1025              : // are distinct.  Order -0.0 strictly below +0.0 and use this rather than
    1026              : // real_less/real_compare, and the signed zeros stop needing a special case.
    1027              : 
    1028              : static int
    1029    128443174 : frange_cmp (const REAL_VALUE_TYPE &a, const REAL_VALUE_TYPE &b)
    1030              : {
    1031    128443174 :   gcc_checking_assert (!real_isnan (&a) && !real_isnan (&b));
    1032              : 
    1033    128443174 :   if (real_less (&a, &b))
    1034              :     return -1;
    1035     54953294 :   if (real_less (&b, &a))
    1036              :     return 1;
    1037     25872442 :   if (real_iszero (&a) && real_iszero (&b))
    1038              :     {
    1039      5544752 :       bool nega = real_isneg (&a);
    1040      5544752 :       bool negb = real_isneg (&b);
    1041      5544752 :       if (nega && !negb)
    1042              :         return -1;
    1043      4187237 :       if (!nega && negb)
    1044       306749 :         return 1;
    1045              :     }
    1046              :   return 0;
    1047              : }
    1048              : 
    1049              : static inline const REAL_VALUE_TYPE &
    1050      9358444 : frange_min (const REAL_VALUE_TYPE &a, const REAL_VALUE_TYPE &b)
    1051              : {
    1052      9358444 :   return frange_cmp (a, b) <= 0 ? a : b;
    1053              : }
    1054              : 
    1055              : static inline const REAL_VALUE_TYPE &
    1056      9358444 : frange_max (const REAL_VALUE_TYPE &a, const REAL_VALUE_TYPE &b)
    1057              : {
    1058      9358444 :   return frange_cmp (a, b) >= 0 ? a : b;
    1059              : }
    1060              : 
    1061              : // Return TRUE if [..., A_MAX] and [B_MIN, ...] can be fused into one interval,
    1062              : // either because they overlap or because no representable value exists between
    1063              : // them.  The latter is how -0.0 and +0.0 abut: there is nothing in between, so
    1064              : // [x, -0.0] U [+0.0, y] is really [x, y].
    1065              : 
    1066              : static bool
    1067     10749229 : frange_fusible_p (machine_mode mode, const REAL_VALUE_TYPE &a_max,
    1068              :                   const REAL_VALUE_TYPE &b_min)
    1069              : {
    1070     10749229 :   if (frange_cmp (b_min, a_max) <= 0)
    1071              :     return true;
    1072      9897587 :   REAL_VALUE_TYPE next = a_max;
    1073      9897587 :   frange_nextafter (mode, next, dconstinf);
    1074      9897587 :   return frange_cmp (b_min, next) <= 0;
    1075              : }
    1076              : 
    1077              : // Flush denormal endpoints to the appropriate 0.0.
    1078              : 
    1079              : void
    1080      6605514 : frange::flush_denormals_to_zero ()
    1081              : {
    1082      6605514 :   if (undefined_p () || known_isnan ())
    1083            0 :     return;
    1084              : 
    1085      6605514 :   machine_mode mode = TYPE_MODE (type ());
    1086      6605514 :   frange_pair pairs[MAX_PAIRS];
    1087      6605514 :   unsigned n = m_num_ranges;
    1088              : 
    1089              :   // Flush a denormal endpoint to a zero of the same sign: a +denormal lower
    1090              :   // bound to +0.0, and a -denormal upper bound to -0.0.  Then set_pairs, via
    1091              :   // canonicalize_zeros, rewrites the sign to whatever the flags make
    1092              :   // canonical.  For example, under !HONOR_SIGNED_ZEROS (-fno-signed-zeros) a
    1093              :   // range reaching zero must hold both signs of it, so:
    1094              :   //
    1095              :   //     [ +DENORMAL, 5.0 ]  flushes to  [ -0.0, 5.0 ]
    1096              :   //
    1097              :   // keeping contains_p (-0.0) true; under HONOR_SIGNED_ZEROS the sign stands
    1098              :   // and it stays [ +0.0, 5.0 ].
    1099     13293913 :   for (unsigned i = 0; i < n; ++i)
    1100              :     {
    1101      6688399 :       pairs[i] = m_pairs[i];
    1102      6688399 :       if (real_isdenormal (&pairs[i].max, mode) && real_isneg (&pairs[i].max))
    1103         4446 :         pairs[i].max = dconstm0;
    1104      6688399 :       if (real_isdenormal (&pairs[i].min, mode) && !real_isneg (&pairs[i].min))
    1105         8247 :         pairs[i].min = dconst0;
    1106              :     }
    1107              : 
    1108      6605514 :   set_pairs (pairs, n);
    1109              : }
    1110              : 
    1111              : // Canonicalize the signed zeros of a sub-range according with what the target
    1112              : // and flags want:
    1113              : //
    1114              : //   !MODE_HAS_SIGNED_ZEROS: the mode has no signed zero, so any zero is +0.0.
    1115              : //
    1116              : //   !HONOR_SIGNED_ZEROS: the two zeros are one value, so widen the range to
    1117              : //   include both signs of it.
    1118              : //
    1119              : //   Otherwise the sign is a real distinction, and we keep it.
    1120              : 
    1121              : void
    1122     54185735 : frange::canonicalize_zeros (frange_pair &p)
    1123              : {
    1124    216742940 :   if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type)))
    1125              :     {
    1126            0 :       if (real_iszero (&p.min, 1))
    1127            0 :         p.min.sign = 0;
    1128            0 :       if (real_iszero (&p.max, 1))
    1129            0 :         p.max.sign = 0;
    1130              :     }
    1131     54185735 :   else if (!HONOR_SIGNED_ZEROS (m_type))
    1132              :     {
    1133      1439427 :       if (real_iszero (&p.max, 1))
    1134           47 :         p.max.sign = 0;
    1135      1439427 :       if (real_iszero (&p.min, 0))
    1136        29496 :         p.min.sign = 1;
    1137              :     }
    1138     54185735 : }
    1139              : 
    1140              : // Sort, fuse and install the N intervals in PAIRS as this range's sub-ranges.
    1141              : //
    1142              : // Fusing merges intervals that overlap or abut.  If more than MAX_PAIRS still
    1143              : // survive, the last slot swallows the surplus.
    1144              : 
    1145              : void
    1146     17433871 : frange::set_pairs (frange_pair *pairs, unsigned n)
    1147              : {
    1148     17433871 :   gcc_checking_assert (n > 0);
    1149     17433871 :   machine_mode mode = TYPE_MODE (m_type);
    1150              : 
    1151              :   // Sort by lower bound.  N is tiny (at most 2 * MAX_PAIRS).
    1152     21998891 :   for (unsigned i = 0; i + 1 < n; ++i)
    1153      9553838 :     for (unsigned j = i + 1; j < n; ++j)
    1154      4988818 :       if (frange_cmp (pairs[j].min, pairs[i].min) < 0)
    1155       825654 :         std::swap (pairs[i], pairs[j]);
    1156              : 
    1157              :   // Fuse overlapping and abutting intervals.
    1158              :   unsigned k = 0;
    1159     21998891 :   for (unsigned i = 1; i < n; ++i)
    1160              :     {
    1161      4565020 :       if (frange_fusible_p (mode, pairs[k].max, pairs[i].min))
    1162              :         {
    1163      1247915 :           if (frange_cmp (pairs[i].max, pairs[k].max) > 0)
    1164       571731 :             pairs[k].max = pairs[i].max;
    1165              :         }
    1166              :       else
    1167      3317105 :         pairs[++k] = pairs[i];
    1168              :     }
    1169     17433871 :   n = k + 1;
    1170              : 
    1171              :   // Only MAX_PAIRS fit.  Like irange, keep the first pieces and let the last
    1172              :   // slot swallow the rest.
    1173     17433871 :   if (n > MAX_PAIRS)
    1174              :     {
    1175        94650 :       pairs[MAX_PAIRS - 1].max = pairs[n - 1].max;
    1176        94650 :       n = MAX_PAIRS;
    1177              :     }
    1178              : 
    1179     17433871 :   m_kind = VR_RANGE;
    1180     17433871 :   m_num_ranges = n;
    1181     38090101 :   for (unsigned i = 0; i < n; ++i)
    1182              :     {
    1183     20656230 :       m_pairs[i] = pairs[i];
    1184     20656230 :       canonicalize_zeros (m_pairs[i]);
    1185              :     }
    1186              : 
    1187     17433871 :   normalize_kind ();
    1188     17433871 :   if (flag_checking)
    1189     17433871 :     verify_range ();
    1190     17433871 : }
    1191              : 
    1192              : // Set the range to everything except the closed interval [MIN, MAX], which
    1193              : // takes two sub-ranges:
    1194              : //
    1195              : //      [-INF, prev (MIN)] U [next (MAX), +INF]
    1196              : //
    1197              : // Either half falls away when the excluded interval reaches the edge of the
    1198              : // domain, and if it covers the entire domain.
    1199              : 
    1200              : void
    1201        86045 : frange::set_excluding (tree type, const REAL_VALUE_TYPE &min,
    1202              :                        const REAL_VALUE_TYPE &max, const nan_state &nan)
    1203              : {
    1204        86045 :   gcc_checking_assert (frange_cmp (min, max) <= 0);
    1205              : 
    1206        86045 :   machine_mode mode = TYPE_MODE (type);
    1207        86045 :   REAL_VALUE_TYPE dom_min = frange_val_min (type);
    1208        86045 :   REAL_VALUE_TYPE dom_max = frange_val_max (type);
    1209        86045 :   frange_pair pairs[MAX_PAIRS];
    1210        86045 :   unsigned n = 0;
    1211              : 
    1212              :   // PREV is the largest value below MIN, so DOM_MIN <= PREV whenever there is
    1213              :   // anything below MIN at all.  Likewise for NEXT above MAX.
    1214        86045 :   if (frange_cmp (dom_min, min) < 0)
    1215              :     {
    1216        85376 :       REAL_VALUE_TYPE prev = min;
    1217        85376 :       frange_nextafter (mode, prev, dconstninf);
    1218        85376 :       pairs[n++] = { dom_min, prev };
    1219              :     }
    1220        86045 :   if (frange_cmp (max, dom_max) < 0)
    1221              :     {
    1222        83730 :       REAL_VALUE_TYPE next = max;
    1223        83730 :       frange_nextafter (mode, next, dconstinf);
    1224        83730 :       pairs[n++] = { next, dom_max };
    1225              :     }
    1226              : 
    1227              :   // The excluded interval covered the entire domain.
    1228        86045 :   if (n == 0)
    1229              :     {
    1230            0 :       if (HONOR_NANS (type) && (nan.pos_p () || nan.neg_p ()))
    1231            0 :         set_nan (type, nan);
    1232              :       else
    1233            0 :         set_undefined ();
    1234            0 :       return;
    1235              :     }
    1236              : 
    1237        86045 :   set (type, pairs[0].min, pairs[0].max, nan);
    1238        86045 :   if (n == 2)
    1239              :     {
    1240        83061 :       frange tmp;
    1241        83061 :       tmp.set (type, pairs[1].min, pairs[1].max, nan);
    1242        83061 :       union_ (tmp);
    1243        83061 :     }
    1244              : }
    1245              : 
    1246              : // Setter for franges.
    1247              : 
    1248              : void
    1249     33615550 : frange::set (tree type,
    1250              :              const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
    1251              :              const nan_state &nan, value_range_kind kind)
    1252              : {
    1253              :   // VARYING and UNDEFINED go through set_varying() and set_undefined()
    1254              :   // respectively, like we do for irange.
    1255     33615550 :   gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
    1256     33615550 :   gcc_checking_assert (!real_isnan (&min) && !real_isnan (&max));
    1257              : 
    1258     33615550 :   if (kind == VR_ANTI_RANGE)
    1259              :     {
    1260        86045 :       set_excluding (type, min, max, nan);
    1261        86045 :       return;
    1262              :     }
    1263              : 
    1264     33529505 :   m_kind = kind;
    1265     33529505 :   m_type = type;
    1266     33529505 :   m_num_ranges = 1;
    1267     33529505 :   m_pairs[0].min = min;
    1268     33529505 :   m_pairs[0].max = max;
    1269     33529505 :   if (HONOR_NANS (m_type))
    1270              :     {
    1271     32617736 :       m_pos_nan = nan.pos_p ();
    1272     32617736 :       m_neg_nan = nan.neg_p ();
    1273              :     }
    1274              :   else
    1275              :     {
    1276       911769 :       m_pos_nan = false;
    1277       911769 :       m_neg_nan = false;
    1278              :     }
    1279              : 
    1280     33529505 :   canonicalize_zeros (m_pairs[0]);
    1281              : 
    1282              :   // For -ffinite-math-only we can drop ranges outside the
    1283              :   // representable numbers to min/max for the type.
    1284     33529505 :   if (!HONOR_INFINITIES (m_type))
    1285              :     {
    1286       911769 :       REAL_VALUE_TYPE min_repr = frange_val_min (m_type);
    1287       911769 :       REAL_VALUE_TYPE max_repr = frange_val_max (m_type);
    1288       911769 :       if (real_less (&m_pairs[0].min, &min_repr))
    1289       298744 :         m_pairs[0].min = min_repr;
    1290       613025 :       else if (real_less (&max_repr, &m_pairs[0].min))
    1291            2 :         m_pairs[0].min = max_repr;
    1292       911769 :       if (real_less (&max_repr, &m_pairs[0].max))
    1293       302336 :         m_pairs[0].max = max_repr;
    1294       609433 :       else if (real_less (&m_pairs[0].max, &min_repr))
    1295            0 :         m_pairs[0].max = min_repr;
    1296              :     }
    1297              : 
    1298              :   // Check for swapped ranges.
    1299     33529505 :   gcc_checking_assert (real_compare (LE_EXPR, &min, &max));
    1300              : 
    1301     33529505 :   normalize_kind ();
    1302              : }
    1303              : 
    1304              : // Setter for an frange defaulting the NAN possibility to +-NAN when
    1305              : // HONOR_NANS.
    1306              : 
    1307              : void
    1308     20676332 : frange::set (tree type,
    1309              :              const REAL_VALUE_TYPE &min, const REAL_VALUE_TYPE &max,
    1310              :              value_range_kind kind)
    1311              : {
    1312     20676332 :   set (type, min, max, nan_state (true), kind);
    1313     20676332 : }
    1314              : 
    1315              : void
    1316           61 : frange::set (tree min, tree max, value_range_kind kind)
    1317              : {
    1318          122 :   set (TREE_TYPE (min),
    1319           61 :        *TREE_REAL_CST_PTR (min), *TREE_REAL_CST_PTR (max), kind);
    1320           61 : }
    1321              : 
    1322              : // Normalize range to VARYING or UNDEFINED, or vice versa.  Return
    1323              : // TRUE if anything changed.
    1324              : //
    1325              : // A range with no known properties can be dropped to VARYING.
    1326              : // Similarly, a VARYING with any properties should be dropped to a
    1327              : // VR_RANGE.  Normalizing ranges upon changing them ensures there is
    1328              : // only one representation for a given range.
    1329              : 
    1330              : bool
    1331     71587023 : frange::normalize_kind ()
    1332              : {
    1333     71587023 :   if (m_kind == VR_RANGE
    1334     66398191 :       && m_num_ranges == 1
    1335     61915341 :       && frange_val_is_min (m_pairs[0].min, m_type)
    1336     88348658 :       && frange_val_is_max (m_pairs[0].max, m_type))
    1337              :     {
    1338     12780033 :       if (!HONOR_NANS (m_type) || (m_pos_nan && m_neg_nan))
    1339              :         {
    1340     11256484 :           set_varying (m_type);
    1341     11256484 :           return true;
    1342              :         }
    1343              :     }
    1344     58806990 :   else if (m_kind == VR_VARYING)
    1345              :     {
    1346      5188613 :       if (HONOR_NANS (m_type) && (!m_pos_nan || !m_neg_nan))
    1347              :         {
    1348      2093399 :           m_kind = VR_RANGE;
    1349      2093399 :           m_num_ranges = 1;
    1350      2093399 :           m_pairs[0].min = frange_val_min (m_type);
    1351      2093399 :           m_pairs[0].max = frange_val_max (m_type);
    1352      2093399 :           if (flag_checking)
    1353      2093399 :             verify_range ();
    1354              :           return true;
    1355              :         }
    1356              :     }
    1357     53618377 :   else if (m_kind == VR_NAN && !m_pos_nan && !m_neg_nan)
    1358            4 :     set_undefined ();
    1359              :   return false;
    1360              : }
    1361              : 
    1362              : // Union two ranges when one is known to be a NAN.
    1363              : 
    1364              : bool
    1365       218328 : frange::union_nans (const frange &r)
    1366              : {
    1367       218328 :   gcc_checking_assert (known_isnan () || r.known_isnan ());
    1368              : 
    1369       218328 :   bool changed = false;
    1370       218328 :   if (known_isnan () && m_kind != r.m_kind)
    1371              :     {
    1372        42168 :       m_kind = r.m_kind;
    1373        42168 :       m_num_ranges = r.m_num_ranges;
    1374        85282 :       for (unsigned i = 0; i < r.m_num_ranges; ++i)
    1375        43114 :         m_pairs[i] = r.m_pairs[i];
    1376              :       changed = true;
    1377              :     }
    1378       218328 :   if (m_pos_nan != r.m_pos_nan || m_neg_nan != r.m_neg_nan)
    1379              :     {
    1380       207827 :       m_pos_nan |= r.m_pos_nan;
    1381       207827 :       m_neg_nan |= r.m_neg_nan;
    1382       207827 :       changed = true;
    1383              :     }
    1384       218328 :   if (changed)
    1385              :     {
    1386       215836 :       normalize_kind ();
    1387       215836 :       return true;
    1388              :     }
    1389              :   return false;
    1390              : }
    1391              : 
    1392              : bool
    1393     28851506 : frange::union_ (const vrange &v)
    1394              : {
    1395     28851506 :   const frange &r = as_a <frange> (v);
    1396              : 
    1397     28851506 :   if (r.undefined_p () || varying_p ())
    1398              :     return false;
    1399     27816445 :   if (undefined_p () || r.varying_p ())
    1400              :     {
    1401     24188661 :       *this = r;
    1402     24188661 :       return true;
    1403              :     }
    1404              : 
    1405              :   // Combine NAN info.
    1406      3627784 :   if (known_isnan () || r.known_isnan ())
    1407       218328 :     return union_nans (r);
    1408              : 
    1409      3409456 :   frange save = *this;
    1410      3409456 :   m_pos_nan |= r.m_pos_nan;
    1411      3409456 :   m_neg_nan |= r.m_neg_nan;
    1412              : 
    1413              :   // Throw both operands' sub-ranges into the pot as set_pairs will
    1414              :   // canonicalize things and hand us back at most MAX_PAIRS.
    1415              :   //
    1416              :   // NOTE: Both operands are already sorted and disjoint, so a merge could
    1417              :   // combine them in O(n) like irange::union_ rather than have set_pairs
    1418              :   // re-sort.  Not worth it while MAX_PAIRS is tiny; revisit if it grows.
    1419      3409456 :   frange_pair pairs[2 * MAX_PAIRS];
    1420      3409456 :   unsigned n = 0;
    1421      7157045 :   for (unsigned i = 0; i < save.m_num_ranges; ++i)
    1422      3747589 :     pairs[n++] = save.m_pairs[i];
    1423      6877295 :   for (unsigned i = 0; i < r.m_num_ranges; ++i)
    1424      3467839 :     pairs[n++] = r.m_pairs[i];
    1425              : 
    1426      3409456 :   set_pairs (pairs, n);
    1427      3409456 :   return *this != save;
    1428      3409456 : }
    1429              : 
    1430              : // Intersect two ranges when one is known to be a NAN.
    1431              : 
    1432              : bool
    1433        54208 : frange::intersect_nans (const frange &r)
    1434              : {
    1435        54208 :   gcc_checking_assert (known_isnan () || r.known_isnan ());
    1436              : 
    1437        54208 :   m_pos_nan &= r.m_pos_nan;
    1438        54208 :   m_neg_nan &= r.m_neg_nan;
    1439        56463 :   if (maybe_isnan ())
    1440        51985 :     set_nan (m_type, get_nan_state ());
    1441              :   else
    1442         2223 :     set_undefined ();
    1443        54208 :   return true;
    1444              : }
    1445              : 
    1446              : bool
    1447     23596433 : frange::intersect (const vrange &v)
    1448              : {
    1449     23596433 :   const frange &r = as_a <frange> (v);
    1450              : 
    1451     23596433 :   if (undefined_p () || r.varying_p ())
    1452              :     return false;
    1453     10118704 :   if (r.undefined_p ())
    1454              :     {
    1455         6445 :       set_undefined ();
    1456         6445 :       return true;
    1457              :     }
    1458     10112259 :   if (varying_p ())
    1459              :     {
    1460      2604053 :       *this = r;
    1461      2604053 :       return true;
    1462              :     }
    1463              : 
    1464              :   // Combine NAN info.
    1465      7508206 :   if (known_isnan () || r.known_isnan ())
    1466        54208 :     return intersect_nans (r);
    1467              : 
    1468      7453998 :   frange save = *this;
    1469      7453998 :   m_pos_nan &= r.m_pos_nan;
    1470      7453998 :   m_neg_nan &= r.m_neg_nan;
    1471              : 
    1472              :   // Meet every sub-range against every other.  Two sorted, disjoint sets of at
    1473              :   // most MAX_PAIRS each cannot yield more than MAX_PAIRS^2 pieces.
    1474              :   //
    1475              :   // NOTE: Since both operands are sorted, a merge-style meet like irange would
    1476              :   // be O(n) and leave set_pairs nothing to sort.  Not worth it while MAX_PAIRS
    1477              :   // is tiny; revisit if it grows.
    1478      7453998 :   frange_pair pairs[MAX_PAIRS * MAX_PAIRS];
    1479      7453998 :   unsigned n = 0;
    1480     15644745 :   for (unsigned i = 0; i < save.m_num_ranges; ++i)
    1481     17549191 :     for (unsigned j = 0; j < r.m_num_ranges; ++j)
    1482              :       {
    1483      9358444 :         const REAL_VALUE_TYPE &min
    1484      9358444 :           = frange_max (save.m_pairs[i].min, r.m_pairs[j].min);
    1485      9358444 :         const REAL_VALUE_TYPE &max
    1486      9358444 :           = frange_min (save.m_pairs[i].max, r.m_pairs[j].max);
    1487              :         // A reversed interval means these two do not overlap.  This also
    1488              :         // catches [+0.0, -0.0], which is empty rather than nonsensical.
    1489      9358444 :         if (frange_cmp (min, max) <= 0)
    1490      8095064 :           pairs[n++] = { min, max };
    1491              :       }
    1492              : 
    1493              :   // Nothing but a possible NAN survives.
    1494      7453998 :   if (n == 0)
    1495              :     {
    1496        40932 :       if (maybe_isnan ())
    1497        29262 :         set_nan (m_type, get_nan_state ());
    1498              :       else
    1499         5835 :         set_undefined ();
    1500              :       return true;
    1501              :     }
    1502              : 
    1503      7418901 :   set_pairs (pairs, n);
    1504      7418901 :   return *this != save;
    1505              : }
    1506              : 
    1507              : frange &
    1508     42179220 : frange::operator= (const frange &src)
    1509              : {
    1510     42179220 :   m_kind = src.m_kind;
    1511     42179220 :   m_type = src.m_type;
    1512     42179220 :   m_num_ranges = src.m_num_ranges;
    1513     86061940 :   for (unsigned i = 0; i < src.m_num_ranges; ++i)
    1514     43882720 :     m_pairs[i] = src.m_pairs[i];
    1515     42179220 :   m_pos_nan = src.m_pos_nan;
    1516     42179220 :   m_neg_nan = src.m_neg_nan;
    1517              : 
    1518     42179220 :   if (flag_checking)
    1519     42179220 :     verify_range ();
    1520     42179220 :   return *this;
    1521              : }
    1522              : 
    1523              : bool
    1524     10952348 : frange::operator== (const frange &src) const
    1525              : {
    1526     10952348 :   if (m_kind == src.m_kind)
    1527              :     {
    1528     10809166 :       if (undefined_p ())
    1529              :         return true;
    1530              : 
    1531     10809008 :       if (varying_p ())
    1532        51806 :         return types_compatible_p (m_type, src.m_type);
    1533              : 
    1534     10757202 :       bool nan1 = known_isnan ();
    1535     10757202 :       bool nan2 = src.known_isnan ();
    1536     10757202 :       if (nan1 || nan2)
    1537              :         {
    1538          129 :           if (nan1 && nan2)
    1539          129 :             return (m_pos_nan == src.m_pos_nan
    1540          129 :                     && m_neg_nan == src.m_neg_nan);
    1541              :           return false;
    1542              :         }
    1543              : 
    1544     10757073 :       if (m_num_ranges != src.m_num_ranges)
    1545              :         return false;
    1546     14925212 :       for (unsigned i = 0; i < m_num_ranges; ++i)
    1547      9165458 :         if (!real_identical (&m_pairs[i].min, &src.m_pairs[i].min)
    1548      9165458 :             || !real_identical (&m_pairs[i].max, &src.m_pairs[i].max))
    1549              :           return false;
    1550              : 
    1551      5759754 :       return (m_pos_nan == src.m_pos_nan
    1552      5575060 :               && m_neg_nan == src.m_neg_nan
    1553     11241378 :               && types_compatible_p (m_type, src.m_type));
    1554              :     }
    1555              :   return false;
    1556              : }
    1557              : 
    1558              : // Return TRUE if range contains R.
    1559              : 
    1560              : bool
    1561      1392821 : frange::contains_p (const REAL_VALUE_TYPE &r) const
    1562              : {
    1563      1392821 :   gcc_checking_assert (m_kind != VR_ANTI_RANGE);
    1564              : 
    1565      1392821 :   if (undefined_p ())
    1566              :     return false;
    1567              : 
    1568      1392821 :   if (varying_p ())
    1569              :     return true;
    1570              : 
    1571      1028121 :   if (real_isnan (&r))
    1572              :     {
    1573              :       // No NAN in range.
    1574            0 :       if (!m_pos_nan && !m_neg_nan)
    1575              :         return false;
    1576              :       // Both +NAN and -NAN are present.
    1577            0 :       if (m_pos_nan && m_neg_nan)
    1578              :         return true;
    1579            0 :       return m_neg_nan == r.sign;
    1580              :     }
    1581      1028121 :   if (known_isnan ())
    1582              :     return false;
    1583              : 
    1584      1666278 :   for (unsigned i = 0; i < m_num_ranges; ++i)
    1585      1039645 :     if (frange_cmp (r, m_pairs[i].min) >= 0
    1586      1039645 :         && frange_cmp (r, m_pairs[i].max) <= 0)
    1587              :       return true;
    1588              : 
    1589              :   return false;
    1590              : }
    1591              : 
    1592              : // If range is a singleton, place it in RESULT and return TRUE.  If
    1593              : // RESULT is NULL, just return TRUE.
    1594              : //
    1595              : // A NAN can never be a singleton.
    1596              : 
    1597              : bool
    1598     27643785 : frange::internal_singleton_p (REAL_VALUE_TYPE *result) const
    1599              : {
    1600     27643785 :   if (m_kind == VR_RANGE
    1601      4839198 :       && m_num_ranges == 1
    1602     31696342 :       && real_identical (&m_pairs[0].min, &m_pairs[0].max))
    1603              :     {
    1604              :       // Return false for any singleton that may be a NAN.
    1605       266060 :       if (HONOR_NANS (m_type) && maybe_isnan ())
    1606              :         return false;
    1607              : 
    1608       924427 :       if (MODE_COMPOSITE_P (TYPE_MODE (m_type)))
    1609              :         {
    1610              :           // For IBM long doubles, if the value is +-Inf or is exactly
    1611              :           // representable in double, the other double could be +0.0
    1612              :           // or -0.0.  Since this means there is more than one way to
    1613              :           // represent a value, return false to avoid propagating it.
    1614              :           // See libgcc/config/rs6000/ibm-ldouble-format for details.
    1615            0 :           if (real_isinf (&m_pairs[0].min))
    1616            0 :             return false;
    1617            0 :           REAL_VALUE_TYPE r;
    1618            0 :           real_convert (&r, DFmode, &m_pairs[0].min);
    1619            0 :           if (real_identical (&r, &m_pairs[0].min))
    1620              :             return false;
    1621              :         }
    1622              : 
    1623       132061 :       if (result)
    1624            0 :         *result = m_pairs[0].min;
    1625              :       return true;
    1626              :     }
    1627              :   return false;
    1628              : }
    1629              : 
    1630              : bool
    1631     27643785 : frange::singleton_p (tree *result) const
    1632              : {
    1633     27643785 :   if (internal_singleton_p ())
    1634              :     {
    1635       132061 :       if (result)
    1636        17883 :         *result = build_real (m_type, m_pairs[0].min);
    1637              :       return true;
    1638              :     }
    1639              :   return false;
    1640              : }
    1641              : 
    1642              : bool
    1643            0 : frange::singleton_p (REAL_VALUE_TYPE &r) const
    1644              : {
    1645            0 :   return internal_singleton_p (&r);
    1646              : }
    1647              : 
    1648              : bool
    1649     66939139 : frange::supports_type_p (const_tree type) const
    1650              : {
    1651     66939139 :   return supports_p (type);
    1652              : }
    1653              : 
    1654              : void
    1655    246043917 : frange::verify_range () const
    1656              : {
    1657    246043917 :   if (!undefined_p ())
    1658     84459168 :     gcc_checking_assert (HONOR_NANS (m_type) || !maybe_isnan ());
    1659    246043917 :   switch (m_kind)
    1660              :     {
    1661    163505627 :     case VR_UNDEFINED:
    1662    163505627 :       gcc_checking_assert (!m_type);
    1663              :       return;
    1664     16533064 :     case VR_VARYING:
    1665     16533064 :       gcc_checking_assert (m_type);
    1666     16533064 :       gcc_checking_assert (m_num_ranges == 1);
    1667     16533064 :       gcc_checking_assert (frange_val_is_min (m_pairs[0].min, m_type));
    1668     16533064 :       gcc_checking_assert (frange_val_is_max (m_pairs[0].max, m_type));
    1669     16533064 :       if (HONOR_NANS (m_type))
    1670     15815729 :         gcc_checking_assert (m_pos_nan && m_neg_nan);
    1671              :       else
    1672       717335 :         gcc_checking_assert (!m_pos_nan && !m_neg_nan);
    1673              :       return;
    1674     65480570 :     case VR_RANGE:
    1675     65480570 :       gcc_checking_assert (m_type);
    1676     65480570 :       gcc_checking_assert (m_num_ranges >= 1 && m_num_ranges <= MAX_PAIRS);
    1677              :       break;
    1678       524656 :     case VR_NAN:
    1679       524656 :       gcc_checking_assert (m_type);
    1680       524656 :       gcc_checking_assert (m_pos_nan || m_neg_nan);
    1681              :       return;
    1682            0 :     default:
    1683            0 :       gcc_unreachable ();
    1684              :     }
    1685              : 
    1686    137145349 :   for (unsigned i = 0; i < m_num_ranges; ++i)
    1687              :     {
    1688              :       // NANs cannot appear in the endpoints of a range.
    1689     71664779 :       gcc_checking_assert (!real_isnan (&m_pairs[i].min)
    1690              :                            && !real_isnan (&m_pairs[i].max));
    1691              : 
    1692              :       // Make sure we don't have swapped ranges.
    1693              :       // This also catches [ +0.0, -0.0].
    1694     71664779 :       gcc_checking_assert (frange_cmp (m_pairs[i].min, m_pairs[i].max) <= 0);
    1695              : 
    1696              :       // A zero endpoint must carry its canonical sign.  Every producer runs
    1697              :       // canonicalize_zeros, so a zero bound can only descend from a canonical
    1698              :       // one.
    1699    286659116 :       if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (m_type)))
    1700            0 :         gcc_checking_assert (!real_iszero (&m_pairs[i].min, 1)
    1701              :                              && !real_iszero (&m_pairs[i].max, 1));
    1702     71664779 :       else if (!HONOR_SIGNED_ZEROS (m_type))
    1703      1280619 :         gcc_checking_assert (!real_iszero (&m_pairs[i].min, 0)
    1704              :                              && !real_iszero (&m_pairs[i].max, 1));
    1705              :     }
    1706              : 
    1707              :   // Sub-ranges are sorted and separated by at least one representable value.
    1708     71664779 :   for (unsigned i = 1; i < m_num_ranges; ++i)
    1709      6184209 :     gcc_checking_assert (!frange_fusible_p (TYPE_MODE (m_type),
    1710              :                                             m_pairs[i - 1].max,
    1711              :                                             m_pairs[i].min));
    1712              : 
    1713              :   // If all the properties are clear, we better not span the entire
    1714              :   // domain, because that would make us varying.
    1715     65480570 :   if (m_num_ranges == 1 && m_pos_nan && m_neg_nan)
    1716     19223430 :     gcc_checking_assert (!frange_val_is_min (m_pairs[0].min, m_type)
    1717              :                          || !frange_val_is_max (m_pairs[0].max, m_type));
    1718              : }
    1719              : 
    1720              : void
    1721            8 : frange::set_nonzero (tree type)
    1722              : {
    1723            8 :   set (type, dconstm0, dconst0, VR_ANTI_RANGE);
    1724            8 : }
    1725              : 
    1726              : // Return TRUE if the range contains zero (+0.0 or -0.0).
    1727              : 
    1728              : bool
    1729      1041290 : frange::contains_zero_p () const
    1730              : {
    1731      1041290 :   return contains_p (dconst0) || contains_p (dconstm0);
    1732              : }
    1733              : 
    1734              : // Set range to [+0.0, +0.0] if honoring signed zeros, or [0.0, 0.0]
    1735              : // otherwise.
    1736              : 
    1737              : void
    1738       713250 : frange::set_zero (tree type)
    1739              : {
    1740       713250 :   if (HONOR_SIGNED_ZEROS (type))
    1741              :     {
    1742       713181 :       set (type, dconstm0, dconst0);
    1743       713181 :       clear_nan ();
    1744              :     }
    1745              :   else
    1746           69 :     set (type, dconst0, dconst0);
    1747       713250 : }
    1748              : 
    1749              : // Return TRUE for any zero regardless of sign.
    1750              : 
    1751              : bool
    1752         8519 : frange::zero_p () const
    1753              : {
    1754         8519 :   return (m_kind == VR_RANGE
    1755         7522 :           && m_num_ranges == 1
    1756         7226 :           && real_iszero (&m_pairs[0].min)
    1757        10484 :           && real_iszero (&m_pairs[0].max));
    1758              : }
    1759              : 
    1760              : // Set the range to non-negative numbers, that is [+0.0, +INF].
    1761              : //
    1762              : // The NAN in the resulting range (if HONOR_NANS) has a varying sign
    1763              : // as there are no guarantees in IEEE 754 wrt to the sign of a NAN,
    1764              : // except for copy, abs, and copysign.  It is the responsibility of
    1765              : // the caller to set the NAN's sign if desired.
    1766              : 
    1767              : void
    1768        39453 : frange::set_nonnegative (tree type)
    1769              : {
    1770        39453 :   set (type, dconst0, frange_val_max (type));
    1771        39453 : }
    1772              : 
    1773              : tree
    1774            0 : frange::lbound () const
    1775              : {
    1776            0 :   return build_real (type (), lower_bound ());
    1777              : }
    1778              : 
    1779              : tree
    1780            0 : frange::ubound () const
    1781              : {
    1782            0 :   return build_real (type (), upper_bound ());
    1783              : }
    1784              : 
    1785              : /* Widen a single bound of a sub-range by 1ulp (or 0.5ulp) in the direction of
    1786              :    DIR.  */
    1787              : 
    1788              : static REAL_VALUE_TYPE
    1789      2074364 : float_widen_bound (tree type, const REAL_VALUE_TYPE &bound,
    1790              :                    const REAL_VALUE_TYPE &dir)
    1791              : {
    1792      2074364 :   REAL_VALUE_TYPE res = bound;
    1793      2074364 :   if (!real_isfinite (&bound) && real_isneg (&bound) == real_isneg (&dir))
    1794              :     return res;
    1795      1490219 :   frange_nextafter (TYPE_MODE (type), res, dir);
    1796      1490219 :   if (real_isinf (&res))
    1797              :     {
    1798              :       /* For +-DBL_MAX, instead of +-Inf use nexttoward (+-DBL_MAX, +-LDBL_MAX)
    1799              :          in a hypothetical wider type with the same mantissa precision but
    1800              :          larger exponent range; it is outside of range of double values, but
    1801              :          makes it clear it is just one ulp larger rather than infinite amount
    1802              :          larger.  */
    1803       145449 :       res = real_isneg (&dir) ? dconstm1 : dconst1;
    1804       581796 :       SET_REAL_EXP (&res, FLOAT_MODE_FORMAT (TYPE_MODE (type))->emax + 1);
    1805              :     }
    1806      1490219 :   if (!flag_rounding_math
    1807     10431398 :       && !MODE_COMPOSITE_P (TYPE_MODE (type))
    1808      2980246 :       && real_isfinite (&bound))
    1809              :     {
    1810              :       /* If not -frounding-math nor IBM double double, actually widen
    1811              :          just by 0.5ulp rather than 1ulp.  */
    1812      1489010 :       REAL_VALUE_TYPE tem;
    1813      1489010 :       real_arithmetic (&tem, PLUS_EXPR, &bound, &res);
    1814      1489010 :       real_arithmetic (&res, RDIV_EXPR, &tem, &dconst2);
    1815              :     }
    1816              :   return res;
    1817              : }
    1818              : 
    1819              : /* Extend the *this range by 1ulp in each direction.  For op1_range
    1820              :    or op2_range of binary operations just computing the inverse
    1821              :    operation on ranges isn't sufficient.  Consider e.g.
    1822              :    [1., 1.] = op1 + [1., 1.].  op1's range is not [0., 0.], but
    1823              :    [-0x1.0p-54, 0x1.0p-53] (when not -frounding-math), any value for
    1824              :    which adding 1. to it results in 1. after rounding to nearest.
    1825              :    So, for op1_range/op2_range extend the lhs range by 1ulp (or 0.5ulp)
    1826              :    in each direction.  See PR109008 for more details.  */
    1827              : 
    1828              : void
    1829       977105 : frange::widen (tree type)
    1830              : {
    1831       977105 :   if (known_isnan ())
    1832              :     return;
    1833              :   /* Temporarily disable -ffinite-math-only, so that frange::set doesn't
    1834              :      reduce the range back to real_min_representable (type) as lower bound
    1835              :      or real_max_representable (type) as upper bound.  */
    1836       971596 :   bool save_flag_finite_math_only = flag_finite_math_only;
    1837       971596 :   flag_finite_math_only = false;
    1838       971596 :   unsigned j = 0;
    1839      2008778 :   for (unsigned i = 0; i < num_pairs (); ++i)
    1840              :     {
    1841      1037182 :       REAL_VALUE_TYPE lb = float_widen_bound (type, lower_bound (i),
    1842              :                                               dconstninf);
    1843      1037182 :       REAL_VALUE_TYPE ub = float_widen_bound (type, upper_bound (i),
    1844              :                                               dconstinf);
    1845              :       /* The result of float_widen_bound is often not representable in
    1846              :          type (could be smaller by 1ulp from representable finite minimum,
    1847              :          0.5ulp from some representable finite value or 1ulp larger than
    1848              :          representable finite maximum).  On such values calling e.g.
    1849              :          frange_nextafter doesn't work properly, so avoid merging the
    1850              :          pairs with union_ because that calls frange_fusible_p etc.
    1851              :          This range is often just something that should have the
    1852              :          real values passed to frange_arithmetic etc. and have the result
    1853              :          of that converted to something actually representable in the
    1854              :          type.  See PR126641 and PR109008.  As lhs should have been
    1855              :          canonicalized before, the slightly adjusted range should have
    1856              :          similar properties, just merge pairs where max would be >= than
    1857              :          min of the next pair.  */
    1858      1037182 :       if (j && !real_less (&m_pairs[j - 1].max, &lb))
    1859            0 :         m_pairs[j - 1].max = ub;
    1860              :       else
    1861              :         {
    1862      1037182 :           m_pairs[j].min = lb;
    1863      1037182 :           m_pairs[j].max = ub;
    1864      1037182 :           ++j;
    1865              :         }
    1866              :     }
    1867       971596 :   m_num_ranges = j;
    1868       971596 :   flag_finite_math_only = save_flag_finite_math_only;
    1869              : }
    1870              : 
    1871              : // Here we copy between any two irange's.
    1872              : 
    1873              : irange &
    1874   1241416568 : irange::operator= (const irange &src)
    1875              : {
    1876   1241416568 :   int needed = src.num_pairs ();
    1877   1241416568 :   maybe_resize (needed);
    1878              : 
    1879   1241416568 :   unsigned x;
    1880   1241416568 :   unsigned lim = src.m_num_ranges;
    1881   1241416568 :   if (lim > m_max_ranges)
    1882        33699 :     lim = m_max_ranges;
    1883              : 
    1884   3954715708 :   for (x = 0; x < lim * 2; ++x)
    1885   2713299140 :     m_base[x] = src.m_base[x];
    1886              : 
    1887              :   // If the range didn't fit, the last range should cover the rest.
    1888   1241416568 :   if (lim != src.m_num_ranges)
    1889        33699 :     m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
    1890              : 
    1891   1241416568 :   m_num_ranges = lim;
    1892   1241416568 :   m_type = src.m_type;
    1893   1241416568 :   m_kind = src.m_kind;
    1894   1241416568 :   m_bitmask = src.m_bitmask;
    1895   1241416568 :   if (m_max_ranges == 1)
    1896     21735811 :     normalize_kind ();
    1897   1241416568 :   if (flag_checking)
    1898   1241410725 :     verify_range ();
    1899   1241416568 :   return *this;
    1900              : }
    1901              : 
    1902              : static value_range_kind
    1903     21584836 : get_legacy_range (const irange &r, tree &min, tree &max)
    1904              : {
    1905     21584836 :   if (r.undefined_p ())
    1906              :     {
    1907       103415 :       min = NULL_TREE;
    1908       103415 :       max = NULL_TREE;
    1909       103415 :       return VR_UNDEFINED;
    1910              :     }
    1911              : 
    1912     21481421 :   tree type = r.type ();
    1913     21481421 :   if (r.varying_p ())
    1914              :     {
    1915      9131804 :       min = wide_int_to_tree (type, r.lower_bound ());
    1916      9131804 :       max = wide_int_to_tree (type, r.upper_bound ());
    1917      9131804 :       return VR_VARYING;
    1918              :     }
    1919              : 
    1920     12349617 :   unsigned int precision = TYPE_PRECISION (type);
    1921     12349617 :   signop sign = TYPE_SIGN (type);
    1922     24699234 :   if (r.num_pairs () > 1
    1923      3285319 :       && precision > 1
    1924     18920255 :       && r.lower_bound () == wi::min_value (precision, sign)
    1925     17780139 :       && r.upper_bound () == wi::max_value (precision, sign))
    1926              :     {
    1927       579848 :       int_range<3> inv (r);
    1928       579848 :       inv.invert ();
    1929       579848 :       min = wide_int_to_tree (type, inv.lower_bound (0));
    1930       579848 :       max = wide_int_to_tree (type, inv.upper_bound (0));
    1931       579848 :       return VR_ANTI_RANGE;
    1932       579848 :     }
    1933              : 
    1934     11769769 :   min = wide_int_to_tree (type, r.lower_bound ());
    1935     11769769 :   max = wide_int_to_tree (type, r.upper_bound ());
    1936     11769769 :   return VR_RANGE;
    1937              : }
    1938              : 
    1939              : static value_range_kind
    1940      3065318 : get_legacy_range (const prange &r, tree &min, tree &max)
    1941              : {
    1942      3065318 :   if (r.undefined_p ())
    1943              :     {
    1944            0 :       min = NULL_TREE;
    1945            0 :       max = NULL_TREE;
    1946            0 :       return VR_UNDEFINED;
    1947              :     }
    1948              : 
    1949      3065318 :   tree type = r.type ();
    1950      3065318 :   if (r.varying_p ())
    1951              :     {
    1952            0 :       min = r.lbound ();
    1953            0 :       max = r.ubound ();
    1954            0 :       return VR_VARYING;
    1955              :     }
    1956      3065318 :   if (r.zero_p ())
    1957              :     {
    1958      2303956 :       min = max = r.lbound ();
    1959      2303956 :       return VR_RANGE;
    1960              :     }
    1961       761362 :   prange nonzero (type);
    1962       761362 :   nonzero.set_nonzero (type);
    1963      1522724 :   if (r.lower_bound () == nonzero.lower_bound ()
    1964       795904 :       && r.upper_bound () == nonzero.upper_bound ())
    1965              :     {
    1966            0 :       min = max = build_zero_cst (type);
    1967            0 :       return VR_ANTI_RANGE;
    1968              :     }
    1969       761362 :   min = r.lbound ();
    1970       761362 :   max = r.ubound ();
    1971       761362 :   return VR_RANGE;
    1972       761362 : }
    1973              : 
    1974              : // Given a range in V, return an old-style legacy range consisting of
    1975              : // a value_range_kind with a MIN/MAX.  This is to maintain
    1976              : // compatibility with passes that still depend on VR_ANTI_RANGE, and
    1977              : // only works for integers and pointers.
    1978              : 
    1979              : value_range_kind
    1980     24650154 : get_legacy_range (const vrange &v, tree &min, tree &max)
    1981              : {
    1982     24650154 :   if (is_a <irange> (v))
    1983     21584836 :     return get_legacy_range (as_a <irange> (v), min, max);
    1984              : 
    1985      3065318 :   return get_legacy_range (as_a <prange> (v), min, max);
    1986              : }
    1987              : 
    1988              : /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
    1989              :    This means adjusting VRTYPE, MIN and MAX representing the case of a
    1990              :    wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
    1991              :    as anti-rage ~[MAX+1, MIN-1].  Likewise for wrapping anti-ranges.
    1992              :    In corner cases where MAX+1 or MIN-1 wraps this will fall back
    1993              :    to varying.
    1994              :    This routine exists to ease canonicalization in the case where we
    1995              :    extract ranges from var + CST op limit.  */
    1996              : 
    1997              : void
    1998   1613113383 : irange::set (tree type, const wide_int &min, const wide_int &max,
    1999              :              value_range_kind kind)
    2000              : {
    2001   1613113383 :   unsigned prec = TYPE_PRECISION (type);
    2002   1613113383 :   signop sign = TYPE_SIGN (type);
    2003   1613113383 :   wide_int min_value = wi::min_value (prec, sign);
    2004   1613113383 :   wide_int max_value = wi::max_value (prec, sign);
    2005              : 
    2006   1613113383 :   m_type = type;
    2007   1613113383 :   m_bitmask.set_unknown (prec);
    2008              : 
    2009   1613113383 :   if (kind == VR_RANGE)
    2010              :     {
    2011   1538195064 :       m_base[0] = min;
    2012   1538195064 :       m_base[1] = max;
    2013   1538195064 :       m_num_ranges = 1;
    2014   2054477862 :       if (min == min_value && max == max_value)
    2015     37692705 :         m_kind = VR_VARYING;
    2016              :       else
    2017   1500502359 :         m_kind = VR_RANGE;
    2018              :     }
    2019              :   else
    2020              :     {
    2021     74918319 :       gcc_checking_assert (kind == VR_ANTI_RANGE);
    2022     74918319 :       gcc_checking_assert (m_max_ranges > 1);
    2023              : 
    2024     74918319 :       m_kind = VR_UNDEFINED;
    2025     74918319 :       m_num_ranges = 0;
    2026     74918319 :       wi::overflow_type ovf;
    2027     74918319 :       wide_int lim;
    2028     74918319 :       if (sign == SIGNED)
    2029     37259311 :         lim = wi::add (min, -1, sign, &ovf);
    2030              :       else
    2031     37660014 :         lim = wi::sub (min, 1, sign, &ovf);
    2032              : 
    2033     74918319 :       if (!ovf)
    2034              :         {
    2035     55152392 :           m_kind = VR_RANGE;
    2036     55152392 :           m_base[0] = min_value;
    2037     55152392 :           m_base[1] = lim;
    2038     55152392 :           ++m_num_ranges;
    2039              :         }
    2040     74918319 :       if (sign == SIGNED)
    2041     37259311 :         lim = wi::sub (max, -1, sign, &ovf);
    2042              :       else
    2043     37660014 :         lim = wi::add (max, 1, sign, &ovf);
    2044     74918319 :       if (!ovf)
    2045              :         {
    2046     74916588 :           m_kind = VR_RANGE;
    2047     74916588 :           m_base[m_num_ranges * 2] = lim;
    2048     74916588 :           m_base[m_num_ranges * 2 + 1] = max_value;
    2049     74916588 :           ++m_num_ranges;
    2050              :         }
    2051     74918319 :     }
    2052              : 
    2053   1613113383 :   if (flag_checking)
    2054   1613108438 :     verify_range ();
    2055   1613113383 : }
    2056              : 
    2057              : void
    2058    258476481 : irange::set (tree min, tree max, value_range_kind kind)
    2059              : {
    2060    258476481 :   if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
    2061              :     {
    2062              :       set_varying (TREE_TYPE (min));
    2063              :       return;
    2064              :     }
    2065              : 
    2066    258476481 :   gcc_checking_assert (TREE_CODE (min) == INTEGER_CST);
    2067    258476481 :   gcc_checking_assert (TREE_CODE (max) == INTEGER_CST);
    2068              : 
    2069    258477668 :   return set (TREE_TYPE (min), wi::to_wide (min), wi::to_wide (max), kind);
    2070              : }
    2071              : 
    2072              : // Check the validity of the range.
    2073              : 
    2074              : void
    2075   5361768341 : irange::verify_range () const
    2076              : {
    2077   5361768341 :   gcc_checking_assert (m_discriminator == VR_IRANGE);
    2078   5361768341 :   if (m_kind == VR_UNDEFINED)
    2079              :     {
    2080       248103 :       gcc_checking_assert (m_num_ranges == 0);
    2081              :       return;
    2082              :     }
    2083   5361520238 :   gcc_checking_assert (supports_p (type ()));
    2084   5361520238 :   gcc_checking_assert (m_num_ranges <= m_max_ranges);
    2085              : 
    2086              :   // Legacy allowed these to represent VARYING for unknown types.
    2087              :   // Leave this in for now, until all users are converted.  Eventually
    2088              :   // we should abort in set_varying.
    2089   5361520238 :   if (m_kind == VR_VARYING && m_type == error_mark_node)
    2090              :     return;
    2091              : 
    2092   5361520238 :   unsigned prec = TYPE_PRECISION (m_type);
    2093   5361520238 :   if (m_kind == VR_VARYING)
    2094              :     {
    2095    254184523 :       gcc_checking_assert (m_bitmask.unknown_p ());
    2096    254184523 :       gcc_checking_assert (m_num_ranges == 1);
    2097    254184523 :       gcc_checking_assert (varying_compatible_p ());
    2098    254184523 :       gcc_checking_assert (lower_bound ().get_precision () == prec);
    2099    254184523 :       gcc_checking_assert (upper_bound ().get_precision () == prec);
    2100    254184523 :       return;
    2101              :     }
    2102   5107335715 :   gcc_checking_assert (m_num_ranges != 0);
    2103   5107335715 :   gcc_checking_assert (!varying_compatible_p ());
    2104  12951230044 :   for (unsigned i = 0; i < m_num_ranges; ++i)
    2105              :     {
    2106   7843894329 :       wide_int lb = lower_bound (i);
    2107   7843894329 :       wide_int ub = upper_bound (i);
    2108   7843894329 :       gcc_checking_assert (lb.get_precision () == prec);
    2109   7843894329 :       gcc_checking_assert (ub.get_precision () == prec);
    2110   7843894329 :       int c = wi::cmp (lb, ub, TYPE_SIGN (m_type));
    2111   7843894329 :       gcc_checking_assert (c == 0 || c == -1);
    2112              :       // Previous UB should be lower than LB
    2113   7843894329 :       if (i > 0)
    2114   5473117228 :         gcc_checking_assert (wi::lt_p (upper_bound (i - 1),
    2115              :                                        lb,
    2116              :                                        TYPE_SIGN (m_type)));
    2117   7846170358 :     }
    2118   5107335715 :   m_bitmask.verify_mask ();
    2119              : }
    2120              : 
    2121              : bool
    2122    162521496 : irange::operator== (const irange &other) const
    2123              : {
    2124    162521496 :   if (m_num_ranges != other.m_num_ranges)
    2125              :     return false;
    2126              : 
    2127    154844106 :   if (m_num_ranges == 0)
    2128              :     return true;
    2129              : 
    2130    154676068 :   signop sign1 = TYPE_SIGN (type ());
    2131    154676068 :   signop sign2 = TYPE_SIGN (other.type ());
    2132              : 
    2133    200780982 :   for (unsigned i = 0; i < m_num_ranges; ++i)
    2134              :     {
    2135    160750557 :       widest_int lb = widest_int::from (lower_bound (i), sign1);
    2136    160750557 :       widest_int ub = widest_int::from (upper_bound (i), sign1);
    2137    160750557 :       widest_int lb_other = widest_int::from (other.lower_bound (i), sign2);
    2138    160750557 :       widest_int ub_other = widest_int::from (other.upper_bound (i), sign2);
    2139    259753085 :       if (lb != lb_other || ub != ub_other)
    2140    114645643 :         return false;
    2141    160750999 :     }
    2142              : 
    2143     40030425 :   irange_bitmask bm1 = get_bitmask ();
    2144     40030425 :   irange_bitmask bm2 = other.get_bitmask ();
    2145     40030425 :   widest_int tmp1 = widest_int::from (bm1.mask (), sign1);
    2146     40030425 :   widest_int tmp2 = widest_int::from (bm2.mask (), sign2);
    2147     40030425 :   if (tmp1 != tmp2)
    2148              :     return false;
    2149     40024970 :   if (bm1.unknown_p ())
    2150              :     return true;
    2151     29638015 :   tmp1 = widest_int::from (bm1.value (), sign1);
    2152     29638015 :   tmp2 = widest_int::from (bm2.value (), sign2);
    2153     29637991 :   return tmp1 == tmp2;
    2154     40030470 : }
    2155              : 
    2156              : /* If range is a singleton, place it in RESULT and return TRUE.  */
    2157              : 
    2158              : bool
    2159    795923548 : irange::singleton_p (tree *result) const
    2160              : {
    2161   1475102009 :   if (num_pairs () == 1 && lower_bound () == upper_bound ())
    2162              :     {
    2163     46826651 :       if (result)
    2164     10212848 :         *result = wide_int_to_tree (type (), lower_bound ());
    2165              :       return true;
    2166              :     }
    2167              :   return false;
    2168              : }
    2169              : 
    2170              : bool
    2171    641158397 : irange::singleton_p (wide_int &w) const
    2172              : {
    2173    871092132 :   if (num_pairs () == 1 && lower_bound () == upper_bound ())
    2174              :     {
    2175     25281810 :       w = lower_bound ();
    2176     25281810 :       return true;
    2177              :     }
    2178              :   return false;
    2179              : }
    2180              : 
    2181              : /* Return 1 if CST is inside value range.
    2182              :           0 if CST is not inside value range.
    2183              : 
    2184              :    Benchmark compile/20001226-1.c compilation time after changing this
    2185              :    function.  */
    2186              : 
    2187              : bool
    2188    267367779 : irange::contains_p (const wide_int &cst) const
    2189              : {
    2190    267367779 :   if (undefined_p ())
    2191              :     return false;
    2192              : 
    2193              :   // Check if the known bits in bitmask exclude CST.
    2194    267284998 :   if (!m_bitmask.member_p (cst))
    2195              :     return false;
    2196              : 
    2197    266207678 :   signop sign = TYPE_SIGN (type ());
    2198    287357106 :   for (unsigned r = 0; r < m_num_ranges; ++r)
    2199              :     {
    2200    286362474 :       if (wi::lt_p (cst, lower_bound (r), sign))
    2201              :         return false;
    2202    148019730 :       if (wi::le_p (cst, upper_bound (r), sign))
    2203              :         return true;
    2204              :     }
    2205              : 
    2206              :   return false;
    2207              : }
    2208              : 
    2209              : // Perform an efficient union with R when both ranges have only a single pair.
    2210              : // Excluded are VARYING and UNDEFINED ranges.
    2211              : 
    2212              : bool
    2213    132421744 : irange::irange_single_pair_union (const irange &r)
    2214              : {
    2215    132421744 :   gcc_checking_assert (!undefined_p () && !varying_p ());
    2216    132421744 :   gcc_checking_assert (!r.undefined_p () && !varying_p ());
    2217              : 
    2218    132421744 :   signop sign = TYPE_SIGN (m_type);
    2219              :   // Check if current lower bound is also the new lower bound.
    2220    132421744 :   if (wi::le_p (m_base[0], r.m_base[0], sign))
    2221              :     {
    2222              :       // If current upper bound is new upper bound, we're done.
    2223    114613684 :       if (wi::le_p (r.m_base[1], m_base[1], sign))
    2224     15264769 :         return union_bitmask (r);
    2225              :       // Otherwise R has the new upper bound.
    2226              :       // Check for overlap/touching ranges, or single target range.
    2227    198697830 :       if (m_max_ranges == 1
    2228    298046737 :           || (widest_int::from (m_base[1], sign) + 1
    2229    397395648 :               >= widest_int::from (r.m_base[0], TYPE_SIGN (r.m_type))))
    2230     31742930 :         m_base[1] = r.m_base[1];
    2231              :       else
    2232              :         {
    2233              :           // This is a dual range result.
    2234     67605985 :           m_base[2] = r.m_base[0];
    2235     67605985 :           m_base[3] = r.m_base[1];
    2236     67605985 :           m_num_ranges = 2;
    2237              :         }
    2238              :       // The range has been altered, so normalize it even if nothing
    2239              :       // changed in the mask.
    2240     99348915 :       if (!union_bitmask (r))
    2241     98010311 :         normalize_kind ();
    2242     99348915 :       if (flag_checking)
    2243     99348783 :         verify_range ();
    2244              :       return true;
    2245              :     }
    2246              : 
    2247              :   // Set the new lower bound to R's lower bound.
    2248     17808060 :   wide_int lb = m_base[0];
    2249     17808060 :   m_base[0] = r.m_base[0];
    2250              : 
    2251              :   // If R fully contains THIS range, just set the upper bound.
    2252     17808060 :   if (wi::ge_p (r.m_base[1], m_base[1], sign))
    2253      1424319 :     m_base[1] = r.m_base[1];
    2254              :   // Check for overlapping ranges, or target limited to a single range.
    2255     32767482 :   else if (m_max_ranges == 1
    2256     49151223 :            || (widest_int::from (r.m_base[1], TYPE_SIGN (r.m_type)) + 1
    2257     65534964 :                >= widest_int::from (lb, sign)))
    2258              :     ;
    2259              :   else
    2260              :     {
    2261              :       // Left with 2 pairs.
    2262      7460864 :       m_num_ranges = 2;
    2263      7460864 :       m_base[2] = lb;
    2264      7460864 :       m_base[3] = m_base[1];
    2265      7460864 :       m_base[1] = r.m_base[1];
    2266              :     }
    2267              :   // The range has been altered, so normalize it even if nothing
    2268              :   // changed in the mask.
    2269     17808060 :   if (!union_bitmask (r))
    2270     16327649 :     normalize_kind ();
    2271     17808060 :   if (flag_checking)
    2272     17808049 :     verify_range ();
    2273     17808060 :   return true;
    2274     17808060 : }
    2275              : 
    2276              : // Append R to this range, knowing that R occurs after all of these subranges.
    2277              : // Return TRUE as something must have changed.
    2278              : 
    2279              : bool
    2280    164195030 : irange::union_append (const irange &r)
    2281              : {
    2282              :   // Check if the first range in R is an immediate successor to the last
    2283              :   // range, thus requiring a merge.
    2284    164195030 :   signop sign = TYPE_SIGN (m_type);
    2285    164195030 :   wide_int lb = r.lower_bound ();
    2286    164195030 :   wide_int ub = upper_bound ();
    2287    164195030 :   unsigned start = 0;
    2288    492585099 :   if (widest_int::from (ub, sign) + 1
    2289    492585090 :       == widest_int::from (lb, sign))
    2290              :     {
    2291      1238775 :       m_base[m_num_ranges * 2 - 1] = r.m_base[1];
    2292      1238775 :       start = 1;
    2293              :     }
    2294    164195030 :   maybe_resize (m_num_ranges + r.m_num_ranges - start);
    2295    491551372 :   for ( ; start < r.m_num_ranges; start++)
    2296              :     {
    2297              :       // Merge the last ranges if it exceeds the maximum size.
    2298    163908437 :       if (m_num_ranges + 1 > m_max_ranges)
    2299              :         {
    2300       747125 :           m_base[m_max_ranges * 2 - 1] = r.m_base[r.m_num_ranges * 2 - 1];
    2301       747125 :           break;
    2302              :         }
    2303    163161312 :       m_base[m_num_ranges * 2] = r.m_base[start * 2];
    2304    163161312 :       m_base[m_num_ranges * 2 + 1] = r.m_base[start * 2 + 1];
    2305    163161312 :       m_num_ranges++;
    2306              :     }
    2307              : 
    2308    164195030 :   if (!union_bitmask (r))
    2309    164142674 :     normalize_kind ();
    2310    164195030 :   if (flag_checking)
    2311    164195030 :     verify_range ();
    2312    164195030 :   return true;
    2313    164195030 : }
    2314              : 
    2315              : // Return TRUE if anything changes.
    2316              : 
    2317              : bool
    2318    450207645 : irange::union_ (const vrange &v)
    2319              : {
    2320    450207645 :   const irange &r = as_a <irange> (v);
    2321              : 
    2322    450207645 :   if (r.undefined_p ())
    2323              :     return false;
    2324              : 
    2325    447968755 :   if (undefined_p ())
    2326              :     {
    2327    103309246 :       operator= (r);
    2328    103309246 :       if (flag_checking)
    2329    103308842 :         verify_range ();
    2330              :       return true;
    2331              :     }
    2332              : 
    2333    344659509 :   if (varying_p ())
    2334              :     return false;
    2335              : 
    2336    334939852 :   if (r.varying_p ())
    2337              :     {
    2338      7329451 :       set_varying (type ());
    2339      7329451 :       return true;
    2340              :     }
    2341              : 
    2342              :   // Special case one range union one range.
    2343    327610401 :   if (m_num_ranges == 1 && r.m_num_ranges == 1)
    2344    132421744 :     return irange_single_pair_union (r);
    2345              : 
    2346    195188657 :   signop sign = TYPE_SIGN (m_type);
    2347              :   // Check for an append to the end.
    2348    585565971 :   if (m_kind == VR_RANGE && wi::gt_p (r.lower_bound (), upper_bound (), sign))
    2349    164195030 :     return union_append (r);
    2350              : 
    2351              :   // If this ranges fully contains R, then we need do nothing.
    2352     30993627 :   if (irange_contains_p (r))
    2353      4600047 :     return union_bitmask (r);
    2354              : 
    2355              :   // Do not worry about merging and such by reserving twice as many
    2356              :   // pairs as needed, and then simply sort the 2 ranges into this
    2357              :   // intermediate form.
    2358              :   //
    2359              :   // The intermediate result will have the property that the beginning
    2360              :   // of each range is <= the beginning of the next range.  There may
    2361              :   // be overlapping ranges at this point.  I.e. this would be valid
    2362              :   // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
    2363              :   // constraint : -20 < -10 < 0 < 40.  When the range is rebuilt into r,
    2364              :   // the merge is performed.
    2365              :   //
    2366              :   // [Xi,Yi]..[Xn,Yn]  U  [Xj,Yj]..[Xm,Ym]   -->  [Xk,Yk]..[Xp,Yp]
    2367     26393580 :   auto_vec<wide_int, 20> res (m_num_ranges * 2 + r.m_num_ranges * 2);
    2368     26393580 :   unsigned i = 0, j = 0, k = 0;
    2369              : 
    2370    114366845 :   while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
    2371              :     {
    2372              :       // lower of Xi and Xj is the lowest point.
    2373    123159370 :       if (widest_int::from (m_base[i], sign)
    2374    184739055 :           <= widest_int::from (r.m_base[j], sign))
    2375              :         {
    2376     31974264 :           res.quick_push (m_base[i]);
    2377     31974264 :           res.quick_push (m_base[i + 1]);
    2378     31974264 :           k += 2;
    2379     31974264 :           i += 2;
    2380              :         }
    2381              :       else
    2382              :         {
    2383     29605421 :           res.quick_push (r.m_base[j]);
    2384     29605421 :           res.quick_push (r.m_base[j + 1]);
    2385     29605421 :           k += 2;
    2386     29605421 :           j += 2;
    2387              :         }
    2388              :     }
    2389     52893095 :   for ( ; i < m_num_ranges * 2; i += 2)
    2390              :     {
    2391     26499515 :       res.quick_push (m_base[i]);
    2392     26499515 :       res.quick_push (m_base[i + 1]);
    2393     26499515 :       k += 2;
    2394              :     }
    2395     33983661 :   for ( ; j < r.m_num_ranges * 2; j += 2)
    2396              :     {
    2397      7590081 :       res.quick_push (r.m_base[j]);
    2398      7590081 :       res.quick_push (r.m_base[j + 1]);
    2399      7590081 :       k += 2;
    2400              :     }
    2401              : 
    2402              :   // Now normalize the vector removing any overlaps.
    2403              :   i = 2;
    2404     95669281 :   for (j = 2; j < k ; j += 2)
    2405              :     {
    2406              :       // Current upper+1 is >= lower bound next pair, then we merge ranges.
    2407    207827117 :       if (widest_int::from (res[i - 1], sign) + 1
    2408    207827103 :           >= widest_int::from (res[j], sign))
    2409              :         {
    2410              :           // New upper bounds is greater of current or the next one.
    2411     62375282 :           if (widest_int::from (res[j + 1], sign)
    2412     93562923 :               > widest_int::from (res[i - 1], sign))
    2413     23679192 :             res[i - 1] = res[j + 1];
    2414              :         }
    2415              :       else
    2416              :         {
    2417              :           // This is a new distinct range, but no point in copying it
    2418              :           // if it is already in the right place.
    2419     38088060 :           if (i != j)
    2420              :             {
    2421     12574077 :               res[i++] = res[j];
    2422     12574077 :               res[i++] = res[j + 1];
    2423              :             }
    2424              :           else
    2425     25513983 :             i += 2;
    2426              :         }
    2427              :     }
    2428              : 
    2429              :   // At this point, the vector should have i ranges, none overlapping.
    2430              :   // Now it simply needs to be copied, and if there are too many
    2431              :   // ranges, merge some.  We wont do any analysis as to what the
    2432              :   // "best" merges are, simply combine the final ranges into one.
    2433     26393580 :   maybe_resize (i / 2);
    2434     26393580 :   if (i > m_max_ranges * 2)
    2435              :     {
    2436         1814 :       res[m_max_ranges * 2 - 1] = res[i - 1];
    2437         1814 :       i = m_max_ranges * 2;
    2438              :     }
    2439              : 
    2440    155353232 :   for (j = 0; j < i ; j++)
    2441    128959652 :     m_base[j] = res [j];
    2442     26393580 :   m_num_ranges = i / 2;
    2443              : 
    2444     26393580 :   m_kind = VR_RANGE;
    2445              :   // The range has been altered, so normalize it even if nothing
    2446              :   // changed in the mask.
    2447     26393580 :   if (!union_bitmask (r))
    2448     25086491 :     normalize_kind ();
    2449     26393580 :   if (flag_checking)
    2450     26393538 :     verify_range ();
    2451     26393580 :   return true;
    2452     26393580 : }
    2453              : 
    2454              : // Return TRUE if THIS fully contains R.  No undefined or varying cases.
    2455              : 
    2456              : bool
    2457    231267566 : irange::irange_contains_p (const irange &r) const
    2458              : {
    2459    231267566 :   gcc_checking_assert (!undefined_p () && !varying_p ());
    2460    231267566 :   gcc_checking_assert (!r.undefined_p () && !varying_p ());
    2461              : 
    2462              :   // Check singletons directly which will include any bitmasks.
    2463    231267566 :   wide_int rl;
    2464    231267566 :   if (r.singleton_p (rl))
    2465     16036808 :     return contains_p (rl);
    2466              : 
    2467              :   // In order for THIS to fully contain R, all of the pairs within R must
    2468              :   // be fully contained by the pairs in this object.
    2469    215230758 :   signop sign = TYPE_SIGN (m_type);
    2470    215230758 :   unsigned ri = 0;
    2471    215230758 :   unsigned i = 0;
    2472    215230758 :   rl = r.m_base[0];
    2473    215230758 :   wide_int ru = r.m_base[1];
    2474    215230758 :   wide_int l = m_base[0];
    2475    215230758 :   wide_int u = m_base[1];
    2476    551768549 :   while (1)
    2477              :     {
    2478              :       // If r is contained within this range, move to the next R
    2479    551768549 :       if (wi::ge_p (rl, l, sign)
    2480    551768549 :           && wi::le_p (ru, u, sign))
    2481              :         {
    2482              :           // This pair is OK, Either done, or bump to the next.
    2483    254361604 :           if (++ri >= r.num_pairs ())
    2484              :             return true;
    2485    165681514 :           rl = r.m_base[ri * 2];
    2486    165681514 :           ru = r.m_base[ri * 2 + 1];
    2487    165681514 :           continue;
    2488              :         }
    2489              :       // Otherwise, check if this's pair occurs before R's.
    2490    297406945 :       if (wi::lt_p (u, rl, sign))
    2491              :         {
    2492              :           // There's still at least one pair of R left.
    2493    171863263 :           if (++i >= num_pairs ())
    2494              :             return false;
    2495    170856277 :           l = m_base[i * 2];
    2496    170856277 :           u = m_base[i * 2 + 1];
    2497    170856277 :           continue;
    2498              :         }
    2499              :       return false;
    2500              :     }
    2501              :   return false;
    2502    215236494 : }
    2503              : 
    2504              : 
    2505              : // Return TRUE if anything changes.
    2506              : 
    2507              : bool
    2508   1030410752 : irange::intersect (const vrange &v)
    2509              : {
    2510   1030410752 :   const irange &r = as_a <irange> (v);
    2511   1030410752 :   gcc_checking_assert (undefined_p () || r.undefined_p ()
    2512              :                        || range_compatible_p (type (), r.type ()));
    2513              : 
    2514   1030410752 :   if (undefined_p ())
    2515              :     return false;
    2516   1029287478 :   if (r.undefined_p ())
    2517              :     {
    2518       524477 :       set_undefined ();
    2519       524477 :       return true;
    2520              :     }
    2521   1028763001 :   if (r.varying_p ())
    2522              :     return false;
    2523    728918540 :   if (varying_p ())
    2524              :     {
    2525     97491124 :       operator= (r);
    2526     97491124 :       return true;
    2527              :     }
    2528              : 
    2529    631427416 :   if (r.num_pairs () == 1)
    2530              :     {
    2531    431020586 :       bool res = intersect (r.lower_bound (), r.upper_bound ());
    2532    431018074 :       if (undefined_p ())
    2533              :         return true;
    2534              : 
    2535    402527324 :       res |= intersect_bitmask (r);
    2536    402527324 :       if (res)
    2537    142946693 :         normalize_kind ();
    2538              :       return res;
    2539              :     }
    2540              : 
    2541              :   // If either range is a singleton and the other range does not contain
    2542              :   // it, the result is undefined.
    2543    200409342 :   wide_int val;
    2544    202189710 :   if ((singleton_p (val) && !r.contains_p (val))
    2545    202054307 :       || (r.singleton_p (val) && !contains_p (val)))
    2546              :     {
    2547       135403 :       set_undefined ();
    2548       135403 :       return true;
    2549              :     }
    2550              : 
    2551              :   // If R fully contains this, then intersection will change nothing.
    2552    200273939 :   if (r.irange_contains_p (*this))
    2553     87356543 :     return intersect_bitmask (r);
    2554              : 
    2555              :   // ?? We could probably come up with something smarter than the
    2556              :   // worst case scenario here.
    2557    112917396 :   int needed = num_pairs () + r.num_pairs ();
    2558    112917396 :   maybe_resize (needed);
    2559              : 
    2560    112917396 :   signop sign = TYPE_SIGN (m_type);
    2561    112917396 :   unsigned bld_pair = 0;
    2562    112917396 :   unsigned bld_lim = m_max_ranges;
    2563    112917396 :   int_range_max r2 (*this);
    2564    112917396 :   unsigned r2_lim = r2.num_pairs ();
    2565    112917396 :   unsigned i2 = 0;
    2566    112917396 :   bool need_snapping = !m_bitmask.unknown_p ();
    2567    329448359 :   for (unsigned i = 0; i < r.num_pairs (); )
    2568              :     {
    2569              :       // If r1's upper is < r2's lower, we can skip r1's pair.
    2570    293698122 :       wide_int ru = r.m_base[i * 2 + 1];
    2571    293698122 :       wide_int r2l = r2.m_base[i2 * 2];
    2572    293698122 :       if (wi::lt_p (ru, r2l, sign))
    2573              :         {
    2574     29885033 :           i++;
    2575     29885033 :           continue;
    2576              :         }
    2577              :       // Likewise, skip r2's pair if its excluded.
    2578    263813089 :       wide_int r2u = r2.m_base[i2 * 2 + 1];
    2579    263813089 :       wide_int rl = r.m_base[i * 2];
    2580    263813089 :       if (wi::lt_p (r2u, rl, sign))
    2581              :         {
    2582     27040967 :           i2++;
    2583     27040967 :           if (i2 < r2_lim)
    2584     21572188 :             continue;
    2585              :           // No more r2, break.
    2586              :           break;
    2587              :         }
    2588              : 
    2589              :       // Must be some overlap.  Find the highest of the lower bounds,
    2590              :       // and set it, unless the build limits lower bounds is already
    2591              :       // set.
    2592    236772122 :       if (bld_pair < bld_lim)
    2593              :         {
    2594    236402982 :           if (wi::ge_p (rl, r2l, sign))
    2595    200000838 :             m_base[bld_pair * 2] = rl;
    2596              :           else
    2597     36402144 :             m_base[bld_pair * 2] = r2l;
    2598              :         }
    2599              :       else
    2600              :         // Decrease the index to use the existing lower bound, and
    2601              :         // set a new upper for this pair.
    2602       369140 :         bld_pair--;
    2603              : 
    2604              :       // Changes to false if the last value in i2's range is consumed.
    2605    236772122 :       bool more = true;
    2606              :       // ...and choose the lower of the upper bounds.
    2607    236772122 :       if (wi::le_p (ru, r2u, sign))
    2608              :         {
    2609    149469183 :           m_base[bld_pair * 2 + 1] = ru;
    2610              :           // Move past the r1 pair and keep trying.
    2611    149469183 :           i++;
    2612              :         }
    2613              :       else
    2614              :         {
    2615     87302939 :           m_base[bld_pair * 2 + 1] = r2u;
    2616     87302939 :           i2++;
    2617              :           // No more r2, break the loop when done.
    2618     87302939 :           if (i2 >= r2_lim)
    2619     71698380 :             more = false;
    2620              :         }
    2621              :       // Now snap these ranges to the bitmask, if there is one.
    2622    236772122 :       if (need_snapping)
    2623              :         {
    2624     65832928 :           bool ovf;
    2625     65832928 :           wide_int lb, ub;
    2626     65832928 :           if (snap (m_base[bld_pair * 2], m_base[bld_pair * 2 + 1],
    2627              :                     lb, ub, ovf))
    2628              :             {
    2629              :               // If the new subrange does not fit the mask, skip it.
    2630      1425402 :               if (ovf)
    2631              :                 {
    2632        10182 :                   if (!more)
    2633              :                     break;
    2634        10182 :                   continue;
    2635              :                 }
    2636              :               // Otherwise adjust the pair.
    2637      1415220 :               m_base[bld_pair * 2] = lb;
    2638      1415220 :               m_base[bld_pair * 2 + 1] = ub;
    2639              :             }
    2640     65832928 :         }
    2641              :       // Current pair now satisfies any mask, ready for another pair.
    2642    236761940 :       bld_pair++;
    2643    236761940 :       if (!more)
    2644              :         break;
    2645    315286311 :     }
    2646              : 
    2647              :   // At the exit of this loop, it is one of 2 things:
    2648              :   // ran out of r1, or r2, but either means we are done.
    2649    112917396 :   m_num_ranges = bld_pair;
    2650    112917396 :   if (m_num_ranges == 0)
    2651              :     {
    2652       110067 :       set_undefined ();
    2653       110067 :       return true;
    2654              :     }
    2655              : 
    2656    112807329 :   m_kind = VR_RANGE;
    2657              :   // The range has been altered, so normalize it even if nothing
    2658              :   // changed in the mask.
    2659    112807329 :   if (!intersect_bitmask (r))
    2660    103288132 :     normalize_kind ();
    2661    112807329 :   if (flag_checking)
    2662    112807307 :     verify_range ();
    2663              :   return true;
    2664    313326738 : }
    2665              : 
    2666              : 
    2667              : // Multirange intersect for a specified wide_int [lb, ub] range.
    2668              : // Return TRUE if intersect changed anything.
    2669              : //
    2670              : // NOTE: It is the caller's responsibility to intersect the mask.
    2671              : 
    2672              : bool
    2673    431018074 : irange::intersect (const wide_int& lb, const wide_int& ub)
    2674              : {
    2675              :   // Undefined remains undefined.
    2676    431018074 :   if (undefined_p ())
    2677              :     return false;
    2678              : 
    2679    431018074 :   tree range_type = type();
    2680    431018074 :   signop sign = TYPE_SIGN (range_type);
    2681              : 
    2682    431018074 :   gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (lb));
    2683    431018074 :   gcc_checking_assert (TYPE_PRECISION (range_type) == wi::get_precision (ub));
    2684              : 
    2685              :   // If this range is fully contained, then intersection will do nothing.
    2686    862036148 :   if (wi::ge_p (lower_bound (), lb, sign)
    2687    772405613 :       && wi::le_p (upper_bound (), ub, sign))
    2688              :     return false;
    2689              : 
    2690    155870284 :   unsigned bld_index = 0;
    2691    155870284 :   unsigned pair_lim = num_pairs ();
    2692    235944907 :   for (unsigned i = 0; i < pair_lim; i++)
    2693              :     {
    2694    173464353 :       wide_int pairl = m_base[i * 2];
    2695    173464353 :       wide_int pairu = m_base[i * 2 + 1];
    2696              :       // Once UB is less than a pairs lower bound, we're done.
    2697    173464353 :       if (wi::lt_p (ub, pairl, sign))
    2698              :         break;
    2699              :       // if LB is greater than this pairs upper, this pair is excluded.
    2700    150298949 :       if (wi::lt_p (pairu, lb, sign))
    2701     20730298 :         continue;
    2702              : 
    2703              :       // Must be some overlap.  Find the highest of the lower bounds,
    2704              :       // and set it
    2705    129568651 :       if (wi::gt_p (lb, pairl, sign))
    2706     71448815 :         m_base[bld_index * 2] = lb;
    2707              :       else
    2708     58119836 :         m_base[bld_index * 2] = pairl;
    2709              : 
    2710              :       // ...and choose the lower of the upper bounds and if the base pair
    2711              :       // has the lower upper bound, need to check next pair too.
    2712    129568651 :       if (wi::lt_p (ub, pairu, sign))
    2713              :         {
    2714     70224326 :           m_base[bld_index++ * 2 + 1] = ub;
    2715     70224326 :           break;
    2716              :         }
    2717              :       else
    2718     59344325 :         m_base[bld_index++ * 2 + 1] = pairu;
    2719    173464890 :     }
    2720              : 
    2721    155870284 :   m_num_ranges = bld_index;
    2722    155870284 :   if (m_num_ranges == 0)
    2723              :     {
    2724     28490750 :       set_undefined ();
    2725     28490750 :       return true;
    2726              :     }
    2727              : 
    2728    127379534 :   m_kind = VR_RANGE;
    2729              :   // The caller must normalize and verify the range, as the bitmask
    2730              :   // still needs to be handled.
    2731    127379534 :   return true;
    2732              : }
    2733              : 
    2734              : 
    2735              : // Signed 1-bits are strange.  You can't subtract 1, because you can't
    2736              : // represent the number 1.  This works around that for the invert routine.
    2737              : 
    2738              : static wide_int inline
    2739     73267212 : subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
    2740              : {
    2741     73267212 :   if (TYPE_SIGN (type) == SIGNED)
    2742     46277042 :     return wi::add (x, -1, SIGNED, &overflow);
    2743              :   else
    2744     26990170 :     return wi::sub (x, 1, UNSIGNED, &overflow);
    2745              : }
    2746              : 
    2747              : // The analogous function for adding 1.
    2748              : 
    2749              : static wide_int inline
    2750     79293935 : add_one (const wide_int &x, tree type, wi::overflow_type &overflow)
    2751              : {
    2752     79293935 :   if (TYPE_SIGN (type) == SIGNED)
    2753     39115117 :     return wi::sub (x, -1, SIGNED, &overflow);
    2754              :   else
    2755     40178818 :     return wi::add (x, 1, UNSIGNED, &overflow);
    2756              : }
    2757              : 
    2758              : // Return the inverse of a range.  Return false if thre is no invert
    2759              : // calculatable.
    2760              : 
    2761              : bool
    2762     80288598 : irange::invert ()
    2763              : {
    2764              :   // UNDEFINED cannot be converted to varying because there is no type
    2765              :   // assocaited.  Callers need to handle these cases.
    2766              :   // Its also ambiguous.. VARYING inverted could also arguably be VARYING
    2767              :   // in some cases. Likewise with UNDEFINED.
    2768     80288598 :   if (undefined_p () || varying_p ())
    2769              :     return false;
    2770              : 
    2771              :   // We always need one more set of bounds to represent an inverse, so
    2772              :   // if we're at the limit, we can't properly represent things.
    2773              :   //
    2774              :   // For instance, to represent the inverse of a 2 sub-range set
    2775              :   // [5, 10][20, 30], we would need a 3 sub-range set
    2776              :   // [-MIN, 4][11, 19][31, MAX].
    2777              :   //
    2778              :   // In this case, return false.
    2779              :   //
    2780              :   // However, if any of the extremes of the range are -MIN/+MAX, we
    2781              :   // know we will not need an extra bound.  For example:
    2782              :   //
    2783              :   //    INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
    2784              :   //    INVERT([-MIN,20][30,MAX]) => [21,29]
    2785     80288598 :   tree ttype = type ();
    2786     80288598 :   unsigned prec = TYPE_PRECISION (ttype);
    2787     80288598 :   signop sign = TYPE_SIGN (ttype);
    2788     80288598 :   wide_int type_min = wi::min_value (prec, sign);
    2789     80288598 :   wide_int type_max = wi::max_value (prec, sign);
    2790     80288598 :   m_bitmask.set_unknown (prec);
    2791              : 
    2792              :   // At this point, we need one extra sub-range to represent the
    2793              :   // inverse.
    2794     80288598 :   maybe_resize (m_num_ranges + 1);
    2795              : 
    2796              :   // The algorithm is as follows.  To calculate INVERT ([a,b][c,d]), we
    2797              :   // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
    2798              :   //
    2799              :   // If there is an over/underflow in the calculation for any
    2800              :   // sub-range, we eliminate that subrange.  This allows us to easily
    2801              :   // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX].  And since
    2802              :   // we eliminate the underflow, only [6, MAX] remains.
    2803     80288598 :   unsigned i = 0;
    2804     80288598 :   wi::overflow_type ovf;
    2805              :   // Construct leftmost range.
    2806     80288598 :   int_range_max orig_range (*this);
    2807     80288598 :   unsigned nitems = 0;
    2808     80288598 :   wide_int tmp;
    2809              :   // If this is going to underflow on the MINUS 1, don't even bother
    2810              :   // checking.  This also handles subtracting one from an unsigned 0,
    2811              :   // which doesn't set the underflow bit.
    2812     80289192 :   if (type_min != orig_range.lower_bound ())
    2813              :     {
    2814     63590084 :       m_base[nitems++] = type_min;
    2815     63590678 :       tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
    2816     63590084 :       m_base[nitems++] = tmp;
    2817     63590084 :       if (ovf)
    2818     16698514 :         nitems = 0;
    2819              :     }
    2820     80288598 :   i++;
    2821              :   // Construct middle ranges if applicable.
    2822     80288598 :   if (orig_range.num_pairs () > 1)
    2823              :     {
    2824              :       unsigned j = i;
    2825     19342674 :       for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
    2826              :         {
    2827              :           // The middle ranges cannot have MAX/MIN, so there's no need
    2828              :           // to check for unsigned overflow on the +1 and -1 here.
    2829      9677128 :           tmp = wi::add (orig_range.m_base[j], 1, sign, &ovf);
    2830      9677128 :           m_base[nitems++] = tmp;
    2831      9677128 :           tmp = subtract_one (orig_range.m_base[j + 1], ttype, ovf);
    2832      9677128 :           m_base[nitems++] = tmp;
    2833      9677128 :           if (ovf)
    2834            0 :             nitems -= 2;
    2835              :         }
    2836              :       i = j;
    2837              :     }
    2838              :   // Construct rightmost range.
    2839              :   //
    2840              :   // However, if this will overflow on the PLUS 1, don't even bother.
    2841              :   // This also handles adding one to an unsigned MAX, which doesn't
    2842              :   // set the overflow bit.
    2843     80288598 :   if (type_max != orig_range.m_base[i])
    2844              :     {
    2845     79293935 :       tmp = add_one (orig_range.m_base[i], ttype, ovf);
    2846     79293935 :       if (!ovf)
    2847              :         {
    2848              :           // Check to see if this inversion is going to work.
    2849     79293935 :           if (nitems / 2 >= m_max_ranges)
    2850              :             {
    2851              :               // No room for the extra field, so revert to the original value
    2852              :               // and return false.
    2853            7 :               *this = orig_range;
    2854            7 :               return false;
    2855              :             }
    2856     79293928 :           m_base[nitems++] = tmp;
    2857     79293928 :           m_base[nitems++] = type_max;
    2858              :         }
    2859              :     }
    2860     80288591 :   m_num_ranges = nitems / 2;
    2861              : 
    2862              :   // We disallow undefined or varying coming in, so the result can
    2863              :   // only be a VR_RANGE.
    2864     80288591 :   gcc_checking_assert (m_kind == VR_RANGE);
    2865              : 
    2866     80288591 :   if (flag_checking)
    2867     80288499 :     verify_range ();
    2868              :   return true;
    2869     80289786 : }
    2870              : 
    2871              : // This routine will take the bounds [LB, UB], and apply the bitmask to those
    2872              : // values such that both bounds satisfy the bitmask.  TRUE is returned
    2873              : // if either bound changes, and they are returned as [NEW_LB, NEW_UB].
    2874              : // If there is an overflow, or if (NEW_UB < NEW_LB), then the entire bound is
    2875              : // to be removed as none of the values are valid.   This is indicated by
    2876              : // teturning TRUE in OVF.   False indicates the bounds are fine.
    2877              : //   ie,   [4, 14] MASK 0xFFFE  VALUE 0x1
    2878              : // means all values must be odd, the new bounds returned will be [5, 13] with
    2879              : // OVF set to FALSE.
    2880              : //   ie,   [4, 4] MASK 0xFFFE  VALUE 0x1
    2881              : // would return TRUE and OVF == TRUE.  The entire subrange should be removed.
    2882              : 
    2883              : bool
    2884    276545273 : irange::snap (const wide_int &lb, const wide_int &ub,
    2885              :               wide_int &new_lb, wide_int &new_ub, bool &ovf)
    2886              : {
    2887    276545273 :   ovf = false;
    2888    276545273 :   int z = wi::ctz (m_bitmask.mask ());
    2889    276545273 :   if (z == 0)
    2890              :     return false;
    2891              : 
    2892              :   // Shortcircuit check for values that are already good.
    2893    331074618 :   if ((((lb ^ m_bitmask.value ()) | (ub ^ m_bitmask.value ()))
    2894    496607275 :        & ~m_bitmask.mask ()) == 0)
    2895              :     return false;
    2896              : 
    2897     16157972 :   const wide_int step = (wi::one (TYPE_PRECISION (type ())) << z);
    2898     16157972 :   const wide_int match_mask = step - 1;
    2899     16157972 :   const wide_int value = m_bitmask.value () & match_mask;
    2900              : 
    2901     16157972 :   wide_int rem_lb = lb & match_mask;
    2902     16157972 :   wide_int offset = (value - rem_lb) & match_mask;
    2903     16157972 :   new_lb = lb + offset;
    2904              :   // Check for overflows at +INF
    2905     16157972 :   if (wi::lt_p (new_lb, lb, TYPE_SIGN (type ())))
    2906              :     {
    2907         1489 :       ovf = true;
    2908         1489 :       return true;
    2909              :     }
    2910              : 
    2911     16156483 :   wide_int rem_ub = ub & match_mask;
    2912     16156483 :   wide_int offset_ub = (rem_ub - value) & match_mask;
    2913     16156483 :   new_ub = ub - offset_ub;
    2914              :   // Check for underflows at -INF
    2915     16156483 :   if (wi::gt_p (new_ub, ub, TYPE_SIGN (type ())))
    2916              :     {
    2917       119956 :       ovf = true;
    2918       119956 :       return true;
    2919              :     }
    2920              : 
    2921              :   // If inverted range is invalid, set overflow to TRUE.
    2922     16036527 :   if (wi::lt_p (new_ub, new_lb, TYPE_SIGN (type ())))
    2923              :     {
    2924        20260 :       ovf = true;
    2925        20260 :       return true;
    2926              :     }
    2927     28621541 :   return (new_lb != lb) || (new_ub != ub);
    2928     32314695 : }
    2929              : 
    2930              : // This method loops through the subranges in THIS, and adjusts any bounds
    2931              : // to satisfy the constraints of the BITMASK.  If a subrange is invalid,
    2932              : // it is removed.   TRUE is returned if there were any changes.
    2933              : 
    2934              : bool
    2935    150499636 : irange::snap_subranges ()
    2936              : {
    2937    150499636 :   bool changed = false;
    2938    150499636 :   int_range_max invalid;
    2939    150499636 :   unsigned x;
    2940    150499636 :   wide_int lb, ub;
    2941    361211981 :   for (x = 0; x < m_num_ranges; x++)
    2942              :     {
    2943    210712345 :       bool ovf;
    2944    210718365 :       if (snap (lower_bound (x), upper_bound (x), lb, ub, ovf))
    2945              :         {
    2946     14507264 :           changed = true;
    2947              :           // Check if this subrange is to be completely removed.
    2948     14507264 :           if (ovf)
    2949              :             {
    2950       131523 :               int_range<1> tmp (type (), lower_bound (x), upper_bound (x));
    2951       131523 :               invalid.union_ (tmp);
    2952       131523 :               continue;
    2953       131523 :             }
    2954     14375789 :           if (lower_bound (x) != lb)
    2955      2439610 :             m_base[x * 2] = lb;
    2956     14375789 :           if (upper_bound (x) != ub)
    2957     12764016 :             m_base[x * 2 + 1] = ub;
    2958              :         }
    2959              :     }
    2960              :   // Remove any subranges which are no invalid.
    2961    150499636 :   if (!invalid.undefined_p ())
    2962              :     {
    2963       128616 :       bool res = invalid.invert ();
    2964       128616 :       gcc_checking_assert (res);
    2965       128616 :       intersect (invalid);
    2966              :     }
    2967    150499636 :   return changed;
    2968    150499675 : }
    2969              : 
    2970              : // If the bitmask has a range representation, intersect this range with
    2971              : // the bitmasks range.  Then ensure all endpoints match the bitmask.
    2972              : // Return TRUE if the range changes at all.
    2973              : 
    2974              : bool
    2975    150499636 : irange::set_range_from_bitmask ()
    2976              : {
    2977    150499636 :   gcc_checking_assert (!undefined_p ());
    2978              :   // Snap subranmges when bitmask is first set.
    2979    150499636 :   snap_subranges ();
    2980    150499636 :   if (undefined_p ())
    2981              :     return true;
    2982              : 
    2983              :   // Calculate the set of ranges valid for the bitmask.
    2984    150499577 :   int_range_max allow;
    2985    150499577 :   if (!m_bitmask.range_from_mask (allow, m_type))
    2986              :     return false;
    2987              :   // And intersect that set of ranges with the current set.
    2988    150337284 :   return intersect (allow);
    2989    150499577 : }
    2990              : 
    2991              : void
    2992    221552011 : irange::update_bitmask (const irange_bitmask &bm)
    2993              : {
    2994    221552011 :   gcc_checking_assert (!undefined_p ());
    2995              : 
    2996              :   // If masks are the same, there is no change.
    2997    221552011 :   if (m_bitmask == bm)
    2998              :     return;
    2999              : 
    3000              :   // Drop VARYINGs with known bits to a plain range.
    3001    102717546 :   if (m_kind == VR_VARYING && !bm.unknown_p ())
    3002     16872787 :     m_kind = VR_RANGE;
    3003              : 
    3004     85844759 :   m_bitmask = bm;
    3005     85844759 :   if (!set_range_from_bitmask ())
    3006     52344993 :     normalize_kind ();
    3007     85844759 :   if (flag_checking)
    3008     85844649 :     verify_range ();
    3009              : }
    3010              : 
    3011              : // Return the bitmask of known bits that includes the bitmask inherent
    3012              : // in the range.
    3013              : 
    3014              : irange_bitmask
    3015   1286854662 : irange::get_bitmask () const
    3016              : {
    3017   1286854662 :   gcc_checking_assert (!undefined_p ());
    3018              : 
    3019              :   // The mask inherent in the range is calculated on-demand.  For
    3020              :   // example, [0,255] does not have known bits set by default.  This
    3021              :   // saves us considerable time, because setting it at creation incurs
    3022              :   // a large penalty for irange::set.  At the time of writing there
    3023              :   // was a 5% slowdown in VRP if we kept the mask precisely up to date
    3024              :   // at all times.  Instead, we default to -1 and set it when
    3025              :   // explicitly requested.  However, this function will always return
    3026              :   // the correct mask.
    3027              :   //
    3028              :   // This also means that the mask may have a finer granularity than
    3029              :   // the range and thus contradict it.  Think of the mask as an
    3030              :   // enhancement to the range.  For example:
    3031              :   //
    3032              :   // [3, 1000] MASK 0xfffffffe VALUE 0x0
    3033              :   //
    3034              :   // 3 is in the range endpoints, but is excluded per the known 0 bits
    3035              :   // in the mask.
    3036              :   //
    3037              :   // See also the note in irange_bitmask::intersect.
    3038   1286930595 :   irange_bitmask bm (type (), lower_bound (), upper_bound ());
    3039   1286854662 :   if (!m_bitmask.unknown_p ())
    3040              :     {
    3041              :       // If the new intersection is unknown, it means there are inconsistent
    3042              :       // bits, so simply return the original bitmask.
    3043    578516138 :       if (!bm.intersect (m_bitmask))
    3044        19376 :         return m_bitmask;
    3045              :     }
    3046   1286835286 :   return bm;
    3047   1286854662 : }
    3048              : 
    3049              : // Set the nonzero bits in R into THIS.  Return TRUE and
    3050              : // normalize the range if anything changed.
    3051              : 
    3052              : void
    3053       838364 : vrange::set_nonzero_bits (const wide_int &bits)
    3054              : {
    3055       838364 :   gcc_checking_assert (!undefined_p ());
    3056       838364 :   irange_bitmask bm (wi::zero (TYPE_PRECISION (type ())), bits);
    3057       838364 :   update_bitmask (bm);
    3058       838364 : }
    3059              : 
    3060              : // Return the nonzero bits in R.
    3061              : 
    3062              : wide_int
    3063    232086131 : vrange::get_nonzero_bits () const
    3064              : {
    3065    232086131 :   gcc_checking_assert (!undefined_p ());
    3066    232086131 :   irange_bitmask bm = get_bitmask ();
    3067    232152280 :   return bm.value () | bm.mask ();
    3068    232086131 : }
    3069              : 
    3070              : // Intersect the bitmask in R into THIS and normalize the range.
    3071              : // Return TRUE if the intersection changed anything.
    3072              : 
    3073              : bool
    3074    602691196 : irange::intersect_bitmask (const irange &r)
    3075              : {
    3076    602691196 :   gcc_checking_assert (!undefined_p () && !r.undefined_p ());
    3077              : 
    3078              :   // If the bitmasks are the same, do nothing.
    3079    602691196 :   if (m_bitmask == r.m_bitmask)
    3080              :     return false;
    3081              : 
    3082    221031312 :   irange_bitmask bm = get_bitmask ();
    3083    221031312 :   irange_bitmask save = bm;
    3084    221031312 :   if (!bm.intersect (r.get_bitmask ()))
    3085              :     {
    3086        34613 :       set_undefined ();
    3087        34613 :       return true;
    3088              :     }
    3089              : 
    3090              :   // If the new mask is the same, there is no change.
    3091    220996699 :   if (m_bitmask == bm)
    3092              :     return false;
    3093              : 
    3094     64654877 :   m_bitmask = bm;
    3095     64654877 :   if (!set_range_from_bitmask ())
    3096     64166803 :     normalize_kind ();
    3097     64654877 :   if (flag_checking)
    3098     64654712 :     verify_range ();
    3099              :   return true;
    3100    221031312 : }
    3101              : 
    3102              : // Union the bitmask in R into THIS.  Return TRUE and normalize the
    3103              : // range if anything changed.
    3104              : 
    3105              : bool
    3106    327610401 : irange::union_bitmask (const irange &r)
    3107              : {
    3108    327610401 :   gcc_checking_assert (!undefined_p () && !r.undefined_p ());
    3109              : 
    3110    327610401 :   if (m_bitmask == r.m_bitmask)
    3111              :     return false;
    3112              : 
    3113     14349762 :   irange_bitmask bm = get_bitmask ();
    3114     14349762 :   irange_bitmask save = bm;
    3115     14349762 :   bm.union_ (r.get_bitmask ());
    3116     24489028 :   if (save == bm && (!bm.unknown_p () || m_bitmask.unknown_p ()))
    3117              :     return false;
    3118              : 
    3119      4210496 :   m_bitmask = bm;
    3120              : 
    3121              :   // Updating m_bitmask may still yield a semantic bitmask (as
    3122              :   // returned by get_bitmask) which is functionally equivalent to what
    3123              :   // we originally had.  In which case, there's still no change.
    3124      4210496 :   if (save == get_bitmask ())
    3125              :     return false;
    3126              : 
    3127              :   // No need to call set_range_from_mask, because we'll never
    3128              :   // narrow the range.  Besides, it would cause endless recursion
    3129              :   // because of the union_ in set_range_from_mask.
    3130      4210496 :   normalize_kind ();
    3131      4210496 :   return true;
    3132     14349762 : }
    3133              : 
    3134              : tree
    3135      9284855 : irange::lbound () const
    3136              : {
    3137      9284855 :   return wide_int_to_tree (type (), lower_bound ());
    3138              : }
    3139              : 
    3140              : tree
    3141       307245 : irange::ubound () const
    3142              : {
    3143       307245 :   return wide_int_to_tree (type (), upper_bound ());
    3144              : }
    3145              : 
    3146              : void
    3147  11862725919 : irange_bitmask::verify_mask () const
    3148              : {
    3149  11862725919 :   gcc_assert (m_value.get_precision () == m_mask.get_precision ());
    3150  11862725919 :   gcc_checking_assert (wi::bit_and (m_mask, m_value) == 0);
    3151  11862725919 : }
    3152              : 
    3153              : void
    3154            0 : dump_value_range (FILE *file, const vrange *vr)
    3155              : {
    3156            0 :   vr->dump (file);
    3157            0 : }
    3158              : 
    3159              : DEBUG_FUNCTION void
    3160            0 : debug (const vrange *vr)
    3161              : {
    3162            0 :   dump_value_range (stderr, vr);
    3163            0 :   fprintf (stderr, "\n");
    3164            0 : }
    3165              : 
    3166              : DEBUG_FUNCTION void
    3167            0 : debug (const vrange &vr)
    3168              : {
    3169            0 :   debug (&vr);
    3170            0 : }
    3171              : 
    3172              : /* Return true, if VAL1 and VAL2 are equal values for VRP purposes.  */
    3173              : 
    3174              : bool
    3175    168952978 : vrp_operand_equal_p (const_tree val1, const_tree val2)
    3176              : {
    3177    168952978 :   if (val1 == val2)
    3178              :     return true;
    3179     62207214 :   if (!val1 || !val2 || !operand_equal_p (val1, val2, 0))
    3180     61436204 :     return false;
    3181              :   return true;
    3182              : }
    3183              : 
    3184              : #define DEFINE_INT_RANGE_INSTANCE(N)                                    \
    3185              :   template int_range<N>::int_range(tree_node *,                           \
    3186              :                                    const wide_int &,                        \
    3187              :                                    const wide_int &,                        \
    3188              :                                    value_range_kind);                   \
    3189              :   template int_range<N>::int_range(tree);                         \
    3190              :   template int_range<N>::int_range(const irange &);           \
    3191              :   template int_range<N>::int_range(const int_range &);                        \
    3192              :   template int_range<N>& int_range<N>::operator= (const int_range &);
    3193              : 
    3194              : DEFINE_INT_RANGE_INSTANCE(1)
    3195              : DEFINE_INT_RANGE_INSTANCE(2)
    3196              : DEFINE_INT_RANGE_INSTANCE(3)
    3197              : DEFINE_INT_RANGE_INSTANCE(255)
    3198              : 
    3199              : #if CHECKING_P
    3200              : #include "selftest.h"
    3201              : 
    3202              : #define INT(x) wi::shwi ((x), TYPE_PRECISION (integer_type_node))
    3203              : #define UINT(x) wi::uhwi ((x), TYPE_PRECISION (unsigned_type_node))
    3204              : #define SCHAR(x) wi::shwi ((x), TYPE_PRECISION (signed_char_type_node))
    3205              : 
    3206              : namespace selftest
    3207              : {
    3208              : 
    3209              : static int_range<2>
    3210          584 : range (tree type, int a, int b, value_range_kind kind = VR_RANGE)
    3211              : {
    3212          584 :   wide_int w1, w2;
    3213          584 :   if (TYPE_UNSIGNED (type))
    3214              :     {
    3215           40 :       w1 = wi::uhwi (a, TYPE_PRECISION (type));
    3216           40 :       w2 = wi::uhwi (b, TYPE_PRECISION (type));
    3217              :     }
    3218              :   else
    3219              :     {
    3220          544 :       w1 = wi::shwi (a, TYPE_PRECISION (type));
    3221          544 :       w2 = wi::shwi (b, TYPE_PRECISION (type));
    3222              :     }
    3223          584 :   return int_range<2> (type, w1, w2, kind);
    3224          584 : }
    3225              : 
    3226              : static int_range<2>
    3227          540 : range_int (int a, int b, value_range_kind kind = VR_RANGE)
    3228              : {
    3229            0 :   return range (integer_type_node, a, b, kind);
    3230              : }
    3231              : 
    3232              : static int_range<2>
    3233            8 : range_uint (int a, int b, value_range_kind kind = VR_RANGE)
    3234              : {
    3235            4 :   return range (unsigned_type_node, a, b, kind);
    3236              : }
    3237              : 
    3238              : static int_range<2>
    3239            8 : range_uint128 (int a, int b, value_range_kind kind = VR_RANGE)
    3240              : {
    3241            8 :   tree u128_type_node = build_nonstandard_integer_type (128, 1);
    3242            8 :   return range (u128_type_node, a, b, kind);
    3243              : }
    3244              : 
    3245              : static int_range<2>
    3246           12 : range_uchar (int a, int b, value_range_kind kind = VR_RANGE)
    3247              : {
    3248            0 :   return range (unsigned_char_type_node, a, b, kind);
    3249              : }
    3250              : 
    3251              : static int_range<2>
    3252            4 : range_char (int a, int b, value_range_kind kind = VR_RANGE)
    3253              : {
    3254            0 :   return range (signed_char_type_node, a, b, kind);
    3255              : }
    3256              : 
    3257              : static int_range<3>
    3258           44 : build_range3 (int a, int b, int c, int d, int e, int f)
    3259              : {
    3260           44 :   int_range<3> i1 = range_int (a, b);
    3261           44 :   int_range<3> i2 = range_int (c, d);
    3262           44 :   int_range<3> i3 = range_int (e, f);
    3263           44 :   i1.union_ (i2);
    3264           44 :   i1.union_ (i3);
    3265           88 :   return i1;
    3266           44 : }
    3267              : 
    3268              : static void
    3269            4 : range_tests_irange3 ()
    3270              : {
    3271            4 :   int_range<3> r0, r1, r2;
    3272            4 :   int_range<3> i1, i2, i3;
    3273              : 
    3274              :   // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
    3275            4 :   r0 = range_int (10, 20);
    3276            4 :   r1 = range_int (5, 8);
    3277            4 :   r0.union_ (r1);
    3278            4 :   r1 = range_int (1, 3);
    3279            4 :   r0.union_ (r1);
    3280            4 :   ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
    3281              : 
    3282              :   // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
    3283            4 :   r1 = range_int (-5, 0);
    3284            4 :   r0.union_ (r1);
    3285            4 :   ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
    3286              : 
    3287              :   // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
    3288            4 :   r1 = range_int (50, 60);
    3289            4 :   r0 = range_int (10, 20);
    3290            4 :   r0.union_ (range_int (30, 40));
    3291            4 :   r0.union_ (r1);
    3292            4 :   ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
    3293              :   // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
    3294            4 :   r1 = range_int (70, 80);
    3295            4 :   r0.union_ (r1);
    3296              : 
    3297            4 :   r2 = build_range3 (10, 20, 30, 40, 50, 60);
    3298            4 :   r2.union_ (range_int (70, 80));
    3299            4 :   ASSERT_TRUE (r0 == r2);
    3300              : 
    3301              :   // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
    3302            4 :   r0 = build_range3 (10, 20, 30, 40, 50, 60);
    3303            4 :   r1 = range_int (6, 35);
    3304            4 :   r0.union_ (r1);
    3305            4 :   r1 = range_int (6, 40);
    3306            4 :   r1.union_ (range_int (50, 60));
    3307            4 :   ASSERT_TRUE (r0 == r1);
    3308              : 
    3309              :   // [10,20][30,40][50,60] U [6,60] => [6,60].
    3310            4 :   r0 = build_range3 (10, 20, 30, 40, 50, 60);
    3311            4 :   r1 = range_int (6, 60);
    3312            4 :   r0.union_ (r1);
    3313            4 :   ASSERT_TRUE (r0 == range_int (6, 60));
    3314              : 
    3315              :   // [10,20][30,40][50,60] U [6,70] => [6,70].
    3316            4 :   r0 = build_range3 (10, 20, 30, 40, 50, 60);
    3317            4 :   r1 = range_int (6, 70);
    3318            4 :   r0.union_ (r1);
    3319            4 :   ASSERT_TRUE (r0 == range_int (6, 70));
    3320              : 
    3321              :   // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
    3322            4 :   r0 = build_range3 (10, 20, 30, 40, 50, 60);
    3323            4 :   r1 = range_int (35, 70);
    3324            4 :   r0.union_ (r1);
    3325            4 :   r1 = range_int (10, 20);
    3326            4 :   r1.union_ (range_int (30, 70));
    3327            4 :   ASSERT_TRUE (r0 == r1);
    3328              : 
    3329              :   // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
    3330            4 :   r0 = build_range3 (10, 20, 30, 40, 50, 60);
    3331            4 :   r1 = range_int (15, 35);
    3332            4 :   r0.union_ (r1);
    3333            4 :   r1 = range_int (10, 40);
    3334            4 :   r1.union_ (range_int (50, 60));
    3335            4 :   ASSERT_TRUE (r0 == r1);
    3336              : 
    3337              :   // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
    3338            4 :   r0 = build_range3 (10, 20, 30, 40, 50, 60);
    3339            4 :   r1 = range_int (35, 35);
    3340            4 :   r0.union_ (r1);
    3341            4 :   ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
    3342            4 : }
    3343              : 
    3344              : static void
    3345            4 : range_tests_int_range_max ()
    3346              : {
    3347            4 :   int_range_max big;
    3348            4 :   unsigned int nrange;
    3349              : 
    3350              :   // Build a huge multi-range range.
    3351          208 :   for (nrange = 0; nrange < 50; ++nrange)
    3352              :     {
    3353          200 :       int_range<1> tmp = range_int (nrange*10, nrange *10 + 5);
    3354          200 :       big.union_ (tmp);
    3355          200 :     }
    3356            4 :   ASSERT_TRUE (big.num_pairs () == nrange);
    3357              : 
    3358              :   // Verify that we can copy it without loosing precision.
    3359            4 :   int_range_max copy (big);
    3360            4 :   ASSERT_TRUE (copy.num_pairs () == nrange);
    3361              : 
    3362              :   // Inverting it should produce one more sub-range.
    3363            4 :   big.invert ();
    3364            4 :   ASSERT_TRUE (big.num_pairs () == nrange + 1);
    3365              : 
    3366            4 :   int_range<1> tmp = range_int (5, 37);
    3367            4 :   big.intersect (tmp);
    3368            4 :   ASSERT_TRUE (big.num_pairs () == 4);
    3369              : 
    3370              :   // Cannot resize tmp, and the invert does not fit,
    3371            4 :   ASSERT_FALSE (tmp.invert ());
    3372              : 
    3373              :   // Test that [10,10][20,20] does NOT contain 15.
    3374            4 :   {
    3375            4 :     int_range_max i1 = range_int (10, 10);
    3376            4 :     int_range_max i2 = range_int (20, 20);
    3377            4 :     i1.union_ (i2);
    3378            4 :     ASSERT_FALSE (i1.contains_p (INT (15)));
    3379            4 :   }
    3380            4 : }
    3381              : 
    3382              : // Simulate -fstrict-enums where the domain of a type is less than the
    3383              : // underlying type.
    3384              : 
    3385              : static void
    3386            4 : range_tests_strict_enum ()
    3387              : {
    3388              :   // The enum can only hold [0, 3].
    3389            4 :   tree rtype = copy_node (unsigned_type_node);
    3390            4 :   TYPE_MIN_VALUE (rtype) = build_int_cstu (rtype, 0);
    3391            4 :   TYPE_MAX_VALUE (rtype) = build_int_cstu (rtype, 3);
    3392              : 
    3393              :   // Test that even though vr1 covers the strict enum domain ([0, 3]),
    3394              :   // it does not cover the domain of the underlying type.
    3395            4 :   int_range<1> vr1 = range (rtype, 0, 1);
    3396            4 :   int_range<1> vr2 = range (rtype, 2, 3);
    3397            4 :   vr1.union_ (vr2);
    3398            4 :   ASSERT_TRUE (vr1 == range (rtype, 0, 3));
    3399            4 :   ASSERT_FALSE (vr1.varying_p ());
    3400              : 
    3401              :   // Test that copying to a multi-range does not change things.
    3402            4 :   int_range<2> ir1 (vr1);
    3403            4 :   ASSERT_TRUE (ir1 == vr1);
    3404            4 :   ASSERT_FALSE (ir1.varying_p ());
    3405              : 
    3406              :   // The same test as above, but using TYPE_{MIN,MAX}_VALUE instead of [0,3].
    3407            8 :   vr1 = int_range<2> (rtype,
    3408            8 :                       wi::to_wide (TYPE_MIN_VALUE (rtype)),
    3409           12 :                       wi::to_wide (TYPE_MAX_VALUE (rtype)));
    3410            4 :   ir1 = vr1;
    3411            4 :   ASSERT_TRUE (ir1 == vr1);
    3412            4 :   ASSERT_FALSE (ir1.varying_p ());
    3413            4 : }
    3414              : 
    3415              : // Test that range bounds are "snapped" to where they are expected to be.
    3416              : 
    3417              : static void
    3418          104 : assert_snap_result (int lb_val, int ub_val,
    3419              :                     int expected_lb, int expected_ub,
    3420              :                     unsigned mask_val, unsigned value_val,
    3421              :                     tree type)
    3422              : {
    3423          104 :   wide_int lb = wi::shwi (lb_val, TYPE_PRECISION (type));
    3424          104 :   wide_int ub = wi::shwi (ub_val, TYPE_PRECISION (type));
    3425          104 :   wide_int new_lb, new_ub;
    3426              : 
    3427          208 :   irange_bitmask bm (wi::uhwi (value_val, TYPE_PRECISION (type)),
    3428          208 :                      wi::uhwi (mask_val, TYPE_PRECISION (type)));
    3429              : 
    3430          104 :   int_range_max r (type);
    3431          104 :   r.set (type, lb, ub);
    3432          104 :   r.update_bitmask (bm);
    3433              : 
    3434          104 :   if (TYPE_SIGN (type) == SIGNED && expected_ub < expected_lb)
    3435           20 :     gcc_checking_assert (r.undefined_p ());
    3436           84 :   else if (TYPE_SIGN (type) == UNSIGNED
    3437           84 :            && ((unsigned)expected_ub < (unsigned)expected_lb))
    3438           16 :     gcc_checking_assert (r.undefined_p ());
    3439              :   else
    3440              :     {
    3441           68 :       gcc_checking_assert (wi::eq_p (r.lower_bound (),
    3442              :                                      wi::shwi (expected_lb,
    3443              :                                                TYPE_PRECISION (type))));
    3444          136 :       gcc_checking_assert (wi::eq_p (r.upper_bound (),
    3445              :                                      wi::shwi (expected_ub,
    3446              :                                                TYPE_PRECISION (type))));
    3447              :     }
    3448          104 : }
    3449              : 
    3450              : 
    3451              : // Run a selection of tests that confirm, bounds are snapped as expected.
    3452              : // We only test individual pairs, multiple pairs use the same snapping
    3453              : // routine as single pairs.
    3454              : 
    3455              : static void
    3456            4 : test_irange_snap_bounds ()
    3457              : {
    3458            4 :   tree u32 = unsigned_type_node;
    3459            4 :   tree s32 = integer_type_node;
    3460            4 :   tree s8 = build_nonstandard_integer_type (8, /*unsigned=*/ 0);
    3461            4 :   tree s1 = build_nonstandard_integer_type (1, /*unsigned=*/ 0);
    3462            4 :   tree u1 = build_nonstandard_integer_type (1, /*unsigned=*/ 1);
    3463              : 
    3464              :   // Basic aligned range: even-only
    3465            4 :   assert_snap_result (5, 15, 6, 14, 0xE, 0x0, u32);
    3466              :   // Singleton that doesn't match mask: undefined.
    3467            4 :   assert_snap_result (7, 7, 1, 0, 0xFFFFFFFE, 0x0, u32);
    3468              :   // 8-bit signed char, mask 0xF0 (i.e. step of 16).
    3469            4 :   assert_snap_result (-100, 100, -96, 96, 0xF0, 0x00, s8);
    3470              :   // Already aligned range: no change.
    3471            4 :   assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, u32);
    3472              :   // Negative range, step 16 alignment (s32).
    3473            4 :   assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
    3474              :   // Negative range, step 16 alignment (trailing-zero aligned mask).
    3475            4 :   assert_snap_result (-123, -17, -112, -32, 0xFFFFFFF0, 0x00, s32);
    3476              :   // s8, 16-alignment mask, value = 0 (valid).
    3477            4 :   assert_snap_result (-50, 10, -48, 0, 0xF0, 0x00, s8);
    3478              :   // No values in range [-3,2] match alignment except 0.
    3479            4 :   assert_snap_result (-3, 2, 0, 0, 0xF8, 0x00, s8);
    3480              :   // No values in range [-3,2] match alignment — undefined.
    3481            4 :   assert_snap_result (-3, 2, 1, 0, 0xF8, 0x04, s8);
    3482              :   // Already aligned range: no change.
    3483            4 :   assert_snap_result (0, 240, 0, 240, 0xF0, 0x00, s32);
    3484              :   // 1-bit signed: only -1 allowed (0b1).
    3485            4 :   assert_snap_result (-1, 0, -1, -1, 0x00, 0x01, s1);
    3486              :   // 1-bit signed: only 0 allowed (0b0).
    3487            4 :   assert_snap_result (-1, 0, 0, 0, 0x00, 0x00, s1);
    3488              :   // 1-bit signed: no match (invalid case).
    3489            4 :   assert_snap_result (-1, -1, 1, 0, 0x00, 0x00, s1);
    3490              :   // 1-bit signed: no match (invalid case).
    3491            4 :   assert_snap_result (0, 0, 1, 0, 0x00, 0x01, s1);
    3492              :   // 1-bit unsigned: only 1 allowed.
    3493            4 :   assert_snap_result (0, 1, 1, 1, 0x00, 0x01, u1);
    3494              :   // 1-bit unsigned: only 0 allowed.
    3495            4 :   assert_snap_result (0, 1, 0, 0, 0x00, 0x00, u1);
    3496              :   // 1-bit unsigned: no match (invalid case).
    3497            4 :   assert_snap_result (1, 1, 1, 0, 0x00, 0x00, u1);
    3498              :   // 1-bit unsigned: no match (invalid case).
    3499            4 :   assert_snap_result (0, 0, 1, 0, 0x00, 0x01, u1);
    3500              :   // Unsigned: Near overflow, even alignment.
    3501            4 :   assert_snap_result (UINT_MAX - 6, UINT_MAX, UINT_MAX - 5, UINT_MAX - 1,
    3502              :                       0xFFFFFFFE, 0x00, u32);
    3503              :   // Unsigned: Wraparound-like range — no valid snapped values.
    3504            4 :   assert_snap_result (UINT_MAX - 5, UINT_MAX, 1, 0, 0xFFFFFFF0, 0x00, u32);
    3505              :   // Signed: Near INT_MAX, 8-aligned.
    3506            4 :   assert_snap_result (INT_MAX - 18, INT_MAX, INT_MAX - 15, INT_MAX - 7,
    3507              :                       0xFFFFFFF8, 0x00, s32);
    3508              :   // Signed: Near INT_MIN, 16-aligned.
    3509            4 :   assert_snap_result (INT_MIN, INT_MIN + 30, INT_MIN, INT_MIN + 16,
    3510              :                       0xFFFFFFF0, 0x00, s32);
    3511              :   // Signed: Full domain, 4-aligned.
    3512            4 :   assert_snap_result (-128, 127, -128, 124, 0xFC, 0x00, s8);
    3513              :   // Singleton at INT_MIN that doesn’t match alignment — undefined
    3514            4 :   assert_snap_result (INT_MIN, INT_MIN, 1, 0, 0xFFFFFFFE, 0x01, s32);
    3515              :   // Range at INT_MIN that doesn’t match alignment — undefined.
    3516            4 :   assert_snap_result (INT_MIN, INT_MIN + 10, 1, 0, 0xFFFFFFF0, 0x0F, s32);
    3517              :   // Unsigned: Full domain, 256-aligned.
    3518            4 :   assert_snap_result (0, UINT_MAX, 0, UINT_MAX & ~255, 0xFFFFFF00, 0x00, u32);
    3519            4 : }
    3520              : 
    3521              : static void
    3522            4 : range_tests_misc ()
    3523              : {
    3524            4 :   bool res;
    3525            4 :   tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
    3526            4 :   int_range<2> i1, i2, i3;
    3527            4 :   int_range<2> r0, r1, rold;
    3528              : 
    3529              :   // Test 1-bit signed integer union.
    3530              :   // [-1,-1] U [0,0] = VARYING.
    3531            4 :   tree one_bit_type = build_nonstandard_integer_type (1, 0);
    3532            4 :   wide_int one_bit_min = irange_val_min (one_bit_type);
    3533            4 :   wide_int one_bit_max = irange_val_max (one_bit_type);
    3534            4 :   {
    3535            4 :     int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
    3536            4 :     int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
    3537            4 :     max.union_ (min);
    3538            4 :     ASSERT_TRUE (max.varying_p ());
    3539            4 :   }
    3540              :   // Test that we can set a range of true+false for a 1-bit signed int.
    3541            4 :   r0 = range_true_and_false (one_bit_type);
    3542              : 
    3543              :   // Test inversion of 1-bit signed integers.
    3544            4 :   {
    3545            4 :     int_range<2> min = int_range<2> (one_bit_type, one_bit_min, one_bit_min);
    3546            4 :     int_range<2> max = int_range<2> (one_bit_type, one_bit_max, one_bit_max);
    3547            4 :     int_range<2> t;
    3548            4 :     t = min;
    3549            4 :     res = t.invert ();
    3550            4 :     ASSERT_TRUE (res && t == max);
    3551            4 :     t = max;
    3552            4 :     res = t.invert ();
    3553            4 :     ASSERT_TRUE (res && t == min);
    3554            4 :   }
    3555              : 
    3556              :   // Test that NOT(255) is [0..254] in 8-bit land.
    3557            4 :   int_range<1> not_255 = range_uchar (255, 255, VR_ANTI_RANGE);
    3558            4 :   ASSERT_TRUE (not_255 == range_uchar (0, 254));
    3559              : 
    3560              :   // Test that NOT(0) is [1..255] in 8-bit land.
    3561            4 :   int_range<2> not_zero;
    3562            4 :   not_zero.set_nonzero (unsigned_char_type_node);
    3563            4 :   ASSERT_TRUE (not_zero == range_uchar (1, 255));
    3564              : 
    3565              :   // Check that [0,127][0x..ffffff80,0x..ffffff]
    3566              :   //  => ~[128, 0x..ffffff7f].
    3567            4 :   r0 = range_uint128 (0, 127);
    3568            4 :   wide_int high = wi::minus_one (128);
    3569              :   // low = -1 - 127 => 0x..ffffff80.
    3570            4 :   wide_int low = wi::sub (high, wi::uhwi (127, 128));
    3571            4 :   r1 = int_range<1> (u128_type, low, high); // [0x..ffffff80, 0x..ffffffff]
    3572              :   // r0 = [0,127][0x..ffffff80,0x..fffffff].
    3573            4 :   r0.union_ (r1);
    3574              :   // r1 = [128, 0x..ffffff7f].
    3575           12 :   r1 = int_range<1> (u128_type,
    3576            8 :                      wi::uhwi (128, 128),
    3577            8 :                      wi::sub (wi::minus_one (128), wi::uhwi (128, 128)));
    3578            4 :   res = r0.invert ();
    3579            4 :   ASSERT_TRUE (res && r0 == r1);
    3580              : 
    3581            4 :   r0.set_varying (integer_type_node);
    3582            4 :   wide_int minint = r0.lower_bound ();
    3583            4 :   wide_int maxint = r0.upper_bound ();
    3584              : 
    3585            4 :   r0.set_varying (short_integer_type_node);
    3586              : 
    3587            4 :   r0.set_varying (unsigned_type_node);
    3588            4 :   wide_int maxuint = r0.upper_bound ();
    3589              : 
    3590              :   // Check that ~[0,5] => [6,MAX] for unsigned int.
    3591            4 :   r0 = range_uint (0, 5);
    3592            4 :   res = r0.invert ();
    3593            4 :   ASSERT_TRUE (res);
    3594            4 :   ASSERT_TRUE (r0 == int_range<1> (unsigned_type_node,
    3595              :                                    wi::uhwi (6, TYPE_PRECISION (unsigned_type_node)),
    3596              :                                    maxuint));
    3597              : 
    3598              :   // Check that ~[10,MAX] => [0,9] for unsigned int.
    3599            8 :   r0 = int_range<1> (unsigned_type_node,
    3600            4 :                      wi::uhwi (10, TYPE_PRECISION (unsigned_type_node)),
    3601            8 :                      maxuint);
    3602            4 :   res = r0.invert ();
    3603            8 :   ASSERT_TRUE (res && r0 == range_uint (0, 9));
    3604              : 
    3605              :   // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
    3606            4 :   r0 = range_uint128 (0, 5, VR_ANTI_RANGE);
    3607            4 :   r1 = int_range<1> (u128_type, wi::uhwi (6, 128), wi::minus_one (128));
    3608            4 :   ASSERT_TRUE (r0 == r1);
    3609              : 
    3610              :   // Check that [~5] is really [-MIN,4][6,MAX].
    3611            4 :   r0 = range_int (5, 5, VR_ANTI_RANGE);
    3612            4 :   r1 = int_range<1> (integer_type_node, minint, INT (4));
    3613            4 :   r1.union_ (int_range<1> (integer_type_node, INT (6), maxint));
    3614            4 :   ASSERT_FALSE (r1.undefined_p ());
    3615            4 :   ASSERT_TRUE (r0 == r1);
    3616              : 
    3617            4 :   r1 = range_int (5, 5);
    3618            4 :   int_range<2> r2 (r1);
    3619            4 :   ASSERT_TRUE (r1 == r2);
    3620              : 
    3621            4 :   r1 = range_int (5, 10);
    3622              : 
    3623            4 :   r1 = range_int (5, 10);
    3624            4 :   ASSERT_TRUE (r1.contains_p (INT (7)));
    3625              : 
    3626            4 :   r1 = range_char (0, 20);
    3627            4 :   ASSERT_TRUE (r1.contains_p (SCHAR(15)));
    3628            4 :   ASSERT_FALSE (r1.contains_p (SCHAR(300)));
    3629              : 
    3630              :   // NOT([10,20]) ==> [-MIN,9][21,MAX].
    3631            4 :   r0 = r1 = range_int (10, 20);
    3632            4 :   r2 = int_range<1> (integer_type_node, minint, INT(9));
    3633            4 :   r2.union_ (int_range<1> (integer_type_node, INT(21), maxint));
    3634            4 :   ASSERT_FALSE (r2.undefined_p ());
    3635            4 :   res = r1.invert ();
    3636            4 :   ASSERT_TRUE (res && r1 == r2);
    3637              :   // Test that NOT(NOT(x)) == x.
    3638            4 :   res = r2.invert ();
    3639            4 :   ASSERT_TRUE (res && r0 == r2);
    3640              : 
    3641              :   // Test that booleans and their inverse work as expected.
    3642            4 :   r0.set_zero (boolean_type_node);
    3643            4 :   ASSERT_TRUE (r0 == range_false ());
    3644            4 :   res = r0.invert ();
    3645            4 :   ASSERT_TRUE (res && r0 == range_true ());
    3646              : 
    3647              :   // Make sure NULL and non-NULL of pointer types work, and that
    3648              :   // inverses of them are consistent.
    3649            4 :   tree voidp = build_pointer_type (void_type_node);
    3650            4 :   prange p0;
    3651            4 :   p0.set_zero (voidp);
    3652            4 :   prange p1 = p0;
    3653            4 :   res = p0.invert ();
    3654            4 :   ASSERT_TRUE (res);
    3655            4 :   res = p0.invert ();
    3656            4 :   ASSERT_TRUE (res && p0 == p1);
    3657              : 
    3658              :   // The intersection of:
    3659              :   //    [0, +INF] MASK 0xff..00 VALUE 0xf8
    3660              :   //    [0, +INF] MASK 0xff..00 VALUE 0x00
    3661              :   // is [0, +INF] MASK 0xff..ff VALUE 0x00, which is VARYING.
    3662              :   // Test that we normalized to VARYING.
    3663            4 :   unsigned prec = TYPE_PRECISION (voidp);
    3664            4 :   p0.set_varying (voidp);
    3665            4 :   wide_int mask = wi::mask (8, true, prec);
    3666            4 :   wide_int value = wi::uhwi (0xf8, prec);
    3667            4 :   irange_bitmask bm (wi::uhwi (0xf8, prec), mask);
    3668            4 :   p0.update_bitmask (bm);
    3669            4 :   p1.set_varying (voidp);
    3670            4 :   bm = irange_bitmask (wi::zero (prec), mask);
    3671            4 :   p1.update_bitmask (bm);
    3672            4 :   p0.intersect (p1);
    3673              : 
    3674              :   // [10,20] U [15, 30] => [10, 30].
    3675            4 :   r0 = range_int (10, 20);
    3676            4 :   r1 = range_int (15, 30);
    3677            4 :   r0.union_ (r1);
    3678            4 :   ASSERT_TRUE (r0 == range_int (10, 30));
    3679              : 
    3680              :   // [15,40] U [] => [15,40].
    3681            4 :   r0 = range_int (15, 40);
    3682            4 :   r1.set_undefined ();
    3683            4 :   r0.union_ (r1);
    3684            4 :   ASSERT_TRUE (r0 == range_int (15, 40));
    3685              : 
    3686              :   // [10,20] U [10,10] => [10,20].
    3687            4 :   r0 = range_int (10, 20);
    3688            4 :   r1 = range_int (10, 10);
    3689            4 :   r0.union_ (r1);
    3690            4 :   ASSERT_TRUE (r0 == range_int (10, 20));
    3691              : 
    3692              :   // [10,20] U [9,9] => [9,20].
    3693            4 :   r0 = range_int (10, 20);
    3694            4 :   r1 = range_int (9, 9);
    3695            4 :   r0.union_ (r1);
    3696            4 :   ASSERT_TRUE (r0 == range_int (9, 20));
    3697              : 
    3698              :   // [10,20] ^ [15,30] => [15,20].
    3699            4 :   r0 = range_int (10, 20);
    3700            4 :   r1 = range_int (15, 30);
    3701            4 :   r0.intersect (r1);
    3702            4 :   ASSERT_TRUE (r0 == range_int (15, 20));
    3703              : 
    3704              :   // Test the internal sanity of wide_int's wrt HWIs.
    3705            4 :   ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
    3706              :                               TYPE_SIGN (boolean_type_node))
    3707              :                == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
    3708              : 
    3709              :   // Test zero_p().
    3710            4 :   r0 = range_int (0, 0);
    3711            4 :   ASSERT_TRUE (r0.zero_p ());
    3712              : 
    3713              :   // Test contains_zero_p().
    3714            4 :   r0 = range_int (0, 0);
    3715            4 :   res = r0.invert ();
    3716            4 :   ASSERT_TRUE (res);
    3717            4 :   ASSERT_FALSE (r0.contains_zero_p ());
    3718              : 
    3719              :   // r0 = ~[1,1]
    3720            4 :   r0 = range_int (1, 1, VR_ANTI_RANGE);
    3721              :   // r1 = ~[3,3]
    3722            4 :   r1 = range_int (3, 3, VR_ANTI_RANGE);
    3723              : 
    3724              :   // vv = [0,0][2,2][4, MAX]
    3725            4 :   int_range<3> vv = r0;
    3726            4 :   vv.intersect (r1);
    3727              : 
    3728            4 :   ASSERT_TRUE (vv.contains_p (UINT (2)));
    3729            4 :   ASSERT_TRUE (vv.num_pairs () == 3);
    3730              : 
    3731            4 :   r0 = range_int (1, 1);
    3732              :   // And union it with  [0,0][2,2][4,MAX] multi range
    3733            4 :   r0.union_ (vv);
    3734              :   // The result should be [0,2][4,MAX], or ~[3,3]  but it must contain 2
    3735            4 :   ASSERT_TRUE (r0.contains_p (INT (2)));
    3736            4 : }
    3737              : 
    3738              : static void
    3739            4 : range_tests_nonzero_bits ()
    3740              : {
    3741            4 :   int_range<8> r0, r1;
    3742              : 
    3743              :   // Adding nonzero bits to a varying drops the varying.
    3744            4 :   r0.set_varying (integer_type_node);
    3745            4 :   r0.set_nonzero_bits (INT (255));
    3746            4 :   ASSERT_TRUE (!r0.varying_p ());
    3747              : 
    3748              :   // Test contains_p with nonzero bits.
    3749            4 :   r0.set_zero (integer_type_node);
    3750            4 :   ASSERT_TRUE (r0.contains_p (INT (0)));
    3751            4 :   ASSERT_FALSE (r0.contains_p (INT (1)));
    3752            4 :   r0.set_nonzero_bits (INT (0xfe));
    3753            4 :   ASSERT_FALSE (r0.contains_p (INT (0x100)));
    3754            4 :   ASSERT_FALSE (r0.contains_p (INT (0x3)));
    3755              : 
    3756              :   // Union of nonzero bits.
    3757            4 :   r0.set_varying (integer_type_node);
    3758            4 :   r0.set_nonzero_bits (INT (0xf0));
    3759            4 :   r1.set_varying (integer_type_node);
    3760            4 :   r1.set_nonzero_bits (INT (0xf));
    3761            4 :   r0.union_ (r1);
    3762            4 :   ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
    3763              : 
    3764              :   // Intersect of nonzero bits.
    3765            4 :   r0 = range_int (0, 255);
    3766            4 :   r0.set_nonzero_bits (INT (0xfe));
    3767            4 :   r1.set_varying (integer_type_node);
    3768            4 :   r1.set_nonzero_bits (INT (0xf0));
    3769            4 :   r0.intersect (r1);
    3770            4 :   ASSERT_TRUE (r0.get_nonzero_bits () == 0xf0);
    3771              : 
    3772              :   // Intersect where the mask of nonzero bits is implicit from the range.
    3773            4 :   r0.set_varying (integer_type_node);
    3774            4 :   r1 = range_int (0, 255);
    3775            4 :   r0.intersect (r1);
    3776            4 :   ASSERT_TRUE (r0.get_nonzero_bits () == 0xff);
    3777              : 
    3778              :   // Test that setting a nonzero bit of 1 does not pessimize the range.
    3779            4 :   r0.set_zero (integer_type_node);
    3780            4 :   r0.set_nonzero_bits (INT (1));
    3781            4 :   ASSERT_TRUE (r0.zero_p ());
    3782              : 
    3783              :   // Now test that range bounds are snapped to match bitmask alignments.
    3784            4 :   test_irange_snap_bounds ();
    3785            4 : }
    3786              : 
    3787              : // Build an frange from string endpoints.
    3788              : 
    3789              : static inline frange
    3790          712 : frange_float (const char *lb, const char *ub, tree type = float_type_node)
    3791              : {
    3792          712 :   REAL_VALUE_TYPE min, max;
    3793          712 :   gcc_assert (real_from_string (&min, lb) == 0);
    3794          712 :   gcc_assert (real_from_string (&max, ub) == 0);
    3795          712 :   return frange (type, min, max);
    3796              : }
    3797              : 
    3798              : // Build the REAL_VALUE_TYPE for the string S.
    3799              : 
    3800              : static REAL_VALUE_TYPE
    3801          304 : real_from_str (const char *s)
    3802              : {
    3803          304 :   REAL_VALUE_TYPE r;
    3804          304 :   gcc_assert (real_from_string (&r, s) == 0);
    3805          304 :   return r;
    3806              : }
    3807              : 
    3808              : static void
    3809            8 : range_tests_sub_ranges ()
    3810              : {
    3811            8 :   frange r0, r1;
    3812              : 
    3813              :   // A union of two disjoint intervals keeps both.
    3814            8 :   r0 = frange_float ("3", "5");
    3815            8 :   r1 = frange_float ("10", "12");
    3816            8 :   r0.union_ (r1);
    3817            8 :   ASSERT_EQ (r0.num_pairs (), 2);
    3818            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("4")));
    3819            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("11")));
    3820            8 :   ASSERT_FALSE (r0.contains_p (real_from_str ("7")));
    3821              : 
    3822            8 :   REAL_VALUE_TYPE three = real_from_str ("3");
    3823            8 :   REAL_VALUE_TYPE twelve = real_from_str ("12");
    3824            8 :   ASSERT_TRUE (real_identical (&r0.lower_bound (), &three));
    3825            8 :   ASSERT_TRUE (real_identical (&r0.upper_bound (), &twelve));
    3826              : 
    3827              :   // Intersecting away one side leaves a single interval again.
    3828            8 :   r1 = frange_float ("0", "6");
    3829            8 :   r0.intersect (r1);
    3830            8 :   ASSERT_EQ (r0.num_pairs (), 1);
    3831            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("4")));
    3832            8 :   ASSERT_FALSE (r0.contains_p (real_from_str ("11")));
    3833              : 
    3834              :   // Overlapping intervals fuse rather than leave a gap.
    3835            8 :   r0 = frange_float ("3", "8");
    3836            8 :   r1 = frange_float ("5", "12");
    3837            8 :   r0.union_ (r1);
    3838            8 :   ASSERT_EQ (r0.num_pairs (), 1);
    3839            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("7")));
    3840              : 
    3841            8 :   if (frange::MAX_PAIRS == 2)
    3842              :     {
    3843              :       // When more pieces arrive than fit, the last slot swallows the tail:
    3844              :       // [0,1] stays and [3,4], [100,101] merge into [3,101].
    3845            8 :       r0 = frange_float ("0", "1");
    3846            8 :       r1 = frange_float ("100", "101");
    3847            8 :       r0.union_ (r1);
    3848            8 :       r1 = frange_float ("3", "4");
    3849            8 :       r0.union_ (r1);
    3850            8 :       ASSERT_EQ (r0.num_pairs (), 2);
    3851            8 :       ASSERT_TRUE (r0.contains_p (real_from_str ("50")));
    3852            8 :       ASSERT_TRUE (r0.contains_p (real_from_str ("3.5")));
    3853            8 :       ASSERT_TRUE (r0.contains_p (real_from_str ("100.5")));
    3854              :     }
    3855              : 
    3856              :   // Equality accounts for the sub-ranges.
    3857            8 :   r0 = frange_float ("3", "5");
    3858            8 :   r1 = frange_float ("10", "12");
    3859            8 :   r0.union_ (r1);
    3860            8 :   r1 = frange_float ("3", "12");
    3861            8 :   ASSERT_NE (r0, r1);
    3862              : 
    3863              :   // Intersecting every piece away, with the NAN cleared, leaves UNDEFINED.
    3864            8 :   r0 = frange_float ("3", "5");
    3865            8 :   r1 = frange_float ("10", "12");
    3866            8 :   r0.union_ (r1);
    3867            8 :   r0.clear_nan ();
    3868            8 :   r1 = frange_float ("20", "25");
    3869            8 :   r1.clear_nan ();
    3870            8 :   r0.intersect (r1);
    3871            8 :   ASSERT_TRUE (r0.undefined_p ());
    3872            8 : }
    3873              : 
    3874              : // Build a range that excludes the single point C.
    3875              : 
    3876              : static frange
    3877          112 : frange_float_excluding (const char *c)
    3878              : {
    3879          112 :   REAL_VALUE_TYPE r = real_from_str (c);
    3880          112 :   frange f;
    3881          112 :   f.set (float_type_node, r, r, VR_ANTI_RANGE);
    3882          112 :   return f;
    3883              : }
    3884              : 
    3885              : static void
    3886            8 : range_tests_excluding ()
    3887              : {
    3888            8 :   frange r0, r1;
    3889              : 
    3890              :   // "x != 1.0" is two sub-ranges with 1.0 missing.
    3891            8 :   r0 = frange_float_excluding ("1.0");
    3892            8 :   ASSERT_FALSE (r0.varying_p ());
    3893            8 :   ASSERT_FALSE (r0.undefined_p ());
    3894            8 :   ASSERT_EQ (r0.num_pairs (), 2);
    3895            8 :   ASSERT_FALSE (r0.contains_p (real_from_str ("1.0")));
    3896            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("2.0")));
    3897            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("0.0")));
    3898            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("-1.0")));
    3899            8 :   ASSERT_FALSE (r0.singleton_p ());
    3900              :   // A NAN compares unequal to everything, so this says nothing about NANs.
    3901            8 :   if (HONOR_NANS (float_type_node))
    3902            8 :     ASSERT_TRUE (r0.maybe_isnan ());
    3903              :   // The extremes still span the domain.
    3904            8 :   REAL_VALUE_TYPE dom_min = frange_val_min (float_type_node);
    3905            8 :   REAL_VALUE_TYPE dom_max = frange_val_max (float_type_node);
    3906            8 :   ASSERT_TRUE (real_identical (&r0.lower_bound (), &dom_min));
    3907            8 :   ASSERT_TRUE (real_identical (&r0.upper_bound (), &dom_max));
    3908              : 
    3909              :   // Any constant, not just 0.0 or 1.0.
    3910            8 :   r0 = frange_float_excluding ("5.5");
    3911            8 :   ASSERT_EQ (r0.num_pairs (), 2);
    3912            8 :   ASSERT_FALSE (r0.contains_p (real_from_str ("5.5")));
    3913            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("5.4")));
    3914              : 
    3915              :   // "x != 1.0" met with [1.0, 1.0] is empty.
    3916            8 :   r0 = frange_float_excluding ("1.0");
    3917            8 :   r1 = frange_float ("1.0", "1.0");
    3918            8 :   r1.clear_nan ();
    3919            8 :   r0.intersect (r1);
    3920            8 :   ASSERT_TRUE (r0.undefined_p ());
    3921              : 
    3922              :   // Excluding a point outside a range changes nothing.
    3923            8 :   r0 = frange_float ("3.0", "5.0");
    3924            8 :   r0.clear_nan ();
    3925            8 :   r1 = frange_float_excluding ("1.0");
    3926            8 :   r0.intersect (r1);
    3927            8 :   ASSERT_EQ (r0.num_pairs (), 1);
    3928            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("3.0")));
    3929            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("5.0")));
    3930              : 
    3931              :   // Union puts the point back.
    3932            8 :   r0 = frange_float_excluding ("1.0");
    3933            8 :   r1 = frange_float ("1.0", "1.0");
    3934            8 :   r0.union_ (r1);
    3935            8 :   ASSERT_TRUE (r0.varying_p ());
    3936              : 
    3937              :   // Two different exclusions cannot both be held.
    3938            8 :   r0 = frange_float_excluding ("1.0");
    3939            8 :   r1 = frange_float_excluding ("2.0");
    3940            8 :   r0.union_ (r1);
    3941            8 :   ASSERT_TRUE (r0.varying_p ());
    3942              : 
    3943              :   // Nor can an intersection hold both.
    3944            8 :   r0 = frange_float_excluding ("1.0");
    3945            8 :   r1 = frange_float_excluding ("2.0");
    3946            8 :   r0.intersect (r1);
    3947            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("0.0")));
    3948            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("3.0")));
    3949              : 
    3950              :   // Equality accounts for the gap.
    3951            8 :   r0 = frange_float_excluding ("1.0");
    3952            8 :   r1 = frange_float_excluding ("2.0");
    3953            8 :   ASSERT_NE (r0, r1);
    3954            8 :   r1 = frange_float_excluding ("1.0");
    3955            8 :   ASSERT_EQ (r0, r1);
    3956            8 : }
    3957              : 
    3958              : static void
    3959            8 : range_tests_sub_ranges_zero ()
    3960              : {
    3961            8 :   frange r0, r1;
    3962              : 
    3963              :   // "x != 0.0" must exclude BOTH zeros, since -0.0 == 0.0 and so "x != 0.0" is
    3964              :   // false for either.  The seam lands on the denormals either side of zero,
    3965              :   // which falls out of nextafter with no special case.
    3966            8 :   r0 = frange_float_excluding ("0.0");
    3967            8 :   ASSERT_EQ (r0.num_pairs (), 2);
    3968            8 :   ASSERT_FALSE (r0.contains_p (dconst0));
    3969            8 :   ASSERT_FALSE (r0.contains_p (dconstm0));
    3970            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("1.0")));
    3971            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("-1.0")));
    3972              : 
    3973              :   // Excluding zero from [-0.0, 5.0] eats the lower end entirely.
    3974            8 :   r0.set_nonzero (float_type_node);
    3975            8 :   ASSERT_FALSE (r0.contains_zero_p ());
    3976            8 :   ASSERT_FALSE (r0.contains_p (dconst0));
    3977            8 :   ASSERT_FALSE (r0.contains_p (dconstm0));
    3978              : 
    3979              :   // A NAN is not a zero, so clearing the NAN leaves the range nonzero.
    3980            8 :   r0.clear_nan ();
    3981            8 :   ASSERT_FALSE (r0.contains_zero_p ());
    3982              : 
    3983              :   // A range that avoids zero does not contain zero.
    3984            8 :   r0 = frange_float ("1.0", "10.0");
    3985            8 :   ASSERT_FALSE (r0.contains_zero_p ());
    3986              : 
    3987              :   // Excluding zero from [-0.0, 5.0] leaves (0, 5], which does not contain zero.
    3988            8 :   r0 = frange_float ("-0.0", "5.0");
    3989            8 :   r0.clear_nan ();
    3990            8 :   r1 = frange_float_excluding ("0.0");
    3991            8 :   r0.intersect (r1);
    3992            8 :   ASSERT_EQ (r0.num_pairs (), 1);
    3993            8 :   ASSERT_FALSE (r0.contains_zero_p ());
    3994            8 :   ASSERT_FALSE (r0.contains_p (dconst0));
    3995            8 :   ASSERT_FALSE (r0.contains_p (dconstm0));
    3996            8 :   ASSERT_TRUE (r0.contains_p (real_from_str ("5.0")));
    3997              : 
    3998              :   // -0.0 and +0.0 abut: nothing is representable between them, so the two
    3999              :   // halves fuse into one interval rather than leaving a gap.
    4000            8 :   r0 = frange_float ("-5", "-0.0");
    4001            8 :   r0.clear_nan ();
    4002            8 :   r1 = frange_float ("0.0", "5");
    4003            8 :   r1.clear_nan ();
    4004            8 :   r0.union_ (r1);
    4005            8 :   ASSERT_EQ (r0.num_pairs (), 1);
    4006            8 :   ASSERT_TRUE (r0.contains_p (dconst0));
    4007            8 :   ASSERT_TRUE (r0.contains_p (dconstm0));
    4008            8 : }
    4009              : 
    4010              : // A cached frange must come back with every sub-range intact.
    4011              : 
    4012              : static void
    4013            8 : range_tests_sub_ranges_storage ()
    4014              : {
    4015            8 :   vrange_allocator alloc (false);
    4016              : 
    4017              :   // A two-piece range comes back as two pieces, unchanged.
    4018            8 :   frange r0 = frange_float ("3", "5");
    4019            8 :   frange r1 = frange_float ("10", "12");
    4020            8 :   r0.union_ (r1);
    4021            8 :   ASSERT_EQ (r0.num_pairs (), 2);
    4022              : 
    4023            8 :   vrange_storage *slot = alloc.clone (r0);
    4024            8 :   frange r2;
    4025            8 :   slot->get_vrange (r2, float_type_node);
    4026            8 :   ASSERT_EQ (r2.num_pairs (), 2);
    4027            8 :   ASSERT_EQ (r2, r0);
    4028            8 : }
    4029              : 
    4030              : // NANs and sub-ranges: unioning in a NAN keeps the intervals, while
    4031              : // intersecting the intervals away collapses to a plain NAN with a single
    4032              : // pair.
    4033              : 
    4034              : static void
    4035            4 : range_tests_sub_ranges_nan ()
    4036              : {
    4037            4 :   frange r0, r1;
    4038              : 
    4039              :   // Union with a NAN keeps both intervals and gains the NAN.
    4040            4 :   r0 = frange_float ("3", "5");
    4041            4 :   r1 = frange_float ("10", "12");
    4042            4 :   r0.union_ (r1);
    4043            4 :   r0.clear_nan ();
    4044            4 :   r1.set_nan (float_type_node);
    4045            4 :   r0.union_ (r1);
    4046            4 :   ASSERT_EQ (r0.num_pairs (), 2);
    4047            8 :   ASSERT_TRUE (r0.maybe_isnan ());
    4048              : 
    4049              :   // Intersecting the intervals away leaves just the NAN.
    4050            4 :   r0 = frange_float ("3", "5");
    4051            4 :   r1 = frange_float ("10", "12");
    4052            4 :   r0.union_ (r1);
    4053            4 :   r1 = frange_float ("20", "25");
    4054            4 :   r0.intersect (r1);
    4055            4 :   ASSERT_TRUE (r0.known_isnan ());
    4056            4 :   ASSERT_EQ (r0.num_pairs (), 1);
    4057            4 : }
    4058              : 
    4059              : static void
    4060            4 : range_tests_nan ()
    4061              : {
    4062            4 :   frange r0, r1;
    4063            4 :   REAL_VALUE_TYPE q, r;
    4064            4 :   bool signbit;
    4065              : 
    4066              :   // Equal ranges but with differing NAN bits are not equal.
    4067            4 :   if (HONOR_NANS (float_type_node))
    4068              :     {
    4069            4 :       r1 = frange_float ("10", "12");
    4070            4 :       r0 = r1;
    4071            4 :       ASSERT_EQ (r0, r1);
    4072            4 :       r0.clear_nan ();
    4073            4 :       ASSERT_NE (r0, r1);
    4074            4 :       r0.update_nan ();
    4075            4 :       ASSERT_EQ (r0, r1);
    4076              : 
    4077              :       // [10, 20] NAN ^ [30, 40] NAN = NAN.
    4078            4 :       r0 = frange_float ("10", "20");
    4079            4 :       r1 = frange_float ("30", "40");
    4080            4 :       r0.intersect (r1);
    4081            4 :       ASSERT_TRUE (r0.known_isnan ());
    4082              : 
    4083              :       // [3,5] U [5,10] NAN = ... NAN
    4084            4 :       r0 = frange_float ("3", "5");
    4085            4 :       r0.clear_nan ();
    4086            4 :       r1 = frange_float ("5", "10");
    4087            4 :       r0.union_ (r1);
    4088            8 :       ASSERT_TRUE (r0.maybe_isnan ());
    4089              :     }
    4090              : 
    4091              :   // [5,6] U NAN = [5,6] NAN.
    4092            4 :   r0 = frange_float ("5", "6");
    4093            4 :   r0.clear_nan ();
    4094            4 :   r1.set_nan (float_type_node);
    4095            4 :   r0.union_ (r1);
    4096            4 :   real_from_string (&q, "5");
    4097            4 :   real_from_string (&r, "6");
    4098            4 :   ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
    4099            4 :   ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
    4100            8 :   ASSERT_TRUE (r0.maybe_isnan ());
    4101              : 
    4102              :   // NAN U NAN = NAN
    4103            4 :   r0.set_nan (float_type_node);
    4104            4 :   r1.set_nan (float_type_node);
    4105            4 :   r0.union_ (r1);
    4106            4 :   ASSERT_TRUE (r0.known_isnan ());
    4107              : 
    4108              :   // [INF, INF] NAN ^ NAN = NAN
    4109            4 :   r0.set_nan (float_type_node);
    4110            4 :   r1 = frange_float ("+Inf", "+Inf");
    4111            4 :   if (!HONOR_NANS (float_type_node))
    4112            0 :     r1.update_nan ();
    4113            4 :   r0.intersect (r1);
    4114            4 :   ASSERT_TRUE (r0.known_isnan ());
    4115              : 
    4116              :   // NAN ^ NAN = NAN
    4117            4 :   r0.set_nan (float_type_node);
    4118            4 :   r1.set_nan (float_type_node);
    4119            4 :   r0.intersect (r1);
    4120            4 :   ASSERT_TRUE (r0.known_isnan ());
    4121              : 
    4122              :   // +NAN ^ -NAN = UNDEFINED
    4123            4 :   r0.set_nan (float_type_node, false);
    4124            4 :   r1.set_nan (float_type_node, true);
    4125            4 :   r0.intersect (r1);
    4126            4 :   ASSERT_TRUE (r0.undefined_p ());
    4127              : 
    4128              :   // VARYING ^ NAN = NAN.
    4129            4 :   r0.set_nan (float_type_node);
    4130            4 :   r1.set_varying (float_type_node);
    4131            4 :   r0.intersect (r1);
    4132            4 :   ASSERT_TRUE (r0.known_isnan ());
    4133              : 
    4134              :   // [3,4] ^ NAN = UNDEFINED.
    4135            4 :   r0 = frange_float ("3", "4");
    4136            4 :   r0.clear_nan ();
    4137            4 :   r1.set_nan (float_type_node);
    4138            4 :   r0.intersect (r1);
    4139            4 :   ASSERT_TRUE (r0.undefined_p ());
    4140              : 
    4141              :   // [-3, 5] ^ NAN = UNDEFINED
    4142            4 :   r0 = frange_float ("-3", "5");
    4143            4 :   r0.clear_nan ();
    4144            4 :   r1.set_nan (float_type_node);
    4145            4 :   r0.intersect (r1);
    4146            4 :   ASSERT_TRUE (r0.undefined_p ());
    4147              : 
    4148              :   // Setting the NAN bit to yes does not make us a known NAN.
    4149            4 :   r0.set_varying (float_type_node);
    4150            4 :   r0.update_nan ();
    4151            4 :   ASSERT_FALSE (r0.known_isnan ());
    4152              : 
    4153              :   // NAN is in a VARYING.
    4154            4 :   r0.set_varying (float_type_node);
    4155            4 :   real_nan (&r, "", 1, TYPE_MODE (float_type_node));
    4156            4 :   REAL_VALUE_TYPE nan = r;
    4157            4 :   ASSERT_TRUE (r0.contains_p (nan));
    4158              : 
    4159              :   // -NAN is in a VARYING.
    4160            4 :   r0.set_varying (float_type_node);
    4161            4 :   q = real_value_negate (&r);
    4162            4 :   REAL_VALUE_TYPE neg_nan = q;
    4163            4 :   ASSERT_TRUE (r0.contains_p (neg_nan));
    4164              : 
    4165              :   // Clearing the NAN on a [] NAN is the empty set.
    4166            4 :   r0.set_nan (float_type_node);
    4167            4 :   r0.clear_nan ();
    4168            4 :   ASSERT_TRUE (r0.undefined_p ());
    4169              : 
    4170              :   // [10,20] NAN ^ [21,25] NAN = [NAN]
    4171            4 :   r0 = frange_float ("10", "20");
    4172            4 :   r0.update_nan ();
    4173            4 :   r1 = frange_float ("21", "25");
    4174            4 :   r1.update_nan ();
    4175            4 :   r0.intersect (r1);
    4176            4 :   ASSERT_TRUE (r0.known_isnan ());
    4177              : 
    4178              :   // NAN U [5,6] should be [5,6] +-NAN.
    4179            4 :   r0.set_nan (float_type_node);
    4180            4 :   r1 = frange_float ("5", "6");
    4181            4 :   r1.clear_nan ();
    4182            4 :   r0.union_ (r1);
    4183            4 :   real_from_string (&q, "5");
    4184            4 :   real_from_string (&r, "6");
    4185            4 :   ASSERT_TRUE (real_identical (&q, &r0.lower_bound ()));
    4186            4 :   ASSERT_TRUE (real_identical (&r, &r0.upper_bound ()));
    4187            4 :   ASSERT_TRUE (!r0.signbit_p (signbit));
    4188            8 :   ASSERT_TRUE (r0.maybe_isnan ());
    4189              : 
    4190              :   // NAN U NAN shouldn't change anything.
    4191            4 :   r0.set_nan (float_type_node);
    4192            4 :   r1.set_nan (float_type_node);
    4193            4 :   ASSERT_FALSE (r0.union_ (r1));
    4194              : 
    4195              :   // [3,5] NAN U NAN shouldn't change anything.
    4196            4 :   r0 = frange_float ("3", "5");
    4197            4 :   r1.set_nan (float_type_node);
    4198            4 :   ASSERT_FALSE (r0.union_ (r1));
    4199              : 
    4200              :   // [3,5] U NAN *does* trigger a change.
    4201            4 :   r0 = frange_float ("3", "5");
    4202            4 :   r0.clear_nan ();
    4203            4 :   r1.set_nan (float_type_node);
    4204            4 :   ASSERT_TRUE (r0.union_ (r1));
    4205            4 : }
    4206              : 
    4207              : static void
    4208            8 : range_tests_signed_zeros ()
    4209              : {
    4210            8 :   REAL_VALUE_TYPE zero = dconst0;
    4211            8 :   REAL_VALUE_TYPE neg_zero = zero;
    4212            8 :   neg_zero.sign = 1;
    4213            8 :   frange r0, r1;
    4214            8 :   bool signbit;
    4215              : 
    4216              :   // [0,0] contains [0,0] but not [-0,-0] and vice versa.
    4217            8 :   r0 = frange_float ("0.0", "0.0");
    4218            8 :   r1 = frange_float ("-0.0", "-0.0");
    4219            8 :   ASSERT_TRUE (r0.contains_p (zero));
    4220            8 :   ASSERT_TRUE (!r0.contains_p (neg_zero));
    4221            8 :   ASSERT_TRUE (r1.contains_p (neg_zero));
    4222            8 :   ASSERT_TRUE (!r1.contains_p (zero));
    4223              : 
    4224              :   // Test contains_p() when we know the sign of the zero.
    4225            8 :   r0 = frange_float ("0.0", "0.0");
    4226            8 :   ASSERT_TRUE (r0.contains_p (zero));
    4227            8 :   ASSERT_FALSE (r0.contains_p (neg_zero));
    4228            8 :   r0 = frange_float ("-0.0", "-0.0");
    4229            8 :   ASSERT_TRUE (r0.contains_p (neg_zero));
    4230            8 :   ASSERT_FALSE (r0.contains_p (zero));
    4231              : 
    4232            8 :   r0 = frange_float ("-0.0", "0.0");
    4233            8 :   ASSERT_TRUE (r0.contains_p (neg_zero));
    4234            8 :   ASSERT_TRUE (r0.contains_p (zero));
    4235              : 
    4236            8 :   r0 = frange_float ("-3", "5");
    4237            8 :   ASSERT_TRUE (r0.contains_p (neg_zero));
    4238            8 :   ASSERT_TRUE (r0.contains_p (zero));
    4239              : 
    4240              :   // The intersection of zeros that differ in sign is a NAN (or
    4241              :   // undefined if not honoring NANs).
    4242            8 :   r0 = frange_float ("-0.0", "-0.0");
    4243            8 :   r1 = frange_float ("0.0", "0.0");
    4244            8 :   r0.intersect (r1);
    4245            8 :   if (HONOR_NANS (float_type_node))
    4246            4 :     ASSERT_TRUE (r0.known_isnan ());
    4247              :   else
    4248            4 :     ASSERT_TRUE (r0.undefined_p ());
    4249              : 
    4250              :   // The union of zeros that differ in sign is a zero with unknown sign.
    4251            8 :   r0 = frange_float ("0.0", "0.0");
    4252            8 :   r1 = frange_float ("-0.0", "-0.0");
    4253            8 :   r0.union_ (r1);
    4254            8 :   ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
    4255              : 
    4256              :   // [-0, +0] has an unknown sign.
    4257            8 :   r0 = frange_float ("-0.0", "0.0");
    4258            8 :   ASSERT_TRUE (r0.zero_p () && !r0.signbit_p (signbit));
    4259              : 
    4260              :   // [-0, +0] ^ [0, 0] is [0, 0]
    4261            8 :   r0 = frange_float ("-0.0", "0.0");
    4262            8 :   r1 = frange_float ("0.0", "0.0");
    4263            8 :   r0.intersect (r1);
    4264            8 :   ASSERT_TRUE (r0.zero_p ());
    4265              : 
    4266            8 :   r0 = frange_float ("+0", "5");
    4267            8 :   r0.clear_nan ();
    4268            8 :   ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
    4269              : 
    4270            8 :   r0 = frange_float ("-0", "5");
    4271            8 :   r0.clear_nan ();
    4272            8 :   ASSERT_TRUE (!r0.signbit_p (signbit));
    4273              : 
    4274            8 :   r0 = frange_float ("-0", "10");
    4275            8 :   r1 = frange_float ("0", "5");
    4276            8 :   r0.intersect (r1);
    4277            8 :   ASSERT_TRUE (real_iszero (&r0.lower_bound (), false));
    4278              : 
    4279            8 :   r0 = frange_float ("-0", "5");
    4280            8 :   r1 = frange_float ("0", "5");
    4281            8 :   r0.union_ (r1);
    4282            8 :   ASSERT_TRUE (real_iszero (&r0.lower_bound (), true));
    4283              : 
    4284            8 :   r0 = frange_float ("-5", "-0");
    4285            8 :   r0.update_nan ();
    4286            8 :   r1 = frange_float ("0", "0");
    4287            8 :   r1.update_nan ();
    4288            8 :   r0.intersect (r1);
    4289            8 :   if (HONOR_NANS (float_type_node))
    4290            4 :     ASSERT_TRUE (r0.known_isnan ());
    4291              :   else
    4292            4 :     ASSERT_TRUE (r0.undefined_p ());
    4293              : 
    4294            8 :   r0.set_nonnegative (float_type_node);
    4295            8 :   if (HONOR_NANS (float_type_node))
    4296            8 :     ASSERT_TRUE (r0.maybe_isnan ());
    4297              : 
    4298              :   // Numbers containing zero should have an unknown SIGNBIT.
    4299            8 :   r0 = frange_float ("0", "10");
    4300            8 :   r0.clear_nan ();
    4301            8 :   ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
    4302            8 : }
    4303              : 
    4304              : static void
    4305            8 : range_tests_signbit ()
    4306              : {
    4307            8 :   frange r0, r1;
    4308            8 :   bool signbit;
    4309              : 
    4310              :   // Negative numbers should have the SIGNBIT set.
    4311            8 :   r0 = frange_float ("-5", "-1");
    4312            8 :   r0.clear_nan ();
    4313            8 :   ASSERT_TRUE (r0.signbit_p (signbit) && signbit);
    4314              :   // Positive numbers should have the SIGNBIT clear.
    4315            8 :   r0 = frange_float ("1", "10");
    4316            8 :   r0.clear_nan ();
    4317            8 :   ASSERT_TRUE (r0.signbit_p (signbit) && !signbit);
    4318              :   // Numbers spanning both positive and negative should have an
    4319              :   // unknown SIGNBIT.
    4320            8 :   r0 = frange_float ("-10", "10");
    4321            8 :   r0.clear_nan ();
    4322            8 :   ASSERT_TRUE (!r0.signbit_p (signbit));
    4323            8 :   r0.set_varying (float_type_node);
    4324            8 :   ASSERT_TRUE (!r0.signbit_p (signbit));
    4325            8 : }
    4326              : 
    4327              : static void
    4328            8 : range_tests_flush_denormals ()
    4329              : {
    4330              :   // We need -0.0 to exist for any of this to mean anything.
    4331           32 :   if (!MODE_HAS_SIGNED_ZEROS (TYPE_MODE (float_type_node)))
    4332            0 :     return;
    4333              : 
    4334            8 :   int save_flag = flag_signed_zeros;
    4335            8 :   flag_signed_zeros = 0;
    4336              : 
    4337              :   // Flushing a positive denormal lower bound to zero must canonicalize that
    4338              :   // zero to -0.0 to agree with set().
    4339            8 :   frange flushed = frange_float ("1e-40", "5");
    4340            8 :   flushed.clear_nan ();
    4341            8 :   flushed.flush_denormals_to_zero ();
    4342              : 
    4343            8 :   frange built = frange_float ("0", "5");
    4344            8 :   built.clear_nan ();
    4345              : 
    4346            8 :   ASSERT_TRUE (flushed == built);
    4347            8 :   ASSERT_TRUE (flushed.contains_p (dconstm0));
    4348            8 :   ASSERT_TRUE (flushed.contains_p (dconst0));
    4349              : 
    4350            8 :   flag_signed_zeros = save_flag;
    4351            8 : }
    4352              : 
    4353              : static void
    4354            8 : range_tests_floats ()
    4355              : {
    4356            8 :   frange r0, r1;
    4357              : 
    4358            8 :   if (HONOR_NANS (float_type_node))
    4359              :     {
    4360            4 :       range_tests_nan ();
    4361            4 :       range_tests_sub_ranges_nan ();
    4362              :     }
    4363            8 :   range_tests_signbit ();
    4364            8 :   range_tests_flush_denormals ();
    4365            8 :   range_tests_sub_ranges ();
    4366            8 :   range_tests_sub_ranges_storage ();
    4367            8 :   range_tests_excluding ();
    4368              : 
    4369            8 :   if (HONOR_SIGNED_ZEROS (float_type_node))
    4370              :     {
    4371            8 :       range_tests_signed_zeros ();
    4372            8 :       range_tests_sub_ranges_zero ();
    4373              :     }
    4374              : 
    4375              :   // A range of [-INF,+INF] is actually VARYING if no other properties
    4376              :   // are set.
    4377            8 :   r0 = frange_float ("-Inf", "+Inf");
    4378            8 :   ASSERT_TRUE (r0.varying_p ());
    4379              :   // ...unless it has some special property...
    4380            8 :   if (HONOR_NANS (r0.type ()))
    4381              :     {
    4382            4 :       r0.clear_nan ();
    4383            4 :       ASSERT_FALSE (r0.varying_p ());
    4384              :     }
    4385              : 
    4386              :   // For most architectures, where float and double are different
    4387              :   // sizes, having the same endpoints does not necessarily mean the
    4388              :   // ranges are equal.
    4389            8 :   if (!types_compatible_p (float_type_node, double_type_node))
    4390              :     {
    4391            8 :       r0 = frange_float ("3.0", "3.0", float_type_node);
    4392            8 :       r1 = frange_float ("3.0", "3.0", double_type_node);
    4393            8 :       ASSERT_NE (r0, r1);
    4394              :     }
    4395              : 
    4396              :   // [3,5] U [10,12] = [3,5][10,12]
    4397            8 :   r0 = frange_float ("3", "5");
    4398            8 :   r1 = frange_float ("10", "12");
    4399            8 :   r0.union_ (r1);
    4400            8 :   ASSERT_EQ (r0.num_pairs (), 2);
    4401            8 :   ASSERT_NE (r0, frange_float ("3", "12"));
    4402              : 
    4403              :   // [5,10] U [4,8] = [4,10]
    4404            8 :   r0 = frange_float ("5", "10");
    4405            8 :   r1 = frange_float ("4", "8");
    4406            8 :   r0.union_ (r1);
    4407            8 :   ASSERT_EQ (r0, frange_float ("4", "10"));
    4408              : 
    4409              :   // [3,5] U [4,10] = [3,10]
    4410            8 :   r0 = frange_float ("3", "5");
    4411            8 :   r1 = frange_float ("4", "10");
    4412            8 :   r0.union_ (r1);
    4413            8 :   ASSERT_EQ (r0, frange_float ("3", "10"));
    4414              : 
    4415              :   // [4,10] U [5,11] = [4,11]
    4416            8 :   r0 = frange_float ("4", "10");
    4417            8 :   r1 = frange_float ("5", "11");
    4418            8 :   r0.union_ (r1);
    4419            8 :   ASSERT_EQ (r0, frange_float ("4", "11"));
    4420              : 
    4421              :   // [3,12] ^ [10,12] = [10,12].
    4422            8 :   r0 = frange_float ("3", "12");
    4423            8 :   r1 = frange_float ("10", "12");
    4424            8 :   r0.intersect (r1);
    4425            8 :   ASSERT_EQ (r0, frange_float ("10", "12"));
    4426              : 
    4427              :   // [10,12] ^ [11,11] = [11,11]
    4428            8 :   r0 = frange_float ("10", "12");
    4429            8 :   r1 = frange_float ("11", "11");
    4430            8 :   r0.intersect (r1);
    4431            8 :   ASSERT_EQ (r0, frange_float ("11", "11"));
    4432              : 
    4433              :   // [10,20] ^ [5,15] = [10,15]
    4434            8 :   r0 = frange_float ("10", "20");
    4435            8 :   r1 = frange_float ("5",  "15");
    4436            8 :   r0.intersect (r1);
    4437            8 :   ASSERT_EQ (r0, frange_float ("10", "15"));
    4438              : 
    4439              :   // [10,20] ^ [15,25] = [15,20]
    4440            8 :   r0 = frange_float ("10", "20");
    4441            8 :   r1 = frange_float ("15", "25");
    4442            8 :   r0.intersect (r1);
    4443            8 :   ASSERT_EQ (r0, frange_float ("15", "20"));
    4444              : 
    4445              :   // [10,20] ^ [21,25] = []
    4446            8 :   r0 = frange_float ("10", "20");
    4447            8 :   r0.clear_nan ();
    4448            8 :   r1 = frange_float ("21", "25");
    4449            8 :   r1.clear_nan ();
    4450            8 :   r0.intersect (r1);
    4451            8 :   ASSERT_TRUE (r0.undefined_p ());
    4452              : 
    4453            8 :   if (HONOR_INFINITIES (float_type_node))
    4454              :     {
    4455              :       // Make sure [-Inf, -Inf] doesn't get normalized.
    4456            4 :       r0 = frange_float ("-Inf", "-Inf");
    4457            4 :       ASSERT_TRUE (real_isinf (&r0.lower_bound (), true));
    4458            4 :       ASSERT_TRUE (real_isinf (&r0.upper_bound (), true));
    4459              :     }
    4460              : 
    4461              :   // Test that reading back a global range yields the same result as
    4462              :   // what we wrote into it.
    4463            8 :   tree ssa = make_temp_ssa_name (float_type_node, NULL, "blah");
    4464            8 :   r0.set_varying (float_type_node);
    4465            8 :   r0.clear_nan ();
    4466            8 :   set_range_info (ssa, r0);
    4467            8 :   get_global_range_query ()->range_of_expr (r1, ssa);
    4468            8 :   ASSERT_EQ (r0, r1);
    4469            8 : }
    4470              : 
    4471              : // Run floating range tests for various combinations of NAN and INF
    4472              : // support.
    4473              : 
    4474              : static void
    4475            4 : range_tests_floats_various ()
    4476              : {
    4477            4 :   int save_finite_math_only = flag_finite_math_only;
    4478              : 
    4479              :   // Test -ffinite-math-only.
    4480            4 :   flag_finite_math_only = 1;
    4481            4 :   range_tests_floats ();
    4482              :   // Test -fno-finite-math-only.
    4483            4 :   flag_finite_math_only = 0;
    4484            4 :   range_tests_floats ();
    4485              : 
    4486            4 :   flag_finite_math_only = save_finite_math_only;
    4487            4 : }
    4488              : 
    4489              : void
    4490            4 : range_tests ()
    4491              : {
    4492            4 :   range_tests_irange3 ();
    4493            4 :   range_tests_int_range_max ();
    4494            4 :   range_tests_strict_enum ();
    4495            4 :   range_tests_nonzero_bits ();
    4496            4 :   range_tests_floats_various ();
    4497            4 :   range_tests_misc ();
    4498            4 : }
    4499              : 
    4500              : } // namespace selftest
    4501              : 
    4502              : #endif // CHECKING_P
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.