Babelmonkeys

Ever so often, particularly when people are talking about strange things that C does, or C compilers do, or feel overly confident in their knowledge about C I have this little "party trick".

I show them the program below, and ask: “If I run this through an optimizing compiler (with optimizations turned on of course) what is the output of the produced binary?” I invite you to think about this yourself for a moment.

 1 #include <stdio.h>
 2 int main(int argc, char *argv[])
 3 {
 4     int a, b;
 5     if (argc > 1)
 6         a = 3;
 7     else
 8         b = 4;
 9 
10     printf("%i\n", a + b);
11 
12     return 0;
13 }

So, what was your answer? In my experience most people think it is going to be either 3 or 4. Potentially even depending on how many parameters you pass. Without optimizations turned on that is actually the case using some compilers. However, once optimizations are turned on the answer is 7. This tends to deviate from peoples intuition, because clearly there is no control flow path through the program, where both a and b are set.

There are some other interesting observations:

• This happens with all optimizing compilers I have seen
• The code usually reduces to printf("7\n")
• This only happens under optimization
• This does not happen if a or b is initialized

Before explaining what is happening here I want to make one thing very clear: This is in fact undefined behaviour. Either a or b are used uninitialized, in which case the C standard allows the compiler to do pretty much whatever it wants to.

In our case this very fact interacts with a common optimization called constant propagation in interesting ways. Constant propagation is one of the so called Dragon Book Optimizations, which are implemented in pretty much any modern (and not so modern) compiler.

A prerequisite for constant propagation is performing data-flow analysis. The particular kind performed here is an analysis for reaching definitions. This analysis tries to determine which definitions of a variable “reach” a use of the variable, i.e. there is no other definition between this definition and the use on at least one control flow path.

Performing this analysis for the uses of a and b on line 10 above tells us that each only has a single reaching definition. a is defined as 3 on line 6 and b is defined as 4 on line 8. Therefore, we can just copy these definitions to line 10. This is what is called constant propagation.

You might object that, while each of the variables has only one definition, it may also be undefined. In fact that is precisely correct. However, if a variable is undefined, the compiler may choose any value for it, including that of the reaching definition. We are case collapsing e.g. <undefined> or 3 down to just 3.

This is also the reason why the result is different once we initialize either of the variables. Doing so creates a second reaching definition via the branch that does not otherwise set the initialized variable, constant propagation therefore become impossible.