Оптимизация: frame pointer omission

История началась с вынужденной переустановки Gentoo. Благодаря когда-то давно где-то увиденной рекомендации из раза в раз в make.conf перекочёвывает переменная CFLAGS с аргументом -fomit-frame-pointer. Но что, собственно, он делает и нужен ли там вообще? Конец года 2020 хорошее время, чтобы в этом разобраться.

Чтобы понять, что делает -fomit-frame-pointer, вспомним кое-что о стеке. Рассмотрим простой код:

#include <stdio.h>

int main(int argc, char** argv)
{
        printf("Hello %s\n", "world");
}

Что происходит при вызове функции printf() (да и самой main() тоже)?

В точности следующее:

00001199 <main>:
    1199:       8d 4c 24 04             lea    0x4(%esp),%ecx
    119d:       83 e4 f0                and    $0xfffffff0,%esp
    11a0:       ff 71 fc                pushl  -0x4(%ecx)
    11a3:       55                      push   %ebp
    11a4:       89 e5                   mov    %esp,%ebp
    11a6:       53                      push   %ebx
    11a7:       51                      push   %ecx
    11a8:       e8 2f 00 00 00          call   11dc <__x86.get_pc_thunk.ax>
    11ad:       05 53 2e 00 00          add    $0x2e53,%eax
    11b2:       83 ec 08                sub    $0x8,%esp
    11b5:       8d 90 08 e0 ff ff       lea    -0x1ff8(%eax),%edx
    11bb:       52                      push   %edx
    11bc:       8d 90 0e e0 ff ff       lea    -0x1ff2(%eax),%edx
    11c2:       52                      push   %edx
    11c3:       89 c3                   mov    %eax,%ebx
    11c5:       e8 66 fe ff ff          call   1030 <printf@plt>
    11ca:       83 c4 10                add    $0x10,%esp
    11cd:       b8 00 00 00 00          mov    $0x0,%eax
    11d2:       8d 65 f8                lea    -0x8(%ebp),%esp
    11d5:       59                      pop    %ecx
    11d6:       5b                      pop    %ebx
    11d7:       5d                      pop    %ebp
    11d8:       8d 61 fc                lea    -0x4(%ecx),%esp
    11db:       c3                      ret

В строках 11bb и 11c2 в стек запихиваются аргументы для printf() и на момент после исполнения инструкции call стек принимает следующий вид:

...	...
0xXXXXfffb	arg1 [ebp + 12]
0xXXXXfff7	arg0 [ebp + 8]
0xXXXXfff3	return addr [ebp + 4]
0xXXXXffef	previous ebp [ebp + 0]
...	...

Если кому-то интересно, что происходит в строках 11a8-11ad, то это работа PIC (position-independent code), в котором данные адресуются относительно текущей инструкции кода. В x86-64 возможна непосредственная адресация относительно rip, но в х86 такого режима не было. Да-да, это 32-битный код для х86. Так было проще продемонстрировать передачу аргументов через стек. Потом поясним, почему. PIC в gcc включен по умолчанию. Запустим gcc с флагом -fno-pic, и вывод будет выглядеть уже иначе:

    11ad:       68 08 20 00 00          push   $0x2008
    11b2:       68 0e 20 00 00          push   $0x200e
    11b7:       e8 fc ff ff ff          call   11b8 <main+0x1f>

что воспринимается заметно проще. Но вернёмся назад к нашей printf(). Наверняка, она использует какие-то локальные переменные. Много локальных переменных. Регистров общего назначения у процессоров x86 не сказать, чтобы много. Едва ли их хватит на все нужды printf() и эти переменные будут размещены на стеке. В самом начале выполнения printf() на вершине стека находится адрес, куда будет передано управление после того, как в теле printf() процессор выполнит инструкцию ret. Для того, чтобы зарезервировать на стеке место для локальных переменных printf(), надо вычесть нужное число байт из esp - указателя на вершину стека, сдвинув его таким образом вперёд. Далее, обращаться к локальным переменным printf() сможет, например, по смещению относительно esp. Но это не всегда удобно, ведь по ходу дела программа может затолкать в стек ещё какие-то данные, не связанные с вызовом подпрограмм, значение esp изменится и смещения поплывут. Однако есть ещё один регистр ebp. Как правило, в прологе функции в нём сохраняется содержимое регистра esp, которое printf() "унаследует" от вызывающего кода. На протяжении выполнения printf() содержимое ebp не изменится. Вот относительно него-то и можно адресовать локальные переменные. Пролог типичной функции выглядит очень просто:

    XXXX:       55                      push   %ebp
    XXXX:       89 e5                   mov    %esp,%ebp

