From e0aecd6e9a5a7c77bb356a511da7e64ef0837855 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Wed, 5 Jun 2019 08:26:36 +0000 Subject: [PATCH] re PR middle-end/90726 (exponential behavior on SCEV results everywhere) 2019-06-05 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. From-SVN: r271950 --- gcc/ChangeLog | 6 +++++ gcc/testsuite/ChangeLog | 5 +++++ gcc/testsuite/gcc.dg/pr90726.c | 2 +- gcc/tree-ssa-loop-niter.c | 41 +++++++++++++++++++++++++++------- 4 files changed, 45 insertions(+), 9 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 6dc657f943f..f5208e1d833 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2019-06-05 Richard Biener + + PR middle-end/90726 + * tree-ssa-loop-niter.c (expand_simple_operations): Do not + turn an expression graph into a tree. + 2019-06-05 Jakub Jelinek * omp-expand.c (struct omp_region): Add has_lastprivate_conditional diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index c4293bb0ef6..35a2d543453 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2019-06-05 Richard Biener + + PR middle-end/90726 + * gcc.dg/pr90726.c: Enable IVOPTs. + 2019-06-05 Jakub Jelinek * g++.dg/vect/simd-1.cc: New test. diff --git a/gcc/testsuite/gcc.dg/pr90726.c b/gcc/testsuite/gcc.dg/pr90726.c index acdb0fe7efc..92987de1c33 100644 --- a/gcc/testsuite/gcc.dg/pr90726.c +++ b/gcc/testsuite/gcc.dg/pr90726.c @@ -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) diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 8cf8ef92b01..84e6e313c85 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -1984,8 +1984,8 @@ simplify_replace_tree (tree expr, tree old, tree new_tree, 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 &cache) { unsigned i, n; tree ret = NULL_TREE, e, ee, e1; @@ -2005,7 +2005,24 @@ expand_simple_operations (tree expr, tree stop) 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; @@ -2045,7 +2062,7 @@ expand_simple_operations (tree expr, tree stop) && 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; @@ -2065,7 +2082,7 @@ expand_simple_operations (tree expr, tree stop) 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; @@ -2074,7 +2091,8 @@ expand_simple_operations (tree expr, tree stop) 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) @@ -2089,7 +2107,7 @@ expand_simple_operations (tree expr, tree stop) { 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: @@ -2104,7 +2122,7 @@ expand_simple_operations (tree expr, tree stop) 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: @@ -2112,6 +2130,13 @@ expand_simple_operations (tree expr, tree stop) } } +tree +expand_simple_operations (tree expr, tree stop) +{ + hash_map 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). */ -- 2.30.2