[LLVMdev] dynamic data dependence extraction using llvm

[Henry Chung]

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>