<div dir="ltr">Thanks for sharing it... learned also something...<div><br></div><div>please share how you made the link llvm<->source using debug info <br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Dec 12, 2014 at 5:55 PM, Henry Chung <span dir="ltr"><<a href="mailto:zhguanwen@gmail.com" target="_blank">zhguanwen@gmail.com</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Dear Dibyendu and Mobi,<div><br></div><div>Thanks for your help! :-)</div><div><br></div><div>I finally figure it out. The solution is really simple. I just need to generate a new bitcode file with the following command:</div><div>-----</div><div>opt -mem2reg -indvars test1.bc -o test2.bc</div><div>-----</div><div>Then the load/store for induction variables will be removed and replaced by PHI instructions and all remaining load/store instructions are those I am interested in. I just simply insert my recording functions into it and everything is OK.</div><div><br></div><div>Thanks again for your kindly help. :-)</div><div><br></div><div>Best regards,</div><div>Henry</div><div><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Dec 12, 2014 at 5:46 PM, Das, Dibyendu <span dir="ltr"><<a href="mailto:Dibyendu.Das@amd.com" target="_blank">Dibyendu.Das@amd.com</a>></span> wrote:<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">This may not be very helpful but you can try one of these:<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><u></u><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><span>a)<span style="font:7.0pt "Times New Roman"">
</span></span></span><u></u><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Identify the loop-control-variable and other loop-induction variables in the compiler and do not track the ld/st of these variables (because you know
how they behave)<u></u><u></u></span></p>
<p><u></u><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><span>b)<span style="font:7.0pt "Times New Roman"">
</span></span></span><u></u><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Create a separate section in the profile dump for the addresses of the loop induction vars and during a post-pass you can do a special handling for
these addresses.<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""> Henry Chung [mailto:<a href="mailto:zhguanwen@gmail.com" target="_blank">zhguanwen@gmail.com</a>]
<br>
<b>Sent:</b> Friday, December 12, 2014 2:29 AM<br>
<b>To:</b> Das, Dibyendu<br>
<b>Cc:</b> LLVM Developers Mailing List<br>
<b>Subject:</b> Re: [LLVMdev] dynamic data dependence extraction using llvm<u></u><u></u></span></p><div><div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">Dear Dibyendu,<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Thanks for your response. :-)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">> <span style="font-size:11.5pt;font-family:"Calibri","sans-serif";color:#1f497d">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><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> 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. :-)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">> <span style="font-size:11.5pt;font-family:"Calibri","sans-serif";color:#1f497d">eliminate such intra-iteration dependences.</span><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.5pt;font-family:"Calibri","sans-serif";color:#1f497d"> For the intra-iteration dependences introduced by iteration (index) variables, I just ignore. However, the "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><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.5pt;font-family:"Calibri","sans-serif";color:#1f497d"> 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><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.5pt;font-family:"Calibri","sans-serif";color:#1f497d">Thanks,</span><u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.5pt;font-family:"Calibri","sans-serif";color:#1f497d">Henry</span><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>
<p class="MsoNormal">On Thu, Dec 11, 2014 at 6:43 PM, Das, Dibyendu <<a href="mailto:Dibyendu.Das@amd.com" target="_blank">Dibyendu.Das@amd.com</a>> wrote:<u></u><u></u></p>
<div>
<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><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></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<br>
<b>To:</b> LLVM Developers Mailing List<br>
<b>Subject:</b> [LLVMdev] dynamic data dependence extraction using llvm</span><u></u><u></u></p>
<div>
<div>
<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>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div></div></div>
</div>
</blockquote></div></div><br clear="all"><div><br></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 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></div>