public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Aldy Hernandez <aldyh@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc r12-3760] path solver: Add relation support. Date: Tue, 21 Sep 2021 16:56:33 +0000 (GMT) [thread overview] Message-ID: <20210921165633.A3130385842E@sourceware.org> (raw) https://gcc.gnu.org/g:f46d33637c71165622aa4c55008798cbd91a8696 commit r12-3760-gf46d33637c71165622aa4c55008798cbd91a8696 Author: Aldy Hernandez <aldyh@redhat.com> 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<basic_block> &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<basic_block> &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<basic_block> &); + 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<basic_block> &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<basic_block> &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<gcond *> (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<y_9(5),...> +// +// 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<basic_block> &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<basic_block> &); + void precompute_phi_relations (basic_block bb, basic_block prev); // Path navigation. void set_path (const vec<basic_block> &); @@ -79,12 +82,16 @@ private: // Path being analyzed. const vec<basic_block> *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);
reply other threads:[~2021-09-21 16:56 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20210921165633.A3130385842E@sourceware.org \ --to=aldyh@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).