This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [RFC] [parloop branch] Supporting reductions for automatic parallelization
On 8/20/07, Razya Ladelsky <RAZYA@il.ibm.com> wrote:
> "Daniel Berlin" <dberlin@dberlin.org> wrote on 20/08/2007 14:50:04:
>
> > 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.
> >
>
> Dan,
> What are the reduction patterns not recognized by vect_is_simple_reduction
> tha tcan be found
> using the SCC?
Anything that involves multiple operations (even if they are the same
operation) for the reduction (IE sum = sum + foo + bar)
Anything that also uses the phi result in the loop (but not the sum result)
Anything that involves using a variable from an outer loop in an inner
loop sum reduction.
Really, any cycle that is not absolutely completely trivial. This is
okay to do simple pattern matching, but if you really want to try to
win on all the reductions you can, you should do it right. (I
understand the vectorizer does what it does because it was simple and
gets 80% of all cases).
--Dan