llvm dev - Mar 2012 - [LLVMdev] 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

On Thu, 15 Mar 2012 09:57:00 -0700
Preston Briggs <preston.briggs at gmail.com> wrote:
> 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
> 
> Preston
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

On Thu, 15 Mar 2012 12:05:12 -0500
Hal Finkel <hfinkel at anl.gov> wrote:
> On Thu, 15 Mar 2012 09:57:00 -0700
> Preston Briggs <preston.briggs at gmail.com> wrote:
> 
> > 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
> 
> Preston, if you're also working on this, can you please look over
> Sanjoy's patch?
> 
>  -Hal
> 
> > 
> > Preston
> > 
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> 


-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory