path: root/gcc/analyzer/region-model.h

/* Classes for modeling the state of memory.
   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_REGION_MODEL_H
#define GCC_ANALYZER_REGION_MODEL_H

/* Implementation of the region-based ternary model described in:
     "A Memory Model for Static Analysis of C Programs"
      (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
     http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf  */

/* A tree, extended with stack frame information for locals, so that
   we can distinguish between different values of locals within a potentially
   recursive callstack.  */
// TODO: would this be better as a new tree code?

using namespace ana;

namespace ana {

class path_var
{
public:
  path_var (tree t, int stack_depth)
  : m_tree (t), m_stack_depth (stack_depth)
  {
    // TODO: ignore stack depth for globals and constants
  }

  bool operator== (const path_var &other) const
  {
    return (m_tree == other.m_tree
	    && m_stack_depth == other.m_stack_depth);
  }

  void dump (pretty_printer *pp) const;

  tree m_tree;
  int m_stack_depth; // or -1 for globals?
};

} // namespace ana

namespace inchash
{
  extern void add_path_var (path_var pv, hash &hstate);
} // namespace inchash


namespace ana {

/* A region_model is effectively a graph of regions and symbolic values.
   We store per-model IDs rather than pointers to make it easier to clone
   and to compare graphs.  */

/* An ID for an svalue within a region_model.  Internally, this is an index
   into a vector of svalue * within the region_model.  */

class svalue_id
{
public:
  static svalue_id null () { return svalue_id (-1); }

  svalue_id () : m_idx (-1) {}

  bool operator== (const svalue_id &other) const
  {
    return m_idx == other.m_idx;
  }

  bool operator!= (const svalue_id &other) const
  {
    return m_idx != other.m_idx;
  }

  bool null_p () const { return m_idx == -1; }

  static svalue_id from_int (int idx) { return svalue_id (idx); }
  int as_int () const { return m_idx; }

  void print (pretty_printer *pp) const;
  void dump_node_name_to_pp (pretty_printer *pp) const;

  void validate (const region_model &model) const;

private:
  svalue_id (int idx) : m_idx (idx) {}

  int m_idx;
};

/* An ID for a region within a region_model.  Internally, this is an index
   into a vector of region * within the region_model.  */

class region_id
{
public:
  static region_id null () { return region_id (-1); }

  region_id () : m_idx (-1) {}

  bool operator== (const region_id &other) const
  {
    return m_idx == other.m_idx;
  }

  bool operator!= (const region_id &other) const
  {
    return m_idx != other.m_idx;
  }

  bool null_p () const { return m_idx == -1; }

  static region_id from_int (int idx) { return region_id (idx); }
  int as_int () const { return m_idx; }

  void print (pretty_printer *pp) const;
  void dump_node_name_to_pp (pretty_printer *pp) const;

  void validate (const region_model &model) const;

private:
  region_id (int idx) : m_idx (idx) {}

  int m_idx;
};

/* A class for renumbering IDs within a region_model, mapping old IDs
   to new IDs (e.g. when removing one or more elements, thus needing to
   renumber).  */
// TODO: could this be useful for equiv_class_ids?

template <typename T>
class id_map
{
 public:
  id_map (int num_ids);
  void put (T src, T dst);
  T get_dst_for_src (T src) const;
  T get_src_for_dst (T dst) const;
  void dump_to_pp (pretty_printer *pp) const;
  void dump () const;
  void update (T *) const;

 private:
  auto_vec<T> m_src_to_dst;
  auto_vec<T> m_dst_to_src;
};

typedef id_map<svalue_id> svalue_id_map;
typedef id_map<region_id> region_id_map;

/* class id_map.  */

/* id_map's ctor, which populates the map with dummy null values.  */

template <typename T>
inline id_map<T>::id_map (int num_svalues)
: m_src_to_dst (num_svalues),
  m_dst_to_src (num_svalues)
{
  for (int i = 0; i < num_svalues; i++)
    {
      m_src_to_dst.quick_push (T::null ());
      m_dst_to_src.quick_push (T::null ());
    }
}

/* Record that SRC is to be mapped to DST.  */

template <typename T>
inline void
id_map<T>::put (T src, T dst)
{
  m_src_to_dst[src.as_int ()] = dst;
  m_dst_to_src[dst.as_int ()] = src;
}

/* Get the new value for SRC within the map.  */

template <typename T>
inline T
id_map<T>::get_dst_for_src (T src) const
{
  if (src.null_p ())
    return src;
  return m_src_to_dst[src.as_int ()];
}

/* Given DST, a new value, determine which old value will be mapped to it
   (the inverse of the map).  */

template <typename T>
inline T
id_map<T>::get_src_for_dst (T dst) const
{
  if (dst.null_p ())
    return dst;
  return m_dst_to_src[dst.as_int ()];
}

/* Dump this id_map to PP.  */

template <typename T>
inline void
id_map<T>::dump_to_pp (pretty_printer *pp) const
{
  pp_string (pp, "src to dst: {");
  unsigned i;
  T *dst;
  FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
    {
      if (i > 0)
	pp_string (pp, ", ");
      T src (T::from_int (i));
      src.print (pp);
      pp_string (pp, " -> ");
      dst->print (pp);
    }
  pp_string (pp, "}");
  pp_newline (pp);

  pp_string (pp, "dst to src: {");
  T *src;
  FOR_EACH_VEC_ELT (m_dst_to_src, i, src)
    {
      if (i > 0)
	pp_string (pp, ", ");
      T dst (T::from_int (i));
      dst.print (pp);
      pp_string (pp, " <- ");
      src->print (pp);
    }
  pp_string (pp, "}");
  pp_newline (pp);
}

/* Dump this id_map to stderr.  */

template <typename T>
DEBUG_FUNCTION inline void
id_map<T>::dump () const
{
  pretty_printer pp;
  pp.buffer->stream = stderr;
  dump_to_pp (&pp);
  pp_flush (&pp);
}

/* Update *ID from the old value to its new value in this map.  */

template <typename T>
inline void
id_map<T>::update (T *id) const
{
  *id = get_dst_for_src (*id);
}

/* Variant of the above, which only stores things in one direction.
   (e.g. for merging, when the number of destination regions is not
   the same of the src regions, and can grow).  */

template <typename T>
class one_way_id_map
{
 public:
  one_way_id_map (int num_ids);
  void put (T src, T dst);
  T get_dst_for_src (T src) const;
  void dump_to_pp (pretty_printer *pp) const;
  void dump () const;
  void update (T *) const;

