<div dir="ltr">It works, thank you, Andy.</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Jun 20, 2013 at 12:45 AM, Andrew Trick <span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><div><div class="h5"><div>On Jun 19, 2013, at 1:04 AM, Eric Lu <<a href="mailto:eirc.lew@gmail.com" target="_blank">eirc.lew@gmail.com</a>> wrote:</div>
<br><blockquote type="cite"><div style="letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div dir="ltr"><div>It seems the options still does not work, or I have misunderstood what you said. </div>
<div><br></div><div>The command:</div><div><div>clang -g -I/home/lxj/software/llvmsvn/include -emit-llvm $1.c -c -o $1.bc </div><div>opt -debug --debug-pass=Structure -scalar-evolution -loop-rotate $1.bc -o $1-loop.bc </div>
<div>opt -S $1-loop.bc -o $1-loop.ll</div></div><div><br></div><div><br></div><div>1) The source code: </div><div><br></div><div>#include <stdio.h></div><div>#define N 100</div><div>int main()</div><div>{</div><div>
<br></div><div> int i, j, a[N];</div><div> int *ptr = (int*) malloc(sizeof(int) *100);</div><div> i = 100;</div><div> for( ; i > 0; i+= -3)</div><div> {</div><div> j = i;</div><div> a[j] = i + 2;;</div><div>
*ptr = i + 1;</div><div> ptr++;</div><div> }</div><div> printf("a[10] = %d \n", a[10]);</div><div><br></div><div> return 0;</div><div>}</div><div><br></div><div>2) The output llvm files, loop.ll, only shows loop related codes. </div>
<div><div>tore i32* %0, i32** %ptr, align 8, !dbg !20</div><div> <span> </span><b><i style="background-color:rgb(255,0,0)">store i32 100, i32* %i, align 4, !dbg !21</i></b></div><div> %1 = load i32* %i, align 4, !dbg !22</div>
<div> %cmp1 = icmp sgt i32 %1, 0, !dbg !22</div><div> br i1 %cmp1, label %<a href="http://for.body.lr.ph/" target="_blank">for.body.lr.ph</a>, label %for.end, !dbg !22</div><div><br></div><div><a href="http://for.body.lr.ph/" target="_blank">for.body.lr.ph</a>: ; preds = %entry</div>
<div> br label %for.body, !dbg !22</div><div><br></div><div>for.body: ; preds = %for.inc, %<a href="http://for.body.lr.ph/" target="_blank">for.body.lr.ph</a></div><div> %2 = load i32* %i, align 4, !dbg !24</div>
<div> store i32 %2, i32* %j, align 4, !dbg !24</div><div> %3 = load i32* %i, align 4, !dbg !26</div><div> %add = add nsw i32 %3, 2, !dbg !26</div><div> <span> </span><span style="background-color:rgb(255,0,0)">%4 = load i32* %j, align 4, !dbg !26</span></div>
<div><span style="background-color:rgb(255,0,0)"> %idxprom = sext i32 %4 to i64, !dbg !26</span></div><div><span style="background-color:rgb(255,0,0)"> %arrayidx = getelementptr inbounds [100 x i32]* %a, i32 0, i64 %idxprom, !dbg !26</span></div>
<div> store i32 %add, i32* %arrayidx, align 4, !dbg !26</div><div> %5 = load i32* %i, align 4, !dbg !27</div><div> %add1 = add nsw i32 %5, 1, !dbg !27</div><div> %6 = load i32** %ptr, align 8, !dbg !27</div><div> store i32 %add1, i32* %6, align 4, !dbg !27</div>
<div> %7 = load i32** %ptr, align 8, !dbg !28</div><div> %incdec.ptr = getelementptr inbounds i32* %7, i32 1, !dbg !28</div><div> store i32* %incdec.ptr, i32** %ptr, align 8, !dbg !28</div><div> br label %for.inc, !dbg !29</div>
<div><br></div><div>for.inc: ; preds = %for.body</div><div> %8 = load i32* %i, align 4, !dbg !22</div><div><font color="#ff0000"> %add2 = add nsw i32 %8, -3, !dbg !22</font></div>
<div> store i32 %add2, i32* %i, align 4, !dbg !22</div><div> %9 = load i32* %i, align 4, !dbg !22</div><div> %cmp = icmp sgt i32 %9, 0, !dbg !22</div><div> br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge, !dbg !22</div>
<div><br></div><div>for.cond.for.end_crit_edge: ; preds = %for.inc</div><div> br label %for.end, !dbg !22</div><div><br></div><div>for.end: ; preds = %for.cond.for.end_crit_edge, %entry</div>
<div> %arrayidx3 = getelementptr inbounds [100 x i32]* %a, i32 0, i64 10, !dbg !30</div></div></div></div></blockquote><div dir="auto"><br></div></div></div><div dir="auto">It’s a good idea to run mem2reg and simplifycfg before anything else:</div>
<div dir="auto">opt -mem2reg -simplifycfg -loop-rotate -indvars</div><div><br></div>define i32 @main() #0 {<br> %a = alloca [100 x i32], align 16<br> %1 = bitcast [100 x i32]* %a to i8*<br> call void @llvm.lifetime.start(i64 400, i8* %1) #1<br>
%2 = call i8* @malloc(i64 400)<br> %3 = bitcast i8* %2 to i32*<br> br label %4<br><br>; <label>:4 ; preds = %0, %4<br> %indvars.iv = phi i64 [ 100, %0 ], [ %indvars.iv.next, %4 ]<br>
%ptr.01 = phi i32* [ %3, %0 ], [ %10, %4 ]<br> %5 = add nsw i64 %indvars.iv, 2<br> %6 = getelementptr inbounds [100 x i32]* %a, i32 0, i64 %indvars.iv<br> %7 = trunc i64 %5 to i32<br> store i32 %7, i32* %6, align 4, !tbaa !0<br>
%8 = add nsw i64 %indvars.iv, 1<br> %9 = trunc i64 %8 to i32<br> store i32 %9, i32* %ptr.01, align 4, !tbaa !0<br> %10 = getelementptr inbounds i32* %ptr.01, i32 1<br> %indvars.iv.next = add i64 %indvars.iv, -3<br> %11 = trunc i64 %indvars.iv.next to i32<br>
%12 = icmp sgt i32 %11, 0<br> br i1 %12, label %4, label %13<br><br>; <label>:13 ; preds = %4<br> %14 = getelementptr inbounds [100 x i32]* %a, i32 0, i64 10<br> %15 = load i32* %14, align 4, !tbaa !0<br>
%16 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([13 x i8]* @.str, i32 0, i32 0), i32 %15)<br> %17 = bitcast [100 x i32]* %a to i8*<br> call void @llvm.lifetime.end(i64 400, i8* %17) #1<br> ret i32 0<br>
}</div><div><br></div><div>Now the loop is in a canonical form while the induction variables are still just the way you’ve written them. (The compiler isn’t going to destructively rewrite your code for no expected benefit).</div>
<div><br></div><div>opt -analyze -scalar-evolution shows the canonical form of each induction variable:</div><div><br></div><div> %6 = getelementptr inbounds [100 x i32]* %a, i32 0, i64 %indvars.iv<br> --> {(400 + %a),+,-12}<%4><span style="white-space:pre-wrap"> </span>Exits: (4 + %a)<br>
<br> %10 = getelementptr inbounds i32* %ptr.01, i32 1<br> --> {(4 + %2),+,4}<nw><%4><span style="white-space:pre-wrap"> </span>Exits: (136 + %2)<br><br>llc -loop-reduce is a codegen pass that rewrites the induction variables in the target’s preferred form.<br>
<br>For IR readability, you may want the induction variables to be rewritten in terms of a 0..N loop counter. That’s a useful tool but not part of LLVM’s standard optimization pipeline. You could add such a pass on a local branch using either the LoopStrengthReduce pass or the 3.1 source as reference.</div>
<div><br></div><div>-Andy<div class="im"><br><br><blockquote type="cite"><div style="letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra">
<div class="gmail_quote">On Wed, Jun 19, 2013 at 1:32 AM, Andrew Trick<span> </span><span dir="ltr"><<a href="mailto:atrick@apple.com" target="_blank">atrick@apple.com</a>></span><span> </span>wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="word-wrap:break-word"><div><br><div><div>On Jun 18, 2013, at 6:08 AM, eric.lew <<a href="mailto:eirc.lew@gmail.com" target="_blank">eirc.lew@gmail.com</a>> wrote:</div><br><blockquote type="cite"><div style="letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">
It seems there is no -enable-iv-rewrite now in llvm3.2, and it suggest<br>-enable-load-pre, but it still does not work.<br><br>So, how to active the transform?<br></div></blockquote></div><br></div><div>Eric,</div><div><br>
</div><div>Loops are canonicalized with -loop-rotate, which implicitly calls -loop-simplify first.</div><div><br></div><div>The canonical form of the induction variables is expressed in the ScalarEvolution analysis.</div>
<div><br></div><div>-indvars simplifies inductions variables, mainly by eliminating sign extension, but does not rewrite them into a canonical form.</div><div><br></div><div>-Andy</div></div></blockquote></div></div></div>
</blockquote></div></div><br></div></blockquote></div><br></div>