llvm dev - May 2018 - LLVM SCEV isAddRecNeverPoison and strength reduction

+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,

Hi,

I don't have much knowledge about how it actually works, but it seems like
the code in getZeroExtendExpr already checks similar stuff, such as:
auto NewFlags = proveNoWrapViaConstantRanges(AR);
I thought that maybe it would not be too difficult to also call
isAddRecNeverPoison in some way.

Thanks for your help!

Gal

-----Original Message-----
From: Sanjoy Das <sanjoy at playingwithpointers.com> 
Sent: Thursday, May 10, 2018 06:04
To: Gal Zohar <Gal.Zohar at ceva-dsp.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: LLVM SCEV isAddRecNeverPoison and strength reduction

+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,

Hi,

After some more investigation, it seems like this code:
          // We can add Flags to the post-inc expression only if we
          // know that it us *undefined behavior* for BEValueV to
          // overflow.
         if (auto *BEInst = dyn_cast<Instruction>(BEValueV))
            if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst,
L))
            {
              (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
            }

          return PHISCEV;

Always gets 0 as the Flags (at least in my example of loop with short iterator).
I don't really understand what this condition is supposed to handle and how
to adjust it to set the appropriate flags.

-----Original Message-----
From: Gal Zohar 
Sent: Thursday, May 10, 2018 08:38
To: 'Sanjoy Das' <sanjoy at playingwithpointers.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: RE: LLVM SCEV isAddRecNeverPoison and strength reduction

Hi,

I don't have much knowledge about how it actually works, but it seems like
the code in getZeroExtendExpr already checks similar stuff, such as:
auto NewFlags = proveNoWrapViaConstantRanges(AR); I thought that maybe it would
not be too difficult to also call isAddRecNeverPoison in some way.

Thanks for your help!

Gal

-----Original Message-----
From: Sanjoy Das <sanjoy at playingwithpointers.com>
Sent: Thursday, May 10, 2018 06:04
To: Gal Zohar <Gal.Zohar at ceva-dsp.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: LLVM SCEV isAddRecNeverPoison and strength reduction

+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,