LLVM SCEV isAddRecNeverPoison and strength reduction

Project Infrastructure LLVM Dev List Archives
1

+CC 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?

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,

2

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

3

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.