gcc/analyzer/constraint-manager.cc

/* Tracking equivalence classes and constraints at a point on an execution path.
   Copyright (C) 2019-2021 Free Software Foundation, Inc.
   Contributed by David Malcolm <dmalcolm@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 "tree.h"
#include "function.h"
#include "basic-block.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "fold-const.h"
#include "selftest.h"
#include "diagnostic-core.h"
#include "graphviz.h"
#include "function.h"
#include "json.h"
#include "analyzer/analyzer.h"
#include "ordered-hash-map.h"
#include "options.h"
#include "cgraph.h"
#include "cfg.h"
#include "digraph.h"
#include "analyzer/supergraph.h"
#include "sbitmap.h"
#include "bitmap.h"
#include "tristate.h"
#include "analyzer/analyzer-logging.h"
#include "analyzer/call-string.h"
#include "analyzer/program-point.h"
#include "analyzer/store.h"
#include "analyzer/region-model.h"
#include "analyzer/constraint-manager.h"
#include "analyzer/analyzer-selftests.h"
#include "tree-pretty-print.h"

#if ENABLE_ANALYZER

namespace ana {

static tristate
compare_constants (tree lhs_const, enum tree_code op, tree rhs_const)
{
  tree comparison
    = fold_binary (op, boolean_type_node, lhs_const, rhs_const);
  if (comparison == boolean_true_node)
    return tristate (tristate::TS_TRUE);
  if (comparison == boolean_false_node)
    return tristate (tristate::TS_FALSE);
  return tristate (tristate::TS_UNKNOWN);
}

/* Return true iff CST is below the maximum value for its type.  */

static bool
can_plus_one_p (tree cst)
{
  gcc_assert (CONSTANT_CLASS_P (cst));
  return tree_int_cst_lt (cst, TYPE_MAX_VALUE (TREE_TYPE (cst)));
}

/* Return (CST + 1).  */

static tree
plus_one (tree cst)
{
  gcc_assert (CONSTANT_CLASS_P (cst));
  gcc_assert (can_plus_one_p (cst));
  tree result = fold_build2 (PLUS_EXPR, TREE_TYPE (cst),
			     cst, integer_one_node);
  gcc_assert (CONSTANT_CLASS_P (result));
  return result;
}

/* Return true iff CST is above the minimum value for its type.  */

static bool
can_minus_one_p (tree cst)
{
  gcc_assert (CONSTANT_CLASS_P (cst));
  return tree_int_cst_lt (TYPE_MIN_VALUE (TREE_TYPE (cst)), cst);
}

/* Return (CST - 1).  */

static tree
minus_one (tree cst)
{
  gcc_assert (CONSTANT_CLASS_P (cst));
  gcc_assert (can_minus_one_p (cst));
  tree result = fold_build2 (MINUS_EXPR, TREE_TYPE (cst),
			     cst, integer_one_node);
  gcc_assert (CONSTANT_CLASS_P (result));
  return result;
}

/* struct bound.  */

/* Ensure that this bound is closed by converting an open bound to a
   closed one.  */

void
bound::ensure_closed (bool is_upper)
{
  if (!m_closed)
    {
      /* Offset by 1 in the appropriate direction.
	 For example, convert 3 < x into 4 <= x,
	 and convert x < 5 into x <= 4.  */
      gcc_assert (CONSTANT_CLASS_P (m_constant));
      m_constant = fold_build2 (is_upper ? MINUS_EXPR : PLUS_EXPR,
				TREE_TYPE (m_constant),
				m_constant, integer_one_node);
      gcc_assert (CONSTANT_CLASS_P (m_constant));
      m_closed = true;
    }
}

/* Get "<=" vs "<" for this bound.  */

const char *
bound::get_relation_as_str () const
{
  if (m_closed)
    return "<=";
  else
    return "<";
}

/* struct range.  */

/* Dump this range to PP, which must support %E for tree.  */

void
range::dump_to_pp (pretty_printer *pp) const
{
  if (m_lower_bound.m_constant)
    {
      if (m_upper_bound.m_constant)
	pp_printf (pp, "%qE %s x %s %qE",
		   m_lower_bound.m_constant,
		   m_lower_bound.get_relation_as_str (),
		   m_upper_bound.get_relation_as_str (),
		   m_upper_bound.m_constant);
      else
	pp_printf (pp, "%qE %s x",
		   m_lower_bound.m_constant,
		   m_lower_bound.get_relation_as_str ());
    }
  else
    {
      if (m_upper_bound.m_constant)
	pp_printf (pp, "x %s %qE",
		   m_upper_bound.get_relation_as_str (),
		   m_upper_bound.m_constant);
      else
	pp_string (pp, "x");
    }
}

/* Dump this range to stderr.  */

DEBUG_FUNCTION void
range::dump () const
{
  pretty_printer pp;
  pp_format_decoder (&pp) = default_tree_printer;
  pp_show_color (&pp) = pp_show_color (global_dc->printer);
  pp.buffer->stream = stderr;
  dump_to_pp (&pp);
  pp_newline (&pp);
  pp_flush (&pp);
}

/* Determine if there is only one possible value for this range.
   If so, return the constant; otherwise, return NULL_TREE.  */

tree
range::constrained_to_single_element ()
{
  if (m_lower_bound.m_constant == NULL_TREE
      || m_upper_bound.m_constant == NULL_TREE)
    return NULL_TREE;

  if (!INTEGRAL_TYPE_P (TREE_TYPE (m_lower_bound.m_constant)))
    return NULL_TREE;
  if (!INTEGRAL_TYPE_P (TREE_TYPE (m_upper_bound.m_constant)))
    return NULL_TREE;

  /* Convert any open bounds to closed bounds.  */
  m_lower_bound.ensure_closed (false);
  m_upper_bound.ensure_closed (true);

  // Are they equal?
  tree comparison = fold_binary (EQ_EXPR, boolean_type_node,
				 m_lower_bound.m_constant,
				 m_upper_bound.m_constant);
  if (comparison == boolean_true_node)
    return m_lower_bound.m_constant;
  else
    return NULL_TREE;
}

/* Eval the condition "X OP RHS_CONST" for X within the range.  */

tristate
range::eval_condition (enum tree_code op, tree rhs_const) const
{
  range copy (*this);
  if (tree single_element = copy.constrained_to_single_element ())
    return compare_constants (single_element, op, rhs_const);

  switch (op)
    {
    case EQ_EXPR:
      if (below_lower_bound (rhs_const))
	return tristate (tristate::TS_FALSE);
      if (above_upper_bound (rhs_const))
	return tristate (tristate::TS_FALSE);
      break;

    case LT_EXPR:
    case LE_EXPR:
      /* Qn: "X </<= RHS_CONST".  */
      /* If RHS_CONST > upper bound, then it's true.
	 If RHS_CONST < lower bound, then it's false.
	 Otherwise unknown.  */
      if (above_upper_bound (rhs_const))
	return tristate (tristate::TS_TRUE);
      if (below_lower_bound (rhs_const))
	return tristate (tristate::TS_FALSE);
      break;

    case NE_EXPR:
      /* Qn: "X != RHS_CONST".  */
      /* If RHS_CONST < lower bound, then it's true.
	 If RHS_CONST > upper bound, then it's false.
	 Otherwise unknown.  */
      if (below_lower_bound (rhs_const))
	return tristate (tristate::TS_TRUE);
      if (above_upper_bound (rhs_const))
	return tristate (tristate::TS_TRUE);
      break;

    case GE_EXPR:
    case GT_EXPR:
      /* Qn: "X >=/> RHS_CONST".  */
      if (above_upper_bound (rhs_const))
	return tristate (tristate::TS_FALSE);
      if (below_lower_bound (rhs_const))
	return tristate (tristate::TS_TRUE);
      break;

    default:
      gcc_unreachable ();
      break;
    }
  return tristate (tristate::TS_UNKNOWN);
}

/* Return true if RHS_CONST is below the lower bound of this range.  */

bool
range::below_lower_bound (tree rhs_const) const
{
  if (!m_lower_bound.m_constant)
    return false;

  return compare_constants (rhs_const,
			    m_lower_bound.m_closed ? LT_EXPR : LE_EXPR,
			    m_lower_bound.m_constant).is_true ();
}

/* Return true if RHS_CONST is above the upper bound of this range.  */

bool
range::above_upper_bound (tree rhs_const) const
{
  if (!m_upper_bound.m_constant)
    return false;

  return compare_constants (rhs_const,
			    m_upper_bound.m_closed ? GT_EXPR : GE_EXPR,
			    m_upper_bound.m_constant).is_true ();
}

/* struct bounded_range.  */

bounded_range::bounded_range (const_tree lower, const_tree upper)
: m_lower (const_cast<tree> (lower)),
  m_upper (const_cast<tree> (upper))
{
  if (lower && upper)
    {
      gcc_assert (TREE_CODE (m_lower) == INTEGER_CST);
      gcc_assert (TREE_CODE (m_upper) == INTEGER_CST);
      /* We should have lower <= upper.  */
      gcc_assert (!tree_int_cst_lt (m_upper, m_lower));
    }
  else
    {
      /* Purely for pending on-stack values, for
	 writing back to.  */
      gcc_assert (m_lower == NULL_TREE);
      gcc_assert (m_lower == NULL_TREE);
    }
}

static void
dump_cst (pretty_printer *pp, tree cst, bool show_types)
{
  gcc_assert (cst);
  if (show_types)
    {
      pp_character (pp, '(');
      dump_generic_node (pp, TREE_TYPE (cst), 0, (dump_flags_t)0, false);
      pp_character (pp, ')');
    }
  dump_generic_node (pp, cst, 0, (dump_flags_t)0, false);
}

/* Dump this object to PP.  */

void
bounded_range::dump_to_pp (pretty_printer *pp, bool show_types) const
{
  if (tree_int_cst_equal (m_lower, m_upper))
    dump_cst (pp, m_lower, show_types);
  else
    {
      pp_character (pp, '[');
      dump_cst (pp, m_lower, show_types);
      pp_string (pp, ", ");
      dump_cst (pp, m_upper, show_types);
      pp_character (pp, ']');
    }
}

/* Dump this object to stderr.  */

void
bounded_range::dump (bool show_types) const
{
  pretty_printer pp;
  pp_format_decoder (&pp) = default_tree_printer;
  pp_show_color (&pp) = pp_show_color (global_dc->printer);
  pp.buffer->stream = stderr;
  dump_to_pp (&pp, show_types);
  pp_newline (&pp);
  pp_flush (&pp);
}

json::object *
bounded_range::to_json () const
{
  json::object *range_obj = new json::object ();
  set_json_attr (range_obj, "lower", m_lower);
  set_json_attr (range_obj, "upper", m_upper);
  return range_obj;
}

/* Subroutine of bounded_range::to_json.  */

void
bounded_range::set_json_attr (json::object *obj, const char *name, tree value)
{
  pretty_printer pp;
  pp_format_decoder (&pp) = default_tree_printer;
  pp_printf (&pp, "%E", value);
  obj->set (name, new json::string (pp_formatted_text (&pp)));
}


/* Return true iff CST is within this range.  */

bool
bounded_range::contains_p (tree cst) const
{
  /* Reject if below lower bound.  */
  if (tree_int_cst_lt (cst, m_lower))
    return false;
  /* Reject if above lower bound.  */
  if (tree_int_cst_lt (m_upper, cst))
    return false;
  return true;
}

/* If this range intersects OTHER, return true, writing
   the intersection to *OUT if OUT is non-NULL.
   Return false if they do not intersect.  */

bool
bounded_range::intersects_p (const bounded_range &other,
			     bounded_range *out) const
{
  const tree max_lower
    = (tree_int_cst_le (m_lower, other.m_lower)
       ? other.m_lower : m_lower);
  gcc_assert (TREE_CODE (max_lower) == INTEGER_CST);
  const tree min_upper
    = (tree_int_cst_le (m_upper, other.m_upper)
       ? m_upper : other.m_upper);
  gcc_assert (TREE_CODE (min_upper) == INTEGER_CST);

  if (tree_int_cst_le (max_lower, min_upper))
    {
      if (out)
	*out = bounded_range (max_lower, min_upper);
      return true;
    }
  else
    return false;
}

bool
bounded_range::operator== (const bounded_range &other) const
{
  return (tree_int_cst_equal (m_lower, other.m_lower)
	  && tree_int_cst_equal (m_upper, other.m_upper));
}

int
bounded_range::cmp (const bounded_range &br1, const bounded_range &br2)
{
  if (int cmp_lower = tree_int_cst_compare (br1.m_lower,
					    br2.m_lower))
    return cmp_lower;
  return tree_int_cst_compare (br1.m_upper, br2.m_upper);
}

/* struct bounded_ranges.  */

/* Construct a bounded_ranges instance from a single range.  */

bounded_ranges::bounded_ranges (const bounded_range &range)
: m_ranges (1)
{
  m_ranges.quick_push (range);
  canonicalize ();
  validate ();
}

/* Construct a bounded_ranges instance from multiple ranges.  */

bounded_ranges::bounded_ranges (const vec<bounded_range> &ranges)
: m_ranges (ranges.length ())
{
  m_ranges.safe_splice (ranges);
  canonicalize ();
  validate ();
}

/* Construct a bounded_ranges instance for values of LHS for which
   (LHS OP RHS_CONST) is true (e.g. "(LHS > 3)".  */

bounded_ranges::bounded_ranges (enum tree_code op, tree rhs_const)
: m_ranges ()
{
  gcc_assert (TREE_CODE (rhs_const) == INTEGER_CST);
  tree type = TREE_TYPE (rhs_const);
  switch (op)
    {
    default:
      gcc_unreachable ();
    case EQ_EXPR:
      m_ranges.safe_push (bounded_range (rhs_const, rhs_const));
      break;

    case GE_EXPR:
      m_ranges.safe_push (bounded_range (rhs_const, TYPE_MAX_VALUE (type)));
      break;

    case LE_EXPR:
      m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type), rhs_const));
      break;

    case NE_EXPR:
      if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const))
	m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type),
					   minus_one (rhs_const)));
      if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type)))
	m_ranges.safe_push (bounded_range (plus_one (rhs_const),
					   TYPE_MAX_VALUE (type)));
      break;
    case GT_EXPR:
      if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type)))
	m_ranges.safe_push (bounded_range (plus_one (rhs_const),
					   TYPE_MAX_VALUE (type)));
      break;
    case LT_EXPR:
      if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const))
	m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type),
					   minus_one (rhs_const)));
      break;
    }
  canonicalize ();
  validate ();
}

