Wrap on integer overflow is not a good idea

A discussion of undefined behaviour and compiler optimisation, particularly in regards to signed integer overflow.

C (and C++) compilers are becoming notorious for exploiting the notion of undefined behaviour – the idea that certain things a program might do have no behaviour proscribed by the language standard, and that the compiler can assume the program doesn’t do these things when it is generating object code. Quite a few people have been objecting to this, since it can result in the generated code not doing what the programmer intended; the problem is becoming more noticeable over time, as compilers introduce more sophisticated optimisation techniques which are more likely to exploit the notion.

One prominent example is that of signed integer overflow. Most C programmers are developing for machines which use a 2’s complement representation of integers; addition and subtraction, with such a representation, is implemented in exactly the same way as for unsigned arithmetic. If the addition of two positive signed integers overflows – that is, if the result is larger than can be represented – the processor will produce a number that, when interpreted as a 2’s complement signed integer, will appear to be negative. This is called “wrapping” because the value has “wrapped around” from the high end of the numeric range to the low end.

For this reason, you occasionally see C code that looks something like this:

int b = a + 1000;
if (b < a) { // overflow
    puts("input too large!"); return;
}

The “if” statement is designed to detect the overflow condition (in this case from adding 1000 to the value from the variable ‘a’) and report an error. The problem is that, in C, signed integer overflow is one case of undefined behaviour. Compilers, for some time now, have performed an analysis which shows that the condition can never be true: if I add 1000 (or any positive number) to another value, the result cannot be smaller than the original value; if overflow occurred, that is undefined behaviour, and it is the programmer’s responsibility (arguably) to ensure that their program never exhibits such behaviour. Therefore, the compiler may decide that the entire if statement can be removed as an optimisation (it can never be true, it can never have an effect, it may as well not be there).

The problem with this compiler optimisation, in this case, is that it has removed the test that the programmer specifically used in an attempt to detect the overflow situation and handle it. An example of this with a real compiler can be seen here. (Side note: the godbolt.org site on which that example is hosted is great! you can edit the code and see the compiled form with a wide range of compilers. Play with it!). Observe that the overflow check is not removed if the type is changed to an unsigned integer, since unsigned overflow has defined behaviour in C (or rather, more accurately, unsigned arithmetic is defined to wrap and thus the overflow does not actually occur).

So is this wrong? Some have argued that it is, though it’s clear that many compiler vendors feel that it’s legitimate. The main arguments made by proponents of (edit: implementation-defined)wrapping overflow behaviour, if I understand them correctly, boil down to variants of the following:

  • Wrapping on overflow is a useful behaviour.
  • Wrapping is the behaviour expected by programmers.
  • Exploiting undefined behaviour semantics on overflow gives no significant benefit.
  • The C language standard, in regards to undefined behaviour, gives license for implementations “ignoring the situation completely, with unpredictable results”, but this doesn’t allow optimisations to assume that the situation for which the undefined behaviour is proscribed will not come about.

Let’s look at these one by one:

Wrapping on overflow is a useful behaviour?

The main utility for a wrapping behaviour is to be able to detect overflow after it occurs. (If there are other uses, that could not be handled using unsigned integers instead, I am not immediately unable to think of any and suspect they are rare). While this would indeed simplify the problem of avoiding the use of erroneously overflowed results, it certainly doesn’t help in all cases (consider multiplication, or addition of two unknown quantities with unknown sign).

For the trivial case where wrapping behaviour does allow simply detecting overflow after it occurs, it is also straightforward to determine whether overflow would occur, before it actually does so. The example above can be rewritten as follows:

if (a > INT_MAX - 1000) { // would overflow
    puts("input too large!");
    return;
}
int b = a + 1000;

That is, you can perform a check to see whether the result of an addition will exceed the maximum representable value, rather than performing the addition and then trying to determine whether that overflow occurred by checking if the result is mathematically inconsistent. (If the sign of both operands is unknown, the check becomes significantly more complicated, but this is also true when checking for overflow after the operation with wrapping overflow semantics).

