Re: Fix phi backedge detection in backprop (PR85989)

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

On Fri, Jun 1, 2018 at 2:38 PM Richard Sandiford
<richard.sandiford@linaro.org> wrote:
>
> This PR is a nasty wrong code bug due to my fluffing a test for a
> backedge in gimple-ssa-backprop.c.  Backedges are supposed to be
> from definitions in the statement we're visiting to uses in statements
> that we haven't visited yet.  However, the check failed to account for
> PHIs in the current block that had already been processed, so if two
> PHIs in the same block referenced each other, we'd treat both
> references as backedges.
>
> In more detail:
>
> The first phase of the pass goes through all statements in an arbitrary
> order, making optimistic assumptions about any statements that haven't
> been visited yet.  The second phase then calculates a correct
> (supposedly maximal) fixed point.
>
> Although the first phase order is arbitrary in principle, we still use
> the CFG rpo to cut down on the backedges.  This means that the only
> thing that's truly arbitrary is the order that we process the PHIs
> in a block.  Any order should be OK and should eventually give the
> same results.  But we have to follow whatever order we pick,
> and the pass wasn't doing that.
>
> Tested on aarch64-linux-gnu (with and without SVE), aarch64_be-elf
> and x86_64-linux-gnu.  OK for trunk and all release branches?

OK.

Thanks,
Richard.

> Sorry for what in hindsight was a really stupid bug.
>
> Richard
>
>
>
> 2018-06-01  Richard Sandiford  <richard.sandiford@linaro.org>
>
> gcc/
>         PR tree-optimization/85989
>         * gimple-ssa-backprop.c (backprop::m_visited_phis): New member
>         variable.
>         (backprop::intersect_uses): Check it when deciding whether this
>         is a backedge reference.
>         (backprop::process_block): Add each phi to m_visited_phis
>         after visiting it, then clear it at the end.
>
> gcc/testsuite/
>         PR tree-optimization/85989
>         * gcc.dg/torture/pr85989.c: New test.
>
> Index: gcc/gimple-ssa-backprop.c
> ===================================================================
> --- gcc/gimple-ssa-backprop.c   2018-05-18 09:26:37.726714678 +0100
> +++ gcc/gimple-ssa-backprop.c   2018-06-01 13:36:04.223449400 +0100
> @@ -260,6 +260,11 @@ dump_usage_info (FILE *file, tree var, u
>       post-order walk.  */
>    auto_sbitmap m_visited_blocks;
>
> +  /* A bitmap of phis that we have finished processing in the initial
> +     post-order walk, excluding those from blocks mentioned in
> +     M_VISITED_BLOCKS.  */
> +  auto_bitmap m_visited_phis;
> +
>    /* A worklist of SSA names whose definitions need to be reconsidered.  */
>    auto_vec <tree, 64> m_worklist;
>
> @@ -496,8 +501,11 @@ backprop::intersect_uses (tree var, usag
>      {
>        if (is_gimple_debug (stmt))
>         continue;
> -      if (is_a <gphi *> (stmt)
> -         && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index))
> +      gphi *phi = dyn_cast <gphi *> (stmt);
> +      if (phi
> +         && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index)
> +         && !bitmap_bit_p (m_visited_phis,
> +                           SSA_NAME_VERSION (gimple_phi_result (phi))))
>         {
>           /* Skip unprocessed phis.  */
>           if (dump_file && (dump_flags & TDF_DETAILS))
> @@ -505,7 +513,7 @@ backprop::intersect_uses (tree var, usag
>               fprintf (dump_file, "[BACKEDGE] ");
>               print_generic_expr (dump_file, var);
>               fprintf (dump_file, " in ");
> -             print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
> +             print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
>             }
>         }
>        else
> @@ -629,7 +637,12 @@ backprop::process_block (basic_block bb)
>      }
>    for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
>         gsi_next (&gpi))
> -    process_var (gimple_phi_result (gpi.phi ()));
> +    {
> +      tree result = gimple_phi_result (gpi.phi ());
> +      process_var (result);
> +      bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result));
> +    }
> +  bitmap_clear (m_visited_phis);
>  }
>
>  /* Delete the definition of VAR, which has no uses.  */
> Index: gcc/testsuite/gcc.dg/torture/pr85989.c
> ===================================================================
> --- /dev/null   2018-04-20 16:19:46.369131350 +0100
> +++ gcc/testsuite/gcc.dg/torture/pr85989.c      2018-06-01 13:36:04.223449400 +0100
> @@ -0,0 +1,31 @@
> +/* { dg-do run } */
> +
> +#define N 9
> +
> +void __attribute__((noipa))
> +f (double x, double y, double *res)
> +{
> +  y = -y;
> +  for (int i = 0; i < N; ++i)
> +    {
> +      double tmp = y;
> +      y = x;
> +      x = tmp;
> +      res[i] = i;
> +    }
> +  res[N] = y * y;
> +  res[N + 1] = x;
> +}
> +
> +int
> +main (void)
> +{
> +  double res[N + 2];
> +  f (10, 20, res);
> +  for (int i = 0; i < N; ++i)
> +    if (res[i] != i)
> +      __builtin_abort ();
> +  if (res[N] != 100 || res[N + 1] != -20)
> +    __builtin_abort ();
> +  return 0;
> +}