[llvm-dev] ScalarEvolution "add nsw" question

[Johannes Doerfert via llvm-dev]

Hey Sanjoy,

Thanks for the quick repsonse.

On 04/10, Sanjoy Das wrote:
> [+CC Bjarke who wrote getNoWrapFlagsFromUB + related bits]
Also thanks.

> One fundamental reason why we cannot reason about NoWrap flags in SCEV
> for arithmetic outside of loops is to avoid issues like this:
> 
> if (cond) {
>   val[x +nsw y] = 42;
> } else {
>   val[x + y] = 42;
> }
> 
> Now *both* the "x +nsw y" and "x + y" will get mapped to the same SCEV
> expression (this is by design [0]), and therefore we cannot mark *the*
> SCEV expression for "x + y" with NSW, otherwise we may incorrectly
> simplify the "val[x + y] = 42" branch.
OK. I might have to look at the IR then since I am interested in the
particular instructions that make up the computation not the abstract
"arithmetic".

> (Btw, I'm sure you're aware of this, but "x +nsw y" by itself does not
> guarantee no-wrap, it only does so if "x +nsw y" is used in a
> side-effecting way.)
I was not (in particular) but that makes sense. For my work the poison
value will (almost) always cause a side-effect to have undefined
behaviour so that should not be a problem.

> getNoWrapFlagsFromUB() avoids the problem above by adding NSW
> (resp. NUW) to operations on add recurrences (i.e. an add-rec + 2,
> say) that are guaranteed to execute at least once per loop iteration.
> Thus we are guaranteed that the *arithmetic operation* (not //that//
> specific instruction, but the arithmetic itself) does not overflow on
> any iteration and thus can be safely marked as non-wrapping, since if
> it didn't the program is guaranteed to be UB.
Mh, I have to think about this a bit...

Is there any plan to use e.g., post-dominance information to
propagate wrapping flags? If x +nsw y post-dominates the entry block
[and is used in some side-effect instruction] the SCEV could be marked
as non-wrapping, couldn't it? How do you determine if the operation will
poison a side-effect instruction anyway?

> [0]: IOW, we don't "key" on the no-wrap tag, we just key on the
> arithmetic bits of the operation and mutate SCEV expression in-place
> when we discover NUW / NSW.
> 
> -- Sanjoy

Cheers,
  Johannes

> Johannes Doerfert via llvm-dev wrote:
> >Hello,
> >
> >I was wondering under which circumstances ScalarEvolution will propagate
> >the no wrap flags from binary operators. In particular I looked at
> >non-loop carried code, e.g., as in the following function:
> >
> >   int add(int x, int y) { return x + y; }
> >
> >for which clang uses an "add nsw" instruction but ScalarEvolution does
> >not propagate this information. The -analyze output looks like this:
> >
> >   Classifying expressions for: @add
> >     %add = add nsw i32 %x, %y
> >     -->   (%x + %y) U: full-set S: full-set
> >
> >The piece of code that causes this (for me) unexpected result is located
> >in the ScalarEvolution::getNoWrapFlagsFromUB(...) function and looks
> >like this:
> >
> >   if (InnermostContainingLoop == nullptr ||
> >       InnermostContainingLoop->getHeader() != BinOp->getParent())
> >     return SCEV::FlagAnyWrap;
> >
> >If the "InnermostContainingLoop" is a nullptr, thus if the binary
> >operator is not contained in a loop, all overflow annotations are simply
> >discarded.
> >
> >I do not know if I am missing something or if simply nobody cared so
> >far. In any case, I would appreciate any documentation on the current
> >implementation as well as pointer to were it could be improved.
> >
> >Cheers,
> >   Johannes
> >
> >
> >P.S.
> >   I have another problem with the way we currently discard the "nsw"
> >   information for accesses ("gep inbounds" apparently only implies nuw).
> >   I will probably start another thread for that one [after I read the
> >   GEP handling in more detail].
> >
> >
> >_______________________________________________
> >LLVM Developers mailing list
> >llvm-dev at lists.llvm.org
> >http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
> -- 
> You received this message because you are subscribed to the Google Groups "Polly Development" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to polly-dev+unsubscribe at googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 

Johannes Doerfert
Researcher / PhD Student

Compiler Design Lab (Prof. Hack)
Saarland University, Computer Science
Building E1.3, Room 4.31

Tel. +49 (0)681 302-57521 : doerfert at cs.uni-saarland.de
Fax. +49 (0)681 302-3065  : http://www.cdl.uni-saarland.de/people/doerfert
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 213 bytes
Desc: Digital signature
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160411/5701d0c2/attachment.sig>