Dependence Analysis

Project Infrastructure LLVM Dev List Archives
1

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

2

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

3

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
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-Chris

4

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

5

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

6

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