Особенности вызова функций в С++18.06.2018 16:17

Не так давно у меня произошёл очередной разговор с коллегой на извечную тему: «по ссылке, или по значению». В результате возникла данная статья. В ней я хочу изложить результаты моего исследования по этой и смежным темам. Далее будут рассмотрены:

Регистры и их назначение при вызове функций.
Передача и возврат простых типов и структур.
Как передача по ссылке и по значению влияют на оптимизации тела функции компилятором.
Как используется место при многочисленных вызовах функций.
Механизм виртуальных вызовов.
Оптимизация хвостовых вызовов и рекурсии.
Инициализация структур, массивов и векторов.

Осторожно! Статья содержит большое количество кода на C++ и ассемблере (с комментариями), а также множество таблиц с оценками производительности.

Информация бралась из документа System V Application Binary Interface. Ассемблерные листинги получены с помощью сайта https://godbolt.org для clang 5.0.0 x86-64 с флагами -O3 -std=c++1z -march=sandybridge. Оценки производительности были сделаны для процессора Intel(R) Xeon(R) CPU E5-2660 2.20GHz.

Registers in x86–64

Все данные хранятся в оперативной памяти. Для ускорения работы с ней используются многоуровневые кэши. Но чтобы эти данные как-то изменить, их в начале необходимо загрузить в регистры. Ниже дано очень краткое описание наиболее используемых регистров в архитектуре x86–64.

16 регистров общего назначения: rax, rbx, rcx, rdx, rbp, rsi, rdi, rsp, а также r8-r15. Размер каждого из них равен 64 битам (8 байтам). Для доступа к младшим 32 битам (4 байтам) используется префикс e вместо r (rax → eax). Поддерживают только не векторные целочисленные операции.
rip (instruction pointer) указывает на инструкцию, которая будет исполнена следующей. Различные константные данные, лежащие в разделе памяти с инструкциями, могут считываться по смещению относительно rip.
rsp (stack pointer) указывает на последний элемент в стеке. Стек растёт в сторону меньших адресов. Запихивание чего-то в стек уменьшает значение rsp.
16 SSE регистров размером 128 бит: xmm0 - xmm15. Если поддерживается режим AVX, то они ссылаются на младшие 128 бит регистров ymm0 - ymm15 каждый из которых имеет размер 256 бит. Для векторных, или не целочисленных операций, данные необходимо предварительно загрузить в эти регистры.

Parameter passing

В этом параграфе приведено несколько сокращённое и упрощённое описание алгоритма распределения аргументов по регистрам/стеку. Полное описание можно увидеть на странице 17 «System V ABI».

Введём несколько классов объектов:

INTEGER — интегральные типы, помещающиеся в регистры общего пользования. Это bool, char, int и так далее.
SSE — числа с плавающей точкой, вмещающиеся в векторный регистр. Это float и double.
MEMORY — объекты, передаваемые через стек.

Для унификации описания, типы __int128 и complex представляются как структуры из двух полей:

struct __int128 {
  int64 low, high;
};
struct complexT {
  T real, imag;
}; // Где T - float, или double.

В начале каждый аргумент функции классифицируется:

Если тип больше 128 бит, или имеет не выровненные поля, то он MEMORY.
Если есть нетривиальные деструктор, конструктор копирования, виртуальные методы, виртуальные базовые классы, то он передаётся через «прозрачную ссылку». Объект заменяется указателем, который имеет тип INTEGER.
Агрегаты, а это структуры и массивы, анализируются кусками по 8 байт.
1. Если в куске есть поле типа MEMORY, то весь кусок MEMORY.
2. Если есть поле типа INTEGER, то весь кусок INTEGER.
3. Иначе весь кусок SSE .
Если есть кусок типа MEMORY, то весь аргумент MEMORY.
Типы long double и complex long double используют специальный набор x87 FPU регистров и имеют тип MEMORY.
Типы __m256, __m128 и __float128 имеют тип SSE .

После классификации, все 8 байтные куски (в одном куске может быть несколько полей структуры, или элементов массива) распределяются по регистрам:

MEMORY передаются через стек.
INTEGER передаются через следующий свободный регистр rdi, rsi, rdx, rcx, r8, r9 в именно таком порядке.
SSE передаются через следующий свободный регистр xmm0 - xmm7.

Аргументы рассматриваются слева направо. Те аргументы, которым не хватило регистров, передаются через стек. Если какому-либо куску аргумента не хватило регистра, то весь аргумент передаётся через стек.

Возвращение значений производится следующим образом:

MEMORY типы возвращаются через стек. Место на нём предоставляется вызывающей функцией и адрес его начала передаётся через rdi как будто бы это первый аргумент функции. При возврате это адрес должен быть возвращён через rax. Первый оригинальный аргумент будет передан, соответственно, как второй, и так далее.
INTEGER кусок возвращается через следующий свободный регистр rax, rdx.
SSE кусок возвращается через следующий свободный регистр xmm0, xmm1. Эти регистры используются как для приёма, так и для возврата значений.

Сводная таблица с регистрами и их назначением, очень полезна при чтении ассемблера:

Регистр	Назначение
`rax`	Временный регистр, возврат первого (ret 1) INTEGER результата.
`rbx`	Принадлежит вызывающие функции, не должен быть изменён на момент возврата.
`rcx`	Передача четвёртого (4) INTEGER аргумента.
`rdx`	Передача третьего (3) INTEGER аргумента, возврат второго (ret 2) INTEGER результата.
`rsp`	Указатель на стек.
`rbp`	Принадлежит вызывающие функции, не должен быть изменён на момент возврата.
`rsi`	Передача второго (2) INTEGER аргумента.
`rdi`	Передача первого (1) INTEGER аргумента.
`r8`	Передача пятого (5) INTEGER аргумента.
`r9`	Передача шестого (6) INTEGER аргумента.
`r10-r11`	Временные регистры.
`r12-r15`	Принадлежит вызывающие функции, не должны быть изменены на момент возврата.
`xmm0-xmm1`	Передача и возврат первого и второго SSE аргументов.
`xmm2-xmm7`	Передача с третьего по шестой SSE аргументов.
`xmm8-xmm15`	Временные регистры.

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

Simple examples

