Может ли оптимизирующий компилятор при встраивании функции C разыменовывать указатель большее количество раз, чем явно написано в исходном коде?
Рассмотрим следующий код:
int y = 1;
int* p = &y;
inline int f(int x) {
return x + x;
}
int g(void) {
return f(*p);
}
В этом коде есть одно явное разыменование.
Разрешено ли компилятору C компилировать/оптимизировать этот код примерно так:
int g(void) {
return *p + *p;
}
То есть, может ли компилятор при встраивании f выполнять и использовать два отдельных доступа к целевой памяти, в отличие от единственного доступа, который был фактически записан? Есть ли в спецификации C определенные разделы, которые разрешают или запрещают такое поведение? Обратите внимание, что в этом примере p не является изменчивым, а «оптимизированный» код, по крайней мере, функционально корректен.
(Обратите внимание, вопрос не в том, «сделает ли компилятор это» или «должен ли компилятор сделать это», а скорее, согласно спецификациям C, может ли компилятор сделать это. Предположим, утечка регистров делает второе разыменование более эффективным, или что-то в этом роде).
Ссылаясь на спецификацию C99, я вижу некоторые возможные намеки на необходимую обработку параметров. Мне интересно, может ли «каждому параметру присвоено значение соответствующего аргумента» (6.5.2.2) или «его идентификатор [параметра] является lvalue» (6.9.1), но такая интерпретация кажется несовместимой с некоторыми из распространенных оптимизаций параметров, которые я видел.
@john - Я бы предпочел ожидать, что оптимизирующий компилятор поймет, что *p — это то же самое, что y, а y — это 1. Итак, f(*p) можно заменить на f(1). А еще мы знаем, что такое 1+1...
@EricPostpischil Любой компилятор C может делать все, что захочет, если он соответствует спецификации языка.
@user207421: user207421: Стандарт C позволяет компилятору делать все, что ему нравится, если он соответствует. Однако вопрос не касается «компилятора C». Там спрашивается об «оптимизирующем компиляторе C». Это имеет два требования к компилятору: первое — это компилятор C, что в данном контексте означает, что он соответствует стандарту C. Во-вторых, это оптимизирующий компилятор. Преобразование одного чтения памяти в два может соответствовать стандарту C, но не соответствует второму требованию, указанному в вопросе. Это не оптимизация.
@EricPostpischil Я не согласен - предположим, что какая-то странная архитектура имеет ограниченную ISA и файл регистра, который медленнее, чем доступ к памяти: двойной доступ к одной и той же памяти может быть быстрее, чем загрузка ее в регистр и использование ее там. Рассмотрим архитектуры только с одним рабочим регистром, который может быть источником или местом назначения, но не обоими одновременно (возможно, это часто встречается в PIC) - он может либо загружать, затем сохранять и загружать временный регистр из стека, либо просто двойную загрузку из памяти, что будь быстрее. Но это все на самом деле не по делу – вопрос на самом деле просто в том, «разрешено ли это?».
@johnsmith: Это шутка, пойми это.
Хотя ничто не мешает компилятору дважды прочитать это местоположение (поскольку чтение не считается побочным эффектом), мой опыт показывает, что компиляторы активно избегают этого. Что не так уж и странно, поскольку чтение памяти — относительно дорогая операция в большинстве систем. Обычное поведение заключается в чтении значения в регистр и дальнейшем сохранении его в регистре — это верно даже для сильно ограниченных 8-битных микроконтроллеров. Разумный компилятор для младшей 8-битной версии мог бы переупорядочить код так, чтобы все вычисления, относящиеся к одному значению, выполнялись в одном и том же месте.
Для справки, технический термин такого рода трансформации — изобретение нагрузок.
Ответы 3
Может ли оптимизирующий компилятор при встраивании функции C разыменовывать указатель большее количество раз, чем явно написано в исходном коде?
Да, при условии, что это не указатель на тип volatile.
Однако при использовании указателя на атомарный тип компилятору, возможно, придется также гарантировать, что референт не может быть изменен другим потоком между двумя разыменованиями. (Спасибо, @Eric) В частности, рассмотрим этот вариант:
_Atomic int y = 1;
_Atomic int *p = &y;
inline int f(int x) {
return x + x;
}
int g(void) {
return f(*p);
}
Предположим, что p никогда не переназначается и что y никогда не принимает значение больше INT_MAX / 2, семантика абстрактной машины требует, чтобы каждое вычисление f(*p) давало в два раза некоторое значение, которое y удерживало в какой-то момент во время выполнения программы. Это может быть проблематично, если этот вызов функции вычисляется как *p + *p, возможно, требуя добавления блокировки или чего-то подобного, но это зависит от контекста. Однако это актуально только в том случае, если результат вызова функции, несовместимый с семантикой абстрактной машины, может проявить изменение в наблюдаемом поведении программы. Это не обязательно так.
Однако если p не указывает на атомарный объект, то конфликтующие доступы приведут к неопределенному поведению, и в этом случае все, что реализация решит с ним сделать, является приемлемым.
То есть, может ли компилятор при встраивании f выполнять и использовать два отдельный доступ к целевой памяти, в отличие от единственного доступ, который был на самом деле написан?
Да, хотя это редко будет означать улучшение, поэтому я не ожидаю, что какой-либо компилятор действительно сделает это.
Есть ли специальные разделы в C? спецификация, которая разрешает или запрещает такое поведение?
Да.
В контексте C17 5.1.2.3/1:
Семантические описания в настоящем стандарте описывают поведение абстрактной машины, в которой решаются вопросы оптимизации. не имеющий отношения.
А основным положением, позволяющим оптимизировать, является C17 5.1.2.3/6:
Наименьшие требования к соответствующей реализации:
Доступ к изменчивым объектам оценивается строго по правилам абстрактной машины.
При завершении программы все данные, записанные в файлы, должны быть идентичны результату выполнения программы в соответствии с возникла бы абстрактная семантика.
Динамика ввода и вывода интерактивных устройств должна осуществляться, как указано в 7.21.3. Цель этих требований состоит в том, что вывод без буферизации или с линейной буферизацией появляется как можно скорее, чтобы убедитесь, что сообщения с подсказками действительно появляются перед программой ожидание ввода.
Это наблюдаемое поведение программы.
Наименьшие требования означают, что пока реализация удовлетворяет этим требованиям, она может делать это любыми способами по своему выбору. Именно это обеспечивает оптимизацию.
Ссылаясь на спецификацию C99,
C99 давно устарел, хотя вывод для этой версии тот же. С тех пор существовал C11 и нынешняя версия C17. А C2X находится на завершающей стадии ратификации.
Я вижу некоторые возможные намеки на необходимая обработка параметров. Мне интересно, «каждый параметру присваивается значение соответствующего аргумента" (6.5.2.2) или «его идентификатор [параметра] является lvalue» (6.9.1) может предотвратить этот сценарий, но такая интерпретация кажется несовместим с некоторыми из моих общих оптимизаций параметров видимый.
Эти детали описывают поведение абстрактной машины. Реализации не обязаны им соответствовать, если они обеспечивают правильное наблюдаемое поведение.
Атомарные объекты также следует учитывать.
Я действительно учитывал их при составлении этого ответа, @EricPostpischil, и, насколько я могу определить, атомарные объекты учитываются только постольку, поскольку семантика доступа к ним является частью семантики абстрактной машины. C не придает volatile-подобное значение доступу к не-volatile атомарным объектам в отношении наблюдаемого поведения программы.
Что произойдет, если p является указателем на атомарный тип, а другой поток изменяет *p между двумя чтениями *p? В абстрактной машине x + x будет производить сумму одного значения в результате чтения *p, но реализация двух чтений может дать сумму двух разных значений. Когда сумма используется в последующем коде, наблюдаемое поведение может отличаться.
@EricPostpischil, ваше «между» не является частью наблюдаемого поведения программы. Когда существует несколько наблюдаемых вариантов поведения, соответствующих семантике абстрактной машины, реализация может удовлетворить минимальным требованиям, создав любое из них. С учетом вышесказанного мое первоначальное «да» не следует воспринимать как утверждение о том, что могут быть выполнены произвольные дополнительные разыменования. Можно было бы построить более сложные примеры, где конкретные случаи двойного, а не одинарного разыменования не могут быть правильными, но я считаю, что это не то, о чем задается вопрос.
Код OP, модифицированный для использования атомарного типа, будет иметь два разрешенных наблюдаемых поведения: одно, где x + x использует значение до изменения другого потока *p, и другое, где оно использует значение после изменения другого потока *p. Не существует допустимого наблюдаемого поведения, при котором используются два разных значения.
Спасибо, @EricPostpischil, я добавил обсуждение дополнительных соображений, связанных с указателями на атомарные объекты. Это не исключает пессимизации, о которой спрашивает ФП, но может потребоваться еще большая пессимизация (например, также установка блокировки вокруг двух разыменований).
Это очень полезно. Предположим, что аспект оптимизации удален из вопроса, изменит ли это ответ? Например. (за исключением случаев изменчивости или атомарности) C17 позволит «x = *p; return x + x;» будет реализовано как «return *p + *p;» ? (Грубо говоря, будет ли что-нибудь в спецификации запрещать дублирование доступа к энергонезависимой переменной или требовать назначения *p в отдельное хранилище и т. д.). Я плохо понимаю, какие требования (если таковые имеются) спецификация предъявляет к внутренностям абстрактной машины - похоже, правильность определяется исключительно наблюдаемым поведением?
@johnsmith, называете ли вы это «оптимизацией», не имеет значения. Так же, действительно ли поведение реализации улучшает производительность или размер кода. Этот ответ уже описывает (довольно широкую) свободу действий, предоставляемую реализациям, чтобы вести себя иначе, чем абстрактная машина, в терминах которой определяется семантика языка, при условии, что создается такое же наблюдаемое поведение.
В отличие от таких языков, как Java, которые используют относительно слабую модель памяти, но, тем не менее, определяют последствия гонок за данные как получение при каждом чтении старых или новых данных, иногда выбираемых произвольно, стандарт C полностью отказывается от юрисдикции в отношении того, как реализации интерпретируют гонки за данными. Это позволяет gcc переводить что-то вроде:
unsigned short test(unsigned short *p)
{
unsigned short temp = *p;
return temp - (temp >> 15);
}
таким образом, чтобы за счет добавления дополнительного разыменования избежать необходимости вычитания при нацеливании на ARM Cortex-M0. Сгенерированный код для вышеизложенного эквивалентен:
unsigned short test(unsigned short *r0)
{
unsigned r1 = 0;
short r2 = *((short*)r0+r1);
unsigned r3 = *r0;
r2 >>= 15;
r3 += r2;
return (unsinged short)r3;
}
Этот конкретный пример возникает даже тогда, когда функция не встраивается, но я не вижу причин полагать, что то же самое не произойдет при встраивании функций.
Многие разработчики компиляторов придерживаются мнения, что любая потенциальная оптимизация, которой можно было бы способствовать путем добавления дополнительных операций разыменования, менее полезна, чем семантические гарантии в стиле Java, которые позволяют программам выдерживать мягкие гонки данных без необходимости добавления дорогостоящей памяти. барьеры для их устранения, но такое мнение не разделяют сопровождающие gcc и, вероятно, не разделяют и clang.
Я знаю, что вы это знаете, но предполагаемым решением этой проблемы в C было memory_order_relaxed, которое на типичных платформах не вводит никаких «дорогостоящих барьеров памяти» и продолжает использовать обычные инструкции загрузки и сохранения. Главное, что он делает, — это подавляет оптимизации, подобные изобретенным нагрузкам, обсуждаемым здесь. Таким образом, вы можете продолжать извлекать из них выгоду, используя неатомарные переменные в тех местах, где вы уверены, что гонки данных не возникают. В коде, где могут возникнуть гонки данных и вам просто нужно убедиться, что они остаются «безопасными», вы используете атомарные объекты с memory_order_relaxed.
Таким образом, в каком-то смысле C действительно дает вам возможность использовать модель памяти, подобную Java, если вы перепишете свой код, чтобы весь доступ к памяти выполнялся с помощью memory_order_relaxed загрузок и сохранений - хотя, конечно, это сделает его очень многословным и нечитаемым. Но, в отличие от Java, он также дает вам возможность не отказываться от таких оптимизаций, как изобретенные нагрузки.
@NateEldredge: Это было бы решение, если бы существовал механизм установки значений по умолчанию. Конечно, существует множество ситуаций, когда изобретенные нагрузки безвредны, и в некоторых из них они могут облегчить полезную оптимизацию, но сделать язык непригодным для целей, для которых он был разработан. Более того, поддержка правильной семантики памяти не должна зависеть от поддержки атомарности, которая на многих платформах была бы просто нарушена.
TL;DR: Да, это разрешено.
Обычно трудно прямо ответить на вопрос типа «разрешено ли это преобразование», прочитав стандарт C. В принципе, это требует от вас взглянуть на правила языка и доказать, что каждый возможный фрагмент кода, наблюдаемое поведение которого четко определено стандартом, будет иметь такое же наблюдаемое поведение после преобразования. Или, если его поведение не указано (т. е. существует некоторый набор допустимых вариантов поведения), то после преобразования его поведение все равно будет находиться в этом наборе.
Однако можно рассуждать немного более неформально. Если бы описанное здесь преобразование (иногда называемое изобретением нагрузок) было недопустимым, должен был бы существовать некоторый код, чье четко определенное наблюдаемое поведение изменилось бы. Вы можете получить представление о законности, придумав фрагмент кода, фактическое поведение которого будет меняться, а затем спросить, действительно ли это поведение определено стандартом.
Если были выполнены две загрузки, то результат может отличаться только в том случае, если эти две загрузки не вернули одно и то же значение. (Мы можем предположить, что по крайней мере один из них вернет то же значение, что и одиночная загрузка в непреобразованной версии x + x.) Как это может произойти на реальной машине? Если загрузка выполняется в обычную память (в отличие от аппаратного регистра, отображаемого в памяти, или чего-то еще, и в этом случае потребуется volatile), то единственный способ это произойти - если какой-то другой объект в системе выполнил сохранение по этому адресу. В стандарте C единственным определенным механизмом одновременного доступа двух разных объектов к одной и той же памяти являются потоки.
Таким образом, примером кода, на наблюдаемое поведение которого может повлиять это преобразование, может быть код, в котором какой-то другой поток одновременно выполняет сохранение в *p. Однако это будет представлять собой гонку данных, которую C явно определяет как вызывающую неопределенное поведение (см. 5.1.2.4, стр. 35), и поэтому на самом деле это недопустимый пример. Если гоночный код изначально не имел четко определенного поведения, то тот факт, что это преобразование меняет свое поведение, не является препятствием для законности преобразования.
Так что, хотя это и не доказательство, это сильное предположение, что эта трансформация законна. И действительно, это преобразование действительно осуществят реальные компиляторы. Вот пример (болт бога) , заимствованный из моего ответа на Какие типы на 64-битном компьютере естественным образом являются атомарными в gnu C и gnu C++? -- это означает, что у них есть атомарное чтение и атомарная запись (ответ категорически отсутствует).
Нет, оптимизирующий компилятор не может этого сделать, потому что это не оптимизация. Деоптимизирующий компилятор может это сделать и будет соответствовать стандарту C, поскольку реализация программы с одним или двумя доступами будет иметь такое же наблюдаемое поведение в той степени, в которой оно определено. Почему вы имеете в виду C99, которому уже более двух десятилетий и который был заменен более новыми версиями?