being more of a real-time DSP/embedded sorta guy, i've never been impressed with code-elimination "optimization" schemes. i also see no reason to say that "value >> (amount-y) will yield Undefined Behavior when amount is zero". first of all, i don't see value >> (amount-y) in the code. i do see value >> (32-amount). if you meant "value >> (32-amount) will yield Undefined Behavior when amount is zero", then the claim is false (the result is well-defined).

@robertbristow-johnson: Some processors have shift instructions where x>>=n is equivalent to performing x>>=1, n times; others have instructions where it's equivalent to x>>=(n & INT_BITS). Further, some platforms might possibly interpret it as x = shift_function[n](x); [which could be good if e.g. a platform can support cheap indexed function calls and includes instructions to shift by 1, 4, 8, or 16, but lacks a shift-by-N instruction]. Consequently, to avoid imposing any extra burden on any platforms, the Standard specifies that on a 32-bit machine, x>>n is only defined for...

...values of n ranging from 0 to 31; consequently, x>>(32-y) is only defined for values of y ranging from 1 to 32. I am unaware that there's ever been any hardware where requiring that x>>32 yield an arbitrary selection between x and 0 would impose any significant burden; it would impose a slight burden on shift_function[x] implementations, but the cost of a single masking instruction (making the code shift_function[x & 31]) would be a fraction of the best-case time for a variable shift, and should thus not be a significant burden.

K&R C? ANSI??? i don't think so. if you have a 32-bit unsigned int x and you shift it right (or left, for that matter) by 32 bits, the result is zero. if a compiler does anything different than that, it's not compliant with what C is. there is nothing wrong with the compiler testing y to see if it exceeds 32 (or whatever is the bit width of the word the shift is acting on) and simply stuffing 0 in for x if the shift amount exceeds 32. but it's not undefined behavior. not in an ANSI-compliant compiler.

well, i just looked up an answer on SO. it appears that i am mistaken, at least regarding ISO definitions: ISO 9899:1999 6.5.7 Bit-wise shift operators §3 "The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined." ---- i think this is inexcusable.

@robertbristow-johnson: Back in 1989, anyone who suggested that a compiler given the above code should make the call to foo unconditional would have been laughed out of the room if not sent to the loony bin. If some processor's shift-right instruction would cause it to overheat and catch fire when shifting by 32 or more bits, I think people might have agreed that a compiler would be under no obligation to prevent that from occurring, but would also expect that a good compiler for such a platform should provide an option to generate "safe" code even though the Standard didn't require it.

Care to chat? My background's probably a bit like yours, and I'd like to somehow shift compiler development back toward a path which allows more useful optimizations than the current standard without going into wackyland.

i'm just pissed to discover the ISO spec. the shift operator should work predictably. you oughta be able to shift something left or right by 10000 bits. i know that C does not check for overflow with addition/subtraction (no saturation), and neither do non-DSP processors, but that is well published. if y>31, then x<<y or x>>y should be zero. if y<0, i think that x should be unchanged. some DSPs (like the SHArC) will interpret negative shift values as shifting the other direction, but i wouldn't put that into C as a feature.

chatting is fine, but i don't like chat rooms (even SE chat). you can google me pretty easily and find my audioimagination e-dress. i am not on-line often, even though i am right now.

What's an audioimagination e-dress? With regard to shifting, I have no problem with the Standard allowing implementations to make an arbitrary choice between the two indicated forms, and expressly indicating that the operation may take time proportional to (unsigned)amount (IIRC, if y was -1, the generated code for the INMOS Transputer would cause the shift instruction to take four billion cycles to execute with interrupts disabled). What I object to is the idea that anything good is achieved by requiring code like that shown above to be replaced by some more complicated form.

