Problem with LoopDependenceAnalysis

Shanmukha Rao wrote:

I am using LLVM for implementing LoopFission pass.
I am using LoopPass.
I know that for checking circular dependency in loop I have to use LoopDependenceAnalysis

This is what i want to do.
for(int i = 0; i< n ; i++){
s1 : a[i] = a[i] + x[i];
s2 : x[i] = x[i+1] + i*2 ;
        }

/**there is no dependence from s2 to s1/
so after distribution(it should be) :

        for(int i = 0; i< n ; i++)
s1: a[i] = a[i] + x[i];

        for(int i = 0; i< n ; i++)
s2: x[i] = x[i+1] + i*2 ;

but in llvm i couldn't able to find there is no dependency from s2 to s1.
LoopDependenceAnalyis always gives there is a dependency from every load instructions to every store instructions.
Is there any other alternative to LoopDependenceAnalysis ?

LoopDependenceAnalysis is the right tool, but it's not completely implemented.
If you look at the source, you'll see the implementation is just outlined.

I'm working on a more complete implementation, but much work remains.

Preston

Shanmukha Rao wrote:
> I am using LLVM for implementing LoopFission pass.
> I am using LoopPass.
> I know that for checking circular dependency in loop I have to use
> LoopDependenceAnalysis
>
> This is what i want to do.
> for(int i = 0; i< n ; i++){
> s1 : a[i] = a[i] + x[i];
> s2 : x[i] = x[i+1] + i*2 ;
> }
>
> /**there is no dependence from s2 to s1/
> so after distribution(it should be) :
>
> for(int i = 0; i< n ; i++)
> s1: a[i] = a[i] + x[i];
>
> for(int i = 0; i< n ; i++)
> s2: x[i] = x[i+1] + i*2 ;
>
> but in llvm i couldn't able to find there is no dependency from s2
> to s1. LoopDependenceAnalyis always gives there is a dependency
> from every load instructions to every store instructions. Is there
> any other alternative to LoopDependenceAnalysis ?

LoopDependenceAnalysis is the right tool, but it's not completely
implemented. If you look at the source, you'll see the implementation
is just outlined.

I'm working on a more complete implementation, but much work remains.

Have you looked at the recently-proposed patch by Sanjoy Das? He has
done some work on actually implementing the SIV tests.
http://permalink.gmane.org/gmane.comp.compilers.llvm.cvs/109305

Preston, if you're also working on this, can you please look over
Sanjoy's patch?

-Hal

> Shanmukha Rao wrote:
> > I am using LLVM for implementing LoopFission pass.
> > I am using LoopPass.
> > I know that for checking circular dependency in loop I have to use
> > LoopDependenceAnalysis
> >
> > This is what i want to do.
> > for(int i = 0; i< n ; i++){
> > s1 : a[i] = a[i] + x[i];
> > s2 : x[i] = x[i+1] + i*2 ;
> > }
> >
> > /**there is no dependence from s2 to s1/
> > so after distribution(it should be) :
> >
> > for(int i = 0; i< n ; i++)
> > s1: a[i] = a[i] + x[i];
> >
> > for(int i = 0; i< n ; i++)
> > s2: x[i] = x[i+1] + i*2 ;
> >
> > but in llvm i couldn't able to find there is no dependency from s2
> > to s1. LoopDependenceAnalyis always gives there is a dependency
> > from every load instructions to every store instructions. Is there
> > any other alternative to LoopDependenceAnalysis ?
>
> LoopDependenceAnalysis is the right tool, but it's not completely
> implemented. If you look at the source, you'll see the
> implementation is just outlined.
>
> I'm working on a more complete implementation, but much work
> remains.

Have you looked at the recently-proposed patch by Sanjoy Das? He has
done some work on actually implementing the SIV tests.
http://permalink.gmane.org/gmane.comp.compilers.llvm.cvs/109305

Better link:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120227/138320.html

-Hal