Можно ли считать ветки с неопределенным поведением недоступными и оптимизировать их как мертвый код?

88

Рассмотрим следующее утверждение:

*((char*)NULL) = 0; //undefined behavior

Он явно вызывает неопределенное поведение. Означает ли существование такого оператора в данной программе, что вся программа не определена или что поведение становится неопределенным только после того, как поток управления попадает в этот оператор?

Будет ли следующая программа четко определена на тот случай, если пользователь никогда не введет номер 3?

while (true) {
 int num = ReadNumberFromConsole();
 if (num == 3)
  *((char*)NULL) = 0; //undefined behavior
}

Или это полностью неопределенное поведение, независимо от того, что вводит пользователь?

Кроме того, может ли компилятор предположить, что неопределенное поведение никогда не будет выполняться во время выполнения? Это позволило бы рассуждать назад во времени:

int num = ReadNumberFromConsole();

if (num == 3) {
 PrintToConsole(num);
 *((char*)NULL) = 0; //undefined behavior
}

Здесь компилятор может решить, что в случае, если num == 3мы всегда будем вызывать неопределенное поведение. Следовательно, этот случай должен быть невозможным, и номер не нужно печатать. Весь ifоператор может быть оптимизирован. Допускается ли этот вид обратных рассуждений согласно стандарту?

usr
источник
19
иногда мне интересно, получают ли пользователи с большим количеством репутации больше голосов за вопросы, потому что «о, у них много репутации, это, должно быть, хороший вопрос» ... но в этом случае я прочитал вопрос и подумал: «Вау, это здорово "еще до того, как я посмотрел на спрашивающего.
turbulencetoo
4
Я думаю, что время, когда возникает неопределенное поведение, не определено.
eerorika
6
Стандарт C ++ явно говорит, что путь выполнения с неопределенным поведением в любой точке полностью не определен. Я бы даже интерпретировал это как утверждение, что любая программа с неопределенным поведением на пути полностью не определена (что включает разумные результаты для других частей, но это не гарантируется). Компиляторы могут использовать неопределенное поведение для изменения вашей программы. blog.llvm.org/2011/05/what-every-c-programmer-should-know.html содержит несколько хороших примеров.
Йенс
4
@Jens: На самом деле это означает просто путь к исполнению. В противном случае у вас будут проблемы const int i = 0; if (i) 5/i;.
MSalters
1
Компилятор в целом не может доказать, что PrintToConsoleон не вызывает, std::exitпоэтому он должен выполнить вызов.
MSalters

Ответы:

65

Означает ли существование такого оператора в данной программе, что вся программа не определена или что поведение становится неопределенным только после того, как поток управления попадает в этот оператор?

Ни то, ни другое. Первое условие слишком сильное, а второе слишком слабое.

Доступ к объектам иногда является последовательным, но стандарт описывает поведение программы вне времени. Данвил уже цитировал:

если любое такое выполнение содержит неопределенную операцию, настоящий международный стандарт не налагает никаких требований на реализацию, выполняющую эту программу с этим вводом (даже в отношении операций, предшествующих первой неопределенной операции)

Это можно интерпретировать:

Если выполнение программы приводит к неопределенному поведению, тогда вся программа имеет неопределенное поведение.

Итак, недостижимый оператор с UB не дает программе UB. Оператор достижимости, который (из-за значений входных данных) никогда не достигается, не дает программе UB. Вот почему ваше первое условие слишком сильное.

Теперь компилятор не может вообще сказать, что есть UB. Таким образом, чтобы позволить оптимизатору переупорядочивать операторы с потенциальным UB, который будет переупорядочен, если их поведение будет определено, необходимо разрешить UB «вернуться назад во времени» и пойти не так до предыдущей точки последовательности (или в C Терминология ++ 11, чтобы UB влиял на вещи, которые упорядочены до вещи UB). Следовательно, ваше второе условие слишком слабое.

