From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 BB65A3857B98 for ; Wed, 10 Aug 2022 16:12:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BB65A3857B98 Received: from mail-oo1-f72.google.com (mail-oo1-f72.google.com [209.85.161.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-639-fPyzGafEPbSDxRS8qtPNBw-1; Wed, 10 Aug 2022 12:12:58 -0400 X-MC-Unique: fPyzGafEPbSDxRS8qtPNBw-1 Received: by mail-oo1-f72.google.com with SMTP id e10-20020a4a828a000000b004389399413cso7344896oog.16 for ; Wed, 10 Aug 2022 09:12:58 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc; bh=QTGvbV0Jyjg6FfjXovPv59DvJkQGKCOJUBYkIDaXfgg=; b=y0bmLOSo6dvTyuaisUKmuoHQmtFCl809Zkn0KZnboZHV5fqaa2vMEoFEREOovsXikm ZLPVV7gJqtV2etq8wkxLxxMzXyyvGOaHILvEiYpFk+X/bawk6y4urY5BV8EI+WAky4SA fe3hYCbB4tx80jPrrFOu7ts5Qr2TVx1hcw++32gjbA6/FZ6EHCPiGMwcMEFq5oe68S4w SZcaOX30yZbbiqODoNki9wg4ihIrrGu0ql2anvyU0hSH3PwA7n6Fl/R6pSkXnUdZo2M/ ePMWMZSYw0s8F+VXUTi/sJwOuSKS7QbBwnFoUnhfi1BPhmbOY3eqrq2wut669zexVUg8 u2uA== X-Gm-Message-State: ACgBeo12/NOqE2euXBPcS5veZq8ogMWCfmPSBC5M8tHjsRt+H4TH+ejc Gs8dhDe3XsBejeBlABzXktWBI9eoUWjIymbk5z1Tlar70tC2sgFhHmOMCS9s8soaBEzG7cSEYWG E3Pa/pZO3tyAvhmzJ3Y1nais2Y68jerUQ/w== X-Received: by 2002:a05:6808:14cb:b0:343:195e:d587 with SMTP id f11-20020a05680814cb00b00343195ed587mr1733779oiw.265.1660147977351; Wed, 10 Aug 2022 09:12:57 -0700 (PDT) X-Google-Smtp-Source: AA6agR7WEUEG4vBCVZ6JZByJUoYWVtQFyUTxYB/6/+lEeffud6YVPUxodQQx+tMXL1p1a0RxvddJAO6MCxrPLp8FM2k= X-Received: by 2002:a05:6808:14cb:b0:343:195e:d587 with SMTP id f11-20020a05680814cb00b00343195ed587mr1733769oiw.265.1660147977087; Wed, 10 Aug 2022 09:12:57 -0700 (PDT) MIME-Version: 1.0 References: <20220810130121.5591F13A7E@imap2.suse-dmz.suse.de> In-Reply-To: From: Aldy Hernandez Date: Wed, 10 Aug 2022 18:12:45 +0200 Message-ID: Subject: Re: [PATCH] Fix path query compute_imports for external path To: Richard Biener Cc: gcc-patches , "MacLeod, Andrew" X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-12.6 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, SPF_HELO_NONE, SPF_NONE, 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-List-Received-Date: Wed, 10 Aug 2022 16:13:01 -0000 Oh, and if it wasn't clear from an earlier message. I'm OK (and thankful) for everything you're doing in this space, especially if you stay on top of the threading counts from patch to patch, and you get your gori questions answered by Andrew ;-). No sense in you getting blocked, since you seem to be making good progress. Aldy On Wed, Aug 10, 2022 at 6:10 PM Aldy Hernandez wrote: > > Looks good to me. > > Thanks. > Aldy > > On Wed, Aug 10, 2022 at 3:01 PM Richard Biener wrote: > > > > 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); > > -- > > 2.35.3 > >