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.
Committed.
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.
---
gcc/gimple-range-path.cc | 89 ++++++++++++++++++++++++++++++++++++++--
gcc/gimple-range-path.h | 3 ++
2 files changed, 88 insertions(+), 4 deletions(-)
@@ -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 ();
@@ -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<basic_block> &);
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);