[llvm-dev] ScalarEvolution "add nsw" question

[Sanjoy Das via llvm-dev]

[+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