[LLVMdev] The order of GVN and IndVarSimplify

[Richard Sandiford]

This might be hard cases making bad law, but the loop:

  void
  f (unsigned short *x, int *l)
  {
    int c = *l;
    int i;
    for (i = 0; i < c; i++)
      if (x[i])
        x[i]++;
  }

is converted to decrement-and-branch form by LoopStrengthReduce while:

  void
  f (unsigned short *x, int *l)
  {
    int i;
    for (i = 0; i < *l; i++)
      if (x[i])
        x[i]++;
  }

isn't.  This makes a big difference on z, which has a native decrement-and-
branch instruction.

The problem seems to be that the strength-reduction pass relies on
IndVarSimplify to convert loop exit conditions into a canonical != form:

    // Equality (== and !=) ICmps are special. We can rewrite (i == N) as
    // (N - i == 0), and this allows (N - i) to be the expression that we work
    // with rather than just N or i, so we can consider the register
    // requirements for both N and i at the same time. Limiting this code to
    // equality icmps is not a problem because all interesting loops use
    // equality icmps, thanks to IndVarSimplify.
    if (ICmpInst *CI = dyn_cast<ICmpInst>(LF.UserInst))
      if (CI->isEquality()) {

and this is happening for the first loop but not the second.  The reason
is that the second loop still has two loads of *l by the time IndVarSimplify
is run; one for the precondition of the rotated loop and one for the loop
exit.  This means that IndVarSimplify can't tell that the precondition
(skip the loop if *l <= 0) is operating on the same *l as the loop exit,
and therefore can't work out that *l is the trip count.  The two "*l"s
are only fused by GVN, which runs after IndVarSimplify.

Moving GVN before IndVarSimplify gives me the code I wanted.  So does adding
an IndVarSimplify pass before LoopStrengthReduce.  Would either of these
be OK?  I was wondering whether the second made sense anyway, since
LoopStrengthReduce is done by CodeGen and is pretty far separated from
the usual IndVarSimplify position.

I've attached the .ll form of the second loop, in case it helps.

Thanks,
Richard


-------------- next part --------------
A non-text attachment was scrubbed...
Name: loop.ll
Type: application/octet-stream
Size: 2140 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131031/2e0655dd/attachment.obj>