From patchwork Wed Mar 1 14:10:33 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 62908 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:5915:0:0:0:0:0 with SMTP id v21csp3653221wrd; Wed, 1 Mar 2023 06:13:00 -0800 (PST) X-Google-Smtp-Source: AK7set99afSTcJejSMFA09uuDMWhJGE7IW3rigYAEkId2d61TNVOJMetK0ZJRtDQMISxVsTEyOJ0 X-Received: by 2002:aa7:cac7:0:b0:4a2:4a89:2331 with SMTP id l7-20020aa7cac7000000b004a24a892331mr7042195edt.29.1677679980438; Wed, 01 Mar 2023 06:13:00 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1677679980; cv=none; d=google.com; s=arc-20160816; b=l1leA+Im7ZYaYYLfoXJnekm7yTzcpoSX1+5NZqlES84gkZ19GRWS8Q7RtCu6GOhVxH SXSwtMeUZLbNuqCB2/P1KwfKUjA/LH2arbGSd2TjoBjWhwtyNzPELGBjWezpfOUQ+WGJ +LHARIk2t9/F0fDoTWDS0Rgo31o24meg4ljPelPOFWjxZn/zu4O11F2XqSaPMB3YM/cI oQXKJNDMgsi9z2O91NamUcmfjKBnXHkA71KtuQ5yhLeR2JeFw4oobMpDexZEXboqJooc 61PxNodsAm0oqxvMNNiohCZ/KE55WfSOp0VutbPp7wGDa2rDR6yWxXAylW+MryZMC9VD eLug== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:message-id:date:subject:cc :to:dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=O2bXfWYBygscfiZ0ZAZPk4/C7ajDBSS13i5tS2+LURc=; b=tWLe1yYeBrPPJRr8jyykpbFJgJIzxXYZjWnY3up2dtuYyaXETttvADAcVytNhofaHY i8MC7aKIK3EoJRW8xOxGG8nyA/7FoZCTgKBaCaFPTDBBm5DLMu8B0ftn0kzaSMRUCmv+ rNuiOKH64VL0DLdHaBUCPAj+E/LxhfTL1oqaeQOf/6gw7PJgrOVwSZ9Qg87IVtGNZsxE RnhKZzH7ZddvTkEIonvkaRtKDykD2wM99BdiY7vCVZ+VabAcufBlOD5pdZvCsKxQRzmz tdQQixRtip+LtmhLJLiY9WgzUnVhGOJJBwaOi54ryMrZ0hj45IGmRA5AEw5O6M/AZCB4 r/1w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=G08aaQqO; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id g23-20020a50ee17000000b004acc81d5053si13991596eds.616.2023.03.01.06.13.00 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 01 Mar 2023 06:13:00 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=G08aaQqO; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 75DCB3858401 for ; Wed, 1 Mar 2023 14:12:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 75DCB3858401 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1677679979; bh=O2bXfWYBygscfiZ0ZAZPk4/C7ajDBSS13i5tS2+LURc=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=G08aaQqOniI2jwanXnURuhmTWDAf9rqMgry84LZlzdRktX8BqgLVXpIjm91Pf+Lcn M9efxN0j5IJl8O1m1SsrZAMz6DPMF0dioDjmMhEfNE6Mms+z1owxAKj6LVZ3js9eND 25odlNaz7gVWs24eJ+J/9mlEdJNkSxLxRnpnfGLI= 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 5A1B13858D33 for ; Wed, 1 Mar 2023 14:12:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5A1B13858D33 Received: from mimecast-mx02.redhat.com (mx3-rdu2.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-661-teZF7yW_MHaT0l5XUtKXgw-1; Wed, 01 Mar 2023 09:12:08 -0500 X-MC-Unique: teZF7yW_MHaT0l5XUtKXgw-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.rdu2.redhat.com [10.11.54.6]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 5C3681C0CB9D for ; Wed, 1 Mar 2023 14:10:37 +0000 (UTC) Received: from t14s.localdomain.com (unknown [10.2.16.186]) by smtp.corp.redhat.com (Postfix) with ESMTP id 314832166B2A; Wed, 1 Mar 2023 14:10:37 +0000 (UTC) To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [pushed] analyzer: fix infinite recursion false +ves [PR108935] Date: Wed, 1 Mar 2023 09:10:33 -0500 Message-Id: <20230301141033.2578200-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.6 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-11.8 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_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1759174963267998279?= X-GMAIL-MSGID: =?utf-8?q?1759174963267998279?= Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as r13-6393-g070523b9d4c6cf. gcc/analyzer/ChangeLog: PR analyzer/108935 * infinite-recursion.cc (contains_unknown_p): New. (sufficiently_different_region_binding_p): New function, splitting out inner loop from... (sufficiently_different_p): ...here. Extend detection of unknown svalues to also include svalues that contain unknown. Treat changes in frames below the entry to the recursion as being sufficiently different to reject being an infinite recursion. gcc/testsuite/ChangeLog: PR analyzer/108935 * gcc.dg/analyzer/infinite-recursion-pr108935-1.c: New test. * gcc.dg/analyzer/infinite-recursion-pr108935-1a.c: New test. * gcc.dg/analyzer/infinite-recursion-pr108935-2.c: New test. Signed-off-by: David Malcolm --- gcc/analyzer/infinite-recursion.cc | 151 ++++++++++++------ .../analyzer/infinite-recursion-pr108935-1.c | 17 ++ .../analyzer/infinite-recursion-pr108935-1a.c | 17 ++ .../analyzer/infinite-recursion-pr108935-2.c | 18 +++ 4 files changed, 152 insertions(+), 51 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c diff --git a/gcc/analyzer/infinite-recursion.cc b/gcc/analyzer/infinite-recursion.cc index 1886534313e..c262e391953 100644 --- a/gcc/analyzer/infinite-recursion.cc +++ b/gcc/analyzer/infinite-recursion.cc @@ -394,12 +394,108 @@ remap_enclosing_frame (const region *base_reg, } } +/* Return true iff SVAL is unknown, or contains an unknown svalue. */ + +static bool +contains_unknown_p (const svalue *sval) +{ + if (sval->get_kind () == SK_UNKNOWN) + return true; + if (const compound_svalue *compound_sval + = sval->dyn_cast_compound_svalue ()) + for (auto iter : *compound_sval) + if (iter.second->get_kind () == SK_UNKNOWN) + return true; + return false; +} + +/* Subroutine of sufficiently_different_p. Compare the store bindings + for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE. + + Return true if the state of NEW_ENTRY_ENODE is sufficiently different + from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is + being modified, and thus the recursion isn't infinite. + + Return false if the states for BASE_REG are effectively the same. */ + +static bool +sufficiently_different_region_binding_p (exploded_node *new_entry_enode, + exploded_node *prev_entry_enode, + const region *base_reg) +{ + /* Compare the stores of the two enodes. */ + const region_model &new_model + = *new_entry_enode->get_state ().m_region_model; + const region_model &prev_model + = *prev_entry_enode->get_state ().m_region_model; + + /* Get the value within the new frame. */ + const svalue *new_sval + = new_model.get_store_value (base_reg, NULL); + + /* If any part of the value is UNKNOWN (e.g. due to hitting + complexity limits) assume that it differs from the previous + value. */ + if (contains_unknown_p (new_sval)) + return true; + + /* Get the equivalent value within the old enode. */ + const svalue *prev_sval; + + if (const frame_region *enclosing_frame + = base_reg->maybe_get_frame_region ()) + { + /* We have a binding within a frame in the new entry enode. */ + + /* Consider changes in bindings below the original entry + to the recursion. */ + const int old_stack_depth = prev_entry_enode->get_stack_depth (); + if (enclosing_frame->get_stack_depth () < old_stack_depth) + prev_sval = prev_model.get_store_value (base_reg, NULL); + else + { + /* Ignore bindings within frames below the new entry node. */ + const int new_stack_depth = new_entry_enode->get_stack_depth (); + if (enclosing_frame->get_stack_depth () < new_stack_depth) + return false; + + /* We have a binding within the frame of the new entry node, + presumably a parameter. */ + + /* Get the value within the equivalent frame of + the old entrypoint; typically will be the initial_svalue + of the parameter. */ + const frame_region *equiv_prev_frame + = prev_model.get_current_frame (); + const region *equiv_prev_base_reg + = remap_enclosing_frame (base_reg, + enclosing_frame, + equiv_prev_frame, + new_model.get_manager ()); + prev_sval + = prev_model.get_store_value (equiv_prev_base_reg, NULL); + } + } + else + prev_sval = prev_model.get_store_value (base_reg, NULL); + + /* If the prev_sval contains UNKNOWN (e.g. due to hitting complexity limits) + assume that it will differ from any new value. */ + if (contains_unknown_p (prev_sval)) + return true; + + if (new_sval != prev_sval) + return true; + + return false; +} + /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE, both of which are entrypoints to the same function, where recursion has occurred. Return true if the state of NEW_ENTRY_ENODE is sufficiently different - from PREV_ENTRY_ENODE to suggests that some variant is being modified, + from PREV_ENTRY_ENODE to suggest that some variant is being modified, and thus the recursion isn't infinite. Return false if the states are effectively the same, suggesting that @@ -459,64 +555,17 @@ sufficiently_different_p (exploded_node *new_entry_enode, gcc_assert (is_entrypoint_p (new_entry_enode)); gcc_assert (is_entrypoint_p (prev_entry_enode)); - const int new_stack_depth = new_entry_enode->get_stack_depth (); - /* Compare the stores of the two enodes. */ const region_model &new_model = *new_entry_enode->get_state ().m_region_model; - const region_model &prev_model - = *prev_entry_enode->get_state ().m_region_model; const store &new_store = *new_model.get_store (); for (auto kv : new_store) { const region *base_reg = kv.first; - - /* Get the value within the new frame. */ - const svalue *new_sval - = new_model.get_store_value (base_reg, NULL); - - /* If the value is UNKNOWN (e.g. due to hitting complexity limits) - assume that it differs from the previous value. */ - if (new_sval->get_kind () == SK_UNKNOWN) - return true; - - /* Get the equivalent value within the old enode. */ - const svalue *prev_sval; - - if (const frame_region *enclosing_frame - = base_reg->maybe_get_frame_region ()) - { - /* We have a binding within a frame in the new entry enode. */ - - /* Ignore bindings within frames below the new entry node. */ - if (enclosing_frame->get_stack_depth () < new_stack_depth) - continue; - - /* We have a binding within the frame of the new entry node, - presumably a parameter. */ - - /* Get the value within the equivalent frame of - the old entrypoint; typically will be the initial_svalue - of the parameter. */ - const frame_region *equiv_prev_frame - = prev_model.get_current_frame (); - const region *equiv_prev_base_reg - = remap_enclosing_frame (base_reg, - enclosing_frame, - equiv_prev_frame, - new_model.get_manager ()); - prev_sval = prev_model.get_store_value (equiv_prev_base_reg, NULL); - } - else - prev_sval = prev_model.get_store_value (base_reg, NULL); - - /* If the prev_sval is UNKNOWN (e.g. due to hitting complexity limits) - assume that it will differ from any new value. */ - if (prev_sval->get_kind () == SK_UNKNOWN) - return true; - - if (new_sval != prev_sval) + if (sufficiently_different_region_binding_p (new_entry_enode, + prev_entry_enode, + base_reg)) return true; } diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c new file mode 100644 index 00000000000..83efe9bb7e0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1.c @@ -0,0 +1,17 @@ +typedef struct { + unsigned idx; + int vals[512]; +} foo_t; + +int ended(foo_t* f) { + return f->idx >= 512; +} +unsigned foo(foo_t* f) { + if (ended(f)) { + return f->idx; + } + do { + f->idx++; + } while(!ended(f) && !f->vals[f->idx]); + return foo(f); /* { dg-bogus "infinite recursion" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c new file mode 100644 index 00000000000..b3c4920b10d --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-1a.c @@ -0,0 +1,17 @@ +typedef struct { + unsigned idx; + int vals[512]; +} foo_t; + +int ended(foo_t* f) { + return f->idx >= 512; +} +unsigned foo(foo_t* f) { + if (ended(f)) { + return f->idx; + } + do { + f->idx += 1000; + } while(!ended(f) && !f->vals[f->idx]); + return foo(f); /* { dg-bogus "infinite recursion" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c new file mode 100644 index 00000000000..c46f1f8012c --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/infinite-recursion-pr108935-2.c @@ -0,0 +1,18 @@ +typedef struct { + unsigned done; +} foo_t; + +unsigned foo(foo_t* f) { + if (f->done) { + return f->done; + } + f->done = 1; + return foo(f); /* { dg-bogus "infinite recursion" } */ +} + +int main() { + foo_t f = (foo_t){ + .done = 0, + }; + foo(&f); +}