llvm dev - Apr 2016 - ScalarEvolution "add nsw" question

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].

-- 

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/20160410/8ad3fb1f/attachment.sig>

[+CC Bjarke who wrote getNoWrapFlagsFromUB + related bits]

Hi Johannes,

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.

(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.)

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.


[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

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

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>