<div dir="ltr">Hi Xiangyang,<div><br></div><div>The algorithm for loop unrolling was changed post-3.5 to do more what you'd expect. If you use 3.6 or 3.7 you'll likely get better results.</div><div><br></div><div>Cheers,</div><div><br></div><div>James</div></div><br><div class="gmail_quote"><div dir="ltr">On Thu, 20 Aug 2015 at 18:09 Philip Reames via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000">
<div>On 08/20/2015 07:38 AM, Xiangyang Guo
via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr"><span style="font-size:12.8000001907349px">Hi, </span>
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">I want to use loop
unrolling pass, however, I find that loop unrolling will
introduces conditional branch at end of every "unrolled" part.
For example, consider the following code</div>
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">
<div><i>void foo( int n, int array_x[])</i></div>
<div><i>{</i></div>
<div><i> for (int i=0; i < n; i++)</i></div>
<div><i><span style="white-space:pre-wrap"> </span>
array_x[i] = i; </i></div>
<div><i>}</i></div>
</div>
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">Then I use this
command "opt-3.5 try.bc -mem2reg -loops -loop-simplify
-loop-rotate -lcssa -indvars -loop-unroll -unroll-count=3
-simplifycfg -S", it gives me this IR:</div>
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">
<div><i>define void @_Z3fooiPi(i32 %n, i32* %array_x) #0 {</i></div>
<div><i> %1 = icmp slt i32 0, %n</i></div>
<div><i> br i1 %1, label %.<a href="http://lr.ph/" target="_blank">lr.ph</a>, label
%._crit_edge</i></div>
<div><i><br>
</i></div>
<div><i>.<a href="http://lr.ph/" target="_blank">lr.ph</a>:
; preds = %0, %7</i></div>
<div><i> %indvars.iv = phi i64 [ %indvars.iv.next.2, %7 ], [
0, %0 ]</i></div>
<div><i> %2 = getelementptr inbounds i32* %array_x, i64
%indvars.iv</i></div>
<div><i> %3 = trunc i64 %indvars.iv to i32</i></div>
<div><i> store i32 %3, i32* %2</i></div>
<div><i> %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1</i></div>
<div><i> %lftr.wideiv = trunc i64 %indvars.iv.next to i32</i></div>
<div><i> %exitcond = icmp ne i32 %lftr.wideiv, %n</i></div>
<div><i> br i1 %exitcond, label %4, label %._crit_edge</i></div>
<div><i><br>
</i></div>
<div><i>._crit_edge: ;
preds = %.<a href="http://lr.ph/" target="_blank">lr.ph</a>, %4, %7, %0</i></div>
<div><i> ret void</i></div>
<div><i><br>
</i></div>
<div><i>; <label>:4
; preds = %.<a href="http://lr.ph/" target="_blank">lr.ph</a></i></div>
<div><i> %5 = getelementptr inbounds i32* %array_x, i64
%indvars.iv.next</i></div>
<div><i> %6 = trunc i64 %indvars.iv.next to i32</i></div>
<div><i> store i32 %6, i32* %5</i></div>
<div><i> %indvars.iv.next.1 = add nuw nsw i64
%indvars.iv.next, 1</i></div>
<div><i> %lftr.wideiv.1 = trunc i64 %indvars.iv.next.1 to i32</i></div>
<div><i> %exitcond.1 = icmp ne i32 %lftr.wideiv.1, %n</i></div>
<div><i> br i1 %exitcond.1, label %7, label %._crit_edge</i></div>
<div><i><br>
</i></div>
<div><i>; <label>:7
; preds = %4</i></div>
<div><i> %8 = getelementptr inbounds i32* %array_x, i64
%indvars.iv.next.1</i></div>
<div><i> %9 = trunc i64 %indvars.iv.next.1 to i32</i></div>
<div><i> store i32 %9, i32* %8</i></div>
<div><i> %indvars.iv.next.2 = add nuw nsw i64
%indvars.iv.next.1, 1</i></div>
<div><i> %lftr.wideiv.2 = trunc i64 %indvars.iv.next.2 to i32</i></div>
<div><i> %exitcond.2 = icmp ne i32 %lftr.wideiv.2, %n</i></div>
<div><i> br i1 %exitcond.2, label %.<a href="http://lr.ph/" target="_blank">lr.ph</a>, label
%._crit_edge</i></div>
<div><i>}</i></div>
</div>
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">As you can see, at the
end of BB <label>4 and BB<label>7 there are "add",
"icmp" and "br" instrcutions to check the boundary. I
understand this is for the correctness. However, I would
expect the loop unrolling can change my code to something like
this:</div>
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">
<div><i>void foo( int n, int array_x[])</i></div>
<div><i>{</i></div>
<div><i> int j = n%3;</i></div>
<div><i> int m = n - j;</i></div>
<div><i> for (int i=0; i < m; i+=3){</i></div>
<div><i><span style="white-space:pre-wrap"> </span>
array_x[i] = i;</i></div>
<div><i><span style="white-space:pre-wrap"> </span>
array_x[i+1] = i+1;</i></div>
<div><i><span style="white-space:pre-wrap"> </span>
array_x[i+2] = i+2; </i></div>
<div><i> }</i></div>
<div><i> for(i=m; i<n; i++)</i></div>
<div><i><span style="white-space:pre-wrap"> </span>
array_x[i] = i; </i></div>
<div><i>}</i></div>
</div>
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">In this case, the
BB<label>4 and BB<label>7 will do not have the
"add", "icmp" and "br" instructions because these BBs can be
merged together.</div>
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">How can I achieve
this? Thanks.</div>
</div>
</blockquote></div><div bgcolor="#FFFFFF" text="#000000">
One - rather heavy weight - way to do this would be to add the -irce
pass after the loop unroll step. InductiveRangeCheckElimination
will introduce a post loop so as to eliminate the range checks in
the inner loop. This might not be the ideal transformation for this
code, but it might get you closer to what you want.<br>
<br>
A couple of caveats:<br>
- 3.5 isn't recent enough to have a stable IRCE. Download ToT.<br>
- IRCE requires profiling information on the branches. I'd start by
manually annotating your IR to see if it works, then exploring a
profile build if it does. <br>
<br>
For the record, teaching the unroller to do this transformation (or
a creating a new pass) would seem interesting. You might check with
Chandler and/or Michael (see recent review threads) for what their
plans in this area are. <br></div><div bgcolor="#FFFFFF" text="#000000">
<blockquote type="cite">
<div dir="ltr">
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">Regards,</div>
<div style="font-size:12.8000001907349px"><br>
</div>
<div style="font-size:12.8000001907349px">Xiangyang</div>
</div>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>