analyzer: don't create bindings or binding keys for empty regions [PR107882]

PR analyzer/107882 reports an ICE, due to trying to get a compound svalue
for this binding:

  cluster for: a:
    key:   {bytes 0-3}
    value:  {UNKNOWN()}
    key:   {empty}
    value:  {UNKNOWN()}
    key:   {bytes 4-7}
    value:  {UNKNOWN()}

where there's an binding to the unknown value of zero bits in size
"somewhere" within "a" (perhaps between bits 3 and 4?)

This makes no sense, so this patch adds an assertion that we never
attempt to create a binding key for an empty region, and adds early
rejection of attempts to get or set the values of such regions, fixing
the ICE.

gcc/analyzer/ChangeLog:
	PR analyzer/107882
	* region-model.cc (region_model::get_store_value): Return an
	unknown value for empty regions.
	(region_model::set_value): Bail on empty regions.
	* region.cc (region::empty_p): New.
	* region.h (region::empty_p): New decl.
	* state-purge.cc (same_binding_p): Bail if either region is empty.
	* store.cc (binding_key::make): Assert that a concrete binding's
	bit_size must be > 0.
	(binding_cluster::mark_region_as_unknown): Bail on empty regions.
	(binding_cluster::get_binding): Likewise.
	(binding_cluster::remove_overlapping_bindings): Likewise.
	(binding_cluster::on_unknown_fncall): Don't conjure values for
	empty regions.
	(store::fill_region): Bail on empty regions.
	* store.h (class concrete_binding): Update comment to reflect that
	the range of bits must be non-empty.
	(concrete_binding::concrete_binding): Assert that bit range is
	non-empty.

gcc/testsuite/ChangeLog:
	PR analyzer/107882
	* gcc.dg/analyzer/memcpy-pr107882.c: New test.

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

7 files changed, 63 insertions, 9 deletions

diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 430c0e9..18eaf22 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -2321,6 +2321,10 @@ const svalue *
 region_model::get_store_value (const region *reg,
 			       region_model_context *ctxt) const
 {
+  /* Getting the value of an empty region gives an unknown_svalue.  */
+  if (reg->empty_p ())
+    return m_mgr->get_or_create_unknown_svalue (reg->get_type ());
+
   check_region_for_read (reg, ctxt);
 
   /* Special-case: handle var_decls in the constant pool.  */
@@ -3159,6 +3163,10 @@ region_model::set_value (const region *lhs_reg, const svalue *rhs_sval,
   gcc_assert (lhs_reg);
   gcc_assert (rhs_sval);
 
+  /* Setting the value of an empty region is a no-op.  */
+  if (lhs_reg->empty_p ())
+    return;
+
   check_region_size (lhs_reg, rhs_sval, ctxt);
 
   check_region_for_write (lhs_reg, ctxt);
diff --git a/gcc/analyzer/region.cc b/gcc/analyzer/region.cc
index 6d97590..67ba948 100644
--- a/gcc/analyzer/region.cc
+++ b/gcc/analyzer/region.cc
@@ -671,6 +671,18 @@ region::symbolic_p () const
   return get_kind () == RK_SYMBOLIC;
 }
 
+/* Return true if this region is known to be zero bits in size.  */
+
+bool
+region::empty_p () const
+{
+  bit_size_t num_bits;
+  if (get_bit_size (&num_bits))
+    if (num_bits == 0)
+      return true;
+  return false;
+}
+
 /* Return true if this is a region for a decl with name DECL_NAME.
    Intended for use when debugging (for assertions and conditional
    breakpoints).  */
diff --git a/gcc/analyzer/region.h b/gcc/analyzer/region.h
index ecae887..6d8bcfb 100644
--- a/gcc/analyzer/region.h
+++ b/gcc/analyzer/region.h
@@ -233,6 +233,8 @@ public:
 
   bool is_named_decl_p (const char *decl_name) const;
 
+  bool empty_p () const;
+
  protected:
   region (complexity c, unsigned id, const region *parent, tree type);
 
diff --git a/gcc/analyzer/state-purge.cc b/gcc/analyzer/state-purge.cc
index 6fac18a..e9bcb4b 100644
--- a/gcc/analyzer/state-purge.cc
+++ b/gcc/analyzer/state-purge.cc
@@ -813,7 +813,11 @@ same_binding_p (const region *reg_a, const region *reg_b,
 {
   if (reg_a->get_base_region () != reg_b->get_base_region ())
     return false;
+  if (reg_a->empty_p ())
+    return false;
   const binding_key *bind_key_a = binding_key::make (store_mgr, reg_a);
+  if (reg_b->empty_p ())
+    return false;
   const binding_key *bind_key_b = binding_key::make (store_mgr, reg_b);
   return bind_key_a == bind_key_b;
 }
diff --git a/gcc/analyzer/store.cc b/gcc/analyzer/store.cc
index 99939b7..dd8ebaa 100644
--- a/gcc/analyzer/store.cc
+++ b/gcc/analyzer/store.cc
@@ -127,8 +127,12 @@ binding_key::make (store_manager *mgr, const region *r)
     {
       bit_size_t bit_size;
       if (r->get_bit_size (&bit_size))
-	return mgr->get_concrete_binding (offset.get_bit_offset (),
-					  bit_size);
+	{
+	  /* Must be non-empty.  */
+	  gcc_assert (bit_size > 0);
+	  return mgr->get_concrete_binding (offset.get_bit_offset (),
+					    bit_size);
+	}
       else
 	return mgr->get_symbolic_binding (r);
     }
@@ -1464,6 +1468,9 @@ binding_cluster::mark_region_as_unknown (store_manager *mgr,
 					 const region *reg_for_overlap,
 					 uncertainty_t *uncertainty)
 {
+  if (reg_to_bind->empty_p ())
+    return;
+
   remove_overlapping_bindings (mgr, reg_for_overlap, uncertainty);
 
   /* Add a default binding to "unknown".  */
@@ -1516,6 +1523,8 @@ const svalue *
 binding_cluster::get_binding (store_manager *mgr,
 			      const region *reg) const
 {
+  if (reg->empty_p ())
+    return NULL;
   const binding_key *reg_binding = binding_key::make (mgr, reg);
   const svalue *sval = m_map.get (reg_binding);
   if (sval)
@@ -1800,6 +1809,8 @@ binding_cluster::remove_overlapping_bindings (store_manager *mgr,
 					      const region *reg,
 					      uncertainty_t *uncertainty)
 {
+  if (reg->empty_p ())
+    return;
   const binding_key *reg_binding = binding_key::make (mgr, reg);
 
   const region *cluster_base_reg = get_base_region ();
@@ -2007,11 +2018,14 @@ binding_cluster::on_unknown_fncall (const gcall *call,
     {
       m_map.empty ();
 
-      /* Bind it to a new "conjured" value using CALL.  */
-      const svalue *sval
-	= mgr->get_svalue_manager ()->get_or_create_conjured_svalue
+      if (!m_base_region->empty_p ())
+	{
+	  /* Bind it to a new "conjured" value using CALL.  */
+	  const svalue *sval
+	    = mgr->get_svalue_manager ()->get_or_create_conjured_svalue
 	    (m_base_region->get_type (), call, m_base_region, p);
-      bind (mgr, m_base_region, sval);
+	  bind (mgr, m_base_region, sval);
+	}
 
       m_touched = true;
     }
@@ -2742,6 +2756,10 @@ store::purge_region (store_manager *mgr, const region *reg)
 void
 store::fill_region (store_manager *mgr, const region *reg, const svalue *sval)
 {
+  /* Filling an empty region is a no-op.  */
+  if (reg->empty_p ())
+    return;
+
   const region *base_reg = reg->get_base_region ();
   if (base_reg->symbolic_for_unknown_ptr_p ()
       || !base_reg->tracked_p ())
diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h
index 6243ec6..30284eb 100644
--- a/gcc/analyzer/store.h
+++ b/gcc/analyzer/store.h
@@ -356,8 +356,8 @@ struct byte_range
   byte_size_t m_size_in_bytes;
 };
 
-/* Concrete subclass of binding_key, for describing a concrete range of
-   bits within the binding_map (e.g. "bits 8-15").  */
+/* Concrete subclass of binding_key, for describing a non-empty
+   concrete range of bits within the binding_map (e.g. "bits 8-15").  */
 
 class concrete_binding : public binding_key
 {
@@ -367,7 +367,9 @@ public:
 
   concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
   : m_bit_range (start_bit_offset, size_in_bits)
-  {}
+  {
+    gcc_assert (!m_bit_range.empty_p ());
+  }
   bool concrete_p () const final override { return true; }
 
   hashval_t hash () const
diff --git a/gcc/testsuite/gcc.dg/analyzer/memcpy-pr107882.c b/gcc/testsuite/gcc.dg/analyzer/memcpy-pr107882.c
new file mode 100644
index 0000000..4ecb0fd
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/memcpy-pr107882.c
@@ -0,0 +1,8 @@
+void
+foo (int *x, int y)
+{
+  int *a = x, *b = (int *) &a;
+
+  __builtin_memcpy (b + 1, x, y);
+  foo (a, 0);
+}