Главный пример этого - когда оптимизатор полагается на строгое алиасинг. Весь смысл строгих правил псевдонима состоит в том, чтобы позволить компилятору переупорядочивать операции, которые нельзя было бы правильно переупорядочить, если бы было возможно, что рассматриваемые указатели являются псевдонимами одной и той же памяти. Таким образом, если вы используете незаконные указатели псевдонимов, а UB действительно встречается, то это может легко повлиять на оператор «перед» оператором UB. Что касается абстрактной машины, то оператор UB еще не был выполнен. Что касается фактического объектного кода, он был частично или полностью выполнен. Но стандарт не пытается подробно описать, что значит для оптимизатора переупорядочить операторы, или каковы последствия этого для UB. Он просто дает лицензию на реализацию пойти не так, как только захочет.

Вы можете думать об этом так: «У UB есть машина времени».

В частности, чтобы ответить на ваши примеры:

  • Поведение не определено, только если прочитано 3.
  • Компиляторы могут исключать и устраняют код как мертвый, если базовый блок содержит операцию, которая точно не определена. Они разрешены (и я предполагаю, что да) в случаях, которые не являются базовым блоком, но когда все ветки ведут к UB. Этот пример не является кандидатом, если PrintToConsole(3)не известно, что он обязательно вернется. Это могло вызвать исключение или что-то еще.

Примером, аналогичным вашему второму, является опция gcc -fdelete-null-pointer-checks, которая может принимать такой код (я не проверял этот конкретный пример, считаю его иллюстративным для общей идеи):

void foo(int *p) {
    if (p) *p = 3;
    std::cout << *p << '\n';
}

и измените его на:

*p = 3;
std::cout << "3\n";

Зачем? Поскольку if pимеет значение NULL, код все равно имеет UB, поэтому компилятор может предположить, что он не равен NULL, и соответственно оптимизировать. Ядро Linux споткнулось об этом ( https://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2009-1897 ) по сути потому, что оно работает в режиме, в котором разыменование нулевого указателя не должно быть UB, ожидается, что это приведет к определенному аппаратному исключению, которое ядро ​​может обработать. Когда оптимизация включена, gcc требует использования-fno-delete-null-pointer-checks , чтобы предоставить эту нестандартную гарантию.

PS Практический ответ на вопрос "когда поражает неопределенное поведение?" это «за 10 минут до того, как вы собирались уехать на день».

Стив Джессоп
источник
4
Собственно, в прошлом из-за этого было немало проблем с безопасностью. В частности, из-за этого существует опасность того, что любая проверка переполнения постфактум может быть удалена. Например , void can_add(int x) { if (x + 100 < x) complain(); }можно оптимизировать прочь полностью, потому что если x+100 Безразлично» переполнения ничего не происходит, а если x+100 же переполнение, что это UB в соответствии со стандартом, так что ничего не может случиться.
fgp
3
@fgp: верно, это оптимизация, на которую люди горько жалуются, если спотыкаются о ней, потому что начинает казаться, что компилятор намеренно нарушает ваш код, чтобы наказать вас. «Зачем мне было писать так, если бы я хотел, чтобы вы его удалили!» ;-) Но я думаю, что иногда оптимизатору при работе с более крупными арифметическими выражениями полезно предположить, что переполнения нет, и избежать чего-либо дорогостоящего, которое может понадобиться только в этих случаях.
Стив Джессоп
2
Было бы правильно сказать, что программа не является неопределенной, если пользователь никогда не вводит 3, но если он вводит 3 во время выполнения, все выполнение становится неопределенным? Как только становится на 100% уверенным, что программа вызовет неопределенное поведение (и не раньше этого), поведение становится разрешенным. Эти мои утверждения на 100% верны?
usr
3
@usr: Я считаю, что это правильно, да. В вашем конкретном примере (и сделав некоторые предположения о неизбежности обрабатываемых данных) я думаю, что реализация может в принципе заглянуть вперед в буферизованном STDIN для a, 3если она захочет, и упаковать домой на день, как только она увидит один входящий.
Стив Джессоп
3
Дополнительный +1 (если бы я мог) для вашего PS
Фред Ларсон
10

Стандартные состояния на 1.9 / 4

[Примечание: этот международный стандарт не предъявляет требований к поведению программ, которые содержат неопределенное поведение. - конец примечания]

Интересно, наверное, что означает «содержать». Чуть позже в 1.9 / 5 говорится:

Однако, если любое такое выполнение содержит неопределенную операцию, настоящий международный стандарт не налагает никаких требований на реализацию, выполняющую эту программу с этим вводом (даже в отношении операций, предшествующих первой неопределенной операции).

