gcc/range-op.cc

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