Re: [llvm-dev] LLVM SCEV isAddRecNeverPoison and strength reduction

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] LLVM SCEV isAddRecNeverPoison and strength reduction

Joel E. Denny via llvm-dev
+CC llvm-dev

On Tue, May 8, 2018 at 2:34 AM, Gal Zohar <[hidden email]> 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,
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] LLVM SCEV isAddRecNeverPoison and strength reduction

Joel E. Denny via llvm-dev
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 <[hidden email]>
Sent: Thursday, May 10, 2018 06:04
To: Gal Zohar <[hidden email]>
Cc: llvm-dev <[hidden email]>
Subject: Re: LLVM SCEV isAddRecNeverPoison and strength reduction

+CC llvm-dev

On Tue, May 8, 2018 at 2:34 AM, Gal Zohar <[hidden email]> 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,
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] LLVM SCEV isAddRecNeverPoison and strength reduction

Joel E. Denny via llvm-dev
In reply to this post by Joel E. Denny via llvm-dev
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' <[hidden email]>
Cc: llvm-dev <[hidden email]>
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 <[hidden email]>
Sent: Thursday, May 10, 2018 06:04
To: Gal Zohar <[hidden email]>
Cc: llvm-dev <[hidden email]>
Subject: Re: LLVM SCEV isAddRecNeverPoison and strength reduction

+CC llvm-dev

On Tue, May 8, 2018 at 2:34 AM, Gal Zohar <[hidden email]> 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,
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev