[analyzer] Introduce point_and_state::validate
David Malcolm
dmalcolm@redhat.com
Wed Nov 27 18:58:00 GMT 2019
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(-)
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;
--
2.21.0
More information about the Gcc-patches
mailing list