Re: [PATCH] Mostly fix PR90726 - exponential compile-time/memory behavior
On Mon, 3 Jun 2019, Richard Biener wrote:
>
> This mostly fixes PR90726, employing proper visited mechanisms to
> avoid exponential behavior when walking a GENERIC expression
> with shared trees. It also fixes the code-generation side where
> gimplification of such tree naturally explodes as well - but
> not by more optimal gimplifying but accounting for out
> stupidness in the expression_expensive_p costing. Ideally
> we'd fix the gimplifier to deal with tree sharing (need to
> remember gimplified operands and re-use the gimplified result
> or preprocess the GENERIC inserting save-exprs, or ...).
> But gratious use of unshare_expr everywhere defeats this
> (unsharing also makes a tree of graphs rather than just
> deep-copying a tree graph).
>
> There's one piece left which is why the testcase uses -fno-ivopts.
> expand_simple_operations runs into the same exponential behavior
> walking the GENERIC expression _and_ the SSA graph reached from it.
> It also will end up turning all modified sub-graphs into trees.
> Changing that behemont warrants a separate patch ;)
>
> Cutting the thing off at the SCEV analysis boundary would be
> another option (there's already expression size limits but
> those do not really work - sth on my list). Ideally the
> GENERIC graph is just a complementary representation of
> the SSA graph, that we handle it by exploding is the thing
> to fix (IMHO), even if that's somewhat more painful than
> giving up during SCEV.
This one fixes the issue in expand_simple_operations. Up
to the point where it starts walking the SSA graph but I
haven't got a testcase for that yet.
Bootstrap / testing running on x86_64-unknown-linux-gnu.
I wonder if it would make sense to have auto-storage
hash_{map,set} for the usual cases with small number of
entries?
Richard.
2019-06-04 Richard Biener
PR middle-end/90726
* tree-ssa-loop-niter.c (expand_simple_operations): Do not
turn an expression graph into a tree.
* gcc.dg/pr90726.c: Enable IVOPTs.
Index: gcc/tree-ssa-loop-niter.c
===
--- gcc/tree-ssa-loop-niter.c (revision 271904)
+++ gcc/tree-ssa-loop-niter.c (working copy)
@@ -1977,8 +1977,8 @@ simplify_replace_tree (tree expr, tree o
enough, and return the new expression. If STOP is specified, stop
expanding if EXPR equals to it. */
-tree
-expand_simple_operations (tree expr, tree stop)
+static tree
+expand_simple_operations (tree expr, tree stop, hash_map )
{
unsigned i, n;
tree ret = NULL_TREE, e, ee, e1;
@@ -1998,7 +1998,24 @@ expand_simple_operations (tree expr, tre
for (i = 0; i < n; i++)
{
e = TREE_OPERAND (expr, i);
- ee = expand_simple_operations (e, stop);
+ /* SCEV analysis feeds us with a proper expression
+graph matching the SSA graph. Avoid turning it
+into a tree here, thus handle tree sharing
+properly.
+??? The SSA walk below still turns the SSA graph
+into a tree but until we find a testcase do not
+introduce additional tree sharing here. */
+ bool existed_p;
+ tree = cache.get_or_insert (e, _p);
+ if (existed_p)
+ ee = cee;
+ else
+ {
+ cee = e;
+ ee = expand_simple_operations (e, stop, cache);
+ if (ee != e)
+ *cache.get (e) = ee;
+ }
if (e == ee)
continue;
@@ -2038,7 +2055,7 @@ expand_simple_operations (tree expr, tre
&& src->loop_father != dest->loop_father)
return expr;
- return expand_simple_operations (e, stop);
+ return expand_simple_operations (e, stop, cache);
}
if (gimple_code (stmt) != GIMPLE_ASSIGN)
return expr;
@@ -2058,7 +2075,7 @@ expand_simple_operations (tree expr, tre
return e;
if (code == SSA_NAME)
- return expand_simple_operations (e, stop);
+ return expand_simple_operations (e, stop, cache);
else if (code == ADDR_EXPR)
{
poly_int64 offset;
@@ -2067,7 +2084,8 @@ expand_simple_operations (tree expr, tre
if (base
&& TREE_CODE (base) == MEM_REF)
{
- ee = expand_simple_operations (TREE_OPERAND (base, 0), stop);
+ ee = expand_simple_operations (TREE_OPERAND (base, 0), stop,
+cache);
return fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (expr), ee,
wide_int_to_tree (sizetype,
mem_ref_offset (base)
@@ -2082,7 +2100,7 @@ expand_simple_operations (tree expr, tre
{
CASE_CONVERT:
/* Casts are simple. */
- ee = expand_simple_operations (e, stop);
+ ee = expand_simple_operations (e, stop, cache);
return fold_build1 (code, TREE_TYPE (expr), ee);
case PLUS_EXPR:
@@
[PATCH] Mostly fix PR90726 - exponential compile-time/memory behavior
This mostly fixes PR90726, employing proper visited mechanisms to
avoid exponential behavior when walking a GENERIC expression
with shared trees. It also fixes the code-generation side where
gimplification of such tree naturally explodes as well - but
not by more optimal gimplifying but accounting for out
stupidness in the expression_expensive_p costing. Ideally
we'd fix the gimplifier to deal with tree sharing (need to
remember gimplified operands and re-use the gimplified result
or preprocess the GENERIC inserting save-exprs, or ...).
But gratious use of unshare_expr everywhere defeats this
(unsharing also makes a tree of graphs rather than just
deep-copying a tree graph).
There's one piece left which is why the testcase uses -fno-ivopts.
expand_simple_operations runs into the same exponential behavior
walking the GENERIC expression _and_ the SSA graph reached from it.
It also will end up turning all modified sub-graphs into trees.
Changing that behemont warrants a separate patch ;)
Cutting the thing off at the SCEV analysis boundary would be
another option (there's already expression size limits but
those do not really work - sth on my list). Ideally the
GENERIC graph is just a complementary representation of
the SSA graph, that we handle it by exploding is the thing
to fix (IMHO), even if that's somewhat more painful than
giving up during SCEV.
Bootstrap / regtest running on x86_64-unknown-linux-gnu.
Richard.
2019-06-03 Richard Biener
PR middle-end/90726
* tree-chrec.c (chrec_contains_symbols): Add to visited.
(tree_contains_chrecs): Likewise.
(chrec_contains_symbols_defined_in_loop): Move here and avoid
exponential behaivor from ...
* tree-scalar-evolution.c (chrec_contains_symbols_defined_in_loop):
... here.
(expression_expensive_p): Avoid exponential behavior and compute
expanded size, rejecting any expansion.
* tree-ssa-loop-ivopts.c (abnormal_ssa_name_p): Remove.
(idx_contains_abnormal_ssa_name_p): Likewise.
(contains_abnormal_ssa_name_p_1): New helper for walk_tree.
(contains_abnormal_ssa_name_p): Simplify and use
walk_tree_without_duplicates.
* gcc.dg/pr90726.c: New testcase.
Index: gcc/tree-chrec.c
===
--- gcc/tree-chrec.c(revision 271867)
+++ gcc/tree-chrec.c(working copy)
@@ -35,6 +35,8 @@ along with GCC; see the file COPYING3.
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-loop-niter.h"
#include "tree-chrec.h"
+#include "gimple.h"
+#include "tree-ssa-loop.h"
#include "dumpfile.h"
#include "params.h"
#include "tree-scalar-evolution.h"
@@ -959,6 +961,9 @@ chrec_contains_symbols (const_tree chrec
&& flow_loop_nested_p (get_chrec_loop (chrec), loop))
return true;
+ if (visited.add (chrec))
+return false;
+
n = TREE_OPERAND_LENGTH (chrec);
for (i = 0; i < n; i++)
if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
@@ -978,6 +983,63 @@ chrec_contains_symbols (const_tree chrec
return chrec_contains_symbols (chrec, visited, loop);
}
+/* Return true when CHREC contains symbolic names defined in
+ LOOP_NB. */
+
+static bool
+chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
+ hash_set )
+{
+ int i, n;
+
+ if (chrec == NULL_TREE)
+return false;
+
+ if (is_gimple_min_invariant (chrec))
+return false;
+
+ if (TREE_CODE (chrec) == SSA_NAME)
+{
+ gimple *def;
+ loop_p def_loop, loop;
+
+ if (SSA_NAME_IS_DEFAULT_DEF (chrec))
+ return false;
+
+ def = SSA_NAME_DEF_STMT (chrec);
+ def_loop = loop_containing_stmt (def);
+ loop = get_loop (cfun, loop_nb);
+
+ if (def_loop == NULL)
+ return false;
+
+ if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
+ return true;
+
+ return false;
+}
+
+ if (visited.add (chrec))
+return false;
+
+ n = TREE_OPERAND_LENGTH (chrec);
+ for (i = 0; i < n; i++)
+if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
+ loop_nb, visited))
+ return true;
+ return false;
+}
+
+/* Return true when CHREC contains symbolic names defined in
+ LOOP_NB. */
+
+bool
+chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
+{
+ hash_set visited;
+ return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
+}
+
/* Determines whether the chrec contains undetermined coefficients. */
static bool
@@ -1026,6 +1088,9 @@ tree_contains_chrecs (const_tree expr, i
if (tree_is_chrec (expr))
return true;
+ if (visited.add (expr))
+return false;
+
n = TREE_OPERAND_LENGTH (expr);
for (i = 0; i < n; i++)
if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
Index: gcc/tree-scalar-evolution.c
