Dependence Analysis

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Dependence Analysis

Naftali Schwartz
Hi, everyone.  I've been examining llvm for a while and been duly
impressed.  I'd like to contribute in the area of dependence analysis, and
a good place to start seems to be in the transformation of pointers to
explicit array accesses.  Is anyone else working on this?  If not, does
this seem a plausible place to start and how would be the best way to go
about it?

Thanks,
Naftali

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis

Chris Lattner
On Mon, 18 Jul 2005, Naftali Schwartz wrote:

> Hi, everyone.  I've been examining llvm for a while and been duly impressed.
> I'd like to contribute in the area of dependence analysis, and a good place
> to start seems to be in the transformation of pointers to explicit array
> accesses.  Is anyone else working on this?  If not, does this seem a
> plausible place to start and how would be the best way to go about it?

LLVM already includes this: the -indvars pass.  It turns things like this:

int *P =
for (...; ... ; ++P)
    *P

to:

int *P = ...
for (int i = 0; ... ; ++i)
   P[i]

If you're interested in dependence analysis, the next important step is to
start analyzing distance and direction vectors.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis

Tanya Lattner-2

> LLVM already includes this: the -indvars pass.  It turns things like this:
>
> int *P = for (...; ... ; ++P)
>   *P
>
> to:
>
> int *P = ...
> for (int i = 0; ... ; ++i)
>  P[i]
>
> If you're interested in dependence analysis, the next important step is to
> start analyzing distance and direction vectors.

You can check out
lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp

It uses Alias Analysis and Scalar Evolution to figure out dependences and
distances for single dimensional arrays. It needs more work, but its a
start. Its not used by anyone currently. I wrote it for my
ModuloScheduling work.

-Tanya

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis

Vikram S. Adve-2
In reply to this post by Naftali Schwartz
Naftali,

Tanya Lattner has already made a start on the dependence analysis  
itself but is not working on it any more.  That is a much bigger  
project than the pointer-to-array-indexing conversion.  If you are  
interested in picking up on that, we should discuss it (probably  
offline).  There are some algorithmic choices that I think are  
important here, to combine speed and generality.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/


On Jul 17, 2005, at 11:53 PM, Naftali Schwartz wrote:

> Hi, everyone.  I've been examining llvm for a while and been duly  
> impressed.  I'd like to contribute in the area of dependence  
> analysis, and a good place to start seems to be in the  
> transformation of pointers to explicit array accesses.  Is anyone  
> else working on this?  If not, does this seem a plausible place to  
> start and how would be the best way to go about it?
>
> Thanks,
> Naftali
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis

Bill Wendling
In reply to this post by Tanya Lattner-2
On 7/20/05, Tanya Lattner <[hidden email]> wrote:

>
> > LLVM already includes this: the -indvars pass.  It turns things like this:
> >
> > int *P = for (...; ... ; ++P)
> >   *P
> >
> > to:
> >
> > int *P = ...
> > for (int i = 0; ... ; ++i)
> >  P[i]
> >
> > If you're interested in dependence analysis, the next important step is to
> > start analyzing distance and direction vectors.
>
> You can check out
> lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp
>
> It uses Alias Analysis and Scalar Evolution to figure out dependences and
> distances for single dimensional arrays. It needs more work, but its a
> start. Its not used by anyone currently. I wrote it for my
> ModuloScheduling work.
>
I've been rereading about dependencies and distance and direction
vectors recently and was thinking of giving this a shot in LLVM as
well (in my copious spare time). Naftali, if you're interested in
working on this, perhaps we could coordinate our efforts.

-bw

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis

Naftali Schwartz
In reply to this post by Naftali Schwartz
> LLVM already includes this: the -indvars pass.  It turns things like
this:

>
> int *P = for (...; ... ; ++P)
>   *P
>
> to:
>
> int *P = ...
> for (int i = 0; ... ; ++i)
>  P[i]
>
> If you're interested in dependence analysis, the next important step is
to
> start analyzing distance and direction vectors.

Well, specifically, I was thinking of a mechanism to turn this:

int A[100], B[100], C[100], X, Y, Z;

         int *p_a = &A[0];
         int *p_b = &B[0];
         int *p_c = &C[0];

         int i, j, k, f;
         for ( k = 0; k < Z; k++ )
         {
                 p_a = &A[0];
                 for ( i = 0; i < X; i++ )
                 {
                         p_b = &B[k*Y];
                         *p_c = *p_a++ * *p_b++;
                         for ( f = 0; f < Y-2; f++ )
                                 *p_c += *p_a++ * *p_b++;
                         *p_c++ += *p_a++ * *p_b++;
                 }
         }

...into:

int A[100], B[100], C[100], X, Y, Z;

         int i, j, k, f;
         for ( k = 0; k < Z; k++ )
                 for ( i = 0; i < X; i++ )
                 {
                         C[X*k+i] = A[Y*i] * B[Y*k];
                         for (f = 0; f < Y-2; f++ )
                                 C[X*k+i] += A[Y*i+f+1] * B[Y*k+f+1];
                         C[X*k+i] += A[Y*i+Y-1] * B[Y*k+Y-1];
                 }

