analyzer: improvements to region_model::get_representative_tree

This patch extends region_model::get_representative_tree so that dumps
are able to refer to string literals, which I've found useful in
investigating a state-bloat issue.

Doing so uncovered a bug in the handling of views I introduced in
r10-7024-ge516294a1acb28aaaad44cfd583cc6a80354044e where the code was
erroneously using TREE_TYPE on the view region's type, rather than just
using its type, which the patch also fixes.

gcc/analyzer/ChangeLog:
	* analyzer.h (class array_region): New forward decl.
	* program-state.cc (selftest::test_program_state_dumping_2): New.
	(selftest::analyzer_program_state_cc_tests): Call it.
	* region-model.cc (array_region::constant_from_key): New.
	(region_model::get_representative_tree): Handle region_svalue by
	generating an ADDR_EXPR.
	(region_model::get_representative_path_var): In view handling,
	remove erroneous TREE_TYPE when determining the type of the tree.
	Handle array regions and STRING_CST.
	(selftest::assert_dump_tree_eq): New.
	(ASSERT_DUMP_TREE_EQ): New macro.
	(selftest::test_get_representative_tree): New selftest.
	(selftest::analyzer_region_model_cc_tests): Call it.
	* region-model.h (region::dyn_cast_array_region): New vfunc.
	(array_region::dyn_cast_array_region): New vfunc implementation.
	(array_region::constant_from_key): New decl.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/malloc-4.c: Update expected output of leak to
	reflect fix to region_model::get_representative_path_var, adding
	the missing "*" from the cast.

5 files changed, 165 insertions, 4 deletions

diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog
index 84c619e..e51a1cd 100644
--- a/gcc/analyzer/ChangeLog
+++ b/gcc/analyzer/ChangeLog
@@ -1,5 +1,24 @@
 2020-03-06  David Malcolm  <dmalcolm@redhat.com>
 
+	* analyzer.h (class array_region): New forward decl.
+	* program-state.cc (selftest::test_program_state_dumping_2): New.
+	(selftest::analyzer_program_state_cc_tests): Call it.
+	* region-model.cc (array_region::constant_from_key): New.
+	(region_model::get_representative_tree): Handle region_svalue by
+	generating an ADDR_EXPR.
+	(region_model::get_representative_path_var): In view handling,
+	remove erroneous TREE_TYPE when determining the type of the tree.
+	Handle array regions and STRING_CST.
+	(selftest::assert_dump_tree_eq): New.
+	(ASSERT_DUMP_TREE_EQ): New macro.
+	(selftest::test_get_representative_tree): New selftest.
+	(selftest::analyzer_region_model_cc_tests): Call it.
+	* region-model.h (region::dyn_cast_array_region): New vfunc.
+	(array_region::dyn_cast_array_region): New vfunc implementation.
+	(array_region::constant_from_key): New decl.
+
+2020-03-06  David Malcolm  <dmalcolm@redhat.com>
+
 	* analyzer.h (dump_quoted_tree): New decl.
 	* engine.cc (exploded_node::dump_dot): Pass region model to
 	sm_state_map::print.
diff --git a/gcc/analyzer/analyzer.h b/gcc/analyzer/analyzer.h
index 78d6009..8d0d169 100644
--- a/gcc/analyzer/analyzer.h
+++ b/gcc/analyzer/analyzer.h
@@ -43,6 +43,7 @@ class svalue;
   class setjmp_svalue;
 class region;
   class map_region;
+  class array_region;
   class symbolic_region;
 class region_model;
 class region_model_context;
diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 804800f..24b6783 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -1467,6 +1467,51 @@ test_program_state_dumping ()
 		  "rmodel: p: &r2 malloc: {sv1: unchecked (`p')}");
 }
 
