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>
Das, Dibyendu
2014-Dec-12 16:46 UTC
[LLVMdev] dynamic data dependence extraction using llvm
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 collectedYes, 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>
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 On Fri, Dec 12, 2014 at 5:46 PM, Das, Dibyendu <Dibyendu.Das at amd.com> wrote:> > 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> > 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/20141212/701deb2e/attachment.html>
Maybe Matching Threads
- [LLVMdev] dynamic data dependence extraction using llvm
- [LLVMdev] dynamic data dependence extraction using llvm
- [LLVMdev] some of Basic blocks are deleted after running embedded ExecutionEngine
- [LLVMdev] dynamic data dependence extraction using llvm
- [LLVMdev] Loop Vectorization and Store-Load Forwarding issue