* Do C++ signed types have modulo semantics? @ 2005-06-27 5:09 Michael Veksler 2005-06-27 13:02 ` Nathan Sidwell 0 siblings, 1 reply; 43+ messages in thread From: Michael Veksler @ 2005-06-27 5:09 UTC (permalink / raw) To: gcc According to the (very) long discussion on VRP, signed char/short/int/etc do not have modulo semantic, they have an undefined behavior on overflow. However in <limits> defines numeric_limits<signed type>::is_modulo = true. 1. Is that a bug in <limits>, a bug in the standard, or is just C++ different than C in this respect? 2. Maybe because overflow is undefined then is_modulo maybe considered "unspecified". I don't like this option, because it does not help generic programming. 3. Do I understand what is_modulo stands for? 4. What should be done (libstdc++ PR, C++ PR, DR, other)? I have seen this in gcc-4.0-20050602, and gcc-3.4.3 Michael ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-27 5:09 Do C++ signed types have modulo semantics? Michael Veksler @ 2005-06-27 13:02 ` Nathan Sidwell 2005-06-27 14:10 ` Gabriel Dos Reis 0 siblings, 1 reply; 43+ messages in thread From: Nathan Sidwell @ 2005-06-27 13:02 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc Michael Veksler wrote: > According to the (very) long discussion on VRP, signed char/short/int/etc > do not have modulo semantic, they have an undefined behavior on overflow. > However in <limits> defines numeric_limits<signed type>::is_modulo = true. signed types are undefined on overflow. [5/5] and [3.9.1/2,3] > 1. Is that a bug in <limits>, a bug in the standard, or is just C++ > different > than C in this respect? a bug in limits, probably > 2. Maybe because overflow is undefined then is_modulo maybe > considered "unspecified". I don't like this option, because it does not > help > generic programming. it's also, I believe, wrong, in that some gcc optimizations will not preserve such behaviour. (I guess this is the whole VRP conversation you mention.) > 3. Do I understand what is_modulo stands for? yes > 4. What should be done (libstdc++ PR, C++ PR, DR, other)? 18.2.1.2/57 claims is_modulo is true 'for signed types on most machines'. Such an assertion is false when optimizations rely the undefinedness of signed overflow. A DR should probably be filed (maybe one is, I'm not at all familiar with library DRs). nathan -- Nathan Sidwell :: http://www.codesourcery.com :: CodeSourcery LLC nathan@codesourcery.com :: http://www.planetfall.pwp.blueyonder.co.uk ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-27 13:02 ` Nathan Sidwell @ 2005-06-27 14:10 ` Gabriel Dos Reis 2005-06-27 14:36 ` Nathan Sidwell 0 siblings, 1 reply; 43+ messages in thread From: Gabriel Dos Reis @ 2005-06-27 14:10 UTC (permalink / raw) To: Nathan Sidwell; +Cc: Michael Veksler, gcc Nathan Sidwell <nathan@codesourcery.com> writes: | Michael Veksler wrote: | > According to the (very) long discussion on VRP, signed char/short/int/etc | > do not have modulo semantic, they have an undefined behavior on overflow. | > However in <limits> defines numeric_limits<signed type>::is_modulo = true. | | signed types are undefined on overflow. [5/5] and [3.9.1/2,3] But a compiler could define them to be modulo -- that is the whole point. The paragraph does not say they don't "modulo". | > 1. Is that a bug in <limits>, a bug in the standard, or is just C++ | > different | > than C in this respect? | a bug in limits, probably | | > 2. Maybe because overflow is undefined then is_modulo maybe | > considered "unspecified". I don't like this option, because it does not | > help | > generic programming. | it's also, I believe, wrong, in that some gcc optimizations will not | preserve such behaviour. (I guess this is the whole VRP conversation | you mention.) | | > 3. Do I understand what is_modulo stands for? | yes | | > 4. What should be done (libstdc++ PR, C++ PR, DR, other)? | | 18.2.1.2/57 claims is_modulo is true 'for signed types on most | machines'. Such an assertion is false when optimizations rely the | undefinedness of signed overflow. A DR should probably be filed | (maybe one is, I'm not at all familiar with library DRs). Well, undefined behaviour does not mean unconditional hell or evil. It is just behaviour left up to the compiler to whatever it wants. And all useful programs we write rely on undefined behaviour of one sort or the other, starting with GCC. In the case of numeric_limits<>, it may help remembering two things: (1) 18.2.1/1 The numeric_limits component provides a C++ program with information about various properties of the implementation's representation of the fundamental types. (2) LIA-1, 5.1.2 If /bounded/ is true, the mathematical operations +, 1, *, / (after rounding) can produce results that lie outside of the set I. In such cases, the computations add_I, sub_I, mul_I and div_I shall either cause a notification (if modulo == false), or return a "wrapped" result (if modulo = true) (1) is something that C++ provides (constains more information that C's <limits.h> and <float.h>) user with. The intented semantics is that that compiler informs users about their representation choices. (2) gives the rationale behing "modulo". C++ does not require notification (the passage you pointed to), so it is up to GCC to define the behaviour should be and correspondingly amend the paragraph so as to display consistent semantics. Back in the dark ages, we used to define is_modulo false but we did not raise notification, basing on the fact since C++ did not require anything, it was already sufficient to tell user that we do not promise modulo arithmetic. When RTH helped cleanup the numeric_limits implementation in September 2002, he made a very good point (which I held to be true, since obviously he is The Middle-end and Back-end Guy) http://gcc.gnu.org/ml/libstdc++/2002-09/msg00207.html Quote: First, GCC does not support any targets for which is_modulo is false for an integer type. This is made obvious by the fact that we do not distinguish between signed and unsigned rtl modes, and eg do not have different patterns for signed and unsigned addition. Thus is_modulo should always be true for the integral types. I don't think there is a DR for that (from the standard point). We do have a consistency problem in GCC. I believe optimizations we do should be consistent with semantics unless we also provide for -finconsistent-semantics. -- Gaby ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-27 14:10 ` Gabriel Dos Reis @ 2005-06-27 14:36 ` Nathan Sidwell 2005-06-27 14:47 ` Paul Koning 2005-06-27 15:17 ` Gabriel Dos Reis 0 siblings, 2 replies; 43+ messages in thread From: Nathan Sidwell @ 2005-06-27 14:36 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Michael Veksler, gcc Gabriel Dos Reis wrote: > But a compiler could define them to be modulo -- that is the whole > point. The paragraph does not say they don't "modulo". of course it could do so, but then to be useful it should document it, and it would be an extension. > | 18.2.1.2/57 claims is_modulo is true 'for signed types on most > | machines'. Such an assertion is false when optimizations rely the > | undefinedness of signed overflow. A DR should probably be filed > | (maybe one is, I'm not at all familiar with library DRs). > > Well, undefined behaviour does not mean unconditional hell or evil. > It is just behaviour left up to the compiler to whatever it wants. correct. However the std *itself* says in one place 'this is undefined' and in another place 'this is usually modulo'. I find that confusing at best. > And all useful programs we write rely on undefined behaviour of one > sort or the other, starting with GCC. In the case of They do? I thought they usually relied on implementation defined, documented extensions or were part of the implementation. Now I'm sure you'll prove me wrong in some way or other, but please stick to the point -- do real important programs that must not break and cannot be changed rely on signed modulo behaviour? > When RTH helped cleanup the numeric_limits implementation in September > 2002, he made a very good point (which I held to be true, since > obviously he is The Middle-end and Back-end Guy) > > http://gcc.gnu.org/ml/libstdc++/2002-09/msg00207.html thanks for that. I was under the impression that some of the loop optimizers relied on the fact that iterating over a signed type did not do odd modulo related things. Indeed this comment in loop.c concerning BIVs leads me to believe we already fail to honor the is_modulo value Note that treating the entire pseudo as a BIV will result in making simple increments to any GIVs based on it. However, if the variable overflows in its declared mode but not its promoted mode, the result will be incorrect. This is acceptable if the variable is signed, since overflows in such cases are undefined, but not if it is unsigned, since those overflows are defined. So we only check for SIGN_EXTEND and not ZERO_EXTEND. Anyway, this doesn't answer Michael's question. He asked whether C and C++ differ in this regard. The answer is the standards are the same, and the implementation is the same (because it is the same backend). So, if whatever optimizations he is turning on change the behaviour rth cited, then limits should change too. I don't particularly care what behaviour is chosen, except that 1) C and C++ implementations should behave the same way 2) we should pick the behaviour that leads to better code generation in real life. 3) if modulo behaviour is chosen, it should be well documented in a place more prominant than type_traits<int>::is_modulo. nathan -- Nathan Sidwell :: http://www.codesourcery.com :: CodeSourcery LLC nathan@codesourcery.com :: http://www.planetfall.pwp.blueyonder.co.uk ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-27 14:36 ` Nathan Sidwell @ 2005-06-27 14:47 ` Paul Koning 2005-06-27 15:21 ` Michael Veksler 2005-06-27 15:17 ` Gabriel Dos Reis 1 sibling, 1 reply; 43+ messages in thread From: Paul Koning @ 2005-06-27 14:47 UTC (permalink / raw) To: nathan; +Cc: gdr, VEKSLER, gcc >>>>> "Nathan" == Nathan Sidwell <nathan@codesourcery.com> writes: >> And all useful programs we write rely on undefined behaviour of >> one sort or the other, starting with GCC. In the case of Nathan> They do? I thought they usually relied on implementation Nathan> defined, documented extensions or were part of the Nathan> implementation. Now I'm sure you'll prove me wrong in some Nathan> way or other, but please stick to the point -- do real Nathan> important programs that must not break and cannot be changed Nathan> rely on signed modulo behaviour? I'm sure they do. Obviously they should not, since the standard says not to. But most programmers are not language lawyers. Most programmers "know" that arithmetic is modulo wordsize. And those few who know the right answer (only unsigned arithmetic is modulo) will from time to time slip up and omit the "unsigned" keyword in their declarations. So I can't point to a direct example but I am certain such examples exist. paul ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-27 14:47 ` Paul Koning @ 2005-06-27 15:21 ` Michael Veksler 2005-06-28 3:06 ` Mark Mitchell 0 siblings, 1 reply; 43+ messages in thread From: Michael Veksler @ 2005-06-27 15:21 UTC (permalink / raw) To: Paul Koning; +Cc: gcc, gdr, nathan Paul Koning <pkoning@equallogic.com> wrote on 27/06/2005 17:47:12: > >>>>> "Nathan" == Nathan Sidwell <nathan@codesourcery.com> writes: > > >> And all useful programs we write rely on undefined behaviour of > >> one sort or the other, starting with GCC. In the case of > > Nathan> They do? I thought they usually relied on implementation > Nathan> defined, documented extensions or were part of the > Nathan> implementation. Now I'm sure you'll prove me wrong in some > Nathan> way or other, but please stick to the point -- do real > Nathan> important programs that must not break and cannot be changed > Nathan> rely on signed modulo behaviour? > > I'm sure they do. Obviously they should not, since the standard says > not to. But most programmers are not language lawyers. Most > programmers "know" that arithmetic is modulo wordsize. And those few > who know the right answer (only unsigned arithmetic is modulo) will > from time to time slip up and omit the "unsigned" keyword in their > declarations. > > So I can't point to a direct example but I am certain such examples > exist. > Please, these arguments have been beaten to death in previous threads. We don't want to slip to long discussions on the merits of either one of the decisions, again. So from what I understand, gcc does something very inconsistent, and this has to be fixed. Anyway, as someone mentioned, it is not clear if the compiler can have a reasonable support for modulo on x86 without a penalty (the MIN_INT/-1 case). What it means that numeric_limits<signed>::is_modulo was inconsistent with gcc for all older gcc/libstdc++ versions. It is now PR 22200, the potentially long debate can move there. http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22200 Michael ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-27 15:21 ` Michael Veksler @ 2005-06-28 3:06 ` Mark Mitchell 2005-06-28 3:49 ` Gabriel Dos Reis ` (2 more replies) 0 siblings, 3 replies; 43+ messages in thread From: Mark Mitchell @ 2005-06-28 3:06 UTC (permalink / raw) To: Michael Veksler; +Cc: Paul Koning, gcc, gdr, nathan Michael Veksler wrote: >> Most programmers "know" that arithmetic is modulo wordsize. And those few >>who know the right answer (only unsigned arithmetic is modulo) will >>from time to time slip up and omit the "unsigned" keyword in their >>declarations. I agree. Although the standard clearly makes signed overflow undefined, I think it would be better if GCC defined it to be modulo arithmetic. The degree to which that would result in inferior code seems likely to be somewhat small, and the amount of user confusion we would eliminate, and the number of programs that would not break with GCC, even though they work with other compilers, seems likely to be high. -- Mark Mitchell CodeSourcery, LLC mark@codesourcery.com (916) 791-8304 ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 3:06 ` Mark Mitchell @ 2005-06-28 3:49 ` Gabriel Dos Reis 2005-06-28 10:08 ` Robert Dewar 2005-06-28 16:54 ` Joe Buck 2 siblings, 0 replies; 43+ messages in thread From: Gabriel Dos Reis @ 2005-06-28 3:49 UTC (permalink / raw) To: Mark Mitchell; +Cc: Michael Veksler, Paul Koning, gcc, nathan Mark Mitchell <mark@codesourcery.com> writes: | Michael Veksler wrote: | | >> Most programmers "know" that arithmetic is modulo wordsize. And those few | >>who know the right answer (only unsigned arithmetic is modulo) will | >>from time to time slip up and omit the "unsigned" keyword in their | >>declarations. | | I agree. | | Although the standard clearly makes signed overflow undefined, I think | it would be better if GCC defined it to be modulo arithmetic. The | degree to which that would result in inferior code seems likely to be | somewhat small, and the amount of user confusion we would eliminate, | and the number of programs that would not break with GCC, even though | they work with other compilers, seems likely to be high. Amen. -- Gaby ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 3:06 ` Mark Mitchell 2005-06-28 3:49 ` Gabriel Dos Reis @ 2005-06-28 10:08 ` Robert Dewar 2005-06-28 11:19 ` Steven Bosscher 2005-06-28 16:54 ` Joe Buck 2 siblings, 1 reply; 43+ messages in thread From: Robert Dewar @ 2005-06-28 10:08 UTC (permalink / raw) To: Mark Mitchell; +Cc: Michael Veksler, Paul Koning, gcc, gdr, nathan Mark Mitchell wrote: > Although the standard clearly makes signed overflow undefined, I think > it would be better if GCC defined it to be modulo arithmetic. The > degree to which that would result in inferior code seems likely to be > somewhat small, and the amount of user confusion we would eliminate, and > the number of programs that would not break with GCC, even though they > work with other compilers, seems likely to be high. I find this reasonable, especially given the general attitude that we don't care much if gcc programs are not easily portable to other compilers, which is always the strongest argument against this kind of language extension (defining the undefined). I would prefer to make such a decision with data about the impact on code quality, rather than Mark's "seem likely" guess. ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 10:08 ` Robert Dewar @ 2005-06-28 11:19 ` Steven Bosscher 2005-06-28 12:03 ` Ulrich Weigand 2005-06-28 12:16 ` Paul Koning 0 siblings, 2 replies; 43+ messages in thread From: Steven Bosscher @ 2005-06-28 11:19 UTC (permalink / raw) To: gcc Cc: Robert Dewar, Mark Mitchell, Michael Veksler, Paul Koning, gdr, nathan On Tuesday 28 June 2005 12:07, Robert Dewar wrote: > Mark Mitchell wrote: > > Although the standard clearly makes signed overflow undefined, I think > > it would be better if GCC defined it to be modulo arithmetic. The > > degree to which that would result in inferior code seems likely to be > > somewhat small, and the amount of user confusion we would eliminate, and > > the number of programs that would not break with GCC, even though they > > work with other compilers, seems likely to be high. > > I find this reasonable, especially given the general attitude that > we don't care much if gcc programs are not easily portable to other > compilers, which is always the strongest argument against this kind > of language extension (defining the undefined). > > I would prefer to make such a decision with data about the impact > on code quality, rather than Mark's "seem likely" guess. Indeed. Frankly this "seems likely" guess confuses me. It is already well known that using unsigned types for loop counters may greatly improve the code gcc can generate for loops. With wrap-around semantics, suddenly countable loops are turned into noncountable loops, overflow can occur, dependencies may be introduced that never happen in reality, and so on. Anyway, I've started a SPEC run with "-O2" vs. "-O2 -fwrapv". Let's see how big the damage would be ;-) Gr. Steven ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 11:19 ` Steven Bosscher @ 2005-06-28 12:03 ` Ulrich Weigand 2005-06-28 12:09 ` Steven Bosscher 2005-06-28 12:16 ` Paul Koning 1 sibling, 1 reply; 43+ messages in thread From: Ulrich Weigand @ 2005-06-28 12:03 UTC (permalink / raw) To: Steven Bosscher Cc: gcc, Robert Dewar, Mark Mitchell, Michael Veksler, Paul Koning, gdr, nathan Steven Bosscher wrote: > Anyway, I've started a SPEC run with "-O2" vs. "-O2 -fwrapv". Let's see > how big the damage would be ;-) Please make sure to include a 64-bit target, where it actually makes any difference. (I recall performance degradations of 20-30% in some SPECfp cases from getting induction variable reduction wrong ...) Bye, Ulrich -- Dr. Ulrich Weigand Linux on zSeries Development Ulrich.Weigand@de.ibm.com ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 12:03 ` Ulrich Weigand @ 2005-06-28 12:09 ` Steven Bosscher 2005-06-29 16:46 ` Steven Bosscher 0 siblings, 1 reply; 43+ messages in thread From: Steven Bosscher @ 2005-06-28 12:09 UTC (permalink / raw) To: Ulrich Weigand Cc: gcc, Robert Dewar, Mark Mitchell, Michael Veksler, Paul Koning, gdr, nathan On Tuesday 28 June 2005 14:02, Ulrich Weigand wrote: > Steven Bosscher wrote: > > Anyway, I've started a SPEC run with "-O2" vs. "-O2 -fwrapv". Let's see > > how big the damage would be ;-) > > Please make sure to include a 64-bit target, where it actually makes any > difference. (I recall performance degradations of 20-30% in some > SPECfp cases from getting induction variable reduction wrong ...) Yeah, I'm testing on an AMD64 box, both 64 bits and 32 bits. Gr. Steven ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 12:09 ` Steven Bosscher @ 2005-06-29 16:46 ` Steven Bosscher 2005-06-29 18:01 ` Daniel Berlin 0 siblings, 1 reply; 43+ messages in thread From: Steven Bosscher @ 2005-06-29 16:46 UTC (permalink / raw) To: Ulrich Weigand Cc: gcc, Robert Dewar, Mark Mitchell, Michael Veksler, Paul Koning, gdr, nathan On Tuesday 28 June 2005 14:09, Steven Bosscher wrote: > On Tuesday 28 June 2005 14:02, Ulrich Weigand wrote: > > Steven Bosscher wrote: > > > Anyway, I've started a SPEC run with "-O2" vs. "-O2 -fwrapv". Let's > > > see how big the damage would be ;-) > > > > Please make sure to include a 64-bit target, where it actually makes any > > difference. (I recall performance degradations of 20-30% in some > > SPECfp cases from getting induction variable reduction wrong ...) > > Yeah, I'm testing on an AMD64 box, both 64 bits and 32 bits. And the numbers are, only those tests that build in both cases, left is base == "-O2", right is peak == "-O2 -fwrapv: 32-bits 64-bits 164.gzip 733 733 819 820 175.vpr 703 707 718 719 176.gcc 886 892 977 955 181.mcf 527 527 415 414 186.crafty 877 893 1345 1351 253.perlbmk 941 944 971 975 254.gap 769 759 784 782 255.vortex 1094 1086 1153 1122 256.bzip2 708 707 786 782 300.twolf 1037 1030 834 830 168.wupwise 762 755 865 829 171.swim 695 679 696 699 172.mgrid 395 394 741 562 173.applu 590 588 693 656 177.mesa 701 693 1055 1058 179.art 479 484 930 912 183.equake 825 834 840 808 188.ammp 716 723 877 862 200.sixtrack 446 456 434 414 Note that (for unknown reasons) peak is always ~.5% higher than base on this tester even if you compare identical compilers. So 1% wins are not really interesting. What is interesting is the higher score for crafty with -fwrapv for the 32-bits case. The rest is in the noise for 32-bits. For 64-bits, gcc itself takes a hit and so do vortex and all the SPECfp benchmarks. See especially mgrid. Gr. Steven ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-29 16:46 ` Steven Bosscher @ 2005-06-29 18:01 ` Daniel Berlin 2005-06-29 18:32 ` Steven Bosscher 2005-06-29 19:13 ` Nicholas Nethercote 0 siblings, 2 replies; 43+ messages in thread From: Daniel Berlin @ 2005-06-29 18:01 UTC (permalink / raw) To: Steven Bosscher Cc: Ulrich Weigand, gcc, Robert Dewar, Mark Mitchell, Michael Veksler, Paul Koning, gdr, nathan On Wed, 2005-06-29 at 18:46 +0200, Steven Bosscher wrote: > On Tuesday 28 June 2005 14:09, Steven Bosscher wrote: > > On Tuesday 28 June 2005 14:02, Ulrich Weigand wrote: > > > Steven Bosscher wrote: > > > > Anyway, I've started a SPEC run with "-O2" vs. "-O2 -fwrapv". Let's > > > > see how big the damage would be ;-) > > > > > > Please make sure to include a 64-bit target, where it actually makes any > > > difference. (I recall performance degradations of 20-30% in some > > > SPECfp cases from getting induction variable reduction wrong ...) > > > > Yeah, I'm testing on an AMD64 box, both 64 bits and 32 bits. > > And the numbers are, only those tests that build in both cases, > left is base == "-O2", right is peak == "-O2 -fwrapv: None of these numbers actually include real loop transformations that often take advantage of wrapping semantics, so it's not interesting. In fact, i'm surprised that the numbers are different *at all*. It's only heavy duty reordering things like vectorization, linear loop transforms, distribution, you name it, etc, that really want to know the number of iterations in a loop, etc that it makes any significant difference. So i would advise anyone arguing against turning on -fwrapv simply because it doesn't seem to hurt us at O2. And i'll again point out that the exact opposite is the default in every other compiler i'm aware of. XLC at O2 has qstrict_induction on by default (the equivalent), and warns the user when it sees a loop where it's making the assumption[1] The XLC people told me since they turned this on in 1998, they have had one real piece of code where it actually mattered, and that was a char induction variable. ICC does the same, though i don't think it bothers to warn. Open64 does the same, but no warning. Not sure about Sun CC, but i'd be very surprised if they did it. Personally, i only care about wrapping for induction variables. If you guys want to leave regular variables to do whatever, fine. But if you turn on this wrapping behavior, you have more or less given up any chance we have of performing heavy duty loop transforms on most real user code, even though the user doesn't actually give two shits about wrapping. --Dan [1] The manual points out the performance degradation using the option is quite severe. I've sent actual numbers privately to some people, but i don't want to make them public because i'm not sure the xlc folks would like it. ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-29 18:01 ` Daniel Berlin @ 2005-06-29 18:32 ` Steven Bosscher 2005-06-29 18:45 ` Robert Dewar 2005-06-29 19:13 ` Nicholas Nethercote 1 sibling, 1 reply; 43+ messages in thread From: Steven Bosscher @ 2005-06-29 18:32 UTC (permalink / raw) To: Daniel Berlin Cc: Ulrich Weigand, gcc, Robert Dewar, Mark Mitchell, Michael Veksler, Paul Koning, gdr, nathan On Wednesday 29 June 2005 20:01, Daniel Berlin wrote: > So i would advise anyone arguing against turning on -fwrapv simply > because it doesn't seem to hurt us at O2. wtf, "doesn't seem to hurt us at -O2". Look again at the 64 bits numbers! Losing 5% on the fp benchmarks is a serious regression. Even without exercising the heavy-ammo loop optimizers, -fwrapv is a serious performance-hurter. Gr. Steven ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-29 18:32 ` Steven Bosscher @ 2005-06-29 18:45 ` Robert Dewar 0 siblings, 0 replies; 43+ messages in thread From: Robert Dewar @ 2005-06-29 18:45 UTC (permalink / raw) To: Steven Bosscher Cc: Daniel Berlin, Ulrich Weigand, gcc, Mark Mitchell, Michael Veksler, Paul Koning, gdr, nathan Steven Bosscher wrote: > On Wednesday 29 June 2005 20:01, Daniel Berlin wrote: > >>So i would advise anyone arguing against turning on -fwrapv simply >>because it doesn't seem to hurt us at O2. > > > wtf, "doesn't seem to hurt us at -O2". Look again at the 64 bits > numbers! Losing 5% on the fp benchmarks is a serious regression. > Even without exercising the heavy-ammo loop optimizers, -fwrapv is > a serious performance-hurter. Still these figures are very interesting for Ada, where I am afraid the kludge we do in the front end for required overflow checking is much more expensive than these figures indicate. Of course this will be *highly* target dependent. ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-29 18:01 ` Daniel Berlin 2005-06-29 18:32 ` Steven Bosscher @ 2005-06-29 19:13 ` Nicholas Nethercote 1 sibling, 0 replies; 43+ messages in thread From: Nicholas Nethercote @ 2005-06-29 19:13 UTC (permalink / raw) To: Daniel Berlin Cc: Steven Bosscher, Ulrich Weigand, gcc, Robert Dewar, Mark Mitchell, Michael Veksler, Paul Koning, gdr, nathan On Wed, 29 Jun 2005, Daniel Berlin wrote: > So i would advise anyone arguing against turning on -fwrapv simply > because it doesn't seem to hurt us at O2. > > And i'll again point out that the exact opposite is the default in every > other compiler i'm aware of. Sorry, I couldn't parse those sentences... are you saying the -fwrapv behaviour (ie. wrap-on-signed-integer-overflow) is the default or not the default in these other compilers? > XLC at O2 has qstrict_induction on by default (the equivalent), and > warns the user when it sees a loop where it's making the assumption[1] Which assumption? > The XLC people told me since they turned this on in 1998, they have had > one real piece of code where it actually mattered, and that was a char > induction variable. > > ICC does the same, though i don't think it bothers to warn. > > Open64 does the same, but no warning. > > Not sure about Sun CC, but i'd be very surprised if they did it. > > Personally, i only care about wrapping for induction variables. If you > guys want to leave regular variables to do whatever, fine. Are you saying you don't want induction variables to have to wrap, but you don't care about non-induction variables? Sorry if I'm being dim... I think it's excellent you're discussing what other compilers do, I just can't understand what you've said as expressed :) Nick ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 11:19 ` Steven Bosscher 2005-06-28 12:03 ` Ulrich Weigand @ 2005-06-28 12:16 ` Paul Koning 2005-06-28 12:30 ` Steven Bosscher 1 sibling, 1 reply; 43+ messages in thread From: Paul Koning @ 2005-06-28 12:16 UTC (permalink / raw) To: stevenb; +Cc: gcc, dewar, mark, VEKSLER, gdr, nathan >>>>> "Steven" == Steven Bosscher <stevenb@suse.de> writes: Steven> Indeed. Frankly this "seems likely" guess confuses me. It Steven> is already well known that using unsigned types for loop Steven> counters may greatly improve the code gcc can generate for Steven> loops. With wrap-around semantics, suddenly countable loops Steven> are turned into noncountable loops, overflow can occur, Steven> dependencies may be introduced that never happen in reality, Steven> and so on. I must be missing something. Unsigned has wraparound (modulo) semantics. So if unsigned loop counters produce better code, why does making signed ints wrap cause worse code rather than better (just as good as unsigned) code? paul ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 12:16 ` Paul Koning @ 2005-06-28 12:30 ` Steven Bosscher 2005-06-28 12:35 ` Michael Veksler 0 siblings, 1 reply; 43+ messages in thread From: Steven Bosscher @ 2005-06-28 12:30 UTC (permalink / raw) To: Paul Koning; +Cc: gcc, dewar, mark, VEKSLER, gdr, nathan On Tuesday 28 June 2005 14:16, Paul Koning wrote: > >>>>> "Steven" == Steven Bosscher <stevenb@suse.de> writes: > > Steven> Indeed. Frankly this "seems likely" guess confuses me. It > Steven> is already well known that using unsigned types for loop > Steven> counters may greatly improve the code gcc can generate for > Steven> loops. With wrap-around semantics, suddenly countable loops > Steven> are turned into noncountable loops, overflow can occur, > Steven> dependencies may be introduced that never happen in reality, > Steven> and so on. > > I must be missing something. Yes. > Unsigned has wraparound (modulo) > semantics. The whole point is that it doesn't. Gr. Steven ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 12:30 ` Steven Bosscher @ 2005-06-28 12:35 ` Michael Veksler 2005-06-28 12:38 ` Steven Bosscher 0 siblings, 1 reply; 43+ messages in thread From: Michael Veksler @ 2005-06-28 12:35 UTC (permalink / raw) To: Steven Bosscher; +Cc: dewar, gcc, gdr, mark, nathan, Paul Koning Steven Bosscher <stevenb@suse.de> wrote on 28/06/2005 15:30:27: > On Tuesday 28 June 2005 14:16, Paul Koning wrote: > > > > I must be missing something. > > Yes. > > > Unsigned has wraparound (modulo) > > semantics. > > The whole point is that it doesn't. > I think that you confuse between signed and unsigned. Signed does not have modulo semantics (in GCC. The standard permits it to have modulo semantics). Michael ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 12:35 ` Michael Veksler @ 2005-06-28 12:38 ` Steven Bosscher 0 siblings, 0 replies; 43+ messages in thread From: Steven Bosscher @ 2005-06-28 12:38 UTC (permalink / raw) To: Michael Veksler; +Cc: dewar, gcc, gdr, mark, nathan, Paul Koning On Tuesday 28 June 2005 14:34, Michael Veksler wrote: > Steven Bosscher <stevenb@suse.de> wrote on 28/06/2005 15:30:27: > > On Tuesday 28 June 2005 14:16, Paul Koning wrote: > > > I must be missing something. > > > > Yes. > > > > > Unsigned has wraparound (modulo) > > > semantics. > > > > The whole point is that it doesn't. > > I think that you confuse between signed and unsigned. > Signed does not have modulo semantics (in GCC. > The standard permits it to have modulo semantics). Hmmyes. Silly me. Gr. Steven ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 3:06 ` Mark Mitchell 2005-06-28 3:49 ` Gabriel Dos Reis 2005-06-28 10:08 ` Robert Dewar @ 2005-06-28 16:54 ` Joe Buck 2005-06-28 17:02 ` Mark Mitchell 2 siblings, 1 reply; 43+ messages in thread From: Joe Buck @ 2005-06-28 16:54 UTC (permalink / raw) To: Mark Mitchell; +Cc: Michael Veksler, Paul Koning, gcc, gdr, nathan On Mon, Jun 27, 2005 at 08:05:48PM -0700, Mark Mitchell wrote: > Michael Veksler wrote: > > >>Most programmers "know" that arithmetic is modulo wordsize. And those few > >>who know the right answer (only unsigned arithmetic is modulo) will > >>from time to time slip up and omit the "unsigned" keyword in their > >>declarations. > > I agree. > > Although the standard clearly makes signed overflow undefined, I think > it would be better if GCC defined it to be modulo arithmetic. The > degree to which that would result in inferior code seems likely to be > somewhat small, and the amount of user confusion we would eliminate, and > the number of programs that would not break with GCC, even though they > work with other compilers, seems likely to be high. I strongly object. I don't think we should give the user any such promise, and if we do give such a promise, we will never catch icc. The main problem is that we will no longer be able to optimize many loops. Here's a simple example. int blah(int); int func(int a, int b) { if (b >= 0) { int c = a + b; int count = 0; for (int i = a; i <= c; i++) count++; blah(count); } } Here, if integer overflow is undefined, this is just int func(int a, int b) { if (b >= 0) { blah(b+1); } } But if integer overflow is defined to wrap, then if a+b overflows, count will be 0. We could still simplify the loop, but we are forced to emit worse code. That said, it is certainly true that if we just have int add(int a, int b) { return a + b; } and the add function is compiled separately, and the target's integer addition instruction wraps, we would get modulo. ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 16:54 ` Joe Buck @ 2005-06-28 17:02 ` Mark Mitchell 2005-06-28 17:08 ` Daniel Berlin 2005-06-28 17:46 ` Theodore Papadopoulo 0 siblings, 2 replies; 43+ messages in thread From: Mark Mitchell @ 2005-06-28 17:02 UTC (permalink / raw) To: Joe Buck; +Cc: Michael Veksler, Paul Koning, gcc, gdr, nathan Joe Buck wrote: > I don't think we should give the user any such promise, and if we do > give such a promise, we will never catch icc. The main problem is that > we will no longer be able to optimize many loops. It's entirely possible that I was naive in assuming that this wouldn't have a big optimization impact. Reiterating my response to Daniel, if it is in fact the case that this is a major loss for optimization, then I would have to retract my claim. > Here's a simple example. > > int blah(int); > > int func(int a, int b) { > if (b >= 0) { > int c = a + b; > int count = 0; > for (int i = a; i <= c; i++) > count++; > blah(count); > } > } Yes, I understand. I just didn't imagine that these kinds of opportunities came up very often. (Perhaps that's because I routinely write code that can't be compiled well, and so don't think about this situation. In particular, I often use unsigned types when the underlying quantity really is always non-negative, and I'm saddened to learn that doing that would result in inferior code.) -- Mark Mitchell CodeSourcery, LLC mark@codesourcery.com (916) 791-8304 ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 17:02 ` Mark Mitchell @ 2005-06-28 17:08 ` Daniel Berlin 2005-06-28 18:12 ` Mark Mitchell 2005-06-28 17:46 ` Theodore Papadopoulo 1 sibling, 1 reply; 43+ messages in thread From: Daniel Berlin @ 2005-06-28 17:08 UTC (permalink / raw) To: Mark Mitchell; +Cc: Joe Buck, Michael Veksler, Paul Koning, gcc, gdr, nathan On Tue, 28 Jun 2005, Mark Mitchell wrote: > Joe Buck wrote: > >> I don't think we should give the user any such promise, and if we do >> give such a promise, we will never catch icc. The main problem is that >> we will no longer be able to optimize many loops. > > It's entirely possible that I was naive in assuming that this wouldn't have a > big optimization impact. Reiterating my response to Daniel, if it is in fact > the case that this is a major loss for optimization, then I would have to > retract my claim. I've got some notes in to various XLC people to get info if they have actual numbers. However, in the meanwhile, the manual actually says it causes very severe performance degradation, and that you are better off doing -O2 and -qnostrict_induction than -O3 + qstrict_induction, if it makes your code work. (which means it says you are better off turning off high level loop opts like interchange/fusion/etc and still letting lower level stuff make the assumption, than you are turning off the assumption and turning on high level loop opts). I imagine it very badly degrades your ability to move things out of loops, perform any kind of cache transformations, etc. and it's just so common to write signed loops without caring about overflow that i'd guess you lose 90% of your opportunities to do anything useful or cool with the loop. ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 17:08 ` Daniel Berlin @ 2005-06-28 18:12 ` Mark Mitchell 0 siblings, 0 replies; 43+ messages in thread From: Mark Mitchell @ 2005-06-28 18:12 UTC (permalink / raw) To: Daniel Berlin; +Cc: Joe Buck, Michael Veksler, Paul Koning, gcc, gdr, nathan Daniel Berlin wrote: > > > On Tue, 28 Jun 2005, Mark Mitchell wrote: > >> Joe Buck wrote: >> >>> I don't think we should give the user any such promise, and if we do >>> give such a promise, we will never catch icc. The main problem is that >>> we will no longer be able to optimize many loops. >> >> >> It's entirely possible that I was naive in assuming that this wouldn't >> have a big optimization impact. Reiterating my response to Daniel, if >> it is in fact the case that this is a major loss for optimization, >> then I would have to retract my claim. > > > I've got some notes in to various XLC people to get info if they have > actual numbers. > > However, in the meanwhile, the manual actually says it causes very > severe performance degradation, and that you are better off doing -O2 > and -qnostrict_induction than -O3 + qstrict_induction, if it makes your > code work. OK. I'll withdraw my statement, then. And, so, I now think that <limits> needs to change is_modulo back to false. -- Mark Mitchell CodeSourcery, LLC mark@codesourcery.com (916) 791-8304 ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 17:02 ` Mark Mitchell 2005-06-28 17:08 ` Daniel Berlin @ 2005-06-28 17:46 ` Theodore Papadopoulo 1 sibling, 0 replies; 43+ messages in thread From: Theodore Papadopoulo @ 2005-06-28 17:46 UTC (permalink / raw) To: Mark Mitchell; +Cc: Joe Buck, Michael Veksler, Paul Koning, gcc, gdr, nathan On Tue, 2005-06-28 at 10:02 -0700, Mark Mitchell wrote: > Joe Buck wrote: > > > > int blah(int); > > > > int func(int a, int b) { > > if (b >= 0) { > > int c = a + b; > > int count = 0; > > for (int i = a; i <= c; i++) > > count++; > > blah(count); > > } > > } > > Yes, I understand. > > I just didn't imagine that these kinds of opportunities came up very > often. (Perhaps that's because I routinely write code that can't be > compiled well, and so don't think about this situation. In particular, > I often use unsigned types when the underlying quantity really is always > non-negative, and I'm saddened to learn that doing that would result in > inferior code.) The real question is how often anyone is writing a loop (with an unsigned of signed index) that is designed to wrap.... So maybe at the end of this lengthy discussion, one decision to make is introduce a flag -floop-index-may-wrap and assume by default that loop indices never, ever go outside of the range of values allowed by the underlying type (or the opposite if backward compatibility is judged more important). A few months ago, problems with integers that may possibly wrap was found to be a major penalty for STL vectors because loops over iterators were never unrolled (because the increment on pointers is 4 and the unroller was not able to decide the finiteness of a loop in such a case). Zdenek (I hope my memory does not misattribute the work) corrected that for increments that are powers of 2 (in which case it is easier to decide whether the loop is finite or not). The fact remains that the loop unroller currently must be pessimist in many cases assuming that the loop induction variable may wrap ending up in an infinite loop.... ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-27 14:36 ` Nathan Sidwell 2005-06-27 14:47 ` Paul Koning @ 2005-06-27 15:17 ` Gabriel Dos Reis 2005-06-30 20:53 ` Kai Henningsen 1 sibling, 1 reply; 43+ messages in thread From: Gabriel Dos Reis @ 2005-06-27 15:17 UTC (permalink / raw) To: Nathan Sidwell; +Cc: Michael Veksler, gcc Nathan Sidwell <nathan@codesourcery.com> writes: | Gabriel Dos Reis wrote: | | > But a compiler could define them to be modulo -- that is the whole | > point. The paragraph does not say they don't "modulo". | | of course it could do so, but then to be useful it should document it, | and it would be an extension. We're in violent agreement there. | > | 18.2.1.2/57 claims is_modulo is true 'for signed types on most | > | machines'. Such an assertion is false when optimizations rely the | > | undefinedness of signed overflow. A DR should probably be filed | > | (maybe one is, I'm not at all familiar with library DRs). | > Well, undefined behaviour does not mean unconditional hell or evil. | > It is just behaviour left up to the compiler to whatever it wants. | | correct. However the std *itself* says in one place 'this is | undefined' and in another place 'this is usually modulo'. I find that | confusing at best. well, you could send a message to -lib. The standard does not prescribe "this is always true", so saying "it is usually true" does not contradict previous statement that it is undefined -- it is just as vague. | > And all useful programs we write rely on undefined behaviour of one | > sort or the other, starting with GCC. In the case of | | They do? Well, just check out GCC for starters :-) | I thought they usually relied on implementation defined, | documented extensions or were part of the implementation. Now I'm | sure you'll prove me wrong in some way or other, but please stick to | the point -- do real important programs that must not break and cannot | be changed rely on signed modulo behaviour? I don't think that is a useful question, because first we would need to agree on what is considered "real important programs" when and where they could or should be changed. I think what we should address is (1) Can we make it useful, not just left to random blue moon? (2) can it be done in a reasonable way? Just saying, "ah but the standard sys it is undefined behaviour" does nto sound to me as a satisfying answer. It one takes the standards literally, then GCC is not required to be useful; just conformant. But then you just need "cp /bin/sh gcc" and appropriate documentation. | > When RTH helped cleanup the numeric_limits implementation in September | > 2002, he made a very good point (which I held to be true, since | > obviously he is The Middle-end and Back-end Guy) | > http://gcc.gnu.org/ml/libstdc++/2002-09/msg00207.html | | thanks for that. I was under the impression that some of the loop | optimizers relied on the fact that iterating over a signed type did | not do odd modulo related things. yes, but in the case of the *concrete* targets supported by GCC, do you know of any that "do odd modulo related things"? GCC's documentation GCC/gcc/doc/implement-c.texi says: GCC supports only two's complement integer types, and all bit patterns are ordinary values. And, in the case of 2's complement, the relation between the min, max of signed integer type is well-defined. It is not left up to the will of the Go'aulds. | Indeed this comment in loop.c | concerning BIVs leads me to believe we already fail to honor the | is_modulo value | | Note that treating the entire pseudo as a BIV will result in making | simple increments to any GIVs based on it. However, if the variable | overflows in its declared mode but not its promoted mode, the result will | be incorrect. This is acceptable if the variable is signed, since | overflows in such cases are undefined, but not if it is unsigned, since | those overflows are defined. So we only check for SIGN_EXTEND and | not ZERO_EXTEND. As I said earlier, we do have a consistency problem in GCC and this is an area where we would be nore useful in improving things. I do not consider lengthy discussions exemplified bt late VRP thing very useful. It does not really help much arguing "but it is undefined behaviour". Yes, we can define it to something useful when we can (and we should). | Anyway, this doesn't answer Michael's question. He asked whether C | and C++ differ in this regard. The answer is the standards are the | same, and the implementation is the same (because it is the same | backend). With the difference that C++ gives users a hook to ask for more information. And that makes a real difference -- as opposed to a mere "undefined behaviour". | So, if whatever optimizations he is turning on change the | behaviour rth cited, then limits should change too. As I said, I'm for consistent semantics. The question remains as whether we should reflect reality -- the arithmetic is modulo -- or just leave in the abstract tower of "standard says it is undefined behaviour". | I don't particularly care what behaviour is chosen, except that | | 1) C and C++ implementations should behave the same way | | 2) we should pick the behaviour that leads to better code generation in real life. We can generate better code if we don't care about semantics and usefulness. Just compile the program as if it was int main() { } | 3) if modulo behaviour is chosen, it should be well documented in a | place more prominant than type_traits<int>::is_modulo. I'm all for more documentation and if you could help there, it would be appreciated. -- Gaby ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-27 15:17 ` Gabriel Dos Reis @ 2005-06-30 20:53 ` Kai Henningsen 0 siblings, 0 replies; 43+ messages in thread From: Kai Henningsen @ 2005-06-30 20:53 UTC (permalink / raw) To: gcc gdr@integrable-solutions.net (Gabriel Dos Reis) wrote on 27.06.05 in <m38y0vzv6q.fsf@uniton.integrable-solutions.net>: > Nathan Sidwell <nathan@codesourcery.com> writes: > > | Gabriel Dos Reis wrote: > | > | > But a compiler could define them to be modulo -- that is the whole > | > point. The paragraph does not say they don't "modulo". > | > | of course it could do so, but then to be useful it should document it, > | and it would be an extension. > > We're in violent agreement there. I think there are actually two different interesting properties here. One is that operations on signed integers can or can not do modulo arithmetic. The other is that for control flow purposes, the compiler can or can not assume that no such overflow actually happens. I think it might be useful to handle these separately - that is, have one set of flags handling modulo behaviour (-frapv, -ftrapv, neither, possibly others) and a different set for specifying control flow assumptions (-fassume-no-wraps, -f-no-assume-no-wraps). -fassume-no-wraps would then allow the compiler to take control flow shortcuts based on the assumption that no overflow actually happens, and -fno-assume-no-wraps would guarantee that control flow handles all possible overflow cases. I don't think it would make sense to specifically call out loops here. We've already seen an example where the actual difference happens outside the loop. It might be a little tricky to get the combination of -fassume-no-wraps and -fwrapv/-ftrapv right. Or not, I wouldn't know. In any case, especially the -ftrapv variant seems useful (assume for control flow that no overflows happen, but if they do happen, trap). It seems to me that most C programs will probably want -f-no-assume and neither wrapv option. MfG Kai ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics?
@ 2005-06-27 14:39 Morten Welinder
2005-06-27 15:21 ` Gabriel Dos Reis
0 siblings, 1 reply; 43+ messages in thread
From: Morten Welinder @ 2005-06-27 14:39 UTC (permalink / raw)
To: gcc
| signed types are undefined on overflow. [5/5] and [3.9.1/2,3]
> But a compiler could define them to be modulo -- that is the whole
> point. The paragraph does not say they don't "modulo".
True, but you are going to have to deal with the run-time version of
(int)0x80000000 / -1
which is unpleasant in the sense that Intel processors will trap and not
do anything modulo-like.
Morten
^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-27 14:39 Morten Welinder @ 2005-06-27 15:21 ` Gabriel Dos Reis 0 siblings, 0 replies; 43+ messages in thread From: Gabriel Dos Reis @ 2005-06-27 15:21 UTC (permalink / raw) To: Morten Welinder; +Cc: gcc Morten Welinder <mwelinder@gmail.com> writes: | | signed types are undefined on overflow. [5/5] and [3.9.1/2,3] | | > But a compiler could define them to be modulo -- that is the whole | > point. The paragraph does not say they don't "modulo". | | True, but you are going to have to deal with the run-time version of | | (int)0x80000000 / -1 | | which is unpleasant in the sense that Intel processors will trap and not | do anything modulo-like. If such things really yields undefined behaviour on Intel's then numeric_limits<> for Intel's should be changed accoordingly. It does not imply that numeric_limits<>::is_modulo is false for all targets supported by GCC. -- Gaby ^ permalink raw reply [flat|nested] 43+ messages in thread
[parent not found: <OF0E4366CA.5D54868B-ON4325702E.0036D351-4325702E.003973C5@il.ibm.com>]
[parent not found: <m3k6keeibo.fsf@uniton.integrable-solutions.net>]
* Re: Do C++ signed types have modulo semantics? [not found] ` <m3k6keeibo.fsf@uniton.integrable-solutions.net> @ 2005-06-28 13:29 ` Nathan Sidwell 2005-06-28 13:59 ` Gabriel Dos Reis 0 siblings, 1 reply; 43+ messages in thread From: Nathan Sidwell @ 2005-06-28 13:29 UTC (permalink / raw) To: Gabriel Dos Reis Cc: Michael Veksler, Daniel Berlin, Mark Mitchell, Paul Koning, gcc mailing list Gabriel Dos Reis wrote: > Michael Veksler <VEKSLER@il.ibm.com> writes: > > [...] > > | The code is not very simple, and different codes will get optimized > | differently. > | The user will have to learn how to write this piece of code differently for > | each > | processor to have best results. > | > | int wrap_sum(int a, int b) > | { > | if ( (a<0) != (b<0)) > | return a+b; // Different sign, no overflow possible. > | unsigned sum = (unsigned) a + b; > | if (sum <= MAX_INT) > | return sum; > | sum -= MIN_INT; > | if (sum > MAX_INT) // can be eliminated for 2's complement > | abort(); // oops > | return (int)sum + MIN_INT; > | } > | > | It does not look too good optimization-wise. > > Thanks for providing this example. This is the sort of thing I > faced. With pipeline process, it does harm. Please explain why int wrap_sum (int a, int b) { return (int) ((unsigned)a + (unsigned)b)); } is unacceptable (provided we're on the standard 2's complement machine where the mapping between negative ints and unsigned is *implementation defined* to be the sane mapping, which I might point out you've already assumed in the wrap_sum I quoted). nathan and whoever silently removed gcc@gcc.gnu.org, shame on you -- Nathan Sidwell :: http://www.codesourcery.com :: CodeSourcery LLC nathan@codesourcery.com :: http://www.planetfall.pwp.blueyonder.co.uk ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 13:29 ` Nathan Sidwell @ 2005-06-28 13:59 ` Gabriel Dos Reis 2005-06-28 14:05 ` Nathan Sidwell 2005-06-28 14:05 ` Andrew Pinski 0 siblings, 2 replies; 43+ messages in thread From: Gabriel Dos Reis @ 2005-06-28 13:59 UTC (permalink / raw) To: Nathan Sidwell Cc: Michael Veksler, Daniel Berlin, Mark Mitchell, Paul Koning, gcc mailing list Nathan Sidwell <nathan@codesourcery.com> writes: | Gabriel Dos Reis wrote: | > Michael Veksler <VEKSLER@il.ibm.com> writes: | > [...] | > | The code is not very simple, and different codes will get optimized | > | differently. | > | The user will have to learn how to write this piece of code differently for | > | each | > | processor to have best results. | > | | int wrap_sum(int a, int b) | > | { | > | if ( (a<0) != (b<0)) | > | return a+b; // Different sign, no overflow possible. | > | unsigned sum = (unsigned) a + b; | > | if (sum <= MAX_INT) | > | return sum; | > | sum -= MIN_INT; | > | if (sum > MAX_INT) // can be eliminated for 2's complement | > | abort(); // oops | > | return (int)sum + MIN_INT; | > | } | > | | It does not look too good optimization-wise. | > Thanks for providing this example. This is the sort of thing I | > faced. With pipeline process, it does harm. | | Please explain why | int wrap_sum (int a, int b) | { | return (int) ((unsigned)a + (unsigned)b)); | } | is unacceptable Notice that in your rendition you're assuming that you can convert any unsigned value > INT_MAX to a int without invoking undefined behaviour. Thus the question is whether you're accepting that as documented behaviour of GCC, and if so, then I'm interested in which ways it would differs from saying that is_modulo is true. That is useful for improving over the current situation, may I point out. | (provided we're on the standard 2's complement machine | where the mapping between negative ints and unsigned is | *implementation defined* to be the sane mapping, which I might point | out you've already assumed in the wrap_sum I quoted). | | nathan | | and whoever silently removed gcc@gcc.gnu.org, shame on you I don't see why you should put shame on Daniel Berlin for having sent a private useful notice. -- Gaby ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 13:59 ` Gabriel Dos Reis @ 2005-06-28 14:05 ` Nathan Sidwell 2005-06-28 14:05 ` Andrew Pinski 1 sibling, 0 replies; 43+ messages in thread From: Nathan Sidwell @ 2005-06-28 14:05 UTC (permalink / raw) To: Gabriel Dos Reis Cc: Michael Veksler, Daniel Berlin, Mark Mitchell, Paul Koning, gcc mailing list Gabriel Dos Reis wrote: > Nathan Sidwell <nathan@codesourcery.com> writes: > > | Gabriel Dos Reis wrote: > | > Michael Veksler <VEKSLER@il.ibm.com> writes: > | > [...] > | > | The code is not very simple, and different codes will get optimized > | > | differently. > | > | The user will have to learn how to write this piece of code differently for > | > | each > | > | processor to have best results. > | > | | int wrap_sum(int a, int b) > | > | { > | > | if ( (a<0) != (b<0)) > | > | return a+b; // Different sign, no overflow possible. > | > | unsigned sum = (unsigned) a + b; > | > | if (sum <= MAX_INT) > | > | return sum; > | > | sum -= MIN_INT; > | > | if (sum > MAX_INT) // can be eliminated for 2's complement > | > | abort(); // oops > | > | return (int)sum + MIN_INT; > | > | } > | > | | It does not look too good optimization-wise. > | > Thanks for providing this example. This is the sort of thing I > | > faced. With pipeline process, it does harm. > | > | Please explain why > | int wrap_sum (int a, int b) > | { > | return (int) ((unsigned)a + (unsigned)b)); > | } > | is unacceptable > > Notice that in your rendition you're assuming that you can convert any > unsigned value > INT_MAX to a int without invoking undefined behaviour. > > Thus the question is whether you're accepting that as documented > behaviour of GCC, and if so, then I'm interested in which ways it > would differs from saying that is_modulo is true. That is useful for > improving over the current situation, may I point out. I give up. nathan -- Nathan Sidwell :: http://www.codesourcery.com :: CodeSourcery LLC nathan@codesourcery.com :: http://www.planetfall.pwp.blueyonder.co.uk ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 13:59 ` Gabriel Dos Reis 2005-06-28 14:05 ` Nathan Sidwell @ 2005-06-28 14:05 ` Andrew Pinski 2005-06-28 14:13 ` Gabriel Dos Reis 1 sibling, 1 reply; 43+ messages in thread From: Andrew Pinski @ 2005-06-28 14:05 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: Nathan Sidwell, gcc mailing list On Jun 28, 2005, at 9:58 AM, Gabriel Dos Reis wrote: > Notice that in your rendition you're assuming that you can convert any > unsigned value > INT_MAX to a int without invoking undefined behaviour. If you read Nathan's mail correctly, the cast is implementation defined and not undefined behavior so your argument does not work. Quote from Nathan's mail (the emphases are not mine but Nathan's which means he wanted to you to read that part and not say it was undefined behavior): > (provided we're on the standard 2's complement machine where the > mapping between negative ints and unsigned is *implementation defined* > to be the sane mapping, which I might point out you've already assumed > in the wrap_sum I quoted). -- Pinski ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 14:05 ` Andrew Pinski @ 2005-06-28 14:13 ` Gabriel Dos Reis 2005-06-28 15:30 ` Michael Veksler 0 siblings, 1 reply; 43+ messages in thread From: Gabriel Dos Reis @ 2005-06-28 14:13 UTC (permalink / raw) To: Andrew Pinski; +Cc: Nathan Sidwell, gcc mailing list Andrew Pinski <pinskia@physics.uc.edu> writes: | On Jun 28, 2005, at 9:58 AM, Gabriel Dos Reis wrote: | | > Notice that in your rendition you're assuming that you can convert any | > unsigned value > INT_MAX to a int without invoking undefined behaviour. | | | | If you read Nathan's mail correctly, the cast is implementation defined | and not undefined behavior so your argument does not work. I stand corrected! -- Gaby ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 14:13 ` Gabriel Dos Reis @ 2005-06-28 15:30 ` Michael Veksler 2005-06-28 15:49 ` Nathan Sidwell 2005-06-28 15:55 ` Gabriel Dos Reis 0 siblings, 2 replies; 43+ messages in thread From: Michael Veksler @ 2005-06-28 15:30 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: gcc mailing list, Nathan Sidwell, Andrew Pinski Gabriel Dos Reis wrote on 28/06/2005 17:12:43: > Andrew Pinski <pinskia@physics.uc.edu> writes: > > | On Jun 28, 2005, at 9:58 AM, Gabriel Dos Reis wrote: > | > | > Notice that in your rendition you're assuming that you can convert any > | > unsigned value > INT_MAX to a int without invoking undefined behaviour. > | > | > | > | If you read Nathan's mail correctly, the cast is implementation defined > | and not undefined behavior so your argument does not work. > > I stand corrected! > So what does gcc gives for (int) (MAX_INT+1U)? Maybe it is constrained such that (int)(unsigned)a == a For 1's complement the reverse seems to be incorrect: unsigned a= 0xFFFFFFFF; // or was it 0x80000000? assert((unsigned)(int)a == a); // may fail This is because as far as I remember 0xFFFFFFFF is interpreted as -0, which then cast to unsigned as 0x00000000. This behavior seems to be undocumented (a documentation PR?). Michael ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 15:30 ` Michael Veksler @ 2005-06-28 15:49 ` Nathan Sidwell 2005-06-28 15:58 ` Michael Veksler 2005-06-28 15:55 ` Gabriel Dos Reis 1 sibling, 1 reply; 43+ messages in thread From: Nathan Sidwell @ 2005-06-28 15:49 UTC (permalink / raw) To: Michael Veksler Cc: Gabriel Dos Reis, gcc mailing list, Andrew Pinski, gcc mailing list Michael Veksler wrote: > > So what does gcc gives for (int) (MAX_INT+1U)? > Maybe it is constrained such that > (int)(unsigned)a == a > For 1's complement the reverse seems to be incorrect: > unsigned a= 0xFFFFFFFF; // or was it 0x80000000? > assert((unsigned)(int)a == a); // may fail why are you talking about one's complement in the context of gcc. From implement-c.texi @cite{Whether signed integer types are represented using sign and magnitude, two's complement, or one's complement, and whether the extraordinary value is a trap representation or an ordinary value (C99 6.2.6.2).} GCC supports only two's complement integer types, and all bit patterns are ordinary values. please stop considering non 2's complement stuff. nathan -- Nathan Sidwell :: http://www.codesourcery.com :: CodeSourcery LLC nathan@codesourcery.com :: http://www.planetfall.pwp.blueyonder.co.uk ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 15:49 ` Nathan Sidwell @ 2005-06-28 15:58 ` Michael Veksler 2005-06-28 16:07 ` Andrew Pinski 2005-06-28 16:39 ` Gabriel Dos Reis 0 siblings, 2 replies; 43+ messages in thread From: Michael Veksler @ 2005-06-28 15:58 UTC (permalink / raw) To: Nathan Sidwell; +Cc: gcc mailing list, Gabriel Dos Reis, Andrew Pinski Nathan Sidwell <nathan@codesourcery.com> wrote on 28/06/2005 18:48:26: > > why are you talking about one's complement in the context of gcc. From > implement-c.texi > > @cite{Whether signed integer types are represented using sign and magnitude, > two's complement, or one's complement, and whether the extraordinary value > is a trap representation or an ordinary value (C99 6.2.6.2).} > > GCC supports only two's complement integer types, and all bit patterns > are ordinary values. > > please stop considering non 2's complement stuff. > Sorry, did not realize this was documented this way. Is "implement-c.texi" part of the user visible documentation, or is it targeted for gcc developers? Michael ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 15:58 ` Michael Veksler @ 2005-06-28 16:07 ` Andrew Pinski 2005-06-28 16:39 ` Gabriel Dos Reis 1 sibling, 0 replies; 43+ messages in thread From: Andrew Pinski @ 2005-06-28 16:07 UTC (permalink / raw) To: Michael Veksler; +Cc: Nathan Sidwell, Gabriel Dos Reis, gcc mailing list On Jun 28, 2005, at 11:58 AM, Michael Veksler wrote: > > Sorry, did not realize this was documented this way. > Is "implement-c.texi" part of the user visible documentation, or is it > targeted for gcc developers? http://gcc.gnu.org/onlinedocs/gcc/C-Implementation.html#C-Implementation in the normal user visible documentation. -- Pinski ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 15:58 ` Michael Veksler 2005-06-28 16:07 ` Andrew Pinski @ 2005-06-28 16:39 ` Gabriel Dos Reis 1 sibling, 0 replies; 43+ messages in thread From: Gabriel Dos Reis @ 2005-06-28 16:39 UTC (permalink / raw) To: Michael Veksler; +Cc: Nathan Sidwell, gcc mailing list, Andrew Pinski Michael Veksler <VEKSLER@il.ibm.com> writes: | Nathan Sidwell <nathan@codesourcery.com> wrote on 28/06/2005 18:48:26: | | > | > why are you talking about one's complement in the context of gcc. From | > implement-c.texi | > | > @cite{Whether signed integer types are represented using sign and | magnitude, | > two's complement, or one's complement, and whether the extraordinary | value | > is a trap representation or an ordinary value (C99 6.2.6.2).} | > | > GCC supports only two's complement integer types, and all bit patterns | > are ordinary values. | > | > please stop considering non 2's complement stuff. | > | | Sorry, did not realize this was documented this way. | Is "implement-c.texi" part of the user visible documentation, or is it | targeted for gcc developers? It is targted at the user audience. An issue I raised earlier -- that still remains -- is how, pratically, that differs from the modulo semantics and the loop optimizer is not willing to make under some circumstances. -- Gaby ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 15:30 ` Michael Veksler 2005-06-28 15:49 ` Nathan Sidwell @ 2005-06-28 15:55 ` Gabriel Dos Reis 2005-06-28 16:47 ` Joseph S. Myers 1 sibling, 1 reply; 43+ messages in thread From: Gabriel Dos Reis @ 2005-06-28 15:55 UTC (permalink / raw) To: Michael Veksler; +Cc: gcc mailing list, Nathan Sidwell, Andrew Pinski Michael Veksler <VEKSLER@il.ibm.com> writes: | Gabriel Dos Reis wrote on 28/06/2005 17:12:43: | | > Andrew Pinski <pinskia@physics.uc.edu> writes: | > | > | On Jun 28, 2005, at 9:58 AM, Gabriel Dos Reis wrote: | > | | > | > Notice that in your rendition you're assuming that you can convert | any | > | > unsigned value > INT_MAX to a int without invoking undefined | behaviour. | > | | > | | > | | > | If you read Nathan's mail correctly, the cast is implementation defined | > | and not undefined behavior so your argument does not work. | > | > I stand corrected! | > | | So what does gcc gives for (int) (MAX_INT+1U)? It should give you INT_MIN. At least numeric_limits<int>::min is implemented that way (suggested by RTH). | This behavior seems to be undocumented (a documentation PR?). Yes, we should document this. In general, implementation defined aspects (and some of the undefined behaviour aspects) are missing documentation for C++ -- JSM did some work for that for C. -- Gaby ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 15:55 ` Gabriel Dos Reis @ 2005-06-28 16:47 ` Joseph S. Myers 2005-06-28 17:58 ` Gabriel Dos Reis 0 siblings, 1 reply; 43+ messages in thread From: Joseph S. Myers @ 2005-06-28 16:47 UTC (permalink / raw) To: Gabriel Dos Reis; +Cc: gcc mailing list, Nathan Sidwell On Tue, 28 Jun 2005, Gabriel Dos Reis wrote: > Yes, we should document this. In general, implementation defined > aspects (and some of the undefined behaviour aspects) are missing > documentation for C++ -- JSM did some work for that for C. Is there a convenient checklist for C++ similar to C99's Annex J.3 and J.4, or is it necessary to go through the whole standard to find what needs documenting? -- Joseph S. Myers http://www.srcf.ucam.org/~jsm28/gcc/ jsm@polyomino.org.uk (personal mail) joseph@codesourcery.com (CodeSourcery mail) jsm28@gcc.gnu.org (Bugzilla assignments and CCs) ^ permalink raw reply [flat|nested] 43+ messages in thread
* Re: Do C++ signed types have modulo semantics? 2005-06-28 16:47 ` Joseph S. Myers @ 2005-06-28 17:58 ` Gabriel Dos Reis 0 siblings, 0 replies; 43+ messages in thread From: Gabriel Dos Reis @ 2005-06-28 17:58 UTC (permalink / raw) To: Joseph S. Myers; +Cc: gcc mailing list, Nathan Sidwell "Joseph S. Myers" <joseph@codesourcery.com> writes: | On Tue, 28 Jun 2005, Gabriel Dos Reis wrote: | | > Yes, we should document this. In general, implementation defined | > aspects (and some of the undefined behaviour aspects) are missing | > documentation for C++ -- JSM did some work for that for C. | | Is there a convenient checklist for C++ similar to C99's Annex J.3 and | J.4, or is it necessary to go through the whole standard to find what | needs documenting? There is no such things as the C99's annex for C++. So, I'm afraid one would go through the entire document. I'll raise the issue so that the next C++0x has something similar. But, int the meantime, I'd try to produce a collection based on grep. -- Gaby ^ permalink raw reply [flat|nested] 43+ messages in thread
end of thread, other threads:[~2005-06-30 20:53 UTC | newest] Thread overview: 43+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2005-06-27 5:09 Do C++ signed types have modulo semantics? Michael Veksler 2005-06-27 13:02 ` Nathan Sidwell 2005-06-27 14:10 ` Gabriel Dos Reis 2005-06-27 14:36 ` Nathan Sidwell 2005-06-27 14:47 ` Paul Koning 2005-06-27 15:21 ` Michael Veksler 2005-06-28 3:06 ` Mark Mitchell 2005-06-28 3:49 ` Gabriel Dos Reis 2005-06-28 10:08 ` Robert Dewar 2005-06-28 11:19 ` Steven Bosscher 2005-06-28 12:03 ` Ulrich Weigand 2005-06-28 12:09 ` Steven Bosscher 2005-06-29 16:46 ` Steven Bosscher 2005-06-29 18:01 ` Daniel Berlin 2005-06-29 18:32 ` Steven Bosscher 2005-06-29 18:45 ` Robert Dewar 2005-06-29 19:13 ` Nicholas Nethercote 2005-06-28 12:16 ` Paul Koning 2005-06-28 12:30 ` Steven Bosscher 2005-06-28 12:35 ` Michael Veksler 2005-06-28 12:38 ` Steven Bosscher 2005-06-28 16:54 ` Joe Buck 2005-06-28 17:02 ` Mark Mitchell 2005-06-28 17:08 ` Daniel Berlin 2005-06-28 18:12 ` Mark Mitchell 2005-06-28 17:46 ` Theodore Papadopoulo 2005-06-27 15:17 ` Gabriel Dos Reis 2005-06-30 20:53 ` Kai Henningsen 2005-06-27 14:39 Morten Welinder 2005-06-27 15:21 ` Gabriel Dos Reis [not found] <OF0E4366CA.5D54868B-ON4325702E.0036D351-4325702E.003973C5@il.ibm.com> [not found] ` <m3k6keeibo.fsf@uniton.integrable-solutions.net> 2005-06-28 13:29 ` Nathan Sidwell 2005-06-28 13:59 ` Gabriel Dos Reis 2005-06-28 14:05 ` Nathan Sidwell 2005-06-28 14:05 ` Andrew Pinski 2005-06-28 14:13 ` Gabriel Dos Reis 2005-06-28 15:30 ` Michael Veksler 2005-06-28 15:49 ` Nathan Sidwell 2005-06-28 15:58 ` Michael Veksler 2005-06-28 16:07 ` Andrew Pinski 2005-06-28 16:39 ` Gabriel Dos Reis 2005-06-28 15:55 ` Gabriel Dos Reis 2005-06-28 16:47 ` Joseph S. Myers 2005-06-28 17:58 ` Gabriel Dos Reis
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).