| Message ID | HE1PR08MB05079F2EA01393116C343DEDE7D20@HE1PR08MB0507.eurprd08.prod.outlook.com |
|---|---|
| State | New |
| Headers | show |
On Fri, Feb 5, 2016 at 8:20 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: > Hi, > As reported by PR68021, there is an ivopt bug all the time. As designed, ivopt tries to identify and reuse induction variables in the original input. Apparently we don't need to compute such original biv because the computation is already there. Every time an iv use is rewritten, ivopt checks if the candidate is an original biv using below code: > > /* An important special case -- if we are asked to express value of > the original iv by itself, just exit; there is no need to > introduce a new computation (that might also need casting the > variable to unsigned and back). */ > if (cand->pos == IP_ORIGINAL > && cand->incremented_at == use->stmt) > { > enum tree_code stmt_code; > > gcc_assert (is_gimple_assign (use->stmt)); > gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after); > > /* Check whether we may leave the computation unchanged. > This is the case only if it does not rely on other > computations in the loop -- otherwise, the computation > we rely upon may be removed in remove_unused_ivs, > thus leading to ICE. */ > stmt_code = gimple_assign_rhs_code (use->stmt); > if (stmt_code == PLUS_EXPR > || stmt_code == MINUS_EXPR > || stmt_code == POINTER_PLUS_EXPR) > { > if (gimple_assign_rhs1 (use->stmt) == cand->var_before) > op = gimple_assign_rhs2 (use->stmt); > else if (gimple_assign_rhs2 (use->stmt) == cand->var_before) > op = gimple_assign_rhs1 (use->stmt); > else > op = NULL_TREE; > } > else > op = NULL_TREE; > > if (op && expr_invariant_in_loop_p (data->current_loop, op)) > return; > } > > Note this code can only handle specific form biv, in which there is a single explicit increment stmt in the form of "biv_after = biv_before + step". > > Unfortunately, in rare case like this, the biv is increased in two stmts, like: > biv_x = biv_before + step_part_1; > biv_after = biv_x + step_part_2; > > That's why control flow goes to ICE point. We should not fix code at the ICE point because: > 1) We shouldn't rewrite biv candidate. Even there is no correctness issue, it will introduce redundant code by rewriting it. > 2) For non biv candidate, all the computation at ICE point has already been done before at iv cost computation part. In other words, if control flow goes here, gcc_assert (comp != NULL" will be true. > > Back to this issue, there are two possible fixes. First one is to specially rewrite mentioned increment stmts into: > biv_after = biv_before + step > This fix needs more change because we are already after candidate creation point and need to do computation on ourself. > > Another fix is just don't add biv. In this way, we check stricter condition when adding biv candidate, guarantee control flow doesn't go to ICE point. It won't cause worse code (Well, maybe a type conversion from unsigned to signed) since we add exact the same candidate anyway (but not as a biv candidate). As a matter of fact, we create/use another candidate which has the same {base, step} as the biv. The computation of biv now becomes dead code and will be removed by following passes. > > This patch fixes the issue by the 2nd method. Bootstrap and test on x86_64 and AArch64 (test ongoing). Is it OK if no failures? Ok. Thanks, Richard. > Thanks, > bin > > 2016-02-04 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/68021 > * tree-ssa-loop-ivopts.c (increment_stmt_for_biv_p): New function. > (add_iv_candidate_for_biv, rewrite_use_nonlinear_expr): Call above > function checking if stmt is increment stmt for biv. > > gcc/testsuite/ChangeLog > 2016-02-04 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/68021 > * gcc.dg/tree-ssa/pr68021.c: New test. >
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 3faed93..adc28aa 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -3035,6 +3035,27 @@ add_standard_iv_candidates (struct ivopts_data *data) build_int_cst (long_long_integer_type_node, 1), true, NULL); } +/* Return true if STMT is the increment stmt for a biv. BEFORE and AFTER + are the corresponding vars before and after increment. */ + +static bool +increment_stmt_for_biv_p (gimple *stmt, tree before, tree after) +{ + enum tree_code code; + + gcc_assert (is_gimple_assign (stmt)); + gcc_assert (gimple_assign_lhs (stmt) == after); + + code = gimple_assign_rhs_code (stmt); + if (code != PLUS_EXPR && code != MINUS_EXPR && code != POINTER_PLUS_EXPR) + return false; + + if (gimple_assign_rhs1 (stmt) != before + && gimple_assign_rhs2 (stmt) != before) + return false; + + return true; +} /* Adds candidates bases on the old induction variable IV. */ @@ -3078,7 +3099,11 @@ add_iv_candidate_for_biv (struct ivopts_data *data, struct iv *iv) /* Don't add candidate if it's from another PHI node because it's an affine iv appearing in the form of PEELED_CHREC. */ phi = SSA_NAME_DEF_STMT (def); - if (gimple_code (phi) != GIMPLE_PHI) + if (gimple_code (phi) == GIMPLE_PHI) + gcc_assert (gimple_bb (phi) == data->current_loop->header); + /* Don't add candidate if we don't know where biv's increment + stmt is. */ + else if (increment_stmt_for_biv_p (phi, iv->ssa_name, def)) { cand = add_candidate_1 (data, iv->base, iv->step, true, IP_ORIGINAL, NULL, @@ -3086,8 +3111,6 @@ add_iv_candidate_for_biv (struct ivopts_data *data, struct iv *iv) cand->var_before = iv->ssa_name; cand->var_after = def; } - else - gcc_assert (gimple_bb (phi) == data->current_loop->header); } } @@ -7053,20 +7076,14 @@ rewrite_use_nonlinear_expr (struct ivopts_data *data, if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt) { - enum tree_code stmt_code; - - gcc_assert (is_gimple_assign (use->stmt)); - gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after); - /* Check whether we may leave the computation unchanged. This is the case only if it does not rely on other computations in the loop -- otherwise, the computation we rely upon may be removed in remove_unused_ivs, thus leading to ICE. */ - stmt_code = gimple_assign_rhs_code (use->stmt); - if (stmt_code == PLUS_EXPR - || stmt_code == MINUS_EXPR - || stmt_code == POINTER_PLUS_EXPR) + if (increment_stmt_for_biv_p (use->stmt, + cand->var_before, + cand->var_after)) { if (gimple_assign_rhs1 (use->stmt) == cand->var_before) op = gimple_assign_rhs2 (use->stmt); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68021.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68021.c new file mode 100644 index 0000000..f60b1ff --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68021.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ + +char a; +void fn1 (char *p1, int p2, int p3) +{ + int i, x; + for (i = 0; i < 10; i++) + { + for (x = 0; x < p3; x++) + { + *p1 = a; + p1--; + } + p1 += p2; + } +}
Hi, As reported by PR68021, there is an ivopt bug all the time. As designed, ivopt tries to identify and reuse induction variables in the original input. Apparently we don't need to compute such original biv because the computation is already there. Every time an iv use is rewritten, ivopt checks if the candidate is an original biv using below code: /* An important special case -- if we are asked to express value of the original iv by itself, just exit; there is no need to introduce a new computation (that might also need casting the variable to unsigned and back). */ if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt) { enum tree_code stmt_code; gcc_assert (is_gimple_assign (use->stmt)); gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after); /* Check whether we may leave the computation unchanged. This is the case only if it does not rely on other computations in the loop -- otherwise, the computation we rely upon may be removed in remove_unused_ivs, thus leading to ICE. */ stmt_code = gimple_assign_rhs_code (use->stmt); if (stmt_code == PLUS_EXPR || stmt_code == MINUS_EXPR || stmt_code == POINTER_PLUS_EXPR) { if (gimple_assign_rhs1 (use->stmt) == cand->var_before) op = gimple_assign_rhs2 (use->stmt); else if (gimple_assign_rhs2 (use->stmt) == cand->var_before) op = gimple_assign_rhs1 (use->stmt); else op = NULL_TREE; } else op = NULL_TREE; if (op && expr_invariant_in_loop_p (data->current_loop, op)) return; } Note this code can only handle specific form biv, in which there is a single explicit increment stmt in the form of "biv_after = biv_before + step". Unfortunately, in rare case like this, the biv is increased in two stmts, like: biv_x = biv_before + step_part_1; biv_after = biv_x + step_part_2; That's why control flow goes to ICE point. We should not fix code at the ICE point because: 1) We shouldn't rewrite biv candidate. Even there is no correctness issue, it will introduce redundant code by rewriting it. 2) For non biv candidate, all the computation at ICE point has already been done before at iv cost computation part. In other words, if control flow goes here, gcc_assert (comp != NULL" will be true. Back to this issue, there are two possible fixes. First one is to specially rewrite mentioned increment stmts into: biv_after = biv_before + step This fix needs more change because we are already after candidate creation point and need to do computation on ourself. Another fix is just don't add biv. In this way, we check stricter condition when adding biv candidate, guarantee control flow doesn't go to ICE point. It won't cause worse code (Well, maybe a type conversion from unsigned to signed) since we add exact the same candidate anyway (but not as a biv candidate). As a matter of fact, we create/use another candidate which has the same {base, step} as the biv. The computation of biv now becomes dead code and will be removed by following passes. This patch fixes the issue by the 2nd method. Bootstrap and test on x86_64 and AArch64 (test ongoing). Is it OK if no failures? Thanks, bin 2016-02-04 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/68021 * tree-ssa-loop-ivopts.c (increment_stmt_for_biv_p): New function. (add_iv_candidate_for_biv, rewrite_use_nonlinear_expr): Call above function checking if stmt is increment stmt for biv. gcc/testsuite/ChangeLog 2016-02-04 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/68021 * gcc.dg/tree-ssa/pr68021.c: New test.