+/* Verify that program_state::dump_to_pp works for string literals.  */
+
+static void
+test_program_state_dumping_2 ()
+{
+    /* Create a program_state for a global ptr "p" that points to
+       a string constant.  */
+  tree p = build_global_decl ("p", ptr_type_node);
+
+  tree string_cst_ptr = build_string_literal (4, "foo");
+
+  auto_delete_vec <state_machine> checkers;
+  extrinsic_state ext_state (checkers);
+
+  program_state s (ext_state);
+  region_model *model = s.m_region_model;
+  region_id p_rid = model->get_lvalue (p, NULL);
+  svalue_id str_sid = model->get_rvalue (string_cst_ptr, NULL);
+  model->set_value (p_rid, str_sid, NULL);
+
+  ASSERT_DUMP_EQ
+    (s, ext_state, false,
+     "rmodel: r0: {kind: `root', parent: null, sval: null}\n"
+     "|-globals: r1: {kind: `globals', parent: r0, sval: null, map: {`p': r2}}\n"
+     "|  `-`p': r2: {kind: `primitive', parent: r1, sval: sv3, type: `void *'}\n"
+     "|    |: sval: sv3: {type: `void *', &r4}\n"
+     "|    |: type: `void *'\n"
+     "`-r3: {kind: `array', parent: r0, sval: sv0, type: `const char[4]', array: {[0]: r4}}\n"
+     "  |: sval: sv0: {type: `const char[4]', `\"foo\"'}\n"
+     "  |: type: `const char[4]'\n"
+     "  `-[0]: r4: {kind: `primitive', parent: r3, sval: null, type: `const char'}\n"
+     "    |: type: `const char'\n"
+     "svalues:\n"
+     "  sv0: {type: `const char[4]', `\"foo\"'}\n"
+     "  sv1: {type: `int', `0'}\n"
+     "  sv2: {type: `const char *', &r4}\n"
+     "  sv3: {type: `void *', &r4}\n"
+     "constraint manager:\n"
+     "  equiv classes:\n"
+     "  constraints:\n");
+
+  ASSERT_DUMP_EQ (s, ext_state, true,
+		  "rmodel: p: &\"foo\"[0]");
+}
+
 /* Verify that program_states with identical sm-state can be merged,
    and that the merged program_state preserves the sm-state.  */
 
@@ -1570,6 +1615,7 @@ analyzer_program_state_cc_tests ()
 {
   test_sm_state_map ();
   test_program_state_dumping ();
+  test_program_state_dumping_2 ();
   test_program_state_merging ();
   test_program_state_merging_2 ();
 }
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index e7e517a..87980e7 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -2494,6 +2494,16 @@ array_region::key_from_constant (tree cst)
   return result;
 }
 
+/* Convert array_region::key_t KEY into a tree constant.  */
+
+tree
+array_region::constant_from_key (key_t key)
+{
+  tree array_type = get_type ();
+  tree index_type = TYPE_DOMAIN (array_type);
+  return build_int_cst (index_type, key);
+}
+
 /* class function_region : public map_region.  */
 
 /* Compare the fields of this function_region with OTHER, returning true
@@ -5669,9 +5679,7 @@ region_model::add_new_malloc_region ()
   return add_region (new symbolic_region (heap_rid, NULL_TREE, true));
 }
 
-/* Attempt to return a tree that represents SID, or return NULL_TREE.
-   Find the first region that stores the value (e.g. a local) and
-   generate a representative tree for it.  */
+/* Attempt to return a tree that represents SID, or return NULL_TREE.  */
 
 tree
 region_model::get_representative_tree (svalue_id sid) const
@@ -5679,6 +5687,8 @@ region_model::get_representative_tree (svalue_id sid) const
   if (sid.null_p ())
     return NULL_TREE;
 
+  /* Find the first region that stores the value (e.g. a local) and
+     generate a representative tree for it.  */
   unsigned i;
   region *region;
   FOR_EACH_VEC_ELT (m_regions, i, region)
@@ -5689,6 +5699,18 @@ region_model::get_representative_tree (svalue_id sid) const
 	  return pv.m_tree;
       }
 
+  /* Handle string literals and various other pointers.  */
+  svalue *sval = get_svalue (sid);
+  if (region_svalue *ptr_sval = sval->dyn_cast_region_svalue ())
+    {
+      region_id rid = ptr_sval->get_pointee ();
+      path_var pv = get_representative_path_var (rid);
+      if (pv.m_tree)
+	return build1 (ADDR_EXPR,
+		       TREE_TYPE (sval->get_type ()),
+		       pv.m_tree);
+    }
+
   return maybe_get_constant (sid);
 }
 
