llvm dev - Oct 2010 - [LLVMdev] 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: two_dim.c
Type: text/x-csrc
Size: 156 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101027/e2316b6c/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: two_dim.preopt.ll
Type: application/octet-stream
Size: 836 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101027/e2316b6c/attachment.obj>

On Oct 27, 2010, at 2:20 PM, Tobias Grosser wrote:
> 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>
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

On 27 October 2010 14:20, Tobias Grosser <grosser at fim.uni-passau.de>
wrote:
> 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

>
> which is actually this:
>
> {(({0,+,%m}<%for.cond>) + %vla),+,8}<%for.cond5>
>
> Any ideas
> Tobi
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101027/8229f1a7/attachment.html>

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.