One of the cases which causes ranger to bog down is processing large
switch statements.
We create ranges for each individual case, and at meet points need to
intersect those ranges and combine them. As Switches get larger, the
number of subranges at meets points increase and this becomes a much
more expensive operation, and it can becomes quadratic or worse in
pathological cases.
This patch introduces a --param=evrp-switch-limit variables which is
used to decide a switch is too large to process, and we will pretend we
don't see it. I've run various values thru a testsuite, and the current
default of 50 appears to give a good trade-off between speedup in
compilation times vs results.
Over 380 GCC source files, this default setting only misses 20 out of
5000 simplification opportunities, which producing a whopping 40%
speedup in EVRP compilation.
I expect to be able to remove this in the next release with some plans I
have for reducing propagation, but this is a decent solution for now.
We could consider increasing that default value when running at -O3.
I also ran experiments to limit the number of sub-ranges instead of, and
along with, this change. Limiting the number of subranges had no
measurable effect on things.
Bootstrapped on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
>From 3ca950c3525527846f13e8c547368ef432547a23 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacl...@redhat.com>
Date: Wed, 29 Sep 2021 17:25:50 -0400
Subject: [PATCH 3/4] Introduce a param-switch-limit for EVRP.
Very large switches cause a lot of range calculations with multiple subranges
to happen. This can cause quadratic or even exponetial time increases in
large testcases. This patch introduces a param variable to limit
the size of switches EVRP will process.
* gimple-range-edge.cc (gimple_outgoing_range::gimple_outgoing_range):
Add parameter to limit size when recognizing switches.
(gimple_outgoing_range::edge_range_p): Check size limit.
* gimple-range-edge.h (gimple_outgoing_range): Add size field.
* gimple-range-gori.cc (gori_map::calculate_gori): Ignore switches
that exceed the size limit.
(gori_compute::gori_compute): Add initializer.
* params.opt (evrp-switch-limit): New.
* doc/invoke.texi: Update docs.
---
gcc/doc/invoke.texi | 3 +++
gcc/gimple-range-edge.cc | 7 ++++++-
gcc/gimple-range-edge.h | 3 ++-
gcc/gimple-range-gori.cc | 6 +++++-
gcc/params.opt | 4 ++++
5 files changed, 20 insertions(+), 3 deletions(-)
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index b4eaa7793b7..80bc7fe41e0 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -14505,6 +14505,9 @@ Maximum number of basic blocks before EVRP uses a sparse cache.
@item evrp-mode
Specifies the mode Early VRP should operate in.
+@item evrp-switch-limit
+Specifies the maximum number of switch cases before EVRP ignores a switch.
+
@item unroll-jam-min-percent
The minimum percentage of memory references that must be optimized
away for the unroll-and-jam transformation to be considered profitable.
diff --git a/gcc/gimple-range-edge.cc b/gcc/gimple-range-edge.cc
index d11153e677e..afffc8dbcae 100644
--- a/gcc/gimple-range-edge.cc
+++ b/gcc/gimple-range-edge.cc
@@ -65,9 +65,10 @@ gcond_edge_range (irange &r, edge e)
}
-gimple_outgoing_range::gimple_outgoing_range ()
+gimple_outgoing_range::gimple_outgoing_range (int max_sw_edges)
{
m_edge_table = NULL;
+ m_max_edges = max_sw_edges;
}
@@ -192,6 +193,10 @@ gimple_outgoing_range::edge_range_p (irange &r, edge e)
return s;
}
+ // Only process switches if it within the size limit.
+ if (EDGE_COUNT (e->src->succs) > (unsigned)m_max_edges)
+ return NULL;
+
gcc_checking_assert (is_a<gswitch *> (s));
gswitch *sw = as_a<gswitch *> (s);
tree type = TREE_TYPE (gimple_switch_index (sw));
diff --git a/gcc/gimple-range-edge.h b/gcc/gimple-range-edge.h
index 87b4124d01d..03e8e82bd03 100644
--- a/gcc/gimple-range-edge.h
+++ b/gcc/gimple-range-edge.h
@@ -38,13 +38,14 @@ along with GCC; see the file COPYING3. If not see
class gimple_outgoing_range
{
public:
- gimple_outgoing_range ();
+ gimple_outgoing_range (int max_sw_edges = INT_MAX);
~gimple_outgoing_range ();
gimple *edge_range_p (irange &r, edge e);
private:
void calc_switch_ranges (gswitch *sw);
bool get_edge_range (irange &r, gimple *s, edge e);
+ int m_max_edges;
hash_map<edge, irange *> *m_edge_table;
irange_allocator m_range_allocator;
};
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 4a1ade7f921..6946fa65dda 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -565,6 +565,9 @@ gori_map::calculate_gori (basic_block bb)
}
else
{
+ // Do not process switches if they are too large.
+ if (EDGE_COUNT (bb->succs) > (unsigned)param_evrp_switch_limit)
+ return;
gswitch *gs = as_a<gswitch *>(stmt);
name = gimple_range_ssa_p (gimple_switch_index (gs));
maybe_add_gori (name, gimple_bb (stmt));
@@ -634,7 +637,8 @@ debug (gori_map &g)
// Construct a gori_compute object.
-gori_compute::gori_compute (int not_executable_flag) : tracer ("GORI ")
+gori_compute::gori_compute (int not_executable_flag)
+ : outgoing (param_evrp_switch_limit), tracer ("GORI ")
{
m_not_executable_flag = not_executable_flag;
// Create a boolean_type true and false range.
diff --git a/gcc/params.opt b/gcc/params.opt
index 658ca028851..82ddbb8b121 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -130,6 +130,10 @@ Maximal estimated growth of function body caused by early inlining of single cal
Common Joined UInteger Var(param_evrp_sparse_threshold) Init(800) Optimization Param
Maximum number of basic blocks before EVRP uses a sparse cache.
+-param=evrp-switch-limit=
+Common Joined UInteger Var(param_evrp_switch_limit) Init(50) Optimization Param
+Maximum number of outgoing edges in a switch before EVRP will not process it.
+
-param=evrp-mode=
Common Joined Var(param_evrp_mode) Enum(evrp_mode) Init(EVRP_MODE_RVRP_ONLY) Param Optimization
--param=evrp-mode=[legacy|ranger|legacy-first|ranger-first|trace|gori|cache|tracegori|debug] Specifies the mode Early VRP should operate in.
--
2.17.2