/* Subroutine of ctors for fixing up m_ranges.
   Also, initialize m_hash.  */

void
bounded_ranges::canonicalize ()
{
  /* Sort the ranges.  */
  m_ranges.qsort ([](const void *p1, const void *p2) -> int
		  {
		    const bounded_range &br1 = *(const bounded_range *)p1;
		    const bounded_range &br2 = *(const bounded_range *)p2;
		    return bounded_range::cmp (br1, br2);
		  });

  /* Merge ranges that are touching or overlapping.  */
  for (unsigned i = 1; i < m_ranges.length (); )
    {
      bounded_range *prev = &m_ranges[i - 1];
      const bounded_range *next = &m_ranges[i];
      if (prev->intersects_p (*next, NULL)
	  || (can_plus_one_p (prev->m_upper)
	      && tree_int_cst_equal (plus_one (prev->m_upper),
				     next->m_lower)))
	{
	  prev->m_upper = next->m_upper;
	  m_ranges.ordered_remove (i);
	}
      else
	i++;
    }

  /* Initialize m_hash.  */
  inchash::hash hstate (0);
  for (const auto &iter : m_ranges)
    {
      inchash::add_expr (iter.m_lower, hstate);
      inchash::add_expr (iter.m_upper, hstate);
    }
  m_hash = hstate.end ();
}

/* Assert that this object is valid.  */

void
bounded_ranges::validate () const
{
  /* Skip this in a release build.  */
#if !CHECKING_P
  return;
#endif

  for (unsigned i = 1; i < m_ranges.length (); i++)
    {
      const bounded_range &prev = m_ranges[i - 1];
      const bounded_range &next = m_ranges[i];

      /* Give up if we somehow have incompatible different types.  */
      if (!types_compatible_p (TREE_TYPE (prev.m_upper),
			       TREE_TYPE (next.m_lower)))
	continue;

      /* Verify sorted.  */
      gcc_assert (tree_int_cst_lt (prev.m_upper, next.m_lower));

      gcc_assert (can_plus_one_p (prev.m_upper));
      /* otherwise there's no room for "next".  */

      /* Verify no ranges touch each other.  */
      gcc_assert (tree_int_cst_lt (plus_one (prev.m_upper), next.m_lower));
    }
}

/* bounded_ranges equality operator.  */

bool
bounded_ranges::operator== (const bounded_ranges &other) const
{
  if (m_ranges.length () != other.m_ranges.length ())
    return false;
  for (unsigned i = 0; i < m_ranges.length (); i++)
    {
      if (m_ranges[i] != other.m_ranges[i])
	return false;
    }
  return true;
}

/* Dump this object to PP.  */

void
bounded_ranges::dump_to_pp (pretty_printer *pp, bool show_types) const
{
  pp_character (pp, '{');
  for (unsigned i = 0; i < m_ranges.length (); ++i)
    {
      if (i > 0)
	pp_string (pp, ", ");
      m_ranges[i].dump_to_pp (pp, show_types);
    }
  pp_character (pp, '}');
}

/* Dump this object to stderr.  */

DEBUG_FUNCTION void
bounded_ranges::dump (bool show_types) const
{
  pretty_printer pp;
  pp_format_decoder (&pp) = default_tree_printer;
  pp_show_color (&pp) = pp_show_color (global_dc->printer);
  pp.buffer->stream = stderr;
  dump_to_pp (&pp, show_types);
  pp_newline (&pp);
  pp_flush (&pp);
}

json::value *
bounded_ranges::to_json () const
{
  json::array *arr_obj = new json::array ();

  for (unsigned i = 0; i < m_ranges.length (); ++i)
    arr_obj->append (m_ranges[i].to_json ());

  return arr_obj;
}

/* Determine whether (X OP RHS_CONST) is known to be true or false
   for all X in the ranges expressed by this object.  */

tristate
bounded_ranges::eval_condition (enum tree_code op,
				tree rhs_const,
				bounded_ranges_manager *mgr) const
{
  /* Convert (X OP RHS_CONST) to a bounded_ranges instance and find
     the intersection of that with this object.  */
  bounded_ranges other (op, rhs_const);
  const bounded_ranges *intersection
    = mgr->get_or_create_intersection (this, &other);

  if (intersection->m_ranges.length () > 0)
    {
      /* We can use pointer equality to check for equality,
	 due to instance consolidation.  */
      if (intersection == this)
	return tristate (tristate::TS_TRUE);
      else
	return tristate (tristate::TS_UNKNOWN);
    }
  else
    /* No intersection.  */
    return tristate (tristate::TS_FALSE);
}

/* Return true if CST is within any of the ranges.  */

bool
bounded_ranges::contain_p (tree cst) const
{
  gcc_assert (TREE_CODE (cst) == INTEGER_CST);
  for (const auto &iter : m_ranges)
    {
      /* TODO: should we optimize this based on sorting?  */
      if (iter.contains_p (cst))
	return true;
    }
  return false;
}

int
bounded_ranges::cmp (const bounded_ranges *a, const bounded_ranges *b)
{
  if (int cmp_length = ((int)a->m_ranges.length ()
			- (int)b->m_ranges.length ()))
    return cmp_length;
  for (unsigned i = 0; i < a->m_ranges.length (); i++)
    {
      if (int cmp_range = bounded_range::cmp (a->m_ranges[i], b->m_ranges[i]))
	return cmp_range;
    }
  /* They are equal.  They ought to have been consolidated, so we should
     have two pointers to the same object.  */
  gcc_assert (a == b);
  return 0;
}

/* class bounded_ranges_manager.  */

/* bounded_ranges_manager's dtor.  */

bounded_ranges_manager::~bounded_ranges_manager ()
{
  /* Delete the managed objects.  */
  for (const auto &iter : m_map)
    delete iter.second;
}

/* Get the bounded_ranges instance for the empty set,  creating it if
   necessary.  */

const bounded_ranges *
bounded_ranges_manager::get_or_create_empty ()
{
  auto_vec<bounded_range> empty_vec;

  return consolidate (new bounded_ranges (empty_vec));
}

/* Get the bounded_ranges instance for {CST}, creating it if necessary.  */

const bounded_ranges *
bounded_ranges_manager::get_or_create_point (const_tree cst)
{
  gcc_assert (TREE_CODE (cst) == INTEGER_CST);

  return get_or_create_range (cst, cst);
}

/* Get the bounded_ranges instance for {[LOWER_BOUND..UPPER_BOUND]},
   creating it if necessary.  */

const bounded_ranges *
bounded_ranges_manager::get_or_create_range (const_tree lower_bound,
					     const_tree upper_bound)
{
  gcc_assert (TREE_CODE (lower_bound) == INTEGER_CST);
  gcc_assert (TREE_CODE (upper_bound) == INTEGER_CST);

  return consolidate
    (new bounded_ranges (bounded_range (lower_bound, upper_bound)));
}

/* Get the bounded_ranges instance for the union of OTHERS,
   creating it if necessary.  */

const bounded_ranges *
bounded_ranges_manager::
get_or_create_union (const vec <const bounded_ranges *> &others)
{
  auto_vec<bounded_range> ranges;
  for (const auto &r : others)
    ranges.safe_splice (r->m_ranges);
  return consolidate (new bounded_ranges (ranges));
}

/* Get the bounded_ranges instance for the intersection of A and B,
   creating it if necessary.  */

const bounded_ranges *
bounded_ranges_manager::get_or_create_intersection (const bounded_ranges *a,
						    const bounded_ranges *b)
{
  auto_vec<bounded_range> ranges;
  unsigned a_idx = 0;
  unsigned b_idx = 0;
  while (a_idx < a->m_ranges.length ()
	 && b_idx < b->m_ranges.length ())
    {
      const bounded_range &r_a = a->m_ranges[a_idx];
      const bounded_range &r_b = b->m_ranges[b_idx];

      bounded_range intersection (NULL_TREE, NULL_TREE);
      if (r_a.intersects_p (r_b, &intersection))
	{
	  ranges.safe_push (intersection);
	}
      if (tree_int_cst_lt (r_a.m_lower, r_b.m_lower))
	{
	  a_idx++;
	}
      else
	{
	  if (tree_int_cst_lt (r_a.m_upper, r_b.m_upper))
	    a_idx++;
	  else
	    b_idx++;
	}
    }

  return consolidate (new bounded_ranges (ranges));
}

/* Get the bounded_ranges instance for the inverse of OTHER relative
   to TYPE, creating it if necessary.
   This is for use when handling "default" in switch statements, where
   OTHER represents all the other cases.  */

const bounded_ranges *
bounded_ranges_manager::get_or_create_inverse (const bounded_ranges *other,
					       tree type)
{
  tree min_val = TYPE_MIN_VALUE (type);
  tree max_val = TYPE_MAX_VALUE (type);
  if (other->m_ranges.length () == 0)
    return get_or_create_range (min_val, max_val);
  auto_vec<bounded_range> ranges;
  tree first_lb = other->m_ranges[0].m_lower;
  if (tree_int_cst_lt (min_val, first_lb)
      && can_minus_one_p (first_lb))
    ranges.safe_push (bounded_range (min_val,
				     minus_one (first_lb)));
  for (unsigned i = 1; i < other->m_ranges.length (); i++)
    {
      tree prev_ub = other->m_ranges[i - 1].m_upper;
      tree iter_lb = other->m_ranges[i].m_lower;
      gcc_assert (tree_int_cst_lt (prev_ub, iter_lb));
      if (can_plus_one_p (prev_ub) && can_minus_one_p (iter_lb))
	ranges.safe_push (bounded_range (plus_one (prev_ub),
					 minus_one (iter_lb)));
    }
  tree last_ub
    = other->m_ranges[other->m_ranges.length () - 1].m_upper;
  if (tree_int_cst_lt (last_ub, max_val)
      && can_plus_one_p (last_ub))
    ranges.safe_push (bounded_range (plus_one (last_ub), max_val));

  return consolidate (new bounded_ranges (ranges));
}

/* If an object equal to INST is already present, delete INST and
   return the existing object.
   Otherwise add INST and return it.  */

const bounded_ranges *
bounded_ranges_manager::consolidate (bounded_ranges *inst)
{
  if (bounded_ranges **slot = m_map.get (inst))
    {
      delete inst;
      return *slot;
    }
  m_map.put (inst, inst);
  return inst;
}

/* Get the bounded_ranges instance for EDGE of SWITCH_STMT,
   creating it if necessary, and caching it by edge.  */

const bounded_ranges *
bounded_ranges_manager::
get_or_create_ranges_for_switch (const switch_cfg_superedge *edge,
				 const gswitch *switch_stmt)
{
  /* Look in per-edge cache.  */
  if (const bounded_ranges ** slot = m_edge_cache.get (edge))
    return *slot;

  /* Not yet in cache.  */
  const bounded_ranges *all_cases_ranges
    = create_ranges_for_switch (*edge, switch_stmt);
  m_edge_cache.put (edge, all_cases_ranges);
  return all_cases_ranges;
}

/* Get the bounded_ranges instance for EDGE of SWITCH_STMT,
   creating it if necessary, for edges for which the per-edge
   cache has not yet been populated.  */

const bounded_ranges *
bounded_ranges_manager::
create_ranges_for_switch (const switch_cfg_superedge &edge,
			  const gswitch *switch_stmt)
{
  /* Get the ranges for each case label.  */
  auto_vec <const bounded_ranges *> case_ranges_vec
    (gimple_switch_num_labels (switch_stmt));

  for (tree case_label : edge.get_case_labels ())
    {
      /* Get the ranges for this case label.  */
      const bounded_ranges *case_ranges
	= make_case_label_ranges (switch_stmt, case_label);
      case_ranges_vec.quick_push (case_ranges);
    }

  /* Combine all the ranges for each case label into a single collection
     of ranges.  */
  const bounded_ranges *all_cases_ranges
    = get_or_create_union (case_ranges_vec);
  return all_cases_ranges;
}

/* Get the bounded_ranges instance for CASE_LABEL within
   SWITCH_STMT.  */

const bounded_ranges *
bounded_ranges_manager::
make_case_label_ranges (const gswitch *switch_stmt,
			tree case_label)
{
  gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
  tree lower_bound = CASE_LOW (case_label);
  tree upper_bound = CASE_HIGH (case_label);
  if (lower_bound)
    {
      if (upper_bound)
	/* Range.  */
	return get_or_create_range (lower_bound, upper_bound);
      else
	/* Single-value.  */
	return get_or_create_point (lower_bound);
    }
  else
    {
      /* The default case.
	 Add exclusions based on the other cases.  */
      auto_vec <const bounded_ranges *> other_case_ranges
	(gimple_switch_num_labels (switch_stmt));
      for (unsigned other_idx = 1;
	   other_idx < gimple_switch_num_labels (switch_stmt);
	   other_idx++)
	{
	  tree other_label = gimple_switch_label (switch_stmt,
						  other_idx);
	  const bounded_ranges *other_ranges
	    = make_case_label_ranges (switch_stmt, other_label);
	  other_case_ranges.quick_push (other_ranges);
	}
      const bounded_ranges *other_cases_ranges
	= get_or_create_union (other_case_ranges);
      tree type = TREE_TYPE (gimple_switch_index (switch_stmt));
      return get_or_create_inverse (other_cases_ranges, type);
    }
}

/* Dump the number of objects of each class that were managed by this
   manager to LOGGER.
   If SHOW_OBJS is true, also dump the objects themselves.  */

void
bounded_ranges_manager::log_stats (logger *logger, bool show_objs) const
{
  LOG_SCOPE (logger);
  logger->log ("  # %s: %li", "ranges", m_map.elements ());
  if (!show_objs)
    return;

  auto_vec<const bounded_ranges *> vec_objs (m_map.elements ());
  for (const auto &iter : m_map)
    vec_objs.quick_push (iter.second);
  vec_objs.qsort
    ([](const void *p1, const void *p2) -> int
     {
       const bounded_ranges *br1 = *(const bounded_ranges * const *)p1;
       const bounded_ranges *br2 = *(const bounded_ranges * const *)p2;
       return bounded_ranges::cmp (br1, br2);
     });

  for (const auto &iter : vec_objs)
    {
      logger->start_log_line ();
      pretty_printer *pp = logger->get_printer ();
      pp_string (pp, "    ");
      iter->dump_to_pp (pp, true);
      logger->end_log_line ();
    }
}

/* class equiv_class.  */

/* equiv_class's default ctor.  */

equiv_class::equiv_class ()
: m_constant (NULL_TREE), m_cst_sval (NULL), m_vars ()
{
}

/* equiv_class's copy ctor.  */

equiv_class::equiv_class (const equiv_class &other)
: m_constant (other.m_constant), m_cst_sval (other.m_cst_sval),
  m_vars (other.m_vars.length ())
{
  for (const svalue *sval : other.m_vars)
    m_vars.quick_push (sval);
}

/* Print an all-on-one-line representation of this equiv_class to PP,
   which must support %E for trees.  */

void
equiv_class::print (pretty_printer *pp) const
{
  pp_character (pp, '{');
  int i;
  const svalue *sval;
  FOR_EACH_VEC_ELT (m_vars, i, sval)
    {
      if (i > 0)
	pp_string (pp, " == ");
      sval->dump_to_pp (pp, true);
    }
  if (m_constant)
    {
      if (i > 0)
	pp_string (pp, " == ");
      pp_printf (pp, "[m_constant]%qE", m_constant);
    }
  pp_character (pp, '}');
}

/* Return a new json::object of the form
   {"svals" : [str],
    "constant" : optional str}.  */

json::object *
equiv_class::to_json () const
{
  json::object *ec_obj = new json::object ();

  json::array *sval_arr = new json::array ();
  for (const svalue *sval : m_vars)
    sval_arr->append (sval->to_json ());
  ec_obj->set ("svals", sval_arr);

  if (m_constant)
    {
      pretty_printer pp;
      pp_format_decoder (&pp) = default_tree_printer;
      pp_printf (&pp, "%qE", m_constant);
      ec_obj->set ("constant", new json::string (pp_formatted_text (&pp)));
    }

  return ec_obj;
}

/* Generate a hash value for this equiv_class.
   This relies on the ordering of m_vars, and so this object needs to
   have been canonicalized for this to be meaningful.  */

hashval_t
equiv_class::hash () const
{
  inchash::hash hstate;

  inchash::add_expr (m_constant, hstate);
  for (const svalue * sval : m_vars)
    hstate.add_ptr (sval);
  return hstate.end ();
}

/* Equality operator for equiv_class.
   This relies on the ordering of m_vars, and so this object
   and OTHER need to have been canonicalized for this to be
   meaningful.  */

bool
equiv_class::operator== (const equiv_class &other)
{
  if (m_constant != other.m_constant)
    return false; // TODO: use tree equality here?

  /* FIXME: should we compare m_cst_sval?  */

  if (m_vars.length () != other.m_vars.length ())
    return false;

  int i;
  const svalue *sval;
  FOR_EACH_VEC_ELT (m_vars, i, sval)
    if (sval != other.m_vars[i])
      return false;

  return true;
}

/* Add SID to this equiv_class, using CM to check if it's a constant.  */

void
equiv_class::add (const svalue *sval)
{
  gcc_assert (sval);
  if (tree cst = sval->maybe_get_constant ())
    {
      gcc_assert (CONSTANT_CLASS_P (cst));
      /* FIXME: should we canonicalize which svalue is the constant
	 when there are multiple equal constants?  */
      m_constant = cst;
      m_cst_sval = sval;
    }
  m_vars.safe_push (sval);
}

/* Remove SID from this equivalence class.
   Return true if SID was the last var in the equivalence class (suggesting
   a possible leak).  */

bool
equiv_class::del (const svalue *sval)
{
  gcc_assert (sval);
  gcc_assert (sval != m_cst_sval);

  int i;
  const svalue *iv;
  FOR_EACH_VEC_ELT (m_vars, i, iv)
    {
      if (iv == sval)
	{
	  m_vars[i] = m_vars[m_vars.length () - 1];
	  m_vars.pop ();
	  return m_vars.length () == 0;
	}
    }

  /* SVAL must be in the class.  */
  gcc_unreachable ();
  return false;
}

/* Get a representative member of this class, for handling cases
   where the IDs can change mid-traversal.  */

const svalue *
equiv_class::get_representative () const
{
  gcc_assert (m_vars.length () > 0);
  return m_vars[0];
}

/* Sort the svalues within this equiv_class.  */

void
equiv_class::canonicalize ()
{
  m_vars.qsort (svalue::cmp_ptr_ptr);
}

/* Get a debug string for C_OP.  */

const char *
constraint_op_code (enum constraint_op c_op)
{
  switch (c_op)
    {
    default:
      gcc_unreachable ();
    case CONSTRAINT_NE: return "!=";
    case CONSTRAINT_LT: return "<";
    case CONSTRAINT_LE: return "<=";
    }
}

/* Convert C_OP to an enum tree_code.  */

enum tree_code
constraint_tree_code (enum constraint_op c_op)
{
  switch (c_op)
    {
    default:
      gcc_unreachable ();
    case CONSTRAINT_NE: return NE_EXPR;
    case CONSTRAINT_LT: return LT_EXPR;
    case CONSTRAINT_LE: return LE_EXPR;
    }
}

/* Given "lhs C_OP rhs", determine "lhs T_OP rhs".

   For example, given "x < y", then "x > y" is false.  */

static tristate
eval_constraint_op_for_op (enum constraint_op c_op, enum tree_code t_op)
{
  switch (c_op)
    {
    default:
      gcc_unreachable ();
    case CONSTRAINT_NE:
      if (t_op == EQ_EXPR)
	return tristate (tristate::TS_FALSE);
      if (t_op == NE_EXPR)
	return tristate (tristate::TS_TRUE);
      break;
    case CONSTRAINT_LT:
      if (t_op == LT_EXPR || t_op == LE_EXPR || t_op == NE_EXPR)
	return tristate (tristate::TS_TRUE);
      if (t_op == EQ_EXPR || t_op == GT_EXPR || t_op == GE_EXPR)
	return tristate (tristate::TS_FALSE);
      break;
    case CONSTRAINT_LE:
      if (t_op == LE_EXPR)
	return tristate (tristate::TS_TRUE);
      if (t_op == GT_EXPR)
	return tristate (tristate::TS_FALSE);
      break;
    }
  return tristate (tristate::TS_UNKNOWN);
}

/* class constraint.  */

/* Print this constraint to PP (which must support %E for trees),
   using CM to look up equiv_class instances from ids.  */

void
constraint::print (pretty_printer *pp, const constraint_manager &cm) const
{
  m_lhs.print (pp);
  pp_string (pp, ": ");
  m_lhs.get_obj (cm).print (pp);
  pp_string (pp, " ");
  pp_string (pp, constraint_op_code (m_op));
  pp_string (pp, " ");
  m_rhs.print (pp);
  pp_string (pp, ": ");
  m_rhs.get_obj (cm).print (pp);
}

/* Return a new json::object of the form
   {"lhs" : int, the EC index
    "op"  : str,
    "rhs" : int, the EC index}.  */

json::object *
constraint::to_json () const
{
  json::object *con_obj = new json::object ();

  con_obj->set ("lhs", new json::integer_number (m_lhs.as_int ()));
  con_obj->set ("op", new json::string (constraint_op_code (m_op)));
  con_obj->set ("rhs", new json::integer_number (m_rhs.as_int ()));

  return con_obj;
}

/* Generate a hash value for this constraint.  */

hashval_t
constraint::hash () const
{
  inchash::hash hstate;
  hstate.add_int (m_lhs.m_idx);
  hstate.add_int (m_op);
  hstate.add_int (m_rhs.m_idx);
  return hstate.end ();
}

/* Equality operator for constraints.  */

bool
constraint::operator== (const constraint &other) const
{
  if (m_lhs != other.m_lhs)
    return false;
  if (m_op != other.m_op)
    return false;
  if (m_rhs != other.m_rhs)
    return false;
  return true;
}

/* Return true if this constraint is implied by OTHER.  */

bool
constraint::implied_by (const constraint &other,
			 const constraint_manager &cm) const
{
  if (m_lhs == other.m_lhs)
    if (tree rhs_const = m_rhs.get_obj (cm).get_any_constant ())
      if (tree other_rhs_const = other.m_rhs.get_obj (cm).get_any_constant ())
	if (m_lhs.get_obj (cm).get_any_constant () == NULL_TREE)
	  if (m_op == other.m_op)
	    switch (m_op)
	      {
	      default:
		break;
	      case CONSTRAINT_LE:
	      case CONSTRAINT_LT:
		if (compare_constants (rhs_const,
				       GE_EXPR,
				       other_rhs_const).is_true ())
		  return true;
		break;
	      }
  return false;
}

/* class bounded_ranges_constraint.  */

void
bounded_ranges_constraint::print (pretty_printer *pp,
				  const constraint_manager &cm) const
{
  m_ec_id.print (pp);
  pp_string (pp, ": ");
  m_ec_id.get_obj (cm).print (pp);
  pp_string (pp, ": ");
  m_ranges->dump_to_pp (pp, true);
}

json::object *
bounded_ranges_constraint::to_json () const
{
  json::object *con_obj = new json::object ();

  con_obj->set ("ec", new json::integer_number (m_ec_id.as_int ()));
  con_obj->set ("ranges", m_ranges->to_json ());

  return con_obj;
}

bool
bounded_ranges_constraint::
operator== (const bounded_ranges_constraint &other) const
{
  if (m_ec_id != other.m_ec_id)
    return false;

  /* We can compare by pointer, since the bounded_ranges_manager
     consolidates instances.  */
  return m_ranges == other.m_ranges;
}

void
bounded_ranges_constraint::add_to_hash (inchash::hash *hstate) const
{
  hstate->add_int (m_ec_id.m_idx);
  hstate->merge_hash (m_ranges->get_hash ());
}

/* class equiv_class_id.  */

/* Get the underlying equiv_class for this ID from CM.  */

const equiv_class &
equiv_class_id::get_obj (const constraint_manager &cm) const
{
  return cm.get_equiv_class_by_index (m_idx);
}

/* Access the underlying equiv_class for this ID from CM.  */

equiv_class &
equiv_class_id::get_obj (constraint_manager &cm) const
{
  return cm.get_equiv_class_by_index (m_idx);
}

/* Print this equiv_class_id to PP.  */

void
equiv_class_id::print (pretty_printer *pp) const
{
  if (null_p ())
    pp_printf (pp, "null");
  else
    pp_printf (pp, "ec%i", m_idx);
}

/* class constraint_manager.  */

/* constraint_manager's copy ctor.  */

constraint_manager::constraint_manager (const constraint_manager &other)
: m_equiv_classes (other.m_equiv_classes.length ()),
  m_constraints (other.m_constraints.length ()),
  m_bounded_ranges_constraints (other.m_bounded_ranges_constraints.length ()),
  m_mgr (other.m_mgr)
{
  int i;
  equiv_class *ec;
  FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
    m_equiv_classes.quick_push (new equiv_class (*ec));
  constraint *c;
  FOR_EACH_VEC_ELT (other.m_constraints, i, c)
    m_constraints.quick_push (*c);
  for (const auto &iter : other.m_bounded_ranges_constraints)
    m_bounded_ranges_constraints.quick_push (iter);
}

/* constraint_manager's assignment operator.  */

constraint_manager&
constraint_manager::operator= (const constraint_manager &other)
{
  gcc_assert (m_equiv_classes.length () == 0);
  gcc_assert (m_constraints.length () == 0);
  gcc_assert (m_bounded_ranges_constraints.length () == 0);

  int i;
  equiv_class *ec;
  m_equiv_classes.reserve (other.m_equiv_classes.length ());
  FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
    m_equiv_classes.quick_push (new equiv_class (*ec));
  constraint *c;
  m_constraints.reserve (other.m_constraints.length ());
  FOR_EACH_VEC_ELT (other.m_constraints, i, c)
    m_constraints.quick_push (*c);
  for (const auto &iter : other.m_bounded_ranges_constraints)
    m_bounded_ranges_constraints.quick_push (iter);

  return *this;
}

/* Generate a hash value for this constraint_manager.  */

hashval_t
constraint_manager::hash () const
{
  inchash::hash hstate;
  int i;
  equiv_class *ec;
  constraint *c;

  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    hstate.merge_hash (ec->hash ());
  FOR_EACH_VEC_ELT (m_constraints, i, c)
    hstate.merge_hash (c->hash ());
  for (const auto &iter : m_bounded_ranges_constraints)
    iter.add_to_hash (&hstate);
  return hstate.end ();
}

/* Equality operator for constraint_manager.  */

bool
constraint_manager::operator== (const constraint_manager &other) const
{
  if (m_equiv_classes.length () != other.m_equiv_classes.length ())
    return false;
  if (m_constraints.length () != other.m_constraints.length ())
    return false;
  if (m_bounded_ranges_constraints.length ()
      != other.m_bounded_ranges_constraints.length ())
    return false;

  int i;
  equiv_class *ec;

  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    if (!(*ec == *other.m_equiv_classes[i]))
      return false;

  constraint *c;

  FOR_EACH_VEC_ELT (m_constraints, i, c)
    if (!(*c == other.m_constraints[i]))
      return false;

  for (unsigned i = 0; i < m_bounded_ranges_constraints.length (); i++)
    {
      if (m_bounded_ranges_constraints[i]
	  != other.m_bounded_ranges_constraints[i])
	return false;
    }

  return true;
}

/* Print this constraint_manager to PP (which must support %E for trees).  */

void
constraint_manager::print (pretty_printer *pp) const
{
  pp_string (pp, "{");
  int i;
  equiv_class *ec;
  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    {
      if (i > 0)
	pp_string (pp, ", ");
      equiv_class_id (i).print (pp);
      pp_string (pp, ": ");
      ec->print (pp);
    }
  pp_string (pp, "  |  ");
  constraint *c;
  FOR_EACH_VEC_ELT (m_constraints, i, c)
    {
      if (i > 0)
	pp_string (pp, " && ");
      c->print (pp, *this);
    }
  if (m_bounded_ranges_constraints.length ())
    {
      pp_string (pp, "  |  ");
      i = 0;
      for (const auto &iter : m_bounded_ranges_constraints)
	{
	  if (i > 0)
	    pp_string (pp, " && ");
	  iter.print (pp, *this);
	  i++;
	}
    }
  pp_printf (pp, "}");
}

