[LLVMdev] dynamic data dependence extraction using llvm

[Henry Chung]

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:

------------------------------------

My test example:

for (j = 0; j < N-2; j++) {

for (i = 1; i < N; i++) {

x = a[i-1][j];

a[i][j+2] = x + 1;

}

}

The corresponding simplified llvm-IR is shown in below:

Beginning of simplified llvm-IR

entry:

    ...

    store i32 0, i32* %j, align4

    br label %for.cond

for.cond:

    ...

    br ...

for.body:

    store i32 1, i32* %i, align4

    br ...

for.cond1:

    ...

for.body3:

    ...

    %temp4 = load[10 x i32]** %a.addr, align 8

    ...

    store i32 %add, i32* %arrayidx10, align4

    br ...

... ...

End of simplified llvm-IR

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.

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.

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.

Any suggestion for my problem?

Thanks,

Henry

------------------------------------

[1]. Minjang Kim, Hyesoon Kim, and Chi-Keung Luk. 2010. SD3: A Scalable Approach to Dynamic Data-Dependence Profiling, MICRO2010

[mobi phil]

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]

[Das, Dibyendu]

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

[Henry Chung]

Dear Dibyendu,

Thanks for your response. :-)

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

> 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

[Henry Chung]

Hi mobi,

Sorry, I am new to clang AST and can not get the point you mentioned. :-(

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

[mobi phil]

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) ;) which made it impossible to use at the end...

[mobi phil]

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

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

--

rgrds,
mobi phil

being mobile, but including technology
http://mobiphil.com

[Henry Chung]

Hi Mobi,

Thanks for your response. :-)

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

Thanks,

Henry

[Das, Dibyendu]

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.

[Henry Chung]

Dear Dibyendu and Mobi,

Thanks for your help! :-)

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

-----

opt -mem2reg -indvars test1.bc -o test2.bc

-----

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.

Thanks again for your kindly help. :-)

Best regards,

Henry

[mobi phil]

Thanks for sharing it... learned also something...

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

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Henry Chung]

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