Если явно не указано обратное, то все используемые функции были помечены как NOINLINE. Делаем вид, что тело функции расположено в cpp файле, а LTO отключено. Также все результаты функций передаются в пустую NOINLINE функцию, чтобы предотвратить удаление всего кода оптимизатором.

#define NOINLINE __attribute__((noinline))
#define INLINE static __attribute__((always_inline))

Рассмотрим что-нибудь простое.

double foo(int8_t a, int16_t b, int32_t c, int64_t d, float x, double y) {
  return a + b + c + d + x + y;
}
...
auto result = foo(1, 2, 3, 4, 5, 6);

Параметры передаются так:

Имя	Регистр	Имя	Регистр	Результат
a	`rdi`	d	`rcx`	`xmm0`
b	`rsi`	x	`xmm0`
c	`rdx`	y	`xmm1`

Рассмотрим сгенерированный кода подробнее.

foo(signed char, short, int, long, float, double):
  add edi, esi # Складываем a и b.
  add edi, edx # Прибавляем c.
  movsxd rax, edi # Копируем результат в rax, расширяя его до 64 бит с сохранением знака.
  add rax, rcx # Прибавляем d.
  vcvtsi2ss xmm2, xmm2, rax # Конвертируем результат в float и сохраняем его в xmm2.
  vaddss xmm0, xmm2, xmm0 # Прибавляем x, суффикс 's' инструкции vaddss обозначает работу с single precision.
  vcvtss2sd xmm0, xmm0, xmm0 # Конвертируем результат в double.
  vaddsd xmm0, xmm0, xmm1 # Прибавляем y, суффикс 'd' команды vaddsd обозначает работу с double precision.
  ret # Выходим из функции и переходим по адресу, сохранённому на вершине стека, стек при этом уменьшается, то есть rsp увеличивается на 8.
.LCPI1_0: # Секция с константными данными.
  .long 1084227584 # float 5
.LCPI1_1:
  .quad 4618441417868443648 # double 6
main: # @main
  sub rsp, 24
  # Распределяем аргументы по соответствующим регистрам.
  vmovss xmm0, dword ptr [rip + .LCPI1_0] # xmm0 = mem[0],zero,zero,zero
  vmovsd xmm1, qword ptr [rip + .LCPI1_1] # xmm1 = mem[0],zero
  mov edi, 1
  mov esi, 2
  mov edx, 3
  mov ecx, 4
  call foo(signed char, short, int, long, float, double) # call сохраняет адрес возврата на вершину стека, тем самым уменьшая rsp на 8, и переходит к месту начала функции.
  vmovsd qword ptr [rsp + 16], xmm0 # Копируем результат обратно на стек.

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

Рассмотрим различные примеры агрегатов. Массивы можно рассматривать как структуры с несколькими полями.

struct St {
  double a, b;
};
double foo(St s) { return s.a + s.b; }
...
St s{1, 2};
auto result = foo(s);

Имя	Регистр	Имя	Регистр	Результат
s.a	`xmm0`	s.b	`xmm1`	`xmm0`

Казалось бы, ничто не мешает запихнуть сразу два double в один xmm регистр. Но увы, алгоритм распределения оперирует только восьмибайтными кусками.

foo(St): # @foo(St)
  vaddsd xmm0, xmm0, xmm1 # Прибавляем второй аргумент к первому, который уже находится в регистре с результатом.
  ret
.LCPI1_0:
  .quad 4607182418800017408 # double 1
.LCPI1_1:
  .quad 4611686018427387904 # double 2
main: # @main
  sub rsp, 24
  # Заполняем входные регистры.
  vmovsd xmm0, qword ptr [rip + .LCPI1_0] # xmm0 = mem[0],zero
  vmovsd xmm1, qword ptr [rip + .LCPI1_1] # xmm1 = mem[0],zero
  call foo(St)  
  vmovsd qword ptr [rsp + 16], xmm0 # Копируем double из регистра с результатом.

Если добавить ещё одно double поле, то вся структура будет передана через стек, так как её размер превысит 128 байт.

struct St {
  double a, b, c;
};
double foo(St s) { return s.a + s.b + s.c; }
...
St s{1, 2, 3};
auto result = foo(s);

foo(St): # @foo(St)
  # При вызове функции, стек увеличивается на 8 байт, в которых хранится адрес возврата. Так как стек растёт в сторону уменьшения адреса, то первый аргумент будет расположен со по адресу rsp+8.
  vmovsd xmm0, qword ptr [rsp + 8] # xmm0 = mem[0],zero
  vaddsd xmm0, xmm0, qword ptr [rsp + 16]
  vaddsd xmm0, xmm0, qword ptr [rsp + 24]
  ret
.L_ZZ4mainE1s:
  .quad 4607182418800017408 # double 1
  .quad 4611686018427387904 # double 2
  .quad 4613937818241073152 # double 3
main: # @main
  sub rsp, 40 # Выделяем на стеке 40 байт.
  # Константы хранятся в разделе памяти с кодом, перекидываем их на стек. Это приходится делать через промежуточный регистр, так как mov не может копировать из памяти в память.
  mov rax, qword ptr [rip + .L_ZZ4mainE1s+16] # Загружаем в регистр '3'.
  mov qword ptr [rsp + 16], rax # Копируем '3' на стек.
  vmovups xmm0, xmmword ptr [rip + .L_ZZ4mainE1s] # Загружаем в xmm0 сразу '1' и '2'.
  vmovups xmmword ptr [rsp], xmm0 # Копируем '1' и '2 на стек. Сейчас стек выглядит так: 1 = *rsp , 2 = *(rsp+8), 3 = *(rsp+16).
  call foo(St)
  vmovsd qword ptr [rsp + 32], xmm0 # Копируем на стек один double с результатом.

Посмотрим, что будет, если заменить double на uint64_t.

struct St {
  uint64_t a, b;
};
uint64_t foo(St s) { return s.a + s.b; }
...
St s{1, 2};
auto result = foo(s);

Имя	Регистр	Имя	Регистр	Результат
s.a	`rdi`	s.b	`rsi`	`rax`

foo(St): # @foo(St)
  lea rax, [rdi + rsi]
  ret
