From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2136) id F065E385842A; Tue, 21 Sep 2021 16:56:48 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org F065E385842A 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-3763] path solver: Use ranger to solve unknowns. X-Act-Checkin: gcc X-Git-Author: Aldy Hernandez X-Git-Refname: refs/heads/master X-Git-Oldrev: e4249b10038bd906f50c00759b37807dd2fffede X-Git-Newrev: 97cfb54c3ff15b9691fd1c12a29de56966bf8e0d Message-Id: <20210921165648.F065E385842A@sourceware.org> Date: Tue, 21 Sep 2021 16:56:48 +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:49 -0000 https://gcc.gnu.org/g:97cfb54c3ff15b9691fd1c12a29de56966bf8e0d commit r12-3763-g97cfb54c3ff15b9691fd1c12a29de56966bf8e0d Author: Aldy Hernandez Date: Tue Sep 21 09:24:12 2021 +0200 path solver: Use ranger to solve unknowns. The default behavior for the path solver is to resort to VARYING when the range for an unknown SSA is outside the given path. This is both cheap and fast, but fails to get a significant amount of ranges that traditionally the DOM and VRP threaders could get. This patch uses the ranger to resolve any unknown names upon entry to the path. It also uses equivalences to improve ranges. gcc/ChangeLog: * gimple-range-path.cc (path_range_query::defined_outside_path): New. (path_range_query::range_on_path_entry): New. (path_range_query::internal_range_of_expr): Resolve unknowns with ranger. (path_range_query::improve_range_with_equivs): New. (path_range_query::ssa_range_in_phi): Resolve unknowns with ranger. * gimple-range-path.h (class path_range_query): Add defined_outside_path, range_on_path_entry, and improve_range_with_equivs. Diff: --- gcc/gimple-range-path.cc | 89 +++++++++++++++++++++++++++++++++++++++++++++--- gcc/gimple-range-path.h | 3 ++ 2 files changed, 88 insertions(+), 4 deletions(-) diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index a8ead3da4dc..e65c7996bb7 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -121,6 +121,34 @@ path_range_query::debug () dump (stderr); } +// Return TRUE if NAME is defined outside the current path. + +bool +path_range_query::defined_outside_path (tree name) +{ + gimple *def = SSA_NAME_DEF_STMT (name); + basic_block bb = gimple_bb (def); + + return !bb || !m_path->contains (bb); +} + +// Return the range of NAME on entry to the path. + +void +path_range_query::range_on_path_entry (irange &r, tree name) +{ + int_range_max tmp; + basic_block entry = entry_bb (); + r.set_undefined (); + for (unsigned i = 0; i < EDGE_COUNT (entry->preds); ++i) + { + edge e = EDGE_PRED (entry, i); + if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) + && m_ranger.range_on_edge (tmp, e, name)) + r.union_ (tmp); + } +} + // Return the range of NAME at the end of the path being analyzed. bool @@ -132,6 +160,16 @@ path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt) if (get_cache (r, name)) return true; + if (m_resolve && defined_outside_path (name)) + { + range_on_path_entry (r, name); + + if (r.varying_p ()) + improve_range_with_equivs (r, name); + + set_cache (r, name); + return true; + } basic_block bb = stmt ? gimple_bb (stmt) : exit_bb (); if (stmt && range_defined_in_block (r, name, bb)) @@ -139,6 +177,9 @@ path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt) if (TREE_CODE (name) == SSA_NAME) r.intersect (gimple_range_global (name)); + if (m_resolve && r.varying_p ()) + improve_range_with_equivs (r, name); + set_cache (r, name); return true; } @@ -160,6 +201,33 @@ path_range_query::range_of_expr (irange &r, tree name, gimple *stmt) return false; } +// Improve the range of NAME with the range of any of its equivalences. + +void +path_range_query::improve_range_with_equivs (irange &r, tree name) +{ + if (TREE_CODE (name) != SSA_NAME) + return; + + basic_block entry = entry_bb (); + relation_oracle *oracle = m_ranger.oracle (); + + if (const bitmap_head *equivs = oracle->equiv_set (name, entry)) + { + int_range_max t; + bitmap_iterator bi; + unsigned i; + + EXECUTE_IF_SET_IN_BITMAP (equivs, 0, i, bi) + if (i != SSA_NAME_VERSION (name) && r.varying_p ()) + { + tree equiv = ssa_name (i); + range_on_path_entry (t, equiv); + r.intersect (t); + } + } +} + bool path_range_query::unreachable_path_p () { @@ -189,10 +257,11 @@ path_range_query::ssa_range_in_phi (irange &r, gphi *phi) tree name = gimple_phi_result (phi); basic_block bb = gimple_bb (phi); - // We experimented with querying ranger's range_on_entry here, but - // the performance penalty was too high, for hardly any improvements. if (at_entry ()) { + if (m_resolve && m_ranger.range_of_expr (r, name, phi)) + return; + // Try fold just in case we can resolve simple things like PHI <5(99), 6(88)>. if (!fold_range (r, phi, this)) r.set_varying (TREE_TYPE (name)); @@ -210,8 +279,20 @@ path_range_query::ssa_range_in_phi (irange &r, gphi *phi) tree arg = gimple_phi_arg_def (phi, i); if (!get_cache (r, arg)) - r.set_varying (TREE_TYPE (name)); - + { + if (m_resolve) + { + int_range_max tmp; + // Using both the range on entry to the path, and the + // range on this edge yields significantly better + // results. + range_on_path_entry (r, arg); + m_ranger.range_on_edge (tmp, e_in, arg); + r.intersect (tmp); + return; + } + r.set_varying (TREE_TYPE (name)); + } return; } gcc_unreachable (); diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index f23cce18391..6f81f21d42f 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -48,6 +48,8 @@ public: private: bool internal_range_of_expr (irange &r, tree name, gimple *); + bool defined_outside_path (tree name); + void range_on_path_entry (irange &r, tree name); // Cache manipulation. void set_cache (const irange &r, tree name); @@ -61,6 +63,7 @@ private: void ssa_range_in_phi (irange &r, gphi *phi); void precompute_relations (const vec &); void precompute_phi_relations (basic_block bb, basic_block prev); + void improve_range_with_equivs (irange &r, tree name); void add_copies_to_imports (); bool add_to_imports (tree name, bitmap imports);