[LLVMdev] The order of GVN and IndVarSimplify

[Andrew Trick]

On Oct 31, 2013, at 10:59 AM, Richard Sandiford <rsandifo at linux.vnet.ibm.com> wrote:

> 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.

This is a good observation, and a bug in the optimization pipeline. A couple things:

- I don’t see any good reason that the LinearFunctionTest replacement being done in IndVars can’t be done late, during LSR. AFAICT, it’s only purpose is enabling LoopStrengthReduce.

- I think GVN should run earlier, before most of the loop opts, and I think IndVars should run much later. I filed a bug for this. See PR17809: Reordering IR-level optimization passes. It’s hard to make progress on a major pass pipeline change because it requires a lot of investment in performance analysis. If you could file a bug for your test case and relate it to that bug it would be great. It can’t hurt, and may motivate someone to get around to fixing it sooner.

-Andy