llvm dev - Nov 2015 - [RFC] Introducing a vector reduction add instruction.

----- Original Message -----
> From: "Xinliang David Li" <davidxl at google.com>
> To: "Cong Hou" <congh at google.com>
> Cc: "Hal Finkel" <hfinkel at anl.gov>, "llvm-dev"
<llvm-dev at lists.llvm.org>
> Sent: Wednesday, November 25, 2015 5:17:58 PM
> Subject: Re: [llvm-dev] [RFC] Introducing a vector reduction add
instruction.
> 
> 
> Hal is probably not questioning about the usefulness of reduction
> recognition and a way to represent it, but the clear semantics of
> the flag. You can probably draw some ideas from OMP SIMD reduction
> clause, or intel's SIMD pragma's reduction clause.
True, but nevertheless, Cong's reply was useful. Here's my
interpretation so far:

Placing this flag on a PHI node, which is only valid for a vector-valued PHI,
indicates that only the sum of vector elements is meaningful. This could easily
be extended to cover any associative operation (only the product is useful, only
the maximum or minimum value is useful, etc.).

Now I completely understand why the flag is useful at the SDAG level. Because
SDAG is basic-block local, we can't examine the loop structure when doing
instruction selection for the relevant operations composing the psadbw (and
friends). We also need to realize, when lowering the horizontal reduction at the
end of the loop, to lower it in some more-trivial way (right?).

Regarding the metadata at the IR level: the motivation here is that, without it,
the SDAG builder would need to examine the uses of the PHI, determine that the
only uses were shuffles and extracts representing a horizontal reduction (add,
etc.), and then deduce that it could add the flag from that.

If this matching is practical (and I suspect that it is, given that we already
do it in the backends to match horizontal adds), this seems better than using
vectorizer-added metadata. In this way, IR generated using vector intrinsics
(etc.) can receive the same good code generation as that generated by the
vectorizer.

