analyzer: eliminate enum binding_key [PR95006]

I rewrote the way the analyzer's region_model tracks the state of memory
in GCC 11 (in 808f4dfeb3a95f50f15e71148e5c1067f90a126d), which
introduced a store with a binding_map class, mapping binding keys to
symbolic values.

The GCC 11 implementation of binding keys has an enum binding_kind,
which can be "default" vs "direct"; the idea being that direct
bindings take priority over default bindings, where the latter could
be used to represent e.g. a zero-fill of a buffer, and the former
expresses those subregions that have since been touched.

This doesn't work well: it doesn't express the idea of filling
different subregions with different values, or a memset that only
touches part of a buffer, leading to numerous XFAILs in the memset
test cases (and elsewhere).

As preparatory work towards tracking uninitialized values, this patch
eliminates the enum binding_kind, so that all bindings have
equal weight; the order in which they happen is all that matters.
If a write happens which partially overwrites an existing binding,
the new code can partially overwrite a binding, potentially punching a
hole so that an existing binding is split into two parts.

The patch adds some new classes:
- a new "bits_within_svalue" symbolic value to support extracting
  parts of an existing value when its binding is partially clobbered
- a new "repeated_svalue" symbolic value to better express filling
  a region with repeated copies of a symbolic value (e.g. constant
  zero)
- a new "sized_region" region to express accessing a subregion
  with a symbolic size in bytes
and it rewrites e.g. how memset is implemented, so that we can precisely
track which bits in a region have not been touched.

That said, the patch doesn't actually implement "uninitialized" values;
I'm saving that for a followup.

gcc/analyzer/ChangeLog:
	PR analyzer/95006
	* analyzer.h (class repeated_svalue): New forward decl.
	(class bits_within_svalue): New forward decl.
	(class sized_region): New forward decl.
	(get_field_at_bit_offset): New forward decl.
	* engine.cc (exploded_graph::get_or_create_node): Validate the
	merged state.
	(exploded_graph::maybe_process_run_of_before_supernode_enodes):
	Validate the states at each stage.
	* program-state.cc (program_state::validate): Validate
	m_region_model.
	* region-model-impl-calls.cc (region_model::impl_call_memset):
	Replace special-case logic for handling constant sizes with
	a call to fill_region of a sized_region with the given fill value.
	* region-model-manager.cc (maybe_undo_optimize_bit_field_compare):
	Drop DK_direct.
	(region_model_manager::maybe_fold_sub_svalue):  Fold element-based
	subregions of an initial value into initial values of an element.
	Fold subvalues of repeated svalues.
	(region_model_manager::maybe_fold_repeated_svalue): New.
	(region_model_manager::get_or_create_repeated_svalue): New.
	(get_bit_range_for_field): New.
	(get_byte_range_for_field): New.
	(get_field_at_byte_range): New.
	(region_model_manager::maybe_fold_bits_within_svalue): New.
	(region_model_manager::get_or_create_bits_within): New.
	(region_model_manager::get_sized_region): New.
	(region_model_manager::log_stats): Update for addition of
	m_repeated_values_map, m_bits_within_values_map, and
	m_sized_regions.
	* region-model.cc (region_model::validate): New.
	(region_model::on_assignment): Drop enum binding_kind.
	(region_model::get_initial_value_for_global): Likewise.
	(region_model::get_rvalue_for_bits): Replace body with call to
	get_or_create_bits_within.
	(region_model::get_capacity): Handle RK_SIZED.
	(region_model::set_value): Drop enum binding_kind.
	(region_model::fill_region): New.
	(region_model::get_representative_path_var_1): Handle RK_SIZED.
	* region-model.h (visitor::visit_repeated_svalue): New.
	(visitor::visit_bits_within_svalue): New.
	(region_model_manager::get_or_create_repeated_svalue): New decl.
	(region_model_manager::get_or_create_bits_within): New decl.
	(region_model_manager::get_sized_region): New decl.
	(region_model_manager::maybe_fold_repeated_svalue): New decl.
	(region_model_manager::maybe_fold_bits_within_svalue): New decl.
	(region_model_manager::repeated_values_map_t): New typedef.
	(region_model_manager::m_repeated_values_map): New field.
	(region_model_manager::bits_within_values_map_t): New typedef.
	(region_model_manager::m_bits_within_values_map): New field.
	(region_model_manager::m_sized_regions): New field.
	(region_model::fill_region): New decl.
	* region.cc (region::get_base_region): Handle RK_SIZED.
	(region::base_region_p): Likewise.
	(region::get_byte_size_sval): New.
	(get_field_at_bit_offset): Make non-static.
	(region::calc_offset): Move implementation of cases to
	get_relative_concrete_offset vfunc implementations.  Handle
	RK_SIZED.
	(region::get_relative_concrete_offset): New.
	(decl_region::get_svalue_for_initializer): Drop enum binding_kind.
	(field_region::get_relative_concrete_offset): New, from
	region::calc_offset.
	(element_region::get_relative_concrete_offset): Likewise.
	(offset_region::get_relative_concrete_offset): Likewise.
	(sized_region::accept): New.
	(sized_region::dump_to_pp): New.
	(sized_region::get_byte_size): New.
	(sized_region::get_bit_size): New.
	* region.h (enum region_kind): Add RK_SIZED.
	(region::dyn_cast_sized_region): New.
	(region::get_byte_size): Make virtual.
	(region::get_bit_size): Likewise.
	(region::get_byte_size_sval): New decl.
	(region::get_relative_concrete_offset): New decl.
	(field_region::get_relative_concrete_offset): New decl.
	(element_region::get_relative_concrete_offset): Likewise.
	(offset_region::get_relative_concrete_offset): Likewise.
	(class sized_region): New.
	* store.cc (binding_kind_to_string): Delete.
	(binding_key::make): Drop enum binding_kind.
	(binding_key::dump_to_pp): Delete.
	(binding_key::cmp_ptrs): Drop enum binding_kind.
	(bit_range::contains_p): New.
	(byte_range::dump): New.
	(byte_range::contains_p): New.
	(byte_range::cmp): New.
	(concrete_binding::dump_to_pp): Drop enum binding_kind.
	(concrete_binding::cmp_ptr_ptr): Likewise.
	(symbolic_binding::dump_to_pp): Likewise.
	(symbolic_binding::cmp_ptr_ptr): Likewise.
	(binding_map::apply_ctor_val_to_range): Likewise.
	(binding_map::apply_ctor_pair_to_child_region): Likewise.
	(binding_map::get_overlapping_bindings): New.
	(binding_map::remove_overlapping_bindings): New.
	(binding_cluster::validate): New.
	(binding_cluster::bind): Drop enum binding_kind.
	(binding_cluster::bind_compound_sval): Likewise.
	(binding_cluster::purge_region): Likewise.
	(binding_cluster::zero_fill_region): Reimplement in terms of...
	(binding_cluster::fill_region): New.
	(binding_cluster::mark_region_as_unknown): Drop enum binding_kind.
	(binding_cluster::get_binding): Likewise.
	(binding_cluster::get_binding_recursive): Likewise.
	(binding_cluster::get_any_binding): Likewise.
	(binding_cluster::maybe_get_compound_binding): Reimplement.
	(binding_cluster::get_overlapping_bindings): Delete.
	(binding_cluster::remove_overlapping_bindings): Reimplement in
	terms of binding_map::remove_overlapping_bindings.
	(binding_cluster::can_merge_p): Update for removal of
	enum binding_kind.
	(binding_cluster::on_unknown_fncall): Drop enum binding_kind.
	(binding_cluster::maybe_get_simple_value): Likewise.
	(store_manager::get_concrete_binding): Likewise.
	(store_manager::get_symbolic_binding): Likewise.
	(store::validate): New.
	(store::set_value): Drop enum binding_kind.
	(store::zero_fill_region): Reimplement in terms of...
	(store::fill_region): New.
	(selftest::test_binding_key_overlap): Drop enum binding_kind.
	* store.h (enum binding_kind): Delete.
	(binding_kind_to_string): Delete decl.
	(binding_key::make): Drop enum binding_kind.
	(binding_key::dump_to_pp): Make pure virtual.
	(binding_key::get_kind): Delete.
	(binding_key::mark_deleted): Delete.
	(binding_key::mark_empty): Delete.
	(binding_key::is_deleted): Delete.
	(binding_key::is_empty): Delete.
	(binding_key::binding_key): Delete.
	(binding_key::impl_hash): Delete.
	(binding_key::impl_eq): Delete.
	(binding_key::m_kind): Delete.
	(bit_range::get_last_bit_offset): New.
	(bit_range::contains_p): New.
	(byte_range::contains_p): New.
	(byte_range::operator==): New.
	(byte_range::get_start_byte_offset): New.
	(byte_range::get_next_byte_offset): New.
	(byte_range::get_last_byte_offset): New.
	(byte_range::as_bit_range): New.
	(byte_range::cmp): New.
	(concrete_binding::concrete_binding): Drop enum binding_kind.
	(concrete_binding::hash): Likewise.
	(concrete_binding::operator==): Likewise.
	(concrete_binding::mark_deleted): New.
	(concrete_binding::mark_empty): New.
	(concrete_binding::is_deleted): New.
	(concrete_binding::is_empty): New.
	(default_hash_traits<ana::concrete_binding>::empty_zero_p): Make false.
	(symbolic_binding::symbolic_binding): Drop enum binding_kind.
	(symbolic_binding::hash): Likewise.
	(symbolic_binding::operator==): Likewise.
	(symbolic_binding::mark_deleted): New.
	(symbolic_binding::mark_empty): New.
	(symbolic_binding::is_deleted): New.
	(symbolic_binding::is_empty): New.
	(binding_map::remove_overlapping_bindings): New decl.
	(binding_map::get_overlapping_bindings): New decl.
	(binding_cluster::validate): New decl.
	(binding_cluster::bind): Drop enum binding_kind.
	(binding_cluster::fill_region): New decl.
	(binding_cluster::get_binding): Drop enum binding_kind.
	(binding_cluster::get_binding_recursive): Likewise.
	(binding_cluster::get_overlapping_bindings): Delete.
	(store::validate): New decl.
	(store::set_value): Drop enum binding_kind.
	(store::fill_region): New decl.
	(store_manager::get_concrete_binding): Drop enum binding_kind.
	(store_manager::get_symbolic_binding): Likewise.
	* svalue.cc (svalue::cmp_ptr): Handle SK_REPEATED and
	SK_BITS_WITHIN.
	(svalue::extract_bit_range): New.
	(svalue::maybe_fold_bits_within): New.
	(constant_svalue::maybe_fold_bits_within): New.
	(unknown_svalue::maybe_fold_bits_within): New.
	(unaryop_svalue::maybe_fold_bits_within): New.
	(repeated_svalue::repeated_svalue): New.
	(repeated_svalue::dump_to_pp): New.
	(repeated_svalue::accept): New.
	(repeated_svalue::all_zeroes_p): New.
	(repeated_svalue::maybe_fold_bits_within): New.
	(bits_within_svalue::bits_within_svalue): New.
	(bits_within_svalue::dump_to_pp): New.
	(bits_within_svalue::maybe_fold_bits_within): New.
	(bits_within_svalue::accept): New.
	(bits_within_svalue::implicitly_live_p): New.
	(compound_svalue::maybe_fold_bits_within): New.
	* svalue.h (enum svalue_kind): Add SK_REPEATED and SK_BITS_WITHIN.
	(svalue::dyn_cast_repeated_svalue): New.
	(svalue::dyn_cast_bits_within_svalue): New.
	(svalue::extract_bit_range): New decl.
	(svalue::maybe_fold_bits_within): New vfunc decl.
	(region_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(region_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<region_svalue::key_t>::empty_zero_p): Make false.
	(constant_svalue::maybe_fold_bits_within): New.
	(unknown_svalue::maybe_fold_bits_within): New.
	(poisoned_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(poisoned_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<poisoned_svalue::key_t>::empty_zero_p): Make
	false.
	(setjmp_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(setjmp_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<setjmp_svalue::key_t>::empty_zero_p): Make
	false.
	(unaryop_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(unaryop_svalue::key_t::is_empty): Likewise.
	(unaryop_svalue::maybe_fold_bits_within): New.
	(default_hash_traits<unaryop_svalue::key_t>::empty_zero_p): Make
	false.
	(binop_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(binop_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<binop_svalue::key_t>::empty_zero_p): Make
	false.
	(sub_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(sub_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<sub_svalue::key_t>::empty_zero_p): Make
	false.
	(class repeated_svalue): New.
	(is_a_helper <const repeated_svalue *>::test): New.
	(struct default_hash_traits<repeated_svalue::key_t>): New.
	(class bits_within_svalue): New.
	(is_a_helper <const bits_within_svalue *>::test): New.
	(struct default_hash_traits<bits_within_svalue::key_t>): New.
	(widening_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(widening_svalue::key_t::is_empty): Likewise.
	(default_hash_traits<widening_svalue::key_t>::empty_zero_p): Make
	false.
	(compound_svalue::key_t::mark_empty): Use 2 rather than NULL_TREE.
	(compound_svalue::key_t::is_empty): Likewise.
	(compound_svalue::maybe_fold_bits_within): New.
	(default_hash_traits<compound_svalue::key_t>::empty_zero_p): Make
	false.

gcc/testsuite/ChangeLog:
	PR analyzer/95006
	* gcc.dg/analyzer/clobbers-1.c: New test.
	* gcc.dg/analyzer/clobbers-2.c: New test.
	* gcc.dg/analyzer/data-model-1.c (test_26): Mark xfail as fixed.
	(test_28): Likewise.
	(test_52): Likewise.  Add coverage for end of buffer.
	* gcc.dg/analyzer/explode-1.c: Add leak warning.
	* gcc.dg/analyzer/memset-1.c (test_3): Mark xfail as fixed.
	(test_4): Use char.  Mark xfail as fixed.
	(test_6b): New.
	(test_7): Mark xfail as fixed.  Add coverage for start of buffer.
	(test_8): New.
	(test_9): New.
	* gcc.dg/analyzer/memset-CVE-2017-18549-1.c: New test.
	* gcc.dg/analyzer/symbolic-8.c: New test.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>

1 files changed, 238 insertions, 24 deletions

diff --git a/gcc/analyzer/svalue.h b/gcc/analyzer/svalue.h
index d9e34aa..3965a5f 100644
--- a/gcc/analyzer/svalue.h
+++ b/gcc/analyzer/svalue.h
@@ -41,6 +41,8 @@ enum svalue_kind
   SK_UNARYOP,
   SK_BINOP,
   SK_SUB,
+  SK_REPEATED,
+  SK_BITS_WITHIN,
   SK_UNMERGEABLE,
   SK_PLACEHOLDER,
   SK_WIDENING,
@@ -63,6 +65,9 @@ enum svalue_kind
      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
+     repeated_svalue (SK_REPEATED): repeating an svalue to fill a larger region
+     bits_within_svalue (SK_BITS_WITHIN): a range of bits/bytes within a larger
+       svalue
      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.
@@ -107,6 +112,10 @@ public:
   dyn_cast_binop_svalue () const { return NULL; }
   virtual const sub_svalue *
   dyn_cast_sub_svalue () const { return NULL; }
+  virtual const repeated_svalue *
+  dyn_cast_repeated_svalue () const { return NULL; }
+  virtual const bits_within_svalue *
+  dyn_cast_bits_within_svalue () const { return NULL; }
   virtual const unmergeable_svalue *
   dyn_cast_unmergeable_svalue () const { return NULL; }
   virtual const widening_svalue *
@@ -138,6 +147,16 @@ public:
 
   bool involves_p (const svalue *other) const;
 
+  const svalue *
+  extract_bit_range (tree type,
+		     const bit_range &subrange,
+		     region_model_manager *mgr) const;
+
+  virtual const svalue *
+  maybe_fold_bits_within (tree type,
+			  const bit_range &subrange,
+			  region_model_manager *mgr) const;
+
  protected:
   svalue (complexity c, tree type)
   : m_complexity (c), m_type (type)
@@ -175,9 +194,9 @@ public:
     }
 
     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
-    void mark_empty () { m_type = NULL_TREE; }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
-    bool is_empty () const { return m_type == NULL_TREE; }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
 
     tree m_type;
     const region *m_reg;
@@ -222,7 +241,7 @@ is_a_helper <const region_svalue *>::test (const svalue *sval)
 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;
+  static const bool empty_zero_p = false;
 };
 
 namespace ana {
@@ -253,6 +272,11 @@ public:
 				  enum tree_code op,
 				  const constant_svalue *rhs);
 
+  const svalue *
+  maybe_fold_bits_within (tree type,
+			  const bit_range &subrange,
+			  region_model_manager *mgr) const FINAL OVERRIDE;
+
  private:
   tree m_cst_expr;
 };
@@ -285,6 +309,11 @@ public:
 
   void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
   void accept (visitor *v) const FINAL OVERRIDE;
+
+  const svalue *
+  maybe_fold_bits_within (tree type,
+			  const bit_range &subrange,
+			  region_model_manager *mgr) const FINAL OVERRIDE;
 };
 
 /* An enum describing a particular kind of "poisoned" value.  */
@@ -327,9 +356,9 @@ public:
     }
 
     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
-    void mark_empty () { m_type = NULL_TREE; }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
-    bool is_empty () const { return m_type == NULL_TREE; }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
 
     enum poison_kind m_kind;
     tree m_type;
@@ -364,7 +393,7 @@ is_a_helper <const poisoned_svalue *>::test (const svalue *sval)
 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;
+  static const bool empty_zero_p = false;
 };
 
 namespace ana {
@@ -426,9 +455,9 @@ public:
     }
 
     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
-    void mark_empty () { m_type = NULL_TREE; }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
-    bool is_empty () const { return m_type == NULL_TREE; }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
 
     setjmp_record m_record;
     tree m_type;
@@ -467,7 +496,7 @@ is_a_helper <const setjmp_svalue *>::test (const svalue *sval)
 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;
+  static const bool empty_zero_p = false;
 };
 
 namespace ana {
@@ -548,9 +577,9 @@ public:
     }
 
     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
-    void mark_empty () { m_type = NULL_TREE; }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
-    bool is_empty () const { return m_type == NULL_TREE; }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
 
     tree m_type;
     enum tree_code m_op;
@@ -574,6 +603,11 @@ public:
   enum tree_code get_op () const { return m_op; }
   const svalue *get_arg () const { return m_arg; }
 
+  const svalue *
+  maybe_fold_bits_within (tree type,
+			  const bit_range &subrange,
+			  region_model_manager *mgr) const FINAL OVERRIDE;
+
  private:
   enum tree_code m_op;
   const svalue *m_arg;
@@ -592,7 +626,7 @@ is_a_helper <const unaryop_svalue *>::test (const svalue *sval)
 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;
+  static const bool empty_zero_p = false;
 };
 
 namespace ana {
@@ -630,9 +664,9 @@ public:
     }
 
     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
-    void mark_empty () { m_type = NULL_TREE; }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
-    bool is_empty () const { return m_type == NULL_TREE; }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
 
     tree m_type;
     enum tree_code m_op;
@@ -683,7 +717,7 @@ is_a_helper <const binop_svalue *>::test (const svalue *sval)
 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;
+  static const bool empty_zero_p = false;
 };
 
 namespace ana {
@@ -719,9 +753,9 @@ public:
     }
 
     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
