[committed] analyzer: track dynamic extents of regions

Message ID 20210615133947.348186-1-dmalcolm@redhat.com
State New
Headers show
Series
  • [committed] analyzer: track dynamic extents of regions
Related show

Commit Message

Jakub Jelinek via Gcc-patches June 15, 2021, 1:39 p.m.
This patch extends region_model to add tracking of the sizes of
dynamically-allocated regions, both on the heap (via malloc etc) and
stack (via alloca).  It adds enough purging of this state to avoid
blowing up any existing analyzer test cases.

The state can be queried via a new "__analyzer_dump_capacity" for use
in DejaGnu tests but other than that doesn't do anything - I have
various followup experiments that make use of this.

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
Pushed to trunk as 9a2c9579fdbf5d24dfe27fb961286ad7a9c3a98b.

gcc/analyzer/ChangeLog:
	* engine.cc (exploded_node::on_stmt): Handle __analyzer_dump_capacity.
	(exploded_node::on_stmt): Drop m_sm_changes from on_stmt_flags.
	(state_change_requires_new_enode_p): New function...
	(exploded_graph::process_node): Call it, rather than querying
	flags.m_sm_changes, so that dynamic-extent differences can also
	trigger the splitting of nodes.
	* exploded-graph.h (struct on_stmt_flags): Drop field m_sm_changes.
	* program-state.cc (program_state::detect_leaks): Purge dead
	heap-allocated regions from dynamic extents.
	(selftest::test_program_state_1): Fix type of "size_in_bytes".
	(selftest::test_program_state_merging): Likewise.
	* region-model-impl-calls.cc
	(region_model::impl_call_analyzer_dump_capacity): New.
	(region_model::impl_call_free): Remove dynamic extents from the
	freed region.
	* region-model-reachability.h
	(reachable_regions::begin_mutable_base_regs): New.
	(reachable_regions::end_mutable_base_regs): New.
	* region-model.cc: Include "tree-object-size.h".
	(region_model::region_model): Support new field m_dynamic_extents.
	(region_model::operator=): Likewise.
	(region_model::operator==): Likewise.
	(region_model::dump_to_pp): Dump sizes of dynamic regions.
	(region_model::handle_unrecognized_call): Purge dynamic extents
	from any regions that have escaped mutably:.
	(region_model::get_capacity): New function.
	(region_model::add_constraint): Unset dynamic extents when a
	heap-allocated region's address is NULL.
	(region_model::unbind_region_and_descendents): Purge dynamic
	extents of unbound regions.
	(region_model::can_merge_with_p): Call
	m_dynamic_extents.can_merge_with_p.
	(region_model::create_region_for_heap_alloc): Assert that
	size_in_bytes's type is compatible with size_type_node.  Update
	for renaming of record_dynamic_extents to set_dynamic_extents.
	(region_model::create_region_for_alloca): Likewise.
	(region_model::record_dynamic_extents): Rename to...
	(region_model::set_dynamic_extents): ...this.  Assert that
	size_in_bytes's type is compatible with size_type_node.  Add it
	to the m_dynamic_extents map.
	(region_model::get_dynamic_extents): New.
	(region_model::unset_dynamic_extents): New.
	(selftest::test_state_merging): Fix type of "size".
	(selftest::test_malloc_constraints): Likewise.
	(selftest::test_malloc): Verify dynamic extents.
	(selftest::test_alloca): Likewise.
	* region-model.h (region_to_value_map::is_empty): New.
	(region_model::dynamic_extents_t): New typedef.
	(region_model::impl_call_analyzer_dump_capacity): New decl.
	(region_model::get_dynamic_extents): New function.
	(region_model::get_dynamic_extents): New decl.
	(region_model::set_dynamic_extents): New decl.
	(region_model::unset_dynamic_extents): New decl.
	(region_model::get_capacity): New decl.
	(region_model::record_dynamic_extents): Rename to set_dynamic_extents.
	(region_model::m_dynamic_extents): New field.

gcc/ChangeLog:
	* doc/analyzer.texi
	(Special Functions for Debugging the Analyzer): Add
	__analyzer_dump_capacity.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/analyzer-decls.h (__analyzer_dump_capacity): New decl.
	* gcc.dg/analyzer/capacity-1.c: New test.
	* gcc.dg/analyzer/capacity-2.c: New test.
	* gcc.dg/analyzer/capacity-3.c: New test.

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

