From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2136) id A3130385842E; Tue, 21 Sep 2021 16:56:33 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A3130385842E MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Aldy Hernandez To: gcc-cvs@gcc.gnu.org Subject: [gcc r12-3760] path solver: Add relation support. X-Act-Checkin: gcc X-Git-Author: Aldy Hernandez X-Git-Refname: refs/heads/master X-Git-Oldrev: 198bc5ece960557044483b1c72417759b4630f04 X-Git-Newrev: f46d33637c71165622aa4c55008798cbd91a8696 Message-Id: <20210921165633.A3130385842E@sourceware.org> Date: Tue, 21 Sep 2021 16:56:33 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 21 Sep 2021 16:56:33 -0000 https://gcc.gnu.org/g:f46d33637c71165622aa4c55008798cbd91a8696 commit r12-3760-gf46d33637c71165622aa4c55008798cbd91a8696 Author: Aldy Hernandez Date: Tue Sep 21 09:04:20 2021 +0200 path solver: Add relation support. This patch adds relational support to the path solver. It uses a path_oracle that keeps track of relations within a path which are augmented by relations on entry to the path. With it, range_of_stmt, range_of_expr, and friends can give relation aware answers. gcc/ChangeLog: * gimple-range-fold.h (class fur_source): Make oracle protected. * gimple-range-path.cc (path_range_query::path_range_query): Add resolve argument. Initialize oracle. (path_range_query::~path_range_query): Delete oracle. (path_range_query::range_of_stmt): Adapt to use relations. (path_range_query::precompute_ranges): Pre-compute relations. (class jt_fur_source): New (jt_fur_source::jt_fur_source): New. (jt_fur_source::register_relation): New. (jt_fur_source::query_relation): New. (path_range_query::precompute_relations): New. (path_range_query::precompute_phi_relations): New. * gimple-range-path.h (path_range_query): Add resolve argument. Add oracle, precompute_relations, precompute_phi_relations. * tree-ssa-threadbackward.c (back_threader::back_threader): Pass resolve argument to solver. Diff: --- gcc/gimple-range-fold.h | 2 +- gcc/gimple-range-path.cc | 204 ++++++++++++++++++++++++++++++++++++++---- gcc/gimple-range-path.h | 15 +++- gcc/tree-ssa-threadbackward.c | 2 +- 4 files changed, 200 insertions(+), 23 deletions(-) diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h index d62d29b7133..bc0874b5f31 100644 --- a/gcc/gimple-range-fold.h +++ b/gcc/gimple-range-fold.h @@ -160,7 +160,7 @@ public: tree op2) OVERRIDE; virtual void register_relation (edge e, relation_kind k, tree op1, tree op2) OVERRIDE; -private: +protected: relation_oracle *m_oracle; }; diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index 10b018b5211..b3040c9bc00 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -30,11 +30,13 @@ along with GCC; see the file COPYING3. If not see #include "tree-pretty-print.h" #include "gimple-range-path.h" #include "ssa.h" +#include "tree-cfg.h" +#include "gimple-iterator.h" // Internal construct to help facilitate debugging of solver. #define DEBUG_SOLVER (0 && dump_file) -path_range_query::path_range_query (gimple_ranger &ranger) +path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) : m_ranger (ranger) { if (DEBUG_SOLVER) @@ -43,12 +45,15 @@ path_range_query::path_range_query (gimple_ranger &ranger) m_cache = new ssa_global_cache; m_has_cache_entry = BITMAP_ALLOC (NULL); m_path = NULL; + m_resolve = resolve; + m_oracle = new path_oracle (ranger.oracle ()); } path_range_query::~path_range_query () { BITMAP_FREE (m_has_cache_entry); delete m_cache; + delete m_oracle; } // Mark cache entry for NAME as unused. @@ -161,22 +166,6 @@ path_range_query::unreachable_path_p () return m_undefined_path; } -// Return the range of STMT at the end of the path being analyzed. - -bool -path_range_query::range_of_stmt (irange &r, gimple *stmt, tree) -{ - tree type = gimple_range_type (stmt); - - if (!irange::supports_type_p (type)) - return false; - - if (!fold_range (r, stmt, this)) - r.set_varying (type); - - return true; -} - // Initialize the current path to PATH. The current block is set to // the entry block to the path. // @@ -371,6 +360,12 @@ path_range_query::precompute_ranges (const vec &path, m_imports = imports; m_undefined_path = false; + if (m_resolve) + { + m_oracle->reset_path (); + precompute_relations (path); + } + if (DEBUG_SOLVER) { fprintf (dump_file, "\npath_range_query: precompute_ranges for path: "); @@ -400,3 +395,178 @@ path_range_query::precompute_ranges (const vec &path, if (DEBUG_SOLVER) dump (dump_file); } + +// 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. +// +// Relations are registered on entry so the path_oracle knows which +// block to query the root oracle at when a relation lies outside the +// path. However, when queried we return the relation on exit to the +// path, since the root_oracle ignores the registered. + +class jt_fur_source : public fur_depend +{ +public: + jt_fur_source (gimple *s, path_range_query *, gori_compute *, + const vec &); + relation_kind query_relation (tree op1, tree op2) override; + void register_relation (gimple *, relation_kind, tree op1, tree op2) override; + void register_relation (edge, relation_kind, tree op1, tree op2) override; +private: + basic_block m_entry; +}; + +jt_fur_source::jt_fur_source (gimple *s, + path_range_query *query, + gori_compute *gori, + const vec &path) + : fur_depend (s, gori, query) +{ + gcc_checking_assert (!path.is_empty ()); + + m_entry = path[path.length () - 1]; + + if (dom_info_available_p (CDI_DOMINATORS)) + m_oracle = query->oracle (); + else + m_oracle = NULL; +} + +// Ignore statement and register relation on entry to path. + +void +jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2) +{ + if (m_oracle) + m_oracle->register_relation (m_entry, k, op1, op2); +} + +// Ignore edge and register relation on entry to path. + +void +jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2) +{ + if (m_oracle) + m_oracle->register_relation (m_entry, k, op1, op2); +} + +relation_kind +jt_fur_source::query_relation (tree op1, tree op2) +{ + if (!m_oracle) + return VREL_NONE; + + if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME) + return VREL_NONE; + + return m_oracle->query_relation (m_entry, op1, op2); +} + +// Return the range of STMT at the end of the path being analyzed. + +bool +path_range_query::range_of_stmt (irange &r, gimple *stmt, tree) +{ + tree type = gimple_range_type (stmt); + + if (!irange::supports_type_p (type)) + return false; + + // If resolving unknowns, fold the statement as it would have + // appeared at the end of the path. + if (m_resolve) + { + fold_using_range f; + jt_fur_source src (stmt, this, &m_ranger.gori (), *m_path); + if (!f.fold_stmt (r, stmt, src)) + r.set_varying (type); + } + // Otherwise, use the global ranger to fold it as it would appear in + // the original IL. This is more conservative, but faster. + else if (!fold_range (r, stmt, this)) + r.set_varying (type); + + return true; +} + +// Precompute relations on a path. This involves two parts: relations +// along the conditionals joining a path, and relations determined by +// examining PHIs. + +void +path_range_query::precompute_relations (const vec &path) +{ + if (!dom_info_available_p (CDI_DOMINATORS)) + return; + + jt_fur_source src (NULL, this, &m_ranger.gori (), path); + basic_block prev = NULL; + for (unsigned i = path.length (); i > 0; --i) + { + basic_block bb = path[i - 1]; + gimple *stmt = last_stmt (bb); + + precompute_phi_relations (bb, prev); + + // Compute relations in outgoing edges along the path. Skip the + // final conditional which we don't know yet. + if (i > 1 + && stmt + && gimple_code (stmt) == GIMPLE_COND + && irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (stmt)))) + { + basic_block next = path[i - 2]; + int_range<2> r; + gcond *cond = as_a (stmt); + + if (EDGE_SUCC (bb, 0)->dest == next) + gcond_edge_range (r, EDGE_SUCC (bb, 0)); + else if (EDGE_SUCC (bb, 1)->dest == next) + gcond_edge_range (r, EDGE_SUCC (bb, 1)); + else + gcc_unreachable (); + + edge e0 = EDGE_SUCC (bb, 0); + edge e1 = EDGE_SUCC (bb, 1); + src.register_outgoing_edges (cond, r, e0, e1); + } + prev = bb; + } +} + +// Precompute relations for each PHI in BB. For example: +// +// x_5 = PHI +// +// If the path flows through BB5, we can register that x_5 == y_9. + +void +path_range_query::precompute_phi_relations (basic_block bb, basic_block prev) +{ + if (prev == NULL) + return; + + basic_block entry = entry_bb (); + edge e_in = find_edge (prev, bb); + gcc_checking_assert (e_in); + + for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter); + gsi_next (&iter)) + { + gphi *phi = iter.phi (); + tree result = gimple_phi_result (phi); + unsigned nargs = gimple_phi_num_args (phi); + + for (size_t i = 0; i < nargs; ++i) + if (e_in == gimple_phi_arg_edge (phi, i)) + { + tree arg = gimple_phi_arg_def (phi, i); + + if (gimple_range_ssa_p (arg)) + m_oracle->register_relation (entry, EQ_EXPR, arg, result); + + break; + } + } +} diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index c75721f6dc0..d12fd7743ca 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -35,13 +35,14 @@ along with GCC; see the file COPYING3. If not see class path_range_query : public range_query { public: - path_range_query (class gimple_ranger &ranger); + path_range_query (class gimple_ranger &ranger, bool resolve); virtual ~path_range_query (); void precompute_ranges (const vec &path, const bitmap_head *imports); bool range_of_expr (irange &r, tree name, gimple * = NULL) override; bool range_of_stmt (irange &r, gimple *, tree name = NULL) override; bool unreachable_path_p (); + path_oracle *oracle () { return m_oracle; } void dump (FILE *) override; void debug (); @@ -58,6 +59,8 @@ private: void precompute_ranges_in_block (basic_block bb); void adjust_for_non_null_uses (basic_block bb); void ssa_range_in_phi (irange &r, gphi *phi); + void precompute_relations (const vec &); + void precompute_phi_relations (basic_block bb, basic_block prev); // Path navigation. void set_path (const vec &); @@ -79,12 +82,16 @@ private: // Path being analyzed. const vec *m_path; - // Current path position. - unsigned m_pos; - const bitmap_head *m_imports; gimple_ranger &m_ranger; non_null_ref m_non_null; + path_oracle *m_oracle; + + // Current path position. + unsigned m_pos; + + // Use ranger to resolve anything not known on entry. + bool m_resolve; // Set if there were any undefined expressions while pre-calculating path. bool m_undefined_path; diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index c6530d3a6bb..95542079faf 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -122,7 +122,7 @@ const edge back_threader::UNREACHABLE_EDGE = (edge) -1; back_threader::back_threader (bool speed_p) : m_registry (param_max_fsm_thread_paths), m_profit (speed_p), - m_solver (m_ranger) + m_solver (m_ranger, /*resolve=*/false) { m_last_stmt = NULL; m_imports = BITMAP_ALLOC (NULL);