Почему GCC и Clang появляются в обеих ветках, а не только один раз? (Выделение частей эпилога из дублирования хвоста)

Это часть сочетания высокоуровневой структуры и попытки оптимизировать хвостовой вызов с помощью прыжка. Всякий раз, когда функция завершается вызовом другой функции (или возвратом), компилятор использует код pop rax; jmp function().

В вашем случае обе ветви являются хвостовыми вызовами. Для краткости я использую тернарный оператор ; он генерирует тот же код, что и if ():

bool pred();
void f();
void g();
void i();

void h() {
    pred() ? f() : g();
    i();
}

// asm
h():
  push rdx
  call pred()
  test al, al
  je .L2
  call f()
  jmp .L3
.L2:
  call g()
.L3:
  pop rax
  jmp i()

Это выглядит ожидаемо, не так ли? Если мы просто вызовем три из них последовательно, хвост щелкнет:

void h() {
    pred();
    f();
    g();
}

h():
  push rax
  call pred()
  call f()
  pop rdx
  jmp g()

В этой форме h() появляется как вторая точка входа для функции g(). Если бы эти функции были в одном блоке или с полнопрограммной оптимизацией, их можно было бы даже объединить в один.

Может быть какая-то техническая причина оставить код, связанный с pop rax, в каждой ветке нетронутым, например, из-за предсказания ветвей.

Я не могу говорить от имени GCC, поскольку у меня нет личного опыта или инструментов для простой проверки проходов оптимизации GCC.

Что касается Клана; важно понимать, что подавляющее большинство оптимизаций происходит в середине компилятора, т. е. внутри LLVM IR, и независимо от особенностей платформы и соглашений о вызовах. LLVM IR в конце всех проходов оптимизации выглядит следующим образом:

define dso_local void @h()() local_unnamed_addr {
entry:
  %call = tail call noundef zeroext i1 @pred()()
  br i1 %call, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  tail call void @f()()
  ret void

if.else:                                          ; preds = %entry
  tail call void @g()()
  ret void
}

Этот IR настолько оптимален, насколько это возможно в конце среднего уровня.

Инструкции POP генерируются проходом вставки пролога/эпилога и финализации кадра (prologepilog) (см. этот пример Compiler Explorer) для обоих вызовов. Обратите внимание, что инструкции push и pop используются просто для выравнивания стека; использование rax произвольно.

Хотя в принципе можно исключить общие инструкции для нескольких ветвей, я думаю, что разработчики LLVM не считают, что это того стоит. Это имеет смысл; На таком позднем этапе конвейера оптимизации вы очищаете нижнюю часть оптимизации с точки зрения оптимизации и удаляете только несколько ненужных инструкций, связанных с выравниванием стека.

Вы правы, может call / pop rcx / test al,al / ...

В этом случае оба пути просто выполняют хвостовой вызов без какой-либо другой работы. Это был бы меньший размер статического кода, а не лучший или худший в каком-либо другом смысле. GCC/clang также должен делать то, что вы предлагаете в -O3.

Не всегда возможно уничтожить кадр стека перед ветвлением и настройкой аргументов (если таковые имеются) для хвостового вызова, поэтому компилятору придется проверить множество вещей, чтобы сделать это безопасно в общем случае. Такая причина является общей для пропущенных оптимизаций в крошечных простых функциях: код, который их ищет, должен быть корректным для не-миниатюрных функций, а выгода должна окупать время компиляции и затраты на обслуживание кода в GCC/ Источник LLVM.

Он помещает больше инструкций ветвления ближе друг к другу, что может быть проблематичным для прогнозирования ветвления в некоторых процессорах. (Даже безусловные ветки нуждаются в некотором прогнозировании, чтобы избежать остановки клиентской части, поскольку выборка кода осуществляется по конвейеру вместе с декодированием.) Точность прогнозирования может быть ниже, если поблизости находится много ветвей. pop — это всего лишь 1-байтовая инструкция, поэтому, вероятно, особой разницы нет.

Это пропущенная оптимизация, о которой вы можете сообщить https://gcc.gnu.org/bugzilla/ и https://github.com/llvm/llvm-project/issues/, если это еще не сделано существующие дубликаты. Соответствующие поисковые запросы могут включать «дублирование хвоста», «эпилог», «разобрать кадр стека».

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

Кстати, здесь есть еще одна пропущенная оптимизация: x86-64 Direct jmp rel32 имеет тот же диапазон, что и jcc rel32, поэтому он может использовать JCC в качестве хвостового вызова (Ошибка GCC 82516 есть короткий ответ от Ричарда Бинера, который проливает некоторый свет на то, почему GCC скучает по этому.)