/* Dump a representation of this constraint_manager to PP
   (which must support %E for trees).  */

void
constraint_manager::dump_to_pp (pretty_printer *pp, bool multiline) const
{
  if (multiline)
    pp_string (pp, "  ");
  pp_string (pp, "equiv classes:");
  if (multiline)
    pp_newline (pp);
  else
    pp_string (pp, " {");
  int i;
  equiv_class *ec;
  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    {
      if (multiline)
	pp_string (pp, "    ");
      else if (i > 0)
	pp_string (pp, ", ");
      equiv_class_id (i).print (pp);
      pp_string (pp, ": ");
      ec->print (pp);
      if (multiline)
	pp_newline (pp);
    }
  if (multiline)
    pp_string (pp, "  ");
  else
    pp_string (pp, "}");
  pp_string (pp, "constraints:");
  if (multiline)
    pp_newline (pp);
  else
    pp_string (pp, "{");
  constraint *c;
  FOR_EACH_VEC_ELT (m_constraints, i, c)
    {
      if (multiline)
	pp_string (pp, "    ");
      pp_printf (pp, "%i: ", i);
      c->print (pp, *this);
      if (multiline)
	pp_newline (pp);
    }
  if (!multiline)
    pp_string (pp, "}");
  if (m_bounded_ranges_constraints.length ())
    {
      if (multiline)
	pp_string (pp, "  ");
      pp_string (pp, "ranges:");
      if (multiline)
	pp_newline (pp);
      else
	pp_string (pp, "{");
      i = 0;
      for (const auto &iter : m_bounded_ranges_constraints)
	{
	  if (multiline)
	    pp_string (pp, "    ");
	  else if (i > 0)
	    pp_string (pp, " && ");
	  iter.print (pp, *this);
	  if (multiline)
	    pp_newline (pp);
	  i++;
	}
      if (!multiline)
	pp_string (pp, "}");
      }
}

/* Dump a multiline representation of this constraint_manager to FP.  */

void
constraint_manager::dump (FILE *fp) const
{
  pretty_printer pp;
  pp_format_decoder (&pp) = default_tree_printer;
  pp_show_color (&pp) = pp_show_color (global_dc->printer);
  pp.buffer->stream = fp;
  dump_to_pp (&pp, true);
  pp_flush (&pp);
}

/* Dump a multiline representation of this constraint_manager to stderr.  */

DEBUG_FUNCTION void
constraint_manager::dump () const
{
  dump (stderr);
}

/* Dump a multiline representation of CM to stderr.  */

DEBUG_FUNCTION void
debug (const constraint_manager &cm)
{
  cm.dump ();
}

/* Return a new json::object of the form
   {"ecs" : array of objects, one per equiv_class
    "constraints" : array of objects, one per constraint}.  */

json::object *
constraint_manager::to_json () const
{
  json::object *cm_obj = new json::object ();

  /* Equivalence classes.  */
  {
    json::array *ec_arr = new json::array ();
    for (const equiv_class *ec : m_equiv_classes)
      ec_arr->append (ec->to_json ());
    cm_obj->set ("ecs", ec_arr);
  }

  /* Constraints.  */
  {
    json::array *con_arr = new json::array ();
    for (const constraint &c : m_constraints)
      con_arr->append (c.to_json ());
    cm_obj->set ("constraints", con_arr);
  }

  /* m_bounded_ranges_constraints.  */
  {
    json::array *con_arr = new json::array ();
    for (const auto &c : m_bounded_ranges_constraints)
      con_arr->append (c.to_json ());
    cm_obj->set ("bounded_ranges_constraints", con_arr);
  }

  return cm_obj;
}

/* Attempt to add the constraint LHS OP RHS to this constraint_manager.
   Return true if the constraint could be added (or is already true).
   Return false if the constraint contradicts existing knowledge.  */

bool
constraint_manager::add_constraint (const svalue *lhs,
				     enum tree_code op,
				     const svalue *rhs)
{
  lhs = lhs->unwrap_any_unmergeable ();
  rhs = rhs->unwrap_any_unmergeable ();

  /* Nothing can be known about unknown/poisoned values.  */
  if (!lhs->can_have_associated_state_p ()
      || !rhs->can_have_associated_state_p ())
    /* Not a contradiction.  */
    return true;

  /* Check the conditions on svalues.  */
  {
    tristate t_cond = eval_condition (lhs, op, rhs);

    /* If we already have the condition, do nothing.  */
    if (t_cond.is_true ())
      return true;

    /* Reject a constraint that would contradict existing knowledge, as
       unsatisfiable.  */
    if (t_cond.is_false ())
      return false;
  }

  equiv_class_id lhs_ec_id = get_or_add_equiv_class (lhs);
  equiv_class_id rhs_ec_id = get_or_add_equiv_class (rhs);

  /* Check the stronger conditions on ECs.  */
  {
    tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);

    /* Discard constraints that are already known.  */
    if (t.is_true ())
      return true;

    /* Reject unsatisfiable constraints.  */
    if (t.is_false ())
      return false;
  }

  add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
  return true;
}

/* Attempt to add the constraint LHS_EC_ID OP RHS_EC_ID to this
   constraint_manager.
   Return true if the constraint could be added (or is already true).
   Return false if the constraint contradicts existing knowledge.  */

bool
constraint_manager::add_constraint (equiv_class_id lhs_ec_id,
				     enum tree_code op,
				     equiv_class_id rhs_ec_id)
{
  tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);

  /* Discard constraints that are already known.  */
  if (t.is_true ())
    return true;

  /* Reject unsatisfiable constraints.  */
  if (t.is_false ())
    return false;

  add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
  return true;
}

/* Add the constraint LHS_EC_ID OP RHS_EC_ID to this constraint_manager,
   where the constraint has already been checked for being "unknown".  */

void
constraint_manager::add_unknown_constraint (equiv_class_id lhs_ec_id,
					     enum tree_code op,
					     equiv_class_id rhs_ec_id)
{
  gcc_assert (lhs_ec_id != rhs_ec_id);

  /* For now, simply accumulate constraints, without attempting any further
     optimization.  */
  switch (op)
    {
    case EQ_EXPR:
      {
	/* Merge rhs_ec into lhs_ec.  */
	equiv_class &lhs_ec_obj = lhs_ec_id.get_obj (*this);
	const equiv_class &rhs_ec_obj = rhs_ec_id.get_obj (*this);

	int i;
	const svalue *sval;
	FOR_EACH_VEC_ELT (rhs_ec_obj.m_vars, i, sval)
	  lhs_ec_obj.add (sval);

	if (rhs_ec_obj.m_constant)
	  {
	    lhs_ec_obj.m_constant = rhs_ec_obj.m_constant;
	    lhs_ec_obj.m_cst_sval = rhs_ec_obj.m_cst_sval;
	  }

	/* Drop rhs equivalence class, overwriting it with the
	   final ec (which might be the same one).  */
	equiv_class_id final_ec_id = m_equiv_classes.length () - 1;
	equiv_class *old_ec = m_equiv_classes[rhs_ec_id.m_idx];
	equiv_class *final_ec = m_equiv_classes.pop ();
	if (final_ec != old_ec)
	  m_equiv_classes[rhs_ec_id.m_idx] = final_ec;
	delete old_ec;
	if (lhs_ec_id == final_ec_id)
	  lhs_ec_id = rhs_ec_id;

	/* Update the constraints.  */
	constraint *c;
	FOR_EACH_VEC_ELT (m_constraints, i, c)
	  {
	    /* Update references to the rhs_ec so that
	       they refer to the lhs_ec.  */
	    if (c->m_lhs == rhs_ec_id)
	      c->m_lhs = lhs_ec_id;
	    if (c->m_rhs == rhs_ec_id)
	      c->m_rhs = lhs_ec_id;

	    /* Renumber all constraints that refer to the final rhs_ec
	       to the old rhs_ec, where the old final_ec now lives.  */
	    if (c->m_lhs == final_ec_id)
	      c->m_lhs = rhs_ec_id;
	    if (c->m_rhs == final_ec_id)
	      c->m_rhs = rhs_ec_id;
	  }
	bounded_ranges_constraint *brc;
	FOR_EACH_VEC_ELT (m_bounded_ranges_constraints, i, brc)
	  {
	    if (brc->m_ec_id == rhs_ec_id)
	      brc->m_ec_id = lhs_ec_id;
	    if (brc->m_ec_id == final_ec_id)
	      brc->m_ec_id = rhs_ec_id;
	  }

	/* We may now have self-comparisons due to the merger; these
	   constraints should be removed.  */
	unsigned read_index, write_index;
	VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
			       (c->m_lhs == c->m_rhs));
      }
      break;
    case GE_EXPR:
      add_constraint_internal (rhs_ec_id, CONSTRAINT_LE, lhs_ec_id);
      break;
    case LE_EXPR:
      add_constraint_internal (lhs_ec_id, CONSTRAINT_LE, rhs_ec_id);
      break;
    case NE_EXPR:
      add_constraint_internal (lhs_ec_id, CONSTRAINT_NE, rhs_ec_id);
      break;
    case GT_EXPR:
      add_constraint_internal (rhs_ec_id, CONSTRAINT_LT, lhs_ec_id);
      break;
    case LT_EXPR:
      add_constraint_internal (lhs_ec_id, CONSTRAINT_LT, rhs_ec_id);
      break;
    default:
      /* do nothing.  */
      break;
    }
  validate ();
}

/* Subroutine of constraint_manager::add_constraint, for handling all
   operations other than equality (for which equiv classes are merged).  */

void
constraint_manager::add_constraint_internal (equiv_class_id lhs_id,
					     enum constraint_op c_op,
					     equiv_class_id rhs_id)
{
  if (m_constraints.length () >= (unsigned)param_analyzer_max_constraints)
    return;

  constraint new_c (lhs_id, c_op, rhs_id);

  /* Remove existing constraints that would be implied by the
     new constraint.  */
  unsigned read_index, write_index;
  constraint *c;
  VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
			 (c->implied_by (new_c, *this)));

  /* Add the constraint.  */
  m_constraints.safe_push (new_c);

  /* We don't yet update m_bounded_ranges_constraints here yet.  */

  if (!flag_analyzer_transitivity)
    return;

  if (c_op != CONSTRAINT_NE)
    {
      /* The following can potentially add EQ_EXPR facts, which could lead
	 to ECs being merged, which would change the meaning of the EC IDs.
	 Hence we need to do this via representatives.  */
      const svalue *lhs = lhs_id.get_obj (*this).get_representative ();
      const svalue *rhs = rhs_id.get_obj (*this).get_representative ();

      /* We have LHS </<= RHS */

      /* Handle transitivity of ordering by adding additional constraints
	 based on what we already knew.

	 So if we have already have:
	   (a < b)
	   (c < d)
	 Then adding:
	   (b < c)
	 will also add:
	   (a < c)
	   (b < d)
	 We need to recurse to ensure we also add:
	   (a < d).
	 We call the checked add_constraint to avoid adding constraints
	 that are already present.  Doing so also ensures termination
	 in the case of cycles.

	 We also check for single-element ranges, adding EQ_EXPR facts
	 where we discover them.  For example 3 < x < 5 implies
	 that x == 4 (if x is an integer).  */
      for (unsigned i = 0; i < m_constraints.length (); i++)
	{
	  const constraint *other = &m_constraints[i];
	  if (other->is_ordering_p ())
	    {
	      /* Refresh the EC IDs, in case any mergers have happened.  */
	      lhs_id = get_or_add_equiv_class (lhs);
	      rhs_id = get_or_add_equiv_class (rhs);

	      tree lhs_const = lhs_id.get_obj (*this).m_constant;
	      tree rhs_const = rhs_id.get_obj (*this).m_constant;
	      tree other_lhs_const
		= other->m_lhs.get_obj (*this).m_constant;
	      tree other_rhs_const
		= other->m_rhs.get_obj (*this).m_constant;

	      /* We have "LHS </<= RHS" and "other.lhs </<= other.rhs".  */

	      /* If we have LHS </<= RHS and RHS </<= LHS, then we have a
		 cycle.  */
	      if (rhs_id == other->m_lhs
		  && other->m_rhs == lhs_id)
		{
		  /* We must have equality for this to be possible.  */
		  gcc_assert (c_op == CONSTRAINT_LE
			      && other->m_op == CONSTRAINT_LE);
		  add_constraint (lhs_id, EQ_EXPR, rhs_id);
		  /* Adding an equality will merge the two ECs and potentially
		     reorganize the constraints.  Stop iterating.  */
		  return;
		}
	      /* Otherwise, check for transitivity.  */
	      if (rhs_id == other->m_lhs)
		{
		  /* With RHS == other.lhs, we have:
		     "LHS </<= (RHS, other.lhs) </<= other.rhs"
		     and thus this implies "LHS </<= other.rhs".  */

		  /* Do we have a tightly-constrained range?  */
		  if (lhs_const
		      && !rhs_const
		      && other_rhs_const)
		    {
		      range r (bound (lhs_const, c_op == CONSTRAINT_LE),
			       bound (other_rhs_const,
				      other->m_op == CONSTRAINT_LE));
		      if (tree constant = r.constrained_to_single_element ())
			{
			  const svalue *cst_sval
			    = m_mgr->get_or_create_constant_svalue (constant);
			  add_constraint
			    (rhs_id, EQ_EXPR,
			     get_or_add_equiv_class (cst_sval));
			  return;
			}
		    }

		  /* Otherwise, add the constraint implied by transitivity.  */
		  enum tree_code new_op
		    = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
		       ? LE_EXPR : LT_EXPR);
		  add_constraint (lhs_id, new_op, other->m_rhs);
		}
	      else if (other->m_rhs == lhs_id)
		{
		  /* With other.rhs == LHS, we have:
		     "other.lhs </<= (other.rhs, LHS) </<= RHS"
		     and thus this implies "other.lhs </<= RHS".  */

		  /* Do we have a tightly-constrained range?  */
		  if (other_lhs_const
		      && !lhs_const
		      && rhs_const)
		    {
		      range r (bound (other_lhs_const,
				      other->m_op == CONSTRAINT_LE),
			       bound (rhs_const,
				      c_op == CONSTRAINT_LE));
		      if (tree constant = r.constrained_to_single_element ())
			{
			  const svalue *cst_sval
			    = m_mgr->get_or_create_constant_svalue (constant);
			  add_constraint
			    (lhs_id, EQ_EXPR,
			     get_or_add_equiv_class (cst_sval));
			  return;
			}
		    }

		  /* Otherwise, add the constraint implied by transitivity.  */
		  enum tree_code new_op
		    = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
		       ? LE_EXPR : LT_EXPR);
		  add_constraint (other->m_lhs, new_op, rhs_id);
		}
	    }
	}
    }
}

/* Attempt to add the constraint that SVAL is within RANGES to this
   constraint_manager.

   Return true if the constraint was successfully added (or is already
   known to be true).
   Return false if the constraint contradicts existing knowledge.  */

bool
constraint_manager::add_bounded_ranges (const svalue *sval,
					const bounded_ranges *ranges)
{
  sval = sval->unwrap_any_unmergeable ();

  /* Nothing can be known about unknown/poisoned values.  */
  if (!sval->can_have_associated_state_p ())
    /* Not a contradiction.  */
    return true;

  /* If SVAL is a constant, then we can look at RANGES directly.  */
  if (tree cst = sval->maybe_get_constant ())
    {
      /* If the ranges contain CST, then it's a successful no-op;
	 otherwise it's a contradiction.  */
      return ranges->contain_p (cst);
    }

  equiv_class_id ec_id = get_or_add_equiv_class (sval);

  /* If the EC has a constant, it's either true or false.  */
  const equiv_class &ec = ec_id.get_obj (*this);
  if (tree ec_cst = ec.get_any_constant ())
    {
      if (ranges->contain_p (ec_cst))
	/* We already have SVAL == EC_CST, within RANGES, so
	   we can discard RANGES and succeed.  */
	return true;
      else
	/* We already have SVAL == EC_CST, not within RANGES, so
	   we can reject RANGES as a contradiction.  */
	return false;
    }

  /* We have at most one per ec_id.  */
  /* Iterate through each range in RANGES.  */
  for (auto iter : m_bounded_ranges_constraints)
    {
      if (iter.m_ec_id == ec_id)
	{
	  /* Update with intersection, or fail if empty.  */
	  bounded_ranges_manager *mgr = get_range_manager ();
	  const bounded_ranges *intersection
	    = mgr->get_or_create_intersection (iter.m_ranges, ranges);
	  if (intersection->empty_p ())
	    {
	      /* No intersection; fail.  */
	      return false;
	    }
	  else
	    {
	      /* Update with intersection; succeed.  */
	      iter.m_ranges = intersection;
	      validate ();
	      return true;
	    }
	}
    }
  m_bounded_ranges_constraints.safe_push
    (bounded_ranges_constraint (ec_id, ranges));

  validate ();

  return true;
}

/* Look for SVAL within the equivalence classes of this constraint_manager;
   if found, return true, writing the id to *OUT if OUT is non-NULL,
   otherwise return false.  */

bool
constraint_manager::get_equiv_class_by_svalue (const svalue *sval,
					       equiv_class_id *out) const
{
  /* TODO: should we have a map, rather than these searches?  */
  int i;
  equiv_class *ec;
  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    {
      int j;
      const svalue *iv;
      FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
	if (iv == sval)
	  {
	    if (out)
	      *out = equiv_class_id (i);
	    return true;
	  }
    }
  return false;
}

/* Ensure that SVAL has an equivalence class within this constraint_manager;
   return the ID of the class.  */

equiv_class_id
constraint_manager::get_or_add_equiv_class (const svalue *sval)
{
  equiv_class_id result (-1);

  gcc_assert (sval->can_have_associated_state_p ());

  /* Convert all NULL pointers to (void *) to avoid state explosions
     involving all of the various (foo *)NULL vs (bar *)NULL.  */
  if (sval->get_type ())
    if (POINTER_TYPE_P (sval->get_type ()))
      if (tree cst = sval->maybe_get_constant ())
	if (zerop (cst))
	  sval = m_mgr->get_or_create_constant_svalue (null_pointer_node);

  /* Try svalue match.  */
  if (get_equiv_class_by_svalue (sval, &result))
    return result;

  /* Try equality of constants.  */
  if (tree cst = sval->maybe_get_constant ())
    {
      int i;
      equiv_class *ec;
      FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
	if (ec->m_constant
	    && types_compatible_p (TREE_TYPE (cst),
				   TREE_TYPE (ec->m_constant)))
	  {
	    tree eq = fold_binary (EQ_EXPR, boolean_type_node,
				   cst, ec->m_constant);
	    if (eq == boolean_true_node)
	      {
		ec->add (sval);
		return equiv_class_id (i);
	      }
	  }
    }


  /* Not found.  */
  equiv_class *new_ec = new equiv_class ();
  new_ec->add (sval);
  m_equiv_classes.safe_push (new_ec);

  equiv_class_id new_id (m_equiv_classes.length () - 1);

  return new_id;
}

/* Evaluate the condition LHS_EC OP RHS_EC.  */

tristate
constraint_manager::eval_condition (equiv_class_id lhs_ec,
				    enum tree_code op,
				    equiv_class_id rhs_ec) const
{
  if (lhs_ec == rhs_ec)
    {
      switch (op)
	{
	case EQ_EXPR:
	case GE_EXPR:
	case LE_EXPR:
	  return tristate (tristate::TS_TRUE);

	case NE_EXPR:
	case GT_EXPR:
	case LT_EXPR:
	  return tristate (tristate::TS_FALSE);
	default:
	  break;
	}
    }

  tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ();
  tree rhs_const = rhs_ec.get_obj (*this).get_any_constant ();
  if (lhs_const && rhs_const)
    {
      tristate result_for_constants
	= compare_constants (lhs_const, op, rhs_const);
      if (result_for_constants.is_known ())
	return result_for_constants;
    }

  enum tree_code swapped_op = swap_tree_comparison (op);

  int i;
  constraint *c;
  FOR_EACH_VEC_ELT (m_constraints, i, c)
    {
      if (c->m_lhs == lhs_ec
	  && c->m_rhs == rhs_ec)
	{
	  tristate result_for_constraint
	    = eval_constraint_op_for_op (c->m_op, op);
	  if (result_for_constraint.is_known ())
	    return result_for_constraint;
	}
      /* Swapped operands.  */
      if (c->m_lhs == rhs_ec
	  && c->m_rhs == lhs_ec)
	{
	  tristate result_for_constraint
	    = eval_constraint_op_for_op (c->m_op, swapped_op);
	  if (result_for_constraint.is_known ())
	    return result_for_constraint;
	}
    }

  /* We don't use m_bounded_ranges_constraints here yet.  */

  return tristate (tristate::TS_UNKNOWN);
}

range
constraint_manager::get_ec_bounds (equiv_class_id ec_id) const
{
  range result;

  int i;
  constraint *c;
  FOR_EACH_VEC_ELT (m_constraints, i, c)
    {
      if (c->m_lhs == ec_id)
	{
	  if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
	    switch (c->m_op)
	      {
	      default:
		gcc_unreachable ();
	      case CONSTRAINT_NE:
		continue;

	      case CONSTRAINT_LT:
		/* We have "EC_ID < OTHER_CST".  */
		result.m_upper_bound = bound (other_cst, false);
		break;

	      case CONSTRAINT_LE:
		/* We have "EC_ID <= OTHER_CST".  */
		result.m_upper_bound = bound (other_cst, true);
		break;
	      }
	}
      if (c->m_rhs == ec_id)
	{
	  if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
	    switch (c->m_op)
	      {
	      default:
		gcc_unreachable ();
	      case CONSTRAINT_NE:
		continue;

	      case CONSTRAINT_LT:
		/* We have "OTHER_CST < EC_ID"
		   i.e. "EC_ID > OTHER_CST".  */
		result.m_lower_bound = bound (other_cst, false);
		break;

	      case CONSTRAINT_LE:
		/* We have "OTHER_CST <= EC_ID"
		   i.e. "EC_ID >= OTHER_CST".  */
		result.m_lower_bound = bound (other_cst, true);
		break;
	      }
	}
    }

  return result;
}

/* Evaluate the condition LHS_EC OP RHS_CONST, avoiding the creation
   of equiv_class instances.  */

tristate
constraint_manager::eval_condition (equiv_class_id lhs_ec,
				    enum tree_code op,
				    tree rhs_const) const
{
  gcc_assert (!lhs_ec.null_p ());
  gcc_assert (CONSTANT_CLASS_P (rhs_const));

  if (tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ())
    return compare_constants (lhs_const, op, rhs_const);

  /* Check for known inequalities of the form
       (LHS_EC != OTHER_CST) or (OTHER_CST != LHS_EC).
     If RHS_CONST == OTHER_CST, then we also know that LHS_EC != OTHER_CST.
     For example, we might have the constraint
       ptr != (void *)0
     so we want the condition
       ptr == (foo *)0
     to be false.  */
  int i;
  constraint *c;
  FOR_EACH_VEC_ELT (m_constraints, i, c)
    {
      if (c->m_op == CONSTRAINT_NE)
	{
	  if (c->m_lhs == lhs_ec)
	    {
	      if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
		if (compare_constants
		      (rhs_const, EQ_EXPR, other_cst).is_true ())
		  {
		    switch (op)
		      {
		      case EQ_EXPR:
			return tristate (tristate::TS_FALSE);
		      case NE_EXPR:
			return tristate (tristate::TS_TRUE);
		      default:
			break;
		      }
		  }
	    }
	  if (c->m_rhs == lhs_ec)
	    {
	      if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
		if (compare_constants
		      (rhs_const, EQ_EXPR, other_cst).is_true ())
		  {
		    switch (op)
		      {
		      case EQ_EXPR:
			return tristate (tristate::TS_FALSE);
		      case NE_EXPR:
			return tristate (tristate::TS_TRUE);
		      default:
			break;
		      }
		  }
	    }
	}
    }

  bounded_ranges_manager *mgr = get_range_manager ();
  for (const auto &iter : m_bounded_ranges_constraints)
    if (iter.m_ec_id == lhs_ec)
      return iter.m_ranges->eval_condition (op, rhs_const, mgr);

  /* Look at existing bounds on LHS_EC.  */
  range lhs_bounds = get_ec_bounds (lhs_ec);
  return lhs_bounds.eval_condition (op, rhs_const);
}

/* Evaluate the condition LHS OP RHS, without modifying this
   constraint_manager (avoiding the creation of equiv_class instances).  */

tristate
constraint_manager::eval_condition (const svalue *lhs,
				    enum tree_code op,
				    const svalue *rhs) const
{
  lhs = lhs->unwrap_any_unmergeable ();
  rhs = rhs->unwrap_any_unmergeable ();

  /* Nothing can be known about unknown or poisoned values.  */
  if (lhs->get_kind () == SK_UNKNOWN
      || lhs->get_kind () == SK_POISONED
      || rhs->get_kind () == SK_UNKNOWN
      || rhs->get_kind () == SK_POISONED)
    return tristate (tristate::TS_UNKNOWN);

  if (lhs == rhs
      && !(FLOAT_TYPE_P (lhs->get_type ())
	   || FLOAT_TYPE_P (rhs->get_type ())))
    {
      switch (op)
	{
	case EQ_EXPR:
	case GE_EXPR:
	case LE_EXPR:
	  return tristate (tristate::TS_TRUE);

	case NE_EXPR:
	case GT_EXPR:
	case LT_EXPR:
	  return tristate (tristate::TS_FALSE);
	default:
	  break;
	}
    }

  equiv_class_id lhs_ec (-1);
  equiv_class_id rhs_ec (-1);
  get_equiv_class_by_svalue (lhs, &lhs_ec);
  get_equiv_class_by_svalue (rhs, &rhs_ec);
  if (!lhs_ec.null_p () && !rhs_ec.null_p ())
    {
      tristate result_for_ecs
	= eval_condition (lhs_ec, op, rhs_ec);
      if (result_for_ecs.is_known ())
	return result_for_ecs;
    }

  /* If at least one is not in an EC, we have no constraints
     comparing LHS and RHS yet.
     They might still be comparable if one (or both) is a constant.

     Alternatively, we can also get here if we had ECs but they weren't
     comparable.  Again, constant comparisons might give an answer.  */
  tree lhs_const = lhs->maybe_get_constant ();
  tree rhs_const = rhs->maybe_get_constant ();
  if (lhs_const && rhs_const)
    {
      tristate result_for_constants
	= compare_constants (lhs_const, op, rhs_const);
      if (result_for_constants.is_known ())
	return result_for_constants;
    }

  if (!lhs_ec.null_p ())
    {
      if (rhs_const)
	return eval_condition (lhs_ec, op, rhs_const);
    }
  if (!rhs_ec.null_p ())
    {
      if (lhs_const)
	{
	  enum tree_code swapped_op = swap_tree_comparison (op);
	  return eval_condition (rhs_ec, swapped_op, lhs_const);
	}
    }

  return tristate (tristate::TS_UNKNOWN);
}

/* Delete any information about svalues identified by P.
   Such instances are removed from equivalence classes, and any
   redundant ECs and constraints are also removed.
   Accumulate stats into STATS.  */

template <typename PurgeCriteria>
void
constraint_manager::purge (const PurgeCriteria &p, purge_stats *stats)
{
  /* Delete any svalues identified by P within the various equivalence
     classes.  */
  for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
    {
      equiv_class *ec = m_equiv_classes[ec_idx];

      int i;
      const svalue *sval;
      bool delete_ec = false;
      FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
	{
	  if (sval == ec->m_cst_sval)
	    continue;
	  if (p.should_purge_p (sval))
	    {
	      if (ec->del (sval))
		if (!ec->m_constant)
		  delete_ec = true;
	    }
	}

      if (delete_ec)
	{
	  delete ec;
	  m_equiv_classes.ordered_remove (ec_idx);
	  if (stats)
	    stats->m_num_equiv_classes++;

	  /* Update the constraints, potentially removing some.  */
	  for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
	    {
	      constraint *c = &m_constraints[con_idx];

	      /* Remove constraints that refer to the deleted EC.  */
	      if (c->m_lhs == ec_idx
		  || c->m_rhs == ec_idx)
		{
		  m_constraints.ordered_remove (con_idx);
		  if (stats)
		    stats->m_num_constraints++;
		}
	      else
		{
		  /* Renumber constraints that refer to ECs that have
		     had their idx changed.  */
		  c->m_lhs.update_for_removal (ec_idx);
		  c->m_rhs.update_for_removal (ec_idx);

		  con_idx++;
		}
	    }

	  /* Update bounded_ranges_constraint instances.  */
	  for (unsigned r_idx = 0;
	       r_idx < m_bounded_ranges_constraints.length (); )
	    {
	      bounded_ranges_constraint *brc
		= &m_bounded_ranges_constraints[r_idx];

	      /* Remove if it refers to the deleted EC.  */
	      if (brc->m_ec_id == ec_idx)
		{
		  m_bounded_ranges_constraints.ordered_remove (r_idx);
		  if (stats)
		    stats->m_num_bounded_ranges_constraints++;
		}
	      else
		{
		  /* Renumber any EC ids that refer to ECs that have
		     had their idx changed.  */
		  brc->m_ec_id.update_for_removal (ec_idx);
		  r_idx++;
		}
	    }
	}
      else
	ec_idx++;
    }

  /* Now delete any constraints that are purely between constants.  */
  for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
    {
      constraint *c = &m_constraints[con_idx];
      if (m_equiv_classes[c->m_lhs.m_idx]->m_vars.length () == 0
	  && m_equiv_classes[c->m_rhs.m_idx]->m_vars.length () == 0)
	{
	  m_constraints.ordered_remove (con_idx);
	  if (stats)
	    stats->m_num_constraints++;
	}
      else
	{
	  con_idx++;
	}
    }

  /* Finally, delete any ECs that purely contain constants and aren't
     referenced by any constraints.  */
  for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
    {
      equiv_class *ec = m_equiv_classes[ec_idx];
      if (ec->m_vars.length () == 0)
	{
	  equiv_class_id ec_id (ec_idx);
	  bool has_constraint = false;
	  for (unsigned con_idx = 0; con_idx < m_constraints.length ();
	       con_idx++)
	    {
	      constraint *c = &m_constraints[con_idx];
	      if (c->m_lhs == ec_id
		  || c->m_rhs == ec_id)
		{
		  has_constraint = true;
		  break;
		}
	    }
	  if (!has_constraint)
	    {
	      delete ec;
	      m_equiv_classes.ordered_remove (ec_idx);
	      if (stats)
		stats->m_num_equiv_classes++;

	      /* Renumber constraints that refer to ECs that have
		 had their idx changed.  */
	      for (unsigned con_idx = 0; con_idx < m_constraints.length ();
		   con_idx++)
		{
		  constraint *c = &m_constraints[con_idx];
		  c->m_lhs.update_for_removal (ec_idx);
		  c->m_rhs.update_for_removal (ec_idx);
		}

	      /* Likewise for m_bounded_ranges_constraints.  */
	      for (unsigned r_idx = 0;
		   r_idx < m_bounded_ranges_constraints.length ();
		   r_idx++)
		{
		  bounded_ranges_constraint *brc
		    = &m_bounded_ranges_constraints[r_idx];
		  brc->m_ec_id.update_for_removal (ec_idx);
		}

	      continue;
	    }
	}
      ec_idx++;
    }

  validate ();
}

/* Implementation of PurgeCriteria: purge svalues that are not live
   with respect to LIVE_SVALUES and MODEL.  */

class dead_svalue_purger
{
public:
  dead_svalue_purger (const svalue_set &live_svalues,
		      const region_model *model)
  : m_live_svalues (live_svalues), m_model (model)
  {
  }

  bool should_purge_p (const svalue *sval) const
  {
    return !sval->live_p (&m_live_svalues, m_model);
  }

private:
  const svalue_set &m_live_svalues;
  const region_model *m_model;
};

/* Purge dead svalues from equivalence classes and update constraints
   accordingly.  */

void
constraint_manager::
on_liveness_change (const svalue_set &live_svalues,
		    const region_model *model)
{
  dead_svalue_purger p (live_svalues, model);
  purge (p, NULL);
}

class svalue_purger
{
public:
  svalue_purger (const svalue *sval) : m_sval (sval) {}

  bool should_purge_p (const svalue *sval) const
  {
    return sval->involves_p (m_sval);
  }

private:
  const svalue *m_sval;
};

/* Purge any state involving SVAL.  */

void
constraint_manager::purge_state_involving (const svalue *sval)
{
  svalue_purger p (sval);
  purge (p, NULL);
}

/* Comparator for use by constraint_manager::canonicalize.
   Sort a pair of equiv_class instances, using the representative
   svalue as a sort key.  */

static int
equiv_class_cmp (const void *p1, const void *p2)
{
  const equiv_class *ec1 = *(const equiv_class * const *)p1;
  const equiv_class *ec2 = *(const equiv_class * const *)p2;

  const svalue *rep1 = ec1->get_representative ();
  const svalue *rep2 = ec2->get_representative ();

  gcc_assert (rep1);
  gcc_assert (rep2);

  return svalue::cmp_ptr (rep1, rep2);
}

/* Comparator for use by constraint_manager::canonicalize.
   Sort a pair of constraint instances.  */

static int
constraint_cmp (const void *p1, const void *p2)
{
  const constraint *c1 = (const constraint *)p1;
  const constraint *c2 = (const constraint *)p2;
  int lhs_cmp = c1->m_lhs.as_int () - c2->m_lhs.as_int ();
  if (lhs_cmp)
    return lhs_cmp;
  int rhs_cmp = c1->m_rhs.as_int () - c2->m_rhs.as_int ();
  if (rhs_cmp)
    return rhs_cmp;
  return c1->m_op - c2->m_op;
}

/* Purge redundant equivalence classes and constraints, and reorder them
   within this constraint_manager into a canonical order, to increase the
   chances of finding equality with another instance.  */

void
constraint_manager::canonicalize ()
{
  /* First, sort svalues within the ECs.  */
  unsigned i;
  equiv_class *ec;
  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    ec->canonicalize ();

  /* TODO: remove constraints where both sides have a constant, and are
     thus implicit.  But does this break transitivity?  */

  /* We will be purging and reordering ECs.
     We will need to remap the equiv_class_ids in the constraints,
     so we need to store the original index of each EC.
     Build a lookup table, mapping from the representative svalue
     to the original equiv_class_id of that svalue.  */
  hash_map<const svalue *, equiv_class_id> original_ec_id;
  const unsigned orig_num_equiv_classes = m_equiv_classes.length ();
  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    {
      const svalue *rep = ec->get_representative ();
      gcc_assert (rep);
      original_ec_id.put (rep, i);
    }

  /* Find ECs used by constraints.  */
  hash_set<const equiv_class *> used_ecs;
  constraint *c;
  FOR_EACH_VEC_ELT (m_constraints, i, c)
    {
      used_ecs.add (m_equiv_classes[c->m_lhs.as_int ()]);
      used_ecs.add (m_equiv_classes[c->m_rhs.as_int ()]);
    }

  for (const auto &iter : m_bounded_ranges_constraints)
    used_ecs.add (m_equiv_classes[iter.m_ec_id.as_int ()]);

  /* Purge unused ECs: those that aren't used by constraints and
     that effectively have only one svalue (either in m_constant
     or in m_vars).  */
  {
    /* "unordered remove if" from a vec.  */
    unsigned i = 0;
    while (i < m_equiv_classes.length ())
      {
	equiv_class *ec = m_equiv_classes[i];
	if (!used_ecs.contains (ec)
	    && ((ec->m_vars.length () < 2 && ec->m_constant == NULL_TREE)
		|| (ec->m_vars.length () == 0)))
	  {
	    m_equiv_classes.unordered_remove (i);
	    delete ec;
	  }
	else
	  i++;
      }
  }

  /* Next, sort the surviving ECs into a canonical order.  */
  m_equiv_classes.qsort (equiv_class_cmp);

  /* Populate ec_id_map based on the old vs new EC ids.  */
  one_way_id_map<equiv_class_id> ec_id_map (orig_num_equiv_classes);
  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    {
      const svalue *rep = ec->get_representative ();
      gcc_assert (rep);
      ec_id_map.put (*original_ec_id.get (rep), i);
    }

  /* Use ec_id_map to update the EC ids within the constraints.  */
  FOR_EACH_VEC_ELT (m_constraints, i, c)
    {
      ec_id_map.update (&c->m_lhs);
      ec_id_map.update (&c->m_rhs);
    }

  for (auto &iter : m_bounded_ranges_constraints)
    ec_id_map.update (&iter.m_ec_id);

  /* Finally, sort the constraints. */
  m_constraints.qsort (constraint_cmp);
}

/* Concrete subclass of fact_visitor for use by constraint_manager::merge.
   For every fact in CM_A, see if it is also true in *CM_B.  Add such
   facts to *OUT.  */

class merger_fact_visitor : public fact_visitor
{
public:
  merger_fact_visitor (const constraint_manager *cm_b,
		       constraint_manager *out)
  : m_cm_b (cm_b), m_out (out)
  {}

  void on_fact (const svalue *lhs, enum tree_code code, const svalue *rhs)
    FINAL OVERRIDE
  {
    /* Special-case for widening.  */
    if (lhs->get_kind () == SK_WIDENING)
      if (!m_cm_b->get_equiv_class_by_svalue (lhs, NULL))
	{
	  /* LHS isn't constrained within m_cm_b.  */
	  bool sat = m_out->add_constraint (lhs, code, rhs);
	  gcc_assert (sat);
	  return;
	}

    if (m_cm_b->eval_condition (lhs, code, rhs).is_true ())
      {
	bool sat = m_out->add_constraint (lhs, code, rhs);
	if (!sat)
	  {
	    /* If -fanalyzer-transitivity is off, we can encounter cases
	       where at least one of the two constraint_managers being merged
	       is infeasible, but we only discover that infeasibility
	       during merging (PR analyzer/96650).
	       Silently drop such constraints.  */
	    gcc_assert (!flag_analyzer_transitivity);
	  }
      }
  }

  void on_ranges (const svalue *lhs_sval,
		  const bounded_ranges *ranges) FINAL OVERRIDE
  {
    for (const auto &iter : m_cm_b->m_bounded_ranges_constraints)
      {
	const equiv_class &ec_rhs = iter.m_ec_id.get_obj (*m_cm_b);
	for (unsigned i = 0; i < ec_rhs.m_vars.length (); i++)
	  {
	    const svalue *rhs_sval = ec_rhs.m_vars[i];
	    if (lhs_sval == rhs_sval)
	      {
		/* Union of the two ranges.  */
		auto_vec <const bounded_ranges *> pair (2);
		pair.quick_push (ranges);
		pair.quick_push (iter.m_ranges);
		bounded_ranges_manager *ranges_mgr
		  = m_cm_b->get_range_manager ();
		const bounded_ranges *union_
		  = ranges_mgr->get_or_create_union (pair);
		bool sat = m_out->add_bounded_ranges (lhs_sval, union_);
		gcc_assert (sat);
	      }
	  }
      }
  }

private:
  const constraint_manager *m_cm_b;
  constraint_manager *m_out;
};

/* Use MERGER to merge CM_A and CM_B into *OUT.
   If one thinks of a constraint_manager as a subset of N-dimensional
   space, this takes the union of the points of CM_A and CM_B, and
   expresses that into *OUT.  Alternatively, it can be thought of
   as the intersection of the constraints.  */

void
constraint_manager::merge (const constraint_manager &cm_a,
			   const constraint_manager &cm_b,
			   constraint_manager *out)
{
  /* Merge the equivalence classes and constraints.
     The easiest way to do this seems to be to enumerate all of the facts
     in cm_a, see which are also true in cm_b,
     and add those to *OUT.  */
  merger_fact_visitor v (&cm_b, out);
  cm_a.for_each_fact (&v);
}

/* Call VISITOR's on_fact vfunc repeatedly to express the various
   equivalence classes and constraints.
   This is used by constraint_manager::merge to find the common
   facts between two input constraint_managers.  */

void
constraint_manager::for_each_fact (fact_visitor *visitor) const
{
  /* First, call EQ_EXPR within the various equivalence classes.  */
  unsigned ec_idx;
  equiv_class *ec;
  FOR_EACH_VEC_ELT (m_equiv_classes, ec_idx, ec)
    {
      if (ec->m_cst_sval)
	{
	  unsigned i;
	  const svalue *sval;
	  FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
	    visitor->on_fact (ec->m_cst_sval, EQ_EXPR, sval);
	}
      for (unsigned i = 0; i < ec->m_vars.length (); i++)
	for (unsigned j = i + 1; j < ec->m_vars.length (); j++)
	  visitor->on_fact (ec->m_vars[i], EQ_EXPR, ec->m_vars[j]);
    }

  /* Now, express the various constraints.  */
  unsigned con_idx;
  constraint *c;
  FOR_EACH_VEC_ELT (m_constraints, con_idx, c)
    {
      const equiv_class &ec_lhs = c->m_lhs.get_obj (*this);
      const equiv_class &ec_rhs = c->m_rhs.get_obj (*this);
      enum tree_code code = constraint_tree_code (c->m_op);

      if (ec_lhs.m_cst_sval)
	{
	  for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
	    {
	      visitor->on_fact (ec_lhs.m_cst_sval, code, ec_rhs.m_vars[j]);
	    }
	}
      for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
	{
	  if (ec_rhs.m_cst_sval)
	    visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_cst_sval);
	  for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
	    visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_vars[j]);
	}
    }

  for (const auto &iter : m_bounded_ranges_constraints)
    {
      const equiv_class &ec_lhs = iter.m_ec_id.get_obj (*this);
      for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
	{
	  const svalue *lhs_sval = ec_lhs.m_vars[i];
	  visitor->on_ranges (lhs_sval, iter.m_ranges);
	}
    }
}

/* Assert that this object is valid.  */

