Hi,

I am just found a scalar evolution function that does not seem canonical to me.

The C code I used to produce it is:

long foo (long n, long m) {

long i, j;

long A[n][m];

for (i = 0; i < n; ++i)

for (j = 0; j < m; ++j)

A[i][j] = 1;

return A[42][42];

}

This produces after applying -mem2reg the attached LLVM-IR.

For the store to the array A in the loop I get this scalar evolution function:

{((8 * ({0,+,(8 * %m)}<%for.cond> /u 8)) + %vla),+,8}<%for.cond5>

For me it seems the devision by "8" is not canonical. Is there any reason this can not be simplified to:

{((1 * ({0,+,(1 * %m)}<%for.cond>)) + %vla),+,8}<%for.cond5>

which is actually this:

{(({0,+,%m}<%for.cond>) + %vla),+,8}<%for.cond5>

Any ideas

Tobi

two_dim.c (156 Bytes)

two_dim.preopt.ll (836 Bytes)

The original expression has an extra *8, so it'd be

{({0,+,(8 * %m)}<%for.cond> + %vla),+,8}<%for.cond5>

Yes, it looks like ScalarEvolution is missing this opportunity to

canonicalize.

It's pretty bizarre that the IR for this code has udiv/lshr

instructions in the first place. Apparently these are to

compensate for the scaling that getelementptr does. That could

probably benefit from some attention too.

Dan

Hi,

I am just found a scalar evolution function that does not seem canonical to me.

The C code I used to produce it is:

long foo (long n, long m) {

long i, j;

long A[n][m];

for (i = 0; i < n; ++i)

for (j = 0; j < m; ++j)

A[i][j] = 1;

return A[42][42];

}

This produces after applying -mem2reg the attached LLVM-IR.

For the store to the array A in the loop I get this scalar evolution function:

{((8 * ({0,+,(8 * %m)}<%for.cond> /u 8)) + %vla),+,8}<%for.cond5>

For me it seems the devision by “8” is not canonical. Is there any reason this can not be simplified to:

{((1 * ({0,+,(1 * %m)}<%for.cond>)) + %vla),+,8}<%for.cond5>

Because we have to assume 2’s complement arithmetic. Unless we know (or can prove) that the “8 *” won’t overflow, we can’t safely fold it away against “/u 8”.

Nick

Hi Nick,

For the store to the array A in the loop I get this scalar evolution function:

{((8 * ({0,+,(8 * %m)}<%for.cond> /u 8)) + %vla),+,8}<%for.cond5>

For me it seems the devision by "8" is not canonical. Is there any reason

this can not be simplified to:

{((1 * ({0,+,(1 * %m)}<%for.cond>)) + %vla),+,8}<%for.cond5>

Because we have to assume 2's complement arithmetic. Unless we know (or can

prove) that the "8 *" won't overflow, we can't safely fold it away against "/u 8".

in the original code, overflow corresponds to undefined behaviour (wrapping

around the end of the address space) so it should be possible to deduce that

this transform is ok using more context.

Ciao,

Duncan.