[LLVMdev] Extending GetElementPointer, or Premature Linearization Considered Harmful

[Andrew Trick]

On May 4, 2012, at 8:59 AM, Duncan Sands <baldrick at free.fr> wrote:
>>> 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.

I'm not sure what more SCEV can do, other than provide a more convenient interface for dependence testing. Each recurrence in the chain directly tells you the lower bounds and stride, while getSCEVAtScope provides the exit value, or upper "array bounds". The problem that's obvious to me is that an inner IV cannot always be tested against the stride of its outer loop. Often I think it can, but Preston points out "hard to delinearize" cases. For those cases, it seems to me that the compiler either needs array bounds checks or preservation of the source language's aliasing rules, maybe in the form of variable size inbounds GEP. But the "inboundsness" of a GEP is not well defined and hard to preserve.

-Andy