analyzer: move svalue and region decls to their own header files

gcc/ChangeLog:
	* Makefile.in (ANALYZER_OBJS): Add analyzer/complexity.o.

gcc/analyzer/ChangeLog:
	* analyzer.h (class state_machine): New forward decl.
	(class logger): Likewise.
	(class visitor): Likewise.
	* complexity.cc: New file, taken from svalue.cc.
	* complexity.h: New file, taken from region-model.h.
	* region-model.h: Include "analyzer/svalue.h" and
	"analyzer/region.h".  Move struct complexity to complexity.h.
	Move svalue, its subclasses and supporting decls to svalue.h.
	Move region, its subclasses and supporting decls to region.h.
	* region.cc: Include "analyzer/region.h".
	(symbolic_region::symbolic_region): Move here from region-model.h.
	* region.h: New file, based on material from region-model.h.
	* svalue.cc: Include "analyzer/svalue.h".
	(complexity::complexity): Move to complexity.cc.
	(complexity::from_pair): Likewise.
	* svalue.h: New file, based on material from region-model.h.

1 files changed, 1150 insertions, 0 deletions

diff --git a/gcc/analyzer/svalue.h b/gcc/analyzer/svalue.h
new file mode 100644
index 0000000..b519d26
--- /dev/null
+++ b/gcc/analyzer/svalue.h
@@ -0,0 +1,1150 @@
+/* Symbolic values.
+   Copyright (C) 2019-2020 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_SVALUE_H
+#define GCC_ANALYZER_SVALUE_H
+
+#include "analyzer/complexity.h"
+
+using namespace ana;
+
+namespace ana {
+
+/* An enum for discriminating between the different concrete subclasses
+   of svalue.  */
+
+enum svalue_kind
+{
+  SK_REGION,
+  SK_CONSTANT,
+  SK_UNKNOWN,
+  SK_POISONED,
+  SK_SETJMP,
+  SK_INITIAL,
+  SK_UNARYOP,
+  SK_BINOP,
+  SK_SUB,
+  SK_UNMERGEABLE,
+  SK_PLACEHOLDER,
+  SK_WIDENING,
+  SK_COMPOUND,
+  SK_CONJURED
+};
+
+/* svalue and its subclasses.
+
+   The class hierarchy looks like this (using indentation to show
+   inheritance, and with svalue_kinds shown for the concrete subclasses):
+
+   svalue
+     region_svalue (SK_REGION): a pointer to a region
+     constant_svalue (SK_CONSTANT): a constant
+     unknown_svalue (SK_UNKNOWN): an unknowable value
+     poisoned_svalue (SK_POISONED): a unusable value (undefined)
+     setjmp_svalue (SK_SETJMP): a setjmp/longjmp buffer
+     initial_svalue (SK_INITIAL): the initial value of a region
+     unaryop_svalue (SK_UNARYOP): unary operation on another svalue
+     binop_svalue (SK_BINOP): binary operation on two svalues
+     sub_svalue (SK_SUB): the result of accessing a subregion
+     unmergeable_svalue (SK_UNMERGEABLE): a value that is so interesting
+       from a control-flow perspective that it can inhibit state-merging
+     placeholder_svalue (SK_PLACEHOLDER): for use in selftests.
+     widening_svalue (SK_WIDENING): a merger of two svalues (possibly
+       in an iteration).
+     compound_svalue (SK_COMPOUND): a mapping of bit-ranges to svalues
+     conjured_svalue (SK_CONJURED): a value arising from a stmt.  */
+
+/* An abstract base class representing a value held by a region of memory.  */
+
+class svalue
+{
+public:
+  virtual ~svalue () {}
+
+  tree get_type () const { return m_type; }
+
+  virtual enum svalue_kind get_kind () const = 0;
+
+  void print (const region_model &model,
+	      pretty_printer *pp) const;
+
+  virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
+  void dump (bool simple=true) const;
+  label_text get_desc (bool simple=true) const;
+
+  json::value *to_json () const;
+
+  virtual const region_svalue *
+  dyn_cast_region_svalue () const { return NULL; }
+  virtual const constant_svalue *
+  dyn_cast_constant_svalue () const { return NULL; }
+  virtual const poisoned_svalue *
+  dyn_cast_poisoned_svalue () const { return NULL; }
+  virtual const setjmp_svalue *
+  dyn_cast_setjmp_svalue () const { return NULL; }
+  virtual const initial_svalue *
+  dyn_cast_initial_svalue () const { return NULL; }
+  virtual const unaryop_svalue *
+  dyn_cast_unaryop_svalue () const { return NULL; }
+  virtual const binop_svalue *
+  dyn_cast_binop_svalue () const { return NULL; }
+  virtual const sub_svalue *
+  dyn_cast_sub_svalue () const { return NULL; }
+  virtual const unmergeable_svalue *
+  dyn_cast_unmergeable_svalue () const { return NULL; }
+  virtual const widening_svalue *
+  dyn_cast_widening_svalue () const { return NULL; }
+  virtual const compound_svalue *
+  dyn_cast_compound_svalue () const { return NULL; }
+  virtual const conjured_svalue *
+  dyn_cast_conjured_svalue () const { return NULL; }
+
+  tree maybe_get_constant () const;
+  const svalue *maybe_undo_cast () const;
+  const svalue *unwrap_any_unmergeable () const;
+
+  const svalue *can_merge_p (const svalue *other,
+			      region_model_manager *mgr,
+			      model_merger *merger) const;
+
+  const complexity &get_complexity () const { return m_complexity; }
+
+  virtual void accept (visitor *v) const  = 0;
+
+  bool live_p (const svalue_set &live_svalues,
+	       const region_model *model) const;
+  virtual bool implicitly_live_p (const svalue_set &live_svalues,
+				  const region_model *model) const;
+
+  static int cmp_ptr (const svalue *, const svalue *);
+  static int cmp_ptr_ptr (const void *, const void *);
+
+ protected:
+  svalue (complexity c, tree type)
+  : m_complexity (c), m_type (type)
+  {}
+
+ private:
+  complexity m_complexity;
+  tree m_type;
+};
+
+/* Concrete subclass of svalue representing a pointer value that points to
+   a known region  */
+
+class region_svalue : public svalue
+{
+public:
+  /* A support class for uniquifying instances of region_svalue.  */
+  struct key_t
+  {
+    key_t (tree type, const region *reg)
+    : m_type (type), m_reg (reg)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_type);
+      hstate.add_ptr (m_reg);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_type == other.m_type && m_reg == other.m_reg);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = NULL_TREE; }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == NULL_TREE; }
+
+    tree m_type;
+    const region *m_reg;
+  };
+
+  region_svalue (tree type, const region *reg)
+  : svalue (complexity (reg), type),
+    m_reg (reg)
+  {
+    gcc_assert (m_reg != NULL);
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_REGION; }
+  const region_svalue *
+  dyn_cast_region_svalue () const FINAL OVERRIDE { return this; }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+
+  const region * get_pointee () const { return m_reg; }
+
+  static tristate eval_condition (const region_svalue *lhs_ptr,
+				  enum tree_code op,
+				  const region_svalue *rhs_ptr);
+
+ private:
+  const region *m_reg;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const region_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_REGION;
+}
+
+template <> struct default_hash_traits<region_svalue::key_t>
+: public member_function_hash_traits<region_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
+/* Concrete subclass of svalue representing a specific constant value.  */
+
+class constant_svalue : public svalue
+{
+public:
+  constant_svalue (tree cst_expr)
+  : svalue (complexity (1, 1), TREE_TYPE (cst_expr)), m_cst_expr (cst_expr)
+  {
+    gcc_assert (cst_expr);
+    gcc_assert (CONSTANT_CLASS_P (cst_expr));
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_CONSTANT; }
+  const constant_svalue *
+  dyn_cast_constant_svalue () const FINAL OVERRIDE { return this; }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+  bool implicitly_live_p (const svalue_set &,
+			  const region_model *) const FINAL OVERRIDE;
+
+  tree get_constant () const { return m_cst_expr; }
+  static tristate eval_condition (const constant_svalue *lhs,
+				  enum tree_code op,
+				  const constant_svalue *rhs);
+
+ private:
+  tree m_cst_expr;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const constant_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_CONSTANT;
+}
+
+namespace ana {
+
+/* Concrete subclass of svalue representing an unknowable value, the bottom
+   value when thinking of svalues as a lattice.
+   This is a singleton (w.r.t. its manager): there is a single unknown_svalue
+   per type.  Self-comparisons of such instances yield "unknown".  */
+
+class unknown_svalue : public svalue
+{
+public:
+  unknown_svalue (tree type)
+  : svalue (complexity (1, 1), type)
+  {}
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_UNKNOWN; }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+};
+
+/* An enum describing a particular kind of "poisoned" value.  */
+
+enum poison_kind
+{
+  /* For use to describe freed memory.  */
+  POISON_KIND_FREED,
+
+  /* For use on pointers to regions within popped stack frames.  */
+  POISON_KIND_POPPED_STACK
+};
+
+extern const char *poison_kind_to_str (enum poison_kind);
+
+/* Concrete subclass of svalue representing a value that should not
+   be used (e.g. uninitialized memory, freed memory).  */
+
+class poisoned_svalue : public svalue
+{
+public:
+  /* A support class for uniquifying instances of poisoned_svalue.  */
+  struct key_t
+  {
+    key_t (enum poison_kind kind, tree type)
+    : m_kind (kind), m_type (type)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_int (m_kind);
+      hstate.add_ptr (m_type);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_kind == other.m_kind && m_type == other.m_type);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = NULL_TREE; }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == NULL_TREE; }
+
+    enum poison_kind m_kind;
+    tree m_type;
+  };
+
+  poisoned_svalue (enum poison_kind kind, tree type)
+  : svalue (complexity (1, 1), type), m_kind (kind) {}
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_POISONED; }
+  const poisoned_svalue *
+  dyn_cast_poisoned_svalue () const FINAL OVERRIDE { return this; }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+
+  enum poison_kind get_poison_kind () const { return m_kind; }
+
+ private:
+  enum poison_kind m_kind;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const poisoned_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_POISONED;
+}
+
+template <> struct default_hash_traits<poisoned_svalue::key_t>
+: public member_function_hash_traits<poisoned_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
+/* A bundle of information recording a setjmp/sigsetjmp call, corresponding
+   roughly to a jmp_buf.  */
+
+struct setjmp_record
+{
+  setjmp_record (const exploded_node *enode,
+		 const gcall *setjmp_call)
+  : m_enode (enode), m_setjmp_call (setjmp_call)
+  {
+  }
+
+  bool operator== (const setjmp_record &other) const
+  {
+    return (m_enode == other.m_enode
+	    && m_setjmp_call == other.m_setjmp_call);
+  }
+
+  void add_to_hash (inchash::hash *hstate) const
+  {
+    hstate->add_ptr (m_enode);
+    hstate->add_ptr (m_setjmp_call);
+  }
+
+  static int cmp (const setjmp_record &rec1, const setjmp_record &rec2);
+
+  const exploded_node *m_enode;
+  const gcall *m_setjmp_call;
+};
+
+/* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp,
+   so that longjmp/siglongjmp can potentially "return" to an entirely
+   different function.  */
+
+class setjmp_svalue : public svalue
+{
+public:
+  /* A support class for uniquifying instances of poisoned_svalue.  */
+  struct key_t
+  {
+    key_t (const setjmp_record &record, tree type)
+    : m_record (record), m_type (type)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      m_record.add_to_hash (&hstate);
+      hstate.add_ptr (m_type);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_record == other.m_record && m_type == other.m_type);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = NULL_TREE; }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == NULL_TREE; }
+
+    setjmp_record m_record;
+    tree m_type;
+  };
+
+  setjmp_svalue (const setjmp_record &setjmp_record,
+		  tree type)
+  : svalue (complexity (1, 1), type), m_setjmp_record (setjmp_record)
+  {}
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_SETJMP; }
+  const setjmp_svalue *
+  dyn_cast_setjmp_svalue () const FINAL OVERRIDE { return this; }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+
+  int get_enode_index () const;
+
+  const setjmp_record &get_setjmp_record () const { return m_setjmp_record; }
+
+ private:
+  setjmp_record m_setjmp_record;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const setjmp_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_SETJMP;
+}
+
+template <> struct default_hash_traits<setjmp_svalue::key_t>
+: public member_function_hash_traits<setjmp_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
+/* Concrete subclass of svalue representing the initial value of a
+   specific region.
+
+   This represents the initial value at the start of the analysis path,
+   as opposed to the first time the region is accessed during the path.
+   Hence as soon as we have a call to an unknown function, all previously
+   unmodelled globals become implicitly "unknown" rathen than "initial".  */
+
+class initial_svalue : public svalue
+{
+public:
+  initial_svalue (tree type, const region *reg)
+  : svalue (complexity (reg), type), m_reg (reg)
+  {
+    gcc_assert (m_reg != NULL);
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_INITIAL; }
+  const initial_svalue *
+  dyn_cast_initial_svalue () const FINAL OVERRIDE { return this; }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+  bool implicitly_live_p (const svalue_set &,
+			  const region_model *) const FINAL OVERRIDE;
+
+  const region *get_region () const { return m_reg; }
+
+ private:
+  const region *m_reg;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const initial_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_INITIAL;
+}
+
+namespace ana {
+
+/* Concrete subclass of svalue representing a unary operation on
+   another svalues (e.g. a cast).  */
+
+class unaryop_svalue : public svalue
+{
+public:
+  /* A support class for uniquifying instances of unaryop_svalue.  */
+  struct key_t
+  {
+    key_t (tree type, enum tree_code op, const svalue *arg)
+    : m_type (type), m_op (op), m_arg (arg)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_type);
+      hstate.add_int (m_op);
+      hstate.add_ptr (m_arg);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_type == other.m_type
+	      && m_op == other.m_op
+	      && m_arg == other.m_arg);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = NULL_TREE; }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == NULL_TREE; }
+
+    tree m_type;
+    enum tree_code m_op;
+    const svalue *m_arg;
+  };
+
+  unaryop_svalue (tree type, enum tree_code op, const svalue *arg)
+  : svalue (complexity (arg), type), m_op (op), m_arg (arg)
+  {
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_UNARYOP; }
+  const unaryop_svalue *
+  dyn_cast_unaryop_svalue () const FINAL OVERRIDE { return this; }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+  bool implicitly_live_p (const svalue_set &,
+			  const region_model *) const FINAL OVERRIDE;
+
+  enum tree_code get_op () const { return m_op; }
+  const svalue *get_arg () const { return m_arg; }
+
+ private:
+  enum tree_code m_op;
+  const svalue *m_arg;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const unaryop_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_UNARYOP;
+}
+
+template <> struct default_hash_traits<unaryop_svalue::key_t>
+: public member_function_hash_traits<unaryop_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
+/* Concrete subclass of svalue representing a binary operation of
+   two svalues.  */
+
+class binop_svalue : public svalue
+{
+public:
+  /* A support class for uniquifying instances of binop_svalue.  */
+  struct key_t
+  {
+    key_t (tree type, enum tree_code op,
+	   const svalue *arg0, const svalue *arg1)
+    : m_type (type), m_op (op), m_arg0 (arg0), m_arg1 (arg1)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_type);
+      hstate.add_int (m_op);
+      hstate.add_ptr (m_arg0);
+      hstate.add_ptr (m_arg1);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_type == other.m_type
+	      && m_op == other.m_op
+	      && m_arg0 == other.m_arg0
+	      && m_arg1 == other.m_arg1);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = NULL_TREE; }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == NULL_TREE; }
+
+    tree m_type;
+    enum tree_code m_op;
+    const svalue *m_arg0;
+    const svalue *m_arg1;
+  };
+
+  binop_svalue (tree type, enum tree_code op,
+		 const svalue *arg0, const svalue *arg1)
+  : svalue (complexity::from_pair (arg0->get_complexity (),
+				    arg1->get_complexity ()),
+	     type),
+    m_op (op), m_arg0 (arg0), m_arg1 (arg1)
+  {
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_BINOP; }
+  const binop_svalue *dyn_cast_binop_svalue () const FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+  bool implicitly_live_p (const svalue_set &,
+			  const region_model *) const FINAL OVERRIDE;
+
+  enum tree_code get_op () const { return m_op; }
+  const svalue *get_arg0 () const { return m_arg0; }
+  const svalue *get_arg1 () const { return m_arg1; }
+
+ private:
+  enum tree_code m_op;
+  const svalue *m_arg0;
+  const svalue *m_arg1;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const binop_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_BINOP;
+}
+
+template <> struct default_hash_traits<binop_svalue::key_t>
+: public member_function_hash_traits<binop_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
+/* Concrete subclass of svalue representing the result of accessing a subregion
+   of another svalue (the value of a component/field of a struct, or an element
+   from an array).  */
+
+class sub_svalue : public svalue
+{
+public:
+  /* A support class for uniquifying instances of sub_svalue.  */
+  struct key_t
+  {
+    key_t (tree type, const svalue *parent_svalue, const region *subregion)
+    : m_type (type), m_parent_svalue (parent_svalue), m_subregion (subregion)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_type);
+      hstate.add_ptr (m_parent_svalue);
+      hstate.add_ptr (m_subregion);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_type == other.m_type
+	      && m_parent_svalue == other.m_parent_svalue
+	      && m_subregion == other.m_subregion);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = NULL_TREE; }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == NULL_TREE; }
+
+    tree m_type;
+    const svalue *m_parent_svalue;
+    const region *m_subregion;
+  };
+  sub_svalue (tree type, const svalue *parent_svalue,
+	       const region *subregion);
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_SUB; }
+  const sub_svalue *dyn_cast_sub_svalue () const FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+  bool implicitly_live_p (const svalue_set &,
+			  const region_model *) const FINAL OVERRIDE;
+
+  const svalue *get_parent () const { return m_parent_svalue; }
+  const region *get_subregion () const { return m_subregion; }
+
+ private:
+  const svalue *m_parent_svalue;
+  const region *m_subregion;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const sub_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_SUB;
+}
+
+template <> struct default_hash_traits<sub_svalue::key_t>
+: public member_function_hash_traits<sub_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
+/* Concrete subclass of svalue: decorate another svalue,
+   so that the resulting svalue can be identified as being
+   "interesting to control flow".
+   For example, consider the return value from setjmp.  We
+   don't want to merge states in which the result is 0 with
+   those in which the result is non-zero.  By using an
+   unmergeable_svalue for the result, we can inhibit such merges
+   and have separate exploded nodes for those states, keeping
+   the first and second returns from setjmp distinct in the exploded
+   graph.  */
+
+class unmergeable_svalue : public svalue
+{
+public:
+  unmergeable_svalue (const svalue *arg)
+  : svalue (complexity (arg), arg->get_type ()), m_arg (arg)
+  {
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_UNMERGEABLE; }
+  const unmergeable_svalue *
+  dyn_cast_unmergeable_svalue () const FINAL OVERRIDE { return this; }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+  bool implicitly_live_p (const svalue_set &,
+			  const region_model *) const FINAL OVERRIDE;
+
+  const svalue *get_arg () const { return m_arg; }
+
+ private:
+  const svalue *m_arg;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const unmergeable_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_UNMERGEABLE;
+}
+
+namespace ana {
+
+/* Concrete subclass of svalue for use in selftests, where
+   we want a specific but unknown svalue.
+   Unlike other svalue subclasses these aren't managed by
+   region_model_manager.  */
+
+class placeholder_svalue : public svalue
+{
+public:
+  placeholder_svalue (tree type, const char *name)
+  : svalue (complexity (1, 1), type), m_name (name)
+  {
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_PLACEHOLDER; }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+
+  const char *get_name () const { return m_name; }
+
+ private:
+  const char *m_name;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <placeholder_svalue *>::test (svalue *sval)
+{
+  return sval->get_kind () == SK_PLACEHOLDER;
+}
+
+namespace ana {
+
+/* Concrete subclass of svalue representing a "widening" seen when merging
+   states, widening from a base value to {base value, iter value} and thus
+   representing a possible fixed point in an iteration from the base to
+   +ve infinity, or -ve infinity, and thus useful for representing a value
+   within a loop.
+   We also need to capture the program_point at which the merger happens,
+   so that distinguish between different iterators, and thus handle
+   nested loops.  (currently we capture the function_point instead, for
+   simplicity of hashing).  */
+
+class widening_svalue : public svalue
+{
+public:
+  /* A support class for uniquifying instances of widening_svalue.  */
+  struct key_t
+  {
+    key_t (tree type, const program_point &point,
+	   const svalue *base_sval, const svalue *iter_sval)
+    : m_type (type), m_point (point.get_function_point ()),
+      m_base_sval (base_sval), m_iter_sval (iter_sval)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_base_sval);
+      hstate.add_ptr (m_iter_sval);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_type == other.m_type
+	      && m_point == other.m_point
+	      && m_base_sval == other.m_base_sval
+	      && m_iter_sval == other.m_iter_sval);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = NULL_TREE; }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == NULL_TREE; }
+
+    tree m_type;
+    function_point m_point;
+    const svalue *m_base_sval;
+    const svalue *m_iter_sval;
+  };
+
+  enum direction_t
+    {
+     DIR_ASCENDING,
+     DIR_DESCENDING,
+     DIR_UNKNOWN
+    };
+
+  widening_svalue (tree type, const program_point &point,
+		   const svalue *base_sval, const svalue *iter_sval)
+  : svalue (complexity::from_pair (base_sval->get_complexity (),
+				   iter_sval->get_complexity ()),
+	    type),
+    m_point (point.get_function_point ()),
+    m_base_sval (base_sval), m_iter_sval (iter_sval)
+  {
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_WIDENING; }
+  const widening_svalue *dyn_cast_widening_svalue () const FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+
+  const function_point &get_point () const { return m_point; }
+  const svalue *get_base_svalue () const { return m_base_sval; }
+  const svalue *get_iter_svalue () const { return m_iter_sval; }
+
+  enum direction_t get_direction () const;
+
+  tristate eval_condition_without_cm (enum tree_code op,
+				      tree rhs_cst) const;
+
+ private:
+  function_point m_point;
+  const svalue *m_base_sval;
+  const svalue *m_iter_sval;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <widening_svalue *>::test (svalue *sval)
+{
+  return sval->get_kind () == SK_WIDENING;
+}
+
+template <> struct default_hash_traits<widening_svalue::key_t>
+: public member_function_hash_traits<widening_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
+/* Concrete subclass of svalue representing a mapping of bit-ranges
+   to svalues, analogous to a cluster within the store.
+
+   This is for use in places where we want to represent a store-like
+   mapping, but are required to use an svalue, such as when handling
+   compound assignments and compound return values.
+
+   All keys within the underlying binding_map are required to be concrete,
+   not symbolic.
+
+   Instances of this class shouldn't be bound as-is into the store;
+   instead they should be unpacked.  Similarly, they should not be
+   nested.  */
+
+class compound_svalue : public svalue
+{
+public:
+  typedef binding_map::iterator_t iterator_t;
+
+  /* A support class for uniquifying instances of compound_svalue.
+     Note that to avoid copies, keys store pointers to binding_maps,
+     rather than the maps themselves.  */
+  struct key_t
+  {
+    key_t (tree type, const binding_map *map_ptr)
+    : m_type (type), m_map_ptr (map_ptr)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_type);
+      //hstate.add_ptr (m_map_ptr); // TODO
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_type == other.m_type
+	      && *m_map_ptr == *other.m_map_ptr);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = NULL_TREE; }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == NULL_TREE; }
+
+    tree m_type;
+    const binding_map *m_map_ptr;
+  };
+
+  compound_svalue (tree type, const binding_map &map);
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_COMPOUND; }
+  const compound_svalue *dyn_cast_compound_svalue () const FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+
+  const binding_map &get_map () const { return m_map; }
+
+  iterator_t begin () const { return m_map.begin (); }
+  iterator_t end () const { return m_map.end (); }
+
+  struct key_t make_key () const
+  {
+    return key_t (get_type (), &m_map);
+  }
+
+ private:
+  static complexity calc_complexity (const binding_map &map);
+
+  binding_map m_map;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <compound_svalue *>::test (svalue *sval)
+{
+  return sval->get_kind () == SK_COMPOUND;
+}
+
+template <> struct default_hash_traits<compound_svalue::key_t>
+: public member_function_hash_traits<compound_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
+/* A defined value arising from a statement, where we want to identify a
+   particular unknown value, rather than resorting to the unknown_value
+   singleton, so that the value can have sm-state.
+
+   Comparisons of variables that share the same conjured_svalue are known
+   to be equal, even if we don't know what the value is.
+
+   For example, this is used for the values of regions that may have been
+   touched when calling an unknown function.
+
+   The value captures a region as well as a stmt in order to avoid falsely
+   aliasing the various values that could arise in one statement.  For
+   example, after:
+      unknown_fn (&a, &b);
+   we want values to clobber a and b with, but we don't want to use the
+   same value, or it would falsely implicitly assume that a == b.  */
+
+class conjured_svalue : public svalue
+{
+public:
+  typedef binding_map::iterator_t iterator_t;
+
+  /* A support class for uniquifying instances of conjured_svalue.  */
+  struct key_t
+  {
+    key_t (tree type, const gimple *stmt, const region *id_reg)
+    : m_type (type), m_stmt (stmt), m_id_reg (id_reg)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_type);
+      hstate.add_ptr (m_stmt);
+      hstate.add_ptr (m_id_reg);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_type == other.m_type
+	      && m_stmt == other.m_stmt
+	      && m_id_reg == other.m_id_reg);
+    }
+
+    /* Use m_stmt to mark empty/deleted, as m_type can be NULL for
+       legitimate instances.  */
+    void mark_deleted () { m_stmt = reinterpret_cast<const gimple *> (1); }
+    void mark_empty () { m_stmt = NULL; }
+    bool is_deleted () const
+    {
+      return m_stmt == reinterpret_cast<const gimple *> (1);
+    }
+    bool is_empty () const { return m_stmt == NULL; }
+
+    tree m_type;
+    const gimple *m_stmt;
+    const region *m_id_reg;
+  };
+
+  conjured_svalue (tree type, const gimple *stmt, const region *id_reg)
+  : svalue (complexity (id_reg), type),
+    m_stmt (stmt), m_id_reg (id_reg)
+  {
+    gcc_assert (m_stmt != NULL);
+  }
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_CONJURED; }
+  const conjured_svalue *dyn_cast_conjured_svalue () const FINAL OVERRIDE
+  {
+    return this;
+  }
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+  void accept (visitor *v) const FINAL OVERRIDE;
+
+  const gimple *get_stmt () const { return m_stmt; }
+  const region *get_id_region () const { return m_id_reg; }
+
+ private:
+  const gimple *m_stmt;
+  const region *m_id_reg;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <conjured_svalue *>::test (svalue *sval)
+{
+  return sval->get_kind () == SK_CONJURED;
+}
+
+template <> struct default_hash_traits<conjured_svalue::key_t>
+: public member_function_hash_traits<conjured_svalue::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+#endif /* GCC_ANALYZER_SVALUE_H */