-    void mark_empty () { m_type = NULL_TREE; }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
-    bool is_empty () const { return m_type == NULL_TREE; }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
 
     tree m_type;
     const svalue *m_parent_svalue;
@@ -762,7 +796,182 @@ is_a_helper <const sub_svalue *>::test (const svalue *sval)
 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;
+  static const bool empty_zero_p = false;
+};
+
+namespace ana {
+
+/* Concrete subclass of svalue representing repeating an inner svalue
+   (possibly not a whole number of times) to fill a larger region of
+   type TYPE of size OUTER_SIZE bytes.  */
+
+class repeated_svalue : public svalue
+{
+public:
+  /* A support class for uniquifying instances of repeated_svalue.  */
+  struct key_t
+  {
+    key_t (tree type,
+	   const svalue *outer_size,
+	   const svalue *inner_svalue)
+    : m_type (type), m_outer_size (outer_size), m_inner_svalue (inner_svalue)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_type);
+      hstate.add_ptr (m_outer_size);
+      hstate.add_ptr (m_inner_svalue);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_type == other.m_type
+	      && m_outer_size == other.m_outer_size
+	      && m_inner_svalue == other.m_inner_svalue);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
+
+    tree m_type;
+    const svalue *m_outer_size;
+    const svalue *m_inner_svalue;
+  };
+  repeated_svalue (tree type,
+		   const svalue *outer_size,
+		   const svalue *inner_svalue);
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_REPEATED; }
+  const repeated_svalue *dyn_cast_repeated_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 svalue *get_outer_size () const { return m_outer_size; }
+  const svalue *get_inner_svalue () const { return m_inner_svalue; }
+
+  bool all_zeroes_p () const;
+
+  const svalue *
+  maybe_fold_bits_within (tree type,
+			  const bit_range &subrange,
+			  region_model_manager *mgr) const FINAL OVERRIDE;
+
+ private:
+  const svalue *m_outer_size;
+  const svalue *m_inner_svalue;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const repeated_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_REPEATED;
+}
+
+template <> struct default_hash_traits<repeated_svalue::key_t>
+: public member_function_hash_traits<repeated_svalue::key_t>
+{
+  static const bool empty_zero_p = false;
+};
+
+namespace ana {
+
+/* A range of bits/bytes within another svalue
+   e.g. bytes 5-39 of INITIAL_SVALUE(R).
+   These can be generated for prefixes and suffixes when part of a binding
+   is clobbered, so that we don't lose too much information.  */
+
+class bits_within_svalue : public svalue
+{
+public:
+  /* A support class for uniquifying instances of bits_within_svalue.  */
+  struct key_t
+  {
+    key_t (tree type,
+	   const bit_range &bits,
+	   const svalue *inner_svalue)
+    : m_type (type), m_bits (bits), m_inner_svalue (inner_svalue)
+    {}
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_type);
+      hstate.add_ptr (m_inner_svalue);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_type == other.m_type
+	      && m_bits == other.m_bits
+	      && m_inner_svalue == other.m_inner_svalue);
+    }
+
+    void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
+    bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
+
+    tree m_type;
+    bit_range m_bits;
+    const svalue *m_inner_svalue;
+  };
+  bits_within_svalue (tree type,
+		      const bit_range &bits,
+		      const svalue *inner_svalue);
+
+  enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_BITS_WITHIN; }
+  const bits_within_svalue *
+  dyn_cast_bits_within_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 bit_range &get_bits () const { return m_bits; }
+  const svalue *get_inner_svalue () const { return m_inner_svalue; }
+
+  const svalue *
+  maybe_fold_bits_within (tree type,
+			  const bit_range &subrange,
+			  region_model_manager *mgr) const FINAL OVERRIDE;
+
+ private:
+  const bit_range m_bits;
+  const svalue *m_inner_svalue;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const bits_within_svalue *>::test (const svalue *sval)
+{
+  return sval->get_kind () == SK_BITS_WITHIN;
+}
+
+template <> struct default_hash_traits<bits_within_svalue::key_t>
+: public member_function_hash_traits<bits_within_svalue::key_t>
+{
+  static const bool empty_zero_p = false;
 };
 
 namespace ana {
@@ -888,9 +1097,9 @@ public:
     }
 
     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
