Могут ли компиляторы исключать бесконечные петли?

Ответ 1

C11 разъясняет ответ на этот вопрос, в проекте стандартного раздела C11 6.8.5 Операторы итерации добавили следующий абзац:

Оператор итерации, управляющее выражение которого не является константой выражение, ¹⁵⁶⁾ которое не выполняет операции ввода/вывода, не доступ к неустойчивым объектам и не выполняет никакой синхронизации или атомной операции в его теле, контролирующее выражение или (в случае для утверждения) его выражение-3, может быть принято реализацией для завершения. ¹⁵⁷⁾

и сноска 157 говорит:

Предполагается разрешить преобразования компилятора, такие как удаление пустых петель, даже если завершение не может быть доказано.

Итак, ваш конкретный пример:

while(1) 
  /* noop */;

не справедливая игра для оптимизации, поскольку управляющее выражение является постоянным выражением.

Бесконечные петли как UB

Итак, почему компиляторам разрешено оптимизировать бесконечные циклы с исключением, указанным выше, хорошо, что Ханс Бем создает обоснование для создания бесконечных циклов поведения undefined в: N1528: почему поведение undefined для бесконечных циклов?, следующая цитата дает хорошее представление о проблеме:

Как правильно указывает N1509, текущий проект существенно дает undefined для бесконечных циклов в 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 точек к ациклическому списку, который, как я считаю, превосходит возможности большинства основных компиляторов, и часто невозможно без цельной программы информация.

С99

Так как C99 не имеет такого вырезания, мы бы посмотрели на правило as-if, описанное в разделе 5.1.2.3, в котором в основном говорится, что компилятор должен только эмулировать наблюдаемое поведение программы, требования следующие:

Наименьшие требования к соответствующей реализации:

• В точках последовательности летучие объекты стабильны в том смысле, что предыдущие обращения полный и последующий доступ еще не произошли.
• При завершении программы все данные, записанные в файлы, должны быть идентичны результату, который выполнение программы в соответствии с абстрактной семантикой.
• Динамика входных и выходных сигналов интерактивных устройств должна иметь место, как указано в 7.19.3. Цель этих требований состоит в том, что небуферизованный или строковый буфер появиться как можно скорее, чтобы убедиться, что подсказки действительно появляются до программа, ожидающая ввода.

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

while(1) ;
printf( "hello world\n" ) ;

Многие утверждают, что выполнение прекращения процесса также является наблюдаемым поведением, эта позиция взята в C Compilers Disprove Fermats Последняя теорема:

Компилятору предоставляется значительная свобода в том, как он реализует программу C, но его вывод должен иметь то же внешне видимое поведение, которое программа имела бы при интерпретации "абстрактной машиной C", которая описана в стандарте. Многие знающие люди (включая меня) читают это, говоря, что поведение завершения программы не должно изменяться. Очевидно, что некоторые компиляторы не согласны или не считают, что это имеет значение. Тот факт, что разумные люди не согласны с интерпретацией, как представляется, указывает на то, что стандарт C является ошибочным.

Обновить

Я как-то пропустил последующую работу над вышеупомянутой статьей, Составители и повторное завершение, в котором говорится следующее о разделе 5.1.2.3:

Второе требование - сложное. Если речь идет о завершении программы, запущенной на абстрактной машине, то она неэффективно встречается, потому что наша программа не заканчивается. Если речь идет о завершении фактической программы, сгенерированной компилятором, то реализация C ошибочна, потому что данные, записанные в файлы (stdout - это файл), отличаются от данных, написанных абстрактной машиной. (Это чтение связано с Хансом Бёмом, я не смог поддразнить эту тонкость из стандарта.)

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

Это относится также к бесконечным циклам goto?

Я считаю, что цель состоит в том, что это также относится и к бесконечным циклам goto. В С++ это явно имеет место, так как раздел 1.10 [intro.multithread] говорит:

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

• кончить,
• сделать вызов функции ввода-вывода библиотеки,
• доступ или изменение изменчивого объекта или
• выполнить операцию синхронизации или атомную операцию.

а затем намерение, выраженное в N1528, заключается в том, что стандарты C и С++ согласуются:

Поскольку компиляторы обычно совместно используются компиляторами C и С++, представляется наиболее важным, чтобы WG14 и WG21 соглашались с тем, какое решение принято. Альтернативами было бы специальное обращение с двумя языками по внутреннему интерфейсу или отключение оптимизации при обработке кода C. Ничего не представляется желательным.

и в конце говорит:

WG21 рассматривает улучшенные формулировки, которые делают обработку последовательной. Надеемся, что WG14 проведет все изменения.

В настоящее время стандарт C11 не содержит аналогичную формулировку в разделе 5.1.2.4 многопоточных исполнений и расчётов данных, но, учитывая N1528, кажется разумным предположить, что компиляторы будут обрабатывать бесконечные циклы goto как поведение undefined в C и С++.

Примечание также см. US comment 38 здесь и N3196 это документ, в котором это изменение было применено.

Ответ 2

Невозможно обнаружить бесконечные циклы повсеместно: см. проблема с остановкой. Таким образом, лучший любой компилятор мог бы сделать, это принять достойное предположение - например, очевидный случай, упомянутый в OP.

Но почему это было бы желательно? Я мог видеть, что выдавал предупреждение и все еще допускал поведение, но удалить цикл не является "оптимизацией" - он изменяет поведение программы!

Ответ 3

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

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

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

Ответ 4

Это обсуждалось много раз раньше на comp.lang.c (например, здесь) без, насколько мне известно, какого-либо консенсусного результата.

Ответ 5

Это необходимость при написании демонов. Почему вы хотите назвать их мертвым кодом?

Ответ 6

Я считаю, что более новые стандарты явно предусматривают, что если кусок кода не имеет доступа к каким-либо изменчивым переменным, выполняет ввод-вывод и т.д., любой другой код, который не полагается на что-либо, вычисленное в первой части, может быть произвольно упорядочен до, Если бесконечный цикл не выполняет никаких операций ввода-вывода и не вычисляет какое-либо значение, которое используется позже в программе, компилятор может просто отложить выполнение цикла до тех пор, пока все остальное не завершится.