 private:
  auto_vec<T> m_src_to_dst;
};

typedef one_way_id_map<svalue_id> one_way_svalue_id_map;
typedef one_way_id_map<region_id> one_way_region_id_map;

/* class one_way_id_map.  */

/* one_way_id_map's ctor, which populates the map with dummy null values.  */

template <typename T>
inline one_way_id_map<T>::one_way_id_map (int num_svalues)
: m_src_to_dst (num_svalues)
{
  for (int i = 0; i < num_svalues; i++)
    m_src_to_dst.quick_push (T::null ());
}

/* Record that SRC is to be mapped to DST.  */

template <typename T>
inline void
one_way_id_map<T>::put (T src, T dst)
{
  m_src_to_dst[src.as_int ()] = dst;
}

/* Get the new value for SRC within the map.  */

template <typename T>
inline T
one_way_id_map<T>::get_dst_for_src (T src) const
{
  if (src.null_p ())
    return src;
  return m_src_to_dst[src.as_int ()];
}

/* Dump this map to PP.  */

template <typename T>
inline void
one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
{
  pp_string (pp, "src to dst: {");
  unsigned i;
  T *dst;
  FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
    {
      if (i > 0)
	pp_string (pp, ", ");
      T src (T::from_int (i));
      src.print (pp);
      pp_string (pp, " -> ");
      dst->print (pp);
    }
  pp_string (pp, "}");
  pp_newline (pp);
}

/* Dump this map to stderr.  */

template <typename T>
DEBUG_FUNCTION inline void
one_way_id_map<T>::dump () const
{
  pretty_printer pp;
  pp.buffer->stream = stderr;
  dump_to_pp (&pp);
  pp_flush (&pp);
}

/* Update *ID from the old value to its new value in this map.  */

template <typename T>
inline void
one_way_id_map<T>::update (T *id) const
{
  *id = get_dst_for_src (*id);
}

/* A set of region_ids within a region_model.  */

class region_id_set
{
public:
  region_id_set (const region_model *model);

  void add_region (region_id rid)
  {
    if (!rid.null_p ())
      bitmap_set_bit (m_bitmap, rid.as_int ());
  }

  bool region_p (region_id rid) const
  {
    gcc_assert (!rid.null_p ());
    return bitmap_bit_p (const_cast <auto_sbitmap &> (m_bitmap),
			 rid.as_int ());
  }

  unsigned int num_regions ()
  {
    return bitmap_count_bits (m_bitmap);
  }

private:
  auto_sbitmap m_bitmap;
};

/* A set of svalue_ids within a region_model.  */

class svalue_id_set
{
public:
  svalue_id_set ();

  void add_svalue (svalue_id sid)
  {
    if (!sid.null_p ())
      bitmap_set_bit (m_bitmap, sid.as_int ());
  }

  bool svalue_p (svalue_id sid) const
  {
    gcc_assert (!sid.null_p ());
    return bitmap_bit_p (const_cast <auto_bitmap &> (m_bitmap),
			 sid.as_int ());
  }

private:
  auto_bitmap m_bitmap;
};

/* Various operations delete information from a region_model.

   This struct tracks how many of each kind of entity were purged (e.g.
   for selftests, and for debugging).  */

struct purge_stats
{
  purge_stats ()
  : m_num_svalues (0),
    m_num_regions (0),
    m_num_equiv_classes (0),
    m_num_constraints (0),
    m_num_client_items (0)
  {}

  int m_num_svalues;
  int m_num_regions;
  int m_num_equiv_classes;
  int m_num_constraints;
  int m_num_client_items;
};

/* An enum for discriminating between the different concrete subclasses
   of svalue.  */

enum svalue_kind
{
  SK_REGION,
  SK_CONSTANT,
  SK_UNKNOWN,
  SK_POISONED,
  SK_SETJMP
};

/* 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)
     constant_svalue (SK_CONSTANT)
     unknown_svalue (SK_UNKNOWN)
     poisoned_svalue (SK_POISONED)
     setjmp_svalue (SK_SETJMP).  */

/* An abstract base class representing a value held by a region of memory.  */

class svalue
{
public:
  virtual ~svalue () {}

  bool operator== (const svalue &other) const;
  bool operator!= (const svalue &other) const { return !(*this == other); }

  virtual svalue *clone () const = 0;

  tree get_type () const { return m_type; }

  virtual enum svalue_kind get_kind () const = 0;

  hashval_t hash () const;

  void print (const region_model &model,
	      svalue_id this_sid,
	      pretty_printer *pp) const;

  virtual void dump_dot_to_pp (const region_model &model,
			       svalue_id this_sid,
			       pretty_printer *pp) const;

  virtual region_svalue *dyn_cast_region_svalue () { return NULL; }
  virtual constant_svalue *dyn_cast_constant_svalue () { return NULL; }
  virtual const constant_svalue *dyn_cast_constant_svalue () const
  { return NULL; }
  virtual poisoned_svalue *dyn_cast_poisoned_svalue () { return NULL; }
  virtual unknown_svalue *dyn_cast_unknown_svalue () { return NULL; }
  virtual setjmp_svalue *dyn_cast_setjmp_svalue () { return NULL; }

  virtual void remap_region_ids (const region_id_map &map);

  virtual void walk_for_canonicalization (canonicalization *c) const;

  virtual svalue_id get_child_sid (region *parent, region *child,
				   region_model &model,
				   region_model_context *ctxt);

  tree maybe_get_constant () const;

 protected:
  svalue (tree type) : m_type (type) {}

  virtual void add_to_hash (inchash::hash &hstate) const = 0;

 private:
  virtual void print_details (const region_model &model,
			      svalue_id this_sid,
			      pretty_printer *pp) const = 0;
  tree m_type;
};

/* Concrete subclass of svalue representing a pointer value that points to
   a known region  */

class region_svalue : public svalue
{
public:
  region_svalue (tree type, region_id rid) : svalue (type), m_rid (rid)
  {
    /* Should we support NULL ptrs here?  */
    gcc_assert (!rid.null_p ());
  }

  bool compare_fields (const region_svalue &other) const;

  svalue *clone () const FINAL OVERRIDE
  { return new region_svalue (get_type (), m_rid); }

  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_REGION; }

  void dump_dot_to_pp (const region_model &model,
		       svalue_id this_sid,
		       pretty_printer *pp) const
    FINAL OVERRIDE;

  region_svalue *dyn_cast_region_svalue () FINAL OVERRIDE { return this; }

  region_id get_pointee () const { return m_rid; }

  void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;

  static void merge_values (const region_svalue &region_sval_a,
			    const region_svalue &region_sval_b,
			    svalue_id *merged_sid,
			    tree type,
			    model_merger *merger);

  void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;

  static tristate eval_condition (region_svalue *lhs_ptr,
				  enum tree_code op,
				  region_svalue *rhs_ptr);

  void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;

 private:
  void print_details (const region_model &model,
		      svalue_id this_sid,
		      pretty_printer *pp) const
    FINAL OVERRIDE;

  region_id m_rid;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <region_svalue *>::test (svalue *sval)
{
  return sval->get_kind () == SK_REGION;
}

namespace ana {

/* Concrete subclass of svalue representing a specific constant value.  */

class constant_svalue : public svalue
{
public:
  constant_svalue (tree cst_expr)
  : svalue (TREE_TYPE (cst_expr)), m_cst_expr (cst_expr)
  {
    gcc_assert (cst_expr);
    gcc_assert (CONSTANT_CLASS_P (cst_expr));
  }

  bool compare_fields (const constant_svalue &other) const;

  svalue *clone () const FINAL OVERRIDE
  { return new constant_svalue (m_cst_expr); }

  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_CONSTANT; }

  void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;

  constant_svalue *dyn_cast_constant_svalue () FINAL OVERRIDE { return this; }
  const constant_svalue *dyn_cast_constant_svalue () const FINAL OVERRIDE
  { return this; }

  tree get_constant () const { return m_cst_expr; }

  static void merge_values (const constant_svalue &cst_sval_a,
			    const constant_svalue &cst_sval_b,
			    svalue_id *merged_sid,
			    model_merger *merger);

  static tristate eval_condition (constant_svalue *lhs,
				  enum tree_code op,
				  constant_svalue *rhs);

  svalue_id get_child_sid (region *parent, region *child,
			   region_model &model,
			   region_model_context *ctxt) FINAL OVERRIDE;

 private:
  void print_details (const region_model &model,
		      svalue_id this_sid,
		      pretty_printer *pp) const
    FINAL OVERRIDE;

  tree m_cst_expr;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <constant_svalue *>::test (svalue *sval)
{
  return sval->get_kind () == SK_CONSTANT;
}

namespace ana {

/* Concrete subclass of svalue representing a unique but unknown value.
   Comparisons of variables that share the same unknown value are known
   to be equal, even if we don't know what the value is.  */

class unknown_svalue : public svalue
{
public:
  unknown_svalue (tree type)
  : svalue (type)
  {}

  bool compare_fields (const unknown_svalue &other) const;

  svalue *clone () const FINAL OVERRIDE
  { return new unknown_svalue (get_type ()); }

  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_UNKNOWN; }

  void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;

  unknown_svalue *dyn_cast_unknown_svalue () FINAL OVERRIDE { return this; }

 private:
  void print_details (const region_model &model,
		      svalue_id this_sid,
		      pretty_printer *pp) 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:
  poisoned_svalue (enum poison_kind kind, tree type)
  : svalue (type), m_kind (kind) {}

  bool compare_fields (const poisoned_svalue &other) const;

  svalue *clone () const FINAL OVERRIDE
  { return new poisoned_svalue (m_kind, get_type ()); }

  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_POISONED; }

  void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;

  poisoned_svalue *dyn_cast_poisoned_svalue () FINAL OVERRIDE { return this; }

  enum poison_kind get_poison_kind () const { return m_kind; }

 private:
  void print_details (const region_model &model,
		      svalue_id this_sid,
		      pretty_printer *pp) const
    FINAL OVERRIDE;

  enum poison_kind m_kind;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <poisoned_svalue *>::test (svalue *sval)
{
  return sval->get_kind () == SK_POISONED;
}

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);
  }

  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:
  setjmp_svalue (const setjmp_record &setjmp_record,
		 tree type)
  : svalue (type), m_setjmp_record (setjmp_record)
  {}

  bool compare_fields (const setjmp_svalue &other) const;

  svalue *clone () const FINAL OVERRIDE
  { return new setjmp_svalue (m_setjmp_record, get_type ()); }

  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_SETJMP; }

  void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;

  setjmp_svalue *dyn_cast_setjmp_svalue () FINAL OVERRIDE { return this; }

  int get_enode_index () const;

  const setjmp_record &get_setjmp_record () const { return m_setjmp_record; }

 private:
  void print_details (const region_model &model,
		      svalue_id this_sid,
		      pretty_printer *pp) const
    FINAL OVERRIDE;

  setjmp_record m_setjmp_record;
};

/* An enum for discriminating between the different concrete subclasses
   of region.  */

enum region_kind
{
  RK_PRIMITIVE,
  RK_STRUCT,
  RK_UNION,
  RK_FRAME,
  RK_GLOBALS,
  RK_CODE,
  RK_FUNCTION,
  RK_ARRAY,
  RK_STACK,
  RK_HEAP,
  RK_ROOT,
  RK_SYMBOLIC
};

extern const char *region_kind_to_str (enum region_kind);

/* Region and its subclasses.

   The class hierarchy looks like this (using indentation to show
   inheritance, and with region_kinds shown for the concrete subclasses):

   region
     primitive_region (RK_PRIMITIVE)
     map_region
       struct_or_union_region
         struct_region (RK_STRUCT)
         union_region (RK_UNION)
       scope_region
         frame_region (RK_FRAME)
         globals_region (RK_GLOBALS)
       code_region (RK_CODE)
       function_region (RK_FUNCTION)
     array_region (RK_ARRAY)
     stack_region (RK_STACK)
     heap_region (RK_HEAP)
     root_region (RK_ROOT)
     label_region (RK_FUNCTION)
     symbolic_region (RK_SYMBOLIC).  */

/* Abstract base class representing a chunk of memory.

   Regions form a tree-like hierarchy, with a root region at the base,
   with memory space regions within it, representing the stack and
   globals, with frames within the stack, and regions for variables
   within the frames and the "globals" region.  Regions for structs
   can have subregions for fields.

   A region can optionally have a value, or inherit its value from
   the first ancestor with a value.  For example, the stack region
   has a "uninitialized" poison value which is inherited by all
   descendent regions that don't themselves have a value.  */

class region
{
public:
  virtual ~region () {}

  bool operator== (const region &other) const;
  bool operator!= (const region &other) const { return !(*this == other); }

  virtual region *clone () const = 0;

  virtual enum region_kind get_kind () const = 0;
  virtual map_region *dyn_cast_map_region () { return NULL; }
  virtual array_region *dyn_cast_array_region () { return NULL; }
  virtual symbolic_region *dyn_cast_symbolic_region () { return NULL; }
  virtual const symbolic_region *dyn_cast_symbolic_region () const { return NULL; }

  region_id get_parent () const { return m_parent_rid; }
  region *get_parent_region (const region_model &model) const;

  void set_value (region_model &model, region_id this_rid, svalue_id rhs_sid,
		  region_model_context *ctxt);
  svalue_id get_value (region_model &model, bool non_null,
		       region_model_context *ctxt);
  svalue_id get_value_direct () const { return m_sval_id; }

  svalue_id get_inherited_child_sid (region *child,
				     region_model &model,
				     region_model_context *ctxt);

  tree get_type () const { return m_type; }

  hashval_t hash () const;

  void print (const region_model &model,
	      region_id this_rid,
	      pretty_printer *pp) const;

  virtual void dump_dot_to_pp (const region_model &model,
			       region_id this_rid,
			       pretty_printer *pp) const;

  void dump_to_pp (const region_model &model,
		   region_id this_rid,
		   pretty_printer *pp,
		   const char *prefix,
		   bool is_last_child) const;
  virtual void dump_child_label (const region_model &model,
				 region_id this_rid,
				 region_id child_rid,
				 pretty_printer *pp) const;

  void remap_svalue_ids (const svalue_id_map &map);
  virtual void remap_region_ids (const region_id_map &map);

  virtual void walk_for_canonicalization (canonicalization *c) const = 0;

  void add_view (region_id view_rid, region_model *model);
  region_id get_view (tree type, region_model *model) const;
  region_id get_active_view () const { return m_active_view_rid; }
  bool is_view_p () const { return m_is_view; }

  virtual void validate (const region_model &model) const;

  bool non_null_p (const region_model &model) const;

 protected:
  region (region_id parent_rid, svalue_id sval_id, tree type);
  region (const region &other);

  virtual void add_to_hash (inchash::hash &hstate) const;
  virtual void print_fields (const region_model &model,
			     region_id this_rid,
			     pretty_printer *pp) const;

 private:
  void become_active_view (region_model &model, region_id this_rid);
  void deactivate_any_active_view (region_model &model);
  void deactivate_view (region_model &model, region_id this_view_rid);

  region_id m_parent_rid;
  svalue_id m_sval_id;
  tree m_type;
  /* Child regions that are "views" (one per type).  */
  auto_vec<region_id> m_view_rids;

  bool m_is_view;
  region_id m_active_view_rid;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <region *>::test (region *)
{
  return true;
}

namespace ana {

/* Concrete region subclass for storing "primitive" types (integral types,
   pointers, etc).  */

class primitive_region : public region
{
public:
  primitive_region (region_id parent_rid, tree type)
  : region (parent_rid, svalue_id::null (), type)
  {}

  region *clone () const FINAL OVERRIDE;

  enum region_kind get_kind () const FINAL OVERRIDE { return RK_PRIMITIVE; }

  void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
};

/* A region that has children identified by tree keys.
   For example a stack frame has subregions per local, and a region
   for a struct has subregions per field.  */

class map_region : public region
{
public:
  typedef ordered_hash_map<tree, region_id> map_t;
  typedef map_t::iterator iterator_t;

  map_region (region_id parent_rid, tree type)
  : region (parent_rid, svalue_id::null (), type)
  {}
  map_region (const map_region &other);

  map_region *dyn_cast_map_region () FINAL OVERRIDE { return this; }

  void dump_dot_to_pp (const region_model &model,
		       region_id this_rid,
		       pretty_printer *pp) const
    FINAL OVERRIDE;

  void dump_child_label (const region_model &model,
			 region_id this_rid,
			 region_id child_rid,
			 pretty_printer *pp) const
    FINAL OVERRIDE;

  region_id get_or_create (region_model *model,
			   region_id this_rid,
			   tree expr, tree type,
			   region_model_context *ctxt);
  void unbind (tree expr);
  region_id *get (tree expr);

  void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;

  tree get_tree_for_child_region (region_id child_rid) const;

  tree get_tree_for_child_region (region *child,
				  const region_model &model) const;

  static bool can_merge_p (const map_region *map_region_a,
			   const map_region *map_region_b,
			   map_region *merged_map_region,
			   region_id merged_rid,
			   model_merger *merger);

  void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;

  virtual bool valid_key_p (tree key) const = 0;

  svalue_id get_value_by_name (tree identifier,
			       const region_model &model) const;

  iterator_t begin () { return m_map.begin (); }
  iterator_t end () { return m_map.end (); }
  size_t elements () const { return m_map.elements (); }

 protected:
  bool compare_fields (const map_region &other) const;
  void add_to_hash (inchash::hash &hstate) const OVERRIDE;
  void print_fields (const region_model &model,
		     region_id this_rid,
		     pretty_printer *pp) const
    OVERRIDE;
  void validate (const region_model &model) const FINAL OVERRIDE;

 private:
  /* Mapping from tree to child region.  */
  map_t m_map;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <map_region *>::test (region *reg)
{
  return (reg->dyn_cast_map_region () != NULL);
}

namespace ana {

/* Abstract subclass representing a region with fields
   (either a struct or a union).  */

class struct_or_union_region : public map_region
{
public:
  bool valid_key_p (tree key) const FINAL OVERRIDE;

 protected:
  struct_or_union_region (region_id parent_rid, tree type)
  : map_region (parent_rid, type)
  {}

  bool compare_fields (const struct_or_union_region &other) const;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <struct_or_union_region *>::test (region *reg)
{
  return (reg->get_kind () == RK_STRUCT
	  || reg->get_kind () == RK_UNION);
}

namespace ana {

/* Concrete region subclass.  A map_region representing a struct, using
   FIELD_DECLs for its keys.  */

class struct_region : public struct_or_union_region
{
public:
  struct_region (region_id parent_rid, tree type)
  : struct_or_union_region (parent_rid, type)
  {
    gcc_assert (TREE_CODE (type) == RECORD_TYPE);
  }

  region *clone () const FINAL OVERRIDE;

  enum region_kind get_kind () const FINAL OVERRIDE { return RK_STRUCT; }

  bool compare_fields (const struct_region &other) const;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <struct_region *>::test (region *reg)
{
  return reg->get_kind () == RK_STRUCT;
}

namespace ana {

/* Concrete region subclass.  A map_region representing a union, using
   FIELD_DECLs for its keys.  */

class union_region : public struct_or_union_region
{
public:
  union_region (region_id parent_rid, tree type)
  : struct_or_union_region (parent_rid, type)
  {
    gcc_assert (TREE_CODE (type) == UNION_TYPE);
  }

  region *clone () const FINAL OVERRIDE;

  enum region_kind get_kind () const FINAL OVERRIDE { return RK_UNION; }

  bool compare_fields (const union_region &other) const;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <union_region *>::test (region *reg)
{
  return reg->get_kind () == RK_UNION;
}

namespace ana {

/* Abstract map_region subclass for accessing decls, used as a base class
   for function frames and for the globals region.  */

class scope_region : public map_region
{
 public:

 protected:
  scope_region (region_id parent_rid)
  : map_region (parent_rid, NULL_TREE)
  {}

  scope_region (const scope_region &other)
  : map_region (other)
  {
  }

  bool compare_fields (const scope_region &other) const;
};

/* Concrete region subclass, representing a function frame on the stack,
   to contain the locals.  */

class frame_region : public scope_region
{
public:
  frame_region (region_id parent_rid, function *fun, int depth)
  : scope_region (parent_rid), m_fun (fun), m_depth (depth)
  {}

  frame_region (const frame_region &other)
  : scope_region (other), m_fun (other.m_fun), m_depth (other.m_depth)
  {
  }

  /* region vfuncs.  */
  region *clone () const FINAL OVERRIDE;
  enum region_kind get_kind () const FINAL OVERRIDE { return RK_FRAME; }
  void print_fields (const region_model &model,
		     region_id this_rid,
		     pretty_printer *pp) const
    FINAL OVERRIDE;
  void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;

  /* map_region vfuncs.  */
  bool valid_key_p (tree key) const FINAL OVERRIDE;

  /* Accessors.  */
  function *get_function () const { return m_fun; }
  int get_depth () const { return m_depth; }

  bool compare_fields (const frame_region &other) const;

 private:
  function *m_fun;
  int m_depth;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <frame_region *>::test (region *reg)
{
  return reg->get_kind () == RK_FRAME;
}

namespace ana {

/* Concrete region subclass, to hold global variables (data and bss).  */

class globals_region : public scope_region
{
 public:
  globals_region (region_id parent_rid)
  : scope_region (parent_rid)
  {}

  globals_region (const globals_region &other)
  : scope_region (other)
  {
  }

  /* region vfuncs.  */
  region *clone () const FINAL OVERRIDE;
  enum region_kind get_kind () const FINAL OVERRIDE { return RK_GLOBALS; }

  /* map_region vfuncs.  */
  bool valid_key_p (tree key) const FINAL OVERRIDE;

  bool compare_fields (const globals_region &other) const;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <globals_region *>::test (region *reg)
{
  return reg->get_kind () == RK_GLOBALS;
}

namespace ana {

/* Concrete region subclass.  A map_region representing the code, using
   FUNCTION_DECLs for its keys.  */

class code_region : public map_region
{
public:
  code_region (region_id parent_rid)
  : map_region (parent_rid, NULL_TREE)
  {}
  code_region (const code_region &other)
  : map_region (other)
  {}

  /* region vfuncs.  */
  region *clone () const FINAL OVERRIDE;
  enum region_kind get_kind () const FINAL OVERRIDE { return RK_CODE; }

  /* map_region vfunc.  */
  bool valid_key_p (tree key) const FINAL OVERRIDE;

  region_id get_element (region_model *model,
			 region_id this_rid,
			 svalue_id index_sid,
			 region_model_context *ctxt);

  bool compare_fields (const code_region &other) const;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <code_region *>::test (region *reg)
{
  return reg->get_kind () == RK_CODE;
}

namespace ana {

/* Concrete region subclass.  A map_region representing the code for
   a particular function, using LABEL_DECLs for its keys.  */

class function_region : public map_region
{
public:
  function_region (region_id parent_rid, tree type)
  : map_region (parent_rid, type)
  {
    gcc_assert (FUNC_OR_METHOD_TYPE_P (type));
  }
  function_region (const function_region &other)
  : map_region (other)
  {}

  /* region vfuncs.  */
  region *clone () const FINAL OVERRIDE;
  enum region_kind get_kind () const FINAL OVERRIDE { return RK_FUNCTION; }

  /* map_region vfunc.  */
  bool valid_key_p (tree key) const FINAL OVERRIDE;

  region_id get_element (region_model *model,
			 region_id this_rid,
			 svalue_id index_sid,
			 region_model_context *ctxt);

  bool compare_fields (const function_region &other) const;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <function_region *>::test (region *reg)
{
  return reg->get_kind () == RK_FUNCTION;
}

namespace ana {

/* Concrete region subclass representing an array (or an array-like view
   of a parent region of memory.
   This can't be a map_region as we can't use trees as the keys: there's
   no guarantee about the uniqueness of an INTEGER_CST.  */

class array_region : public region
{
public:
#if 0
  wide_int m_test;

  typedef wide_int key_t;
  typedef int_hash <wide_int, -1, -2> hash_t;
  typedef ordered_hash_map<hash_t, region_id> map_t;
#else
  typedef int key_t;
  typedef int_hash <int, -1, -2> int_hash_t;
  typedef ordered_hash_map<int_hash_t, region_id> map_t;
#endif
  typedef map_t::iterator iterator_t;

  array_region (region_id parent_rid, tree type)
  : region (parent_rid, svalue_id::null (), type)
  {
    gcc_assert (TREE_CODE (type) == ARRAY_TYPE);
  }
  array_region (const array_region &other);

  void dump_dot_to_pp (const region_model &model,
		       region_id this_rid,
		       pretty_printer *pp) const
    FINAL OVERRIDE;

  void dump_child_label (const region_model &model,
			 region_id this_rid,
			 region_id child_rid,
			 pretty_printer *pp) const
    FINAL OVERRIDE;

  /* region vfuncs.  */
  region *clone () const FINAL OVERRIDE;
  enum region_kind get_kind () const FINAL OVERRIDE { return RK_ARRAY; }
  array_region *dyn_cast_array_region () { return this; }

  region_id get_element (region_model *model,
			 region_id this_rid,
			 svalue_id index_sid,
			 region_model_context *ctxt);

  bool compare_fields (const array_region &other) const;

  static bool can_merge_p (const array_region *array_region_a,
			   const array_region *array_region_b,
			   array_region *merged_array_region,
			   region_id merged_rid,
			   model_merger *merger);

  void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;

  iterator_t begin () { return m_map.begin (); }
  iterator_t end () { return m_map.end (); }
  size_t elements () const { return m_map.elements (); }

  region_id get_or_create (region_model *model,
			   region_id this_rid,
			   key_t key, tree type,
			   region_model_context *ctxt);
//  void unbind (int expr);
  region_id *get (key_t key);

  void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;

  bool get_key_for_child_region (region_id child_rid,
				 key_t *out) const;

#if 0
  bool get_key_for_child_region (region *child,
				 const region_model &model,
				 key_t *out) const;
#endif

  void add_to_hash (inchash::hash &hstate) const OVERRIDE;
  void print_fields (const region_model &model,
		     region_id this_rid,
		     pretty_printer *pp) const
    OVERRIDE;
  void validate (const region_model &model) const FINAL OVERRIDE;

  static key_t key_from_constant (tree cst);
  tree constant_from_key (key_t key);

 private:
  static int key_cmp (const void *, const void *);

  /* Mapping from tree to child region.  */
  map_t m_map;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <array_region *>::test (region *reg)
{
  return reg->get_kind () == RK_ARRAY;
}

namespace ana {

/* Concrete region subclass representing a stack, containing all stack
   frames, and implicitly providing a POISON_KIND_UNINIT value to all
   child regions by default.  */

class stack_region : public region
{
public:
  stack_region (region_id parent_rid, svalue_id sval_id)
  : region (parent_rid, sval_id, NULL_TREE)
  {}

  stack_region (const stack_region &other);

  bool compare_fields (const stack_region &other) const;

  region *clone () const FINAL OVERRIDE;

  enum region_kind get_kind () const FINAL OVERRIDE { return RK_STACK; }

  void dump_child_label (const region_model &model,
			 region_id this_rid,
			 region_id child_rid,
			 pretty_printer *pp) const
    FINAL OVERRIDE;

  void push_frame (region_id frame_rid);
  region_id get_current_frame_id () const;
  void pop_frame (region_model *model, region_id result_dst_rid,
		  bool purge, purge_stats *stats,
		  region_model_context *ctxt);

  void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;

  unsigned get_num_frames () const { return m_frame_rids.length (); }
  region_id get_frame_rid (unsigned i) const { return m_frame_rids[i]; }

  static bool can_merge_p (const stack_region *stack_region_a,
			   const stack_region *stack_region_b,
			   model_merger *merger);

  void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;

  svalue_id get_value_by_name (tree identifier,
			       const region_model &model) const;

  void validate (const region_model &model) const FINAL OVERRIDE;

 private:
  void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
  void print_fields (const region_model &model,
		     region_id this_rid,
		     pretty_printer *pp) const
    FINAL OVERRIDE;

  auto_vec<region_id> m_frame_rids;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <stack_region *>::test (region *reg)
{
  return reg->get_kind () == RK_STACK;
}

namespace ana {

/* Concrete region subclass: a region within which regions can be
   dynamically allocated.  */

class heap_region : public region
{
public:
  heap_region (region_id parent_rid, svalue_id sval_id)
  : region (parent_rid, sval_id, NULL_TREE)
  {}
  heap_region (const heap_region &other);

  bool compare_fields (const heap_region &other) const;

  region *clone () const FINAL OVERRIDE;

  enum region_kind get_kind () const FINAL OVERRIDE { return RK_HEAP; }

  static bool can_merge_p (const heap_region *heap_a, region_id heap_a_rid,
			   const heap_region *heap_b, region_id heap_b_rid,
			   heap_region *merged_heap, region_id merged_heap_rid,
			   model_merger *merger);

  void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;

};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <heap_region *>::test (region *reg)
{
  return reg->get_kind () == RK_HEAP;
}

namespace ana {

/* Concrete region subclass.  The root region, containing all regions
   (either directly, or as descendents).
   Unique within a region_model.  */

class root_region : public region
{
public:
  root_region ();
  root_region (const root_region &other);

  bool compare_fields (const root_region &other) const;

  region *clone () const FINAL OVERRIDE;

  enum region_kind get_kind () const FINAL OVERRIDE { return RK_ROOT; }

  void dump_child_label (const region_model &model,
			 region_id this_rid,
			 region_id child_rid,
			 pretty_printer *pp) const
    FINAL OVERRIDE;

  region_id push_frame (region_model *model, function *fun,
			vec<svalue_id> *arg_sids,
			region_model_context *ctxt);
  region_id get_current_frame_id (const region_model &model) const;
  void pop_frame (region_model *model, region_id result_dst_rid,
		  bool purge, purge_stats *stats,
		  region_model_context *ctxt);

  region_id ensure_stack_region (region_model *model);
  region_id get_stack_region_id () const { return m_stack_rid; }
  stack_region *get_stack_region (const region_model *model) const;

  region_id ensure_globals_region (region_model *model);
  region_id get_globals_region_id () const { return m_globals_rid; }
  globals_region *get_globals_region (const region_model *model) const;

  region_id ensure_code_region (region_model *model);
  code_region *get_code_region (const region_model *model) const;

  region_id ensure_heap_region (region_model *model);
  heap_region *get_heap_region (const region_model *model) const;

  void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;

  static bool can_merge_p (const root_region *root_region_a,
			   const root_region *root_region_b,
			   root_region *merged_root_region,
			   model_merger *merger);

  void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;

  svalue_id get_value_by_name (tree identifier,
			       const region_model &model) const;

  void validate (const region_model &model) const FINAL OVERRIDE;

private:
  void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
  void print_fields (const region_model &model,
		     region_id this_rid,
		     pretty_printer *pp) const
    FINAL OVERRIDE;

  region_id m_stack_rid;
  region_id m_globals_rid;
  region_id m_code_rid;
  region_id m_heap_rid;
};

} // namespace ana

template <>
template <>
inline bool
is_a_helper <root_region *>::test (region *reg)
{
  return reg->get_kind () == RK_ROOT;
}

namespace ana {

/* Concrete region subclass: a region to use when dereferencing an unknown
   pointer.  */

class symbolic_region : public region
{
public:
  symbolic_region (region_id parent_rid, tree type, bool possibly_null)
  : region (parent_rid, svalue_id::null (), type),
    m_possibly_null (possibly_null)
  {}
  symbolic_region (const symbolic_region &other);

  const symbolic_region *dyn_cast_symbolic_region () const FINAL OVERRIDE
  { return this; }
  symbolic_region *dyn_cast_symbolic_region () FINAL OVERRIDE
  { return this; }

  bool compare_fields (const symbolic_region &other) const;

  region *clone () const FINAL OVERRIDE;

  enum region_kind get_kind () const FINAL OVERRIDE { return RK_SYMBOLIC; }

  void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;

  void print_fields (const region_model &model,
		     region_id this_rid,
		     pretty_printer *pp) const FINAL OVERRIDE;

  bool m_possibly_null;
};

/* A region_model encapsulates a representation of the state of memory, with
   a tree of regions, along with their associated values.
   The representation is graph-like because values can be pointers to
   regions.
   It also stores a constraint_manager, capturing relationships between
   the values.  */

class region_model
{
 public:
  region_model ();
  region_model (const region_model &other);
  ~region_model ();

#if 0//__cplusplus >= 201103
  region_model (region_model &&other);
#endif

  region_model &operator= (const region_model &other);

  bool operator== (const region_model &other) const;
  bool operator!= (const region_model &other) const
  {
    return !(*this == other);
  }

  hashval_t hash () const;

  void print (pretty_printer *pp) const;

  void print_svalue (svalue_id sid, pretty_printer *pp) const;

  void dump_dot_to_pp (pretty_printer *pp) const;
  void dump_dot_to_file (FILE *fp) const;
  void dump_dot (const char *path) const;

  void dump_to_pp (pretty_printer *pp, bool summarize) const;
  void dump (FILE *fp, bool summarize) const;
  void dump (bool summarize) const;

  void debug () const;

  void validate () const;

  void canonicalize (region_model_context *ctxt);
  bool canonicalized_p () const;

  void check_for_poison (tree expr, region_model_context *ctxt);
  void on_assignment (const gassign *stmt, region_model_context *ctxt);
  bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
  void on_call_post (const gcall *stmt,
		     bool unknown_side_effects,
		     region_model_context *ctxt);
  void handle_unrecognized_call (const gcall *call,
				 region_model_context *ctxt);
  void on_return (const greturn *stmt, region_model_context *ctxt);
  void on_setjmp (const gcall *stmt, const exploded_node *enode,
		  region_model_context *ctxt);
  void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
		   int setjmp_stack_depth, region_model_context *ctxt);

  void update_for_phis (const supernode *snode,
			const cfg_superedge *last_cfg_superedge,
			region_model_context *ctxt);

  void handle_phi (const gphi *phi,
		   tree lhs, tree rhs, bool is_back_edge,
		   region_model_context *ctxt);

  bool maybe_update_for_edge (const superedge &edge,
			      const gimple *last_stmt,
			      region_model_context *ctxt);

  region_id get_root_rid () const { return m_root_rid; }
  root_region *get_root_region () const;

  region_id get_stack_region_id () const;
  region_id push_frame (function *fun, vec<svalue_id> *arg_sids,
			region_model_context *ctxt);
  region_id get_current_frame_id () const;
  function * get_current_function () const;
  void pop_frame (region_id result_dst_rid,
		  bool purge, purge_stats *stats,
		  region_model_context *ctxt);
  int get_stack_depth () const;
  function *get_function_at_depth (unsigned depth) const;

  region_id get_globals_region_id () const;

  svalue_id add_svalue (svalue *sval);
  void replace_svalue (svalue_id sid, svalue *new_sval);

  region_id add_region (region *r);

  region_id add_region_for_type (region_id parent_rid, tree type,
				 region_model_context *ctxt);

  svalue *get_svalue (svalue_id sval_id) const;
  region *get_region (region_id rid) const;

  template <typename Subclass>
  Subclass *get_region (region_id rid) const
  {
    region *result = get_region (rid);
    if (result)
      gcc_assert (is_a<Subclass *> (result));
    return (Subclass *)result;
  }

  region_id get_lvalue (path_var pv, region_model_context *ctxt);
  region_id get_lvalue (tree expr, region_model_context *ctxt);
  svalue_id get_rvalue (path_var pv, region_model_context *ctxt);
  svalue_id get_rvalue (tree expr, region_model_context *ctxt);

  svalue_id get_or_create_ptr_svalue (tree ptr_type, region_id id);
  svalue_id get_or_create_constant_svalue (tree cst_expr);
  svalue_id get_svalue_for_fndecl (tree ptr_type, tree fndecl,
				   region_model_context *ctxt);
  svalue_id get_svalue_for_label (tree ptr_type, tree label,
				  region_model_context *ctxt);

  region_id get_region_for_fndecl (tree fndecl, region_model_context *ctxt);
  region_id get_region_for_label (tree label, region_model_context *ctxt);

  svalue_id maybe_cast (tree type, svalue_id sid, region_model_context *ctxt);
  svalue_id maybe_cast_1 (tree type, svalue_id sid);

  region_id get_field_region (region_id rid, tree field,
			      region_model_context *ctxt);

  region_id deref_rvalue (svalue_id ptr_sid, region_model_context *ctxt);
  region_id deref_rvalue (tree ptr, region_model_context *ctxt);

  void set_value (region_id lhs_rid, svalue_id rhs_sid,
		  region_model_context *ctxt);
  void set_value (tree lhs, tree rhs, region_model_context *ctxt);
  svalue_id set_to_new_unknown_value (region_id dst_rid, tree type,
				      region_model_context *ctxt);

  void copy_region (region_id dst_rid, region_id src_rid,
		    region_model_context *ctxt);

