<div dir="ltr"><div><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">I doubt there is any easy way to pick up ‘interesting ld/st’ and ignore the rest. If you are looking for only dependences which are inter-iteration (dependence distance != 0 ) you can do a post-pass on the ld/st addresses collected and eliminate such intra-iteration dependences. Maybe there is a smarter way </span><span style="font-size:11pt;font-family:Wingdings;color:rgb(31,73,125)">J</span><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u><u></u></span></p></div><div><span style="font-size:11pt;font-family:Wingdings;color:rgb(31,73,125)"><br></span></div>would be myself curious how LLVM debug information could be used here, if at all<div class="gmail_extra"><br><div class="gmail_quote"><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 lang="EN-US" link="blue" vlink="purple"><div><p class="MsoNormal"><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:11pt"> </span><br></p>
<p class="MsoNormal"><b><span style="font-size:10pt;font-family:Tahoma,sans-serif">From:</span></b><span style="font-size:10pt;font-family:Tahoma,sans-serif"> <a href="mailto:llvmdev-bounces@cs.uiuc.edu" target="_blank">llvmdev-bounces@cs.uiuc.edu</a> [mailto:<a href="mailto:llvmdev-bounces@cs.uiuc.edu" target="_blank">llvmdev-bounces@cs.uiuc.edu</a>]
<b>On Behalf Of </b>Henry Chung<br>
<b>Sent:</b> Thursday, December 11, 2014 6:57 PM<br>
<b>To:</b> LLVM Developers Mailing List<br>
<b>Subject:</b> [LLVMdev] dynamic data dependence extraction using llvm<u></u><u></u></span></p><div><div class="h5">
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">Hi LLVM-ers,<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">I try to develop my custom dynamic data dependence tool (focusing on nested loops), currently I can successfully get the trace including load/store address, loop information, etc.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">However, when I try to analyze dynamic data dependence based on the pairwise method described in [1], the load/store for iteration variables may interfere my analysis (I only care about the load/store for meaningful load/store, eg, load/store
for arrays).<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">To be more precise and make the problem understandable, here is an simple example:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">------------------------------------<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">My test example:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<div>
<p class="MsoNormal">for (j = 0; j < N-2; j++) {<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> for (i = 1; i < N; i++) {<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> x = a[i-1][j];<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> a[i][j+2] = x + 1;<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> }<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">}<u></u><u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">The corresponding simplified llvm-IR is shown in below:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><b>Beginning of simplified llvm-IR</b><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">entry:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> store i32 0, i32* %j, align4<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> br label %for.cond<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">for.cond:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> br ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">for.body:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> store i32 1, i32* %i, align4<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> br ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">for.cond1:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">for.body3:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> %temp4 = load[10 x i32]** %a.addr, align 8<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> store i32 %add, i32* %arrayidx10, align4<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> br ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">... ...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><b>End of simplified llvm-IR</b><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">The general idea to obtain the dynamic data dependence is that 1. get and record corresponding load/store addresses; 2. analyze load/store addresses in different iterations to figure out RAW, WAR or WAW dependence.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">However, as we can see in the llvm-IR, apart from load/store instructions for array accesses we interested, there are lots of load/store instructions for iteration variables, i and j for the above example. And these noise load/store instructions
will affect whether we have dependencies across loop iterations (loop-carried dependence) and dependence distance calculation.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Initially, I try to only focus on analyze the address in basic blocks containing "for.body", but it might be a problem if we have if-else statement in source codes and sometimes it also has load/store for iteration variables in basic blocks
containing "for.body". Therefore, this approach can not solve my problem.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Any suggestion for my problem?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Thanks,<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Henry<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">------------------------------------<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">[1]. <span style="font-family:Verdana,sans-serif;color:black">Minjang Kim, Hyesoon Kim, and Chi-Keung Luk. 2010. SD3: A Scalable Approach to Dynamic Data-Dependence Profiling, MICRO2010</span><u></u><u></u></p>
</div>
</div>
</div></div></div>
</div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature">rgrds,<br>mobi phil<br><br>being mobile, but including technology<br><a href="http://mobiphil.com">http://mobiphil.com</a></div>
</div></div>