[llvm-dev] Question on induction variable simplification pass

[Chawla, Pankaj via llvm-dev]

Hi all,

It looks like the induction variable simplification pass prefers doing a zero-extension to compute the wider trip count of loops when extending the IV. This can sometimes result in loss of information making ScalarEvolution's analysis conservative which can lead to missed performance opportunities.

For example, consider this loopnest-

  int i, j;
  for(i=0; i< 40; i++)
  for(j=0; j< i-1; j++)
    A[i+j] = j;


We are mainly interested in the backedge taken count of the inner loop.

Before indvars, the backedge information computed by ScalarEvolution is as follows-

Outer loop-
backedge-taken count is 39
max backedge-taken count is 39

Inner loop-
backedge-taken count is {-2,+,1}<nsw><%for.cond1.preheader>
max backedge-taken count is 37


After indvars, the backedge information computed by ScalarEvolution is as follows-

Outer loop-
backedge-taken count is 39
max backedge-taken count is 39

Inner loop-
backedge-taken count is (-1 + (zext i32 {-1,+,1}<nsw><%for.cond1.preheader> to i64))<nsw>
max backedge-taken count is -1


If we generate sext instead of zext, the information computed by ScalarEvolution is as follows-

Outer loop-
backedge-taken count is 39
max backedge-taken count is 39

Inner loop-
backedge-taken count is {-2,+,1}<nw><%for.cond1.preheader>
max backedge-taken count is -2

We now have a simplified backedge taken count for the inner loop which is almost as precise as before indvars, except for the <nw> flag instead of <nsw> flag. I think ScalarEvolution should be able to precisely deduce wrap flags in the presence of sext but this may require a separate fix. The reason for the conservative max backedge taken count may be the same.

Thanks,
Pankaj
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170413/61343235/attachment.html>