A question on nature of generated assembly in C++ and code Algebra

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Try initializing it first.

Answer 4

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.

Answer 5

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.

Answer 6

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.