diff options
author | Aldy Hernandez <aldyh@redhat.com> | 2021-09-21 09:04:20 +0200 |
---|---|---|
committer | Aldy Hernandez <aldyh@redhat.com> | 2021-09-21 18:55:14 +0200 |
commit | f46d33637c71165622aa4c55008798cbd91a8696 (patch) | |
tree | b623530c77549d9c837cfa8bfaf267019e2dc570 /gcc | |
parent | 198bc5ece960557044483b1c72417759b4630f04 (diff) | |
download | gcc-f46d33637c71165622aa4c55008798cbd91a8696.zip gcc-f46d33637c71165622aa4c55008798cbd91a8696.tar.gz gcc-f46d33637c71165622aa4c55008798cbd91a8696.tar.bz2 |
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.
Diffstat (limited to 'gcc')
-rw-r--r-- | gcc/gimple-range-fold.h | 2 | ||||
-rw-r--r-- | gcc/gimple-range-path.cc | 204 | ||||
-rw-r--r-- | gcc/gimple-range-path.h | 15 | ||||
-rw-r--r-- | 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 d62d29b..bc0874b 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 10b018b..b3040c9 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 c75721f..d12fd7743 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 c6530d3..9554207 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); |