Integer arithmetic when overflow exists

[Alf P. Steinbach]

On 09/10/13 13:50, (e-mail address removed) wrote:

On Wednesday, October 9, 2013 1:29:56 PM UTC+2, David Brown wrote:

On 09/10/13 00:49, (e-mail address removed) wrote:

A compiler that yields unpredictable (lack of) effects for ordinary
code, is simply ... unpredictable.

Not a good thing, regardless of the users.

And let's face: not every C++ programmer is a language lawyer.

A C or C++ programmer who writes code without a defined meaning, but
expects the compiler to read his mind for what he wants, has a lot to
learn.

That's totally irrelevant, a slur.
Do quote the alleged "code without a defined meaning".

[snipped pages of further misrepresentation and innuendo]

My post was not meant to be a slur or to cause annoyance of any sort. I
am sorry you took it that way.

No quote of the alleged "code without a defined meaning".

Since there was no such.

I.e. your claim of being sorry can only refer to being caught.

I am still lost here.

I said that a programmer who writes code without a defined meaning has a
lot to learn. At no point did I say /you/ wrote such code, or that
/you/ "have a lot to learn".

That sounds a bit far fetched, like a thief caught red-handed with the
house's silver cutlery and denying that he was at all intending to take
it out of the house.

But it happens I have occasionally written code with UB (apparently you
don't have enough experience to have done that), and moreover I do have
a lot to learn, and I hope I will continue to learn for a long time...

However, no matter whether I'm dumb or smart, have lots to learn or not,
that does not help the reputation of gcc as being rather perverse and
impractical in its exploitation of formal loop-holes.

And using such sly arguments certainly does not help your reputation.

I certainly can't quote code that has not been posted
Right.


[snip]

This pretends to be arguing against something I have written.

It is at best a misrepresentation.

It is either something you agree with, in which case write "Yes", or it
is something you /disagree/ with - in which case try to explain why.

The context indicates that your explanation (?) addresses something I
have written -- that it somehow corrects or teaches.

In that most natural interpretation, as correction or teaching, it's
false, a statement that only misleads.

I have not written anything that could make you doubt I'm unaware of the
standards.

On the contrary, in my answer to the OP, first in this thread, I
referred to "the formal UB for overflow" [of signed arithmetic].

You replied to that.

Therefore, you can't be unaware that I'm well aware of the C++ standard
(and elsewhere in this thread it's shown that you aren't, with respect
to the requirements on "main", but that you do know a bit about the C
standard, which I happily learned from). And so the statement is an
attempt to make others believe something that you /know/ is false.

It also has an interpretation where it's literally true but meaningless,
like a tautology (did you know, a definition is a definition), but I
think that no-one of sound mind could offer that as argument for or
against anything.

In short, like the first comment that you now say was intended to just
point out the existence of programmers and that every programmer has a
lot to learn, the second comment, which you now say was just intended to
point out the existence of standards, is nothing but deception.


- Alf

 

[Alf P. Steinbach]

<snipping the extras, and skipping to the relevant point>

I know fine that you understand that signed overflow is undefined
behaviour - that has never been questioned.
Thanks.


What I /do/ question is your belief that it is better to define it as
modular arithmetic, and that gcc is uniquely and intentionally perverse
in not following that idea.

Well those are two separate issues.


(1)
Regarding the first issue, it's this: is it as of 2013 advantageous in
some way to DEFINE C++ signed arithmetic as modulo arithmetic?

In my opinion yes. I wrote thusly in this group about that in 2004,
https://groups.google.com/d/msg/comp.lang.c++/E6xhw_YN97c/xDuAa5AXbkMJ

The current UB prevents programs from checking for error and from
utilizing the overflow behavior, in a formally portable manner.

That's far worse and far more concrete than the extremely marginal and
hypothetical possibility of some error-detecting implementation, which
AFAIK does not exist (if it had some utility, presumably it would exist).

So the argument about allowing an implementation to treat overflow as
error is a fallacy.

On the other hand, the thread in [comp.std.c++] showed that the
arguments in favor of standardization are not especially forceful.

And there the matter rests, I think (personally I agree with John, but
nice-to-have is not need-to-have, and standardizing existing practice
would be a break with the tradition in C++ standardization, wouldn't it?).

My reference to lack of [reliable] error checking implementation appears
to now have been voided by the clang compiler (see
http://lists.cs.uiuc.edu/pipermail/cfe-dev/2010-September/010906.html).

Also, the wording "prevents" was and is too strong, except in a
practical sense, which I probably was just assuming. Not having formally
defined modular arithmetic merely makes checking more impractical in
single-source portable code. But that's bad enough.

So I think that that 2004 argument -- for a change in the language
definition, reflecting the now universal practice -- is still
forceful, now 9 years later, for it would replace "unpredictable" with
"reliable", which in turn, of course, is exploitable.

And in addition there is the issue of disallowing counter-intuitive and
meaning-changing optimizations.


(2)
Regarding "that gcc is uniquely and intentionally perverse in not
following that idea",

NO, there is no data that I'm aware of to say that the resulting
perverseness is intentional, and

NO, the perverseness does not result from not following the idea of
changing the language rules.

Rather, as already explained, the perverseness follows from exploiting
formal UB to do the unexpected, as a kind of micro-optimization that
indicates that the programmers disregarded the effect on more important
global issues such as predictability, employing a very narrow view.

It's as if the compiler replaced "x = foo( i++, i++ )" with "x = 666;",
with no call of foo(), because that optimization -- yes it's FASTER --
is allowed by the formal UB, and if the missing call is undesired then
it's the programmer's own fault surely -- surely the programmer
intended to have the compiler "optimize" the specified call, yes?

One simply does not expect a compiler to be that UNREASONABLE. One
expects it to be reasonable and predictable. With perhaps some option
for doing very aggressive things when the need for that is great.

- Alf

 

[Öö Tiib]

(2)
Regarding "that gcc is uniquely and intentionally perverse in not
following that idea", NO, there is no data that I'm aware of to say
that the resulting perverseness is intentional, and NO, the
perverseness does not result from not following the idea of
changing the language rules.

"Uniquely" I disagree with (jokers are all around) also "perverse" is
maybe too strong but ... historically GCC team has taken steps to
implement the nasal demons (or closest acceptable thing to nasal demons)
before.

Most famous is perhaps GCC 1.17 that upon finding a #pragma directive,
attempted to launch NetHack or Rogue, or start Emacs running a simulation
of the Towers of Hanoi. http://everything2.com/title/%23pragma

 

[Alf P. Steinbach]

The order of evaluation of "x = foo(i++, i++)" is not undefined
behaviour - it is unspecified behaviour. The compiler can evaluate the
parameters in the order it wants - it can even swap the order between
calls if it wants. But it cannot change the behaviour otherwise.

You're wrong in two ways:

1. Factually.
It's "undefined", not "unspecified", which is important for
what the compiler is formally allowed to do.

2. Logic.
When you try to show that something is incorrect it does not
suffice to make an assertion. Even if that assertion sounds
pretty plausible. In other words, Herb Schildt-way = ungood.

As of C++11 the relevant language has been moved from section 5 about
expressions to section 1 about general issues, as

C++11 §1.9/15,
"If a side effect on a scalar object is unsequenced relative to either
another side effect on the same scalar object or a value computation
using the value of the same scalar object, the behavior is undefined."

In return, the compiler expects the programmer to be reasonable - and
avoid undefined behaviour.

No, the situation is vastly asymmetric, and you know that.

Try finding out why you get a funny result by setting a breakpoint on
code that has been silently removed.

The compiler, e.g. g++, SHOULD be a tool for the programmer, helping the
programmer, and not require massive efforts to learn about hidden almost
unbelievable subtleties before it can be used.

- Alf

 

[Öö Tiib]

If that joke from 20 years ago is the worst nasal demon from the gcc
developers, then I am not worried.

It is the most famous one. g++ is otherwise very useful tool and I can
easily tolerate few jokes. Apple's C++ compiler was also full of subtle
jokes. I am content with it, even been happy with it and not worried
at all. What is a day worth with zero jokes?

Correct hacker's attitude is that if you do not like something (a joke
got old) then you beat it into shape. g++ however is masterpiece there
too, it is rather fun to try and hack it.

Correct engineer's attitude is that if you do not like something then
you make better one. That has been done: Weakness of g++ diagnostics,
tendency of it to "optimize" on UB (instead of diagnosing) and
unsuitability for integration with other tools were the prime drivers
of Clang coming to be. They even say it directly on front page if
you read it carefully. http://clang.llvm.org/

So ... it is rather deep discussion you guys have picked up.

 

[Alf P. Steinbach]

I don't get what you have against g++,

Not surprising, since that has not been discussed.

A long thread about someone's denial of a single wart can make that wart
seem really really important, but in the big scheme it's still just a
wart. I think the denial is important. The wart itself, no.

It was absolutely not unexpected, because it regularly happens with
discussions of warts involving Microsoft, g++ compiler and/or Python
language, the 3 big fanboï groups.

I just fear for the thread, in some forum, involving all 3.

And so I write in my FIRST answer to David Brown, in the signature, that
I was "noting that the holiness of g++ is a religious issue".

I.e. I knew very well what would happen, I knew the (probable) resulting
length of the thread and its noise factor, and I decided, I hope
correctly, that it was best to have this over and done with.

Now, since you ask, what I have against g++ is mainly

* Very incomplete support for Windows:

- Lack of library support for the Windows API after Windows XP,
i.e. for Windows Vista, Windows 7 and Windows 8.

- Incomplete tool support for standard Windows resource data.

- Lack of tool support for Windows "COM" servers, and to some
degree Windows DLLs in general.

* Unpredictability in general:

- Too "clever" by far aggressive optimizations (e.g. current wart
discussion).

* Lagging support for the C++ standard library:

- In the old days, lacking support for wide streams and strings.

- Currently, lacking support for threading library (I think that
was just implemented, but not yet available for Windows),
regexp, etc.

That said -- because you asked -- g++ is generally very much
more standard-conforming and up to date regarding the core language
parts of the standard, than Visual C++.

So, it's a nice and often necessary #2 compiler even in Windows.

this is probably the only compiler
which guarantees the wrap-over behavior you are advocating (with the -
fwrapv flag). With other compilers one just has to guess how they behave,
and the results are probably different on different hardware (e.g. DSP).

I disagree, because this is all about the in-practice, and for the
in-practice I have not heard of ANY example of
non-modular-signed-arithmetic C++ compiler the last 10 years.

So I think we're well past that point.

If anything, it's the C++ standard what should be blamed, for letting such
basic behavior undefined. If some next version of the standard happens to
make the wrap-over mandatory, then g++ folks are well prepared, they have
already implemented the feature and can make it the default in the blink of
an eye.

Yeps.


Cheers,

- Alf

 

[Alf P. Steinbach]

gcc is a toolchain, not a library (other than the standard C and C++
libraries), and it is not a OS-specific development tool. It does not
have libraries or headers for Windows - nor does it have libraries or
headers for Linux. The difference is that Linux installations typically
have headers and libraries on-hand, so they are easy to use - while in
Windows you have nothing of the sort.

You contention that those libraries, like in my g++ installation
"libshlwapi.a" etc., don't exist, is a denial of reality.

It's insane.

Without the proper headers and import libraries the API level Windows
programs and libraries that others and I make with g++, would never
build, novices with old machines could not install Code::Blocks or
whatever g++-based IDE and go for it, so on.

You can make your statement "true" in a literal sense, like Bill
Clinton's "I did not have 'sex' with that woman!", by suitably narrowing
your definition of "gcc".

For it is most probably not the GNU gang but rather Cygwin and MinGW
folks who maintain the Windows-specific libs, and then one can choose a
suitably narrow definition of "gcc" that excludes Windows versions.

With such interpretation your statement is idiotic in context, sorry!,
just like "I did not have 'sex'".


- Alf

 

[Tobias Müller]

It's as if the compiler replaced "x = foo( i++, i++ )" with "x = 666;",
with no call of foo(), because that optimization -- yes it's FASTER -- is
allowed by the formal UB, and if the missing call is undesired then it's
the programmer's own fault surely -- surely the programmer intended to
have the compiler "optimize" the specified call, yes?

This comparison just does not hold. The above is UB in any case and it is
clear even at compile time. There is no possibility of defined behavior and
any attempt of "optimization" is worthless anyway because the programmers
intention is not clear at all. A compiler warning (or even error, if
allowed) would be sensible here.

Signed integer addition OTOH is well defined for most cases. UB is only
clear at runtime. In this case, optimizing the the well defined cases makes
sense IMO.

[...]

Tobi

 

[Alf P. Steinbach]

This comparison just does not hold. The above is UB in any case and it is
clear even at compile time. There is no possibility of defined behavior and
any attempt of "optimization" is worthless anyway because the programmers
intention is not clear at all. A compiler warning (or even error, if
allowed) would be sensible here.

Signed integer addition OTOH is well defined for most cases. UB is only
clear at runtime. In this case, optimizing the the well defined cases makes
sense IMO.

No, the signed arithmetic optimizations that are troublesome are where
the result is known at compile time, even if not obvious or visible to
the programmer.

I do not know of any optimization of the general run time behavior of
signed integer addition that come in addition to general optimizations
like replacing "i = i + 1" with an increment instruction.


Cheers & hth.,

- Alf

 

[Öö Tiib]

When you say "fun", I assume you mean the fun of the challenge? Some
parts of gcc's code base are okay, but there is a lot that is barely
comprehensible to the experts.

Exactly, that I meant with fun. Experts like challenge to not get rusty.
Especially real challenges. Unfortunately lot of people are not experts
and even experts integrating their tool-set are often impatient when the
challenge is boring and they are not in mood for games today.

I think the competition has been good for both gcc and llvm. One
obvious case is that Clang had far more helpful error messages - now the
gcc error and warning messages have had greater improvement in the past
couple of versions than for many years previously.

The competition has pushed gcc towards average taste and now it treats
developers more like users and less like targets of jokes. It is because
the average people writing C++ do not like to deal with the jokes.
They want to deal with the data structures, algorithms and communications
of their program.

 

[Tobias Müller]

No, the signed arithmetic optimizations that are troublesome are where
the result is known at compile time, even if not obvious or visible to the programmer.

I didn't say that the _optimizations_ are only visible at runtime,
optimizations are obviously always made at compile time. But this is not
restricted to constant propagation, but also symbolic optimizations that
still allow for different values at runtime.

I do not know of any optimization of the general run time behavior of
signed integer addition that come in addition to general optimizations
like replacing "i = i + 1" with an increment instruction.

x < x + 1 ==> true
x * 2 / 2 ==> x
(found here:
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html?m=1)

I don't fully understand the for-loop example on that page, but it seems to
enable various loop optimizations.

Tobi

 

[Alf P. Steinbach]

x < x + 1 ==> true
x * 2 / 2 ==> x
(found here:
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html?m=1)

Yeah, this is what we've been talking about (so, obviously known), and
no, these are not optimizations of the run time behavior.

Anyway, note well that if a C++ programmer writes

if( x < x + 1 )

then the programmer does NOT mean "if( true )".

Rather, the programmer is then exploiting platform-specific
functionality, most probably compiling with g++ code originally written
for some other compiler.

So it's just wrong to optimize that, regardless of assumptions about the
arithmetic. It certainly does not help any to optimize it. It's like,
wrong no matter how you regard it, like, always wrong, you know.

More importantly, such aggressive and non-intuitive micro-optimizations
that affect intended meaning and therefore correctness, can be TURNED ON
instead of having to be turned off.

I don't fully understand the for-loop example on that page, but it seems to
enable various loop optimizations.

It's good that you don't understand it, because the description is
fallacious and wrong. In particular, for the example

for (i = 0; i <= N; ++i) { ... }

the description "if the variable [namely 'i'] is defined to wrap around
on overflow, then the compiler must assume that the loop is possibly
infinite" is false. The author may be thinking of the case where N is
the maximum signed value, but that's easy to check for, and even easier
for the programmer to specify if e.g. loop unrolling is desired.

I can only think of one reason for writing such a blatantly false and
misleading statement, and that is a blind faith in and acceptance
gcc/clang so that the author's think-box is completely turned off.


Cheers & hth.,

- Alf

 

[Tobias Müller]

Yeah, this is what we've been talking about (so, obviously known), and
no, these are not optimizations of the run time behavior.

Anyway, note well that if a C++ programmer writes

if( x < x + 1 )

then the programmer does NOT mean "if( true )".

Rather, the programmer is then exploiting platform-specific
functionality, most probably compiling with g++ code originally written
for some other compiler.

No, writing this code literally and thus _actively_ relying on UB is just
stupid, I thought we agree on that.
I don't want to miss important optimization opportunities because of some
people writing stupid code.

So it's just wrong to optimize that, regardless of assumptions about the
arithmetic. It certainly does not help any to optimize it. It's like,
wrong no matter how you regard it, like, always wrong, you know.

No, it is essential, especially in combination with templates.
In the generic form, the optimizations are usually not possible, but in a
specific instanciation they may be important.
Similar for inlining and whole program optimization.

More importantly, such aggressive and non-intuitive micro-optimizations
that affect intended meaning and therefore correctness, can be TURNED ON
instead of having to be turned off.

They only affect the meaning of badly written code!

It's good that you don't understand it, because the description is fallacious and wrong.

Despite your experience, in this case I trust the llvm devs. Please don't
take this as a personal attack, it's not.

In particular, for the example

for (i = 0; i <= N; ++i) { ... }

the description "if the variable [namely 'i'] is defined to wrap around
on overflow, then the compiler must assume that the loop is possibly
infinite" is false. The author may be thinking of the case where N is the
maximum signed value, but that's easy to check for, and even easier for
the programmer to specify if e.g. loop unrolling is desired.

I hope you don't expect me to annotate my code with all desired
optimizations.
The test if N == INT_MAX would still have to be done at runtime and handled
properly. This means you have one optimized and one unoptimized
(superfluous) version of the loop in your binary.

[snip attacks on clang/gcc devs]

Tobi

 

[Alf P. Steinbach]

In my practice, this kind of expressions arise from templated code,
possibly after inlining some functors passed as template parameters, so
in the actual source code the expression would not look anything like
above, and the type of the x could be for example whatever numeric type,
either signed or unsigned.

I would appreciate greatly if the compiler would be able to optimize such
code as much as possible, for example eliding any x<0 code branches for
unsigned types, etc.


If the resulting expression after all template inlining is 'x<x+1' for a
signed integer type then surely I am meaning 'true'.

Well, in this case the programmer didn't write it.

And if 'x<x+1' is produced by template inlining then 'x' is presumably
known at compile time, or do I misunderstand what you have in mind?

And then the expression can be reduced directly without recourse to
general properties of the arithmetic operations, i.e. without exploiting
formal UB by assuming infinite precision arithmetic.

Then he should not be surprised that his implementation-specific code
ceases to work when ported to another implementation.

For established platform conventions, he (or she) should, IMHO, be
surprised that the compiler doesn't honor them by default.

Even weak conventions like this.

Why can't he write
portable code like 'if (x<INT_MAX) which would express the intent much
better?

I totally agree.

But then, there are any number of reasons: some programmers insist on
being "clever" (or, all do, at some times?), some constructs result from
editing and paring down, some code is just copied around, ...


Cheers,

- Alf

 

[K. Frank]

Hello Alf!

...
Now, since you ask, what I have against g++ is mainly
...

* Lagging support for the C++ standard library:

I find that current versions of g++ have very good
support for the c++11 standard library (and c++11
language features). Not totally complete, but almost
all of the features I've found myself wanting use
have been there.

- In the old days, lacking support for wide streams and strings.

- Currently, lacking support for threading library (I think that
was just implemented, but not yet available for Windows),
regexp, etc.

I have been using std::thread with g++ for four years
now, on windows, no less. Basic support for std::thread
(and related features) has been around for a while now
(years) and has become more complete over time. I won't
go so far as to state that it is fully complete or error
free, but g++'s support for std::thread is currently at
least nearly complete, and I have used it without incident
in real-world code.

...
Cheers,

- Alf

Best.


K. Frank

 

[Alf P. Steinbach]

No, writing this code literally and thus _actively_ relying on UB is just
stupid, I thought we agree on that.

Oh yes.

Don't do that.

I don't want to miss important optimization opportunities because of some
people writing stupid code.

You don't have to miss out on speed. For example, for the Windows
platform Visual C++ (to take one example) generally produces faster code
than gcc, and Intel (which I'm not experienced with) faster still, it's
said. Without those silly breaking optimizations.

No, it is essential, especially in combination with templates.
In the generic form, the optimizations are usually not possible, but in a
specific instanciation they may be important.
Similar for inlining and whole program optimization.


They only affect the meaning of badly written code!

So? How do you propose to avoid all such code?

Despite your experience, in this case I trust the llvm devs. Please don't
take this as a personal attack, it's not.

It's OK, my explanation was just not clear enough. So, thanks for that
feedback. ;-)

In particular, for the example

for (i = 0; i <= N; ++i) { ... }

the description "if the variable [namely 'i'] is defined to wrap around
on overflow, then the compiler must assume that the loop is possibly
infinite" is false. The author may be thinking of the case where N is the
maximum signed value, but that's easy to check for, and even easier for
the programmer to specify if e.g. loop unrolling is desired.

I omitted this sentence continuation for brevity in the quote above: "-
which then disables these important loop optimization".

Even if you disagree with the notion that "must assume" is false,
clearly the bit about disabling the optimization is false.

After all, they can easily be done, which contradicts that they cannot
be done.

Is that clear enough explanation?

Oh well, to prove that for yourself if you don't see it, simply look up
Duff's Device in Wikipedia (if you're not familiar with it), and
hand-craft that optimization for a relevant loop with signed loop
variable where N can possibly but necessarily be INT_MAX.

So, even more importantly than the incorrect "must assume", the claim
that this loop would be impossible to optimize is completely and utterly
false.

And so, with errors and misdirections galore, all of them pointing in
one direction, for the purely technical, for what you assume internally
for your programming, it's NOT a good idea to trust that document.

Rather trust your instinct, that when you initially find that, as you
wrote, you "don't fully understand" it, and it's about something simple,
then there's most likely something fishy, something not right, and when
written by intelligent people it's likely misdirection.

I hope you don't expect me to annotate my code with all desired
optimizations.

No, that would be a rather impractical approach.

Can you think of anything more practical?

The test if N == INT_MAX would still have to be done at runtime and handled
properly.

No, but knowledge about N has to be established either at compile time
or at run time.

Note that this is the same as for unsigned loop variable.

Effectively, therefore, the author(s) pretend that people are using
signed loop variables in order to allow gcc to silently exploit formal
UB to optimize away two machine code instructions for the case where N
is not known to be in reasonable range, and that it's important to have
this micro-optimization invoked in that very subtle and implicit way.

Which is just silly.

At least when you reflect on it a bit.

This means you have one optimized and one unoptimized
(superfluous) version of the loop in your binary.

No, but that's the worst case.

One far more PRACTICAL approach is that the compiler warns when the loop
can be infinite and unrolling has been asked for; then it can be
rewritten or an option supplied that says "assume finite loops".

Same with unsigned loop variable. ;-)


