<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Sep 18, 2014, at 11:48 AM, suyog sarda <<a href="mailto:sardask01@gmail.com" class="">sardask01@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class="">Hi,<br class=""><br class=""></div>I am trying to understand LLVM vectorization implementation and was looking into both loop and SLP vectorization.<br class=""><br class=""></div>test case 1:<br class=""><br class=""></div><i class="">int foo(int *a) {<br class="">int sum = 0,i;<br class="">for(i=0; i<16; i++)<br class=""> sum += a[i];<br class="">return sum;<br class="">}</i><br class=""><br class=""></div>This code is vectorized by loop vectorizer where we calculate scalar loop cost as 4 and vector loop cost as 2.<br class=""></div>Since vector loop cost is less and above reduction is legal to vectorize, loop vectorizer produces vectorized code :<br class=""><br class=""></div><u class=""><b class="">IR without vectorization:</b></u><br class=""><i class=""><br class="">target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"<br class="">target triple = "x86_64-pc-linux-gnu"<br class=""><br class="">; Function Attrs: nounwind readonly<br class="">define i32 @foo(i32* nocapture readonly %a, i32 %n) #0 {<br class="">entry:<br class=""> br label %for.body<br class=""><br class="">for.body: ; preds = %for.body, %entry<br class=""> %i.05 = phi i32 [ 0, %entry ], [ %inc, %for.body ]<br class=""> %sum.04 = phi i32 [ 0, %entry ], [ %add, %for.body ]<br class=""> %arrayidx = getelementptr inbounds i32* %a, i32 %i.05<br class=""> %0 = load i32* %arrayidx, align 4, !tbaa !1<br class=""> %add = add nsw i32 %0, %sum.04<br class=""> %inc = add nsw i32 %i.05, 1<br class=""> %exitcond = icmp eq i32 %i.05, 15<br class=""> br i1 %exitcond, label %for.end, label %for.body<br class=""><br class="">for.end: ; preds = %for.body<br class=""> ret i32 %add<br class="">}</i><br class=""><br class=""></div><u class=""><b class="">IR after vectorization:</b><br class=""></u><br class=""><i class="">target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"<br class="">target triple = "x86_64-pc-linux-gnu"<br class=""><br class="">; Function Attrs: nounwind readonly<br class="">define i32 @foo(i32* nocapture readonly %a, i32 %n) #0 {<br class="">entry:<br class=""> %backedge.overflow = icmp eq i32 15, -1<br class=""> %overflow.check.anchor = add i32 0, 0<br class=""> br i1 %backedge.overflow, label %<a href="http://scalar.ph/" class="">scalar.ph</a>, label %overflow.checked<br class=""><br class="">overflow.checked: ; preds = %entry<br class=""> br i1 false, label %middle.block, label %<a href="http://vector.ph/" class="">vector.ph</a><br class=""><br class=""><a href="http://vector.ph/" class="">vector.ph</a>: ; preds = %overflow.checked<br class=""> br label %vector.body<br class=""><br class="">vector.body: ; preds = %vector.body, %<a href="http://vector.ph/" class="">vector.ph</a><br class=""> %index = phi i32 [ 0, %<a href="http://vector.ph/" class="">vector.ph</a> ], [ %index.next, %vector.body ]<br class=""> %vec.phi = phi <4 x i32> [ zeroinitializer, %<a href="http://vector.ph/" class="">vector.ph</a> ], [ %14, %vector.body ]<br class=""> %broadcast.splatinsert = insertelement <4 x i32> undef, i32 %index, i32 0<br class=""> %broadcast.splat = shufflevector <4 x i32> %broadcast.splatinsert, <4 x i32> undef, <4 x i32> zeroinitializer<br class=""> %induction = add <4 x i32> %broadcast.splat, <i32 0, i32 1, i32 2, i32 3><br class=""> %0 = extractelement <4 x i32> %induction, i32 0<br class=""> %1 = getelementptr inbounds i32* %a, i32 %0<br class=""> %2 = insertelement <4 x i32*> undef, i32* %1, i32 0<br class=""> %3 = extractelement <4 x i32> %induction, i32 1<br class=""> %4 = getelementptr inbounds i32* %a, i32 %3<br class=""> %5 = insertelement <4 x i32*> %2, i32* %4, i32 1<br class=""> %6 = extractelement <4 x i32> %induction, i32 2<br class=""> %7 = getelementptr inbounds i32* %a, i32 %6<br class=""> %8 = insertelement <4 x i32*> %5, i32* %7, i32 2<br class=""> %9 = extractelement <4 x i32> %induction, i32 3<br class=""> %10 = getelementptr inbounds i32* %a, i32 %9<br class=""> %11 = insertelement <4 x i32*> %8, i32* %10, i32 3<br class=""> %12 = getelementptr i32* %1, i32 0<br class=""> %13 = bitcast i32* %12 to <4 x i32>*<br class=""> %wide.load = load <4 x i32>* %13, align 4, !tbaa !1<br class=""> %14 = add nsw <4 x i32> %wide.load, %vec.phi<br class=""> %15 = add nsw <4 x i32> %induction, <i32 1, i32 1, i32 1, i32 1><br class=""> %16 = icmp eq <4 x i32> %induction, <i32 15, i32 15, i32 15, i32 15><br class=""> %index.next = add i32 %index, 4<br class=""> %17 = icmp eq i32 %index.next, 16<br class=""> br i1 %17, label %middle.block, label %vector.body, !llvm.loop !5<br class=""><br class="">middle.block: ; preds = %vector.body, %overflow.checked<br class=""> %resume.val = phi i32 [ 0, %overflow.checked ], [ 16, %vector.body ]<br class=""> %trunc.resume.val = phi i32 [ 0, %overflow.checked ], [ 16, %vector.body ]<br class=""> %rdx.vec.exit.phi = phi <4 x i32> [ zeroinitializer, %overflow.checked ], [ %14, %vector.body ]<br class=""> %rdx.shuf = shufflevector <4 x i32> %rdx.vec.exit.phi, <4 x i32> undef, <4 x i32> <i32 2, i32 3, i32 undef, i32 undef><br class=""> %bin.rdx = add <4 x i32> %rdx.vec.exit.phi, %rdx.shuf<br class=""> %rdx.shuf1 = shufflevector <4 x i32> %bin.rdx, <4 x i32> undef, <4 x i32> <i32 1, i32 undef, i32 undef, i32 undef><br class=""> %bin.rdx2 = add <4 x i32> %bin.rdx, %rdx.shuf1<br class=""> %18 = extractelement <4 x i32> %bin.rdx2, i32 0<br class=""> %cmp.n = icmp eq i32 16, %resume.val<br class=""> br i1 %cmp.n, label %for.end, label %<a href="http://scalar.ph/" class="">scalar.ph</a><br class=""><br class=""><a href="http://scalar.ph/" class="">scalar.ph</a>: ; preds = %middle.block, %entry<br class=""> %bc.resume.val = phi i32 [ %resume.val, %middle.block ], [ 0, %entry ]<br class=""> %bc.trunc.resume.val = phi i32 [ %trunc.resume.val, %middle.block ], [ 0, %entry ]<br class=""> %bc.merge.rdx = phi i32 [ 0, %entry ], [ %18, %middle.block ]<br class=""> br label %for.body<br class=""><br class="">for.body: ; preds = %for.body, %<a href="http://scalar.ph/" class="">scalar.ph</a><br class=""> %i.05 = phi i32 [ %bc.trunc.resume.val, %<a href="http://scalar.ph/" class="">scalar.ph</a> ], [ %inc, %for.body ]<br class=""> %sum.04 = phi i32 [ %bc.merge.rdx, %<a href="http://scalar.ph/" class="">scalar.ph</a> ], [ %add, %for.body ]<br class=""> %arrayidx = getelementptr inbounds i32* %a, i32 %i.05<br class=""> %19 = load i32* %arrayidx, align 4, !tbaa !1<br class=""> %add = add nsw i32 %19, %sum.04<br class=""> %inc = add nsw i32 %i.05, 1<br class=""> %exitcond = icmp eq i32 %i.05, 15<br class=""> br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !8<br class=""><br class="">for.end: ; preds = %middle.block, %for.body<br class=""> %add.lcssa = phi i32 [ %add, %for.body ], [ %18, %middle.block ]<br class=""> ret i32 %add.lcssa<br class="">}</i> <br class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class=""><br clear="all" class=""><div class=""><div class=""><div class=""><div class=""><br class=""></div><div class="">Now for test case 2, where we unroll the loop totally : <br class=""><br class=""><i class="">int foo(int *a) {<br class="">int sum = 0;<br class="">sum = a[0]+a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9]+a[10]+a[11]+a[12]+a[13]+a[14]+a[15];<br class="">return sum;<br class="">}</i><br class=""><br class=""></div><div class="">This code is not vectorized by SLP vectorization.<br class=""><br class=""></div><div class=""><u class=""><b class="">IR before vectorization: </b></u><br class=""><br class=""></div><div class="">test.ll<br class=""></div><div class=""><br class=""><i class="">target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"<br class="">target triple = "x86_64-pc-linux-gnu"<br class=""><br class="">; Function Attrs: nounwind readonly<br class="">define i32 @foo(i32* nocapture readonly %a, i32 %n) #0 {<br class="">entry:<br class=""> %0 = load i32* %a, align 4, !tbaa !1<br class=""> %arrayidx1 = getelementptr inbounds i32* %a, i32 1<br class=""> %1 = load i32* %arrayidx1, align 4, !tbaa !1<br class=""> %add = add nsw i32 %1, %0<br class=""> %arrayidx2 = getelementptr inbounds i32* %a, i32 2<br class=""> %2 = load i32* %arrayidx2, align 4, !tbaa !1<br class=""> %add3 = add nsw i32 %add, %2<br class=""> %arrayidx4 = getelementptr inbounds i32* %a, i32 3<br class=""> %3 = load i32* %arrayidx4, align 4, !tbaa !1<br class=""> %add5 = add nsw i32 %add3, %3<br class=""> %arrayidx6 = getelementptr inbounds i32* %a, i32 4<br class=""> %4 = load i32* %arrayidx6, align 4, !tbaa !1<br class=""> %add7 = add nsw i32 %add5, %4<br class=""> %arrayidx8 = getelementptr inbounds i32* %a, i32 5<br class=""> %5 = load i32* %arrayidx8, align 4, !tbaa !1<br class=""> %add9 = add nsw i32 %add7, %5<br class=""> %arrayidx10 = getelementptr inbounds i32* %a, i32 6<br class=""> %6 = load i32* %arrayidx10, align 4, !tbaa !1<br class=""> %add11 = add nsw i32 %add9, %6<br class=""> %arrayidx12 = getelementptr inbounds i32* %a, i32 7<br class=""> %7 = load i32* %arrayidx12, align 4, !tbaa !1<br class=""> %add13 = add nsw i32 %add11, %7<br class=""> %arrayidx14 = getelementptr inbounds i32* %a, i32 8<br class=""> %8 = load i32* %arrayidx14, align 4, !tbaa !1<br class=""> %add15 = add nsw i32 %add13, %8<br class=""> %arrayidx16 = getelementptr inbounds i32* %a, i32 9<br class=""> %9 = load i32* %arrayidx16, align 4, !tbaa !1<br class=""> %add17 = add nsw i32 %add15, %9<br class=""> %arrayidx18 = getelementptr inbounds i32* %a, i32 10<br class=""> %10 = load i32* %arrayidx18, align 4, !tbaa !1<br class=""> %add19 = add nsw i32 %add17, %10<br class=""> %arrayidx20 = getelementptr inbounds i32* %a, i32 11<br class=""> %11 = load i32* %arrayidx20, align 4, !tbaa !1<br class=""> %add21 = add nsw i32 %add19, %11<br class=""> %arrayidx22 = getelementptr inbounds i32* %a, i32 12<br class=""> %12 = load i32* %arrayidx22, align 4, !tbaa !1<br class=""> %add23 = add nsw i32 %add21, %12<br class=""> %arrayidx24 = getelementptr inbounds i32* %a, i32 13<br class=""> %13 = load i32* %arrayidx24, align 4, !tbaa !1<br class=""> %add25 = add nsw i32 %add23, %13<br class=""> %arrayidx26 = getelementptr inbounds i32* %a, i32 14<br class=""> %14 = load i32* %arrayidx26, align 4, !tbaa !1<br class=""> %add27 = add nsw i32 %add25, %14<br class=""> %arrayidx28 = getelementptr inbounds i32* %a, i32 15<br class=""> %15 = load i32* %arrayidx28, align 4, !tbaa !1<br class=""> %add29 = add nsw i32 %add27, %15<br class=""> ret i32 %add29<br class="">}<br class=""></i><br class="">$ opt -S -slp-vectorizer -slp-vectorize-hor test.ll -debug -o test2.ll <br class=""><br class="">Features:+64bit,+sse2<br class="">CPU:generic<br class=""><br class="">Subtarget features: SSELevel 3, 3DNowLevel 0, 64bit 1<br class="">SLP: Analyzing blocks in foo.<br class=""><br class=""></div><div class=""><u class=""><b class="">test2.ll (IR after SLP vectorization) :</b></u><br class=""><br class=""><i class="">target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"<br class="">target triple = "x86_64-pc-linux-gnu"<br class=""><br class="">; Function Attrs: nounwind readonly<br class="">define i32 @foo(i32* nocapture readonly %a, i32 %n) #0 {<br class="">entry:<br class=""> %0 = load i32* %a, align 4, !tbaa !1<br class=""> %arrayidx1 = getelementptr inbounds i32* %a, i32 1<br class=""> %1 = load i32* %arrayidx1, align 4, !tbaa !1<br class=""> %add = add nsw i32 %1, %0<br class=""> %arrayidx2 = getelementptr inbounds i32* %a, i32 2<br class=""> %2 = load i32* %arrayidx2, align 4, !tbaa !1<br class=""> %add3 = add nsw i32 %add, %2<br class=""> %arrayidx4 = getelementptr inbounds i32* %a, i32 3<br class=""> %3 = load i32* %arrayidx4, align 4, !tbaa !1<br class=""> %add5 = add nsw i32 %add3, %3<br class=""> %arrayidx6 = getelementptr inbounds i32* %a, i32 4<br class=""> %4 = load i32* %arrayidx6, align 4, !tbaa !1<br class=""> %add7 = add nsw i32 %add5, %4<br class=""> %arrayidx8 = getelementptr inbounds i32* %a, i32 5<br class=""> %5 = load i32* %arrayidx8, align 4, !tbaa !1<br class=""> %add9 = add nsw i32 %add7, %5<br class=""> %arrayidx10 = getelementptr inbounds i32* %a, i32 6<br class=""> %6 = load i32* %arrayidx10, align 4, !tbaa !1<br class=""> %add11 = add nsw i32 %add9, %6<br class=""> %arrayidx12 = getelementptr inbounds i32* %a, i32 7<br class=""> %7 = load i32* %arrayidx12, align 4, !tbaa !1<br class=""> %add13 = add nsw i32 %add11, %7<br class=""> %arrayidx14 = getelementptr inbounds i32* %a, i32 8<br class=""> %8 = load i32* %arrayidx14, align 4, !tbaa !1<br class=""> %add15 = add nsw i32 %add13, %8<br class=""> %arrayidx16 = getelementptr inbounds i32* %a, i32 9<br class=""> %9 = load i32* %arrayidx16, align 4, !tbaa !1<br class=""> %add17 = add nsw i32 %add15, %9<br class=""> %arrayidx18 = getelementptr inbounds i32* %a, i32 10<br class=""> %10 = load i32* %arrayidx18, align 4, !tbaa !1<br class=""> %add19 = add nsw i32 %add17, %10<br class=""> %arrayidx20 = getelementptr inbounds i32* %a, i32 11<br class=""> %11 = load i32* %arrayidx20, align 4, !tbaa !1<br class=""> %add21 = add nsw i32 %add19, %11<br class=""> %arrayidx22 = getelementptr inbounds i32* %a, i32 12<br class=""> %12 = load i32* %arrayidx22, align 4, !tbaa !1<br class=""> %add23 = add nsw i32 %add21, %12<br class=""> %arrayidx24 = getelementptr inbounds i32* %a, i32 13<br class=""> %13 = load i32* %arrayidx24, align 4, !tbaa !1<br class=""> %add25 = add nsw i32 %add23, %13<br class=""> %arrayidx26 = getelementptr inbounds i32* %a, i32 14<br class=""> %14 = load i32* %arrayidx26, align 4, !tbaa !1<br class=""> %add27 = add nsw i32 %add25, %14<br class=""> %arrayidx28 = getelementptr inbounds i32* %a, i32 15<br class=""> %15 = load i32* %arrayidx28, align 4, !tbaa !1<br class=""> %add29 = add nsw i32 %add27, %15<br class=""> ret i32 %add29<br class="">}<br class=""><br class=""></i></div><div class="">Shouldn't the SLP vectorizer vectorize above code? Am I missing out something?<br class=""></div><div class="">How does loop unrolling affect the final vectorization of code?<br class=""></div><div class=""><br class=""></div></div></div></div></div></div></div></div></div></div></div></div></div></blockquote><div><br class=""></div><div>Hi Suyog, </div><div><br class=""></div><div>Thank you for taking the time to investigate the performance of the vectorizers. You are correct that the SLP-vectorizer should be able to do something about the second case (the unrolled one). Please look into line 2861 in the SLP-vectorizer. This is where we try to analyze reductions and vectorize them. At the moment we don’t have support for a flat yet large reduction that is the result of unrolled loops because the current algorithm tries to construct trees that start at the chains, and it does not support joining multiple trees. </div><div><br class=""></div><div><a href="http://llvm.org/docs/doxygen/html/SLPVectorizer_8cpp_source.html#l02861" class="">http://llvm.org/docs/doxygen/html/SLPVectorizer_8cpp_source.html#l02861</a></div><div><br class=""></div><div>Thanks,</div><div>Nadav</div><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class=""><div class="">I tried to debug above IR. Since there is no store in above IR, SLP vectorization doesn't call <br class="">vectorizeStoreChains(). In vectorizeChainsInBlock(), as there is no phi node in above IR, it<br class="">also fails to vectorize the IR.<br class=""><br class=""></div><div class="">If it is perfectly legal to vectorize above IR, are we lacking code for it right now? Or its not <br class=""></div><div class="">possible to vectorize above code (as far as i know, it is perfectly possible to vectorize above code)?<br class=""></div><div class="">If its possible, can someone help me/point out specifics how to start for implementing vectorization for such code?<br class=""></div><div class="">(We do have function calls isConsecutiveAccess() to identify it. Is it a case for horizontal reduction, though the term<br class="">'reduction' is associated with loops/phi nodes.)<br class=""></div><div class=""><br class=""></div><div class="">This brings to me another question - if we perform aggressive loop unrolling, we might loose opportunity for<br class=""></div><div class="">vectorization as visible above !!<br class=""><br class=""></div><div class="">(I was looking into bug 20035, when i encountered above issue. Though both are not related.)<br class=""><br class=""></div><div class="">Your comments/suggestions are most awaited.<br class=""></div><div class=""><br class=""> <br class=""></div><div class="">-- <br class="">With regards,<br class="">Suyog Sarda<br class="">
</div></div></div></div></div></div></div></div></div></div></div></div>
</div></blockquote></div><br class=""></body></html>