LoopModels icon indicating copy to clipboard operation
LoopModels copied to clipboard

Add support for comparing references with different numbers of dimensions

Open chriselrod opened this issue 1 year ago • 0 comments

There are two primary examples. One is when we have a big block of memory, and different parts of these blocks correspond to different arrays.

unsigned M, N, K;
double* p = malloc((M*N + K)*sizeof(double));
MutPtrMatrix<double> A(p, DenseDims{M,N});
MutPtrVector<double> b(p + M*N, K);
// A[m,n]
// b[k]

In this case, we should be able to prove that no indexes into A can alias any into b and vice versa. A and b can thus be treated as separate, non-aliasing arrays, and their respective numbers of dimensions don't matter for dependence analysis. Their memory regions do not overlap.

A secondary motivating example is

for (size_t i = 0; i < M*N; ++i)
  C[i] = 0.0;
for (size_t n = 0; n < N; ++n)
  for (size_t k = 0; k < K; ++k)
    for (size_t m = 0; m < M; ++m)
      C[m + n*M] += A[m + k*M]*B[k + n*K];
for (size_t i = 0; i < M*N; ++i)
  C[i] = relu(C[i]);

here, we'd want to be able to fuse all of these into a single loop nest. C is treated as a 1-d array in the first and third tree, and as a 2-d array in the middle one, but here we should be able to see that we can convert the 1-d representation into 2-d.

Similarly, we should also support translating 2-d into 1-d in code generation, when possible.

chriselrod avatar Jun 03 '23 03:06 chriselrod