In PR70010, a function is marked with target(no-vsx) to disable VSX code

[thirdparty/gcc.git] / gcc / range-op.cc

/* Code for range operators.
   Copyright (C) 2017-2019 Free Software Foundation, Inc.
   Contributed by Andrew MacLeod <amacleod@redhat.com>
   and Aldy Hernandez <aldyh@redhat.com>.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "insn-codes.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "tree-pass.h"
#include "ssa.h"
#include "optabs-tree.h"
#include "gimple-pretty-print.h"
#include "diagnostic-core.h"
#include "flags.h"
#include "fold-const.h"
#include "stor-layout.h"
#include "calls.h"
#include "cfganal.h"
#include "gimple-fold.h"
#include "tree-eh.h"
#include "gimple-iterator.h"
#include "gimple-walk.h"
#include "tree-cfg.h"
#include "wide-int.h"
#include "range-op.h"

// Return the upper limit for a type.

static inline wide_int
max_limit (const_tree type)
{
  return wi::max_value (TYPE_PRECISION (type) , TYPE_SIGN (type));
}

// Return the lower limit for a type.

static inline wide_int
min_limit (const_tree type)
{
  return wi::min_value (TYPE_PRECISION (type) , TYPE_SIGN (type));
}

// If the range of either op1 or op2 is undefined, set the result to
// undefined and return TRUE.

inline bool
empty_range_check (value_range_base &r,
                   const value_range_base &op1,
                   const value_range_base & op2)
{
  if (op1.undefined_p () || op2.undefined_p ())
    {
      r.set_undefined ();
      return true;
    }
  else
    return false;
}

// Return TRUE if shifting by OP is undefined behavior, and set R to
// the appropriate range.

static inline bool
undefined_shift_range_check (value_range_base &r, tree type,
                             value_range_base op)
{
  if (op.undefined_p ())
    {
      r = value_range_base ();
      return true;
    }

  // Shifting by any values outside [0..prec-1], gets undefined
  // behavior from the shift operation.  We cannot even trust
  // SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
  // shifts, and the operation at the tree level may be widened.
  if (wi::lt_p (op.lower_bound (), 0, TYPE_SIGN (op.type ()))
      || wi::ge_p (op.upper_bound (),
                   TYPE_PRECISION (type), TYPE_SIGN (op.type ())))
    {
      r = value_range_base (type);
      return true;
    }
  return false;
}

// Return TRUE if 0 is within [WMIN, WMAX].

static inline bool
wi_includes_zero_p (tree type, const wide_int &wmin, const wide_int &wmax)
{
  signop sign = TYPE_SIGN (type);
  return wi::le_p (wmin, 0, sign) && wi::ge_p (wmax, 0, sign);
}

// Return TRUE if [WMIN, WMAX] is the singleton 0.

static inline bool
wi_zero_p (tree type, const wide_int &wmin, const wide_int &wmax)
{
  unsigned prec = TYPE_PRECISION (type);
  return wmin == wmax && wi::eq_p (wmin, wi::zero (prec));
}

// Default wide_int fold operation returns [MIN, MAX].

value_range_base
range_operator::wi_fold (tree type,
                         const wide_int &lh_lb ATTRIBUTE_UNUSED,
                         const wide_int &lh_ub ATTRIBUTE_UNUSED,
                         const wide_int &rh_lb ATTRIBUTE_UNUSED,
                         const wide_int &rh_ub ATTRIBUTE_UNUSED) const
{
  return value_range_base (type);
}

// The default for fold is to break all ranges into sub-ranges and
// invoke the wi_fold method on each sub-range pair.

value_range_base
range_operator::fold_range (tree type,
                            const value_range_base &lh,
                            const value_range_base &rh) const
{
  value_range_base r;
  if (empty_range_check (r, lh, rh))
    return r;

  for (unsigned x = 0; x < lh.num_pairs (); ++x)
    for (unsigned y = 0; y < rh.num_pairs (); ++y)
      {
        wide_int lh_lb = lh.lower_bound (x);
        wide_int lh_ub = lh.upper_bound (x);
        wide_int rh_lb = rh.lower_bound (y);
        wide_int rh_ub = rh.upper_bound (y);
        r.union_ (wi_fold (type, lh_lb, lh_ub, rh_lb, rh_ub));
        if (r.varying_p ())
          return r;
      }
  return r;
}

// The default for op1_range is to return false.

bool
range_operator::op1_range (value_range_base &r ATTRIBUTE_UNUSED,
                           tree type ATTRIBUTE_UNUSED,
                           const value_range_base &lhs ATTRIBUTE_UNUSED,
                           const value_range_base &op2 ATTRIBUTE_UNUSED) const
{
  return false;
}

// The default for op2_range is to return false.

bool
range_operator::op2_range (value_range_base &r ATTRIBUTE_UNUSED,
                           tree type ATTRIBUTE_UNUSED,
                           const value_range_base &lhs ATTRIBUTE_UNUSED,
                           const value_range_base &op1 ATTRIBUTE_UNUSED) const
{
  return false;
}


// Create and return a range from a pair of wide-ints that are known
// to have overflowed (or underflowed).

static value_range_base
value_range_from_overflowed_bounds (tree type,
                                    const wide_int &wmin,
                                    const wide_int &wmax)
{
  const signop sgn = TYPE_SIGN (type);
  const unsigned int prec = TYPE_PRECISION (type);

  wide_int tmin = wide_int::from (wmin, prec, sgn);
  wide_int tmax = wide_int::from (wmax, prec, sgn);

  bool covers = false;
  wide_int tem = tmin;
  tmin = tmax + 1;
  if (wi::cmp (tmin, tmax, sgn) < 0)
    covers = true;
  tmax = tem - 1;
  if (wi::cmp (tmax, tem, sgn) > 0)
    covers = true;

  // If the anti-range would cover nothing, drop to varying.
  // Likewise if the anti-range bounds are outside of the types
  // values.
  if (covers || wi::cmp (tmin, tmax, sgn) > 0)
    return value_range_base (type);

  return value_range_base (VR_ANTI_RANGE, type, tmin, tmax);
}

// Create and return a range from a pair of wide-ints.  MIN_OVF and
// MAX_OVF describe any overflow that might have occurred while
// calculating WMIN and WMAX respectively.

static value_range_base
value_range_with_overflow (tree type,
                           const wide_int &wmin, const wide_int &wmax,
                           wi::overflow_type min_ovf = wi::OVF_NONE,
                           wi::overflow_type max_ovf = wi::OVF_NONE)
{
  const signop sgn = TYPE_SIGN (type);
  const unsigned int prec = TYPE_PRECISION (type);
  const bool overflow_wraps = TYPE_OVERFLOW_WRAPS (type);

  // For one bit precision if max != min, then the range covers all
  // values.
  if (prec == 1 && wi::ne_p (wmax, wmin))
    return value_range_base (type);

  if (overflow_wraps)
    {
      // If overflow wraps, truncate the values and adjust the range,
      // kind, and bounds appropriately.
      if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE))
        {
          wide_int tmin = wide_int::from (wmin, prec, sgn);
          wide_int tmax = wide_int::from (wmax, prec, sgn);
          // If the limits are swapped, we wrapped around and cover
          // the entire range.
          if (wi::gt_p (tmin, tmax, sgn))
            return value_range_base (type);

          // No overflow or both overflow or underflow.  The range
          // kind stays normal.
          return value_range_base (type, tmin, tmax);
        }

      if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE)
          || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE))
        return value_range_from_overflowed_bounds (type, wmin, wmax);

      // Other underflow and/or overflow, drop to VR_VARYING.
      return value_range_base (type);
    }
  else
    {
      // If overflow does not wrap, saturate to [MIN, MAX].
      wide_int new_lb, new_ub;
      if (min_ovf == wi::OVF_UNDERFLOW)
        new_lb = wi::min_value (prec, sgn);
      else if (min_ovf == wi::OVF_OVERFLOW)
        new_lb = wi::max_value (prec, sgn);
      else
        new_lb = wmin;

      if (max_ovf == wi::OVF_UNDERFLOW)
        new_ub = wi::min_value (prec, sgn);
      else if (max_ovf == wi::OVF_OVERFLOW)
        new_ub = wi::max_value (prec, sgn);
      else
        new_ub = wmax;

      return value_range_base (type, new_lb, new_ub);
    }
}

// Create and return a range from a pair of wide-ints.  Canonicalize
// the case where the bounds are swapped.  In which case, we transform
// [10,5] into [MIN,5][10,MAX].

static inline value_range_base
create_possibly_reversed_range (tree type,
                                const wide_int &new_lb, const wide_int &new_ub)
{
  signop s = TYPE_SIGN (type);
  // If the bounds are swapped, treat the result as if an overflow occured.
  if (wi::gt_p (new_lb, new_ub, s))
    return value_range_from_overflowed_bounds (type, new_lb, new_ub);

  // Otherwise its just a normal range.
  return value_range_base (type, new_lb, new_ub);
}

// Return a value_range_base instance that is a boolean TRUE.

static inline value_range_base
range_true (tree type)
{
  unsigned prec = TYPE_PRECISION (type);
  return value_range_base (type, wi::one (prec), wi::one (prec));
}

// Return a value_range_base instance that is a boolean FALSE.

static inline value_range_base
range_false (tree type)
{
  unsigned prec = TYPE_PRECISION (type);
  return value_range_base (type, wi::zero (prec), wi::zero (prec));
}

// Return a value_range_base that covers both true and false.

static inline value_range_base
range_true_and_false (tree type)
{
  unsigned prec = TYPE_PRECISION (type);
  return value_range_base (type, wi::zero (prec), wi::one (prec));
}

enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL };

// Return the summary information about boolean range LHS.  Return an
// "interesting" range in R.  For EMPTY or FULL, return the equivalent
// range for TYPE, for BRS_TRUE and BRS false, return the negation of
// the bool range.

static bool_range_state
get_bool_state (value_range_base &r,
                const value_range_base &lhs, tree val_type)
{
  // If there is no result, then this is unexecutable.
  if (lhs.undefined_p ())
    {
      r.set_undefined ();
      return BRS_EMPTY;
    }

  // If the bounds aren't the same, then it's not a constant.
  if (!wi::eq_p (lhs.upper_bound (), lhs.lower_bound ()))
    {
      r.set_varying (val_type);
      return BRS_FULL;
    }

  if (lhs.zero_p ())
    return BRS_FALSE;

  return BRS_TRUE;
}


class operator_equal : public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &val) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &val) const;
} op_equal;

value_range_base
operator_equal::fold_range (tree type,
                            const value_range_base &op1,
                            const value_range_base &op2) const
{
  value_range_base r;
  if (empty_range_check (r, op1, op2))
    return r;

  // We can be sure the values are always equal or not if both ranges
  // consist of a single value, and then compare them.
  if (wi::eq_p (op1.lower_bound (), op1.upper_bound ())
      && wi::eq_p (op2.lower_bound (), op2.upper_bound ()))
    {
      if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
        r = range_true (type);
      else
        r = range_false (type);
    }
  else
    {
      // If ranges do not intersect, we know the range is not equal,
      // otherwise we don't know anything for sure.
      r = range_intersect (op1, op2);
      if (r.undefined_p ())
        r = range_false (type);
      else
        r = range_true_and_false (type);
    }

  return r;
}

bool
operator_equal::op1_range (value_range_base &r, tree type,
                           const value_range_base &lhs,
                           const value_range_base &op2) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_FALSE:
      // If the result is false, the only time we know anything is
      // if OP2 is a constant.
      if (wi::eq_p (op2.lower_bound(), op2.upper_bound()))
        r = range_invert (op2);
      else
        r.set_varying (type);
      break;

    case BRS_TRUE:
      // If it's true, the result is the same as OP2.
      r = op2;
      break;

    default:
      break;
    }
  return true;
}

bool
operator_equal::op2_range (value_range_base &r, tree type,
                           const value_range_base &lhs,
                           const value_range_base &op1) const
{
  return operator_equal::op1_range (r, type, lhs, op1);
}


class operator_not_equal : public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
} op_not_equal;

value_range_base
operator_not_equal::fold_range (tree type,
                                const value_range_base &op1,
                                const value_range_base &op2) const
{
  value_range_base r;
  if (empty_range_check (r, op1, op2))
    return r;

  // We can be sure the values are always equal or not if both ranges
  // consist of a single value, and then compare them.
  if (wi::eq_p (op1.lower_bound (), op1.upper_bound ())
      && wi::eq_p (op2.lower_bound (), op2.upper_bound ()))
    {
      if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
        r = range_true (type);
      else
        r = range_false (type);
    }
  else
    {
      // If ranges do not intersect, we know the range is not equal,
      // otherwise we don't know anything for sure.
      r = range_intersect (op1, op2);
      if (r.undefined_p ())
        r = range_true (type);
      else
        r = range_true_and_false (type);
    }

  return r;
}

bool
operator_not_equal::op1_range (value_range_base &r, tree type,
                               const value_range_base &lhs,
                               const value_range_base &op2) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_TRUE:
      // If the result is true, the only time we know anything is if
      // OP2 is a constant.
      if (wi::eq_p (op2.lower_bound(), op2.upper_bound()))
        r = range_invert (op2);
      else
        r.set_varying (type);
      break;

    case BRS_FALSE:
      // If its true, the result is the same as OP2.
      r = op2;
      break;

    default:
      break;
    }
  return true;
}


bool
operator_not_equal::op2_range (value_range_base &r, tree type,
                               const value_range_base &lhs,
                               const value_range_base &op1) const
{
  return operator_not_equal::op1_range (r, type, lhs, op1);
}

// (X < VAL) produces the range of [MIN, VAL - 1].

static void
build_lt (value_range_base &r, tree type, const wide_int &val)
{
  wi::overflow_type ov;
  wide_int lim = wi::sub (val, 1, TYPE_SIGN (type), &ov);

  // If val - 1 underflows, check if X < MIN, which is an empty range.
  if (ov)
    r.set_undefined ();
  else
    r = value_range_base (type, min_limit (type), lim);
}

// (X <= VAL) produces the range of [MIN, VAL].

static void
build_le (value_range_base &r, tree type, const wide_int &val)
{
  r = value_range_base (type, min_limit (type), val);
}

// (X > VAL) produces the range of [VAL + 1, MAX].

static void
build_gt (value_range_base &r, tree type, const wide_int &val)
{
  wi::overflow_type ov;
  wide_int lim = wi::add (val, 1, TYPE_SIGN (type), &ov);
  // If val + 1 overflows, check is for X > MAX, which is an empty range.
  if (ov)
    r.set_undefined ();
  else
    r = value_range_base (type, lim, max_limit (type));
}

// (X >= val) produces the range of [VAL, MAX].

static void
build_ge (value_range_base &r, tree type, const wide_int &val)
{
  r = value_range_base (type, val, max_limit (type));
}


class operator_lt :  public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
} op_lt;

value_range_base
operator_lt::fold_range (tree type,
                         const value_range_base &op1,
                         const value_range_base &op2) const
{
  value_range_base r;
  if (empty_range_check (r, op1, op2))
    return r;

  signop sign = TYPE_SIGN (op1.type ());
  gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));

  if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
    r = range_true (type);
  else if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
    r = range_false (type);
  else
    r = range_true_and_false (type);
  return r;
}

bool
operator_lt::op1_range (value_range_base &r, tree type,
                        const value_range_base &lhs,
                        const value_range_base &op2) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_TRUE:
      build_lt (r, type, op2.upper_bound ());
      break;

    case BRS_FALSE:
      build_ge (r, type, op2.lower_bound ());
      break;

    default:
      break;
    }
  return true;
}

bool
operator_lt::op2_range (value_range_base &r, tree type,
                        const value_range_base &lhs,
                        const value_range_base &op1) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_FALSE:
      build_le (r, type, op1.upper_bound ());
      break;

    case BRS_TRUE:
      build_gt (r, type, op1.lower_bound ());
      break;

    default:
      break;
    }
  return true;
}


class operator_le :  public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
} op_le;

value_range_base
operator_le::fold_range (tree type,
                         const value_range_base &op1,
                         const value_range_base &op2) const
{
  value_range_base r;
  if (empty_range_check (r, op1, op2))
    return r;

  signop sign = TYPE_SIGN (op1.type ());
  gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));

  if (wi::le_p (op1.upper_bound (), op2.lower_bound (), sign))
    r = range_true (type);
  else if (!wi::le_p (op1.lower_bound (), op2.upper_bound (), sign))
    r = range_false (type);
  else
    r = range_true_and_false (type);
  return r;
}

bool
operator_le::op1_range (value_range_base &r, tree type,
                        const value_range_base &lhs,
                        const value_range_base &op2) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_TRUE:
      build_le (r, type, op2.upper_bound ());
      break;

    case BRS_FALSE:
      build_gt (r, type, op2.lower_bound ());
      break;

    default:
      break;
    }
  return true;
}

bool
operator_le::op2_range (value_range_base &r, tree type,
                        const value_range_base &lhs,
                        const value_range_base &op1) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_FALSE:
      build_lt (r, type, op1.upper_bound ());
      break;

    case BRS_TRUE:
      build_ge (r, type, op1.lower_bound ());
      break;

    default:
      break;
    }
  return true;
}


class operator_gt :  public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
} op_gt;

value_range_base
operator_gt::fold_range (tree type,
                         const value_range_base &op1,
                         const value_range_base &op2) const
{
  value_range_base r;
  if (empty_range_check (r, op1, op2))
    return r;

  signop sign = TYPE_SIGN (op1.type ());
  gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));

  if (wi::gt_p (op1.lower_bound (), op2.upper_bound (), sign))
    r = range_true (type);
  else if (!wi::gt_p (op1.upper_bound (), op2.lower_bound (), sign))
    r = range_false (type);
  else
    r = range_true_and_false (type);
  return r;
}

bool
operator_gt::op1_range (value_range_base &r, tree type,
                        const value_range_base &lhs,
                        const value_range_base &op2) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_TRUE:
      build_gt (r, type, op2.lower_bound ());
      break;

    case BRS_FALSE:
      build_le (r, type, op2.upper_bound ());
      break;

    default:
      break;
    }
  return true;
}

bool
operator_gt::op2_range (value_range_base &r, tree type,
                        const value_range_base &lhs,
                        const value_range_base &op1) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_FALSE:
      build_ge (r, type, op1.lower_bound ());
      break;

    case BRS_TRUE:
      build_lt (r, type, op1.upper_bound ());
      break;

    default:
      break;
    }
  return true;
}


class operator_ge :  public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
} op_ge;

value_range_base
operator_ge::fold_range (tree type,
                         const value_range_base &op1,
                         const value_range_base &op2) const
{
  value_range_base r;
  if (empty_range_check (r, op1, op2))
    return r;

  signop sign = TYPE_SIGN (op1.type ());
  gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));

  if (wi::ge_p (op1.lower_bound (), op2.upper_bound (), sign))
    r = range_true (type);
  else if (!wi::ge_p (op1.upper_bound (), op2.lower_bound (), sign))
    r = range_false (type);
  else
    r = range_true_and_false (type);
  return r;
}

bool
operator_ge::op1_range (value_range_base &r, tree type,
                        const value_range_base &lhs,
                        const value_range_base &op2) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_TRUE:
      build_ge (r, type, op2.lower_bound ());
      break;

    case BRS_FALSE:
      build_lt (r, type, op2.upper_bound ());
      break;

    default:
      break;
    }
  return true;
}

bool
operator_ge::op2_range (value_range_base &r, tree type,
                        const value_range_base &lhs,
                        const value_range_base &op1) const
{
  switch (get_bool_state (r, lhs, type))
    {
    case BRS_FALSE:
      build_gt (r, type, op1.lower_bound ());
      break;

    case BRS_TRUE:
      build_le (r, type, op1.upper_bound ());
      break;

    default:
      break;
    }
  return true;
}


class operator_plus : public range_operator
{
public:
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
} op_plus;

value_range_base
operator_plus::wi_fold (tree type,
                        const wide_int &lh_lb, const wide_int &lh_ub,
                        const wide_int &rh_lb, const wide_int &rh_ub) const
{
  wi::overflow_type ov_lb, ov_ub;
  signop s = TYPE_SIGN (type);
  wide_int new_lb = wi::add (lh_lb, rh_lb, s, &ov_lb);
  wide_int new_ub = wi::add (lh_ub, rh_ub, s, &ov_ub);
  return value_range_with_overflow (type, new_lb, new_ub, ov_lb, ov_ub);
}

bool
operator_plus::op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const
{
  r = range_op_handler (MINUS_EXPR, type)->fold_range (type, lhs, op2);
  return true;
}

bool
operator_plus::op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const
{
  r = range_op_handler (MINUS_EXPR, type)->fold_range (type, lhs, op1);
  return true;
}


class operator_minus : public range_operator
{
public:
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
} op_minus;

value_range_base
operator_minus::wi_fold (tree type,
                         const wide_int &lh_lb, const wide_int &lh_ub,
                         const wide_int &rh_lb, const wide_int &rh_ub) const
{
  wi::overflow_type ov_lb, ov_ub;
  signop s = TYPE_SIGN (type);
  wide_int new_lb = wi::sub (lh_lb, rh_ub, s, &ov_lb);
  wide_int new_ub = wi::sub (lh_ub, rh_lb, s, &ov_ub);
  return value_range_with_overflow (type, new_lb, new_ub, ov_lb, ov_ub);
}

bool
operator_minus::op1_range (value_range_base &r, tree type,
                           const value_range_base &lhs,
                           const value_range_base &op2) const
{
  r = range_op_handler (PLUS_EXPR, type)->fold_range (type, lhs, op2);
  return true;
}

bool
operator_minus::op2_range (value_range_base &r, tree type,
                           const value_range_base &lhs,
                           const value_range_base &op1) const
{
  r = fold_range (type, op1, lhs);
  return true;
}


class operator_min : public range_operator
{
public:
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
} op_min;

value_range_base
operator_min::wi_fold (tree type,
                       const wide_int &lh_lb, const wide_int &lh_ub,
                       const wide_int &rh_lb, const wide_int &rh_ub) const
{
  signop s = TYPE_SIGN (type);
  wide_int new_lb = wi::min (lh_lb, rh_lb, s);
  wide_int new_ub = wi::min (lh_ub, rh_ub, s);
  return value_range_with_overflow (type, new_lb, new_ub);
}


class operator_max : public range_operator
{
public:
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
} op_max;

value_range_base
operator_max::wi_fold (tree type,
                       const wide_int &lh_lb, const wide_int &lh_ub,
                       const wide_int &rh_lb, const wide_int &rh_ub) const
{
  signop s = TYPE_SIGN (type);
  wide_int new_lb = wi::max (lh_lb, rh_lb, s);
  wide_int new_ub = wi::max (lh_ub, rh_ub, s);
  return value_range_with_overflow (type, new_lb, new_ub);
}


class cross_product_operator : public range_operator
{
public:
  // Perform an operation between two wide-ints and place the result
  // in R.  Return true if the operation overflowed.
  virtual bool wi_op_overflows (wide_int &r,
                                tree type,
                                const wide_int &,
                                const wide_int &) const = 0;

  // Calculate the cross product of two sets of sub-ranges and return it.
  value_range_base wi_cross_product (tree type,
                                     const wide_int &lh_lb,
                                     const wide_int &lh_ub,
                                     const wide_int &rh_lb,
                                     const wide_int &rh_ub) const;
};

// Calculate the cross product of two sets of ranges and return it.
//
// Multiplications, divisions and shifts are a bit tricky to handle,
// depending on the mix of signs we have in the two ranges, we need to
// operate on different values to get the minimum and maximum values
// for the new range.  One approach is to figure out all the
// variations of range combinations and do the operations.
//
// However, this involves several calls to compare_values and it is
// pretty convoluted.  It's simpler to do the 4 operations (MIN0 OP
// MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP MAX1) and then
// figure the smallest and largest values to form the new range.

value_range_base
cross_product_operator::wi_cross_product (tree type,
                                          const wide_int &lh_lb,
                                          const wide_int &lh_ub,
                                          const wide_int &rh_lb,
                                          const wide_int &rh_ub) const
{
  wide_int cp1, cp2, cp3, cp4;

  // Compute the 4 cross operations, bailing if we get an overflow we
  // can't handle.
  if (wi_op_overflows (cp1, type, lh_lb, rh_lb))
    return value_range_base (type);
  if (wi::eq_p (lh_lb, lh_ub))
    cp3 = cp1;
  else if (wi_op_overflows (cp3, type, lh_ub, rh_lb))
    return value_range_base (type);
  if (wi::eq_p (rh_lb, rh_ub))
    cp2 = cp1;
  else if (wi_op_overflows (cp2, type, lh_lb, rh_ub))
    return value_range_base (type);
  if (wi::eq_p (lh_lb, lh_ub))
    cp4 = cp2;
  else if (wi_op_overflows (cp4, type, lh_ub, rh_ub))
    return value_range_base (type);

  // Order pairs.
  signop sign = TYPE_SIGN (type);
  if (wi::gt_p (cp1, cp2, sign))
    std::swap (cp1, cp2);
  if (wi::gt_p (cp3, cp4, sign))
    std::swap (cp3, cp4);

  // Choose min and max from the ordered pairs.
  wide_int res_lb = wi::min (cp1, cp3, sign);
  wide_int res_ub = wi::max (cp2, cp4, sign);
  return value_range_with_overflow (type, res_lb, res_ub);
}


class operator_mult : public cross_product_operator
{
public:
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
  virtual bool wi_op_overflows (wide_int &res,
                                tree type,
                                const wide_int &w0,
                                const wide_int &w1) const;
} op_mult;

bool
operator_mult::wi_op_overflows (wide_int &res,
                                tree type,
                                const wide_int &w0,
                                const wide_int &w1) const
{
  wi::overflow_type overflow = wi::OVF_NONE;
  signop sign = TYPE_SIGN (type);
  res = wi::mul (w0, w1, sign, &overflow);
   if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
     {
       // For multiplication, the sign of the overflow is given
       // by the comparison of the signs of the operands.
       if (sign == UNSIGNED || w0.sign_mask () == w1.sign_mask ())
         res = wi::max_value (w0.get_precision (), sign);
       else
         res = wi::min_value (w0.get_precision (), sign);
       return false;
     }
   return overflow;
}

value_range_base
operator_mult::wi_fold (tree type,
                        const wide_int &lh_lb, const wide_int &lh_ub,
                        const wide_int &rh_lb, const wide_int &rh_ub) const
{
  if (TYPE_OVERFLOW_UNDEFINED (type))
    return wi_cross_product (type, lh_lb, lh_ub, rh_lb, rh_ub);

  // Multiply the ranges when overflow wraps.  This is basically fancy
  // code so we don't drop to varying with an unsigned
  // [-3,-1]*[-3,-1].
  //
  // This test requires 2*prec bits if both operands are signed and
  // 2*prec + 2 bits if either is not.  Therefore, extend the values
  // using the sign of the result to PREC2.  From here on out,
  // everthing is just signed math no matter what the input types
  // were.

  signop sign = TYPE_SIGN (type);
  unsigned prec = TYPE_PRECISION (type);
  widest2_int min0 = widest2_int::from (lh_lb, sign);
  widest2_int max0 = widest2_int::from (lh_ub, sign);
  widest2_int min1 = widest2_int::from (rh_lb, sign);
  widest2_int max1 = widest2_int::from (rh_ub, sign);
  widest2_int sizem1 = wi::mask <widest2_int> (prec, false);
  widest2_int size = sizem1 + 1;

  // Canonicalize the intervals.
  if (sign == UNSIGNED)
    {
      if (wi::ltu_p (size, min0 + max0))
        {
          min0 -= size;
          max0 -= size;
        }
      if (wi::ltu_p (size, min1 + max1))
        {
          min1 -= size;
          max1 -= size;
        }
    }

  // Sort the 4 products so that min is in prod0 and max is in
  // prod3.
  widest2_int prod0 = min0 * min1;
  widest2_int prod1 = min0 * max1;
  widest2_int prod2 = max0 * min1;
  widest2_int prod3 = max0 * max1;

  // min0min1 > max0max1
  if (prod0 > prod3)
    std::swap (prod0, prod3);

  // min0max1 > max0min1
  if (prod1 > prod2)
    std::swap (prod1, prod2);

  if (prod0 > prod1)
    std::swap (prod0, prod1);

  if (prod2 > prod3)
    std::swap (prod2, prod3);

  // diff = max - min
  prod2 = prod3 - prod0;
  if (wi::geu_p (prod2, sizem1))
    // The range covers all values.
    return value_range_base (type);

  wide_int new_lb = wide_int::from (prod0, prec, sign);
  wide_int new_ub = wide_int::from (prod3, prec, sign);
  return create_possibly_reversed_range (type, new_lb, new_ub);
}


class operator_div : public cross_product_operator
{
public:
  operator_div (enum tree_code c)  { code = c; }
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
  virtual bool wi_op_overflows (wide_int &res,
                                tree type,
                                const wide_int &,
                                const wide_int &) const;
private:
  enum tree_code code;
};

bool
operator_div::wi_op_overflows (wide_int &res,
                               tree type,
                               const wide_int &w0,
                               const wide_int &w1) const
{
  if (w1 == 0)
    return true;

  wi::overflow_type overflow = wi::OVF_NONE;
  signop sign = TYPE_SIGN (type);

  switch (code)
    {
    case EXACT_DIV_EXPR:
      // EXACT_DIV_EXPR is implemented as TRUNC_DIV_EXPR in
      // operator_exact_divide.  No need to handle it here.
      gcc_unreachable ();
      break;
    case TRUNC_DIV_EXPR:
      res = wi::div_trunc (w0, w1, sign, &overflow);
      break;
    case FLOOR_DIV_EXPR:
      res = wi::div_floor (w0, w1, sign, &overflow);
      break;
    case ROUND_DIV_EXPR:
      res = wi::div_round (w0, w1, sign, &overflow);
      break;
    case CEIL_DIV_EXPR:
      res = wi::div_ceil (w0, w1, sign, &overflow);
      break;
    default:
      gcc_unreachable ();
    }

  if (overflow && TYPE_OVERFLOW_UNDEFINED (type))
    {
      // For division, the only case is -INF / -1 = +INF.
      res = wi::max_value (w0.get_precision (), sign);
      return false;
    }
  return overflow;
}

value_range_base
operator_div::wi_fold (tree type,
                       const wide_int &lh_lb, const wide_int &lh_ub,
                       const wide_int &rh_lb, const wide_int &rh_ub) const
{
  // If we know we will divide by zero, return undefined.
  if (rh_lb == 0 && rh_ub == 0)
    return value_range_base ();

  const wide_int dividend_min = lh_lb;
  const wide_int dividend_max = lh_ub;
  const wide_int divisor_min = rh_lb;
  const wide_int divisor_max = rh_ub;
  signop sign = TYPE_SIGN (type);
  unsigned prec = TYPE_PRECISION (type);
  wide_int extra_min, extra_max;

  // If we know we won't divide by zero, just do the division.
  if (!wi_includes_zero_p (type, divisor_min, divisor_max))
    return wi_cross_product (type, dividend_min, dividend_max,
                             divisor_min, divisor_max);

  // If flag_non_call_exceptions, we must not eliminate a division by zero.
  if (cfun->can_throw_non_call_exceptions)
    return value_range_base (type);

  // If we're definitely dividing by zero, there's nothing to do.
  if (wi_zero_p (type, divisor_min, divisor_max))
    return value_range_base ();

  // Perform the division in 2 parts, [LB, -1] and [1, UB], which will
  // skip any division by zero.

  // First divide by the negative numbers, if any.
  value_range_base r;
  if (wi::neg_p (divisor_min, sign))
    r = wi_cross_product (type, dividend_min, dividend_max,
                          divisor_min, wi::minus_one (prec));
  // Then divide by the non-zero positive numbers, if any.
  if (wi::gt_p (divisor_max, wi::zero (prec), sign))
    {
      value_range_base tmp;
      tmp = wi_cross_product (type, dividend_min, dividend_max,
                              wi::one (prec), divisor_max);
      r.union_ (tmp);
    }
  return r;
}

operator_div op_trunc_div (TRUNC_DIV_EXPR);
operator_div op_floor_div(FLOOR_DIV_EXPR);
operator_div op_round_div (ROUND_DIV_EXPR);
operator_div op_ceil_div (CEIL_DIV_EXPR);


class operator_exact_divide : public operator_div
{
public:
  operator_exact_divide () : operator_div (TRUNC_DIV_EXPR) { }
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;

} op_exact_div;

bool
operator_exact_divide::op1_range (value_range_base &r, tree type,
                                  const value_range_base &lhs,
                                  const value_range_base &op2) const
{
  tree offset;
  // [2, 4] = op1 / [3,3]   since its exact divide, no need to worry about
  // remainders in the endpoints, so op1 = [2,4] * [3,3] = [6,12].
  // We wont bother trying to enumerate all the in between stuff :-P
  // TRUE accuraacy is [6,6][9,9][12,12].  This is unlikely to matter most of
  // the time however.
  // If op2 is a multiple of 2, we would be able to set some non-zero bits.
  if (op2.singleton_p (&offset)
      && !integer_zerop (offset))
    {
      r = range_op_handler (MULT_EXPR, type)->fold_range (type, lhs, op2);
      return true;
    }
  return false;
}


class operator_lshift : public cross_product_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;

  virtual value_range_base wi_fold (tree type,
                          const wide_int &lh_lb, const wide_int &lh_ub,
                          const wide_int &rh_lb, const wide_int &rh_ub) const;
  virtual bool wi_op_overflows (wide_int &res,
                                tree type,
                                const wide_int &,
                                const wide_int &) const;
} op_lshift;

value_range_base
operator_lshift::fold_range (tree type,
                             const value_range_base &op1,
                             const value_range_base &op2) const
{
  value_range_base r;
  if (undefined_shift_range_check (r, type, op2))
    return r;

  // Transform left shifts by constants into multiplies.
  if (op2.singleton_p ())
    {
      unsigned shift = op2.lower_bound ().to_uhwi ();
      wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
      value_range_base mult (type, tmp, tmp);

      // Force wrapping multiplication.
      bool saved_flag_wrapv = flag_wrapv;
      bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
      flag_wrapv = 1;
      flag_wrapv_pointer = 1;
      r = range_op_handler (MULT_EXPR, type)->fold_range (type, op1, mult);
      flag_wrapv = saved_flag_wrapv;
      flag_wrapv_pointer = saved_flag_wrapv_pointer;
      return r;
    }

  // Otherwise, invoke the generic fold routine.
  return range_operator::fold_range (type, op1, op2);
}

value_range_base
operator_lshift::wi_fold (tree type,
                          const wide_int &lh_lb, const wide_int &lh_ub,
                          const wide_int &rh_lb, const wide_int &rh_ub) const
{
  signop sign = TYPE_SIGN (type);
  unsigned prec = TYPE_PRECISION (type);
  int overflow_pos = sign == SIGNED ? prec - 1 : prec;
  int bound_shift = overflow_pos - rh_ub.to_shwi ();
  // If bound_shift == HOST_BITS_PER_WIDE_INT, the llshift can
  // overflow.  However, for that to happen, rh.max needs to be zero,
  // which means rh is a singleton range of zero, which means it
  // should be handled by the lshift fold_range above.
  wide_int bound = wi::set_bit_in_zero (bound_shift, prec);
  wide_int complement = ~(bound - 1);
  wide_int low_bound, high_bound;
  bool in_bounds = false;

  if (sign == UNSIGNED)
    {
      low_bound = bound;
      high_bound = complement;
      if (wi::ltu_p (lh_ub, low_bound))
        {
          // [5, 6] << [1, 2] == [10, 24].
          // We're shifting out only zeroes, the value increases
          // monotonically.
          in_bounds = true;
        }
      else if (wi::ltu_p (high_bound, lh_lb))
        {
          // [0xffffff00, 0xffffffff] << [1, 2]
          // == [0xfffffc00, 0xfffffffe].
          // We're shifting out only ones, the value decreases
          // monotonically.
          in_bounds = true;
        }
    }
  else
    {
      // [-1, 1] << [1, 2] == [-4, 4]
      low_bound = complement;
      high_bound = bound;
      if (wi::lts_p (lh_ub, high_bound)
          && wi::lts_p (low_bound, lh_lb))
        {
          // For non-negative numbers, we're shifting out only zeroes,
          // the value increases monotonically.  For negative numbers,
          // we're shifting out only ones, the value decreases
          // monotonically.
          in_bounds = true;
        }
    }

  if (in_bounds)
    return wi_cross_product (type, lh_lb, lh_ub, rh_lb, rh_ub);

  return value_range_base (type);
}

bool
operator_lshift::wi_op_overflows (wide_int &res,
                                  tree type,
                                  const wide_int &w0,
                                  const wide_int &w1) const
{
  signop sign = TYPE_SIGN (type);
  if (wi::neg_p (w1))
    {
      // It's unclear from the C standard whether shifts can overflow.
      // The following code ignores overflow; perhaps a C standard
      // interpretation ruling is needed.
      res = wi::rshift (w0, -w1, sign);
    }
  else
    res = wi::lshift (w0, w1);
  return false;
}


class operator_rshift : public cross_product_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual value_range_base wi_fold (tree type,
                          const wide_int &lh_lb, const wide_int &lh_ub,
                          const wide_int &rh_lb, const wide_int &rh_ub) const;
  virtual bool wi_op_overflows (wide_int &res,
                                tree type,
                                const wide_int &w0,
                                const wide_int &w1) const;
} op_rshift;

bool
operator_rshift::wi_op_overflows (wide_int &res,
                                  tree type,
                                  const wide_int &w0,
                                  const wide_int &w1) const
{
  signop sign = TYPE_SIGN (type);
  if (wi::neg_p (w1))
    res = wi::lshift (w0, -w1);
  else
    {
      // It's unclear from the C standard whether shifts can overflow.
      // The following code ignores overflow; perhaps a C standard
      // interpretation ruling is needed.
      res = wi::rshift (w0, w1, sign);
    }
  return false;
}

value_range_base
operator_rshift::fold_range (tree type,
                             const value_range_base &op1,
                             const value_range_base &op2) const
{
  value_range_base r;
  if (undefined_shift_range_check (r, type, op2))
    return r;

  // Otherwise, invoke the generic fold routine.
  return range_operator::fold_range (type, op1, op2);
}

value_range_base
operator_rshift::wi_fold (tree type,
                          const wide_int &lh_lb, const wide_int &lh_ub,
                          const wide_int &rh_lb, const wide_int &rh_ub) const
{
  return wi_cross_product (type, lh_lb, lh_ub, rh_lb, rh_ub);
}


class operator_cast: public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;

} op_convert;

value_range_base
operator_cast::fold_range (tree type ATTRIBUTE_UNUSED,
                           const value_range_base &lh,
                           const value_range_base &rh) const
{
  value_range_base r;
  if (empty_range_check (r, lh, rh))
    return r;

  tree inner = lh.type ();
  tree outer = rh.type ();
  gcc_checking_assert (rh.varying_p ());
  gcc_checking_assert (types_compatible_p (outer, type));
  signop inner_sign = TYPE_SIGN (inner);
  signop outer_sign = TYPE_SIGN (outer);
  unsigned inner_prec = TYPE_PRECISION (inner);
  unsigned outer_prec = TYPE_PRECISION (outer);

  for (unsigned x = 0; x < lh.num_pairs (); ++x)
    {
      wide_int lh_lb = lh.lower_bound (x);
      wide_int lh_ub = lh.upper_bound (x);

      // If the conversion is not truncating we can convert the min
      // and max values and canonicalize the resulting range.
      // Otherwise, we can do the conversion if the size of the range
      // is less than what the precision of the target type can
      // represent.
      if (outer_prec >= inner_prec
          || wi::rshift (wi::sub (lh_ub, lh_lb),
                         wi::uhwi (outer_prec, inner_prec),
                         inner_sign) == 0)
        {
          wide_int min = wide_int::from (lh_lb, outer_prec, inner_sign);
          wide_int max = wide_int::from (lh_ub, outer_prec, inner_sign);
          if (!wi::eq_p (min, wi::min_value (outer_prec, outer_sign))
              || !wi::eq_p (max, wi::max_value (outer_prec, outer_sign)))
            {
              value_range_base tmp;
              tmp = create_possibly_reversed_range (type, min, max);
              r.union_ (tmp);
              continue;
            }
        }
      return value_range_base (type);
    }
  return r;
}

bool
operator_cast::op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const
{
  tree lhs_type = lhs.type ();
  gcc_checking_assert (types_compatible_p (op2.type(), type));

  // If the precision of the LHS is smaller than the precision of the
  // RHS, then there would be truncation of the value on the RHS, and
  // so we can tell nothing about it.
  if (TYPE_PRECISION (lhs_type) < TYPE_PRECISION (type))
    {
      // If we've been passed an actual value for the RHS rather than
      // the type, see if it fits the LHS, and if so, then we can allow
      // it.
      r = op2;
      r = fold_range (lhs_type, r, value_range_base (lhs_type));
      r = fold_range (type, r, value_range_base (type));
      if (r == op2)
        {
          // We know the value of the RHS fits in the LHS type, so
          // convert the LHS and remove any values that arent in OP2.
          r = lhs;
          r = fold_range (type, r, value_range_base (type));
          r.intersect (op2);
          return true;
        }
      // Special case if the LHS is a boolean.  A 0 means the RHS is
      // zero, and a 1 means the RHS is non-zero.
      if (TREE_CODE (lhs_type) == BOOLEAN_TYPE)
        {
          // If the LHS is unknown, the result is whatever op2 already is.
          if (!lhs.singleton_p ())
            {
              r = op2;
              return true;
            }
          // Boolean casts are weird in GCC. It's actually an implied
          // mask with 0x01, so all that is known is whether the
          // rightmost bit is 0 or 1, which implies the only value
          // *not* in the RHS is 0 or -1.
          unsigned prec = TYPE_PRECISION (type);
          if (lhs.zero_p ())
            r = value_range_base (VR_ANTI_RANGE, type,
                        wi::minus_one (prec), wi::minus_one (prec));
          else
            r = value_range_base (VR_ANTI_RANGE, type,
                        wi::zero (prec), wi::zero (prec));
          // And intersect it with what we know about op2.
          r.intersect (op2);
        }
      else
        // Otherwise we'll have to assume it's whatever we know about op2.
        r = op2;
      return true;
    }

  // If the LHS precision is greater than the rhs precision, the LHS
  // range is restricted to the range of the RHS by this
  // assignment.
  if (TYPE_PRECISION (lhs_type) > TYPE_PRECISION (type))
    {
      // Cast the range of the RHS to the type of the LHS.
      value_range_base op_type (type);
      op_type = fold_range (lhs_type, op_type, value_range_base (lhs_type));

      // Intersect this with the LHS range will produce the RHS range.
      r = range_intersect (lhs, op_type);
    }
  else
    r = lhs;

  // Cast the calculated range to the type of the RHS.
  r = fold_range (type, r, value_range_base (type));
  return true;
}


class operator_logical_and : public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &lh,
                                       const value_range_base &rh) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
} op_logical_and;


value_range_base
operator_logical_and::fold_range (tree type,
                                  const value_range_base &lh,
                                  const value_range_base &rh) const
{
  value_range_base r;
  if (empty_range_check (r, lh, rh))
    return r;

  // 0 && anything is 0.
  if ((wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (lh.upper_bound (), 0))
      || (wi::eq_p (lh.lower_bound (), 0) && wi::eq_p (rh.upper_bound (), 0)))
    return range_false (type);

  // To reach this point, there must be a logical 1 on each side, and
  // the only remaining question is whether there is a zero or not.
  if (lh.contains_p (build_zero_cst (lh.type ()))
      || rh.contains_p (build_zero_cst (rh.type ())))
    return range_true_and_false (type);

  return range_true (type);
}

bool
operator_logical_and::op1_range (value_range_base &r, tree type,
                                 const value_range_base &lhs,
                                 const value_range_base &op2 ATTRIBUTE_UNUSED) const
{
   switch (get_bool_state (r, lhs, type))
     {
     case BRS_TRUE:
       // A true result means both sides of the AND must be true.
       r = range_true (type);
       break;
     default:
       // Any other result means only one side has to be false, the
       // other side can be anything. So we cannott be sure of any
       // result here.
       r = range_true_and_false (type);
       break;
     }
  return true;
}

bool
operator_logical_and::op2_range (value_range_base &r, tree type,
                                 const value_range_base &lhs,
                                 const value_range_base &op1) const
{
  return operator_logical_and::op1_range (r, type, lhs, op1);
}


class operator_bitwise_and : public range_operator
{
public:
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
} op_bitwise_and;

// Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
// possible.  Basically, see if we can optimize:
//
//      [LB, UB] op Z
//   into:
//      [LB op Z, UB op Z]
//
// If the optimization was successful, accumulate the range in R and
// return TRUE.

static bool
wi_optimize_and_or (value_range_base &r,
                    enum tree_code code,
                    tree type,
                    const wide_int &lh_lb, const wide_int &lh_ub,
                    const wide_int &rh_lb, const wide_int &rh_ub)
{
  // Calculate the singleton mask among the ranges, if any.
  wide_int lower_bound, upper_bound, mask;
  if (wi::eq_p (rh_lb, rh_ub))
    {
      mask = rh_lb;
      lower_bound = lh_lb;
      upper_bound = lh_ub;
    }
  else if (wi::eq_p (lh_lb, lh_ub))
    {
      mask = lh_lb;
      lower_bound = rh_lb;
      upper_bound = rh_ub;
    }
  else
    return false;

  // If Z is a constant which (for op | its bitwise not) has n
  // consecutive least significant bits cleared followed by m 1
  // consecutive bits set immediately above it and either
  // m + n == precision, or (x >> (m + n)) == (y >> (m + n)).
  //
  // The least significant n bits of all the values in the range are
  // cleared or set, the m bits above it are preserved and any bits
  // above these are required to be the same for all values in the
  // range.
  wide_int w = mask;
  int m = 0, n = 0;
  if (code == BIT_IOR_EXPR)
    w = ~w;
  if (wi::eq_p (w, 0))
    n = w.get_precision ();
  else
    {
      n = wi::ctz (w);
      w = ~(w | wi::mask (n, false, w.get_precision ()));
      if (wi::eq_p (w, 0))
        m = w.get_precision () - n;
      else
        m = wi::ctz (w) - n;
    }
  wide_int new_mask = wi::mask (m + n, true, w.get_precision ());
  if ((new_mask & lower_bound) != (new_mask & upper_bound))
    return false;

  wide_int res_lb, res_ub;
  if (code == BIT_AND_EXPR)
    {
      res_lb = wi::bit_and (lower_bound, mask);
      res_ub = wi::bit_and (upper_bound, mask);
    }
  else if (code == BIT_IOR_EXPR)
    {
      res_lb = wi::bit_or (lower_bound, mask);
      res_ub = wi::bit_or (upper_bound, mask);
    }
  else
    gcc_unreachable ();
  r = value_range_with_overflow (type, res_lb, res_ub);
  return true;
}

// For range [LB, UB] compute two wide_int bit masks.
//
// In the MAYBE_NONZERO bit mask, if some bit is unset, it means that
// for all numbers in the range the bit is 0, otherwise it might be 0
// or 1.
//
// In the MUSTBE_NONZERO bit mask, if some bit is set, it means that
// for all numbers in the range the bit is 1, otherwise it might be 0
// or 1.

static void
wi_set_zero_nonzero_bits (tree type,
                          const wide_int &lb, const wide_int &ub,
                          wide_int &maybe_nonzero,
                          wide_int &mustbe_nonzero)
{
  signop sign = TYPE_SIGN (type);

  if (wi::eq_p (lb, ub))
    maybe_nonzero = mustbe_nonzero = lb;
  else if (wi::ge_p (lb, 0, sign) || wi::lt_p (ub, 0, sign))
    {
      wide_int xor_mask = lb ^ ub;
      maybe_nonzero = lb | ub;
      mustbe_nonzero = lb & ub;
      if (xor_mask != 0)
        {
          wide_int mask = wi::mask (wi::floor_log2 (xor_mask), false,
                                    maybe_nonzero.get_precision ());
          maybe_nonzero = maybe_nonzero | mask;
          mustbe_nonzero = wi::bit_and_not (mustbe_nonzero, mask);
        }
    }
  else
    {
      maybe_nonzero = wi::minus_one (lb.get_precision ());
      mustbe_nonzero = wi::zero (lb.get_precision ());
    }
}

value_range_base
operator_bitwise_and::wi_fold (tree type,
                               const wide_int &lh_lb,
                               const wide_int &lh_ub,
                               const wide_int &rh_lb,
                               const wide_int &rh_ub) const
{
  value_range_base r;
  if (wi_optimize_and_or (r, BIT_AND_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
    return r;

  wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
  wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
  wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
                            maybe_nonzero_lh, mustbe_nonzero_lh);
  wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
                            maybe_nonzero_rh, mustbe_nonzero_rh);

  wide_int new_lb = mustbe_nonzero_lh & mustbe_nonzero_rh;
  wide_int new_ub = maybe_nonzero_lh & maybe_nonzero_rh;
  signop sign = TYPE_SIGN (type);
  unsigned prec = TYPE_PRECISION (type);
  // If both input ranges contain only negative values, we can
  // truncate the result range maximum to the minimum of the
  // input range maxima.
  if (wi::lt_p (lh_ub, 0, sign) && wi::lt_p (rh_ub, 0, sign))
    {
      new_ub = wi::min (new_ub, lh_ub, sign);
      new_ub = wi::min (new_ub, rh_ub, sign);
    }
  // If either input range contains only non-negative values
  // we can truncate the result range maximum to the respective
  // maximum of the input range.
  if (wi::ge_p (lh_lb, 0, sign))
    new_ub = wi::min (new_ub, lh_ub, sign);
  if (wi::ge_p (rh_lb, 0, sign))
    new_ub = wi::min (new_ub, rh_ub, sign);
  // PR68217: In case of signed & sign-bit-CST should
  // result in [-INF, 0] instead of [-INF, INF].
  if (wi::gt_p (new_lb, new_ub, sign))
    {
      wide_int sign_bit = wi::set_bit_in_zero (prec - 1, prec);
      if (sign == SIGNED
          && ((wi::eq_p (lh_lb, lh_ub)
               && !wi::cmps (lh_lb, sign_bit))
              || (wi::eq_p (rh_lb, rh_ub)
                  && !wi::cmps (rh_lb, sign_bit))))
        {
          new_lb = wi::min_value (prec, sign);
          new_ub = wi::zero (prec);
        }
    }
  // If the limits got swapped around, return varying.
  if (wi::gt_p (new_lb, new_ub,sign))
    return value_range_base (type);

  return value_range_with_overflow (type, new_lb, new_ub);
}

bool
operator_bitwise_and::op1_range (value_range_base &r, tree type,
                                 const value_range_base &lhs,
                                 const value_range_base &op2) const
{
  // If this is really a logical wi_fold, call that.
  if (types_compatible_p (type, boolean_type_node))
    return op_logical_and.op1_range (r, type, lhs, op2);

  // For now do nothing with bitwise AND of value_range's.
  r.set_varying (type);
  return true;
}

bool
operator_bitwise_and::op2_range (value_range_base &r, tree type,
                                 const value_range_base &lhs,
                                 const value_range_base &op1) const
{
  return operator_bitwise_and::op1_range (r, type, lhs, op1);
}


class operator_logical_or : public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &lh,
                                       const value_range_base &rh) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
} op_logical_or;

value_range_base
operator_logical_or::fold_range (tree type ATTRIBUTE_UNUSED,
                                 const value_range_base &lh,
                                 const value_range_base &rh) const
{
  value_range_base r;
  if (empty_range_check (r, lh, rh))
    return r;

  return range_union (lh, rh);
}

bool
operator_logical_or::op1_range (value_range_base &r, tree type,
                                const value_range_base &lhs,
                                const value_range_base &op2 ATTRIBUTE_UNUSED) const
{
   switch (get_bool_state (r, lhs, type))
     {
     case BRS_FALSE:
       // A false result means both sides of the OR must be false.
       r = range_false (type);
       break;
     default:
       // Any other result means only one side has to be true, the
       // other side can be anything. so we can't be sure of any result
       // here.
       r = range_true_and_false (type);
       break;
    }
  return true;
}

bool
operator_logical_or::op2_range (value_range_base &r, tree type,
                                const value_range_base &lhs,
                                const value_range_base &op1) const
{
  return operator_logical_or::op1_range (r, type, lhs, op1);
}


class operator_bitwise_or : public range_operator
{
public:
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
  virtual bool op2_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op1) const;
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
} op_bitwise_or;

value_range_base
operator_bitwise_or::wi_fold (tree type,
                              const wide_int &lh_lb,
                              const wide_int &lh_ub,
                              const wide_int &rh_lb,
                              const wide_int &rh_ub) const
{
  value_range_base r;
  if (wi_optimize_and_or (r, BIT_IOR_EXPR, type, lh_lb, lh_ub, rh_lb, rh_ub))
    return r;

  wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
  wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
  wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
                            maybe_nonzero_lh, mustbe_nonzero_lh);
  wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
                            maybe_nonzero_rh, mustbe_nonzero_rh);
  wide_int new_lb = mustbe_nonzero_lh | mustbe_nonzero_rh;
  wide_int new_ub = maybe_nonzero_lh | maybe_nonzero_rh;
  signop sign = TYPE_SIGN (type);
  // If the input ranges contain only positive values we can
  // truncate the minimum of the result range to the maximum
  // of the input range minima.
  if (wi::ge_p (lh_lb, 0, sign)
      && wi::ge_p (rh_lb, 0, sign))
    {
      new_lb = wi::max (new_lb, lh_lb, sign);
      new_lb = wi::max (new_lb, rh_lb, sign);
    }
  // If either input range contains only negative values
  // we can truncate the minimum of the result range to the
  // respective minimum range.
  if (wi::lt_p (lh_ub, 0, sign))
    new_lb = wi::max (new_lb, lh_lb, sign);
  if (wi::lt_p (rh_ub, 0, sign))
    new_lb = wi::max (new_lb, rh_lb, sign);
  // If the limits got swapped around, return varying.
  if (wi::gt_p (new_lb, new_ub,sign))
    return value_range_base (type);

  return value_range_with_overflow (type, new_lb, new_ub);
}

bool
operator_bitwise_or::op1_range (value_range_base &r, tree type,
                                const value_range_base &lhs,
                                const value_range_base &op2) const
{
  // If this is really a logical wi_fold, call that.
  if (types_compatible_p (type, boolean_type_node))
    return op_logical_or.op1_range (r, type, lhs, op2);

  // For now do nothing with bitwise OR of value_range's.
  r.set_varying (type);
  return true;
}

bool
operator_bitwise_or::op2_range (value_range_base &r, tree type,
                                const value_range_base &lhs,
                                const value_range_base &op1) const
{
  return operator_bitwise_or::op1_range (r, type, lhs, op1);
}


class operator_bitwise_xor : public range_operator
{
public:
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
} op_bitwise_xor;

value_range_base
operator_bitwise_xor::wi_fold (tree type,
                               const wide_int &lh_lb,
                               const wide_int &lh_ub,
                               const wide_int &rh_lb,
                               const wide_int &rh_ub) const
{
  signop sign = TYPE_SIGN (type);
  wide_int maybe_nonzero_lh, mustbe_nonzero_lh;
  wide_int maybe_nonzero_rh, mustbe_nonzero_rh;
  wi_set_zero_nonzero_bits (type, lh_lb, lh_ub,
                            maybe_nonzero_lh, mustbe_nonzero_lh);
  wi_set_zero_nonzero_bits (type, rh_lb, rh_ub,
                            maybe_nonzero_rh, mustbe_nonzero_rh);

  wide_int result_zero_bits = ((mustbe_nonzero_lh & mustbe_nonzero_rh)
                               | ~(maybe_nonzero_lh | maybe_nonzero_rh));
  wide_int result_one_bits
    = (wi::bit_and_not (mustbe_nonzero_lh, maybe_nonzero_rh)
       | wi::bit_and_not (mustbe_nonzero_rh, maybe_nonzero_lh));
  wide_int new_ub = ~result_zero_bits;
  wide_int new_lb = result_one_bits;

  // If the range has all positive or all negative values, the result
  // is better than VARYING.
  if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
    return value_range_with_overflow (type, new_lb, new_ub);

  return value_range_base (type);
}


class operator_trunc_mod : public range_operator
{
public:
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
} op_trunc_mod;

value_range_base
operator_trunc_mod::wi_fold (tree type,
                             const wide_int &lh_lb,
                             const wide_int &lh_ub,
                             const wide_int &rh_lb,
                             const wide_int &rh_ub) const
{
  wide_int new_lb, new_ub, tmp;
  signop sign = TYPE_SIGN (type);
  unsigned prec = TYPE_PRECISION (type);

  // Mod 0 is undefined.  Return undefined.
  if (wi_zero_p (type, rh_lb, rh_ub))
    return value_range_base ();

  // ABS (A % B) < ABS (B) and either 0 <= A % B <= A or A <= A % B <= 0.
  new_ub = rh_ub - 1;
  if (sign == SIGNED)
    {
      tmp = -1 - rh_lb;
      new_ub = wi::smax (new_ub, tmp);
    }

  if (sign == UNSIGNED)
    new_lb = wi::zero (prec);
  else
    {
      new_lb = -new_ub;
      tmp = lh_lb;
      if (wi::gts_p (tmp, 0))
        tmp = wi::zero (prec);
      new_lb = wi::smax (new_lb, tmp);
    }
  tmp = lh_ub;
  if (sign == SIGNED && wi::neg_p (tmp))
    tmp = wi::zero (prec);
  new_ub = wi::min (new_ub, tmp, sign);

  return value_range_with_overflow (type, new_lb, new_ub);
}


class operator_logical_not : public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &lh,
                                       const value_range_base &rh) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
} op_logical_not;

// Folding a logical NOT, oddly enough, involves doing nothing on the
// forward pass through.  During the initial walk backwards, the
// logical NOT reversed the desired outcome on the way back, so on the
// way forward all we do is pass the range forward.
//
//      b_2 = x_1 < 20
//      b_3 = !b_2
//      if (b_3)
//  to determine the TRUE branch, walking  backward
//       if (b_3)               if ([1,1])
//       b_3 = !b_2             [1,1] = ![0,0]
//       b_2 = x_1 < 20         [0,0] = x_1 < 20,   false, so x_1 == [20, 255]
//   which is the result we are looking for.. so.. pass it through.

value_range_base
operator_logical_not::fold_range (tree type,
                                  const value_range_base &lh,
                                  const value_range_base &rh ATTRIBUTE_UNUSED) const
{
  value_range_base r;
  if (empty_range_check (r, lh, rh))
    return r;

  if (lh.varying_p () || lh.undefined_p ())
    r = lh;
  else
    r = range_invert (lh);
  gcc_checking_assert (lh.type() == type);
  return r;
}

bool
operator_logical_not::op1_range (value_range_base &r,
                                 tree type ATTRIBUTE_UNUSED,
                                 const value_range_base &lhs,
                                 const value_range_base &op2 ATTRIBUTE_UNUSED) const
{
  if (lhs.varying_p () || lhs.undefined_p ())
    r = lhs;
  else
    r = range_invert (lhs);
  return true;
}


class operator_bitwise_not : public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &lh,
                                       const value_range_base &rh) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
} op_bitwise_not;

value_range_base
operator_bitwise_not::fold_range (tree type,
                                  const value_range_base &lh,
                                  const value_range_base &rh) const
{
  value_range_base r;
  if (empty_range_check (r, lh, rh))
    return r;

  // ~X is simply -1 - X.
  value_range_base minusone (type,
                   wi::minus_one (TYPE_PRECISION (type)),
                   wi::minus_one (TYPE_PRECISION (type)));
  r = range_op_handler (MINUS_EXPR, type)->fold_range (type, minusone, lh);
  return r;
}

bool
operator_bitwise_not::op1_range (value_range_base &r, tree type,
                                 const value_range_base &lhs,
                                 const value_range_base &op2) const
{
  // ~X is -1 - X and since bitwise NOT is involutary...do it again.
  r = fold_range (type, lhs, op2);
  return true;
}


class operator_cst : public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
} op_integer_cst;

value_range_base
operator_cst::fold_range (tree type ATTRIBUTE_UNUSED,
                          const value_range_base &lh,
                          const value_range_base &rh ATTRIBUTE_UNUSED) const
{
  return lh;
}


class operator_identity : public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
} op_identity;

value_range_base
operator_identity::fold_range (tree type ATTRIBUTE_UNUSED,
                               const value_range_base &lh,
                               const value_range_base &rh ATTRIBUTE_UNUSED) const
{
  return lh;
}

bool
operator_identity::op1_range (value_range_base &r, tree type ATTRIBUTE_UNUSED,
                              const value_range_base &lhs,
                              const value_range_base &op2 ATTRIBUTE_UNUSED) const
{
  r = lhs;
  return true;
}


class operator_abs : public range_operator
{
 public:
  virtual value_range_base wi_fold (tree type,
                                    const wide_int &lh_lb,
                                    const wide_int &lh_ub,
                                    const wide_int &rh_lb,
                                    const wide_int &rh_ub) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
} op_abs;

value_range_base
operator_abs::wi_fold (tree type,
                       const wide_int &lh_lb, const wide_int &lh_ub,
                       const wide_int &rh_lb ATTRIBUTE_UNUSED,
                       const wide_int &rh_ub ATTRIBUTE_UNUSED) const
{
  wide_int min, max;
  signop sign = TYPE_SIGN (type);
  unsigned prec = TYPE_PRECISION (type);

  // Pass through LH for the easy cases.
  if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
    return value_range_base (type, lh_lb, lh_ub);

  // -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get
  // a useful range.
  wide_int min_value = wi::min_value (prec, sign);
  wide_int max_value = wi::max_value (prec, sign);
  if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
    return value_range_base (type);

  // ABS_EXPR may flip the range around, if the original range
  // included negative values.
  if (wi::eq_p (lh_lb, min_value))
    min = max_value;
  else
    min = wi::abs (lh_lb);
  if (wi::eq_p (lh_ub, min_value))
    max = max_value;
  else
    max = wi::abs (lh_ub);

  // If the range contains zero then we know that the minimum value in the
  // range will be zero.
  if (wi::le_p (lh_lb, 0, sign) && wi::ge_p (lh_ub, 0, sign))
    {
      if (wi::gt_p (min, max, sign))
        max = min;
      min = wi::zero (prec);
    }
  else
    {
      // If the range was reversed, swap MIN and MAX.
      if (wi::gt_p (min, max, sign))
        std::swap (min, max);
    }

  // If the new range has its limits swapped around (MIN > MAX), then
  // the operation caused one of them to wrap around.  The only thing
  // we know is that the result is positive.
  if (wi::gt_p (min, max, sign))
    {
      min = wi::zero (prec);
      max = max_value;
    }
  return value_range_base (type, min, max);
}

bool
operator_abs::op1_range (value_range_base &r, tree type,
                         const value_range_base &lhs,
                         const value_range_base &op2) const
{
  if (empty_range_check (r, lhs, op2))
    return true;
  if (TYPE_UNSIGNED (type))
    {
      r = lhs;
      return true;
    }
  // Start with the positives because negatives are an impossible result.
  value_range_base positives = range_positives (type);
  positives.intersect (lhs);
  r = positives;
  // Then add the negative of each pair:
  // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
  for (unsigned i = 0; i < positives.num_pairs (); ++i)
    r.union_ (value_range_base (type,
                      -positives.upper_bound (i),
                      -positives.lower_bound (i)));
  return true;
}


class operator_absu : public range_operator
{
 public:
  virtual value_range_base wi_fold (tree type,
                          const wide_int &lh_lb, const wide_int &lh_ub,
                          const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_absu;

value_range_base
operator_absu::wi_fold (tree type,
                        const wide_int &lh_lb, const wide_int &lh_ub,
                        const wide_int &rh_lb ATTRIBUTE_UNUSED,
                        const wide_int &rh_ub ATTRIBUTE_UNUSED) const
{
  wide_int new_lb, new_ub;

  // Pass through VR0 the easy cases.
  if (wi::ges_p (lh_lb, 0))
    {
      new_lb = lh_lb;
      new_ub = lh_ub;
    }
  else
    {
      new_lb = wi::abs (lh_lb);
      new_ub = wi::abs (lh_ub);

      // If the range contains zero then we know that the minimum
      // value in the range will be zero.
      if (wi::ges_p (lh_ub, 0))
        {
          if (wi::gtu_p (new_lb, new_ub))
            new_ub = new_lb;
          new_lb = wi::zero (TYPE_PRECISION (type));
        }
      else
        std::swap (new_lb, new_ub);
    }

  gcc_checking_assert (TYPE_UNSIGNED (type));
  return value_range_base (type, new_lb, new_ub);
}


class operator_negate : public range_operator
{
 public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
} op_negate;

value_range_base
operator_negate::fold_range (tree type,
                             const value_range_base &lh,
                             const value_range_base &rh) const
{
  value_range_base r;
  if (empty_range_check (r, lh, rh))
    return r;
  // -X is simply 0 - X.
  return
    range_op_handler (MINUS_EXPR, type)->fold_range (type,
                                                     range_zero (type), lh);
}

bool
operator_negate::op1_range (value_range_base &r, tree type,
                            const value_range_base &lhs,
                            const value_range_base &op2) const
{
  // NEGATE is involutory.
  r = fold_range (type, lhs, op2);
  return true;
}


class operator_addr_expr : public range_operator
{
public:
  virtual value_range_base fold_range (tree type,
                                       const value_range_base &op1,
                                       const value_range_base &op2) const;
  virtual bool op1_range (value_range_base &r, tree type,
                          const value_range_base &lhs,
                          const value_range_base &op2) const;
} op_addr;

value_range_base
operator_addr_expr::fold_range (tree type,
                                const value_range_base &lh,
                                const value_range_base &rh) const
{
  value_range_base r;
  if (empty_range_check (r, lh, rh))
    return r;

  // Return a non-null pointer of the LHS type (passed in op2).
  if (lh.zero_p ())
    return range_zero (type);
  if (!lh.contains_p (build_zero_cst (lh.type ())))
    return range_nonzero (type);
  return value_range_base (type);
}

bool
operator_addr_expr::op1_range (value_range_base &r, tree type,
                               const value_range_base &lhs,
                               const value_range_base &op2) const
{
  r = operator_addr_expr::fold_range (type, lhs, op2);
  return true;
}


class pointer_plus_operator : public range_operator
{
public:
  virtual value_range_base wi_fold (tree type,
                          const wide_int &lh_lb, const wide_int &lh_ub,
                          const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_pointer_plus;

value_range_base
pointer_plus_operator::wi_fold (tree type,
                                const wide_int &lh_lb,
                                const wide_int &lh_ub,
                                const wide_int &rh_lb,
                                const wide_int &rh_ub) const
{
  // For pointer types, we are really only interested in asserting
  // whether the expression evaluates to non-NULL.
  //
  // With -fno-delete-null-pointer-checks we need to be more
  // conservative.  As some object might reside at address 0,
  // then some offset could be added to it and the same offset
  // subtracted again and the result would be NULL.
  // E.g.
  // static int a[12]; where &a[0] is NULL and
  // ptr = &a[6];
  // ptr -= 6;
  // ptr will be NULL here, even when there is POINTER_PLUS_EXPR
  // where the first range doesn't include zero and the second one
  // doesn't either.  As the second operand is sizetype (unsigned),
  // consider all ranges where the MSB could be set as possible
  // subtractions where the result might be NULL.
  if ((!wi_includes_zero_p (type, lh_lb, lh_ub)
       || !wi_includes_zero_p (type, rh_lb, rh_ub))
      && !TYPE_OVERFLOW_WRAPS (type)
      && (flag_delete_null_pointer_checks
          || !wi::sign_mask (rh_ub)))
    return range_nonzero (type);
  if (lh_lb == lh_ub && lh_lb == 0
      && rh_lb == rh_ub && rh_lb == 0)
    return range_zero (type);
  return value_range_base (type);
}


class pointer_min_max_operator : public range_operator
{
public:
  virtual value_range_base wi_fold (tree type,
                          const wide_int &lh_lb, const wide_int &lh_ub,
                          const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_ptr_min_max;

value_range_base
pointer_min_max_operator::wi_fold (tree type,
                                   const wide_int &lh_lb,
                                   const wide_int &lh_ub,
                                   const wide_int &rh_lb,
                                   const wide_int &rh_ub) const
{
  // For MIN/MAX expressions with pointers, we only care about
  // nullness.  If both are non null, then the result is nonnull.
  // If both are null, then the result is null.  Otherwise they
  // are varying.
  if (!wi_includes_zero_p (type, lh_lb, lh_ub)
      && !wi_includes_zero_p (type, rh_lb, rh_ub))
    return range_nonzero (type);
  if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
    return range_zero (type);
  return value_range_base (type);
}


class pointer_and_operator : public range_operator
{
public:
  virtual value_range_base wi_fold (tree type,
                          const wide_int &lh_lb, const wide_int &lh_ub,
                          const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_pointer_and;

value_range_base
pointer_and_operator::wi_fold (tree type,
                               const wide_int &lh_lb,
                               const wide_int &lh_ub,
                               const wide_int &rh_lb ATTRIBUTE_UNUSED,
                               const wide_int &rh_ub ATTRIBUTE_UNUSED) const
{
  // For pointer types, we are really only interested in asserting
  // whether the expression evaluates to non-NULL.
  if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub))
    return range_zero (type);

  return value_range_base (type);
}


class pointer_or_operator : public range_operator
{
public:
  virtual value_range_base wi_fold (tree type,
                          const wide_int &lh_lb, const wide_int &lh_ub,
                          const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_pointer_or;

value_range_base
pointer_or_operator::wi_fold (tree type,
                              const wide_int &lh_lb,
                              const wide_int &lh_ub,
                              const wide_int &rh_lb,
                              const wide_int &rh_ub) const
{
  // For pointer types, we are really only interested in asserting
  // whether the expression evaluates to non-NULL.
  if (!wi_includes_zero_p (type, lh_lb, lh_ub)
      && !wi_includes_zero_p (type, rh_lb, rh_ub))
    return range_nonzero (type);
  if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
    return range_zero (type);
  return value_range_base (type);
}
\f
// This implements the range operator tables as local objects in this file.

class range_op_table
{
public:
  inline range_operator *operator[] (enum tree_code code);
protected:
  void set (enum tree_code code, range_operator &op);
private:
  range_operator *m_range_tree[MAX_TREE_CODES];
};

// Return a pointer to the range_operator instance, if there is one
// associated with tree_code CODE.

range_operator *
range_op_table::operator[] (enum tree_code code)
{
  gcc_checking_assert (code > 0 && code < MAX_TREE_CODES);
  return m_range_tree[code];
}

// Add OP to the handler table for CODE.

void
range_op_table::set (enum tree_code code, range_operator &op)
{
  gcc_checking_assert (m_range_tree[code] == NULL);
  m_range_tree[code] = &op;
}

// Instantiate a range op table for integral operations.

class integral_table : public range_op_table
{
public:
  integral_table ();
} integral_tree_table;

integral_table::integral_table ()
{
  set (EQ_EXPR, op_equal);
  set (NE_EXPR, op_not_equal);
  set (LT_EXPR, op_lt);
  set (LE_EXPR, op_le);
  set (GT_EXPR, op_gt);
  set (GE_EXPR, op_ge);
  set (PLUS_EXPR, op_plus);
  set (MINUS_EXPR, op_minus);
  set (MIN_EXPR, op_min);
  set (MAX_EXPR, op_max);
  set (MULT_EXPR, op_mult);
  set (TRUNC_DIV_EXPR, op_trunc_div);
  set (FLOOR_DIV_EXPR, op_floor_div);
  set (ROUND_DIV_EXPR, op_round_div);
  set (CEIL_DIV_EXPR, op_ceil_div);
  set (EXACT_DIV_EXPR, op_exact_div);
  set (LSHIFT_EXPR, op_lshift);
  set (RSHIFT_EXPR, op_rshift);
  set (NOP_EXPR, op_convert);
  set (CONVERT_EXPR, op_convert);
  set (TRUTH_AND_EXPR, op_logical_and);
  set (BIT_AND_EXPR, op_bitwise_and);
  set (TRUTH_OR_EXPR, op_logical_or);
  set (BIT_IOR_EXPR, op_bitwise_or);
  set (BIT_XOR_EXPR, op_bitwise_xor);
  set (TRUNC_MOD_EXPR, op_trunc_mod);
  set (TRUTH_NOT_EXPR, op_logical_not);
  set (BIT_NOT_EXPR, op_bitwise_not);
  set (INTEGER_CST, op_integer_cst);
  set (SSA_NAME, op_identity);
  set (PAREN_EXPR, op_identity);
  set (OBJ_TYPE_REF, op_identity);
  set (ABS_EXPR, op_abs);
  set (ABSU_EXPR, op_absu);
  set (NEGATE_EXPR, op_negate);
  set (ADDR_EXPR, op_addr);
}

// Instantiate a range op table for pointer operations.

class pointer_table : public range_op_table
{
public:
  pointer_table ();
} pointer_tree_table;

pointer_table::pointer_table ()
{
  set (BIT_AND_EXPR, op_pointer_and);
  set (BIT_IOR_EXPR, op_pointer_or);
  set (MIN_EXPR, op_ptr_min_max);
  set (MAX_EXPR, op_ptr_min_max);
  set (POINTER_PLUS_EXPR, op_pointer_plus);

  set (EQ_EXPR, op_equal);
  set (NE_EXPR, op_not_equal);
  set (LT_EXPR, op_lt);
  set (LE_EXPR, op_le);
  set (GT_EXPR, op_gt);
  set (GE_EXPR, op_ge);
  set (SSA_NAME, op_identity);
  set (ADDR_EXPR, op_addr);
  set (NOP_EXPR, op_convert);
  set (CONVERT_EXPR, op_convert);

  set (BIT_NOT_EXPR, op_bitwise_not);
  set (BIT_XOR_EXPR, op_bitwise_xor);
}

// The tables are hidden and accessed via a simple extern function.

range_operator *
range_op_handler (enum tree_code code, tree type)
{
  // First check if there is apointer specialization.
  if (POINTER_TYPE_P (type))
    return pointer_tree_table[code];
  return integral_tree_table[code];
}

// Cast the range in R to TYPE.

void
range_cast (value_range_base &r, tree type)
{
  range_operator *op = range_op_handler (CONVERT_EXPR, type);
  r = op->fold_range (type, r, value_range_base (type));
}

#if CHECKING_P
#include "selftest.h"
#include "stor-layout.h"

// Ideally this should go in namespace selftest, but range_tests
// needs to be a friend of class value_range_base so it can access
// value_range_base::m_max_pairs.

#define INT(N) build_int_cst (integer_type_node, (N))
#define UINT(N) build_int_cstu (unsigned_type_node, (N))
#define INT16(N) build_int_cst (short_integer_type_node, (N))
#define UINT16(N) build_int_cstu (short_unsigned_type_node, (N))
#define INT64(N) build_int_cstu (long_long_integer_type_node, (N))
#define UINT64(N) build_int_cstu (long_long_unsigned_type_node, (N))
#define UINT128(N) build_int_cstu (u128_type, (N))
#define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
#define SCHAR(N) build_int_cst (signed_char_type_node, (N))

#define RANGE3(A,B,C,D,E,F)             \
( i1 = value_range_base (INT (A), INT (B)),     \
  i2 = value_range_base (INT (C), INT (D)),     \
  i3 = value_range_base (INT (E), INT (F)),     \
  i1.union_ (i2),                       \
  i1.union_ (i3),                       \
  i1 )

// Run all of the selftests within this file.

void
range_tests ()
{
  tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
  value_range_base i1, i2, i3;
  value_range_base r0, r1, rold;

  // Test that NOT(255) is [0..254] in 8-bit land.
  value_range_base not_255 (VR_ANTI_RANGE, UCHAR (255), UCHAR (255));
  ASSERT_TRUE (not_255 == value_range_base (UCHAR (0), UCHAR (254)));

  // Test that NOT(0) is [1..255] in 8-bit land.
  value_range_base not_zero = range_nonzero (unsigned_char_type_node);
  ASSERT_TRUE (not_zero == value_range_base (UCHAR (1), UCHAR (255)));

  // Check that [0,127][0x..ffffff80,0x..ffffff]
  //  => ~[128, 0x..ffffff7f].
  r0 = value_range_base (UINT128 (0), UINT128 (127));
  tree high = build_minus_one_cst (u128_type);
  // low = -1 - 127 => 0x..ffffff80.
  tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127));
  r1 = value_range_base (low, high); // [0x..ffffff80, 0x..ffffffff]
  // r0 = [0,127][0x..ffffff80,0x..fffffff].
  r0.union_ (r1);
  // r1 = [128, 0x..ffffff7f].
  r1 = value_range_base (UINT128(128),
                         fold_build2 (MINUS_EXPR, u128_type,
                                      build_minus_one_cst (u128_type),
                                      UINT128(128)));
  r0.invert ();
  ASSERT_TRUE (r0 == r1);

  r0.set_varying (integer_type_node);
  tree minint = wide_int_to_tree (integer_type_node, r0.lower_bound ());
  tree maxint = wide_int_to_tree (integer_type_node, r0.upper_bound ());

  r0.set_varying (short_integer_type_node);
  tree minshort = wide_int_to_tree (short_integer_type_node, r0.lower_bound ());
  tree maxshort = wide_int_to_tree (short_integer_type_node, r0.upper_bound ());

  r0.set_varying (unsigned_type_node);
  tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ());

  // Check that ~[0,5] => [6,MAX] for unsigned int.
  r0 = value_range_base (UINT (0), UINT (5));
  r0.invert ();
  ASSERT_TRUE (r0 == value_range_base (UINT(6), maxuint));

  // Check that ~[10,MAX] => [0,9] for unsigned int.
  r0 = value_range_base (VR_RANGE, UINT(10), maxuint);
  r0.invert ();
  ASSERT_TRUE (r0 == value_range_base (UINT (0), UINT (9)));

  // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
  r0 = value_range_base (VR_ANTI_RANGE, UINT128 (0), UINT128 (5));
  r1 = value_range_base (UINT128(6), build_minus_one_cst (u128_type));
  ASSERT_TRUE (r0 == r1);

  // Check that [~5] is really [-MIN,4][6,MAX].
  r0 = value_range_base (VR_ANTI_RANGE, INT (5), INT (5));
  r1 = value_range_base (minint, INT (4));
  r1.union_ (value_range_base (INT (6), maxint));
  ASSERT_FALSE (r1.undefined_p ());
  ASSERT_TRUE (r0 == r1);

  r1 = value_range_base (INT (5), INT (5));
  r1.check ();
  value_range_base r2 (r1);
  ASSERT_TRUE (r1 == r2);

  r1 = value_range_base (INT (5), INT (10));
  r1.check ();

  r1 = value_range_base (integer_type_node,
               wi::to_wide (INT (5)), wi::to_wide (INT (10)));
  r1.check ();
  ASSERT_TRUE (r1.contains_p (INT (7)));

  r1 = value_range_base (SCHAR (0), SCHAR (20));
  ASSERT_TRUE (r1.contains_p (SCHAR(15)));
  ASSERT_FALSE (r1.contains_p (SCHAR(300)));

  // If a range is in any way outside of the range for the converted
  // to range, default to the range for the new type.
  if (TYPE_PRECISION (TREE_TYPE (maxint))
      > TYPE_PRECISION (short_integer_type_node))
    {
      r1 = value_range_base (integer_zero_node, maxint);
      range_cast (r1, short_integer_type_node);
      ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort)
                   && r1.upper_bound() == wi::to_wide (maxshort));
    }

  // (unsigned char)[-5,-1] => [251,255].
  r0 = rold = value_range_base (SCHAR (-5), SCHAR (-1));
  range_cast (r0, unsigned_char_type_node);
  ASSERT_TRUE (r0 == value_range_base (UCHAR (251), UCHAR (255)));
  range_cast (r0, signed_char_type_node);
  ASSERT_TRUE (r0 == rold);

  // (signed char)[15, 150] => [-128,-106][15,127].
  r0 = rold = value_range_base (UCHAR (15), UCHAR (150));
  range_cast (r0, signed_char_type_node);
  r1 = value_range_base (SCHAR (15), SCHAR (127));
  r2 = value_range_base (SCHAR (-128), SCHAR (-106));
  r1.union_ (r2);
  ASSERT_TRUE (r1 == r0);
  range_cast (r0, unsigned_char_type_node);
  ASSERT_TRUE (r0 == rold);

  // (unsigned char)[-5, 5] => [0,5][251,255].
  r0 = rold = value_range_base (SCHAR (-5), SCHAR (5));
  range_cast (r0, unsigned_char_type_node);
  r1 = value_range_base (UCHAR (251), UCHAR (255));
  r2 = value_range_base (UCHAR (0), UCHAR (5));
  r1.union_ (r2);
  ASSERT_TRUE (r0 == r1);
  range_cast (r0, signed_char_type_node);
  ASSERT_TRUE (r0 == rold);

  // (unsigned char)[-5,5] => [0,5][251,255].
  r0 = value_range_base (INT (-5), INT (5));
  range_cast (r0, unsigned_char_type_node);
  r1 = value_range_base (UCHAR (0), UCHAR (5));
  r1.union_ (value_range_base (UCHAR (251), UCHAR (255)));
  ASSERT_TRUE (r0 == r1);

  // (unsigned char)[5U,1974U] => [0,255].
  r0 = value_range_base (UINT (5), UINT (1974));
  range_cast (r0, unsigned_char_type_node);
  ASSERT_TRUE (r0 == value_range_base (UCHAR (0), UCHAR (255)));
  range_cast (r0, integer_type_node);
  // Going to a wider range should not sign extend.
  ASSERT_TRUE (r0 == value_range_base (INT (0), INT (255)));

  // (unsigned char)[-350,15] => [0,255].
  r0 = value_range_base (INT (-350), INT (15));
  range_cast (r0, unsigned_char_type_node);
  ASSERT_TRUE (r0 == (value_range_base
                      (TYPE_MIN_VALUE (unsigned_char_type_node),
                       TYPE_MAX_VALUE (unsigned_char_type_node))));

  // Casting [-120,20] from signed char to unsigned short.
  // => [0, 20][0xff88, 0xffff].
  r0 = value_range_base (SCHAR (-120), SCHAR (20));
  range_cast (r0, short_unsigned_type_node);
  r1 = value_range_base (UINT16 (0), UINT16 (20));
  r2 = value_range_base (UINT16 (0xff88), UINT16 (0xffff));
  r1.union_ (r2);
  ASSERT_TRUE (r0 == r1);
  // A truncating cast back to signed char will work because [-120, 20]
  // is representable in signed char.
  range_cast (r0, signed_char_type_node);
  ASSERT_TRUE (r0 == value_range_base (SCHAR (-120), SCHAR (20)));

  // unsigned char -> signed short
  //    (signed short)[(unsigned char)25, (unsigned char)250]
  // => [(signed short)25, (signed short)250]
  r0 = rold = value_range_base (UCHAR (25), UCHAR (250));
  range_cast (r0, short_integer_type_node);
  r1 = value_range_base (INT16 (25), INT16 (250));
  ASSERT_TRUE (r0 == r1);
  range_cast (r0, unsigned_char_type_node);
  ASSERT_TRUE (r0 == rold);

  // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
  r0 = value_range_base (TYPE_MIN_VALUE (long_long_integer_type_node),
               TYPE_MAX_VALUE (long_long_integer_type_node));
  range_cast (r0, short_unsigned_type_node);
  r1 = value_range_base (TYPE_MIN_VALUE (short_unsigned_type_node),
               TYPE_MAX_VALUE (short_unsigned_type_node));
  ASSERT_TRUE (r0 == r1);

  // NOT([10,20]) ==> [-MIN,9][21,MAX].
  r0 = r1 = value_range_base (INT (10), INT (20));
  r2 = value_range_base (minint, INT(9));
  r2.union_ (value_range_base (INT(21), maxint));
  ASSERT_FALSE (r2.undefined_p ());
  r1.invert ();
  ASSERT_TRUE (r1 == r2);
  // Test that NOT(NOT(x)) == x.
  r2.invert ();
  ASSERT_TRUE (r0 == r2);

  // Test that booleans and their inverse work as expected.
  r0 = range_zero (boolean_type_node);
  ASSERT_TRUE (r0 == value_range_base (build_zero_cst (boolean_type_node),
                                       build_zero_cst (boolean_type_node)));
  r0.invert ();
  ASSERT_TRUE (r0 == value_range_base (build_one_cst (boolean_type_node),
                                       build_one_cst (boolean_type_node)));

  // Casting NONZERO to a narrower type will wrap/overflow so
  // it's just the entire range for the narrower type.
  //
  // "NOT 0 at signed 32-bits" ==> [-MIN_32,-1][1, +MAX_32].  This is
  // is outside of the range of a smaller range, return the full
  // smaller range.
  if (TYPE_PRECISION (integer_type_node)
      > TYPE_PRECISION (short_integer_type_node))
    {
      r0 = range_nonzero (integer_type_node);
      range_cast (r0, short_integer_type_node);
      r1 = value_range_base (TYPE_MIN_VALUE (short_integer_type_node),
                             TYPE_MAX_VALUE (short_integer_type_node));
      ASSERT_TRUE (r0 == r1);
    }

  // Casting NONZERO from a narrower signed to a wider signed.
  //
  // NONZERO signed 16-bits is [-MIN_16,-1][1, +MAX_16].
  // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
  r0 = range_nonzero (short_integer_type_node);
  range_cast (r0, integer_type_node);
  r1 = value_range_base (INT (-32768), INT (-1));
  r2 = value_range_base (INT (1), INT (32767));
  r1.union_ (r2);
  ASSERT_TRUE (r0 == r1);

  if (value_range_base::m_max_pairs > 2)
    {
      // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
      r0 = value_range_base (INT (10), INT (20));
      r1 = value_range_base (INT (5), INT (8));
      r0.union_ (r1);
      r1 = value_range_base (INT (1), INT (3));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == RANGE3 (1, 3, 5, 8, 10, 20));

      // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
      r1 = value_range_base (INT (-5), INT (0));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == RANGE3 (-5, 3, 5, 8, 10, 20));
    }

  // [10,20] U [30,40] ==> [10,20][30,40].
  r0 = value_range_base (INT (10), INT (20));
  r1 = value_range_base (INT (30), INT (40));
  r0.union_ (r1);
  ASSERT_TRUE (r0 == range_union (value_range_base (INT (10), INT (20)),
                                  value_range_base (INT (30), INT (40))));
  if (value_range_base::m_max_pairs > 2)
    {
      // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
      r1 = value_range_base (INT (50), INT (60));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60));
      // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
      r1 = value_range_base (INT (70), INT (80));
      r0.union_ (r1);

      r2 = RANGE3 (10, 20, 30, 40, 50, 60);
      r2.union_ (value_range_base (INT (70), INT (80)));
      ASSERT_TRUE (r0 == r2);
    }

  // Make sure NULL and non-NULL of pointer types work, and that
  // inverses of them are consistent.
  tree voidp = build_pointer_type (void_type_node);
  r0 = range_zero (voidp);
  r1 = r0;
  r0.invert ();
  r0.invert ();
  ASSERT_TRUE (r0 == r1);

  if (value_range_base::m_max_pairs > 2)
    {
      // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
      r0 = RANGE3 (10, 20, 30, 40, 50, 60);
      r1 = value_range_base (INT (6), INT (35));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == range_union (value_range_base (INT (6), INT (40)),
                                      value_range_base (INT (50), INT (60))));

      // [10,20][30,40][50,60] U [6,60] => [6,60].
      r0 = RANGE3 (10, 20, 30, 40, 50, 60);
      r1 = value_range_base (INT (6), INT (60));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == value_range_base (INT (6), INT (60)));

      // [10,20][30,40][50,60] U [6,70] => [6,70].
      r0 = RANGE3 (10, 20, 30, 40, 50, 60);
      r1 = value_range_base (INT (6), INT (70));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == value_range_base (INT (6), INT (70)));

      // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
      r0 = RANGE3 (10, 20, 30, 40, 50, 60);
      r1 = value_range_base (INT (35), INT (70));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == range_union (value_range_base (INT (10), INT (20)),
                                      value_range_base (INT (30), INT (70))));
    }

  // [10,20][30,40] U [25,70] => [10,70].
  r0 = range_union (value_range_base (INT (10), INT (20)),
                     value_range_base (INT (30), INT (40)));
  r1 = value_range_base (INT (25), INT (70));
  r0.union_ (r1);
  ASSERT_TRUE (r0 == range_union (value_range_base (INT (10), INT (20)),
                                  value_range_base (INT (25), INT (70))));

  if (value_range_base::m_max_pairs > 2)
    {
      // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
      r0 = RANGE3 (10, 20, 30, 40, 50, 60);
      r1 = value_range_base (INT (15), INT (35));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == range_union (value_range_base (INT (10), INT (40)),
                                      value_range_base (INT (50), INT (60))));
    }

  // [10,20] U [15, 30] => [10, 30].
  r0 = value_range_base (INT (10), INT (20));
  r1 = value_range_base (INT (15), INT (30));
  r0.union_ (r1);
  ASSERT_TRUE (r0 == value_range_base (INT (10), INT (30)));

  // [10,20] U [25,25] => [10,20][25,25].
  r0 = value_range_base (INT (10), INT (20));
  r1 = value_range_base (INT (25), INT (25));
  r0.union_ (r1);
  ASSERT_TRUE (r0 == range_union (value_range_base (INT (10), INT (20)),
                                  value_range_base (INT (25), INT (25))));

  if (value_range_base::m_max_pairs > 2)
    {
      // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
      r0 = RANGE3 (10, 20, 30, 40, 50, 60);
      r1 = value_range_base (INT (35), INT (35));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == RANGE3 (10, 20, 30, 40, 50, 60));
    }

  // [15,40] U [] => [15,40].
  r0 = value_range_base (INT (15), INT (40));
  r1.set_undefined ();
  r0.union_ (r1);
  ASSERT_TRUE (r0 == value_range_base (INT (15), INT (40)));

  // [10,20] U [10,10] => [10,20].
  r0 = value_range_base (INT (10), INT (20));
  r1 = value_range_base (INT (10), INT (10));
  r0.union_ (r1);
  ASSERT_TRUE (r0 == value_range_base (INT (10), INT (20)));

  // [10,20] U [9,9] => [9,20].
  r0 = value_range_base (INT (10), INT (20));
  r1 = value_range_base (INT (9), INT (9));
  r0.union_ (r1);
  ASSERT_TRUE (r0 == value_range_base (INT (9), INT (20)));

  if (value_range_base::m_max_pairs > 2)
    {
      // [10,10][12,12][20,100] ^ [15,200].
      r0 = RANGE3 (10, 10, 12, 12, 20, 100);
      r1 = value_range_base (INT (15), INT (200));
      r0.intersect (r1);
      ASSERT_TRUE (r0 == value_range_base (INT (20), INT (100)));

      // [10,20][30,40][50,60] ^ [15,25][38,51][55,70]
      // => [15,20][38,40][50,51][55,60]
      r0 = RANGE3 (10, 20, 30, 40, 50, 60);
      r1 = RANGE3 (15, 25, 38, 51, 55, 70);
      r0.intersect (r1);
      if (value_range_base::m_max_pairs == 3)
        {
          // When pairs==3, we don't have enough space, so
          //  conservatively handle things.  Thus, the ...[50,60].
          ASSERT_TRUE (r0 == RANGE3 (15, 20, 38, 40, 50, 60));
        }
      else
        {
          r2 = RANGE3 (15, 20, 38, 40, 50, 51);
          r2.union_ (value_range_base (INT (55), INT (60)));
          ASSERT_TRUE (r0 == r2);
        }

      // [15,20][30,40][50,60] ^ [15,35][40,90][100,200]
      // => [15,20][30,35][40,60]
      r0 = RANGE3 (15, 20, 30, 40, 50, 60);
      r1 = RANGE3 (15, 35, 40, 90, 100, 200);
      r0.intersect (r1);
      if (value_range_base::m_max_pairs == 3)
        {
          // When pairs==3, we don't have enough space, so
          // conservatively handle things.
          ASSERT_TRUE (r0 == RANGE3 (15, 20, 30, 35, 40, 60));
        }
      else
        {
          r2 = RANGE3 (15, 20, 30, 35, 40, 40);
          r2.union_ (value_range_base (INT (50), INT (60)));
          ASSERT_TRUE (r0 == r2);
        }

      // Test cases where a union inserts a sub-range inside a larger
      // range.
      //
      // [8,10][135,255] U [14,14] => [8,10][14,14][135,255]
      r0 = range_union (value_range_base (INT (8), INT (10)),
                         value_range_base (INT (135), INT (255)));
      r1 = value_range_base (INT (14), INT (14));
      r0.union_ (r1);
      ASSERT_TRUE (r0 == RANGE3 (8, 10, 14, 14, 135, 255));
    }

  // [10,20] ^ [15,30] => [15,20].
  r0 = value_range_base (INT (10), INT (20));
  r1 = value_range_base (INT (15), INT (30));
  r0.intersect (r1);
  ASSERT_TRUE (r0 == value_range_base (INT (15), INT (20)));

  // [10,20][30,40] ^ [40,50] => [40,40].
  r0 = range_union (value_range_base (INT (10), INT (20)),
                     value_range_base (INT (30), INT (40)));
  r1 = value_range_base (INT (40), INT (50));
  r0.intersect (r1);
  ASSERT_TRUE (r0 == value_range_base (INT (40), INT (40)));

  // Test non-destructive intersection.
  r0 = rold = value_range_base (INT (10), INT (20));
  ASSERT_FALSE (range_intersect (r0, value_range_base (INT (15),
                                             INT (30))).undefined_p ());
  ASSERT_TRUE (r0 == rold);

  // Test the internal sanity of wide_int's wrt HWIs.
  ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
                              TYPE_SIGN (boolean_type_node))
               == wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));

  // Test zero_p().
  r0 = value_range_base (INT (0), INT (0));
  ASSERT_TRUE (r0.zero_p ());

  // Test nonzero_p().
  r0 = value_range_base (INT (0), INT (0));
  r0.invert ();
  ASSERT_TRUE (r0.nonzero_p ());
}
#endif // CHECKING_P