[LLVMdev] Scalar dependences in Dependence Analysis pass

[Vaivaswatha N]

Hi,

I am trying to understand the dependence analysis framework in LLVM. In particular, regarding scalar dependencies, I noticed that the precision of the dependences returned were less than optimal for some simple kernels like matrix multiplication.

1.
for (i = 0; i < 100; i++)
  for (j = 0; j < 100 j++)
    for (k = 0; k < 100; k++)
      C[i][j] += (A[i][k] * B[k][j])

As remarked on the project webpage (https://sites.google.com/site/parallelizationforllvm/), the scalar dependence for 'C' along the 'k' dimension is (0, 0, S). However, in this case, it is safe to consider this dependence to be (0, 0, 1), which is more precise.

Similarly,

2. For the Hyperbolic PDE-style kernel (taken from M.Wolf's PLDI 91 paper)
  for (i = 0; i < 100; i++) {
    for (j = 0; j < 101; j++) {
      A[j+1] = (1/3) * (A[j] + A[j+1] + A[j+2]);
    }
  }
The set of dependences would be { (0,1), (1,0), (1,-1) }. However, due to 'A' being a scalar along the 'i' dimension, the analysis reports { (S, 1), (S, 0), (S, -1) }.

I am curious to understand why this precision loss is happening and what are the ways to fix it. I would be happy to contribute this to the LLVM tree if I can fix it.

Thanks,

- Vaivaswatha