  tristate eval_condition (svalue_id lhs,
			   enum tree_code op,
			   svalue_id rhs) const;
  tristate eval_condition_without_cm (svalue_id lhs,
				      enum tree_code op,
				      svalue_id rhs) const;
  tristate eval_condition (tree lhs,
			   enum tree_code op,
			   tree rhs,
			   region_model_context *ctxt);
  bool add_constraint (tree lhs, enum tree_code op, tree rhs,
		       region_model_context *ctxt);

  tree maybe_get_constant (svalue_id sid) const;

  region_id add_new_malloc_region ();

  tree get_representative_tree (svalue_id sid) const;
  path_var get_representative_path_var (region_id rid) const;
  void get_path_vars_for_svalue (svalue_id sid, vec<path_var> *out) const;

  void purge_unused_svalues (purge_stats *out,
			     region_model_context *ctxt,
			     svalue_id_set *known_used_sids = NULL);
  void remap_svalue_ids (const svalue_id_map &map);
  void remap_region_ids (const region_id_map &map);

  void purge_regions (const region_id_set &set,
		      purge_stats *stats,
		      logger *logger);

  unsigned get_num_svalues () const { return m_svalues.length (); }
  unsigned get_num_regions () const { return m_regions.length (); }

  /* For selftests.  */
  constraint_manager *get_constraints ()
  {
    return m_constraints;
  }

  void get_descendents (region_id rid, region_id_set *out,
			region_id exclude_rid) const;

  void delete_region_and_descendents (region_id rid,
				      enum poison_kind pkind,
				      purge_stats *stats,
				      logger *logger);

  bool can_merge_with_p (const region_model &other_model,
			 region_model *out_model,
			 svalue_id_merger_mapping *out) const;
  bool can_merge_with_p (const region_model &other_model,
			 region_model *out_model) const;

  svalue_id get_value_by_name (const char *name) const;

  svalue_id convert_byte_offset_to_array_index (tree ptr_type,
						svalue_id offset_sid);

  region_id get_or_create_mem_ref (tree type,
				   svalue_id ptr_sid,
				   svalue_id offset_sid,
				   region_model_context *ctxt);
  region_id get_or_create_pointer_plus_expr (tree type,
					     svalue_id ptr_sid,
					     svalue_id offset_sid,
					     region_model_context *ctxt);
  region_id get_or_create_view (region_id raw_rid, tree type,
				region_model_context *ctxt);

  tree get_fndecl_for_call (const gcall *call,
			    region_model_context *ctxt);

 private:
  region_id get_lvalue_1 (path_var pv, region_model_context *ctxt);
  svalue_id get_rvalue_1 (path_var pv, region_model_context *ctxt);

  void copy_struct_region (region_id dst_rid, struct_region *dst_reg,
			   struct_region *src_reg, region_model_context *ctxt);
  void copy_union_region (region_id dst_rid, union_region *src_reg,
			  region_model_context *ctxt);
  void copy_array_region (region_id dst_rid, array_region *dst_reg,
			  array_region *src_reg, region_model_context *ctxt);

  region_id make_region_for_unexpected_tree_code (region_model_context *ctxt,
						  tree t,
						  const dump_location_t &loc);

  void add_any_constraints_from_ssa_def_stmt (tree lhs,
					      enum tree_code op,
					      tree rhs,
					      region_model_context *ctxt);
  void add_any_constraints_from_gassign (enum tree_code op,
					 tree rhs,
					 const gassign *assign,
					 region_model_context *ctxt);
  void add_any_constraints_from_gcall (enum tree_code op,
				       tree rhs,
				       const gcall *call,
				       region_model_context *ctxt);

  void update_for_call_superedge (const call_superedge &call_edge,
				  region_model_context *ctxt);
  void update_for_return_superedge (const return_superedge &return_edge,
				    region_model_context *ctxt);
  void update_for_call_summary (const callgraph_superedge &cg_sedge,
				region_model_context *ctxt);
  bool apply_constraints_for_gcond (const cfg_superedge &edge,
				    const gcond *cond_stmt,
				    region_model_context *ctxt);
  bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
				      const gswitch *switch_stmt,
				      region_model_context *ctxt);

  void poison_any_pointers_to_bad_regions (const region_id_set &bad_regions,
					   enum poison_kind pkind);

  void dump_summary_of_rep_path_vars (pretty_printer *pp,
				      auto_vec<path_var> *rep_path_vars,
				      bool *is_first);

  auto_delete_vec<svalue> m_svalues;
  auto_delete_vec<region> m_regions;
  region_id m_root_rid;
  constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
};

/* Some region_model activity could lead to warnings (e.g. attempts to use an
   uninitialized value).  This abstract base class encapsulates an interface
   for the region model to use when emitting such warnings.

   It also provides an interface for being notified about svalue_ids being
   remapped, and being deleted.

   Having this as an abstract base class allows us to support the various
   operations needed by program_state in the analyzer within region_model,
   whilst keeping them somewhat modularized.  */

class region_model_context
{
 public:
  virtual void warn (pending_diagnostic *d) = 0;

  /* Hook for clients that store svalue_id instances, so that they
     can remap their IDs when the underlying region_model renumbers
     the IDs.  */
  virtual void remap_svalue_ids (const svalue_id_map &map) = 0;

#if 0
  /* Return true if if's OK to purge SID when simplifying state.
     Subclasses can return false for values that have sm state,
     to avoid generating "leak" false positives.  */
  virtual bool can_purge_p (svalue_id sid) = 0;
#endif

  /* Hook for clients to be notified when a range of SIDs have
     been purged, so that they can purge state relating to those
     values (and potentially emit warnings about leaks).
     All SIDs from FIRST_PURGED_SID numerically upwards are being
     purged.
     The return values is a count of how many items of data the client
     has purged (potentially for use in selftests).
     MAP has already been applied to the IDs, but is provided in case
     the client needs to figure out the old IDs.  */
  virtual int on_svalue_purge (svalue_id first_purged_sid,
			       const svalue_id_map &map) = 0;

  virtual logger *get_logger () = 0;

  /* Hook for clients to be notified when CHILD_SID is created
     from PARENT_SID, when "inheriting" a value for a region from a
     parent region.
     This exists so that state machines that inherit state can
     propagate the state from parent to child.  */
  virtual void on_inherited_svalue (svalue_id parent_sid,
				    svalue_id child_sid) = 0;

  /* Hook for clients to be notified when DST_SID is created
     (or reused) as a cast from SRC_SID.
     This exists so that state machines can propagate the state
     from SRC_SID to DST_SID.  */
  virtual void on_cast (svalue_id src_sid,
			svalue_id dst_sid) = 0;

  /* Hook for clients to be notified when the condition
     "LHS OP RHS" is added to the region model.
     This exists so that state machines can detect tests on edges,
     and use them to trigger sm-state transitions (e.g. transitions due
     to ptrs becoming known to be NULL or non-NULL, rather than just
     "unchecked") */
  virtual void on_condition (tree lhs, enum tree_code op, tree rhs) = 0;

  /* Hooks for clients to be notified when an unknown change happens
     to SID (in response to a call to an unknown function).  */
  virtual void on_unknown_change (svalue_id sid) = 0;

  /* Hooks for clients to be notified when a phi node is handled,
     where RHS is the pertinent argument.  */
  virtual void on_phi (const gphi *phi, tree rhs) = 0;

