[llvm-dev] LLVM SCEV isAddRecNeverPoison and strength reduction

[Sanjoy Das via llvm-dev]

+CC llvm-dev

On Tue, May 8, 2018 at 2:34 AM, Gal Zohar <Gal.Zohar at ceva-dsp.com> wrote:
> I noticed that SCEV, when trying to perform strength reduction, doesn’t use
> the ability to prove an induction variable does not signed/unsigned wrap due
> to infinite loops.
>
> Is there an easy way to use the isAddRecNeverPoison function when
> determining if strength reduction is possible? In getZeroExtendExpr.
>
> Is there a reason why this doesn’t happen?

I guess your point is that in

int foo(int a) {
  int sum = 0;

  for (short i = 0; i < a; i++) {
    sum++;
  }
  return sum;
}

either the loop is finite (and i <= SHORT_MAX) or the program has UB
(since sum overflows), so we can assume i<=SHORT_MAX and compute the
trip count accordingly?

In LLVM the fix isn't as simple unfortunately because signed integer
overflow is not UB, but it produces a "poison value" that causes UB
(roughly) if consumed by some side effecting operation.

It should still be possible to do this optimization -- the return
value is either poison or i <= SHORT_MAX.  Because it is legal to
replace poison with whatever value we want, we can just pretend i <=
SHORT_MAX, compute the exit value under that assumption and delete the
loop.  However, I suspect this will be a fair amount of work.

Thanks!
-- Sanjoy

PS: this is the original email for llvm-dev:



I noticed that SCEV, when trying to perform strength reduction,
doesn’t use the ability to prove an induction variable does not
signed/unsigned wrap due to infinite loops.



Is there an easy way to use the isAddRecNeverPoison function when
determining if strength reduction is possible? In getZeroExtendExpr.

Is there a reason why this doesn’t happen?



This simple example is not optimized due to this:



int foo(int a)

{

                int sum = 0;

                for (short i = 0; i < a; i++)

                {

                                sum++;

                }

                return sum;

}



Thanks,