<div dir="ltr">
<p style="margin-bottom:0.35cm;line-height:115%">Hi,</p>
<p style="margin-bottom:0.35cm;line-height:115%">I have been
studying LLVM infrastructure from past 1 month and trying out some
hands on to get familiar with it. I am keen to propose loop reversal
pass in LLVM as a part of GSoC 2015. Following are the details of my
proposal.</p>
<p style="margin-bottom:0.35cm;line-height:115%">A for loop can
run in two ways – it can count up or it can count down.
</p>
<ol>
<li><p style="margin-bottom:0.35cm;line-height:115%">for(i=0;
i<10 ;i++) {// Do something}</p>
</li><li><p style="margin-bottom:0.35cm;line-height:115%">for(i=9;
i--;) {// Do something}</p>
</li></ol>
<p style="margin-bottom:0.35cm;line-height:115%">Counting down to
zero with the decrement operator (i--) is faster than counting up to
a number of iterations with the increment operator (i++).</p>
<p style="margin-bottom:0.35cm;line-height:115%">I have run a
program with sufficient iteration for both types of loops (The
program file Loop.cpp is attached with the mail). The average run
time observed for both the loops over 100 runs
</p>
<p style="margin-bottom:0.35cm;line-height:115%">Loop counting up
0.15 ms</p>
<p style="margin-bottom:0.35cm;line-height:115%">Loop counting
down 0.08 ms</p>
<p style="margin-bottom:0.35cm;line-height:115%">As observed,
there is an execution time gain of almost 50%. The test case is
rather simple though; need to check in wide variety of test cases.</p>
<p style="margin-bottom:0.35cm;line-height:115%">It is a legal
transformation if the resulting dependence vector remains
lexicographically positive. Although trivial, it is a useful
optimization since it may enable others such as loop interchange and
can reduce the loop exit condition to a single
branch-not-equal-to-zero instruction.</p>
<p style="margin-bottom:0.35cm;line-height:115%">For example, the
following code cannot be interchanged or have its inner loop
parallelized because of (1,−1) dependencies.</p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>do i = 1, n</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>do j = 1, n</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>a[i,j] = a[i-1,j+1] + 1</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>end do</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>end do</i></p>
<p style="margin-bottom:0.35cm;line-height:115%">Reversing the
inner loop yields (1, 1) dependencies. The loops can now be
interchanged and/or the inner loop made parallel.</p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>do i = 1, n</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>do j = n, 1, -1</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>a[i,j] = a[i-1,j+1] + 1</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>end do</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>end do</i></p>
<p style="margin-bottom:0.35cm;line-height:115%">
</p>
<p style="margin-bottom:0.35cm;line-height:115%">To see the
difference in LLVM IR, I have taken a simpler test case:</p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>int a[5], b[5], c[5], d[5];</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>void foo() {</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>int i;</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>for(i=0; i<5; i++)</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>a[i] = b[i] + c[i];</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>}</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>void foo2() {</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>int i;</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>for(i=4; i--;)</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>d[i] = a[i] + b[i];</i></p>
<p style="margin-left:6.35cm;margin-bottom:0.35cm;line-height:115%">
<i>}</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<br><br>
</p>
<p style="margin-bottom:0.35cm;line-height:115%"><b>IR for foo()</b></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%"><a name="_GoBack"></a>
<i>define void @foo() {</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>br label %1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>; <label>:1 ; preds =
%13, %0</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%i.0 = phi i32 [ 0, %0 ], [ %14, %13 ]</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%2 = icmp slt i32 %i.0, 5</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>br i1 %2, label %3, label %15</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>; <label>:3 ; preds =
%1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%4 = sext i32 %i.0 to i64</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%5 = getelementptr inbounds [5 x i32], [5 x i32]* @b, i32 0, i64
%4</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%6 = load i32, i32* %5, align 4</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%7 = sext i32 %i.0 to i64</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%8 = getelementptr inbounds [5 x i32], [5 x i32]* @c, i32 0, i64
%7</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%9 = load i32, i32* %8, align 4</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%10 = add nsw i32 %6, %9</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%11 = sext i32 %i.0 to i64</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%12 = getelementptr inbounds [5 x i32], [5 x i32]* @a, i32 0,
i64 %11</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>store i32 %10, i32* %12, align 4</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>br label %13</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>; <label>:13 ; preds =
%3</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%14 = add nsw i32 %i.0, 1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>br label %1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>; <label>:15 ; preds =
%1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>ret void</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>}</i></p>
<p style="margin-bottom:0.35cm;line-height:115%"><br><br>
</p>
<p style="margin-bottom:0.35cm;line-height:115%"><b>IR for foo2()</b></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>define void @foo2() #0 {</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>br label %1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>; <label>:1 ; preds =
%4, %0</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%i.0 = phi i32 [ 4, %0 ], [ %2, %4 ]</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%2 = add nsw i32 %i.0, -1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%3 = icmp ne i32 %i.0, 0</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>br i1 %3, label %4, label %14</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>; <label>:4 ; preds =
%1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%5 = sext i32 %2 to i64</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%6 = getelementptr inbounds [5 x i32], [5 x i32]* @b, i32 0, i64
%5</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%7 = load i32, i32* %6, align 4</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%8 = sext i32 %2 to i64</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%9 = getelementptr inbounds [5 x i32], [5 x i32]* @c, i32 0, i64
%8</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%10 = load i32, i32* %9, align 4</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%11 = add nsw i32 %7, %10</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%12 = sext i32 %2 to i64</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>%13 = getelementptr inbounds [5 x i32], [5 x i32]* @d, i32 0,
i64 %12</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>store i32 %11, i32* %13, align 4</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>br label %1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<br><br>
</p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>; <label>:14 ; preds =
%1</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>ret void</i></p>
<p style="margin-left:5.08cm;margin-bottom:0.35cm;line-height:115%">
<i>}</i></p>
<p style="margin-bottom:0.35cm;line-height:115%">As visible, one
of the blocks is eliminated in case of loop reverse traversal, and
induction variable updating instruction (i--) has been hoisted to the
start block.
</p>
<p style="margin-bottom:0.35cm;line-height:115%">(This has
constant inbounds of the loop, which in further optimizations
eliminates all the blocks. The above IR is for demo purpose)</p>
<p style="margin-bottom:0.35cm;line-height:115%">
</p>
<p style="margin-bottom:0.35cm;line-height:115%">As of now I can
think of 3 stages to achieve this :</p>
<ol>
<li><p style="margin-bottom:0.35cm;line-height:115%">Check
legality if the loop can be reversed – check dependence analysis
in the loop , various scenarios will come – exit condition being
constant, variable, nested loops, etc.</p>
</li><li><p style="margin-bottom:0.35cm;line-height:115%">Check
profitability of the loop – check if somehow the loop exit
condition can be trimmed down to comparison with zero ( More Inputs
on this are required )</p>
</li><li><p style="margin-bottom:0.35cm;line-height:115%">If steps 1
and 2 are true, then reverse the loop.</p>
</li></ol>
<p style="margin-bottom:0.35cm;line-height:115%">Inputs on 1<sup>st</sup>
and 2<sup>nd</sup> steps are the critical for implementation.</p>
<p style="margin-bottom:0.35cm;line-height:115%">I am pasting some
of the links of the papers, where I found mention of loop traversal
as one of the prominent loop optimization techniques.</p>
<p style="margin-bottom:0.35cm;line-height:115%"><a href="http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf">http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf</a></p>
<p style="margin-bottom:0.35cm;line-height:115%"><a href="http://perso.citi.insa-lyon.fr/trisset/papers/sympa08.pdf">http://perso.citi.insa-lyon.fr/trisset/papers/sympa08.pdf</a></p>
<p style="margin-bottom:0.35cm;line-height:115%"><a href="https://www.complang.tuwien.ac.at/andi/papers/ijcsee_13.pdf">https://www.complang.tuwien.ac.at/andi/papers/ijcsee_13.pdf</a></p>
<p style="margin-bottom:0.35cm;line-height:115%"><a href="ftp://gcc.gnu.org/pub/gcc/summit/2004/High%20Level%20Loop%20Optimizations.pdf">ftp://gcc.gnu.org/pub/gcc/summit/2004/High%20Level%20Loop%20Optimizations.pdf</a></p>
<p style="margin-bottom:0.35cm;line-height:115%">Can anyone review
my idea and suggest improvements? I will be glad if someone mentors
me on this, especially on the first 2 steps, if idea is found to be
useful.
</p>
<p style="margin-bottom:0.35cm;line-height:115%">Regards, </p><p style="margin-bottom:0.35cm;line-height:115%"> Vishal Sarda,</p><p style="margin-bottom:0.35cm;line-height:115%"> 3<sup>rd</sup> Year
Undergraduate, </p><p style="margin-bottom:0.35cm;line-height:115%"> Department of Computer Engineering,</p><p style="margin-bottom:0.35cm;line-height:115%"> College of Engineering, Pune</p></div>