Здесь конкретно упоминается «выполнение ... с этим вводом». Я бы интерпретировал это как неопределенное поведение в одной возможной ветке, которая не выполняется прямо сейчас, не влияет на текущую ветвь выполнения.

Однако другой проблемой являются предположения, основанные на неопределенном поведении во время генерации кода. См. Ответ Стива Джессопа для получения более подробной информации об этом.

Danvil
источник
1
Если понимать буквально, это смертный приговор для всех существующих программ.
usr
6
Я не думаю, что вопрос был в том, может ли UB появиться до того, как код действительно будет достигнут. Вопрос, как я понял, был ли UB, если код вообще не дойдёт. И, конечно же, ответ - «нет».
sepp2k
Что ж, стандарт не так ясно об этом в 1.9 / 4, но 1.9 / 5 можно интерпретировать как то, что вы сказали.
Danvil
1
Примечания не являются нормативными. 1.9 / 5 превосходит примечание в 1.9 / 4
MSalters
5

Поучительный пример:

int foo(int x)
{
    int a;
    if (x)
        return a;
    return 0;
}

И текущий GCC, и текущий Clang оптимизируют это (на x86) для

xorl %eax,%eax
ret

потому что они выводят, что xэто всегда ноль из UB в if (x)пути управления. GCC даже не выдаст предупреждение об использовании неинициализированного значения! (поскольку проход, в котором применяется указанная выше логика, выполняется перед проходом, который генерирует предупреждения о неинициализированном значении)

Zwol
источник
1
Интересный пример. Довольно неприятно, что включение оптимизации скрывает предупреждение. Это даже не задокументировано - в документации GCC только сказано, что включение оптимизации вызывает больше предупреждений.
sleske
@sleske Это неприятно, я согласен, но предупреждения о неинициализированных значениях, как известно, трудно "получить правильно" - их точное выполнение эквивалентно проблеме остановки, и программисты становятся до странности иррациональными в отношении добавления "ненужных" инициализаций переменных для подавления ложных срабатываний, так что авторы компилятора запутались. Я имел обыкновение взламывать GCC и помню, что все боялись связываться с проходом с предупреждением о неинициализированном значении.
zwol
@zwol: Мне интересно, какая часть «оптимизации», возникающая в результате такого удаления мертвого кода, на самом деле делает полезный код меньше, а какая в конечном итоге заставляет программистов делать код больше (например, добавляя код для инициализации, aдаже если во всех обстоятельствах, когда неинициализированный aбудет передан функции, которая никогда не будет с ней ничего делать)?
supercat
@supercat Я не был глубоко вовлечен в работу над компилятором около 10 лет, и почти невозможно рассуждать об оптимизации на игрушечных примерах. Если я правильно помню, этот тип оптимизации имеет тенденцию быть связан с общим сокращением размера кода на 2-5% в реальных приложениях.
zwol
1
@supercat 2-5% - это огромная сумма, когда все идет. Я видел, как люди потеют на 0,1%.
zwol
4

В текущем рабочем проекте C ++ в версии 1.9.4 говорится, что

Этот международный стандарт не предъявляет требований к поведению программ, которые содержат неопределенное поведение.

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

Есть две действительно хорошие статьи о поведении undefined и о том, что обычно делают компиляторы:

Йенс
источник
1
Это не имеет смысла. Функция int f(int x) { if (x > 0) return 100/x; else return 100; }определенно никогда не вызывает неопределенное поведение, даже если 100/0оно, конечно, не определено.
fgp
1
@fgp Однако стандарт (особенно 1.9 / 5) говорит о том, что если может быть достигнуто неопределенное поведение , не имеет значения, когда оно будет достигнуто. Например, печать чего-либо printf("Hello, World"); *((char*)NULL) = 0 не гарантируется. Это способствует оптимизации, поскольку компилятор может свободно изменять порядок операций (конечно, с учетом ограничений зависимости), которые, как он знает, в конечном итоге произойдут, без необходимости принимать во внимание неопределенное поведение.
fgp
Я бы сказал, что программа с вашей функцией не содержит неопределенного поведения, потому что нет ввода, где будет оцениваться 100/0.
Йенс
1
Точно - так что важно то, может ли UB действительно сработать или нет, а не то, может ли он теоретически сработать. Или вы готовы возразить, что int x,y; std::cin >> x >> y; std::cout << (x+y);можно сказать, что «1 + 1 = 17», только потому, что есть некоторые входные данные, которые x+yпереполняются (что является UB, поскольку intэто тип со знаком).
fgp
Формально я бы сказал, что программа имеет неопределенное поведение, потому что существуют входные данные, которые запускают ее. Но вы правы, что это не имеет смысла в контексте C ++, потому что было бы невозможно написать программу без неопределенного поведения. Я бы хотел, чтобы в C ++ было меньше неопределенного поведения, но язык работает не так (и для этого есть несколько веских причин, но они не касаются моего повседневного использования ...).
Йенс
3