-    void mark_empty () { m_type = NULL_TREE; }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
-    bool is_empty () const { return m_type == NULL_TREE; }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
 
     tree m_type;
     function_point m_point;
@@ -952,7 +1161,7 @@ is_a_helper <widening_svalue *>::test (svalue *sval)
 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;
+  static const bool empty_zero_p = false;
 };
 
 namespace ana {
@@ -1000,9 +1209,9 @@ public:
     }
 
     void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
-    void mark_empty () { m_type = NULL_TREE; }
+    void mark_empty () { m_type = reinterpret_cast<tree> (2); }
     bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
-    bool is_empty () const { return m_type == NULL_TREE; }
+    bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
 
     tree m_type;
     const binding_map *m_map_ptr;
@@ -1029,6 +1238,11 @@ public:
     return key_t (get_type (), &m_map);
   }
 
+  const svalue *
+  maybe_fold_bits_within (tree type,
+			  const bit_range &subrange,
+			  region_model_manager *mgr) const FINAL OVERRIDE;
+
  private:
   static complexity calc_complexity (const binding_map &map);
 
@@ -1048,7 +1262,7 @@ is_a_helper <compound_svalue *>::test (svalue *sval)
 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;
+  static const bool empty_zero_p = false;
 };
 
 namespace ana {