From 3ca950c3525527846f13e8c547368ef432547a23 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@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(-)
@@ -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.
@@ -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));
@@ -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;
};
@@ -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.
@@ -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