<div dir="ltr">The dependence analyzer helps with array references in loops.<div>The example you show,</div><div><br></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><span style="font-family:arial,sans-serif;font-size:13px">int nonLoopDep( int A, int B, int C ) {</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px"> A = B + C;</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"> B = A / C; </span></div><div><span style="font-family:arial,sans-serif;font-size:13px"> return B;</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">}</span></div></blockquote><div><span style="font-family:arial,sans-serif;font-size:13px"><br>
</span></div><div><span style="font-family:arial,sans-serif;font-size:13px">has no loops and no array refs, so dependence analysis won't help.</span></div><div><span style="font-family:arial,sans-serif;font-size:13px">But that's ok, because these cases (scalar references) are particularly</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">simple </span><span style="font-family:arial,sans-serif;font-size:13px">and well understood by the rest of the compiler.</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br>
</span></div><div>
<span style="font-family:arial,sans-serif;font-size:13px">Unfortunately, there's more for you to learn and I don't really know</span></div><div><span style="font-family:arial,sans-serif;font-size:13px">all the answers (in LLVM terms). </span><span style="font-family:arial,sans-serif;font-size:13px">LLVM converts everything to SSA form</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">(static single assignment), making it easy </span><span style="font-family:arial,sans-serif;font-size:13px">to chase from the use of a variable</span></div><div>
<span style="font-family:arial,sans-serif;font-size:13px">to its definitions.</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div><span style="font-family:arial,sans-serif;font-size:13px">If we put your example in a file called z.c</span></div>
<div><span style="font-family:arial,sans-serif;font-size:13px">and compile it like this,</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px">
<div><font face="arial, sans-serif">clang -O -S -emit-llvm z.c</font></div></blockquote><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">we'll get a file z.s with the IL after optimization:</font></div>
<div><font face="arial, sans-serif"><br></font></div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><font face="arial, sans-serif"><div>define i32 @nonLoopDep(i32 %A, i32 %B, i32 %C) #0 {</div></font></div>
<div><font face="arial, sans-serif"><div>entry:</div></font></div><div><font face="arial, sans-serif"><div> %add = add nsw i32 %C, %B</div></font></div><div><font face="arial, sans-serif"><div> %div = sdiv i32 %add, %C</div>
</font></div><div><font face="arial, sans-serif"><div> ret i32 %div</div></font></div><div><font face="arial, sans-serif"><div>}</div></font></div></blockquote><div><font face="arial, sans-serif"><div><br></div><div>Note that each name (%A, %B, %C, %add, and %div) has exactly</div>
<div>one definition but may have multiple uses (e.g., %C).</div><div>If you zip through the code and record the location of each definition,</div><div>then whenever you see a use, you can immediately see where it was defined.</div>
<div><br></div><div>Note that the procedure entrance serves as a definition point for the parameters %A, %B, and %C.</div><div>Note also that your original variable B had 2 distinct definitions, and the compiler has</div>
<div>recognized this and given one of them a new name, %div.</div><div><br></div><div>It's a little more complicated when multiple definitions can reach a single use.</div><div>For example, if we compile this code</div>
<div><br></div></font></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="arial, sans-serif"><div><div>int dumb( int A, int B, int C ) {</div></div></font></div><div><font face="arial, sans-serif"><div>
<div> if (A == B)</div></div></font></div><div><font face="arial, sans-serif"><div><div> A = C + 5;</div></div></font></div><div><font face="arial, sans-serif"><div><div> else</div></div></font></div><div><font face="arial, sans-serif"><div>
<div> A = C / 5;</div></div></font></div><div><font face="arial, sans-serif"><div><div> return A + B;</div></div></font></div><div><font face="arial, sans-serif"><div><div>}</div></div></font></div></blockquote><div><font face="arial, sans-serif"><div>
<br></div><div>we get</div><div><br></div></font></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="arial, sans-serif"><div><div>define i32 @dumb(i32 %A, i32 %B, i32 %C) #0 {</div></div></font></div>
<div><font face="arial, sans-serif"><div><div>entry:</div></div></font></div><div><font face="arial, sans-serif"><div><div> %cmp = icmp eq i32 %A, %B</div></div></font></div><div><font face="arial, sans-serif"><div><div>
br i1 %cmp, label %if.then, label %if.else</div></div></font></div><div><font face="arial, sans-serif"><div><div><br></div></div></font></div><div><font face="arial, sans-serif"><div><div>if.then: ; preds = %entry</div>
</div></font></div><div><font face="arial, sans-serif"><div><div> %add = add nsw i32 %C, 5</div></div></font></div><div><font face="arial, sans-serif"><div><div> br label %if.end</div></div></font></div><div><font face="arial, sans-serif"><div>
<div><br></div></div></font></div><div><font face="arial, sans-serif"><div><div>if.else: ; preds = %entry</div></div></font></div><div><font face="arial, sans-serif"><div><div> %div = sdiv i32 %C, 5</div>
</div></font></div><div><font face="arial, sans-serif"><div><div> br label %if.end</div></div></font></div><div><font face="arial, sans-serif"><div><div><br></div></div></font></div><div><font face="arial, sans-serif"><div>
<div>if.end: ; preds = %if.else, %if.then</div></div></font></div><div><font face="arial, sans-serif"><div><div> %A.addr.0 = phi i32 [ %add, %if.then ], [ %div, %if.else ]</div></div>
</font></div><div><font face="arial, sans-serif"><div><div> %add1 = add nsw i32 %A.addr.0, %B</div></div></font></div><div><font face="arial, sans-serif"><div><div> ret i32 %add1</div></div></font></div><div><font face="arial, sans-serif"><div>
<div>}</div></div></font></div></blockquote><div><font face="arial, sans-serif"><div><br></div><div>Note that 2 different definitions of A reach the use of A after the if statement.</div><div>In the LLVM IR, this situation is handled with a phi statement.</div>
<div>So what was originally A has become %A, %add, %div, and %A.addr.0</div><div>where the last is defined by a phi serving to join two of the names.</div><div><br></div><div>It's not actually very complicated to use; if you play with a few more examples</div>
<div>(be sure to try some loops) and trace out all the use-def connections,</div><div>I think it'll become clear.</div><div><br></div><div>Preston</div><div><br></div><div><br></div><div><br></div></font></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br>
</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Aug 23, 2013 at 11:53 AM, Valmico <span dir="ltr"><<a href="mailto:valmico88@gmail.com" target="_blank">valmico88@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Hello, thanks to your advices now my pass is on good way (i hope), but i've faced one problem that i cannot solve by myself:<br>
Running
all these passes (-basicaa -mem2reg -simplifycfg -loop-simplify
-loop-rotate -simplifycfg -instcombine -indvars -da) helped a lot, but
now i'm unable to find dependencies that are outside of the loop. <a href="http://f.eg" target="_blank">f.eg</a>.
code like this returns no dependencies (and no store/load instruction at
all).<br><br>int nonLoopDep( int A, int B, int C ) {<br> A = B + C;<br> B = A / C; <br> return B;<br>}<br><br></div>I've
figured out that removing -mem2reg and -instcombine helps a little but
it reports more dependencies than it should and also it messes up
looking for dependencies inside loops completly.<br></div>
</blockquote></div><br></div>