Re: [PATCH PR68021]Don't add biv candidate if it's not incremented by a single stmt

[Richard Biener <richard dot guenther at gmail dot com>]

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.
>