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>
Thanks for sharing it... learned also something... please share how you made the link llvm<->source using debug info On Fri, Dec 12, 2014 at 5:55 PM, Henry Chung <zhguanwen at gmail.com> wrote:> > 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 >> >> >> >> >> > > > > _______________________________________________ > 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/20141212/197ec920/attachment.html>
For llvm IR -> source line using debug info, some projects such as LLVM Giri have this feature, maybe you can take a look at that On Fri, Dec 12, 2014 at 7:00 PM, mobi phil <mobi at mobiphil.com> wrote:> > Thanks for sharing it... learned also something... > > please share how you made the link llvm<->source using debug info > > On Fri, Dec 12, 2014 at 5:55 PM, Henry Chung <zhguanwen at gmail.com> wrote: > >> 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 >>> >>> >>> >>> >>> >> >> >> >> _______________________________________________ >> 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/20141212/98ea3a19/attachment.html>