From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2209) id E483038A9425; Tue, 11 Jan 2022 14:17:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E483038A9425 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 r12-6476] analyzer: fix false +ve on bitwise binops (PR analyzer/102692) X-Act-Checkin: gcc X-Git-Author: David Malcolm X-Git-Refname: refs/heads/master X-Git-Oldrev: 438f2a24a4f02a3128847f7186bfcb56e7a60d83 X-Git-Newrev: 4f34f8cc1d064bfaaed723312c71e92f495d429b Message-Id: <20220111141724.E483038A9425@sourceware.org> Date: Tue, 11 Jan 2022 14:17:24 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 11 Jan 2022 14:17:25 -0000 https://gcc.gnu.org/g:4f34f8cc1d064bfaaed723312c71e92f495d429b commit r12-6476-g4f34f8cc1d064bfaaed723312c71e92f495d429b Author: David Malcolm Date: Fri Jan 7 17:44:23 2022 -0500 analyzer: fix false +ve on bitwise binops (PR analyzer/102692) PR analyzer/102692 reports a false positive at -O2 from -Wanalyzer-null-dereference on: if (!p || q || !p->next) At the gimple level, -O2 has converted the first || into bitwise or controlling a jump: _4 = _2 | _3; if (_4 != 0) and a recursive call has been converted to iteration. The analyzer hits the symbolic value complexity limit whilst analyzing the iteration and hits a case where _2 is (_Bool)1 (i.e. true) and _3 (i.e. q) is UNKNOWN(_Bool). There are two issues leading to the false positive; fixing either issue fixes the false positive; this patch fixes both for good measure: (a) The analyzer erronously treats bitwise ops on UNKNOWN(_Bool) as UNKNOWN, even for case like (1 | UNKNOWN) where we know the result, leading to bogus edges in the exploded graph. The patch fixes these cases. (b) The state-handling code creates "UNKNOWN" symbolic values, as a way to give up when symbolic expressions get too complicated, and in various other cases. This makes sense when building the exploded graph, since we want the analysis to terminate, but doesn't make sense when checking the feasibility along a specific path, where we want precision. The patch prevents all use of "unknown" symbolic values when performing feasibility checking of a path (before it merely stopped doing complexity-checking), by creating a unique placeholder_svalue instead. This fixes the -Wanalyzer-null-dereference false positive. Unfortunately, with GCC 12 there's also a false positive from -Wanalyzer-use-of-uninitialized-value on this code, which is a separate issue that the patch does not fix. gcc/analyzer/ChangeLog: PR analyzer/102692 * diagnostic-manager.cc (class auto_disable_complexity_checks): Rename to... (class auto_checking_feasibility): ...this, updating the calls accordingly. (epath_finder::explore_feasible_paths): Update for renaming. * region-model-manager.cc (region_model_manager::region_model_manager): Update for change from m_check_complexity to m_checking_feasibility. (region_model_manager::reject_if_too_complex): Likewise. (region_model_manager::get_or_create_unknown_svalue): Handle m_checking_feasibility. (region_model_manager::create_unique_svalue): New. (region_model_manager::maybe_fold_binop): Handle BIT_AND_EXPR and BIT_IOR_EXPRs on booleans where we know the result. * region-model.cc (test_binop_svalue_folding): Add test coverage for the above. * region-model.h (region_model_manager::create_unique_svalue): New decl. (region_model_manager::enable_complexity_check): Replace with... (region_model_manager::begin_checking_feasibility): ...this. (region_model_manager::disable_complexity_check): Replace with... (region_model_manager::end_checking_feasibility): ...this. (region_model_manager::m_check_complexity): Replace with... (region_model_manager::m_checking_feasibility): ...this. (region_model_manager::m_managed_dynamic_svalues): New field. gcc/testsuite/ChangeLog: PR analyzer/102692 * gcc.dg/analyzer/pr102692.c: New test. Signed-off-by: David Malcolm Diff: --- gcc/analyzer/diagnostic-manager.cc | 17 +++-- gcc/analyzer/region-model-manager.cc | 55 +++++++++++++++- gcc/analyzer/region-model.cc | 33 ++++++++++ gcc/analyzer/region-model.h | 16 ++++- gcc/testsuite/gcc.dg/analyzer/pr102692.c | 110 +++++++++++++++++++++++++++++++ 5 files changed, 219 insertions(+), 12 deletions(-) diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index e9b8fe36177..73c133dd66d 100644 --- a/gcc/analyzer/diagnostic-manager.cc +++ b/gcc/analyzer/diagnostic-manager.cc @@ -303,18 +303,21 @@ private: Hence this is an RAII class for temporarily disabling complexity-checking in the region_model_manager, for use within - epath_finder::explore_feasible_paths. */ + epath_finder::explore_feasible_paths. -class auto_disable_complexity_checks + We also disable the creation of unknown_svalue instances during feasibility + checking, instead creating unique svalues, to avoid paradoxes in paths. */ + +class auto_checking_feasibility { public: - auto_disable_complexity_checks (region_model_manager *mgr) : m_mgr (mgr) + auto_checking_feasibility (region_model_manager *mgr) : m_mgr (mgr) { - m_mgr->disable_complexity_check (); + m_mgr->begin_checking_feasibility (); } - ~auto_disable_complexity_checks () + ~auto_checking_feasibility () { - m_mgr->enable_complexity_check (); + m_mgr->end_checking_feasibility (); } private: region_model_manager *m_mgr; @@ -406,7 +409,7 @@ epath_finder::explore_feasible_paths (const exploded_node *target_enode, exploded_path *best_path = NULL; { - auto_disable_complexity_checks sentinel (mgr); + auto_checking_feasibility sentinel (mgr); while (process_worklist_item (&worklist, tg, &fg, target_enode, diag_idx, &best_path)) diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc index 998bbe7858c..903cdfde91d 100644 --- a/gcc/analyzer/region-model-manager.cc +++ b/gcc/analyzer/region-model-manager.cc @@ -73,7 +73,7 @@ region_model_manager::region_model_manager (logger *logger) m_stack_region (alloc_region_id (), &m_root_region), m_heap_region (alloc_region_id (), &m_root_region), m_unknown_NULL (NULL), - m_check_complexity (true), + m_checking_feasibility (false), m_max_complexity (0, 0), m_code_region (alloc_region_id (), &m_root_region), m_fndecls_map (), m_labels_map (), @@ -166,7 +166,7 @@ region_model_manager::too_complex_p (const complexity &c) const bool region_model_manager::reject_if_too_complex (svalue *sval) { - if (!m_check_complexity) + if (m_checking_feasibility) return false; const complexity &c = sval->get_complexity (); @@ -238,6 +238,11 @@ region_model_manager::get_or_create_int_cst (tree type, poly_int64 val) const svalue * region_model_manager::get_or_create_unknown_svalue (tree type) { + /* Don't create unknown values when doing feasibility testing; + instead, create a unique svalue. */ + if (m_checking_feasibility) + return create_unique_svalue (type); + /* Special-case NULL, so that the hash_map can use NULL as the "empty" value. */ if (type == NULL_TREE) @@ -255,6 +260,16 @@ region_model_manager::get_or_create_unknown_svalue (tree type) return sval; } +/* Return a freshly-allocated svalue of TYPE, owned by this manager. */ + +const svalue * +region_model_manager::create_unique_svalue (tree type) +{ + svalue *sval = new placeholder_svalue (type, "unique"); + m_managed_dynamic_svalues.safe_push (sval); + return sval; +} + /* Return the svalue * for the initial value of REG, creating it if necessary. */ @@ -584,6 +599,42 @@ region_model_manager::maybe_fold_binop (tree type, enum tree_code op, cst1, arg1)) return sval; } + if (arg0->get_type () == boolean_type_node + && arg1->get_type () == boolean_type_node) + { + /* If the LHS are both _Bool, then... */ + /* ..."(1 & x) -> x". */ + if (cst0 && !zerop (cst0)) + return get_or_create_cast (type, arg1); + /* ..."(x & 1) -> x". */ + if (cst1 && !zerop (cst1)) + return get_or_create_cast (type, arg0); + /* ..."(0 & x) -> 0". */ + if (cst0 && zerop (cst0)) + return get_or_create_int_cst (type, 0); + /* ..."(x & 0) -> 0". */ + if (cst1 && zerop (cst1)) + return get_or_create_int_cst (type, 0); + } + break; + case BIT_IOR_EXPR: + if (arg0->get_type () == boolean_type_node + && arg1->get_type () == boolean_type_node) + { + /* If the LHS are both _Bool, then... */ + /* ..."(1 | x) -> 1". */ + if (cst0 && !zerop (cst0)) + return get_or_create_int_cst (type, 1); + /* ..."(x | 1) -> 1". */ + if (cst1 && !zerop (cst1)) + return get_or_create_int_cst (type, 1); + /* ..."(0 | x) -> x". */ + if (cst0 && zerop (cst0)) + return get_or_create_cast (type, arg1); + /* ..."(x | 0) -> x". */ + if (cst1 && zerop (cst1)) + return get_or_create_cast (type, arg0); + } break; case TRUTH_ANDIF_EXPR: case TRUTH_AND_EXPR: diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index 8708a91551d..b58d0894d4a 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -4555,6 +4555,39 @@ test_binop_svalue_folding () = mgr.get_or_create_binop (integer_type_node, PLUS_EXPR, x_init_plus_one, cst_sval[1]); ASSERT_EQ (x_init_plus_one_plus_one, x_init_plus_two); + + /* Verify various binops on booleans. */ + { + const svalue *sval_true = mgr.get_or_create_int_cst (boolean_type_node, 1); + const svalue *sval_false = mgr.get_or_create_int_cst (boolean_type_node, 0); + const svalue *sval_unknown + = mgr.get_or_create_unknown_svalue (boolean_type_node); + const placeholder_svalue sval_placeholder (boolean_type_node, "v"); + for (auto op : {BIT_IOR_EXPR, TRUTH_OR_EXPR}) + { + ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, + sval_true, sval_unknown), + sval_true); + ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, + sval_false, sval_unknown), + sval_unknown); + ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, + sval_false, &sval_placeholder), + &sval_placeholder); + } + for (auto op : {BIT_AND_EXPR, TRUTH_AND_EXPR}) + { + ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, + sval_false, sval_unknown), + sval_false); + ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, + sval_true, sval_unknown), + sval_unknown); + ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, + sval_true, &sval_placeholder), + &sval_placeholder); + } + } } /* Verify that sub_svalues are folded as expected. */ diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h index b1fa4fc82af..c78efe8f215 100644 --- a/gcc/analyzer/region-model.h +++ b/gcc/analyzer/region-model.h @@ -286,6 +286,11 @@ public: const svalue *maybe_get_char_from_string_cst (tree string_cst, tree byte_offset_cst); + /* Dynamically-allocated svalue instances. + The number of these within the analysis can grow arbitrarily. + They are still owned by the manager. */ + const svalue *create_unique_svalue (tree type); + /* region consolidation. */ const stack_region * get_stack_region () const { return &m_stack_region; } const heap_region *get_heap_region () const { return &m_heap_region; } @@ -332,8 +337,8 @@ public: void log_stats (logger *logger, bool show_objs) const; - void enable_complexity_check (void) { m_check_complexity = true; } - void disable_complexity_check (void) { m_check_complexity = false; } + void begin_checking_feasibility (void) { m_checking_feasibility = true; } + void end_checking_feasibility (void) { m_checking_feasibility = false; } logger *get_logger () const { return m_logger; } @@ -429,7 +434,12 @@ private: asm_output_svalue *> asm_output_values_map_t; asm_output_values_map_t m_asm_output_values_map; - bool m_check_complexity; + bool m_checking_feasibility; + + /* "Dynamically-allocated" svalue instances. + The number of these within the analysis can grow arbitrarily. + They are still owned by the manager. */ + auto_delete_vec m_managed_dynamic_svalues; /* Maximum complexity of svalues that weren't rejected. */ complexity m_max_complexity; diff --git a/gcc/testsuite/gcc.dg/analyzer/pr102692.c b/gcc/testsuite/gcc.dg/analyzer/pr102692.c new file mode 100644 index 00000000000..c8993c82980 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/pr102692.c @@ -0,0 +1,110 @@ +/* { dg-additional-options "-O2 -Wno-analyzer-too-complex" } */ +/* TODO: remove the need for -Wno-analyzer-too-complex. */ + +struct lisp; +union vectorlike_header { long size; }; + +static struct lisp * +make_lisp_ptr (void *ptr, int type) +{ + char *p = ptr; + void *q = p + type; + return q; +} + +static _Bool +TAGGEDP (struct lisp *a, unsigned tag) +{ + return ! (((unsigned) (long) a - tag) & 7); +} + +static _Bool +VECTORLIKEP (struct lisp *x) +{ + return TAGGEDP (x, 5); +} + +extern _Bool +PSEUDOVECTOR_TYPEP (union vectorlike_header const *a, int code); + +static _Bool +PSEUDOVECTORP (struct lisp *a, int code) +{ + if (! VECTORLIKEP (a)) + return 0; + else + return PSEUDOVECTOR_TYPEP ((union vectorlike_header *) ((char *) a - 5), + code); +} + +struct Lisp_Overlay +{ + union vectorlike_header header; + struct lisp *end; + struct Lisp_Overlay *next; +}; + +static _Bool +OVERLAYP (struct lisp *x) +{ + return PSEUDOVECTORP (x, 4); +} + +static struct Lisp_Overlay * +XOVERLAY (struct lisp *a) +{ + void *r = (char *) a - 5; + return r; +} +struct buffer { struct Lisp_Overlay *overlays_before; }; + +long marker_position (struct lisp *); + +void +fix_overlays_before (struct buffer *bp, long prev, long pos) +{ + struct Lisp_Overlay *tail = bp->overlays_before, *parent = 0, *right_pair; + struct lisp *tem; + long end; + while (tail + && (tem = make_lisp_ptr (tail, 5), + (end = marker_position (XOVERLAY (tem)->end)) >= pos)) + { + parent = tail; + tail = tail->next; + } + if (!tail || end < prev || !tail->next) /* { dg-bogus "use of uninitialized value 'end'" "uninit" { xfail *-*-* } } */ + /* { dg-bogus "dereference of NULL 'tail'" "null deref" { target *-*-* } .-1 } */ + return; + right_pair = parent; + parent = tail; + tail = tail->next; + while (tail) + { + tem = make_lisp_ptr (tail, 5); + end = marker_position (XOVERLAY (tem)->end); + if (end == pos) + { + struct Lisp_Overlay *found = tail; + tail = found->next; + parent->next = tail; + if (!right_pair) + { + found->next = bp->overlays_before; + bp->overlays_before = found; + } + else + { + found->next = right_pair->next; + right_pair->next = found; + } + } + else if (end == prev) + { + parent = tail; + tail = tail->next; + } + else + break; + } +}