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