# LoopVectorize fails to vectorize more complex loops

Hello.
Could you please tell me why the first loop of the following program (also maybe the commented loop) doesn't get vectorized with LoopVectorize (from a recent LLVM build from the SVN repository from Jun 2018)?

typedef short TYPE;
TYPE data;

void kernel_covariance(int m, int n, TYPE mean) {
int i, j, k;

for (j = 0; j < m; j++)
{
mean[j] = 0.0;
for (i = 0; i < n; i++)
mean[j] += data[j][i];
//mean[j] /= float_n;
}

// This loop gets vectorized
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
data[i][j] -= mean[j];

/*
// This loop doesn't get vectorized either:
for (i = 0; i < m; i++)
for (j = i; j < m; j++)
{
cov[i][j] = 0.0;
for (k = 0; k < n; k++)
cov[i][j] += data[i][k] * data[j][k];
sum += data[i][k] * data[j][k];
cov[i][j] /= (float_n - 1.0);
cov[j][i] = cov[i][j];
}
*/
}

For the first loop I get the following debug info from clang and opt:
LV: Checking a loop in "kernel_covariance" from test.c:10:7
LV: Loop hints: force=? width=0 unroll=0
LV: Found a loop: for.body3.us
LV: PHI is not a poly recurrence.
LV: Found an unidentified PHI. %2 = phi i16 [ 0, %for.body.us ], [ %add.us, %for.body3.us ], !dbg !48
LV: Can't vectorize the instructions or CFG
LV: Not vectorizing: Cannot prove legality.

Thank you,
Alex

Hi Alex,

This seems like LICM problem, where it's not able to promote the memory reference to scalar because of unknown aliasing.
This result recurrence store remain in the loop body and loop vectorization fails to vectorize.
Loop Versioning LICM pass can help in this case.

- Ashutosh

Agreed on the aliasing issue. You could also rewrite your loop like this:

for (j = 0; j < m; j++)
{
TYPE red = 0.0;
for (i = 0; i < n; i++)
red += data[j][i];
mean[j] = red;
}

Diego