[LLVMdev] Scalar Evolution not canonalizing division?

Dan Gohman gohman at apple.com
Wed Oct 27 16:17:47 PDT 2010


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





More information about the llvm-dev mailing list