Адресное пространство – из нескольких областей данных. На схеме приведено типичное распределение логических адресов:

Количество памяти, необходимое для размещения объекта, определяется его типом.

На схему размещения оказывают влияние ограничения целевой машины. Например, многие архитектуры требуют выравнивания: размещения в адресах, кратных какой-то константе, например 4. Тогда, хотя для хранения массива 10 байт, могут выделяться 12 байт из-за выравнивания.

Статическое выделение памяти – решение принято в процессе компиляции. В противном случае, динамическое выделение памяти.

Для динамического выделения памяти – комбинация стратегий:

Локальные данные процедуры и вспомогательная информация (запись активации) – в стеке.

Данные, время жизни которых не определено – в куче.

Записи активации

Говоря о памяти на стеке, вызов процедуры принято называть активацией, а процедуры, которые в настоящий момент выполняются – активными.

Вызовы процедур и возвраты управляются стеком управления. Каждая активная процедура имеет запись активации. Записи активации иногда называются кадрами или фреймами. На стеке всегда фреймы, соответствующие активным процедурам. Фрейм последней по времени активации – на вершине стека.

Не исчерпывающий список возможных данных в фрейме:

1. Область памяти для временных значений, которые не удаётся разместить в регистрах
2. Локальные данные процедуры
3. Состояние до активации (адрес возврата, содержимое регистров)
4. Связь доступа – доступ к нелокальным данным
5. Связь управления – указатель на фрейм вызывающей процедуры
6. Область памяти для возвращаемого значения (часто в регистре)
7. Параметры вызова процедуры (часто в регистрах)

Последовательности вызова и возврата

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

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

При проектировании структуры записи активации, принципы:

1. Передаваемые параметры – в начале фрейма. Конструирует вызывающая процедура
2. Элементы фиксированного размера – связь управления, связь доступа и состояние машины – посередине.
3. Элементы неизвестного размера – например, локальные массивы – в конце фрейма.

Доступ к нелокальным данным

Рассмотрим, как процедура обращается к данным, не принадлежащим ей.

Для языков без вложенных процедур (C), доступ к нелокальным переменным – простой. Переменные:

• Глобальные, память статическая
• Локальные к текущей активации, в активном фрейме

Существенно сложнее при вложенных процедурах: переменные, локальные для внешней процедуры, должны быть доступны во внутренней.

Реализация – через связь доступа.

Если процедура P непосредственно вложена в процедуру Q, то связь доступа каждой активации P указывает на последнюю активацию Q.

Связи доступа образуют цепочку записей активации, в которых все данные, доступные процедуре.

Введём понятие глубины вложенности. Для процедур, не вложенных ни в какую другую, глубина вложенности – 0. Для процедур, определённых непосредственно внутри процедуры с глубиной вложенности \(n\), глубина вложенности будет \(n+1\).

Если процедура P с вложенностью \(n_p\) получает доступ к локальным данным процедуры Q с вложенностью \(n_q\), (понятно, \(n_q \le n_p\)), то ищется последний фрейм для Q – через \(n_p-n_q\) переходов по связям доступа. Локальные данные Q – по фиксированному смещению от фрейма Q.

Язык с передачей процедур как параметров – ещё немного сложнее. При вызове процедуры, переданной параметром, недостаточно информации для определения связи доступа. Решение – при передачи процедуры, вместе с ней передавать и связь доступа. Связь доступа известна в месте определения.

При большой вложенности процедур – многократный переход по связям доступа; негативно для производительности. Тогда в каждом фрейме – массив связей доступа, индексированный глубиной вложенности. Такие массивы называются дисплеями. Минус: при каждой активации – копирование дисплея.

Хороший диспетчер памяти должен:

• Эффективно использовать память. Снижение фрагментации.
• Так размещать объекты в памяти, чтобы программа выполнялась максимально быстро. Локальность данных.
• Иметь низкие накладные расходы. Сложнее для мелких выделений памяти.

Снижение фрагментации кучи

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

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

При освобождении памяти, блоки помечаются как свободные. Смежные свободные блоки – сливаются, иначе их размер будет монотонно уменьшаться.