---
 gcc/analyzer/engine.cc                        |  40 +++++-
 gcc/analyzer/exploded-graph.h                 |  20 +--
 gcc/analyzer/program-state.cc                 |  13 +-
 gcc/analyzer/region-model-impl-calls.cc       |  20 +++
 gcc/analyzer/region-model-reachability.h      |   8 ++
 gcc/analyzer/region-model.cc                  | 130 ++++++++++++++++--
 gcc/analyzer/region-model.h                   |  33 ++++-
 gcc/doc/analyzer.texi                         |   7 +
 .../gcc.dg/analyzer/analyzer-decls.h          |   3 +
 gcc/testsuite/gcc.dg/analyzer/capacity-1.c    | 106 ++++++++++++++
 gcc/testsuite/gcc.dg/analyzer/capacity-2.c    |  53 +++++++
 gcc/testsuite/gcc.dg/analyzer/capacity-3.c    |  82 +++++++++++
 12 files changed, 473 insertions(+), 42 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/analyzer/capacity-1.c
 create mode 100644 gcc/testsuite/gcc.dg/analyzer/capacity-2.c
 create mode 100644 gcc/testsuite/gcc.dg/analyzer/capacity-3.c

-- 
2.26.3

Patch

diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 50652b2cfa6..df04b0ba5d6 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -1185,6 +1185,8 @@  exploded_node::on_stmt (exploded_graph &eg,
 	       to stderr.  */
 	    state->dump (eg.get_ext_state (), true);
 	  }
+	else if (is_special_named_call_p (call, "__analyzer_dump_capacity", 1))
+	  state->m_region_model->impl_call_analyzer_dump_capacity (call, &ctxt);
 	else if (is_special_named_call_p (call, "__analyzer_dump_path", 0))
 	  {
 	    /* Handle the builtin "__analyzer_dump_path" by queuing a
@@ -1237,7 +1239,6 @@  exploded_node::on_stmt (exploded_graph &eg,
   if (terminate_path)
     return on_stmt_flags::terminate_path ();
 
-  bool any_sm_changes = false;
   int sm_idx;
   sm_state_map *smap;
   FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap)
@@ -1276,14 +1277,12 @@  exploded_node::on_stmt (exploded_graph &eg,
       /* Allow the state_machine to handle the stmt.  */
       if (sm.on_stmt (&sm_ctxt, snode, stmt))
 	unknown_side_effects = false;
-      if (*old_smap != *new_smap)
-	any_sm_changes = true;
     }
 
   if (const gcall *call = dyn_cast <const gcall *> (stmt))
     state->m_region_model->on_call_post (call, unknown_side_effects, &ctxt);
 
-  return on_stmt_flags (any_sm_changes);
+  return on_stmt_flags ();
 }
 
 /* Consider the effect of following superedge SUCC from this node.
@@ -2925,6 +2924,36 @@  stmt_requires_new_enode_p (const gimple *stmt,
   return false;
 }
 
+/* Return true if OLD_STATE and NEW_STATE are sufficiently different that
+   we should split enodes and create an exploded_edge separating them
+   (which makes it easier to identify state changes of intereset when
+   constructing checker_paths).  */
+
+static bool
+state_change_requires_new_enode_p (const program_state &old_state,
+				   const program_state &new_state)
+{
+  /* Changes in dynamic extents signify creations of heap/alloca regions
+     and resizings of heap regions; likely to be of interest in
+     diagnostic paths.  */
+  if (old_state.m_region_model->get_dynamic_extents ()
+      != new_state.m_region_model->get_dynamic_extents ())
+    return true;
+
+  /* Changes in sm-state are of interest.  */
+  int sm_idx;
+  sm_state_map *smap;
+  FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap)
+    {
+      const sm_state_map *old_smap = old_state.m_checker_states[sm_idx];
+      const sm_state_map *new_smap = new_state.m_checker_states[sm_idx];
+      if (*old_smap != *new_smap)
+	return true;
+    }
+
+  return false;
+}
+
 /* The core of exploded_graph::process_worklist (the main analysis loop),
    handling one node in the worklist.
 
@@ -3067,7 +3096,8 @@  exploded_graph::process_node (exploded_node *node)
 	    next_state = next_state.prune_for_point (*this, next_point, node,
 						     &uncertainty);
 
-	    if (flags.m_sm_changes || flag_analyzer_fine_grained)
+	    if (flag_analyzer_fine_grained
+		|| state_change_requires_new_enode_p (old_state, next_state))
 	      {
 		program_point split_point
 		  = program_point::before_stmt (point.get_supernode (),
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index c67f7b70605..eb1baefad69 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -198,33 +198,21 @@  class exploded_node : public dnode<eg_traits>
   /* The result of on_stmt.  */
   struct on_stmt_flags
   {
-    on_stmt_flags (bool sm_changes)
-    : m_sm_changes (sm_changes),
-      m_terminate_path (false)
+    on_stmt_flags () : m_terminate_path (false)
     {}
 
     static on_stmt_flags terminate_path ()
     {
-      return on_stmt_flags (true, true);
+      return on_stmt_flags (true);
     }
 
-    static on_stmt_flags state_change (bool any_sm_changes)
-    {
-      return on_stmt_flags (any_sm_changes, false);
-    }
-
-    /* Did any sm-changes occur handling the stmt.  */
-    bool m_sm_changes : 1;
-
     /* Should we stop analyzing this path (on_stmt may have already
        added nodes/edges, e.g. when handling longjmp).  */
     bool m_terminate_path : 1;
 
   private:
-    on_stmt_flags (bool sm_changes,
-		   bool terminate_path)
-    : m_sm_changes (sm_changes),
-      m_terminate_path (terminate_path)
+    on_stmt_flags (bool terminate_path)
+    : m_terminate_path (terminate_path)
     {}
   };
 
diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 76959c135db..67dd785297e 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -1270,6 +1270,15 @@  program_state::detect_leaks (const program_state &src_state,
   /* Purge dead svals from constraints.  */
   dest_state.m_region_model->get_constraints ()->on_liveness_change
     (maybe_dest_svalues, dest_state.m_region_model);
+
+  /* Purge dead heap-allocated regions from dynamic extents.  */
+  for (const svalue *sval : dead_svals)
+    if (const region_svalue *region_sval = sval->dyn_cast_region_svalue ())
+      {
+	const region *reg = region_sval->get_pointee ();
+	if (reg->get_kind () == RK_HEAP_ALLOCATED)
+	  dest_state.m_region_model->unset_dynamic_extents (reg);
+      }
 }
 
 #if CHECKING_P
@@ -1426,7 +1435,7 @@  test_program_state_1 ()
   program_state s (ext_state);
   region_model *model = s.m_region_model;
   const svalue *size_in_bytes
-    = mgr->get_or_create_unknown_svalue (integer_type_node);
+    = mgr->get_or_create_unknown_svalue (size_type_node);
   const region *new_reg = model->create_region_for_heap_alloc (size_in_bytes);
   const svalue *ptr_sval = mgr->get_ptr_svalue (ptr_type_node, new_reg);
   model->set_value (model->get_lvalue (p, NULL),
@@ -1482,7 +1491,7 @@  test_program_state_merging ()
 
   region_model *model0 = s0.m_region_model;
   const svalue *size_in_bytes
-    = mgr->get_or_create_unknown_svalue (integer_type_node);
+    = mgr->get_or_create_unknown_svalue (size_type_node);
   const region *new_reg = model0->create_region_for_heap_alloc (size_in_bytes);
   const svalue *ptr_sval = mgr->get_ptr_svalue (ptr_type_node, new_reg);
   model0->set_value (model0->get_lvalue (p, &ctxt),
diff --git a/gcc/analyzer/region-model-impl-calls.cc b/gcc/analyzer/region-model-impl-calls.cc
index 4052bb393f8..099520a95b0 100644
--- a/gcc/analyzer/region-model-impl-calls.cc
+++ b/gcc/analyzer/region-model-impl-calls.cc
@@ -206,6 +206,25 @@  region_model::impl_call_analyzer_describe (const gcall *call,
   warning_at (call->location, 0, "svalue: %qs", desc.m_buffer);
 }
 
+/* Handle a call to "__analyzer_dump_capacity".
+
+   Emit a warning describing the capacity of the base region of
+   the region pointed to by the 1st argument.
+   This is for use when debugging, and may be of use in DejaGnu tests.  */
+
+void
+region_model::impl_call_analyzer_dump_capacity (const gcall *call,
+						region_model_context *ctxt)
+{
+  tree t_ptr = gimple_call_arg (call, 0);
+  const svalue *sval_ptr = get_rvalue (t_ptr, ctxt);
+  const region *reg = deref_rvalue (sval_ptr, t_ptr, ctxt);
+  const region *base_reg = reg->get_base_region ();
+  const svalue *capacity = get_capacity (base_reg);
+  label_text desc = capacity->get_desc (true);
+  warning_at (call->location, 0, "capacity: %qs", desc.m_buffer);
+}
+
 /* Handle a call to "__analyzer_eval" by evaluating the input
    and dumping as a dummy warning, so that test cases can use
    dg-warning to validate the result (and so unexpected warnings will
@@ -312,6 +331,7 @@  region_model::impl_call_free (const call_details &cd)
 	 poisoning pointers.  */
       const region *freed_reg = ptr_to_region_sval->get_pointee ();
       unbind_region_and_descendents (freed_reg, POISON_KIND_FREED);
+      m_dynamic_extents.remove (freed_reg);
     }
 }
 