Слово «поведение» означает, что что-то делается . Государственный деятель, который никогда не исполняется, не является «поведением».

Иллюстрация:

*ptr = 0;

Это неопределенное поведение? Предположим, мы ptr == nullptrхотя бы раз за время выполнения программы уверены на 100% . Ответ должен быть положительным.

Как насчет этого?

 if (ptr) *ptr = 0;

Это не определено? (Помните ptr == nullptrхотя бы раз?) Надеюсь, что нет, иначе вы вообще не сможете написать какую-либо полезную программу.

Этот ответ не пострадал ни от одного шрандардца.

п. 'местоимения' м.
источник
3

Неопределенное поведение проявляется, когда программа вызывает неопределенное поведение независимо от того, что происходит дальше. Однако вы привели следующий пример.

int num = ReadNumberFromConsole();

if (num == 3) {
 PrintToConsole(num);
 *((char*)NULL) = 0; //undefined behavior
}

Если компилятор не знает определения PrintToConsole, он не может удалить if (num == 3)условное выражение . Предположим, у вас есть LongAndCamelCaseStdio.hсистемный заголовок со следующим объявлением PrintToConsole.

void PrintToConsole(int);

Ничего особенного, хорошо. Теперь давайте посмотрим, насколько злой (или, возможно, не такой злой, неопределенное поведение могло быть хуже) поставщик, проверив фактическое определение этой функции.

int printf(const char *, ...);
void exit(int);

void PrintToConsole(int num) {
    printf("%d\n", num);
    exit(0);
}

На самом деле компилятор должен предположить, что любая произвольная функция, которую компилятор не знает, что она делает, может завершиться или вызвать исключение (в случае C ++). Вы можете заметить, что *((char*)NULL) = 0;он не будет выполнен, так как выполнение не будет продолжено после PrintToConsoleвызова.

Неопределенное поведение проявляется, когда PrintToConsoleдействительно возвращается. Компилятор ожидает, что этого не произойдет (так как это заставит программу выполнять неопределенное поведение, несмотря ни на что), поэтому может произойти все, что угодно.

Однако давайте рассмотрим другое. Допустим, мы выполняем нулевую проверку и используем переменную после нулевой проверки.

int putchar(int);

const char *warning;

void lol_null_check(const char *pointer) {
    if (!pointer) {
        warning = "pointer is null";
    }
    putchar(*pointer);
}

В этом случае легко заметить, что lol_null_checkтребуется указатель, отличный от NULL. Отнесение к глобальному энергонезависимомуwarning переменной - это не то, что могло бы выйти из программы или вызвать какое-либо исключение. Также pointerявляется энергонезависимым, поэтому он не может волшебным образом изменить свое значение в середине функции (если это так, это неопределенное поведение). Вызов lol_null_check(NULL)вызовет неопределенное поведение, которое может привести к тому, что переменная не будет назначена (потому что в этот момент известен факт, что программа выполняет неопределенное поведение).

Однако неопределенное поведение означает, что программа может делать все, что угодно. Следовательно, ничто не мешает неопределенному поведению вернуться в прошлое и привести к сбою вашей программы до выполнения первой строки int main(). Это неопределенное поведение, оно не должно иметь смысла. Он также может дать сбой после ввода 3, но поведение undefined вернется в прошлое и выйдет из строя еще до того, как вы даже наберете 3. И кто знает, возможно, поведение undefined перезапишет вашу системную оперативную память и вызовет сбой вашей системы через две недели, пока ваша неопределенная программа не запущена.

