Message ID | 20220817115848.512165-1-aldyh@redhat.com |
---|---|
State | New |
Headers |
Return-Path: <gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org> X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 59EB8385842F for <patchwork@sourceware.org>; Wed, 17 Aug 2022 11:59:35 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 59EB8385842F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1660737575; bh=fh/e8MFop/zqJ4/RBccozgJhorsRAyL1jKX9Ptea+ko=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=LNqKeOAfgXL92c6PXhqOOikT6PHeKJZwiTESGuddlcyWPVk4tXiEvYekQyRZ6WaSB +eYpraaFLjklCR5NELEF1T0Qw3dxZU7D5CTdtlq3hK2zDSGat/FM/mkR2LvLXFXo2u PW6+wk9y26Yq10/1+ArmLL1+p0hFcsq3hxhFaJl4= 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 06EF63858D1E for <gcc-patches@gcc.gnu.org>; Wed, 17 Aug 2022 11:59:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 06EF63858D1E Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-441-ASld8oMJNGiaLDNnCh7t3w-1; Wed, 17 Aug 2022 07:58:59 -0400 X-MC-Unique: ASld8oMJNGiaLDNnCh7t3w-1 Received: from smtp.corp.redhat.com (int-mx09.intmail.prod.int.rdu2.redhat.com [10.11.54.9]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id B2BFF1011353; Wed, 17 Aug 2022 11:58:58 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.193.107]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 04091492CA5; Wed, 17 Aug 2022 11:58:56 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.17.1/8.17.1) with ESMTPS id 27HBwshK512179 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Wed, 17 Aug 2022 13:58:54 +0200 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 27HBwsx3512178; Wed, 17 Aug 2022 13:58:54 +0200 To: Richard Biener <richard.guenther@gmail.com> Subject: [PATCH] Make path_range_query standalone and add reset_path. Date: Wed, 17 Aug 2022 13:58:48 +0200 Message-Id: <20220817115848.512165-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.85 on 10.11.54.9 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true 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_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 <gcc-patches.gcc.gnu.org> List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe> List-Archive: <https://gcc.gnu.org/pipermail/gcc-patches/> List-Post: <mailto:gcc-patches@gcc.gnu.org> List-Help: <mailto:gcc-patches-request@gcc.gnu.org?subject=help> List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe> From: Aldy Hernandez via Gcc-patches <gcc-patches@gcc.gnu.org> Reply-To: Aldy Hernandez <aldyh@redhat.com> Cc: GCC patches <gcc-patches@gcc.gnu.org> Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" <gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org> |
Series |
Make path_range_query standalone and add reset_path.
|
|
Commit Message
Aldy Hernandez
Aug. 17, 2022, 11:58 a.m. UTC
These are a bunch of cleanups inspired by Richi's suggestion of making path_range_query standalone, instead of having to call compute_ranges() for each path. I've made the ranger need explicit, and moved the responsibility for its creation to the caller. I've also investigated and documented why the forward threader needs its own compute exit dependencies variant. I can't wait for it to go away :-/. I've also added constructors that take a path and dependencies, and made compute_ranges() private. Unfortunately, reinstantiating path_range_query in the forward threader caused a 14% performance regression in DOM, because the old threader calls it over and over on the same path to simplify statements (some of which not even in the IL, but that's old news). In the meantime, I've left the ability to reset a path, but this time appropriately called reset_path(). I've moved the verify_marked_backedges call to the threader. Is this ok? Interestingly, comparing the thread counts for the patch yielded more threads. I narrowed this down to a bug in the path oracle reset code that's not cleaning things up as expected. I'll fix that before committing this, but figured I'd post for comments in the meantime. Thoughts? gcc/ChangeLog: * gimple-range-path.cc (path_range_query::path_range_query): Add various constructors to take a path. (path_range_query::~path_range_query): Remove m_alloced_ranger. (path_range_query::range_on_path_entry): Adjust for m_ranger being a reference. (path_range_query::set_path): Rename to... (path_range_query::reset_path): ...this and call compute_ranges. (path_range_query::ssa_range_in_phi): Adjust for m_ranger reference. (path_range_query::range_defined_in_block): Same. (path_range_query::compute_ranges_in_block): Same. (path_range_query::adjust_for_non_null_uses): Same. (path_range_query::compute_exit_dependencies): Use m_path instead of argument. (path_range_query::compute_ranges): Remove path argument. (path_range_query::range_of_stmt): Adjust for m_ranger reference. (path_range_query::compute_outgoing_relations): Same. * gimple-range-path.h (class path_range_query): Add various constructors. Make compute_ranges and compute_exit_dependencies private. Rename set_path to reset_path. Make m_ranger a reference. Remove m_alloced_ranger. * tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to path_range_query. * tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a ranger and instantiate a new path_range_query every time. (ch_base::copy_headers): Pass ranger instead of path_range_query. * tree-ssa-threadbackward.cc (class back_threader): Remove m_solver. (back_threader::~back_threader): Remove m_solver. (back_threader::find_taken_edge_switch): Adjust for m_ranger reference. (back_threader::find_taken_edge_cond): Same. (back_threader::dump): Remove m_solver. (back_threader::back_threader): Move verify_marked_backedges here from the path_range_query constructor. * tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move some code from compute_ranges_from_state here. (hybrid_jt_simplifier::compute_ranges_from_state): Rename... (hybrid_jt_simplifier::compute_exit_dependencies): ...to this. * tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename compute_ranges_from_state to compute_exit_dependencies. Remove m_path. --- gcc/gimple-range-path.cc | 112 +++++++++++++++++---------------- gcc/gimple-range-path.h | 22 +++---- gcc/tree-ssa-dom.cc | 2 +- gcc/tree-ssa-loop-ch.cc | 12 ++-- gcc/tree-ssa-threadbackward.cc | 27 ++++---- gcc/tree-ssa-threadedge.cc | 30 +++++---- gcc/tree-ssa-threadedge.h | 5 +- 7 files changed, 111 insertions(+), 99 deletions(-)
Comments
FWIW, here is a rebased version with the latest trunk. There are no regressions, or differences in threading counts, and the performance change is negligible. Aldy On Wed, Aug 17, 2022 at 1:59 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > These are a bunch of cleanups inspired by Richi's suggestion of making > path_range_query standalone, instead of having to call > compute_ranges() for each path. > > I've made the ranger need explicit, and moved the responsibility for > its creation to the caller. > > I've also investigated and documented why the forward threader needs its > own compute exit dependencies variant. I can't wait for it to go away > :-/. > > I've also added constructors that take a path and dependencies, and > made compute_ranges() private. Unfortunately, reinstantiating > path_range_query in the forward threader caused a 14% performance > regression in DOM, because the old threader calls it over and over on > the same path to simplify statements (some of which not even in the > IL, but that's old news). > > In the meantime, I've left the ability to reset a path, but this time > appropriately called reset_path(). > > I've moved the verify_marked_backedges call to the threader. Is this > ok? > > Interestingly, comparing the thread counts for the patch yielded more > threads. I narrowed this down to a bug in the path oracle reset code > that's not cleaning things up as expected. I'll fix that before > committing this, but figured I'd post for comments in the meantime. > > Thoughts? > > gcc/ChangeLog: > > * gimple-range-path.cc (path_range_query::path_range_query): Add > various constructors to take a path. > (path_range_query::~path_range_query): Remove m_alloced_ranger. > (path_range_query::range_on_path_entry): Adjust for m_ranger being > a reference. > (path_range_query::set_path): Rename to... > (path_range_query::reset_path): ...this and call compute_ranges. > (path_range_query::ssa_range_in_phi): Adjust for m_ranger > reference. > (path_range_query::range_defined_in_block): Same. > (path_range_query::compute_ranges_in_block): Same. > (path_range_query::adjust_for_non_null_uses): Same. > (path_range_query::compute_exit_dependencies): Use m_path instead > of argument. > (path_range_query::compute_ranges): Remove path argument. > (path_range_query::range_of_stmt): Adjust for m_ranger reference. > (path_range_query::compute_outgoing_relations): Same. > * gimple-range-path.h (class path_range_query): Add various > constructors. > Make compute_ranges and compute_exit_dependencies private. > Rename set_path to reset_path. > Make m_ranger a reference. > Remove m_alloced_ranger. > * tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to > path_range_query. > * tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a > ranger and instantiate a new path_range_query every time. > (ch_base::copy_headers): Pass ranger instead of path_range_query. > * tree-ssa-threadbackward.cc (class back_threader): Remove m_solver. > (back_threader::~back_threader): Remove m_solver. > (back_threader::find_taken_edge_switch): Adjust for m_ranger > reference. > (back_threader::find_taken_edge_cond): Same. > (back_threader::dump): Remove m_solver. > (back_threader::back_threader): Move verify_marked_backedges > here from the path_range_query constructor. > * tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move > some code from compute_ranges_from_state here. > (hybrid_jt_simplifier::compute_ranges_from_state): Rename... > (hybrid_jt_simplifier::compute_exit_dependencies): ...to this. > * tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename > compute_ranges_from_state to compute_exit_dependencies. > Remove m_path. > --- > gcc/gimple-range-path.cc | 112 +++++++++++++++++---------------- > gcc/gimple-range-path.h | 22 +++---- > gcc/tree-ssa-dom.cc | 2 +- > gcc/tree-ssa-loop-ch.cc | 12 ++-- > gcc/tree-ssa-threadbackward.cc | 27 ++++---- > gcc/tree-ssa-threadedge.cc | 30 +++++---- > gcc/tree-ssa-threadedge.h | 5 +- > 7 files changed, 111 insertions(+), 99 deletions(-) > > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc > index c99d77dd340..d37605f4539 100644 > --- a/gcc/gimple-range-path.cc > +++ b/gcc/gimple-range-path.cc > @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see > // Internal construct to help facilitate debugging of solver. > #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) > > -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) > +path_range_query::path_range_query (gimple_ranger &ranger, > + const vec<basic_block> &path, > + const bitmap_head *dependencies, > + bool resolve) > : m_cache (new ssa_global_cache), > m_has_cache_entry (BITMAP_ALLOC (NULL)), > - m_resolve (resolve), > - m_alloced_ranger (!ranger) > + m_ranger (ranger), > + m_resolve (resolve) > { > - if (m_alloced_ranger) > - m_ranger = new gimple_ranger; > - else > - m_ranger = ranger; > + m_oracle = new path_oracle (m_ranger.oracle ()); > + > + reset_path (path, dependencies); > +} > > - m_oracle = new path_oracle (m_ranger->oracle ()); > +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) > + : m_cache (new ssa_global_cache), > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > + m_ranger (ranger), > + m_resolve (resolve) > +{ > + m_oracle = new path_oracle (m_ranger.oracle ()); > +} > > - if (m_resolve && flag_checking) > - verify_marked_backedges (cfun); > +path_range_query::path_range_query (gimple_ranger &ranger, > + edge e, > + bool resolve) > + : m_cache (new ssa_global_cache), > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > + m_ranger (ranger), > + m_resolve (resolve) > +{ > + m_oracle = new path_oracle (m_ranger.oracle ()); > + auto_vec<basic_block> bbs (2); > + bbs.quick_push (e->dest); > + bbs.quick_push (e->src); > + reset_path (bbs, NULL); > } > > path_range_query::~path_range_query () > { > delete m_oracle; > - if (m_alloced_ranger) > - delete m_ranger; > BITMAP_FREE (m_has_cache_entry); > delete m_cache; > } > > -// Return TRUE if NAME is an exit depenency for the path. > +// Return TRUE if NAME is an exit dependency for the path. > > bool > path_range_query::exit_dependency_p (tree name) > @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) > { > gcc_checking_assert (defined_outside_path (name)); > basic_block entry = entry_bb (); > - m_ranger->range_on_entry (r, entry, name); > + m_ranger.range_on_entry (r, entry, name); > } > > // Return the range of NAME at the end of the path being analyzed. > @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () > return m_undefined_path; > } > > -// Initialize the current path to PATH. The current block is set to > -// the entry block to the path. > -// > -// Note that the blocks are in reverse order, so the exit block is > -// path[0]. > +// Reset the current path to PATH. > > void > -path_range_query::set_path (const vec<basic_block> &path) > +path_range_query::reset_path (const vec<basic_block> &path, > + const bitmap_head *dependencies) > { > gcc_checking_assert (path.length () > 1); > m_path = path.copy (); > m_pos = m_path.length () - 1; > + m_undefined_path = false; > bitmap_clear (m_has_cache_entry); > + > + compute_ranges (dependencies); > } > > bool > @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > if (at_entry ()) > { > - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) > + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) > return; > > // Try to fold the phi exclusively with global or cached values. > @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > range_on_path_entry (r, arg); > else > r.set_varying (TREE_TYPE (name)); > - m_ranger->range_on_edge (tmp, e_in, arg); > + m_ranger.range_on_edge (tmp, e_in, arg); > r.intersect (tmp); > return; > } > @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) > } > > if (bb && POINTER_TYPE_P (TREE_TYPE (name))) > - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); > + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); > > if (DEBUG_SOLVER && (bb || !r.varying_p ())) > { > @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) > p->set_root_oracle (nullptr); > } > > - gori_compute &g = m_ranger->gori (); > + gori_compute &g = m_ranger.gori (); > bitmap exports = g.exports (bb); > EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) > { > @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) > else > r.set_varying (TREE_TYPE (name)); > > - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) > + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) > set_cache (r, name); > } > } > @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) > // SSA names used to calculate the final conditional along the path. > > void > -path_range_query::compute_exit_dependencies (bitmap dependencies, > - const vec<basic_block> &path) > +path_range_query::compute_exit_dependencies (bitmap dependencies) > { > // Start with the imports from the exit block... > - basic_block exit = path[0]; > - gori_compute &gori = m_ranger->gori (); > + basic_block exit = m_path[0]; > + gori_compute &gori = m_ranger.gori (); > bitmap_copy (dependencies, gori.imports (exit)); > > auto_vec<tree> worklist (bitmap_count_bits (dependencies)); > @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > tree name = worklist.pop (); > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > if (SSA_NAME_IS_DEFAULT_DEF (name) > - || !path.contains (gimple_bb (def_stmt))) > + || !m_path.contains (gimple_bb (def_stmt))) > continue; > > if (gphi *phi = dyn_cast <gphi *> (def_stmt)) > @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > tree arg = gimple_phi_arg (phi, i)->def; > > if (TREE_CODE (arg) == SSA_NAME > - && path.contains (e->src) > + && m_path.contains (e->src) > && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) > worklist.safe_push (arg); > } > @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > } > // Exported booleans along the path, may help conditionals. > if (m_resolve) > - for (i = 0; i < path.length (); ++i) > + for (i = 0; i < m_path.length (); ++i) > { > - basic_block bb = path[i]; > + basic_block bb = m_path[i]; > tree name; > FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) > if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) > @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > // calculated from the final conditional in the path. > > void > -path_range_query::compute_ranges (const vec<basic_block> &path, > - const bitmap_head *dependencies) > +path_range_query::compute_ranges (const bitmap_head *dependencies) > { > if (DEBUG_SOLVER) > fprintf (dump_file, "\n==============================================\n"); > > - set_path (path); > - m_undefined_path = false; > - > if (dependencies) > bitmap_copy (m_exit_dependencies, dependencies); > else > - compute_exit_dependencies (m_exit_dependencies, m_path); > + compute_exit_dependencies (m_exit_dependencies); > > if (m_resolve) > get_path_oracle ()->reset_path (); > @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > if (DEBUG_SOLVER) > { > fprintf (dump_file, "path_range_query: compute_ranges for path: "); > - for (unsigned i = path.length (); i > 0; --i) > + for (unsigned i = m_path.length (); i > 0; --i) > { > - basic_block bb = path[i - 1]; > + basic_block bb = m_path[i - 1]; > fprintf (dump_file, "%d", bb->index); > if (i > 1) > fprintf (dump_file, "->"); > @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > } > } > > -// Convenience function to compute ranges along a path consisting of > -// E->SRC and E->DEST. > - > -void > -path_range_query::compute_ranges (edge e) > -{ > - auto_vec<basic_block> bbs (2); > - bbs.quick_push (e->dest); > - bbs.quick_push (e->src); > - compute_ranges (bbs); > -} > - > // A folding aid used to register and query relations along a path. > // When queried, it returns relations as they would appear on exit to > // the path. > @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) > if (m_resolve) > { > fold_using_range f; > - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); > + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); > if (!f.fold_stmt (r, stmt, src)) > r.set_varying (type); > } > @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) > else > gcc_unreachable (); > > - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); > + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); > src.register_outgoing_edges (cond, r, e0, e1); > } > } > diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h > index 3cb794e34a9..483fde0d431 100644 > --- a/gcc/gimple-range-path.h > +++ b/gcc/gimple-range-path.h > @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see > class path_range_query : public range_query > { > public: > - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); > + path_range_query (class gimple_ranger &ranger, > + const vec<basic_block> &path, > + const bitmap_head *dependencies = NULL, > + bool resolve = true); > + path_range_query (gimple_ranger &ranger, bool resolve = true); > + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); > virtual ~path_range_query (); > - void compute_ranges (const vec<basic_block> &, > - const bitmap_head *dependencies = NULL); > - void compute_ranges (edge e); > - void compute_exit_dependencies (bitmap dependencies, > - const vec<basic_block> &); > + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); > 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 (); > @@ -47,6 +48,8 @@ public: > > private: > bool internal_range_of_expr (vrange &r, tree name, gimple *); > + void compute_ranges (const bitmap_head *dependencies); > + void compute_exit_dependencies (bitmap_head *dependencies); > bool defined_outside_path (tree name); > void range_on_path_entry (vrange &r, tree name); > path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } > @@ -71,7 +74,6 @@ private: > bool relations_may_be_invalidated (edge); > > // Path navigation. > - void set_path (const vec<basic_block> &); > basic_block entry_bb () { return m_path[m_path.length () - 1]; } > basic_block exit_bb () { return m_path[0]; } > basic_block curr_bb () { return m_path[m_pos]; } > @@ -99,7 +101,7 @@ private: > > // A ranger used to resolve ranges for SSA names whose values come > // from outside the path. > - gimple_ranger *m_ranger; > + gimple_ranger &m_ranger; > > // Current path position. > unsigned m_pos; > @@ -109,10 +111,6 @@ private: > > // Set if there were any undefined expressions while pre-calculating path. > bool m_undefined_path; > - > - // True if m_ranger was allocated in this class and must be freed at > - // destruction. > - bool m_alloced_ranger; > }; > > #endif // GCC_TREE_SSA_THREADSOLVER_H > diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc > index 44dc27b464c..513e0c88254 100644 > --- a/gcc/tree-ssa-dom.cc > +++ b/gcc/tree-ssa-dom.cc > @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) > > /* Recursively walk the dominator tree optimizing statements. */ > gimple_ranger *ranger = enable_ranger (fun); > - path_range_query path_query (/*resolve=*/true, ranger); > + path_range_query path_query (*ranger); > dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); > dom_jt_state state (const_and_copies, avail_exprs_stack); > jump_threader threader (&simplifier, &state); > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc > index 3b91a89eaf5..96816b89287 100644 > --- a/gcc/tree-ssa-loop-ch.cc > +++ b/gcc/tree-ssa-loop-ch.cc > @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see > be statically determined. */ > > static bool > -entry_loop_condition_is_static (class loop *l, path_range_query *query) > +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) > { > edge e = loop_preheader_edge (l); > gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); > @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) > desired_static_value = boolean_true_node; > > int_range<2> r; > - query->compute_ranges (e); > - query->range_of_stmt (r, last); > + path_range_query query (*ranger, e); > + query.range_of_stmt (r, last); > return r == int_range<2> (desired_static_value, desired_static_value); > } > > @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) > auto_vec<std::pair<edge, loop_p> > copied; > > mark_dfs_back_edges (); > - path_range_query *query = new path_range_query; > + gimple_ranger *ranger = new gimple_ranger; > for (auto loop : loops_list (cfun, 0)) > { > int initial_limit = param_max_loop_header_insns; > @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) > iteration. */ > if (optimize_loop_for_size_p (loop) > && !loop->force_vectorize > - && !entry_loop_condition_is_static (loop, query)) > + && !entry_loop_condition_is_static (loop, ranger)) > { > if (dump_file && (dump_flags & TDF_DETAILS)) > fprintf (dump_file, > @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) > candidates.safe_push (loop); > } > /* Do not use ranger after we change the IL and not have updated SSA. */ > - delete query; > + delete ranger; > > for (auto loop : candidates) > { > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc > index b886027fccf..22748b9ec08 100644 > --- a/gcc/tree-ssa-threadbackward.cc > +++ b/gcc/tree-ssa-threadbackward.cc > @@ -99,7 +99,6 @@ private: > > back_threader_registry m_registry; > back_threader_profitability m_profit; > - path_range_query *m_solver; > > // Current path being analyzed. > auto_vec<basic_block> m_path; > @@ -119,6 +118,8 @@ private: > // with the ranger. Otherwise, unknown SSA names are assumed to be > // VARYING. Setting to true is more precise but slower. > function *m_fun; > + // Ranger for the path solver. > + gimple_ranger *m_ranger; > unsigned m_flags; > // Set to TRUE for the first of each thread[12] pass or the first of > // each threadfull[12] pass. This is used to differentiate between > @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) > > // The path solver needs EDGE_DFS_BACK in resolving mode. > if (flags & BT_RESOLVE) > - mark_dfs_back_edges (); > - m_solver = new path_range_query (flags & BT_RESOLVE); > + { > + mark_dfs_back_edges (); > + > + if (flag_checking) > + verify_marked_backedges (fun); > + } > + > + m_ranger = new gimple_ranger; > } > > back_threader::~back_threader () > { > - delete m_solver; > - > + delete m_ranger; > loop_optimizer_finalize (); > } > > @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, > tree name = gimple_switch_index (sw); > int_range_max r; > > - m_solver->compute_ranges (path, m_imports); > - m_solver->range_of_expr (r, name, sw); > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > + solver.range_of_expr (r, name, sw); > > if (r.undefined_p ()) > return UNREACHABLE_EDGE; > @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, > { > int_range_max r; > > - m_solver->compute_ranges (path, m_imports); > - m_solver->range_of_stmt (r, cond); > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > + solver.range_of_stmt (r, cond); > > - if (m_solver->unreachable_path_p ()) > + if (solver.unreachable_path_p ()) > return UNREACHABLE_EDGE; > > int_range<2> true_range (boolean_true_node, boolean_true_node); > @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) > void > back_threader::dump (FILE *out) > { > - m_solver->dump (out); > fprintf (out, "\nCandidates for pre-computation:\n"); > fprintf (out, "===================================\n"); > > diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc > index e64e4f209f7..905a98c8c68 100644 > --- a/gcc/tree-ssa-threadedge.cc > +++ b/gcc/tree-ssa-threadedge.cc > @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, > > // Hybrid threader implementation. > > - > hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, > path_range_query *q) > { > @@ -1411,7 +1410,12 @@ tree > hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > jt_state *state) > { > - compute_ranges_from_state (stmt, state); > + auto_bitmap dependencies; > + auto_vec<basic_block> path; > + > + state->get_path (path); > + compute_exit_dependencies (dependencies, path, stmt); > + m_query->reset_path (path, dependencies); > > if (gimple_code (stmt) == GIMPLE_COND > || gimple_code (stmt) == GIMPLE_ASSIGN) > @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > return NULL; > } > > -// Use STATE to generate the list of imports needed for the solver, > -// and calculate the ranges along the path. > +// Calculate the set of exit dependencies for a path and statement to > +// be simplified. This is different than the > +// compute_exit_dependencies in the path solver because the forward > +// threader asks questions about statements not necessarily in the > +// path. Using the default compute_exit_dependencies in the path > +// solver gets noticeably less threads. > > void > -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, > + const vec<basic_block> &path, > + gimple *stmt) > { > - auto_bitmap imports; > gori_compute &gori = m_ranger->gori (); > > - state->get_path (m_path); > - > // Start with the imports to the final conditional. > - bitmap_copy (imports, gori.imports (m_path[0])); > + bitmap_copy (dependencies, gori.imports (path[0])); > > // Add any other interesting operands we may have missed. > - if (gimple_bb (stmt) != m_path[0]) > + if (gimple_bb (stmt) != path[0]) > { > for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) > { > @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > if (op > && TREE_CODE (op) == SSA_NAME > && Value_Range::supports_type_p (TREE_TYPE (op))) > - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); > + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); > } > } > - m_query->compute_ranges (m_path, imports); > } > diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h > index ca70b33f5ed..790ac2ea538 100644 > --- a/gcc/tree-ssa-threadedge.h > +++ b/gcc/tree-ssa-threadedge.h > @@ -69,11 +69,12 @@ public: > tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; > > private: > - void compute_ranges_from_state (gimple *stmt, jt_state *); > + void compute_exit_dependencies (bitmap dependencies, > + const vec<basic_block> &path, > + gimple *stmt); > > gimple_ranger *m_ranger; > path_range_query *m_query; > - auto_vec<basic_block> m_path; > }; > > // This is the high level threader. The entry point is > -- > 2.37.1 >
On Thu, Aug 18, 2022 at 9:58 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > FWIW, here is a rebased version with the latest trunk. > > There are no regressions, or differences in threading counts, and the > performance change is negligible. + { + mark_dfs_back_edges (); + + if (flag_checking) + verify_marked_backedges (fun); that looks redundant. Otherwise looks good - it might be possible to get rid of the reset_path use as well? Richard. > Aldy > > On Wed, Aug 17, 2022 at 1:59 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > These are a bunch of cleanups inspired by Richi's suggestion of making > > path_range_query standalone, instead of having to call > > compute_ranges() for each path. > > > > I've made the ranger need explicit, and moved the responsibility for > > its creation to the caller. > > > > I've also investigated and documented why the forward threader needs its > > own compute exit dependencies variant. I can't wait for it to go away > > :-/. > > > > I've also added constructors that take a path and dependencies, and > > made compute_ranges() private. Unfortunately, reinstantiating > > path_range_query in the forward threader caused a 14% performance > > regression in DOM, because the old threader calls it over and over on > > the same path to simplify statements (some of which not even in the > > IL, but that's old news). > > > > In the meantime, I've left the ability to reset a path, but this time > > appropriately called reset_path(). > > > > I've moved the verify_marked_backedges call to the threader. Is this > > ok? > > > > Interestingly, comparing the thread counts for the patch yielded more > > threads. I narrowed this down to a bug in the path oracle reset code > > that's not cleaning things up as expected. I'll fix that before > > committing this, but figured I'd post for comments in the meantime. > > > > Thoughts? > > > > gcc/ChangeLog: > > > > * gimple-range-path.cc (path_range_query::path_range_query): Add > > various constructors to take a path. > > (path_range_query::~path_range_query): Remove m_alloced_ranger. > > (path_range_query::range_on_path_entry): Adjust for m_ranger being > > a reference. > > (path_range_query::set_path): Rename to... > > (path_range_query::reset_path): ...this and call compute_ranges. > > (path_range_query::ssa_range_in_phi): Adjust for m_ranger > > reference. > > (path_range_query::range_defined_in_block): Same. > > (path_range_query::compute_ranges_in_block): Same. > > (path_range_query::adjust_for_non_null_uses): Same. > > (path_range_query::compute_exit_dependencies): Use m_path instead > > of argument. > > (path_range_query::compute_ranges): Remove path argument. > > (path_range_query::range_of_stmt): Adjust for m_ranger reference. > > (path_range_query::compute_outgoing_relations): Same. > > * gimple-range-path.h (class path_range_query): Add various > > constructors. > > Make compute_ranges and compute_exit_dependencies private. > > Rename set_path to reset_path. > > Make m_ranger a reference. > > Remove m_alloced_ranger. > > * tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to > > path_range_query. > > * tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a > > ranger and instantiate a new path_range_query every time. > > (ch_base::copy_headers): Pass ranger instead of path_range_query. > > * tree-ssa-threadbackward.cc (class back_threader): Remove m_solver. > > (back_threader::~back_threader): Remove m_solver. > > (back_threader::find_taken_edge_switch): Adjust for m_ranger > > reference. > > (back_threader::find_taken_edge_cond): Same. > > (back_threader::dump): Remove m_solver. > > (back_threader::back_threader): Move verify_marked_backedges > > here from the path_range_query constructor. > > * tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move > > some code from compute_ranges_from_state here. > > (hybrid_jt_simplifier::compute_ranges_from_state): Rename... > > (hybrid_jt_simplifier::compute_exit_dependencies): ...to this. > > * tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename > > compute_ranges_from_state to compute_exit_dependencies. > > Remove m_path. > > --- > > gcc/gimple-range-path.cc | 112 +++++++++++++++++---------------- > > gcc/gimple-range-path.h | 22 +++---- > > gcc/tree-ssa-dom.cc | 2 +- > > gcc/tree-ssa-loop-ch.cc | 12 ++-- > > gcc/tree-ssa-threadbackward.cc | 27 ++++---- > > gcc/tree-ssa-threadedge.cc | 30 +++++---- > > gcc/tree-ssa-threadedge.h | 5 +- > > 7 files changed, 111 insertions(+), 99 deletions(-) > > > > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc > > index c99d77dd340..d37605f4539 100644 > > --- a/gcc/gimple-range-path.cc > > +++ b/gcc/gimple-range-path.cc > > @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see > > // Internal construct to help facilitate debugging of solver. > > #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) > > > > -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) > > +path_range_query::path_range_query (gimple_ranger &ranger, > > + const vec<basic_block> &path, > > + const bitmap_head *dependencies, > > + bool resolve) > > : m_cache (new ssa_global_cache), > > m_has_cache_entry (BITMAP_ALLOC (NULL)), > > - m_resolve (resolve), > > - m_alloced_ranger (!ranger) > > + m_ranger (ranger), > > + m_resolve (resolve) > > { > > - if (m_alloced_ranger) > > - m_ranger = new gimple_ranger; > > - else > > - m_ranger = ranger; > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > + > > + reset_path (path, dependencies); > > +} > > > > - m_oracle = new path_oracle (m_ranger->oracle ()); > > +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) > > + : m_cache (new ssa_global_cache), > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > + m_ranger (ranger), > > + m_resolve (resolve) > > +{ > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > +} > > > > - if (m_resolve && flag_checking) > > - verify_marked_backedges (cfun); > > +path_range_query::path_range_query (gimple_ranger &ranger, > > + edge e, > > + bool resolve) > > + : m_cache (new ssa_global_cache), > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > + m_ranger (ranger), > > + m_resolve (resolve) > > +{ > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > + auto_vec<basic_block> bbs (2); > > + bbs.quick_push (e->dest); > > + bbs.quick_push (e->src); > > + reset_path (bbs, NULL); > > } > > > > path_range_query::~path_range_query () > > { > > delete m_oracle; > > - if (m_alloced_ranger) > > - delete m_ranger; > > BITMAP_FREE (m_has_cache_entry); > > delete m_cache; > > } > > > > -// Return TRUE if NAME is an exit depenency for the path. > > +// Return TRUE if NAME is an exit dependency for the path. > > > > bool > > path_range_query::exit_dependency_p (tree name) > > @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) > > { > > gcc_checking_assert (defined_outside_path (name)); > > basic_block entry = entry_bb (); > > - m_ranger->range_on_entry (r, entry, name); > > + m_ranger.range_on_entry (r, entry, name); > > } > > > > // Return the range of NAME at the end of the path being analyzed. > > @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () > > return m_undefined_path; > > } > > > > -// Initialize the current path to PATH. The current block is set to > > -// the entry block to the path. > > -// > > -// Note that the blocks are in reverse order, so the exit block is > > -// path[0]. > > +// Reset the current path to PATH. > > > > void > > -path_range_query::set_path (const vec<basic_block> &path) > > +path_range_query::reset_path (const vec<basic_block> &path, > > + const bitmap_head *dependencies) > > { > > gcc_checking_assert (path.length () > 1); > > m_path = path.copy (); > > m_pos = m_path.length () - 1; > > + m_undefined_path = false; > > bitmap_clear (m_has_cache_entry); > > + > > + compute_ranges (dependencies); > > } > > > > bool > > @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > > if (at_entry ()) > > { > > - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) > > + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) > > return; > > > > // Try to fold the phi exclusively with global or cached values. > > @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > range_on_path_entry (r, arg); > > else > > r.set_varying (TREE_TYPE (name)); > > - m_ranger->range_on_edge (tmp, e_in, arg); > > + m_ranger.range_on_edge (tmp, e_in, arg); > > r.intersect (tmp); > > return; > > } > > @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) > > } > > > > if (bb && POINTER_TYPE_P (TREE_TYPE (name))) > > - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); > > + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > > if (DEBUG_SOLVER && (bb || !r.varying_p ())) > > { > > @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) > > p->set_root_oracle (nullptr); > > } > > > > - gori_compute &g = m_ranger->gori (); > > + gori_compute &g = m_ranger.gori (); > > bitmap exports = g.exports (bb); > > EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) > > { > > @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) > > else > > r.set_varying (TREE_TYPE (name)); > > > > - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > set_cache (r, name); > > } > > } > > @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) > > // SSA names used to calculate the final conditional along the path. > > > > void > > -path_range_query::compute_exit_dependencies (bitmap dependencies, > > - const vec<basic_block> &path) > > +path_range_query::compute_exit_dependencies (bitmap dependencies) > > { > > // Start with the imports from the exit block... > > - basic_block exit = path[0]; > > - gori_compute &gori = m_ranger->gori (); > > + basic_block exit = m_path[0]; > > + gori_compute &gori = m_ranger.gori (); > > bitmap_copy (dependencies, gori.imports (exit)); > > > > auto_vec<tree> worklist (bitmap_count_bits (dependencies)); > > @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > tree name = worklist.pop (); > > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > > if (SSA_NAME_IS_DEFAULT_DEF (name) > > - || !path.contains (gimple_bb (def_stmt))) > > + || !m_path.contains (gimple_bb (def_stmt))) > > continue; > > > > if (gphi *phi = dyn_cast <gphi *> (def_stmt)) > > @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > tree arg = gimple_phi_arg (phi, i)->def; > > > > if (TREE_CODE (arg) == SSA_NAME > > - && path.contains (e->src) > > + && m_path.contains (e->src) > > && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) > > worklist.safe_push (arg); > > } > > @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > } > > // Exported booleans along the path, may help conditionals. > > if (m_resolve) > > - for (i = 0; i < path.length (); ++i) > > + for (i = 0; i < m_path.length (); ++i) > > { > > - basic_block bb = path[i]; > > + basic_block bb = m_path[i]; > > tree name; > > FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) > > if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) > > @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > // calculated from the final conditional in the path. > > > > void > > -path_range_query::compute_ranges (const vec<basic_block> &path, > > - const bitmap_head *dependencies) > > +path_range_query::compute_ranges (const bitmap_head *dependencies) > > { > > if (DEBUG_SOLVER) > > fprintf (dump_file, "\n==============================================\n"); > > > > - set_path (path); > > - m_undefined_path = false; > > - > > if (dependencies) > > bitmap_copy (m_exit_dependencies, dependencies); > > else > > - compute_exit_dependencies (m_exit_dependencies, m_path); > > + compute_exit_dependencies (m_exit_dependencies); > > > > if (m_resolve) > > get_path_oracle ()->reset_path (); > > @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > if (DEBUG_SOLVER) > > { > > fprintf (dump_file, "path_range_query: compute_ranges for path: "); > > - for (unsigned i = path.length (); i > 0; --i) > > + for (unsigned i = m_path.length (); i > 0; --i) > > { > > - basic_block bb = path[i - 1]; > > + basic_block bb = m_path[i - 1]; > > fprintf (dump_file, "%d", bb->index); > > if (i > 1) > > fprintf (dump_file, "->"); > > @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > } > > } > > > > -// Convenience function to compute ranges along a path consisting of > > -// E->SRC and E->DEST. > > - > > -void > > -path_range_query::compute_ranges (edge e) > > -{ > > - auto_vec<basic_block> bbs (2); > > - bbs.quick_push (e->dest); > > - bbs.quick_push (e->src); > > - compute_ranges (bbs); > > -} > > - > > // A folding aid used to register and query relations along a path. > > // When queried, it returns relations as they would appear on exit to > > // the path. > > @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) > > if (m_resolve) > > { > > fold_using_range f; > > - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); > > + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); > > if (!f.fold_stmt (r, stmt, src)) > > r.set_varying (type); > > } > > @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) > > else > > gcc_unreachable (); > > > > - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); > > + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); > > src.register_outgoing_edges (cond, r, e0, e1); > > } > > } > > diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h > > index 3cb794e34a9..483fde0d431 100644 > > --- a/gcc/gimple-range-path.h > > +++ b/gcc/gimple-range-path.h > > @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see > > class path_range_query : public range_query > > { > > public: > > - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); > > + path_range_query (class gimple_ranger &ranger, > > + const vec<basic_block> &path, > > + const bitmap_head *dependencies = NULL, > > + bool resolve = true); > > + path_range_query (gimple_ranger &ranger, bool resolve = true); > > + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); > > virtual ~path_range_query (); > > - void compute_ranges (const vec<basic_block> &, > > - const bitmap_head *dependencies = NULL); > > - void compute_ranges (edge e); > > - void compute_exit_dependencies (bitmap dependencies, > > - const vec<basic_block> &); > > + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); > > 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 (); > > @@ -47,6 +48,8 @@ public: > > > > private: > > bool internal_range_of_expr (vrange &r, tree name, gimple *); > > + void compute_ranges (const bitmap_head *dependencies); > > + void compute_exit_dependencies (bitmap_head *dependencies); > > bool defined_outside_path (tree name); > > void range_on_path_entry (vrange &r, tree name); > > path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } > > @@ -71,7 +74,6 @@ private: > > bool relations_may_be_invalidated (edge); > > > > // Path navigation. > > - void set_path (const vec<basic_block> &); > > basic_block entry_bb () { return m_path[m_path.length () - 1]; } > > basic_block exit_bb () { return m_path[0]; } > > basic_block curr_bb () { return m_path[m_pos]; } > > @@ -99,7 +101,7 @@ private: > > > > // A ranger used to resolve ranges for SSA names whose values come > > // from outside the path. > > - gimple_ranger *m_ranger; > > + gimple_ranger &m_ranger; > > > > // Current path position. > > unsigned m_pos; > > @@ -109,10 +111,6 @@ private: > > > > // Set if there were any undefined expressions while pre-calculating path. > > bool m_undefined_path; > > - > > - // True if m_ranger was allocated in this class and must be freed at > > - // destruction. > > - bool m_alloced_ranger; > > }; > > > > #endif // GCC_TREE_SSA_THREADSOLVER_H > > diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc > > index 44dc27b464c..513e0c88254 100644 > > --- a/gcc/tree-ssa-dom.cc > > +++ b/gcc/tree-ssa-dom.cc > > @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) > > > > /* Recursively walk the dominator tree optimizing statements. */ > > gimple_ranger *ranger = enable_ranger (fun); > > - path_range_query path_query (/*resolve=*/true, ranger); > > + path_range_query path_query (*ranger); > > dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); > > dom_jt_state state (const_and_copies, avail_exprs_stack); > > jump_threader threader (&simplifier, &state); > > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc > > index 3b91a89eaf5..96816b89287 100644 > > --- a/gcc/tree-ssa-loop-ch.cc > > +++ b/gcc/tree-ssa-loop-ch.cc > > @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see > > be statically determined. */ > > > > static bool > > -entry_loop_condition_is_static (class loop *l, path_range_query *query) > > +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) > > { > > edge e = loop_preheader_edge (l); > > gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); > > @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) > > desired_static_value = boolean_true_node; > > > > int_range<2> r; > > - query->compute_ranges (e); > > - query->range_of_stmt (r, last); > > + path_range_query query (*ranger, e); > > + query.range_of_stmt (r, last); > > return r == int_range<2> (desired_static_value, desired_static_value); > > } > > > > @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) > > auto_vec<std::pair<edge, loop_p> > copied; > > > > mark_dfs_back_edges (); > > - path_range_query *query = new path_range_query; > > + gimple_ranger *ranger = new gimple_ranger; > > for (auto loop : loops_list (cfun, 0)) > > { > > int initial_limit = param_max_loop_header_insns; > > @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) > > iteration. */ > > if (optimize_loop_for_size_p (loop) > > && !loop->force_vectorize > > - && !entry_loop_condition_is_static (loop, query)) > > + && !entry_loop_condition_is_static (loop, ranger)) > > { > > if (dump_file && (dump_flags & TDF_DETAILS)) > > fprintf (dump_file, > > @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) > > candidates.safe_push (loop); > > } > > /* Do not use ranger after we change the IL and not have updated SSA. */ > > - delete query; > > + delete ranger; > > > > for (auto loop : candidates) > > { > > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc > > index b886027fccf..22748b9ec08 100644 > > --- a/gcc/tree-ssa-threadbackward.cc > > +++ b/gcc/tree-ssa-threadbackward.cc > > @@ -99,7 +99,6 @@ private: > > > > back_threader_registry m_registry; > > back_threader_profitability m_profit; > > - path_range_query *m_solver; > > > > // Current path being analyzed. > > auto_vec<basic_block> m_path; > > @@ -119,6 +118,8 @@ private: > > // with the ranger. Otherwise, unknown SSA names are assumed to be > > // VARYING. Setting to true is more precise but slower. > > function *m_fun; > > + // Ranger for the path solver. > > + gimple_ranger *m_ranger; > > unsigned m_flags; > > // Set to TRUE for the first of each thread[12] pass or the first of > > // each threadfull[12] pass. This is used to differentiate between > > @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) > > > > // The path solver needs EDGE_DFS_BACK in resolving mode. > > if (flags & BT_RESOLVE) > > - mark_dfs_back_edges (); > > - m_solver = new path_range_query (flags & BT_RESOLVE); > > + { > > + mark_dfs_back_edges (); > > + > > + if (flag_checking) > > + verify_marked_backedges (fun); > > + } > > + > > + m_ranger = new gimple_ranger; > > } > > > > back_threader::~back_threader () > > { > > - delete m_solver; > > - > > + delete m_ranger; > > loop_optimizer_finalize (); > > } > > > > @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, > > tree name = gimple_switch_index (sw); > > int_range_max r; > > > > - m_solver->compute_ranges (path, m_imports); > > - m_solver->range_of_expr (r, name, sw); > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > + solver.range_of_expr (r, name, sw); > > > > if (r.undefined_p ()) > > return UNREACHABLE_EDGE; > > @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, > > { > > int_range_max r; > > > > - m_solver->compute_ranges (path, m_imports); > > - m_solver->range_of_stmt (r, cond); > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > + solver.range_of_stmt (r, cond); > > > > - if (m_solver->unreachable_path_p ()) > > + if (solver.unreachable_path_p ()) > > return UNREACHABLE_EDGE; > > > > int_range<2> true_range (boolean_true_node, boolean_true_node); > > @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) > > void > > back_threader::dump (FILE *out) > > { > > - m_solver->dump (out); > > fprintf (out, "\nCandidates for pre-computation:\n"); > > fprintf (out, "===================================\n"); > > > > diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc > > index e64e4f209f7..905a98c8c68 100644 > > --- a/gcc/tree-ssa-threadedge.cc > > +++ b/gcc/tree-ssa-threadedge.cc > > @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, > > > > // Hybrid threader implementation. > > > > - > > hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, > > path_range_query *q) > > { > > @@ -1411,7 +1410,12 @@ tree > > hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > jt_state *state) > > { > > - compute_ranges_from_state (stmt, state); > > + auto_bitmap dependencies; > > + auto_vec<basic_block> path; > > + > > + state->get_path (path); > > + compute_exit_dependencies (dependencies, path, stmt); > > + m_query->reset_path (path, dependencies); > > > > if (gimple_code (stmt) == GIMPLE_COND > > || gimple_code (stmt) == GIMPLE_ASSIGN) > > @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > return NULL; > > } > > > > -// Use STATE to generate the list of imports needed for the solver, > > -// and calculate the ranges along the path. > > +// Calculate the set of exit dependencies for a path and statement to > > +// be simplified. This is different than the > > +// compute_exit_dependencies in the path solver because the forward > > +// threader asks questions about statements not necessarily in the > > +// path. Using the default compute_exit_dependencies in the path > > +// solver gets noticeably less threads. > > > > void > > -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, > > + const vec<basic_block> &path, > > + gimple *stmt) > > { > > - auto_bitmap imports; > > gori_compute &gori = m_ranger->gori (); > > > > - state->get_path (m_path); > > - > > // Start with the imports to the final conditional. > > - bitmap_copy (imports, gori.imports (m_path[0])); > > + bitmap_copy (dependencies, gori.imports (path[0])); > > > > // Add any other interesting operands we may have missed. > > - if (gimple_bb (stmt) != m_path[0]) > > + if (gimple_bb (stmt) != path[0]) > > { > > for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) > > { > > @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > if (op > > && TREE_CODE (op) == SSA_NAME > > && Value_Range::supports_type_p (TREE_TYPE (op))) > > - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); > > + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); > > } > > } > > - m_query->compute_ranges (m_path, imports); > > } > > diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h > > index ca70b33f5ed..790ac2ea538 100644 > > --- a/gcc/tree-ssa-threadedge.h > > +++ b/gcc/tree-ssa-threadedge.h > > @@ -69,11 +69,12 @@ public: > > tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; > > > > private: > > - void compute_ranges_from_state (gimple *stmt, jt_state *); > > + void compute_exit_dependencies (bitmap dependencies, > > + const vec<basic_block> &path, > > + gimple *stmt); > > > > gimple_ranger *m_ranger; > > path_range_query *m_query; > > - auto_vec<basic_block> m_path; > > }; > > > > // This is the high level threader. The entry point is > > -- > > 2.37.1 > >
On Thu, Aug 18, 2022, 11:34 Richard Biener <richard.guenther@gmail.com> wrote: > > On Thu, Aug 18, 2022 at 9:58 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > FWIW, here is a rebased version with the latest trunk. > > > > There are no regressions, or differences in threading counts, and the > > performance change is negligible. > > + { > + mark_dfs_back_edges (); > + > + if (flag_checking) > + verify_marked_backedges (fun); > > that looks redundant. Do you suggest somewhere else, or should we nuke verify_marked_backedges altogether since that's its only use? > > Otherwise looks good - it might be possible to get rid of the reset_path use > as well? That's what I mentioned wrt DOM threading. There's a 14% degradation from not reusing the path_range_query in the forward threader because it really abuses the query to try to simplify its statements. So I've left reset_path for it to use, but we can get rid of it when we nuke the old threader. Aldy Aldy > > Richard. > > > Aldy > > > > On Wed, Aug 17, 2022 at 1:59 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > > > These are a bunch of cleanups inspired by Richi's suggestion of making > > > path_range_query standalone, instead of having to call > > > compute_ranges() for each path. > > > > > > I've made the ranger need explicit, and moved the responsibility for > > > its creation to the caller. > > > > > > I've also investigated and documented why the forward threader needs its > > > own compute exit dependencies variant. I can't wait for it to go away > > > :-/. > > > > > > I've also added constructors that take a path and dependencies, and > > > made compute_ranges() private. Unfortunately, reinstantiating > > > path_range_query in the forward threader caused a 14% performance > > > regression in DOM, because the old threader calls it over and over on > > > the same path to simplify statements (some of which not even in the > > > IL, but that's old news). > > > > > > In the meantime, I've left the ability to reset a path, but this time > > > appropriately called reset_path(). > > > > > > I've moved the verify_marked_backedges call to the threader. Is this > > > ok? > > > > > > Interestingly, comparing the thread counts for the patch yielded more > > > threads. I narrowed this down to a bug in the path oracle reset code > > > that's not cleaning things up as expected. I'll fix that before > > > committing this, but figured I'd post for comments in the meantime. > > > > > > Thoughts? > > > > > > gcc/ChangeLog: > > > > > > * gimple-range-path.cc (path_range_query::path_range_query): Add > > > various constructors to take a path. > > > (path_range_query::~path_range_query): Remove m_alloced_ranger. > > > (path_range_query::range_on_path_entry): Adjust for m_ranger being > > > a reference. > > > (path_range_query::set_path): Rename to... > > > (path_range_query::reset_path): ...this and call compute_ranges. > > > (path_range_query::ssa_range_in_phi): Adjust for m_ranger > > > reference. > > > (path_range_query::range_defined_in_block): Same. > > > (path_range_query::compute_ranges_in_block): Same. > > > (path_range_query::adjust_for_non_null_uses): Same. > > > (path_range_query::compute_exit_dependencies): Use m_path instead > > > of argument. > > > (path_range_query::compute_ranges): Remove path argument. > > > (path_range_query::range_of_stmt): Adjust for m_ranger reference. > > > (path_range_query::compute_outgoing_relations): Same. > > > * gimple-range-path.h (class path_range_query): Add various > > > constructors. > > > Make compute_ranges and compute_exit_dependencies private. > > > Rename set_path to reset_path. > > > Make m_ranger a reference. > > > Remove m_alloced_ranger. > > > * tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to > > > path_range_query. > > > * tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a > > > ranger and instantiate a new path_range_query every time. > > > (ch_base::copy_headers): Pass ranger instead of path_range_query. > > > * tree-ssa-threadbackward.cc (class back_threader): Remove m_solver. > > > (back_threader::~back_threader): Remove m_solver. > > > (back_threader::find_taken_edge_switch): Adjust for m_ranger > > > reference. > > > (back_threader::find_taken_edge_cond): Same. > > > (back_threader::dump): Remove m_solver. > > > (back_threader::back_threader): Move verify_marked_backedges > > > here from the path_range_query constructor. > > > * tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move > > > some code from compute_ranges_from_state here. > > > (hybrid_jt_simplifier::compute_ranges_from_state): Rename... > > > (hybrid_jt_simplifier::compute_exit_dependencies): ...to this. > > > * tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename > > > compute_ranges_from_state to compute_exit_dependencies. > > > Remove m_path. > > > --- > > > gcc/gimple-range-path.cc | 112 +++++++++++++++++---------------- > > > gcc/gimple-range-path.h | 22 +++---- > > > gcc/tree-ssa-dom.cc | 2 +- > > > gcc/tree-ssa-loop-ch.cc | 12 ++-- > > > gcc/tree-ssa-threadbackward.cc | 27 ++++---- > > > gcc/tree-ssa-threadedge.cc | 30 +++++---- > > > gcc/tree-ssa-threadedge.h | 5 +- > > > 7 files changed, 111 insertions(+), 99 deletions(-) > > > > > > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc > > > index c99d77dd340..d37605f4539 100644 > > > --- a/gcc/gimple-range-path.cc > > > +++ b/gcc/gimple-range-path.cc > > > @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see > > > // Internal construct to help facilitate debugging of solver. > > > #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) > > > > > > -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) > > > +path_range_query::path_range_query (gimple_ranger &ranger, > > > + const vec<basic_block> &path, > > > + const bitmap_head *dependencies, > > > + bool resolve) > > > : m_cache (new ssa_global_cache), > > > m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > - m_resolve (resolve), > > > - m_alloced_ranger (!ranger) > > > + m_ranger (ranger), > > > + m_resolve (resolve) > > > { > > > - if (m_alloced_ranger) > > > - m_ranger = new gimple_ranger; > > > - else > > > - m_ranger = ranger; > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > + > > > + reset_path (path, dependencies); > > > +} > > > > > > - m_oracle = new path_oracle (m_ranger->oracle ()); > > > +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) > > > + : m_cache (new ssa_global_cache), > > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > + m_ranger (ranger), > > > + m_resolve (resolve) > > > +{ > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > +} > > > > > > - if (m_resolve && flag_checking) > > > - verify_marked_backedges (cfun); > > > +path_range_query::path_range_query (gimple_ranger &ranger, > > > + edge e, > > > + bool resolve) > > > + : m_cache (new ssa_global_cache), > > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > + m_ranger (ranger), > > > + m_resolve (resolve) > > > +{ > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > + auto_vec<basic_block> bbs (2); > > > + bbs.quick_push (e->dest); > > > + bbs.quick_push (e->src); > > > + reset_path (bbs, NULL); > > > } > > > > > > path_range_query::~path_range_query () > > > { > > > delete m_oracle; > > > - if (m_alloced_ranger) > > > - delete m_ranger; > > > BITMAP_FREE (m_has_cache_entry); > > > delete m_cache; > > > } > > > > > > -// Return TRUE if NAME is an exit depenency for the path. > > > +// Return TRUE if NAME is an exit dependency for the path. > > > > > > bool > > > path_range_query::exit_dependency_p (tree name) > > > @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) > > > { > > > gcc_checking_assert (defined_outside_path (name)); > > > basic_block entry = entry_bb (); > > > - m_ranger->range_on_entry (r, entry, name); > > > + m_ranger.range_on_entry (r, entry, name); > > > } > > > > > > // Return the range of NAME at the end of the path being analyzed. > > > @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () > > > return m_undefined_path; > > > } > > > > > > -// Initialize the current path to PATH. The current block is set to > > > -// the entry block to the path. > > > -// > > > -// Note that the blocks are in reverse order, so the exit block is > > > -// path[0]. > > > +// Reset the current path to PATH. > > > > > > void > > > -path_range_query::set_path (const vec<basic_block> &path) > > > +path_range_query::reset_path (const vec<basic_block> &path, > > > + const bitmap_head *dependencies) > > > { > > > gcc_checking_assert (path.length () > 1); > > > m_path = path.copy (); > > > m_pos = m_path.length () - 1; > > > + m_undefined_path = false; > > > bitmap_clear (m_has_cache_entry); > > > + > > > + compute_ranges (dependencies); > > > } > > > > > > bool > > > @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > > > > if (at_entry ()) > > > { > > > - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) > > > + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) > > > return; > > > > > > // Try to fold the phi exclusively with global or cached values. > > > @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > range_on_path_entry (r, arg); > > > else > > > r.set_varying (TREE_TYPE (name)); > > > - m_ranger->range_on_edge (tmp, e_in, arg); > > > + m_ranger.range_on_edge (tmp, e_in, arg); > > > r.intersect (tmp); > > > return; > > > } > > > @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) > > > } > > > > > > if (bb && POINTER_TYPE_P (TREE_TYPE (name))) > > > - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > > > > if (DEBUG_SOLVER && (bb || !r.varying_p ())) > > > { > > > @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) > > > p->set_root_oracle (nullptr); > > > } > > > > > > - gori_compute &g = m_ranger->gori (); > > > + gori_compute &g = m_ranger.gori (); > > > bitmap exports = g.exports (bb); > > > EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) > > > { > > > @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) > > > else > > > r.set_varying (TREE_TYPE (name)); > > > > > > - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > > + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > > set_cache (r, name); > > > } > > > } > > > @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) > > > // SSA names used to calculate the final conditional along the path. > > > > > > void > > > -path_range_query::compute_exit_dependencies (bitmap dependencies, > > > - const vec<basic_block> &path) > > > +path_range_query::compute_exit_dependencies (bitmap dependencies) > > > { > > > // Start with the imports from the exit block... > > > - basic_block exit = path[0]; > > > - gori_compute &gori = m_ranger->gori (); > > > + basic_block exit = m_path[0]; > > > + gori_compute &gori = m_ranger.gori (); > > > bitmap_copy (dependencies, gori.imports (exit)); > > > > > > auto_vec<tree> worklist (bitmap_count_bits (dependencies)); > > > @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > tree name = worklist.pop (); > > > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > > > if (SSA_NAME_IS_DEFAULT_DEF (name) > > > - || !path.contains (gimple_bb (def_stmt))) > > > + || !m_path.contains (gimple_bb (def_stmt))) > > > continue; > > > > > > if (gphi *phi = dyn_cast <gphi *> (def_stmt)) > > > @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > tree arg = gimple_phi_arg (phi, i)->def; > > > > > > if (TREE_CODE (arg) == SSA_NAME > > > - && path.contains (e->src) > > > + && m_path.contains (e->src) > > > && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) > > > worklist.safe_push (arg); > > > } > > > @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > } > > > // Exported booleans along the path, may help conditionals. > > > if (m_resolve) > > > - for (i = 0; i < path.length (); ++i) > > > + for (i = 0; i < m_path.length (); ++i) > > > { > > > - basic_block bb = path[i]; > > > + basic_block bb = m_path[i]; > > > tree name; > > > FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) > > > if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) > > > @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > // calculated from the final conditional in the path. > > > > > > void > > > -path_range_query::compute_ranges (const vec<basic_block> &path, > > > - const bitmap_head *dependencies) > > > +path_range_query::compute_ranges (const bitmap_head *dependencies) > > > { > > > if (DEBUG_SOLVER) > > > fprintf (dump_file, "\n==============================================\n"); > > > > > > - set_path (path); > > > - m_undefined_path = false; > > > - > > > if (dependencies) > > > bitmap_copy (m_exit_dependencies, dependencies); > > > else > > > - compute_exit_dependencies (m_exit_dependencies, m_path); > > > + compute_exit_dependencies (m_exit_dependencies); > > > > > > if (m_resolve) > > > get_path_oracle ()->reset_path (); > > > @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > > if (DEBUG_SOLVER) > > > { > > > fprintf (dump_file, "path_range_query: compute_ranges for path: "); > > > - for (unsigned i = path.length (); i > 0; --i) > > > + for (unsigned i = m_path.length (); i > 0; --i) > > > { > > > - basic_block bb = path[i - 1]; > > > + basic_block bb = m_path[i - 1]; > > > fprintf (dump_file, "%d", bb->index); > > > if (i > 1) > > > fprintf (dump_file, "->"); > > > @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > > } > > > } > > > > > > -// Convenience function to compute ranges along a path consisting of > > > -// E->SRC and E->DEST. > > > - > > > -void > > > -path_range_query::compute_ranges (edge e) > > > -{ > > > - auto_vec<basic_block> bbs (2); > > > - bbs.quick_push (e->dest); > > > - bbs.quick_push (e->src); > > > - compute_ranges (bbs); > > > -} > > > - > > > // A folding aid used to register and query relations along a path. > > > // When queried, it returns relations as they would appear on exit to > > > // the path. > > > @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) > > > if (m_resolve) > > > { > > > fold_using_range f; > > > - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); > > > + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); > > > if (!f.fold_stmt (r, stmt, src)) > > > r.set_varying (type); > > > } > > > @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) > > > else > > > gcc_unreachable (); > > > > > > - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); > > > + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); > > > src.register_outgoing_edges (cond, r, e0, e1); > > > } > > > } > > > diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h > > > index 3cb794e34a9..483fde0d431 100644 > > > --- a/gcc/gimple-range-path.h > > > +++ b/gcc/gimple-range-path.h > > > @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see > > > class path_range_query : public range_query > > > { > > > public: > > > - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); > > > + path_range_query (class gimple_ranger &ranger, > > > + const vec<basic_block> &path, > > > + const bitmap_head *dependencies = NULL, > > > + bool resolve = true); > > > + path_range_query (gimple_ranger &ranger, bool resolve = true); > > > + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); > > > virtual ~path_range_query (); > > > - void compute_ranges (const vec<basic_block> &, > > > - const bitmap_head *dependencies = NULL); > > > - void compute_ranges (edge e); > > > - void compute_exit_dependencies (bitmap dependencies, > > > - const vec<basic_block> &); > > > + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); > > > 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 (); > > > @@ -47,6 +48,8 @@ public: > > > > > > private: > > > bool internal_range_of_expr (vrange &r, tree name, gimple *); > > > + void compute_ranges (const bitmap_head *dependencies); > > > + void compute_exit_dependencies (bitmap_head *dependencies); > > > bool defined_outside_path (tree name); > > > void range_on_path_entry (vrange &r, tree name); > > > path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } > > > @@ -71,7 +74,6 @@ private: > > > bool relations_may_be_invalidated (edge); > > > > > > // Path navigation. > > > - void set_path (const vec<basic_block> &); > > > basic_block entry_bb () { return m_path[m_path.length () - 1]; } > > > basic_block exit_bb () { return m_path[0]; } > > > basic_block curr_bb () { return m_path[m_pos]; } > > > @@ -99,7 +101,7 @@ private: > > > > > > // A ranger used to resolve ranges for SSA names whose values come > > > // from outside the path. > > > - gimple_ranger *m_ranger; > > > + gimple_ranger &m_ranger; > > > > > > // Current path position. > > > unsigned m_pos; > > > @@ -109,10 +111,6 @@ private: > > > > > > // Set if there were any undefined expressions while pre-calculating path. > > > bool m_undefined_path; > > > - > > > - // True if m_ranger was allocated in this class and must be freed at > > > - // destruction. > > > - bool m_alloced_ranger; > > > }; > > > > > > #endif // GCC_TREE_SSA_THREADSOLVER_H > > > diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc > > > index 44dc27b464c..513e0c88254 100644 > > > --- a/gcc/tree-ssa-dom.cc > > > +++ b/gcc/tree-ssa-dom.cc > > > @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) > > > > > > /* Recursively walk the dominator tree optimizing statements. */ > > > gimple_ranger *ranger = enable_ranger (fun); > > > - path_range_query path_query (/*resolve=*/true, ranger); > > > + path_range_query path_query (*ranger); > > > dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); > > > dom_jt_state state (const_and_copies, avail_exprs_stack); > > > jump_threader threader (&simplifier, &state); > > > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc > > > index 3b91a89eaf5..96816b89287 100644 > > > --- a/gcc/tree-ssa-loop-ch.cc > > > +++ b/gcc/tree-ssa-loop-ch.cc > > > @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see > > > be statically determined. */ > > > > > > static bool > > > -entry_loop_condition_is_static (class loop *l, path_range_query *query) > > > +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) > > > { > > > edge e = loop_preheader_edge (l); > > > gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); > > > @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) > > > desired_static_value = boolean_true_node; > > > > > > int_range<2> r; > > > - query->compute_ranges (e); > > > - query->range_of_stmt (r, last); > > > + path_range_query query (*ranger, e); > > > + query.range_of_stmt (r, last); > > > return r == int_range<2> (desired_static_value, desired_static_value); > > > } > > > > > > @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) > > > auto_vec<std::pair<edge, loop_p> > copied; > > > > > > mark_dfs_back_edges (); > > > - path_range_query *query = new path_range_query; > > > + gimple_ranger *ranger = new gimple_ranger; > > > for (auto loop : loops_list (cfun, 0)) > > > { > > > int initial_limit = param_max_loop_header_insns; > > > @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) > > > iteration. */ > > > if (optimize_loop_for_size_p (loop) > > > && !loop->force_vectorize > > > - && !entry_loop_condition_is_static (loop, query)) > > > + && !entry_loop_condition_is_static (loop, ranger)) > > > { > > > if (dump_file && (dump_flags & TDF_DETAILS)) > > > fprintf (dump_file, > > > @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) > > > candidates.safe_push (loop); > > > } > > > /* Do not use ranger after we change the IL and not have updated SSA. */ > > > - delete query; > > > + delete ranger; > > > > > > for (auto loop : candidates) > > > { > > > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc > > > index b886027fccf..22748b9ec08 100644 > > > --- a/gcc/tree-ssa-threadbackward.cc > > > +++ b/gcc/tree-ssa-threadbackward.cc > > > @@ -99,7 +99,6 @@ private: > > > > > > back_threader_registry m_registry; > > > back_threader_profitability m_profit; > > > - path_range_query *m_solver; > > > > > > // Current path being analyzed. > > > auto_vec<basic_block> m_path; > > > @@ -119,6 +118,8 @@ private: > > > // with the ranger. Otherwise, unknown SSA names are assumed to be > > > // VARYING. Setting to true is more precise but slower. > > > function *m_fun; > > > + // Ranger for the path solver. > > > + gimple_ranger *m_ranger; > > > unsigned m_flags; > > > // Set to TRUE for the first of each thread[12] pass or the first of > > > // each threadfull[12] pass. This is used to differentiate between > > > @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) > > > > > > // The path solver needs EDGE_DFS_BACK in resolving mode. > > > if (flags & BT_RESOLVE) > > > - mark_dfs_back_edges (); > > > - m_solver = new path_range_query (flags & BT_RESOLVE); > > > + { > > > + mark_dfs_back_edges (); > > > + > > > + if (flag_checking) > > > + verify_marked_backedges (fun); > > > + } > > > + > > > + m_ranger = new gimple_ranger; > > > } > > > > > > back_threader::~back_threader () > > > { > > > - delete m_solver; > > > - > > > + delete m_ranger; > > > loop_optimizer_finalize (); > > > } > > > > > > @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, > > > tree name = gimple_switch_index (sw); > > > int_range_max r; > > > > > > - m_solver->compute_ranges (path, m_imports); > > > - m_solver->range_of_expr (r, name, sw); > > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > > + solver.range_of_expr (r, name, sw); > > > > > > if (r.undefined_p ()) > > > return UNREACHABLE_EDGE; > > > @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, > > > { > > > int_range_max r; > > > > > > - m_solver->compute_ranges (path, m_imports); > > > - m_solver->range_of_stmt (r, cond); > > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > > + solver.range_of_stmt (r, cond); > > > > > > - if (m_solver->unreachable_path_p ()) > > > + if (solver.unreachable_path_p ()) > > > return UNREACHABLE_EDGE; > > > > > > int_range<2> true_range (boolean_true_node, boolean_true_node); > > > @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) > > > void > > > back_threader::dump (FILE *out) > > > { > > > - m_solver->dump (out); > > > fprintf (out, "\nCandidates for pre-computation:\n"); > > > fprintf (out, "===================================\n"); > > > > > > diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc > > > index e64e4f209f7..905a98c8c68 100644 > > > --- a/gcc/tree-ssa-threadedge.cc > > > +++ b/gcc/tree-ssa-threadedge.cc > > > @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, > > > > > > // Hybrid threader implementation. > > > > > > - > > > hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, > > > path_range_query *q) > > > { > > > @@ -1411,7 +1410,12 @@ tree > > > hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > > jt_state *state) > > > { > > > - compute_ranges_from_state (stmt, state); > > > + auto_bitmap dependencies; > > > + auto_vec<basic_block> path; > > > + > > > + state->get_path (path); > > > + compute_exit_dependencies (dependencies, path, stmt); > > > + m_query->reset_path (path, dependencies); > > > > > > if (gimple_code (stmt) == GIMPLE_COND > > > || gimple_code (stmt) == GIMPLE_ASSIGN) > > > @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > > return NULL; > > > } > > > > > > -// Use STATE to generate the list of imports needed for the solver, > > > -// and calculate the ranges along the path. > > > +// Calculate the set of exit dependencies for a path and statement to > > > +// be simplified. This is different than the > > > +// compute_exit_dependencies in the path solver because the forward > > > +// threader asks questions about statements not necessarily in the > > > +// path. Using the default compute_exit_dependencies in the path > > > +// solver gets noticeably less threads. > > > > > > void > > > -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > > +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, > > > + const vec<basic_block> &path, > > > + gimple *stmt) > > > { > > > - auto_bitmap imports; > > > gori_compute &gori = m_ranger->gori (); > > > > > > - state->get_path (m_path); > > > - > > > // Start with the imports to the final conditional. > > > - bitmap_copy (imports, gori.imports (m_path[0])); > > > + bitmap_copy (dependencies, gori.imports (path[0])); > > > > > > // Add any other interesting operands we may have missed. > > > - if (gimple_bb (stmt) != m_path[0]) > > > + if (gimple_bb (stmt) != path[0]) > > > { > > > for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) > > > { > > > @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > > if (op > > > && TREE_CODE (op) == SSA_NAME > > > && Value_Range::supports_type_p (TREE_TYPE (op))) > > > - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); > > > + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); > > > } > > > } > > > - m_query->compute_ranges (m_path, imports); > > > } > > > diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h > > > index ca70b33f5ed..790ac2ea538 100644 > > > --- a/gcc/tree-ssa-threadedge.h > > > +++ b/gcc/tree-ssa-threadedge.h > > > @@ -69,11 +69,12 @@ public: > > > tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; > > > > > > private: > > > - void compute_ranges_from_state (gimple *stmt, jt_state *); > > > + void compute_exit_dependencies (bitmap dependencies, > > > + const vec<basic_block> &path, > > > + gimple *stmt); > > > > > > gimple_ranger *m_ranger; > > > path_range_query *m_query; > > > - auto_vec<basic_block> m_path; > > > }; > > > > > > // This is the high level threader. The entry point is > > > -- > > > 2.37.1 > > > >
On Thu, Aug 18, 2022 at 1:10 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > On Thu, Aug 18, 2022, 11:34 Richard Biener <richard.guenther@gmail.com> wrote: > > > > On Thu, Aug 18, 2022 at 9:58 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > > > FWIW, here is a rebased version with the latest trunk. > > > > > > There are no regressions, or differences in threading counts, and the > > > performance change is negligible. > > > > + { > > + mark_dfs_back_edges (); > > + > > + if (flag_checking) > > + verify_marked_backedges (fun); > > > > that looks redundant. > > Do you suggest somewhere else, or should we nuke > verify_marked_backedges altogether since that's its only use? Not sure. I'd leave the function around in any case. > > > > Otherwise looks good - it might be possible to get rid of the reset_path use > > as well? > > > That's what I mentioned wrt DOM threading. There's a 14% degradation > from not reusing the path_range_query in the forward threader because > it really abuses the query to try to simplify its statements. So I've > left reset_path for it to use, but we can get rid of it when we nuke > the old threader. Ah, I see. > Aldy > > > Aldy > > > > > Richard. > > > > > Aldy > > > > > > On Wed, Aug 17, 2022 at 1:59 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > > > > > These are a bunch of cleanups inspired by Richi's suggestion of making > > > > path_range_query standalone, instead of having to call > > > > compute_ranges() for each path. > > > > > > > > I've made the ranger need explicit, and moved the responsibility for > > > > its creation to the caller. > > > > > > > > I've also investigated and documented why the forward threader needs its > > > > own compute exit dependencies variant. I can't wait for it to go away > > > > :-/. > > > > > > > > I've also added constructors that take a path and dependencies, and > > > > made compute_ranges() private. Unfortunately, reinstantiating > > > > path_range_query in the forward threader caused a 14% performance > > > > regression in DOM, because the old threader calls it over and over on > > > > the same path to simplify statements (some of which not even in the > > > > IL, but that's old news). > > > > > > > > In the meantime, I've left the ability to reset a path, but this time > > > > appropriately called reset_path(). > > > > > > > > I've moved the verify_marked_backedges call to the threader. Is this > > > > ok? > > > > > > > > Interestingly, comparing the thread counts for the patch yielded more > > > > threads. I narrowed this down to a bug in the path oracle reset code > > > > that's not cleaning things up as expected. I'll fix that before > > > > committing this, but figured I'd post for comments in the meantime. > > > > > > > > Thoughts? > > > > > > > > gcc/ChangeLog: > > > > > > > > * gimple-range-path.cc (path_range_query::path_range_query): Add > > > > various constructors to take a path. > > > > (path_range_query::~path_range_query): Remove m_alloced_ranger. > > > > (path_range_query::range_on_path_entry): Adjust for m_ranger being > > > > a reference. > > > > (path_range_query::set_path): Rename to... > > > > (path_range_query::reset_path): ...this and call compute_ranges. > > > > (path_range_query::ssa_range_in_phi): Adjust for m_ranger > > > > reference. > > > > (path_range_query::range_defined_in_block): Same. > > > > (path_range_query::compute_ranges_in_block): Same. > > > > (path_range_query::adjust_for_non_null_uses): Same. > > > > (path_range_query::compute_exit_dependencies): Use m_path instead > > > > of argument. > > > > (path_range_query::compute_ranges): Remove path argument. > > > > (path_range_query::range_of_stmt): Adjust for m_ranger reference. > > > > (path_range_query::compute_outgoing_relations): Same. > > > > * gimple-range-path.h (class path_range_query): Add various > > > > constructors. > > > > Make compute_ranges and compute_exit_dependencies private. > > > > Rename set_path to reset_path. > > > > Make m_ranger a reference. > > > > Remove m_alloced_ranger. > > > > * tree-ssa-dom.cc (pass_dominator::execute): Adjust constructor to > > > > path_range_query. > > > > * tree-ssa-loop-ch.cc (entry_loop_condition_is_static): Take a > > > > ranger and instantiate a new path_range_query every time. > > > > (ch_base::copy_headers): Pass ranger instead of path_range_query. > > > > * tree-ssa-threadbackward.cc (class back_threader): Remove m_solver. > > > > (back_threader::~back_threader): Remove m_solver. > > > > (back_threader::find_taken_edge_switch): Adjust for m_ranger > > > > reference. > > > > (back_threader::find_taken_edge_cond): Same. > > > > (back_threader::dump): Remove m_solver. > > > > (back_threader::back_threader): Move verify_marked_backedges > > > > here from the path_range_query constructor. > > > > * tree-ssa-threadedge.cc (hybrid_jt_simplifier::simplify): Move > > > > some code from compute_ranges_from_state here. > > > > (hybrid_jt_simplifier::compute_ranges_from_state): Rename... > > > > (hybrid_jt_simplifier::compute_exit_dependencies): ...to this. > > > > * tree-ssa-threadedge.h (class hybrid_jt_simplifier): Rename > > > > compute_ranges_from_state to compute_exit_dependencies. > > > > Remove m_path. > > > > --- > > > > gcc/gimple-range-path.cc | 112 +++++++++++++++++---------------- > > > > gcc/gimple-range-path.h | 22 +++---- > > > > gcc/tree-ssa-dom.cc | 2 +- > > > > gcc/tree-ssa-loop-ch.cc | 12 ++-- > > > > gcc/tree-ssa-threadbackward.cc | 27 ++++---- > > > > gcc/tree-ssa-threadedge.cc | 30 +++++---- > > > > gcc/tree-ssa-threadedge.h | 5 +- > > > > 7 files changed, 111 insertions(+), 99 deletions(-) > > > > > > > > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc > > > > index c99d77dd340..d37605f4539 100644 > > > > --- a/gcc/gimple-range-path.cc > > > > +++ b/gcc/gimple-range-path.cc > > > > @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see > > > > // Internal construct to help facilitate debugging of solver. > > > > #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) > > > > > > > > -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) > > > > +path_range_query::path_range_query (gimple_ranger &ranger, > > > > + const vec<basic_block> &path, > > > > + const bitmap_head *dependencies, > > > > + bool resolve) > > > > : m_cache (new ssa_global_cache), > > > > m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > > - m_resolve (resolve), > > > > - m_alloced_ranger (!ranger) > > > > + m_ranger (ranger), > > > > + m_resolve (resolve) > > > > { > > > > - if (m_alloced_ranger) > > > > - m_ranger = new gimple_ranger; > > > > - else > > > > - m_ranger = ranger; > > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > > + > > > > + reset_path (path, dependencies); > > > > +} > > > > > > > > - m_oracle = new path_oracle (m_ranger->oracle ()); > > > > +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) > > > > + : m_cache (new ssa_global_cache), > > > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > > + m_ranger (ranger), > > > > + m_resolve (resolve) > > > > +{ > > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > > +} > > > > > > > > - if (m_resolve && flag_checking) > > > > - verify_marked_backedges (cfun); > > > > +path_range_query::path_range_query (gimple_ranger &ranger, > > > > + edge e, > > > > + bool resolve) > > > > + : m_cache (new ssa_global_cache), > > > > + m_has_cache_entry (BITMAP_ALLOC (NULL)), > > > > + m_ranger (ranger), > > > > + m_resolve (resolve) > > > > +{ > > > > + m_oracle = new path_oracle (m_ranger.oracle ()); > > > > + auto_vec<basic_block> bbs (2); > > > > + bbs.quick_push (e->dest); > > > > + bbs.quick_push (e->src); > > > > + reset_path (bbs, NULL); > > > > } > > > > > > > > path_range_query::~path_range_query () > > > > { > > > > delete m_oracle; > > > > - if (m_alloced_ranger) > > > > - delete m_ranger; > > > > BITMAP_FREE (m_has_cache_entry); > > > > delete m_cache; > > > > } > > > > > > > > -// Return TRUE if NAME is an exit depenency for the path. > > > > +// Return TRUE if NAME is an exit dependency for the path. > > > > > > > > bool > > > > path_range_query::exit_dependency_p (tree name) > > > > @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) > > > > { > > > > gcc_checking_assert (defined_outside_path (name)); > > > > basic_block entry = entry_bb (); > > > > - m_ranger->range_on_entry (r, entry, name); > > > > + m_ranger.range_on_entry (r, entry, name); > > > > } > > > > > > > > // Return the range of NAME at the end of the path being analyzed. > > > > @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () > > > > return m_undefined_path; > > > > } > > > > > > > > -// Initialize the current path to PATH. The current block is set to > > > > -// the entry block to the path. > > > > -// > > > > -// Note that the blocks are in reverse order, so the exit block is > > > > -// path[0]. > > > > +// Reset the current path to PATH. > > > > > > > > void > > > > -path_range_query::set_path (const vec<basic_block> &path) > > > > +path_range_query::reset_path (const vec<basic_block> &path, > > > > + const bitmap_head *dependencies) > > > > { > > > > gcc_checking_assert (path.length () > 1); > > > > m_path = path.copy (); > > > > m_pos = m_path.length () - 1; > > > > + m_undefined_path = false; > > > > bitmap_clear (m_has_cache_entry); > > > > + > > > > + compute_ranges (dependencies); > > > > } > > > > > > > > bool > > > > @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > > > > > > if (at_entry ()) > > > > { > > > > - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) > > > > + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) > > > > return; > > > > > > > > // Try to fold the phi exclusively with global or cached values. > > > > @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) > > > > range_on_path_entry (r, arg); > > > > else > > > > r.set_varying (TREE_TYPE (name)); > > > > - m_ranger->range_on_edge (tmp, e_in, arg); > > > > + m_ranger.range_on_edge (tmp, e_in, arg); > > > > r.intersect (tmp); > > > > return; > > > > } > > > > @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) > > > > } > > > > > > > > if (bb && POINTER_TYPE_P (TREE_TYPE (name))) > > > > - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > > + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); > > > > > > > > if (DEBUG_SOLVER && (bb || !r.varying_p ())) > > > > { > > > > @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) > > > > p->set_root_oracle (nullptr); > > > > } > > > > > > > > - gori_compute &g = m_ranger->gori (); > > > > + gori_compute &g = m_ranger.gori (); > > > > bitmap exports = g.exports (bb); > > > > EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) > > > > { > > > > @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) > > > > else > > > > r.set_varying (TREE_TYPE (name)); > > > > > > > > - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > > > + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) > > > > set_cache (r, name); > > > > } > > > > } > > > > @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) > > > > // SSA names used to calculate the final conditional along the path. > > > > > > > > void > > > > -path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > - const vec<basic_block> &path) > > > > +path_range_query::compute_exit_dependencies (bitmap dependencies) > > > > { > > > > // Start with the imports from the exit block... > > > > - basic_block exit = path[0]; > > > > - gori_compute &gori = m_ranger->gori (); > > > > + basic_block exit = m_path[0]; > > > > + gori_compute &gori = m_ranger.gori (); > > > > bitmap_copy (dependencies, gori.imports (exit)); > > > > > > > > auto_vec<tree> worklist (bitmap_count_bits (dependencies)); > > > > @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > tree name = worklist.pop (); > > > > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > > > > if (SSA_NAME_IS_DEFAULT_DEF (name) > > > > - || !path.contains (gimple_bb (def_stmt))) > > > > + || !m_path.contains (gimple_bb (def_stmt))) > > > > continue; > > > > > > > > if (gphi *phi = dyn_cast <gphi *> (def_stmt)) > > > > @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > tree arg = gimple_phi_arg (phi, i)->def; > > > > > > > > if (TREE_CODE (arg) == SSA_NAME > > > > - && path.contains (e->src) > > > > + && m_path.contains (e->src) > > > > && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) > > > > worklist.safe_push (arg); > > > > } > > > > @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > } > > > > // Exported booleans along the path, may help conditionals. > > > > if (m_resolve) > > > > - for (i = 0; i < path.length (); ++i) > > > > + for (i = 0; i < m_path.length (); ++i) > > > > { > > > > - basic_block bb = path[i]; > > > > + basic_block bb = m_path[i]; > > > > tree name; > > > > FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) > > > > if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) > > > > @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, > > > > // calculated from the final conditional in the path. > > > > > > > > void > > > > -path_range_query::compute_ranges (const vec<basic_block> &path, > > > > - const bitmap_head *dependencies) > > > > +path_range_query::compute_ranges (const bitmap_head *dependencies) > > > > { > > > > if (DEBUG_SOLVER) > > > > fprintf (dump_file, "\n==============================================\n"); > > > > > > > > - set_path (path); > > > > - m_undefined_path = false; > > > > - > > > > if (dependencies) > > > > bitmap_copy (m_exit_dependencies, dependencies); > > > > else > > > > - compute_exit_dependencies (m_exit_dependencies, m_path); > > > > + compute_exit_dependencies (m_exit_dependencies); > > > > > > > > if (m_resolve) > > > > get_path_oracle ()->reset_path (); > > > > @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > > > if (DEBUG_SOLVER) > > > > { > > > > fprintf (dump_file, "path_range_query: compute_ranges for path: "); > > > > - for (unsigned i = path.length (); i > 0; --i) > > > > + for (unsigned i = m_path.length (); i > 0; --i) > > > > { > > > > - basic_block bb = path[i - 1]; > > > > + basic_block bb = m_path[i - 1]; > > > > fprintf (dump_file, "%d", bb->index); > > > > if (i > 1) > > > > fprintf (dump_file, "->"); > > > > @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, > > > > } > > > > } > > > > > > > > -// Convenience function to compute ranges along a path consisting of > > > > -// E->SRC and E->DEST. > > > > - > > > > -void > > > > -path_range_query::compute_ranges (edge e) > > > > -{ > > > > - auto_vec<basic_block> bbs (2); > > > > - bbs.quick_push (e->dest); > > > > - bbs.quick_push (e->src); > > > > - compute_ranges (bbs); > > > > -} > > > > - > > > > // A folding aid used to register and query relations along a path. > > > > // When queried, it returns relations as they would appear on exit to > > > > // the path. > > > > @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) > > > > if (m_resolve) > > > > { > > > > fold_using_range f; > > > > - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); > > > > + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); > > > > if (!f.fold_stmt (r, stmt, src)) > > > > r.set_varying (type); > > > > } > > > > @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) > > > > else > > > > gcc_unreachable (); > > > > > > > > - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); > > > > + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); > > > > src.register_outgoing_edges (cond, r, e0, e1); > > > > } > > > > } > > > > diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h > > > > index 3cb794e34a9..483fde0d431 100644 > > > > --- a/gcc/gimple-range-path.h > > > > +++ b/gcc/gimple-range-path.h > > > > @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see > > > > class path_range_query : public range_query > > > > { > > > > public: > > > > - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); > > > > + path_range_query (class gimple_ranger &ranger, > > > > + const vec<basic_block> &path, > > > > + const bitmap_head *dependencies = NULL, > > > > + bool resolve = true); > > > > + path_range_query (gimple_ranger &ranger, bool resolve = true); > > > > + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); > > > > virtual ~path_range_query (); > > > > - void compute_ranges (const vec<basic_block> &, > > > > - const bitmap_head *dependencies = NULL); > > > > - void compute_ranges (edge e); > > > > - void compute_exit_dependencies (bitmap dependencies, > > > > - const vec<basic_block> &); > > > > + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); > > > > 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 (); > > > > @@ -47,6 +48,8 @@ public: > > > > > > > > private: > > > > bool internal_range_of_expr (vrange &r, tree name, gimple *); > > > > + void compute_ranges (const bitmap_head *dependencies); > > > > + void compute_exit_dependencies (bitmap_head *dependencies); > > > > bool defined_outside_path (tree name); > > > > void range_on_path_entry (vrange &r, tree name); > > > > path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } > > > > @@ -71,7 +74,6 @@ private: > > > > bool relations_may_be_invalidated (edge); > > > > > > > > // Path navigation. > > > > - void set_path (const vec<basic_block> &); > > > > basic_block entry_bb () { return m_path[m_path.length () - 1]; } > > > > basic_block exit_bb () { return m_path[0]; } > > > > basic_block curr_bb () { return m_path[m_pos]; } > > > > @@ -99,7 +101,7 @@ private: > > > > > > > > // A ranger used to resolve ranges for SSA names whose values come > > > > // from outside the path. > > > > - gimple_ranger *m_ranger; > > > > + gimple_ranger &m_ranger; > > > > > > > > // Current path position. > > > > unsigned m_pos; > > > > @@ -109,10 +111,6 @@ private: > > > > > > > > // Set if there were any undefined expressions while pre-calculating path. > > > > bool m_undefined_path; > > > > - > > > > - // True if m_ranger was allocated in this class and must be freed at > > > > - // destruction. > > > > - bool m_alloced_ranger; > > > > }; > > > > > > > > #endif // GCC_TREE_SSA_THREADSOLVER_H > > > > diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc > > > > index 44dc27b464c..513e0c88254 100644 > > > > --- a/gcc/tree-ssa-dom.cc > > > > +++ b/gcc/tree-ssa-dom.cc > > > > @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) > > > > > > > > /* Recursively walk the dominator tree optimizing statements. */ > > > > gimple_ranger *ranger = enable_ranger (fun); > > > > - path_range_query path_query (/*resolve=*/true, ranger); > > > > + path_range_query path_query (*ranger); > > > > dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); > > > > dom_jt_state state (const_and_copies, avail_exprs_stack); > > > > jump_threader threader (&simplifier, &state); > > > > diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc > > > > index 3b91a89eaf5..96816b89287 100644 > > > > --- a/gcc/tree-ssa-loop-ch.cc > > > > +++ b/gcc/tree-ssa-loop-ch.cc > > > > @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see > > > > be statically determined. */ > > > > > > > > static bool > > > > -entry_loop_condition_is_static (class loop *l, path_range_query *query) > > > > +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) > > > > { > > > > edge e = loop_preheader_edge (l); > > > > gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); > > > > @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) > > > > desired_static_value = boolean_true_node; > > > > > > > > int_range<2> r; > > > > - query->compute_ranges (e); > > > > - query->range_of_stmt (r, last); > > > > + path_range_query query (*ranger, e); > > > > + query.range_of_stmt (r, last); > > > > return r == int_range<2> (desired_static_value, desired_static_value); > > > > } > > > > > > > > @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) > > > > auto_vec<std::pair<edge, loop_p> > copied; > > > > > > > > mark_dfs_back_edges (); > > > > - path_range_query *query = new path_range_query; > > > > + gimple_ranger *ranger = new gimple_ranger; > > > > for (auto loop : loops_list (cfun, 0)) > > > > { > > > > int initial_limit = param_max_loop_header_insns; > > > > @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) > > > > iteration. */ > > > > if (optimize_loop_for_size_p (loop) > > > > && !loop->force_vectorize > > > > - && !entry_loop_condition_is_static (loop, query)) > > > > + && !entry_loop_condition_is_static (loop, ranger)) > > > > { > > > > if (dump_file && (dump_flags & TDF_DETAILS)) > > > > fprintf (dump_file, > > > > @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) > > > > candidates.safe_push (loop); > > > > } > > > > /* Do not use ranger after we change the IL and not have updated SSA. */ > > > > - delete query; > > > > + delete ranger; > > > > > > > > for (auto loop : candidates) > > > > { > > > > diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc > > > > index b886027fccf..22748b9ec08 100644 > > > > --- a/gcc/tree-ssa-threadbackward.cc > > > > +++ b/gcc/tree-ssa-threadbackward.cc > > > > @@ -99,7 +99,6 @@ private: > > > > > > > > back_threader_registry m_registry; > > > > back_threader_profitability m_profit; > > > > - path_range_query *m_solver; > > > > > > > > // Current path being analyzed. > > > > auto_vec<basic_block> m_path; > > > > @@ -119,6 +118,8 @@ private: > > > > // with the ranger. Otherwise, unknown SSA names are assumed to be > > > > // VARYING. Setting to true is more precise but slower. > > > > function *m_fun; > > > > + // Ranger for the path solver. > > > > + gimple_ranger *m_ranger; > > > > unsigned m_flags; > > > > // Set to TRUE for the first of each thread[12] pass or the first of > > > > // each threadfull[12] pass. This is used to differentiate between > > > > @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) > > > > > > > > // The path solver needs EDGE_DFS_BACK in resolving mode. > > > > if (flags & BT_RESOLVE) > > > > - mark_dfs_back_edges (); > > > > - m_solver = new path_range_query (flags & BT_RESOLVE); > > > > + { > > > > + mark_dfs_back_edges (); > > > > + > > > > + if (flag_checking) > > > > + verify_marked_backedges (fun); > > > > + } > > > > + > > > > + m_ranger = new gimple_ranger; > > > > } > > > > > > > > back_threader::~back_threader () > > > > { > > > > - delete m_solver; > > > > - > > > > + delete m_ranger; > > > > loop_optimizer_finalize (); > > > > } > > > > > > > > @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, > > > > tree name = gimple_switch_index (sw); > > > > int_range_max r; > > > > > > > > - m_solver->compute_ranges (path, m_imports); > > > > - m_solver->range_of_expr (r, name, sw); > > > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > > > + solver.range_of_expr (r, name, sw); > > > > > > > > if (r.undefined_p ()) > > > > return UNREACHABLE_EDGE; > > > > @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, > > > > { > > > > int_range_max r; > > > > > > > > - m_solver->compute_ranges (path, m_imports); > > > > - m_solver->range_of_stmt (r, cond); > > > > + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); > > > > + solver.range_of_stmt (r, cond); > > > > > > > > - if (m_solver->unreachable_path_p ()) > > > > + if (solver.unreachable_path_p ()) > > > > return UNREACHABLE_EDGE; > > > > > > > > int_range<2> true_range (boolean_true_node, boolean_true_node); > > > > @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) > > > > void > > > > back_threader::dump (FILE *out) > > > > { > > > > - m_solver->dump (out); > > > > fprintf (out, "\nCandidates for pre-computation:\n"); > > > > fprintf (out, "===================================\n"); > > > > > > > > diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc > > > > index e64e4f209f7..905a98c8c68 100644 > > > > --- a/gcc/tree-ssa-threadedge.cc > > > > +++ b/gcc/tree-ssa-threadedge.cc > > > > @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, > > > > > > > > // Hybrid threader implementation. > > > > > > > > - > > > > hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, > > > > path_range_query *q) > > > > { > > > > @@ -1411,7 +1410,12 @@ tree > > > > hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > > > jt_state *state) > > > > { > > > > - compute_ranges_from_state (stmt, state); > > > > + auto_bitmap dependencies; > > > > + auto_vec<basic_block> path; > > > > + > > > > + state->get_path (path); > > > > + compute_exit_dependencies (dependencies, path, stmt); > > > > + m_query->reset_path (path, dependencies); > > > > > > > > if (gimple_code (stmt) == GIMPLE_COND > > > > || gimple_code (stmt) == GIMPLE_ASSIGN) > > > > @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, > > > > return NULL; > > > > } > > > > > > > > -// Use STATE to generate the list of imports needed for the solver, > > > > -// and calculate the ranges along the path. > > > > +// Calculate the set of exit dependencies for a path and statement to > > > > +// be simplified. This is different than the > > > > +// compute_exit_dependencies in the path solver because the forward > > > > +// threader asks questions about statements not necessarily in the > > > > +// path. Using the default compute_exit_dependencies in the path > > > > +// solver gets noticeably less threads. > > > > > > > > void > > > > -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > > > +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, > > > > + const vec<basic_block> &path, > > > > + gimple *stmt) > > > > { > > > > - auto_bitmap imports; > > > > gori_compute &gori = m_ranger->gori (); > > > > > > > > - state->get_path (m_path); > > > > - > > > > // Start with the imports to the final conditional. > > > > - bitmap_copy (imports, gori.imports (m_path[0])); > > > > + bitmap_copy (dependencies, gori.imports (path[0])); > > > > > > > > // Add any other interesting operands we may have missed. > > > > - if (gimple_bb (stmt) != m_path[0]) > > > > + if (gimple_bb (stmt) != path[0]) > > > > { > > > > for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) > > > > { > > > > @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) > > > > if (op > > > > && TREE_CODE (op) == SSA_NAME > > > > && Value_Range::supports_type_p (TREE_TYPE (op))) > > > > - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); > > > > + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); > > > > } > > > > } > > > > - m_query->compute_ranges (m_path, imports); > > > > } > > > > diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h > > > > index ca70b33f5ed..790ac2ea538 100644 > > > > --- a/gcc/tree-ssa-threadedge.h > > > > +++ b/gcc/tree-ssa-threadedge.h > > > > @@ -69,11 +69,12 @@ public: > > > > tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; > > > > > > > > private: > > > > - void compute_ranges_from_state (gimple *stmt, jt_state *); > > > > + void compute_exit_dependencies (bitmap dependencies, > > > > + const vec<basic_block> &path, > > > > + gimple *stmt); > > > > > > > > gimple_ranger *m_ranger; > > > > path_range_query *m_query; > > > > - auto_vec<basic_block> m_path; > > > > }; > > > > > > > > // This is the high level threader. The entry point is > > > > -- > > > > 2.37.1 > > > > > > >
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index c99d77dd340..d37605f4539 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -36,33 +36,52 @@ along with GCC; see the file COPYING3. If not see // Internal construct to help facilitate debugging of solver. #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL)) -path_range_query::path_range_query (bool resolve, gimple_ranger *ranger) +path_range_query::path_range_query (gimple_ranger &ranger, + const vec<basic_block> &path, + const bitmap_head *dependencies, + bool resolve) : m_cache (new ssa_global_cache), m_has_cache_entry (BITMAP_ALLOC (NULL)), - m_resolve (resolve), - m_alloced_ranger (!ranger) + m_ranger (ranger), + m_resolve (resolve) { - if (m_alloced_ranger) - m_ranger = new gimple_ranger; - else - m_ranger = ranger; + m_oracle = new path_oracle (m_ranger.oracle ()); + + reset_path (path, dependencies); +} - m_oracle = new path_oracle (m_ranger->oracle ()); +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) + : m_cache (new ssa_global_cache), + m_has_cache_entry (BITMAP_ALLOC (NULL)), + m_ranger (ranger), + m_resolve (resolve) +{ + m_oracle = new path_oracle (m_ranger.oracle ()); +} - if (m_resolve && flag_checking) - verify_marked_backedges (cfun); +path_range_query::path_range_query (gimple_ranger &ranger, + edge e, + bool resolve) + : m_cache (new ssa_global_cache), + m_has_cache_entry (BITMAP_ALLOC (NULL)), + m_ranger (ranger), + m_resolve (resolve) +{ + m_oracle = new path_oracle (m_ranger.oracle ()); + auto_vec<basic_block> bbs (2); + bbs.quick_push (e->dest); + bbs.quick_push (e->src); + reset_path (bbs, NULL); } path_range_query::~path_range_query () { delete m_oracle; - if (m_alloced_ranger) - delete m_ranger; BITMAP_FREE (m_has_cache_entry); delete m_cache; } -// Return TRUE if NAME is an exit depenency for the path. +// Return TRUE if NAME is an exit dependency for the path. bool path_range_query::exit_dependency_p (tree name) @@ -153,7 +172,7 @@ path_range_query::range_on_path_entry (vrange &r, tree name) { gcc_checking_assert (defined_outside_path (name)); basic_block entry = entry_bb (); - m_ranger->range_on_entry (r, entry, name); + m_ranger.range_on_entry (r, entry, name); } // Return the range of NAME at the end of the path being analyzed. @@ -211,19 +230,19 @@ path_range_query::unreachable_path_p () return m_undefined_path; } -// Initialize the current path to PATH. The current block is set to -// the entry block to the path. -// -// Note that the blocks are in reverse order, so the exit block is -// path[0]. +// Reset the current path to PATH. void -path_range_query::set_path (const vec<basic_block> &path) +path_range_query::reset_path (const vec<basic_block> &path, + const bitmap_head *dependencies) { gcc_checking_assert (path.length () > 1); m_path = path.copy (); m_pos = m_path.length () - 1; + m_undefined_path = false; bitmap_clear (m_has_cache_entry); + + compute_ranges (dependencies); } bool @@ -248,7 +267,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) if (at_entry ()) { - if (m_resolve && m_ranger->range_of_expr (r, name, phi)) + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) return; // Try to fold the phi exclusively with global or cached values. @@ -290,7 +309,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) range_on_path_entry (r, arg); else r.set_varying (TREE_TYPE (name)); - m_ranger->range_on_edge (tmp, e_in, arg); + m_ranger.range_on_edge (tmp, e_in, arg); r.intersect (tmp); return; } @@ -325,7 +344,7 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) } if (bb && POINTER_TYPE_P (TREE_TYPE (name))) - m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb); + m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb); if (DEBUG_SOLVER && (bb || !r.varying_p ())) { @@ -442,7 +461,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) p->set_root_oracle (nullptr); } - gori_compute &g = m_ranger->gori (); + gori_compute &g = m_ranger.gori (); bitmap exports = g.exports (bb); EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi) { @@ -496,7 +515,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) else r.set_varying (TREE_TYPE (name)); - if (m_ranger->m_cache.m_exit.maybe_adjust_range (r, name, bb)) + if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) set_cache (r, name); } } @@ -516,12 +535,11 @@ path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies) // SSA names used to calculate the final conditional along the path. void -path_range_query::compute_exit_dependencies (bitmap dependencies, - const vec<basic_block> &path) +path_range_query::compute_exit_dependencies (bitmap dependencies) { // Start with the imports from the exit block... - basic_block exit = path[0]; - gori_compute &gori = m_ranger->gori (); + basic_block exit = m_path[0]; + gori_compute &gori = m_ranger.gori (); bitmap_copy (dependencies, gori.imports (exit)); auto_vec<tree> worklist (bitmap_count_bits (dependencies)); @@ -539,7 +557,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, tree name = worklist.pop (); gimple *def_stmt = SSA_NAME_DEF_STMT (name); if (SSA_NAME_IS_DEFAULT_DEF (name) - || !path.contains (gimple_bb (def_stmt))) + || !m_path.contains (gimple_bb (def_stmt))) continue; if (gphi *phi = dyn_cast <gphi *> (def_stmt)) @@ -550,7 +568,7 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, tree arg = gimple_phi_arg (phi, i)->def; if (TREE_CODE (arg) == SSA_NAME - && path.contains (e->src) + && m_path.contains (e->src) && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg))) worklist.safe_push (arg); } @@ -582,9 +600,9 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, } // Exported booleans along the path, may help conditionals. if (m_resolve) - for (i = 0; i < path.length (); ++i) + for (i = 0; i < m_path.length (); ++i) { - basic_block bb = path[i]; + basic_block bb = m_path[i]; tree name; FOR_EACH_GORI_EXPORT_NAME (gori, bb, name) if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE) @@ -600,19 +618,15 @@ path_range_query::compute_exit_dependencies (bitmap dependencies, // calculated from the final conditional in the path. void -path_range_query::compute_ranges (const vec<basic_block> &path, - const bitmap_head *dependencies) +path_range_query::compute_ranges (const bitmap_head *dependencies) { if (DEBUG_SOLVER) fprintf (dump_file, "\n==============================================\n"); - set_path (path); - m_undefined_path = false; - if (dependencies) bitmap_copy (m_exit_dependencies, dependencies); else - compute_exit_dependencies (m_exit_dependencies, m_path); + compute_exit_dependencies (m_exit_dependencies); if (m_resolve) get_path_oracle ()->reset_path (); @@ -620,9 +634,9 @@ path_range_query::compute_ranges (const vec<basic_block> &path, if (DEBUG_SOLVER) { fprintf (dump_file, "path_range_query: compute_ranges for path: "); - for (unsigned i = path.length (); i > 0; --i) + for (unsigned i = m_path.length (); i > 0; --i) { - basic_block bb = path[i - 1]; + basic_block bb = m_path[i - 1]; fprintf (dump_file, "%d", bb->index); if (i > 1) fprintf (dump_file, "->"); @@ -650,18 +664,6 @@ path_range_query::compute_ranges (const vec<basic_block> &path, } } -// Convenience function to compute ranges along a path consisting of -// E->SRC and E->DEST. - -void -path_range_query::compute_ranges (edge e) -{ - auto_vec<basic_block> bbs (2); - bbs.quick_push (e->dest); - bbs.quick_push (e->src); - compute_ranges (bbs); -} - // A folding aid used to register and query relations along a path. // When queried, it returns relations as they would appear on exit to // the path. @@ -744,7 +746,7 @@ path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree) if (m_resolve) { fold_using_range f; - jt_fur_source src (stmt, this, &m_ranger->gori (), m_path); + jt_fur_source src (stmt, this, &m_ranger.gori (), m_path); if (!f.fold_stmt (r, stmt, src)) r.set_varying (type); } @@ -834,7 +836,7 @@ path_range_query::compute_outgoing_relations (basic_block bb, basic_block next) else gcc_unreachable (); - jt_fur_source src (NULL, this, &m_ranger->gori (), m_path); + jt_fur_source src (NULL, this, &m_ranger.gori (), m_path); src.register_outgoing_edges (cond, r, e0, e1); } } diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index 3cb794e34a9..483fde0d431 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -32,13 +32,14 @@ along with GCC; see the file COPYING3. If not see class path_range_query : public range_query { public: - path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); + path_range_query (class gimple_ranger &ranger, + const vec<basic_block> &path, + const bitmap_head *dependencies = NULL, + bool resolve = true); + path_range_query (gimple_ranger &ranger, bool resolve = true); + path_range_query (gimple_ranger &ranger, edge e, bool resolve = true); virtual ~path_range_query (); - void compute_ranges (const vec<basic_block> &, - const bitmap_head *dependencies = NULL); - void compute_ranges (edge e); - void compute_exit_dependencies (bitmap dependencies, - const vec<basic_block> &); + void reset_path (const vec<basic_block> &, const bitmap_head *dependencies); 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 (); @@ -47,6 +48,8 @@ public: private: bool internal_range_of_expr (vrange &r, tree name, gimple *); + void compute_ranges (const bitmap_head *dependencies); + void compute_exit_dependencies (bitmap_head *dependencies); bool defined_outside_path (tree name); void range_on_path_entry (vrange &r, tree name); path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } @@ -71,7 +74,6 @@ private: bool relations_may_be_invalidated (edge); // Path navigation. - void set_path (const vec<basic_block> &); basic_block entry_bb () { return m_path[m_path.length () - 1]; } basic_block exit_bb () { return m_path[0]; } basic_block curr_bb () { return m_path[m_pos]; } @@ -99,7 +101,7 @@ private: // A ranger used to resolve ranges for SSA names whose values come // from outside the path. - gimple_ranger *m_ranger; + gimple_ranger &m_ranger; // Current path position. unsigned m_pos; @@ -109,10 +111,6 @@ private: // Set if there were any undefined expressions while pre-calculating path. bool m_undefined_path; - - // True if m_ranger was allocated in this class and must be freed at - // destruction. - bool m_alloced_ranger; }; #endif // GCC_TREE_SSA_THREADSOLVER_H diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc index 44dc27b464c..513e0c88254 100644 --- a/gcc/tree-ssa-dom.cc +++ b/gcc/tree-ssa-dom.cc @@ -798,7 +798,7 @@ pass_dominator::execute (function *fun) /* Recursively walk the dominator tree optimizing statements. */ gimple_ranger *ranger = enable_ranger (fun); - path_range_query path_query (/*resolve=*/true, ranger); + path_range_query path_query (*ranger); dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query); dom_jt_state state (const_and_copies, avail_exprs_stack); jump_threader threader (&simplifier, &state); diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc index 3b91a89eaf5..96816b89287 100644 --- a/gcc/tree-ssa-loop-ch.cc +++ b/gcc/tree-ssa-loop-ch.cc @@ -49,7 +49,7 @@ along with GCC; see the file COPYING3. If not see be statically determined. */ static bool -entry_loop_condition_is_static (class loop *l, path_range_query *query) +entry_loop_condition_is_static (class loop *l, gimple_ranger *ranger) { edge e = loop_preheader_edge (l); gcond *last = safe_dyn_cast <gcond *> (last_stmt (e->dest)); @@ -72,8 +72,8 @@ entry_loop_condition_is_static (class loop *l, path_range_query *query) desired_static_value = boolean_true_node; int_range<2> r; - query->compute_ranges (e); - query->range_of_stmt (r, last); + path_range_query query (*ranger, e); + query.range_of_stmt (r, last); return r == int_range<2> (desired_static_value, desired_static_value); } @@ -385,7 +385,7 @@ ch_base::copy_headers (function *fun) auto_vec<std::pair<edge, loop_p> > copied; mark_dfs_back_edges (); - path_range_query *query = new path_range_query; + gimple_ranger *ranger = new gimple_ranger; for (auto loop : loops_list (cfun, 0)) { int initial_limit = param_max_loop_header_insns; @@ -409,7 +409,7 @@ ch_base::copy_headers (function *fun) iteration. */ if (optimize_loop_for_size_p (loop) && !loop->force_vectorize - && !entry_loop_condition_is_static (loop, query)) + && !entry_loop_condition_is_static (loop, ranger)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, @@ -422,7 +422,7 @@ ch_base::copy_headers (function *fun) candidates.safe_push (loop); } /* Do not use ranger after we change the IL and not have updated SSA. */ - delete query; + delete ranger; for (auto loop : candidates) { diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc index b886027fccf..22748b9ec08 100644 --- a/gcc/tree-ssa-threadbackward.cc +++ b/gcc/tree-ssa-threadbackward.cc @@ -99,7 +99,6 @@ private: back_threader_registry m_registry; back_threader_profitability m_profit; - path_range_query *m_solver; // Current path being analyzed. auto_vec<basic_block> m_path; @@ -119,6 +118,8 @@ private: // with the ranger. Otherwise, unknown SSA names are assumed to be // VARYING. Setting to true is more precise but slower. function *m_fun; + // Ranger for the path solver. + gimple_ranger *m_ranger; unsigned m_flags; // Set to TRUE for the first of each thread[12] pass or the first of // each threadfull[12] pass. This is used to differentiate between @@ -145,14 +146,19 @@ back_threader::back_threader (function *fun, unsigned flags, bool first) // The path solver needs EDGE_DFS_BACK in resolving mode. if (flags & BT_RESOLVE) - mark_dfs_back_edges (); - m_solver = new path_range_query (flags & BT_RESOLVE); + { + mark_dfs_back_edges (); + + if (flag_checking) + verify_marked_backedges (fun); + } + + m_ranger = new gimple_ranger; } back_threader::~back_threader () { - delete m_solver; - + delete m_ranger; loop_optimizer_finalize (); } @@ -290,8 +296,8 @@ back_threader::find_taken_edge_switch (const vec<basic_block> &path, tree name = gimple_switch_index (sw); int_range_max r; - m_solver->compute_ranges (path, m_imports); - m_solver->range_of_expr (r, name, sw); + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); + solver.range_of_expr (r, name, sw); if (r.undefined_p ()) return UNREACHABLE_EDGE; @@ -314,10 +320,10 @@ back_threader::find_taken_edge_cond (const vec<basic_block> &path, { int_range_max r; - m_solver->compute_ranges (path, m_imports); - m_solver->range_of_stmt (r, cond); + path_range_query solver (*m_ranger, path, m_imports, m_flags & BT_RESOLVE); + solver.range_of_stmt (r, cond); - if (m_solver->unreachable_path_p ()) + if (solver.unreachable_path_p ()) return UNREACHABLE_EDGE; int_range<2> true_range (boolean_true_node, boolean_true_node); @@ -588,7 +594,6 @@ debug (const vec <basic_block> &path) void back_threader::dump (FILE *out) { - m_solver->dump (out); fprintf (out, "\nCandidates for pre-computation:\n"); fprintf (out, "===================================\n"); diff --git a/gcc/tree-ssa-threadedge.cc b/gcc/tree-ssa-threadedge.cc index e64e4f209f7..905a98c8c68 100644 --- a/gcc/tree-ssa-threadedge.cc +++ b/gcc/tree-ssa-threadedge.cc @@ -1399,7 +1399,6 @@ jt_state::register_equivs_stmt (gimple *stmt, basic_block bb, // Hybrid threader implementation. - hybrid_jt_simplifier::hybrid_jt_simplifier (gimple_ranger *r, path_range_query *q) { @@ -1411,7 +1410,12 @@ tree hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, jt_state *state) { - compute_ranges_from_state (stmt, state); + auto_bitmap dependencies; + auto_vec<basic_block> path; + + state->get_path (path); + compute_exit_dependencies (dependencies, path, stmt); + m_query->reset_path (path, dependencies); if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_ASSIGN) @@ -1432,22 +1436,25 @@ hybrid_jt_simplifier::simplify (gimple *stmt, gimple *, basic_block, return NULL; } -// Use STATE to generate the list of imports needed for the solver, -// and calculate the ranges along the path. +// Calculate the set of exit dependencies for a path and statement to +// be simplified. This is different than the +// compute_exit_dependencies in the path solver because the forward +// threader asks questions about statements not necessarily in the +// path. Using the default compute_exit_dependencies in the path +// solver gets noticeably less threads. void -hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) +hybrid_jt_simplifier::compute_exit_dependencies (bitmap dependencies, + const vec<basic_block> &path, + gimple *stmt) { - auto_bitmap imports; gori_compute &gori = m_ranger->gori (); - state->get_path (m_path); - // Start with the imports to the final conditional. - bitmap_copy (imports, gori.imports (m_path[0])); + bitmap_copy (dependencies, gori.imports (path[0])); // Add any other interesting operands we may have missed. - if (gimple_bb (stmt) != m_path[0]) + if (gimple_bb (stmt) != path[0]) { for (unsigned i = 0; i < gimple_num_ops (stmt); ++i) { @@ -1455,8 +1462,7 @@ hybrid_jt_simplifier::compute_ranges_from_state (gimple *stmt, jt_state *state) if (op && TREE_CODE (op) == SSA_NAME && Value_Range::supports_type_p (TREE_TYPE (op))) - bitmap_set_bit (imports, SSA_NAME_VERSION (op)); + bitmap_set_bit (dependencies, SSA_NAME_VERSION (op)); } } - m_query->compute_ranges (m_path, imports); } diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h index ca70b33f5ed..790ac2ea538 100644 --- a/gcc/tree-ssa-threadedge.h +++ b/gcc/tree-ssa-threadedge.h @@ -69,11 +69,12 @@ public: tree simplify (gimple *stmt, gimple *, basic_block, jt_state *) override; private: - void compute_ranges_from_state (gimple *stmt, jt_state *); + void compute_exit_dependencies (bitmap dependencies, + const vec<basic_block> &path, + gimple *stmt); gimple_ranger *m_ranger; path_range_query *m_query; - auto_vec<basic_block> m_path; }; // This is the high level threader. The entry point is