diff --git a/gcc/analyzer/region-model-reachability.h b/gcc/analyzer/region-model-reachability.h
index c6a21e98e61..57daf7255fb 100644
--- a/gcc/analyzer/region-model-reachability.h
+++ b/gcc/analyzer/region-model-reachability.h
@@ -89,6 +89,14 @@  public:
   {
     return m_mutable_svals.end ();
   }
+  hash_set<const region *>::iterator begin_mutable_base_regs ()
+  {
+    return m_mutable_base_regs.begin ();
+  }
+  hash_set<const region *>::iterator end_mutable_base_regs ()
+  {
+    return m_mutable_base_regs.end ();
+  }
 
   void dump_to_pp (pretty_printer *pp) const;
 
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 43f991a2a29..e02a89765f0 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -66,6 +66,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "analyzer/analyzer-selftests.h"
 #include "stor-layout.h"
 #include "attribs.h"
+#include "tree-object-size.h"
 
 #if ENABLE_ANALYZER
 
@@ -225,7 +226,8 @@  region_to_value_map::can_merge_with_p (const region_to_value_map &other,
 /* Ctor for region_model: construct an "empty" model.  */
 
 region_model::region_model (region_model_manager *mgr)
-: m_mgr (mgr), m_store (), m_current_frame (NULL)
+: m_mgr (mgr), m_store (), m_current_frame (NULL),
+  m_dynamic_extents ()
 {
   m_constraints = new constraint_manager (mgr);
 }
@@ -235,7 +237,8 @@  region_model::region_model (region_model_manager *mgr)
 region_model::region_model (const region_model &other)
 : m_mgr (other.m_mgr), m_store (other.m_store),
   m_constraints (new constraint_manager (*other.m_constraints)),
-  m_current_frame (other.m_current_frame)
+  m_current_frame (other.m_current_frame),
+  m_dynamic_extents (other.m_dynamic_extents)
 {
 }
 
@@ -261,6 +264,8 @@  region_model::operator= (const region_model &other)
 
   m_current_frame = other.m_current_frame;
 
+  m_dynamic_extents = other.m_dynamic_extents;
+
   return *this;
 }
 
@@ -285,6 +290,9 @@  region_model::operator== (const region_model &other) const
   if (m_current_frame != other.m_current_frame)
     return false;
 
+  if (m_dynamic_extents != other.m_dynamic_extents)
+    return false;
+
   gcc_checking_assert (hash () == other.hash ());
 
   return true;
@@ -346,6 +354,13 @@  region_model::dump_to_pp (pretty_printer *pp, bool simple,
   m_constraints->dump_to_pp (pp, multiline);
   if (!multiline)
     pp_string (pp, "}");
+
+  /* Dump sizes of dynamic regions, if any are known.  */
+  if (!m_dynamic_extents.is_empty ())
+    {
+      pp_string (pp, "dynamic_extents:");
+      m_dynamic_extents.dump_to_pp (pp, simple, multiline);
+    }
 }
 
 /* Dump a representation of this model to FILE.  */