Cheers & hth.,

- Alf

 

[Alf P. Steinbach]

I have been using std::thread with g++ for four years
now, on windows, no less. Basic support for std::thread
(and related features) has been around for a while now
(years) and has become more complete over time. I won't
go so far as to state that it is fully complete or error
free, but g++'s support for std::thread is currently at
least nearly complete, and I have used it without incident
in real-world code.

Thanks!

I now googled up this SO question about it: <url:
http://stackoverflow.com/questions/...-not-compiling-simple-c11-code-under-winvista>.

So, I've evidently been exposed to the wrong MinGW builds re <thread>,

g++ library status (this looks current):

http://gcc.gnu.org/onlinedocs/libstdc++/manual/status.html#status.iso.2011

No regexp yet -- but then, as the adage goes, if one has a problem,
and thinks the solution is regular expressions, then one has 2 problems.


Cheers,

- Alf
By mistake this was mailed first, instead of posted. Thunderbird. Sorry.

 

[Alf P. Steinbach]

Irrelevant, this is what the optimizer sees at one step. Or are you
suggesting the optimizer should start to guess what the programmer had in
mind, and produce different code based on that?

Far from the compiler adding EXTRA unreliability, as you suggest, it
should instead be (more) predictable, more reliable.

The programmer should not have to guess at the compiler.

No guessing or telepathy is needed for that, but instead, common sense.

No, this is not what I had in my mind. The type of x would be (one of)
template parameters, but the values are known only at run-time. I am mostly
concerned about array operations, where the type of array elements is not
fixed and the code must support all (numeric) types, for example.

Perhaps you could give a CONCRETE EXAMPLE?

Because I'm baffled as to how "x < x+1" could be produced, with x a
variable and the original code meaningful.

Cheers,

- Alf

 

[Alf P. Steinbach]

One possibility is as the result of being able to determine the values
of other variable in the original equation. Let's say you started
with:

if ((x*a) < (x+b))

And we happen to know, perhaps because of the parameters passed to a
template instantiation or an inlined function, that a and b are both
one.

You have convinced me, that expression, "x < x+1", CAN happen for good
reasons.

Thanks.

That sort of optimization is fundamental to why inlined functions can
produce significant performance gains. And the next thing I'd expect
would be for the compiler to remove the dead code in the "else" leg,
and then possibly find dead variable to eliminate, and then be better
able to optimize the containing loop (perhaps strength reduction
becomes possible with the loss of the conditional), etc.

Or we can throw that all away and assume the programmer wants to test
undefined behavior. To be sure there's a balance to be struck here
someplace.

Well that sounds rather ominous, as if guaranteed wrap-around behavior
for this would impose some unacceptable inefficiency in some cases.

A standards change in that direction, which is the outer discussion
topic one level up the call stack (so to speak), would maybe force
compilers to introduce such inefficiency, like comparing two integers,
instead of that being the existing practice as I have maintained?

Let's check REALITY then.

Like, what does real Windows compilers do with that construct, when
asked to optimize?

Do they optimize the resulting x <= x+1 to "true", or do they introduce
the unacceptable inefficiency of performing the comparison or even
optimizing x <= x+1 to its wrap-around behavior "false" for known x?

#include <iostream>
using namespace std;

void fire_nukes_at( int const destination )
{
auto const victim = (destination >= 0? "them" : "ourselves");
cout << " Firing nukes at " << victim << "!" << endl;
}

template< int a, int b >
void foo( int const x )
{
if( x*a <= 0 ) throw 666;
cout << "x*a = " << x*a << ", x+b = " << x+b << endl;

if( x*a <= x+b )
{
fire_nukes_at( x+b );   // Safe! Guaranteed x+b > 0! Yay!
}
else
{
cout << "Oh thank Odin! The war is over!" << endl;
// Massive sillycode here may be optimized away, or ... ?
}
}

int main()
{
foo<1, 1>( unsigned(-1)/2 );
}
[code]

I use a platform-specific construct in "main", since it works for all
platforms I would ever need to support (not Univac), just to show how
silly it is to abstain from everything not guaranteed by the standard,
and to throw a bone to those dogs who would like to make some noise.

Anyway, compiling with Visual C++ 11.0 (that's Visual C++ 2012, and also
internal version number 17.00, as you see reported below), where option
"/Ox" requests maximum optimization:

[example]
[D:\dev\test][QUOTE]
version cl[/QUOTE]
Microsoft (R) C/C++ Optimizing Compiler Version 17.00.60610.1 for x86

[D:\dev\test][QUOTE]
cl foo.cpp /Ox /Feb foo.cpp

[D:\dev\test]
b[/QUOTE]
x*a = 2147483647, x+b = -2147483648
Oh thank Odin! The war is over!

[D:\dev\test][QUOTE]
_[/QUOTE]
[/example]

Hm, it yielded wrap-around behavior.

In one (important?) sense that's pretty nice, because it avoided having
the "if" body executed with its condition indicating something untrue,
which could then cause nuclear missiles to be FIRED ON OURSELVES.

But anyway, what does MinGW g++ do?

I'm no wizard with g++ options, so maybe the example below lacks the
specific option that will cause a bit of nuclear fireworks.

I'm just hoping "-ofast" will suffice to get that awfully expensive and
unacceptable integer comparison in the "if" condition, removed:

[example]
[D:\dev\test][QUOTE]
version g++[/QUOTE]
g++ (GCC) 4.7.2

[D:\dev\test][QUOTE]
g++ foo.cpp -fno-wrapv -Ofast 
[D:\dev\test]
a[/QUOTE]
x*a = 2147483647, x+b = -2147483648
Oh thank Odin! The war is over!

[D:\dev\test][QUOTE]
_[/QUOTE]

Oh dear also g++ produced wrap-around behavior.

Which means that changing the standard in that direction would not
introduce any new inefficiency (assuming for the sake of discussion that
it is an inefficiency, which I'm not sure I agree with), but instead
capture existing practice, at least for these two compilers.


Cheers & hth.,

- Alf (reality inspector)

 

[Alf P. Steinbach]

I don't fully understand the for-loop example on that page, but it
seems to enable various loop optimizations.

It's good that you don't understand it, because the description is
fallacious and wrong. In particular, for the example

for (i = 0; i <= N; ++i) { ... }

the description "if the variable [namely 'i'] is defined to wrap around
on overflow, then the compiler must assume that the loop is possibly
infinite" is false. The author may be thinking of the case where N is
the maximum signed value, but that's easy to check for, and even easier
for the programmer to specify if e.g. loop unrolling is desired.

It is quite simple - "N" is not a compile-time constant. The compiler
may be able to generate better code knowing that the loop will always
end and that "i" will always be non-negative (assuming undefined
behaviour for integer overflow), than it could do without that assumption.

The compiler can always (emit code to) split the cases of terminating
and infinite loop, so you're wrong about that, but I think you're RIGHT
about the possibly better code when the compiler can assume that "i" is
non-negative.

I can't think of an example right here and now, but more constraints
generally do help the optimizer.

However that's not what is claimed on the referred page, and quoted above.

- Alf