[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).
>
> You're right, though of course I was quoting from the FAQ.
>
> You worry about handling Ada...
> I'm old and worry that we can't even handle Fortran well.

...

>>>     *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.
>
> I merely argue for allowing constant-but-unknown multipliers, i.e.,
> parameters. They're still affine for purposes of dependence analysis
> (by things like the Delta test or Polly), but oh so much more useful.
>
> Multi-dimensional VLAs happen, especially in scientific code. How are
> we going to express DGEMM (matrix multiplication)?  We could do it by
> manually linearizing all the array references, or we could do it the
> way god intended when he standardized C90, with VLAs. I'm arguing that
> it would be wonderful to be able to analyze such code accurately.

this would be a radical change to GEP, and as such would mean a huge amount of
work.  That said, being able to describe affine functions with locally constant
multipliers in a nice and effective way would be great.  I expect that this is
really a job for SCEV, not for GEP.  Hopefully Chris will comment on this issue.

Ciao, Duncan.