Re: [RFC] [parloop branch] Supporting reductions for automatic parallelization

["Daniel Berlin" <dberlin at dberlin dot org>]

On 8/20/07, Razya Ladelsky <RAZYA@il.ibm.com> wrote:
> Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote on 17/08/2007 18:13:36:
>
> >
> I'm a little confused...
>
> If I understand correctly, the scalar variable is what defines the
> reduction
> and therefore I'm looking  for all uses/defs of the same reduction
> variable, what
> other way is there to do so?

You actually probably mean:
L0:
sum_0 = phi (0, sum_1)
...

sum_1 = sum_0 + something
(goto L0)

(the way you had it written, x would have only kept the last value in the loop)

Note that in the above, it is not the fact that all variables are
named "sum" that make this a reduction.
I could write it

L0:
sum_0 = phi (0, foo_37)
...

foo_37 = sum_0 + something
(goto L0)

and it would still be a reduction.

You can detect all these reductions by using an SCC finding algorithm
on the SSA graph.

All reductions will form a cycle in the SSA graph.  You then simply
need to see if the operations involved in the cycle form a reduction
form you can support.

This is 100% guaranteed to find *all* these simple types of
reductions, regardless of name.

We have code to do this kind of cycle finding on the SSA graph in
tree-ssa-sccvn.c

> Currently I am dealing only with simple reduction patterns, that
> are identified by vect_is_simple_reduction, which is looking for
> the reduction in a (single block)loop in the following way:
>
> L0:
> x_i = phi (x_j, x_k)
> ...
>
> x_g = x_i + something
> (goto L0)
>
> Where the "+" represents a reduction operation.
>
> More complicated patterns are not identified at the moment, and hopefully
> can be reduced to this form for easier handling.
>
> Is my conception wrong?

What makes you think the names matter?