@@ -421,7 +421,7 @@ dump_cst (pretty_printer *pp, tree cst, bool show_types)
void
bounded_range::dump_to_pp (pretty_printer *pp, bool show_types) const
{
- if (tree_int_cst_equal (m_lower, m_upper))
+ if (singleton_p ())
dump_cst (pp, m_lower, show_types);
else
{
@@ -2118,6 +2118,17 @@ bool
constraint_manager::add_bounded_ranges (const svalue *sval,
const bounded_ranges *ranges)
{
+ /* If RANGES is just a singleton, convert this to adding the constraint:
+ "SVAL == {the singleton}". */
+ if (ranges->get_count () == 1
+ && ranges->get_range (0).singleton_p ())
+ {
+ tree range_cst = ranges->get_range (0).m_lower;
+ const svalue *range_sval
+ = m_mgr->get_or_create_constant_svalue (range_cst);
+ return add_constraint (sval, EQ_EXPR, range_sval);
+ }
+
sval = sval->unwrap_any_unmergeable ();
/* Nothing can be known about unknown/poisoned values. */
@@ -2466,6 +2477,66 @@ constraint_manager::eval_condition (equiv_class_id lhs_ec,
return tristate::unknown ();
}
+/* Return true iff "LHS == RHS" is known to be impossible due to
+ derived conditions.
+
+ Look for an EC containing an EC_VAL of the form (LHS OP CST).
+ If found, see if (LHS OP CST) == EC_VAL is false.
+ If so, we know this condition is false.
+
+ For example, if we already know that
+ (X & CST_MASK) == Y
+ and we're evaluating X == Z, we can test to see if
+ (Z & CST_MASK) == EC_VAL
+ and thus if:
+ (Z & CST_MASK) == Y
+ and reject this if we know that's false. */
+
+bool
+constraint_manager::impossible_derived_conditions_p (const svalue *lhs,
+ const svalue *rhs) const
+{
+ int i;
+ equiv_class *ec;
+ FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
+ {
+ for (const svalue *ec_sval : ec->m_vars)
+ switch (ec_sval->get_kind ())
+ {
+ default:
+ break;
+ case SK_BINOP:
+ {
+ const binop_svalue *iter_binop
+ = as_a <const binop_svalue *> (ec_sval);
+ if (lhs == iter_binop->get_arg0 ()
+ && iter_binop->get_type ())
+ if (iter_binop->get_arg1 ()->get_kind () == SK_CONSTANT)
+ {
+ /* Try evalating EC_SVAL with LHS
+ as the value of EC_SVAL's lhs, and see if it's
+ consistent with existing knowledge. */
+ const svalue *subst_bin_op
+ = m_mgr->get_or_create_binop
+ (iter_binop->get_type (),
+ iter_binop->get_op (),
+ rhs,
+ iter_binop->get_arg1 ());
+ tristate t = eval_condition (subst_bin_op,
+ EQ_EXPR,
+ ec_sval);
+ if (t.is_false ())
+ return true; /* Impossible. */
+ }
+ }
+ break;
+ }
+ }
+ /* Not known to be impossible. */
+ return false;
+}
+
+
/* Evaluate the condition LHS OP RHS, without modifying this
constraint_manager (avoiding the creation of equiv_class instances). */
@@ -2516,6 +2587,10 @@ constraint_manager::eval_condition (const svalue *lhs,
return result_for_ecs;
}
+ if (op == EQ_EXPR
+ && impossible_derived_conditions_p (lhs, rhs))
+ return false;
+
/* If at least one is not in an EC, we have no constraints
comparing LHS and RHS yet.
They might still be comparable if one (or both) is a constant.
@@ -4435,6 +4510,94 @@ test_bounded_ranges ()
mgr.get_or_create_point (ch1));
}
+/* Verify that we can handle sufficiently simple bitmasking operations. */
+
+static void
+test_bits (void)
+{
+ region_model_manager mgr;
+
+ tree int_0 = build_int_cst (integer_type_node, 0);
+ tree int_0x80 = build_int_cst (integer_type_node, 0x80);
+ tree int_0xff = build_int_cst (integer_type_node, 0xff);
+ tree x = build_global_decl ("x", integer_type_node);
+
+ tree x_bit_and_0x80 = build2 (BIT_AND_EXPR, integer_type_node, x, int_0x80);
+ tree x_bit_and_0xff = build2 (BIT_AND_EXPR, integer_type_node, x, int_0xff);
+
+ /* "x & 0x80 == 0x80". */
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, EQ_EXPR, int_0x80);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
+ }
+
+ /* "x & 0x80 != 0x80". */
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, NE_EXPR, int_0x80);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
+ }
+
+ /* "x & 0x80 == 0". */
+ {
+ region_model model (&mgr);
+
+ ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, EQ_EXPR, int_0);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
+ }
+
+ /* "x & 0x80 != 0". */
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, NE_EXPR, int_0);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
+ }
+
+ /* More that one bit in the mask. */
+
+ /* "x & 0xff == 0x80". */
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, EQ_EXPR, int_0x80);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0xff);
+ }
+
+ /* "x & 0xff != 0x80". */
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, NE_EXPR, int_0x80);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0xff);
+ }
+
+ /* "x & 0xff == 0". */
+ {
+ region_model model (&mgr);
+
+ ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, EQ_EXPR, int_0);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0xff);
+ }
+
+ /* "x & 0xff != 0". */
+ {
+ region_model model (&mgr);
+ ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, NE_EXPR, int_0);
+ ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
+ ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0xff);
+ }
+}
+
/* Run the selftests in this file, temporarily overriding
flag_analyzer_transitivity with TRANSITIVITY. */
@@ -4458,6 +4621,7 @@ run_constraint_manager_tests (bool transitivity)
test_purging ();
test_bounded_range ();
test_bounded_ranges ();
+ test_bits ();
flag_analyzer_transitivity = saved_flag_analyzer_transitivity;
}
@@ -100,6 +100,11 @@ struct bounded_range
static int cmp (const bounded_range &a, const bounded_range &b);
+ bool singleton_p () const
+ {
+ return tree_int_cst_equal (m_lower, m_upper);
+ }
+
tree m_lower;
tree m_upper;
@@ -498,6 +503,8 @@ public:
void add_constraint_internal (equiv_class_id lhs_id,
enum constraint_op c_op,
equiv_class_id rhs_id);
+ bool impossible_derived_conditions_p (const svalue *lhs,
+ const svalue *rhs) const;
region_model_manager *m_mgr;
};
@@ -2253,6 +2253,9 @@ region_model::get_rvalue_1 (path_var pv, region_model_context *ctxt) const
/* Binary ops. */
case PLUS_EXPR:
case MULT_EXPR:
+ case BIT_AND_EXPR:
+ case BIT_IOR_EXPR:
+ case BIT_XOR_EXPR:
{
tree expr = pv.m_tree;
tree arg0 = TREE_OPERAND (expr, 0);
new file mode 100644
@@ -0,0 +1,105 @@
+/* Reduced from qemu-7.2.0's hw/intc/omap_intc.c */
+
+#define NULL ((void*)0)
+
+typedef unsigned char __uint8_t;
+typedef unsigned int __uint32_t;
+typedef unsigned long int __uint64_t;
+typedef __uint8_t uint8_t;
+typedef __uint32_t uint32_t;
+typedef __uint64_t uint64_t;
+typedef uint64_t hwaddr;
+typedef struct omap_intr_handler_s omap_intr_handler;
+
+struct omap_intr_handler_bank_s
+{
+ uint32_t irqs;
+ uint32_t inputs;
+ uint32_t mask;
+ uint32_t fiq;
+ uint32_t sens_edge;
+ uint32_t swi;
+ unsigned char priority[32];
+};
+
+struct omap_intr_handler_s
+{
+ /* [...snip...] */
+ unsigned char nbanks;
+ /* [...snip...] */
+ int sir_intr[2];
+ int autoidle;
+ uint32_t mask;
+ struct omap_intr_handler_bank_s bank[3];
+};
+
+uint64_t
+omap2_inth_read(struct omap_intr_handler_s* s, int offset)
+{
+ int bank_no, line_no;
+ struct omap_intr_handler_bank_s* bank = NULL;
+
+ if ((offset & 0xf80) == 0x80) {
+ bank_no = (offset & 0x60) >> 5;
+ if (bank_no < s->nbanks) {
+ offset &= ~0x60;
+ bank = &s->bank[bank_no];
+ } else {
+ return 0;
+ }
+ }
+
+ switch (offset) {
+ case 0x10:
+ return (s->autoidle >> 2) & 1;
+
+ case 0x14:
+ return 1;
+
+ case 0x40:
+ return s->sir_intr[0];
+
+ case 0x44:
+ return s->sir_intr[1];
+
+ case 0x48:
+ return (!s->mask) << 2;
+
+ case 0x4c:
+ return 0;
+
+ case 0x50:
+ return s->autoidle & 3;
+
+ case 0x80:
+ return bank->inputs; /* { dg-bogus "dereference of NULL 'bank'" "PR analyzer/108806" } */
+
+ case 0x84:
+ return bank->mask; /* { dg-bogus "dereference of NULL 'bank'" "PR analyzer/108806" } */
+
+ case 0x88:
+ case 0x8c:
+ return 0;
+
+ case 0x90:
+ return bank->swi; /* { dg-bogus "dereference of NULL 'bank'" "PR analyzer/108806" } */
+
+ case 0x94:
+ return 0;
+
+ case 0x98:
+ return bank->irqs & ~bank->mask & ~bank->fiq; /* { dg-bogus "dereference of NULL 'bank'" "PR analyzer/108806" } */
+
+ case 0x9c:
+ return bank->irqs & ~bank->mask & bank->fiq; /* { dg-bogus "dereference of NULL 'bank'" "PR analyzer/108806" } */
+
+ case 0x100 ... 0x300:
+ bank_no = (offset - 0x100) >> 7;
+ if (bank_no > s->nbanks)
+ break;
+ bank = &s->bank[bank_no];
+ line_no = (offset & 0x7f) >> 2;
+ return (bank->priority[line_no] << 2) | ((bank->fiq >> line_no) & 1);
+ }
+ return 0;
+}
@@ -1,3 +1,5 @@
+/* { dg-additional-options "-Wno-analyzer-too-complex" } */
+
extern char *strdup (const char *__s)
__attribute__ ((__nothrow__ , __leaf__, __malloc__, __nonnull__ (1)));
@@ -161,3 +161,79 @@ int test_7 ()
}
return 0;
}
+
+int test_bitmask_1 (int x)
+{
+ int flag = 0;
+ if (x & 0x80)
+ flag = 1;
+
+ switch (x)
+ {
+ case 0:
+ if (flag)
+ __analyzer_dump_path (); /* { dg-bogus "path" } */
+ else
+ __analyzer_dump_path (); /* { dg-message "path" } */
+ break;
+
+ case 0x80:
+ if (flag)
+ __analyzer_dump_path (); /* { dg-message "path" } */
+ else
+ __analyzer_dump_path (); /* { dg-bogus "path" } */
+ break;
+
+ case 0x81:
+ if (flag)
+ __analyzer_dump_path (); /* { dg-message "path" } */
+ else
+ __analyzer_dump_path (); /* { dg-bogus "path" } */
+ break;
+ }
+}
+
+int test_bitmask_2 (int x)
+{
+ int flag = 0;
+ if ((x & 0xf80) == 0x80)
+ flag = 1;
+
+ switch (x)
+ {
+ case 0:
+ if (flag)
+ __analyzer_dump_path (); /* { dg-bogus "path" } */
+ else
+ __analyzer_dump_path (); /* { dg-message "path" } */
+ break;
+
+ case 0x80:
+ if (flag)
+ __analyzer_dump_path (); /* { dg-message "path" } */
+ else
+ __analyzer_dump_path (); /* { dg-bogus "path" } */
+ break;
+
+ case 0x81:
+ if (flag)
+ __analyzer_dump_path (); /* { dg-message "path" } */
+ else
+ __analyzer_dump_path (); /* { dg-bogus "path" } */
+ break;
+
+ case 0x180:
+ if (flag)
+ __analyzer_dump_path (); /* { dg-bogus "path" } */
+ else
+ __analyzer_dump_path (); /* { dg-message "path" } */
+ break;
+
+ case 0xf80:
+ if (flag)
+ __analyzer_dump_path (); /* { dg-bogus "path" } */
+ else
+ __analyzer_dump_path (); /* { dg-message "path" } */
+ break;
+ }
+}
new file mode 100644
@@ -0,0 +1,108 @@
+/* Reduced from qemu-7.2.0's hw/intc/omap_intc.c as per
+ null-deref-pr108806.c, but with the:
+ struct omap_intr_handler_bank_s* bank = NULL;
+ converted to:
+ struct omap_intr_handler_bank_s* bank;
+ */
+
+typedef unsigned char __uint8_t;
+typedef unsigned int __uint32_t;
+typedef unsigned long int __uint64_t;
+typedef __uint8_t uint8_t;
+typedef __uint32_t uint32_t;
+typedef __uint64_t uint64_t;
+typedef uint64_t hwaddr;
+typedef struct omap_intr_handler_s omap_intr_handler;
+
+struct omap_intr_handler_bank_s
+{
+ uint32_t irqs;
+ uint32_t inputs;
+ uint32_t mask;
+ uint32_t fiq;
+ uint32_t sens_edge;
+ uint32_t swi;
+ unsigned char priority[32];
+};
+
+struct omap_intr_handler_s
+{
+ /* [...snip...] */
+ unsigned char nbanks;
+ /* [...snip...] */
+ int sir_intr[2];
+ int autoidle;
+ uint32_t mask;
+ struct omap_intr_handler_bank_s bank[3];
+};
+
+uint64_t
+omap2_inth_read(struct omap_intr_handler_s* s, int offset)
+{
+ int bank_no, line_no;
+ struct omap_intr_handler_bank_s* bank;
+
+ if ((offset & 0xf80) == 0x80) {
+ bank_no = (offset & 0x60) >> 5;
+ if (bank_no < s->nbanks) {
+ offset &= ~0x60;
+ bank = &s->bank[bank_no];
+ } else {
+ return 0;
+ }
+ }
+
+ switch (offset) {
+ case 0x10:
+ return (s->autoidle >> 2) & 1;
+
+ case 0x14:
+ return 1;
+
+ case 0x40:
+ return s->sir_intr[0];
+
+ case 0x44:
+ return s->sir_intr[1];
+
+ case 0x48:
+ return (!s->mask) << 2;
+
+ case 0x4c:
+ return 0;
+
+ case 0x50:
+ return s->autoidle & 3;
+
+ case 0x80:
+ return bank->inputs; /* { dg-bogus "use of uninitialized value 'bank'" "PR analyzer/108806" } */
+
+ case 0x84:
+ return bank->mask; /* { dg-bogus "use of uninitialized value 'bank'" "PR analyzer/108806" } */
+
+ case 0x88:
+ case 0x8c:
+ return 0;
+
+ case 0x90:
+ return bank->swi; /* { dg-bogus "use of uninitialized value 'bank'" "PR analyzer/108806" } */
+
+ case 0x94:
+ return 0;
+
+ case 0x98:
+ return bank->irqs & ~bank->mask & ~bank->fiq; /* { dg-bogus "use of uninitialized value 'bank'" "PR analyzer/108806" } */
+
+ case 0x9c:
+ return bank->irqs & ~bank->mask & bank->fiq; /* { dg-bogus "use of uninitialized value 'bank'" "PR analyzer/108806" } */
+
+ case 0x100 ... 0x300:
+ bank_no = (offset - 0x100) >> 7;
+ if (bank_no > s->nbanks)
+ break;
+ bank = &s->bank[bank_no];
+ line_no = (offset & 0x7f) >> 2;
+ return (bank->priority[line_no] << 2) | ((bank->fiq >> line_no) & 1);
+ }
+ return 0;
+}
PR analyzer/108806 reports false +ves seen from -fanalyzer on code like this in qemu-7.2.0's hw/intc/omap_intc.c: [...snip...] struct omap_intr_handler_bank_s* bank = NULL; if ((offset & 0xf80) == 0x80) { [...set "bank" to non-NULL...] } switch (offset) { [...snip various cases that don't deref "bank"...] case 0x80: return bank->inputs; case 0x84: return bank->mask; [...etc...] } where the analyzer falsely complains about execution paths in which "(offset & 0xf80) == 0x80" was false (leaving "bank" as NULL), but then in which "switch (offset)" goes to a case for which "(offset & 0xf80) == 0x80" is true and dereferences NULL "bank", i.e. paths in which "(offset & 0xf80) == 0x80" is both true *and* false. This patch adds enough logic to constraint_manager for -fanalyzer to reject such execution paths as impossible, fixing the false +ves. Integration testing shows this eliminates 20 probable false positives: Comparison: 9.08% -> 9.34% GOOD: 66 BAD: 661 -> 641 (-20) where the affected warnings/projects are: -Wanalyzer-null-dereference: 0.00% GOOD: 0 BAD: 279 -> 269 (-10) qemu-7.2.0: 175 -> 165 (-10) -Wanalyzer-use-of-uninitialized-value: 0.00% GOOD: 0 BAD: 153 -> 143 (-10) coreutils-9.1: 18 -> 14 (-4) qemu-7.2.0: 54 -> 48 (-6) Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as r13-6101-g4d3b7be281e73e. gcc/analyzer/ChangeLog: PR analyzer/108806 * constraint-manager.cc (bounded_range::dump_to_pp): Use bounded_range::singleton_p. (constraint_manager::add_bounded_ranges): Handle singleton ranges by adding an EQ_EXPR constraint. (constraint_manager::impossible_derived_conditions_p): New. (constraint_manager::eval_condition): Reject EQ_EXPR when it would imply impossible derived conditions. (selftest::test_bits): New. (selftest::run_constraint_manager_tests): Run it. * constraint-manager.h (bounded_range::singleton_p): New. (constraint_manager::impossible_derived_conditions_p): New decl. * region-model.cc (region_model::get_rvalue_1): Handle BIT_AND_EXPR, BIT_IOR_EXPR, and BIT_XOR_EXPR. gcc/testsuite/ChangeLog: PR analyzer/108806 * gcc.dg/analyzer/null-deref-pr108806-qemu.c: New test. * gcc.dg/analyzer/pr103217.c: Add -Wno-analyzer-too-complex. * gcc.dg/analyzer/switch.c (test_bitmask_1): New. (test_bitmask_2): New. * gcc.dg/analyzer/uninit-pr108806-qemu.c: New test. Signed-off-by: David Malcolm <dmalcolm@redhat.com> --- gcc/analyzer/constraint-manager.cc | 166 +++++++++++++++++- gcc/analyzer/constraint-manager.h | 7 + gcc/analyzer/region-model.cc | 3 + .../analyzer/null-deref-pr108806-qemu.c | 105 +++++++++++ gcc/testsuite/gcc.dg/analyzer/pr103217.c | 2 + gcc/testsuite/gcc.dg/analyzer/switch.c | 76 ++++++++ .../gcc.dg/analyzer/uninit-pr108806-qemu.c | 108 ++++++++++++ 7 files changed, 466 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/analyzer/null-deref-pr108806-qemu.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/uninit-pr108806-qemu.c