http://habrahabr.ru/post/229963/
В соответствии со стандартами 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 приводило к значительным последствиям:
В 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
31), стандарт C++ объявляет «неопределённым действием» бесконечный цикл без изменения внешнего состояния — поэтому компиляторы C++
вправе считать любой такой цикл конечным.
Компилятор легко видит, что единственный выход из цикла
while(1)
— это оператор
return 1;
, а оператор
return 0;
в конце
fermat()
недостижим; поэтому он оптимизирует эту функцию до
int fermat (void)
{
return 1;
}
Иначе говоря, единственная возможность написать на C++ такой бесконечный цикл, который компилятор не смог бы удалить — это добавить внутрь цикла изменение внешнего состояния. Самый простой (и стандартный!) способ сделать это — изменять переменную, объявленную как
volatile
.