With this in mind, I’m not really convinced that wrapping overflow is generally useful.

Wrapping is the behaviour expected by programmers?

It’s more difficult to argue against this point, since clearly at least some C programmers have written code which expects wrapping semantics for signed integer overflow. However, I don’t think that this alone is a strong argument for implementing wrapping semantics by default (note that several compilers implement options for wrapping overflow, if it really is desired).

An obvious mitigation for the problem of programmers expecting this particular behaviour is for the compiler to issue a warning when it optimises based on the alternative undefined-behaviour-is-assumed-not-to-occur semantics. Unfortunately as we see in the godbolt.org link above, compilers don’t always do so (Gcc 7.3 does but 8.1 does not, so this appears to be a regression).

Exploiting undefined behaviour semantics on overflow gives no significant benefit?

If true in all cases this would be a compelling argument for having compilers default to wrap-on-overflow, since it is probably better to allow the “detect overflow after it occurs” mechanism described above to work even if it is technically incorrect – if only because that mechanism may be in use in code which is arguably broken.

I suspect that with typical C programs the benefit of this particular optimisation (removing checks for mathematically impossible conditions) is usually negligible, because C programs tend to be written by programmers who are seeking good performance and who tend to hand-optimise their code anyway: that is, if it’s obvious that particular “if” statement has a condition that can never be true, the programmer would likely have removed the statement themselves. Indeed, a search reveals a few studies where the effectiveness of this optimisation has been questioned, tested, and found to be mostly insignificant for the particular benchmarks under test. However, while in many cases there is no benefit for C, the code generation engines and optimisers in compilers are commonly general and could be used for other languages where the same might not be so generally true; consider C++, where it is somewhat idiomatic in templated code to rely on the optimiser from removing redundant code, rather than doing it manually. There is also the case of languages being transpiled to C and relying on the C compiler to optimise away redundant code.

Also, even without overflow check elimination, it is not necessarily correct to assume that wrapping integers has minimal direct cost even on machines which use 2’s complement representation. The Mips architecture, for example, can perform arithmetic operations only in registers, which are fixed size (32 bit). A “short int” is generally 16 bits and a “char” is 8 bits; if assigned to a register, the underlying width of a variable with one of these types will expand, and forcing it to wrap according to the limit of the declared type would require at least one additional operation and possibly the use of an additional register (to contain an appropriate bitmask). I have to admit that it’s been a while since I’ve had exposure to any Mips code and so I’m a little fuzzy on the precise cost involved, but I’m certain it is non-zero and other RISC architectures may well have similar issues.

The language standard does not allow for signed integer overflow not to wrap, if that’s what the underlying architecture does?

This argument is particularly weak when examined. It essentially states that there is a requirement that “undefined behaviour” actually grants only limited license to the implementation (compiler), by the text of the standard. What the text that proponents latch on to says precisely is the following, as part of the definition of undefined behaviour:

NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, …

The claim is that “ignoring the situation completely” would not allow for assuming that the situation leading to the undefined behaviour – overflowing addition, for example – could not happen, but rather that, if it does happen, the implementation must carry on as if it did not happen but must respect the result it would obtain from asking the processor to perform such an operation (putting it another way: as if the translation from source to machine code was direct and naive).

First, we should observe that this text is in a NOTE and therefore non-normative (may not proscribe behaviour), according to the ISO directive mentioned in the foreword of the same document:

In accordance with Part 3 of the ISO/IEC Directives, this foreword, the introduction, notes, footnotes, and examples are also for information only.

Given that the “possible undefined behaviour” appears in such a note, it is not proscriptive. Note that the actual definition text for “undefined behavior” reads:

behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements.

I have added emphasis on the important part: there are no requirements for undefined behaviour; the list of “possible undefined behaviors” in the note contains merely examples and cannot be definitive. “Imposes no requirements” is unambiguous.

