From patchwork Wed Aug 10 13:01:20 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 461 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:6a10:20da:b0:2d3:3019:e567 with SMTP id n26csp3151997pxc; Wed, 10 Aug 2022 06:02:08 -0700 (PDT) X-Google-Smtp-Source: AA6agR6WJB/QhKplWdwNymhEUYtGxzkDHOnk32gemo25A46arn1kpz3g08OKDEUa0iYylwMWC5Gb X-Received: by 2002:a05:6402:28ca:b0:43b:5235:f325 with SMTP id ef10-20020a05640228ca00b0043b5235f325mr25814877edb.320.1660136527875; Wed, 10 Aug 2022 06:02:07 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1660136527; cv=none; d=google.com; s=arc-20160816; b=JpfK+F6AxPTnfzoi0Tm4lelMV8L/D+d4UmVtcL+rSWeXFOU4CTMP7JBSdQGC9Bdgax GCNOtmt9n+1oKdXZJcKLmpuZC8Ujvbbsc8Ax76E+goHmR08NIUIdEGaNPTSTY+TuH32F t3MWrsVMuzXkREAX1ORMKYmLPTodqe6RuWXhOmAbn3dZvbqTB29vI7dpmkrAZFP5z7i2 WON17kXEu63ZEXR4c499wX8ly8lCUR13+CW7IUS36Up+kwgqMbEhwSfAP9i8TcAEz1TE Gpl9mQV9kYKmI0nbCOP23wn7N6VRgPbyKXVjt4Szyb2EVahyPcDGFIUfIzggrGAXePAI omZg== 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:message-id :mime-version:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=9GVYAD4Rx6dUq+KkKH4sUTU4QLT3amkKXVnTtr12c0o=; b=j36iMZHJoe8zPRL87ArYvfvp66nsQk3y9raPw9sYCIEsmXqOOE1lY5Tu16p2zM2tvw p9Sp+V1q8ez+XXF2wSQKhFOMYZGBYiVn2a1rmb25K6Yvsa5HoR1AJBvWJ2sLI6ppAipu wFM706XeFBkSvXq4RdattbnmtNak1xoUDWm3PE/jOQ6Gtc3S0z4vqNZIpazXRDtaKCEz ndtm4YCDehJ5Jkk1Fc+XMB6hA6z3d48hSjCMWsCwWGVcooMCEHH2IxDNalY3Jauj1tuN jbv6vRo4IOamYf9qQ4drKs9AbToeYztGTd8z/89/19IHEeewDLgyX8K32fErIn4vrHME QT9g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=cvRvQYpB; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id hr7-20020a1709073f8700b00732f74749d1si5005075ejc.911.2022.08.10.06.02.07 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 10 Aug 2022 06:02:07 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=cvRvQYpB; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 6E0D43858407 for ; Wed, 10 Aug 2022 13:02:06 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6E0D43858407 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1660136526; bh=9GVYAD4Rx6dUq+KkKH4sUTU4QLT3amkKXVnTtr12c0o=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=cvRvQYpBpv5FjGgBrd2WywLrr/Fl0co5YHIB8LIDCtgKu8x7io1FKuHbtB9B7QVe1 RhhXutqmZbg8GqH77gzzix3l0c/o/GMr3YHbD10jtFCX1yXpVQ75q/r/HbLekAKdgr pscfLag2DeL4GzYOVP2tghwHJo2f9HxYAyt6qUs8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 9C9CF3858D1E for ; Wed, 10 Aug 2022 13:01:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 9C9CF3858D1E Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 7715938232; Wed, 10 Aug 2022 13:01:21 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 5591F13A7E; Wed, 10 Aug 2022 13:01:21 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id K0mlEyGs82KyCgAAMHmgww (envelope-from ); Wed, 10 Aug 2022 13:01:21 +0000 Date: Wed, 10 Aug 2022 15:01:20 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Fix path query compute_imports for external path MIME-Version: 1.0 Message-Id: <20220810130121.5591F13A7E@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener 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?1740779319771043564?= X-GMAIL-MSGID: =?utf-8?q?1740779319771043564?= The following fixes the use of compute_imports from the backwards threader which ends up accessing stale m_path from a previous threading attempt. The fix is to pass in the path explicitely (and not the exit), and initializing it with the exit around this call from the backwards threader. That unfortunately exposed that we rely on this broken behavior as the new testcase shows. The missed threading can be restored by registering all relations from conditions on the path during solving, for the testcase the particular important case is for relations provided by the path entry conditional. I've verified that the GORI query for imported ranges on edges is not restricted this way. This regresses the new ssa-thread-19.c testcase which is exactly a case for the other patch re-doing how we compute imports since this misses imports for defs that are not on the dominating path from the exit. That's one of the cases this regresses (it also progresses a few due to more or the correct relations added). Overall it reduces the number of threads from 98649 to 98620 on my set of cc1files. I think it's a reasonable intermediate step to find a stable, less random ground to compare stats to. Bootstrapped and tested on x86_64-unknown-linux-gnu. OK? Thanks, Richard. * gimple-range-path.h (path_range_query::compute_imports): Take path as argument, not the exit block. * gimple-range-path.cc (path_range_query::compute_imports): Likewise, and adjust, avoiding possibly stale m_path. (path_range_query::compute_outgoing_relations): Register relations for all conditionals. * tree-ssa-threadbackward.cc (back_threader::find_paths): Adjust. * gcc.dg/tree-ssa/ssa-thread-18.c: New testcase. * gcc.dg/tree-ssa/ssa-thread-19.c: Likewise, but XFAILed. --- gcc/gimple-range-path.cc | 21 +++++------- gcc/gimple-range-path.h | 2 +- gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c | 20 +++++++++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c | 33 +++++++++++++++++++ gcc/tree-ssa-threadbackward.cc | 4 ++- 5 files changed, 65 insertions(+), 15 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index 43e7526b6fc..389faec260c 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -549,7 +549,7 @@ path_range_query::add_to_imports (tree name, bitmap imports) return false; } -// Compute the imports to the path ending in EXIT. These are +// Compute the imports to PATH. These are // essentially the SSA names used to calculate the final conditional // along the path. // @@ -559,9 +559,10 @@ path_range_query::add_to_imports (tree name, bitmap imports) // we can solve. void -path_range_query::compute_imports (bitmap imports, basic_block exit) +path_range_query::compute_imports (bitmap imports, const vec &path) { // Start with the imports from the exit block... + basic_block exit = path[0]; gori_compute &gori = m_ranger->gori (); bitmap r_imports = gori.imports (exit); bitmap_copy (imports, r_imports); @@ -599,7 +600,7 @@ path_range_query::compute_imports (bitmap imports, basic_block exit) tree arg = gimple_phi_arg (phi, i)->def; if (TREE_CODE (arg) == SSA_NAME - && m_path.contains (e->src) + && path.contains (e->src) && bitmap_set_bit (imports, SSA_NAME_VERSION (arg))) worklist.safe_push (arg); } @@ -607,9 +608,9 @@ path_range_query::compute_imports (bitmap imports, basic_block exit) } // Exported booleans along the path, may help conditionals. if (m_resolve) - for (i = 0; i < m_path.length (); ++i) + for (i = 0; i < path.length (); ++i) { - basic_block bb = m_path[i]; + basic_block bb = path[i]; tree name; FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) @@ -636,7 +637,7 @@ path_range_query::compute_ranges (const vec &path, if (imports) bitmap_copy (m_imports, imports); else - compute_imports (m_imports, exit_bb ()); + compute_imports (m_imports, m_path); if (m_resolve) get_path_oracle ()->reset_path (); @@ -845,15 +846,9 @@ path_range_query::compute_phi_relations (basic_block bb, basic_block prev) void path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) { - gimple *stmt = last_stmt (bb); - - if (stmt - && gimple_code (stmt) == GIMPLE_COND - && (import_p (gimple_cond_lhs (stmt)) - || import_p (gimple_cond_rhs (stmt)))) + if (gcond *cond = safe_dyn_cast (last_stmt (bb))) { int_range<2> r; - gcond *cond = as_a (stmt); edge e0 = EDGE_SUCC (bb, 0); edge e1 = EDGE_SUCC (bb, 1); diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index 2c4624e4cef..e783e00b2f5 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -37,7 +37,7 @@ public: void compute_ranges (const vec &, const bitmap_head *imports = NULL); void compute_ranges (edge e); - void compute_imports (bitmap imports, basic_block exit); + void compute_imports (bitmap imports, const vec &); bool range_of_expr (vrange &r, tree name, gimple * = NULL) override; bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override; bool unreachable_path_p (); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c new file mode 100644 index 00000000000..a899f4f3fc0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-18.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-threadfull1-stats" } */ + +void foo (int nest, int print_nest) +{ + _Bool t0 = nest != 0; + _Bool t1 = nest == print_nest; + _Bool t2 = t0 & t1; + if (t2) + __builtin_puts ("x"); + nest++; + if (nest > 2) + __builtin_abort (); + if (print_nest == nest) + __builtin_puts ("y"); +} + +/* We should be able to thread (t2) to !(print_nest == nest) using the + nest == print_nest relation implied by the entry block. */ +/* { dg-final { scan-tree-dump "Jumps threaded: 1" "threadfull1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c new file mode 100644 index 00000000000..58a872b8d25 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-19.c @@ -0,0 +1,33 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-threadfull1-stats" } */ + +struct S; +struct S { struct S *next; }; +int foo (struct S *chain, _Bool is_ctor, _Bool is_dtor) +{ + int num_args = 0; + if (chain) /* A */ + { + do { + num_args++; + chain = chain->next; + if (!chain) + break; + } while (1); + } + if (is_ctor) + num_args++; /* B */ + if (is_dtor) + num_args++; + else + { + if (num_args > 2) /* C */ + __builtin_puts ("x"); + } + return num_args; +} + +/* We want to thread both paths from A with NULL chain to C, the one through + B and one around it. + ??? Ideally we'd thread one "path" containing the half-diamond with B. */ +/* { dg-final { scan-tree-dump "Jumps threaded: 2" "threadfull1" { xfail *-*-* } } } */ diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc index 30047c654fb..6585a30551d 100644 --- a/gcc/tree-ssa-threadbackward.cc +++ b/gcc/tree-ssa-threadbackward.cc @@ -451,7 +451,9 @@ back_threader::find_paths (basic_block bb, tree name) m_visited_bbs.empty (); m_path.truncate (0); m_name = name; - m_solver->compute_imports (m_imports, bb); + m_path.safe_push (bb); + m_solver->compute_imports (m_imports, m_path); + m_path.pop (); auto_bitmap interesting; bitmap_copy (interesting, m_imports);