Конрад Боровски
источник
Все действительные баллы. PrintToConsoleэто моя попытка вставить внешний побочный эффект программы, который виден даже после сбоев и строго упорядочен. Я хотел создать ситуацию, когда мы можем точно сказать, оптимизирован ли этот оператор. Но вы правы в том, что он может никогда не вернуться; Ваш пример записи в глобальный может быть предметом других оптимизаций, не связанных с UB. Например, можно удалить неиспользуемый глобал. У вас есть идея создать внешний побочный эффект таким образом, чтобы гарантированно вернуть контроль?
usr
Могут ли какие-либо наблюдаемые во внешнем мире побочные эффекты быть вызваны кодом, который компилятор может принять на себя? Насколько я понимаю, даже метод, который просто считывает volatileпеременную, может законно инициировать операцию ввода-вывода, которая, в свою очередь, может немедленно прервать текущий поток; обработчик прерывания может убить поток до того, как у него появится возможность выполнить что-либо еще. Я не вижу оправдания, по которому компилятор мог бы продвигать неопределенное поведение до этого момента.
supercat 05
С точки зрения стандарта C, не было бы ничего противозаконного в том, что Undefined Behavior заставляет компьютер отправлять сообщение некоторым людям, которые будут отслеживать и уничтожать все свидетельства предыдущих действий программы, но если действие может завершить поток, тогда все, что упорядочено до этого действия, должно было произойти до любого неопределенного поведения, которое произошло после него.
supercat 05
1

Если программа достигает оператора, который вызывает неопределенное поведение, никакие требования не предъявляются ни к одному из результатов / поведения программы; не имеет значения, будут ли они иметь место «до» или «после» вызова неопределенного поведения.

Ваши рассуждения по поводу всех трех фрагментов кода верны. В частности, компилятор может обрабатывать любой оператор, который безоговорочно вызывает неопределенное поведение, как GCC обрабатывает __builtin_unreachable(): как подсказку оптимизации, что оператор недоступен (и, следовательно, все пути кода, ведущие к нему безоговорочно, также недоступны). Конечно, возможны и другие подобные оптимизации.

R .. GitHub НЕ ПОМОГАЕТ ICE
источник
1
Из любопытства, когда же __builtin_unreachable()начали проявляться эффекты, движущиеся вперед и назад во времени? Учитывая что-то вроде этого, extern volatile uint32_t RESET_TRIGGER; void RESET(void) { RESET_TRIGGER = 0xAA55; __memorybarrier(); __builtin_unreachable(); }я мог бы builtin_unreachable()счесть полезным сообщить компилятору, что он может пропустить returnинструкцию, но это будет несколько отличаться от того, чтобы сказать, что предыдущий код может быть опущен.
supercat
@supercat, поскольку RESET_TRIGGER непостоянен, запись в это место может иметь произвольные побочные эффекты. Для компилятора это как вызов непрозрачного метода. Следовательно, невозможно доказать (и это не так), что было __builtin_unreachableдостигнуто. Эта программа определена.
usr
@usr: Я бы подумал, что низкоуровневые компиляторы должны рассматривать изменчивые обращения как непрозрачные вызовы методов, но ни clang, ни gcc этого не делают. Среди прочего, вызов непрозрачного метода может привести к тому, что все байты любого объекта, адрес которого был открыт для внешнего мира, и к которому не был и не будет доступ с помощью активного restrictуказателя, будут записаны с использованием unsigned char*.
supercat
@usr: Если компилятор не рассматривает изменчивый доступ как вызов непрозрачного метода в отношении доступа к открытым объектам, я не вижу особых причин ожидать, что он будет делать это для других целей. Стандарт не требует, чтобы реализации делали это, потому что есть некоторые аппаратные платформы, на которых компилятор может знать все возможные эффекты от изменчивого доступа. Однако компилятор, подходящий для встроенного использования, должен понимать, что изменчивый доступ может запускать оборудование, которое не было изобретено на момент написания компилятора.
supercat
@supercat Думаю, ты прав. Кажется, что изменчивые операции «не влияют на абстрактную машину» и поэтому не могут завершить программу или вызвать побочные эффекты.
usr
1

