<div dir="ltr">Dear Dibyendu,<div><br></div><div>Thanks for your response. :-)</div><div>> <span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:15px">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</span></div><div> Yes, I am more interested in inter-iteration dependence. Could you provide more information or some links on post-pass approach? I have no idea on your method. :-)</div><div><br></div><div>> <span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:15px">eliminate such intra-iteration dependences.</span></div><div><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:15px"> For the intra-iteration dependences introduced by iteration (index) variables, I just ignore. However, t</span><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:15px">he "uninteresting ld/st" still can be come from iteration(index) variables, such as i, j, k. For example, at the end of the 4th iteration, we increase variable 'i' and introduce a store instruction for 'i'. And at the beginning of the 5th iteration, we load the same address of 'i', to see whether the loop condition is true or false. Since I can not distinguish with the interesting and uninteresting ld/st, I will get the two trace entries for the 'i' and produce a WAR dependence with distance != 0. </span></div><div><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:15px"> I just wonder how can I detect these kind of iteration (index) variables, then I just need to do not insert recordload/store functions into these "uninteresting" load/store instructions. </span></div><div><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:15px"><br></span></div><div><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:15px">Thanks,</span></div><div><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:15px">Henry</span></div><div><span style="color:rgb(31,73,125);font-family:Calibri,sans-serif;font-size:15px"><br></span></div><div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Dec 11, 2014 at 6:43 PM, Das, Dibyendu <span dir="ltr"><<a href="mailto:Dibyendu.Das@amd.com" target="_blank">Dibyendu.Das@amd.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">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:11.0pt;font-family:Wingdings;color:#1f497d">J</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;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<span class=""><br>
<b>To:</b> LLVM Developers Mailing List<br>
</span><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>
</blockquote></div><br></div><br></div>