[LLVMdev] dynamic data dependence extraction using llvm

Fri Dec 12 11:50:15 PST 2014

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>