Unitialized Variable with Undefined Behavior

If you code in C/C++, undefined behavior shouldn’t be new to you. Out-of-boundary access, dereferencing null pointer or dividing by zero can all end up with undefined behavior.

C++ reference defines undefined behavior as

Renders the entire program meaningless if certain rules of the language are violated.

For well-known causes mentioned above, chances are good that you either have been trained not to produce them, or you won’t be surprised if you find it while debugging. However, some causes can render the program so meaninglessly that you will be surprised by its output.

Here I will share my experience digging into such a surprising undefined behavior. To my bigger surprise, I end up finding that Linus Torvalds was hit by the same issue!

Let’s take a look at it.

Example

This code snippet demonstrates the undefined behavior.

Function contain() checks whether the given vector of numbers contains the target number and returns the result. The caller, main function prints different message given different results. Simple and Straightforward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<vector>

bool contain(const int target, const std::vector<int>& numbers) {
bool found;
for (const int num : numbers) {
if (num == target) {
found = true;
}
}
return found;
}

int main() {
int target = 42;
std::vector<int> numbers = {1, 2, 3};
const bool found = contain(target, numbers);
if (!found) {
std::cout << "Target not found!" << std::endl;
} else {
std::cout << "Target found!" << std::endl;
}
return 0;
}

Compiled and executed it. Everything was normal.

1
2
g++ -Wall a.cc && ./a.out
Target not found!

However, if I turned on compiler optimization, strange thing happens:

1
2
g++ -Wall -O2 a.cc && ./a.out
Target found!

Now function contain() thinks {1 ,2, 3} contains 42! What a surprise!

You can try it yourself at this compiler explorer website.

Exploration

You may quickly locate the problem to be the uninitialized boolean variable. Simply initializing it to false will fix the problem. Yes, fixing it isn’t difficult. The difficult part is to understand why it happened at first place.

To understand what happened, we can simply check the output assembly code on the same complier explorer site. Here is part of it:

1
2
3
4
5
contain(int, std::vector<int, std::allocator<int> > const&):
mov eax, 1
ret
.LC0:
.string "Target found!"
  • The first section is the generated code for function contain(). All it does is making 1 as return value and then return. In other words it will always return true!

  • The second section stores the read only string literals in the original code. Now it only holds "Target found", which means the other string "Target not found!" is totally optimized away.

This is so counter-intuitive. How could the compiler “determine” in compilation time about the output of contain() when it all depends on the values of parameters the function received at runtime? This is a very bold move for the compiler. Is it a bug?

Turns out it’s not a bug, but a feature. (Sounds familiar?) We will check intermediate outputs of GCC tree passes to see what happened deeper. Fortunately the online compiler explorer also allows us to do so. For local run you can try gcc option -fdump-tree-all.

Everything looks fine at pass 027t.objsz1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
contain (const int target, const struct vector & numbers) {
// Checks when to stop iterating vector.
<bb 3> :
# found_2 = PHI <found_10(D)(2), found_3(6)>
if (retval.0_12 != 0)
goto <bb 4>; [INV]
else
goto <bb 7>; [INV]

// Checks whether current vector element equals the target.
<bb 4> :
if (num_17 == target_18(D))
goto <bb 5>; [INV]
else
goto <bb 6>; [INV]

// Sets `found` to true when target is found.
<bb 5> :
found_19 = 1;

// Otherwise moves on to the next element.
<bb 6> :
# found_3 = PHI <found_2(4), found_19(5)>
_28 = __for_begin._M_current;
_29 = _28 + 4;
__for_begin._M_current = _29;
_41 = &__for_begin;
goto <bb 3>; [100.00%]

// Prepares for returning.
<bb 7> :
_15 = found_2;
return _15;
}

But at next pass 028t.cpp1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Removing basic block 5
Merging blocks 4 and 6
contain (const int target, const struct vector & numbers)
{
// Checks when to stop iterating vector.
<bb 3> :
if (_26 != 0)
goto <bb 4>; [INV]
else
goto <bb 5>; [INV]

// Does nothing. Simply move on to the next element!!!
<bb 4> :
_21 = MEM[(const int * *)&__for_begin];
num_17 = *_21;
_28 = __for_begin._M_current;
_29 = _28 + 4;
__for_begin._M_current = _29;
goto <bb 3>; [100.00%]

// Unconditionally returns 1!!!
<bb 5> :
return 1;
}

All the branches conditioned on the value of found is removed. Single return value 1 starts appearing.

OK. Seems the optimization is related to the PHI function, no surprise. But to dig even deeper, we need to check the gcc source code. However, equipped with this key word, maybe we can find some good explanation on Google. This is actually how I ended up with an explanation from a 15-year-old gcc bug:

When CCP visits the PHI node for first1, it merges the values of first2 (UNDEFINED since it’s a default definition of a local variable) with 0. Since we are allowed to assume whatever value is convenient, we go ahead with 0 and fold ‘if (first_1 == 0)’ into ‘if (1)’.

In short, since the behavior of accessing uninitialized variable is undefined, gcc simply assume the most convenient value for her, and in our case true. And based on that optimized away all the conditions.

Discussion

The gcc bug isn’t complaining about the behavior itself. It complains there isn’t any warning about the uninitialized variable even with warning enabled, which is a real bug. Hope you have noticed that even if I have -Wall set all the time, there isn’t any warning message printed.

Just few months ago, Linus reported a bug which ends up marked as duplicate of the one above. Discussion there is also very helpful for understanding the intuition behind the optimization. You can read further if you are still not satisfied.

It is totally legit for the compiler to assume convenient value for uninitialized local variable. Undefined behavior, as a contract between compiler implementation and its client code, gives the compiler creator the freedom to do so in order to make generated code more efficient. As the other signee of the contract, we should try our best to avoid violating it.

Or maybe hire a C++ lawyer. ;)