Thanks again,
Hal
> 
> 
>
https://software.intel.com/en-us/articles/enabling-simd-in-program-using-openmp40
> 
> 
> 
> David
> 
> 
> On Wed, Nov 25, 2015 at 3:07 PM, Cong Hou < congh at google.com >
wrote:
> 
> 
> On Wed, Nov 25, 2015 at 2:32 PM, Hal Finkel < hfinkel at anl.gov >
> wrote:
> > Hi Cong,
> > 
> > After reading the original RFC and this update, I'm still not
> > entirely sure I understand the semantics of the flag you're
> > proposing to add. Does it having something to do with the ordering
> > of the reduction operations?
> 
> The flag is only useful for vectorized reduction for now. I'll give
> you an example how this flag is used.
> 
> Given the following reduction loop:
> 
> int a[N];
> int s = 0;
> for (int i = 0; i < N; ++i)
> s += a[i];
> 
> After it is vectorized, we have a reduction operation add whose
> operands and the result are vectors. Suppose it is represented as:
> 
> [s0, s1, s2, s3] = [s0, s1, s2, s3] + [a0, a1, a2, a3].
> 
> If we know this operation is a reduction one, then we could have some
> flexibility on how elements in the result are organized, as long as
> the sum of them stays the same (the precondition is that the only use
> of the reduction result is the reduction phi node, and this is
> usually
> true as long as a reduction loop can be vectorized). For example, if
> we let the result be [s0+s1, 0, s2+s3, 0] or [0, 0, s0+s1+s2+s3, 0],
> the reduction result won't change. This enable us to detect SAD or
> dot-product patterns and use SSE's psadbw and pmaddwd instructions.
> Please see my respond to your another email for more details.
> 
> Thanks!
> 
> Cong
> 
> 
> 
> > 
> > Thanks again,
> > Hal
> > 
> > ----- Original Message -----
> >> From: "Cong Hou via llvm-dev" < llvm-dev at
lists.llvm.org >
> >> To: "llvm-dev" < llvm-dev at lists.llvm.org >
> >> Cc: "David Li" < davidxl at google.com >
> >> Sent: Thursday, November 19, 2015 3:12:10 PM
> >> Subject: Re: [llvm-dev] [RFC] Introducing a vector reduction add
> >> instruction.
> >> 
> >> After some attempt to implement reduce-add in LLVM, I found out a
> >> easier way to detect reduce-add without introducing new IR
> >> operations.
> >> The basic idea is annotating phi node instead of add (so that it
> >> is
> >> easier to handle other reduction operations). In PHINode class, we
> >> can
> >> add a flag indicating if the phi node is a reduction one (the flag
> >> can
> >> be set in loop vectorizer for vectorized phi nodes). Then when we
> >> build SDNode for instruction selection, we detect those reduction
> >> phi
> >> nodes and then annotate reduction operations. This requires an
> >> additional flag in SDNodeFlags. We can then check this flag when
> >> combining instructions to detect reduction operations.
> >> 
> >> In this approach, I have managed to let LLVM compile a SAD loop
> >> into
> >> psadbw instructions.
> >> 
> >> Source code:
> >> 
> >> 
> >> const int N = 1024;
> >> unsigned char a[N], b[N];
> >> 
> >> int sad() {
> >> int s = 0;
> >> for (int i = 0; i < N; ++i) {
> >> int res = a[i] - b[i];
> >> s += (res > 0) ? res : -res;
> >> }
> >> return s;
> >> }
> >> 
> >> 
> >> Emitted instructions on X86:
> >> 
> >> 
> >> 
> >> # BB#0: # %entry
> >> pxor %xmm0, %xmm0
> >> movq $-1024, %rax # imm = 0xFFFFFFFFFFFFFC00
> >> pxor %xmm1, %xmm1
> >> .align 16, 0x90
> >> .LBB0_1: # %vector.body
> >> # =>This Inner Loop Header:
> >> Depth=1
> >> movd b+1024(%rax), %xmm2 # xmm2 = mem[0],zero,zero,zero
> >> movd a+1024(%rax), %xmm3 # xmm3 = mem[0],zero,zero,zero
> >> psadbw %xmm2, %xmm3
> >> paddd %xmm3, %xmm0
> >> movd b+1028(%rax), %xmm2 # xmm2 = mem[0],zero,zero,zero
> >> movd a+1028(%rax), %xmm3 # xmm3 = mem[0],zero,zero,zero
> >> psadbw %xmm2, %xmm3
> >> paddd %xmm3, %xmm1
> >> addq $8, %rax
> >> jne .LBB0_1
> >> # BB#2: # %middle.block
> >> paddd %xmm0, %xmm1
> >> pshufd $78, %xmm1, %xmm0 # xmm0 = xmm1[2,3,0,1]
> >> paddd %xmm1, %xmm0
> >> pshufd $229, %xmm0, %xmm1 # xmm1 = xmm0[1,1,2,3]
> >> paddd %xmm0, %xmm1
> >> movd %xmm1, %eax
> >> retq
> >> 
> >> 
> >> Note that due to smaller VF we are using now (currently 4), we
> >> could
> >> not explore the most benefit of psadbw. The patch in
> >> http://reviews.llvm.org/D8943 has enables us to use bigger VFs
> >> based
> >> on the smallest type in a loop. The follow-up work is refining the
> >> cost model to let bigger VFs have less cost. For the example above
> >> the
> >> best result is from VF >=16.
> >> 
> >> The draft of the patch is here: http://reviews.llvm.org/D14840
> >> 
> >> I will refine the patch later and submit it for review.
> >> 
> >> 
> >> thanks,
> >> Cong
> >> 
> >> 
> >> On Wed, Nov 18, 2015 at 2:45 PM, Cong Hou < congh at google.com
>
> >> wrote:
> >> > On Mon, Nov 16, 2015 at 9:31 PM, Shahid, Asghar-ahmad
> >> > < Asghar-ahmad.Shahid at amd.com > wrote:
> >> >> Hi Cong,
> >> >> 
> >> >>> -----Original Message-----
> >> >>> From: Cong Hou [mailto: congh at google.com ]
> >> >>> Sent: Tuesday, November 17, 2015 12:47 AM
> >> >>> To: Shahid, Asghar-ahmad
> >> >>> Cc: David Li
> >> >>> Subject: Re: [llvm-dev] [RFC] Introducing a vector
reduction
> >> >>> add
> >> >>> instruction.
> >> >>> 
> >> >>> On Thu, Nov 12, 2015 at 9:37 PM, Shahid, Asghar-ahmad
<Asghar-
> >> >>> ahmad.Shahid at amd.com > wrote:
> >> >>> > Hi Cong,
> >> >>> > 
> >> >>> > We had proposed an intrinsic approach to do
this. However
> >> >>> > the
> >> >>> > discussion reached to a point where it was asked
that "Why
> >> >>> > do
> >> >>> > we need
> >> >>> > another approach if "reduction add"
can be pattern matched
> >> >>> > in
> >> >>> DAGCombine?"
> >> >>> > However I feel if we have strong enough
rationale for
> >> >>> > introduction of
> >> >>> > this instruction, it would be great. The 1st
link below has
> >> >>> > the
> >> >>> > complete
> >> >>> discussion about the intrinsic approach.
> >> >>> 
> >> >>> Yes, I think introducing such a reduction add can let
us do
> >> >>> pattern recognition
> >> >>> of either SAD or dot production (or more?) without
introducing
> >> >>> any
> >> >>> additional intrinsics.
> >> >> I agree. Another use case could be POPCOUNT operation.
> >> >> Moreover,
> >> >> as 'reduction add'
> >> >> Is being adopted by more targets now a days, reflecting
that in
> >> >> LLVM IR as an instruction
> >> >> Is a good idea.
> >> >> BTW, what is the idea of the syntax and semantic of this
> >> >> operation
> >> >> you have?
> >> > 
> >> > We can introduce a reduce-add for vectors only, or make it
> >> > general
> >> > so
> >> > that it could also accept scale operands. Normally it is
> >> > identical
> >> > to
> >> > normal add, but during instruction selection we can do
pattern
> >> > recognition based on more information provided by this new
> >> > operations.
> >> > For vectors, this means the result of this operation only
> >> > guarantee
> >> > that the sum of all elements in the result is identical to
the
> >> > sum
> >> > of
> >> > all elements of its operands. This gives us enough freedom to
do
> >> > aggressive transformations, such as SAD or dot-product.
> >> > 
> >> > Do you think if this is enough for us to get there?
> >> > 
> >> > 
> >> > Cong
> >> > 
> >> >> 
> >> >> The main concern may be cost
> >> >>> model: we could not guarantee that a SAD loop is
unrolled 16
> >> >>> times on SSE to
> >> >>> make use the most benefit of SAD. After the patch
> >> >>> http://reviews.llvm.org/D8943 is landed, I am now
working on
> >> >>> improving cost
> >> >>> models of type conversions on X86. I believe even
without SAD
> >> >>> instruction
> >> >>> we can still get better performance with unrolling a
SAD loop
> >> >>> 16
> >> >>> times. This
> >> >>> seems tricky but it works. What do you think?
> >> >> I also think same as we can increase the bandwidth with
proper
> >> >> cost modeling.
> >> >> 
> >> >> Regards,
> >> >> Shahid
> >> >>> 
> >> >>> Cong
> >> >>> 
> >> >>> > 
> >> >>> > http://reviews.llvm.org/D10964
> >> >>> >
http://lists.llvm.org/pipermail/llvm-dev/2015-May/085078.html
> >> >>> > 
> >> >>> > Regards,
> >> >>> > Shahid
> >> >>> > 
> >> >>> > 
> >> >>> > 
> >> >>> >> -----Original Message-----
> >> >>> >> From: llvm-dev [mailto: llvm-dev-bounces at
lists.llvm.org ]
> >> >>> >> On
> >> >>> >> Behalf Of
> >> >>> >> Cong Hou via llvm-dev
> >> >>> >> Sent: Friday, November 13, 2015 5:47 AM
> >> >>> >> To: llvm-dev at lists.llvm.org
> >> >>> >> Cc: David Li
> >> >>> >> Subject: [llvm-dev] [RFC] Introducing a
vector reduction
> >> >>> >> add
> >> >>> >> instruction.
> >> >>> >> 
> >> >>> >> Hi
> >> >>> >> 
> >> >>> >> When a reduction instruction is vectorized
in a loop, it
> >> >>> >> will
> >> >>> >> be
> >> >>> >> turned into an instruction with vector
operands of the same
> >> >>> >> operation
> >> >>> >> type. This new instruction has a special
property that can
> >> >>> >> give us
> >> >>> >> more flexibility during instruction
selection later: this
> >> >>> >> operation
> >> >>> >> is valid as long as the reduction of all
elements of the
> >> >>> >> result
> >> >>> >> vector is identical to the reduction of all
elements of its
> >> >>> >> operands.
> >> >>> >> 
> >> >>> >> One example that can benefit this property
is SAD (sum of
> >> >>> >> absolute
> >> >>> >> differences) pattern detection in SSE2,
which provides a
> >> >>> >> psadbw
> >> >>> >> instruction whose description is shown
below:
> >> >>> >> 
> >> >>> >> '''
> >> >>> >> psadbw: Compute the absolute differences of
packed unsigned
> >> >>> >> 8-bit
> >> >>> >> integers in a and b, then horizontally sum
each consecutive
> >> >>> >> 8
> >> >>> >> differences to produce two unsigned 16-bit
integers, and
> >> >>> >> pack
> >> >>> >> these
> >> >>> >> unsigned 16-bit integers in the low 16 bits
of 64-bit
> >> >>> >> elements
> >> >>> >> in dst.
> >> >>> >> '''
> >> >>> >> 
> >> >>> >> In LLVM's IR, for a SAD loop we will
have two v4i8 as
> >> >>> >> inputs
> >> >>> >> and one
> >> >>> >> v4i32 as output. However, psadbw will
actually produce one
> >> >>> >> i32
> >> >>> >> result
> >> >>> >> for four pairs of 8-bit integers (an already
reduced
> >> >>> >> result),
> >> >>> >> and the
> >> >>> >> result is stored in the first element in
v4i32. If we
> >> >>> >> properly
> >> >>> >> zero
> >> >>> >> out the other three elements in v4i32, and
with the
> >> >>> >> information that
> >> >>> >> we have a reduction add that is performed on
this result,
> >> >>> >> then
> >> >>> >> we can
> >> >>> >> safely use psadbw here for much better
performance. This
> >> >>> >> can
> >> >>> >> be done
> >> >>> >> during DAG combine. Another similar example
is dot product.
> >> >>> >> And I
> >> >>> >> think there may be many other scenarios that
can benefit
> >> >>> >> from
> >> >>> >> this
> >> >>> >> property like eliminating redundant
shuffles.
> >> >>> >> 
> >> >>> >> The question is, how to let DAG combiner
know that a vector
> >> >>> >> operation
> >> >>> >> is a reduction one?
> >> >>> >> 
> >> >>> >> Here I propose to introduce a
"reduction add" instruction
> >> >>> >> for
> >> >>> >> vectors.
> >> >>> >> This will be a new instruction with vector
operands only.
> >> >>> >> Normally it
> >> >>> >> is treated as a normal ADD operation, but
the selection DAG
> >> >>> >> combiner
> >> >>> >> can make use of this new operation to
generate better
> >> >>> >> instructions.
> >> >>> >> This new instruction is generated when
vectorizing
> >> >>> >> reduction
> >> >>> >> add in
> >> >>> >> loop vectorizer.
> >> >>> >> 
> >> >>> >> I would like to hear more comments on this
proposal or
> >> >>> >> suggestions of
> >> >>> >> better alternative implementations.
> >> >>> >> 
> >> >>> >> 
> >> >>> >> thanks,
> >> >>> >> Cong
> >> >>> >>
_______________________________________________
> >> >>> >> LLVM Developers mailing list
> >> >>> >> llvm-dev at lists.llvm.org
> >> >>> >>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >> _______________________________________________
> >> LLVM Developers mailing list
> >> llvm-dev at lists.llvm.org
> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >> 
> > 
> > --
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Wed, Nov 25, 2015 at 3:44 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
> ----- Original Message -----
>> From: "Xinliang David Li" <davidxl at google.com>
>> To: "Cong Hou" <congh at google.com>
>> Cc: "Hal Finkel" <hfinkel at anl.gov>,
"llvm-dev" <llvm-dev at lists.llvm.org>
>> Sent: Wednesday, November 25, 2015 5:17:58 PM
>> Subject: Re: [llvm-dev] [RFC] Introducing a vector reduction add
instruction.
>>
>>
>> Hal is probably not questioning about the usefulness of reduction
>> recognition and a way to represent it, but the clear semantics of
>> the flag. You can probably draw some ideas from OMP SIMD reduction
>> clause, or intel's SIMD pragma's reduction clause.
>
> True, but nevertheless, Cong's reply was useful. Here's my
interpretation so far:
>
> Placing this flag on a PHI node, which is only valid for a vector-valued
PHI, indicates that only the sum of vector elements is meaningful. This could
easily be extended to cover any associative operation (only the product is
useful, only the maximum or minimum value is useful, etc.).
Right.
>
> Now I completely understand why the flag is useful at the SDAG level.
Because SDAG is basic-block local, we can't examine the loop structure when
doing instruction selection for the relevant operations composing the psadbw
(and friends). We also need to realize, when lowering the horizontal reduction
at the end of the loop, to lower it in some more-trivial way (right?).
The benefit of collecting the result outside of the loop is trivial
unless it is in an outer loop. And I am afraid if the reduction info
helps here as the way how the results are collected is determined
already after the loop is vectorized.
>
> Regarding the metadata at the IR level: the motivation here is that,
without it, the SDAG builder would need to examine the uses of the PHI,
determine that the only uses were shuffles and extracts representing a
horizontal reduction (add, etc.), and then deduce that it could add the flag
from that.
The reduction pattern detection for the vectorized loop at this point
can be difficult for the following reasons:


1. The vectorized code outside of the loop which collects results in
the vector into a scalar can be messy. For example, there may be many
shuffles, which is not straightforward to understand (although it is
still possible to detected them).

2. After loop unrolling, the reduction operation is duplicated several
times but the phi node is not. We should be able to detect all those
unrolled reductions but this task is also challenging.

3. We need to make sure there is no other uses of the result of the
reduction operation (those operations after loop unrolling is an
exception, where the result can be used by another copy of the same
reduction operation).


However, all those information can be easily obtained during loop
vectorization. So why not record it in that stage?
>
> If this matching is practical (and I suspect that it is, given that we
already do it in the backends to match horizontal adds), this seems better than
using vectorizer-added metadata. In this way, IR generated using vector
intrinsics (etc.) can receive the same good code generation as that generated by
the vectorizer.
This is a good point. But I am not sure if it is worth the effort to
write a reduction detector for instrinsics. But the whole idea is
flexible to accept any reduction detector.

Cong
>
> Thanks again,
> Hal
>
>>
>>
>>
https://software.intel.com/en-us/articles/enabling-simd-in-program-using-openmp40
>>
>>
>>
>> David
>>
>>
>> On Wed, Nov 25, 2015 at 3:07 PM, Cong Hou < congh at google.com >
wrote:
>>
>>
>> On Wed, Nov 25, 2015 at 2:32 PM, Hal Finkel < hfinkel at anl.gov
>
>> wrote:
>> > Hi Cong,
>> >
>> > After reading the original RFC and this update, I'm still not
>> > entirely sure I understand the semantics of the flag you're
>> > proposing to add. Does it having something to do with the ordering
>> > of the reduction operations?
>>
>> The flag is only useful for vectorized reduction for now. I'll give
>> you an example how this flag is used.
>>
>> Given the following reduction loop:
>>
>> int a[N];
>> int s = 0;
>> for (int i = 0; i < N; ++i)
>> s += a[i];
>>
>> After it is vectorized, we have a reduction operation add whose
>> operands and the result are vectors. Suppose it is represented as:
>>
>> [s0, s1, s2, s3] = [s0, s1, s2, s3] + [a0, a1, a2, a3].
>>
>> If we know this operation is a reduction one, then we could have some
>> flexibility on how elements in the result are organized, as long as
>> the sum of them stays the same (the precondition is that the only use
>> of the reduction result is the reduction phi node, and this is
>> usually
>> true as long as a reduction loop can be vectorized). For example, if
>> we let the result be [s0+s1, 0, s2+s3, 0] or [0, 0, s0+s1+s2+s3, 0],
>> the reduction result won't change. This enable us to detect SAD or
>> dot-product patterns and use SSE's psadbw and pmaddwd instructions.
>> Please see my respond to your another email for more details.
>>
>> Thanks!
>>
>> Cong
>>
>>
>>
>> >
>> > Thanks again,
>> > Hal
>> >
>> > ----- Original Message -----
>> >> From: "Cong Hou via llvm-dev" < llvm-dev at
lists.llvm.org >
>> >> To: "llvm-dev" < llvm-dev at lists.llvm.org >
>> >> Cc: "David Li" < davidxl at google.com >
>> >> Sent: Thursday, November 19, 2015 3:12:10 PM
>> >> Subject: Re: [llvm-dev] [RFC] Introducing a vector reduction
add
>> >> instruction.
>> >>
>> >> After some attempt to implement reduce-add in LLVM, I found
out a
>> >> easier way to detect reduce-add without introducing new IR
>> >> operations.
>> >> The basic idea is annotating phi node instead of add (so that
it
>> >> is
>> >> easier to handle other reduction operations). In PHINode
class, we
>> >> can
>> >> add a flag indicating if the phi node is a reduction one (the
flag
>> >> can
>> >> be set in loop vectorizer for vectorized phi nodes). Then when
we
>> >> build SDNode for instruction selection, we detect those
reduction
>> >> phi
>> >> nodes and then annotate reduction operations. This requires an
>> >> additional flag in SDNodeFlags. We can then check this flag
when
>> >> combining instructions to detect reduction operations.
>> >>
>> >> In this approach, I have managed to let LLVM compile a SAD
loop
>> >> into
>> >> psadbw instructions.
>> >>
>> >> Source code:
>> >>
>> >>
>> >> const int N = 1024;
>> >> unsigned char a[N], b[N];
>> >>
>> >> int sad() {
>> >> int s = 0;
>> >> for (int i = 0; i < N; ++i) {
>> >> int res = a[i] - b[i];
>> >> s += (res > 0) ? res : -res;
>> >> }
>> >> return s;
>> >> }
>> >>
>> >>
>> >> Emitted instructions on X86:
>> >>
>> >>
>> >>
>> >> # BB#0: # %entry
>> >> pxor %xmm0, %xmm0
>> >> movq $-1024, %rax # imm = 0xFFFFFFFFFFFFFC00
>> >> pxor %xmm1, %xmm1
>> >> .align 16, 0x90
>> >> .LBB0_1: # %vector.body
>> >> # =>This Inner Loop Header:
>> >> Depth=1
>> >> movd b+1024(%rax), %xmm2 # xmm2 = mem[0],zero,zero,zero
>> >> movd a+1024(%rax), %xmm3 # xmm3 = mem[0],zero,zero,zero
>> >> psadbw %xmm2, %xmm3
>> >> paddd %xmm3, %xmm0
>> >> movd b+1028(%rax), %xmm2 # xmm2 = mem[0],zero,zero,zero
>> >> movd a+1028(%rax), %xmm3 # xmm3 = mem[0],zero,zero,zero
>> >> psadbw %xmm2, %xmm3
>> >> paddd %xmm3, %xmm1
>> >> addq $8, %rax
>> >> jne .LBB0_1
>> >> # BB#2: # %middle.block
>> >> paddd %xmm0, %xmm1
>> >> pshufd $78, %xmm1, %xmm0 # xmm0 = xmm1[2,3,0,1]
>> >> paddd %xmm1, %xmm0
>> >> pshufd $229, %xmm0, %xmm1 # xmm1 = xmm0[1,1,2,3]
>> >> paddd %xmm0, %xmm1
>> >> movd %xmm1, %eax
>> >> retq
>> >>
>> >>
>> >> Note that due to smaller VF we are using now (currently 4), we
>> >> could
>> >> not explore the most benefit of psadbw. The patch in
>> >> http://reviews.llvm.org/D8943 has enables us to use bigger VFs
>> >> based
>> >> on the smallest type in a loop. The follow-up work is refining
the
>> >> cost model to let bigger VFs have less cost. For the example
above
>> >> the
>> >> best result is from VF >=16.
>> >>
>> >> The draft of the patch is here: http://reviews.llvm.org/D14840
>> >>
>> >> I will refine the patch later and submit it for review.
>> >>
>> >>
>> >> thanks,
>> >> Cong
>> >>
>> >>
>> >> On Wed, Nov 18, 2015 at 2:45 PM, Cong Hou < congh at
google.com >
>> >> wrote:
>> >> > On Mon, Nov 16, 2015 at 9:31 PM, Shahid, Asghar-ahmad
>> >> > < Asghar-ahmad.Shahid at amd.com > wrote:
>> >> >> Hi Cong,
>> >> >>
>> >> >>> -----Original Message-----
>> >> >>> From: Cong Hou [mailto: congh at google.com ]
>> >> >>> Sent: Tuesday, November 17, 2015 12:47 AM
>> >> >>> To: Shahid, Asghar-ahmad
>> >> >>> Cc: David Li
>> >> >>> Subject: Re: [llvm-dev] [RFC] Introducing a
vector reduction
>> >> >>> add
>> >> >>> instruction.
>> >> >>>
>> >> >>> On Thu, Nov 12, 2015 at 9:37 PM, Shahid,
Asghar-ahmad <Asghar-
>> >> >>> ahmad.Shahid at amd.com > wrote:
>> >> >>> > Hi Cong,
>> >> >>> >
>> >> >>> > We had proposed an intrinsic approach to do
this. However
>> >> >>> > the
>> >> >>> > discussion reached to a point where it was
asked that "Why
>> >> >>> > do
>> >> >>> > we need
>> >> >>> > another approach if "reduction
add" can be pattern matched
>> >> >>> > in
>> >> >>> DAGCombine?"
>> >> >>> > However I feel if we have strong enough
rationale for
>> >> >>> > introduction of
>> >> >>> > this instruction, it would be great. The 1st
link below has
>> >> >>> > the
>> >> >>> > complete
>> >> >>> discussion about the intrinsic approach.
>> >> >>>
>> >> >>> Yes, I think introducing such a reduction add can
let us do
>> >> >>> pattern recognition
>> >> >>> of either SAD or dot production (or more?)
without introducing
>> >> >>> any
>> >> >>> additional intrinsics.
>> >> >> I agree. Another use case could be POPCOUNT
operation.
>> >> >> Moreover,
>> >> >> as 'reduction add'
>> >> >> Is being adopted by more targets now a days,
reflecting that in
>> >> >> LLVM IR as an instruction
>> >> >> Is a good idea.
>> >> >> BTW, what is the idea of the syntax and semantic of
this
>> >> >> operation
>> >> >> you have?
>> >> >
>> >> > We can introduce a reduce-add for vectors only, or make
it
>> >> > general
>> >> > so
>> >> > that it could also accept scale operands. Normally it is
>> >> > identical
>> >> > to
>> >> > normal add, but during instruction selection we can do
pattern
>> >> > recognition based on more information provided by this
new
>> >> > operations.
>> >> > For vectors, this means the result of this operation only
>> >> > guarantee
>> >> > that the sum of all elements in the result is identical
to the
>> >> > sum
>> >> > of
>> >> > all elements of its operands. This gives us enough
freedom to do
>> >> > aggressive transformations, such as SAD or dot-product.
>> >> >
>> >> > Do you think if this is enough for us to get there?
>> >> >
>> >> >
>> >> > Cong
>> >> >
>> >> >>
>> >> >> The main concern may be cost
>> >> >>> model: we could not guarantee that a SAD loop is
unrolled 16
>> >> >>> times on SSE to
>> >> >>> make use the most benefit of SAD. After the patch
>> >> >>> http://reviews.llvm.org/D8943 is landed, I am now
working on
>> >> >>> improving cost
>> >> >>> models of type conversions on X86. I believe even
without SAD
>> >> >>> instruction
>> >> >>> we can still get better performance with
unrolling a SAD loop
>> >> >>> 16
>> >> >>> times. This
>> >> >>> seems tricky but it works. What do you think?
>> >> >> I also think same as we can increase the bandwidth
with proper
>> >> >> cost modeling.
>> >> >>
>> >> >> Regards,
>> >> >> Shahid
>> >> >>>
>> >> >>> Cong
>> >> >>>
>> >> >>> >
>> >> >>> > http://reviews.llvm.org/D10964
>> >> >>> >
http://lists.llvm.org/pipermail/llvm-dev/2015-May/085078.html
>> >> >>> >
>> >> >>> > Regards,
>> >> >>> > Shahid
>> >> >>> >
>> >> >>> >
>> >> >>> >
>> >> >>> >> -----Original Message-----
>> >> >>> >> From: llvm-dev [mailto: llvm-dev-bounces
at lists.llvm.org ]
>> >> >>> >> On
>> >> >>> >> Behalf Of
>> >> >>> >> Cong Hou via llvm-dev
>> >> >>> >> Sent: Friday, November 13, 2015 5:47 AM
>> >> >>> >> To: llvm-dev at lists.llvm.org
>> >> >>> >> Cc: David Li
>> >> >>> >> Subject: [llvm-dev] [RFC] Introducing a
vector reduction
>> >> >>> >> add
>> >> >>> >> instruction.
>> >> >>> >>
>> >> >>> >> Hi
>> >> >>> >>
>> >> >>> >> When a reduction instruction is
vectorized in a loop, it
>> >> >>> >> will
>> >> >>> >> be
>> >> >>> >> turned into an instruction with vector
operands of the same
>> >> >>> >> operation
>> >> >>> >> type. This new instruction has a special
property that can
>> >> >>> >> give us
>> >> >>> >> more flexibility during instruction
selection later: this
>> >> >>> >> operation
>> >> >>> >> is valid as long as the reduction of all
elements of the
>> >> >>> >> result
>> >> >>> >> vector is identical to the reduction of
all elements of its
>> >> >>> >> operands.
>> >> >>> >>
>> >> >>> >> One example that can benefit this
property is SAD (sum of
>> >> >>> >> absolute
>> >> >>> >> differences) pattern detection in SSE2,
which provides a
>> >> >>> >> psadbw
>> >> >>> >> instruction whose description is shown
below:
>> >> >>> >>
>> >> >>> >> '''
>> >> >>> >> psadbw: Compute the absolute differences
of packed unsigned
>> >> >>> >> 8-bit
>> >> >>> >> integers in a and b, then horizontally
sum each consecutive
>> >> >>> >> 8
>> >> >>> >> differences to produce two unsigned
16-bit integers, and
>> >> >>> >> pack
>> >> >>> >> these
>> >> >>> >> unsigned 16-bit integers in the low 16
bits of 64-bit
>> >> >>> >> elements
>> >> >>> >> in dst.
>> >> >>> >> '''
>> >> >>> >>
>> >> >>> >> In LLVM's IR, for a SAD loop we will
have two v4i8 as
>> >> >>> >> inputs
>> >> >>> >> and one
>> >> >>> >> v4i32 as output. However, psadbw will
actually produce one
>> >> >>> >> i32
>> >> >>> >> result
>> >> >>> >> for four pairs of 8-bit integers (an
already reduced
>> >> >>> >> result),
>> >> >>> >> and the
>> >> >>> >> result is stored in the first element in
v4i32. If we
>> >> >>> >> properly
>> >> >>> >> zero
>> >> >>> >> out the other three elements in v4i32,
and with the
>> >> >>> >> information that
>> >> >>> >> we have a reduction add that is
performed on this result,
>> >> >>> >> then
>> >> >>> >> we can
>> >> >>> >> safely use psadbw here for much better
performance. This
>> >> >>> >> can
>> >> >>> >> be done
>> >> >>> >> during DAG combine. Another similar
example is dot product.
>> >> >>> >> And I
>> >> >>> >> think there may be many other scenarios
that can benefit
>> >> >>> >> from
>> >> >>> >> this
>> >> >>> >> property like eliminating redundant
shuffles.
>> >> >>> >>
>> >> >>> >> The question is, how to let DAG combiner
know that a vector
>> >> >>> >> operation
>> >> >>> >> is a reduction one?
>> >> >>> >>
>> >> >>> >> Here I propose to introduce a
"reduction add" instruction
>> >> >>> >> for
>> >> >>> >> vectors.
>> >> >>> >> This will be a new instruction with
vector operands only.
>> >> >>> >> Normally it
>> >> >>> >> is treated as a normal ADD operation,
but the selection DAG
>> >> >>> >> combiner
>> >> >>> >> can make use of this new operation to
generate better
>> >> >>> >> instructions.
>> >> >>> >> This new instruction is generated when
vectorizing
>> >> >>> >> reduction
>> >> >>> >> add in
>> >> >>> >> loop vectorizer.
>> >> >>> >>
>> >> >>> >> I would like to hear more comments on
this proposal or
>> >> >>> >> suggestions of
>> >> >>> >> better alternative implementations.
>> >> >>> >>
>> >> >>> >>
>> >> >>> >> thanks,
>> >> >>> >> Cong
>> >> >>> >>
_______________________________________________
>> >> >>> >> LLVM Developers mailing list
>> >> >>> >> llvm-dev at lists.llvm.org
>> >> >>> >>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> >> _______________________________________________
>> >> LLVM Developers mailing list
>> >> llvm-dev at lists.llvm.org
>> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> >>
>> >
>> > --
>> > Hal Finkel
>> > Assistant Computational Scientist
>> > Leadership Computing Facility
>> > Argonne National Laboratory
>>
>>
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory

----- Original Message -----
> From: "Cong Hou" <congh at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Xinliang David Li" <davidxl at google.com>,
"llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Wednesday, November 25, 2015 6:33:04 PM
> Subject: Re: [llvm-dev] [RFC] Introducing a vector reduction add
instruction.
> 
> On Wed, Nov 25, 2015 at 3:44 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
> > ----- Original Message -----
> >> From: "Xinliang David Li" <davidxl at google.com>
> >> To: "Cong Hou" <congh at google.com>
> >> Cc: "Hal Finkel" <hfinkel at anl.gov>,
"llvm-dev"
> >> <llvm-dev at lists.llvm.org>
> >> Sent: Wednesday, November 25, 2015 5:17:58 PM
> >> Subject: Re: [llvm-dev] [RFC] Introducing a vector reduction add
> >> instruction.
> >>
> >>
> >> Hal is probably not questioning about the usefulness of reduction
> >> recognition and a way to represent it, but the clear semantics of
> >> the flag. You can probably draw some ideas from OMP SIMD reduction
> >> clause, or intel's SIMD pragma's reduction clause.
> >
> > True, but nevertheless, Cong's reply was useful. Here's my
> > interpretation so far:
> >
> > Placing this flag on a PHI node, which is only valid for a
> > vector-valued PHI, indicates that only the sum of vector elements
> > is meaningful. This could easily be extended to cover any
> > associative operation (only the product is useful, only the
> > maximum or minimum value is useful, etc.).
> 
> Right.
> 
> >
> > Now I completely understand why the flag is useful at the SDAG
> > level. Because SDAG is basic-block local, we can't examine the
> > loop structure when doing instruction selection for the relevant
> > operations composing the psadbw (and friends). We also need to
> > realize, when lowering the horizontal reduction at the end of the
> > loop, to lower it in some more-trivial way (right?).
> 
> The benefit of collecting the result outside of the loop is trivial
> unless it is in an outer loop. And I am afraid if the reduction info
> helps here as the way how the results are collected is determined
> already after the loop is vectorized.
Yes, but "unless it is in an outer loop" is an important case in
practice. The underlying situation is: Given that the target has lowered the
instructions producing the PHI value to ones that always leave certain vector
elements zero, we should be able to use that information when
simplifying/lowering the horizontal sum in the exit block.

