From fc06280eb11be2316b12a51112cb62614141f32d Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Fri, 13 Feb 2015 05:44:46 +0000 Subject: [PATCH] re PR tree-optimization/64705 (Bad code generation of sieve on x86-64 because of too aggressive IV optimizations) PR tree-optimization/64705 * tree-ssa-loop-niter.h (expand_simple_operations): New parameter. * tree-ssa-loop-niter.c (expand_simple_operations): New parameter. * tree-ssa-loop-ivopts.c (extract_single_var_from_expr): New. (find_bivs, find_givs_in_stmt_scev): Pass new argument to expand_simple_operations. testsuite PR tree-optimization/64705 * gcc.dg/tree-ssa/pr64705.c: New test. From-SVN: r220676 --- gcc/ChangeLog | 13 ++++++- gcc/testsuite/ChangeLog | 5 +++ gcc/testsuite/gcc.dg/tree-ssa/pr64705.c | 27 ++++++++++++++ gcc/tree-ssa-loop-ivopts.c | 49 ++++++++++++++++++++++--- gcc/tree-ssa-loop-niter.c | 18 +++++---- gcc/tree-ssa-loop-niter.h | 2 +- 6 files changed, 98 insertions(+), 16 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr64705.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 375d9f4ea9f..66550042ee9 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,4 +1,13 @@ -2015-02-12 H.J. Lu +2015-02-13 Bin Cheng + + PR tree-optimization/64705 + * tree-ssa-loop-niter.h (expand_simple_operations): New parameter. + * tree-ssa-loop-niter.c (expand_simple_operations): New parameter. + * tree-ssa-loop-ivopts.c (extract_single_var_from_expr): New. + (find_bivs, find_givs_in_stmt_scev): Pass new argument to + expand_simple_operations. + +2015-02-13 H.J. Lu Richard Henderson PR rtl/32219 @@ -21,7 +30,7 @@ * config/rs6000/rs6000.c (rs6000_emit_epilogue): Fix typo in code setting up r11 for out-of-line fp restore. -2015-02-12 Eric Botcazou +2015-02-13 Eric Botcazou * config/visium/visium.opt (msv-mode): Add RejectNegative and Report. (muser-mode): Likewise. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 4f11dc60777..729f92d14fa 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2015-02-13 Bin Cheng + + PR tree-optimization/64705 + * gcc.dg/tree-ssa/pr64705.c: New test. + 2015-02-12 H.J. Lu PR rtl/32219 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr64705.c b/gcc/testsuite/gcc.dg/tree-ssa/pr64705.c new file mode 100644 index 00000000000..35a696168f5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr64705.c @@ -0,0 +1,27 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ivopts-details" } */ + +double g; + +int foo(char *flags, long len, long i, long steps) +{ + register long step, iter; + + if(*(flags + i)) + { + step = i + i + 3; + for(iter = i + step ; iter <= len ; iter += step) + { + steps++; + *(flags + iter)=0; + } + } + g = 5.0*(double)steps; + + return 0; +} + +/* Don't expand iv {base+step, step}_loop into {base+x+y, step}_loop + even if "step == x + y". */ +/* { dg-final { scan-tree-dump "base step_\[0-9\]* \\+ iter|base iter_\[0-9\]* \\+ step" "ivopts"} } */ +/* { dg-final { cleanup-tree-dump "ivopts" } } */ diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 438ff967852..6c964308067 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -1081,13 +1081,40 @@ determine_biv_step (gphi *phi) return integer_zerop (iv.step) ? NULL_TREE : iv.step; } +/* Return the first non-invariant ssa var found in EXPR. */ + +static tree +extract_single_var_from_expr (tree expr) +{ + int i, n; + tree tmp; + enum tree_code code; + + if (!expr || is_gimple_min_invariant (expr)) + return NULL; + + code = TREE_CODE (expr); + if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))) + { + n = TREE_OPERAND_LENGTH (expr); + for (i = 0; i < n; i++) + { + tmp = extract_single_var_from_expr (TREE_OPERAND (expr, i)); + + if (tmp) + return tmp; + } + } + return (TREE_CODE (expr) == SSA_NAME) ? expr : NULL; +} + /* Finds basic ivs. */ static bool find_bivs (struct ivopts_data *data) { gphi *phi; - tree step, type, base; + tree step, type, base, stop; bool found = false; struct loop *loop = data->current_loop; gphi_iterator psi; @@ -1104,7 +1131,13 @@ find_bivs (struct ivopts_data *data) continue; base = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); - base = expand_simple_operations (base); + /* Stop expanding iv base at the first ssa var referred by iv step. + Ideally we should stop at any ssa var, because that's expensive + and unusual to happen, we just do it on the first one. + + See PR64705 for the rationale. */ + stop = extract_single_var_from_expr (step); + base = expand_simple_operations (base, stop); if (contains_abnormal_ssa_name_p (base) || contains_abnormal_ssa_name_p (step)) continue; @@ -1176,7 +1209,7 @@ mark_bivs (struct ivopts_data *data) static bool find_givs_in_stmt_scev (struct ivopts_data *data, gimple stmt, affine_iv *iv) { - tree lhs; + tree lhs, stop; struct loop *loop = data->current_loop; iv->base = NULL_TREE; @@ -1191,13 +1224,19 @@ find_givs_in_stmt_scev (struct ivopts_data *data, gimple stmt, affine_iv *iv) if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true)) return false; - iv->base = expand_simple_operations (iv->base); + /* Stop expanding iv base at the first ssa var referred by iv step. + Ideally we should stop at any ssa var, because that's expensive + and unusual to happen, we just do it on the first one. + + See PR64705 for the rationale. */ + stop = extract_single_var_from_expr (iv->step); + iv->base = expand_simple_operations (iv->base, stop); if (contains_abnormal_ssa_name_p (iv->base) || contains_abnormal_ssa_name_p (iv->step)) return false; - /* If STMT could throw, then do not consider STMT as defining a GIV. + /* If STMT could throw, then do not consider STMT as defining a GIV. While this will suppress optimizations, we can not safely delete this GIV and associated statements, even if it appears it is not used. */ if (stmt_could_throw_p (stmt)) diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index a6779585b79..7f6c451c0c2 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -1563,10 +1563,11 @@ simplify_replace_tree (tree expr, tree old, tree new_tree) } /* Expand definitions of ssa names in EXPR as long as they are simple - enough, and return the new expression. */ + enough, and return the new expression. If STOP is specified, stop + expanding if EXPR equals to it. */ tree -expand_simple_operations (tree expr) +expand_simple_operations (tree expr, tree stop) { unsigned i, n; tree ret = NULL_TREE, e, ee, e1; @@ -1586,7 +1587,7 @@ expand_simple_operations (tree expr) for (i = 0; i < n; i++) { e = TREE_OPERAND (expr, i); - ee = expand_simple_operations (e); + ee = expand_simple_operations (e, stop); if (e == ee) continue; @@ -1605,7 +1606,8 @@ expand_simple_operations (tree expr) return ret; } - if (TREE_CODE (expr) != SSA_NAME) + /* Stop if it's not ssa name or the one we don't want to expand. */ + if (TREE_CODE (expr) != SSA_NAME || expr == stop) return expr; stmt = SSA_NAME_DEF_STMT (expr); @@ -1625,7 +1627,7 @@ expand_simple_operations (tree expr) && src->loop_father != dest->loop_father) return expr; - return expand_simple_operations (e); + return expand_simple_operations (e, stop); } if (gimple_code (stmt) != GIMPLE_ASSIGN) return expr; @@ -1645,7 +1647,7 @@ expand_simple_operations (tree expr) return e; if (code == SSA_NAME) - return expand_simple_operations (e); + return expand_simple_operations (e, stop); return expr; } @@ -1654,7 +1656,7 @@ expand_simple_operations (tree expr) { CASE_CONVERT: /* Casts are simple. */ - ee = expand_simple_operations (e); + ee = expand_simple_operations (e, stop); return fold_build1 (code, TREE_TYPE (expr), ee); case PLUS_EXPR: @@ -1669,7 +1671,7 @@ expand_simple_operations (tree expr) if (!is_gimple_min_invariant (e1)) return expr; - ee = expand_simple_operations (e); + ee = expand_simple_operations (e, stop); return fold_build2 (code, TREE_TYPE (expr), ee, e1); default: diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h index 2b0c2d39098..7134906dd80 100644 --- a/gcc/tree-ssa-loop-niter.h +++ b/gcc/tree-ssa-loop-niter.h @@ -20,7 +20,7 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_TREE_SSA_LOOP_NITER_H #define GCC_TREE_SSA_LOOP_NITER_H -extern tree expand_simple_operations (tree); +extern tree expand_simple_operations (tree, tree = NULL); extern bool loop_only_exit_p (const struct loop *, const_edge); extern bool number_of_iterations_exit (struct loop *, edge, struct tree_niter_desc *niter, bool, -- 2.30.2