From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2209) id 041103858D33; Thu, 16 Feb 2023 23:14:51 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 041103858D33 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1676589292; bh=lYbRC8qYXoDYXE5iiUgVkPfKweMEuWbdmJeXa7AxwKw=; h=From:To:Subject:Date:From; b=bJZepMYoyQv2SnZXPLWzCM30/qunaZkXNYKWDxsfLZpvjPS345/hB8bDx6tPdQQV7 zshKHKua0chezc8VqEr6KmWKDhAIslJPxH1lQ3/1Go65qlDZnXyI3g9UUHKFhwHuGA ANIjZ/KDtCCwI1q+oNDlu9X2gDrgUZtoAuhmAu4M= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: David Malcolm To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-6101] analyzer: respect some conditions from bit masks [PR108806] X-Act-Checkin: gcc X-Git-Author: David Malcolm X-Git-Refname: refs/heads/master X-Git-Oldrev: c381327dd6c2d9996702b2a341b91cf48942a8ae X-Git-Newrev: 4d3b7be281e73ecdaa233598db1a8390422b7770 Message-Id: <20230216231452.041103858D33@sourceware.org> Date: Thu, 16 Feb 2023 23:14:51 +0000 (GMT) List-Id: https://gcc.gnu.org/g:4d3b7be281e73ecdaa233598db1a8390422b7770 commit r13-6101-g4d3b7be281e73ecdaa233598db1a8390422b7770 Author: David Malcolm Date: Thu Feb 16 18:12:55 2023 -0500 analyzer: respect some conditions from bit masks [PR108806] 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) 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 Diff: --- gcc/analyzer/constraint-manager.cc | 166 ++++++++++++++++++++- gcc/analyzer/constraint-manager.h | 7 + gcc/analyzer/region-model.cc | 3 + .../gcc.dg/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(-) diff --git a/gcc/analyzer/constraint-manager.cc b/gcc/analyzer/constraint-manager.cc index 5a859c6c0f7..2c9c435527e 100644 --- a/gcc/analyzer/constraint-manager.cc +++ b/gcc/analyzer/constraint-manager.cc @@ -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 (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; } diff --git a/gcc/analyzer/constraint-manager.h b/gcc/analyzer/constraint-manager.h index 2d82bc9656c..3afbc7f848e 100644 --- a/gcc/analyzer/constraint-manager.h +++ b/gcc/analyzer/constraint-manager.h @@ -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; }; diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index 424d83c191f..e3de74bbf45 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -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); diff --git a/gcc/testsuite/gcc.dg/analyzer/null-deref-pr108806-qemu.c b/gcc/testsuite/gcc.dg/analyzer/null-deref-pr108806-qemu.c new file mode 100644 index 00000000000..3ab72c053af --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/null-deref-pr108806-qemu.c @@ -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; +} diff --git a/gcc/testsuite/gcc.dg/analyzer/pr103217.c b/gcc/testsuite/gcc.dg/analyzer/pr103217.c index a0ef8bf3210..08889acb2c9 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr103217.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr103217.c @@ -1,3 +1,5 @@ +/* { dg-additional-options "-Wno-analyzer-too-complex" } */ + extern char *strdup (const char *__s) __attribute__ ((__nothrow__ , __leaf__, __malloc__, __nonnull__ (1))); diff --git a/gcc/testsuite/gcc.dg/analyzer/switch.c b/gcc/testsuite/gcc.dg/analyzer/switch.c index 0b9e7e3b869..5f42e7f21db 100644 --- a/gcc/testsuite/gcc.dg/analyzer/switch.c +++ b/gcc/testsuite/gcc.dg/analyzer/switch.c @@ -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; + } +} diff --git a/gcc/testsuite/gcc.dg/analyzer/uninit-pr108806-qemu.c b/gcc/testsuite/gcc.dg/analyzer/uninit-pr108806-qemu.c new file mode 100644 index 00000000000..34fe802f495 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/uninit-pr108806-qemu.c @@ -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; +}