[LLVMdev] dynamic data dependence extraction using llvm

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

From: Henry Chung [mailto:zhguanwen at gmail.com]
Sent: Friday, December 12, 2014 2:29 AM
To: Das, Dibyendu
Cc: LLVM Developers Mailing List
Subject: Re: [LLVMdev] dynamic data dependence extraction using llvm

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



On Thu, Dec 11, 2014 at 6:43 PM, Das, Dibyendu <Dibyendu.Das at amd.com<mailto:Dibyendu.Das at amd.com>> wrote:
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 ☺

From: llvmdev-bounces at cs.uiuc.edu<mailto:llvmdev-bounces at cs.uiuc.edu> [mailto:llvmdev-bounces at cs.uiuc.edu<mailto:llvmdev-bounces at cs.uiuc.edu>] On Behalf Of Henry Chung
Sent: Thursday, December 11, 2014 6:57 PM
To: LLVM Developers Mailing List
Subject: [LLVMdev] 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:
------------------------------------
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


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141212/0732bbec/attachment.html>