Add assertions on the internal state of the analyzer, made
possible by r16-4334-g310a70ef6db45d, to verify that concrete binding
keys don't overlap.
Doing so uncovers an issue in the state merging where overzealous merging
of partially-overlapping maps could lead to a malformed merged state.
Fix this by rejecting such state mergers.
Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
Successful run of analyzer integration tests on x86_64-pc-linux-gnu.
Pushed to trunk as r16-6962-g59b9ec2d24e60a
gcc/analyzer/ChangeLog:
* store.cc (binding_cluster::validate): Reimplement as...
(binding_map::validate): ...this new function, using
m_concrete and m_symbolic sizes rather than iterating through
map and counting. Verify that concrete keys do not overlap.
(binding_cluster::can_merge_p): Reject cases that would lead to
overlapping concrete clusters.
* store.h (binding_cluster::validate): New decl.
(binding_map::get_concrete_bindings): New accessor.
gcc/testsuite/ChangeLog:
* c-c++-common/analyzer/flex-without-call-summaries.c: Skip on
C++98 and tweak xfails to reflect slight differences in where
we hit exploration limits.
* c-c++-common/analyzer/raw-data-cst-pr117262-1.c: Add params to
force full exploration of the loop.
* gcc.dg/analyzer/pr93355-localealias.c (read_alias_file): Drop
xfail.
Signed-off-by: David Malcolm <[email protected]>
---
gcc/analyzer/store.cc | 71 +++++++++++++++----
gcc/analyzer/store.h | 5 ++
.../analyzer/flex-without-call-summaries.c | 6 +-
.../analyzer/raw-data-cst-pr117262-1.c | 2 +
.../gcc.dg/analyzer/pr93355-localealias.c | 2 +-
5 files changed, 68 insertions(+), 18 deletions(-)
diff --git a/gcc/analyzer/store.cc b/gcc/analyzer/store.cc
index 94769755b66..b11a81c39a4 100644
--- a/gcc/analyzer/store.cc
+++ b/gcc/analyzer/store.cc
@@ -941,6 +941,40 @@ binding_map::dump (bool simple) const
pp_newline (&pp);
}
+/* Assert that this object is valid. */
+
+void
+binding_map::validate () const
+{
+ const size_t num_concrete = m_concrete.size ();
+ const size_t num_symbolic = m_symbolic.size ();
+
+ /* We shouldn't have more than one symbolic key per cluster
+ (or one would have clobbered the other). */
+ gcc_assert (num_symbolic < 2);
+ /* We can't have both concrete and symbolic keys. */
+ gcc_assert (num_concrete == 0 || num_symbolic == 0);
+
+ /* Check for overlapping concrete bindings. */
+ for (auto iter = m_concrete.begin (); iter != m_concrete.end (); ++iter)
+ {
+ auto next (iter);
+ ++next;
+ if (next != m_concrete.end ())
+ {
+ /* Verify they are in order, and do not overlap. */
+ const bit_range &iter_bits = iter->first;
+ const bit_range &next_bits = next->first;
+ gcc_assert (iter_bits.get_start_bit_offset ()
+ < next_bits.get_start_bit_offset ());
+ gcc_assert (iter_bits.get_last_bit_offset ()
+ < next_bits.get_start_bit_offset ());
+ gcc_assert (iter_bits.get_next_bit_offset ()
+ <= next_bits.get_start_bit_offset ());
+ }
+ }
+}
+
/* Return a new json::object of the form
{KEY_DESC : SVALUE_DESC,
...for the various key/value pairs in this binding_map}. */
@@ -1584,20 +1618,7 @@ binding_cluster::dump (bool simple) const
void
binding_cluster::validate () const
{
- int num_symbolic = 0;
- int num_concrete = 0;
- for (auto iter : m_map)
- {
- if (iter.m_key->symbolic_p ())
- num_symbolic++;
- else
- num_concrete++;
- }
- /* We shouldn't have more than one symbolic key per cluster
- (or one would have clobbered the other). */
- gcc_assert (num_symbolic < 2);
- /* We can't have both concrete and symbolic keys. */
- gcc_assert (num_concrete == 0 || num_symbolic == 0);
+ m_map.validate ();
}
/* Return a new json::object of the form
@@ -2287,6 +2308,28 @@ binding_cluster::can_merge_p (const binding_cluster
*cluster_a,
out_cluster->m_map.put (key, unknown_sval);
}
+ /* We might now have overlapping concrete clusters in OUT_CLUSTER.
+ Reject such cases. */
+ if (num_concrete_keys > 0)
+ {
+ /* Check for overlapping concrete bindings. */
+ const auto &concrete_bindings
+ = out_cluster->get_map ().get_concrete_bindings ();
+ for (auto iter = concrete_bindings.begin ();
+ iter != concrete_bindings.end (); ++iter)
+ {
+ auto next (iter);
+ ++next;
+ if (next != concrete_bindings.end ())
+ {
+ const bit_range &iter_bits = iter->first;
+ const bit_range &next_bits = next->first;
+ if (iter_bits.intersects_p (next_bits))
+ return false;
+ }
+ }
+ }
+
/* We can only have at most one symbolic key per cluster,
and if we do, we can't have any concrete keys.
If this happens, mark the cluster as touched, with no keys. */
diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h
index a1ed9ee757f..3c2be4a76b0 100644
--- a/gcc/analyzer/store.h
+++ b/gcc/analyzer/store.h
@@ -641,6 +641,8 @@ public:
void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
void dump (bool simple) const;
+ void validate () const;
+
std::unique_ptr<json::object> to_json () const;
void add_to_tree_widget (text_art::tree_widget &parent_widget,
@@ -657,6 +659,9 @@ public:
svalue_set *maybe_live_values,
bool always_overlap);
+ const concrete_bindings_t &
+ get_concrete_bindings () const { return m_concrete; }
+
private:
void get_overlapping_bindings (const binding_key *key,
auto_vec<const binding_key *> *out);
diff --git a/gcc/testsuite/c-c++-common/analyzer/flex-without-call-summaries.c
b/gcc/testsuite/c-c++-common/analyzer/flex-without-call-summaries.c
index 03492078e2f..2fff8fb9328 100644
--- a/gcc/testsuite/c-c++-common/analyzer/flex-without-call-summaries.c
+++ b/gcc/testsuite/c-c++-common/analyzer/flex-without-call-summaries.c
@@ -7,7 +7,7 @@
/* { dg-additional-options "-D_POSIX_SOURCE" } */
/* { dg-skip-if "requires hosted libstdc++ for stdlib malloc" { ! hostedlib }
} */
-
+/* { dg-skip-if "C++98 builds hit different limits exploring egraph" {
c++98_only } } */
/* A lexical scanner generated by flex */
@@ -882,14 +882,14 @@ static int yy_get_next_buffer (void)
b->yy_buf_size *= 2;
b->yy_ch_buf = (char *) /* { dg-warning "leak
of '\\*b.yy_ch_buf'" "" { xfail *-*-* } } */
- /* { dg-warning "leak
of '\\*b.yy_buffer_state::yy_ch_buf'" "" { xfail *-*-* } .-1 } */
+ /* { dg-warning "leak
of '\\*b.yy_buffer_state::yy_ch_buf'" "" { target c++ } .-1 } */
/* Include room in for 2 EOB chars. */
yyrealloc( (void *) b->yy_ch_buf,
(yy_size_t)
(b->yy_buf_size + 2) );
}
else
/* Can't grow it, we don't own it. */
- b->yy_ch_buf = NULL; /* { dg-bogus "leak" "PR
analyzer/103546" } */
+ b->yy_ch_buf = NULL; /* { dg-bogus "leak" "PR
analyzer/103546" { xfail c++ } } */
if ( ! b->yy_ch_buf )
YY_FATAL_ERROR(
diff --git a/gcc/testsuite/c-c++-common/analyzer/raw-data-cst-pr117262-1.c
b/gcc/testsuite/c-c++-common/analyzer/raw-data-cst-pr117262-1.c
index 0c8d3e6a508..bf2b09c857d 100644
--- a/gcc/testsuite/c-c++-common/analyzer/raw-data-cst-pr117262-1.c
+++ b/gcc/testsuite/c-c++-common/analyzer/raw-data-cst-pr117262-1.c
@@ -1,3 +1,5 @@
+/* { dg-additional-options "--param analyzer-max-enodes-per-program-point=50
--param analyzer-bb-explosion-factor=50" } */
+
int
main ()
{
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c
b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c
index be82afe3e28..44f0e84ffcf 100644
--- a/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c
+++ b/gcc/testsuite/gcc.dg/analyzer/pr93355-localealias.c
@@ -298,7 +298,7 @@ read_alias_file (fname, fname_len)
if (nmap >= maxmap)
if (__builtin_expect (extend_alias_table (), 0))
- return added; /* { dg-warning "leak of FILE 'fp'" "" { xfail
*-*-* } } */
+ return added; /* { dg-warning "leak of FILE 'fp'" } */
alias_len = strlen (alias) + 1;
value_len = strlen (value) + 1;
--
2.26.3
