Undefined behavior and Fermat's theorem

According to the C and C ++ standards, if the program execution leads to overflow of a signed integer variable, or to any of hundreds of other “undefined behavior” (undefined behavior, UB), then the result of the program execution can be any: it can post obscenity on Twitter, can format the disk for you ...
Alas, in fact, the “Easter eggs” that would force the program to do something out of the ordinary in the case of UB have not been seen since GCC 1.17 - it launched nethack when it encountered unknown people in the program code#pragma. Usually, the result of UB is much more boring: the compiler simply optimizes the code for cases where UB does not happen, without giving the slightest importance to what this code will do in the case of UB - because the standard allows you to do anything in this case!
To illustrate how the abundance of UB in the standard allows the compiler to perform non-obvious optimizations, Raymond Chen gives the following code example:

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

In the condition of the cycle, we made a mistake by one, setting <=instead <. As a result, she exists_in_table()must either return trueat one of the first four iterations, or she will read table[4]what UB is, and in this case she exists_in_table()can do anything - including return true! In full compliance with the standard, the compiler can optimize the code exists_in_table()to

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

Such optimizations sometimes take programmers by surprise. John Reger gives a selection of examples where UB has led to significant consequences:

• UB, with a sign left shift, allowed the compiler to remove the return address check, important for security, from NaCl.
• In the Linux kernel, dereferencing a pointer before checking for NULLit allowed the compiler to remove this check, creating a vulnerability in the system.
• In Debian, using an uninitialized array as a source of random data to initialize an RNG seed has caused the entire seed calculation to be removed by the compiler.
• When a variable is pnot initialized, the program can execute both the code inside if (p) { ... }and the code inside if (!p) { ... }.
• When the sign variable xis equal INT_MAX, the expression (x+1)>xin different places of the same program can be interpreted both as true and false.
• An infinite loop, such as searching for a nonexistent value, can be removed by the compiler. For example, this way the compiler can “refute” Fermat’s Great Theorem. (We will analyze this example in more detail.)
• The compiler can make the program "clairvoyant" by rearranging an operation that could potentially crash the process (division by zero, reading by a null pointer, etc.), ahead of the output operation. For example, this code:
  

  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;
  }
  

  
  - manages to print a message before SIGFPE, if it is compiled without optimizations; and will crash immediately at startup if you enable optimization. The program "knows in advance" that it is destined to fall from SIGFPE, and therefore does not even bother to print the message. A similar example, only with SIGSEGV, leads Chen.

In 2012, Reger announced a competition for "the most bizarre UB result." One of the winners took advantage of the fact that the use of the pointer after it is passed to the parameter in realloc()is UB. His program prints different values ​​on 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
12

The programs of the other winners of the contest, in my opinion, are more boring and partially overlap with the previously cited examples.
But nothing compares with the example of Reger himself — the “refutation” by the compiler of Fermat's theorem .

He explains that for some embedded application he needed to write an endless loop in C ++ so that the optimizing compiler could not remove all the code following the loop from the program. Modern compilers are smart enough to recognize "idioms" like while (1) { }or for (;;) { }- they understand that the code following such a cycle will never execute, which means there is no need to compile it. For example, the function

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

- most compilers "shorten" to a single instruction:

  foo:
    L2: jmp L2

Clang is even smarter, it is able to recognize (and delete) even such disguised endless loops:

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

Here, as in the previous example, the compiler is able to prove that exit from the loop is impossible, which means that it can be replaced with one instruction jmp.

Reger decided: are Fermat's theorem compilers unlikely to be able to prove at compile time?

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 so? The cycle will end in return 1;- the compiler was able to prove that Fermat's theorem is wrong ?!

I wonder what meanings a,b,che "found"?

Reger added the print of “found values” before return 1;- then the compiler recognized the powerlessness and honestly compiled an infinite loop. (Nothing, of course, was printed.)

Despite the fact that this program does not contain any arithmetic overflows (multipliers vary within 1..1000, the sum of their cubes does not exceed 2 ³¹ ), the C ++ standard declares an “indefinite action” an endless loop without changes in the external state - therefore, C ++ compilers have the right to consider any such cycle to be finite.
The compiler easily sees that the only way out of the loopwhile(1)- this is an operator return 1;, and the operator return 0;at the end is fermat()unattainable; therefore it optimizes this function to

int fermat (void)
{
  return 1;
}

In other words, the only way to write such an endless loop in C ++ that the compiler could not delete is to add a change in the external state inside the loop. The easiest (and standard!) Way to do this is to modify a variable declared as volatile.