Каково обоснование строгого правила псевдонимов?

В настоящее время меня интересует обоснование строгого правила псевдонимов. Я понимаю, что определенные псевдонимы не разрешены в C и что намерение состоит в том, чтобы разрешить оптимизацию, но я удивлен, что это было предпочтительным решением по сравнению с трассировкой приведения типов, когда был определен стандарт.

Итак, по-видимому, следующий пример нарушает строгое правило псевдонимов:

uint64_t swap(uint64_t val)
{
    uint64_t copy = val;
    uint32_t *ptr = (uint32_t*)© // strict aliasing violation
    uint32_t tmp = ptr[0];
    ptr[0] = ptr[1];
    ptr[1] = tmp;
    return copy;
}

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

Итак, какие проблемы со строгим правилом алиасинга я пропустил, которые компилятор не может легко решить для автоматического обнаружения возможных оптимизаций)?


person Julius    schedule 28.12.2018    source источник
comment
Вы смотрели на канонические вопросы и ответы о строгом псевдониме и что это значит. «Почему» в основном «потому что это позволяет проводить более мощную оптимизацию»; это обычная причина. То же самое с переполнением целого числа со знаком.   -  person Jonathan Leffler    schedule 28.12.2018
comment
@JonathanLeffler Да, наверное, я не думал о компиляторе без оптимизации, а скорее о компиляторе, который определяет, когда такая оптимизация невозможна.   -  person Julius    schedule 28.12.2018
comment
Есть ли у вас опыт работы с системами, отличными от x86? Те, у кого есть строгие ограничения выравнивания для разных типов данных, таких как double или long, должны быть на 8-байтовой границе, чтобы ваш процесс не был убит с помощью чего-то вроде SIGBUS? Технически это не является строгой проблемой псевдонимов, но затрагивает множество тех же основных проблем.   -  person Andrew Henle    schedule 28.12.2018
comment
@AndrewHenle Да, я знаю об этом, и вы правы - это определенно стоит упомянуть. Однако в настоящее время меня интересует только строгое правило псевдонимов.   -  person Julius    schedule 28.12.2018
comment
uint64_t почти по определению подходит для uint32_t @AndrewHenle, так что это точно не проблема.   -  person Antti Haapala    schedule 28.12.2018
comment
Рассмотрим отдельную компиляцию.   -  person curiousguy    schedule 28.12.2018
comment
Отмеченная строка не является строгим нарушением алиасинга. Нарушение находится на следующей строке.   -  person M.M    schedule 05.01.2019


Ответы (4)


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

Подумайте, содержит ли код вместо этого:

foo(&val, ptr)

где объявление foo равно void foo(uint64_t *a, uint32_t *b);. Тогда внутри foo, который может находиться в другой единице перевода, компилятор не сможет узнать, что a и b указывают на (части) одного и того же объекта.

Тогда есть два варианта: во-первых, язык может разрешать псевдонимы, и в этом случае компилятор при переводе foo не может оптимизировать, полагаясь на тот факт, что *a и *b различны. Например, всякий раз, когда что-то записывается в *b, компилятор должен сгенерировать ассемблерный код для перезагрузки *a, поскольку он мог измениться. Такие оптимизации, как сохранение копии *a в регистрах во время работы с ним, будут запрещены.

Второй выбор, два, состоит в том, чтобы запретить псевдонимы (в частности, не определять поведение, если программа это делает). В этом случае компилятор может провести оптимизацию, полагаясь на то, что *a и *b различны.

Комитет C выбрал второй вариант, потому что он предлагает лучшую производительность, не ограничивая программистов необоснованно.