@@ -1140,6 +1155,17 @@  region_model::handle_unrecognized_call (const gcall *call,
   /* Update bindings for all clusters that have escaped, whether above,
      or previously.  */
   m_store.on_unknown_fncall (call, m_mgr->get_store_manager ());
+
+  /* Purge dynamic extents from any regions that have escaped mutably:
+     realloc could have been called on them.  */
+  for (hash_set<const region *>::iterator
+	 iter = reachable_regs.begin_mutable_base_regs ();
+       iter != reachable_regs.end_mutable_base_regs ();
+       ++iter)
+    {
+      const region *base_reg = (*iter);
+      unset_dynamic_extents (base_reg);
+    }
 }
 
 /* Traverse the regions in this model, determining what regions are
@@ -1972,6 +1998,41 @@  region_model::check_for_writable_region (const region* dest_reg,
     }
 }
 
+/* Get the capacity of REG in bytes.  */
+
+const svalue *
+region_model::get_capacity (const region *reg) const
+{
+  switch (reg->get_kind ())
+    {
+    default:
+      break;
+    case RK_DECL:
+      {
+	const decl_region *decl_reg = as_a <const decl_region *> (reg);
+	tree decl = decl_reg->get_decl ();
+	if (TREE_CODE (decl) == SSA_NAME)
+	  {
+	    tree type = TREE_TYPE (decl);
+	    tree size = TYPE_SIZE (type);
+	    return get_rvalue (size, NULL);
+	  }
+	else
+	  {
+	    tree size = decl_init_size (decl, false);
+	    if (size)
+	      return get_rvalue (size, NULL);
+	  }
+      }
+      break;
+    }
+
+  if (const svalue *recorded = get_dynamic_extents (reg))
+    return recorded;
+
+  return m_mgr->get_or_create_unknown_svalue (sizetype);
+}
+
 /* Set the value of the region given by LHS_REG to the value given
    by RHS_SVAL.  */
 
@@ -2241,6 +2302,12 @@  region_model::add_constraint (tree lhs, enum tree_code op, tree rhs,
   if (ctxt)
     ctxt->on_condition (lhs, op, rhs);
 
+  /* If we have &REGION == NULL, then drop dynamic extents for REGION (for
+     the case where REGION is heap-allocated and thus could be NULL).  */
+  if (op == EQ_EXPR && zerop (rhs))
+    if (const region_svalue *region_sval = lhs_sval->dyn_cast_region_svalue ())
+      unset_dynamic_extents (region_sval->get_pointee ());
+
   return true;
 }
 
