Re: Do C++ signed types have modulo semantics?

Re: Do C++ signed types have modulo semantics?

[Nathan Sidwell]

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

Re: Do C++ signed types have modulo semantics?

[Gabriel Dos Reis]

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

Re: Do C++ signed types have modulo semantics?

[Andrew Pinski]

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

Re: Do C++ signed types have modulo semantics?

[Nathan Sidwell]

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

Re: Do C++ signed types have modulo semantics?

[Gabriel Dos Reis]

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

Re: Do C++ signed types have modulo semantics?

[Michael Veksler]

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

Re: Do C++ signed types have modulo semantics?

[Nathan Sidwell]

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

Re: Do C++ signed types have modulo semantics?

[Gabriel Dos Reis]

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

Re: Do C++ signed types have modulo semantics?

[Michael Veksler]

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

Re: Do C++ signed types have modulo semantics?

[Andrew Pinski]

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

Re: Do C++ signed types have modulo semantics?

[Gabriel Dos Reis]

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

Re: Do C++ signed types have modulo semantics?

[Joseph S. Myers]

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)

Re: Do C++ signed types have modulo semantics?

[Gabriel Dos Reis]

"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

Re: Do C++ signed types have modulo semantics?

[Kai Henningsen]

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

Re: Do C++ signed types have modulo semantics?

[Nicholas Nethercote]

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

Re: Do C++ signed types have modulo semantics?

[Robert Dewar]

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.

Re: Do C++ signed types have modulo semantics?

[Steven Bosscher]

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

Re: Do C++ signed types have modulo semantics?

[Daniel Berlin]

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.

Re: Do C++ signed types have modulo semantics?

[Steven Bosscher]

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

Re: Do C++ signed types have modulo semantics?

[Mark Mitchell]

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

Re: Do C++ signed types have modulo semantics?

[Theodore Papadopoulo]

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

Re: Do C++ signed types have modulo semantics?

[Daniel Berlin]

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.

Re: Do C++ signed types have modulo semantics?

[Mark Mitchell]

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

Re: Do C++ signed types have modulo semantics?

[Joe Buck]

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.

Re: Do C++ signed types have modulo semantics?

[Steven Bosscher]

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
  

Re: Do C++ signed types have modulo semantics?

[Michael Veksler]

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

Re: Do C++ signed types have modulo semantics?

[Steven Bosscher]

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

Re: Do C++ signed types have modulo semantics?

[Paul Koning]

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

Re: Do C++ signed types have modulo semantics?

[Steven Bosscher]

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

Re: Do C++ signed types have modulo semantics?

[Ulrich Weigand]

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

Re: Do C++ signed types have modulo semantics?

[Steven Bosscher]

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

Re: Do C++ signed types have modulo semantics?

[Robert Dewar]

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.

Re: Do C++ signed types have modulo semantics?

[Gabriel Dos Reis]

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

Re: Do C++ signed types have modulo semantics?

[Mark Mitchell]

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

Re: Do C++ signed types have modulo semantics?

[Gabriel Dos Reis]

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

Re: Do C++ signed types have modulo semantics?

[Michael Veksler]

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

Re: Do C++ signed types have modulo semantics?

[Gabriel Dos Reis]

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

Re: Do C++ signed types have modulo semantics?

[Paul Koning]

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

Re: Do C++ signed types have modulo semantics?

[Morten Welinder]

| 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

Re: Do C++ signed types have modulo semantics?

[Nathan Sidwell]

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

Re: Do C++ signed types have modulo semantics?

[Gabriel Dos Reis]

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

Re: Do C++ signed types have modulo semantics?

[Nathan Sidwell]

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

Do C++ signed types have modulo semantics?

[Michael Veksler]

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