[LLVMdev] Extending GetElementPointer, or Premature Linearization Considered Harmful

[Duncan Sands]

Hi Preston,

> As noted in the GEP FAQ, GEPs don't support variable-length arrays;

that's not quite right.  The problem is only with arrays of variable length
arrays, and more generally with arrays where the element type has variable
size (this occurs with Ada, which has all kinds of funky variable sized types,
for example).  Consider your examples:

>     *void zap(long int n, long int A[]) {*
>     *  for (unsigned int i = 0; i < n; i++)*
>     *    A[1 + 2*i] = 0;*
>     *}*
...
>     *%arrayidx = getelementptr inbounds i64* %A, i64 %add3*

Here GEP has no problem with this variable sized array.

>     *void z1(long int n, long int A[][100][100]) {
>     **  for (long int i = 0; i < n; i++)
>     **    for (long int j = 0; j < n; j++)
>     **      for (long int k = 0; k < n; k++)
>     ****A[1 + 2*i][3 + 4*j][5 + 6*k] = 0;*
>     }
...
>     *%arrayidx12 = getelementptr inbounds [100 x [100 x i64]]* %A, i64 %add109,

Here neither.

>     *void z2(long int n, long int A[][n][n][100][100]) { *
>     *  for (long int i = 0; i < n; i++) *
>     *    for (long int j = 0; j < n; j++) *
>     *      for (long int k = 0; k < n; k++) *
>     ***for (long int l = 0; l < n; l++) *
>     ***for (long int m = 0; m < n; m++) *
>     ***A[1 + 2*i][3 + 4*j][5 + 6*k][7 + 8*l][9 + 10*m] = 0; *
>     }

This is where you run into trouble, because this is an array with a variable
sized element type.

Currently GEP is designed so that the offset from the base pointer is an affine
function *with constant multipliers*, eg: 3*x + 10*y.  This is analytically a
completely different beast to an offset of eg: x * y.

Yes, this is a limitation, but x*y is fundamentally different to and harder than
3*x.

Ciao, Duncan.