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.133.124]) by sourceware.org (Postfix) with ESMTPS id C33C23858401 for ; Wed, 10 Aug 2022 16:10:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C33C23858401 Received: from mail-oa1-f72.google.com (mail-oa1-f72.google.com [209.85.160.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-312-9e_LMYIvP2ua9J6cSkjOZg-1; Wed, 10 Aug 2022 12:10:49 -0400 X-MC-Unique: 9e_LMYIvP2ua9J6cSkjOZg-1 Received: by mail-oa1-f72.google.com with SMTP id 586e51a60fabf-10e7cc69a90so3278126fac.6 for ; Wed, 10 Aug 2022 09:10:49 -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=j2WxeXMIqkzQINa2lukbuimygK5GP62GrdiM0Nsc8go=; b=2Fl/x7UT/H2tZ5td8zuwN3HdtdnGVb5o1qv8WvA+Kjb3TeqiZRi62lQXwWBVsnv1MG I3Z7OAD/9ZjHITGqH0gylkk+iiAoDhfGGJ2iNm6h2QJcsXvb1Y1ryaqZxetJxSacjDJY 1BSPlU0XLEf3zB+GaCDuRhJUrHaxcNk4It838cRgnpR1egk6yJL9+iuOw9v5MSzybqif SlLttUZym7/TUNr9BKvB1iicK6ncHaZwfpsCmqAABVazwR5M/yEips0bcqEL4ZFxw1Rq mcS6HEdpvGcBpOHOfzrIei5+hZbAYZXmx1cXmsd7N2RfHPLmQVwMPYzZLKEKOcyK4qgP 0fgA== X-Gm-Message-State: ACgBeo1+N7fYWHGgbRE941pcGvipuFtyRH1v79nXMgr6juFsqdSsQ11z 6kwLrumSSnUdI3ijchwIBpxvbVGtuat+f12yhZiJCgsVu7Y8F15QYM11q09Te36oVF3Z5FvjdzL parzvaSgF3cKRfqc7wuS7aHdU2gQNG8IKPg== X-Received: by 2002:a05:6808:f0f:b0:343:2e0e:ac52 with SMTP id m15-20020a0568080f0f00b003432e0eac52mr1581344oiw.36.1660147848711; Wed, 10 Aug 2022 09:10:48 -0700 (PDT) X-Google-Smtp-Source: AA6agR5+mhqvDtWrFTnElPaTGypqzy14mNjsPfprsyCRqx8ftLZEw0N8IBGwEc7jeIGpuRTUgV+JU5pB5SSbTFj2lwc= X-Received: by 2002:a05:6808:f0f:b0:343:2e0e:ac52 with SMTP id m15-20020a0568080f0f00b003432e0eac52mr1581322oiw.36.1660147848336; Wed, 10 Aug 2022 09:10:48 -0700 (PDT) MIME-Version: 1.0 References: <20220810130121.5591F13A7E@imap2.suse-dmz.suse.de> In-Reply-To: <20220810130121.5591F13A7E@imap2.suse-dmz.suse.de> From: Aldy Hernandez Date: Wed, 10 Aug 2022 18:10:36 +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.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_NONE, 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:10:52 -0000 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 >