“Плохой” диспетчер фрагментирует кучу, т.е. куча состоит из большого количества несмежных мелких свободных блоков. При очередном выделении памяти – подходящих блоков нет, при этом общий объём свободной памяти – велик.

Снижение фрагментации – управлением размещения в куче. Эмпирически, хорошая стратегия – выделение в наименьшем из подходящих блоков. Называется стратегией наилучшего подходящего (best-fit).

Выделение в первом найденном блоке – простая стратегия первого подходящего (first-fit), проигрывает в смысле фрагментации памяти, но возможно заметно быстрее.

Эффективная реализация стратегии best-fit

Блоки свободной памяти – по “корзинам” в соответствии с их размерами.

Много блоков в корзине с малым размером, и меньше – с большим.

Например, диспетчер памяти dlmalloc (Lea), выравнивает блоки на 8-байтовые границы. По одной корзине для блоков каждого кратного 8 байтам размера от 16 до 512 байт. Корзины размеров, больших 512 байт – с блоками разных размеров, минимальный размер каждой корзины вдвое больше предыдущего, а внутри корзины блоки упорядочены по размерам. Один блок свободной памяти имеет изменяемый размер и считается самым большим. Такая схема позволяет достаточно быстро находить блоки нужного размера.

“Корзины” – списки указателей на начальные адреса блоков, хранятся в массиве.

Стратегия best-fit – негативна для локальности. Модификация – для идущих подряд запросов на выделение памяти – по возможности выделение из смежных блоков. Называется “стратегия следующего подходящего” (next-fit)

Управление свободной памятью

Об объединении свободных блоков.

При наличии “корзин” фиксированного размера – объединение бессмысленно. Тогда, занятость блоков – по битовой карте. При нехватке свободных блоков – запрос памяти у ОС и расширение битовой карты.

В противном случае, комбинация двух подходов:

1. Дескрипторы границ. С обоих концов блока хранится информация, указывающая, свободен блок или занят, а также его размер.

2. Двусвязный список свободных блоков. Свободные блоки связываются в двусвязный список. Указатели этого списка хранятся в самих блоках. Порядок блоков в списке может быть произвольный, но вообще говоря список может быть и отсортирован, например, по размеру, чтобы облегчить поиск подходящих блоков.

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

Задачи генератора кода:

• выбор команд
• распределение регистров
• упорядочение команд

Целевой код

Сложность разработки хорошего кодогенератора зависит от целевой архитектуры. Наиболее распространёнными являются архитектуры типа:

• RISC (Restricted/Reduced Instruction Set Computer)
• CISC (Complex/Complete Instruction Set Computer)
• Стековая машина

RISC-архитектуры – много регистров, простой набор команд. Хорошо вписываются в концепцию кодогенератора, но плохи для “ручной” разработки.

CISC-архитектуры — мало регистров, множество различных, возможно дублирующих, команд. Хорошо для “ручной” разработки, хуже для кодогенератора. Ассемблеры x86 и x86_64 – CISС. На практике – RISC-ядро и трансляция CISC в RISC.

Стековые машины – редки в “железном” исполнении. Чаще – виртуальная машина для байт-кода, например, Java.

Выбор команд

Кодогенератор отображает промежуточный код на целевой.

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

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

Напр., команды x=y+z – несколько инструкций загрузки из памяти и сохранения в память. Несколько последовательных команд такого вида могут избыточно работать с памятью.

Другой фактор – скорость выполнения разных команд целевого кода. Напр., инструкция a=a+1 может быть (абстрактно) транслирована в ADD a, 1 или в INC a. Могут иметь разное время выполнения.

Распределение регистров

Одна из ключевых задач эффективной кодогенерации.

Регистры – наиболее быстрая память, но их мало. Важно использовать максимально эффективно.

Оптимальное распределение регистров – NP-полная задача. Следовательно, эвристики.

Ряд регистров – под специализированные нужды, напр. указатель на вершину стека. Другие – свободно.

Алгоритм выбора регистров внутри базового блока

Рассмотрим x = y + z (где + – любой оператор).

Тогда, сначала – регистры для y и z, затем – регистр для x.

Регистры для y и z – одинаково. Выбор для y:

