Scalar Evolution not canonalizing division?

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.