[analyzer] Introduce point_and_state::validate

Message ID 20191127185701.29642-1-dmalcolm@redhat.com
State New
Headers show
Series
  • [analyzer] Introduce point_and_state::validate
Related show

Commit Message

David Malcolm Nov. 27, 2019, 6:57 p.m.
This patch adds various validate functions to assert that the internal
state of the analyzer is consistent.

In particular, it asserts that the call_string in the program_point
agrees with the stack_region in the region_model (in terms of the
stack depth, and which function is at each depth).

Doing so uncovered some inconsistencies in e.g. setjmp-3.c due to
creating a "next" node after the on_longjmp containing an
"after-supernode" point directly after the "longjmp" call with the
same call_string as the longjmp call, but with a program_state
containing popped frames due to rewinding the stack.

The patch fixes this by adding a new flag to exploded_node::on_stmt so
that we can stop analyzing the path in the normal way at a longjmp
call, relying on the special-case node/edge creation in
exploded_node::on_longjmp.

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.

Pushed to branch "dmalcolm/analyzer" on the GCC git mirror.

gcc/ChangeLog:
	* analyzer/call-string.cc (call_string::validate): New function.
	* analyzer/call-string.h (call_string::validate): New decl.
	* analyzer/engine.cc (point_and_state::validate): New function.
	(exploded_node::on_stmt): Convert return type from bool to
	exploded_node::on_stmt_flags.  Terminate the path after handling
	longjmp.
	(exploded_graph::get_or_create_node): Validate the point_and_state
	after creating it, and after any merging.
	(exploded_graph::process_node): Bail out after on_stmt if
	m_terminate_path is set.
	* analyzer/exploded-graph.h (point_and_state::validate): New decl.
	(exploded_node::on_stmt_flags): New struct.
	(exploded_node::on_stmt): Convert return type from bool to
	exploded_node::on_stmt_flags.
	* analyzer/program-point.cc
	(program_point::get_function_at_depth): New function.
	(program_point::validate): New function.
	* analyzer/program-point.h (program_point::get_function_at_depth):
	New decl.
	(program_point::validate): New decl.
	* analyzer/region-model.cc (region_model::get_function_at_depth):
	New function.
	(selftest::test_state_merging): Add coverage for
	region_model::get_stack_depth and
	region_model::get_function_at_depth.
	* analyzer/region-model.h (region_model::get_function_at_depth):
	New decl.
---
 gcc/analyzer/call-string.cc   | 19 +++++++++++++
 gcc/analyzer/call-string.h    |  2 ++
 gcc/analyzer/engine.cc        | 53 ++++++++++++++++++++++++++++++-----
 gcc/analyzer/exploded-graph.h | 45 +++++++++++++++++++++++++----
 gcc/analyzer/program-point.cc | 30 ++++++++++++++++++++
 gcc/analyzer/program-point.h  |  3 ++
 gcc/analyzer/region-model.cc  | 17 +++++++++++
 gcc/analyzer/region-model.h   |  1 +
 8 files changed, 158 insertions(+), 12 deletions(-)

-- 
2.21.0

Patch

diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc
index 796b5e798187..a9a9ce51ea52 100644
--- a/gcc/analyzer/call-string.cc
+++ b/gcc/analyzer/call-string.cc
@@ -199,3 +199,22 @@  call_string::cmp_1 (const call_string &a,
       // TODO: test coverage for this
     }
 }
+
+/* Assert that this object is sane.  */
+
+void
+call_string::validate () const
+{
+  /* Skip this in a release build.  */
+#if !CHECKING_P
+  return;
+#endif
+
+  /* Each entry's "caller" should be the "callee" of the previous entry.  */
+  const return_superedge *e;
+  int i;
+  FOR_EACH_VEC_ELT (m_return_edges, i, e)
+    if (i > 0)
+      gcc_assert (e->get_caller_function ()
+		  == m_return_edges[i - 1]->get_callee_function ());
+}
diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h
index e5657e6799bd..221867652e95 100644
--- a/gcc/analyzer/call-string.h
+++ b/gcc/analyzer/call-string.h
@@ -64,6 +64,8 @@  public:
     return m_return_edges[idx];
   }
 
+  void validate () const;
+
 private:
   static int cmp_1 (const call_string &a,
 		    const call_string &b);
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index e02ac7de6577..b1624777a221 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -595,6 +595,38 @@  impl_region_model_context::on_condition (tree lhs, enum tree_code op, tree rhs)
 
 ////////////////////////////////////////////////////////////////////////////
 