@@ -3146,7 +3213,8 @@  region_model::get_frame_at_index (int index) const
 
 /* Unbind svalues for any regions in REG and below.
    Find any pointers to such regions; convert them to
-   poisoned values of kind PKIND.  */
+   poisoned values of kind PKIND.
+   Also purge any dynamic extents.  */
 
 void
 region_model::unbind_region_and_descendents (const region *reg,
@@ -3167,6 +3235,15 @@  region_model::unbind_region_and_descendents (const region *reg,
 
   /* Find any pointers to REG or its descendents; convert to poisoned.  */
   poison_any_pointers_to_descendents (reg, pkind);
+
+  /* Purge dynamic extents of any base regions in REG and below
+     (e.g. VLAs and alloca stack regions).  */
+  for (auto iter : m_dynamic_extents)
+    {
+      const region *iter_reg = iter.first;
+      if (iter_reg->descendent_of_p (reg))
+	unset_dynamic_extents (iter_reg);
+    }
 }
 
 /* Implementation of BindingVisitor.
@@ -3241,6 +3318,10 @@  region_model::can_merge_with_p (const region_model &other_model,
 			   &m))
     return false;
 
+  if (!m_dynamic_extents.can_merge_with_p (other_model.m_dynamic_extents,
+					   &out_model->m_dynamic_extents))
+    return false;
+
   /* Merge constraints.  */
   constraint_manager::merge (*m_constraints,
 			      *other_model.m_constraints,
@@ -3322,7 +3403,8 @@  const region *
 region_model::create_region_for_heap_alloc (const svalue *size_in_bytes)
 {
   const region *reg = m_mgr->create_region_for_heap_alloc ();
-  record_dynamic_extents (reg, size_in_bytes);
+  assert_compat_types (size_in_bytes->get_type (), size_type_node);
+  set_dynamic_extents (reg, size_in_bytes);
   return reg;
 }
 
@@ -3333,18 +3415,38 @@  const region *
 region_model::create_region_for_alloca (const svalue *size_in_bytes)
 {
   const region *reg = m_mgr->create_region_for_alloca (m_current_frame);
-  record_dynamic_extents (reg, size_in_bytes);
+  assert_compat_types (size_in_bytes->get_type (), size_type_node);
+  set_dynamic_extents (reg, size_in_bytes);
   return reg;
 }
 
-/* Placeholder hook for recording that the size of REG is SIZE_IN_BYTES.
-   Currently does nothing.  */
+/* Record that the size of REG is SIZE_IN_BYTES.  */
 
 void
-region_model::
-record_dynamic_extents (const region *reg ATTRIBUTE_UNUSED,
-			const svalue *size_in_bytes ATTRIBUTE_UNUSED)
+region_model::set_dynamic_extents (const region *reg,
+				   const svalue *size_in_bytes)
+{
+  assert_compat_types (size_in_bytes->get_type (), size_type_node);
+  m_dynamic_extents.put (reg, size_in_bytes);
+}
+
+/* Get the recording of REG in bytes, or NULL if no dynamic size was
+   recorded.  */
+
+const svalue *
+region_model::get_dynamic_extents (const region *reg) const
 {
+  if (const svalue * const *slot = m_dynamic_extents.get (reg))
+    return *slot;
+  return NULL;
+}
+
+/* Unset any recorded dynamic size of REG.  */
+
+void
+region_model::unset_dynamic_extents (const region *reg)
+{
+  m_dynamic_extents.remove (reg);
 }
 
 /* struct model_merger.  */
@@ -4644,7 +4746,7 @@  test_state_merging ()
   {
     test_region_model_context ctxt;
     region_model model0 (&mgr);
-    tree size = build_int_cst (integer_type_node, 1024);
+    tree size = build_int_cst (size_type_node, 1024);
     const svalue *size_sval = mgr.get_or_create_constant_svalue (size);
     const region *new_reg = model0.create_region_for_heap_alloc (size_sval);
     const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg);
@@ -5034,7 +5136,7 @@  test_malloc_constraints ()
   tree null_ptr = build_int_cst (ptr_type_node, 0);
 
   const svalue *size_in_bytes
-    = mgr.get_or_create_unknown_svalue (integer_type_node);
+    = mgr.get_or_create_unknown_svalue (size_type_node);
   const region *reg = model.create_region_for_heap_alloc (size_in_bytes);
   const svalue *sval = mgr.get_ptr_svalue (ptr_type_node, reg);
   model.set_value (model.get_lvalue (p, NULL), sval, NULL);
@@ -5259,7 +5361,7 @@  test_malloc ()
   const region *reg = model.create_region_for_heap_alloc (size_sval);
   const svalue *ptr = mgr.get_ptr_svalue (int_star, reg);
   model.set_value (model.get_lvalue (p, &ctxt), ptr, &ctxt);
-  // TODO: verify dynamic extents
+  ASSERT_EQ (model.get_capacity (reg), size_sval);
 }
 
 /* Verify that alloca works.  */
@@ -5294,7 +5396,7 @@  test_alloca ()
   ASSERT_EQ (reg->get_parent_region (), frame_reg);
   const svalue *ptr = mgr.get_ptr_svalue (int_star, reg);
   model.set_value (model.get_lvalue (p, &ctxt), ptr, &ctxt);
-  // TODO: verify dynamic extents
+  ASSERT_EQ (model.get_capacity (reg), size_sval);
 
   /* Verify that the pointers to the alloca region are replaced by
      poisoned values when the frame is popped.  */
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index 0afcb8635a9..8b669df00be 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -163,6 +163,8 @@  public:
     m_hash_map.remove (reg);
   }
 
+  bool is_empty () const { return m_hash_map.is_empty (); }
+
   void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
   void dump (bool simple) const;
 
@@ -450,12 +452,16 @@  private:
    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.  */
