[llvm-dev] The undef story

[Peter Lawrence via llvm-dev]

> On Jun 29, 2017, at 10:38 AM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:
> 
> Hi Peter,
> 
> On Thu, Jun 29, 2017 at 8:41 AM, Peter Lawrence
> <peterl95124 at sbcglobal.net <mailto:peterl95124 at sbcglobal.net>> wrote:
>> Here’s another way to look at it, no one has ever filed a bug that reads
>> “I used undefined behavior in my program, but the optimizer isn’t taking advantage of it”
>> But if they do I think the response should be
>> “you should not expect that, standard says nothing positive about what undefined behavior does"
> 
> Of course no one would file such a bug (since if your program has UB,
> the first thing you do is fix your program).  However, there are
> plenty of bugs where people complain about: "LLVM does not optimize my
> (UB-free) program under the assumption that it does not have UB"
> (which is what poison allows):
> 

Sanjoy,
            I copied the bug reports below for reference.

The way I read the first report is that the reason this problem exists today is the 
existence of “poison” in the LangRef, IE. we have to call isSCEVExprNeverPoison()
which returns true in this case.

So this is a reason to not have “poison”, “poison” is not enabling anything
here, it is actually making it harder to do this optimization.

This entire problem disappears in the alternate proposal
(Fix “undef”, delete “poison” and “freeze”, no hoisting of nsw attributes)
because the function isSCEVExprNeverPoison() would be deleted.


The way I read the second report is that a special case needs to be added for "+nsw"
This does not seem to have any thing to do with “undef” or “poison"



Note that I don’t consider optimizing “nsw” as an example of optimizing “undefined
Behavior”, “nsw” is simply an attribute that we take advantage of, so

I am still waiting for someone to come up with a real source code example
were “undef” / “poison” occurs in the IR and the optimizer takes advantage.


Peter Lawrence.



> https://bugs.llvm.org/show_bug.cgi?id=28429 <https://bugs.llvm.org/show_bug.cgi?id=28429>

The following loop is not unrolled because the trip count is not simple constant: 

void foo(int x, int *p) {
   x += 2; //any value bigger than 1
   for (int i = x; i <= x+1; ++i) p[i] = i;
}

The attached IR is generated compiling the above source with:
./bin/clang --target=aarch64-arm-none-eabi  -mllvm -debug-only=loop-unroll -O3

SCEV find the trip count as: (-2 + (-1 * %x) + ((2 + %x) smax (3 + %x)))

This expression can be simplified into a constant if the arguments of smax are not wrapping. But while the original source has non-wrapping expressions, they are not marked as such by SCEV. Reason is that SCEV considers these expressions possible poison values and marks them as wrapping. This seem to be a limitation in the llvm::ScalarEvolution::isSCEVExprNeverPoison function.

Analysis so far:
The actual add instructions have the nsw flags and reside in a basic block just before the loop body. The isSCEVExprNeverPoison function is called on them but assumes the instruction must be part of a loop. If the instruction is not part of any loop it is reported as a possible poison value. 

A possible fix would be to assume the instruction is loop independent if it is not part of any loop. But I am not sure if the loop information is complete (does absence of loop info on a basic block means there is no loop in the code in the scalar evolution pass?). With such a fix the resulting expression would be:
(-2 + (-1 * %x) + ((2 + %x)<nsw> smax (3 + %x)<nsw>)

This is foldable, although the current folding expression constructors don’t handle this case yet.



> https://groups.google.com/forum/#!topic/llvm-dev/JGsDrfvS5wc <https://groups.google.com/forum/#!topic/llvm-dev/JGsDrfvS5wc>


It looks like ScalarEvolution bails out of loop backedge computation
if it cannot prove the IV stride as either positive or negative 
(based on loop control condition). 
I think this logic can be refined for signed IVs.

Consider this simple loop-

void foo(int *A, int n, int s) {
  int I;
  for(i=0; i<n; i += s) {
    A[i]++;
  }
} 

 
The IV of this loop has this SCEV form-

{0,+,%s}<nsw><%for.body>

 
Can someone please clarify why it is not ok to deduce the stride to be 
positive based on the assumption that the IV cannot have a signed 
underflow due to the presence of the NSW flag otherwise the program 
has undefined behavior?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170629/57e01d87/attachment.html>