One way to handle this is to enhance the
SelectionDAGISel::ComputeLiveOutVRegInfo() function, and related infrastructure,
to understand what is going on (with target help), so that by the time we get to
the exit block, the necessary information is known and can be used to simplify
the incoming vector values. This can certainly be considered follow-up work.
> 
> >
> > Regarding the metadata at the IR level: the motivation here is
> > that, without it, the SDAG builder would need to examine the uses
> > of the PHI, determine that the only uses were shuffles and
> > extracts representing a horizontal reduction (add, etc.), and then
> > deduce that it could add the flag from that.
> 
> The reduction pattern detection for the vectorized loop at this point
> can be difficult for the following reasons:
> 
> 
> 1. The vectorized code outside of the loop which collects results in
> the vector into a scalar can be messy. For example, there may be many
> shuffles, which is not straightforward to understand (although it is
> still possible to detected them).
> 
> 2. After loop unrolling, the reduction operation is duplicated
> several
> times but the phi node is not. We should be able to detect all those
> unrolled reductions but this task is also challenging.
> 
> 3. We need to make sure there is no other uses of the result of the
> reduction operation (those operations after loop unrolling is an
> exception, where the result can be used by another copy of the same
> reduction operation).
> 
> 
> However, all those information can be easily obtained during loop
> vectorization. So why not record it in that stage?
Because it adds yet-another place (PHI nodes) that we need to worry about
preserving metadata, and it adds information redundant with that already
contained in the IR. Generally, we try not to do that.