main: # @main
  sub rsp, 24
  mov edi, 1
  mov esi, 2
  call foo(St)
  mov qword ptr [rsp + 16], rax

Результат заметно компактнее. Подробнее про то, почему используется инструкция lea, а не add, можно почитать, к примеру, тут: https://stackoverflow.com/a/6328441/1418863

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

Рассмотрим что-нибудь более интересное.

struct St {
  float a, b, c, d;
};
St foo(St s1, St s2) {
  return {s1.a + s2.a, s1.b + s2.b, s1.c + s2.c, s1.d + s2.d};
}
...
St s1{1, 2, 3, 4}, s2{5, 6, 7, 8}; 
auto result = foo(s1, s2);

Имя	Регистр	Имя	Регистр	Результат
s1.a	`xmm0`	s1.b	`xmm0`	`xmm0, xmm1`
s1.c	`xmm1`	s1.d	`xmm1`
s2.a	`xmm2`	s2.b	`xmm2`
s2.c	`xmm3`	s2.d	`xmm3`

В каждый xmm регистр запихиваются по два float поля.

foo(St, St): # @foo(St, St)
  # Одной инструкцией vaddps складываем сразу два float значения.
  vaddps xmm0, xmm0, xmm2 
  vaddps xmm1, xmm1, xmm3
  ret
.LCPI1_0:
  .long 1065353216 # float 1
  .long 1073741824 # float 2
  .zero 4
  .zero 4
  # Аналогично определены LCPI1_1 - LCPI1_3.
...
main: # @main
  sub rsp, 24
  # Заполняем регистры, копируя константные данные из области кода.
  vmovapd xmm0, xmmword ptr [rip + .LCPI1_0] # xmm0 = <1,2,u,u>
  vmovapd xmm1, xmmword ptr [rip + .LCPI1_1] # xmm1 = <3,4,u,u>
  vmovaps xmm2, xmmword ptr [rip + .LCPI1_2] # xmm2 = <5,6,u,u>
  vmovaps xmm3, xmmword ptr [rip + .LCPI1_3] # xmm3 = <7,8,u,u>
  call foo(St, St)
  # Так как тут нужно загрузить результат в стек, то предварительно два регистра с результатом смешиваются в один. xmm имеет размер 256 байт, поэтому в младшие 128 байт копируются поля a и b, в старшие - c и d.
  vunpcklpd xmm0, xmm0, xmm1 # xmm0 = xmm0[0],xmm1[0]
  vmovupd xmmword ptr [rsp + 8], xmm0

Если бы в структуре было не 4, а три поля, то код функции был бы аналогичен, за исключением замены второй инструкции vaddps на vaddss, которая складывает только первые 64 бита регистра.

struct St {
  int32_t a, b, c, d;
};
St foo(St s1, St s2) {
  return {s1.a + s2.a, s1.b + s2.b, s1.c + s2.c, s1.d + s2.d};
}
...
St s1{1, 2, 3, 4}, s2{5, 6, 7, 8}; 
auto result = foo(s1, s2);

Имя	Регистр	Имя	Регистр	Результат
s1.a	`rdi`	s1.b	`rdi`	`rax, rdx`
s1.c	`rsi`	s1.d	`rsi`
s2.a	`rdx`	s2.b	`rdx`
s2.c	`rcx`	s2.d	`rcx`

foo(St, St): # @foo(St, St)
  lea eax, [rdx + rdi]
  movabs r8, -4294967296 # 0xFFFFFFFF00000000 Битовая маска.
  and rdi, r8
  add rdi, rdx
  and rdi, r8
  or rax, rdi
  lea edx, [rcx + rsi] # То же, что и add.
  and rsi, r8
  add rsi, rcx
  and rsi, r8
  or rdx, rsi
  ret
main: # @main
  sub rsp, 24
  movabs rdi, 8589934593 # Загружаем в регистры сразу по два числа.
  movabs rsi, 17179869187
  movabs rdx, 25769803781
  movabs rcx, 34359738375
  call foo(St, St)
  mov qword ptr [rsp + 8], rax # Копируем результат на стек.
  mov qword ptr [rsp + 16], rdx

Внутри функции происходит битовая магия, но принцип примерно ясен. Каждая пара 32 битных чисел запаковывается в один 64 битный регистр. Возврат производится таким же образом.

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

struct St {
  int32_t a, b;
  float c, d;
};
St foo(St s1, St s2) {
  return {s1.a + s2.a, s1.b + s2.b, s1.c + s2.c, s1.d + s2.d};
}
...
St s1{1, 2, 3, 4}, s2{5, 6, 7, 8};
auto result = foo(s1, s2);

Имя	Регистр	Имя	Регистр	Результат
s1.a	`rdi`	s1.b	`rdi`	`rax, xmm0`
s1.c	`xmm0`	s1.d	`xmm0`
s2.a	`rsi`	s2.b	`rsi`
s2.c	`xmm1`	s2.d	`xmm1`

foo(St, St): # @foo(St, St)
  lea eax, [rsi + rdi] # Эта часть аналогична предыдущему примеру.
  movabs rcx, -4294967296
  and rdi, rcx
  add rdi, rsi
  and rdi, rcx
  or rax, rdi
  vaddps xmm0, xmm0, xmm1 # Складываем сразу два поля.
  ret
.LCPI1_0:
  .long 1077936128 # float 3
  .long 1082130432 # float 4
  .zero 4
  .zero 4
...
main: # @main
  sub rsp, 24
  vmovaps xmm0, xmmword ptr [rip + .LCPI1_0] # xmm0 = <3,4,u,u>
  vmovaps xmm1, xmmword ptr [rip + .LCPI1_1] # xmm1 = <7,8,u,u>
  movabs rdi, 8589934593
  movabs rsi, 25769803781
  call foo(St, St)
  mov qword ptr [rsp + 8], rax # Копируем результат на стек.
  vmovlps qword ptr [rsp + 16], xmm0

Но это не интересно, так как типы полей в каждом 8 байтном куске совпадают. Перемешаем поля.

struct St {
  int32_t a;
  float b;
  int32_t c;
  float d;
};
St foo(St s1, St s2) {
  return {s1.a + s2.a, s1.b + s2.b, s1.c + s2.c, s1.d + s2.d};
}
...
St s1{1, 2, 3, 4}, s2{5, 6, 7, 8};
auto result = foo(s1, s2);