a la Frank and O'Boyle, which -indvars seems not to be able to handle
(unless I'm doing something wrong...)

Naftali

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Dependence Analysis

AaronNGray
This may sound like a dumb question but for those who do not follow either
:-

    "why do you want to turn pointers into indexes ?"

Aaron

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Dependence Analysis

Chris Lattner
In reply to this post by Naftali Schwartz
On Thu, 21 Jul 2005, Naftali Schwartz wrote:
>> If you're interested in dependence analysis, the next important step is
> to
>> start analyzing distance and direction vectors.
>
> Well, specifically, I was thinking of a mechanism to turn this:

The indvars pass is *intentionally* restricted to only promoting affine
expressions to array subscripts, not arbitrary expressions.  To enable
this, remove the two if's at IndVarSimplify.cpp:647 (unconditionally
pushing the discovered indvar on the IndVars list).

See the comments in that code for a justification.

-Chris

> int A[100], B[100], C[100], X, Y, Z;
>
>        int *p_a = &A[0];
>        int *p_b = &B[0];
>        int *p_c = &C[0];
>
>        int i, j, k, f;
>        for ( k = 0; k < Z; k++ )
>        {
>                p_a = &A[0];
>                for ( i = 0; i < X; i++ )
>                {
>                        p_b = &B[k*Y];
>                        *p_c = *p_a++ * *p_b++;
>                        for ( f = 0; f < Y-2; f++ )
>                                *p_c += *p_a++ * *p_b++;
>                        *p_c++ += *p_a++ * *p_b++;
>                }
>        }
>
> ...into:
>
> int A[100], B[100], C[100], X, Y, Z;
>
>        int i, j, k, f;
>        for ( k = 0; k < Z; k++ )
>                for ( i = 0; i < X; i++ )
>                {
>                        C[X*k+i] = A[Y*i] * B[Y*k];
>                        for (f = 0; f < Y-2; f++ )
>                                C[X*k+i] += A[Y*i+f+1] * B[Y*k+f+1];
>                        C[X*k+i] += A[Y*i+Y-1] * B[Y*k+Y-1];
>                }
>
> a la Frank and O'Boyle, which -indvars seems not to be able to handle (unless
> I'm doing something wrong...)
>
> Naftali
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

-Chris

--
http://nondot.org/sabre/
http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Dependence Analysis

Naftali Schwartz
In reply to this post by AaronNGray
Well, dependence analysis depends on the ability to compare memory
accesses to determine whether or not they may overlap, and under what
circumstances such overlap may occur.  If all memory referencs are
expressed as a displacement from a base, then it becomes trivial to decide
whether or not two references may overlap (do they have the same base?)
and we can concentrate our symbolic analysis on the question of under what
circumstances such overlap may occur.

Naftali

On Thu, 21 Jul 2005, Aaron Gray wrote:

> This may sound like a dumb question but for those who do not follow either :-
>
>   "why do you want to turn pointers into indexes ?"
>
> Aaron
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Dependence Analysis

Chris Lattner
In reply to this post by AaronNGray
On Thu, 21 Jul 2005, Aaron Gray wrote:
> This may sound like a dumb question but for those who do not follow either :-
>   "why do you want to turn pointers into indexes ?"

It makes the code far easier to perform dependence analysis on.  For
example, this code:

   int A[100];
   int *B;
   for (B = &A[1]; ... ; ++i, ++B)
     *B = A[i];

If you turn that into:

   for (; ... ; ++i, ++B)
     A[i+1] = A[i];

... it is much easier for analyzers to understand.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Re: Dependence Analysis

Naftali Schwartz
In reply to this post by Chris Lattner
OK, I've tried this, and it does convert the p_b's to B[] references.  How
would I get this to work for the p_a and p_c references?

Naftali

On Thu, 21 Jul 2005, Chris Lattner wrote:

> On Thu, 21 Jul 2005, Naftali Schwartz wrote:
>>> If you're interested in dependence analysis, the next important step is
>> to
>>> start analyzing distance and direction vectors.
>>
>> Well, specifically, I was thinking of a mechanism to turn this:
>
> The indvars pass is *intentionally* restricted to only promoting affine
> expressions to array subscripts, not arbitrary expressions.  To enable this,
> remove the two if's at IndVarSimplify.cpp:647 (unconditionally pushing the
> discovered indvar on the IndVars list).
>
> See the comments in that code for a justification.
>
> -Chris
>
>> int A[100], B[100], C[100], X, Y, Z;
>>
>>        int *p_a = &A[0];
>>        int *p_b = &B[0];
>>        int *p_c = &C[0];
>>
>>        int i, j, k, f;
>>        for ( k = 0; k < Z; k++ )
>>        {
>>                p_a = &A[0];
>>                for ( i = 0; i < X; i++ )
>>                {
>>                        p_b = &B[k*Y];
>>                        *p_c = *p_a++ * *p_b++;
>>                        for ( f = 0; f < Y-2; f++ )
>>                                *p_c += *p_a++ * *p_b++;
>>                        *p_c++ += *p_a++ * *p_b++;
>>                }
>>        }
>>
>> ...into:
>>
>> int A[100], B[100], C[100], X, Y, Z;
>>
>>        int i, j, k, f;
>>        for ( k = 0; k < Z; k++ )
>>                for ( i = 0; i < X; i++ )
>>                {
>>                        C[X*k+i] = A[Y*i] * B[Y*k];
>>                        for (f = 0; f < Y-2; f++ )
>>                                C[X*k+i] += A[Y*i+f+1] * B[Y*k+f+1];
>>                        C[X*k+i] += A[Y*i+Y-1] * B[Y*k+Y-1];
>>                }
>>
>> a la Frank and O'Boyle, which -indvars seems not to be able to handle
>> (unless I'm doing something wrong...)
>>
>> Naftali
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> [hidden email]         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>
> -Chris
>
> --
> http://nondot.org/sabre/
> http://llvm.org/
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev