[30/49] analyzer: new files: constraint-manager.{cc|h}
diff mbox series

Message ID 1573867416-55618-31-git-send-email-dmalcolm@redhat.com
State New
Headers show
Series
  • RFC: Add a static analysis framework to GCC
Related show

Commit Message

David Malcolm Nov. 16, 2019, 1:23 a.m. UTC
This patch adds classes for tracking the equivalence classes and
constraints that hold at a point on an execution path.

gcc/ChangeLog:
	* analyzer/constraint-manager.cc: New file.
	* analyzer/constraint-manager.h: New file.
---
 gcc/analyzer/constraint-manager.cc | 2263 ++++++++++++++++++++++++++++++++++++
 gcc/analyzer/constraint-manager.h  |  248 ++++
 2 files changed, 2511 insertions(+)
 create mode 100644 gcc/analyzer/constraint-manager.cc
 create mode 100644 gcc/analyzer/constraint-manager.h

Patch
diff mbox series

diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc
new file mode 100644
index 0000000..12846f2
--- /dev/null
+++ b/gcc/analyzer/constraint-manager.cc
@@ -0,0 +1,2263 @@ 
+/* Tracking equivalence classes and constraints at a point on an execution path.
+   Copyright (C) 2019 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 "gcc-plugin.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "graphviz.h"
+#include "selftest.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/supergraph.h"
+#include "analyzer/constraint-manager.h"
+#include "analyzer/analyzer-selftests.h"
+
+/* One of the end-points of a range.  */
+
+struct bound
+{
+  bound () : m_constant (NULL_TREE), m_closed (false) {}
+  bound (tree constant, bool closed)
+  : m_constant (constant), m_closed (closed) {}
+
+  void ensure_closed (bool is_upper);
+
+  const char * get_relation_as_str () const;
+
+  tree m_constant;
+  bool m_closed;
+};
+
+/* A range of values, used for determining if a value has been
+   constrained to just one possible constant value.  */
+
+struct range
+{
+  range () : m_lower_bound (), m_upper_bound () {}
+  range (const bound &lower, const bound &upper)
+  : m_lower_bound (lower), m_upper_bound (upper) {}
+
+  void dump (pretty_printer *pp) const;
+
+  bool constrained_to_single_element (tree *out);
+
+  bound m_lower_bound;
+  bound m_upper_bound;
+};
+
+////////////////////////////////////////////////////////////////////////////
+
+/* 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 (pretty_printer *pp) const
+{
+PUSH_IGNORE_WFORMAT
+  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);
+POP_IGNORE_WFORMAT
+}
+
+/* Determine if there is only one possible value for this range.
+   If so, return true and write the constant to *OUT.
+   Otherwise, return false.  */
+
+bool
+range::constrained_to_single_element (tree *out)
+{
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (m_lower_bound.m_constant)))
+    return false;
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (m_upper_bound.m_constant)))
+    return false;
+
+  /* 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_build2 (EQ_EXPR, boolean_type_node,
+		   m_lower_bound.m_constant,
+		   m_upper_bound.m_constant);
+  if (comparison == boolean_true_node)
+    {
+      *out = m_lower_bound.m_constant;
+      return true;
+    }
+  else
+    return false;
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* class equiv_class.  */
+
+/* equiv_class's default ctor.  */
+
+equiv_class::equiv_class ()
+: m_constant (NULL_TREE), m_cst_sid (svalue_id::null ()),
+  m_vars ()
+{
+}
+
+/* equiv_class's copy ctor.  */
+
+equiv_class::equiv_class (const equiv_class &other)
+: m_constant (other.m_constant), m_cst_sid (other.m_cst_sid),
+  m_vars (other.m_vars.length ())
+{
+  int i;
+  svalue_id *sid;
+  FOR_EACH_VEC_ELT (other.m_vars, i, sid)
+    m_vars.quick_push (*sid);
+}
+
+/* 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;
+  svalue_id *sid;
+  FOR_EACH_VEC_ELT (m_vars, i, sid)
+    {
+      if (i > 0)
+	pp_string (pp, " == ");
+      sid->print (pp);
+    }
+  if (m_constant)
+    {
+      if (i > 0)
+	pp_string (pp, " == ");
+PUSH_IGNORE_WFORMAT
+      pp_printf (pp, "%qE", m_constant);
+POP_IGNORE_WFORMAT
+    }
+  pp_character (pp, '}');
+}
+
+/* Generate a hash value for this equiv_class.  */
+
+hashval_t
+equiv_class::hash () const
+{
+  inchash::hash hstate;
+  int i;
+  svalue_id *sid;
+
+  inchash::add_expr (m_constant, hstate);
+  FOR_EACH_VEC_ELT (m_vars, i, sid)
+    inchash::add (*sid, hstate);
+  return hstate.end ();
+}
+
+/* Equality operator for equiv_class.  */
+
+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_sid?  */
+
+  if (m_vars.length () != other.m_vars.length ())
+    return false;
+
+  int i;
+  svalue_id *sid;
+  FOR_EACH_VEC_ELT (m_vars, i, sid)
+    if (! (*sid == 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 (svalue_id sid, const constraint_manager &cm)
+{
+  gcc_assert (!sid.null_p ());
+  if (tree cst = cm.maybe_get_constant (sid))
+    {
+      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_sid = sid;
+    }
+  m_vars.safe_push (sid);
+}
+
+/* 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 (svalue_id sid)
+{
+  gcc_assert (!sid.null_p ());
+  gcc_assert (sid != m_cst_sid);
+
+  int i;
+  svalue_id *iv;
+  FOR_EACH_VEC_ELT (m_vars, i, iv)
+    {
+      if (*iv == sid)
+	{
+	  m_vars[i] = m_vars[m_vars.length () - 1];
+	  m_vars.pop ();
+	  return m_vars.length () == 0;
+	}
+    }
+
+  /* SID 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.  */
+
+svalue_id
+equiv_class::get_representative () const
+{
+  if (!m_cst_sid.null_p ())
+    return m_cst_sid;
+  else
+    {
+      gcc_assert (m_vars.length () > 0);
+      return m_vars[0];
+    }
+}
+
+/* Remap all svalue_ids within this equiv_class using MAP.  */
+
+void
+equiv_class::remap_svalue_ids (const svalue_id_map &map)
+{
+  int i;
+  svalue_id *iv;
+  FOR_EACH_VEC_ELT (m_vars, i, iv)
+    map.update (iv);
+  map.update (&m_cst_sid);
+}
+
+/* Comparator for use by equiv_class::canonicalize.  */
+
+static int
+svalue_id_cmp_by_id (const void *p1, const void *p2)
+{
+  const svalue_id *sid1 = (const svalue_id *)p1;
+  const svalue_id *sid2 = (const svalue_id *)p2;
+  return sid1->as_int () - sid2->as_int ();
+}
+
+/* Sort the svalues_ids within this equiv_class.  */
+
+void
+equiv_class::canonicalize ()
+{
+  m_vars.qsort (svalue_id_cmp_by_id);
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* 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);
+}
+
+/* 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;
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* 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 ())
+{
+  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);
+}
+
+/* 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);
+
+  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);
+
+  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 ());
+  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;
+
+  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;
+
+  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);
+    }
+  pp_printf (pp, "}");
+}
+
+/* Dump a multiline representation of this constraint_manager to PP
+   (which must support %E for trees).  */
+
+void
+constraint_manager::dump_to_pp (pretty_printer *pp) const
+{
+  // TODO
+  pp_string (pp, "  equiv classes:");
+  pp_newline (pp);
+  int i;
+  equiv_class *ec;
+  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
+    {
+      pp_string (pp, "    ");
+      equiv_class_id (i).print (pp);
+      pp_string (pp, ": ");
+      ec->print (pp);
+      pp_newline (pp);
+    }
+  pp_string (pp, "  constraints:");
+  pp_newline (pp);
+  constraint *c;
+  FOR_EACH_VEC_ELT (m_constraints, i, c)
+    {
+      pp_printf (pp, "    %i: ", i);
+      c->print (pp, *this);
+      pp_newline (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);
+  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 ();
+}
+
+/* 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 (svalue_id lhs,
+				    enum tree_code op,
+				    svalue_id rhs)
+{
+  equiv_class_id lhs_ec_id = get_or_add_equiv_class (lhs);
+  equiv_class_id rhs_ec_id = get_or_add_equiv_class (rhs);
+  return add_constraint (lhs_ec_id, op,rhs_ec_id);
+}
+
+/* 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;
+
+  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;
+	svalue_id *sid;
+	FOR_EACH_VEC_ELT (rhs_ec_obj.m_vars, i, sid)
+	  lhs_ec_obj.add (*sid, *this);
+
+	if (rhs_ec_obj.m_constant)
+	  {
+	    //gcc_assert (lhs_ec_obj.m_constant == NULL);
+	    lhs_ec_obj.m_constant = rhs_ec_obj.m_constant;
+	  }
+
+	/* 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;
+
+	/* 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;
+	  }
+      }
+      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 ();
+  return true;
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+/* 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)
+{
+  /* Add the constraint.  */
+  m_constraints.safe_push (constraint (lhs_id, c_op, rhs_id));
+
+  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.  */
+      svalue_id lhs = lhs_id.get_obj (*this).get_representative ();
+      svalue_id 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));
+		      tree constant;
+		      if (r.constrained_to_single_element (&constant))
+			{
+			  svalue_id cst_sid = get_sid_for_constant (constant);
+			  add_constraint
+			    (rhs_id, EQ_EXPR,
+			     get_or_add_equiv_class (cst_sid));
+			  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));
+		      tree constant;
+		      if (r.constrained_to_single_element (&constant))
+			{
+			  svalue_id cst_sid = get_sid_for_constant (constant);
+			  add_constraint
+			    (lhs_id, EQ_EXPR,
+			     get_or_add_equiv_class (cst_sid));
+			  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);
+		}
+	    }
+	}
+    }
+}
+
+/* Look for SID within the equivalence classes of this constraint_manager;
+   if found, write the id to *OUT and return true, otherwise return false.  */
+
+bool
+constraint_manager::get_equiv_class_by_sid (svalue_id sid, 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;
+      svalue_id *iv;
+      FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
+	if (*iv == sid)
+	  {
+	    *out = equiv_class_id (i);
+	    return true;
+	  }
+    }
+  return false;
+}
+
+/* Ensure that SID has an equivalence class within this constraint_manager;
+   return the ID of the class.  */
+
+equiv_class_id
+constraint_manager::get_or_add_equiv_class (svalue_id sid)
+{
+  equiv_class_id result (-1);
+
+  /* Try svalue_id match.  */
+  if (get_equiv_class_by_sid (sid, &result))
+    return result;
+
+  /* Try equality of constants.  */
+  if (tree cst = maybe_get_constant (sid))
+    {
+      int i;
+      equiv_class *ec;
+      FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
+	if (ec->m_constant)
+	  {
+	    tree eq = fold_build2 (EQ_EXPR, boolean_type_node,
+				   cst, ec->m_constant);
+	    if (eq == boolean_true_node)
+	      {
+		ec->add (sid, *this);
+		return equiv_class_id (i);
+	      }
+	  }
+    }
+
+
+  /* Not found.  */
+  equiv_class *new_ec = new equiv_class ();
+  new_ec->add (sid, *this);
+  m_equiv_classes.safe_push (new_ec);
+
+  equiv_class_id new_id (m_equiv_classes.length () - 1);
+
+  if (maybe_get_constant (sid))
+    {
+      /* If we have a new EC for a constant, add constraints comparing this
+	 to other constants we may have (so that we accumulate the transitive
+	 closure of all constraints on constants as the constants are
+	 added).  */
+      for (equiv_class_id other_id (0); other_id.m_idx < new_id.m_idx;
+	   other_id.m_idx++)
+	{
+	  const equiv_class &other_ec = other_id.get_obj (*this);
+	  if (other_ec.m_constant)
+	    {
+	      /* If we have two ECs, both with constants, the constants must be
+		 non-equal (or they would be in the same EC).
+		 Determine the direction of the inequality, and record that
+		 fact.  */
+	      tree lt
+		= fold_build2 (LT_EXPR, boolean_type_node,
+			       new_ec->m_constant, other_ec.m_constant);
+	      //gcc_assert (lt == boolean_true_node || lt == boolean_false_node);
+	      // not true for int vs float comparisons
+	      if (lt == boolean_true_node)
+		add_constraint_internal (new_id, CONSTRAINT_LT, other_id);
+	      else if (lt == boolean_false_node)
+		add_constraint_internal (other_id, CONSTRAINT_LT, new_id);
+	      /* Refresh new_id, in case ECs were merged.  SID should always
+		 be present by now, so this should never lead to a
+		 recursion.  */
+	      new_id = get_or_add_equiv_class (sid);
+	    }
+	}
+    }
+
+  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)
+{
+  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)
+    {
+      tree comparison
+	= fold_build2 (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);
+    }
+
+  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;
+	}
+    }
+
+  return tristate (tristate::TS_UNKNOWN);
+}
+
+/* Evaluate the condition LHS OP RHS, creating equiv_class instances for
+   LHS and RHS if they aren't already in equiv_classes.  */
+
+tristate
+constraint_manager::eval_condition (svalue_id lhs,
+				    enum tree_code op,
+				    svalue_id rhs)
+{
+  return eval_condition (get_or_add_equiv_class (lhs),
+			 op,
+			 get_or_add_equiv_class (rhs));
+}
+
+/* Delete any information about svalue_id instances identified by P.
+   Such instances are removed from equivalence classes, and any
+   redundant ECs and constraints are also removed.
+   Accumulate stats into STATS.  */
+
+void
+constraint_manager::purge (const purge_criteria &p, purge_stats *stats)
+{
+  /* Delete any svalue_ids 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;
+      svalue_id *pv;
+      bool delete_ec = false;
+      FOR_EACH_VEC_ELT (ec->m_vars, i, pv)
+	{
+	  if (*pv == ec->m_cst_sid)
+	    continue;
+	  if (p.should_purge_p (*pv))
+	    {
+	      if (ec->del (*pv))
+		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++;
+		}
+	    }
+	}
+      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);
+		}
+	      continue;
+	    }
+	}
+      ec_idx++;
+    }
+
+  validate ();
+}
+
+/* Remap all svalue_ids within this constraint_manager using MAP.  */
+
+void
+constraint_manager::remap_svalue_ids (const svalue_id_map &map)
+{
+  int i;
+  equiv_class *ec;
+  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
+    ec->remap_svalue_ids (map);
+}
+
+/* Comparator for use by constraint_manager::canonicalize.
+   Sort a pair of equiv_class instances, using the representative
+   svalue_id 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;
+
+  svalue_id rep1 = ec1->get_representative ();
+  svalue_id rep2 = ec2->get_representative ();
+
+  return rep1.as_int () - rep2.as_int ();
+}
+
+/* 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;
+}
+
+/* Reorder the equivalence classes and constraints within this
+   constraint_manager into a canonical order, to increase the
+   chances of finding equality with another instance.  */
+
+void
+constraint_manager::canonicalize (unsigned num_svalue_ids)
+{
+  /* First, sort svalue_ids within the ECs.  */
+  unsigned i;
+  equiv_class *ec;
+  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
+    ec->canonicalize ();
+
+  /* Next, sort the ECs into a canonical order.  */
+
+  /* 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 representative svalue_id
+     to the original equiv_class_id of that svalue_id.  */
+  auto_vec<equiv_class_id> original_ec_id (num_svalue_ids);
+  for (i = 0; i < num_svalue_ids; i++)
+    original_ec_id.quick_push (equiv_class_id::null ());
+  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
+    {
+      svalue_id rep = ec->get_representative ();
+      gcc_assert (!rep.null_p ());
+      original_ec_id[rep.as_int ()] = i;
+    }
+
+  /* Sort the equivalence classes.  */
+  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 (m_equiv_classes.length ());
+  FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
+    {
+      svalue_id rep = ec->get_representative ();
+      ec_id_map.put (original_ec_id[rep.as_int ()], i);
+    }
+
+  /* Update the EC ids within the constraints.  */
+  constraint *c;
+  FOR_EACH_VEC_ELT (m_constraints, i, c)
+    {
+      ec_id_map.update (&c->m_lhs);
+      ec_id_map.update (&c->m_rhs);
+    }
+
+  /* Finally, sort the constraints. */
+  m_constraints.qsort (constraint_cmp);
+}
+
+/* A concrete subclass of constraint_manager for use when
+   merging two constraint_manager into a third constraint_manager,
+   each of which has its own region_model.
+   Calls are delegated to the constraint_manager for the merged model,
+   and thus affect its region_model.  */
+
+class cleaned_constraint_manager : public constraint_manager
+{
+public:
+  cleaned_constraint_manager (constraint_manager *merged) : m_merged (merged) {}
+
+  constraint_manager *clone (region_model *) const FINAL OVERRIDE
+  {
+    gcc_unreachable ();
+  }
+  tree maybe_get_constant (svalue_id sid) const FINAL OVERRIDE
+  {
+    return m_merged->maybe_get_constant (sid);
+  }
+  svalue_id get_sid_for_constant (tree cst) const FINAL OVERRIDE
+  {
+    return m_merged->get_sid_for_constant (cst);
+  }
+  virtual int get_num_svalues () const FINAL OVERRIDE
+  {
+    return m_merged->get_num_svalues ();
+  }
+private:
+  constraint_manager *m_merged;
+};
+
+/* 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 (constraint_manager *cm_b,
+		       constraint_manager *out)
+  : m_cm_b (cm_b), m_out (out)
+  {}
+
+  void on_fact (svalue_id lhs, enum tree_code code, svalue_id rhs)
+    FINAL OVERRIDE
+  {
+    if (m_cm_b->eval_condition (lhs, code, rhs).is_true ())
+      {
+	bool sat = m_out->add_constraint (lhs, code, rhs);
+	gcc_assert (sat);
+      }
+  }
+
+private:
+  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,
+			   const model_merger &merger)
+{
+  gcc_assert (merger.m_sid_mapping);
+
+  /* Map svalue_ids in each equiv class from both sources
+     to the merged region_model, dropping ids that don't survive merger,
+     and potentially creating svalues in *OUT for constants.  */
+  cleaned_constraint_manager cleaned_cm_a (out);
+  const one_way_svalue_id_map &map_a_to_m
+    = merger.m_sid_mapping->m_map_from_a_to_m;
+  clean_merger_input (cm_a, map_a_to_m, &cleaned_cm_a);
+
+  cleaned_constraint_manager cleaned_cm_b (out);
+  const one_way_svalue_id_map &map_b_to_m
+    = merger.m_sid_mapping->m_map_from_b_to_m;
+  clean_merger_input (cm_b, map_b_to_m, &cleaned_cm_b);
+
+  /* At this point, the two cleaned CMs have ECs and constraints referring
+     to svalues in the merged region model, but both of them have separate
+     ECs.  */
+
+  /* Merge the equivalence classes and constraints.
+     The easiest way to do this seems to be to enumerate all of the facts
+     in cleaned_cm_a, see which are also true in cleaned_cm_b,
+     and add those to *OUT.  */
+  merger_fact_visitor v (&cleaned_cm_b, out);
+  cleaned_cm_a.for_each_fact (&v);
+}
+
+/* A subroutine of constraint_manager::merge.
+   Use MAP_SID_TO_M to map equivalence classes and constraints from
+   SM_IN to *OUT.  Purge any non-constant svalue_id that don't appear
+   in the result of MAP_SID_TO_M, purging any ECs and their constraints
+   that become empty as a result.  Potentially create svalues in
+   the merged region_model for constants that weren't already in use there.  */
+
+void
+constraint_manager::
+clean_merger_input (const constraint_manager &cm_in,
+		    const one_way_svalue_id_map &map_sid_to_m,
+		    constraint_manager *out)
+{
+  one_way_id_map<equiv_class_id> map_ec_to_m
+    (cm_in.m_equiv_classes.length ());
+  unsigned ec_idx;
+  equiv_class *ec;
+  FOR_EACH_VEC_ELT (cm_in.m_equiv_classes, ec_idx, ec)
+    {
+      equiv_class cleaned_ec;
+      if (tree cst = ec->get_any_constant ())
+	{
+	  cleaned_ec.m_constant = cst;
+	  /* Lazily create the constant in the out region_model.  */
+	  cleaned_ec.m_cst_sid = out->get_sid_for_constant (cst);
+	}
+      unsigned var_idx;
+      svalue_id *var_in_sid;
+      FOR_EACH_VEC_ELT (ec->m_vars, var_idx, var_in_sid)
+	{
+	  svalue_id var_m_sid = map_sid_to_m.get_dst_for_src (*var_in_sid);
+	  if (!var_m_sid.null_p ())
+	    cleaned_ec.m_vars.safe_push (var_m_sid);
+	}
+      if (cleaned_ec.get_any_constant () || !cleaned_ec.m_vars.is_empty ())
+	{
+	  map_ec_to_m.put (ec_idx, out->m_equiv_classes.length ());
+	  out->m_equiv_classes.safe_push (new equiv_class (cleaned_ec));
+	}
+    }
+
+  /* Write out to *OUT any constraints for which both sides survived
+     cleaning, using the new EC IDs.  */
+  unsigned con_idx;
+  constraint *c;
+  FOR_EACH_VEC_ELT (cm_in.m_constraints, con_idx, c)
+    {
+      equiv_class_id new_lhs = map_ec_to_m.get_dst_for_src (c->m_lhs);
+      if (new_lhs.null_p ())
+	continue;
+      equiv_class_id new_rhs = map_ec_to_m.get_dst_for_src (c->m_rhs);
+      if (new_rhs.null_p ())
+	continue;
+      out->m_constraints.safe_push (constraint (new_lhs,
+						c->m_op,
+						new_rhs));
+    }
+}
+
+/* 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_sid.null_p ())
+	{
+	  unsigned i;
+	  svalue_id *sid;
+	  FOR_EACH_VEC_ELT (ec->m_vars, i, sid)
+	    visitor->on_fact (ec->m_cst_sid, EQ_EXPR, *sid);
+	}
+      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_sid.null_p ())
+	{
+	  for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
+	    {
+	      visitor->on_fact (ec_lhs.m_cst_sid, code, ec_rhs.m_vars[j]);
+	    }
+	}
+      for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
+	{
+	  if (!ec_rhs.m_cst_sid.null_p ())
+	    visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_cst_sid);
+	  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]);
+	}
+    }
+}
+
+/* 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;
+      svalue_id *sid;
+      FOR_EACH_VEC_ELT (ec->m_vars, j, sid)
+	{
+	  gcc_assert (!sid->null_p ());
+	  gcc_assert (sid->as_int () < get_num_svalues ());
+	}
+      if (ec->m_constant)
+	gcc_assert (CONSTANT_CLASS_P (ec->m_constant));
+#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 ());
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////
+
+#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 and svalue_id
+   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 model;
+    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);
+  }
+
+  /* x == y.  */
+  {
+    region_model model;
+    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 model;
+    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 model;
+
+    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 model;
+
+    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 model;
+
+    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 model;
+
+    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 model;
+
+    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 model;
+    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 model;
+    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 model;
+    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
+    ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, y);
+  }
+
+  /* x == 0 then x == 42.  */
+  {
+    region_model model;
+    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 model;
+    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 model;
+    ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
+    ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, int_0);
+  }
+
+  /* x != y && x == y.  */
+  {
+    region_model model;
+    ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
+    ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, y);
+  }
+
+  /* x <= y && x > y.  */
+  {
+    region_model model;
+    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 model;
+    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 model;
+    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 model;
+    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 model;
+    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 model;
+    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 model;
+    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 model;
+    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 model;
+    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 model;
+    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);
+  }
+
+  /* Transitivity: "a >= b", "b > a" should be impossible.  */
+  {
+    region_model model;
+    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 model;
+    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 model;
+    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 model;
+    ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_1024);
+    ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_1023);
+  }
+
+  /* a > 4.  */
+  {
+    region_model model;
+    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 model;
+    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 model;
+    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 model;
+      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 model;
+      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 model;
+      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 model;
+      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 model;
+      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 model;
+    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 model;
+
+    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 model;
+    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 model;
+    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 model;
+
+    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 (), 1);
+    ASSERT_EQ (cm->m_equiv_classes.length (), 2);
+    ASSERT_EQ (cm->m_constraints[0].m_lhs,
+	       cm->get_or_add_equiv_class (model.get_rvalue (int_0, NULL)));
+    ASSERT_EQ (cm->m_constraints[0].m_rhs,
+	       cm->get_or_add_equiv_class (model.get_rvalue (int_42, NULL)));
+    ASSERT_EQ (cm->m_constraints[0].m_op, CONSTRAINT_LT);
+  }
+
+  // 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 model0;
+    region_model model1;
+
+    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;
+    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 ()
+{
+  tree a = build_global_decl ("a", integer_type_node);
+
+  region_model model;
+  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;
+      ASSERT_TRUE (model.can_merge_with_p (other, &merged));
+      model.canonicalize (NULL);
+      merged.canonicalize (NULL);
+      ASSERT_EQ (model, merged);
+
+      for (int j = 0; j <= i; j++)
+	ASSERT_CONDITION_TRUE (model, a, NE_EXPR, constants[j]);
+    }
+}
+
+/* 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 ();
+
+  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 */
diff --git a/gcc/analyzer/constraint-manager.h b/gcc/analyzer/constraint-manager.h
new file mode 100644
index 0000000..7710dc8
--- /dev/null
+++ b/gcc/analyzer/constraint-manager.h
@@ -0,0 +1,248 @@ 
+/* Tracking equivalence classes and constraints at a point on an execution path.
+   Copyright (C) 2019 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/>.  */
+
+#ifndef GCC_ANALYZER_CONSTRAINT_MANAGER_H
+#define GCC_ANALYZER_CONSTRAINT_MANAGER_H
+
+#include "analyzer/region-model.h" // for svalue_id
+
+class constraint_manager;
+
+/* Abstract base class for specifying how state should be purged.  */
+
+class purge_criteria
+{
+public:
+  virtual ~purge_criteria () {}
+  virtual bool should_purge_p (svalue_id sid) const = 0;
+};
+
+/* An equivalence class within a constraint manager: a set of
+   svalue_ids that are known to all be equal to each other,
+   together with an optional tree constant that they are equal to.  */
+
+class equiv_class
+{
+public:
+  equiv_class ();
+  equiv_class (const equiv_class &other);
+
+  hashval_t hash () const;
+  bool operator== (const equiv_class &other);
+
+  void add (svalue_id sid, const constraint_manager &cm);
+  bool del (svalue_id sid);
+
+  tree get_any_constant () const { return m_constant; }
+
+  svalue_id get_representative () const;
+
+  void remap_svalue_ids (const svalue_id_map &map);
+
+  void canonicalize ();
+
+  void print (pretty_printer *pp) const;
+
+  /* An equivalence class can contain multiple constants (e.g. multiple
+     different zeroes, for different types); these are just for the last
+     constant added.  */
+  tree m_constant;
+  svalue_id m_cst_sid;
+
+  // TODO: should this be a set rather than a vec?
+  auto_vec<svalue_id> m_vars;
+};
+
+/* The various kinds of constraint.  */
+
+enum constraint_op
+{
+  CONSTRAINT_NE,
+  CONSTRAINT_LT,
+  CONSTRAINT_LE
+};
+
+const char *constraint_op_code (enum constraint_op c_op);
+
+/* An ID for an equiv_class within a constraint_manager.  Internally, this
+   is an index into a vector of equiv_class * within the constraint_manager.  */
+
+class equiv_class_id
+{
+public:
+  static equiv_class_id null () { return equiv_class_id (-1); }
+
+  equiv_class_id (unsigned idx) : m_idx (idx) {}
+  const equiv_class &get_obj (const constraint_manager &cm) const;
+  equiv_class &get_obj (constraint_manager &cm) const;
+
+  bool operator== (const equiv_class_id &other) const
+  {
+    return m_idx == other.m_idx;
+  }
+  bool operator!= (const equiv_class_id &other) const
+  {
+    return m_idx != other.m_idx;
+  }
+
+  bool null_p () const { return m_idx == -1; }
+
+  static equiv_class_id from_int (int idx) { return equiv_class_id (idx); }
+  int as_int () const { return m_idx; }
+
+  void print (pretty_printer *pp) const;
+
+  void update_for_removal (equiv_class_id other)
+  {
+    if (m_idx > other.m_idx)
+      m_idx--;
+  }
+
+  int m_idx;
+};
+
+/* A relationship between two equivalence classes in a constraint_manager.  */
+
+class constraint
+{
+ public:
+  constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs)
+  : m_lhs (lhs), m_op (c_op), m_rhs (rhs)
+  {
+    gcc_assert (!lhs.null_p ());
+    gcc_assert (!rhs.null_p ());
+  }
+
+  void print (pretty_printer *pp, const constraint_manager &cm) const;
+
+  hashval_t hash () const;
+  bool operator== (const constraint &other) const;
+
+  /* Is this an ordering, rather than a "!=".  */
+  bool is_ordering_p () const
+  {
+    return m_op != CONSTRAINT_NE;
+  }
+
+  equiv_class_id m_lhs;
+  enum constraint_op m_op;
+  equiv_class_id m_rhs;
+};
+
+/* An abstract base class for use with constraint_manager::for_each_fact.  */
+
+class fact_visitor
+{
+ public:
+  virtual ~fact_visitor () {}
+  virtual void on_fact (svalue_id lhs, enum tree_code, svalue_id rhs) = 0;
+};
+
+/* A collection of equivalence classes and constraints on them.
+
+   Given N svalues, this can be thought of as representing a subset of
+   N-dimensional space.  When we call add_constraint,
+   we are effectively taking an intersection with that constraint.  */
+
+class constraint_manager
+{
+public:
+  constraint_manager () {}
+  constraint_manager (const constraint_manager &other);
+  virtual ~constraint_manager () {}
+
+  virtual constraint_manager *clone (region_model *) const = 0;
+  virtual tree maybe_get_constant (svalue_id sid) const = 0;
+  virtual svalue_id get_sid_for_constant (tree cst) const = 0;
+  virtual int get_num_svalues () const = 0;
+
+  constraint_manager& operator= (const constraint_manager &other);
+
+  hashval_t hash () const;
+  bool operator== (const constraint_manager &other) const;
+  bool operator!= (const constraint_manager &other) const
+  {
+    return !(*this == other);
+  }
+
+  void print (pretty_printer *pp) const;
+  void dump_to_pp (pretty_printer *pp) const;
+  void dump (FILE *fp) const;
+  void dump () const;
+
+  const equiv_class &get_equiv_class_by_index (unsigned idx) const
+  {
+    return *m_equiv_classes[idx];
+  }
+  equiv_class &get_equiv_class_by_index (unsigned idx)
+  {
+    return *m_equiv_classes[idx];
+  }
+
+  equiv_class &get_equiv_class (svalue_id sid)
+  {
+    equiv_class_id ec_id = get_or_add_equiv_class (sid);
+    return ec_id.get_obj (*this);
+  }
+
+  bool add_constraint (svalue_id lhs, enum tree_code op, svalue_id rhs);
+
+  bool add_constraint (equiv_class_id lhs_ec_id,
+		       enum tree_code op,
+		       equiv_class_id rhs_ec_id);
+
+  bool get_equiv_class_by_sid (svalue_id sid, equiv_class_id *out) const;
+  equiv_class_id get_or_add_equiv_class (svalue_id sid);
+  tristate eval_condition (equiv_class_id lhs,
+			   enum tree_code op,
+			   equiv_class_id rhs);
+  tristate eval_condition (svalue_id lhs,
+			   enum tree_code op,
+			   svalue_id rhs);
+
+  void purge (const purge_criteria &p, purge_stats *stats);
+
+  void remap_svalue_ids (const svalue_id_map &map);
+
+  void canonicalize (unsigned num_svalue_ids);
+
+  static void merge (const constraint_manager &cm_a,
+		     const constraint_manager &cm_b,
+		     constraint_manager *out,
+		     const model_merger &merger);
+
+  void for_each_fact (fact_visitor *) const;
+
+  void validate () const;
+
+  auto_delete_vec<equiv_class> m_equiv_classes;
+  auto_vec<constraint> m_constraints;
+
+ private:
+  static void clean_merger_input (const constraint_manager &cm_in,
+				  const one_way_svalue_id_map &map_sid_to_m,
+				  constraint_manager *out);
+
+  void add_constraint_internal (equiv_class_id lhs_id,
+				enum constraint_op c_op,
+				equiv_class_id rhs_id);
+};
+
+#endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */