CODEWITHSUNDEEP
c++
Johann Gerell
Johann Gerell

Reputation: 25581

Is a standards conforming C++ compiler allowed to optimize away branching on <= 0 for unsigned integers?

Consider this code:

void foo(size_t value)
{
    if (value > 0) { ... }    // A

    if (value <= 0) { ... }   // B
}

Since an unsigned cannot be negative, could a standards conforming C++ compiler optimize away the B statement? Or would it just choose to compare to 0?

Upvotes: 2

Views: 129

Answers (3)

T.C.
T.C.

Reputation: 137310

If the code is correctly written, B cannot be optimized away, because value can be zero, though the particular comparison used can be replaced with an equivalent one as shown in Angew's answer. But if the statements in B invoke undefined behavior, all bets are off. For ease of reference, let's rewrite foo as

void foo(size_t value)
{
    if (value > 0) bar(); // A
    if (value <= 0) baz(); // B
}

If the compiler can determine that baz() invokes undefined behavior, then it can treat it as unreachable. From that, it can then deduce that value > 0, and optimize foo into

void foo(size_t value)
{
    bar();
}

Upvotes: 3

Pixelchemist
Pixelchemist

Reputation: 24936

Since the compound statement must be executed if the unsinged value == 0, a conforming compiler cannot optimize away if (value <= 0) { /* ... */ }.

An optimizing compiler will probably consider several things here:

  1. Both statements are mutually exclusive
  2. There is no code in between both of them.
  3. value cannot be smaller than zero

There are several possible "outcomes" of this scenario where every scenario consists of one comparison and one conditional jump instruction.

I suspect test R,R to be "more optimal" than cmp R, 0 but in general there is not much of a difference.

The resulting code can be (where Code A and Code B contain a ret):

Using cmp

 cmp <value>, 0

A)

 je equal
 // Code A
equal:
 // Code B

B)

 jne nequal
 // Code B
nequal:
 // Code A

C)

 jg great
 // Code B
great:
 // Code A

D)

 jbe smoe
 // Code A
smoe:
 // Code B

Using test

 test <value>, <value>

A)

 je equal
 // Code A
equal:
 // Code B

B)

 jne nequal
 // Code B
nequal:
 // Code A

Upvotes: 2

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171117

Well, it clearly cannot optimise away the B statement altogether—the condition body does execute when value is 0.

Since value cannot, by any means, be < 0, the compiler can of course transform B into if (value == 0) { ... }. Furthermore, if it can prove (remember that the standard mandates strict aliasing rules!) that value is not changed by statement A, it can legally transform the entire function like this:

void foo(size_t value)
{
    if (value > 0) { ... }    // A
    else { ... }   // B
}

Or, if it happens to know that the target architecture likes == better, into this:

void foo(size_t value)
{
    if (value == 0) { ... }    // B
    else { ... }   // A
}

Upvotes: 8

Related Questions