<div>Hello Minjang,</div><div><br></div>Exactly what information do you need to get in your instrumentation? Is it essentially all loop entry-continue-exit events, interspersed with the memory access trace (address, read/write, pc)?<div>
<br></div><div>It seems the Thread Sanitizer people have already done something similar:</div><div><a href="http://code.google.com/p/data-race-test/source/browse/trunk/llvm/opt/ThreadSanitizer/ThreadSanitizer.cpp">http://code.google.com/p/data-race-test/source/browse/trunk/llvm/opt/ThreadSanitizer/ThreadSanitizer.cpp</a></div>
<div><br></div><div>Not sure what state it's in, I was just browsing their repo.</div><div><br></div><div>I would say it's a good idea to do your instrumentation after the optimization of the program. The optimized version is probably closer to what would have been produced in the final binary than the unoptimized IR. If you don't run the optimizations, you'll have to do a lot of work to sort out what memory accesses are obviously not dependent on the previous iteration. Optimizations will clean this up a lot.</div>
<div><br></div><div>The only issue then is that there are some dependencies that stay only in registers and not in memory, like the temporary in a summation loop. It will be a phi node between the base case and the last iteration. There should be some machinery in LLVM for finding these loop carried dependencies, and you should be able to record them in your instrumentation another way.</div>
<div><br></div><div>---</div><div><br></div><div>Finally, if you're strongly concerned with the performance of your tool, I think doing something similar to PiPA with DynamoRIO would give you the best performance:</div>
<div><a href="http://dynamorio.org/pubs/PiPA-pipelined-profiling-cgo08.pdf">http://dynamorio.org/pubs/PiPA-pipelined-profiling-cgo08.pdf</a></div><div><br></div><div>Disclaimer: I work on DynamoRIO. :)</div><div><br>It would be a very large amount of work, but I think the approach is very clever. The gist of it is that you try to precompute a table of all of the memory access offsets, read-write info, and application pc for every BB, and you record only the base registers and the id of the bb's table every time the basic block is executed. Beyond that, you just pipeline the analysis, which is straightforward.</div>
<div><br></div><div>Good luck,</div><div>Reid<br><br><div class="gmail_quote">On Mon, Mar 21, 2011 at 11:31 AM, Minjang Kim <span dir="ltr"><<a href="mailto:minjang@gatech.edu">minjang@gatech.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Hello, I'd like to listen your opinions regarding my research with LLVM.<div><div><div><br></div><div>My work is a dynamic analysis of data dependences [1]. Briefly speaking, I'm instrumenting memory loads/stores and loop entries/exits/back edges, and then calculating data dependences in runtime, especially focusing on loop-carried dependences.</div>
<div><br></div><div>So far, I have been working with a binary-level instrumentation tool (Pin). However, doing sophisticated static analysis with binaries is really daunting, so I'm porting my code to LLVM. </div><div>
<br></div><div>The implementation for LLVM is actually simple because my core analysis module is already orthogonal to instrumentation frameworks. So, all I need to do is inserting calls of stub functions that send events to the analysis module (e.g., loop A has been started).</div>
<div><br></div><div>First, instrumenting loop events such as entry/exit/back edges was very straightforward and simple, comparing to my previous binary-level approach, though there was quite a learning curve to use LLVM methods correctly and efficiently. FYI, in a binary-level approach, even extracting loops is challenging. No single pre-header and hard to capture loop exits as well.</div>
<div><br></div><div><br></div><div>However, instrumenting loads and stores efficiently is somewhat tricky. An obvious way is instrumenting every loads and stores, which is what I did with binaries. But, I'd like to filter loads and stores whose dependences can be decided in static time to minimize runtime overhead. Notable examples would be (1) induction variables and (2) local temporary variables:</div>
<div><br></div><div>for (int i = 0; i < N; ++i) {</div><div> int temp = 10;</div><div> ...</div><div>}</div><div><br></div><div>In the above example, it is obvious 'i' and 'temp' do not need to be analyzed in runtime. So, I'm writing the code that skip instrumentations for such local scalar variables.</div>
<div><br></div><div>I do believe this is doable. But, as a non-expert in static and compiler-level analysis, implementing such instrumentation code isn't straightforward so far.</div><div><br></div><div>One reason that makes this problem tricky would be I can't do any significant optimizations before instrumentation, because optimizations heavily change code such as loop interchanges, instruction reordering and elimination of variables. I'm currently doing instrumentation before any optimizations.</div>
<div><br></div><div>Such restriction makes some problems: before any optimizations, the IR code isn't a SSA-form, so sophisticated loop analysis is impossible such as identifying induction variable easily. Without SSA form, there are bunch of loads and stores, so extracting such variables require dirty hack.</div>
<div><br></div><div>I think I can implement this loads/stores instrumentation code anyway. However, I'd like to hear opinions from experts on this domain. What would be the most elegant and best approach for this problem? I will appreciate any comments for my work.</div>
<div><br></div><div><br></div><div>Thank you for reading such a long article,</div><div>Minjang</div><div><br></div><div>[1] <a href="http://www.cc.gatech.edu/~minjang/micro10-mjkim.pdf" target="_blank">http://www.cc.gatech.edu/~minjang/micro10-mjkim.pdf</a></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></div>