Re: [PATCH GCC][04/13]Sort statements in topological order for loop distribution

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

On Mon, Jun 12, 2017 at 7:02 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> During the work I ran into a latent bug for distributing.  For the moment we sort statements
> in dominance order, but that's not enough because basic blocks may be sorted in reverse order
> of execution flow.  This results in wrong data dependence direction later.  This patch fixes
> the issue by sorting in topological order.
>
> Bootstrap and test on x86_64 and AArch64.  Is it OK?

I suppose you are fixing

static int
pg_add_dependence_edges (struct graph *rdg, vec<loop_p> loops, int dir,
                         vec<data_reference_p> drs1,
                         vec<data_reference_p> drs2)
{
...
        /* Re-shuffle data-refs to be in dominator order.  */
        if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
            > rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
          {
            std::swap (dr1, dr2);
            this_dir = -this_dir;
          }

but then for stmts that are not "ordered" by RPO or DOM like

   if (flag)
     ... = dr1;
   else
     ... = dr2;

this doesn't avoid spurious swaps?  Also the code was basically
copied from tree-data-refs.c:find_data_references_in_loop which
does iterate over get_loop_body_in_dom_order as well.  So isn't the
issue latent there as well?

That said, what about those "unordered" stmts?  I suppose
dependence analysis still happily computes a dependence
distance but in reality we'd have to consider both execution
orders?

Thanks,
Richard.


>
> Thanks,
> bin
> 2017-06-07  Bin Cheng  <bin.cheng@arm.com>
>
>         * tree-loop-distribution.c (bb_top_order_index): New.
>         (bb_top_order_index_size, bb_top_order_cmp): New.
>         (stmts_from_loop): Use topological order.
>         (pass_loop_distribution::execute): Compute topological order for.
>         basic blocks.