analyzer: fix ICE with pointers between stack frames (PR 93438)

PR analyzer/93438 reports an ICE when merging two region_models
in which an older stack frame has a local pointing to a local in
a more recent stack frame.

  stack
    older frame
      int *: "ow" --+
                    |
    newer frame     |
      int: "pk" <---+

The root cause is that the state-merging code assumes that all frame
regions in the merged model have already been created.
stack_region::can_merge_p iterates through the frames, creating
and populating each merged frame in turn, so when it attempts to
populate the older frame, it attempts to reference the newer frame in
the merged model, which doesn't exist yet.

This patch reworks stack_region::can_merge_p to use a two-pass approach
in which all frames in the merged model are created first, and then
are all populated, fixing the bug.

gcc/analyzer/ChangeLog:
	PR analyzer/93438
	* region-model.cc (stack_region::can_merge_p): Split into a two
	pass approach, creating all stack regions first, then populating
	them.
	(selftest::test_state_merging): Add test coverage for (a) the case
	of self-merging a model in which a local in an older stack frame
	points to a local in a more recent stack frame (which previously
	would ICE), and (b) the case of self-merging a model in which a
	local points to a global (which previously worked OK).

gcc/testsuite/ChangeLog:
	PR analyzer/93438
	* gcc.dg/analyzer/torture/pr93438.c: New test.
	* gcc.dg/analyzer/torture/pr93438-2.c: New test.

5 files changed, 153 insertions, 19 deletions

diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog
index a46ee26..8806a77 100644
--- a/gcc/analyzer/ChangeLog
+++ b/gcc/analyzer/ChangeLog
@@ -1,5 +1,17 @@
 2020-01-31  David Malcolm  <dmalcolm@redhat.com>
 
+	PR analyzer/93438
+	* region-model.cc (stack_region::can_merge_p): Split into a two
+	pass approach, creating all stack regions first, then populating
+	them.
+	(selftest::test_state_merging): Add test coverage for (a) the case
+	of self-merging a model in which a local in an older stack frame
+	points to a local in a more recent stack frame (which previously
+	would ICE), and (b) the case of self-merging a model in which a
+	local points to a global (which previously worked OK).
+
+2020-01-31  David Malcolm  <dmalcolm@redhat.com>
+
 	* analyzer.cc (is_named_call_p): Replace tests for fndecl being
 	extern at file scope and having a non-NULL DECL_NAME with a call
 	to maybe_special_function_p.
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index b546114..f116c0a 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -2624,27 +2624,45 @@ stack_region::can_merge_p (const stack_region *stack_region_a,
   stack_region *merged_stack
     = merged_model->get_region <stack_region> (rid_merged_stack);
 
-  for (unsigned i = 0; i < stack_region_a->get_num_frames (); i++)
-    {
-      region_id rid_a = stack_region_a->get_frame_rid (i);
-      frame_region *frame_a = merger->get_region_a <frame_region> (rid_a);
+  /* First, create all frames in the merged model, without populating them.
+     The merging code assumes that all frames in the merged model already exist,
+     so we have to do this first to handle the case in which a local in an
+     older frame points at a local in a more recent frame.  */
+    for (unsigned i = 0; i < stack_region_a->get_num_frames (); i++)
+      {
+	region_id rid_a = stack_region_a->get_frame_rid (i);
+	frame_region *frame_a = merger->get_region_a <frame_region> (rid_a);
 
-      region_id rid_b = stack_region_b->get_frame_rid (i);
-      frame_region *frame_b = merger->get_region_b <frame_region> (rid_b);
+	region_id rid_b = stack_region_b->get_frame_rid (i);
+	frame_region *frame_b = merger->get_region_b <frame_region> (rid_b);
 
-      if (frame_a->get_function () != frame_b->get_function ())
-	return false;
-      frame_region *merged_frame = new frame_region (rid_merged_stack,
-						     frame_a->get_function (),
-						     frame_a->get_depth ());
-      region_id rid_merged_frame = merged_model->add_region (merged_frame);
-      merged_stack->push_frame (rid_merged_frame);
-
-      if (!map_region::can_merge_p (frame_a, frame_b,
-				    merged_frame, rid_merged_frame,
-				    merger))
-	return false;
-    }
+	if (frame_a->get_function () != frame_b->get_function ())
+	  return false;
+
+	frame_region *merged_frame = new frame_region (rid_merged_stack,
+						       frame_a->get_function (),
+						       frame_a->get_depth ());
+	region_id rid_merged_frame = merged_model->add_region (merged_frame);
+	merged_stack->push_frame (rid_merged_frame);
+      }
+
+    /* Now populate the frames we created.  */
+    for (unsigned i = 0; i < stack_region_a->get_num_frames (); i++)
+      {
+	region_id rid_a = stack_region_a->get_frame_rid (i);
+	frame_region *frame_a = merger->get_region_a <frame_region> (rid_a);
+
+	region_id rid_b = stack_region_b->get_frame_rid (i);
+	frame_region *frame_b = merger->get_region_b <frame_region> (rid_b);
+
+	region_id rid_merged_frame = merged_stack->get_frame_rid (i);
+	frame_region *merged_frame
+	  = merged_model->get_region <frame_region> (rid_merged_frame);
+	if (!map_region::can_merge_p (frame_a, frame_b,
+				      merged_frame, rid_merged_frame,
+				      merger))
+	  return false;
+      }
 
   return true;
 }
