diff options
author | Richard Biener <rguenther@suse.de> | 2019-06-05 08:26:36 +0000 |
---|---|---|
committer | Richard Biener <rguenth@gcc.gnu.org> | 2019-06-05 08:26:36 +0000 |
commit | e0aecd6e9a5a7c77bb356a511da7e64ef0837855 (patch) | |
tree | b03922aa2f8337a17fbacd3ec75b969f6853bbdf /gcc/tree-ssa-loop-niter.c | |
parent | 0b887b756ab330b3d37e6831094510c435240b00 (diff) |
re PR middle-end/90726 (exponential behavior on SCEV results everywhere)
2019-06-05 Richard Biener <rguenther@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.
From-SVN: r271950
Diffstat (limited to 'gcc/tree-ssa-loop-niter.c')
-rw-r--r-- | gcc/tree-ssa-loop-niter.c | 41 |
1 files changed, 33 insertions, 8 deletions
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<tree, tree> &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<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). */ |