void
constraint_manager::validate () const
{
  /* Skip this in a release build.  */
#if !CHECKING_P
  return;
#endif

  int i;
  equiv_class *ec;
  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
    {
      gcc_assert (ec);

      int j;
      const svalue *sval;
      FOR_EACH_VEC_ELT (ec->m_vars, j, sval)
	gcc_assert (sval);
      if (ec->m_constant)
	{
	  gcc_assert (CONSTANT_CLASS_P (ec->m_constant));
	  gcc_assert (ec->m_cst_sval);
	}
#if 0
      else
	gcc_assert (ec->m_vars.length () > 0);
#endif
    }

  constraint *c;
  FOR_EACH_VEC_ELT (m_constraints, i, c)
    {
      gcc_assert (!c->m_lhs.null_p ());
      gcc_assert (c->m_lhs.as_int () < (int)m_equiv_classes.length ());
      gcc_assert (!c->m_rhs.null_p ());
      gcc_assert (c->m_rhs.as_int () < (int)m_equiv_classes.length ());
    }

  for (const auto &iter : m_bounded_ranges_constraints)
    {
      gcc_assert (!iter.m_ec_id.null_p ());
      gcc_assert (iter.m_ec_id.as_int () < (int)m_equiv_classes.length ());
    }
}

bounded_ranges_manager *
constraint_manager::get_range_manager () const
{
  return m_mgr->get_range_manager ();
}

#if CHECKING_P

namespace selftest {

/* Various constraint_manager selftests.
   These have to be written in terms of a region_model, since
   the latter is responsible for managing svalue instances.  */

/* Verify that setting and getting simple conditions within a region_model
   work (thus exercising the underlying constraint_manager).  */

static void
test_constraint_conditions ()
{
  tree int_42 = build_int_cst (integer_type_node, 42);
  tree int_0 = build_int_cst (integer_type_node, 0);

  tree x = build_global_decl ("x", integer_type_node);
  tree y = build_global_decl ("y", integer_type_node);
  tree z = build_global_decl ("z", integer_type_node);

  /* Self-comparisons.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, x);
    ASSERT_CONDITION_TRUE (model, x, LE_EXPR, x);
    ASSERT_CONDITION_TRUE (model, x, GE_EXPR, x);
    ASSERT_CONDITION_FALSE (model, x, NE_EXPR, x);
    ASSERT_CONDITION_FALSE (model, x, LT_EXPR, x);
    ASSERT_CONDITION_FALSE (model, x, GT_EXPR, x);
  }

  /* Adding self-equality shouldn't add equiv classes.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, x);
    ADD_SAT_CONSTRAINT (model, int_42, EQ_EXPR, int_42);
    /* ...even when done directly via svalues: */
    const svalue *sval_int_42 = model.get_rvalue (int_42, NULL);
    bool sat = model.get_constraints ()->add_constraint (sval_int_42,
							  EQ_EXPR,
							  sval_int_42);
    ASSERT_TRUE (sat);
    ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0);
  }

  /* x == y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);

    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);

    ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, NE_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);

    /* Swapped operands.  */
    ASSERT_CONDITION_TRUE (model, y, EQ_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
    ASSERT_CONDITION_FALSE (model, y, NE_EXPR, x);
    ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
    ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);

    /* Comparison with other var.  */
    ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
  }

  /* x == y, then y == z  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);

    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, z);

    ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, z);
    ASSERT_CONDITION_TRUE (model, x, LE_EXPR, z);
    ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
    ASSERT_CONDITION_FALSE (model, x, NE_EXPR, z);
    ASSERT_CONDITION_FALSE (model, x, LT_EXPR, z);
    ASSERT_CONDITION_FALSE (model, x, GT_EXPR, z);
  }

  /* x != y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);

    ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);

    ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);

    /* Swapped operands.  */
    ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
    ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);

    /* Comparison with other var.  */
    ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
  }

  /* x < y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);

    ADD_SAT_CONSTRAINT (model, x, LT_EXPR, y);

    ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);

    /* Swapped operands.  */
    ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
    ASSERT_CONDITION_FALSE (model, y, LE_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
    ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, GT_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
  }

  /* x <= y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);

    ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);

    ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);

    /* Swapped operands.  */
    ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
  }

  /* x > y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);

    ADD_SAT_CONSTRAINT (model, x, GT_EXPR, y);

    ASSERT_CONDITION_TRUE (model, x, GT_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, LE_EXPR, y);

    /* Swapped operands.  */
    ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
    ASSERT_CONDITION_FALSE (model, y, GE_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
    ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, LT_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
  }

  /* x >= y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);

    ADD_SAT_CONSTRAINT (model, x, GE_EXPR, y);

    ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);

    /* Swapped operands.  */
    ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
    ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
    ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
  }

  // TODO: implied orderings

  /* Constants.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ASSERT_CONDITION_FALSE (model, int_0, EQ_EXPR, int_42);
    ASSERT_CONDITION_TRUE (model, int_0, NE_EXPR, int_42);
    ASSERT_CONDITION_TRUE (model, int_0, LT_EXPR, int_42);
    ASSERT_CONDITION_TRUE (model, int_0, LE_EXPR, int_42);
    ASSERT_CONDITION_FALSE (model, int_0, GT_EXPR, int_42);
    ASSERT_CONDITION_FALSE (model, int_0, GE_EXPR, int_42);
  }

  /* x == 0, y == 42.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, int_42);

    ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);
    ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
    ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
  }

  /* Unsatisfiable combinations.  */

  /* x == y && x != y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
    ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, y);
  }

  /* x == 0 then x == 42.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, int_42);
  }

  /* x == 0 then x != 0.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, int_0);
  }

  /* x == 0 then x > 0.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, int_0);
  }

  /* x != y && x == y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
    ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, y);
  }

  /* x <= y && x > y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);
    ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, y);
  }

  // etc
}

/* Test transitivity of conditions.  */

static void
test_transitivity ()
{
  tree a = build_global_decl ("a", integer_type_node);
  tree b = build_global_decl ("b", integer_type_node);
  tree c = build_global_decl ("c", integer_type_node);
  tree d = build_global_decl ("d", integer_type_node);

  /* a == b, then c == d, then c == b.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, b);
    ASSERT_CONDITION_UNKNOWN (model, b, EQ_EXPR, c);
    ASSERT_CONDITION_UNKNOWN (model, c, EQ_EXPR, d);
    ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);

    ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, b);
    ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);

    ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, d);
    ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, d);
    ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);

    ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, b);
    ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, b);
    ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, d);
  }

  /* Transitivity: "a < b", "b < c" should imply "a < c".  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
    ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);

    ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
    ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
  }

  /* Transitivity: "a <= b", "b < c" should imply "a < c".  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
    ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);

    ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
    ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
  }

  /* Transitivity: "a <= b", "b <= c" should imply "a <= c".  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
    ADD_SAT_CONSTRAINT (model, b, LE_EXPR, c);

    ASSERT_CONDITION_TRUE (model, a, LE_EXPR, c);
    ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
  }

  /* Transitivity: "a > b", "b > c" should imply "a > c".  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
    ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);

    ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
    ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
  }

  /* Transitivity: "a >= b", "b > c" should imply " a > c".  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);

    ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
    ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
  }

  /* Transitivity: "a >= b", "b >= c" should imply "a >= c".  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);

    ASSERT_CONDITION_TRUE (model, a, GE_EXPR, c);
    ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
  }

  /* Transitivity: "(a < b)", "(c < d)", "(b < c)" should
     imply the easy cases:
       (a < c)
       (b < d)
     but also that:
       (a < d).  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
    ADD_SAT_CONSTRAINT (model, c, LT_EXPR, d);
    ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);

    ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
    ASSERT_CONDITION_TRUE (model, b, LT_EXPR, d);
    ASSERT_CONDITION_TRUE (model, a, LT_EXPR, d);
  }

  /* Transitivity: "a >= b", "b >= a" should imply that a == b.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    ADD_SAT_CONSTRAINT (model, b, GE_EXPR, a);

    // TODO:
    ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);

    /* The ECs for a and b should have merged, and any constraints removed.  */
    ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
    ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
  }

  /* Transitivity: "a >= b", "b > a" should be impossible.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    ADD_UNSAT_CONSTRAINT (model, b, GT_EXPR, a);
  }

  /* Transitivity: "a >= b", "b >= c", "c >= a" should imply
     that a == b == c.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
    ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);
    ADD_SAT_CONSTRAINT (model, c, GE_EXPR, a);

    ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, c);
  }

  /* Transitivity: "a > b", "b > c", "c > a"
     should be impossible.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
    ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
    ADD_UNSAT_CONSTRAINT (model, c, GT_EXPR, a);
  }

}

/* Test various conditionals involving constants where the results
   ought to be implied based on the values of the constants.  */

static void
test_constant_comparisons ()
{
  tree int_3 = build_int_cst (integer_type_node, 3);
  tree int_4 = build_int_cst (integer_type_node, 4);
  tree int_5 = build_int_cst (integer_type_node, 5);

  tree int_1023 = build_int_cst (integer_type_node, 1023);
  tree int_1024 = build_int_cst (integer_type_node, 1024);

  tree a = build_global_decl ("a", integer_type_node);
  tree b = build_global_decl ("b", integer_type_node);

  /* Given a >= 1024, then a <= 1023 should be impossible.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_1024);
    ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_1023);
  }

  /* a > 4.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_4);
    ASSERT_CONDITION_TRUE (model, a, GT_EXPR, int_4);
    ASSERT_CONDITION_TRUE (model, a, NE_EXPR, int_3);
    ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_5);
  }

  /* a <= 4.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
    ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_4);
    ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_5);
    ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_3);
  }

  /* If "a > b" and "a == 3", then "b == 4" ought to be unsatisfiable.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
    ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_3);
    ADD_UNSAT_CONSTRAINT (model, b, EQ_EXPR, int_4);
  }

  /* Various tests of int ranges where there is only one possible candidate.  */
  {
    /* If "a <= 4" && "a > 3", then "a == 4",
       assuming a is of integral type.  */
    {
      region_model_manager mgr;
      region_model model (&mgr);
      ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
      ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
      ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    }

    /* If "a > 3" && "a <= 4", then "a == 4",
       assuming a is of integral type.  */
    {
      region_model_manager mgr;
      region_model model (&mgr);
      ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
      ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
      ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    }
    /* If "a > 3" && "a < 5", then "a == 4",
       assuming a is of integral type.  */
    {
      region_model_manager mgr;
      region_model model (&mgr);
      ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
      ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
      ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    }
    /* If "a >= 4" && "a < 5", then "a == 4",
       assuming a is of integral type.  */
    {
      region_model_manager mgr;
      region_model model (&mgr);
      ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
      ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
      ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    }
    /* If "a >= 4" && "a <= 4", then "a == 4".  */
    {
      region_model_manager mgr;
      region_model model (&mgr);
      ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
      ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
      ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
    }
  }

  /* As above, but for floating-point:
     if "f > 3" && "f <= 4" we don't know that f == 4.  */
  {
    tree f = build_global_decl ("f", double_type_node);
    tree float_3 = build_real_from_int_cst (double_type_node, int_3);
    tree float_4 = build_real_from_int_cst (double_type_node, int_4);

    region_model_manager mgr;
    region_model model (&mgr);
    ADD_SAT_CONSTRAINT (model, f, GT_EXPR, float_3);
    ADD_SAT_CONSTRAINT (model, f, LE_EXPR, float_4);
    ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, float_4);
    ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, int_4);
  }
}

/* Verify various lower-level implementation details about
   constraint_manager.  */

static void
test_constraint_impl ()
{
  tree int_42 = build_int_cst (integer_type_node, 42);
  tree int_0 = build_int_cst (integer_type_node, 0);

  tree x = build_global_decl ("x", integer_type_node);
  tree y = build_global_decl ("y", integer_type_node);
  tree z = build_global_decl ("z", integer_type_node);

  /* x == y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);

    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);

    /* Assert various things about the insides of model.  */
    constraint_manager *cm = model.get_constraints ();
    ASSERT_EQ (cm->m_constraints.length (), 0);
    ASSERT_EQ (cm->m_equiv_classes.length (), 1);
  }

  /* y <= z; x == y.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);

    ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
    ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);

    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);

    /* Assert various things about the insides of model.  */
    constraint_manager *cm = model.get_constraints ();
    ASSERT_EQ (cm->m_constraints.length (), 1);
    ASSERT_EQ (cm->m_equiv_classes.length (), 2);

    /* Ensure that we merged the constraints.  */
    ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
  }

  /* y <= z; y == x.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);
    ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
    ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);

    ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
    ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
    ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);

    ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, x);

    /* Assert various things about the insides of model.  */
    constraint_manager *cm = model.get_constraints ();
    ASSERT_EQ (cm->m_constraints.length (), 1);
    ASSERT_EQ (cm->m_equiv_classes.length (), 2);

    /* Ensure that we merged the constraints.  */
    ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
  }

  /* x == 0, then x != 42.  */
  {
    region_model_manager mgr;
    region_model model (&mgr);

    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
    ADD_SAT_CONSTRAINT (model, x, NE_EXPR, int_42);

    /* Assert various things about the insides of model.  */
    constraint_manager *cm = model.get_constraints ();
    ASSERT_EQ (cm->m_constraints.length (), 0);
    ASSERT_EQ (cm->m_equiv_classes.length (), 1);
  }

  // TODO: selftest for merging ecs "in the middle"
  // where a non-final one gets overwritten

  // TODO: selftest where there are pre-existing constraints
}

/* Check that operator== and hashing works as expected for the
   various types.  */

static void
test_equality ()
{
  tree x = build_global_decl ("x", integer_type_node);
  tree y = build_global_decl ("y", integer_type_node);

  {
    region_model_manager mgr;
    region_model model0 (&mgr);
    region_model model1 (&mgr);

    constraint_manager *cm0 = model0.get_constraints ();
    constraint_manager *cm1 = model1.get_constraints ();

    ASSERT_EQ (cm0->hash (), cm1->hash ());
    ASSERT_EQ (*cm0, *cm1);

    ASSERT_EQ (model0.hash (), model1.hash ());
    ASSERT_EQ (model0, model1);

    ADD_SAT_CONSTRAINT (model1, x, EQ_EXPR, y);
    ASSERT_NE (cm0->hash (), cm1->hash ());
    ASSERT_NE (*cm0, *cm1);

    ASSERT_NE (model0.hash (), model1.hash ());
    ASSERT_NE (model0, model1);

    region_model model2 (&mgr);
    constraint_manager *cm2 = model2.get_constraints ();
    /* Make the same change to cm2.  */
    ADD_SAT_CONSTRAINT (model2, x, EQ_EXPR, y);
    ASSERT_EQ (cm1->hash (), cm2->hash ());
    ASSERT_EQ (*cm1, *cm2);

    ASSERT_EQ (model1.hash (), model2.hash ());
    ASSERT_EQ (model1, model2);
  }
}

