Может ли компилятор C оптимизировать условное сохранение в безусловное?
Возьмите следующий фрагмент кода:
#include <stdbool.h>
bool global;
bool foo(void) {
if (global) {
global = false;
return true;
}
return false;
}
Теоретически этот код равен следующему?
#include <stdbool.h>
bool global;
bool baz(void) {
bool tmp = global;
global = false;
return tmp;
}
Я склонен думать, что foo и baz теоретически эквивалентны: global не изменчив и нет ничего другого, заставляющего компилятор учитывать многопоточность (что-то вроде atomic_bool, например). Поэтому я думаю, что если филиал намного дороже, чем магазин, то компилятор предпочтет использовать решение baz вместо foo. Но я не могу заставить компилятор это сделать, поскольку компилятор GCC 13.2.0 RISC-V с -std=gnu2x -march=rv32if -mabi=ilp32f -O3 -mbranch-cost=2000 по-прежнему приводит к foo. С другой стороны, я также не могу заставить компилятор превратить baz в foo.
Так я ошибаюсь и есть ли теоретическая разница между foo и baz? Или это просто оптимизация GCC (RISC-V?) не берется?
Но компилятору разрешено превращать условный код в безусловный, если нет измеримых побочных эффектов, верно? Простым примером может быть что-то вроде static const bool f = false; if (f) printf("true); else printf("false");, которое каждый раз превращается в printf("false").
Да, но тогда компилятор уже знает состояние f. Когда вызывается ваша функция foo или baz, состояние global неизвестно. Компилятор не может определить значение global.
Но ведь не обязательно делать вывод global, верно? Если global уже было false, то запись false в него не будет иметь измеримых побочных эффектов. Если это было true, то оно должно стать false, поэтому запись обязательна. Таким образом, запись false во всех сценариях имеет те же побочные эффекты, что и запись false, когда глобально было true.
Некоторые современные компиляторы генерируют условный переход, так что, хотя формально в коде HLL есть оператор if, путь выполнения машинного кода не разветвляется (хотя, очевидно, не в GCC RISC-V). Вторая форма, которую вы показываете, всегда будет присваивать глобальному значению false каждый раз, когда она выполняется. Несмотря на это, я ожидаю, что вторая форма все равно будет немного быстрее. Я ожидаю, что оба будут встроены на более высоких уровнях оптимизации.
Вы предполагаете, что удаление ветки является оптимизацией.
@Barmar: Нет, они этого не предполагают; в вопросе это прямо указано как условие: «… если филиал намного дороже магазина, то…»
@Бармар Может быть. Многие встроенные системы имеют память с доступом за один цикл, но условный переход все равно может вызвать пузыри в конвейере. Таким образом, существуют реальные сценарии, в которых безусловная запись обходится дешевле, чем ветвление.
@Cheiron Я не утверждаю, что это не так. Но я обычно предполагаю, что авторы компиляторов знают, какие оптимизации являются правильными, поэтому, если они не выполняют эту оптимизацию, она может на самом деле не быть оптимальной.
Удаление ветки приведет к загрязнению строки кэша, не так ли?
@IanAbbott Затрагивает ли это спецификацию C? Возможно, на некоторых платформах вы правы, но некоторые кеши достаточно умны, чтобы не помечать строку как грязную, когда фактических изменений нет, а некоторые процессоры вообще не имеют кешей. В общем, я бы не думал, что составители должны это учитывать.
@Cheiron Нет, спецификация C не касается строк кэша, но это может быть проблема «качества реализации» в компиляторе.
Ответы 2
Изменение объекта — это то, что C формально называет побочным эффектом (c17 5.1.2.3), и компиляторам не разрешено оптимизировать «необходимые побочные эффекты», но «необходимость» — это довольно субъективно...
Стандарт C на самом деле ничего не говорит о том, разрешено ли компиляторам добавлять новые побочные эффекты, отсутствующие в исходном коде. Там просто говорится, что компилятору не разрешено влиять на результат программы - "наблюдаемое поведение". Доступ к объекту volatile влияет на наблюдаемое поведение, но здесь это неприменимо.
Замена первой функции второй — это ручная оптимизация, которую может выполнить, по крайней мере, программист. Я не уверен, почему ни gcc, ни clang не оптимизируют код для удаления ветки, но мы склонны иногда переоценивать оптимизаторы — они не работают по волшебству.
Однако, если вы измените код на
global = false;
global = false;
Тогда «нужен» только один побочный эффект, и его можно удалить, поскольку объект не является volatile и запись в простые переменные не имеет особого значения, кроме побочных эффектов. Дополнительная запись здесь оптимизируется.
Обратите внимание, что компилятор, вероятно, понятия не имеет, как внешняя переменная связи global может использоваться где-либо в программе, что может ограничить возможные оптимизации.
«Обратите внимание, что компилятор, вероятно, понятия не имеет, как внешняя переменная связи global может использоваться где-либо еще в программе, что может ограничить возможные оптимизации». Но так ли это? Существует общее предположение, что программа однопоточная и память не меняется без прямого вмешательства со стороны кода (вы можете нарушить оба этих предположения, используя атомику или volatile, но ни то, ни другое здесь не используется). Именно из-за этого предположения написание многопоточного кода или использование прерываний является своего рода минным полем.
@Cheiron Threading не поэтому. Он просто не может предполагать, что внешние функции, вызываемые из той же единицы перевода, что и он сам, не изменяют переменную. Это, в свою очередь, ограничивает такие оптимизации, как встраивание + изменение порядка. Переменную придется перезагружать из ОЗУ каждый раз, когда вызывается функция и т. д. и т. п.
Эти две функции различаются в многопоточной среде. Рассмотрим, что произойдет, если существует поток, который время от времени читает global и вызывает foo или baz, пока global содержит false. В этой ситуации foo не будет сохраняться в global, но baz будет.
C 2018 5.1.2.4 4 определяет конфликт:
Две оценки выражения конфликтуют, если одна из них изменяет ячейку памяти, а другая читает или изменяет ту же ячейку памяти.
C 2018 51.2.4 35 говорит:
Выполнение программы содержит гонку данных, если она содержит два конфликтующих действия в разных потоках, по крайней мере одно из которых не является атомарным, и ни одно из них не происходит раньше другого. Любая такая гонка данных приводит к неопределенному поведению.
Это означает, что поведение с baz не определено, поскольку модификация global (примечание 2 в C 2018 3.1 3 говорит нам, что «'Изменить' включает случай, когда новое сохраняемое значение совпадает с предыдущим значением.») в потоке вызов baz конфликтует с чтением в другой теме.
Однако поведение с foo в этой ситуации остаётся определённым, поскольку оно не изменяет global. (Поскольку поведение baz не определено, компилятор может сгенерировать для него тот же код, что и для foo.)
Обратите внимание, что это различие в семантике подпрограмм не мешает компилятору генерировать для них один и тот же код. В одном потоке две процедуры имеют одинаковую семантику, определенную стандартом C:
- Ни в одной из подпрограмм нет наблюдаемого поведения (нет доступа к изменчивым объектам, нет данных, записываемых в файлы, нет взаимодействия ввода/вывода).
- После вызова любой из подпрограмм
globalсодержитfalseи возвращаемое значение равноtrue. - Ни одна из подпрограмм не вносит никаких других изменений в состояние программы.
Следовательно, независимо от того, какая подпрограмма вызывается, однопоточное воздействие на наблюдаемое поведение и состояние абстрактной машины одинаково.
Просто чтобы уточнить: вы утверждаете, что такая функция, как baz, всегда будет считаться неопределенным поведением, если вы используете -std=c18 или выше?
@Cheiron: Нет. Я процитировал C 2018, потому что это текущий стандарт C, а не потому, что его спецификации многопоточности отличаются от более ранних или (ожидаемых) более поздних версий. Также baz не обязательно имеет неопределенное поведение. Как я уже писал, его семантика отличается от foo. Имеет ли программа, в которой она находится, определенное поведение или неопределенное поведение, является функцией как baz, так и других вещей в программе, а не только baz.
Можете ли вы сказать, что для целей спецификации языка сохранение того же значения в объекте, которое этот объект уже содержит, считается модификацией? Этот ответ предполагает это, но я не нахожу этого явно выраженным в спецификации.
@JohnBollinger: В этом ответе цитируется примечание 2 в C 2018 3.1 3: ««Изменить» включает случай, когда новое сохраняемое значение совпадает с предыдущим значением». 3.1 определяет «доступ» как «чтение или изменение значения объекта», а в примечании 2 говорится, что «модификация» включает сохранение уже имеющегося значения.
Нет, эти две функции не эквивалентны. В первом присвоение
globalусловное, во втором — безусловное. Компилятор может (и, вероятно, будет) генерировать для них другой код, даже при сборке с включенной оптимизацией.