dynamic data dependence extraction using llvm

Hi LLVM-ers,

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.

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

To be more precise and make the problem understandable, here is an simple example:

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

without being a guru, also in learning process and having been analyzing a
similar situation to "hack" some pointer operations, I came to the
conclusion that the clang AST is the guy. In my case I would have had to
manipulate the AST, but in your case it seems that you only need to analyse
the AST.
And the above statement is made without knowing the content of the work in
[1]

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 J

Dear Dibyendu,

Thanks for your response. :slight_smile:

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
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. :slight_smile:

eliminate such intra-iteration dependences.
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.
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.

Thanks,
Henry

Hi mobi,

Sorry, I am new to clang AST and can not get the point you mentioned. :frowning:
What I try to do is develop a tool that can analyze data dependence at runtime. Therefore, I need to analyze trace containing memory accessing information (eg. arrays within loops). To do that, I first instrument a recording function to get addresses of load/store instructions. However, there are ‘uninteresting’ ld/st instructions, such as load/store instructions for iteration/index variables, i, j or k. And these ‘uninteresting’ ld/st instructions will affect my dependence analysis results.

If clang AST could solve this problem, could you provide more information?

Thanks,
Henry

Veterans could tell you more, what I say may be wrong, it is just based on
my still enough poor understanding of clang and LLVM nonetheless poor
understanding of the paper.

What I mean with AST is that you can static-analyze your AST to find the
"to dynamically analyze" points and inject code (also in form of AST) in
form of "report now that there is a read from array (memory)" or "now there
is a save to memory". This would give though tons of false positives as the
compiler will optimize out lot of stuff, so I think it would be a false
positives. To understand this in details you should read how the clang
compiler works.

But I think nobody could give you a precise answer without reading the
paper in question you marked with [1] especially that you did not provide a
link to it.

tools/libraries like vallgrind, dynamorio, intel.pin are in my opinion more
specialized for what you probably want to do. Anyway I think mainly there
are two approaches. You either inject analysis code near the instructions
to be observed or you run your code through an interpreter (vallgrind or
llvm) and try to "catch" what you are interested in. With "AST" hacking you
could inject code I think more precisely than any of the other tools... but
all depends on what exactly you want to measure.

Think also about performance. Running such an analyzis through an
interpreter often is impossible (valgrind, llvm). Myself I had to do some
profiling with valgrind, but given that starting the server in real
situation took half an hour. Running it through valgrind (thus intepreter)
took one day (if it was not crashing) :wink: which made it impossible to use at
the end...

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 J

would be myself curious how LLVM debug information could be used here, if at all

Hi Mobi,

Thanks for your response. :slight_smile:

Veterans could tell you more, what I say may be wrong, it is just based on my still enough poor understanding of clang and LLVM nonetheless poor understanding of the paper.
In the first stage of my post, I just show the general picture how I try to get the dynamic data dependence. The paper only focuses on how to analyze the ready trace and produce dependence results. Actually, it does not related with the problem I post, just for describing the whole picture. If you do not know the paper, it is totally fine and will not affect the discussion on the problem. The problem comes before the analysis step (before we can use the method in the paper), “how can we ignore the uninteresting load/store instructions”.

What I mean with AST is that you can static-analyze your AST to find the “to dynamically analyze” points and inject code (also in form of AST) in form of “report now that there is a read from array (memory)” or “now there is a save to memory”. This would give though tons of false positives as the compiler will optimize out lot of stuff, so I think it would be a false positives. To understand this in details you should read how the clang compiler works.
I check clang AST, it seems to only provide source-level information. What I mean to inject code, is to insert a Call Instruction right before or after an interesting load/store instruction. Therefore, it seems it could not provide me enough information. I think one solution might be using debugging information and make a connection between llvm instructions with source code lines, then specify the uninteresting source code lines. I guess this approach will work, but I am still finding better solutions.

tools/libraries like vallgrind, dynamorio, intel.pin are in my opinion more specialized for what you probably want to do. Anyway I think mainly there are two approaches. You either inject analysis code near the instructions to be observed or you run your code through an interpreter (vallgrind or llvm) and try to “catch” what you are interested in. With “AST” hacking you could inject code I think more precisely than any of the other tools… but all depends on what exactly you want to measure.
Yes, you’re right, it depends on what I want to get. Actually, the instrumentation part is not a problem now and I have integrated an embedded Execution Engine inside my project, I just try to finish the last part of my project. The reason why I do not consider the other tools, like Pin or something is that my later research project is strongly related with LLVM and I need the trace and llvm-IR for further usage. :slight_smile:

Thanks,
Henry

This may not be very helpful but you can try one of these:

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

b) 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.

Dear Dibyendu and Mobi,

Thanks for your help! :slight_smile:

I finally figure it out. The solution is really simple. I just need to generate a new bitcode file with the following command:

Thanks for sharing it… learned also something…

please share how you made the link llvm<->source using debug info

For llvm IR → source line using debug info, some projects such as LLVM Giri have this feature, maybe you can take a look at that