gcc/range-op.cc

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