If it were the case that re-deriving that information during SDAG building would
be non-trivial (because, for example, it would require pulling in some expensive
analysis), I'd consider that a valid reason. That does not seem to be the
case, however.

We need to be very careful not to fall into the trap of having a "magic
vectorizer", meaning a vectorizer that knows how to induce special
code-generation functionality not otherwise available to generic input code. It
is trivial to write, using completely generic LLVM IR with vector types, the
code that the vectorizer would produce. A frontend might generate this directly,
for example. It is important that we treat such code as a "first-class
citizen" within our framework. Thus, I'd highly prefer that we pattern
match the necessary IR in the SDAG builder instead of adding metadata in the
vectorizer.
> 
> >
> > If this matching is practical (and I suspect that it is, given that
> > we already do it in the backends to match horizontal adds), this
> > seems better than using vectorizer-added metadata. In this way, IR
> > generated using vector intrinsics (etc.) can receive the same good
> > code generation as that generated by the vectorizer.
> 
> This is a good point. But I am not sure if it is worth the effort to
> write a reduction detector for instrinsics. But the whole idea is
> flexible to accept any reduction detector.
When I say "intrinsics", I mean using native LLVM vector types.

Thanks again,
Hal
> 
> Cong
> 
> >
> > Thanks again,
> > Hal
> >
> >>
> >>
> >>
https://software.intel.com/en-us/articles/enabling-simd-in-program-using-openmp40
> >>
> >>
> >>
> >> David
> >>
> >>
> >> On Wed, Nov 25, 2015 at 3:07 PM, Cong Hou < congh at google.com
>
> >> wrote:
> >>
> >>
> >> On Wed, Nov 25, 2015 at 2:32 PM, Hal Finkel < hfinkel at
anl.gov >
> >> wrote:
> >> > Hi Cong,
> >> >
> >> > After reading the original RFC and this update, I'm still
not
> >> > entirely sure I understand the semantics of the flag
you're
> >> > proposing to add. Does it having something to do with the
> >> > ordering
> >> > of the reduction operations?
> >>
> >> The flag is only useful for vectorized reduction for now. I'll
> >> give
> >> you an example how this flag is used.
> >>
> >> Given the following reduction loop:
> >>
> >> int a[N];
> >> int s = 0;
> >> for (int i = 0; i < N; ++i)
> >> s += a[i];
> >>
> >> After it is vectorized, we have a reduction operation add whose
> >> operands and the result are vectors. Suppose it is represented as:
> >>
> >> [s0, s1, s2, s3] = [s0, s1, s2, s3] + [a0, a1, a2, a3].
> >>
> >> If we know this operation is a reduction one, then we could have
> >> some
> >> flexibility on how elements in the result are organized, as long
> >> as
> >> the sum of them stays the same (the precondition is that the only
> >> use
> >> of the reduction result is the reduction phi node, and this is
> >> usually
> >> true as long as a reduction loop can be vectorized). For example,
> >> if
> >> we let the result be [s0+s1, 0, s2+s3, 0] or [0, 0, s0+s1+s2+s3,
> >> 0],
> >> the reduction result won't change. This enable us to detect
SAD or
> >> dot-product patterns and use SSE's psadbw and pmaddwd
> >> instructions.
> >> Please see my respond to your another email for more details.
> >>
> >> Thanks!
> >>
> >> Cong
> >>
> >>
> >>
> >> >
> >> > Thanks again,
> >> > Hal
> >> >
> >> > ----- Original Message -----
> >> >> From: "Cong Hou via llvm-dev" < llvm-dev at
lists.llvm.org >
> >> >> To: "llvm-dev" < llvm-dev at lists.llvm.org
>
> >> >> Cc: "David Li" < davidxl at google.com >
> >> >> Sent: Thursday, November 19, 2015 3:12:10 PM
> >> >> Subject: Re: [llvm-dev] [RFC] Introducing a vector
reduction
> >> >> add
> >> >> instruction.
> >> >>
> >> >> After some attempt to implement reduce-add in LLVM, I
found out
> >> >> a
> >> >> easier way to detect reduce-add without introducing new
IR
> >> >> operations.
> >> >> The basic idea is annotating phi node instead of add (so
that
> >> >> it
> >> >> is
> >> >> easier to handle other reduction operations). In PHINode
class,
> >> >> we
> >> >> can
> >> >> add a flag indicating if the phi node is a reduction one
(the
> >> >> flag
> >> >> can
> >> >> be set in loop vectorizer for vectorized phi nodes). Then
when
> >> >> we
> >> >> build SDNode for instruction selection, we detect those
> >> >> reduction
> >> >> phi
> >> >> nodes and then annotate reduction operations. This
requires an
> >> >> additional flag in SDNodeFlags. We can then check this
flag
> >> >> when
> >> >> combining instructions to detect reduction operations.
> >> >>
> >> >> In this approach, I have managed to let LLVM compile a
SAD loop
> >> >> into
> >> >> psadbw instructions.
> >> >>
> >> >> Source code:
> >> >>
> >> >>
> >> >> const int N = 1024;
> >> >> unsigned char a[N], b[N];
> >> >>
> >> >> int sad() {
> >> >> int s = 0;
> >> >> for (int i = 0; i < N; ++i) {
> >> >> int res = a[i] - b[i];
> >> >> s += (res > 0) ? res : -res;
> >> >> }
> >> >> return s;
> >> >> }
> >> >>
> >> >>
> >> >> Emitted instructions on X86:
> >> >>
> >> >>
> >> >>
> >> >> # BB#0: # %entry
> >> >> pxor %xmm0, %xmm0
> >> >> movq $-1024, %rax # imm = 0xFFFFFFFFFFFFFC00
> >> >> pxor %xmm1, %xmm1
> >> >> .align 16, 0x90
> >> >> .LBB0_1: # %vector.body
> >> >> # =>This Inner Loop Header:
> >> >> Depth=1
> >> >> movd b+1024(%rax), %xmm2 # xmm2 = mem[0],zero,zero,zero
> >> >> movd a+1024(%rax), %xmm3 # xmm3 = mem[0],zero,zero,zero
> >> >> psadbw %xmm2, %xmm3
> >> >> paddd %xmm3, %xmm0
> >> >> movd b+1028(%rax), %xmm2 # xmm2 = mem[0],zero,zero,zero
> >> >> movd a+1028(%rax), %xmm3 # xmm3 = mem[0],zero,zero,zero
> >> >> psadbw %xmm2, %xmm3
> >> >> paddd %xmm3, %xmm1
> >> >> addq $8, %rax
> >> >> jne .LBB0_1
> >> >> # BB#2: # %middle.block
> >> >> paddd %xmm0, %xmm1
> >> >> pshufd $78, %xmm1, %xmm0 # xmm0 = xmm1[2,3,0,1]
> >> >> paddd %xmm1, %xmm0
> >> >> pshufd $229, %xmm0, %xmm1 # xmm1 = xmm0[1,1,2,3]
> >> >> paddd %xmm0, %xmm1
> >> >> movd %xmm1, %eax
> >> >> retq
> >> >>
> >> >>
> >> >> Note that due to smaller VF we are using now (currently
4), we
> >> >> could
> >> >> not explore the most benefit of psadbw. The patch in
> >> >> http://reviews.llvm.org/D8943 has enables us to use
bigger VFs
> >> >> based
> >> >> on the smallest type in a loop. The follow-up work is
refining
> >> >> the
> >> >> cost model to let bigger VFs have less cost. For the
example
> >> >> above
> >> >> the
> >> >> best result is from VF >=16.
> >> >>
> >> >> The draft of the patch is here:
http://reviews.llvm.org/D14840
> >> >>
> >> >> I will refine the patch later and submit it for review.
> >> >>
> >> >>
> >> >> thanks,
> >> >> Cong
> >> >>
> >> >>
> >> >> On Wed, Nov 18, 2015 at 2:45 PM, Cong Hou < congh at
google.com >
> >> >> wrote:
> >> >> > On Mon, Nov 16, 2015 at 9:31 PM, Shahid,
Asghar-ahmad
> >> >> > < Asghar-ahmad.Shahid at amd.com > wrote:
> >> >> >> Hi Cong,
> >> >> >>
> >> >> >>> -----Original Message-----
> >> >> >>> From: Cong Hou [mailto: congh at google.com
]
> >> >> >>> Sent: Tuesday, November 17, 2015 12:47 AM
> >> >> >>> To: Shahid, Asghar-ahmad
> >> >> >>> Cc: David Li
> >> >> >>> Subject: Re: [llvm-dev] [RFC] Introducing a
vector
> >> >> >>> reduction
> >> >> >>> add
> >> >> >>> instruction.
> >> >> >>>
> >> >> >>> On Thu, Nov 12, 2015 at 9:37 PM, Shahid,
Asghar-ahmad
> >> >> >>> <Asghar-
> >> >> >>> ahmad.Shahid at amd.com > wrote:
> >> >> >>> > Hi Cong,
> >> >> >>> >
> >> >> >>> > We had proposed an intrinsic approach
to do this. However
> >> >> >>> > the
> >> >> >>> > discussion reached to a point where it
was asked that
> >> >> >>> > "Why
> >> >> >>> > do
> >> >> >>> > we need
> >> >> >>> > another approach if "reduction
add" can be pattern
> >> >> >>> > matched
> >> >> >>> > in
> >> >> >>> DAGCombine?"
> >> >> >>> > However I feel if we have strong enough
rationale for
> >> >> >>> > introduction of
> >> >> >>> > this instruction, it would be great.
The 1st link below
> >> >> >>> > has
> >> >> >>> > the
> >> >> >>> > complete
> >> >> >>> discussion about the intrinsic approach.
> >> >> >>>
> >> >> >>> Yes, I think introducing such a reduction
add can let us do
> >> >> >>> pattern recognition
> >> >> >>> of either SAD or dot production (or more?)
without
> >> >> >>> introducing
> >> >> >>> any
> >> >> >>> additional intrinsics.
> >> >> >> I agree. Another use case could be POPCOUNT
operation.
> >> >> >> Moreover,
> >> >> >> as 'reduction add'
> >> >> >> Is being adopted by more targets now a days,
reflecting that
> >> >> >> in
> >> >> >> LLVM IR as an instruction
> >> >> >> Is a good idea.
> >> >> >> BTW, what is the idea of the syntax and semantic
of this
> >> >> >> operation
> >> >> >> you have?
> >> >> >
> >> >> > We can introduce a reduce-add for vectors only, or
make it
> >> >> > general
> >> >> > so
> >> >> > that it could also accept scale operands. Normally
it is
> >> >> > identical
> >> >> > to
> >> >> > normal add, but during instruction selection we can
do
> >> >> > pattern
> >> >> > recognition based on more information provided by
this new
> >> >> > operations.
> >> >> > For vectors, this means the result of this operation
only
> >> >> > guarantee
> >> >> > that the sum of all elements in the result is
identical to
> >> >> > the
> >> >> > sum
> >> >> > of
> >> >> > all elements of its operands. This gives us enough
freedom to
> >> >> > do
> >> >> > aggressive transformations, such as SAD or
dot-product.
> >> >> >
> >> >> > Do you think if this is enough for us to get there?
> >> >> >
> >> >> >
> >> >> > Cong
> >> >> >
> >> >> >>
> >> >> >> The main concern may be cost
> >> >> >>> model: we could not guarantee that a SAD
loop is unrolled
> >> >> >>> 16
> >> >> >>> times on SSE to
> >> >> >>> make use the most benefit of SAD. After the
patch
> >> >> >>> http://reviews.llvm.org/D8943 is landed, I
am now working
> >> >> >>> on
> >> >> >>> improving cost
> >> >> >>> models of type conversions on X86. I believe
even without
> >> >> >>> SAD
> >> >> >>> instruction
> >> >> >>> we can still get better performance with
unrolling a SAD
> >> >> >>> loop
> >> >> >>> 16
> >> >> >>> times. This
> >> >> >>> seems tricky but it works. What do you
think?
> >> >> >> I also think same as we can increase the
bandwidth with
> >> >> >> proper
> >> >> >> cost modeling.
> >> >> >>
> >> >> >> Regards,
> >> >> >> Shahid
> >> >> >>>
> >> >> >>> Cong
> >> >> >>>
> >> >> >>> >
> >> >> >>> > http://reviews.llvm.org/D10964
> >> >> >>> >
http://lists.llvm.org/pipermail/llvm-dev/2015-May/085078.html
> >> >> >>> >
> >> >> >>> > Regards,
> >> >> >>> > Shahid
> >> >> >>> >
> >> >> >>> >
> >> >> >>> >
> >> >> >>> >> -----Original Message-----
> >> >> >>> >> From: llvm-dev [mailto:
llvm-dev-bounces at lists.llvm.org
> >> >> >>> >> ]
> >> >> >>> >> On
> >> >> >>> >> Behalf Of
> >> >> >>> >> Cong Hou via llvm-dev
> >> >> >>> >> Sent: Friday, November 13, 2015
5:47 AM
> >> >> >>> >> To: llvm-dev at lists.llvm.org
> >> >> >>> >> Cc: David Li
> >> >> >>> >> Subject: [llvm-dev] [RFC]
Introducing a vector reduction
> >> >> >>> >> add
> >> >> >>> >> instruction.
> >> >> >>> >>
> >> >> >>> >> Hi
> >> >> >>> >>
> >> >> >>> >> When a reduction instruction is
vectorized in a loop, it
> >> >> >>> >> will
> >> >> >>> >> be
> >> >> >>> >> turned into an instruction with
vector operands of the
> >> >> >>> >> same
> >> >> >>> >> operation
> >> >> >>> >> type. This new instruction has a
special property that
> >> >> >>> >> can
> >> >> >>> >> give us
> >> >> >>> >> more flexibility during instruction
selection later:
> >> >> >>> >> this
> >> >> >>> >> operation
> >> >> >>> >> is valid as long as the reduction
of all elements of the
> >> >> >>> >> result
> >> >> >>> >> vector is identical to the
reduction of all elements of
> >> >> >>> >> its
> >> >> >>> >> operands.
> >> >> >>> >>
> >> >> >>> >> One example that can benefit this
property is SAD (sum
> >> >> >>> >> of
> >> >> >>> >> absolute
> >> >> >>> >> differences) pattern detection in
SSE2, which provides a
> >> >> >>> >> psadbw
> >> >> >>> >> instruction whose description is
shown below:
> >> >> >>> >>
> >> >> >>> >> '''
> >> >> >>> >> psadbw: Compute the absolute
differences of packed
> >> >> >>> >> unsigned
> >> >> >>> >> 8-bit
> >> >> >>> >> integers in a and b, then
horizontally sum each
> >> >> >>> >> consecutive
> >> >> >>> >> 8
> >> >> >>> >> differences to produce two unsigned
16-bit integers, and
> >> >> >>> >> pack
> >> >> >>> >> these
> >> >> >>> >> unsigned 16-bit integers in the low
16 bits of 64-bit
> >> >> >>> >> elements
> >> >> >>> >> in dst.
> >> >> >>> >> '''
> >> >> >>> >>
> >> >> >>> >> In LLVM's IR, for a SAD loop we
will have two v4i8 as
> >> >> >>> >> inputs
> >> >> >>> >> and one
> >> >> >>> >> v4i32 as output. However, psadbw
will actually produce
> >> >> >>> >> one
> >> >> >>> >> i32
> >> >> >>> >> result
> >> >> >>> >> for four pairs of 8-bit integers
(an already reduced
> >> >> >>> >> result),
> >> >> >>> >> and the
> >> >> >>> >> result is stored in the first
element in v4i32. If we
> >> >> >>> >> properly
> >> >> >>> >> zero
> >> >> >>> >> out the other three elements in
v4i32, and with the
> >> >> >>> >> information that
> >> >> >>> >> we have a reduction add that is
performed on this
> >> >> >>> >> result,
> >> >> >>> >> then
> >> >> >>> >> we can
> >> >> >>> >> safely use psadbw here for much
better performance. This
> >> >> >>> >> can
> >> >> >>> >> be done
> >> >> >>> >> during DAG combine. Another similar
example is dot
> >> >> >>> >> product.
> >> >> >>> >> And I
> >> >> >>> >> think there may be many other
scenarios that can benefit
> >> >> >>> >> from
> >> >> >>> >> this
> >> >> >>> >> property like eliminating redundant
shuffles.
> >> >> >>> >>
> >> >> >>> >> The question is, how to let DAG
combiner know that a
> >> >> >>> >> vector
> >> >> >>> >> operation
> >> >> >>> >> is a reduction one?
> >> >> >>> >>
> >> >> >>> >> Here I propose to introduce a
"reduction add"
> >> >> >>> >> instruction
> >> >> >>> >> for
> >> >> >>> >> vectors.
> >> >> >>> >> This will be a new instruction with
vector operands
> >> >> >>> >> only.
> >> >> >>> >> Normally it
> >> >> >>> >> is treated as a normal ADD
operation, but the selection
> >> >> >>> >> DAG
> >> >> >>> >> combiner
> >> >> >>> >> can make use of this new operation
to generate better
> >> >> >>> >> instructions.
> >> >> >>> >> This new instruction is generated
when vectorizing
> >> >> >>> >> reduction
> >> >> >>> >> add in
> >> >> >>> >> loop vectorizer.
> >> >> >>> >>
> >> >> >>> >> I would like to hear more comments
on this proposal or
> >> >> >>> >> suggestions of
> >> >> >>> >> better alternative implementations.
> >> >> >>> >>
> >> >> >>> >>
> >> >> >>> >> thanks,
> >> >> >>> >> Cong
> >> >> >>> >>
_______________________________________________
> >> >> >>> >> LLVM Developers mailing list
> >> >> >>> >> llvm-dev at lists.llvm.org
> >> >> >>> >>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >> >> _______________________________________________
> >> >> LLVM Developers mailing list
> >> >> llvm-dev at lists.llvm.org
> >> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >> >>
> >> >
> >> > --
> >> > Hal Finkel
> >> > Assistant Computational Scientist
> >> > Leadership Computing Facility
> >> > Argonne National Laboratory
> >>
> >>
> >
> > --
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory