PR analyzer/98447 covers a false positive from -fanalyzer.
The root cause is that the analyzer's constraint-handling code
doesn't "know" that if X := Y / 64, then X < 64.
This patch adds some minimal usage of value_range and range_op to
-fanalyzer. It adds a new svalue::maybe_get_value_range vfunc, which
attempts to get a value_range for an svalue (but bails out for awkward
cases), and if value_ranges are available, uses them in eval_condition
to determine if the result is known based on range_op.
Doing so fixes the above false positive, improves a couple of other
tests in the DejaGnu testsuite, and eliminates 31 false +ves in the
analyzer integration testsuite (out of ~2200), along with a slight
speedup to the latter (albeit testing with a debug build of gcc).
A deeper integration with ranger could probably be made, but that is
clearly stage 1 material.
Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
Successful run of analyzer integration tests on x86_64-pc-linux-gnu.
Andrew: is this OK for trunk? (from a value_range/range_op perspective)
Jakub/Richi: is it OK to push this in stage 4, or do you want me to
wait to stage 1?
Thanks
Dave
gcc/analyzer/ChangeLog:
PR analyzer/98447
* common.h: Include "value-range.h".
* region-model.cc: Include "value-relation.h" and "range-op.h".
(region_model::eval_condition): Try using range_op to see if we
can get a known boolean from the value_ranges of the operands.
* svalue.cc: Include "value-relation.h" and "range-op.h".
(type_can_have_value_range_p): New.
(svalue::maybe_get_value_range): New.
(constant_svalue::maybe_get_value_range): New.
(unknown_svalue::maybe_get_value_range): New.
(unaryop_svalue::maybe_get_value_range): New.
(binop_svalue::maybe_get_value_range): New.
* svalue.h (svalue::maybe_get_value_range): New vfunc decl.
(constant_svalue::maybe_get_value_range): New decl.
(unknown_svalue::maybe_get_value_range): New decl.
(unaryop_svalue::maybe_get_value_range): New decl.
(binop_svalue::maybe_get_value_range): New decl.
gcc/testsuite/ChangeLog:
PR analyzer/98447
* c-c++-common/analyzer/conditionals-pr98447-1.c: New test.
* c-c++-common/analyzer/conditionals-pr98447-2.c: New test.
* c-c++-common/analyzer/null-deref-pr108400-SoftEtherVPN-WebUi.c:
Updated for false positive being fixed for C.
* gcc.dg/analyzer/data-model-1.c: Update expected output to
reflect improved output.
Signed-off-by: David Malcolm <[email protected]>
---
gcc/analyzer/common.h | 1 +
gcc/analyzer/region-model.cc | 26 ++++
gcc/analyzer/svalue.cc | 113 ++++++++++++++++++
gcc/analyzer/svalue.h | 12 ++
.../analyzer/conditionals-pr98447-1.c | 28 +++++
.../analyzer/conditionals-pr98447-2.c | 40 +++++++
.../null-deref-pr108400-SoftEtherVPN-WebUi.c | 4 +-
gcc/testsuite/gcc.dg/analyzer/data-model-1.c | 2 +-
8 files changed, 223 insertions(+), 3 deletions(-)
create mode 100644 gcc/testsuite/c-c++-common/analyzer/conditionals-pr98447-1.c
create mode 100644 gcc/testsuite/c-c++-common/analyzer/conditionals-pr98447-2.c
diff --git a/gcc/analyzer/common.h b/gcc/analyzer/common.h
index 27ca49ee1c81..cbe36dfb9c99 100644
--- a/gcc/analyzer/common.h
+++ b/gcc/analyzer/common.h
@@ -41,6 +41,7 @@ along with GCC; see the file COPYING3. If not see
#include "function.h"
#include "json.h"
#include "tristate.h"
+#include "value-range.h"
class graphviz_out;
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 1efb19b07761..1c851130c45c 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -46,6 +46,8 @@ along with GCC; see the file COPYING3. If not see
#include "selftest-tree.h"
#include "context.h"
#include "channels.h"
+#include "value-relation.h"
+#include "range-op.h"
#include "text-art/tree-widget.h"
@@ -5348,6 +5350,30 @@ region_model::eval_condition (const svalue *lhs,
}
}
+ /* Try range_op, but avoid cases where we have been sloppy about types. */
+ if (lhs->get_type ()
+ && rhs->get_type ()
+ && range_compatible_p (lhs->get_type (), rhs->get_type ()))
+ {
+ value_range lhs_vr, rhs_vr;
+ if (lhs->maybe_get_value_range (lhs_vr))
+ if (rhs->maybe_get_value_range (rhs_vr))
+ {
+ range_op_handler handler (op);
+ if (handler)
+ {
+ int_range_max out;
+ if (handler.fold_range (out, boolean_type_node, lhs_vr, rhs_vr))
+ {
+ if (out.zero_p ())
+ return tristate::TS_FALSE;
+ if (out.nonzero_p ())
+ return tristate::TS_TRUE;
+ }
+ }
+ }
+ }
+
/* Attempt to unwrap cast if there is one, and the types match. */
tree lhs_type = lhs->get_type ();
tree rhs_type = rhs->get_type ();
diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc
index 0b3ef6e5f050..5cb0fafbf5da 100644
--- a/gcc/analyzer/svalue.cc
+++ b/gcc/analyzer/svalue.cc
@@ -25,6 +25,8 @@ along with GCC; see the file COPYING3. If not see
#include "fold-const.h"
#include "diagnostic.h"
#include "tree-diagnostic.h"
+#include "value-relation.h"
+#include "range-op.h"
#include "text-art/dump.h"
@@ -880,6 +882,34 @@ svalue::maybe_get_type_from_typeinfo () const
return NULL_TREE;
}
+/* Return true if we can get a value_range for TYPE (which could be
+ NULL_TREE); false otherwise. */
+
+static bool
+type_can_have_value_range_p (tree type)
+{
+ if (!type)
+ return false;
+ if (!irange::supports_p (type))
+ return false;
+ return true;
+}
+
+/* Base implementation of svalue::maybe_get_value_range vfunc.
+ If there is a suitable underlying type, write a "varying" for it to OUT
+ (for "any value of that type") and return true; otherwise return false. */
+
+bool
+svalue::maybe_get_value_range (value_range &out) const
+{
+ tree type = get_type ();
+ if (!type_can_have_value_range_p (type))
+ return false;
+
+ out.set_varying (type);
+ return true;
+}
+
/* class region_svalue : public svalue. */
/* Implementation of svalue::dump_to_pp vfunc for region_svalue. */
@@ -1165,6 +1195,22 @@ constant_svalue::all_zeroes_p () const
return zerop (m_cst_expr);
}
+
+/* Implementation of svalue::maybe_get_value_range for constant_svalue.
+ If there is a suitable underlying type, write the value_range for the
+ single value of m_cst_expr to OUT and return true; otherwise return
+ false. */
+
+bool
+constant_svalue::maybe_get_value_range (value_range &out) const
+{
+ if (!type_can_have_value_range_p (get_type ()))
+ return false;
+
+ out = value_range (m_cst_expr, m_cst_expr);
+ return true;
+}
+
/* class unknown_svalue : public svalue. */
/* Implementation of svalue::dump_to_pp vfunc for unknown_svalue. */
@@ -1228,6 +1274,14 @@ unknown_svalue::maybe_fold_bits_within (tree type,
return mgr->get_or_create_unknown_svalue (type);
}
+bool
+unknown_svalue::maybe_get_value_range (value_range &) const
+{
+ /* Don't attempt to participate in range ops. */
+ return false;
+}
+
+
/* Get a string for KIND for use in debug dumps. */
const char *
@@ -1518,6 +1572,33 @@ unaryop_svalue::maybe_fold_bits_within (tree type,
return nullptr;
}
+/* Implementation of svalue::maybe_get_value_range for unaryop_svalue. */
+
+bool
+unaryop_svalue::maybe_get_value_range (value_range &out) const
+{
+ tree type = get_type ();
+ if (!type_can_have_value_range_p (type))
+ return false;
+
+ value_range arg_vr;
+ if (m_arg->maybe_get_value_range (arg_vr))
+ {
+ range_op_handler handler (m_op);
+ if (handler)
+ {
+ /* For unary ops, range_op_hander::fold_range expects
+ a VARYING of the unknown value as the 2nd operand. */
+ value_range varying (type);
+ varying.set_varying (type);
+ out.set_type (type);
+ if (handler.fold_range (out, type, arg_vr, varying))
+ return true;
+ }
+ }
+ return false;
+}
+
/* class binop_svalue : public svalue. */
/* Return whether OP be printed as an infix operator. */
@@ -1634,6 +1715,38 @@ sub_svalue::sub_svalue (symbol::id_t id,
gcc_assert (parent_svalue->can_have_associated_state_p ());
}
+/* Implementation of svalue::maybe_get_value_range for binop_svalue. */
+
+bool
+binop_svalue::maybe_get_value_range (value_range &out) const
+{
+ tree type = get_type ();
+ if (!type_can_have_value_range_p (type))
+ return false;
+
+ /* Avoid cases where we have been sloppy about types. */
+ if (!m_arg0->get_type ())
+ return false;
+ if (!m_arg1->get_type ())
+ return false;
+ if (!range_compatible_p (m_arg0->get_type (), m_arg1->get_type ()))
+ return false;
+
+ value_range lhs, rhs;
+ if (m_arg0->maybe_get_value_range (lhs))
+ if (m_arg1->maybe_get_value_range (rhs))
+ {
+ range_op_handler handler (m_op);
+ if (handler)
+ {
+ out.set_type (type);
+ if (handler.fold_range (out, get_type (), lhs, rhs))
+ return true;
+ }
+ }
+ return false;
+}
+
/* Implementation of svalue::dump_to_pp vfunc for sub_svalue. */
void
diff --git a/gcc/analyzer/svalue.h b/gcc/analyzer/svalue.h
index 5025d966f8f0..bd3ffdd52d8f 100644
--- a/gcc/analyzer/svalue.h
+++ b/gcc/analyzer/svalue.h
@@ -190,6 +190,10 @@ public:
tree maybe_get_type_from_typeinfo () const;
+ /* If we can get a value_range for this svalue, write it to OUT
+ and return true. Otherwise return false. */
+ virtual bool maybe_get_value_range (value_range &out) const;
+
protected:
svalue (complexity c, symbol::id_t id, tree type)
: symbol (c, id), m_type (type)
@@ -366,6 +370,8 @@ public:
bool all_zeroes_p () const final override;
+ bool maybe_get_value_range (value_range &out) const final override;
+
private:
tree m_cst_expr;
};
@@ -417,6 +423,8 @@ public:
const bit_range &subrange,
region_model_manager *mgr) const final override;
+ bool maybe_get_value_range (value_range &out) const final override;
+
/* Unknown values are singletons per-type, so can't have state. */
bool can_have_associated_state_p () const final override { return false; }
};
@@ -763,6 +771,8 @@ public:
const bit_range &subrange,
region_model_manager *mgr) const final override;
+ bool maybe_get_value_range (value_range &out) const final override;
+
private:
enum tree_code m_op;
const svalue *m_arg;
@@ -859,6 +869,8 @@ public:
bool implicitly_live_p (const svalue_set *,
const region_model *) const final override;
+ bool maybe_get_value_range (value_range &out) const final override;
+
enum tree_code get_op () const { return m_op; }
const svalue *get_arg0 () const { return m_arg0; }
const svalue *get_arg1 () const { return m_arg1; }
diff --git a/gcc/testsuite/c-c++-common/analyzer/conditionals-pr98447-1.c
b/gcc/testsuite/c-c++-common/analyzer/conditionals-pr98447-1.c
new file mode 100644
index 000000000000..b94d1ae9d67d
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/analyzer/conditionals-pr98447-1.c
@@ -0,0 +1,28 @@
+void
+pr98447_original (unsigned long *p, int r, int i)
+{
+ int b = 63, n = r % 16;
+
+ while (i >= 0)
+ {
+ if (n > b)
+ {
+ p[i--] = b + 1 >= 64 ? 0UL : 1UL << (b + 1); /* { dg-bogus
"-Wanalyzer-shift-count-overflow" } */
+ b += 64;
+ }
+ b -= n;
+ }
+}
+
+void
+pr98477_comment_4 (unsigned long *p, int r, int i)
+{
+ int b = 64, n = r % 64;
+
+ while (i >= 0 && b >= 0)
+ {
+ if (b <= n)
+ p[i--] = 1UL << b; /* { dg-bogus "-Wanalyzer-shift-count-overflow" } */
+ b -= n;
+ }
+}
diff --git a/gcc/testsuite/c-c++-common/analyzer/conditionals-pr98447-2.c
b/gcc/testsuite/c-c++-common/analyzer/conditionals-pr98447-2.c
new file mode 100644
index 000000000000..73f87af19e7f
--- /dev/null
+++ b/gcc/testsuite/c-c++-common/analyzer/conditionals-pr98447-2.c
@@ -0,0 +1,40 @@
+#include "analyzer-decls.h"
+
+void test_1 (int i)
+{
+ __analyzer_eval (64 <= (i % 64)); /* { dg-warning "FALSE" } */
+ __analyzer_eval (64 < (i % 64)); /* { dg-warning "FALSE" } */
+ __analyzer_eval (63 <= (i % 64)); /* { dg-warning "UNKNOWN" } */
+
+ /* (i % 64) > X for various X. */
+ __analyzer_eval ((i % 64) > -65); /* { dg-warning "TRUE" } */
+ __analyzer_eval ((i % 64) > -64); /* { dg-warning "TRUE" } */
+ __analyzer_eval ((i % 64) > -63); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) > 62); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) > 63); /* { dg-warning "FALSE" } */
+ __analyzer_eval ((i % 64) > 64); /* { dg-warning "FALSE" } */
+
+ /* (i % 64) >= X for various X. */
+ __analyzer_eval ((i % 64) >= -64); /* { dg-warning "TRUE" } */
+ __analyzer_eval ((i % 64) >= -63); /* { dg-warning "TRUE" } */
+ __analyzer_eval ((i % 64) >= -62); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) >= 62); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) >= 63); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) >= 64); /* { dg-warning "FALSE" } */
+
+ /* (i % 64) < X for various X. */
+ __analyzer_eval ((i % 64) < -64); /* { dg-warning "FALSE" } */
+ __analyzer_eval ((i % 64) < -63); /* { dg-warning "FALSE" } */
+ __analyzer_eval ((i % 64) < -62); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) < 63); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) < 64); /* { dg-warning "TRUE" } */
+ __analyzer_eval ((i % 64) < 65); /* { dg-warning "TRUE" } */
+
+ /* (i % 64) <= X for various X. */
+ __analyzer_eval ((i % 64) <= -64); /* { dg-warning "FALSE" } */
+ __analyzer_eval ((i % 64) <= -63); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) <= -62); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) <= 62); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval ((i % 64) <= 63); /* { dg-warning "TRUE" } */
+ __analyzer_eval ((i % 64) <= 64); /* { dg-warning "TRUE" } */
+}
diff --git
a/gcc/testsuite/c-c++-common/analyzer/null-deref-pr108400-SoftEtherVPN-WebUi.c
b/gcc/testsuite/c-c++-common/analyzer/null-deref-pr108400-SoftEtherVPN-WebUi.c
index 0ebeeff8348c..1ae93b1fa212 100644
---
a/gcc/testsuite/c-c++-common/analyzer/null-deref-pr108400-SoftEtherVPN-WebUi.c
+++
b/gcc/testsuite/c-c++-common/analyzer/null-deref-pr108400-SoftEtherVPN-WebUi.c
@@ -60,8 +60,8 @@ void WuExpireSessionKey(WEBUI *wu)
for(i=0; i<LIST_NUM(wu->Contexts); i++)
{
- STRMAP_ENTRY *entry = (STRMAP_ENTRY*)LIST_DATA(wu->Contexts,
i); /* { dg-message "'entry' is NULL" } */
- WU_CONTEXT *context = (WU_CONTEXT*)entry->Value; /* { dg-bogus
"dereference of NULL 'entry'" "PR analyzer/108400" { xfail *-*-* } } */
+ STRMAP_ENTRY *entry = (STRMAP_ENTRY*)LIST_DATA(wu->Contexts,
i); /* { dg-bogus "'entry' is NULL" "" { xfail c++ } } */
+ WU_CONTEXT *context = (WU_CONTEXT*)entry->Value; /* { dg-bogus
"dereference of NULL 'entry'" "PR analyzer/108400" { xfail c++ } } */
if(context->ExpireDate < Tick64())
{
Add(Expired, entry);
diff --git a/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
b/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
index b7301616edd1..ce77d1254772 100644
--- a/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/data-model-1.c
@@ -374,7 +374,7 @@ void test_20 (int i, int j)
__analyzer_eval (i & 1); /* { dg-warning "UNKNOWN" } */
__analyzer_eval (i & j); /* { dg-warning "UNKNOWN" } */
- __analyzer_eval (i | 1); /* { dg-warning "UNKNOWN" } */
+ __analyzer_eval (i | 1); /* { dg-warning "TRUE" } */
__analyzer_eval (i | j); /* { dg-warning "UNKNOWN" } */
__analyzer_eval (i ^ 1); /* { dg-warning "UNKNOWN" } */
--
2.26.3