@@ -7721,6 +7739,11 @@ test_state_merging ()
 		       integer_type_node);
   tree addr_of_a = build1 (ADDR_EXPR, ptr_type_node, a);
 
+  /* Param "q", a pointer.  */
+  tree q = build_decl (UNKNOWN_LOCATION, PARM_DECL,
+		       get_identifier ("q"),
+		       ptr_type_node);
+
   {
     region_model model0;
     region_model model1;
@@ -7991,6 +8014,60 @@ test_state_merging ()
     region_model merged;
     ASSERT_TRUE (model0.can_merge_with_p (model1, &merged));
   }
+
+  /* Verify that we can merge a model in which a local in an older stack
+     frame points to a local in a more recent stack frame.  */
+  {
+    region_model model0;
+    model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL);
+    region_id q_in_first_frame = model0.get_lvalue (q, NULL);
+
+    /* Push a second frame.  */
+    region_id rid_2nd_frame
+      = model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL);
+
+    /* Have a pointer in the older frame point to a local in the
+       more recent frame.  */
+    svalue_id sid_ptr = model0.get_rvalue (addr_of_a, NULL);
+    model0.set_value (q_in_first_frame, sid_ptr, NULL);
+
+    /* Verify that it's pointing at the newer frame.  */
+    region_id rid_pointee
+      = model0.get_svalue (sid_ptr)->dyn_cast_region_svalue ()->get_pointee ();
+    ASSERT_EQ (model0.get_region (rid_pointee)->get_parent (), rid_2nd_frame);
+
+    model0.canonicalize (NULL);
+
+    region_model model1 (model0);
+    ASSERT_EQ (model0, model1);
+
+    /* They should be mergeable, and the result should be the same
+       (after canonicalization, at least).  */
+    region_model merged;
+    ASSERT_TRUE (model0.can_merge_with_p (model1, &merged));
+    merged.canonicalize (NULL);
+    ASSERT_EQ (model0, merged);
+  }
+
+  /* Verify that we can merge a model in which a local points to a global.  */
+  {
+    region_model model0;
+    model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL);
+    model0.set_value (model0.get_lvalue (q, NULL),
+		      model0.get_rvalue (addr_of_y, NULL), NULL);
+
+    model0.canonicalize (NULL);
+
+    region_model model1 (model0);
+    ASSERT_EQ (model0, model1);
+
+    /* They should be mergeable, and the result should be the same
+       (after canonicalization, at least).  */
+    region_model merged;
+    ASSERT_TRUE (model0.can_merge_with_p (model1, &merged));
+    merged.canonicalize (NULL);
+    ASSERT_EQ (model0, merged);
+  }
 }
 
 /* Verify that constraints are correctly merged when merging region_model
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index ae14602..f8051b44 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2020-01-31  David Malcolm  <dmalcolm@redhat.com>
+
+	PR analyzer/93438
+	* gcc.dg/analyzer/torture/pr93438.c: New test.
+	* gcc.dg/analyzer/torture/pr93438-2.c: New test.
+
 2020-01-31  Jakub Jelinek  <jakub@redhat.com>
 
 	PR rtl-optimization/91838
diff --git a/gcc/testsuite/gcc.dg/analyzer/torture/pr93438-2.c b/gcc/testsuite/gcc.dg/analyzer/torture/pr93438-2.c
new file mode 100644
index 0000000..218dc78
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/torture/pr93438-2.c
@@ -0,0 +1,26 @@
+/* A non-recursive example of state-merger of a pointer
+   from an old stack frame to a local in a newer stack frame.  */
+
+int newer (int **ptr_to_ow, int flag);
+
+int
+older (int flag)
+{
+  int *ow;
+  return newer (&ow, flag);
+}
+
+int
+newer (int **ptr_to_ow, int flag)
+{
+  int pk;
+  *ptr_to_ow = &pk;
+  
+  if (flag)
+    pk = 3;
+  else
+    pk = 4;
+  /* State merger.  */
+
+  return pk;
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/torture/pr93438.c b/gcc/testsuite/gcc.dg/analyzer/torture/pr93438.c
new file mode 100644
index 0000000..3a23770
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/torture/pr93438.c
@@ -0,0 +1,13 @@
+/* { dg-additional-options "-Wno-analyzer-too-complex" } */
+
+void
+tw (int **la, int pk)
+{
+  int *ow = *la;
+  int jo = !!pk;
+
+  if (jo == 0)
+    *la = &pk;
+
+  tw (&ow, pk);
+}