Some extend the argument to say that, regardless of what the text actually says, the intention of the language committee when those words were drafted was that the behaviour should in general match that of the underlying hardware, as closely as possible, assuming a naive translation to machine code. This may be true, though I’ve not seen any evidence (such as historical text) that supports it. Even if it were true, however, it would not necessarily apply to the current incarnation of the text.

Final thoughts

The arguments for wrapping on overflow are mostly flawed. Probably the strongest argument that can be made is a combination: it is occasionally expected by less experienced programmers (who do not understand the nuances of C and of its undefined behaviour), and is not particularly harmful to performance – however, the latter is not true in all cases, and the former is a somewhat dubious reasoning when considered by itself.

Personally, I feel that I would much rather have trap on overflow than wrap. That is, I would rather that a program crash instead of continuing with either undefined behaviour or a potentially incorrect value, either of which could be a security issue. This would certainly have a slight performance impact on most(?) architectures, particularly x86, but on the other hand it would immediately flag overflow bugs rather than allowing them to be exploited or to produce incorrect results further down the line. It could also in theory allow the compiler to safely remove redundant comparisons following a potential overflow, because it ensures that they really can’t happen, though I note that Clang and Gcc both apparently fail to take advantage of this.

Fortunately, both trapping and wrapping options are implemented by the compiler I use most often, which is Gcc. The “-ftrapv” and “-fwrapv” command line arguments can be used to enable each respectively.

There are of course a number of other causes of undefined behaviour; integer overflow is only one. I don’t necessarily think that all of these are useful and I do think that there are plenty of specific cases where the semantics should be defined by the language, or at least classified as implementation-defined. And I’m wary of compiler vendors being too liberal in their interpretation: if the compiler behaves in ways that are counter-intuitive, especially for someone who has read the language specification themselves, there is always the risk of real software bugs resulting; if the opportunities for optimisation that such an interpretation opens up are negligible, it is hardly worthwhile to adopt it. An examination of some issues around this area may be the topic of a future post.

Addendum (24 Aug 2018)

I’ve realised that much of the above could be better written. To briefly summarise, clarify, and add some minor points:

  • I was not trying to argue that undefined behaviour on overflow is preferable to wrapping, but rather that wrapping is not much better than undefined behaviour on overflow in practice. In particular, you can get security issues from wrapping behavior in much the same way as you can with undefined behaviour – and I’d argue that many security issues resulting from unchecked integer overflow, other than those which come from the compiler removing erroneous post-overflow checks, actually come from the fact that the value has wrapped around rather than any other undefined behaviour associated with the overflow.
  • The only real benefit of wrap-on-overflow is that it doesn’t cause post-overflow checks to be removed. While that might eliminate some attack vectors, it leaves open the possibility that some overflows won’t be checked for at all (i.e. the programmer did not include an overflow check) and will be uncaught.
  • If security is not a concern but speed of execution is, undefined behaviour on overflow may allow better optimisation possibilities and provide a performance benefit, at least in some cases. On the other hand if security is a concern, wrap-on-overflow potentially leaves holes open.
  • This means that between trap-on-overflow, wrap-on-overflow, and undefined-behaviour-on-overflow, I see very few cases where wrap-on-overflow should be the preferred choice.
  • In regards to post-overflow checks, I have concerns that leaving them in place could lead to the wrong perception (that post-overflow checks work and are guaranteed to work). Trap-on-overflow avoids this problem. Good warnings help to alleviate it.
  • I think that any programmer writing security-sensitive code will ideally have a good grasp of the semantics of, and the potential pitfalls of, the language they are writing in. For C, this means understanding the overflow semantics and nuances of undefined behaviour. It’s unfortunate that some C programmers still don’t seem to have that level of understanding.
  • I have seen a claim that “most C programmers expect wrapping behaviour”, but I’m not aware of any evidence that this is true. (I’ve said “some” above since I’ve seen anecdotal evidence and I doubt this would be disputed anyway).
  • There are two separate issues: one is what the C language standard should require, and another is what the compilers should implement. I’m (somewhat) ok with the language standard specifying undefined behaviour for overflow. This post is arguing for what the behaviour of compilers should be.
  • Trap-on-overflow need not require that every operation is checked for overflow; ideally it would only mandate that the program either behaves in a mathematically consistent manner or aborts, which allows for “temporary overflow” that doesn’t generate an incorrect result. This would allow optimising “a + b – b” to “a” (which wrapping also does) and “(a * b) / b” to “a” (which wrapping doesn’t).

Addendum (21 Nov 2018)

It turns out that the GCC implementation (circa 8.2) of -ftrapv is terrible – it doesn’t detect all overflow cases, and it causes a large performance degradation due to farming out most arithmetic operations to support functions (i.e. it imposes a function call overhead for a simple addition). The Clang/LLVM implementation is much better.

 

18 thoughts on “Wrap on integer overflow is not a good idea

  1. Isn’t this mostly a straw-man? I haven’t seen anyone arguing for wrapping behavior, but rather wrapping behavior is what we have because that is what the hardware provides. Trapping, or having explicit access to the overflow bit for checking are also fine.

    Anyway, the original C89 standard did not have that bit you quote as a Note, and it didn’t use the language “possible” but “permissible”, which makes the intent very clear.

    See http://blog.metaobject.com/2018/07/a-one-word-change-to-c-standard-to-make.html

    1. Isn’t this mostly a straw-man?

      A straw-man is when you re-phrase or otherwise misrepresent another argument. I’m not sure what the other argument is that you think I’m misrepresenting here. (edit: maybe it can refer more generally to fabricating an argument in order to tear it down; in any case, no. Plenty of people advocate wrap-on-overflow).

      I haven’t seen anyone arguing for wrapping behavior

      Except, err, for the link you posted?

      Another one:
      https://lobste.rs/s/rufxsx/one_word_change_c_standard_make_undefined#c_ffunm2

      There are plenty more if you search.

      Anyway, the original C89 standard did not have that bit you quote as a Note, and it didn’t use the language “possible” but “permissible”, which makes the intent very clear.

      a) It was changed to a note in C99, as a deliberate action. That was nearly 20 years ago. I think that if the language changed 20 years ago, we should probably accept that and move on.
      b) it said “permissible behaviour ranges from – which suggests that the list was never considered exhaustive.
      c) I’m also pretty sure that it also contained the words “imposes no behavior”, so if the intent was to impose limits on the possible behaviour, it’s not what I would call “very clear”. (edit: I’ve since checked, and it does indeed contain that phrase).
      d) in C99 at least (ed: yep also in C89/90) the next possible behaviour in the list is “behaving during translation or program execution in a documented manner characteristic of the environment”. That covers wrapping integer arithmetic, which implies that “ignoring the situation completely” refers to an alternative to that.

      So, no, I think not.

      1. The most common form of “ignoring the situation”, by far, occurs when one or more parts of the Standard define the behavior of some actions, another part says that an overlapping class of actions invokes UB, and in at least some of those cases, an implementation that failed to give priority to the portions defining the behavior might be “conforming”, but would be universally recognized as garbage. In that case, the “situation” exists purely because a portion of the Standard which is intended to make clear that compilers have no blanket obligation to define the behavior of all actions in a particular category is written in such a way that no other part of the Standard can define the behavior of any actions in that category.

        For example, given the definition “struct foo {int x;} s1,s2;”, according to N1570 6.5.2.3p3, the expression “s1.x” is an lvalue of type “int” whose address coincides with that of “s1”. According to N1570 6.5p7, however, an lvalue of type “struct foo” cannot have its stored value accessed using an lvalue of type “int”. Consequently, given “s1=s2; s1.x=5; s2=s1;”, there are two opposite ways a compiler could “ignore the situation”:

        A conforming-but-garbage compiler could infer that since an lvalue of type “int” cannot modify the stored value of an object of type “struct foo”, it may ignore the possibility that the write in question might affect the value of s1. This would in turn allow the compiler to optimize out the write to s2.
        A vastly more common treatment is for compilers to ignore the fact that the N1570 6.5p7 would classify the behavior as UB. Whether or not this is what the authors of the Standard meant by “ignore the situation”, I would hardly classify such behavior as being “characteristic of the environment”.

        Returning to integer math, the action I’d characterize as “ignoring the situation” would be evaluating an expression that would produce an overflow as written, in such a way that the overflow in question doesn’t actually occur. For example, given an expression like “x*4/4;”, a compiler might reasonably optimize that to “x”. Likewise if a compiler can determine that the result of an overflowed computation happens to be ignored [e.g. because a function computes several values, not all of which are used by every caller], it might reasonably optimize out the expression altogether. In such cases, worrying about whether an expression might overflow would be more expensive than simply being agnostic to it. Note, incidentally, that such optimizations would be possible if an implementation had to use precise wrapping semantics, but can be allowed without having to throw laws of time and causality out the window.

      2. I haven’t seen anyone arguing for wrapping behavior

        Except, err, for the link you posted?

        Hmm…that post in no way argues for wrapping behavior.

        What the article argues is that using the undefined-ness of the operation to optimize is wrong, and the standard text makes it pretty clear that, while technically legal, this is wrong. Someone else mentioned Quality of Implementation, I think that’s a good way of putting it. Yes, such an implementation is legally within the bounds of the C standard, but the C standard being what it is, that is not sufficient for having a quality of implementation. In other words: yes you can do this, but then your compiler sucks.

        Anyway, the only place the word “overflow” even occurs is in the following sentence:

        “so if the CPU hardware produces an overflow or underflow on an arithmetic operation, well that’s what you get”

        Again, this in no way argues for wrapping behavior, it just argues that this is what the hardware currently gives us, and the C compiler should just deliver the result the hardware comes up with. If that hardware traps on overflow, you get a trap. If the hardware overflows, you get overflow. If you can set that with a flag, you get the result of whatever the flag says.

        C is very much a language whose behavior depends on the hardware it runs, on, rather than language whose behavior is defined by a specified/standardized abstract machine that then gets mapped onto hardware. See the fact that the size of the various integers is dependent on the hardware.

        1. What the article argues is that using the undefined-ness of the operation to optimize is wrong, and the standard text makes it pretty clear that, while technically legal, this is wrong.

          Where does it (the standard) do that?

          Hmm…that post in no way argues for wrapping behavior.
          Anyway, the only place the word “overflow” even occurs is in the following sentence:
          “so if the CPU hardware produces an overflow or underflow on an arithmetic operation, well that’s what you get”

          So it’s arguing for wrapping on processors which have that behaviour on arithmetic operations, i.e. the vast majority of desktop processors. How can you say that this “in no way argues for wrapping behaviour”? Seems like you’re trying to play word games here. This post specifically talks about wrapping on such processors, not on others.

          1. The C Standard describes one clearly-useful thing that implementations may do in cases where the Standard imposes no requirements (behaving in a documented fashion characteristic of the implementation is an easy way of exposing implementation-specific behaviors), but the Standard itself gives no indication of how implementations should choose to do that. The published Rationale, however, makes clear that such decisions are left as a Quality of Implementation issue:

            “The terms unspecified behavior, undefined behavior, and implementation-defined behavior are
            used to categorize the result of writing programs whose properties the Standard does not, or
            25 cannot, completely describe. The goal of adopting this categorization is to allow a certain
            variety among implementations which permits quality of implementation to be an active force in
            the marketplace as well as to allow certain popular extensions, without removing the cachet of
            conformance to the Standard.”

            Programs in different application fields have different needs, and a C implementation which would be excellent for some fields may be mediocre or even completely useless in others. Quoting again from the C Rationale:

            “C code can be non-portable. Although it strove to give programmers the opportunity to write
            truly portable programs, the C89 Committee did not want to force programmers into writing
            portably, to preclude the use of C as a ‘high-level assembler’: the ability to write machine-
            specific code is one of the strengths of C. It is this principle which largely motivates drawing the
            distinction between strictly conforming program and conforming program ”

            Someone seeking to design a high-quality compiler–or a high-quality anything for that matter–should make an effort to identify and satisfy the customer’s needs and–to the extent practical–desires. One of the things users of “general-purpose” compilers often want to do is run a variety of non-portable programs, many of which were originally written for use with other similar implementations. A quality general-purpose compiler should attempt to efficiently process such programs without regard for whether the Standard would require it to do so.

            A major weakness of the Standard (and one which actually makes use of the term “Standard” somewhat questionable) is that it fails one of the fundamental goal of a programming standard: define a category of programs PP and implementations II such that, for any program P in set PP, and every implementation I in set II, it says something useful about the effect of feeding program I to implementation I. It would be impractical for a Standard to define those sets so that every such combination would be guaranteed to behave usefully. What a Standard could do, however, is specify a category of Safely Conforming implementations and Selectively Conforming programs such that:

            (1) A Safely Conforming Implementation must document a set of environmental requirements and means by which it might indicate a refusal to process or continue processing a program; when fed a Selectively Conforming program, it must process it as described by the Standard unless or until it indicates a refusal to do so via Implementation-Defined means, without any other behaviors. An intrinsic __STATICALLY_SAFE should yield 1 (Quality of Implementation issue) if a compiler can guarantee that it will not refuse to process the contents thereof unless the program invokes UB, and must return 0 otherwise (a conforming, but low-quality implementation, could simply define the intrinsic to always yield zero).

            (2) A Selectively Conforming program may exploit the behavior of actions which are not universally supported, provided that it includes directives indicating that it does so. A Safely Conforming implementation would then be required to–at its leisure (QoI issue)–either process the program while treating those actions as having the indicated behaviors or refuse to process the program.

            For many forms of UB, it should then be possible to define directives which indicate how much or how little freedom a compiler may exercise when processing them. While it would not be practical to require that all implementations support all the features and guarantees necessary to meet the needs of all programs (or even 50% of them), it should be practical to define optional features and guarantees sufficient to allow 90%+ of tasks to be accomplished without UB [note that the behavior a volatile value to an address that doesn’t represent any object known to the compiler would typically simply be “issue a volatile store to the environment, and have the code generator refrain from reordering access to [some category] objects across it.”; whether that happens to make the hardware do anything useful would be the programmer’s responsibility.

          2. the standard text makes it pretty clear that, while technically legal, this is wrong.

            Where does it (the standard) do that?

            Not sure why this is even a question. The standard describes a range (not a set!) of “permissible” (C89) behaviors.

            I don’t see how you can argue that “silently assume UB can’t occur and optimize based on that assumption” falls within the range of behavior bounded by the examples given. Given that, the behavior in question is not in the range of “permissible” behaviors. Not being permissible to me sounds like “wrong”, not sure what else it would be. Certainly not “right”. Though being wrong/outside the permissible range does not make the compiler non-compliant at this point, that’s the wonderful world of the C standard for you.

            [Arguing for wrapping]

            Hmm…if I understand you correctly, you seem to be saying that because CPUs currently do wrapping, arguing for just using the CPU behavior is effectively arguing for wrapping, because that is the outcome. Is that correct?

            Not sure how to disentangle that, because it seems such a basic/fundamental thing. Two things are not the same, even if they have the same effect.

            Arguing for following electoral laws does not mean arguing for a Trump presidency, even if following the electoral laws leads to a Trump presidency. What it means is that not following electoral law is not the right way to not have a Trump presidency. The right way is to follow the law and have enough votes in the right places to not get a Trump presidency.

            Arguing for the C compiler to let the hardware decide is not arguing for the current behavior of the hardware, it is arguing that the C compiler is the wrong place to decide this. If you want other behavior, you can build your own abstractions on top of C, not use C at all, have different hardware etc.

            My own preference is a real numeric tower with unlimited precision integers, like Smalltalk for example. Hardware support for that would be nice.

            1. The standard describes a range (not a set!) of “permissible” (C89) behaviors.

              That’s a 30-year old standard you’re talking about. It hasn’t said “permissible” for almost 20 years. It’s not clear what is meant by a “range” of behaviour, and how you could decide if a certain behaviour was outside that range. It’s also not clear that “ignoring the situation completely” actually means and whether the current compiler behaviour does or does not qualify as exactly that.

              Hmm…if I understand you correctly, you seem to be saying that because CPUs currently do wrapping, arguing for just using the CPU behavior is effectively arguing for wrapping, because that is the outcome. Is that correct?

              Indeed.

              Arguing for following electoral laws does not mean arguing for a Trump presidency, even if following the electoral laws leads to a Trump presidency.

              That’s not an equivalent example, and is true due to an equivocation that’s not present in the argument regarding CPU behaviour / wrapping.

              Since this is now getting ridiculous, please stop posting here.

        2. The phrase “quality of implementation” is not my invention, but appears repeatedly within the Rationale for the C Standard. It’s too bad that people opposing gcc’s abuse of the Standard haven’t quoted the rationale from the get-go, since it thoroughly exposes the bankruptcy of hyper-modern “optimization” philosophy.

  2. According to the C89 Rationale, support for features beyond those required by the Standard is a Quality of Implementation Issue; nothing in later standards suggests an intention to change that. Given that the Rationale recognizes that an implementation can be conforming while being of such poor quality as to be useless, the authors clearly expected quality implementations to do more than is required by the Standard. A quality implementation intended to be suitable for various tasks should support behaviors which are useful for those tasks, whether or not the Standard requires it to do so.

    Although relatively few tasks would be facilitated by a guarantee that integer computations will yield consistent wrapping semantics, many would benefit from a number of weaker guarantees that would be implied or facilitated by that. Among them:

    If an additive, multiplicative, left-shift, or bitwise operation is performed using a signed integer type and the result is converted to the corresponding unsigned type, behavior will be equivalent to that of having performed the operation on the unsigned type. Given the rationale for making short unsigned types promote to signed int, the authors of the Standard seem to have taken this for granted.
    Integer operators other than division and remainder will never have side-effects beyond the evaluation of their operands (quality implementations should extend the same guarantee to shifts).
    An expression of integer type will always yield a value in the range type_MIN..type_MAX.
    After an object of integer type is written with a value of that type, repeated reads without intervening modification will yield that same value.

    Many tasks can be facilitated by the first, second, and fourth guarantees. Far fewer of them particularly benefit from the third. On the flip side, waiving the third guarantee would be sufficient to allow most useful overflow-related optimizations.

    That would suggest that quality general-purpose implementations should attempt to support the guarantees which are useful and cheap, even if they don’t support the one which is more expensive and less useful.

    On a related note, tasks that would require reliable diagnostics in cases where calculations would produce incorrect results would benefit from a category of implementation that can reliably detect integer overflow in such cases and report via some intrinsic whether it has occurred. If the semantics of the intrinsic were such that overflows which do not prevent a program from computing arithmetically-correct results may be reported or not at the compiler’s leisure, such freedom would often allow a compiler to generate overflow-detection code that is more efficient what a programmer could write (for example, given “int a=b+c+d+e+f;”, a compiler could promote all values to “int64_t”, add them, and check whether the result fits in an “int” in cases where that would be faster than testing for overflow on each partial sum).

    Trapping and detecting overflows precisely when they occur is expensive, whether done in user code or by a compiler. Among other things, it severely limits a compiler to use vectorization or other forms of out-of-order execution to improve performance. Having a standard means by which a program could determine whether an overflow occurred within a section of code without requiring that a loop stop precisely at the point of overflow would be far more valuable than finding more “optimizations” that require programmers to add precise overflow-trapping code even in cases where guarantees #1, #2, and #4 above would render it unnecessary.

    1. Many tasks can be facilitated by the first, second, and fourth guarantees. Far fewer of them particularly benefit from the third. On the flip side, waiving the third guarantee would be sufficient to allow most useful overflow-related optimizations.

      I’m not sure. The fourth guarantee would certainly prevent the “erroneous post-overflow check” described in the post from being optimised away. (I guess the question then is whether that is indeed a useful optimisation).

      That would suggest that quality general-purpose implementations should attempt to support the guarantees which are useful and cheap, even if they don’t support the one which is more expensive and less useful.

      I think I agree with that, principally.

      for example, given “int a=b+c+d+e+f;”, a compiler could promote all values to “int64_t”, add them, and check whether the result fits in an “int” in cases where that would be faster than testing for overflow on each partial sum

      Yes, I agree that this would be better than forcing a trap-check on each and every operation that might overflow, though perhaps there should be some syntactic marker to force a trap-check at particular points.

      Trapping and detecting overflows precisely when they occur is expensive, whether done in user code or by a compiler

      That’s true with current architecture. There’s always a trade-off, performance vs safety, I think. It’s important that compilers support multiple options and that the standard gives them the flexibility to do so.

      Having a standard means by which a program could determine whether an overflow occurred within a section of code without requiring that a loop stop precisely at the point of overflow would be far more valuable

      Yes, in combination with suitable restrictions of the effect of overflow, I agree that would be useful. For most of the day-to-day software on servers and PCs, I would still prefer trap-on-overflow as a default.

  3. Given the just the first, second, and fourth rules, a compiler could omit the comparison in some cases where it could see everything that would be done with the object being compared and know that it would consistently behave as positive number. Such behavior may be entirely reasonable. For example, given “int x=ushort1*40000; if (x<0) { …}; x/=40000; …” it would be faster–even in the absence of the comparison–for a compiler to generate code that behaves as though it performs the calculation correctly (yielding a positive result) than for it to do anything else.

    I don’t think there’s any practical way to design an architecture where precise overflow traps aren’t expensive. Efficient computation often requires the ability to run groups of operations in parallel, and that won’t be possible in cases where an overflow in an earlier operation would be required to prevent any attempt to perform a later one. If C added a means of loose overflow checking, quality implementations could for many purposes outperform existing languages that lack such a feature.

    For many purposes, loose overflow detection semantics would be superior to wraparound semantics. I would regard “behave unpredictably” semantics, however, as being worse than wraparound semantics in almost every way.

    1. Sad if true. That’s a pretty old bug though, and most of the bugs linked into it are marked as fixed. Is it still an issue? (Incidentally, clang also supports -ftrapv). It appears the bug you link to doesn’t actually claim that anything isn’t working, just that the implementation of -ftrapv in gcc requires some internal functionality that they are/were considering removing.

      1. To decide whether an implementation that’s supposed to trap on overflow works “correctly”, one must determine what behavior is expected in various corner cases. For example, if it would be faster to perform a calculation as though integers had infinite precision than to handle overflow, should that be considered acceptable behavior? If code never uses the result of an operation, should the implementation be required to check whether it would overflow? Unless the authors of gcc have documented the answers to such questions (so far as I know they haven’t) it would seem unlikely that all parts of the compiler would behave consistently.

        It’s not hard to imagine situations where this could be completely disastrous. For example, if a function like “int foo(int x, int y) { int z=x*y; return (x > 60000 && y > 60000);}”, is invoked with x and y both greater than 60000, it may be reasonable for the function to trap, or for it to return 1, but it should not return zero. It’s not hard to imagine that one part of the optimizer might omit the multiplication and overflow check (since the function is never required to overflow), and another part might omit the comparisons against 60000 (since the function is never required to return 1). Unless each part of the optimizer can know what the other parts will and won’t do, it will be hard for them to ensure that required cases get handled exactly once.

  4. Hello. Unfortunately, I haven’t found a way how to write you directly. I liked your article and I’m going to translate it in Russian for posting on a Russian site for developers Habr.com. Also I’d like to post a translation and original text on our site viva64.com. I ask for your permission to do it. I’ll give a link to the source material. Please, write me back to my email: [redacted]

    Best regards,
    Andrey Karpov, Microsoft MVP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.