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 <rguent...@suse.de>
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<tree, tree> &cache)
{
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 &cee = cache.get_or_insert (e, &existed_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:
@@ -2097,7 +2115,7 @@ expand_simple_operations (tree expr, tre
if (!is_gimple_min_invariant (e1))
return expr;
- ee = expand_simple_operations (e, stop);
+ ee = expand_simple_operations (e, stop, cache);
return fold_build2 (code, TREE_TYPE (expr), ee, e1);
default:
@@ -2105,6 +2123,13 @@ expand_simple_operations (tree expr, tre
}
}
+tree
+expand_simple_operations (tree expr, tree stop)
+{
+ hash_map<tree, tree> cache;
+ return expand_simple_operations (expr, stop, cache);
+}
+
/* Tries to simplify EXPR using the condition COND. Returns the simplified
expression (or EXPR unchanged, if no simplification was possible). */
Index: gcc/testsuite/gcc.dg/pr90726.c
===================================================================
--- gcc/testsuite/gcc.dg/pr90726.c (revision 271904)
+++ gcc/testsuite/gcc.dg/pr90726.c (working copy)
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-fgimple -O2 -fno-ivopts" } */
+/* { dg-options "-fgimple -O2" } */
int __GIMPLE (ssa,guessed_local(12348030),startwith("fix_loops"))
un (int dd)
