* Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? @ 2005-06-30 19:15 Paul Schlie 2005-06-30 20:08 ` Paul Schlie 2005-06-30 22:06 ` Joe Buck 0 siblings, 2 replies; 27+ messages in thread From: Paul Schlie @ 2005-06-30 19:15 UTC (permalink / raw) To: gcc Given that the formal implication of GCC's choice not define signed integer overflow semantics as being other than undefined will be to guaranteed that all programs, with reachable signed integer arithmetic operations which can not warrant that their respective operand expressions are recursively constrained to each others corresponding additive, multiplicative inverse, may produce unpredictably arbitrary results and/or behavior by default; might it be a good idea to publish a formal rule/warning, as it's a good thing to know and not particularly obvious: - Signed integer types and/or arithmetic operations should not be utilized in GCC compiled programs (or any program desired to be strictly portable, even if it's values are known or desired to be constrained to signed integers) unless it is provably known that the corresponding operands to all signed arithmetic operation which may use their values directly and/or indirectly are correspondingly recursively constrained to their respective additive or multiplicative inverse. As GCC complied programs may produce arbitrary results and/or behavior in such instances by default, as enabled by the C/C++ standards. Or more generally as C/C++'s default integer promotion rules may convert unsigned integer types to signed operand types if it's other operand is signed, should the general rule be broadened to discourage the use of all integer variable types unless all signed integer operations which may utilize their values directly or indirectly are provably known to have their correspondingly operands constrained to their respective additive or multiplicative inverse value ranges? (or if by default it warrants otherwise, maybe that should be stated?) ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-06-30 19:15 Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? Paul Schlie @ 2005-06-30 20:08 ` Paul Schlie 2005-06-30 22:06 ` Joe Buck 1 sibling, 0 replies; 27+ messages in thread From: Paul Schlie @ 2005-06-30 20:08 UTC (permalink / raw) To: gcc (sorry, meant additive/multiplicative inverse +/- MAX/MIN_<TYPE> value; but even that's wrong, which is why it seems that leaving signed overflow as being undefined is such a bad idea, as it becomes correspondingly very difficult to even try determine if a program is warranted to have a deterministic behavior, or potentially a completely arbitrary one.) > Given that the formal implication of GCC's choice not define signed integer > overflow semantics as being other than undefined will be to guaranteed that > all programs, with reachable signed integer arithmetic operations which can > not warrant that their respective operand expressions are recursively > constrained to each others corresponding additive or multiplicative inverse, > may produce unpredictably arbitrary results and/or behavior by default; might > it be a good idea to publish a formal rule/warning, as it's a good thing to > know and not particularly obvious: > > - Signed integer types and/or arithmetic operations should not be utilized > in GCC compiled programs (or any program desired to be strictly portable, > even if it's values are known or desired to be constrained to signed > integers) unless it is provably known that the corresponding operands to > all signed arithmetic operation which may use their values directly and/or > indirectly are correspondingly recursively constrained to their respective > additive or multiplicative inverse. As GCC complied programs may produce > arbitrary results and/or behavior in such instances by default, as enabled > by the C/C++ standards. > > Or more generally as C/C++'s default integer promotion rules may convert > unsigned integer types to signed operand types if it's other operand is > signed, should the general rule be broadened to discourage the use of all > integer variable types unless all signed integer operations which may utilize > their values directly or indirectly are provably known to have > their correspondingly operands constrained to their respective additive or > multiplicative inverse value ranges? > > (or if by default it warrants otherwise, maybe that should be stated?) ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-06-30 19:15 Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? Paul Schlie 2005-06-30 20:08 ` Paul Schlie @ 2005-06-30 22:06 ` Joe Buck 2005-06-30 22:26 ` Gabriel Dos Reis 1 sibling, 1 reply; 27+ messages in thread From: Joe Buck @ 2005-06-30 22:06 UTC (permalink / raw) To: Paul Schlie; +Cc: gcc On Thu, Jun 30, 2005 at 03:14:54PM -0400, Paul Schlie wrote: > Given that the formal implication of GCC's choice not define signed integer > overflow semantics as being other than undefined will be to guaranteed that > all programs, with reachable signed integer arithmetic operations which can > not warrant that their respective operand expressions are recursively > constrained to each others corresponding additive, multiplicative inverse, > may produce unpredictably arbitrary results and/or behavior by default; > might it be a good idea to publish a formal rule/warning, as it's a good > thing to know and not particularly obvious: The formal rule is called the ISO C standard. It's the only one you're going to get. > - Signed integer types and/or arithmetic operations should not be utilized > in GCC compiled programs (or any program desired to be strictly portable, > even if it's values are known or desired to be constrained to signed > integers) unless it is provably known that the corresponding operands to > all signed arithmetic operation which may use their values directly and/or > indirectly are correspondingly recursively constrained to their respective > additive or multiplicative inverse. As GCC complied programs may produce > arbitrary results and/or behavior in such instances by default, as enabled > by the C/C++ standards. Your alleged required condition is way too strict, to the point of being offensive, and you are falsely implying that GCC is aggressively doing what other compilers do not. The writer of a C program (or C++) needs to ensure that integer overflow does not occur when using signed types. If she fails to do this, we can't make any promise about the results, though in some cases the program might do what the user expects. Any promise we did make would inevitably harm the code quality for those who do write correct C programs, by preventing many common loops from being optimized. However, because we don't generate traps, in many cases programs that have overflows produce correct results anyway. It's just that we cannot promise that this will always be so. If the user does need the mathematical properties of arithmetic modulo 2**32 (8 or 16 or 64), he can readily obtain this by using unsigned types. The only correct way to write a bignum package in C, for example, is to use an unsigned type to store each word. Given your biases, you might be happier with Java as a language (than C or C++). The Java language designers decided to strictly define many cases that are not defined in C (example: the order side effects is always strictly left to right, floating point is always IEEE, etc., integer overflow wraps around). There is a performance penalty for this, but given the "write once, run everywhere" goal it was felt that it's worth paying this price. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-06-30 22:06 ` Joe Buck @ 2005-06-30 22:26 ` Gabriel Dos Reis 2005-06-30 23:25 ` Joe Buck 0 siblings, 1 reply; 27+ messages in thread From: Gabriel Dos Reis @ 2005-06-30 22:26 UTC (permalink / raw) To: Joe Buck; +Cc: Paul Schlie, gcc Joe Buck <Joe.Buck@synopsys.COM> writes: [...] | Given your biases, you might be happier with Java as a language (than C or | C++). The Java language designers decided to strictly define many cases | that are not defined in C (example: the order side effects is always | strictly left to right, floating point is always IEEE, etc., integer | overflow wraps around). There is a performance penalty for this, but | given the "write once, run everywhere" goal it was felt that it's worth | paying this price. Well, in the case of C++ I can say that the designer and original implementor of C++ is quite amazed as to how people interpret "undefined behaviour" in this thread. I don't think he would suggest that people go to use Java instead. -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-06-30 22:26 ` Gabriel Dos Reis @ 2005-06-30 23:25 ` Joe Buck 2005-07-01 0:49 ` Gabriel Dos Reis ` (2 more replies) 0 siblings, 3 replies; 27+ messages in thread From: Joe Buck @ 2005-06-30 23:25 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Paul Schlie, gcc On Fri, Jul 01, 2005 at 12:25:58AM +0200, Gabriel Dos Reis wrote: > Joe Buck <Joe.Buck@synopsys.COM> writes: > > [...] > > | Given your biases, you might be happier with Java as a language (than C or > | C++). The Java language designers decided to strictly define many cases > | that are not defined in C (example: the order side effects is always > | strictly left to right, floating point is always IEEE, etc., integer > | overflow wraps around). There is a performance penalty for this, but > | given the "write once, run everywhere" goal it was felt that it's worth > | paying this price. > > Well, in the case of C++ I can say that the designer and original > implementor of C++ is quite amazed as to how people interpret > "undefined behaviour" in this thread. Really? You've talked to Stroustrup? Can you be more specific? (If you're talking about the regularly repeated claim that "undefined behavior" means the compiler can delete all your files, hack your bank account, and send all your money to the GCC team, well, that's just hyperbole not to be taken seriously). > I don't think he would suggest > that people go to use Java instead. Are you claiming that Stroustrup would want to sacrifice loop optimization to make Paul happy? Undefined behavior doesn't mean that we should attempt to arbitrarily punish those who cross the line; that's why I don't think forcing integer overflows to trap (at least by default) is a good idea. In many cases, "assume no overflow, but don't trap" can produce a better result than "assume wrap" does, as in the example I gave before. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-06-30 23:25 ` Joe Buck @ 2005-07-01 0:49 ` Gabriel Dos Reis 2005-07-01 1:03 ` Andrew Pinski 2005-07-02 16:45 ` Robert Dewar 2005-07-01 1:04 ` Paul Schlie 2005-07-01 1:35 ` Paul Schlie 2 siblings, 2 replies; 27+ messages in thread From: Gabriel Dos Reis @ 2005-07-01 0:49 UTC (permalink / raw) To: Joe Buck; +Cc: Paul Schlie, gcc Joe Buck <Joe.Buck@synopsys.COM> writes: | On Fri, Jul 01, 2005 at 12:25:58AM +0200, Gabriel Dos Reis wrote: | > Joe Buck <Joe.Buck@synopsys.COM> writes: | > | > [...] | > | > | Given your biases, you might be happier with Java as a language (than C or | > | C++). The Java language designers decided to strictly define many cases | > | that are not defined in C (example: the order side effects is always | > | strictly left to right, floating point is always IEEE, etc., integer | > | overflow wraps around). There is a performance penalty for this, but | > | given the "write once, run everywhere" goal it was felt that it's worth | > | paying this price. | > | > Well, in the case of C++ I can say that the designer and original | > implementor of C++ is quite amazed as to how people interpret | > "undefined behaviour" in this thread. | | Really? You've talked to Stroustrup? I work with him on daily basis, and as a matter of fact we've discussed the heart of this topic of this thread yesterday over lunch. But, as much as I hate argument by authority I could not let this discussion goes on the slope it is taking without saying what I understood from discussion with him on the topic. It wasn't meant as a proof. Just a data point. Of course, it is far preferable he speaks for himself but it is hard to have him take part of a debate where extreme abstract arguments are more dominant than balance between two apparant conflicting goals. And that is, I guess, a wise thing to do just as core developers like RTH may have a say on this very issue :-) | Can you be more specific? yes, see below. | (If you're talking about the regularly repeated claim that "undefined | behavior" means the compiler can delete all your files, hack your bank | account, and send all your money to the GCC team, well, that's just | hyperbole not to be taken seriously). as you may correctly guess he is familiar with those rethorical figures. | > I don't think he would suggest | > that people go to use Java instead. | | Are you claiming that Stroustrup would want to sacrifice loop optimization | to make Paul happy? No, I'm not claiming that. But, on the other hand he does not believe engineering decisions for useful compilers should be primarily based on SPEC numbers for example, or primarily driven by the best optimizations without some considerations on the impacts and "practices" and expectations. And he is not claiming it is easy :-) What I'm claiming is that he thinks "undefined behaviour" in the standard should not be taken as meaning "go to hell" (or punishment to borrow words from you) or absolute liberty for compiler writers to do just about everything that is imaginable, regardless of expectations. In other words, it is a question of balance. As, an example, he illustrated the issue with the story -- quickly classified as "legend" by Robert Dewar -- about the best C optimizing compilers that miscompiled the Unix kernel that nobody wanted to use in practice (even if it would blow up any other competing compiler) and the company running out of business. (Interestingly, it was also predictated that Robert would react ;-)) | Undefined behavior doesn't mean that we should attempt to arbitrarily | punish those who cross the line; that's why I don't think forcing integer | overflows to trap (at least by default) is a good idea. In many cases, | "assume no overflow, but don't trap" can produce a better result than | "assume wrap" does, as in the example I gave before. Yes, I understand. I just don't think the answer would be to tell Paul to go to Java, even though that would have the side effect of closing the already long discussion :-) Correctness and efficiency is important to us. GCC is of great interest to us too. -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 0:49 ` Gabriel Dos Reis @ 2005-07-01 1:03 ` Andrew Pinski 2005-07-01 1:23 ` Gabriel Dos Reis ` (2 more replies) 2005-07-02 16:45 ` Robert Dewar 1 sibling, 3 replies; 27+ messages in thread From: Andrew Pinski @ 2005-07-01 1:03 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: 'gcc mailing list' On Jun 30, 2005, at 8:48 PM, Gabriel Dos Reis wrote: > | Really? You've talked to Stroustrup? > > I work with him on daily basis, and as a matter of fact we've discussed > the heart of this topic of this thread yesterday over lunch. But, as > much as I hate argument by authority I could not let this discussion > goes on the slope it is taking without saying what I understood from > discussion with him on the topic. It wasn't meant as a proof. Just a > data point. Of course, it is far preferable he speaks for himself but > it is hard to have him take part of a debate where extreme abstract > arguments are more dominant than balance between two apparant > conflicting goals. And that is, I guess, a wise thing to do just as > core developers like RTH may have a say on this very issue :-) But the reason question is why make it an undefined behavior instead of an implementation defined? This would have made it clearer instead of allowing the compiler not document what happens. Or is C++ just following C here? In which case it might be better to ask the C committee why it was done this way and real definition of undefined for this case? -- Pinski ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 1:03 ` Andrew Pinski @ 2005-07-01 1:23 ` Gabriel Dos Reis 2005-07-01 1:25 ` Joe Buck 2005-07-02 16:47 ` Robert Dewar 2 siblings, 0 replies; 27+ messages in thread From: Gabriel Dos Reis @ 2005-07-01 1:23 UTC (permalink / raw) To: Andrew Pinski; +Cc: 'gcc mailing list' Andrew Pinski <pinskia@physics.uc.edu> writes: | On Jun 30, 2005, at 8:48 PM, Gabriel Dos Reis wrote: | | > | Really? You've talked to Stroustrup? | > | > I work with him on daily basis, and as a matter of fact we've discussed | > the heart of this topic of this thread yesterday over lunch. But, as | > much as I hate argument by authority I could not let this discussion | > goes on the slope it is taking without saying what I understood from | > discussion with him on the topic. It wasn't meant as a proof. Just a | > data point. Of course, it is far preferable he speaks for himself but | > it is hard to have him take part of a debate where extreme abstract | > arguments are more dominant than balance between two apparant | > conflicting goals. And that is, I guess, a wise thing to do just as | > core developers like RTH may have a say on this very issue :-) | | But the reason question is why make it an undefined behavior instead of | an implementation defined? I cannot tell you exactly why it was made undefined behaviour. But, I can tell you from experience working in the C++ committee that there may be various reasons why something is left undefined (including oversight), not just because the committee thought it would be fun. In this specific case, I think (but I'm not 100% sure) it is a carry over from C90 (like many other "curious" cases). -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 1:03 ` Andrew Pinski 2005-07-01 1:23 ` Gabriel Dos Reis @ 2005-07-01 1:25 ` Joe Buck 2005-07-01 1:40 ` Gabriel Dos Reis 2005-07-02 16:47 ` Robert Dewar 2 siblings, 1 reply; 27+ messages in thread From: Joe Buck @ 2005-07-01 1:25 UTC (permalink / raw) To: Andrew Pinski; +Cc: Gabriel Dos Reis, 'gcc mailing list' On Thu, Jun 30, 2005 at 09:02:48PM -0400, Andrew Pinski wrote: > But the reason question is why make it an undefined behavior instead of > an implementation defined? This would have made it clearer instead of > allowing the compiler not document what happens. Or is C++ > just following C here? In which case it might be better to ask the C > committee why it was done this way and real definition of undefined for > this case? I already showed you the answer: loop optimization works better if you can ignore overflow. How much do you want to pay for "implementation defined"? If you specify the behavior of overflow precisely, then every optimizer in GCC must preserve this behavior. That has a high cost. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 1:25 ` Joe Buck @ 2005-07-01 1:40 ` Gabriel Dos Reis 2005-07-01 3:16 ` Daniel Berlin 0 siblings, 1 reply; 27+ messages in thread From: Gabriel Dos Reis @ 2005-07-01 1:40 UTC (permalink / raw) To: Joe Buck; +Cc: Andrew Pinski, 'gcc mailing list' Joe Buck <Joe.Buck@synopsys.COM> writes: | On Thu, Jun 30, 2005 at 09:02:48PM -0400, Andrew Pinski wrote: | > But the reason question is why make it an undefined behavior instead of | > an implementation defined? This would have made it clearer instead of | > allowing the compiler not document what happens. Or is C++ | > just following C here? In which case it might be better to ask the C | > committee why it was done this way and real definition of undefined for | > this case? | | I already showed you the answer: loop optimization works better if you | can ignore overflow. There are various ways to work within "loop optimization" assumptions. Assuming undefined behaviour is not the only one. In fact, given the fact that the natural integer type for indices is "int" and not "unsigned" and the known dislike of the original implementer of C++ for "unsigned", it is legitimate to question whether that is "the answer". I think that can be an "a posteriori" justification, but I'm not sure that is "the answer". -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 1:40 ` Gabriel Dos Reis @ 2005-07-01 3:16 ` Daniel Berlin 2005-07-01 4:07 ` Gabriel Dos Reis 0 siblings, 1 reply; 27+ messages in thread From: Daniel Berlin @ 2005-07-01 3:16 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Joe Buck, Andrew Pinski, 'gcc mailing list' On Fri, 2005-07-01 at 03:39 +0200, Gabriel Dos Reis wrote: > Joe Buck <Joe.Buck@synopsys.COM> writes: > > | On Thu, Jun 30, 2005 at 09:02:48PM -0400, Andrew Pinski wrote: > | > But the reason question is why make it an undefined behavior instead of > | > an implementation defined? This would have made it clearer instead of > | > allowing the compiler not document what happens. Or is C++ > | > just following C here? In which case it might be better to ask the C > | > committee why it was done this way and real definition of undefined for > | > this case? > | > | I already showed you the answer: loop optimization works better if you > | can ignore overflow. > > There are various ways to work within "loop optimization" assumptions. Gaby, if you have plans to do what nobody else has had any real luck doing for 10 years in compilers in any practical way, which is proving the iteration count of loops in the presence of overflow, please share. It's possible, but all methods i'm aware that even attempt it are incredibly expensive (exponential) in every case. This isn't about SPEC numbers, it's about every single piece of Numerical C, Fortran, and C++ i've ever seen. --Dan ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 3:16 ` Daniel Berlin @ 2005-07-01 4:07 ` Gabriel Dos Reis 2005-07-01 4:15 ` Andrew Pinski 2005-07-02 16:51 ` Robert Dewar 0 siblings, 2 replies; 27+ messages in thread From: Gabriel Dos Reis @ 2005-07-01 4:07 UTC (permalink / raw) To: Daniel Berlin; +Cc: Joe Buck, Andrew Pinski, 'gcc mailing list' Daniel Berlin <dberlin@dberlin.org> writes: | On Fri, 2005-07-01 at 03:39 +0200, Gabriel Dos Reis wrote: | > Joe Buck <Joe.Buck@synopsys.COM> writes: | > | > | On Thu, Jun 30, 2005 at 09:02:48PM -0400, Andrew Pinski wrote: | > | > But the reason question is why make it an undefined behavior instead of | > | > an implementation defined? This would have made it clearer instead of | > | > allowing the compiler not document what happens. Or is C++ | > | > just following C here? In which case it might be better to ask the C | > | > committee why it was done this way and real definition of undefined for | > | > this case? | > | | > | I already showed you the answer: loop optimization works better if you | > | can ignore overflow. | > | > There are various ways to work within "loop optimization" assumptions. | | Gaby, if you have plans to do what nobody else has had any real luck | doing for 10 years in compilers in any practical way, which is proving | the iteration count of loops in the presence of overflow, please share. As we have briefly discussed in mails, the most critical part of the issue seems to be what can be assumed for loop variables. I countend that for many if not most practical loops, the variable can be assumed not to overflow and apply the transformation. But we need not apply "undefined behaviour" to all other cases; only for those "well-written" loop and loop variables. In summary, if user's loop is well-written then he will benefit from the transformation. That will cover already a good set of common loops. There are of course coner and pathological cases, but I don't think we should worry too much about missing them. Let's first cover the structured loops, and address the contorsed ones later if they become really important. This is why I suggested earlier whether you'd be happy with letting user specify through a switch that his loops behave well. Some counter-examples were produced, but after some thoughts I think that if user specifies through switch that his loops behave well but write such deceiving codes then, well, he looses. -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 4:07 ` Gabriel Dos Reis @ 2005-07-01 4:15 ` Andrew Pinski 2005-07-01 4:58 ` Gabriel Dos Reis 2005-07-02 16:51 ` Robert Dewar 1 sibling, 1 reply; 27+ messages in thread From: Andrew Pinski @ 2005-07-01 4:15 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Daniel Berlin, Joe Buck, 'gcc mailing list' On Jul 1, 2005, at 12:06 AM, Gabriel Dos Reis wrote: > > There are of course coner and pathological cases, but I don't think we > should worry too much about missing them. Let's first cover the > structured loops, and address the contorsed ones later if they become > really important. And I just submitted a patch for one of those corner/pathological cases and it actually does improve code, how much I don't know because I don't have access to any benchmark to test on. If someone wants to test it, they will most likely find it, it does in fact improve code. Also knowing in let say fold if the variable is a loop index or not is actually not trivial. Another testcase where we will fail out at if we take the view you want to take is: int f(int i) { return (i - 1) > i; } Which is always false if overflow is undefined and not considered wrapping and this shows up in fortran code even though the person did not write it out explicitly: SUBROUTINE d ( a, b,n) IMPLICIT NONE INTEGER :: n REAL,DIMENSION(n) :: a REAL,DIMENSION(n) :: b b(n-2:n) = sqrt(a(n-2:n)) END SUBROUTINE d And this is now done in two different places, fold and simplify-rtx (even though fold does not catch the fortran one as we need a tree combiner for that). And yes I actually reduced that testcase from real fortran code (I forgot which one right now). -- Pinski ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 4:15 ` Andrew Pinski @ 2005-07-01 4:58 ` Gabriel Dos Reis 2005-07-01 4:53 ` Andrew Pinski 0 siblings, 1 reply; 27+ messages in thread From: Gabriel Dos Reis @ 2005-07-01 4:58 UTC (permalink / raw) To: Andrew Pinski; +Cc: Daniel Berlin, Joe Buck, 'gcc mailing list' Andrew Pinski <pinskia@physics.uc.edu> writes: | On Jul 1, 2005, at 12:06 AM, Gabriel Dos Reis wrote: | > | > There are of course coner and pathological cases, but I don't think we | > should worry too much about missing them. Let's first cover the | > structured loops, and address the contorsed ones later if they become | > really important. | | And I just submitted a patch for one of those corner/pathological cases | and it actually does improve code, how much I don't know because I don't | have access to any benchmark to test on. If someone wants to test it, | they will most likely find it, it does in fact improve code. | | Also knowing in let say fold if the variable is a loop index or not is | actually not trivial. | | Another testcase where we will fail out at if we take the view you want | to take is: As I said, if you let user tell you that his loop behaves well, i.e. bounds do not rely on wrapping semantics, and yet he writes his loop to deceive the compiler, then he loses. Let him choose his own poinson, don't think you have to choose it for him. -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 4:58 ` Gabriel Dos Reis @ 2005-07-01 4:53 ` Andrew Pinski 2005-07-01 5:02 ` Gabriel Dos Reis 0 siblings, 1 reply; 27+ messages in thread From: Andrew Pinski @ 2005-07-01 4:53 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Daniel Berlin, Joe Buck, 'gcc mailing list' On Jul 1, 2005, at 12:49 AM, Gabriel Dos Reis wrote: > > As I said, if you let user tell you that his loop behaves well, i.e. > bounds do not rely on wrapping semantics, and yet he writes his loop to > deceive the compiler, then he loses. Let him choose his own poinson, > don't think you have to choose it for him. They already can, that is what -fwrapv is for. If you ignore that there is already a flag for this, then fine but there is already a flag for this, just like there is already a flag for disabling C/C++ aliasing rules. -- Pinski ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 4:53 ` Andrew Pinski @ 2005-07-01 5:02 ` Gabriel Dos Reis 0 siblings, 0 replies; 27+ messages in thread From: Gabriel Dos Reis @ 2005-07-01 5:02 UTC (permalink / raw) To: Andrew Pinski; +Cc: Daniel Berlin, Joe Buck, 'gcc mailing list' Andrew Pinski <pinskia@physics.uc.edu> writes: | On Jul 1, 2005, at 12:49 AM, Gabriel Dos Reis wrote: | | > | > As I said, if you let user tell you that his loop behaves well, i.e. | > bounds do not rely on wrapping semantics, and yet he writes his loop to | > deceive the compiler, then he loses. Let him choose his own poinson, | > don't think you have to choose it for him. | | They already can, that is what -fwrapv is for. No, you completely missed the point and it would help if you read through carefully. The choice was about letting user tell you what he knows/assumes about his loop bounds. Not applying uniformly the wrapping semantics. (Not counting the fact that it was pointed out -fwrapv is useful as is). -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 4:07 ` Gabriel Dos Reis 2005-07-01 4:15 ` Andrew Pinski @ 2005-07-02 16:51 ` Robert Dewar 2005-07-02 19:07 ` Gabriel Dos Reis 1 sibling, 1 reply; 27+ messages in thread From: Robert Dewar @ 2005-07-02 16:51 UTC (permalink / raw) To: Gabriel Dos Reis Cc: Daniel Berlin, Joe Buck, Andrew Pinski, 'gcc mailing list' Gabriel Dos Reis wrote: > As we have briefly discussed in mails, the most critical part of the > issue seems to be what can be assumed for loop variables. I countend > that for many if not most practical loops, the variable can be assumed > not to overflow and apply the transformation. But we need not apply > "undefined behaviour" to all other cases; only for those > "well-written" loop and loop variables. In summary, if user's loop is > well-written then he will benefit from the transformation. > That will cover already a good set of common loops. Note that the lack of a FOR loop in C adds to the problems here. In languages with FOR loops, this issue comes up very explicitly, but at the code generation level, you have to be careful to generate code that deals with the boundary cases correctly. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-02 16:51 ` Robert Dewar @ 2005-07-02 19:07 ` Gabriel Dos Reis 2005-07-02 23:15 ` Robert Dewar 0 siblings, 1 reply; 27+ messages in thread From: Gabriel Dos Reis @ 2005-07-02 19:07 UTC (permalink / raw) To: Robert Dewar Cc: Daniel Berlin, Joe Buck, Andrew Pinski, 'gcc mailing list' Robert Dewar <dewar@adacore.com> writes: | Gabriel Dos Reis wrote: | | > As we have briefly discussed in mails, the most critical part of the | > issue seems to be what can be assumed for loop variables. I countend | > that for many if not most practical loops, the variable can be assumed | > not to overflow and apply the transformation. But we need not apply | > "undefined behaviour" to all other cases; only for those | > "well-written" loop and loop variables. In summary, if user's loop is | > well-written then he will benefit from the transformation. That will | > cover already a good set of common loops. | | Note that the lack of a FOR loop in C adds to the problems here. In This is why I think a switch is useful here. The programmer may know more about his/her loops than the current GCC infrastructure may prove. Furthermore, the blanket statement of lack of a "FOR loop" does not preclude existence of properly writeen FOR loop. We should be able to do conservative analysis and catch those. If, User writes for (int i = min; i < max; ++i) .... and i, min and max don't change in the body, no matter what you think of C's general "for" not being a FOR loop, the above is a FOR loop. -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-02 19:07 ` Gabriel Dos Reis @ 2005-07-02 23:15 ` Robert Dewar 2005-07-02 23:28 ` Joe Buck 2005-07-03 0:16 ` Gabriel Dos Reis 0 siblings, 2 replies; 27+ messages in thread From: Robert Dewar @ 2005-07-02 23:15 UTC (permalink / raw) To: Gabriel Dos Reis Cc: Daniel Berlin, Joe Buck, Andrew Pinski, 'gcc mailing list' Gabriel Dos Reis wrote: > > for (int i = min; i < max; ++i) > .... > > and i, min and max don't change in the body, no matter what you think > of C's general "for" not being a FOR loop, the above is a FOR loop. But this normal paradigm for representing a FOR loop does not work for all possible ranges, that's precisely the trouble! ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-02 23:15 ` Robert Dewar @ 2005-07-02 23:28 ` Joe Buck 2005-07-03 0:20 ` Gabriel Dos Reis 2005-07-03 0:16 ` Gabriel Dos Reis 1 sibling, 1 reply; 27+ messages in thread From: Joe Buck @ 2005-07-02 23:28 UTC (permalink / raw) To: Robert Dewar Cc: Gabriel Dos Reis, Daniel Berlin, Andrew Pinski, 'gcc mailing list' On Sat, Jul 02, 2005 at 07:15:17PM -0400, Robert Dewar wrote: > Gabriel Dos Reis wrote: > > > > for (int i = min; i < max; ++i) > > .... > > > >and i, min and max don't change in the body, no matter what you think > >of C's general "for" not being a FOR loop, the above is a FOR loop. > > But this normal paradigm for representing a FOR loop does not work for > all possible ranges, that's precisely the trouble! Yes, there's a problem if the maximum value of i is intended to be INT_MAX. There's a more common problem with for (unsigned i = array_size-1; i >= 0; --i) ... which, of course, doesn't work because unsigned values are always greater than zero. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-02 23:28 ` Joe Buck @ 2005-07-03 0:20 ` Gabriel Dos Reis 0 siblings, 0 replies; 27+ messages in thread From: Gabriel Dos Reis @ 2005-07-03 0:20 UTC (permalink / raw) To: Joe Buck Cc: Robert Dewar, Daniel Berlin, Andrew Pinski, 'gcc mailing list' Joe Buck <Joe.Buck@synopsys.COM> writes: | On Sat, Jul 02, 2005 at 07:15:17PM -0400, Robert Dewar wrote: | > Gabriel Dos Reis wrote: | > > | > > for (int i = min; i < max; ++i) | > > .... | > > | > >and i, min and max don't change in the body, no matter what you think | > >of C's general "for" not being a FOR loop, the above is a FOR loop. | > | > But this normal paradigm for representing a FOR loop does not work for | > all possible ranges, that's precisely the trouble! | | Yes, there's a problem if the maximum value of i is intended to be | INT_MAX. I don't think the cases of INT_MAX represents the majority of such FOR loop. The semi-open interval is a widespread idiom and has become a standard idiom, at least if you move to STL :-) -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-02 23:15 ` Robert Dewar 2005-07-02 23:28 ` Joe Buck @ 2005-07-03 0:16 ` Gabriel Dos Reis 1 sibling, 0 replies; 27+ messages in thread From: Gabriel Dos Reis @ 2005-07-03 0:16 UTC (permalink / raw) To: Robert Dewar Cc: Daniel Berlin, Joe Buck, Andrew Pinski, 'gcc mailing list' Robert Dewar <dewar@adacore.com> writes: | Gabriel Dos Reis wrote: | > for (int i = min; i < max; ++i) | > .... | > and i, min and max don't change in the body, no matter what you think | > of C's general "for" not being a FOR loop, the above is a FOR loop. | | But this normal paradigm for representing a FOR loop does not work for | all possible ranges, Yes, but it needs not cover all possible ranges. For practical purposes, if it covers the vast majority of such loops I'll take it and leave you complaining about not covering all possible ranges. -- Gaby ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 1:03 ` Andrew Pinski 2005-07-01 1:23 ` Gabriel Dos Reis 2005-07-01 1:25 ` Joe Buck @ 2005-07-02 16:47 ` Robert Dewar 2 siblings, 0 replies; 27+ messages in thread From: Robert Dewar @ 2005-07-02 16:47 UTC (permalink / raw) To: Andrew Pinski; +Cc: Gabriel Dos Reis, 'gcc mailing list' Andrew Pinski wrote: > But the reason question is why make it an undefined behavior instead of > an implementation defined? This would have made it clearer instead of > allowing the compiler not document what happens. Or is C++ > just following C here? In which case it might be better to ask the C > committee why it was done this way and real definition of undefined for > this case? Note that implementation defined in practice is a fairly severe constraint. That's because you don't want to have a super complicated definition that takes a book to describe all the horrible things that might happen, so in practice you are pushed into some simple decision (always traps, always saturates, always wraps etc for the case of overflow). ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 0:49 ` Gabriel Dos Reis 2005-07-01 1:03 ` Andrew Pinski @ 2005-07-02 16:45 ` Robert Dewar 1 sibling, 0 replies; 27+ messages in thread From: Robert Dewar @ 2005-07-02 16:45 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Joe Buck, Paul Schlie, gcc Gabriel Dos Reis wrote: > What I'm claiming is that he thinks "undefined behaviour" in the > standard should not be taken as meaning "go to hell" (or punishment to > borrow words from you) or absolute liberty for compiler writers to do > just about everything that is imaginable, regardless of expectations. > In other words, it is a question of balance. The trouble is that the standard does not formalize the balance, and that is why we use the rhetoric. The real issue is whether the compiler optimizer circuits should be allowed to assume that there is no overflow. At first glance, it seems reasonable to say yes, that is after all what the undefined semantics is about. The trouble, is, as I have pointed out before, and tried to illustrate with my password example, that this assumption, propagated by clever global flow algorithms, can have very unexpected results. So what to do? We could try to formalize the notion that although overflow is undefined, this information cannot be propagated, or perhaps more specifically cannot be propagated backwards. But in practice this is very difficult to formalize, and it is very hard to put bounds on what propagation means in this case. We have a sort of informal notion that says the kind of thing that occurred in my password example is a bad thing and should not happen, but we have a lot of trouble formalizing it (I know of lots of attempts to do this, no successes, anyone know a success story here?) Note that a similar issue arises with assertions (is the compiler allowed to assume that assertions are true and propagate this information?) We could try to avoid the use of the general undefined. After all if Stroustrup doesn't like the consequence of unbounded undefinedness, then presumably he doesn't like the language of the standard. It is the standard that introduces this notion of unbounded undefinedness not me :-) In fact I think the attempt to avoid unbounded undefinedness (what Ada calls erroneous execution), is something that is very worth while. One of the major steps forward in the Ada 95 standard over the Ada 83 standard was that we eliminated many of the common cases of erroneousness and replaced it with bounded errors. FOr example, consider the case of uninitialized variables. In Ada 83, a reference to an uninitialized scalar variable caused the program to be erroneous. Now in Ada 95, such a value may have an invalid representation. To reference an uninitialized variable is now not-erroneous, but rather a bounded error. The possible effects are defined as follows in the RM: 9 If the representation of a scalar object does not represent a value of the object's subtype (perhaps because the object was not initialized), the object is said to have an invalid representation. It is a bounded error to evaluate the value of such an object. If the error is detected, either Constraint_Error or Program_Error is raised. Otherwise, execution continues using the invalid representation. The rules of the language outside this subclause assume that all objects have valid representations. The semantics of operations on invalid representations are as follows: 10 If the representation of the object represents a value of the object's type, the value of the type is used. 11 If the representation of the object does not represent a value of the object's type, the semantics of operations on such representations is implementation-defined, but does not by itself lead to erroneous or unpredictable execution, or to other objects becoming abnormal. > As, an example, he > illustrated the issue with the story -- quickly classified as "legend" by > Robert Dewar -- about the best C optimizing compilers that miscompiled > the Unix kernel that nobody wanted to use in practice (even if it > would blow up any other competing compiler) and the company > running out of business. Actually I asked for documentation of this claim, and as far as I remember no one provided it, which is a pity. It is really useful to have examples of real life situations where sticking to the standard and ignoring real world practice resulted in useless compilers. I gave one such example, the Burroughs Fortran Compiler. In class, I have always suggested as another example that a C compiler that generated code for a flat address space would be a menace if it gave random results for comparing addresses between different allocated objects. I assume no C compiler does this in practice. So the Unix kernel example would be really nice to pin down. What compiler was this? And what was the "legitimate" freedom that it took that it should not have. By the way, I generally agree that C is a language where the expected behavior is quite a bit larger than the formally defined behavior (I consider this a bad characteristic of a language by the way). At another extreme, in the case of COBOL, when we wrote Realia COBOL, there were a number of places where we deliberately deviated from the COBOL standard. Why? Because there were bugs in the IBM mainframe implementations, and it was more important to maintain compatibility with these bugs than to do what the standard demanded :-) ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-06-30 23:25 ` Joe Buck 2005-07-01 0:49 ` Gabriel Dos Reis @ 2005-07-01 1:04 ` Paul Schlie 2005-07-02 16:48 ` Robert Dewar 2005-07-01 1:35 ` Paul Schlie 2 siblings, 1 reply; 27+ messages in thread From: Paul Schlie @ 2005-07-01 1:04 UTC (permalink / raw) To: Joe Buck, Gabriel Dos Reis; +Cc: gcc > Joe Buck <Joe.Buck@synopsys.COM> > Undefined behavior doesn't mean that we should attempt to arbitrarily > punish those who cross the line; that's why I don't think forcing integer > overflows to trap (at least by default) is a good idea. In many cases, > "assume no overflow, but don't trap" can produce a better result than > "assume wrap" does, as in the example I gave before. My primary concern is about predictability, and could live with undefined integer overflow if it were likely reasonably possible to verify that in the general case an overflow would not occur, as otherwise an undefined behavior may result. (which I can't believe is acceptable to anyone). Although I recognize and accept that most trivial uses of signed arithmetic can likely be verified as being constrained or not; it seems pretty clear to me that it's very difficult and often strictly impossible in the general case to do so; implying that signed integer arithmetic needs to be avoided in the general case by either specifying signed integers as being unsigned and convert them as required post-fact (which may also be undefined), and/or utilize floats if one wants to produce a program which has a reasonable chance of predictable behavior. (My question was an honest one, although candidly somewhat pointed; as prior to recent discussions it wasn't clear to me how potentially serious an issue this was; so thought being forewarned was better than being surprised by unexpected behaviors which may only express themselves in subtle non-obvious circumstances.) ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-07-01 1:04 ` Paul Schlie @ 2005-07-02 16:48 ` Robert Dewar 0 siblings, 0 replies; 27+ messages in thread From: Robert Dewar @ 2005-07-02 16:48 UTC (permalink / raw) To: Paul Schlie; +Cc: Joe Buck, Gabriel Dos Reis, gcc Paul Schlie wrote: > My primary concern is about predictability, and could live with undefined > integer overflow if it were likely reasonably possible to verify that in > the general case an overflow would not occur, as otherwise an undefined > behavior may result. (which I can't believe is acceptable to anyone). Well bugs in programs in general are not acceptable. This is just one example of a bug. > > Although I recognize and accept that most trivial uses of signed arithmetic > can likely be verified as being constrained or not; it seems pretty clear > to me that it's very difficult and often strictly impossible in the general > case to do so; implying that signed integer arithmetic needs to be avoided > in the general case by either specifying signed integers as being unsigned > and convert them as required post-fact (which may also be undefined), and/or > utilize floats if one wants to produce a program which has a reasonable > chance of predictable behavior. Actually in the safety critical world, people all the time go through procedures to verify that their program is free of bugs, including unexpected overflow. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? 2005-06-30 23:25 ` Joe Buck 2005-07-01 0:49 ` Gabriel Dos Reis 2005-07-01 1:04 ` Paul Schlie @ 2005-07-01 1:35 ` Paul Schlie 2 siblings, 0 replies; 27+ messages in thread From: Paul Schlie @ 2005-07-01 1:35 UTC (permalink / raw) To: gcc > Joe Buck <Joe.Buck@synopsys.COM> > Undefined behavior doesn't mean that we should attempt to arbitrarily > punish those who cross the line; that's why I don't think forcing integer > overflows to trap (at least by default) is a good idea. In many cases, > "assume no overflow, but don't trap" can produce a better result than > "assume wrap" does, as in the example I gave before. My primary concern is about predictability, and could live with undefined integer overflow if it were likely reasonably possible to verify that in the general case an overflow would not occur, as otherwise an undefined behavior may result. (which I can't believe is acceptable to anyone). Although I recognize and accept that most trivial uses of signed arithmetic can likely be verified as being constrained or not; it seems pretty clear to me that it's very difficult and often strictly impossible in the general case to do so; implying that signed integer arithmetic needs to be avoided in the general case by either specifying signed integers as being unsigned and convert them as required post-fact (which may also be undefined), and/or utilize floats if one wants to produce a program which has a reasonable chance of predictable behavior. (My question was an honest one, although candidly somewhat pointed; as prior to recent discussions it wasn't clear to me how potentially serious an issue this was; so thought being forewarned was better than being surprised by unexpected behaviors which may only express themselves in subtle non-obvious circumstances.) ^ permalink raw reply [flat|nested] 27+ messages in thread
end of thread, other threads:[~2005-07-03 0:20 UTC | newest] Thread overview: 27+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2005-06-30 19:15 Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics? Paul Schlie 2005-06-30 20:08 ` Paul Schlie 2005-06-30 22:06 ` Joe Buck 2005-06-30 22:26 ` Gabriel Dos Reis 2005-06-30 23:25 ` Joe Buck 2005-07-01 0:49 ` Gabriel Dos Reis 2005-07-01 1:03 ` Andrew Pinski 2005-07-01 1:23 ` Gabriel Dos Reis 2005-07-01 1:25 ` Joe Buck 2005-07-01 1:40 ` Gabriel Dos Reis 2005-07-01 3:16 ` Daniel Berlin 2005-07-01 4:07 ` Gabriel Dos Reis 2005-07-01 4:15 ` Andrew Pinski 2005-07-01 4:58 ` Gabriel Dos Reis 2005-07-01 4:53 ` Andrew Pinski 2005-07-01 5:02 ` Gabriel Dos Reis 2005-07-02 16:51 ` Robert Dewar 2005-07-02 19:07 ` Gabriel Dos Reis 2005-07-02 23:15 ` Robert Dewar 2005-07-02 23:28 ` Joe Buck 2005-07-03 0:20 ` Gabriel Dos Reis 2005-07-03 0:16 ` Gabriel Dos Reis 2005-07-02 16:47 ` Robert Dewar 2005-07-02 16:45 ` Robert Dewar 2005-07-01 1:04 ` Paul Schlie 2005-07-02 16:48 ` Robert Dewar 2005-07-01 1:35 ` Paul Schlie
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).