  /* Hooks for clients to be notified when the region model doesn't
     know how to handle the tree code of T at LOC.  */
  virtual void on_unexpected_tree_code (tree t,
					const dump_location_t &loc) = 0;
};

/* A "do nothing" subclass of region_model_context.  */

class noop_region_model_context : public region_model_context
{
public:
  void warn (pending_diagnostic *) OVERRIDE {}
  void remap_svalue_ids (const svalue_id_map &) OVERRIDE {}
  int on_svalue_purge (svalue_id, const svalue_id_map &) OVERRIDE
  {
    return 0;
  }
  logger *get_logger () OVERRIDE { return NULL; }
  void on_inherited_svalue (svalue_id parent_sid ATTRIBUTE_UNUSED,
			    svalue_id child_sid  ATTRIBUTE_UNUSED)
    OVERRIDE
  {
  }
  void on_cast (svalue_id src_sid ATTRIBUTE_UNUSED,
		svalue_id dst_sid ATTRIBUTE_UNUSED) OVERRIDE
  {
  }
  void on_condition (tree lhs ATTRIBUTE_UNUSED,
		     enum tree_code op ATTRIBUTE_UNUSED,
		     tree rhs ATTRIBUTE_UNUSED) OVERRIDE
  {
  }
  void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) OVERRIDE
  {
  }
  void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
	       tree rhs ATTRIBUTE_UNUSED) OVERRIDE
  {
  }
  void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {}
};

/* A subclass of region_model_context for determining if operations fail
   e.g. "can we generate a region for the lvalue of EXPR?".  */

class tentative_region_model_context : public noop_region_model_context
{
public:
  tentative_region_model_context () : m_num_unexpected_codes (0) {}

  void on_unexpected_tree_code (tree, const dump_location_t &)
    FINAL OVERRIDE
  {
    m_num_unexpected_codes++;
  }

  bool had_errors_p () const { return m_num_unexpected_codes > 0; }

private:
  int m_num_unexpected_codes;
};

/* A bundle of data for use when attempting to merge two region_model
   instances to make a third.  */

struct model_merger
{
  model_merger (const region_model *model_a,
		const region_model *model_b,
		region_model *merged_model,
		svalue_id_merger_mapping *sid_mapping)
  : m_model_a (model_a), m_model_b (model_b),
    m_merged_model (merged_model),
    m_map_regions_from_a_to_m (model_a->get_num_regions ()),
    m_map_regions_from_b_to_m (model_b->get_num_regions ()),
    m_sid_mapping (sid_mapping)
  {
    gcc_assert (sid_mapping);
  }

  void dump_to_pp (pretty_printer *pp) const;
  void dump (FILE *fp) const;
  void dump () const;

  template <typename Subclass>
  Subclass *get_region_a (region_id rid_a) const
  {
    return m_model_a->get_region <Subclass> (rid_a);
  }

  template <typename Subclass>
  Subclass *get_region_b (region_id rid_b) const
  {
    return m_model_b->get_region <Subclass> (rid_b);
  }

  bool can_merge_values_p (svalue_id sid_a,
			   svalue_id sid_b,
			   svalue_id *merged_sid);

  void record_regions (region_id a_rid,
		       region_id b_rid,
		       region_id merged_rid);

  void record_svalues (svalue_id a_sid,
		       svalue_id b_sid,
		       svalue_id merged_sid);

  const region_model *m_model_a;
  const region_model *m_model_b;
  region_model *m_merged_model;

  one_way_region_id_map m_map_regions_from_a_to_m;
  one_way_region_id_map m_map_regions_from_b_to_m;
  svalue_id_merger_mapping *m_sid_mapping;
};

/* A bundle of data that can be optionally generated during merger of two
   region_models that describes how svalue_ids in each of the two inputs
   are mapped to svalue_ids in the merged output.

   For use when merging sm-states within program_state.  */

struct svalue_id_merger_mapping
{
  svalue_id_merger_mapping (const region_model &a,
			    const region_model &b);

  void dump_to_pp (pretty_printer *pp) const;
  void dump (FILE *fp) const;
  void dump () const;

  one_way_svalue_id_map m_map_from_a_to_m;
  one_way_svalue_id_map m_map_from_b_to_m;
};

/* A bundle of data used when canonicalizing a region_model so that the
   order of regions and svalues is in a predictable order (thus increasing
   the chance of two region_models being equal).

   This object is used to keep track of a recursive traversal across the
   svalues and regions within the model, made in a deterministic order,
   assigning new ids the first time each region or svalue is
   encountered.  */

struct canonicalization
{
  canonicalization (const region_model &model);
  void walk_rid (region_id rid);
  void walk_sid (svalue_id sid);

  void dump_to_pp (pretty_printer *pp) const;
  void dump (FILE *fp) const;
  void dump () const;

  const region_model &m_model;
  /* Maps from existing IDs to new IDs.  */
  region_id_map m_rid_map;
  svalue_id_map m_sid_map;
  /* The next IDs to hand out.  */
  int m_next_rid_int;
  int m_next_sid_int;
};

} // namespace ana

namespace inchash
{
  extern void add (svalue_id sid, hash &hstate);
  extern void add (region_id rid, hash &hstate);
} // namespace inchash

extern void debug (const region_model &rmodel);

namespace ana {

#if CHECKING_P

namespace selftest {

using namespace ::selftest;

/* An implementation of region_model_context for use in selftests, which
   stores any pending_diagnostic instances passed to it.  */

class test_region_model_context : public noop_region_model_context
{
public:
  void warn (pending_diagnostic *d) FINAL OVERRIDE
  {
    m_diagnostics.safe_push (d);
  }

  unsigned get_num_diagnostics () const { return m_diagnostics.length (); }

  void on_unexpected_tree_code (tree t, const dump_location_t &)
    FINAL OVERRIDE
  {
    internal_error ("unhandled tree code: %qs",
		    t ? get_tree_code_name (TREE_CODE (t)) : "(null)");
  }

private:
  /* Implicitly delete any diagnostics in the dtor.  */
  auto_delete_vec<pending_diagnostic> m_diagnostics;
};

/* Attempt to add the constraint (LHS OP RHS) to MODEL.
   Verify that MODEL remains satisfiable.  */

#define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS)	\
  SELFTEST_BEGIN_STMT					\
    bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);	\
    ASSERT_TRUE (sat);					\
  SELFTEST_END_STMT

/* Attempt to add the constraint (LHS OP RHS) to MODEL.
   Verify that the result is not satisfiable.  */

#define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS)	\
  SELFTEST_BEGIN_STMT					\
    bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL);	\
    ASSERT_FALSE (sat);				\
  SELFTEST_END_STMT

/* Implementation detail of the ASSERT_CONDITION_* macros.  */

void assert_condition (const location &loc,
		       region_model &model,
		       tree lhs, tree_code op, tree rhs,
		       tristate expected);

/* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
   as "true".  */

#define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
  SELFTEST_BEGIN_STMT							\
  assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,	\
		    tristate (tristate::TS_TRUE));		\
  SELFTEST_END_STMT

/* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
   as "false".  */

#define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
  SELFTEST_BEGIN_STMT							\
  assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,	\
		    tristate (tristate::TS_FALSE));		\
  SELFTEST_END_STMT

/* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
   as "unknown".  */

#define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
  SELFTEST_BEGIN_STMT							\
  assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS,	\
		    tristate (tristate::TS_UNKNOWN));		\
  SELFTEST_END_STMT

} /* end of namespace selftest.  */

#endif /* #if CHECKING_P */

} // namespace ana

#endif /* GCC_ANALYZER_REGION_MODEL_H */