<div dir="ltr">While there are no instructions in e.g. ARMv7 to do horizontal reductions in a single instruction, you can still do better than the loop in the source code, and the easy way to get the optimum result is probably to transform the loop into a horizontal reduction intrinsic and then lower it to a target-appropriate sequence of instructions.<div><br></div><div>e.g.</div><div><br></div><div><div>vpadd.i8<span style="white-space:pre">     </span>d1, d16, d17</div><div>vpaddl.u8<span class="" style="white-space:pre">      </span>d1, d1</div><div>vpaddl.u16<span class="" style="white-space:pre">   </span>d1, d1</div><div>vmov.32<span class="" style="white-space:pre">      </span>r1, d1[1]</div><div>vmov.32<span class="" style="white-space:pre">   </span>r0, d1[0]</div><div>add<span class="" style="white-space:pre">       </span>r0, r1</div></div><div><br></div><div>(I'm not sure offhand whether an additional reduction stage in the vector unit and transferring just one result to the integer registers is possible or desirable)</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Nov 12, 2014 at 4:00 AM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">----- Original Message -----<br>
> From: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>><br>
> To: "James Molloy" <<a href="mailto:james@jamesmolloy.co.uk">james@jamesmolloy.co.uk</a>><br>
> Cc: <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a><br>
</span><div><div class="h5">> Sent: Tuesday, November 11, 2014 8:54:01 AM<br>
> Subject: Re: [LLVMdev] supporting SAD in loop vectorizer<br>
><br>
> ----- Original Message -----<br>
> > From: "James Molloy" <<a href="mailto:james@jamesmolloy.co.uk">james@jamesmolloy.co.uk</a>><br>
> > To: "Hal Finkel" <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>><br>
> > Cc: "Dibyendu Das" <<a href="mailto:Dibyendu.Das@amd.com">Dibyendu.Das@amd.com</a>>, <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a><br>
> > Sent: Tuesday, November 11, 2014 8:21:37 AM<br>
> > Subject: Re: [LLVMdev] supporting SAD in loop vectorizer<br>
> ><br>
> ><br>
> > If you'd like to contribute support for this, look at<br>
> > isHorizontalBinOp and go from there. Feel free to ask questions if<br>
> > you get stuck.<br>
> ><br>
> ><br>
> ><br>
> > FWIW, I've looked at isHorizontalBinOp for inspiration for matching<br>
> > AArch64 ADDV-and-friends (horizontal reduction operations), and<br>
> > thought it was rather temperamental and noticed it being prone to<br>
> > breaking depending on the exact format of the IR. Given that we<br>
> > don't have a canonical form for reductions, I think it wrong that<br>
> > we<br>
> > expect targets to undo quite complex patterns.<br>
> ><br>
> ><br>
> > The reduction pattern is a log2(n) sequence of shuffles and binops,<br>
> > that are really rather complex. These sort of things should, IMHO,<br>
> > be intrinsics. I chatted with Arnold about this at the devmtg and<br>
> > was going to send a patch to do exactly that in a week or so.<br>
><br>
> Sounds good. We should try hard to canonicalize into the intrinsic in<br>
> InstCombine from the shuffles<br>
<br>
</div></div>Or maybe we should do this in CGP -- would we want to do this if there is no actual target support?<br>
<span class="HOEnZb"><font color="#888888"><br>
 -Hal<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
> (in addition to emitting it directly<br>
> from the vectorizer), but it is likely easier to do there than in<br>
> the backend.<br>
><br>
>  -Hal<br>
><br>
> ><br>
> ><br>
> > Cheers,<br>
> ><br>
> ><br>
> > James<br>
> ><br>
> ><br>
> > On 11 November 2014 13:35, Hal Finkel < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> > wrote:<br>
> ><br>
> ><br>
> > ----- Original Message -----<br>
> > > From: "Dibyendu Das" < <a href="mailto:Dibyendu.Das@amd.com">Dibyendu.Das@amd.com</a> ><br>
> > > To: "Hal Finkel" < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> >, "Renato Golin" <<br>
> > > <a href="mailto:renato.golin@linaro.org">renato.golin@linaro.org</a> ><br>
> > > Cc: <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a><br>
> > > Sent: Tuesday, November 4, 2014 12:15:12 PM<br>
> > > Subject: RE: [LLVMdev] supporting SAD in loop vectorizer<br>
> > ><br>
> > > Here's the simple SAD code:<br>
> > > ---------------------------------------------------<br>
> > > 1 #include <stdlib.h><br>
> > > 2<br>
> > > 3 extern int ly,lx;<br>
> > > 4 int sad_c( unsigned char *pix1, unsigned char *pix2)<br>
> > > 5 {<br>
> > > 6 int i_sum = 0;<br>
> > > 7 for( int x = 0; x < lx; x++ )<br>
> > > 8 i_sum += abs( pix1[x] - pix2[x] );<br>
> > > 9 return i_sum;<br>
> > > 10 }<br>
> > > 11<br>
> > > -----------------------------------------------------<br>
> > ><br>
> > > The loop vectorizer does vectorize the loop and then unrolls it<br>
> > > twice. The main body of the loop at the end looks like below<br>
> > > where<br>
> > > we see the icmp, neg select pattern appearing twice.<br>
> > > Are we saying we pattern match this to PSADBW in target ?<br>
> ><br>
> > Yes.<br>
> ><br>
> > > That seems<br>
> > > to have some challenges<br>
> ><br>
> > It does, but we already have code in the backend that matches other<br>
> > horizontal operations (see isHorizontalBinOp and its callers in<br>
> > lib/Target/X86/X86ISelLowering.cpp), and I suspect this won't be<br>
> > significantly more complicated.<br>
> ><br>
> > > including the fact that we would need a<br>
> > > 4-way unroll to use all of 128b PSADBWs. Or am I<br>
> > > missing something ?<br>
> ><br>
> > No, each unrolling will get its own, so you'll get a PSADBW from<br>
> > each<br>
> > time the loop is unrolled. Each unrolling is vectorized in terms of<br>
> > <4 x i32>, and that is the 128 bits you need.<br>
> ><br>
> > If you'd like to contribute support for this, look at<br>
> > isHorizontalBinOp and go from there. Feel free to ask questions if<br>
> > you get stuck.<br>
> ><br>
> > -Hal<br>
> ><br>
> ><br>
> ><br>
> > ><br>
> > > 2783 vector.body: ; preds =<br>
> > > %vector.body.preheader, %vector.body<br>
> > > 2784 %index = phi i64 [ %index.next, %vector.body ], [ 0,<br>
> > > %vector.body.preheader ]<br>
> > > 2785 %vec.phi = phi <4 x i32> [ %24, %vector.body ], [<br>
> > > zeroinitializer, %vector.body.preheader ]<br>
> > > 2786 %vec.phi9 = phi <4 x i32> [ %25, %vector.body ], [<br>
> > > zeroinitializer, %vector.body.preheader ]<br>
> > > 2787 %4 = getelementptr inbounds i8* %pix1, i64 %index<br>
> > > 2788 %5 = bitcast i8* %4 to <4 x i8>*<br>
> > > 2789 %wide.load = load <4 x i8>* %5, align 1<br>
> > > 2790 %.sum19 = or i64 %index, 4<br>
> > > 2791 %6 = getelementptr i8* %pix1, i64 %.sum19<br>
> > > 2792 %7 = bitcast i8* %6 to <4 x i8>*<br>
> > > 2793 %wide.load10 = load <4 x i8>* %7, align 1<br>
> > > 2794 %8 = zext <4 x i8> %wide.load to <4 x i32><br>
> > > 2795 %9 = zext <4 x i8> %wide.load10 to <4 x i32><br>
> > > 2796 %10 = getelementptr inbounds i8* %pix2, i64 %index<br>
> > > 2797 %11 = bitcast i8* %10 to <4 x i8>*<br>
> > > 2798 %wide.load11 = load <4 x i8>* %11, align 1<br>
> > > 2799 %.sum20 = or i64 %index, 4<br>
> > > 2800 %12 = getelementptr i8* %pix2, i64 %.sum20<br>
> > > 2801 %13 = bitcast i8* %12 to <4 x i8>*<br>
> > > 2802 %wide.load12 = load <4 x i8>* %13, align 1<br>
> > > 2803 %14 = zext <4 x i8> %wide.load11 to <4 x i32><br>
> > > 2804 %15 = zext <4 x i8> %wide.load12 to <4 x i32><br>
> > > 2805 %16 = sub nsw <4 x i32> %8, %14<br>
> > > 2806 %17 = sub nsw <4 x i32> %9, %15<br>
> > > 2807 %18 = icmp sgt <4 x i32> %16, <i32 -1, i32 -1, i32 -1, i32<br>
> > > -1><br>
> > > 2808 %19 = icmp sgt <4 x i32> %17, <i32 -1, i32 -1, i32 -1, i32<br>
> > > -1><br>
> > > 2809 %20 = sub <4 x i32> zeroinitializer, %16<br>
> > > 2810 %21 = sub <4 x i32> zeroinitializer, %17<br>
> > > 2811 %22 = select <4 x i1> %18, <4 x i32> %16, <4 x i32> %20<br>
> > > 2812 %23 = select <4 x i1> %19, <4 x i32> %17, <4 x i32> %21<br>
> > > 2813 %24 = add nsw <4 x i32> %22, %vec.phi<br>
> > > 2814 %25 = add nsw <4 x i32> %23, %vec.phi9<br>
> > > 2815 %index.next = add i64 %index, 8<br>
> > > 2816 %26 = icmp eq i64 %index.next, %n.vec<br>
> > > 2817 br i1 %26, label %middle.block.loopexit, label %vector.body,<br>
> > > !llvm.loop !1<br>
> > > -----------------------------------------------------<br>
> > ><br>
> > > -----Original Message-----<br>
> > > From: Hal Finkel [mailto: <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> ]<br>
> > > Sent: Tuesday, November 04, 2014 9:54 PM<br>
> > > To: Renato Golin<br>
> > > Cc: <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a> ; Das, Dibyendu<br>
> > > Subject: Re: [LLVMdev] supporting SAD in loop vectorizer<br>
> > ><br>
> > > ----- Original Message -----<br>
> > > > From: "Renato Golin" < <a href="mailto:renato.golin@linaro.org">renato.golin@linaro.org</a> ><br>
> > > > To: "Dibyendu Das" < <a href="mailto:Dibyendu.Das@amd.com">Dibyendu.Das@amd.com</a> ><br>
> > > > Cc: <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a><br>
> > > > Sent: Tuesday, November 4, 2014 5:23:30 AM<br>
> > > > Subject: Re: [LLVMdev] supporting SAD in loop vectorizer<br>
> > > ><br>
> > > > On 4 November 2014 11:06, Das, Dibyendu < <a href="mailto:Dibyendu.Das@amd.com">Dibyendu.Das@amd.com</a><br>
> > > > ><br>
> > > > wrote:<br>
> > > > > Is there any plan to support special idioms in the loop<br>
> > > > > vectorizer<br>
> > > > > like sum of absolute difference (SAD) ? We see some useful<br>
> > > > > cases<br>
> > > > > where llvm is losing performance at -O3 due to SADs not being<br>
> > > > > vectorized (hence PSADBWs not being generated).<br>
> > > ><br>
> > > > It's been a while, but this could either be that the<br>
> > > > legalisation<br>
> > > > phase is not recognising the reduction or that the cost is not<br>
> > > > taking<br>
> > > > into account the lowered abs().<br>
> > > ><br>
> > > > What does -debug-only=loop-vectorize say about it?<br>
> > ><br>
> > > FWIW, I agree, this sounds like a cost-model problem. The<br>
> > > loop-vectorizer should be able to vectorize the 'icmp; neg;<br>
> > > select'<br>
> > > pattern, and then the backend can pattern-patch that with the<br>
> > > reduction (which is a series of shuffles and extract_element)<br>
> > > into<br>
> > > the single instruction PSADBW -- we're quite likely missing the<br>
> > > target code to do that.<br>
> > ><br>
> > > -Hal<br>
> > ><br>
> > > ><br>
> > > > cheers,<br>
> > > > --renato<br>
> > > > _______________________________________________<br>
> > > > LLVM Developers mailing list<br>
> > > > <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> > > > <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
> > > ><br>
> > ><br>
> > > --<br>
> > > Hal Finkel<br>
> > > Assistant Computational Scientist<br>
> > > Leadership Computing Facility<br>
> > > Argonne National Laboratory<br>
> > ><br>
> ><br>
> > --<br>
> > Hal Finkel<br>
> > Assistant Computational Scientist<br>
> > Leadership Computing Facility<br>
> > Argonne National Laboratory<br>
> > _______________________________________________<br>
> > LLVM Developers mailing list<br>
> > <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> > <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
> ><br>
> ><br>
><br>
> --<br>
> Hal Finkel<br>
> Assistant Computational Scientist<br>
> Leadership Computing Facility<br>
> Argonne National Laboratory<br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
><br>
<br>
--<br>
Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</div></div></blockquote></div><br></div>