From patchwork Tue Jan 11 14:19:35 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1578519 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=JD7Sfr/8; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4JYD115TYCz9s1l for ; Wed, 12 Jan 2022 01:41:55 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7C97938A9403 for ; Tue, 11 Jan 2022 14:41:53 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7C97938A9403 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1641912113; bh=h0quqHDKNB98jJqPrwwuoWNWAh+vWlKK3oUuP4WTSLw=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=JD7Sfr/8m5OskXQd2WQcxRlb3USNyl8aNQdr5B2IxCLgWggIDQax/PuwGFhWSyusj sMEGBX2YiZN/uyAbvRD1+Ul9FaQilfCXYeneviZFfDaUPIYFaI+rV1Z1QYoBNZzdlP JW0pTR+xhRaQL8KDxvIIBFiPgtrypx17fLH/JZ6k= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 53C6F38AAC1A for ; Tue, 11 Jan 2022 14:19:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 53C6F38AAC1A Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-251-Vxo7Hg4AOWadFEBt0rgkjg-1; Tue, 11 Jan 2022 09:19:40 -0500 X-MC-Unique: Vxo7Hg4AOWadFEBt0rgkjg-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id D2BCF5F9CF for ; Tue, 11 Jan 2022 14:19:38 +0000 (UTC) Received: from t14s.localdomain.com (unknown [10.2.16.212]) by smtp.corp.redhat.com (Postfix) with ESMTP id 611AA7D3D2; Tue, 11 Jan 2022 14:19:38 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [committed] analyzer: fix false +ve on bitwise binops (PR analyzer/102692) Date: Tue, 11 Jan 2022 09:19:35 -0500 Message-Id: <20220111141935.1430352-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: David Malcolm via Gcc-patches From: David Malcolm Reply-To: David Malcolm Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" 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. Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as r12-6476-g4f34f8cc1d064bfaaed723312c71e92f495d429b. 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. --- 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(-) create mode 100644 gcc/testsuite/gcc.dg/analyzer/pr102692.c diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc index 766effa75a4..cf480514c0e 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; + } +}