Имя	Регистр	Имя	Регистр	Результат
s1.a	`rdi`	s1.b	`rdi`	`rax, rdx`
s1.c	`rsi`	s1.d	`rsi`
s2.a	`rdx`	s2.b	`rdx`
s2.c	`rcx`	s2.d	`rcx`

Смотрим пункт 3.2. Так как в 8 байтном куске есть и float, и int, то весь кусок будет иметь тип INTEGER и будет передан в регистрах общего назначения.

foo(St, St): # @foo(St, St)
  mov rax, rdx
  add edx, edi
  shr rdi, 32
  vmovd xmm0, edi
  mov rdi, rcx
  add ecx, esi
  shr rsi, 32
  vmovd xmm1, esi
  shr rax, 32
  vmovd xmm2, eax
  vaddss xmm0, xmm0, xmm2
  shr rdi, 32
  vmovd xmm2, edi
  vaddss xmm1, xmm1, xmm2
  vmovd eax, xmm0
  shl rax, 32
  or rdx, rax
  vmovd eax, xmm1
  shl rax, 32
  or rcx, rax
  mov rax, rdx
  mov rdx, rcx
  ret
main: # @main
  sub rsp, 24
  movabs rdi, 4611686018427387905 # 0x4000000000000001, в младших 32 битах хранится int, в старших - float.
  movabs rsi, 4647714815446351875
  movabs rdx, 4665729213955833861
  movabs rcx, 4683743612465315847
  call foo(St, St)
  mov qword ptr [rsp + 8], rax # Возвращается результат тоже исключительно через 64 битные регистры.
  mov qword ptr [rsp + 16], rdx

Тут можно видеть 6 операций сдвига для извлечения float полей и их запихивания в регистр с результатом. А также отсутствие каких-либо векторных операций. В общем, лучше не мешать типы полей в пределах 8 байтовых кусков структуры.

References

Передача параметров по константной ссылке аналогично передаче указателя на объект. Если объект не помещается в регистрах, то он передаётся и возвращается через стек. Посмотрим, как это происходит. Для реалистичности рассмотрим структуру для трёхмерной точки.

struct Point3f {
  float x, y, z;
};
struct Point3d {
  double x, y, z;
};
Point3f scale(Point3f p) { return {p.x * 2, p.y * 2, p.z * 2}; }
Point3f scaleR(const Point3f& p) { return {p.x * 2, p.y * 2, p.z * 2}; }
Point3d scale(Point3d p) { return {p.x * 2, p.y * 2, p.z * 2}; }
Point3d scaleR(const Point3d& p) { return {p.x * 2, p.y * 2, p.z * 2}; }

Сравним код функций. Использоваться будут преимущественно новые xmm регистры, поэтому логика вполне понятна.

scale(Point3f): # @scale(Point3f)
  # Как и в прошлых примерах, x, y передаются в xmm0, z - xmm1, возвращается результат в них же.
  vaddps xmm0, xmm0, xmm0
  vaddss xmm1, xmm1, xmm1  
  ret
scaleR(Point3f const&): # @scaleR(Point3f const&)
  # Указатель на аргумент находится в регистре rdi, служащего для передачи первого аргумента. Возврат так же через регистры xmm0, xmm1.
  vmovsd xmm0, qword ptr [rdi] # xmm0 = mem[0],zero
  vaddps xmm0, xmm0, xmm0
  vmovss xmm1, dword ptr [rdi + 8] # xmm1 = mem[0],zero,zero,zero
  vaddss xmm1, xmm1, xmm1
  ret
scale(Point3d): # @scale(Point3d)
  # В регистре rid передаётся адрес, по которому нужно записывать результат. Сам аргумент передаётся через стек и расположен по адресам [rsp+8, rsp+32). В [rsp, rsp+8) находится адрес возврата из функции.
  vmovapd xmm0, xmmword ptr [rsp + 8]
  vaddpd xmm0, xmm0, xmm0
  vmovupd xmmword ptr [rdi], xmm0
  vmovsd xmm0, qword ptr [rsp + 24] # xmm0 = mem[0],zero
  vaddsd xmm0, xmm0, xmm0
  vmovsd qword ptr [rdi + 16], xmm0
  mov rax, rdi # Возвращаем адрес, по которому записан результат.
  ret
scaleR(Point3d const&): # @scaleR(Point3d const&)
  # Код абсолютно идентичен, но аргумент начинается не в [rsp+8, rsp+32), а в [rsi, rsi+24).
  vmovupd xmm0, xmmword ptr [rsi]
  vaddpd xmm0, xmm0, xmm0
  vmovupd xmmword ptr [rdi], xmm0
  vmovsd xmm0, qword ptr [rsi + 16] # xmm0 = mem[0],zero
  vaddsd xmm0, xmm0, xmm0
  vmovsd qword ptr [rdi + 16], xmm0
  mov rax, rdi
  ret

Теперь посмотрим на место вызова этих функций.

# scale(Point3f)
main: # @main 
  sub rsp, 24
  # Копируем константы во входные регистры.
  vmovaps xmm0, xmmword ptr [rip + .LCPI4_0] # xmm0 = <1,2,u,u>
  vmovss xmm1, dword ptr [rip + .LCPI4_1] # xmm1 = <3,u,u,u>
  call scale(Point3f)

# scaleR(const Point3f&)
main: # @main  
  sub rsp, 24
  # Просто записываем адрес участка с константами в регистр rdi, в котором передаётся первый аргумент.
  mov edi, .L_ZZ4mainE1p # <1,2,3,u>
  call scaleR(Point3f const&)

# scale(Point3d)
main: # @main
  sub rsp, 64
  # Копируем константы из раздела с данным на стек.
  mov rax, qword ptr [rip + .L_ZZ4mainE1p+16]
  mov qword ptr [rsp + 16], rax
  vmovups xmm0, xmmword ptr [rip + .L_ZZ4mainE1p]
  vmovups xmmword ptr [rsp], xmm0  
  lea rbx, [rsp + 40]
  mov rdi, rbx # Результат будет записан в [rsp+40, rsp+64).
  call scale(Point3d)
