<div dir="ltr"><div><div><div><div><div><div><div>Hi,<br><br></div>I am trying to understand LLVM vectorization implementation and was looking into both loop and SLP vectorization.<br><br></div>test case 1:<br><br></div><i>int foo(int *a) {<br>int sum = 0,i;<br>for(i=0; i<16; i++)<br> sum += a[i];<br>return sum;<br>}</i><br><br></div>This code is vectorized by loop vectorizer where we calculate scalar loop cost as 4 and vector loop cost as 2.<br></div>Since vector loop cost is less and above reduction is legal to vectorize, loop vectorizer produces vectorized code :<br><br></div><u><b>IR without vectorization:</b></u><br><i><br>target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"<br>target triple = "x86_64-pc-linux-gnu"<br><br>; Function Attrs: nounwind readonly<br>define i32 @foo(i32* nocapture readonly %a, i32 %n) #0 {<br>entry:<br> br label %for.body<br><br>for.body: ; preds = %for.body, %entry<br> %i.05 = phi i32 [ 0, %entry ], [ %inc, %for.body ]<br> %sum.04 = phi i32 [ 0, %entry ], [ %add, %for.body ]<br> %arrayidx = getelementptr inbounds i32* %a, i32 %i.05<br> %0 = load i32* %arrayidx, align 4, !tbaa !1<br> %add = add nsw i32 %0, %sum.04<br> %inc = add nsw i32 %i.05, 1<br> %exitcond = icmp eq i32 %i.05, 15<br> br i1 %exitcond, label %for.end, label %for.body<br><br>for.end: ; preds = %for.body<br> ret i32 %add<br>}</i><br><br></div><u><b>IR after vectorization:</b><br></u><br><i>target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"<br>target triple = "x86_64-pc-linux-gnu"<br><br>; Function Attrs: nounwind readonly<br>define i32 @foo(i32* nocapture readonly %a, i32 %n) #0 {<br>entry:<br> %backedge.overflow = icmp eq i32 15, -1<br> %overflow.check.anchor = add i32 0, 0<br> br i1 %backedge.overflow, label %<a href="http://scalar.ph">scalar.ph</a>, label %overflow.checked<br><br>overflow.checked: ; preds = %entry<br> br i1 false, label %middle.block, label %<a href="http://vector.ph">vector.ph</a><br><br><a href="http://vector.ph">vector.ph</a>: ; preds = %overflow.checked<br> br label %vector.body<br><br>vector.body: ; preds = %vector.body, %<a href="http://vector.ph">vector.ph</a><br> %index = phi i32 [ 0, %<a href="http://vector.ph">vector.ph</a> ], [ %index.next, %vector.body ]<br> %vec.phi = phi <4 x i32> [ zeroinitializer, %<a href="http://vector.ph">vector.ph</a> ], [ %14, %vector.body ]<br> %broadcast.splatinsert = insertelement <4 x i32> undef, i32 %index, i32 0<br> %broadcast.splat = shufflevector <4 x i32> %broadcast.splatinsert, <4 x i32> undef, <4 x i32> zeroinitializer<br> %induction = add <4 x i32> %broadcast.splat, <i32 0, i32 1, i32 2, i32 3><br> %0 = extractelement <4 x i32> %induction, i32 0<br> %1 = getelementptr inbounds i32* %a, i32 %0<br> %2 = insertelement <4 x i32*> undef, i32* %1, i32 0<br> %3 = extractelement <4 x i32> %induction, i32 1<br> %4 = getelementptr inbounds i32* %a, i32 %3<br> %5 = insertelement <4 x i32*> %2, i32* %4, i32 1<br> %6 = extractelement <4 x i32> %induction, i32 2<br> %7 = getelementptr inbounds i32* %a, i32 %6<br> %8 = insertelement <4 x i32*> %5, i32* %7, i32 2<br> %9 = extractelement <4 x i32> %induction, i32 3<br> %10 = getelementptr inbounds i32* %a, i32 %9<br> %11 = insertelement <4 x i32*> %8, i32* %10, i32 3<br> %12 = getelementptr i32* %1, i32 0<br> %13 = bitcast i32* %12 to <4 x i32>*<br> %wide.load = load <4 x i32>* %13, align 4, !tbaa !1<br> %14 = add nsw <4 x i32> %wide.load, %vec.phi<br> %15 = add nsw <4 x i32> %induction, <i32 1, i32 1, i32 1, i32 1><br> %16 = icmp eq <4 x i32> %induction, <i32 15, i32 15, i32 15, i32 15><br> %index.next = add i32 %index, 4<br> %17 = icmp eq i32 %index.next, 16<br> br i1 %17, label %middle.block, label %vector.body, !llvm.loop !5<br><br>middle.block: ; preds = %vector.body, %overflow.checked<br> %resume.val = phi i32 [ 0, %overflow.checked ], [ 16, %vector.body ]<br> %trunc.resume.val = phi i32 [ 0, %overflow.checked ], [ 16, %vector.body ]<br> %rdx.vec.exit.phi = phi <4 x i32> [ zeroinitializer, %overflow.checked ], [ %14, %vector.body ]<br> %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> %bin.rdx = add <4 x i32> %rdx.vec.exit.phi, %rdx.shuf<br> %rdx.shuf1 = shufflevector <4 x i32> %bin.rdx, <4 x i32> undef, <4 x i32> <i32 1, i32 undef, i32 undef, i32 undef><br> %bin.rdx2 = add <4 x i32> %bin.rdx, %rdx.shuf1<br> %18 = extractelement <4 x i32> %bin.rdx2, i32 0<br> %cmp.n = icmp eq i32 16, %resume.val<br> br i1 %cmp.n, label %for.end, label %<a href="http://scalar.ph">scalar.ph</a><br><br><a href="http://scalar.ph">scalar.ph</a>: ; preds = %middle.block, %entry<br> %bc.resume.val = phi i32 [ %resume.val, %middle.block ], [ 0, %entry ]<br> %bc.trunc.resume.val = phi i32 [ %trunc.resume.val, %middle.block ], [ 0, %entry ]<br> %bc.merge.rdx = phi i32 [ 0, %entry ], [ %18, %middle.block ]<br> br label %for.body<br><br>for.body: ; preds = %for.body, %<a href="http://scalar.ph">scalar.ph</a><br> %i.05 = phi i32 [ %bc.trunc.resume.val, %<a href="http://scalar.ph">scalar.ph</a> ], [ %inc, %for.body ]<br> %sum.04 = phi i32 [ %bc.merge.rdx, %<a href="http://scalar.ph">scalar.ph</a> ], [ %add, %for.body ]<br> %arrayidx = getelementptr inbounds i32* %a, i32 %i.05<br> %19 = load i32* %arrayidx, align 4, !tbaa !1<br> %add = add nsw i32 %19, %sum.04<br> %inc = add nsw i32 %i.05, 1<br> %exitcond = icmp eq i32 %i.05, 15<br> br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !8<br><br>for.end: ; preds = %middle.block, %for.body<br> %add.lcssa = phi i32 [ %add, %for.body ], [ %18, %middle.block ]<br> ret i32 %add.lcssa<br>}</i> <br><div><div><div><div><div><div><div><br clear="all"><div><div><div><div><br></div><div>Now for test case 2, where we unroll the loop totally : <br><br><i>int foo(int *a) {<br>int sum = 0;<br>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>return sum;<br>}</i><br><br></div><div>This code is not vectorized by SLP vectorization.<br><br></div><div><u><b>IR before vectorization: </b></u><br><br></div><div>test.ll<br></div><div><br><i>target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"<br>target triple = "x86_64-pc-linux-gnu"<br><br>; Function Attrs: nounwind readonly<br>define i32 @foo(i32* nocapture readonly %a, i32 %n) #0 {<br>entry:<br> %0 = load i32* %a, align 4, !tbaa !1<br> %arrayidx1 = getelementptr inbounds i32* %a, i32 1<br> %1 = load i32* %arrayidx1, align 4, !tbaa !1<br> %add = add nsw i32 %1, %0<br> %arrayidx2 = getelementptr inbounds i32* %a, i32 2<br> %2 = load i32* %arrayidx2, align 4, !tbaa !1<br> %add3 = add nsw i32 %add, %2<br> %arrayidx4 = getelementptr inbounds i32* %a, i32 3<br> %3 = load i32* %arrayidx4, align 4, !tbaa !1<br> %add5 = add nsw i32 %add3, %3<br> %arrayidx6 = getelementptr inbounds i32* %a, i32 4<br> %4 = load i32* %arrayidx6, align 4, !tbaa !1<br> %add7 = add nsw i32 %add5, %4<br> %arrayidx8 = getelementptr inbounds i32* %a, i32 5<br> %5 = load i32* %arrayidx8, align 4, !tbaa !1<br> %add9 = add nsw i32 %add7, %5<br> %arrayidx10 = getelementptr inbounds i32* %a, i32 6<br> %6 = load i32* %arrayidx10, align 4, !tbaa !1<br> %add11 = add nsw i32 %add9, %6<br> %arrayidx12 = getelementptr inbounds i32* %a, i32 7<br> %7 = load i32* %arrayidx12, align 4, !tbaa !1<br> %add13 = add nsw i32 %add11, %7<br> %arrayidx14 = getelementptr inbounds i32* %a, i32 8<br> %8 = load i32* %arrayidx14, align 4, !tbaa !1<br> %add15 = add nsw i32 %add13, %8<br> %arrayidx16 = getelementptr inbounds i32* %a, i32 9<br> %9 = load i32* %arrayidx16, align 4, !tbaa !1<br> %add17 = add nsw i32 %add15, %9<br> %arrayidx18 = getelementptr inbounds i32* %a, i32 10<br> %10 = load i32* %arrayidx18, align 4, !tbaa !1<br> %add19 = add nsw i32 %add17, %10<br> %arrayidx20 = getelementptr inbounds i32* %a, i32 11<br> %11 = load i32* %arrayidx20, align 4, !tbaa !1<br> %add21 = add nsw i32 %add19, %11<br> %arrayidx22 = getelementptr inbounds i32* %a, i32 12<br> %12 = load i32* %arrayidx22, align 4, !tbaa !1<br> %add23 = add nsw i32 %add21, %12<br> %arrayidx24 = getelementptr inbounds i32* %a, i32 13<br> %13 = load i32* %arrayidx24, align 4, !tbaa !1<br> %add25 = add nsw i32 %add23, %13<br> %arrayidx26 = getelementptr inbounds i32* %a, i32 14<br> %14 = load i32* %arrayidx26, align 4, !tbaa !1<br> %add27 = add nsw i32 %add25, %14<br> %arrayidx28 = getelementptr inbounds i32* %a, i32 15<br> %15 = load i32* %arrayidx28, align 4, !tbaa !1<br> %add29 = add nsw i32 %add27, %15<br> ret i32 %add29<br>}<br></i><br>$ opt -S -slp-vectorizer -slp-vectorize-hor test.ll -debug -o test2.ll <br><br>Features:+64bit,+sse2<br>CPU:generic<br><br>Subtarget features: SSELevel 3, 3DNowLevel 0, 64bit 1<br>SLP: Analyzing blocks in foo.<br><br></div><div><u><b>test2.ll (IR after SLP vectorization) :</b></u><br><br><i>target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"<br>target triple = "x86_64-pc-linux-gnu"<br><br>; Function Attrs: nounwind readonly<br>define i32 @foo(i32* nocapture readonly %a, i32 %n) #0 {<br>entry:<br> %0 = load i32* %a, align 4, !tbaa !1<br> %arrayidx1 = getelementptr inbounds i32* %a, i32 1<br> %1 = load i32* %arrayidx1, align 4, !tbaa !1<br> %add = add nsw i32 %1, %0<br> %arrayidx2 = getelementptr inbounds i32* %a, i32 2<br> %2 = load i32* %arrayidx2, align 4, !tbaa !1<br> %add3 = add nsw i32 %add, %2<br> %arrayidx4 = getelementptr inbounds i32* %a, i32 3<br> %3 = load i32* %arrayidx4, align 4, !tbaa !1<br> %add5 = add nsw i32 %add3, %3<br> %arrayidx6 = getelementptr inbounds i32* %a, i32 4<br> %4 = load i32* %arrayidx6, align 4, !tbaa !1<br> %add7 = add nsw i32 %add5, %4<br> %arrayidx8 = getelementptr inbounds i32* %a, i32 5<br> %5 = load i32* %arrayidx8, align 4, !tbaa !1<br> %add9 = add nsw i32 %add7, %5<br> %arrayidx10 = getelementptr inbounds i32* %a, i32 6<br> %6 = load i32* %arrayidx10, align 4, !tbaa !1<br> %add11 = add nsw i32 %add9, %6<br> %arrayidx12 = getelementptr inbounds i32* %a, i32 7<br> %7 = load i32* %arrayidx12, align 4, !tbaa !1<br> %add13 = add nsw i32 %add11, %7<br> %arrayidx14 = getelementptr inbounds i32* %a, i32 8<br> %8 = load i32* %arrayidx14, align 4, !tbaa !1<br> %add15 = add nsw i32 %add13, %8<br> %arrayidx16 = getelementptr inbounds i32* %a, i32 9<br> %9 = load i32* %arrayidx16, align 4, !tbaa !1<br> %add17 = add nsw i32 %add15, %9<br> %arrayidx18 = getelementptr inbounds i32* %a, i32 10<br> %10 = load i32* %arrayidx18, align 4, !tbaa !1<br> %add19 = add nsw i32 %add17, %10<br> %arrayidx20 = getelementptr inbounds i32* %a, i32 11<br> %11 = load i32* %arrayidx20, align 4, !tbaa !1<br> %add21 = add nsw i32 %add19, %11<br> %arrayidx22 = getelementptr inbounds i32* %a, i32 12<br> %12 = load i32* %arrayidx22, align 4, !tbaa !1<br> %add23 = add nsw i32 %add21, %12<br> %arrayidx24 = getelementptr inbounds i32* %a, i32 13<br> %13 = load i32* %arrayidx24, align 4, !tbaa !1<br> %add25 = add nsw i32 %add23, %13<br> %arrayidx26 = getelementptr inbounds i32* %a, i32 14<br> %14 = load i32* %arrayidx26, align 4, !tbaa !1<br> %add27 = add nsw i32 %add25, %14<br> %arrayidx28 = getelementptr inbounds i32* %a, i32 15<br> %15 = load i32* %arrayidx28, align 4, !tbaa !1<br> %add29 = add nsw i32 %add27, %15<br> ret i32 %add29<br>}<br><br></i></div><div>Shouldn't the SLP vectorizer vectorize above code? Am I missing out something?<br></div><div>How does loop unrolling affect the final vectorization of code?<br></div><div><br></div><div>I tried to debug above IR. Since there is no store in above IR, SLP vectorization doesn't call <br>vectorizeStoreChains(). In vectorizeChainsInBlock(), as there is no phi node in above IR, it<br>also fails to vectorize the IR.<br><br></div><div>If it is perfectly legal to vectorize above IR, are we lacking code for it right now? Or its not <br></div><div>possible to vectorize above code (as far as i know, it is perfectly possible to vectorize above code)?<br></div><div>If its possible, can someone help me/point out specifics how to start for implementing vectorization for such code?<br></div><div>(We do have function calls isConsecutiveAccess() to identify it. Is it a case for horizontal reduction, though the term<br>'reduction' is associated with loops/phi nodes.)<br></div><div><br></div><div>This brings to me another question - if we perform aggressive loop unrolling, we might loose opportunity for<br></div><div>vectorization as visible above !!<br><br></div><div>(I was looking into bug 20035, when i encountered above issue. Though both are not related.)<br><br></div><div>Your comments/suggestions are most awaited.<br></div><div><br> <br></div><div>-- <br>With regards,<br>Suyog Sarda<br>
</div></div></div></div></div></div></div></div></div></div></div></div>