@robertbristow-johnson: I've been writing some proposals on a blog if you'd like to see them at supercatnet.blogspot.com (the blog is a bit of a mess, but it's a place I can write stuff and make it available).

As I see it [this differs a little from what I've said in my blog] different kinds of code will have different requirements with regard to invalid inputs: (1) In some cases code must either perform the indicated algorithm or indicate failure if invalid input makes that impossible; (2) In some cases, it's merely necessary that invalid input don't do anything too wacky; (3) In some cases, the supplier of the previous input will be willing to stake the fate of humanity on the fact that all input is valid.

The draft piece on my blog suggests that for many cases #2 above is the most accurate description of requirements. I'm not really sure whether it's better for a language to favor #1 or #2, but I'd posit that #3 represents an extreme minority of usage scenarios. If a program's only requirement when given invalid input is to refrain from launching nuclear missiles, achieving that objective shouldn't require more code than computing proper results when given valid input.

You could also ask when compilers started to optimize. As the first C compilers didn't. And @robert, if C had made the decision to always be mathematically correct and rigidly defined instead of going for speed and low implementation-complexity implying corner-cases and no-go-zones (trusting the programmer), it would have been a non-starter.

@Deduplicator: Early optimizers sought to find instruction sequences whose behavior was equivalent to a straightforward stack-machine translation of the source code. The kinds of integer optimizations that appeared in the 1990s would be supportable under an execution model that allowed would allow e.g. a 16-bit compiler regard an expression like 200*200 as arbitrarily being 40000, -25536, or any other number which was congruent to 40000 mod 65536.

BTW: One could have opted (if one rewrites history now) for far more regularity of the language and the need for the programmer to document all his assumptions as guarantees, instead of letting the compiler try to infer what it can by analysing what's allowed and what is not.

@Deduplicator: Returning to the primary question, can you point to any evidence of someone prior to 2009 advocating (and being taken seriously) the idea that compilers should use Undefined Behavior to make inferences about the inputs a program will receive.

@Deduplicator: The rules for what things are or are not Undefined Behavior were written to allow certain relatively narrow but useful forms of optimizations. I've seen no hint of evidence that they were ever intended to facilitate reverse-causal inference. If you can show evidence that such notions were considered prior to 2009 I'd love to see them. What's needed is not a language where everything is rigidly specified, but rather one where things are specified in just enough detail to make them usable for a program whose sole requirement when given invalid input is that it not launch nukes.

Well, it isn't "reverse-causal-inferrence". More like, it isn't smart enough to completely analyse the program from first principles, beside not neccessarily having the full sources, thus it trusts the programmer to know what he did, and uses hints (see UB) for determining when shortcuts can be taken.

Anyway, for unearthing historical documents, count me out, though I'll observe with interest. Also, did you kill the discussion which lead to this question? Because I thought I ran over some such this week...

@Deduplicator: I'm asking this question in response to someone else commenting that my claim that something changed around 2009-2010 was untrue and unfounded. The term "reverse-causal inference" is my own, but I don't know any other short way to describe the concept of working code backward to figure out what conditions would need to apply to avoid UB, and then generating code on the assumption that they do apply, whether or not it would actually be possible for them to do so. Can you offer a better term?

Hm. How about "trusting that the programmer is right, and your piece of the puzzle is simply too small to proove it"? Not catchy, and not really small. Maybe "trusting"? Anyway, sch optimizations are much more important in C++ with templates...

@Deduplicator: Trusting that the programmer is right about what? If I need to compute (y & ARBITRARY_MASK) > 31 ? 0 : x >> (y & 31) for whatever value of ARBITRARY_MASK would be most efficient, how should I write that in C?

@Deduplicator: Code for the x86 would be most efficient using a value of 0 for ARBITRARY_MASK, but code for the ARM would be most efficient using a value of 224. If the reason for having the compilers interpret x>>y as something other than the formula indicated above (but substituting the most efficient value of ARBITRARY_MASK) is to let compilers make code efficient, there should be a way for programmers wanting the above interpretation to get it without having to know which value of ARBITRARY_MASK will be best for the target platform.

@supercat Sorry, you lost me in the comment before rwong. I have no idea what you are arguing now.

@Deduplicator: My argument is that if a programmer wanted a compiler to assume the method would never be called with y==0, the programmer could have written something like ASSUME(y!=0); before it [having defined an ASSUME macro suitable for the platform being used]. I would posit that it is far more reasonable to say that x>>n implies the programmer knows that either of the common shifting approaches will meet requirements, than to say imply that the programmer knows that n will always be between 0 and 31.

@Deduplicator: Per the Standard: "If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined."

... As I said, there's a bit too much UB.

@Deduplicator: I just noticed you edited your earlier comment re trusting the programmer; my question is still open as to what terminology would most succinctly describe the idea of a compiler working backward and assuming that inputs which would cause UB cannot occur? "Trusting the programmer" hardly hints at that. Further, even if the lack of proper causal-inference directives made UB-based hackery necessary in C++, that's hardly a reason to pollute C with it (nor to favor UB-based hackery over a deliberately-designed set of inference directives).

The reasoning backwards in time is explained here: stackoverflow.com/questions/23153445/… The standards explicitly allows this. That question does not answer historical aspects, though.

@usr: I'm starting to wonder if the historical basis for the effective revocation of what used to be common implementation guarantees which most implementations supported and which many programs relied upon is a result of SFINAE in C++ requiring that implementations regard certain constructs as forbidden, rather than merely refraining from specifying their behaviors, an attitude which has consequently infected C. Any idea what kind of evidence might support or refute that theory? I was around in the 1980s-1990s when C overtook Pascal. If C compilers back then had treated...

...UB in hyper-modern fashion, I don't think it would have won the language wars. If a guarantee that certain actions will be a certain way would be of great benefit some kinds of programs, but some platforms (which might have little hope of running such programs) would be unable to support that guarantees, omitting the guarantees from the C standard makes it possible for the language to be used to implement programs that don't require them on platforms that can't easily support them, but if no platform offered additional guarantees the language would be too anemic to do much.

@supercat I wish C compilers would have been super strict about it from the beginning. Even now GCC and LLVM do nor replace each and every occurrence of UB with unreachable(). I think they should so that UB can no longer be ignored by mainstream developers. All compilers should run dataflow analysis and mercilessly replace all guaranteed UB with unreachable() (and potentially warn). UB really is not that hard to understand I think. The only reason it is still a curiosity for many is that it hits rarely enough to often be irrelevant.

@usr it is not just unreachable(); it is that some code produces UB for some input values, and the compiler is then designed to exclude those values out of the input domain. So, the compiler reasons that input value cannot be such-and-such. If it finds that the input value cannot be anything at all, then the function may even be eliminated.

@rwong yes, all of that follows from backwards control flow analysis. Anything that is postdominated by unreachable is also unreachable. Conditionals with one unreachable branch can be converted to an assert/assume. And so on.

@usr: Removing from the input domain values that would invoke behavior not defined by the Standard may improve performance in cases where all inputs come from trusted sources. It will degrade the level of performance that can be safely achieved in cases where inputs come from untrusted sources, and programs are allowed to yield essentially arbitrary output (with a few constraints) when given arbitrary inputs. The historical interpretation of UB on many platforms is in fact a good fit for such application requirements; a stricter interpretation is a lousy fit.

@supercat hm not sure what you are saying. I was not proposing to change anything about semantics of C. I meant to say that it would have been beneficial for the C ecosystem if compilers had exploited UB to the maximum from the beginning.

@usr: If a programmer doesn't care whether a platform (assuming int x,y,z;) evaluates if (x-y > z)... as if ((long)x-y > z or if (UINT_MAX/2+1+x-y > UINT_MAX/2+1+z), being able to use the first syntax to request whichever of the latter options would be more convenient for the compiler will provide useful opportunities for optimization which cannot be achieved any other way. If the only way a programmer can guarantee that the comparison will have no effect other than to yield 1 or zero is to write one of the latter forms, optimization will be impossible unless the programmer...

...somehow guesses right. If you take the grossly false view that C is a single unified language, the new interpretation of UB might not be a change, but C has never been and should not be a unified language. It is a collection of dialects which make a variety of trade-offs in order to best fit a variety of purposes. The dialect people seem to be pushing today may be good for applications that will never receive invalid input, but is lousy for applications which are allowed to produce almost arbitrary output when given invalid input, but must obey a few constraints regardless.

@supercat are we in agreement? I think the existence of UB in the language is useful. Also, I don't object to the idea that different compilers show different behavior in the presence of UB.

@usr: For the Standard to allow different dialects of C to offer different trade-offs of predictability versus performance for things like overflow is a good thing. The idea that compilers should interpret overflow as an excuse to throw causality out the window, and that any code which would rely upon any other behavior should be seen as defective, is a bad thing. If a program needs to meet two requirements (1) produce valid output when given valid input; (2) don't launch nukes when given invalid input, a good dialect should allow a both a programmer and the machine running the code...

...to focus most of their efforts on the first requirement. If an audiovisual decoder will receive data from untrusted sources, and if it would be acceptable to output arbitrary waveforms and pixels when given invalid data, code written in such a fashion that no input can trigger any actions not defined by the Standard will be much slower and harder to read than would be code which could exploit behavioral guarantees which the vast majority of compilers used to support (and many still do). Further, if (as is often the case) applications accept input from untrusted sources...

...optimizations that use UB to determine what inputs can or cannot occur will be rendered non-productive by virtue of programmers having had to write out code to define behavior even in cases where old-style UB would otherwise have allowed useful optimizations. If the Standard were to say that unless an implementation defines a macro indicating otherwise, it would be required to uphold some very loose behavioral guarantees regarding overflow, that would allow a lot of code to be simpler and faster than is possible with code that is strictly-compliant under today's Standard.

Seems like you want some operations that right now are UB to produce arbitrary values instead. Seems reasonable. Prevents some optimizations, though, I'm sure. On some platforms UB operations trap. That would be incompatible with the idea of producing a value.

@supercat

@usr: What I would like to see would be a set of macros that would allow code to specify what it requires (a typical implementation could simply check if the requirements were compatible with a what a compiler would do given the current command-line settings). It should be possible to implement a thing in such a fashion that almost any current compiler could be made compliant with that part of the new standard merely by adding a suitable tcsb.h [I'd use the terms...

Testably Constrained Behavior for things that are presently UB like overflow, and Testably Specified Behavior for things that are presently IB, like storing a 1234567 to int16_t, and use tcsb.h for macros related to both].

For some kinds of programming, tightly-trapped overflows are needed. For others, yield-arbitrary-value and even maybe-exit-loops-prematurely are needed. A type of semantics I'd like to see added would be loosely trapped overflow (have a flag like errno, and also allow code to mark a block which the compiler would be free to have exit prematurely in case of overflow [useful on systems with hardware-trapped overflow], with the semantics...

...that if the compiler exits the block for overflow [or other similarly-handled cause] there would be no guarantee as to which statements executed or did not, and further that the compiler need not do anything in response to an overflow that does not cause loss of numeric precision. For example, given long1 = int1+int2; a compiler could signal an overflow if the sum isn't representable as int, and...

...would be required to signal an overflow if long1 didn't receive the arithmetically-correct value of int1+int2, but would be not be required to signal an overflow in cases where the generated code was able to preserve arithmetic correctness. The only useful optimization I can think of that wouldn't be available with a partially-indeterminate-value semantic would be loop index replacement, and that could be allowed if code specified that early loop exit was an acceptable overflow behavior.

I think C could significantly outperform FORTRAN for some applications if it reined in some forms of Undefined Behavior to the point that programs could exploit them, especially if it defined loosely-trapped overflows.

For example, if code needed to compute the sum of many int32_t values or report that if overflowed, having a DSP with a 40-bit accumulator compute subtotals of groups of 128 items and check after each group whether the 40-bit total was within range for an int32_t would be faster than having it check after adding each value. A straightforward optimization under loose semantics, but not under semantics which would require that the loop exit as soon as an overflow occurs.

Code which wanted to meet the specified requirements using the present Standard would need to either compute the total using an int64_t or check for overflow at each step; on many platforms, one or the other of those choices (if not both) would take twice as long as would the optimal code for loose overflow semantics.

Under the present standard performance should be optimal and the DSP optimization that you mention should be possible. No overflow checking at all is needed. This should offer the best possible performance.

Maybe it's a useful idea to split all code into two groups: Either full UB semantics or safe by default semantics.

99% of code is cold and can be safe by default.

In any case UB semantics allow for maximum performance.

If the application requirement says that the function must either report an arithmetically-correct sum, or report that an overflow occurred (with the option of doing either in case an overflow occurred but the sum ended up fitting in the destination type), then it will be necessary to either use an oversized accumulator or check overflows.

Given int dcomp(int x, int y, int z) { return x-y > z; } write an optimal implementation if either a 0 or 1 result would be acceptable in case of overflow.

On some platforms, (int)((unsigned)x-y) > z would be faster than return (long)x-y > z, but on others, the latter would be faster. Allowing x-y > z to yield either as convenient in case of overflow would allow optimal performance in either case. Requiring programmers to pick one will result in sub-optimal performance in cases where the other would have been better. Can you suggest a way to write the expression that would always yield optimal results?

Given a particular piece of source code, allowing total UB may allow a compiler to yield a more "efficient" executable from that source code in cases where no UB occurs, but the most optimizer-friendly source code that meets application requirements under the total UB model may not allow the compiler to yield code as efficient as would be possible given that most optimizer-friendly source code that would meet those same requirements under a tighter UB model.

Maybe this can be better solved by adding an intrinsic library function for adding two numbers that returns a struct { int result; bool isOverflow; }. That returns all information available and the compiler can optimize all kind of usage patterns.

It's probably very hard to craft the language in such a way that you can tell the compiler what kinds of effects you want to allow in case of overflow because it could be all kinds of things.

UB, mangled result, exception and so on

That seems like an unwieldy language feature for little gain.

if there was real demand for that you could always guard a+b by a manual overflow check and make the compiler recognize this pattern

that seems like a good solution as well

I have seen that being done, too

for example memcpy to convert a float to an int. That's a pattern compilers recognize because it's one of the very few standards compliant ways to do it

While C would definitely benefit from adding some compiler intrinsics, I don't think there's any way they could represent the notion that overflows in a computation will only occur in situations where the result of the computation and its side-effects will be irrelevant, but where behavioral guarantees unrelated to the computation must still be met.

I'm not sure what's unwieldy about having code say "I need overflows to behave in somewhat-constrained fashion" and then write programs which focuses on the job at hand, including only enough overflow-handling code to ensure that requirements will be met even when overflow occurs.

With regard to the intrinsic route, unless one defines an intrinsic specifically to compute x-y > z, how would you suggest that a function with the earlier-specified behavioral requirements might be written so as to allow the compiler a choice of overflow behaviors? I suppose if the Standard were to define a standard macro __ARBITRARY_CHOICE(x,y) which would evaluate as either x or y at the compiler's option, the appropriate semantics could be achieved via...

...__ARBITRARY_CHOICE((int)((unsigned)x-y) > z, (long)x-y > z) [compilers without advanced optimizers could define that macro to simply perform the first action, while those with advanced optimizers could define it to use a compiler intrinsic which could select whichever option was better in any given case]. On the other hand...

...simply saying that a compiler must either refuse compilation when encountering predefined macros which would demand the kind of lightly-constrained overflow semantics consistent with those many compilers can already implement and then including such a macro within a module and writing the expression as x-y > z would yield results that were easier to read and could yield optimal results with much less work on the part of the compiler.

Incidently, with regard to memcpy/memmove, I wonder if it would be useful for the Standard to define a compiler intrinsic equivalent to memmove(s,s,n). By my understanding, given #define __update(s,n) memmove((s),(s),n) uint32_t n1=0x12345678,n2; *((uint16*)&n)=0x4321; __update(&n,sizeof n); n2=n; the memmove would avoid UB, but no fancy analysis would be required to allow a compiler to refrain from generating any code for the memmove.

@usr: Forgot to ping you.

how could the source code for the (unsigned)x-y) > z thing look like? what do you propose?

@usr: What do you mean? If the goal is to compute x-y > z so that in case of overflow it assumes the calculation of x-y "wraps around", then (int)((unsigned)x-y) > z should yield that behavior on machines which define (int)(unsigned)(int)x in such fashion as to always equal (int)x.

With regard to how I'd like to be able to write the code, I'd like the Standard to define directives so that I could write within the source file, somewhere before the code in question, something like like __TCSB_REQUIRE(__TCSB_OVERFLOW_INT, __TCSB_PARTIAL_INDETERMINATE_VALUE) or maybe __TCSB_REQUIRE(__TCSB_OVERFLOW_INT, __TCSB_PARTIAL_INDETERMINATE_VALUE | __TCSB_PREMATURE_FOR_LOOP_EXIT) and...

...be assured that if the code compiled, it would yield the required semantics.

__TCSB_OVERFLOW_INT would be a macro which would either yield a 32-bit long constant or a compiler intrinsic that yielded such a constant (possibly based on current compilation options) with bits defining possible things that might occur in case of overflow; an implementation which defines __TCSB_OVERFLOW_INT as -1 could do anything it likes any time overflow would become inevitable.

I meant to say that what I'd like would be able to use one of the above directives and then simply write x-y > z, secure in the knowledge that compiler which didn't refuse to compile the directive would generate code for x-y > z which would, in case of overflow, yield 0 or 1 and not do anything else except possibly (depending upon the directive I chose) cause a for loop to exit prematurely as a consequence of overflow in loop-induction calculations.

As I see it, if the purpose of the code is to compute x-y > z when there's no overflow (five tokens), it doesn't make sense that one should have to write twice as much code to specify overflow behaviors in cases where almost any platform's natural underlying behavior would suffice. C is the only language I know of where the amount of source code necessary to achieve a simple operation in a modern implementation would exceed the amount required in a typical implementation ten years ago.