Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I wrote this code:

#include <iostream>
int main()
{
    int a;
    std::cin >> a;
    if(a*a== 3){
        std::cout << a;
    }
    return 0;
}

On MSVC I turned ON all optimization flags. I expected that since a*a can never be 3, so compiler should not generate code for the section:

if(a*a== 3){
    std::cout << a;
}

However it generated code for the section. I did not check GCC or LLVM/CLang.

What are the limits of expectation from a C++ compiler in these scenarios?

share|improve this question
1  
    
Indeed. What about (a*a*a) + (b*b*b) == (c*c*c) ? –  MSalters Sep 17 '12 at 13:37
add comment

6 Answers 6

Consider what happens if input fails. a can be left with an undefined value, and hilarities may ensue.

Try initializing it first.

share|improve this answer
    
Well, if a was unintialized, wouldn't reading (let alone squaring) it trigger undefined behaviour, meaning the compiler may do whatever it wants - including assuming it won't happen? –  delnan Apr 26 '12 at 19:57
2  
Come on, be serious: compilers are still automatas: Undefined behavior can be "anything the compoiler writer wants to happen". The uninitialized a is in any case an integer. You don't know which one, but always an integer is. Initialization is irrelevant in the context of this question. –  Emilio Garavaglia Apr 28 '12 at 13:21
    
@EmilioGaravaglia: Actually, it matters a lot. Optimizers that try to track values are definitely FSM's, but to deal with the enormous size of the domain space they generally fold values together. "Uninitialized" may fold with 0 in one branch and 1 in another. Hence, 0==uninitialized AND 1==uninitialized at other moments. This is real behavior in real optimizers, and obviously NOT the behavior of any finite integer. –  MSalters Sep 17 '12 at 13:41
add comment

Checking for a few fairly specific literal values like if (0), if (1), if (LOG_LEVEL > 1)`, etc., is pretty routine.

Checking that a number is a perfect square so that squaring an integer could produce that value? I'd be surprised to see a compiler do that. It undoubtedly could be done -- it's actually simpler than a lot of things that are done. At the same time, most such optimization makes the compiler run at least a tiny bit slower, and I doubt anybody wants to slow the compiler at all for something that's likely to be used anywhere close to as rarely as that.

share|improve this answer
    
It might be slightly tough in this case for compiler, but what about: if(a*a < 0){ ... }. What is the expectation from compiler? –  nature1729 Apr 26 '12 at 20:13
    
Also what about statements like: if(6*a/2 -a*3 == 0) { ... } ? Compilers are Algebra unaware? –  nature1729 Apr 26 '12 at 20:15
2  
@ReeteshMukul: if (a*a<0) will probably depend on the type of a. If it's unsigned, then I'd expect it to know the result can't be <0. If it's signed, then contrary to normal math, it can produce a negative result, and the compiler had better know it... –  Jerry Coffin Apr 26 '12 at 20:18
    
@ReeteshMukul: As far as 6*a/2 -a*3 == 0 goes, sort of -- they do know things like strength reduction, common sub-expression elimination, and commutative properties, which would probably be enough for that case -- at last if a is some integer type. If a is floating point, they probably can't (and shouldn't). –  Jerry Coffin Apr 26 '12 at 20:25
add comment

Compiler optimization are normally designed to avoid repetitions, resort branches, eliminate copies on return etc. They can remove impossible branches after a static analysis (involving just constant)

But, normally, compiler don't evaluate expression containing variables since it assumes their value depends on input. Compilers cannot produce inference on values (saying "no integer can square into 3" is -at all effect- a theorem to be demonstrated, and automatic demonstration of theorems can be demonstrated to be a non-MT decidable problem: If I complicate the expression a lot, demonstrate it's "field of existence" can require ... creativity: something computer don't have by their very nature: finite state machines).

A compiler can do this kind of optimization only for a finite and pre-determined number of cases (and -frankly- I think statistics about user demands don't justify an interest in optimizing expression appositely written to fool the optimizer around - and it can always be fooled around, since whatever case it can manage you can always imagine another one it does not manage). Attempting to solve these kind of problems in a "general way" will sooner or later find a case that will put the compiler into an infinite loop or into a stack overflow.

share|improve this answer
add comment

There is research into so-called 'superoptimizing' compilers that would spot this, however not everyone is willing to wait a few hours for their code to compile.

share|improve this answer
add comment

I think compiler optimization normally reduces (sub)expressions that depend on constant values only.

If an expression contains variables whose value is bound at run-time, only some basic properties can be checked, e.g. when comparing an unsigned integer with 0, like this:

unsigned int c;

...

if (c < 0)
{
   ...
}

On the other hand, I do not think that it makes sense (or that it is even possible) for a compiler to try and investigate more complex properties of an expression that are valid for all possible inputs and optimize based on that. What to do for example with:

unsigned int a, b, c, n;

std::cin >> a;
std::cin >> b;
std::cin >> c;
std::cin >> n;

if (n > 2 && pow(a, n) + pow(b, n) == pow(c, n))
{
    std::cout << "OK";
}

Apart from possible computation errors due to rounding or overflow the program will never execute the body of the if block(see this wikipedia article for some background), but how should a compiler be able to determine this?

Proving (let alone discovering) theorems about mathematical expression is too complex (or even not computable in certain cases) so it cannot be used as a compiler optimization technique.

share|improve this answer
add comment

I'm pretty sure there's a similar question over on StackOverflow with an excellent answer from Eric Lippert, but SO is down just now for some maintenance. I'll post a link when I find it, but my recollection is that Lippert's answer was along the lines of:

Yes, a compiler can check for that sort of thing, but since time and manpower are limited, that would mean not implementing some other feature. It just comes down to a matter of priorities.

Apologies to Eric Lippert if I got that wrong... Again, I'll post a link once SO is back.

Update: Here's the answer I was thinking of.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.