[llvm-dev] the nsw story, revisited
Peter Lawrence via llvm-dev
llvm-dev at lists.llvm.org
Tue Jun 13 14:54:04 PDT 2017
John,
Sanjoy,
Nuno,
David,
Thanks for the tip, below is a complete list and summary of every
thread in the archives with “nsw” in its subject line that I could find.
I am suggesting something similar to Dan's third option below (Tue Nov 29 2011
"the nsw story”, Dan Gohman), when hoisting an instruction with ‘nsw’ it looses
the ‘nsw’ attribute, but without saying “add-nsw is a fully side-effecting
instruction”.
This option was back then seen by Dan as too much effort, but the current
proposal requires at least the same amount of effort. To be specific the
current proposal requires adding “freeze” instead of removing “nsw”. It is
pretty much the same amount of editing work on the compiler sources either
way as far as add/sub/mul/shl are concerned.
The difference is that removing “nsw” from an operation is simpler and cleaner
than adding “freeze” to it, and in software engineering we are always striving
for the simplest and cleanest solution.
IIUC option three does not inhibit Dan's original goal of promoting 32-bit
induction variables to 64-bit on an LP64 target. And I don’t agree with Dan's
description of this being “suboptimal” for any other reason, the lost
information does not seem to be useable AFAICT, but if you disagree then simply
insert an “llvm.assume" in the spot where the operation is being hoisted from.
So I propose that we revisit this option. It was never fully explored in Dan’s
original email, nor in any subsequent emails, and now especially it seems to
deserve it.
Thoughts ?
Comments ?
Questions ?
Peter Lawrence.
———————————————————————————————————————————————————————
llvm-dev No Signed Wrap (NSW) Subject Line References
2017: =========================================================================
# all quiet until that pesky Peter Lawrence came along !
2016: =========================================================================
------------------------------------------------------------------------
Tue Sep 20 2016 "Inferring nsw/nuw flags for increment/decrement based on relational comparisons" (Matti Neimenmaa)
> 1. If (X s< Y), then both X + 1 and Y - 1 are nsw.
> 2. If (X u< Y), then both X + 1 and Y - 1 are nuw.
------------------------------------------------------------------------
Mon Aug 8 2016 "X86ISelLowering: Promote add nsw to a wider type" --- continued
------------------------------------------------------------------------
Tue Jul 19 2016 "X86ISelLowering: Promote add nsw to a wider type" (Artur Pilipenko)
# Artur asks if X86 sext-nsw fix can be applied to zext
------------------------------------------------------------------------
Fri Apr 15 2016 "is trapping allowed when add with nsw flag overflows" (Manuel Jacob)
# hmmm, responses aren't very clear, yet another example why
# the LangRef needs a revision
------------------------------------------------------------------------
Sun Apr 10 2016 "Scalar Evolution 'add nsw' question" (Johannes Doerfert)
# Sanjoy explains why SCEV doesn't key on nsw/nuw flags,
# Johannes notes the difference between SCEV's flow-insensitive
# analysis and Polly's flow-sensitive analysis
2015: =========================================================================
------------------------------------------------------------------------
Mon Aug 10 2015 "nsw and ExtLdPromotion()" (Lawrence Hu)
# Lawrence seems confused about nsw,
# resolved with some explainations by Jonathan
------------------------------------------------------------------------
Wed Jul 1 2015 "deriving undefined behavior from nsw/inbounds/poison for scalar evolution" --- continued
# Andy offers some observations regarding SCEV, Loop Strength
# Reduction (LSR), ...
# Hal recommends fiddling with target DataLayout description
# * the thread ends without resolution, was probably resolved off-line
------------------------------------------------------------------------
Fri Jun 26 2015 "deriving undefined behavior from nsw/inbounds/poison for scalar evolution" (Bjarke Roune)
# Bjarke wants to write an analysis pass that figures out when "poison"
# is guaranteed to produce "undefined behavior", his motivation is
# (once again) related to sign extend and loop induction vars in LP64,
# but where 64-bit are more expensive than 32-bit (?)
------------------------------------------------------------------------
Mon May 11 2015 "Scalar Evolution code on nsw inconsisten with commment" (Jingyue Wu)
# Sanjoy replys with "the [SCEV] code looks incorrect"
# * the thread ends without resolution, was probably resolved off-line
2014: =========================================================================
------------------------------------------------------------------------
Tue Jul 22 2014 "On semantics of add instruction - nsw,nuw flags" (Rekha R)
# Rekha asks why "a +nsw b" and "a + b" GVN/CSE to "a + b" and
# not "a +nsw b"
#
# it is interesting to note that there is a lot of confusion in the
# responses. especially that there is no answer to the follow on
# question that is how are these two statements consistent: "the LangRef
# says nsw is a *guarantee* that the operation will not overflow" and "the
# LangRef says that if the operation overflows the result is poison"
------------------------------------------------------------------------
Tue Sep 2 2014 "preserving nsw/nuw bits" (Chad Rosier)
# Chad has a WIP that makes this a complicated request that is never
# resolved in the thread
------------------------------------------------------------------------
Sat Jan 4 2014 "a question about everyone's favorite constructs: nsw and nuw" (Chandler Charruth)
# Chandler brings back the question about sext in LP64 targets,
# but in the context of straight line code (or unrolled loop) rather
# than in Dan's context of within a loop.
# Chandler starts out feeling this should be done in the IR for all
# targets, rather than in CodeGenPrepare (CGP) just for LP64 targets,
# Hal wants the nsw/nuw info to propagate into the SDAG and even MI
# representations, Andy counters with arguments against that and with
# arguments for CGP, Jim concurs with Andy, Quentin concurs with Andy
# and Jim and starts working on it, finally Chandler concludes with
# "can I have the patch".
2013: =========================================================================
------------------------------------------------------------------------
Fri Nov 1 2013 "SCEV and GEP nsw flag" --- continued
------------------------------------------------------------------------
Thu Oct 31 2013 "SCEV and GEP nsw flag" (Hal Finkel)
# Hal wants the compiler to conclude that "(&A[i] - &A[i+k])" is
# negative when inside "if (k > 0)", but SCEV doesn't because it
# doesn't handle nsw well
------------------------------------------------------------------------
Tue Jun 25 2013 "SimplfyIndVar looses nsw flag" ()
------------------------------------------------------------------------
Mon May 6 2013 "do we abuse the nsw flag"
# someone needed to use "-fwrapv" to get (x*y)/y ===> (x)
# IE the compiler won't do the simplification if it thinks the
# multiply could overflow and wrap
2012: =========================================================================
# a quiet year for nsw/undef/poison !
2011: =========================================================================
------------------------------------------------------------------------
Mon Dec 12 2011 "nsw is still logically inconsistent" (Dan Gohman)
# Dan provides this example
# i32 a,b; i64 c,d,e,f;
#
# if (cond) { // assume cond prevents signed wrap
# c = sext64( a +nsw b ) // upper 33-bits all 1's or all 0's
# d = (c >> 31) + 1 // 0 or 1 result
# e = d <u 2 // 1 result
# f = 1 / e // no possible divide-by-zero
# }
# the problem is when the compiler tries to speculatively hoist everything
# out of the if-cond. now when (a +nsw b) does overflow wrap, the
# promotion of a and b to i64 means sext64(a) + sext64(b) can evaluate
# to something whose upper 33-bits aren't all 1's or all 0's and we can
# end up with divide-by-zero.
#
# (remember that nsw was introduced to allow promotion to i64 to
# allow eliminating sext64 on LP64 targets, they haven't been
# eliminated in this example because the actual goal is just to
# hoist the sext64 out of a loop which isn't shown for simplicity)
# ===> the thread is left unresolved, whatever llvm is actually
# doing to resolve the problem isn't documented here <===
------------------------------------------------------------------------
Thu Dec 1 2011 "the nsw story" --- continued
# Dan shows this argument against option 1 (“undef" as alt to "poison")
# but its still not clear how "poison" solves the problem
int a = INT_MAX, b = 1;
long c = (long)(a + b);
What is the value of c, on an LP64 target?
By standard C rules, the add overflow invokes immediate undefined behavior of course.
If a and b are promoted to 64-bit, c is 0x0000000080000000.
In a world where signed add overflow returns undef, c could be any of
0x0000000000000000
0x0000000000000001
0x0000000000000002
...
0x000000007fffffff
or
0xffffffff80000000
0xffffffff80000001
0xffffffff80000002
...
0xffffffffffffffff
however it can't ever be 0x0000000080000000, because there's no 32-bit value
the undef could take which sign-extends into that 64-bit value.
Therefore, if signed add overflow returns undef, promoting such 32-bit variables to
64-bit variables is not a behavior-preserving transformation.
------------------------------------------------------------------------
Tue Nov 29 2011 "the nsw story" (Dan Gohman)
# starts by describing sign-extension on LP64 targets as the
# motivation for "nsw", in that in many situations a 32-bit add-nsw
# can be promoted to a 64-bit add, eliminating the sext operation,
# or at least hoisting it out of a loop where it can be expensive
# could also be titled "the poison story",
# because it ends with this list of alternatives to "poison"
# none of which seem to be acceptable to Dan, but I'm still
# not sure how "poison" solves the LP64 sext problem
# here are Dan's alternatives to "poison"
A natural reaction to this problem is to think that LLVM IR is so nice
and pretty that naturally there must be a nice and pretty solution. Here
are some alternatives that have been considered:
- Go back to using undef for overflow. There were no known real-world
bugs with this. It's just inconsistent.
- Define add nsw as a fully side-effecting operation, and accept the
limits on code motion that this implies. However, as LLVM starts doing
profile-guided optimizations, and starts thinking about more diverse
architectures, code speculation will likely become more important.
- Define add nsw as a fully side-effecting operation, and teach
optimization passes to strip nsw when moving code past control
boundaries. This is seen as suboptimal because it prevents subsequent
passes from making use of the nsw information. And, it's extra work
for optimization passes.
- Instead of trying to define dependence in LangRef, just say that if
changing the value returned from an overflowing add nsw would
affect the observable behavior of the program, then the behavior of
the program is undefined. This would reduce the amount of text in
LangRef, but it would be a weaker definition, and it would require
sign-extension optimizers and others to do significantly more work
to establish that their transformations are safe.
- Give up on nsw and have compilers emit warnings when they are unable
to perform some optimization due to their inability to exclude the
possibility of overflow. Obviously the warnings would not be on by
default, or even -Wall or probably even -Wextra, so -Werror users need
not revolt. Many people are often faced with code that they cannot
modify for any number of reasons, and would not be able to make use
of such warnings. It's an interesting tradeoff, but it's unpopular.
Unfortunately, none of these are completely nice and pretty. Because of
this, and because most people don't care, nsw with all its conceptual
complexity has survived.
------------------------------------------------------------------------
Mon Oct 3 2011 "definition of C/C++ integeral conversion (was re:nsw/nuw for trunc)" --- continued
# * still no resolution
------------------------------------------------------------------------
Fri Sep 30 2011 "definition of C/C++ integeral conversion (was re:nsw/nuw for trunc)" (Tobias Grosser)
# C language seems to say trunc of signed is "implementation-defined"
# for overflow, meaning ??? for llvm ...
# * unresolved in this thread,
------------------------------------------------------------------------
Thu Aug 11 2011 "nsw/nuw for trunc" (Florian Merz)
# some folks think this request isn't consistent with existing use in
# add/mul/shl, Chris thinks it is, ...
# * unresolved in this thread, the LangRef still doesn't have this
------------------------------------------------------------------------
Wed Jan 12 2011 "Question about nsw and nuw flags" (Douglas Teixeira)
# Chris says RTM !
2010: =========================================================================
# a quiet year for nsw !
2009: =========================================================================
------------------------------------------------------------------------
Wed Sep 2 2009 "LangRef description of 'add nsw' doesn't match reality" (Paul Melis)
# LangRef changed to conform to llvm-as syntax restrictions
===============================================================================
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170613/d6bfd072/attachment-0001.html>
More information about the llvm-dev
mailing list