gcc/range-op.cc

   1 /* Code for range operators.
   2    Copyright (C) 2017-2022 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod <amacleod@redhat.com>
   4    and Aldy Hernandez <aldyh@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 "insn-codes.h"
  27 #include "rtl.h"
  28 #include "tree.h"
  29 #include "gimple.h"
  30 #include "cfghooks.h"
  31 #include "tree-pass.h"
  32 #include "ssa.h"
  33 #include "optabs-tree.h"
  34 #include "gimple-pretty-print.h"
  35 #include "diagnostic-core.h"
  36 #include "flags.h"
  37 #include "fold-const.h"
  38 #include "stor-layout.h"
  39 #include "calls.h"
  40 #include "cfganal.h"
  41 #include "gimple-iterator.h"
  42 #include "gimple-fold.h"
  43 #include "tree-eh.h"
  44 #include "gimple-walk.h"
  45 #include "tree-cfg.h"
  46 #include "wide-int.h"
  47 #include "value-relation.h"
  48 #include "range-op.h"
  49
  50 // Return the upper limit for a type.
  51
  52 static inline wide_int
  53 max_limit (const_tree type)
  54 {
  55   return wi::max_value (TYPE_PRECISION (type) , TYPE_SIGN (type));
  56 }
  57
  58 // Return the lower limit for a type.
  59
  60 static inline wide_int
  61 min_limit (const_tree type)
  62 {
  63   return wi::min_value (TYPE_PRECISION (type) , TYPE_SIGN (type));
  64 }
  65
  66 // Return false if shifting by OP is undefined behavior.  Otherwise, return
  67 // true and the range it is to be shifted by.  This allows trimming out of
  68 // undefined ranges, leaving only valid ranges if there are any.
  69
  70 static inline bool
  71 get_shift_range (irange &r, tree type, const irange &op)
  72 {
  73   if (op.undefined_p ())
  74     return false;
  75
  76   // Build valid range and intersect it with the shift range.
  77   r = value_range (build_int_cst_type (op.type (), 0),
  78                    build_int_cst_type (op.type (), TYPE_PRECISION (type) - 1));
  79   r.intersect (op);
  80
  81   // If there are no valid ranges in the shift range, returned false.
  82   if (r.undefined_p ())
  83     return false;
  84   return true;
  85 }
  86
  87 // Return TRUE if 0 is within [WMIN, WMAX].
  88
  89 static inline bool
  90 wi_includes_zero_p (tree type, const wide_int &wmin, const wide_int &wmax)
  91 {
  92   signop sign = TYPE_SIGN (type);
  93   return wi::le_p (wmin, 0, sign) && wi::ge_p (wmax, 0, sign);
  94 }
  95
  96 // Return TRUE if [WMIN, WMAX] is the singleton 0.
  97
  98 static inline bool
  99 wi_zero_p (tree type, const wide_int &wmin, const wide_int &wmax)
 100 {
 101   unsigned prec = TYPE_PRECISION (type);
 102   return wmin == wmax && wi::eq_p (wmin, wi::zero (prec));
 103 }
 104
 105 // Default wide_int fold operation returns [MIN, MAX].
 106
 107 void
 108 range_operator::wi_fold (irange &r, tree type,
 109                          const wide_int &lh_lb ATTRIBUTE_UNUSED,
 110                          const wide_int &lh_ub ATTRIBUTE_UNUSED,
 111                          const wide_int &rh_lb ATTRIBUTE_UNUSED,
 112                          const wide_int &rh_ub ATTRIBUTE_UNUSED) const
 113 {
 114   gcc_checking_assert (r.supports_type_p (type));
 115   r.set_varying (type);
 116 }
 117
 118 // Call wi_fold, except further split small subranges into constants.
 119 // This can provide better precision. For something   8 >> [0,1]
 120 // Instead of [8, 16], we will produce [8,8][16,16]
 121
 122 void
 123 range_operator::wi_fold_in_parts (irange &r, tree type,
 124                                   const wide_int &lh_lb,
 125                                   const wide_int &lh_ub,
 126                                   const wide_int &rh_lb,
 127                                   const wide_int &rh_ub) const
 128 {
 129   int_range_max tmp;
 130   widest_int rh_range = wi::sub (widest_int::from (rh_ub, TYPE_SIGN (type)),
 131                                  widest_int::from (rh_lb, TYPE_SIGN (type)));
 132   widest_int lh_range = wi::sub (widest_int::from (lh_ub, TYPE_SIGN (type)),
 133                                  widest_int::from (lh_lb, TYPE_SIGN (type)));
 134   // If there are 2, 3, or 4 values in the RH range, do them separately.
 135   // Call wi_fold_in_parts to check the RH side.
 136   if (rh_range > 0 && rh_range < 4)
 137     {
 138       wi_fold_in_parts (r, type, lh_lb, lh_ub, rh_lb, rh_lb);
 139       if (rh_range > 1)
 140         {
 141           wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 1, rh_lb + 1);
 142           r.union_ (tmp);
 143           if (rh_range == 3)
 144             {
 145               wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb + 2, rh_lb + 2);
 146               r.union_ (tmp);
 147             }
 148         }
 149       wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_ub, rh_ub);
 150       r.union_ (tmp);
 151     }
 152   // Otherise check for 2, 3, or 4 values in the LH range and split them up.
 153   // The RH side has been checked, so no recursion needed.
 154   else if (lh_range > 0 && lh_range < 4)
 155     {
 156       wi_fold (r, type, lh_lb, lh_lb, rh_lb, rh_ub);
 157       if (lh_range > 1)
 158         {
 159           wi_fold (tmp, type, lh_lb + 1, lh_lb + 1, rh_lb, rh_ub);
 160           r.union_ (tmp);
 161           if (lh_range == 3)
 162             {
 163               wi_fold (tmp, type, lh_lb + 2, lh_lb + 2, rh_lb, rh_ub);
 164               r.union_ (tmp);
 165             }
 166         }
 167       wi_fold (tmp, type, lh_ub, lh_ub, rh_lb, rh_ub);
 168       r.union_ (tmp);
 169     }
 170   // Otherwise just call wi_fold.
 171   else
 172     wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
 173 }
 174
 175 // The default for fold is to break all ranges into sub-ranges and
 176 // invoke the wi_fold method on each sub-range pair.
 177
 178 bool
 179 range_operator::fold_range (irange &r, tree type,
 180                             const irange &lh,
 181                             const irange &rh,
 182                             relation_trio trio) const
 183 {
 184   gcc_checking_assert (r.supports_type_p (type));
 185   if (empty_range_varying (r, type, lh, rh))
 186     return true;
 187
 188   relation_kind rel = trio.op1_op2 ();
 189   unsigned num_lh = lh.num_pairs ();
 190   unsigned num_rh = rh.num_pairs ();
 191
 192   // If both ranges are single pairs, fold directly into the result range.
 193   // If the number of subranges grows too high, produce a summary result as the
 194   // loop becomes exponential with little benefit.  See PR 103821.
 195   if ((num_lh == 1 && num_rh == 1) || num_lh * num_rh > 12)
 196     {
 197       wi_fold_in_parts (r, type, lh.lower_bound (), lh.upper_bound (),
 198                         rh.lower_bound (), rh.upper_bound ());
 199       op1_op2_relation_effect (r, type, lh, rh, rel);
 200       return true;
 201     }
 202
 203   int_range_max tmp;
 204   r.set_undefined ();
 205   for (unsigned x = 0; x < num_lh; ++x)
 206     for (unsigned y = 0; y < num_rh; ++y)
 207       {
 208         wide_int lh_lb = lh.lower_bound (x);
 209         wide_int lh_ub = lh.upper_bound (x);
 210         wide_int rh_lb = rh.lower_bound (y);
 211         wide_int rh_ub = rh.upper_bound (y);
 212         wi_fold_in_parts (tmp, type, lh_lb, lh_ub, rh_lb, rh_ub);
 213         r.union_ (tmp);
 214         if (r.varying_p ())
 215           {
 216             op1_op2_relation_effect (r, type, lh, rh, rel);
 217             return true;
 218           }
 219       }
 220   op1_op2_relation_effect (r, type, lh, rh, rel);
 221   return true;
 222 }
 223
 224 // The default for op1_range is to return false.
 225
 226 bool
 227 range_operator::op1_range (irange &r ATTRIBUTE_UNUSED,
 228                            tree type ATTRIBUTE_UNUSED,
 229                            const irange &lhs ATTRIBUTE_UNUSED,
 230                            const irange &op2 ATTRIBUTE_UNUSED,
 231                            relation_trio) const
 232 {
 233   return false;
 234 }
 235
 236 // The default for op2_range is to return false.
 237
 238 bool
 239 range_operator::op2_range (irange &r ATTRIBUTE_UNUSED,
 240                            tree type ATTRIBUTE_UNUSED,
 241                            const irange &lhs ATTRIBUTE_UNUSED,
 242                            const irange &op1 ATTRIBUTE_UNUSED,
 243                            relation_trio) const
 244 {
 245   return false;
 246 }
 247
 248 // The default relation routines return VREL_VARYING.
 249
 250 relation_kind
 251 range_operator::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
 252                                   const irange &op1 ATTRIBUTE_UNUSED,
 253                                   const irange &op2 ATTRIBUTE_UNUSED,
 254                                   relation_kind rel ATTRIBUTE_UNUSED) const
 255 {
 256   return VREL_VARYING;
 257 }
 258
 259 relation_kind
 260 range_operator::lhs_op2_relation (const irange &lhs ATTRIBUTE_UNUSED,
 261                                   const irange &op1 ATTRIBUTE_UNUSED,
 262                                   const irange &op2 ATTRIBUTE_UNUSED,
 263                                   relation_kind rel ATTRIBUTE_UNUSED) const
 264 {
 265   return VREL_VARYING;
 266 }
 267
 268 relation_kind
 269 range_operator::op1_op2_relation (const irange &lhs ATTRIBUTE_UNUSED) const
 270 {
 271   return VREL_VARYING;
 272 }
 273
 274 // Default is no relation affects the LHS.
 275
 276 bool
 277 range_operator::op1_op2_relation_effect (irange &lhs_range ATTRIBUTE_UNUSED,
 278                                        tree type ATTRIBUTE_UNUSED,
 279                                        const irange &op1_range ATTRIBUTE_UNUSED,
 280                                        const irange &op2_range ATTRIBUTE_UNUSED,
 281                                        relation_kind rel ATTRIBUTE_UNUSED) const
 282 {
 283   return false;
 284 }
 285
 286 // Create and return a range from a pair of wide-ints that are known
 287 // to have overflowed (or underflowed).
 288
 289 static void
 290 value_range_from_overflowed_bounds (irange &r, tree type,
 291                                     const wide_int &wmin,
 292                                     const wide_int &wmax)
 293 {
 294   const signop sgn = TYPE_SIGN (type);
 295   const unsigned int prec = TYPE_PRECISION (type);
 296
 297   wide_int tmin = wide_int::from (wmin, prec, sgn);
 298   wide_int tmax = wide_int::from (wmax, prec, sgn);
 299
 300   bool covers = false;
 301   wide_int tem = tmin;
 302   tmin = tmax + 1;
 303   if (wi::cmp (tmin, tmax, sgn) < 0)
 304     covers = true;
 305   tmax = tem - 1;
 306   if (wi::cmp (tmax, tem, sgn) > 0)
 307     covers = true;
 308
 309   // If the anti-range would cover nothing, drop to varying.
 310   // Likewise if the anti-range bounds are outside of the types
 311   // values.
 312   if (covers || wi::cmp (tmin, tmax, sgn) > 0)
 313     r.set_varying (type);
 314   else
 315     {
 316       tree tree_min = wide_int_to_tree (type, tmin);
 317       tree tree_max = wide_int_to_tree (type, tmax);
 318       r.set (tree_min, tree_max, VR_ANTI_RANGE);
 319     }
 320 }
 321
 322 // Create and return a range from a pair of wide-ints.  MIN_OVF and
 323 // MAX_OVF describe any overflow that might have occurred while
 324 // calculating WMIN and WMAX respectively.
 325
 326 static void
 327 value_range_with_overflow (irange &r, tree type,
 328                            const wide_int &wmin, const wide_int &wmax,
 329                            wi::overflow_type min_ovf = wi::OVF_NONE,
 330                            wi::overflow_type max_ovf = wi::OVF_NONE)
 331 {
 332   const signop sgn = TYPE_SIGN (type);
 333   const unsigned int prec = TYPE_PRECISION (type);
 334   const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);
 335
 336   // For one bit precision if max != min, then the range covers all
 337   // values.
 338   if (prec == 1 && wi::ne_p (wmax, wmin))
 339     {
 340       r.set_varying (type);
 341       return;
 342     }
 343
 344   if (overflow_wraps)
 345     {
 346       // If overflow wraps, truncate the values and adjust the range,
 347       // kind, and bounds appropriately.
 348       if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
 349         {
 350           wide_int tmin = wide_int::from (wmin, prec, sgn);
 351           wide_int tmax = wide_int::from (wmax, prec, sgn);
 352           // If the limits are swapped, we wrapped around and cover
 353           // the entire range.
 354           if (wi::gt_p (tmin, tmax, sgn))
 355             r.set_varying (type);
 356           else
 357             // No overflow or both overflow or underflow.  The range
 358             // kind stays normal.
 359             r.set (wide_int_to_tree (type, tmin),
 360                    wide_int_to_tree (type, tmax));
 361           return;
 362         }
 363
 364       if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
 365           || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
 366         value_range_from_overflowed_bounds (r, type, wmin, wmax);
 367       else
 368         // Other underflow and/or overflow, drop to VR_VARYING.
 369         r.set_varying (type);
 370     }
 371   else
 372     {
 373       // If both bounds either underflowed or overflowed, then the result
 374       // is undefined.
 375       if ((min_ovf == wi::OVF_OVERFLOW && max_ovf == wi::OVF_OVERFLOW)
 376           || (min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_UNDERFLOW))
 377         {
 378           r.set_undefined ();
 379           return;
 380         }
 381
 382       // If overflow does not wrap, saturate to [MIN, MAX].
 383       wide_int new_lb, new_ub;
 384       if (min_ovf == wi::OVF_UNDERFLOW)
 385         new_lb = wi::min_value (prec, sgn);
 386       else if (min_ovf == wi::OVF_OVERFLOW)
 387         new_lb = wi::max_value (prec, sgn);
 388       else
 389         new_lb = wmin;
 390
 391       if (max_ovf == wi::OVF_UNDERFLOW)
 392         new_ub = wi::min_value (prec, sgn);
 393       else if (max_ovf == wi::OVF_OVERFLOW)
 394         new_ub = wi::max_value (prec, sgn);
 395       else
 396         new_ub = wmax;
 397
 398       r.set (wide_int_to_tree (type, new_lb),
 399              wide_int_to_tree (type, new_ub));
 400     }
 401 }
 402
 403 // Create and return a range from a pair of wide-ints.  Canonicalize
 404 // the case where the bounds are swapped.  In which case, we transform
 405 // [10,5] into [MIN,5][10,MAX].
 406
 407 static inline void
 408 create_possibly_reversed_range (irange &r, tree type,
 409                                 const wide_int &new_lb, const wide_int &new_ub)
 410 {
 411   signop s = TYPE_SIGN (type);
 412   // If the bounds are swapped, treat the result as if an overflow occured.
 413   if (wi::gt_p (new_lb, new_ub, s))
 414     value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
 415   else
 416     // Otherwise it's just a normal range.
 417     r.set (wide_int_to_tree (type, new_lb), wide_int_to_tree (type, new_ub));
 418 }
 419
 420 // Return the summary information about boolean range LHS.  If EMPTY/FULL,
 421 // return the equivalent range for TYPE in R; if FALSE/TRUE, do nothing.
 422
 423 bool_range_state
 424 get_bool_state (vrange &r, const vrange &lhs, tree val_type)
 425 {
 426   // If there is no result, then this is unexecutable.
 427   if (lhs.undefined_p ())
 428     {
 429       r.set_undefined ();
 430       return BRS_EMPTY;
 431     }
 432
 433   if (lhs.zero_p ())
 434     return BRS_FALSE;
 435
 436   // For TRUE, we can't just test for [1,1] because Ada can have
 437   // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
 438   if (lhs.contains_p (build_zero_cst (lhs.type ())))
 439     {
 440       r.set_varying (val_type);
 441       return BRS_FULL;
 442     }
 443
 444   return BRS_TRUE;
 445 }
 446
 447
 448 class operator_equal : public range_operator
 449 {
 450   using range_operator::fold_range;
 451   using range_operator::op1_range;
 452   using range_operator::op2_range;
 453 public:
 454   virtual bool fold_range (irange &r, tree type,
 455                            const irange &op1,
 456                            const irange &op2,
 457                            relation_trio = TRIO_VARYING) const;
 458   virtual bool op1_range (irange &r, tree type,
 459                           const irange &lhs,
 460                           const irange &val,
 461                           relation_trio = TRIO_VARYING) const;
 462   virtual bool op2_range (irange &r, tree type,
 463                           const irange &lhs,
 464                           const irange &val,
 465                           relation_trio = TRIO_VARYING) const;
 466   virtual relation_kind op1_op2_relation (const irange &lhs) const;
 467 } op_equal;
 468
 469 // Check if the LHS range indicates a relation between OP1 and OP2.
 470
 471 relation_kind
 472 equal_op1_op2_relation (const irange &lhs)
 473 {
 474   if (lhs.undefined_p ())
 475     return VREL_UNDEFINED;
 476
 477   // FALSE = op1 == op2 indicates NE_EXPR.
 478   if (lhs.zero_p ())
 479     return VREL_NE;
 480
 481   // TRUE = op1 == op2 indicates EQ_EXPR.
 482   if (!lhs.contains_p (build_zero_cst (lhs.type ())))
 483     return VREL_EQ;
 484   return VREL_VARYING;
 485 }
 486
 487 relation_kind
 488 operator_equal::op1_op2_relation (const irange &lhs) const
 489 {
 490   return equal_op1_op2_relation (lhs);
 491 }
 492
 493
 494 bool
 495 operator_equal::fold_range (irange &r, tree type,
 496                             const irange &op1,
 497                             const irange &op2,
 498                             relation_trio rel) const
 499 {
 500   if (relop_early_resolve (r, type, op1, op2, rel, VREL_EQ))
 501     return true;
 502
 503   // We can be sure the values are always equal or not if both ranges
 504   // consist of a single value, and then compare them.
 505   if (wi::eq_p (op1.lower_bound (), op1.upper_bound ())
 506       && wi::eq_p (op2.lower_bound (), op2.upper_bound ()))
 507     {
 508       if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
 509         r = range_true (type);
 510       else
 511         r = range_false (type);
 512     }
 513   else
 514     {
 515       // If ranges do not intersect, we know the range is not equal,
 516       // otherwise we don't know anything for sure.
 517       int_range_max tmp = op1;
 518       tmp.intersect (op2);
 519       if (tmp.undefined_p ())
 520         r = range_false (type);
 521       else
 522         r = range_true_and_false (type);
 523     }
 524   return true;
 525 }
 526
 527 bool
 528 operator_equal::op1_range (irange &r, tree type,
 529                            const irange &lhs,
 530                            const irange &op2,
 531                            relation_trio) const
 532 {
 533   switch (get_bool_state (r, lhs, type))
 534     {
 535     case BRS_TRUE:
 536       // If it's true, the result is the same as OP2.
 537       r = op2;
 538       break;
 539
 540     case BRS_FALSE:
 541       // If the result is false, the only time we know anything is
 542       // if OP2 is a constant.
 543       if (wi::eq_p (op2.lower_bound(), op2.upper_bound()))
 544         {
 545           r = op2;
 546           r.invert ();
 547         }
 548       else
 549         r.set_varying (type);
 550       break;
 551
 552     default:
 553       break;
 554     }
 555   return true;
 556 }
 557
 558 bool
 559 operator_equal::op2_range (irange &r, tree type,
 560                            const irange &lhs,
 561                            const irange &op1,
 562                            relation_trio rel) const
 563 {
 564   return operator_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
 565 }
 566
 567 class operator_not_equal : public range_operator
 568 {
 569   using range_operator::fold_range;
 570   using range_operator::op1_range;
 571   using range_operator::op2_range;
 572 public:
 573   virtual bool fold_range (irange &r, tree type,
 574                            const irange &op1,
 575                            const irange &op2,
 576                            relation_trio = TRIO_VARYING) const;
 577   virtual bool op1_range (irange &r, tree type,
 578                           const irange &lhs,
 579                           const irange &op2,
 580                           relation_trio = TRIO_VARYING) const;
 581   virtual bool op2_range (irange &r, tree type,
 582                           const irange &lhs,
 583                           const irange &op1,
 584                           relation_trio = TRIO_VARYING) const;
 585   virtual relation_kind op1_op2_relation (const irange &lhs) const;
 586 } op_not_equal;
 587
 588 // Check if the LHS range indicates a relation between OP1 and OP2.
 589
 590 relation_kind
 591 not_equal_op1_op2_relation (const irange &lhs)
 592 {
 593   if (lhs.undefined_p ())
 594     return VREL_UNDEFINED;
 595
 596   // FALSE = op1 != op2  indicates EQ_EXPR.
 597   if (lhs.zero_p ())
 598     return VREL_EQ;
 599
 600   // TRUE = op1 != op2  indicates NE_EXPR.
 601   if (!lhs.contains_p (build_zero_cst (lhs.type ())))
 602     return VREL_NE;
 603   return VREL_VARYING;
 604 }
 605
 606 relation_kind
 607 operator_not_equal::op1_op2_relation (const irange &lhs) const
 608 {
 609   return not_equal_op1_op2_relation (lhs);
 610 }
 611
 612 bool
 613 operator_not_equal::fold_range (irange &r, tree type,
 614                                 const irange &op1,
 615                                 const irange &op2,
 616                                 relation_trio rel) const
 617 {
 618   if (relop_early_resolve (r, type, op1, op2, rel, VREL_NE))
 619     return true;
 620
 621   // We can be sure the values are always equal or not if both ranges
 622   // consist of a single value, and then compare them.
 623   if (wi::eq_p (op1.lower_bound (), op1.upper_bound ())
 624       && wi::eq_p (op2.lower_bound (), op2.upper_bound ()))
 625     {
 626       if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
 627         r = range_true (type);
 628       else
 629         r = range_false (type);
 630     }
 631   else
 632     {
 633       // If ranges do not intersect, we know the range is not equal,
 634       // otherwise we don't know anything for sure.
 635       int_range_max tmp = op1;
 636       tmp.intersect (op2);
 637       if (tmp.undefined_p ())
 638         r = range_true (type);
 639       else
 640         r = range_true_and_false (type);
 641     }
 642   return true;
 643 }
 644
 645 bool
 646 operator_not_equal::op1_range (irange &r, tree type,
 647                                const irange &lhs,
 648                                const irange &op2,
 649                                relation_trio) const
 650 {
 651   switch (get_bool_state (r, lhs, type))
 652     {
 653     case BRS_TRUE:
 654       // If the result is true, the only time we know anything is if
 655       // OP2 is a constant.
 656       if (wi::eq_p (op2.lower_bound(), op2.upper_bound()))
 657         {
 658           r = op2;
 659           r.invert ();
 660         }
 661       else
 662         r.set_varying (type);
 663       break;
 664
 665     case BRS_FALSE:
 666       // If it's false, the result is the same as OP2.
 667       r = op2;
 668       break;
 669
 670     default:
 671       break;
 672     }
 673   return true;
 674 }
 675
 676
 677 bool
 678 operator_not_equal::op2_range (irange &r, tree type,
 679                                const irange &lhs,
 680                                const irange &op1,
 681                                relation_trio rel) const
 682 {
 683   return operator_not_equal::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
 684 }
 685
 686 // (X < VAL) produces the range of [MIN, VAL - 1].
 687
 688 static void
 689 build_lt (irange &r, tree type, const wide_int &val)
 690 {
 691   wi::overflow_type ov;
 692   wide_int lim;
 693   signop sgn = TYPE_SIGN (type);
 694
 695   // Signed 1 bit cannot represent 1 for subtraction.
 696   if (sgn == SIGNED)
 697     lim = wi::add (val, -1, sgn, &ov);
 698   else
 699     lim = wi::sub (val, 1, sgn, &ov);
 700
 701   // If val - 1 underflows, check if X < MIN, which is an empty range.
 702   if (ov)
 703     r.set_undefined ();
 704   else
 705     r = int_range<1> (type, min_limit (type), lim);
 706 }
 707
 708 // (X <= VAL) produces the range of [MIN, VAL].
 709
 710 static void
 711 build_le (irange &r, tree type, const wide_int &val)
 712 {
 713   r = int_range<1> (type, min_limit (type), val);
 714 }
 715
 716 // (X > VAL) produces the range of [VAL + 1, MAX].
 717
 718 static void
 719 build_gt (irange &r, tree type, const wide_int &val)
 720 {
 721   wi::overflow_type ov;
 722   wide_int lim;
 723   signop sgn = TYPE_SIGN (type);
 724
 725   // Signed 1 bit cannot represent 1 for addition.
 726   if (sgn == SIGNED)
 727     lim = wi::sub (val, -1, sgn, &ov);
 728   else
 729     lim = wi::add (val, 1, sgn, &ov);
 730   // If val + 1 overflows, check is for X > MAX, which is an empty range.
 731   if (ov)
 732     r.set_undefined ();
 733   else
 734     r = int_range<1> (type, lim, max_limit (type));
 735 }
 736
 737 // (X >= val) produces the range of [VAL, MAX].
 738
 739 static void
 740 build_ge (irange &r, tree type, const wide_int &val)
 741 {
 742   r = int_range<1> (type, val, max_limit (type));
 743 }
 744
 745
 746 class operator_lt :  public range_operator
 747 {
 748   using range_operator::fold_range;
 749   using range_operator::op1_range;
 750   using range_operator::op2_range;
 751 public:
 752   virtual bool fold_range (irange &r, tree type,
 753                            const irange &op1,
 754                            const irange &op2,
 755                            relation_trio = TRIO_VARYING) const;
 756   virtual bool op1_range (irange &r, tree type,
 757                           const irange &lhs,
 758                           const irange &op2,
 759                           relation_trio = TRIO_VARYING) const;
 760   virtual bool op2_range (irange &r, tree type,
 761                           const irange &lhs,
 762                           const irange &op1,
 763                           relation_trio = TRIO_VARYING) const;
 764   virtual relation_kind op1_op2_relation (const irange &lhs) const;
 765 } op_lt;
 766
 767 // Check if the LHS range indicates a relation between OP1 and OP2.
 768
 769 relation_kind
 770 lt_op1_op2_relation (const irange &lhs)
 771 {
 772   if (lhs.undefined_p ())
 773     return VREL_UNDEFINED;
 774
 775   // FALSE = op1 < op2 indicates GE_EXPR.
 776   if (lhs.zero_p ())
 777     return VREL_GE;
 778
 779   // TRUE = op1 < op2 indicates LT_EXPR.
 780   if (!lhs.contains_p (build_zero_cst (lhs.type ())))
 781     return VREL_LT;
 782   return VREL_VARYING;
 783 }
 784
 785 relation_kind
 786 operator_lt::op1_op2_relation (const irange &lhs) const
 787 {
 788   return lt_op1_op2_relation (lhs);
 789 }
 790
 791 bool
 792 operator_lt::fold_range (irange &r, tree type,
 793                          const irange &op1,
 794                          const irange &op2,
 795                          relation_trio rel) const
 796 {
 797   if (relop_early_resolve (r, type, op1, op2, rel, VREL_LT))
 798     return true;
 799
 800   signop sign = TYPE_SIGN (op1.type ());
 801   gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
 802
 803   if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
 804     r = range_true (type);
 805   else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
 806     r = range_false (type);
 807   // Use nonzero bits to determine if < 0 is false.
 808   else if (op2.zero_p () && !wi::neg_p (op1.get_nonzero_bits (), sign))
 809     r = range_false (type);
 810   else
 811     r = range_true_and_false (type);
 812   return true;
 813 }
 814
 815 bool
 816 operator_lt::op1_range (irange &r, tree type,
 817                         const irange &lhs,
 818                         const irange &op2,
 819                         relation_trio) const
 820 {
 821   switch (get_bool_state (r, lhs, type))
 822     {
 823     case BRS_TRUE:
 824       build_lt (r, type, op2.upper_bound ());
 825       break;
 826
 827     case BRS_FALSE:
 828       build_ge (r, type, op2.lower_bound ());
 829       break;
 830
 831     default:
 832       break;
 833     }
 834   return true;
 835 }
 836
 837 bool
 838 operator_lt::op2_range (irange &r, tree type,
 839                         const irange &lhs,
 840                         const irange &op1,
 841                         relation_trio) const
 842 {
 843   switch (get_bool_state (r, lhs, type))
 844     {
 845     case BRS_TRUE:
 846       build_gt (r, type, op1.lower_bound ());
 847       break;
 848
 849     case BRS_FALSE:
 850       build_le (r, type, op1.upper_bound ());
 851       break;
 852
 853     default:
 854       break;
 855     }
 856   return true;
 857 }
 858
 859
 860 class operator_le :  public range_operator
 861 {
 862   using range_operator::fold_range;
 863   using range_operator::op1_range;
 864   using range_operator::op2_range;
 865 public:
 866   virtual bool fold_range (irange &r, tree type,
 867                            const irange &op1,
 868                            const irange &op2,
 869                            relation_trio = TRIO_VARYING) const;
 870   virtual bool op1_range (irange &r, tree type,
 871                           const irange &lhs,
 872                           const irange &op2,
 873                           relation_trio = TRIO_VARYING) const;
 874   virtual bool op2_range (irange &r, tree type,
 875                           const irange &lhs,
 876                           const irange &op1,
 877                           relation_trio = TRIO_VARYING) const;
 878   virtual relation_kind op1_op2_relation (const irange &lhs) const;
 879 } op_le;
 880
 881 // Check if the LHS range indicates a relation between OP1 and OP2.
 882
 883 relation_kind
 884 le_op1_op2_relation (const irange &lhs)
 885 {
 886   if (lhs.undefined_p ())
 887     return VREL_UNDEFINED;
 888
 889   // FALSE = op1 <= op2 indicates GT_EXPR.
 890   if (lhs.zero_p ())
 891     return VREL_GT;
 892
 893   // TRUE = op1 <= op2 indicates LE_EXPR.
 894   if (!lhs.contains_p (build_zero_cst (lhs.type ())))
 895     return VREL_LE;
 896   return VREL_VARYING;
 897 }
 898
 899 relation_kind
 900 operator_le::op1_op2_relation (const irange &lhs) const
 901 {
 902   return le_op1_op2_relation (lhs);
 903 }
 904
 905 bool
 906 operator_le::fold_range (irange &r, tree type,
 907                          const irange &op1,
 908                          const irange &op2,
 909                          relation_trio rel) const
 910 {
 911   if (relop_early_resolve (r, type, op1, op2, rel, VREL_LE))
 912     return true;
 913
 914   signop sign = TYPE_SIGN (op1.type ());
 915   gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
 916
 917   if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
 918     r = range_true (type);
 919   else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
 920     r = range_false (type);
 921   else
 922     r = range_true_and_false (type);
 923   return true;
 924 }
 925
 926 bool
 927 operator_le::op1_range (irange &r, tree type,
 928                         const irange &lhs,
 929                         const irange &op2,
 930                         relation_trio) const
 931 {
 932   switch (get_bool_state (r, lhs, type))
 933     {
 934     case BRS_TRUE:
 935       build_le (r, type, op2.upper_bound ());
 936       break;
 937
 938     case BRS_FALSE:
 939       build_gt (r, type, op2.lower_bound ());
 940       break;
 941
 942     default:
 943       break;
 944     }
 945   return true;
 946 }
 947
 948 bool
 949 operator_le::op2_range (irange &r, tree type,
 950                         const irange &lhs,
 951                         const irange &op1,
 952                         relation_trio) const
 953 {
 954   switch (get_bool_state (r, lhs, type))
 955     {
 956     case BRS_TRUE:
 957       build_ge (r, type, op1.lower_bound ());
 958       break;
 959
 960     case BRS_FALSE:
 961       build_lt (r, type, op1.upper_bound ());
 962       break;
 963
 964     default:
 965       break;
 966     }
 967   return true;
 968 }
 969
 970
 971 class operator_gt :  public range_operator
 972 {
 973   using range_operator::fold_range;
 974   using range_operator::op1_range;
 975   using range_operator::op2_range;
 976 public:
 977   virtual bool fold_range (irange &r, tree type,
 978                            const irange &op1,
 979                            const irange &op2,
 980                            relation_trio = TRIO_VARYING) const;
 981   virtual bool op1_range (irange &r, tree type,
 982                           const irange &lhs,
 983                           const irange &op2,
 984                           relation_trio = TRIO_VARYING) const;
 985   virtual bool op2_range (irange &r, tree type,
 986                           const irange &lhs,
 987                           const irange &op1,
 988                           relation_trio = TRIO_VARYING) const;
 989   virtual relation_kind op1_op2_relation (const irange &lhs) const;
 990 } op_gt;
 991
 992 // Check if the LHS range indicates a relation between OP1 and OP2.
 993
 994 relation_kind
 995 gt_op1_op2_relation (const irange &lhs)
 996 {
 997   if (lhs.undefined_p ())
 998     return VREL_UNDEFINED;
 999
1000   // FALSE = op1 > op2 indicates LE_EXPR.
1001   if (lhs.zero_p ())
1002     return VREL_LE;
1003
1004   // TRUE = op1 > op2 indicates GT_EXPR.
1005   if (!lhs.contains_p (build_zero_cst (lhs.type ())))
1006     return VREL_GT;
1007   return VREL_VARYING;
1008 }
1009
1010 relation_kind
1011 operator_gt::op1_op2_relation (const irange &lhs) const
1012 {
1013   return gt_op1_op2_relation (lhs);
1014 }
1015
1016
1017 bool
1018 operator_gt::fold_range (irange &r, tree type,
1019                          const irange &op1, const irange &op2,
1020                          relation_trio rel) const
1021 {
1022   if (relop_early_resolve (r, type, op1, op2, rel, VREL_GT))
1023     return true;
1024
1025   signop sign = TYPE_SIGN (op1.type ());
1026   gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1027
1028   if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
1029     r = range_true (type);
1030   else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
1031     r = range_false (type);
1032   else
1033     r = range_true_and_false (type);
1034   return true;
1035 }
1036
1037 bool
1038 operator_gt::op1_range (irange &r, tree type,
1039                         const irange &lhs, const irange &op2,
1040                         relation_trio) const
1041 {
1042   switch (get_bool_state (r, lhs, type))
1043     {
1044     case BRS_TRUE:
1045       build_gt (r, type, op2.lower_bound ());
1046       break;
1047
1048     case BRS_FALSE:
1049       build_le (r, type, op2.upper_bound ());
1050       break;
1051
1052     default:
1053       break;
1054     }
1055   return true;
1056 }
1057
1058 bool
1059 operator_gt::op2_range (irange &r, tree type,
1060                         const irange &lhs,
1061                         const irange &op1,
1062                         relation_trio) const
1063 {
1064   switch (get_bool_state (r, lhs, type))
1065     {
1066     case BRS_TRUE:
1067       build_lt (r, type, op1.upper_bound ());
1068       break;
1069
1070     case BRS_FALSE:
1071       build_ge (r, type, op1.lower_bound ());
1072       break;
1073
1074     default:
1075       break;
1076     }
1077   return true;
1078 }
1079
1080
1081 class operator_ge :  public range_operator
1082 {
1083   using range_operator::fold_range;
1084   using range_operator::op1_range;
1085   using range_operator::op2_range;
1086 public:
1087   virtual bool fold_range (irange &r, tree type,
1088                            const irange &op1,
1089                            const irange &op2,
1090                            relation_trio = TRIO_VARYING) const;
1091   virtual bool op1_range (irange &r, tree type,
1092                           const irange &lhs,
1093                           const irange &op2,
1094                           relation_trio = TRIO_VARYING) const;
1095   virtual bool op2_range (irange &r, tree type,
1096                           const irange &lhs,
1097                           const irange &op1,
1098                           relation_trio = TRIO_VARYING) const;
1099   virtual relation_kind op1_op2_relation (const irange &lhs) const;
1100 } op_ge;
1101
1102 // Check if the LHS range indicates a relation between OP1 and OP2.
1103
1104 relation_kind
1105 ge_op1_op2_relation (const irange &lhs)
1106 {
1107   if (lhs.undefined_p ())
1108     return VREL_UNDEFINED;
1109
1110   // FALSE = op1 >= op2 indicates LT_EXPR.
1111   if (lhs.zero_p ())
1112     return VREL_LT;
1113
1114   // TRUE = op1 >= op2 indicates GE_EXPR.
1115   if (!lhs.contains_p (build_zero_cst (lhs.type ())))
1116     return VREL_GE;
1117   return VREL_VARYING;
1118 }
1119
1120 relation_kind
1121 operator_ge::op1_op2_relation (const irange &lhs) const
1122 {
1123   return ge_op1_op2_relation (lhs);
1124 }
1125
1126 bool
1127 operator_ge::fold_range (irange &r, tree type,
1128                          const irange &op1,
1129                          const irange &op2,
1130                          relation_trio rel) const
1131 {
1132   if (relop_early_resolve (r, type, op1, op2, rel, VREL_GE))
1133     return true;
1134
1135   signop sign = TYPE_SIGN (op1.type ());
1136   gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
1137
1138   if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
1139     r = range_true (type);
1140   else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
1141     r = range_false (type);
1142   else
1143     r = range_true_and_false (type);
1144   return true;
1145 }
1146
1147 bool
1148 operator_ge::op1_range (irange &r, tree type,
1149                         const irange &lhs,
1150                         const irange &op2,
1151                         relation_trio) const
1152 {
1153   switch (get_bool_state (r, lhs, type))
1154     {
1155     case BRS_TRUE:
1156       build_ge (r, type, op2.lower_bound ());
1157       break;
1158
1159     case BRS_FALSE:
1160       build_lt (r, type, op2.upper_bound ());
1161       break;
1162
1163     default:
1164       break;
1165     }
1166   return true;
1167 }
1168
1169 bool
1170 operator_ge::op2_range (irange &r, tree type,
1171                         const irange &lhs,
1172                         const irange &op1,
1173                         relation_trio) const
1174 {
1175   switch (get_bool_state (r, lhs, type))
1176     {
1177     case BRS_TRUE:
1178       build_le (r, type, op1.upper_bound ());
1179       break;
1180
1181     case BRS_FALSE:
1182       build_gt (r, type, op1.lower_bound ());
1183       break;
1184
1185     default:
1186       break;
1187     }
1188   return true;
1189 }
1190
1191
1192 class operator_plus : public range_operator
1193 {
1194   using range_operator::op1_range;
1195   using range_operator::op2_range;
1196   using range_operator::lhs_op1_relation;
1197   using range_operator::lhs_op2_relation;
1198 public:
1199   virtual bool op1_range (irange &r, tree type,
1200                           const irange &lhs,
1201                           const irange &op2,
1202                           relation_trio) const;
1203   virtual bool op2_range (irange &r, tree type,
1204                           const irange &lhs,
1205                           const irange &op1,
1206                           relation_trio) const;
1207   virtual void wi_fold (irange &r, tree type,
1208                         const wide_int &lh_lb,
1209                         const wide_int &lh_ub,
1210                         const wide_int &rh_lb,
1211                         const wide_int &rh_ub) const;
1212   virtual relation_kind lhs_op1_relation (const irange &lhs, const irange &op1,
1213                                           const irange &op2,
1214                                           relation_kind rel) const;
1215   virtual relation_kind lhs_op2_relation (const irange &lhs, const irange &op1,
1216                                           const irange &op2,
1217                                           relation_kind rel) const;
1218 } op_plus;
1219
1220 // Check to see if the range of OP2 indicates anything about the relation
1221 // between LHS and OP1.
1222
1223 relation_kind
1224 operator_plus::lhs_op1_relation (const irange &lhs,
1225                                  const irange &op1,
1226                                  const irange &op2,
1227                                  relation_kind) const
1228 {
1229   if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
1230     return VREL_VARYING;
1231
1232   tree type = lhs.type ();
1233   unsigned prec = TYPE_PRECISION (type);
1234   wi::overflow_type ovf1, ovf2;
1235   signop sign = TYPE_SIGN (type);
1236
1237   // LHS = OP1 + 0  indicates LHS == OP1.
1238   if (op2.zero_p ())
1239     return VREL_EQ;
1240
1241   if (TYPE_OVERFLOW_WRAPS (type))
1242     {
1243       wi::add (op1.lower_bound (), op2.lower_bound (), sign, &ovf1);
1244       wi::add (op1.upper_bound (), op2.upper_bound (), sign, &ovf2);
1245     }
1246   else
1247     ovf1 = ovf2 = wi::OVF_NONE;
1248
1249   // Never wrapping additions.
1250   if (!ovf1 && !ovf2)
1251     {
1252       // Positive op2 means lhs > op1.
1253       if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1254         return VREL_GT;
1255       if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1256         return VREL_GE;
1257
1258       // Negative op2 means lhs < op1.
1259       if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1260         return VREL_LT;
1261       if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1262         return VREL_LE;
1263     }
1264   // Always wrapping additions.
1265   else if (ovf1 && ovf1 == ovf2)
1266     {
1267       // Positive op2 means lhs < op1.
1268       if (wi::gt_p (op2.lower_bound (), wi::zero (prec), sign))
1269         return VREL_LT;
1270       if (wi::ge_p (op2.lower_bound (), wi::zero (prec), sign))
1271         return VREL_LE;
1272
1273       // Negative op2 means lhs > op1.
1274       if (wi::lt_p (op2.upper_bound (), wi::zero (prec), sign))
1275         return VREL_GT;
1276       if (wi::le_p (op2.upper_bound (), wi::zero (prec), sign))
1277         return VREL_GE;
1278     }
1279
1280   // If op2 does not contain 0, then LHS and OP1 can never be equal.
1281   if (!range_includes_zero_p (&op2))
1282     return VREL_NE;
1283
1284   return VREL_VARYING;
1285 }
1286
1287 // PLUS is symmetrical, so we can simply call lhs_op1_relation with reversed
1288 // operands.
1289
1290 relation_kind
1291 operator_plus::lhs_op2_relation (const irange &lhs, const irange &op1,
1292                                  const irange &op2, relation_kind rel) const
1293 {
1294   return lhs_op1_relation (lhs, op2, op1, rel);
1295 }
1296
1297 void
1298 operator_plus::wi_fold (irange &r, tree type,
1299                         const wide_int &lh_lb, const wide_int &lh_ub,
1300                         const wide_int &rh_lb, const wide_int &rh_ub) const
1301 {
1302   wi::overflow_type ov_lb, ov_ub;
1303   signop s = TYPE_SIGN (type);
1304   wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
1305   wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
1306   value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1307 }
1308
1309 // Given addition or subtraction, determine the possible NORMAL ranges and
1310 // OVERFLOW ranges given an OFFSET range.  ADD_P is true for addition.
1311 // Return the relation that exists between the LHS and OP1 in order for the
1312 // NORMAL range to apply.
1313 // a return value of VREL_VARYING means no ranges were applicable.
1314
1315 static relation_kind
1316 plus_minus_ranges (irange &r_ov, irange &r_normal, const irange &offset,
1317                 bool add_p)
1318 {
1319   relation_kind kind = VREL_VARYING;
1320   // For now, only deal with constant adds.  This could be extended to ranges
1321   // when someone is so motivated.
1322   if (!offset.singleton_p () || offset.zero_p ())
1323     return kind;
1324
1325   // Always work with a positive offset.  ie a+ -2 -> a-2  and a- -2 > a+2
1326   wide_int off = offset.lower_bound ();
1327   if (wi::neg_p (off, SIGNED))
1328     {
1329       add_p = !add_p;
1330       off = wi::neg (off);
1331     }
1332
1333   wi::overflow_type ov;
1334   tree type = offset.type ();
1335   unsigned prec = TYPE_PRECISION (type);
1336   wide_int ub;
1337   wide_int lb;
1338   // calculate the normal range and relation for the operation.
1339   if (add_p)
1340     {
1341       //  [ 0 , INF - OFF]
1342       lb = wi::zero (prec);
1343       ub = wi::sub (wi::to_wide (vrp_val_max (type)), off, UNSIGNED, &ov);
1344       kind = VREL_GT;
1345     }
1346   else
1347     {
1348       //  [ OFF, INF ]
1349       lb = off;
1350       ub = wi::to_wide (vrp_val_max (type));
1351       kind = VREL_LT;
1352     }
1353   int_range<2> normal_range (type, lb, ub);
1354   int_range<2> ov_range (type, lb, ub, VR_ANTI_RANGE);
1355
1356   r_ov = ov_range;
1357   r_normal = normal_range;
1358   return kind;
1359 }
1360
1361 // Once op1 has been calculated by operator_plus or operator_minus, check
1362 // to see if the relation passed causes any part of the calculation to
1363 // be not possible.  ie
1364 // a_2 = b_3 + 1  with a_2 < b_3 can refine the range of b_3 to [INF, INF]
1365 // and that further refines a_2 to [0, 0].
1366 // R is the value of op1, OP2 is the offset being added/subtracted, REL is the
1367 // relation between LHS relatoin OP1  and ADD_P is true for PLUS, false for
1368 // MINUS.    IF any adjustment can be made, R will reflect it.
1369
1370 static void
1371 adjust_op1_for_overflow (irange &r, const irange &op2, relation_kind rel,
1372                          bool add_p)
1373 {
1374   if (r.undefined_p ())
1375     return;
1376   tree type = r.type ();
1377   // Check for unsigned overflow and calculate the overflow part.
1378   signop s = TYPE_SIGN (type);
1379   if (!TYPE_OVERFLOW_WRAPS (type) || s == SIGNED)
1380     return;
1381
1382   // Only work with <, <=, >, >= relations.
1383   if (!relation_lt_le_gt_ge_p (rel))
1384     return;
1385
1386   // Get the ranges for this offset.
1387   int_range_max normal, overflow;
1388   relation_kind k = plus_minus_ranges (overflow, normal, op2, add_p);
1389
1390   // VREL_VARYING means there are no adjustments.
1391   if (k == VREL_VARYING)
1392     return;
1393
1394   // If the relations match use the normal range, otherwise use overflow range.
1395   if (relation_intersect (k, rel) == k)
1396     r.intersect (normal);
1397   else
1398     r.intersect (overflow);
1399   return;
1400 }
1401
1402 bool
1403 operator_plus::op1_range (irange &r, tree type,
1404                           const irange &lhs,
1405                           const irange &op2,
1406                           relation_trio trio) const
1407 {
1408   if (lhs.undefined_p ())
1409     return false;
1410   // Start with the default operation.
1411   range_op_handler minus (MINUS_EXPR, type);
1412   if (!minus)
1413     return false;
1414   bool res = minus.fold_range (r, type, lhs, op2);
1415   relation_kind rel = trio.lhs_op2 ();
1416   // Check for a relation refinement.
1417   if (res)
1418     adjust_op1_for_overflow (r, op2, rel, true /* PLUS_EXPR */);
1419   return res;
1420 }
1421
1422 bool
1423 operator_plus::op2_range (irange &r, tree type,
1424                           const irange &lhs,
1425                           const irange &op1,
1426                           relation_trio rel) const
1427 {
1428   return op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1429 }
1430
1431
1432 class operator_minus : public range_operator
1433 {
1434   using range_operator::fold_range;
1435   using range_operator::op1_range;
1436   using range_operator::op2_range;
1437 public:
1438   virtual bool op1_range (irange &r, tree type,
1439                           const irange &lhs,
1440                           const irange &op2,
1441                           relation_trio) const;
1442   virtual bool op2_range (irange &r, tree type,
1443                           const irange &lhs,
1444                           const irange &op1,
1445                           relation_trio) const;
1446   virtual void wi_fold (irange &r, tree type,
1447                         const wide_int &lh_lb,
1448                         const wide_int &lh_ub,
1449                         const wide_int &rh_lb,
1450                         const wide_int &rh_ub) const;
1451   virtual relation_kind lhs_op1_relation (const irange &lhs,
1452                                            const irange &op1,
1453                                            const irange &op2,
1454                                            relation_kind rel) const;
1455   virtual bool op1_op2_relation_effect (irange &lhs_range,
1456                                         tree type,
1457                                         const irange &op1_range,
1458                                         const irange &op2_range,
1459                                         relation_kind rel) const;
1460 } op_minus;
1461
1462 void
1463 operator_minus::wi_fold (irange &r, tree type,
1464                          const wide_int &lh_lb, const wide_int &lh_ub,
1465                          const wide_int &rh_lb, const wide_int &rh_ub) const
1466 {
1467   wi::overflow_type ov_lb, ov_ub;
1468   signop s = TYPE_SIGN (type);
1469   wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
1470   wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
1471   value_range_with_overflow (r, type, new_lb, new_ub, ov_lb, ov_ub);
1472 }
1473
1474
1475 // Return the relation between LHS and OP1 based on the relation between
1476 // OP1 and OP2.
1477
1478 relation_kind
1479 operator_minus::lhs_op1_relation (const irange &, const irange &op1,
1480                                   const irange &, relation_kind rel) const
1481 {
1482   if (!op1.undefined_p () && TYPE_SIGN (op1.type ()) == UNSIGNED)
1483     switch (rel)
1484       {
1485       case VREL_GT:
1486       case VREL_GE:
1487         return VREL_LE;
1488       default:
1489         break;
1490       }
1491   return VREL_VARYING;
1492 }
1493
1494 // Check to see if the relation REL between OP1 and OP2 has any effect on the
1495 // LHS of the expression.  If so, apply it to LHS_RANGE.  This is a helper
1496 // function for both MINUS_EXPR and POINTER_DIFF_EXPR.
1497
1498 static bool
1499 minus_op1_op2_relation_effect (irange &lhs_range, tree type,
1500                                const irange &op1_range ATTRIBUTE_UNUSED,
1501                                const irange &op2_range ATTRIBUTE_UNUSED,
1502                                relation_kind rel)
1503 {
1504   if (rel == VREL_VARYING)
1505     return false;
1506
1507   int_range<2> rel_range;
1508   unsigned prec = TYPE_PRECISION (type);
1509   signop sgn = TYPE_SIGN (type);
1510
1511   // == and != produce [0,0] and ~[0,0] regardless of wrapping.
1512   if (rel == VREL_EQ)
1513     rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec));
1514   else if (rel == VREL_NE)
1515     rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
1516                               VR_ANTI_RANGE);
1517   else if (TYPE_OVERFLOW_WRAPS (type))
1518     {
1519       switch (rel)
1520         {
1521           // For wrapping signed values and unsigned, if op1 > op2 or
1522           // op1 < op2, then op1 - op2 can be restricted to ~[0, 0].
1523           case VREL_GT:
1524           case VREL_LT:
1525               rel_range = int_range<2> (type, wi::zero (prec), wi::zero (prec),
1526                                         VR_ANTI_RANGE);
1527             break;
1528           default:
1529             return false;
1530         }
1531     }
1532   else
1533     {
1534       switch (rel)
1535         {
1536           // op1 > op2, op1 - op2 can be restricted to [1, +INF]
1537           case VREL_GT:
1538             rel_range = int_range<2> (type, wi::one (prec),
1539                                       wi::max_value (prec, sgn));
1540             break;
1541           // op1 >= op2, op1 - op2 can be restricted to [0, +INF]
1542           case VREL_GE:
1543             rel_range = int_range<2> (type, wi::zero (prec),
1544                                       wi::max_value (prec, sgn));
1545             break;
1546           // op1 < op2, op1 - op2 can be restricted to [-INF, -1]
1547           case VREL_LT:
1548             rel_range = int_range<2> (type, wi::min_value (prec, sgn),
1549                                       wi::minus_one (prec));
1550             break;
1551           // op1 <= op2, op1 - op2 can be restricted to [-INF, 0]
1552           case VREL_LE:
1553             rel_range = int_range<2> (type, wi::min_value (prec, sgn),
1554                                       wi::zero (prec));
1555             break;
1556           default:
1557             return false;
1558         }
1559     }
1560   lhs_range.intersect (rel_range);
1561   return true;
1562 }
1563
1564 bool
1565 operator_minus::op1_op2_relation_effect (irange &lhs_range, tree type,
1566                                          const irange &op1_range,
1567                                          const irange &op2_range,
1568                                          relation_kind rel) const
1569 {
1570   return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
1571                                         rel);
1572 }
1573
1574 bool
1575 operator_minus::op1_range (irange &r, tree type,
1576                            const irange &lhs,
1577                            const irange &op2,
1578                            relation_trio trio) const
1579 {
1580   if (lhs.undefined_p ())
1581     return false;
1582   // Start with the default operation.
1583   range_op_handler minus (PLUS_EXPR, type);
1584   if (!minus)
1585     return false;
1586   bool res = minus.fold_range (r, type, lhs, op2);
1587   relation_kind rel = trio.lhs_op2 ();
1588   if (res)
1589     adjust_op1_for_overflow (r, op2, rel, false /* PLUS_EXPR */);
1590   return res;
1591
1592 }
1593
1594 bool
1595 operator_minus::op2_range (irange &r, tree type,
1596                            const irange &lhs,
1597                            const irange &op1,
1598                            relation_trio) const
1599 {
1600   if (lhs.undefined_p ())
1601     return false;
1602   return fold_range (r, type, op1, lhs);
1603 }
1604
1605
1606 class operator_pointer_diff : public range_operator
1607 {
1608   virtual bool op1_op2_relation_effect (irange &lhs_range,
1609                                         tree type,
1610                                         const irange &op1_range,
1611                                         const irange &op2_range,
1612                                         relation_kind rel) const;
1613 } op_pointer_diff;
1614
1615 bool
1616 operator_pointer_diff::op1_op2_relation_effect (irange &lhs_range, tree type,
1617                                                 const irange &op1_range,
1618                                                 const irange &op2_range,
1619                                                 relation_kind rel) const
1620 {
1621   return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
1622                                         rel);
1623 }
1624
1625
1626 class operator_min : public range_operator
1627 {
1628 public:
1629   virtual void wi_fold (irange &r, tree type,
1630                         const wide_int &lh_lb,
1631                         const wide_int &lh_ub,
1632                         const wide_int &rh_lb,
1633                         const wide_int &rh_ub) const;
1634 } op_min;
1635
1636 void
1637 operator_min::wi_fold (irange &r, tree type,
1638                        const wide_int &lh_lb, const wide_int &lh_ub,
1639                        const wide_int &rh_lb, const wide_int &rh_ub) const
1640 {
1641   signop s = TYPE_SIGN (type);
1642   wide_int new_lb = wi::min (lh_lb, rh_lb, s);
1643   wide_int new_ub = wi::min (lh_ub, rh_ub, s);
1644   value_range_with_overflow (r, type, new_lb, new_ub);
1645 }
1646
1647
1648 class operator_max : public range_operator
1649 {
1650 public:
1651   virtual void wi_fold (irange &r, tree type,
1652                         const wide_int &lh_lb,
1653                         const wide_int &lh_ub,
1654                         const wide_int &rh_lb,
1655                         const wide_int &rh_ub) const;
1656 } op_max;
1657
1658 void
1659 operator_max::wi_fold (irange &r, tree type,
1660                        const wide_int &lh_lb, const wide_int &lh_ub,
1661                        const wide_int &rh_lb, const wide_int &rh_ub) const
1662 {
1663   signop s = TYPE_SIGN (type);
1664   wide_int new_lb = wi::max (lh_lb, rh_lb, s);
1665   wide_int new_ub = wi::max (lh_ub, rh_ub, s);
1666   value_range_with_overflow (r, type, new_lb, new_ub);
1667 }
1668
1669
1670 class cross_product_operator : public range_operator
1671 {
1672 public:
1673   // Perform an operation between two wide-ints and place the result
1674   // in R.  Return true if the operation overflowed.
1675   virtual bool wi_op_overflows (wide_int &r,
1676                                 tree type,
1677                                 const wide_int &,
1678                                 const wide_int &) const = 0;
1679
1680   // Calculate the cross product of two sets of sub-ranges and return it.
1681   void wi_cross_product (irange &r, tree type,
1682                          const wide_int &lh_lb,
1683                          const wide_int &lh_ub,
1684                          const wide_int &rh_lb,
1685                          const wide_int &rh_ub) const;
1686 };
1687
1688 // Calculate the cross product of two sets of ranges and return it.
1689 //
1690 // Multiplications, divisions and shifts are a bit tricky to handle,
1691 // depending on the mix of signs we have in the two ranges, we need to
1692 // operate on different values to get the minimum and maximum values
1693 // for the new range.  One approach is to figure out all the
1694 // variations of range combinations and do the operations.
1695 //
1696 // However, this involves several calls to compare_values and it is
1697 // pretty convoluted.  It's simpler to do the 4 operations (MIN0 OP
1698 // MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
1699 // figure the smallest and largest values to form the new range.
1700
1701 void
1702 cross_product_operator::wi_cross_product (irange &r, tree type,
1703                                           const wide_int &lh_lb,
1704                                           const wide_int &lh_ub,
1705                                           const wide_int &rh_lb,
1706                                           const wide_int &rh_ub) const
1707 {
1708   wide_int cp1, cp2, cp3, cp4;
1709   // Default to varying.
1710   r.set_varying (type);
1711
1712   // Compute the 4 cross operations, bailing if we get an overflow we
1713   // can't handle.
1714   if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
1715     return;
1716   if (wi::eq_p (lh_lb, lh_ub))
1717     cp3 = cp1;
1718   else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
1719     return;
1720   if (wi::eq_p (rh_lb, rh_ub))
1721     cp2 = cp1;
1722   else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
1723     return;
1724   if (wi::eq_p (lh_lb, lh_ub))
1725     cp4 = cp2;
1726   else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
1727     return;
1728
1729   // Order pairs.
1730   signop sign = TYPE_SIGN (type);
1731   if (wi::gt_p (cp1, cp2, sign))
1732     std::swap (cp1, cp2);
1733   if (wi::gt_p (cp3, cp4, sign))
1734     std::swap (cp3, cp4);
1735
1736   // Choose min and max from the ordered pairs.
1737   wide_int res_lb = wi::min (cp1, cp3, sign);
1738   wide_int res_ub = wi::max (cp2, cp4, sign);
1739   value_range_with_overflow (r, type, res_lb, res_ub);
1740 }
1741
1742
1743 class operator_mult : public cross_product_operator
1744 {
1745   using range_operator::fold_range;
1746   using range_operator::op1_range;
1747   using range_operator::op2_range;
1748 public:
1749   virtual bool fold_range (irange &r, tree type,
1750                            const irange &lh, const irange &rh,
1751                            relation_trio = TRIO_VARYING) const final override;
1752   virtual void wi_fold (irange &r, tree type,
1753                         const wide_int &lh_lb,
1754                         const wide_int &lh_ub,
1755                         const wide_int &rh_lb,
1756                         const wide_int &rh_ub) const final override;
1757   virtual bool wi_op_overflows (wide_int &res, tree type,
1758                                 const wide_int &w0, const wide_int &w1)
1759     const final override;
1760   virtual bool op1_range (irange &r, tree type,
1761                           const irange &lhs,
1762                           const irange &op2,
1763                           relation_trio) const final override;
1764   virtual bool op2_range (irange &r, tree type,
1765                           const irange &lhs,
1766                           const irange &op1,
1767                           relation_trio) const final override;
1768 } op_mult;
1769
1770 bool
1771 operator_mult::fold_range (irange &r, tree type,
1772                            const irange &lh, const irange &rh,
1773                            relation_trio trio) const
1774 {
1775   if (!cross_product_operator::fold_range (r, type, lh, rh, trio))
1776     return false;
1777
1778   if (lh.undefined_p ())
1779     return true;
1780
1781   tree t;
1782   if (rh.singleton_p (&t))
1783     {
1784       wide_int w = wi::to_wide (t);
1785       int shift = wi::exact_log2 (w);
1786       if (shift != -1)
1787         {
1788           wide_int nz = lh.get_nonzero_bits ();
1789           nz = wi::lshift (nz, shift);
1790           r.set_nonzero_bits (nz);
1791         }
1792     }
1793   return true;
1794 }
1795
1796 bool
1797 operator_mult::op1_range (irange &r, tree type,
1798                           const irange &lhs, const irange &op2,
1799                           relation_trio) const
1800 {
1801   tree offset;
1802   if (lhs.undefined_p ())
1803     return false;
1804
1805   // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
1806   // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
1807   // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
1808   if (TYPE_OVERFLOW_WRAPS (type))
1809     return false;
1810
1811   if (op2.singleton_p (&offset) && !integer_zerop (offset))
1812     return range_op_handler (TRUNC_DIV_EXPR, type).fold_range (r, type,
1813                                                                lhs, op2);
1814   return false;
1815 }
1816
1817 bool
1818 operator_mult::op2_range (irange &r, tree type,
1819                           const irange &lhs, const irange &op1,
1820                           relation_trio rel) const
1821 {
1822   return operator_mult::op1_range (r, type, lhs, op1, rel.swap_op1_op2 ());
1823 }
1824
1825 bool
1826 operator_mult::wi_op_overflows (wide_int &res, tree type,
1827                                 const wide_int &w0, const wide_int &w1) const
1828 {
1829   wi::overflow_type overflow = wi::OVF_NONE;
1830   signop sign = TYPE_SIGN (type);
1831   res = wi::mul (w0, w1, sign, &overflow);
1832    if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
1833      {
1834        // For multiplication, the sign of the overflow is given
1835        // by the comparison of the signs of the operands.
1836        if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
1837          res = wi::max_value (w0.get_precision (), sign);
1838        else
1839          res = wi::min_value (w0.get_precision (), sign);
1840        return false;
1841      }
1842    return overflow;
1843 }
1844
1845 void
1846 operator_mult::wi_fold (irange &r, tree type,
1847                         const wide_int &lh_lb, const wide_int &lh_ub,
1848                         const wide_int &rh_lb, const wide_int &rh_ub) const
1849 {
1850   if (TYPE_OVERFLOW_UNDEFINED (type))
1851     {
1852       wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
1853       return;
1854     }
1855
1856   // Multiply the ranges when overflow wraps.  This is basically fancy
1857   // code so we don't drop to varying with an unsigned
1858   // [-3,-1]*[-3,-1].
1859   //
1860   // This test requires 2*prec bits if both operands are signed and
1861   // 2*prec + 2 bits if either is not.  Therefore, extend the values
1862   // using the sign of the result to PREC2.  From here on out,
1863   // everthing is just signed math no matter what the input types
1864   // were.
1865
1866   signop sign = TYPE_SIGN (type);
1867   unsigned prec = TYPE_PRECISION (type);
1868   widest2_int min0 = widest2_int::from (lh_lb, sign);
1869   widest2_int max0 = widest2_int::from (lh_ub, sign);
1870   widest2_int min1 = widest2_int::from (rh_lb, sign);
1871   widest2_int max1 = widest2_int::from (rh_ub, sign);
1872   widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
1873   widest2_int size = sizem1 + 1;
1874
1875   // Canonicalize the intervals.
1876   if (sign == UNSIGNED)
1877     {
1878       if (wi::ltu_p (size, min0 + max0))
1879         {
1880           min0 -= size;
1881           max0 -= size;
1882         }
1883       if (wi::ltu_p (size, min1 + max1))
1884         {
1885           min1 -= size;
1886           max1 -= size;
1887         }
1888     }
1889
1890   // Sort the 4 products so that min is in prod0 and max is in
1891   // prod3.
1892   widest2_int prod0 = min0 * min1;
1893   widest2_int prod1 = min0 * max1;
1894   widest2_int prod2 = max0 * min1;
1895   widest2_int prod3 = max0 * max1;
1896
1897   // min0min1 > max0max1
1898   if (prod0 > prod3)
1899     std::swap (prod0, prod3);
1900
1901   // min0max1 > max0min1
1902   if (prod1 > prod2)
1903     std::swap (prod1, prod2);
1904
1905   if (prod0 > prod1)
1906     std::swap (prod0, prod1);
1907
1908   if (prod2 > prod3)
1909     std::swap (prod2, prod3);
1910
1911   // diff = max - min
1912   prod2 = prod3 - prod0;
1913   if (wi::geu_p (prod2, sizem1))
1914     // The range covers all values.
1915     r.set_varying (type);
1916   else
1917     {
1918       wide_int new_lb = wide_int::from (prod0, prec, sign);
1919       wide_int new_ub = wide_int::from (prod3, prec, sign);
1920       create_possibly_reversed_range (r, type, new_lb, new_ub);
1921     }
1922 }
1923
1924
1925 class operator_div : public cross_product_operator
1926 {
1927 public:
1928   operator_div (enum tree_code c)  { code = c; }
1929   virtual void wi_fold (irange &r, tree type,
1930                         const wide_int &lh_lb,
1931                         const wide_int &lh_ub,
1932                         const wide_int &rh_lb,
1933                         const wide_int &rh_ub) const final override;
1934   virtual bool wi_op_overflows (wide_int &res, tree type,
1935                                 const wide_int &, const wide_int &)
1936     const final override;
1937   virtual bool fold_range (irange &r, tree type,
1938                            const irange &lh, const irange &rh,
1939                            relation_trio trio) const final override;
1940 private:
1941   enum tree_code code;
1942 };
1943
1944 bool
1945 operator_div::fold_range (irange &r, tree type,
1946                           const irange &lh, const irange &rh,
1947                           relation_trio trio) const
1948 {
1949   if (!cross_product_operator::fold_range (r, type, lh, rh, trio))
1950     return false;
1951
1952   if (lh.undefined_p ())
1953     return true;
1954
1955   tree t;
1956   if (code == TRUNC_DIV_EXPR
1957       && rh.singleton_p (&t)
1958       && !wi::neg_p (lh.lower_bound ()))
1959     {
1960       wide_int wi = wi::to_wide (t);
1961       int shift = wi::exact_log2 (wi);
1962       if (shift != -1)
1963         {
1964           wide_int nz = lh.get_nonzero_bits ();
1965           nz = wi::rshift (nz, shift, TYPE_SIGN (type));
1966           r.set_nonzero_bits (nz);
1967         }
1968     }
1969   return true;
1970 }
1971
1972 bool
1973 operator_div::wi_op_overflows (wide_int &res, tree type,
1974                                const wide_int &w0, const wide_int &w1) const
1975 {
1976   if (w1 == 0)
1977     return true;
1978
1979   wi::overflow_type overflow = wi::OVF_NONE;
1980   signop sign = TYPE_SIGN (type);
1981
1982   switch (code)
1983     {
1984     case EXACT_DIV_EXPR:
1985       // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in
1986       // operator_exact_divide.  No need to handle it here.
1987       gcc_unreachable ();
1988       break;
1989     case TRUNC_DIV_EXPR:
1990       res = wi::div_trunc (w0, w1, sign, &overflow);
1991       break;
1992     case FLOOR_DIV_EXPR:
1993       res = wi::div_floor (w0, w1, sign, &overflow);
1994       break;
1995     case ROUND_DIV_EXPR:
1996       res = wi::div_round (w0, w1, sign, &overflow);
1997       break;
1998     case CEIL_DIV_EXPR:
1999       res = wi::div_ceil (w0, w1, sign, &overflow);
2000       break;
2001     default:
2002       gcc_unreachable ();
2003     }
2004
2005   if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
2006     {
2007       // For division, the only case is -INF / -1 = +INF.
2008       res = wi::max_value (w0.get_precision (), sign);
2009       return false;
2010     }
2011   return overflow;
2012 }
2013
2014 void
2015 operator_div::wi_fold (irange &r, tree type,
2016                        const wide_int &lh_lb, const wide_int &lh_ub,
2017                        const wide_int &rh_lb, const wide_int &rh_ub) const
2018 {
2019   const wide_int dividend_min = lh_lb;
2020   const wide_int dividend_max = lh_ub;
2021   const wide_int divisor_min = rh_lb;
2022   const wide_int divisor_max = rh_ub;
2023   signop sign = TYPE_SIGN (type);
2024   unsigned prec = TYPE_PRECISION (type);
2025   wide_int extra_min, extra_max;
2026
2027   // If we know we won't divide by zero, just do the division.
2028   if (!wi_includes_zero_p (type, divisor_min, divisor_max))
2029     {
2030       wi_cross_product (r, type, dividend_min, dividend_max,
2031                        divisor_min, divisor_max);
2032       return;
2033     }
2034
2035   // If we're definitely dividing by zero, there's nothing to do.
2036   if (wi_zero_p (type, divisor_min, divisor_max))
2037     {
2038       r.set_undefined ();
2039       return;
2040     }
2041
2042   // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
2043   // skip any division by zero.
2044
2045   // First divide by the negative numbers, if any.
2046   if (wi::neg_p (divisor_min, sign))
2047     wi_cross_product (r, type, dividend_min, dividend_max,
2048                       divisor_min, wi::minus_one (prec));
2049   else
2050     r.set_undefined ();
2051
2052   // Then divide by the non-zero positive numbers, if any.
2053   if (wi::gt_p (divisor_max, wi::zero (prec), sign))
2054     {
2055       int_range_max tmp;
2056       wi_cross_product (tmp, type, dividend_min, dividend_max,
2057                         wi::one (prec), divisor_max);
2058       r.union_ (tmp);
2059     }
2060   // We shouldn't still have undefined here.
2061   gcc_checking_assert (!r.undefined_p ());
2062 }
2063
2064 operator_div op_trunc_div (TRUNC_DIV_EXPR);
2065 operator_div op_floor_div (FLOOR_DIV_EXPR);
2066 operator_div op_round_div (ROUND_DIV_EXPR);
2067 operator_div op_ceil_div (CEIL_DIV_EXPR);
2068
2069
2070 class operator_exact_divide : public operator_div
2071 {
2072   using range_operator::op1_range;
2073 public:
2074   operator_exact_divide () : operator_div (TRUNC_DIV_EXPR) { }
2075   virtual bool op1_range (irange &r, tree type,
2076                           const irange &lhs,
2077                           const irange &op2,
2078                           relation_trio) const;
2079
2080 } op_exact_div;
2081
2082 bool
2083 operator_exact_divide::op1_range (irange &r, tree type,
2084                                   const irange &lhs,
2085                                   const irange &op2,
2086                                   relation_trio) const
2087 {
2088   if (lhs.undefined_p ())
2089     return false;
2090   tree offset;
2091   // [2, 4] = op1 / [3,3]   since its exact divide, no need to worry about
2092   // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
2093   // We wont bother trying to enumerate all the in between stuff :-P
2094   // TRUE accuraacy is [6,6][9,9][12,12].  This is unlikely to matter most of
2095   // the time however.
2096   // If op2 is a multiple of 2, we would be able to set some non-zero bits.
2097   if (op2.singleton_p (&offset)
2098       && !integer_zerop (offset))
2099     return range_op_handler (MULT_EXPR, type).fold_range (r, type, lhs, op2);
2100   return false;
2101 }
2102
2103
2104 class operator_lshift : public cross_product_operator
2105 {
2106   using range_operator::fold_range;
2107   using range_operator::op1_range;
2108 public:
2109   virtual bool op1_range (irange &r, tree type,
2110                           const irange &lhs,
2111                           const irange &op2,
2112                           relation_trio rel = TRIO_VARYING) const;
2113   virtual bool fold_range (irange &r, tree type,
2114                            const irange &op1,
2115                            const irange &op2,
2116                            relation_trio rel = TRIO_VARYING) const;
2117
2118   virtual void wi_fold (irange &r, tree type,
2119                         const wide_int &lh_lb, const wide_int &lh_ub,
2120                         const wide_int &rh_lb, const wide_int &rh_ub) const;
2121   virtual bool wi_op_overflows (wide_int &res,
2122                                 tree type,
2123                                 const wide_int &,
2124                                 const wide_int &) const;
2125 } op_lshift;
2126
2127 class operator_rshift : public cross_product_operator
2128 {
2129   using range_operator::fold_range;
2130   using range_operator::op1_range;
2131   using range_operator::lhs_op1_relation;
2132 public:
2133   virtual bool fold_range (irange &r, tree type,
2134                            const irange &op1,
2135                            const irange &op2,
2136                            relation_trio rel = TRIO_VARYING) const;
2137   virtual void wi_fold (irange &r, tree type,
2138                         const wide_int &lh_lb,
2139                         const wide_int &lh_ub,
2140                         const wide_int &rh_lb,
2141                         const wide_int &rh_ub) const;
2142   virtual bool wi_op_overflows (wide_int &res,
2143                                 tree type,
2144                                 const wide_int &w0,
2145                                 const wide_int &w1) const;
2146   virtual bool op1_range (irange &, tree type,
2147                           const irange &lhs,
2148                           const irange &op2,
2149                           relation_trio rel = TRIO_VARYING) const;
2150   virtual relation_kind lhs_op1_relation (const irange &lhs,
2151                                            const irange &op1,
2152                                            const irange &op2,
2153                                            relation_kind rel) const;
2154 } op_rshift;
2155
2156
2157 relation_kind
2158 operator_rshift::lhs_op1_relation (const irange &lhs ATTRIBUTE_UNUSED,
2159                                    const irange &op1,
2160                                    const irange &op2,
2161                                    relation_kind) const
2162 {
2163   // If both operands range are >= 0, then the LHS <= op1.
2164   if (!op1.undefined_p () && !op2.undefined_p ()
2165       && wi::ge_p (op1.lower_bound (), 0, TYPE_SIGN (op1.type ()))
2166       && wi::ge_p (op2.lower_bound (), 0, TYPE_SIGN (op2.type ())))
2167     return VREL_LE;
2168   return VREL_VARYING;
2169 }
2170
2171 bool
2172 operator_lshift::fold_range (irange &r, tree type,
2173                              const irange &op1,
2174                              const irange &op2,
2175                              relation_trio rel) const
2176 {
2177   int_range_max shift_range;
2178   if (!get_shift_range (shift_range, type, op2))
2179     {
2180       if (op2.undefined_p ())
2181         r.set_undefined ();
2182       else
2183         r.set_varying (type);
2184       return true;
2185     }
2186
2187   // Transform left shifts by constants into multiplies.
2188   if (shift_range.singleton_p ())
2189     {
2190       unsigned shift = shift_range.lower_bound ().to_uhwi ();
2191       wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
2192       int_range<1> mult (type, tmp, tmp);
2193
2194       // Force wrapping multiplication.
2195       bool saved_flag_wrapv = flag_wrapv;
2196       bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
2197       flag_wrapv = 1;
2198       flag_wrapv_pointer = 1;
2199       bool b = op_mult.fold_range (r, type, op1, mult);
2200       flag_wrapv = saved_flag_wrapv;
2201       flag_wrapv_pointer = saved_flag_wrapv_pointer;
2202       return b;
2203     }
2204   else
2205     // Otherwise, invoke the generic fold routine.
2206     return range_operator::fold_range (r, type, op1, shift_range, rel);
2207 }
2208
2209 void
2210 operator_lshift::wi_fold (irange &r, tree type,
2211                           const wide_int &lh_lb, const wide_int &lh_ub,
2212                           const wide_int &rh_lb, const wide_int &rh_ub) const
2213 {
2214   signop sign = TYPE_SIGN (type);
2215   unsigned prec = TYPE_PRECISION (type);
2216   int overflow_pos = sign == SIGNED ? prec - 1 : prec;
2217   int bound_shift = overflow_pos - rh_ub.to_shwi ();
2218   // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
2219   // overflow.  However, for that to happen, rh.max needs to be zero,
2220   // which means rh is a singleton range of zero, which means we simply return
2221   // [lh_lb, lh_ub] as the range.
2222   if (wi::eq_p (rh_ub, rh_lb) && wi::eq_p (rh_ub, 0))
2223     {
2224       r = int_range<2> (type, lh_lb, lh_ub);
2225       return;
2226     }
2227
2228   wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
2229   wide_int complement = ~(bound - 1);
2230   wide_int low_bound, high_bound;
2231   bool in_bounds = false;
2232
2233   if (sign == UNSIGNED)
2234     {
2235       low_bound = bound;
2236       high_bound = complement;
2237       if (wi::ltu_p (lh_ub, low_bound))
2238         {
2239           // [5, 6] << [1, 2] == [10, 24].
2240           // We're shifting out only zeroes, the value increases
2241           // monotonically.
2242           in_bounds = true;
2243         }
2244       else if (wi::ltu_p (high_bound, lh_lb))
2245         {
2246           // [0xffffff00, 0xffffffff] << [1, 2]
2247           // == [0xfffffc00, 0xfffffffe].
2248           // We're shifting out only ones, the value decreases
2249           // monotonically.
2250           in_bounds = true;
2251         }
2252     }
2253   else
2254     {
2255       // [-1, 1] << [1, 2] == [-4, 4]
2256       low_bound = complement;
2257       high_bound = bound;
2258       if (wi::lts_p (lh_ub, high_bound)
2259           && wi::lts_p (low_bound, lh_lb))
2260         {
2261           // For non-negative numbers, we're shifting out only zeroes,
2262           // the value increases monotonically.  For negative numbers,
2263           // we're shifting out only ones, the value decreases
2264           // monotonically.
2265           in_bounds = true;
2266         }
2267     }
2268
2269   if (in_bounds)
2270     wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2271   else
2272    r.set_varying (type);
2273 }
2274
2275 bool
2276 operator_lshift::wi_op_overflows (wide_int &res, tree type,
2277                                   const wide_int &w0, const wide_int &w1) const
2278 {
2279   signop sign = TYPE_SIGN (type);
2280   if (wi::neg_p (w1))
2281     {
2282       // It's unclear from the C standard whether shifts can overflow.
2283       // The following code ignores overflow; perhaps a C standard
2284       // interpretation ruling is needed.
2285       res = wi::rshift (w0, -w1, sign);
2286     }
2287   else
2288     res = wi::lshift (w0, w1);
2289   return false;
2290 }
2291
2292 bool
2293 operator_lshift::op1_range (irange &r,
2294                             tree type,
2295                             const irange &lhs,
2296                             const irange &op2,
2297                             relation_trio) const
2298 {
2299   if (lhs.undefined_p ())
2300     return false;
2301   tree shift_amount;
2302
2303   if (!lhs.contains_p (build_zero_cst (type)))
2304     r.set_nonzero (type);
2305   else
2306     r.set_varying (type);
2307
2308   if (op2.singleton_p (&shift_amount))
2309     {
2310       wide_int shift = wi::to_wide (shift_amount);
2311       if (wi::lt_p (shift, 0, SIGNED))
2312         return false;
2313       if (wi::ge_p (shift, wi::uhwi (TYPE_PRECISION (type),
2314                                      TYPE_PRECISION (op2.type ())),
2315                     UNSIGNED))
2316         return false;
2317       if (shift == 0)
2318         {
2319           r.intersect (lhs);
2320           return true;
2321         }
2322
2323       // Work completely in unsigned mode to start.
2324       tree utype = type;
2325       int_range_max tmp_range;
2326       if (TYPE_SIGN (type) == SIGNED)
2327         {
2328           int_range_max tmp = lhs;
2329           utype = unsigned_type_for (type);
2330           range_cast (tmp, utype);
2331           op_rshift.fold_range (tmp_range, utype, tmp, op2);
2332         }
2333       else
2334         op_rshift.fold_range (tmp_range, utype, lhs, op2);
2335
2336       // Start with ranges which can produce the LHS by right shifting the
2337       // result by the shift amount.
2338       // ie   [0x08, 0xF0] = op1 << 2 will start with
2339       //      [00001000, 11110000] = op1 << 2
2340       //  [0x02, 0x4C] aka [00000010, 00111100]
2341
2342       // Then create a range from the LB with the least significant upper bit
2343       // set, to the upper bound with all the bits set.
2344       // This would be [0x42, 0xFC] aka [01000010, 11111100].
2345
2346       // Ideally we do this for each subrange, but just lump them all for now.
2347       unsigned low_bits = TYPE_PRECISION (utype)
2348                           - TREE_INT_CST_LOW (shift_amount);
2349       wide_int up_mask = wi::mask (low_bits, true, TYPE_PRECISION (utype));
2350       wide_int new_ub = wi::bit_or (up_mask, tmp_range.upper_bound ());
2351       wide_int new_lb = wi::set_bit (tmp_range.lower_bound (), low_bits);
2352       int_range<2> fill_range (utype, new_lb, new_ub);
2353       tmp_range.union_ (fill_range);
2354
2355       if (utype != type)
2356         range_cast (tmp_range, type);
2357
2358       r.intersect (tmp_range);
2359       return true;
2360     }
2361
2362   return !r.varying_p ();
2363 }
2364
2365 bool
2366 operator_rshift::op1_range (irange &r,
2367                             tree type,
2368                             const irange &lhs,
2369                             const irange &op2,
2370                             relation_trio) const
2371 {
2372   tree shift;
2373   if (lhs.undefined_p ())
2374     return false;
2375   if (op2.singleton_p (&shift))
2376     {
2377       // Ignore nonsensical shifts.
2378       unsigned prec = TYPE_PRECISION (type);
2379       if (wi::ge_p (wi::to_wide (shift),
2380                     wi::uhwi (prec, TYPE_PRECISION (TREE_TYPE (shift))),
2381                     UNSIGNED))
2382         return false;
2383       if (wi::to_wide (shift) == 0)
2384         {
2385           r = lhs;
2386           return true;
2387         }
2388
2389       // Folding the original operation may discard some impossible
2390       // ranges from the LHS.
2391       int_range_max lhs_refined;
2392       op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
2393       lhs_refined.intersect (lhs);
2394       if (lhs_refined.undefined_p ())
2395         {
2396           r.set_undefined ();
2397           return true;
2398         }
2399       int_range_max shift_range (shift, shift);
2400       int_range_max lb, ub;
2401       op_lshift.fold_range (lb, type, lhs_refined, shift_range);
2402       //    LHS
2403       // 0000 0111 = OP1 >> 3
2404       //
2405       // OP1 is anything from 0011 1000 to 0011 1111.  That is, a
2406       // range from LHS<<3 plus a mask of the 3 bits we shifted on the
2407       // right hand side (0x07).
2408       tree mask = fold_build1 (BIT_NOT_EXPR, type,
2409                                fold_build2 (LSHIFT_EXPR, type,
2410                                             build_minus_one_cst (type),
2411                                             shift));
2412       int_range_max mask_range (build_zero_cst (type), mask);
2413       op_plus.fold_range (ub, type, lb, mask_range);
2414       r = lb;
2415       r.union_ (ub);
2416       if (!lhs_refined.contains_p (build_zero_cst (type)))
2417         {
2418           mask_range.invert ();
2419           r.intersect (mask_range);
2420         }
2421       return true;
2422     }
2423   return false;
2424 }
2425
2426 bool
2427 operator_rshift::wi_op_overflows (wide_int &res,
2428                                   tree type,
2429                                   const wide_int &w0,
2430                                   const wide_int &w1) const
2431 {
2432   signop sign = TYPE_SIGN (type);
2433   if (wi::neg_p (w1))
2434     res = wi::lshift (w0, -w1);
2435   else
2436     {
2437       // It's unclear from the C standard whether shifts can overflow.
2438       // The following code ignores overflow; perhaps a C standard
2439       // interpretation ruling is needed.
2440       res = wi::rshift (w0, w1, sign);
2441     }
2442   return false;
2443 }
2444
2445 bool
2446 operator_rshift::fold_range (irange &r, tree type,
2447                              const irange &op1,
2448                              const irange &op2,
2449                              relation_trio rel) const
2450 {
2451   int_range_max shift;
2452   if (!get_shift_range (shift, type, op2))
2453     {
2454       if (op2.undefined_p ())
2455         r.set_undefined ();
2456       else
2457         r.set_varying (type);
2458       return true;
2459     }
2460
2461   return range_operator::fold_range (r, type, op1, shift, rel);
2462 }
2463
2464 void
2465 operator_rshift::wi_fold (irange &r, tree type,
2466                           const wide_int &lh_lb, const wide_int &lh_ub,
2467                           const wide_int &rh_lb, const wide_int &rh_ub) const
2468 {
2469   wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
2470 }
2471
2472
2473 class operator_cast: public range_operator
2474 {
2475   using range_operator::fold_range;
2476   using range_operator::op1_range;
2477 public:
2478   virtual bool fold_range (irange &r, tree type,
2479                            const irange &op1,
2480                            const irange &op2,
2481                            relation_trio rel = TRIO_VARYING) const;
2482   virtual bool op1_range (irange &r, tree type,
2483                           const irange &lhs,
2484                           const irange &op2,
2485                           relation_trio rel = TRIO_VARYING) const;
2486   virtual relation_kind lhs_op1_relation (const irange &lhs,
2487                                           const irange &op1,
2488                                           const irange &op2,
2489                                           relation_kind) const;
2490 private:
2491   bool truncating_cast_p (const irange &inner, const irange &outer) const;
2492   bool inside_domain_p (const wide_int &min, const wide_int &max,
2493                         const irange &outer) const;
2494   void fold_pair (irange &r, unsigned index, const irange &inner,
2495                            const irange &outer) const;
2496 } op_convert;
2497
2498 // Add a partial equivalence between the LHS and op1 for casts.
2499
2500 relation_kind
2501 operator_cast::lhs_op1_relation (const irange &lhs,
2502                                  const irange &op1,
2503                                  const irange &op2 ATTRIBUTE_UNUSED,
2504                                  relation_kind) const
2505 {
2506   if (lhs.undefined_p () || op1.undefined_p ())
2507     return VREL_VARYING;
2508   unsigned lhs_prec = TYPE_PRECISION (lhs.type ());
2509   unsigned op1_prec = TYPE_PRECISION (op1.type ());
2510   // If the result gets sign extended into a larger type check first if this
2511   // qualifies as a partial equivalence.
2512   if (TYPE_SIGN (op1.type ()) == SIGNED && lhs_prec > op1_prec)
2513     {
2514       // If the result is sign extended, and the LHS is larger than op1,
2515       // check if op1's range can be negative as the sign extention will
2516       // cause the upper bits to be 1 instead of 0, invalidating the PE.
2517       int_range<3> negs = range_negatives (op1.type ());
2518       negs.intersect (op1);
2519       if (!negs.undefined_p ())
2520         return VREL_VARYING;
2521     }
2522
2523   unsigned prec = MIN (lhs_prec, op1_prec);
2524   return bits_to_pe (prec);
2525 }
2526
2527 // Return TRUE if casting from INNER to OUTER is a truncating cast.
2528
2529 inline bool
2530 operator_cast::truncating_cast_p (const irange &inner,
2531                                   const irange &outer) const
2532 {
2533   return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
2534 }
2535
2536 // Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
2537
2538 bool
2539 operator_cast::inside_domain_p (const wide_int &min,
2540                                 const wide_int &max,
2541                                 const irange &range) const
2542 {
2543   wide_int domain_min = wi::to_wide (vrp_val_min (range.type ()));
2544   wide_int domain_max = wi::to_wide (vrp_val_max (range.type ()));
2545   signop domain_sign = TYPE_SIGN (range.type ());
2546   return (wi::le_p (min, domain_max, domain_sign)
2547           && wi::le_p (max, domain_max, domain_sign)
2548           && wi::ge_p (min, domain_min, domain_sign)
2549           && wi::ge_p (max, domain_min, domain_sign));
2550 }
2551
2552
2553 // Helper for fold_range which work on a pair at a time.
2554
2555 void
2556 operator_cast::fold_pair (irange &r, unsigned index,
2557                            const irange &inner,
2558                            const irange &outer) const
2559 {
2560   tree inner_type = inner.type ();
2561   tree outer_type = outer.type ();
2562   signop inner_sign = TYPE_SIGN (inner_type);
2563   unsigned outer_prec = TYPE_PRECISION (outer_type);
2564
2565   // check to see if casting from INNER to OUTER is a conversion that
2566   // fits in the resulting OUTER type.
2567   wide_int inner_lb = inner.lower_bound (index);
2568   wide_int inner_ub = inner.upper_bound (index);
2569   if (truncating_cast_p (inner, outer))
2570     {
2571       // We may be able to accomodate a truncating cast if the
2572       // resulting range can be represented in the target type...
2573       if (wi::rshift (wi::sub (inner_ub, inner_lb),
2574                       wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
2575                                 inner_sign) != 0)
2576         {
2577           r.set_varying (outer_type);
2578           return;
2579         }
2580     }
2581   // ...but we must still verify that the final range fits in the
2582   // domain.  This catches -fstrict-enum restrictions where the domain
2583   // range is smaller than what fits in the underlying type.
2584   wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
2585   wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
2586   if (inside_domain_p (min, max, outer))
2587     create_possibly_reversed_range (r, outer_type, min, max);
2588   else
2589     r.set_varying (outer_type);
2590 }
2591
2592
2593 bool
2594 operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
2595                            const irange &inner,
2596                            const irange &outer,
2597                            relation_trio) const
2598 {
2599   if (empty_range_varying (r, type, inner, outer))
2600     return true;
2601
2602   gcc_checking_assert (outer.varying_p ());
2603   gcc_checking_assert (inner.num_pairs () > 0);
2604
2605   // Avoid a temporary by folding the first pair directly into the result.
2606   fold_pair (r, 0, inner, outer);
2607
2608   // Then process any additonal pairs by unioning with their results.
2609   for (unsigned x = 1; x < inner.num_pairs (); ++x)
2610     {
2611       int_range_max tmp;
2612       fold_pair (tmp, x, inner, outer);
2613       r.union_ (tmp);
2614       if (r.varying_p ())
2615         return true;
2616     }
2617
2618   // Update the nonzero mask.  Truncating casts are problematic unless
2619   // the conversion fits in the resulting outer type.
2620   wide_int nz = inner.get_nonzero_bits ();
2621   if (truncating_cast_p (inner, outer)
2622       && wi::rshift (nz, wi::uhwi (TYPE_PRECISION (outer.type ()),
2623                                    TYPE_PRECISION (inner.type ())),
2624                      TYPE_SIGN (inner.type ())) != 0)
2625     return true;
2626   nz = wide_int::from (nz, TYPE_PRECISION (type), TYPE_SIGN (inner.type ()));
2627   r.set_nonzero_bits (nz);
2628
2629   return true;
2630 }
2631
2632 bool
2633 operator_cast::op1_range (irange &r, tree type,
2634                           const irange &lhs,
2635                           const irange &op2,
2636                           relation_trio) const
2637 {
2638   if (lhs.undefined_p ())
2639     return false;
2640   tree lhs_type = lhs.type ();
2641   gcc_checking_assert (types_compatible_p (op2.type(), type));
2642
2643   // If we are calculating a pointer, shortcut to what we really care about.
2644   if (POINTER_TYPE_P (type))
2645     {
2646       // Conversion from other pointers or a constant (including 0/NULL)
2647       // are straightforward.
2648       if (POINTER_TYPE_P (lhs.type ())
2649           || (lhs.singleton_p ()
2650               && TYPE_PRECISION (lhs.type ()) >= TYPE_PRECISION (type)))
2651         {
2652           r = lhs;
2653           range_cast (r, type);
2654         }
2655       else
2656         {
2657           // If the LHS is not a pointer nor a singleton, then it is
2658           // either VARYING or non-zero.
2659           if (!lhs.contains_p (build_zero_cst (lhs.type ())))
2660             r.set_nonzero (type);
2661           else
2662             r.set_varying (type);
2663         }
2664       r.intersect (op2);
2665       return true;
2666     }
2667
2668   if (truncating_cast_p (op2, lhs))
2669     {
2670       if (lhs.varying_p ())
2671         r.set_varying (type);
2672       else
2673         {
2674           // We want to insert the LHS as an unsigned value since it
2675           // would not trigger the signed bit of the larger type.
2676           int_range_max converted_lhs = lhs;
2677           range_cast (converted_lhs, unsigned_type_for (lhs_type));
2678           range_cast (converted_lhs, type);
2679           // Start by building the positive signed outer range for the type.
2680           wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
2681                                               TYPE_PRECISION (type));
2682           r = int_range<1> (type, lim, wi::max_value (TYPE_PRECISION (type),
2683                                                       SIGNED));
2684           // For the signed part, we need to simply union the 2 ranges now.
2685           r.union_ (converted_lhs);
2686
2687           // Create maximal negative number outside of LHS bits.
2688           lim = wi::mask (TYPE_PRECISION (lhs_type), true,
2689                           TYPE_PRECISION (type));
2690           // Add this to the unsigned LHS range(s).
2691           int_range_max lim_range (type, lim, lim);
2692           int_range_max lhs_neg;
2693           range_op_handler (PLUS_EXPR, type).fold_range (lhs_neg, type,
2694                                                          converted_lhs,
2695                                                          lim_range);
2696           // lhs_neg now has all the negative versions of the LHS.
2697           // Now union in all the values from SIGNED MIN (0x80000) to
2698           // lim-1 in order to fill in all the ranges with the upper
2699           // bits set.
2700
2701           // PR 97317.  If the lhs has only 1 bit less precision than the rhs,
2702           // we don't need to create a range from min to lim-1
2703           // calculate neg range traps trying to create [lim, lim - 1].
2704           wide_int min_val = wi::min_value (TYPE_PRECISION (type), SIGNED);
2705           if (lim != min_val)
2706             {
2707               int_range_max neg (type,
2708                                  wi::min_value (TYPE_PRECISION (type),
2709                                                 SIGNED),
2710                                  lim - 1);
2711               lhs_neg.union_ (neg);
2712             }
2713           // And finally, munge the signed and unsigned portions.
2714           r.union_ (lhs_neg);
2715         }
2716       // And intersect with any known value passed in the extra operand.
2717       r.intersect (op2);
2718       return true;
2719     }
2720
2721   int_range_max tmp;
2722   if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
2723     tmp = lhs;
2724   else
2725     {
2726       // The cast is not truncating, and the range is restricted to
2727       // the range of the RHS by this assignment.
2728       //
2729       // Cast the range of the RHS to the type of the LHS.
2730       fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
2731       // Intersect this with the LHS range will produce the range,
2732       // which will be cast to the RHS type before returning.
2733       tmp.intersect (lhs);
2734     }
2735
2736   // Cast the calculated range to the type of the RHS.
2737   fold_range (r, type, tmp, int_range<1> (type));
2738   return true;
2739 }
2740
2741
2742 class operator_logical_and : public range_operator
2743 {
2744   using range_operator::fold_range;
2745   using range_operator::op1_range;
2746   using range_operator::op2_range;
2747 public:
2748   virtual bool fold_range (irange &r, tree type,
2749                            const irange &lh,
2750                            const irange &rh,
2751                            relation_trio rel = TRIO_VARYING) const;
2752   virtual bool op1_range (irange &r, tree type,
2753                           const irange &lhs,
2754                           const irange &op2,
2755                           relation_trio rel = TRIO_VARYING) const;
2756   virtual bool op2_range (irange &r, tree type,
2757                           const irange &lhs,
2758                           const irange &op1,
2759                           relation_trio rel = TRIO_VARYING) const;
2760 } op_logical_and;
2761
2762
2763 bool
2764 operator_logical_and::fold_range (irange &r, tree type,
2765                                   const irange &lh,
2766                                   const irange &rh,
2767                                   relation_trio) const
2768 {
2769   if (empty_range_varying (r, type, lh, rh))
2770     return true;
2771
2772   // 0 && anything is 0.
2773   if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
2774       || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
2775     r = range_false (type);
2776   else if (lh.contains_p (build_zero_cst (lh.type ()))
2777            || rh.contains_p (build_zero_cst (rh.type ())))
2778     // To reach this point, there must be a logical 1 on each side, and
2779     // the only remaining question is whether there is a zero or not.
2780     r = range_true_and_false (type);
2781   else
2782     r = range_true (type);
2783   return true;
2784 }
2785
2786 bool
2787 operator_logical_and::op1_range (irange &r, tree type,
2788                                  const irange &lhs,
2789                                  const irange &op2 ATTRIBUTE_UNUSED,
2790                                  relation_trio) const
2791 {
2792    switch (get_bool_state (r, lhs, type))
2793      {
2794      case BRS_TRUE:
2795        // A true result means both sides of the AND must be true.
2796        r = range_true (type);
2797        break;
2798      default:
2799        // Any other result means only one side has to be false, the
2800        // other side can be anything.  So we cannot be sure of any
2801        // result here.
2802        r = range_true_and_false (type);
2803        break;
2804      }
2805   return true;
2806 }
2807
2808 bool
2809 operator_logical_and::op2_range (irange &r, tree type,
2810                                  const irange &lhs,
2811                                  const irange &op1,
2812                                  relation_trio) const
2813 {
2814   return operator_logical_and::op1_range (r, type, lhs, op1);
2815 }
2816
2817
2818 class operator_bitwise_and : public range_operator
2819 {
2820   using range_operator::fold_range;
2821   using range_operator::op1_range;
2822   using range_operator::op2_range;
2823 public:
2824   virtual bool fold_range (irange &r, tree type,
2825                            const irange &lh,
2826                            const irange &rh,
2827                            relation_trio rel = TRIO_VARYING) const;
2828   virtual bool op1_range (irange &r, tree type,
2829                           const irange &lhs,
2830                           const irange &op2,
2831                           relation_trio rel = TRIO_VARYING) const;
2832   virtual bool op2_range (irange &r, tree type,
2833                           const irange &lhs,
2834                           const irange &op1,
2835                           relation_trio rel = TRIO_VARYING) const;
2836   virtual void wi_fold (irange &r, tree type,
2837                         const wide_int &lh_lb,
2838                         const wide_int &lh_ub,
2839                         const wide_int &rh_lb,
2840                         const wide_int &rh_ub) const;
2841   virtual relation_kind lhs_op1_relation (const irange &lhs,
2842                                           const irange &op1,
2843                                           const irange &op2,
2844                                           relation_kind) const;
2845 private:
2846   void simple_op1_range_solver (irange &r, tree type,
2847                                 const irange &lhs,
2848                                 const irange &op2) const;
2849 } op_bitwise_and;
2850
2851 bool
2852 operator_bitwise_and::fold_range (irange &r, tree type,
2853                                   const irange &lh,
2854                                   const irange &rh,
2855                                   relation_trio) const
2856 {
2857   if (range_operator::fold_range (r, type, lh, rh))
2858     {
2859       if (!lh.undefined_p () && !rh.undefined_p ())
2860         r.set_nonzero_bits (wi::bit_and (lh.get_nonzero_bits (),
2861                                          rh.get_nonzero_bits ()));
2862       return true;
2863     }
2864   return false;
2865 }
2866
2867
2868 // Optimize BIT_AND_EXPR, BIT_IOR_EXPR and BIT_XOR_EXPR of signed types
2869 // by considering the number of leading redundant sign bit copies.
2870 // clrsb (X op Y) = min (clrsb (X), clrsb (Y)), so for example
2871 // [-1, 0] op [-1, 0] is [-1, 0] (where nonzero_bits doesn't help).
2872 static bool
2873 wi_optimize_signed_bitwise_op (irange &r, tree type,
2874                                const wide_int &lh_lb, const wide_int &lh_ub,
2875                                const wide_int &rh_lb, const wide_int &rh_ub)
2876 {
2877   int lh_clrsb = MIN (wi::clrsb (lh_lb), wi::clrsb (lh_ub));
2878   int rh_clrsb = MIN (wi::clrsb (rh_lb), wi::clrsb (rh_ub));
2879   int new_clrsb = MIN (lh_clrsb, rh_clrsb);
2880   if (new_clrsb == 0)
2881     return false;
2882   int type_prec = TYPE_PRECISION (type);
2883   int rprec = (type_prec - new_clrsb) - 1;
2884   value_range_with_overflow (r, type,
2885                              wi::mask (rprec, true, type_prec),
2886                              wi::mask (rprec, false, type_prec));
2887   return true;
2888 }
2889
2890 // An AND of 8,16, 32 or 64 bits can produce a partial equivalence between
2891 // the LHS and op1.
2892
2893 relation_kind
2894 operator_bitwise_and::lhs_op1_relation (const irange &lhs,
2895                                  const irange &op1,
2896                                  const irange &op2,
2897                                  relation_kind) const
2898 {
2899   if (lhs.undefined_p () || op1.undefined_p () || op2.undefined_p ())
2900     return VREL_VARYING;
2901   if (!op2.singleton_p ())
2902     return VREL_VARYING;
2903   // if val == 0xff or 0xFFFF OR 0Xffffffff OR 0Xffffffffffffffff, return TRUE
2904   int prec1 = TYPE_PRECISION (op1.type ());
2905   int prec2 = TYPE_PRECISION (op2.type ());
2906   int mask_prec = 0;
2907   wide_int mask = op2.lower_bound ();
2908   if (wi::eq_p (mask, wi::mask (8, false, prec2)))
2909     mask_prec = 8;
2910   else if (wi::eq_p (mask, wi::mask (16, false, prec2)))
2911     mask_prec = 16;
2912   else if (wi::eq_p (mask, wi::mask (32, false, prec2)))
2913     mask_prec = 32;
2914   else if (wi::eq_p (mask, wi::mask (64, false, prec2)))
2915     mask_prec = 64;
2916   return bits_to_pe (MIN (prec1, mask_prec));
2917 }
2918
2919 // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
2920 // possible.  Basically, see if we can optimize:
2921 //
2922 //      [LB, UB] op Z
2923 //   into:
2924 //      [LB op Z, UB op Z]
2925 //
2926 // If the optimization was successful, accumulate the range in R and
2927 // return TRUE.
2928
2929 static bool
2930 wi_optimize_and_or (irange &r,
2931                     enum tree_code code,
2932                     tree type,
2933                     const wide_int &lh_lb, const wide_int &lh_ub,
2934                     const wide_int &rh_lb, const wide_int &rh_ub)
2935 {
2936   // Calculate the singleton mask among the ranges, if any.
2937   wide_int lower_bound, upper_bound, mask;
2938   if (wi::eq_p (rh_lb, rh_ub))
2939     {
2940       mask = rh_lb;
2941       lower_bound = lh_lb;
2942       upper_bound = lh_ub;
2943     }
2944   else if (wi::eq_p (lh_lb, lh_ub))
2945     {
2946       mask = lh_lb;
2947       lower_bound = rh_lb;
2948       upper_bound = rh_ub;
2949     }
2950   else
2951     return false;
2952
2953   // If Z is a constant which (for op | its bitwise not) has n
2954   // consecutive least significant bits cleared followed by m 1
2955   // consecutive bits set immediately above it and either
2956   // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
2957   //
2958   // The least significant n bits of all the values in the range are
2959   // cleared or set, the m bits above it are preserved and any bits
2960   // above these are required to be the same for all values in the
2961   // range.
2962   wide_int w = mask;
2963   int m = 0, n = 0;
2964   if (code == BIT_IOR_EXPR)
2965     w = ~w;
2966   if (wi::eq_p (w, 0))
2967     n = w.get_precision ();
2968   else
2969     {
2970       n = wi::ctz (w);
2971       w = ~(w | wi::mask (n, false, w.get_precision ()));
2972       if (wi::eq_p (w, 0))
2973         m = w.get_precision () - n;
2974       else
2975         m = wi::ctz (w) - n;
2976     }
2977   wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
2978   if ((new_mask & lower_bound) != (new_mask & upper_bound))
2979     return false;
2980
2981   wide_int res_lb, res_ub;
2982   if (code == BIT_AND_EXPR)
2983     {
2984       res_lb = wi::bit_and (lower_bound, mask);
2985       res_ub = wi::bit_and (upper_bound, mask);
2986     }
2987   else if (code == BIT_IOR_EXPR)
2988     {
2989       res_lb = wi::bit_or (lower_bound, mask);
2990       res_ub = wi::bit_or (upper_bound, mask);
2991     }
2992   else
2993     gcc_unreachable ();
2994   value_range_with_overflow (r, type, res_lb, res_ub);
2995
2996   // Furthermore, if the mask is non-zero, an IOR cannot contain zero.
2997   if (code == BIT_IOR_EXPR && wi::ne_p (mask, 0))
2998     {
2999       int_range<2> tmp;
3000       tmp.set_nonzero (type);
3001       r.intersect (tmp);
3002     }
3003   return true;
3004 }
3005
3006 // For range [LB, UB] compute two wide_int bit masks.
3007 //
3008 // In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
3009 // for all numbers in the range the bit is 0, otherwise it might be 0
3010 // or 1.
3011 //
3012 // In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
3013 // for all numbers in the range the bit is 1, otherwise it might be 0
3014 // or 1.
3015
3016 void
3017 wi_set_zero_nonzero_bits (tree type,
3018                           const wide_int &lb, const wide_int &ub,
3019                           wide_int &maybe_nonzero,
3020                           wide_int &mustbe_nonzero)
3021 {
3022   signop sign = TYPE_SIGN (type);
3023
3024   if (wi::eq_p (lb, ub))
3025     maybe_nonzero = mustbe_nonzero = lb;
3026   else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
3027     {
3028       wide_int xor_mask = lb ^ ub;
3029       maybe_nonzero = lb | ub;
3030       mustbe_nonzero = lb & ub;
3031       if (xor_mask != 0)
3032         {
3033           wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
3034                                     maybe_nonzero.get_precision ());
3035           maybe_nonzero = maybe_nonzero | mask;
3036           mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
3037         }
3038     }
3039   else
3040     {
3041       maybe_nonzero = wi::minus_one (lb.get_precision ());
3042       mustbe_nonzero = wi::zero (lb.get_precision ());
3043     }
3044 }
3045
3046 void
3047 operator_bitwise_and::wi_fold (irange &r, tree type,
3048                                const wide_int &lh_lb,
3049                                const wide_int &lh_ub,
3050                                const wide_int &rh_lb,
3051                                const wide_int &rh_ub) const
3052 {
3053   if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3054     return;
3055
3056   wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3057   wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3058   wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3059                             maybe_nonzero_lh, mustbe_nonzero_lh);
3060   wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3061                             maybe_nonzero_rh, mustbe_nonzero_rh);
3062
3063   wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
3064   wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
3065   signop sign = TYPE_SIGN (type);
3066   unsigned prec = TYPE_PRECISION (type);
3067   // If both input ranges contain only negative values, we can
3068   // truncate the result range maximum to the minimum of the
3069   // input range maxima.
3070   if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
3071     {
3072       new_ub = wi::min (new_ub, lh_ub, sign);
3073       new_ub = wi::min (new_ub, rh_ub, sign);
3074     }
3075   // If either input range contains only non-negative values
3076   // we can truncate the result range maximum to the respective
3077   // maximum of the input range.
3078   if (wi::ge_p (lh_lb, 0, sign))
3079     new_ub = wi::min (new_ub, lh_ub, sign);
3080   if (wi::ge_p (rh_lb, 0, sign))
3081     new_ub = wi::min (new_ub, rh_ub, sign);
3082   // PR68217: In case of signed & sign-bit-CST should
3083   // result in [-INF, 0] instead of [-INF, INF].
3084   if (wi::gt_p (new_lb, new_ub, sign))
3085     {
3086       wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
3087       if (sign == SIGNED
3088           && ((wi::eq_p (lh_lb, lh_ub)
3089                && !wi::cmps (lh_lb, sign_bit))
3090               || (wi::eq_p (rh_lb, rh_ub)
3091                   && !wi::cmps (rh_lb, sign_bit))))
3092         {
3093           new_lb = wi::min_value (prec, sign);
3094           new_ub = wi::zero (prec);
3095         }
3096     }
3097   // If the limits got swapped around, return varying.
3098   if (wi::gt_p (new_lb, new_ub,sign))
3099     {
3100       if (sign == SIGNED
3101           && wi_optimize_signed_bitwise_op (r, type,
3102                                             lh_lb, lh_ub,
3103                                             rh_lb, rh_ub))
3104         return;
3105       r.set_varying (type);
3106     }
3107   else
3108     value_range_with_overflow (r, type, new_lb, new_ub);
3109 }
3110
3111 static void
3112 set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
3113 {
3114   if (!lhs.contains_p (build_zero_cst (type)))
3115     r = range_nonzero (type);
3116   else
3117     r.set_varying (type);
3118 }
3119
3120 // This was shamelessly stolen from register_edge_assert_for_2 and
3121 // adjusted to work with iranges.
3122
3123 void
3124 operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
3125                                                const irange &lhs,
3126                                                const irange &op2) const
3127 {
3128   if (!op2.singleton_p ())
3129     {
3130       set_nonzero_range_from_mask (r, type, lhs);
3131       return;
3132     }
3133   unsigned int nprec = TYPE_PRECISION (type);
3134   wide_int cst2v = op2.lower_bound ();
3135   bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
3136   wide_int sgnbit;
3137   if (cst2n)
3138     sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
3139   else
3140     sgnbit = wi::zero (nprec);
3141
3142   // Solve [lhs.lower_bound (), +INF] = x & MASK.
3143   //
3144   // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
3145   // maximum unsigned value is ~0.  For signed comparison, if CST2
3146   // doesn't have the most significant bit set, handle it similarly.  If
3147   // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
3148   wide_int valv = lhs.lower_bound ();
3149   wide_int minv = valv & cst2v, maxv;
3150   bool we_know_nothing = false;
3151   if (minv != valv)
3152     {
3153       // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
3154       minv = masked_increment (valv, cst2v, sgnbit, nprec);
3155       if (minv == valv)
3156         {
3157           // If we can't determine anything on this bound, fall
3158           // through and conservatively solve for the other end point.
3159           we_know_nothing = true;
3160         }
3161     }
3162   maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
3163   if (we_know_nothing)
3164     r.set_varying (type);
3165   else
3166     r = int_range<1> (type, minv, maxv);
3167
3168   // Solve [-INF, lhs.upper_bound ()] = x & MASK.
3169   //
3170   // Minimum unsigned value for <= is 0 and maximum unsigned value is
3171   // VAL | ~CST2 if (VAL & CST2) == VAL.  Otherwise, find smallest
3172   // VAL2 where
3173   // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
3174   // as maximum.
3175   // For signed comparison, if CST2 doesn't have most significant bit
3176   // set, handle it similarly.  If CST2 has MSB set, the maximum is
3177   // the same and minimum is INT_MIN.
3178   valv = lhs.upper_bound ();
3179   minv = valv & cst2v;
3180   if (minv == valv)
3181     maxv = valv;
3182   else
3183     {
3184       maxv = masked_increment (valv, cst2v, sgnbit, nprec);
3185       if (maxv == valv)
3186         {
3187           // If we couldn't determine anything on either bound, return
3188           // undefined.
3189           if (we_know_nothing)
3190             r.set_undefined ();
3191           return;
3192         }
3193       maxv -= 1;
3194     }
3195   maxv |= ~cst2v;
3196   minv = sgnbit;
3197   int_range<1> upper_bits (type, minv, maxv);
3198   r.intersect (upper_bits);
3199 }
3200
3201 bool
3202 operator_bitwise_and::op1_range (irange &r, tree type,
3203                                  const irange &lhs,
3204                                  const irange &op2,
3205                                  relation_trio) const
3206 {
3207   if (lhs.undefined_p ())
3208     return false;
3209   if (types_compatible_p (type, boolean_type_node))
3210     return op_logical_and.op1_range (r, type, lhs, op2);
3211
3212   r.set_undefined ();
3213   for (unsigned i = 0; i < lhs.num_pairs (); ++i)
3214     {
3215       int_range_max chunk (lhs.type (),
3216                            lhs.lower_bound (i),
3217                            lhs.upper_bound (i));
3218       int_range_max res;
3219       simple_op1_range_solver (res, type, chunk, op2);
3220       r.union_ (res);
3221     }
3222   if (r.undefined_p ())
3223     set_nonzero_range_from_mask (r, type, lhs);
3224
3225   // For 0 = op1 & MASK, op1 is ~MASK.
3226   if (lhs.zero_p () && op2.singleton_p ())
3227     {
3228       wide_int nz = wi::bit_not (op2.get_nonzero_bits ());
3229       int_range<2> tmp (type);
3230       tmp.set_nonzero_bits (nz);
3231       r.intersect (tmp);
3232     }
3233   return true;
3234 }
3235
3236 bool
3237 operator_bitwise_and::op2_range (irange &r, tree type,
3238                                  const irange &lhs,
3239                                  const irange &op1,
3240                                  relation_trio) const
3241 {
3242   return operator_bitwise_and::op1_range (r, type, lhs, op1);
3243 }
3244
3245
3246 class operator_logical_or : public range_operator
3247 {
3248   using range_operator::fold_range;
3249   using range_operator::op1_range;
3250   using range_operator::op2_range;
3251 public:
3252   virtual bool fold_range (irange &r, tree type,
3253                            const irange &lh,
3254                            const irange &rh,
3255                            relation_trio rel = TRIO_VARYING) const;
3256   virtual bool op1_range (irange &r, tree type,
3257                           const irange &lhs,
3258                           const irange &op2,
3259                           relation_trio rel = TRIO_VARYING) const;
3260   virtual bool op2_range (irange &r, tree type,
3261                           const irange &lhs,
3262                           const irange &op1,
3263                           relation_trio rel = TRIO_VARYING) const;
3264 } op_logical_or;
3265
3266 bool
3267 operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3268                                  const irange &lh,
3269                                  const irange &rh,
3270                                  relation_trio) const
3271 {
3272   if (empty_range_varying (r, type, lh, rh))
3273     return true;
3274
3275   r = lh;
3276   r.union_ (rh);
3277   return true;
3278 }
3279
3280 bool
3281 operator_logical_or::op1_range (irange &r, tree type,
3282                                 const irange &lhs,
3283                                 const irange &op2 ATTRIBUTE_UNUSED,
3284                                 relation_trio) const
3285 {
3286    switch (get_bool_state (r, lhs, type))
3287      {
3288      case BRS_FALSE:
3289        // A false result means both sides of the OR must be false.
3290        r = range_false (type);
3291        break;
3292      default:
3293        // Any other result means only one side has to be true, the
3294        // other side can be anything. so we can't be sure of any result
3295        // here.
3296        r = range_true_and_false (type);
3297        break;
3298     }
3299   return true;
3300 }
3301
3302 bool
3303 operator_logical_or::op2_range (irange &r, tree type,
3304                                 const irange &lhs,
3305                                 const irange &op1,
3306                                 relation_trio) const
3307 {
3308   return operator_logical_or::op1_range (r, type, lhs, op1);
3309 }
3310
3311
3312 class operator_bitwise_or : public range_operator
3313 {
3314   using range_operator::op1_range;
3315   using range_operator::op2_range;
3316 public:
3317   virtual bool op1_range (irange &r, tree type,
3318                           const irange &lhs,
3319                           const irange &op2,
3320                           relation_trio rel = TRIO_VARYING) const;
3321   virtual bool op2_range (irange &r, tree type,
3322                           const irange &lhs,
3323                           const irange &op1,
3324                           relation_trio rel = TRIO_VARYING) const;
3325   virtual void wi_fold (irange &r, tree type,
3326                         const wide_int &lh_lb,
3327                         const wide_int &lh_ub,
3328                         const wide_int &rh_lb,
3329                         const wide_int &rh_ub) const;
3330 } op_bitwise_or;
3331
3332 void
3333 operator_bitwise_or::wi_fold (irange &r, tree type,
3334                               const wide_int &lh_lb,
3335                               const wide_int &lh_ub,
3336                               const wide_int &rh_lb,
3337                               const wide_int &rh_ub) const
3338 {
3339   if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
3340     return;
3341
3342   wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3343   wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3344   wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3345                             maybe_nonzero_lh, mustbe_nonzero_lh);
3346   wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3347                             maybe_nonzero_rh, mustbe_nonzero_rh);
3348   wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
3349   wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
3350   signop sign = TYPE_SIGN (type);
3351   // If the input ranges contain only positive values we can
3352   // truncate the minimum of the result range to the maximum
3353   // of the input range minima.
3354   if (wi::ge_p (lh_lb, 0, sign)
3355       && wi::ge_p (rh_lb, 0, sign))
3356     {
3357       new_lb = wi::max (new_lb, lh_lb, sign);
3358       new_lb = wi::max (new_lb, rh_lb, sign);
3359     }
3360   // If either input range contains only negative values
3361   // we can truncate the minimum of the result range to the
3362   // respective minimum range.
3363   if (wi::lt_p (lh_ub, 0, sign))
3364     new_lb = wi::max (new_lb, lh_lb, sign);
3365   if (wi::lt_p (rh_ub, 0, sign))
3366     new_lb = wi::max (new_lb, rh_lb, sign);
3367   // If the limits got swapped around, return a conservative range.
3368   if (wi::gt_p (new_lb, new_ub, sign))
3369     {
3370       // Make sure that nonzero|X is nonzero.
3371       if (wi::gt_p (lh_lb, 0, sign)
3372           || wi::gt_p (rh_lb, 0, sign)
3373           || wi::lt_p (lh_ub, 0, sign)
3374           || wi::lt_p (rh_ub, 0, sign))
3375         r.set_nonzero (type);
3376       else if (sign == SIGNED
3377                && wi_optimize_signed_bitwise_op (r, type,
3378                                                  lh_lb, lh_ub,
3379                                                  rh_lb, rh_ub))
3380         return;
3381       else
3382         r.set_varying (type);
3383       return;
3384     }
3385   value_range_with_overflow (r, type, new_lb, new_ub);
3386 }
3387
3388 bool
3389 operator_bitwise_or::op1_range (irange &r, tree type,
3390                                 const irange &lhs,
3391                                 const irange &op2,
3392                                 relation_trio) const
3393 {
3394   if (lhs.undefined_p ())
3395     return false;
3396   // If this is really a logical wi_fold, call that.
3397   if (types_compatible_p (type, boolean_type_node))
3398     return op_logical_or.op1_range (r, type, lhs, op2);
3399
3400   if (lhs.zero_p ())
3401     {
3402       tree zero = build_zero_cst (type);
3403       r = int_range<1> (zero, zero);
3404       return true;
3405     }
3406   r.set_varying (type);
3407   return true;
3408 }
3409
3410 bool
3411 operator_bitwise_or::op2_range (irange &r, tree type,
3412                                 const irange &lhs,
3413                                 const irange &op1,
3414                                 relation_trio) const
3415 {
3416   return operator_bitwise_or::op1_range (r, type, lhs, op1);
3417 }
3418
3419
3420 class operator_bitwise_xor : public range_operator
3421 {
3422   using range_operator::op1_range;
3423   using range_operator::op2_range;
3424 public:
3425   virtual void wi_fold (irange &r, tree type,
3426                         const wide_int &lh_lb,
3427                         const wide_int &lh_ub,
3428                         const wide_int &rh_lb,
3429                         const wide_int &rh_ub) const;
3430   virtual bool op1_range (irange &r, tree type,
3431                           const irange &lhs,
3432                           const irange &op2,
3433                           relation_trio rel = TRIO_VARYING) const;
3434   virtual bool op2_range (irange &r, tree type,
3435                           const irange &lhs,
3436                           const irange &op1,
3437                           relation_trio rel = TRIO_VARYING) const;
3438   virtual bool op1_op2_relation_effect (irange &lhs_range,
3439                                         tree type,
3440                                         const irange &op1_range,
3441                                         const irange &op2_range,
3442                                         relation_kind rel) const;
3443 } op_bitwise_xor;
3444
3445 void
3446 operator_bitwise_xor::wi_fold (irange &r, tree type,
3447                                const wide_int &lh_lb,
3448                                const wide_int &lh_ub,
3449                                const wide_int &rh_lb,
3450                                const wide_int &rh_ub) const
3451 {
3452   signop sign = TYPE_SIGN (type);
3453   wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
3454   wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
3455   wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
3456                             maybe_nonzero_lh, mustbe_nonzero_lh);
3457   wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
3458                             maybe_nonzero_rh, mustbe_nonzero_rh);
3459
3460   wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
3461                                | ~(maybe_nonzero_lh | maybe_nonzero_rh));
3462   wide_int result_one_bits
3463     = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
3464        | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
3465   wide_int new_ub = ~result_zero_bits;
3466   wide_int new_lb = result_one_bits;
3467
3468   // If the range has all positive or all negative values, the result
3469   // is better than VARYING.
3470   if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
3471     value_range_with_overflow (r, type, new_lb, new_ub);
3472   else if (sign == SIGNED
3473            && wi_optimize_signed_bitwise_op (r, type,
3474                                              lh_lb, lh_ub,
3475                                              rh_lb, rh_ub))
3476     ;  /* Do nothing.  */
3477   else
3478     r.set_varying (type);
3479
3480   /* Furthermore, XOR is non-zero if its arguments can't be equal.  */
3481   if (wi::lt_p (lh_ub, rh_lb, sign)
3482       || wi::lt_p (rh_ub, lh_lb, sign)
3483       || wi::ne_p (result_one_bits, 0))
3484     {
3485       int_range<2> tmp;
3486       tmp.set_nonzero (type);
3487       r.intersect (tmp);
3488     }
3489 }
3490
3491 bool
3492 operator_bitwise_xor::op1_op2_relation_effect (irange &lhs_range,
3493                                                tree type,
3494                                                const irange &,
3495                                                const irange &,
3496                                                relation_kind rel) const
3497 {
3498   if (rel == VREL_VARYING)
3499     return false;
3500
3501   int_range<2> rel_range;
3502
3503   switch (rel)
3504     {
3505     case VREL_EQ:
3506       rel_range.set_zero (type);
3507       break;
3508     case VREL_NE:
3509       rel_range.set_nonzero (type);
3510       break;
3511     default:
3512       return false;
3513     }
3514
3515   lhs_range.intersect (rel_range);
3516   return true;
3517 }
3518
3519 bool
3520 operator_bitwise_xor::op1_range (irange &r, tree type,
3521                                  const irange &lhs,
3522                                  const irange &op2,
3523                                  relation_trio) const
3524 {
3525   if (lhs.undefined_p () || lhs.varying_p ())
3526     {
3527       r = lhs;
3528       return true;
3529     }
3530   if (types_compatible_p (type, boolean_type_node))
3531     {
3532       switch (get_bool_state (r, lhs, type))
3533         {
3534         case BRS_TRUE:
3535           if (op2.varying_p ())
3536             r.set_varying (type);
3537           else if (op2.zero_p ())
3538             r = range_true (type);
3539           else
3540             r = range_false (type);
3541           break;
3542         case BRS_FALSE:
3543           r = op2;
3544           break;
3545         default:
3546           break;
3547         }
3548       return true;
3549     }
3550   r.set_varying (type);
3551   return true;
3552 }
3553
3554 bool
3555 operator_bitwise_xor::op2_range (irange &r, tree type,
3556                                  const irange &lhs,
3557                                  const irange &op1,
3558                                  relation_trio) const
3559 {
3560   return operator_bitwise_xor::op1_range (r, type, lhs, op1);
3561 }
3562
3563 class operator_trunc_mod : public range_operator
3564 {
3565   using range_operator::op1_range;
3566   using range_operator::op2_range;
3567 public:
3568   virtual void wi_fold (irange &r, tree type,
3569                         const wide_int &lh_lb,
3570                         const wide_int &lh_ub,
3571                         const wide_int &rh_lb,
3572                         const wide_int &rh_ub) const;
3573   virtual bool op1_range (irange &r, tree type,
3574                           const irange &lhs,
3575                           const irange &op2,
3576                           relation_trio) const;
3577   virtual bool op2_range (irange &r, tree type,
3578                           const irange &lhs,
3579                           const irange &op1,
3580                           relation_trio) const;
3581 } op_trunc_mod;
3582
3583 void
3584 operator_trunc_mod::wi_fold (irange &r, tree type,
3585                              const wide_int &lh_lb,
3586                              const wide_int &lh_ub,
3587                              const wide_int &rh_lb,
3588                              const wide_int &rh_ub) const
3589 {
3590   wide_int new_lb, new_ub, tmp;
3591   signop sign = TYPE_SIGN (type);
3592   unsigned prec = TYPE_PRECISION (type);
3593
3594   // Mod 0 is undefined.
3595   if (wi_zero_p (type, rh_lb, rh_ub))
3596     {
3597       r.set_undefined ();
3598       return;
3599     }
3600
3601   // Check for constant and try to fold.
3602   if (lh_lb == lh_ub && rh_lb == rh_ub)
3603     {
3604       wi::overflow_type ov = wi::OVF_NONE;
3605       tmp = wi::mod_trunc (lh_lb, rh_lb, sign, &ov);
3606       if (ov == wi::OVF_NONE)
3607         {
3608           r = int_range<2> (type, tmp, tmp);
3609           return;
3610         }
3611     }
3612
3613   // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
3614   new_ub = rh_ub - 1;
3615   if (sign == SIGNED)
3616     {
3617       tmp = -1 - rh_lb;
3618       new_ub = wi::smax (new_ub, tmp);
3619     }
3620
3621   if (sign == UNSIGNED)
3622     new_lb = wi::zero (prec);
3623   else
3624     {
3625       new_lb = -new_ub;
3626       tmp = lh_lb;
3627       if (wi::gts_p (tmp, 0))
3628         tmp = wi::zero (prec);
3629       new_lb = wi::smax (new_lb, tmp);
3630     }
3631   tmp = lh_ub;
3632   if (sign == SIGNED && wi::neg_p (tmp))
3633     tmp = wi::zero (prec);
3634   new_ub = wi::min (new_ub, tmp, sign);
3635
3636   value_range_with_overflow (r, type, new_lb, new_ub);
3637 }
3638
3639 bool
3640 operator_trunc_mod::op1_range (irange &r, tree type,
3641                                const irange &lhs,
3642                                const irange &,
3643                                relation_trio) const
3644 {
3645   if (lhs.undefined_p ())
3646     return false;
3647   // PR 91029.
3648   signop sign = TYPE_SIGN (type);
3649   unsigned prec = TYPE_PRECISION (type);
3650   // (a % b) >= x && x > 0 , then a >= x.
3651   if (wi::gt_p (lhs.lower_bound (), 0, sign))
3652     {
3653       r = value_range (type, lhs.lower_bound (), wi::max_value (prec, sign));
3654       return true;
3655     }
3656   // (a % b) <= x && x < 0 , then a <= x.
3657   if (wi::lt_p (lhs.upper_bound (), 0, sign))
3658     {
3659       r = value_range (type, wi::min_value (prec, sign), lhs.upper_bound ());
3660       return true;
3661     }
3662   return false;
3663 }
3664
3665 bool
3666 operator_trunc_mod::op2_range (irange &r, tree type,
3667                                const irange &lhs,
3668                                const irange &,
3669                                relation_trio) const
3670 {
3671   if (lhs.undefined_p ())
3672     return false;
3673   // PR 91029.
3674   signop sign = TYPE_SIGN (type);
3675   unsigned prec = TYPE_PRECISION (type);
3676   // (a % b) >= x && x > 0 , then b is in ~[-x, x] for signed
3677   //                           or b > x for unsigned.
3678   if (wi::gt_p (lhs.lower_bound (), 0, sign))
3679     {
3680       if (sign == SIGNED)
3681         r = value_range (type, wi::neg (lhs.lower_bound ()),
3682                          lhs.lower_bound (), VR_ANTI_RANGE);
3683       else if (wi::lt_p (lhs.lower_bound (), wi::max_value (prec, sign),
3684                          sign))
3685         r = value_range (type, lhs.lower_bound () + 1,
3686                          wi::max_value (prec, sign));
3687       else
3688         return false;
3689       return true;
3690     }
3691   // (a % b) <= x && x < 0 , then b is in ~[x, -x].
3692   if (wi::lt_p (lhs.upper_bound (), 0, sign))
3693     {
3694       if (wi::gt_p (lhs.upper_bound (), wi::min_value (prec, sign), sign))
3695         r = value_range (type, lhs.upper_bound (),
3696                          wi::neg (lhs.upper_bound ()), VR_ANTI_RANGE);
3697       else
3698         return false;
3699       return true;
3700     }
3701   return false;
3702 }
3703
3704
3705 class operator_logical_not : public range_operator
3706 {
3707   using range_operator::fold_range;
3708   using range_operator::op1_range;
3709 public:
3710   virtual bool fold_range (irange &r, tree type,
3711                            const irange &lh,
3712                            const irange &rh,
3713                            relation_trio rel = TRIO_VARYING) const;
3714   virtual bool op1_range (irange &r, tree type,
3715                           const irange &lhs,
3716                           const irange &op2,
3717                           relation_trio rel = TRIO_VARYING) const;
3718 } op_logical_not;
3719
3720 // Folding a logical NOT, oddly enough, involves doing nothing on the
3721 // forward pass through.  During the initial walk backwards, the
3722 // logical NOT reversed the desired outcome on the way back, so on the
3723 // way forward all we do is pass the range forward.
3724 //
3725 //      b_2 = x_1 < 20
3726 //      b_3 = !b_2
3727 //      if (b_3)
3728 //  to determine the TRUE branch, walking  backward
3729 //       if (b_3)               if ([1,1])
3730 //       b_3 = !b_2             [1,1] = ![0,0]
3731 //       b_2 = x_1 < 20         [0,0] = x_1 < 20,   false, so x_1 == [20, 255]
3732 //   which is the result we are looking for.. so.. pass it through.
3733
3734 bool
3735 operator_logical_not::fold_range (irange &r, tree type,
3736                                   const irange &lh,
3737                                   const irange &rh ATTRIBUTE_UNUSED,
3738                                   relation_trio) const
3739 {
3740   if (empty_range_varying (r, type, lh, rh))
3741     return true;
3742
3743   r = lh;
3744   if (!lh.varying_p () && !lh.undefined_p ())
3745     r.invert ();
3746
3747   return true;
3748 }
3749
3750 bool
3751 operator_logical_not::op1_range (irange &r,
3752                                  tree type,
3753                                  const irange &lhs,
3754                                  const irange &op2,
3755                                  relation_trio) const
3756 {
3757   // Logical NOT is involutary...do it again.
3758   return fold_range (r, type, lhs, op2);
3759 }
3760
3761
3762 class operator_bitwise_not : public range_operator
3763 {
3764   using range_operator::fold_range;
3765   using range_operator::op1_range;
3766 public:
3767   virtual bool fold_range (irange &r, tree type,
3768                            const irange &lh,
3769                            const irange &rh,
3770                            relation_trio rel = TRIO_VARYING) const;
3771   virtual bool op1_range (irange &r, tree type,
3772                           const irange &lhs,
3773                           const irange &op2,
3774                           relation_trio rel = TRIO_VARYING) const;
3775 } op_bitwise_not;
3776
3777 bool
3778 operator_bitwise_not::fold_range (irange &r, tree type,
3779                                   const irange &lh,
3780                                   const irange &rh,
3781                                   relation_trio) const
3782 {
3783   if (empty_range_varying (r, type, lh, rh))
3784     return true;
3785
3786   if (types_compatible_p (type, boolean_type_node))
3787     return op_logical_not.fold_range (r, type, lh, rh);
3788
3789   // ~X is simply -1 - X.
3790   int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
3791                          wi::minus_one (TYPE_PRECISION (type)));
3792   return range_op_handler (MINUS_EXPR, type).fold_range (r, type, minusone, lh);
3793 }
3794
3795 bool
3796 operator_bitwise_not::op1_range (irange &r, tree type,
3797                                  const irange &lhs,
3798                                  const irange &op2,
3799                                  relation_trio) const
3800 {
3801   if (lhs.undefined_p ())
3802     return false;
3803   if (types_compatible_p (type, boolean_type_node))
3804     return op_logical_not.op1_range (r, type, lhs, op2);
3805
3806   // ~X is -1 - X and since bitwise NOT is involutary...do it again.
3807   return fold_range (r, type, lhs, op2);
3808 }
3809
3810
3811 class operator_cst : public range_operator
3812 {
3813   using range_operator::fold_range;
3814 public:
3815   virtual bool fold_range (irange &r, tree type,
3816                            const irange &op1,
3817                            const irange &op2,
3818                            relation_trio rel = TRIO_VARYING) const;
3819 } op_integer_cst;
3820
3821 bool
3822 operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3823                           const irange &lh,
3824                           const irange &rh ATTRIBUTE_UNUSED,
3825                           relation_trio) const
3826 {
3827   r = lh;
3828   return true;
3829 }
3830
3831
3832 class operator_identity : public range_operator
3833 {
3834   using range_operator::fold_range;
3835   using range_operator::op1_range;
3836   using range_operator::lhs_op1_relation;
3837 public:
3838   virtual bool fold_range (irange &r, tree type,
3839                            const irange &op1,
3840                            const irange &op2,
3841                            relation_trio rel = TRIO_VARYING) const;
3842   virtual bool op1_range (irange &r, tree type,
3843                           const irange &lhs,
3844                           const irange &op2,
3845                           relation_trio rel = TRIO_VARYING) const;
3846   virtual relation_kind lhs_op1_relation (const irange &lhs,
3847                                            const irange &op1,
3848                                            const irange &op2,
3849                                            relation_kind rel) const;
3850 } op_identity;
3851
3852 // Determine if there is a relationship between LHS and OP1.
3853
3854 relation_kind
3855 operator_identity::lhs_op1_relation (const irange &lhs,
3856                                      const irange &op1 ATTRIBUTE_UNUSED,
3857                                      const irange &op2 ATTRIBUTE_UNUSED,
3858                                      relation_kind) const
3859 {
3860   if (lhs.undefined_p ())
3861     return VREL_VARYING;
3862   // Simply a copy, so they are equivalent.
3863   return VREL_EQ;
3864 }
3865
3866 bool
3867 operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
3868                                const irange &lh,
3869                                const irange &rh ATTRIBUTE_UNUSED,
3870                                relation_trio) const
3871 {
3872   r = lh;
3873   return true;
3874 }
3875
3876 bool
3877 operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
3878                               const irange &lhs,
3879                               const irange &op2 ATTRIBUTE_UNUSED,
3880                               relation_trio) const
3881 {
3882   r = lhs;
3883   return true;
3884 }
3885
3886
3887 class operator_unknown : public range_operator
3888 {
3889   using range_operator::fold_range;
3890 public:
3891   virtual bool fold_range (irange &r, tree type,
3892                            const irange &op1,
3893                            const irange &op2,
3894                            relation_trio rel = TRIO_VARYING) const;
3895 } op_unknown;
3896
3897 bool
3898 operator_unknown::fold_range (irange &r, tree type,
3899                               const irange &lh ATTRIBUTE_UNUSED,
3900                               const irange &rh ATTRIBUTE_UNUSED,
3901                               relation_trio) const
3902 {
3903   r.set_varying (type);
3904   return true;
3905 }
3906
3907
3908 class operator_abs : public range_operator
3909 {
3910   using range_operator::op1_range;
3911  public:
3912   virtual void wi_fold (irange &r, tree type,
3913                         const wide_int &lh_lb,
3914                         const wide_int &lh_ub,
3915                         const wide_int &rh_lb,
3916                         const wide_int &rh_ub) const;
3917   virtual bool op1_range (irange &r, tree type,
3918                           const irange &lhs,
3919                           const irange &op2,
3920                           relation_trio) const;
3921 } op_abs;
3922
3923 void
3924 operator_abs::wi_fold (irange &r, tree type,
3925                        const wide_int &lh_lb, const wide_int &lh_ub,
3926                        const wide_int &rh_lb ATTRIBUTE_UNUSED,
3927                        const wide_int &rh_ub ATTRIBUTE_UNUSED) const
3928 {
3929   wide_int min, max;
3930   signop sign = TYPE_SIGN (type);
3931   unsigned prec = TYPE_PRECISION (type);
3932
3933   // Pass through LH for the easy cases.
3934   if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
3935     {
3936       r = int_range<1> (type, lh_lb, lh_ub);
3937       return;
3938     }
3939
3940   // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
3941   // a useful range.
3942   wide_int min_value = wi::min_value (prec, sign);
3943   wide_int max_value = wi::max_value (prec, sign);
3944   if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
3945     {
3946       r.set_varying (type);
3947       return;
3948     }
3949
3950   // ABS_EXPR may flip the range around, if the original range
3951   // included negative values.
3952   if (wi::eq_p (lh_lb, min_value))
3953     {
3954       // ABS ([-MIN, -MIN]) isn't representable, but we have traditionally
3955       // returned [-MIN,-MIN] so this preserves that behaviour.  PR37078
3956       if (wi::eq_p (lh_ub, min_value))
3957         {
3958           r = int_range<1> (type, min_value, min_value);
3959           return;
3960         }
3961       min = max_value;
3962     }
3963   else
3964     min = wi::abs (lh_lb);
3965
3966   if (wi::eq_p (lh_ub, min_value))
3967     max = max_value;
3968   else
3969     max = wi::abs (lh_ub);
3970
3971   // If the range contains zero then we know that the minimum value in the
3972   // range will be zero.
3973   if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
3974     {
3975       if (wi::gt_p (min, max, sign))
3976         max = min;
3977       min = wi::zero (prec);
3978     }
3979   else
3980     {
3981       // If the range was reversed, swap MIN and MAX.
3982       if (wi::gt_p (min, max, sign))
3983         std::swap (min, max);
3984     }
3985
3986   // If the new range has its limits swapped around (MIN > MAX), then
3987   // the operation caused one of them to wrap around.  The only thing
3988   // we know is that the result is positive.
3989   if (wi::gt_p (min, max, sign))
3990     {
3991       min = wi::zero (prec);
3992       max = max_value;
3993     }
3994   r = int_range<1> (type, min, max);
3995 }
3996
3997 bool
3998 operator_abs::op1_range (irange &r, tree type,
3999                          const irange &lhs,
4000                          const irange &op2,
4001                          relation_trio) const
4002 {
4003   if (empty_range_varying (r, type, lhs, op2))
4004     return true;
4005   if (TYPE_UNSIGNED (type))
4006     {
4007       r = lhs;
4008       return true;
4009     }
4010   // Start with the positives because negatives are an impossible result.
4011   int_range_max positives = range_positives (type);
4012   positives.intersect (lhs);
4013   r = positives;
4014   // Then add the negative of each pair:
4015   // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
4016   for (unsigned i = 0; i < positives.num_pairs (); ++i)
4017     r.union_ (int_range<1> (type,
4018                             -positives.upper_bound (i),
4019                             -positives.lower_bound (i)));
4020   // With flag_wrapv, -TYPE_MIN_VALUE = TYPE_MIN_VALUE which is
4021   // unrepresentable.  Add -TYPE_MIN_VALUE in this case.
4022   wide_int min_value = wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type));
4023   wide_int lb = lhs.lower_bound ();
4024   if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lb, min_value))
4025     r.union_ (int_range<2> (type, lb, lb));
4026   return true;
4027 }
4028
4029
4030 class operator_absu : public range_operator
4031 {
4032  public:
4033   virtual void wi_fold (irange &r, tree type,
4034                         const wide_int &lh_lb, const wide_int &lh_ub,
4035                         const wide_int &rh_lb, const wide_int &rh_ub) const;
4036 } op_absu;
4037
4038 void
4039 operator_absu::wi_fold (irange &r, tree type,
4040                         const wide_int &lh_lb, const wide_int &lh_ub,
4041                         const wide_int &rh_lb ATTRIBUTE_UNUSED,
4042                         const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4043 {
4044   wide_int new_lb, new_ub;
4045
4046   // Pass through VR0 the easy cases.
4047   if (wi::ges_p (lh_lb, 0))
4048     {
4049       new_lb = lh_lb;
4050       new_ub = lh_ub;
4051     }
4052   else
4053     {
4054       new_lb = wi::abs (lh_lb);
4055       new_ub = wi::abs (lh_ub);
4056
4057       // If the range contains zero then we know that the minimum
4058       // value in the range will be zero.
4059       if (wi::ges_p (lh_ub, 0))
4060         {
4061           if (wi::gtu_p (new_lb, new_ub))
4062             new_ub = new_lb;
4063           new_lb = wi::zero (TYPE_PRECISION (type));
4064         }
4065       else
4066         std::swap (new_lb, new_ub);
4067     }
4068
4069   gcc_checking_assert (TYPE_UNSIGNED (type));
4070   r = int_range<1> (type, new_lb, new_ub);
4071 }
4072
4073
4074 class operator_negate : public range_operator
4075 {
4076   using range_operator::fold_range;
4077   using range_operator::op1_range;
4078  public:
4079   virtual bool fold_range (irange &r, tree type,
4080                            const irange &op1,
4081                            const irange &op2,
4082                            relation_trio rel = TRIO_VARYING) const;
4083   virtual bool op1_range (irange &r, tree type,
4084                           const irange &lhs,
4085                           const irange &op2,
4086                           relation_trio rel = TRIO_VARYING) const;
4087 } op_negate;
4088
4089 bool
4090 operator_negate::fold_range (irange &r, tree type,
4091                              const irange &lh,
4092                              const irange &rh,
4093                              relation_trio) const
4094 {
4095   if (empty_range_varying (r, type, lh, rh))
4096     return true;
4097   // -X is simply 0 - X.
4098   return range_op_handler (MINUS_EXPR, type).fold_range (r, type,
4099                                                          range_zero (type), lh);
4100 }
4101
4102 bool
4103 operator_negate::op1_range (irange &r, tree type,
4104                             const irange &lhs,
4105                             const irange &op2,
4106                             relation_trio) const
4107 {
4108   // NEGATE is involutory.
4109   return fold_range (r, type, lhs, op2);
4110 }
4111
4112
4113 class operator_addr_expr : public range_operator
4114 {
4115   using range_operator::fold_range;
4116   using range_operator::op1_range;
4117 public:
4118   virtual bool fold_range (irange &r, tree type,
4119                            const irange &op1,
4120                            const irange &op2,
4121                            relation_trio rel = TRIO_VARYING) const;
4122   virtual bool op1_range (irange &r, tree type,
4123                           const irange &lhs,
4124                           const irange &op2,
4125                           relation_trio rel = TRIO_VARYING) const;
4126 } op_addr;
4127
4128 bool
4129 operator_addr_expr::fold_range (irange &r, tree type,
4130                                 const irange &lh,
4131                                 const irange &rh,
4132                                 relation_trio) const
4133 {
4134   if (empty_range_varying (r, type, lh, rh))
4135     return true;
4136
4137   // Return a non-null pointer of the LHS type (passed in op2).
4138   if (lh.zero_p ())
4139     r = range_zero (type);
4140   else if (!lh.contains_p (build_zero_cst (lh.type ())))
4141     r = range_nonzero (type);
4142   else
4143     r.set_varying (type);
4144   return true;
4145 }
4146
4147 bool
4148 operator_addr_expr::op1_range (irange &r, tree type,
4149                                const irange &lhs,
4150                                const irange &op2,
4151                                relation_trio) const
4152 {
4153   return operator_addr_expr::fold_range (r, type, lhs, op2);
4154 }
4155
4156
4157 class pointer_plus_operator : public range_operator
4158 {
4159 public:
4160   virtual void wi_fold (irange &r, tree type,
4161                         const wide_int &lh_lb,
4162                         const wide_int &lh_ub,
4163                         const wide_int &rh_lb,
4164                         const wide_int &rh_ub) const;
4165 } op_pointer_plus;
4166
4167 void
4168 pointer_plus_operator::wi_fold (irange &r, tree type,
4169                                 const wide_int &lh_lb,
4170                                 const wide_int &lh_ub,
4171                                 const wide_int &rh_lb,
4172                                 const wide_int &rh_ub) const
4173 {
4174   // Check for [0,0] + const, and simply return the const.
4175   if (lh_lb == 0 && lh_ub == 0 && rh_lb == rh_ub)
4176     {
4177       tree val = wide_int_to_tree (type, rh_lb);
4178       r.set (val, val);
4179       return;
4180     }
4181
4182   // For pointer types, we are really only interested in asserting
4183   // whether the expression evaluates to non-NULL.
4184   //
4185   // With -fno-delete-null-pointer-checks we need to be more
4186   // conservative.  As some object might reside at address 0,
4187   // then some offset could be added to it and the same offset
4188   // subtracted again and the result would be NULL.
4189   // E.g.
4190   // static int a[12]; where &a[0] is NULL and
4191   // ptr = &a[6];
4192   // ptr -= 6;
4193   // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
4194   // where the first range doesn't include zero and the second one
4195   // doesn't either.  As the second operand is sizetype (unsigned),
4196   // consider all ranges where the MSB could be set as possible
4197   // subtractions where the result might be NULL.
4198   if ((!wi_includes_zero_p (type, lh_lb, lh_ub)
4199        || !wi_includes_zero_p (type, rh_lb, rh_ub))
4200       && !TYPE_OVERFLOW_WRAPS (type)
4201       && (flag_delete_null_pointer_checks
4202           || !wi::sign_mask (rh_ub)))
4203     r = range_nonzero (type);
4204   else if (lh_lb == lh_ub && lh_lb == 0
4205            && rh_lb == rh_ub && rh_lb == 0)
4206     r = range_zero (type);
4207   else
4208    r.set_varying (type);
4209 }
4210
4211
4212 class pointer_min_max_operator : public range_operator
4213 {
4214 public:
4215   virtual void wi_fold (irange & r, tree type,
4216                         const wide_int &lh_lb, const wide_int &lh_ub,
4217                         const wide_int &rh_lb, const wide_int &rh_ub) const;
4218 } op_ptr_min_max;
4219
4220 void
4221 pointer_min_max_operator::wi_fold (irange &r, tree type,
4222                                    const wide_int &lh_lb,
4223                                    const wide_int &lh_ub,
4224                                    const wide_int &rh_lb,
4225                                    const wide_int &rh_ub) const
4226 {
4227   // For MIN/MAX expressions with pointers, we only care about
4228   // nullness.  If both are non null, then the result is nonnull.
4229   // If both are null, then the result is null.  Otherwise they
4230   // are varying.
4231   if (!wi_includes_zero_p (type, lh_lb, lh_ub)
4232       && !wi_includes_zero_p (type, rh_lb, rh_ub))
4233     r = range_nonzero (type);
4234   else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
4235     r = range_zero (type);
4236   else
4237     r.set_varying (type);
4238 }
4239
4240
4241 class pointer_and_operator : public range_operator
4242 {
4243 public:
4244   virtual void wi_fold (irange &r, tree type,
4245                         const wide_int &lh_lb, const wide_int &lh_ub,
4246                         const wide_int &rh_lb, const wide_int &rh_ub) const;
4247 } op_pointer_and;
4248
4249 void
4250 pointer_and_operator::wi_fold (irange &r, tree type,
4251                                const wide_int &lh_lb,
4252                                const wide_int &lh_ub,
4253                                const wide_int &rh_lb ATTRIBUTE_UNUSED,
4254                                const wide_int &rh_ub ATTRIBUTE_UNUSED) const
4255 {
4256   // For pointer types, we are really only interested in asserting
4257   // whether the expression evaluates to non-NULL.
4258   if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub))
4259     r = range_zero (type);
4260   else
4261     r.set_varying (type);
4262 }
4263
4264
4265 class pointer_or_operator : public range_operator
4266 {
4267   using range_operator::op1_range;
4268   using range_operator::op2_range;
4269 public:
4270   virtual bool op1_range (irange &r, tree type,
4271                           const irange &lhs,
4272                           const irange &op2,
4273                           relation_trio rel = TRIO_VARYING) const;
4274   virtual bool op2_range (irange &r, tree type,
4275                           const irange &lhs,
4276                           const irange &op1,
4277                           relation_trio rel = TRIO_VARYING) const;
4278   virtual void wi_fold (irange &r, tree type,
4279                         const wide_int &lh_lb, const wide_int &lh_ub,
4280                         const wide_int &rh_lb, const wide_int &rh_ub) const;
4281 } op_pointer_or;
4282
4283 bool
4284 pointer_or_operator::op1_range (irange &r, tree type,
4285                                 const irange &lhs,
4286                                 const irange &op2 ATTRIBUTE_UNUSED,
4287                                 relation_trio) const
4288 {
4289   if (lhs.undefined_p ())
4290     return false;
4291   if (lhs.zero_p ())
4292     {
4293       tree zero = build_zero_cst (type);
4294       r = int_range<1> (zero, zero);
4295       return true;
4296     }
4297   r.set_varying (type);
4298   return true;
4299 }
4300
4301 bool
4302 pointer_or_operator::op2_range (irange &r, tree type,
4303                                 const irange &lhs,
4304                                 const irange &op1,
4305                                 relation_trio) const
4306 {
4307   return pointer_or_operator::op1_range (r, type, lhs, op1);
4308 }
4309
4310 void
4311 pointer_or_operator::wi_fold (irange &r, tree type,
4312                               const wide_int &lh_lb,
4313                               const wide_int &lh_ub,
4314                               const wide_int &rh_lb,
4315                               const wide_int &rh_ub) const
4316 {
4317   // For pointer types, we are really only interested in asserting
4318   // whether the expression evaluates to non-NULL.
4319   if (!wi_includes_zero_p (type, lh_lb, lh_ub)
4320       && !wi_includes_zero_p (type, rh_lb, rh_ub))
4321     r = range_nonzero (type);
4322   else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
4323     r = range_zero (type);
4324   else
4325     r.set_varying (type);
4326 }
4327 \f
4328 // Return a pointer to the range_operator instance, if there is one
4329 // associated with tree_code CODE.
4330
4331 range_operator *
4332 range_op_table::operator[] (enum tree_code code)
4333 {
4334   gcc_checking_assert (code > 0 && code < MAX_TREE_CODES);
4335   return m_range_tree[code];
4336 }
4337
4338 // Add OP to the handler table for CODE.
4339
4340 void
4341 range_op_table::set (enum tree_code code, range_operator &op)
4342 {
4343   gcc_checking_assert (m_range_tree[code] == NULL);
4344   m_range_tree[code] = &op;
4345 }
4346
4347 // Instantiate a range op table for integral operations.
4348
4349 class integral_table : public range_op_table
4350 {
4351 public:
4352   integral_table ();
4353 } integral_tree_table;
4354
4355 integral_table::integral_table ()
4356 {
4357   set (EQ_EXPR, op_equal);
4358   set (NE_EXPR, op_not_equal);
4359   set (LT_EXPR, op_lt);
4360   set (LE_EXPR, op_le);
4361   set (GT_EXPR, op_gt);
4362   set (GE_EXPR, op_ge);
4363   set (PLUS_EXPR, op_plus);
4364   set (MINUS_EXPR, op_minus);
4365   set (MIN_EXPR, op_min);
4366   set (MAX_EXPR, op_max);
4367   set (MULT_EXPR, op_mult);
4368   set (TRUNC_DIV_EXPR, op_trunc_div);
4369   set (FLOOR_DIV_EXPR, op_floor_div);
4370   set (ROUND_DIV_EXPR, op_round_div);
4371   set (CEIL_DIV_EXPR, op_ceil_div);
4372   set (EXACT_DIV_EXPR, op_exact_div);
4373   set (LSHIFT_EXPR, op_lshift);
4374   set (RSHIFT_EXPR, op_rshift);
4375   set (NOP_EXPR, op_convert);
4376   set (CONVERT_EXPR, op_convert);
4377   set (TRUTH_AND_EXPR, op_logical_and);
4378   set (BIT_AND_EXPR, op_bitwise_and);
4379   set (TRUTH_OR_EXPR, op_logical_or);
4380   set (BIT_IOR_EXPR, op_bitwise_or);
4381   set (BIT_XOR_EXPR, op_bitwise_xor);
4382   set (TRUNC_MOD_EXPR, op_trunc_mod);
4383   set (TRUTH_NOT_EXPR, op_logical_not);
4384   set (BIT_NOT_EXPR, op_bitwise_not);
4385   set (INTEGER_CST, op_integer_cst);
4386   set (SSA_NAME, op_identity);
4387   set (PAREN_EXPR, op_identity);
4388   set (OBJ_TYPE_REF, op_identity);
4389   set (IMAGPART_EXPR, op_unknown);
4390   set (REALPART_EXPR, op_unknown);
4391   set (POINTER_DIFF_EXPR, op_pointer_diff);
4392   set (ABS_EXPR, op_abs);
4393   set (ABSU_EXPR, op_absu);
4394   set (NEGATE_EXPR, op_negate);
4395   set (ADDR_EXPR, op_addr);
4396 }
4397
4398 // Instantiate a range op table for pointer operations.
4399
4400 class pointer_table : public range_op_table
4401 {
4402 public:
4403   pointer_table ();
4404 } pointer_tree_table;
4405
4406 pointer_table::pointer_table ()
4407 {
4408   set (BIT_AND_EXPR, op_pointer_and);
4409   set (BIT_IOR_EXPR, op_pointer_or);
4410   set (MIN_EXPR, op_ptr_min_max);
4411   set (MAX_EXPR, op_ptr_min_max);
4412   set (POINTER_PLUS_EXPR, op_pointer_plus);
4413
4414   set (EQ_EXPR, op_equal);
4415   set (NE_EXPR, op_not_equal);
4416   set (LT_EXPR, op_lt);
4417   set (LE_EXPR, op_le);
4418   set (GT_EXPR, op_gt);
4419   set (GE_EXPR, op_ge);
4420   set (SSA_NAME, op_identity);
4421   set (INTEGER_CST, op_integer_cst);
4422   set (ADDR_EXPR, op_addr);
4423   set (NOP_EXPR, op_convert);
4424   set (CONVERT_EXPR, op_convert);
4425
4426   set (BIT_NOT_EXPR, op_bitwise_not);
4427   set (BIT_XOR_EXPR, op_bitwise_xor);
4428 }
4429
4430 // The tables are hidden and accessed via a simple extern function.
4431
4432 static inline range_operator *
4433 get_handler (enum tree_code code, tree type)
4434 {
4435   // First check if there is a pointer specialization.
4436   if (POINTER_TYPE_P (type))
4437     return pointer_tree_table[code];
4438   if (INTEGRAL_TYPE_P (type))
4439     return integral_tree_table[code];
4440   return NULL;
4441 }
4442
4443 // Return the floating point operator for CODE or NULL if none available.
4444
4445 static inline range_operator_float *
4446 get_float_handler (enum tree_code code, tree)
4447 {
4448   return (*floating_tree_table)[code];
4449 }
4450
4451 void
4452 range_op_handler::set_op_handler (tree_code code, tree type)
4453 {
4454   if (irange::supports_p (type))
4455     {
4456       m_float = NULL;
4457       m_int = get_handler (code, type);
4458       m_valid = m_int != NULL;
4459     }
4460   else if (frange::supports_p (type))
4461     {
4462       m_int = NULL;
4463       m_float = get_float_handler (code, type);
4464       m_valid = m_float != NULL;
4465     }
4466   else
4467     {
4468       m_int = NULL;
4469       m_float = NULL;
4470       m_valid = false;
4471     }
4472 }
4473
4474 range_op_handler::range_op_handler ()
4475 {
4476   m_int = NULL;
4477   m_float = NULL;
4478   m_valid = false;
4479 }
4480
4481 range_op_handler::range_op_handler (tree_code code, tree type)
4482 {
4483   set_op_handler (code, type);
4484 }
4485
4486
4487 bool
4488 range_op_handler::fold_range (vrange &r, tree type,
4489                               const vrange &lh,
4490                               const vrange &rh,
4491                               relation_trio rel) const
4492 {
4493   gcc_checking_assert (m_valid);
4494   if (m_int)
4495     return m_int->fold_range (as_a <irange> (r), type,
4496                            as_a <irange> (lh),
4497                            as_a <irange> (rh), rel);
4498
4499   if (is_a <irange> (r))
4500     {
4501       if (is_a <irange> (rh))
4502         return m_float->fold_range (as_a <irange> (r), type,
4503                                     as_a <frange> (lh),
4504                                     as_a <irange> (rh), rel);
4505       else
4506         return m_float->fold_range (as_a <irange> (r), type,
4507                                     as_a <frange> (lh),
4508                                     as_a <frange> (rh), rel);
4509     }
4510   return m_float->fold_range (as_a <frange> (r), type,
4511                               as_a <frange> (lh),
4512                               as_a <frange> (rh), rel);
4513 }
4514
4515 bool
4516 range_op_handler::op1_range (vrange &r, tree type,
4517                              const vrange &lhs,
4518                              const vrange &op2,
4519                              relation_trio rel) const
4520 {
4521   gcc_checking_assert (m_valid);
4522
4523   if (lhs.undefined_p ())
4524     return false;
4525   if (m_int)
4526     return m_int->op1_range (as_a <irange> (r), type,
4527                              as_a <irange> (lhs),
4528                              as_a <irange> (op2), rel);
4529
4530   if (is_a <irange> (lhs))
4531     return m_float->op1_range (as_a <frange> (r), type,
4532                                as_a <irange> (lhs),
4533                                as_a <frange> (op2), rel);
4534   return m_float->op1_range (as_a <frange> (r), type,
4535                              as_a <frange> (lhs),
4536                              as_a <frange> (op2), rel);
4537 }
4538
4539 bool
4540 range_op_handler::op2_range (vrange &r, tree type,
4541                              const vrange &lhs,
4542                              const vrange &op1,
4543                              relation_trio rel) const
4544 {
4545   gcc_checking_assert (m_valid);
4546   if (lhs.undefined_p ())
4547     return false;
4548   if (m_int)
4549     return m_int->op2_range (as_a <irange> (r), type,
4550                              as_a <irange> (lhs),
4551                              as_a <irange> (op1), rel);
4552
4553   if (is_a <irange> (lhs))
4554     return m_float->op2_range (as_a <frange> (r), type,
4555                                as_a <irange> (lhs),
4556                                as_a <frange> (op1), rel);
4557   return m_float->op2_range (as_a <frange> (r), type,
4558                              as_a <frange> (lhs),
4559                              as_a <frange> (op1), rel);
4560 }
4561
4562 relation_kind
4563 range_op_handler::lhs_op1_relation (const vrange &lhs,
4564                                     const vrange &op1,
4565                                     const vrange &op2,
4566                                     relation_kind rel) const
4567 {
4568   gcc_checking_assert (m_valid);
4569   if (m_int)
4570     return m_int->lhs_op1_relation (as_a <irange> (lhs),
4571                                     as_a <irange> (op1),
4572                                     as_a <irange> (op2), rel);
4573
4574   if (is_a <irange> (lhs))
4575     return m_float->lhs_op1_relation (as_a <irange> (lhs),
4576                                  as_a <frange> (op1),
4577                                  as_a <frange> (op2), rel);
4578   return m_float->lhs_op1_relation (as_a <frange> (lhs),
4579                                as_a <frange> (op1),
4580                                as_a <frange> (op2), rel);
4581 }
4582
4583 relation_kind
4584 range_op_handler::lhs_op2_relation (const vrange &lhs,
4585                                     const vrange &op1,
4586                                     const vrange &op2,
4587                                     relation_kind rel) const
4588 {
4589   gcc_checking_assert (m_valid);
4590   if (m_int)
4591     return m_int->lhs_op2_relation (as_a <irange> (lhs),
4592                                     as_a <irange> (op1),
4593                                     as_a <irange> (op2), rel);
4594
4595   if (is_a <irange> (lhs))
4596     return m_float->lhs_op2_relation (as_a <irange> (lhs),
4597                                       as_a <frange> (op1),
4598                                       as_a <frange> (op2), rel);
4599   return m_float->lhs_op2_relation (as_a <frange> (lhs),
4600                                       as_a <frange> (op1),
4601                                       as_a <frange> (op2), rel);
4602 }
4603
4604 relation_kind
4605 range_op_handler::op1_op2_relation (const vrange &lhs) const
4606 {
4607   gcc_checking_assert (m_valid);
4608   if (m_int)
4609     return m_int->op1_op2_relation (as_a <irange> (lhs));
4610   if (is_a <irange> (lhs))
4611     return m_float->op1_op2_relation (as_a <irange> (lhs));
4612   return m_float->op1_op2_relation (as_a <frange> (lhs));
4613 }
4614
4615 // Cast the range in R to TYPE.
4616
4617 bool
4618 range_cast (vrange &r, tree type)
4619 {
4620   Value_Range tmp (r);
4621   Value_Range varying (type);
4622   varying.set_varying (type);
4623   range_op_handler op (CONVERT_EXPR, type);
4624   // Call op_convert, if it fails, the result is varying.
4625   if (!op || !op.fold_range (r, type, tmp, varying))
4626     {
4627       r.set_varying (type);
4628       return false;
4629     }
4630   return true;
4631 }
4632
4633 #if CHECKING_P
4634 #include "selftest.h"
4635
4636 namespace selftest
4637 {
4638 #define INT(N) build_int_cst (integer_type_node, (N))
4639 #define UINT(N) build_int_cstu (unsigned_type_node, (N))
4640 #define INT16(N) build_int_cst (short_integer_type_node, (N))
4641 #define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
4642 #define SCHAR(N) build_int_cst (signed_char_type_node, (N))
4643 #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
4644
4645 static void
4646 range_op_cast_tests ()
4647 {
4648   int_range<1> r0, r1, r2, rold;
4649   r0.set_varying (integer_type_node);
4650   tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ());
4651
4652   // If a range is in any way outside of the range for the converted
4653   // to range, default to the range for the new type.
4654   r0.set_varying (short_integer_type_node);
4655   tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ());
4656   tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ());
4657   if (TYPE_PRECISION (TREE_TYPE (maxint))
4658       > TYPE_PRECISION (short_integer_type_node))
4659     {
4660       r1 = int_range<1> (integer_zero_node, maxint);
4661       range_cast (r1, short_integer_type_node);
4662       ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort)
4663                    && r1.upper_bound() == wi::to_wide (maxshort));
4664     }
4665
4666   // (unsigned char)[-5,-1] => [251,255].
4667   r0 = rold = int_range<1> (SCHAR (-5), SCHAR (-1));
4668   range_cast (r0, unsigned_char_type_node);
4669   ASSERT_TRUE (r0 == int_range<1> (UCHAR (251), UCHAR (255)));
4670   range_cast (r0, signed_char_type_node);
4671   ASSERT_TRUE (r0 == rold);
4672
4673   // (signed char)[15, 150] => [-128,-106][15,127].
4674   r0 = rold = int_range<1> (UCHAR (15), UCHAR (150));
4675   range_cast (r0, signed_char_type_node);
4676   r1 = int_range<1> (SCHAR (15), SCHAR (127));
4677   r2 = int_range<1> (SCHAR (-128), SCHAR (-106));
4678   r1.union_ (r2);
4679   ASSERT_TRUE (r1 == r0);
4680   range_cast (r0, unsigned_char_type_node);
4681   ASSERT_TRUE (r0 == rold);
4682
4683   // (unsigned char)[-5, 5] => [0,5][251,255].
4684   r0 = rold = int_range<1> (SCHAR (-5), SCHAR (5));
4685   range_cast (r0, unsigned_char_type_node);
4686   r1 = int_range<1> (UCHAR (251), UCHAR (255));
4687   r2 = int_range<1> (UCHAR (0), UCHAR (5));
4688   r1.union_ (r2);
4689   ASSERT_TRUE (r0 == r1);
4690   range_cast (r0, signed_char_type_node);
4691   ASSERT_TRUE (r0 == rold);
4692
4693   // (unsigned char)[-5,5] => [0,5][251,255].
4694   r0 = int_range<1> (INT (-5), INT (5));
4695   range_cast (r0, unsigned_char_type_node);
4696   r1 = int_range<1> (UCHAR (0), UCHAR (5));
4697   r1.union_ (int_range<1> (UCHAR (251), UCHAR (255)));
4698   ASSERT_TRUE (r0 == r1);
4699
4700   // (unsigned char)[5U,1974U] => [0,255].
4701   r0 = int_range<1> (UINT (5), UINT (1974));
4702   range_cast (r0, unsigned_char_type_node);
4703   ASSERT_TRUE (r0 == int_range<1> (UCHAR (0), UCHAR (255)));
4704   range_cast (r0, integer_type_node);
4705   // Going to a wider range should not sign extend.
4706   ASSERT_TRUE (r0 == int_range<1> (INT (0), INT (255)));
4707
4708   // (unsigned char)[-350,15] => [0,255].
4709   r0 = int_range<1> (INT (-350), INT (15));
4710   range_cast (r0, unsigned_char_type_node);
4711   ASSERT_TRUE (r0 == (int_range<1>
4712                       (TYPE_MIN_VALUE (unsigned_char_type_node),
4713                        TYPE_MAX_VALUE (unsigned_char_type_node))));
4714
4715   // Casting [-120,20] from signed char to unsigned short.
4716   // => [0, 20][0xff88, 0xffff].
4717   r0 = int_range<1> (SCHAR (-120), SCHAR (20));
4718   range_cast (r0, short_unsigned_type_node);
4719   r1 = int_range<1> (UINT16 (0), UINT16 (20));
4720   r2 = int_range<1> (UINT16 (0xff88), UINT16 (0xffff));
4721   r1.union_ (r2);
4722   ASSERT_TRUE (r0 == r1);
4723   // A truncating cast back to signed char will work because [-120, 20]
4724   // is representable in signed char.
4725   range_cast (r0, signed_char_type_node);
4726   ASSERT_TRUE (r0 == int_range<1> (SCHAR (-120), SCHAR (20)));
4727
4728   // unsigned char -> signed short
4729   //    (signed short)[(unsigned char)25, (unsigned char)250]
4730   // => [(signed short)25, (signed short)250]
4731   r0 = rold = int_range<1> (UCHAR (25), UCHAR (250));
4732   range_cast (r0, short_integer_type_node);
4733   r1 = int_range<1> (INT16 (25), INT16 (250));
4734   ASSERT_TRUE (r0 == r1);
4735   range_cast (r0, unsigned_char_type_node);
4736   ASSERT_TRUE (r0 == rold);
4737
4738   // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
4739   r0 = int_range<1> (TYPE_MIN_VALUE (long_long_integer_type_node),
4740                TYPE_MAX_VALUE (long_long_integer_type_node));
4741   range_cast (r0, short_unsigned_type_node);
4742   r1 = int_range<1> (TYPE_MIN_VALUE (short_unsigned_type_node),
4743                TYPE_MAX_VALUE (short_unsigned_type_node));
4744   ASSERT_TRUE (r0 == r1);
4745
4746   // Casting NONZERO to a narrower type will wrap/overflow so
4747   // it's just the entire range for the narrower type.
4748   //
4749   // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32].  This is
4750   // is outside of the range of a smaller range, return the full
4751   // smaller range.
4752   if (TYPE_PRECISION (integer_type_node)
4753       > TYPE_PRECISION (short_integer_type_node))
4754     {
4755       r0 = range_nonzero (integer_type_node);
4756       range_cast (r0, short_integer_type_node);
4757       r1 = int_range<1> (TYPE_MIN_VALUE (short_integer_type_node),
4758                          TYPE_MAX_VALUE (short_integer_type_node));
4759       ASSERT_TRUE (r0 == r1);
4760     }
4761
4762   // Casting NONZERO from a narrower signed to a wider signed.
4763   //
4764   // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
4765   // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
4766   r0 = range_nonzero (short_integer_type_node);
4767   range_cast (r0, integer_type_node);
4768   r1 = int_range<1> (INT (-32768), INT (-1));
4769   r2 = int_range<1> (INT (1), INT (32767));
4770   r1.union_ (r2);
4771   ASSERT_TRUE (r0 == r1);
4772 }
4773
4774 static void
4775 range_op_lshift_tests ()
4776 {
4777   // Test that 0x808.... & 0x8.... still contains 0x8....
4778   // for a large set of numbers.
4779   {
4780     int_range_max res;
4781     tree big_type = long_long_unsigned_type_node;
4782     // big_num = 0x808,0000,0000,0000
4783     tree big_num = fold_build2 (LSHIFT_EXPR, big_type,
4784                                 build_int_cst (big_type, 0x808),
4785                                 build_int_cst (big_type, 48));
4786     op_bitwise_and.fold_range (res, big_type,
4787                                int_range <1> (big_type),
4788                                int_range <1> (big_num, big_num));
4789     // val = 0x8,0000,0000,0000
4790     tree val = fold_build2 (LSHIFT_EXPR, big_type,
4791                             build_int_cst (big_type, 0x8),
4792                             build_int_cst (big_type, 48));
4793     ASSERT_TRUE (res.contains_p (val));
4794   }
4795
4796   if (TYPE_PRECISION (unsigned_type_node) > 31)
4797     {
4798       // unsigned VARYING = op1 << 1 should be VARYING.
4799       int_range<2> lhs (unsigned_type_node);
4800       int_range<2> shift (INT (1), INT (1));
4801       int_range_max op1;
4802       op_lshift.op1_range (op1, unsigned_type_node, lhs, shift);
4803       ASSERT_TRUE (op1.varying_p ());
4804
4805       // 0 = op1 << 1  should be [0,0], [0x8000000, 0x8000000].
4806       int_range<2> zero (UINT (0), UINT (0));
4807       op_lshift.op1_range (op1, unsigned_type_node, zero, shift);
4808       ASSERT_TRUE (op1.num_pairs () == 2);
4809       // Remove the [0,0] range.
4810       op1.intersect (zero);
4811       ASSERT_TRUE (op1.num_pairs () == 1);
4812       //  op1 << 1   should be [0x8000,0x8000] << 1,
4813       //  which should result in [0,0].
4814       int_range_max result;
4815       op_lshift.fold_range (result, unsigned_type_node, op1, shift);
4816       ASSERT_TRUE (result == zero);
4817     }
4818   // signed VARYING = op1 << 1 should be VARYING.
4819   if (TYPE_PRECISION (integer_type_node) > 31)
4820     {
4821       // unsigned VARYING = op1 << 1  hould be VARYING.
4822       int_range<2> lhs (integer_type_node);
4823       int_range<2> shift (INT (1), INT (1));
4824       int_range_max op1;
4825       op_lshift.op1_range (op1, integer_type_node, lhs, shift);
4826       ASSERT_TRUE (op1.varying_p ());
4827
4828       //  0 = op1 << 1  should be [0,0], [0x8000000, 0x8000000].
4829       int_range<2> zero (INT (0), INT (0));
4830       op_lshift.op1_range (op1, integer_type_node, zero, shift);
4831       ASSERT_TRUE (op1.num_pairs () == 2);
4832       // Remove the [0,0] range.
4833       op1.intersect (zero);
4834       ASSERT_TRUE (op1.num_pairs () == 1);
4835       //  op1 << 1   shuould be [0x8000,0x8000] << 1,
4836       //  which should result in [0,0].
4837       int_range_max result;
4838       op_lshift.fold_range (result, unsigned_type_node, op1, shift);
4839       ASSERT_TRUE (result == zero);
4840     }
4841 }
4842
4843 static void
4844 range_op_rshift_tests ()
4845 {
4846   // unsigned: [3, MAX] = OP1 >> 1
4847   {
4848     int_range_max lhs (build_int_cst (unsigned_type_node, 3),
4849                        TYPE_MAX_VALUE (unsigned_type_node));
4850     int_range_max one (build_one_cst (unsigned_type_node),
4851                        build_one_cst (unsigned_type_node));
4852     int_range_max op1;
4853     op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
4854     ASSERT_FALSE (op1.contains_p (UINT (3)));
4855   }
4856
4857   // signed: [3, MAX] = OP1 >> 1
4858   {
4859     int_range_max lhs (INT (3), TYPE_MAX_VALUE (integer_type_node));
4860     int_range_max one (INT (1), INT (1));
4861     int_range_max op1;
4862     op_rshift.op1_range (op1, integer_type_node, lhs, one);
4863     ASSERT_FALSE (op1.contains_p (INT (-2)));
4864   }
4865
4866   // This is impossible, so OP1 should be [].
4867   // signed: [MIN, MIN] = OP1 >> 1
4868   {
4869     int_range_max lhs (TYPE_MIN_VALUE (integer_type_node),
4870                        TYPE_MIN_VALUE (integer_type_node));
4871     int_range_max one (INT (1), INT (1));
4872     int_range_max op1;
4873     op_rshift.op1_range (op1, integer_type_node, lhs, one);
4874     ASSERT_TRUE (op1.undefined_p ());
4875   }
4876
4877   // signed: ~[-1] = OP1 >> 31
4878   if (TYPE_PRECISION (integer_type_node) > 31)
4879     {
4880       int_range_max lhs (INT (-1), INT (-1), VR_ANTI_RANGE);
4881       int_range_max shift (INT (31), INT (31));
4882       int_range_max op1;
4883       op_rshift.op1_range (op1, integer_type_node, lhs, shift);
4884       int_range_max negatives = range_negatives (integer_type_node);
4885       negatives.intersect (op1);
4886       ASSERT_TRUE (negatives.undefined_p ());
4887     }
4888 }
4889
4890 static void
4891 range_op_bitwise_and_tests ()
4892 {
4893   int_range_max res;
4894   tree min = vrp_val_min (integer_type_node);
4895   tree max = vrp_val_max (integer_type_node);
4896   tree tiny = fold_build2 (PLUS_EXPR, integer_type_node, min,
4897                            build_one_cst (integer_type_node));
4898   int_range_max i1 (tiny, max);
4899   int_range_max i2 (build_int_cst (integer_type_node, 255),
4900                     build_int_cst (integer_type_node, 255));
4901
4902   // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
4903   op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
4904   ASSERT_TRUE (res == int_range<1> (integer_type_node));
4905
4906   // VARYING = OP1 & 255: OP1 is VARYING
4907   i1 = int_range<1> (integer_type_node);
4908   op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
4909   ASSERT_TRUE (res == int_range<1> (integer_type_node));
4910
4911   // For 0 = x & MASK, x is ~MASK.
4912   {
4913     int_range<2> zero (integer_zero_node, integer_zero_node);
4914     int_range<2> mask = int_range<2> (INT (7), INT (7));
4915     op_bitwise_and.op1_range (res, integer_type_node, zero, mask);
4916     wide_int inv = wi::shwi (~7U, TYPE_PRECISION (integer_type_node));
4917     ASSERT_TRUE (res.get_nonzero_bits () == inv);
4918   }
4919
4920   // (NONZERO | X) is nonzero.
4921   i1.set_nonzero (integer_type_node);
4922   i2.set_varying (integer_type_node);
4923   op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
4924   ASSERT_TRUE (res.nonzero_p ());
4925
4926   // (NEGATIVE | X) is nonzero.
4927   i1 = int_range<1> (INT (-5), INT (-3));
4928   i2.set_varying (integer_type_node);
4929   op_bitwise_or.fold_range (res, integer_type_node, i1, i2);
4930   ASSERT_FALSE (res.contains_p (INT (0)));
4931 }
4932
4933 static void
4934 range_relational_tests ()
4935 {
4936   int_range<2> lhs (unsigned_char_type_node);
4937   int_range<2> op1 (UCHAR (8), UCHAR (10));
4938   int_range<2> op2 (UCHAR (20), UCHAR (20));
4939
4940   // Never wrapping additions mean LHS > OP1.
4941   relation_kind code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
4942   ASSERT_TRUE (code == VREL_GT);
4943
4944   // Most wrapping additions mean nothing...
4945   op1 = int_range<2> (UCHAR (8), UCHAR (10));
4946   op2 = int_range<2> (UCHAR (0), UCHAR (255));
4947   code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
4948   ASSERT_TRUE (code == VREL_VARYING);
4949
4950   // However, always wrapping additions mean LHS < OP1.
4951   op1 = int_range<2> (UCHAR (1), UCHAR (255));
4952   op2 = int_range<2> (UCHAR (255), UCHAR (255));
4953   code = op_plus.lhs_op1_relation (lhs, op1, op2, VREL_VARYING);
4954   ASSERT_TRUE (code == VREL_LT);
4955 }
4956
4957 void
4958 range_op_tests ()
4959 {
4960   range_op_rshift_tests ();
4961   range_op_lshift_tests ();
4962   range_op_bitwise_and_tests ();
4963   range_op_cast_tests ();
4964   range_relational_tests ();
4965
4966   extern void range_op_float_tests ();
4967   range_op_float_tests ();
4968 }
4969
4970 } // namespace selftest
4971
4972 #endif // CHECKING_P