.L_ZZ4mainE1p:
  .quad 4607182418800017408 # double 1
  .quad 4611686018427387904 # double 2
  .quad 4613937818241073152 # double 3

  # scaleR(const Point3d&)
main: # @main
  sub rsp, 64
  # То же самое.
  mov rax, qword ptr [rip + .L_ZZ4mainE1p+16]
  mov qword ptr [rsp + 32], rax
  vmovups xmm0, xmmword ptr [rip + .L_ZZ4mainE1p]
  vmovaps xmmword ptr [rsp + 16], xmm0
  lea rbx, [rsp + 40]
  lea rsi, [rsp + 16] # Аргумент будет по адресу [rsp+16, rsp+40).
  mov rdi, rbx # Результат будет записан в [rsp+40, rsp+64).
  call scaleR(Point3d const&)

Посмотрим, что если у нас много полей, но структура всё-таки влезает в регистры. Тут начинается самое интересное.

struct St {
  char d[16];
};

St foo(St s1, St s2) {  // Просто суммируем s1 и s2.
    St res; 
    for(int i{}; i < 16; ++i) res.d[i] = s1.d[i] + s2.d[i]; 
    return res;
}

Код для функции, принимающей аргументы по значению.

Имя	Регистр	Имя	Регистр	Результат
s1.d[1:8]	`rdi`	s1.d[8:16]	`rsi`	`rax, rdx`
s2.d[1:8]	`rdx`	s2.d[8:16]	`rcx`

foo(St, St): # @foo(St, St)
  mov qword ptr [rsp - 16], rdi
  mov qword ptr [rsp - 8], rsi
  mov qword ptr [rsp - 32], rdx
  mov qword ptr [rsp - 24], rcx
  mov eax, edx
  add al, dil
  mov byte ptr [rsp - 48], al
  mov r8, rdi
  shr r8, 8
  mov rax, rdx
  shr rax, 8
  add al, r8b
  mov byte ptr [rsp - 47], al
  mov r8, rdi
  shr r8, 16
  mov rax, rdx
  shr rax, 16
  add al, r8b
  mov byte ptr [rsp - 46], al
  mov r8, rdi
  shr r8, 24
  mov rax, rdx
  shr rax, 24
  add al, r8b
  mov byte ptr [rsp - 45], al
  mov r8, rdi
  shr r8, 32
  mov rax, rdx
  shr rax, 32
  add al, r8b
  mov byte ptr [rsp - 44], al
  mov r8, rdi
  shr r8, 40
  mov rax, rdx
  shr rax, 40
  add al, r8b
  mov byte ptr [rsp - 43], al
  mov r8, rdi
  shr r8, 48
  mov rax, rdx
  shr rax, 48
  add al, r8b
  mov byte ptr [rsp - 42], al
  shr rdi, 56
  shr rdx, 56
  add dl, dil
  mov byte ptr [rsp - 41], dl
  mov eax, ecx
  add al, sil
  mov byte ptr [rsp - 40], al
  mov rax, rsi
  shr rax, 8
  mov rdx, rcx
  shr rdx, 8
  add dl, al
  mov byte ptr [rsp - 39], dl
  shr rsi, 16
  shr rcx, 16
  add cl, sil
  mov byte ptr [rsp - 38], cl
  mov al, byte ptr [rsp - 21]
  mov cl, byte ptr [rsp - 20]
  add al, byte ptr [rsp - 5]
  mov byte ptr [rsp - 37], al
  add cl, byte ptr [rsp - 4]
  mov byte ptr [rsp - 36], cl
  mov al, byte ptr [rsp - 19]
  mov cl, byte ptr [rsp - 18]
  add al, byte ptr [rsp - 3]
  mov byte ptr [rsp - 35], al
  add cl, byte ptr [rsp - 2]
  mov byte ptr [rsp - 34], cl
  mov al, byte ptr [rsp - 17]
  add al, byte ptr [rsp - 1]
  mov byte ptr [rsp - 33], al
  mov rax, qword ptr [rsp - 48]
  mov rdx, qword ptr [rsp - 40]
  ret

Да, тут все аргументы копируются на стек, после чего из него извлекается и складывается по одному байту за раз. Как можно посчитать, в функции ровно 16 инструкций add. Может ли компилятор что-то с этим поделать? Передадим структуру по ссылке.

St fooR(const St& s1, const St& s2) { /* Без изменений. */ }

Имя	Регистр	Имя	Регистр	Результат
s1	`rdi`	s2	`rsi`	`rax, rdx`

fooR(St const&, St const&): # @fooR(St const&, St const&)
  vmovdqu xmm0, xmmword ptr [rsi]
  vpaddb xmm0, xmm0, xmmword ptr [rdi]
  vmovdqa xmmword ptr [rsp - 24], xmm0
  mov rax, qword ptr [rsp - 24]
  mov rdx, qword ptr [rsp - 16]
  ret

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

void fooR1(St &s1, const St& s2) { 
    for(int i{}; i < 16; ++i) s1.d[i] += s2.d[i];
}

Имя	Регистр	Имя	Регистр	Результат
s1	`rdi`	s2	`rsi`

fooR1(St&, St const&): # @fooR1(St&, St const&)
  mov al, byte ptr [rsi]
  add byte ptr [rdi], al
  mov al, byte ptr [rsi + 1]
  add byte ptr [rdi + 1], al
  mov al, byte ptr [rsi + 2]
  add byte ptr [rdi + 2], al
  mov al, byte ptr [rsi + 3]
  add byte ptr [rdi + 3], al
  mov al, byte ptr [rsi + 4]
  add byte ptr [rdi + 4], al
  mov al, byte ptr [rsi + 5]
  add byte ptr [rdi + 5], al
  mov al, byte ptr [rsi + 6]
  add byte ptr [rdi + 6], al
  mov al, byte ptr [rsi + 7]
  add byte ptr [rdi + 7], al
  mov al, byte ptr [rsi + 8]
  add byte ptr [rdi + 8], al
  mov al, byte ptr [rsi + 9]
  add byte ptr [rdi + 9], al
  mov al, byte ptr [rsi + 10]
  add byte ptr [rdi + 10], al
  mov al, byte ptr [rsi + 11]
  add byte ptr [rdi + 11], al
  mov al, byte ptr [rsi + 12]
  add byte ptr [rdi + 12], al
  mov al, byte ptr [rsi + 13]
  add byte ptr [rdi + 13], al
  mov al, byte ptr [rsi + 14]
  add byte ptr [rdi + 14], al
  mov al, byte ptr [rsi + 15]
  add byte ptr [rdi + 15], al
  ret

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