+/* struct point_and_state.  */
+
+/* Assert that this object is sane.  */
+
+void
+point_and_state::validate (const extrinsic_state &ext_state) const
+{
+  /* Skip this in a release build.  */
+#if !CHECKING_P
+  return;
+#endif
+
+  m_point.validate ();
+
+  m_state.validate (ext_state);
+
+  /* Verify that the callstring's model of the stack corresponds to that
+     of the region_model.  */
+  /* They should have the same depth.  */
+  gcc_assert (m_point.get_stack_depth ()
+	      == m_state.m_region_model->get_stack_depth ());
+  /* Check the functions in the callstring vs those in the frames
+     at each depth.  */
+  for (int depth = 0; depth < m_point.get_stack_depth (); ++depth)
+    {
+      gcc_assert (m_point.get_function_at_depth (depth)
+		  == m_state.m_region_model->get_function_at_depth (depth));
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////
+
 /* Subroutine of print_enode_indices: print a run of indices from START_IDX
    to END_IDX to PP, using and updating *FIRST_RUN.  */
 
@@ -821,10 +853,9 @@  public:
 };
 
 /* Modify STATE in place, applying the effects of the stmt at this node's
-   point.
-   Return true if there were any sm-state changes.  */
+   point.  */
 
-bool
+exploded_node::on_stmt_flags
 exploded_node::on_stmt (exploded_graph &eg,
 			const supernode *snode,
 			const gimple *stmt,
@@ -894,7 +925,7 @@  exploded_node::on_stmt (exploded_graph &eg,
       else if (is_longjmp_call_p (call))
 	{
 	  on_longjmp (eg, call, state, &ctxt);
-	  return true;
+	  return on_stmt_flags::terminate_path ();
 	}
       else
 	state->m_region_model->on_call_pre (call, &ctxt);
@@ -933,7 +964,7 @@  exploded_node::on_stmt (exploded_graph &eg,
   if (const gcall *call = dyn_cast <const gcall *> (stmt))
     state->m_region_model->on_call_post (call, &ctxt);
 
-  return any_sm_changes;
+  return on_stmt_flags (any_sm_changes);
 }
 
 /* Consider the effect of following superedge SUCC from this node.
@@ -1701,6 +1732,7 @@  exploded_graph::get_or_create_node (const program_point &point,
     = &get_or_create_per_call_string_data (point.get_call_string ())->m_stats;
 
   point_and_state ps (point, pruned_state);
+  ps.validate (m_ext_state);
   if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
     {
       /* An exploded_node for PS already exists.  */
@@ -1771,6 +1803,8 @@  exploded_graph::get_or_create_node (const program_point &point,
       return NULL;
     }
 
+  ps.validate (m_ext_state);
+
   /* An exploded_node for "ps" doesn't already exist; create one.  */
   exploded_node *node = new exploded_node (ps, m_nodes.length ());
   add_node (node);
@@ -2254,10 +2288,15 @@  exploded_graph::process_node (exploded_node *node)
 	    prev_stmt = stmt;
 
 	    /* Process the stmt.  */
-	    bool any_sm_changes
+	    exploded_node::on_stmt_flags flags
 	      = node->on_stmt (*this, snode, stmt, &next_state, &change);
 
-	    if (any_sm_changes || flag_analyzer_fine_grained)
+	    /* If flags.m_terminate_path, stop analyzing; any nodes/edges
+	       will have been added by on_stmt (e.g. for handling longjmp).  */
+	    if (flags.m_terminate_path)
+	      return;
+
+	    if (flags.m_sm_changes || flag_analyzer_fine_grained)
 	      break;
 	  }
 	unsigned next_idx = stmt_idx + 1;
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index 97e10050518a..c8e36f25a575 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -121,6 +121,8 @@  struct point_and_state
     m_hash = m_point.hash () ^ m_state.hash ();
   }
 
+  void validate (const extrinsic_state &ext_state) const;
+
   program_point m_point;
   program_state m_state;
   hashval_t m_hash;
@@ -166,11 +168,44 @@  class exploded_node : public dnode<eg_traits>
   void dump (FILE *fp, const extrinsic_state &ext_state) const;
   void dump (const extrinsic_state &ext_state) const;
 
-  bool on_stmt (exploded_graph &eg,
-		const supernode *snode,
-		const gimple *stmt,
-		program_state *state,
-		state_change *change) const;
+  /* The result of on_stmt.  */
+  struct on_stmt_flags
+  {
+    on_stmt_flags (bool sm_changes)
+    : m_sm_changes (sm_changes),
+      m_terminate_path (false)
+    {}
+
+    static on_stmt_flags terminate_path ()
+    {
+      return on_stmt_flags (true, 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 on_stmt (exploded_graph &eg,
+			 const supernode *snode,
+			 const gimple *stmt,
+			 program_state *state,
+			 state_change *change) const;
   bool on_edge (exploded_graph &eg,
 		const superedge *succ,
 		program_point *next_point,
diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc
index ea8423832603..c46aa51eb43b 100644
--- a/gcc/analyzer/program-point.cc
+++ b/gcc/analyzer/program-point.cc
@@ -215,6 +215,36 @@  program_point::hash () const
   return hstate.end ();
 }
 
+/* Get the function * at DEPTH within the call stack.  */
+
+function *
+program_point::get_function_at_depth (unsigned depth) const
+{
+  gcc_assert (depth <= m_call_string.length ());
+  if (depth == m_call_string.length ())
+    return m_function_point.get_function ();
+  else
+    return m_call_string[depth]->get_caller_function ();
+}
+
+/* Assert that this object is sane.  */
+
+void
+program_point::validate () const
+{
+  /* Skip this in a release build.  */
+#if !CHECKING_P
+  return;
+#endif
+
+  m_call_string.validate ();
+  /* The "callee" of the final entry in the callstring should be the
+     function of the m_function_point.  */
+  if (m_call_string.length () > 0)
+    gcc_assert (m_call_string[m_call_string.length () - 1]->get_callee_function ()
+		== get_function ());
+}
+
 /* Check to see if SUCC is a valid edge to take (ensuring that we have
    interprocedurally valid paths in the exploded graph, and enforcing
    recursion limits).
diff --git a/gcc/analyzer/program-point.h b/gcc/analyzer/program-point.h
index ad7b9cdb44ca..2f4505a3b6a7 100644
--- a/gcc/analyzer/program-point.h
+++ b/gcc/analyzer/program-point.h
@@ -225,6 +225,7 @@  public:
   {
     return m_function_point.get_function ();
   }
+  function *get_function_at_depth (unsigned depth) const;
   tree get_fndecl () const
   {
     gcc_assert (get_kind () != PK_ORIGIN);
@@ -308,6 +309,8 @@  public:
 
   bool on_edge (exploded_graph &eg, const superedge *succ);
 
+  void validate () const;
+
  private:
   const function_point m_function_point;
   call_string m_call_string;
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 56aa44dae142..11804dc116b4 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -5653,6 +5653,18 @@  region_model::get_stack_depth () const
     return 0;
 }
 
+/* Get the function * at DEPTH within the call stack.  */
+
+function *
+region_model::get_function_at_depth (unsigned depth) const
+{
+  stack_region *stack = get_root_region ()->get_stack_region (this);
+  gcc_assert (stack);
+  region_id frame_rid = stack->get_frame_rid (depth);
+  frame_region *frame = get_region <frame_region> (frame_rid);
+  return frame->get_function ();
+}
+
 /* Get the region_id of this model's globals region (if any).  */
 
 region_id
@@ -7429,8 +7441,13 @@  test_state_merging ()
     test_region_model_context ctxt;
     region_model model0;
     region_model model1;
+    ASSERT_EQ (model0.get_stack_depth (), 0);
     model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, &ctxt);
+    ASSERT_EQ (model0.get_stack_depth (), 1);
+    ASSERT_EQ (model0.get_function_at_depth (0),
+	       DECL_STRUCT_FUNCTION (test_fndecl));
     model1.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, &ctxt);
+
     svalue_id sid_a
       = model0.set_to_new_unknown_value (model0.get_lvalue (a, &ctxt),
 					 integer_type_node, &ctxt);
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index 6f92e94372be..0b8d366a2e51 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -1631,6 +1631,7 @@  class region_model
   svalue_id pop_frame (bool purge, purge_stats *stats,
 		       region_model_context *ctxt);
   int get_stack_depth () const;
+  function *get_function_at_depth (unsigned depth) const;
 
   region_id get_globals_region_id () const;