[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141211/0fa09980/attachment.html>