+   It also stores:
+   - a constraint_manager, capturing relationships between the values, and
+   - dynamic extents, mapping dynamically-allocated regions to svalues (their
+   capacities).  */
 
 class region_model
 {
  public:
+  typedef region_to_value_map dynamic_extents_t;
+
   region_model (region_model_manager *mgr);
   region_model (const region_model &other);
   ~region_model ();
@@ -495,6 +501,8 @@  class region_model
   bool impl_call_alloca (const call_details &cd);
   void impl_call_analyzer_describe (const gcall *call,
 				    region_model_context *ctxt);
+  void impl_call_analyzer_dump_capacity (const gcall *call,
+					 region_model_context *ctxt);
   void impl_call_analyzer_eval (const gcall *call,
 				region_model_context *ctxt);
   bool impl_call_builtin_expect (const call_details &cd);
@@ -606,6 +614,16 @@  class region_model
   store *get_store () { return &m_store; }
   const store *get_store () const { return &m_store; }
 
+  const dynamic_extents_t &
+  get_dynamic_extents () const
+  {
+    return m_dynamic_extents;
+  }
+  const svalue *get_dynamic_extents (const region *reg) const;
+  void set_dynamic_extents (const region *reg,
+			    const svalue *size_in_bytes);
+  void unset_dynamic_extents (const region *reg);
+
   region_model_manager *get_manager () const { return m_mgr; }
 
   void unbind_region_and_descendents (const region *reg,
@@ -629,6 +647,8 @@  class region_model
 
   void loop_replay_fixup (const region_model *dst_state);
 
+  const svalue *get_capacity (const region *reg) const;
+
  private:
   const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const;
   const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const;
@@ -676,9 +696,6 @@  class region_model
 
   void on_top_level_param (tree param, region_model_context *ctxt);
 
-  void record_dynamic_extents (const region *reg,
-			       const svalue *size_in_bytes);
-
   bool called_from_main_p () const;
   const svalue *get_initial_value_for_global (const region *reg) const;
 
@@ -693,6 +710,12 @@  class region_model
   constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
 
   const frame_region *m_current_frame;
+
+  /* Map from base region to size in bytes, for tracking the sizes of
+     dynamically-allocated regions.
+     This is part of the region_model rather than the region to allow for
+     memory regions to be resized (e.g. by realloc).  */
+  dynamic_extents_t m_dynamic_extents;
 };
 
 /* Some region_model activity could lead to warnings (e.g. attempts to use an
diff --git a/gcc/doc/analyzer.texi b/gcc/doc/analyzer.texi
index 26808ff5d22..2ca4bf61352 100644
--- a/gcc/doc/analyzer.texi
+++ b/gcc/doc/analyzer.texi
@@ -479,6 +479,13 @@  __analyzer_dump ();
 will dump the copious information about the analyzer's state each time it
 reaches the call in its traversal of the source.
 
+@smallexample
+extern void __analyzer_dump_capacity (const void *ptr);
+@end smallexample
+
+will emit a warning describing the capacity of the base region of
+the region pointed to by the 1st argument.
+
 @smallexample
 __analyzer_dump_path ();
 @end smallexample
diff --git a/gcc/testsuite/gcc.dg/analyzer/analyzer-decls.h b/gcc/testsuite/gcc.dg/analyzer/analyzer-decls.h
index d96b3f2f29a..24466939882 100644
--- a/gcc/testsuite/gcc.dg/analyzer/analyzer-decls.h
+++ b/gcc/testsuite/gcc.dg/analyzer/analyzer-decls.h
@@ -15,6 +15,9 @@  extern void __analyzer_describe (int verbosity, ...);
 /* Dump copious information about the analyzer’s state when reached.  */
 extern void __analyzer_dump (void);
 
+/* Emit a warning describing the size of the base region of (*ptr).  */
+extern void __analyzer_dump_capacity (const void *ptr);
+
 /* Dump information after analysis on all of the exploded nodes at this
    program point.
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/capacity-1.c b/gcc/testsuite/gcc.dg/analyzer/capacity-1.c
new file mode 100644
index 00000000000..9ea41f72e1d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/capacity-1.c
@@ -0,0 +1,106 @@ 
+#include <stdlib.h>
+#include "analyzer-decls.h"
+
+typedef unsigned __INT32_TYPE__ u32;
+
+void
+test_1 (void)
+{
+  char buf[16];
+  __analyzer_dump_capacity (buf); /* { dg-warning "capacity: '\\(sizetype\\)16'" } */
+}
+
+void
+test_2 (void)
+{
+  char ch;
+  __analyzer_dump_capacity (&ch); /* { dg-warning "capacity: '\\(sizetype\\)1'" } */
+}
+
+struct s3 { char buf[100]; };
+
+void
+test_3 (void)
+{
+  struct s3 s;
+  __analyzer_dump_capacity (&s); /* { dg-warning "capacity: '\\(sizetype\\)100'" } */
+}
+
+/* Capacity refers to the base region, not any offset within it.  */
+
+void
+test_4 (void)
+{
+  char buf[1024];
+  __analyzer_dump_capacity (buf + 100); /* { dg-warning "capacity: '\\(sizetype\\)1024'" } */
+}
+
+void
+test_5 (void *p)
+{
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */
+}
+
+void
+test_malloc (void)
+{
+  void *p = malloc (1024);
+
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)1024'" } */
+  free (p);
+}
+
+void
+test_alloca (size_t sz)
+{
+  void *p = alloca (sz);
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */
+}
+
+void
+test_vla (size_t sz)
+{
+  char buf[sz];
+  __analyzer_dump_capacity (buf);  /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */
+}
+
+static void * __attribute__((noinline))
+called_by_test_interproc_malloc (size_t a)
+{
+  return malloc (a);
+}
+
+void *
+test_interproc_malloc (size_t sz)
+{
+  void *p = called_by_test_interproc_malloc (sz);
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */
+  return p;
+}
+
+struct s
+{
+  u32 f1;
+  char arr[];
+};
+
+static struct s * __attribute__((noinline))
+alloc_s (size_t num)
+{
+  struct s *p = malloc (sizeof(struct s) + num);
+  return p;
+}
+
+struct s *
+test_trailing_array (void)
+{
+  struct s *p = alloc_s (5);
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(\[^\n\r\]*\\)9'" } */
+  return p;
+}
+
+void
+test_unknown_arr (int p[])
+{
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/capacity-2.c b/gcc/testsuite/gcc.dg/analyzer/capacity-2.c
new file mode 100644
index 00000000000..9f92bcfc0a4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/capacity-2.c
@@ -0,0 +1,53 @@ 
+#include <stdlib.h>
+#include "analyzer-decls.h"
+
+extern void might_realloc (void *);
+extern void cant_realloc (const void *);
+
+void *
+test_realloc_1 (void *p, size_t new_sz)
+{
+  void *q = realloc (p, new_sz);
+  __analyzer_dump_capacity (q); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */
+  return q;
+}
+
+void *
+test_realloc_2 (size_t sz_a, size_t sz_b)
+{
+  void *p = malloc (sz_a);
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_a_\[^\n\r\]*\\)'" } */
+  void *q = realloc (p, sz_b);
+  __analyzer_dump_capacity (q); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */
+  return p;  
+}
+
+void *
+test_might_realloc (void)
+{
+  void *p = malloc (1024);
+
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)1024'" } */
+
+  might_realloc (p);
+
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */
+
+  return p;
+}
+
+void *
+test_cant_realloc (void)
+{
+  void *p = malloc (1024);
+
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)1024'" } */
+
+  cant_realloc (p);
+
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)1024'" } */
+
+  return p;
+}
+
+
diff --git a/gcc/testsuite/gcc.dg/analyzer/capacity-3.c b/gcc/testsuite/gcc.dg/analyzer/capacity-3.c
new file mode 100644
index 00000000000..41e282cee92
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/capacity-3.c
@@ -0,0 +1,82 @@ 
+#include <stdlib.h>
+#include "analyzer-decls.h"
+
+static void __attribute__((noinline))
+__analyzer_callee_1 (size_t inner_sz)
+{
+  void *p = alloca (inner_sz);
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(outer_sz_\[^\n\r\]*\\)'" } */
+}
+
+void
+test_1 (int flag, size_t outer_sz)
+{
+  if (flag)
+    __analyzer_callee_1 (outer_sz);
+
+  /* Verify that we merge state; in particular, the dynamic size of "p"
+     in the called frame should have been purged.  */
+  __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}
+
+void
+test_2 (int flag, size_t sz)
+{
+  if (flag)
+    {
+      void *p = malloc (sz);
+      __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */
+      free (p);
+      /* The dynamic size of "p" should have been purged.  */
+      __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */
+    }
+
+  /* Verify that we merge state.  */
+  __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}
+/* Verify that we purge state on the NULL branch when a malloc result is
+   tested against NULL.  */
+
+void
+test_3 (size_t sz)
+{
+  void *p = malloc (sz);
+
+  if (p)
+    {
+      __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */
+    }
+  else
+    {
+      /* The dynamic size of "p" should have been purged
+	 due to "p" being equal to NULL.  */
+      __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */
+    }
+
+  free (p);
+  
+  /* The dynamic size of "p" should have been purged.  */
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */
+
+    /* Verify that we merge state.  */
+  __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}
+
+/* Verify that we purge dynamic extent of a pointer when it leaks.  */
+
+static void __attribute__((noinline))
+__analyzer_callee_4 (size_t inner_sz)
+{
+  void *p = malloc (inner_sz);
+  __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(outer_sz_\[^\n\r\]*\\)'" } */
+} /* { dg-warning "leak of 'p'" } */
+
+void
+test_4 (int flag, size_t outer_sz)
+{
+  if (flag)
+    __analyzer_callee_4 (outer_sz);
+
+  /* Verify that we merge state.  */
+  __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */
+}