thr3ads.net - llvm dev - [LLVMdev] dynamic data dependence extraction using llvm [Dec 2014]

If this information is useful, please help other people find it:
Share via:

Henry Chung

2014-Dec-11 13:27 UTC

[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/20141211/0fa09980/attachment.html>

mobi phil

2014-Dec-11 13:56 UTC

head link

[LLVMdev] dynamic data dependence extraction using llvm

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

Das, Dibyendu

2014-Dec-11 17:43 UTC

head link

[LLVMdev] dynamic data dependence extraction using llvm

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] 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/20141211/e4effc60/attachment.html>

Henry Chung

2014-Dec-11 20:59 UTC

head link

[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>
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 J
>
>
>
> *From:* 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/20141211/a15961c0/attachment.html>

Henry Chung

2014-Dec-11 21:08 UTC

head link

[LLVMdev] dynamic data dependence extraction using llvm

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

On Thu, Dec 11, 2014 at 2:56 PM, mobi phil <mobi at mobiphil.com> wrote:
> 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]
>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141211/12126c63/attachment.html>

mobi phil

2014-Dec-11 22:56 UTC

head link

[LLVMdev] dynamic data dependence extraction using llvm

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

>
> *From:* 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
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141211/62a58eb5/attachment.html>

Possibly Parallel Threads

Search for more reasonably related threads

llvm dev - Dec 2014 - [LLVMdev] dynamic data dependence extraction using llvm

[LLVMdev] dynamic data dependence extraction using llvm

[LLVMdev] dynamic data dependence extraction using llvm

[LLVMdev] dynamic data dependence extraction using llvm

[LLVMdev] dynamic data dependence extraction using llvm

[LLVMdev] dynamic data dependence extraction using llvm

[LLVMdev] dynamic data dependence extraction using llvm

Possibly Parallel Threads