@@ -5727,7 +5749,7 @@ region_model::get_representative_path_var (region_id rid) const
 	  path_var parent_pv = get_representative_path_var (parent_rid);
 	  if (parent_pv.m_tree && reg->get_type ())
 	    return path_var (build1 (NOP_EXPR,
-				     TREE_TYPE (reg->get_type ()),
+				     reg->get_type (),
 				     parent_pv.m_tree),
 			     parent_pv.m_stack_depth);
 	}
@@ -5750,6 +5772,32 @@ region_model::get_representative_path_var (region_id rid) const
 	}
     }
 
+  /* Handle elements within an array.  */
+  if (array_region *array_reg = parent_region->dyn_cast_array_region ())
+    {
+      array_region::key_t key;
+      if (array_reg->get_key_for_child_region (rid, &key))
+	{
+	  path_var parent_pv = get_representative_path_var (parent_rid);
+	  if (parent_pv.m_tree && reg->get_type ())
+	    {
+	      tree index = array_reg->constant_from_key (key);
+	      return path_var (build4 (ARRAY_REF,
+				       reg->get_type (),
+				       parent_pv.m_tree, index,
+				       NULL_TREE, NULL_TREE),
+			       parent_pv.m_stack_depth);
+	    }
+	}
+    }
+
+  /* Handle string literals.  */
+  svalue_id sid = reg->get_value_direct ();
+  if (svalue *sval = get_svalue (sid))
+    if (tree cst = sval->maybe_get_constant ())
+      if (TREE_CODE (cst) == STRING_CST)
+	return path_var (cst, 0);
+
   return path_var (NULL_TREE, 0);
 }
 
@@ -7273,6 +7321,25 @@ assert_condition (const location &loc,
   ASSERT_EQ_AT (loc, actual, expected);
 }
 
+/* Implementation detail of ASSERT_DUMP_TREE_EQ.  */
+
+static void
+assert_dump_tree_eq (const location &loc, tree t, const char *expected)
+{
+  auto_fix_quotes sentinel;
+  pretty_printer pp;
+  pp_format_decoder (&pp) = default_tree_printer;
+  dump_tree (&pp, t);
+  ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
+}
+
+/* Assert that dump_tree (T) is EXPECTED.  */
+
+#define ASSERT_DUMP_TREE_EQ(T, EXPECTED) \
+  SELFTEST_BEGIN_STMT							\
+  assert_dump_tree_eq ((SELFTEST_LOCATION), (T), (EXPECTED)); \
+  SELFTEST_END_STMT
+
 /* Implementation detail of ASSERT_DUMP_EQ.  */
 
 static void
@@ -7321,6 +7388,30 @@ test_dump ()
   ASSERT_DUMP_EQ (model, true, "");
 }
 
+/* Verify that region_model::get_representative_tree works as expected.  */
+
+static void
+test_get_representative_tree ()
+{
+  /* STRING_CST.  */
+  {
+    tree string_cst = build_string (4, "foo");
+    region_model m;
+    svalue_id str_sid = m.get_rvalue (string_cst, NULL);
+    tree rep = m.get_representative_tree (str_sid);
+    ASSERT_EQ (rep, string_cst);
+  }
+
+  /* String literal.  */
+  {
+    tree string_cst_ptr = build_string_literal (4, "foo");
+    region_model m;
+    svalue_id str_sid = m.get_rvalue (string_cst_ptr, NULL);
+    tree rep = m.get_representative_tree (str_sid);
+    ASSERT_DUMP_TREE_EQ (rep, "&\"foo\"[0]");
+  }
+}
+
 /* Verify that calling region_model::get_rvalue repeatedly on the same
    tree constant retrieves the same svalue_id.  */
 
@@ -8372,6 +8463,7 @@ analyzer_region_model_cc_tests ()
 {
   test_tree_cmp_on_constants ();
   test_dump ();
+  test_get_representative_tree ();
   test_unique_constants ();
   test_svalue_equality ();
   test_region_equality ();
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index c782e93..c1fe592 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -844,6 +844,7 @@ public:
 
   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 const symbolic_region *dyn_cast_symbolic_region () const
   { return NULL; }
 
@@ -1354,6 +1355,7 @@ public:
   /* 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,
@@ -1400,6 +1402,7 @@ public:
   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 *);