# Hand-written with both optimizations applied
h:
    push    rax         # Align the stack
    call    pred()@PLT
    pop     rcx         # Clean up the stack, restoring the stack
                        # pointer to its initial state
    test    al, al
    je      g()@PLT
    jmp     f()@PLT     # Tailcall f

Если вы не скомпилируете с -fno-plt, вместо jmp qword ptr [rip + f()@GOTPCREL] # TAILCALL вы получите jmp f()@PLT, не имеющий эквивалента JCC.

(Если f и g присутствуют во время компоновки, компоновщик может ослабить косвенный вызов addr32 jmp f (при этом префиксный байт 67h addr32 просто заполняет пространство, чтобы сделать его такой же длины, как и косвенный переход, который он заменяет. Точно так же, как он может ослаблять прыжки / вызывает f@PLT только в f, если он статически связан, а не находится в другом общем объекте.)

Такие вещи, как __attribute__((visibility("hidden"))), могут сообщить компилятору, что f и g являются внутренними по отношению к тому, что он компилирует, либо к основному исполняемому файлу, либо к общей библиотеке, поэтому он может в первую очередь использовать прямые вызовы.

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

Причина всех этих ошибок одна: компиляторы выполняют большую часть своей работы по оптимизации над своего рода «промежуточным представлением», настроенным для нужд алгоритмов оптимизации общего назначения. Как правило, здесь будет использоваться форма SSA и будут содержаться абстрактные операции, такие как «a <- b + c», вместо конкретных машинных инструкций, таких как «добавить это 16-битное немедленное значение в этот 32-битный регистр и поместить результат в другой 32-битный регистр». регистр". А также, что очень важно, он не будет использовать регистры и слоты кадров стека. Вместо этого будет неограниченное количество локальных переменных, как и в любом компилируемом языке высокого уровня.

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

Любая оптимизация, которая выполняется после выбора инструкций и распределения регистров, работает более или менее напрямую с реальным языком ассемблера ЦП, а это означает, что она должна учитывать все ограничения этого языка. Например, этап свертки констант, который выполняется после выделения регистра, должен знать, что он не может объединить эти две инструкции:

mov  r0, #0xFEFE0000
add  r0, #0x0000FEFE

... потому что этот выдуманный ассемблер допускает только 16-битные непосредственные операнды (возможно, со сдвигом).

Таким образом, любую оптимизацию, которую вы хотели бы выполнить как до, так и после выделения регистров, придется писать дважды. Реализация «после» должна проделать дополнительную работу, если она хочет сделать что-то необычное, потому что настоящий язык ассемблера не находится в форме SSA. И он имеет множество ограничений, специфичных для машины, которые он должен учитывать, что может означать написание отдельной версии для каждого процессора, для которого вы можете сгенерировать код.

Это, в свою очередь, означает, что авторы компиляторов, как правило, вкладывают гораздо меньше усилий в оптимизацию после выделения регистров, а это означает, что код, который не существует до тех пор, пока он не будет сгенерирован в результате выделения регистров, например, при настройке и удалении кадра стека — не оптимизируется так тщательно, как хотелось бы. В частности, я не удивлюсь, узнав, что LLVM даже не пытается перемещать инструкции через границы базового блока после выделения регистров. Или, может быть, он пытается, но этот этап оптимизации не знает, какие инструкции касаются регистра флагов, и поэтому в вашем примере он не знает, безопасно ли помещать инструкцию pop между test и je.

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

Примером может быть: «если вы столкнулись с условной ветвью, в которой инструкция X, следующая за ветвью, и инструкция Y в целевой ветке одинаковы, код условия не изменяется, и Y не является целью какой-либо другой ветки, затем переместите X перед условным переходом, измените цель условного перехода на следующую инструкцию после Y и удалите инструкцию Y». Очевидно, это можно повторить.

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

Я обнаружил одну вещь: Кланг, похоже, предполагает, что константы всегда оптимальны. Это происходит довольно часто, но это неправильно для больших целочисленных констант на ARM , для построения которых может потребоваться несколько инструкций, и их лучше хранить в регистре (то же самое для чисел с плавающей запятой и значений SIMD). У меня был код, который был улучшен путем написания чего-то вроде

static unsigned long long x = 0x123456789abcdef0;
static unsigned long long y = 0;
if (++y == 0) ++x;

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