@@ -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;
+}