Ranger spends a lot of time tracking pointer type ssa_names which are
initialized to non-null, ie (a_2 = &foo). This turns out to be a waste
of effort.
Pointers can effectively have one of 3 values we care about: VARYING,
[0,0], or [1, +INF]. If an ssa_name is globally [0,0] or [1, +INF],
the only "refinement" that can be made on an outgoing edge is to
evaluate to UNDEFINED. There is no need to track UNDEFINED on the
un-taken edge as the branch will be folded and the edge removed. The
range will remain the same on the other edge.
Initializing to [0,0] produces a singleton range, and constants like
this tend to be propagated away anyway, so their usage patterns are less
of an issue. [1, +INF] however looks like a range which can be
modified, and we spend a lot of pointless time in this PR processing it.
This patch extends current invariant tracking to also include pointers
which evaluate to [1, +INF] at their definition, and thus will not be
included in the on-entry cache, and resolves the compilation time issue.
I also renamed the local member name as it now has a more specific
definition.
Bootstrapped on x86_64-pc-linux-gnu with no regressions.
I'm not sure the current protocol for checking things in, so I will ask
for blessing from the release managers:-) OK for trunk?
Andrew
commit ca1d3735fd826c42e71b48c6d79240402fa4a6f9
Author: Andrew MacLeod <amacl...@redhat.com>
Date: Fri Jan 29 09:23:48 2021 -0500
tree-optimization/98866 - Compile time hog in VRP
Don't track [1, +INF] for pointer types, treat them as invariant for caching
purposes as they cannot be further refined without evaluating to UNDEFINED.
PR tree-optimization/98866
* gimple-range-gori.h (gori_map::set_range_invariant): New.
(gori_map::m_maybe_invariant): Rename from all_outgoing.
(gori_map::gori_map): Rename all_outgoing to m_maybe_invariant.
(gori_map::is_export_p): Ditto.
(gori_map::calculate_gori): Ditto.
(gori_compute::set_range_invariant): New.
* gimple-range-gori.h (gori_compute:set_range_invariant): New.
* gimple-range.cc (gimple_ranger::range_of_stmt): Set range
invariant for pointers evaluating to [1, +INF].
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 65faa2d24d4..7f7f3dc0d69 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -232,13 +232,14 @@ public:
bool is_export_p (tree name, basic_block bb = NULL);
bool def_chain_in_export_p (tree name, basic_block bb);
bitmap exports (basic_block bb);
+ void set_range_invariant (tree name);
void dump (FILE *f);
void dump (FILE *f, basic_block bb);
private:
bitmap_obstack m_bitmaps;
vec<bitmap> m_outgoing; // BB: Outgoing ranges calculatable on edges
- bitmap all_outgoing; // All outgoing ranges combined.
+ bitmap m_maybe_variant; // Names which might have outgoing ranges.
void maybe_add_gori (tree name, basic_block bb);
void calculate_gori (basic_block bb);
};
@@ -251,7 +252,7 @@ gori_map::gori_map ()
m_outgoing.create (0);
m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
bitmap_obstack_initialize (&m_bitmaps);
- all_outgoing = BITMAP_ALLOC (&m_bitmaps);
+ m_maybe_variant = BITMAP_ALLOC (&m_bitmaps);
}
// Free any memory the GORI map allocated.
@@ -280,10 +281,18 @@ gori_map::is_export_p (tree name, basic_block bb)
{
// If no BB is specified, test if it is exported anywhere in the IL.
if (!bb)
- return bitmap_bit_p (all_outgoing, SSA_NAME_VERSION (name));
+ return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name));
return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name));
}
+// Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
+
+void
+gori_map::set_range_invariant (tree name)
+{
+ bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name));
+}
+
// Return true if any element in the def chain of NAME is in the
// export list for BB.
@@ -348,7 +357,7 @@ gori_map::calculate_gori (basic_block bb)
maybe_add_gori (name, gimple_bb (stmt));
}
// Add this bitmap to the aggregate list of all outgoing names.
- bitmap_ior_into (all_outgoing, m_outgoing[bb->index]);
+ bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]);
}
// Dump the table information for BB to file F.
@@ -447,7 +456,7 @@ gori_compute::gori_compute ()
m_gori_map = new gori_map;
unsigned x, lim = last_basic_block_for_fn (cfun);
// Calculate outgoing range info upfront. This will fully populate the
- // all_outgoing bitmap which will help eliminate processing of names
+ // m_maybe_variant bitmap which will help eliminate processing of names
// which never have their ranges adjusted.
for (x = 0; x < lim ; x++)
{
@@ -996,6 +1005,14 @@ gori_compute::has_edge_range_p (tree name, edge e)
|| m_gori_map->def_chain_in_export_p (name, e->src));
}
+// Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
+
+void
+gori_compute::set_range_invariant (tree name)
+{
+ m_gori_map->set_range_invariant (name);
+}
+
// Dump what is known to GORI computes to listing file F.
void
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index 3b9db0d406b..48c746d1f37 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -72,6 +72,7 @@ public:
~gori_compute ();
bool outgoing_edge_range_p (irange &r, edge e, tree name);
bool has_edge_range_p (tree name, edge e = NULL);
+ void set_range_invariant (tree name);
void dump (FILE *f);
protected:
virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb);
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 029aaa58640..6158a754dd6 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -1072,6 +1072,12 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
// can sometimes get different results. See PR 97741.
r.intersect (tmp);
m_cache.set_global_range (name, r);
+
+ // Pointers which resolve to non-zero at the defintion point do not need
+ // tracking in the cache as they will never change. See PR 98866.
+ if (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ())
+ m_cache.set_range_invariant (name);
+
return true;
}