Многие стандарты для многих вещей затрачивают много усилий на описание того, что реализации ДОЛЖНЫ или НЕ ДОЛЖНЫ делать, используя номенклатуру, аналогичную той, которая определена в IETF RFC 2119 (хотя и не обязательно со ссылкой на определения в этом документе). Во многих случаях описания вещей, которые реализации должны выполнять, за исключением случаев, когда они были бы бесполезны или непрактичны , более важны, чем требования, которым должны соответствовать все соответствующие реализации.

К сожалению, стандарты C и C ++ обычно избегают описаний вещей, которые, хотя и не требуются на 100%, тем не менее следует ожидать от качественных реализаций, не документирующих противоположное поведение. Предложение о том, что реализации должны что-то делать, может рассматриваться как подразумевающее, что те, которые этого не делают, являются неполноценными, и в случаях, когда в целом было бы очевидно, какое поведение было бы полезным или практичным, а не непрактичным и бесполезным для данной реализации, было малая осознанная необходимость в Стандарте вмешиваться в такие суждения.

Умный компилятор мог бы соответствовать Стандарту, исключая любой код, который не имел бы никакого эффекта, за исключением случаев, когда код получает входные данные, которые неизбежно вызывают неопределенное поведение, но «умный» и «тупой» не антонимы. Тот факт, что авторы Стандарта решили, что могут быть некоторые виды реализаций, в которых полезное поведение в данной ситуации было бы бесполезным и непрактичным, не подразумевает никакого суждения о том, следует ли считать такое поведение практичным и полезным для других. Если бы реализация могла поддерживать поведенческую гарантию без каких-либо затрат, кроме потери возможности отсечения «мертвой ветви», почти любое значение, которое пользовательский код мог бы получить от этой гарантии, превысило бы стоимость ее предоставления. Устранение мертвых ветвей может подойти в тех случаях, когда не потребуется отказываться от него., Но если в данной ситуации пользовательского кода мог бы справиться практически любое возможное поведение другого , чем устранение мертвой ветви, любое усилие кода пользователь должен затратить , чтобы избежать UB, скорее всего , превысит значение достигнутого с DBE.

суперкар
источник
Это хороший момент, когда отказ от UB может дорого обойтись пользовательскому коду.
usr
@usr: Это момент, который полностью упускают модернисты. Стоит добавить пример? Например, если код должен оценить, x*y < zкогда x*yне происходит переполнения, и в случае переполнения выдает 0 или 1 произвольным образом, но без побочных эффектов, на большинстве платформ нет причин, по которым выполнение второго и третьего требований должно быть дороже, чем соответствует первому, но любой способ написания выражения, гарантирующий стандартное поведение во всех случаях, в некоторых случаях приведет к значительным затратам. Написание выражения (int64_t)x*y < zможет более чем в четыре раза увеличить стоимость вычислений ...
supercat
... на некоторых платформах и написав его так (int)((unsigned)x*y) < z, чтобы компилятор не мог использовать то, что в противном случае могло бы быть полезными алгебраическими заменами (например, если он знает это xи zравны и положительны, он может упростить исходное выражение до y<0, но версия с использованием беззнакового заставит компилятор выполнить умножение). Если компилятор может гарантировать, даже если Стандарт не требует этого, он будет поддерживать требование «yield 0 или 1 без побочных эффектов», пользовательский код может дать компилятору возможности оптимизации, которые он не мог бы получить иначе.
supercat
Да, кажется, здесь была бы полезна более мягкая форма неопределенного поведения. Программист может включить режим, при котором x*yв случае переполнения будет выдаваться нормальное значение, но вообще любое значение. Мне кажется важным настраиваемый UB на C / C ++.
usr
@usr: если бы авторы Стандарта C89 были правдивы, говоря, что продвижение коротких беззнаковых значений для входа в систему было самым серьезным критическим изменением и не были невежественными дураками, это означало бы, что они ожидали, что в тех случаях, когда платформы определяли полезные поведенческие гарантии, реализации для таких платформ делали эти гарантии доступными для программистов, и программисты их использовали, компиляторы для таких платформ продолжали бы предлагать такие поведенческие гарантии, независимо от того, приказывал ли им Стандарт или нет .
supercat