char buff[17];
fooR1(*reinterpret_cast(buff+1), reinterpret_cast(buff));

В этом случае, на каждой итерации вычисляется buff[i+1] += buff[i], то есть имеется pointer aliasing. Для того, чтобы указать компилятору, что такого странного использования функции не предвидится, существует ключевое слово __restrict.

void fooR2(St & __restrict s1, const St& s2) { /* Без изменений. */ }

Что и даёт желаемый результат.

fooR2(St&, St const&): # @fooR2(St&, St const&)
  vmovdqu xmm0, xmmword ptr [rdi]
  vpaddb xmm0, xmm0, xmmword ptr [rsi]
  vmovdqu xmmword ptr [rdi], xmm0
  ret

Изменении сигнатуры на void fooR3(St &__restrict s1, St s2), тоже приведёт к раздутому код, похожему на первый пример с St foo(St, St).

Кстати, если размер массива заранее не известен, то void foo(char* __restrict s1, const char* s2, int size) генерирует примерно в полтора раза меньше строк кода, чем версия без __restrict.

Benchmark

Будем четыре раза прибавлять b к a, к примеру, для foo это будет выглядеть так:

St a, b; st(a, b); // st(St& a, St& b) { a = b = {}; } в другом файле.
a = foo(a, b);
a = foo(a, b);
a = foo(a, b);
a = foo(a, b);

Code	Cycles per iteration
`St a, b; st(a, b);`	7.6
4 x `foo` no reuse	121.9
4 x `foo`	117.7
4 x `fooR` no reuse	66.3
4 x `fooR`	64.6
4 x `fooR1`	84.5
4 x `fooR2`	20.6
4 x `foo` inline	51.9
4 x `fooR` inline	30.5
4 x `fooR1` inline	8.8
4 x `fooR2` inline	8.8

'no reuse' указывает на то, что для хранения каждого результата используется новая переменная. auto a2 = foo(a, b); auto a3 = foo(a2, b);. 'inline' означает, что функции помечены как INLINE, а не NOINLINE.

Если посмотреть на листинг fooR1 inline / fooR2 inline, то в нём будет всего пара инструкций, но в случае, когда структура передаётся, или возвращается через регистры, foo inline / fooR inline, компилятор сходит с ума и выдаёт сотни строк кода. Видимо, встраивание происходит после распределения всех полей по регистрам, после чего компилятор запутывается в происходящем и уже не может нормально упростить результат.

Transparent pointers

Посмотрим, что будет, если добавить немного деструктора.

struct Point3f {
  float x, y, z;
  ~Point3f() {}
};
Point3f scale(Point3f p) { return {p.x * 2, p.y * 2, p.z * 2}; }

Первым параметром в rdi передаётся адрес, по которому нужно записывать результат. Вторым, в rsi, передаётся указатель на первый аргумент функции.

scale(Point3f): # @scale(Point3f)     
  vmovss xmm0, dword ptr [rsi] # xmm0 = mem[0],zero,zero,zero
  vaddss xmm0, xmm0, xmm0
  vmovss dword ptr [rdi], xmm0
  vmovss xmm0, dword ptr [rsi + 4] # xmm0 = mem[0],zero,zero,zero
  vaddss xmm0, xmm0, xmm0
  vmovss dword ptr [rdi + 4], xmm0
  vmovss xmm0, dword ptr [rsi + 8] # xmm0 = mem[0],zero,zero,zero
  vaddss xmm0, xmm0, xmm0
  vmovss dword ptr [rdi + 8], xmm0
  mov rax, rdi
  ret

Как видно, загрузка, умножение (через сложение) и сохранение производится по одному полю за раз. Компилятор не очень хочет оптимизировать не POD типы. Версия функции с константной ссылкой Point3f scaleR(const Point3f&) даст идентичный код. Посмотрим на место вызова.

Point3f p{1, 2, 3};
auto result = scale(p);
sink(&result);

main: # @main
  push rbx
  sub rsp, 48
  movabs rax, 4611686019492741120 # Копируем константы на стек.
  mov qword ptr [rsp + 16], rax 
  mov dword ptr [rsp + 24], 1077936128
  lea rbx, [rsp + 32]
  lea rsi, [rsp + 16] # Аргумент будет в [rsp+16, rsp+28)
  mov rdi, rbx # Результат будет в [rsp+32, rsp+44)
  call scale(Point3f)  
  mov qword ptr [rsp + 8], rbx # В [rsp+8, rsp+16) будет указатель на результат.
  lea rdi, [rsp + 8]
  call void sink(Point3f* const&)
  xor eax, eax
  add rsp, 48
  pop rbx
  ret
  # Обработка исключений.
  mov rdi, rax
  call _Unwind_Resume

Если сделать деструктор NOINLINE, то всё будет гораздо запутаннее.

main: # @main
  push r14
  push rbx
  sub rsp, 56
  movabs rax, 4611686019492741120 # Константы будут в [rsp, rsp+12). Это переменная p.
  mov qword ptr [rsp], rax
  mov dword ptr [rsp + 8], 1077936128
  # Копируем константы в [rsp+24, rsp+36), это временная переменная pTmp.
  mov eax, dword ptr [rsp + 8]
  mov dword ptr [rsp + 32], eax
  mov rax, qword ptr [rsp]
  mov qword ptr [rsp + 24], rax
  lea r14, [rsp + 40]
  lea rbx, [rsp + 24]
  mov rdi, r14 # Результат сохраняем в [rsp+40, rsp+52), это result.
  mov rsi, rbx # Первый аргумент - указатель на pTmp.
  call scale(Point3f)
  mov rdi, rbx # Вызываем деструктор у pTmp. Первый аргумент деструктора - указатель this.
  call Point3f::~Point3f()
  mov qword ptr [rsp + 16], r14 # В [rsp+16, rsp+24) будет храниться указатель на result. Он же первый аргумент sink.
  lea rdi, [rsp + 16]
  call void sink(Point3f* const&)
  lea rdi, [rsp + 40] # Вызывает деструктор у result.
  call Point3f::~Point3f()
  mov rdi, rsp # Вызывает деструктор у p.
  call Point3f::~Point3f()
  xor eax, eax
  add rsp, 56
  pop rbx
  pop r14
  ret
  # Обработка исключений. Сюда может быть произведён переход в случае возникновения и перехвата исключения.
  mov rbx, rax
  lea rdi, [rsp + 40] # Вызывает деструктор у result.
  call Point3f::~Point3f()
  mov rdi, rsp # Вызывает деструктор у p.
  call Point3f::~Point3f()
  mov rdi, rbx
  call _Unwind_Resume