Действия, вполняемые этим кодом, отменяются единственной инструкцией 32-разрядных процессоров x86 leave, которая эквивалентна этому коду:

    XXXX:       89 ec                   mov    %ebp,%esp
    XXXX:       5d                      pop    %ebp

Невероятно, но факт: существует инструкция enter, которая настраивает фрейм, то есть, соответствует прологу. Однако этот факт тщательно скрывается её эффективность оказалась ниже, чем хотелось бы. Так что она не используется в коде, генерируемом gcc. А с leave всё в порядке. Потому и видим мы её, а не комбинацию мув-поп.

Казалось бы, к чему всё это? Именно к самой сути флага -fomit-frame-pointer, ведь содержимое ebp и есть тот самый указатель на фрейм, а наш флаг просто подавляет генерацию пролога и, соответственно, эпилога. Имеет ли такая оптимизация смысл? Ведь в сумме мы экономим самое большее 6 байтов и какое-то мизерное число тактов на грани статистической погрешности. Этот аргумент звучит не очень убедительно, но вряд ли разработчики компиляторов стали бы заморачиваться, если смысла совсем не было - да, MSVC тоже умеет элиминировать указатель на фреймы ключом /Oy. Действительно, если функция достаточно мала, настолько, что пролог и эпилог составляют ощутимый процент её тела, и в то же время вызывается она очень часто, выигрыш может стоить свеч. Хотя тут уже впору задуматься об инлайнинге. Может показаться, что эта оптимизация в любом случае не навредит, хотя бы и толку от неё было не особо много. На самом деле она усложняет отладку. Для компилятора заменить все ссылки на содержимое стека относительно ebp смещениями от esp не особо-то большое дело. Но при этом будет утрачена или существенно затруднена возможность следовать за выполнением кода по стеку вызовов. Отладчик всегда может без проблем найти ссылку на вызывающий код по содержимому ebp. Ведь как мы помним на вершине стека хранится адрес, принадлежащий функции, которой надлежит вернуть управление по окончании работы. Так как содержимое ebp больше не указывает гарантированно на вершину стека на момент вызова данной функции, то отладчик поставлен в тупик. Палка о двух концах. Но, кстати, вдобавок мы ещё получили свободный регистр... Когда их не так много и ещё один дополнительный регистр - это плюс 16% к объёму регистровой памяти, то возможно результат уже более ощутим. На процессорах x86 это близко к истине. Но не на amd64, где регистры широкие и их уже побольше.

Ещё один нюанс флага -fomit-frame-pointer состоит в том, что он включает оптимизацию, но не гарантирует её. Вот что по этому поводу можно прочесть в первоисточнике, man-странице gcc:

-fomit-frame-pointer
           Omit the frame pointer in functions that don't need one.  This avoids the
           instructions to save, set up and restore the frame pointer; on many
           targets it also makes an extra register available.

           On some targets this flag has no effect because the standard calling
           sequence always uses a frame pointer, so it cannot be omitted.

           Note that -fno-omit-frame-pointer doesn't guarantee the frame pointer is
           used in all functions.  Several targets always omit the frame pointer in
           leaf functions.

           Enabled by default at -O and higher.

В частности, пролог функции не может быть элиминирован в том случае, когда функция вызывает alloca(). alloca() не особо популярна и обладает неоднозначной репутацией, но тем не менее. Между тем, alloca(), выделяя память на стеке, делает это куда быстрее, чем malloc(), не требует парного вызова free(), так как память освобождается автоматически при выходе из стекового фрейма. Впрочем, alloca() не может использоваться в inline-функциях и пригодна для выделения лишь небольших блоков памяти на несколько сотен байтов максимум при гарантии, что указатель на блок не будет использован после возврата из функции, в которой был выделен данный блок. С точки зрения безопасности элиминация прологов функци сокращает attack surface для перехвата управления, когда злонамеренный код перезаписывает пролог инструкциями ветвления, так называемый трамплин (trampoline)[1].

Условия, при которых компилятор не будет генерировать пролог и эпилог функции, могут в частности, включать следующее:

• Данная функция - тупиковая (leaf function). То есть, она находится на вершине стека вызовов и в свою очередь не вызывает другие функции;
• Не используются исключения;
• Данная функция не содержит вызовов других функций, параметры которых передаются на стеке;
• Данная функция не принимает аргументов.

Возвращаясь к вопросу, почему в целях демонстрации использовался 32-разрядный код, можно сказать следующее. Linux ABI на amd64 требует передачи параметров в регистрах. Как уже упоминалось, в amd64 регистров общего назначения больше. Добиться от кода использования стека, соответственно, несколько проблематичнее, в противоположность ABI IA-32.

Ссылки:

1. Learning Linux binary analysis. Ryan O'Neill. 2016
2. Agner Vog's optimization manuals
3. System V Application Binary Interface. Intel386 Architecture Processor Supplement, Version 1.1