In accordance with the C and C++ standards, if the program leads to an integer overflow or any other “undefined behavior” (UB), the result of the program performance can be anything: it can post obscenities to Twitter or format your disk…

Unfortunately, “Easter eggs” that would make the program do something out of the ordinary in case of UB, have not been noticed since the GCC 1.17 that invoked NetHack, when the code contained unknown #pragma. Usually, the undefined behavior result is much more boring: the compiler just optimizes the code for cases when UB does not take place, without giving the slightest importance to the situation when it does take place, as the standard allows to do anything in that case!

To illustrate how UB in the standard allows the compiler to perform non-obvious optimizations, Raymond Chen provides the following sample code:

int table[4];
bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}

There is a off-by-one mistake in a loop condition, as we used <= instead of <. As a result, exists_in_table() should either return true at one of the first four iterations, or it will read table[4], which is UB. In this case, exists_in_table() can do anything, including returning a true! In full accordance with the standard, the compiler can optimize the code to:

int table[4];
bool exists_in_table(int v)
{
    return true;
}

Such optimizations often catch programmers off guard. John Regehr provides the following selection of examples when undefined behavior led to significant consequences:

int a;
void bar (void)
{
  setlinebuf(stdout);
  printf ("hello!\n");
}
void foo3 (unsigned y, unsigned z)
{
  bar();
  a = y%z;
}
int main (void)
{
  foo3(1,0);
  return 0;
}

will have time to print the message before SIGFPE, if compiled without optimizations, and it will crash right away in case we enable optimization. The program “knows in advance” that it is destined to crash with SIGFPE, and does not even bother printing the message. Chen provides a similar example, but with SIGSEGV.

In 2012, Regehr announced a contest for the craziest consequence of undefined behavior. One of the winners took advantage of the fact that the usage of a pointer after being passed to realloc(), is undefined behavior. His program prints different values for the same pointer:

#include 
#include 
int main() {
  int *p = (int*)malloc(sizeof(int));
  int *q = (int*)realloc(p, sizeof(int));
  *p = 1;
  *q = 2;
  if (p == q)
    printf("%d %d\n", *p, *q);
}

$ clang -O realloc.c; ./a.out

1 2

To my mind, the programs of other contest winners are more boring and partially overlap with the mentioned examples.

But nothing can compare with Regehr’s example: the disprove of Fermat’s Last Theorem by the compiler.

He says that he had to write an infinite loop for some embedded software, so that the optimizing compiler could not remove the entire code that follows the loop. Modern compilers are clever enough to detect “idioms” like while (1) { } or for (;;) { }. They understand that the code following such loop is unreachable and, therefore, there is no need to compile it. For instance, compilers will “shorten” the following function

void foo (void)
  {
    for (;;) { }
    open_pod_bay_doors();
  }

to a single instruction:

foo:
    L2: jmp L2

Clang is even smarter, it can detect (and remove) even the following masked infinite loops:

unsigned int i = 0;
  do {
    i+=2;
  } while (0==(i&1));

As in the previous example, the compiler is able to prove that the loop termination is not possible, and, therefore, it can be replaced by a single jmp instruction.

Regehr decided that compilers are unlikely to prove Fermat’s Last Theorem during compilation.

int fermat (void)
{
  const int MAX = 1000;
  int a=1,b=1,c=1;
  while (1) {
    if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1;
    a++;
    if (a>MAX) {
      a=1;
      b++;
    }
    if (b>MAX) {
      b=1;
      c++;
    }      
    if (c>MAX) {
      c=1;
    }
  }
  return 0;
}
#include 
int main (void)
{
  if (fermat()) {
    printf ("Fermat's Last Theorem has been disproved.\n");
  } else {
    printf ("Fermat's Last Theorem has not been disproved.\n");
  }
  return 0;
}
regehr@john-home:~$ icc fermat2.c -o fermat2
regehr@john-home:~$ ./fermat2
Fermat's Last Theorem has been disproved.
regehr@john-home:~$ suncc -O fermat2.c -o fermat2
"fermat2.c", line 20: warning: statement not reached
regehr@john-home:~$ ./fermat2
Fermat's Last Theorem has been disproved.

How come? The loop will terminate by return 1. Has the compiler managed to prove that Fermat’s Last Theorem is false?!

So, what a,b,c values has it found?

Regehr added printing of the found values before return 1. That's when the compiler admitted its weakness and compiled and infinite loop. (Of course, nothing was printed).

Despite the fact that this program does not contain any arithmetic overflows (multiplier factors vary in the range from 1 to 1000, the sum of their cubes does not exceed 231), the C++ standard defines an infinite loop as an undefined action, without changing the external state. That’s why C++ compilers are entitled to consider similar loops as finite.

The compiler can easily see that the only way out of the while(1) loop is the return 1; statement, while the return 0; statement at the end of fermat() cannot be reached. Therefore, it optimizes this function to

int fermat (void)
{
  return 1;
}

In other words, the only possibility to write an infinite loop that could not be removed by the compiler is to add a modification of the external state to the loop body. The easiest (and the most standard) way to do this is to change the variable declared as volatile.

  • 0

Subscribe to Kukuruku Hub

Or subscribe with RSS

1 comment

Shafik Yaghmour
As John Regehr says in the article Compilers and Termination Revisited in the C 1999 standard it is unclear whether the as-if rule rule allows compilers to eliminate infinite loops or not. The fact that reasonable people can come to different conclusions says it is underspecified.

In the C 2011 standard this was clarified and it now forbids optimizing away an infinite loop if the control statement is a constant expression, for example:
while (1) { } 
is not fair game for optimization. You can find more detail in my Stackoverflow answer here

Read Next

Hi Everyone! We are about to launch a new project very soon - CrowdMind.co. Sign up to get a private beta access!