Если параметр p явно передавать по ссылке, то кода станет несколько меньше и будет произведено только два вызова деструктора.

Stack reuse

Посмотрим, как компилятор переиспользует регистры и стек между вызовами. Будут использоваться функции из параграфа references.

# Point3f result = scale(scale(Point3f{1, 2, 3}));
  sub rsp, 24
  vmovaps xmm0, xmmword ptr [rip + .LCPI4_0] # xmm0 = <1,2,u,u>
  vmovss xmm1, dword ptr [rip + .LCPI4_1] # xmm1 = mem[0],zero,zero,zero
  # Так как регистры xmm0, xmm1 используются как для передачи, так и для возврата, то просто вызываем несколько раз нужную функцию!
  call scale(Point3f)
  call scale(Point3f)
  vmovlps qword ptr [rsp + 8], xmm0
  vmovss dword ptr [rsp + 16], xmm1

# Point3f result = scaleR(scaleR(Point3f{1, 2, 3}));
  sub rsp, 56
  # Копируем константы на стек в диапазоне [rsp+24, rsp+36).
  movabs rax, 4611686019492741120 # 0x400000003F800000 = [2.0f, 1.0f]
  mov qword ptr [rsp + 24], rax
  mov dword ptr [rsp + 32], 1077936128 # 0x40400000 = 3.0f
  lea rdi, [rsp + 24] # Аргумент с указателем на входные данные.
  call scaleR(Point3f const&)
  # Сохраняем результат в [rsp+8, rsp+20).
  vmovlps qword ptr [rsp + 8], xmm0
  vmovss dword ptr [rsp + 16], xmm1
  lea rdi, [rsp + 8] # Аргумент с указателем на результат первого вызова.
  call scaleR(Point3f const&)
  vmovlps qword ptr [rsp + 40], xmm0
  vmovss dword ptr [rsp + 48], xmm1

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

# Point3d result = scale(scale(Point3d{1, 2, 3}));
  sub rsp, 112
  # Загружаем константы в [rsp, rsp+24).
  vmovaps xmm0, xmmword ptr [rip + .LCPI4_0] # xmm0 = [1.000000e+00,2.000000e+00]
  vmovaps xmmword ptr [rsp + 32], xmm0
  movabs rax, 4613937818241073152 # 0x4008000000000000 = 3.0
  mov qword ptr [rsp + 48], rax
  mov rax, qword ptr [rsp + 48]
  mov qword ptr [rsp + 16], rax
  vmovaps xmm0, xmmword ptr [rsp + 32]
  vmovups xmmword ptr [rsp], xmm0
  # Результат будет в [rsp+64, rsp+88).
  lea rdi, [rsp + 64] # В rdi передаём адрес стека для результата.
  call scale(Point3d)
  # Аргумент второй функции будет также по адресу [rsp, rsp+24).
  mov rax, qword ptr [rsp + 80] # Копируем z результата в z аргумента.
  mov qword ptr [rsp + 16], rax
  vmovups xmm0, xmmword ptr [rsp + 64] # Копируем [x, y] результата в [x, y] аргумента.
  vmovups xmmword ptr [rsp], xmm0
  # Результат будет в [rsp+88, rsp+112).
  lea rbx, [rsp + 88]
  mov rdi, rbx
  call scale(Point3d)

# Point3d result = scaleR(scaleR(Point3d{1, 2, 3}));
  sub rsp, 72
  # Загружаем константы в [rsp, rsp+24), аналогично предыдущему коду.
  vmovaps xmm0, xmmword ptr [rip + .LCPI4_0]
  vmovaps xmmword ptr [rsp], xmm0
  movabs rax, 4613937818241073152
  mov qword ptr [rsp + 16], rax
  lea r14, [rsp + 24]
  mov rsi, rsp # Второй аргумент - указатель на стек с входными данными [rsp, rsp+24).
  mov rdi, r14 # Первый аргумент - указатель на стек для результата [rsp+24, rsp+48).
  call scaleR(Point3d const&)
  lea rbx, [rsp + 48]
  mov rdi, rbx # Указатель на стек для результата [rsp+48, rsp+72).
  mov rsi, r14 # Указатель на стек с входными данными [rsp+24, rsp+48).
  call scaleR(Point3d const&)

Видно, что при передаче аргументов, помещающихся в регистры, код значительно короче, если передавать по значению. Если же они не помещаются — то лучше передавать по ссылке. В этом случае компилятор может удалить лишние копирования и передавать сразу указатель на стек с результатом предыдущего вызова. Причём он не может сделать так же, если параметр передаётся по значению через стек, и ему приходится выполнять лишние копирования.

Benchmark

Посмотрим, какое влияние всё это оказывает на быстродействие. Функции для получения точек были объявлены в отдельном файле, чтобы предотвратить оптимизации для константных данных. Напомню, что при возврате из функции и передаче по значению, Point3f будет передаваться через регистры, а Point3d — через стек.

// В файле data.cpp. Предотвращаем встраивание.
Point3f pf() { return {1, 2, 3}; }
Point3d pd() { return {1, 2, 3}; }