1. Если y – уже в регистре, использовать его
2. Если y не в регистре, и есть пустой регистр (не содержащий живых переменных), используем его

3. Если пустых регистров нет, для каждого из занятых регистров R, хранящего значение v:
   1. Если v есть где-то кроме R (например, было загружено из памяти), используем R
   2. Если v есть x, т.е. будет перезаписано текущей командой, и x – не y или z, используем R
   3. Если v в базовом блоке более не используется, используем R
   4. Иначе, регистр R нельзя использовать.
   5. Если ни один регистр не подходит, сброс одного регистра в память, с последующим восстановлением.

Выбор регистра для x похож, но есть отличия:

1. Регистр, хранящий x, всегда подходит для x, даже если x есть y или z (если допускается целевой машиной, обычно – да)
2. Если значения y или z более не используется в рамках базового блока, их регистры можно использовать для x.

Вне базовых блоков осмыслено назначение “глобальных” регистров для часто используемых переменных (например, счётчики циклов). Правило не универсально, компиляторы, могут производить анализ ожидаемого выигрыша.

Примеры оптимизаций:

• Устранение “лишних” инструкций
  • В частности, лишних загрузок и сохранений из/в оперативную память
  • Недостижимого кода (скажем, используемого для отладки)
• Оптимизация потока управления
  • Устранение цепочек переходов (т.е. устранение лишних безусловных переходов)
• Алгебраические упрощения
• Использование машинных идиом

Идея – начало обработки следующей команды до завершения предыдущей. Типичный процессор для каждой команды выполняет:

1. Чтение команды из памяти
2. Декодирование команды
3. Исполнение команды
4. Обращение к памяти
5. Сохранение результата

Сложность – команды ветвления. Неизвестно, по какой ветви пойдёт выполнение. Следствие – опустошение конвейера. Решение – спекулятивное исполнение, попытка предсказать, по какой ветви пойдёт исполнение, тогда опустошение – только при неверном предсказании. Следствие – уязвимости Meltdown и Spectre. Как следствие исправления – потеря производительности.

Не все команды полностью конвейеризуемы. Если следующая команда зависит от результатов предыдущей, то не может быть конвейеризована. Компиляторы (и даже процессоры!) могут менять порядок выполнения команд для обхода этой проблемы. Может влиять на наблюдаемое поведение.

Другой источник ускорения – векторные команды, т.е. команды, производящие операцию над несколькими адресами. Может быть реализовано как в компиляторе (тогда используются специальные инструкции, называемые в общем VLIW – very long instruction word), так и непосредственно в исполнительном устройстве, тогда такой процессор называется суперскалярным.

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

Локальность данных важна, поскольку в кэши процессора данные загружаются “блоками”. Обращение к данным, находящимся рядом в памяти, с большей вероятностью использует быстрый кэш. Та же логика – к временной локальности – если к одним и тем же данным производятся обращения в течение небольшого промежутка времени, эти данные с большей вероятностью будут в кэше.

Два эмпирических принципа:

• Данные, объявляемые вместе, используются вместе. Следствие – стратегия next-fit размещения в куче более эффективна.
• Временная и пространственная локальность коррелируют. К данным, расположенным близко в памяти, доступ осуществляется близко по времени. Следствие – работает кэширование.

Пример:

for(i = 0; i < n; ++i) {
  Z[i] = X[i] - Y[i];
  Z[i] = Z[i] * Z[i];
}

тот же код можно написать иначе:

for(i = 0; i < n; ++i) {
  Z[i] = X[i] - Y[i];
}
for(i = 0; i < n; ++i) {
  Z[i] = Z[i] * Z[i];
}

Оба варианта имеют одинаковое количество присваиваний. Без оптимизаций, первый вариант будет – быстрее за счёт лучшей локальности (заметно при больших n).

Пример:

for (j = 0; j < n; ++j)
  for (i = 0; i < m; ++i)
    Z[i+m*j] = 0;

против

for (i = 0; i < m; ++i)
  for (j = 0; j < n; ++j)
    Z[i+m*j] = 0;

Одно и то же, но в разном порядке. Первый вариант проходит по массиву линейно, второй – “прыгает” по массиву. В силу худшей локальности, второй вариант – медленнее (возможно на порядок!)

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