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, 123 insertions, 2 deletions

diff --git a/gcc/analyzer/region.h b/gcc/analyzer/region.h
index 175a82a..353d5c4 100644
--- a/gcc/analyzer/region.h
+++ b/gcc/analyzer/region.h
@@ -43,6 +43,7 @@ enum region_kind
   RK_FIELD,
   RK_ELEMENT,
   RK_OFFSET,
+  RK_SIZED,
   RK_CAST,
   RK_HEAP_ALLOCATED,
   RK_ALLOCA,
@@ -70,6 +71,7 @@ enum region_kind
      field_region (RK_FIELD)
      element_region (RK_ELEMENT)
      offset_region (RK_OFFSET)
+     sized_region (RK_SIZED)
      cast_region (RK_CAST)
      heap_allocated_region (RK_HEAP_ALLOCATED)
      alloca_region (RK_ALLOCA)
@@ -107,6 +109,8 @@ public:
   dyn_cast_element_region () const { return NULL; }
   virtual const offset_region *
   dyn_cast_offset_region () const { return NULL; }
+  virtual const sized_region *
+  dyn_cast_sized_region () const { return NULL; }
   virtual const cast_region *
   dyn_cast_cast_region () const { return NULL; }
   virtual const string_region *
@@ -138,8 +142,25 @@ public:
   static int cmp_ptr_ptr (const void *, const void *);
 
   region_offset get_offset () const;
-  bool get_byte_size (byte_size_t *out) const;
-  bool get_bit_size (bit_size_t *out) const;
+
+  /* Attempt to get the size of this region as a concrete number of bytes.
+     If successful, return true and write the size to *OUT.
+     Otherwise return false.  */
+  virtual bool get_byte_size (byte_size_t *out) const;
+
+  /* Attempt to get the size of this region as a concrete number of bits.
+     If successful, return true and write the size to *OUT.
+     Otherwise return false.  */
+  virtual bool get_bit_size (bit_size_t *out) const;
+
+  /* Get a symbolic value describing the size of this region in bytes
+     (which could be "unknown").  */
+  virtual const svalue *get_byte_size_sval (region_model_manager *mgr) const;
+
+  /* Attempt to get the offset in bits of this region relative to its parent.
+     If successful, return true and write to *OUT.
+     Otherwise return false.  */
+  virtual bool get_relative_concrete_offset (bit_offset_t *out) const;
 
   void
   get_subregions_for_binding (region_model_manager *mgr,
@@ -670,6 +691,8 @@ public:
 
   tree get_field () const { return m_field; }
 
+  bool get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
+
 private:
   tree m_field;
 };
@@ -751,6 +774,9 @@ public:
 
   const svalue *get_index () const { return m_index; }
 
+  virtual bool
+  get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
+
 private:
   const svalue *m_index;
 };
@@ -833,6 +859,8 @@ public:
 
   const svalue *get_byte_offset () const { return m_byte_offset; }
 
+  bool get_relative_concrete_offset (bit_offset_t *out) const FINAL OVERRIDE;
+
 private:
   const svalue *m_byte_offset;
 };
@@ -855,6 +883,99 @@ template <> struct default_hash_traits<offset_region::key_t>
 
 namespace ana {
 
+/* A region that is size BYTES_SIZE_SVAL in size within its parent
+   region (or possibly larger, which would lead to an overflow.  */
+
+class sized_region : public region
+{
+public:
+  /* A support class for uniquifying instances of sized_region.  */
+  struct key_t
+  {
+    key_t (const region *parent, tree element_type,
+	   const svalue *byte_size_sval)
+      : m_parent (parent), m_element_type (element_type),
+	m_byte_size_sval (byte_size_sval)
+    {
+      gcc_assert (byte_size_sval);
+    }
+
+    hashval_t hash () const
+    {
+      inchash::hash hstate;
+      hstate.add_ptr (m_parent);
+      hstate.add_ptr (m_element_type);
+      hstate.add_ptr (m_byte_size_sval);
+      return hstate.end ();
+    }
+
+    bool operator== (const key_t &other) const
+    {
+      return (m_parent == other.m_parent
+	      && m_element_type == other.m_element_type
+	      && m_byte_size_sval == other.m_byte_size_sval);
+    }
+
+    void mark_deleted () { m_byte_size_sval = reinterpret_cast<const svalue *> (1); }
+    void mark_empty () { m_byte_size_sval = NULL; }
+    bool is_deleted () const
+    {
+      return m_byte_size_sval == reinterpret_cast<const svalue *> (1);
+    }
+    bool is_empty () const { return m_byte_size_sval == NULL; }
+
+    const region *m_parent;
+    tree m_element_type;
+    const svalue *m_byte_size_sval;
+    const svalue *m_end_offset;
+  };
+
+  sized_region (unsigned id, const region *parent, tree type,
+		const svalue *byte_size_sval)
+  : region (complexity::from_pair (parent, byte_size_sval),
+	    id, parent, type),
+    m_byte_size_sval (byte_size_sval)
+  {}
+
+  enum region_kind get_kind () const FINAL OVERRIDE { return RK_SIZED; }
+  const sized_region *
+  dyn_cast_sized_region () const FINAL OVERRIDE { return this; }
+
+  void accept (visitor *v) const FINAL OVERRIDE;
+
+  void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+
+  bool get_byte_size (byte_size_t *out) const FINAL OVERRIDE;
+  bool get_bit_size (bit_size_t *out) const FINAL OVERRIDE;
+
+  const svalue *
+  get_byte_size_sval (region_model_manager *) const FINAL OVERRIDE
+  {
+    return m_byte_size_sval;
+  }
+
+private:
+  const svalue *m_byte_size_sval;
+};
+
+} // namespace ana
+
+template <>
+template <>
+inline bool
+is_a_helper <const sized_region *>::test (const region *reg)
+{
+  return reg->get_kind () == RK_SIZED;
+}
+
+template <> struct default_hash_traits<sized_region::key_t>
+: public member_function_hash_traits<sized_region::key_t>
+{
+  static const bool empty_zero_p = true;
+};
+
+namespace ana {
+
 /* A region that views another region using a different type.  */
 
 class cast_region : public region