person Eric Postpischil    schedule 28.12.2018
comment
Спасибо, в этом есть смысл. Однако LTO может решить эту проблему, не так ли? - person Julius; 28.12.2018
comment
@Julius: В таком простом случае мы видим, что foo(&val, ptr) дается два указателя на один и тот же объект. Однако учтите, что указатели могут быть вычислены различными способами. Я ожидаю, что общая проблема определения во время трансляции (включая связывание), могут ли два указателя указывать на один и тот же объект, не поддается вычислению. (Вероятно, похоже на проблему остановки: если бы мы могли ее вычислить, мы могли бы написать процедуру, которая передает тот же адрес тогда и только тогда, когда код для проверки сообщает, что код не передает тот же адрес.) - person Eric Postpischil; 28.12.2018
comment
Я понимаю. Размышляя об этом... Я думаю, что вычисления могут выполняться даже во время выполнения, и это, вероятно, даже невозможно предсказать. Я бы все же предпочел менее ограничивающее правило :-) Спасибо! - person Julius; 28.12.2018
comment
@Julius Джулиус, отсутствие псевдонимов - это то, что делает Fortran таким быстрым по сравнению с C, говорят они ... больше информации на beza1e1.tuxen.de/articles/faster_than_C.html - person Antti Haapala; 28.12.2018
comment
@AnttiHaapala интересно знать, что это может иметь большое влияние. В конце концов, я, конечно же, хочу, чтобы эти оптимизации произошли, я просто хочу, чтобы компилятор был умнее и чтобы были более очевидные и менее ограничивающие правила. - person Julius; 28.12.2018
comment
@Julius: Если бы авторы компилятора серьезно отнеслись к сноске к N1570 6.5p7, все было бы просто. Заявленная цель правила состоит в том, чтобы сказать, когда вещи могут создавать псевдонимы, но ситуации, когда правила вызывают наибольшие проблемы для программистов, это те, где вещи не имеют псевдонимов в коде, как написано но компиляторы переписывают код так, как они делают. Если бы компиляторы могли просто распознавать, что доступ через только что полученное значение lvalue или указатель является доступом к объекту, из которого оно получено, это устранило бы 99% проблем, связанных со строгим правилом псевдонимов. - person supercat; 04.01.2019
comment
Вы забыли третий вариант: напишите правила, предназначенные просто для запрещения псевдонимов, но выражающие это намерение в сноске, а не в нормативном правиле, чтобы позволить тупым авторам компиляторов интерпретировать их как запрещенные конструкции, которые не включают псевдонимы в том виде, в каком они написаны. . - person supercat; 04.01.2019
comment
@Julius компилятор был умнее, чтобы он мог изящно обнаруживать и обрабатывать более очевидные случаи? Насколько очевидно? Вы хотите пойти и написать спецификацию случаев, которые вы хотели бы видеть поддержанными? - person curiousguy; 05.01.2019
comment
@curiousguy: Если бы правило было написано, чтобы сказать, что оно применяется только в тех случаях, когда не было видимой связи между lvalue, используемым для доступа, и чем-либо соответствующего типа, но явно указывалось, что способность распознавать такие отношения в ситуациях, когда они может быть полезной была проблема качества реализации, мог ли кто-нибудь сказать с серьезным видом, что фактическое поведение clang и gcc согласуется с любым добросовестным стремлением вести себя качественно? - person supercat; 28.02.2020

Это позволяет компилятору оптимизировать перезагрузку переменных, не требуя, чтобы вы ограничивали свои указатели.

Пример:

int f(long *L, short *S)
{
    *L=42;
    *S=43;
    return *L;
}

int g(long *restrict L, short *restrict S)
{
    *L=42;
    *S=43;
    return *L;
}

Скомпилировано с gcc -O3 -fno-strict-aliasing на x86_64:

f:
        movl    $43, %eax
        movq    $42, (%rdi)
        movw    %ax, (%rsi)
        movq    (%rdi), %rax ; <<*L reloaded here cuz *S =43 might have changed it
        ret
g:
        movl    $43, %eax
        movq    $42, (%rdi)
        movw    %ax, (%rsi)
        movl    $42, %eax     ; <<42 constant-propagated from *L=42 because *S=43 cannot have changed it  (because of `restrict`)
        ret

Скомпилировано с gcc -O3 (подразумевается -fstrict-alising) на x86_64:

f:
        movl    $43, %eax
        movq    $42, (%rdi)
        movw    %ax, (%rsi)
        movl    $42, %eax   ; <<same as w/ restrict
        ret
g:
        movl    $43, %eax
        movq    $42, (%rdi)
        movw    %ax, (%rsi)
        movl    $42, %eax
        ret

https://gcc.godbolt.org/z/rQDNGt

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

person PSkocik    schedule 28.12.2018

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

Такой код:

float f(int *pi, float *pf) {
  *pi = 1;
  return *pf;
}

при использовании с pi и pf, имеющими один и тот же адрес, где *pf предназначен для переинтерпретации битов недавно написанного *pi, считается неразумным, поэтому уважаемые члены комитета (а до них разработчики C язык) не считал уместным требовать от компилятора избегать преобразования программы здравого смысла в несколько более сложном примере:

float f(int *pi, double *pf) {
  (*pi)++;
  (*pf) *= 2.;
  (*pi)++;
}

Здесь разрешение углового случая, когда оба указателя указывают на один и тот же объект, сделает любое упрощение, когда приращения сливаются, недействительным; предполагая, что такое сглаживание не происходит, код может быть скомпилирован как:

float f(int *pi, double *pf) {
  (*pf) *= 2.;
  (*pi) += 2;
}
person curiousguy    schedule 04.01.2019
comment
Насколько я понимаю, выделенный жирным шрифтом текст не совсем подходит для C89. Основной мотивацией для правил C89 была поддержка поведения существующих реализаций. - person M.M; 05.01.2019
comment
@MM Даже в этом случае существующие реализации отражают только интуицию разработчиков этих компиляторов WRT, что является разумной практикой здравого смысла. - person curiousguy; 05.01.2019
comment
Согласно опубликованному документу с обоснованием, авторы стандарта C не пытались указать все, что должна делать реализация, чтобы быть подходящей для какой-либо конкретной цели, а вместо этого ожидали, что рынок будет побуждать разработчиков компиляторов создавать качественные реализации, поддерживающие различные популярные расширения. независимо от того, требует их Стандарт или нет. - person supercat; 09.01.2019
comment
@curiousguy: Существующие реализации отражали не только интуицию их дизайнеров, но и их клиентов. Кроме того, не существует фиксированной концепции разумной, основанной на здравом смысле практики, которая единообразно применялась бы ко всем реализациям. Некоторые конструкции, которые могут отражать здравый смысл в низкоуровневом коде ОС, могут быть неуместны в высокоуровневом коде, обрабатывающем числа. Авторы Стандарта ожидали, что составители компиляторов будут знать больше, чем составители Стандарта, о том, какие конструкции и методы будут типичными для их целевых платформ и предполагаемых областей применения. - person supercat; 09.01.2019

В сноске к N1570 p6.5p7 четко указана цель правила: сказать, когда что-то может алиаситься. Что касается того, почему правило написано таким образом, чтобы запрещать конструкции, подобные вашей, которые не включают в себя псевдонимы, как написано (поскольку все обращения с использованием uint32_t* выполняются в контекстах, где он явно получен из uint64_t, это, скорее всего, потому, что авторы Стандарта признали, что любой, кто добросовестно пытается создать качественную реализацию, подходящую для низкоуровневого программирования, будет поддерживать конструкции, подобные вашей (как «популярное расширение»), независимо от того, предписывается ли это Стандартом. тот же принцип проявляется более явно в отношении таких конструкций, как:

unsigned mulMod65536(unsigned short x, unsigned short y)
{ return (x*y) & 65535u; }

Согласно Обоснованию, стандартные реализации будут обрабатывать операции над короткими значениями без знака способом, эквивалентным арифметике без знака, даже если результат находится между INT_MAX+1u и UINT_MAX, кроме случаев, когда применяются определенные условия. Нет необходимости в специальном правиле, заставляющем компилятор обрабатывать выражения, включающие короткие беззнаковые типы, как беззнаковые, когда результаты принудительно приводятся к unsigned, потому что, согласно авторам Стандарта, обычные реализации делают это даже без такого правило.

Стандарт никогда не предназначался для того, чтобы полностью указать все, что следует ожидать от качественной реализации, которая претендует на пригодность для какой-либо конкретной цели. На самом деле, даже не требуется, чтобы реализации были пригодны для какой-либо полезной цели (Обоснование даже признает возможность «соответствующей» реализации такого низкого качества, которая не может осмысленно обрабатывать что-либо, кроме одной надуманной и бесполезной программы) .

person supercat    schedule 09.01.2019
comment
Одна проблема, с которой я столкнулся в этом POV, заключается в том, что явно свежевыведенное не является формально определенным (AFAIK), а формальная спецификация чрезвычайно полезна для рассуждений как о программном коде, так и о коде компилятора. - person curiousguy; 09.01.2019
comment
@curiousguy: Авторы, вероятно, сделали сноску ненормативной, чтобы избежать необходимости писать точное определение алиасинга, а также потому, что обработка некоторых пограничных случаев (например, что компилятор должен предположить об указателях, извлеченных из volatile объектов или созданных с помощью целочисленных приведений) следует рассматривать как проблему качества реализации. Хотя авторы могли потребовать, чтобы реализации обрабатывали одни очевидные случаи, оставляя другие вопросы QOI, я не думаю, что они рассматривали идею о том, что разработчики будут использовать Стандарт в качестве предлога для игнорирования очевидных случаев. - person supercat; 09.01.2019
comment
@curiousguy: Авторы Стандарта опубликовали обоснование своих намерений. Они открыто признают возможность соответствующей реализации, которая настолько плохого качества, что становится бесполезной. Тот факт, что они не требуют код обработки реализации в соответствии с духом C, описанным в обосновании, никоим образом не означает, что от качественных реализаций не следует ожидать этого в любом случае. - person supercat; 09.01.2019
comment
@curiousguy: Если бы программисты придерживались позиции «не делайте ничего странного с памятью, не делая очевидным, что происходит что-то странное», а разработчики компиляторов придерживались позиции «прилагайте добросовестные усилия, чтобы заметить доказательства того, что может происходить что-то странное», эти принципы были бы вероятно, решить большинство проблем проще и эффективнее, чем более подробный стандарт. Ситуации, в которых люди громче всего кричат ​​о -fstrict-aliasing поведении, — это те, в которых авторы gcc и clang действуют с необоснованным пренебрежением к свидетельствам паттернов доступа перекрестного типа. - person supercat; 09.01.2019