Code	Cycles per iteration
`auto r = pf();`	6.7
`auto r = scale(pf());`	11.1
`auto r = scaleR(pf());`	12.6
`auto r = scale(scale(pf()));`	18.2
`auto r = scaleR(scaleR(pf()));`	18.3
`auto r = scale(scale(scale(pf())));`	16.8
`auto r = scaleR(scaleR(scaleR(pf())));`	20.2
`auto r = pd();`	7.3
`auto r = scale(pd());`	11.7
`auto r = scaleR(pd());`	11.0
`auto r = scale(scale(pd()));`	16.9
`auto r = scaleR(scaleR(pd()));`	14.1
`auto r = scale(scale(scale(pd())));`	21.2
`auto r = scaleR(scaleR(scaleR(pd())));`	17.2
Если функции пометить INLINE	8.1 — 8.9

Если заменить Point3f на struct Point3i { int32_t x, y, z; }; и Point3d на struct Point3ll { int64_t x, y, z; };, то различия в производительности будет менее выраженными. Видимо, значительное время уходит на распаковку параметров из регистров, вспомним, что в один 64 битный регистры обычно запаковывается сразу два int, а векторные операции они не поддерживают. С другой стороны, если заменить Point3f на struct Point2ll { int64_t x, y; }; и Point3d на struct Point4ll { int64_t x, y, z, a; };, то цифры будут примерно такие-же.

Что можно заметить:

Небольшие параметры лучше передавать по значению. Передача по ссылке только вредит.
Параметры, не влезающие в регистры, лучше передавать по ссылке.
Если есть возможность сделать функцию inline и поместить её в заголовочный файл, то это стоит сделать. При этом способ передачи параметров, по ссылке, или значению, не играет особой роли. По крайней мере для небольших простых типов.

About optional

Стандартный тип std::optional в данный момент имеет кривую реализацию (смотри http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0602r2.html), которая исправлена только в «x86–64 clang (experimental concepts)» и, вроде бы, MSVC последних версий, поэтому

struct Point {
  float x, y;
};
using OptPoint1 = optional;

будет совсем не эквивалентно

struct OptPoint2 {
  float x, y;
  union { char _; bool d; }; // Как в std::optional.
};

Несмотря на одинаковые размер и выравнивание, OptPoint1 будет передаваться через стек, а OptPoint2 — через регистры.

OptPoint1 foo(OptPoint1 s) { return Point{s->x + 1, s->y + 1}; }
OptPoint2 foo(OptPoint2 s) { return {s.x + 1, s.y + 1, true}; }
...
OptPoint1 s1{Point{1, 2}};
OptPoint2 s2{3, 4, true};
auto result1 = foo(s1);
auto result2 = foo(s2);

.LCPI0_0:
  .long 1065353216 # float 1
foo(std::optional): # @foo(std::optional)
  vmovss xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
  # В rsi хранится адрес начала участка стека с аргументом.
  vaddss xmm1, xmm0, dword ptr [rsi] # Загружаем x со стека, прибавляя 1.
  vaddss xmm0, xmm0, dword ptr [rsi + 4] # Загружаем y со стека, прибавляя 1.
  vmovss dword ptr [rdi], xmm1 # Загружаем x на стек, rdi хранит адрес начала участка на стеке, в который нужно записывать результат.
  vmovss dword ptr [rdi + 4], xmm0 # Загружаем y на стек.
  mov byte ptr [rdi + 8], 1 # Флаг optional::has_value().
  mov rax, rdi # Возвращаем адрес с результатом.
  ret
.LCPI1_0:
  .long 1065353216 # float 1
  .long 1065353216 # float 1
  .zero 4
  .zero 4
foo(OptPoint2): # @foo(OptPoint2)
  vaddps xmm0, xmm0, xmmword ptr [rip + .LCPI1_0] # Складываем [x, y] c [1, 1]. В xmm0 хранится результат.
  mov al, 1  # Возвращаем d, al - это младшие 8 бит регистра rax.
  ret
.LCPI2_0:
  .long 1077936128 # float 3
  .long 1082130432 # float 4
  .zero 4
  .zero 4
main: # @main
  push rbx
  sub rsp, 64
  movabs rax, 4611686019492741120 # 0x400000003F800000 Поля x и y.
  mov qword ptr [rsp + 32], rax # Копируем x, y на стек.
  mov byte ptr [rsp + 40], 1 # Флаг optional::has_value().
  lea rbx, [rsp + 48]
  lea rsi, [rsp + 32] # Участок стека с аргументом.
  mov rdi, rbx # Участок стека с результатом.
  call foo(std::optional)
  # Второй вызов осуществляется гораздо проще.
  vmovaps xmm0, xmmword ptr [rip + .LCPI2_0] # xmm0 = <3,4,u,u>
  mov edi, 1 # Флаг bool d.
  call foo(OptPoint2)
  vmovlps qword ptr [rsp + 16], xmm0 # Копируем результат на стек.
  mov byte ptr [rsp + 24], al # В al хранится самый младший байт регистра rax.

Впрочем, если пометить функции foo как inline, то генерируемый в месте использования код будет примерно одинаков.

  # OptPoint1 foo(OptPoint1) или OptPoint1 foo(const OptPoint1&)
  vmovss xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
  vaddss xmm1, xmm0, dword ptr [rsp + 32]
  vaddss xmm0, xmm0, dword ptr [rsp + 36]
  vmovss dword ptr [rsp + 8], xmm1
  vmovss dword ptr [rsp + 12], xmm0
  mov byte ptr [rsp + 16], 1

  # OptPoint2 foo(OptPoint2) или OptPoint2 foo(const OptPoint2&)
  vmovsd xmm0, qword ptr [rsp + 48] # xmm0 = mem[0],zero
  vaddps xmm0, xmm0, xmmword ptr [rip + .LCPI0_1]
  vmovlps qword ptr [rsp + 8], xmm0
  mov byte ptr [rsp + 16], 1

Видно, что в случае с простой структурой, компилятор смог соптимизировать код чуть лучше, но в остальном всё одинаково.

Вывод: если функция не inline, то лучше всегда передавать std::optional по ссылке.

Virtual functions

Кратко рассм

Особенности вызова функций в С++18.06.2018 16:17

Table of contents

Registers in x86–64

Parameter passing

Simple examples

References

Benchmark

Transparent pointers

Stack reuse

Benchmark

About optional

Virtual functions