[LLVMdev] Multi-dimensional array accesses in LLVM-IR | Thoughts

[David Tweed]

| Here we have to be careful because when there are several accesses to the
same
| array (base pointer) not only the coefficients (8, 8*%o, 8*%o*%m above)
have to
| match but also the range of the subscripts must be right (globally over
all
| arrays). For example with two accesses
|
|  A[i+4][j-4][k-7]
|  A[...][i-k][3*j]
|
| we'd need to check that
|
|   max{j-4, i-k}  -  min{j-4, i-k}   <=  %m - 1
|   max{k-7, 3*j}  -  min{k-7, 3*j}   <=  %o - 1

An interjection from the peanut gallery...

One thing that would be nice would be a way to indicate in LLVM instructions
that _by construction_ a given variable will be a valid index for a given
dimension of a given array. This isn't so much use in C-style languages
where arrays don't have size data canonically associated with them, but for
languages with constructs like (in the simplest case)

for i=0:dimension(A,0): acc+=A[i]

or other more complicated "index generator" expressions like generating
indices from stencils. At the moment (as I understand the LLVM IR) a
language can only specify that an entire linearised access expression is
within the linearised bounds. This would provide a way to hopefully boost
the "safe to apply" rate of LLVM optimisers like polly for languages that
are amenable to such constructs. This presumably requires a way to link
array pointers, dimensions, bounds and indexes so it's not obvious how to do
it within the LLVM context of course... (There's also the issue of exposing
transitivity: the source language may know i is a by construction index into
A, and B is the same shape as A hence i is also guaranteed to be
within-bounds index into B.)

Just a vague thought,
Regards,
Dave