At issue here is the dynamic approach we currently use for outgoing edge
calculations. It isn't normally a problem, but once you get a very
large number of possible outgoing values (ie very long unrolled blocks)
with pairs of values on a statement, and individual queries for each
one, it becomes exponential if they relate to each other.
So. We previously introduced a param for PR 100081 which limited the
depth of logical expressions GORI would pursue because we always make 2
or 4 queries for each logical expression, which accelerated the
exponential behaviour much quicker.
This patch reuses that to apply to any statement which has 2 ssa-names,
as the potential for 2 queries can happen then as well.. leading to
exponential behaviour. Each statement we step back through with
multiple ssa-names decreases the odds of calculating a useful outgoing
range anyway. This will remove ridiculous behaviour like this PR
demonstrates.
Next release I plan to revamp GORI to cache outgoing values, which will
eliminate all this sort of behaviour, and we can remove all such
restrictions.
Bootstrapped on x86_64-pc-linux-gnu with no regressions. OK for trunk?
Andrew
PS. This also points out something we are investigating with the
threader. There are no uses of _14 outside the block, so asking for its
range is problematic and contributing to excess work and cache filling
that we don't need to be doing. The VRP passes do not demonstrate this
behaviour unless, as observed, we ask for details output which queries
*all* the names.
commit bfecf512fb719dcb072e54d842b1e7a62fe03d2d
Author: Andrew MacLeod <amacl...@redhat.com>
Date: Wed Nov 17 14:14:06 2021 -0500
Limit depth for all GORI expressions.
Apply the logical_depth limit ranger uses to all stmts with multiple ssa-names
to avoid excessive outgoing calculations.
gcc/
PR tree-optimization/103254
* gimple-range-gori.cc (range_def_chain::get_def_chain): Limit the
depth for all statements with multple ssa names.
gcc/testsuite/
* gcc.dg/pr103254.c: New.
diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index fb2d571ef44..911d7ac4ec8 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -331,7 +331,6 @@ range_def_chain::get_def_chain (tree name)
{
tree ssa1, ssa2, ssa3;
unsigned v = SSA_NAME_VERSION (name);
- bool is_logical = false;
// If it has already been processed, just return the cached value.
if (has_def_chain (name))
@@ -348,15 +347,6 @@ range_def_chain::get_def_chain (tree name)
gimple *stmt = SSA_NAME_DEF_STMT (name);
if (gimple_range_handler (stmt))
{
- is_logical = is_gimple_logical_p (stmt);
- // Terminate the def chains if we see too many cascading logical stmts.
- if (is_logical)
- {
- if (m_logical_depth == param_ranger_logical_depth)
- return NULL;
- m_logical_depth++;
- }
-
ssa1 = gimple_range_ssa_p (gimple_range_operand1 (stmt));
ssa2 = gimple_range_ssa_p (gimple_range_operand2 (stmt));
ssa3 = NULL_TREE;
@@ -376,6 +366,14 @@ range_def_chain::get_def_chain (tree name)
return NULL;
}
+ // Terminate the def chains if we see too many cascading stmts.
+ if (m_logical_depth == param_ranger_logical_depth)
+ return NULL;
+
+ // Increase the depth if we have a pair of ssa-names.
+ if (ssa1 && ssa2)
+ m_logical_depth++;
+
register_dependency (name, ssa1, gimple_bb (stmt));
register_dependency (name, ssa2, gimple_bb (stmt));
register_dependency (name, ssa3, gimple_bb (stmt));
@@ -383,7 +381,7 @@ range_def_chain::get_def_chain (tree name)
if (!ssa1 && !ssa2 & !ssa3)
set_import (m_def_chain[v], name, NULL);
- if (is_logical)
+ if (ssa1 && ssa2)
m_logical_depth--;
return m_def_chain[v].bm;
diff --git a/gcc/testsuite/gcc.dg/pr103254.c b/gcc/testsuite/gcc.dg/pr103254.c
new file mode 100644
index 00000000000..62d2415f216
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr103254.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+/* { dg-timeout 10 } */
+
+short int i;
+
+void
+foo (void)
+{
+ for (i = 1; i < 2; i += 4)
+ {
+ int j;
+
+ for (j = 0; j < 5; j += 4)
+ {
+ int k;
+
+ for (k = 0; k < 68; k += 4)
+ {
+ i &= j;
+ j &= i;
+ }
+ }
+ }
+}
