Re: [llvm-dev] the nsw story, revisited

Previous Topic Next Topic
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
Report Content as Inappropriate

Re: [llvm-dev] the nsw story, revisited

Tim Northover via llvm-dev
         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

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


LLVM Developers mailing list
[hidden email]