Неопределённое поведение и теорема Ферма

В соответствии со стандартами C и C++, если выполнение программы приводит к переполнению знаковой целой переменной, или к любому из сотен других «неопределённых действий» (undefined behaviour, UB), то результат выполнения программы может быть любым: она может запостить на Твиттер непристойности, может отформатировать вам диск…
Увы, в действительности «пасхальные яйца», которые бы заставляли программу в случае UB делать что-то из ряда вон выходящее, не встречались со времён GCC 1.17 — та запускала nethack, когда встречала в коде программы неизвестные #pragma. Обычно же результат UB намного скучнее: компилятор просто оптимизирует код для тех случаев, когда UB не происходит, не придавая ни малейшего значения тому, что этот код будет делать в случае UB — ведь стандарт разрешает сделать в этом случае что угодно!
В качестве иллюстрации того, как изобилие UB в стандарте позволяет компилятору выполнять неочевидные оптимизации, Реймонд Чен приводит такой пример кода:

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

В условии цикла мы ошиблись на единицу, поставив <= вместо <. В итоге exists_in_table() либо должна вернуть true на одной из первых четырёх итераций, либо она прочтёт table[4], что является UB, и в этом случае exists_in_table() может сделать всё что угодно — в том числе, вернуть true! В полном соответствии со стандартом, компилятор может соптимизировать код exists_in_table() до

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

Такие оптимизации иногда застают программистов врасплох. Джон Регер приводит подборку примеров, когда UB приводило к значительным последствиям:

• UB при знаковом сдвиге влево позволило компилятору удалить из NaCl проверку адреса возврата, важную для безопасности.
• В ядре Linux, разыменование указателя перед его проверкой на NULL позволило компилятору удалить эту проверку, создав уязвимость в системе.
• В Debian, использование неинициализированного массива в качестве источника случайных данных для инициализации RNG seed привело к тому, что всё вычисление seed было удалено компилятором.
• Когда переменная p не инициализирована, программа может выполнить и код внутри if (p) { ... }, и код внутри if (!p) { ... }.
• Когда знаковая переменная x равна INT_MAX, выражение (x+1)>x в разных местах одной программы может трактоваться и как истинное, и как ложное.
• Бесконечный цикл, например поиск несуществующего значения, может быть удалён компилятором. Например, так компилятор может «опровергнуть» Великую теорему Ферма. (Этот пример мы ещё разберём подробно.)
• Компилятор может сделать программу «ясновидящей», переставив операцию, потенциально способную обрушить процесс (деление на ноль, чтение по нулевому указателю и т.п.), вперёд операции вывода. Например, вот этот код:
  

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

  — успеет напечатать сообщение перед SIGFPE, если его скомпилировать без оптимизаций; и рухнет сразу при старте, если включить оптимизацию. Программа «заранее знает», что ей суждено упасть с SIGFPE, и поэтому даже не заморачивается печатью сообщения. Похожий пример, только с SIGSEGV, приводит и Чен.

В 2012 Регер объявил конкурс на «самый причудливый результат UB». Один из победителей воспользовался тем, что использование указателя после того, как он передан параметром в realloc(), является UB. Его программа печатает разные значения по одному и тому же указателю:

#include <stdio.h> #include <stdlib.h>   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 

Программы остальных победителей конкурса, на мой взгляд, скучнее и частично перекрываются с ранее приведёнными примерами.
Но ничто не сравнится с примером самого Регера — «опровержением» компилятором теоремы Ферма.

Он объясняет, что для какого-то встроенного приложения ему нужно было написать на C++ бесконечный цикл так, чтобы оптимизирующий компилятор не смог удалить из программы весь код, следующий за циклом. Современные компиляторы достаточно умны, чтобы узнавать «идиомы» навроде while (1) { } или for (;;) { } — они понимают, что код, следующий за таким циклом, никогда не выполнится, а значит, его и компилировать незачем. Например, функцию

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

— большинство компиляторов «укоротят» до единственной инструкции:

  foo:     L2: jmp L2 

Clang оказывается ещё умнее, он способен распознавать (и удалять) даже такие замаскированные бесконечные циклы:

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

Здесь, как и в предыдущем примере, компилятор способен доказать, что выход из цикла невозможен, а значит, его можно заменить одной инструкцией jmp.

Регер решил: уж теорему Ферма-то компиляторы вряд ли смогут доказать во время компиляции?

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 <stdio.h>  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. 

Как так? Цикл завершится по return 1; — компилятор смог доказать, что теорема Ферма неверна?!

Интересно, какие же значения a,b,c он «нашёл»?

Регер добавил печать «найденных значений» перед return 1; — вот тогда компилятор признал бессилие и честно скомпилировал бесконечный цикл. (Ничего, естественно, не напечаталось.)

Несмотря на то, что эта программа не содержит никаких арифметических переполнений (множители изменяются в пределах 1..1000, сумма их кубов не превосходит 2³¹), стандарт C++ объявляет «неопределённым действием» бесконечный цикл без изменения внешнего состояния — поэтому компиляторы C++ вправе считать любой такой цикл конечным.
Компилятор легко видит, что единственный выход из цикла while(1) — это оператор return 1;, а оператор return 0; в конце fermat() недостижим; поэтому он оптимизирует эту функцию до

int fermat (void) {   return 1; } 

Иначе говоря, единственная возможность написать на C++ такой бесконечный цикл, который компилятор не смог бы удалить — это добавить внутрь цикла изменение внешнего состояния. Самый простой (и стандартный!) способ сделать это — изменять переменную, объявленную как volatile.