llvm dev - Aug 2014 - [LLVMdev] Scalar dependences in Dependence Analysis pass

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