[LLVMdev] Efficient instrumentation of loads and stores

[Reid Kleckner]

Hello Minjang,

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)?

It seems the Thread Sanitizer people have already done something similar:
http://code.google.com/p/data-race-test/source/browse/trunk/llvm/opt/ThreadSanitizer/ThreadSanitizer.cpp

Not sure what state it's in, I was just browsing their repo.

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.

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.

---

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:
http://dynamorio.org/pubs/PiPA-pipelined-profiling-cgo08.pdf

Disclaimer: I work on DynamoRIO.  :)

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.

Good luck,
Reid

On Mon, Mar 21, 2011 at 11:31 AM, Minjang Kim <minjang at gatech.edu> wrote:

> Hello, I'd like to listen your opinions regarding my research with LLVM.
>
> 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.
>
> 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.
>
> 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).
>
> 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.
>
>
> 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:
>
> for (int i = 0; i < N; ++i) {
>   int temp = 10;
>   ...
> }
>
> 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.
>
> 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.
>
> 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.
>
> 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.
>
> 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.
>
>
> Thank you for reading such a long article,
> Minjang
>
> [1] http://www.cc.gatech.edu/~minjang/micro10-mjkim.pdf
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110321/9648c9dd/attachment.html>