Разрешено ли компиляторам устранять бесконечные циклы?
Может ли оптимизирующий компилятор удалить бесконечные циклы, что не меняет никаких данных, например
while(1)
/* noop */;
Из анализа компилятора графа потока данных можно сделать вывод, что такой цикл является "мертвым кодом" без каких-либо побочных эффектов.
Запрещено ли удаление бесконечных циклов стандартами C90/C99?
Разрешают ли стандарты C90 или C99 компилятору удалять такие циклы?
Upd: "Microsoft C версии 6.0 по сути сделал эту оптимизацию.", См. Ссылку на caf.
label: goto label;
return 0;
будет преобразован в
return 0;
6 ответов
C11 уточняет ответ на этот вопрос в разделе проекта стандарта C11 6.8.5 В итерационные операторы добавлен следующий абзац:
Оператор итерации, управляющее выражение которого не является константным выражением, 156), который не выполняет никаких операций ввода-вывода, не обращается к изменчивым объектам и не выполняет никаких синхронизирующих или атомарных операций в своем теле, управляющем выражении или (в случае для for утверждение) его выражение-3, может быть принято реализацией для завершения. 157)
и сноска 157 говорит:
Это предназначено для разрешения преобразований компилятора, таких как удаление пустых циклов, даже если завершение не может быть доказано.
Итак, ваш конкретный пример:
while(1)
/* noop */;
не является честной игрой для оптимизации, поскольку управляющее выражение является константным выражением.
Бесконечные циклы как UB
Итак, почему компиляторам разрешено оптимизировать бесконечные циклы с исключением, предоставленным выше, хорошо, Ганс Бем предлагает обоснование для создания неопределенного поведения неопределенного цикла в: N1528: Почему неопределенное поведение для бесконечных циклов? следующая цитата дает хорошее представление о проблеме:
Как правильно указывает N1509, текущий черновик по сути дает неопределенное поведение бесконечным циклам в 6.8.5p6. Основной проблемой для этого является то, что он позволяет коду перемещаться по потенциально не завершающемуся циклу. Например, предположим, что у нас есть следующие циклы, где count и count2 являются глобальными переменными (или у них был взят их адрес), а p является локальной переменной, адрес которой не был взят:
for (p = q; p != 0; p = p -> next) { ++count; } for (p = q; p != 0; p = p -> next) { ++count2; }Могут ли эти два цикла быть объединены и заменены следующим циклом?
for (p = q; p != 0; p = p -> next) { ++count; ++count2; }Без специального разрешения в 6.8.5p6 для бесконечных циклов это было бы запрещено: если первый цикл не завершается, поскольку q указывает на циклический список, оригинал никогда не записывает в count2. Таким образом, он может быть запущен параллельно с другим потоком, который обращается или обновляет count2. Это больше не безопасно с преобразованной версией, которая делает доступ к count2, несмотря на бесконечный цикл. Таким образом, преобразование потенциально вводит гонку данных.
В таких случаях очень маловероятно, что компилятор сможет доказать завершение цикла; необходимо понимать, что q указывает на ациклический список, который, как я считаю, находится за пределами возможностей большинства основных компиляторов и часто невозможен без всей информации о программе.
C99
Поскольку C99 не имеет этого исключения, мы обратимся к правилу " как будто", описанному в разделе 5.1.2.3 что в основном говорит о том, что компилятор должен только эмулировать наблюдаемое поведение программы, требования следующие:
Минимальные требования к соответствующей реализации:
- В точках последовательности изменчивые объекты стабильны в том смысле, что предыдущие обращения завершены, а последующие обращения еще не произошли.
- При завершении программы все данные, записанные в файлы, должны быть идентичны результату, который произойдет при выполнении программы в соответствии с абстрактной семантикой.
- Динамика ввода и вывода интерактивных устройств должна осуществляться, как указано в 7.19.3. Цель этих требований заключается в том, чтобы небуферизованный или линейно-буферизованный вывод появлялся как можно быстрее, чтобы гарантировать, что сообщения-подсказки действительно появляются до того, как программа ожидает ввода.
Строгое прочтение этого может позволить реализации оптимизировать бесконечный цикл. Конечно, мы можем придумать сценарии, в которых оптимизация бесконечного цикла вызовет изменение в наблюдаемом поведении:
while(1) ;
printf( "hello world\n" ) ;
Многие утверждают, что воздействие на завершение процесса также является наблюдаемым поведением, эта позиция взята из C-компиляторов, опровергающих последнюю теорему Ферма:
Компилятору предоставляется значительная свобода в том, как он реализует программу на C, но его выходные данные должны иметь то же внешне видимое поведение, что и программа при интерпретации "абстрактной машиной C", которая описана в стандарте. Многие знающие люди (в том числе и я) считают это тем, что говорят, что поведение при завершении программы не должно изменяться. Очевидно, что некоторые авторы компиляторов не согласны или не верят, что это имеет значение. Тот факт, что разумные люди не согласны с интерпретацией, может указывать на то, что стандарт С имеет недостатки.
Обновить
Я как-то пропустил продолжение к вышеупомянутой статье, Compilers and Termination Revisited, в которой говорится следующее о разделе 5.1.2.3:
Второе требование - хитрое. Если речь идет о прекращении работы программы на абстрактной машине, то это встречается в вакууме, потому что наша программа не завершается. Если речь идет об окончании фактической программы, сгенерированной компилятором, то реализация C ошибочна, поскольку данные, записанные в файлы (stdout - это файл), отличаются от данных, записываемых абстрактной машиной. (Это чтение из-за Ганса Бема; я не смог дразнить эту тонкость вне стандарта.)
Можно также сделать более слабый аргумент, что необходимость создания вырезки в C11 для разрешения удаления пустых циклов подразумевает, что ранее это не было допустимой оптимизацией.
Это относится и к бесконечным циклам goto?
Я полагаю, что намерение состоит в том, что это также относится к бесконечным циклам goto. В C++ это явно так, поскольку раздел 1.10 [intro.multithread] говорит:
Реализация может предполагать, что любой поток в конечном итоге выполнит одно из следующих действий.
- прекратить,
- сделать вызов функции ввода-вывода библиотеки,
- получить доступ или изменить изменчивый объект, или
- выполнить операцию синхронизации или атомарную операцию.
а затем намерение, как выражено в N1528 является то, что стандарт C и C++ согласен:
Поскольку бэкэнды компилятора обычно совместно используются компиляторами C и C++, представляется наиболее важным, чтобы WG14 и WG21 согласовали любое принятое решение. Альтернативы могут заключаться в особой обработке двух языков бэк-эндом или отключении оптимизаций при обработке кода на языке Си. Ни то, ни другое не кажется желательным.
и в конце говорит:
WG21 рассматривает улучшенную формулировку, которая делает обработку последовательной. Надеюсь, WG14 отследит любые возникающие изменения.
В настоящее время стандарт C11 не содержит аналогичной формулировки в разделе 5.1.2.4 Многопоточные исполнения и гонки данных, но с учетом N1528 кажется разумным предположить, что компиляторы будут обрабатывать бесконечные циклы goto как неопределенное поведение в C и C++.
Обратите внимание также на комментарий США 38 здесь и N3196, который является бумагой, с которой это изменение было применено.
Не существует способа универсального обнаружения бесконечных циклов: см. Проблему остановки. Поэтому лучшее, что может сделать любой компилятор, - это сделать приличное предположение - например, очевидный случай, упомянутый в ОП.
Но почему это было бы желательно? Я мог видеть выдачу предупреждения и все еще разрешать поведение, но удалить цикл - это не "оптимизация" - это меняет поведение программы!
Цикл - это не мертвый код, он в основном не позволяет программе достичь того, что последует за ней. Это не то, что произошло бы, если цикл был удален, поэтому компилятор не может удалить цикл.
Он мог бы заменить его зависимой от платформы командой ожидания, чтобы сигнализировать процессору, что поток больше не собирается ничего делать.
То, что может сделать компилятор, это удалить любой код, который идет после цикла, потому что он недоступен и никогда не будет выполнен.
Это обсуждалось много раз, прежде чем на comp.lang.c (например, здесь) без, насколько я знаю, никакого согласованного результата.
Они необходимы при написании демонов. Почему вы хотите назвать их мертвым кодом?
Я полагаю, что более новые стандарты прямо предусматривают, что если часть кода не имеет доступа к каким-либо изменчивым переменным, выполняет ввод-вывод и т. Д., Любой другой код, который не зависит от чего-либо, вычисленного в первом фрагменте, может быть произвольно упорядочен перед ним. Если бесконечный цикл не выполняет никаких операций ввода-вывода и не вычисляет какое-либо значение, которое будет использовано позже в программе, компилятор может просто отложить выполнение цикла до завершения всего остального.