[LLVMdev] data dependency and fully loop unrolling

[Cheng Liu]

Hal,

Thanks for our quick reply. I am expecting the data dependency after 
fully loop unrolling.
Actually I am trying to build the data dependency graph, I mean the data 
dependency between operands.
When there is no load and store in a basic block, I can simply compare 
the operands and build the data flow graph.
However, when there are both load and stores in a unrolled loop block, 
it is not easy to compare without knowing the address.
For example,
load a[i]
b[i]=a[i]+1;
store b[i]
c[i]=b[i]+2;
After fully loop unrolling, 'i' is a determined number. And the data 
dependency is
a[1]->b[1]->c[1]
a[2]->b[2]->c[2]
It seems pretty straightforward, but we can not draw the dependency 
without knowing the array index.

I have looked into the links that you have suggested, it seems quite 
related but I am not sure yet.
I will spend more time on it.

Best regards,

On 5/24/2012 8:45 PM, Hal Finkel wrote:
> Cheng,
>
> Are you looking specifically for an analysis that can 'undo' the
> effects of loop unrolling, or do you want dependency analysis that can
> run on the loop prior to unrolling?
>
> For dependency analysis on loops (prior to unrolling) Preston and
> Sanjoy have been working on this, see:
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-May/049769.html
> http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-April/048812.html
> (and other related threads)
>
>   -Hal
>
> On Thu, 24 May 2012 19:07:33 +0800
> Cheng Liu<st.liucheng at gmail.com>  wrote:
>
>> Hi, all
>>
>> When I have a loop unrolled, in the loop body, the same element of
>> the array may be accessed multiple times.
>> I see there are then load and store instructions and I can no longer
>> trace the data dependency directly by comparing
>> the operands. So I am writing to see if anyone has done this or any
>> methods in llvm that may help?
>>
>> Best regards,
>>
>
>


-- 
Cheng Liu
PhD Candidate
Department of Electrical and Electronic Engineering
The University of Hong Kong