/* Verify tracking inequality of a variable against many constants.  */

static void
test_many_constants ()
{
  program_point point (program_point::origin ());
  tree a = build_global_decl ("a", integer_type_node);

  region_model_manager mgr;
  region_model model (&mgr);
  auto_vec<tree> constants;
  for (int i = 0; i < 20; i++)
    {
      tree constant = build_int_cst (integer_type_node, i);
      constants.safe_push (constant);
      ADD_SAT_CONSTRAINT (model, a, NE_EXPR, constant);

      /* Merge, and check the result.  */
      region_model other (model);

      region_model merged (&mgr);
      ASSERT_TRUE (model.can_merge_with_p (other, point, &merged));
      model.canonicalize ();
      merged.canonicalize ();
      ASSERT_EQ (model, merged);

      for (int j = 0; j <= i; j++)
	ASSERT_CONDITION_TRUE (model, a, NE_EXPR, constants[j]);
    }
}

/* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ.  */

static void
assert_dump_bounded_range_eq (const location &loc,
			      const bounded_range &range,
			      const char *expected)
{
  auto_fix_quotes sentinel;
  pretty_printer pp;
  pp_format_decoder (&pp) = default_tree_printer;
  range.dump_to_pp (&pp, false);
  ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
}

/* Assert that BR.dump (false) is EXPECTED.  */

#define ASSERT_DUMP_BOUNDED_RANGE_EQ(BR, EXPECTED) \
  SELFTEST_BEGIN_STMT							\
  assert_dump_bounded_range_eq ((SELFTEST_LOCATION), (BR), (EXPECTED)); \
  SELFTEST_END_STMT

/* Verify that bounded_range works as expected.  */

static void
test_bounded_range ()
{
  tree u8_0 = build_int_cst (unsigned_char_type_node, 0);
  tree u8_1 = build_int_cst (unsigned_char_type_node, 1);
  tree u8_64 = build_int_cst (unsigned_char_type_node, 64);
  tree u8_128 = build_int_cst (unsigned_char_type_node, 128);
  tree u8_255 = build_int_cst (unsigned_char_type_node, 255);

  tree s8_0 = build_int_cst (signed_char_type_node, 0);
  tree s8_1 = build_int_cst (signed_char_type_node, 1);
  tree s8_2 = build_int_cst (signed_char_type_node, 2);

  bounded_range br_u8_0 (u8_0, u8_0);
  ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0, "0");
  ASSERT_TRUE (br_u8_0.contains_p (u8_0));
  ASSERT_FALSE (br_u8_0.contains_p (u8_1));
  ASSERT_TRUE (br_u8_0.contains_p (s8_0));
  ASSERT_FALSE (br_u8_0.contains_p (s8_1));

  bounded_range br_u8_0_1 (u8_0, u8_1);
  ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0_1, "[0, 1]");

  bounded_range tmp (NULL_TREE, NULL_TREE);
  ASSERT_TRUE (br_u8_0.intersects_p (br_u8_0_1, &tmp));
  ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "0");

  bounded_range br_u8_64_128 (u8_64, u8_128);
  ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_64_128, "[64, 128]");

  ASSERT_FALSE (br_u8_0.intersects_p (br_u8_64_128, NULL));
  ASSERT_FALSE (br_u8_64_128.intersects_p (br_u8_0, NULL));

  bounded_range br_u8_128_255 (u8_128, u8_255);
  ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_128_255, "[128, 255]");
  ASSERT_TRUE (br_u8_128_255.intersects_p (br_u8_64_128, &tmp));
  ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "128");

  bounded_range br_s8_2 (s8_2, s8_2);
  ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2, "2");
  bounded_range br_s8_2_u8_255 (s8_2, u8_255);
  ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2_u8_255, "[2, 255]");
}

/* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ.  */

static void
assert_dump_bounded_ranges_eq (const location &loc,
			       const bounded_ranges *ranges,
			       const char *expected)
{
  auto_fix_quotes sentinel;
  pretty_printer pp;
  pp_format_decoder (&pp) = default_tree_printer;
  ranges->dump_to_pp (&pp, false);
  ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
}

/* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ.  */

static void
assert_dump_bounded_ranges_eq (const location &loc,
			       const bounded_ranges &ranges,
			       const char *expected)
{
  auto_fix_quotes sentinel;
  pretty_printer pp;
  pp_format_decoder (&pp) = default_tree_printer;
  ranges.dump_to_pp (&pp, false);
  ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
}

/* Assert that BRS.dump (false) is EXPECTED.  */

#define ASSERT_DUMP_BOUNDED_RANGES_EQ(BRS, EXPECTED) \
  SELFTEST_BEGIN_STMT							\
  assert_dump_bounded_ranges_eq ((SELFTEST_LOCATION), (BRS), (EXPECTED)); \
  SELFTEST_END_STMT

/* Verify that the bounded_ranges class works as expected.  */

static void
test_bounded_ranges ()
{
  bounded_ranges_manager mgr;

  tree ch0 = build_int_cst (unsigned_char_type_node, 0);
  tree ch1 = build_int_cst (unsigned_char_type_node, 1);
  tree ch2 = build_int_cst (unsigned_char_type_node, 2);
  tree ch3 = build_int_cst (unsigned_char_type_node, 3);
  tree ch128 = build_int_cst (unsigned_char_type_node, 128);
  tree ch129 = build_int_cst (unsigned_char_type_node, 129);
  tree ch254 = build_int_cst (unsigned_char_type_node, 254);
  tree ch255 = build_int_cst (unsigned_char_type_node, 255);

  const bounded_ranges *empty = mgr.get_or_create_empty ();
  ASSERT_DUMP_BOUNDED_RANGES_EQ (empty, "{}");

  const bounded_ranges *point0 = mgr.get_or_create_point (ch0);
  ASSERT_DUMP_BOUNDED_RANGES_EQ (point0, "{0}");

  const bounded_ranges *point1 = mgr.get_or_create_point (ch1);
  ASSERT_DUMP_BOUNDED_RANGES_EQ (point1, "{1}");

  const bounded_ranges *point2 = mgr.get_or_create_point (ch2);
  ASSERT_DUMP_BOUNDED_RANGES_EQ (point2, "{2}");

  const bounded_ranges *range0_128 = mgr.get_or_create_range (ch0, ch128);
  ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_128, "{[0, 128]}");

  const bounded_ranges *range0_255 = mgr.get_or_create_range (ch0, ch255);
  ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_255, "{[0, 255]}");

  ASSERT_FALSE (empty->contain_p (ch0));
  ASSERT_FALSE (empty->contain_p (ch1));
  ASSERT_FALSE (empty->contain_p (ch255));

  ASSERT_TRUE (point0->contain_p (ch0));
  ASSERT_FALSE (point0->contain_p (ch1));
  ASSERT_FALSE (point0->contain_p (ch255));

  ASSERT_FALSE (point1->contain_p (ch0));
  ASSERT_TRUE (point1->contain_p (ch1));
  ASSERT_FALSE (point0->contain_p (ch255));

  ASSERT_TRUE (range0_128->contain_p (ch0));
  ASSERT_TRUE (range0_128->contain_p (ch1));
  ASSERT_TRUE (range0_128->contain_p (ch128));
  ASSERT_FALSE (range0_128->contain_p (ch129));
  ASSERT_FALSE (range0_128->contain_p (ch254));
  ASSERT_FALSE (range0_128->contain_p (ch255));

  const bounded_ranges *inv0_128
    = mgr.get_or_create_inverse (range0_128, unsigned_char_type_node);
  ASSERT_DUMP_BOUNDED_RANGES_EQ (inv0_128, "{[129, 255]}");

  const bounded_ranges *range128_129 = mgr.get_or_create_range (ch128, ch129);
  ASSERT_DUMP_BOUNDED_RANGES_EQ (range128_129, "{[128, 129]}");

  const bounded_ranges *inv128_129
    = mgr.get_or_create_inverse (range128_129, unsigned_char_type_node);
  ASSERT_DUMP_BOUNDED_RANGES_EQ (inv128_129, "{[0, 127], [130, 255]}");

  /* Intersection.  */
  {
    /* Intersection of disjoint ranges should be empty set.  */
    const bounded_ranges *intersect0_1
      = mgr.get_or_create_intersection (point0, point1);
    ASSERT_DUMP_BOUNDED_RANGES_EQ (intersect0_1, "{}");
  }

  /* Various tests of "union of ranges".  */
  {
    {
      /* Touching points should be merged into a range.  */
      auto_vec <const bounded_ranges *> v;
      v.safe_push (point0);
      v.safe_push (point1);
      const bounded_ranges *union_0_and_1 = mgr.get_or_create_union (v);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (union_0_and_1, "{[0, 1]}");
    }

    {
      /* Overlapping and out-of-order.  */
      auto_vec <const bounded_ranges *> v;
      v.safe_push (inv0_128); // {[129, 255]}
      v.safe_push (range128_129);
      const bounded_ranges *union_129_255_and_128_129
	= mgr.get_or_create_union (v);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (union_129_255_and_128_129, "{[128, 255]}");
    }

    {
      /* Union of R and inverse(R) should be full range of type.  */
      auto_vec <const bounded_ranges *> v;
      v.safe_push (range128_129);
      v.safe_push (inv128_129);
      const bounded_ranges *union_ = mgr.get_or_create_union (v);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{[0, 255]}");
    }

    /* Union with an endpoint.  */
    {
      const bounded_ranges *range2_to_255
	= mgr.get_or_create_range (ch2, ch255);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (range2_to_255, "{[2, 255]}");
      auto_vec <const bounded_ranges *> v;
      v.safe_push (point0);
      v.safe_push (point2);
      v.safe_push (range2_to_255);
      const bounded_ranges *union_ = mgr.get_or_create_union (v);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{0, [2, 255]}");
    }

    /* Construct from vector of bounded_range.  */
    {
      auto_vec<bounded_range> v;
      v.safe_push (bounded_range (ch2, ch2));
      v.safe_push (bounded_range (ch0, ch0));
      v.safe_push (bounded_range (ch2, ch255));
      bounded_ranges br (v);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (&br, "{0, [2, 255]}");
    }
  }

  /* Various tests of "inverse".  */
  {
    {
      const bounded_ranges *range_1_to_3 = mgr.get_or_create_range (ch1, ch3);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_3, "{[1, 3]}");
      const bounded_ranges *inv
	= mgr.get_or_create_inverse (range_1_to_3, unsigned_char_type_node);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0, [4, 255]}");
    }
    {
      const bounded_ranges *range_1_to_255
	= mgr.get_or_create_range (ch1, ch255);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_255, "{[1, 255]}");
      const bounded_ranges *inv
	= mgr.get_or_create_inverse (range_1_to_255, unsigned_char_type_node);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0}");
    }
    {
      const bounded_ranges *range_0_to_254
	= mgr.get_or_create_range (ch0, ch254);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (range_0_to_254, "{[0, 254]}");
      const bounded_ranges *inv
	= mgr.get_or_create_inverse (range_0_to_254, unsigned_char_type_node);
      ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{255}");
    }
  }

  /* "case 'a'-'z': case 'A-Z':" vs "default:", for ASCII.  */
  {
    tree ch65 = build_int_cst (unsigned_char_type_node, 65);
    tree ch90 = build_int_cst (unsigned_char_type_node, 90);

    tree ch97 = build_int_cst (unsigned_char_type_node, 97);
    tree ch122 = build_int_cst (unsigned_char_type_node, 122);

    const bounded_ranges *A_to_Z = mgr.get_or_create_range (ch65, ch90);
    ASSERT_DUMP_BOUNDED_RANGES_EQ (A_to_Z, "{[65, 90]}");
    const bounded_ranges *a_to_z = mgr.get_or_create_range (ch97, ch122);
    ASSERT_DUMP_BOUNDED_RANGES_EQ (a_to_z, "{[97, 122]}");
    auto_vec <const bounded_ranges *> v;
    v.safe_push (A_to_Z);
    v.safe_push (a_to_z);
    const bounded_ranges *label_ranges = mgr.get_or_create_union (v);
    ASSERT_DUMP_BOUNDED_RANGES_EQ (label_ranges, "{[65, 90], [97, 122]}");
    const bounded_ranges *default_ranges
      = mgr.get_or_create_inverse (label_ranges, unsigned_char_type_node);
    ASSERT_DUMP_BOUNDED_RANGES_EQ (default_ranges,
				   "{[0, 64], [91, 96], [123, 255]}");
  }

  /* Verify ranges from ops.  */
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (EQ_EXPR, ch128),
				 "{128}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch128),
				 "{[0, 127], [129, 255]}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch128),
				 "{[0, 127]}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch128),
				 "{[0, 128]}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch128),
				 "{[128, 255]}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch128),
				 "{[129, 255]}");
  /* Ops at endpoints of type ranges.  */
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch0),
				 "{0}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch0),
				 "{}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch0),
				 "{[1, 255]}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch255),
				 "{255}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch255),
				 "{}");
  ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch255),
				 "{[0, 254]}");

  /* Verify that instances are consolidated by mgr.  */
  ASSERT_EQ (mgr.get_or_create_point (ch0),
	     mgr.get_or_create_point (ch0));
  ASSERT_NE (mgr.get_or_create_point (ch0),
	     mgr.get_or_create_point (ch1));
}

/* Run the selftests in this file, temporarily overriding
   flag_analyzer_transitivity with TRANSITIVITY.  */

static void
run_constraint_manager_tests (bool transitivity)
{
  int saved_flag_analyzer_transitivity = flag_analyzer_transitivity;
  flag_analyzer_transitivity = transitivity;

  test_constraint_conditions ();
  if (flag_analyzer_transitivity)
    {
      /* These selftests assume transitivity.  */
      test_transitivity ();
    }
  test_constant_comparisons ();
  test_constraint_impl ();
  test_equality ();
  test_many_constants ();
  test_bounded_range ();
  test_bounded_ranges ();

  flag_analyzer_transitivity = saved_flag_analyzer_transitivity;
}

/* Run all of the selftests within this file.  */

void
analyzer_constraint_manager_cc_tests ()
{
  /* Run the tests twice: with and without transitivity.  */
  run_constraint_manager_tests (true);
  run_constraint_manager_tests (false);
}

} // namespace selftest

#endif /* CHECKING_P */

} // namespace ana

#endif /* #if ENABLE_ANALYZER */