Продолжение статьи, где удалось продемонстрировать, что фронтенд стековой машины вполне позволяет спрятать за ним суперскалярный процессор с OoO.
Тема данной статьи — вызов функций.

Стек(и) и вызов функций

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

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

Но прежде сделаем лирическое отступление на тему стека как такового.
Само понятие стек способно вводить в заблуждение.

Вот в IBM/360 нет аппаратного стека. Но функции (в том числе и рекурсивно) вызывать можно, для этого параметры сохраняются в области памяти, которую перед вызовом необходимо выпрашивать у ОС.

В x86 есть аппаратный стек, но никто не относит эту архитектуру к стековым. Этот стек является отличным механизмом для хранения локальных переменных и параметров функций.

AMD29K, SPARC и Itanium относятся к так называемому Berkeley Risc семейству архитектур, у них стек выполняет еще одну важную функцию: пул регистров является верхушкой стека (register windows), что, как предполагается, ускоряет передачу параметров при вызове функций.
SPARC V7 появился на пару лет раньше AMD29K, но он видится (автору) менее архитектурно стройным.
RSE блок Itanium’а в целом аналогичен таковому от AMD29K, но появился существенно позже.

AMD29K заслуживает отдельных добрых слов

В нём два аппаратных стека. Несколько стеков в архитектуре не новы, это было еще на Burroughs B5000, советских (да и нынешних) Эльбрусах. Но там второй стек предназначен для хранения адресов возврата из процедур. Здесь же они оба используются для хранения данных:

• memory stack — используется для хранения больших локальных переменных (структуры и массивы) также как и хвоста параметров, если их больше 16. Регистр gr125(msp) является указателем на вершину этого стека.
• register stack — в наличии 128 локальных регистров, которые образуют вершину стека
  
  • регистровый стек служит для быстрого доступа к вершине стека в памяти (отличного от вышеописанного memory stack, конечно)
  • глобальные регистры gr126(rab) и gr127(rfb) определяют верх и низ стека, gr1(rsp) хранит указатель на его вершину
    
  • умеет делать в одном цикле два чтения и одну запись
  • в нём нет явных стековых операций таких как push&pop, вместо них при вызове функции для нее освобождается определенное компилятором количество регистров (activation record, так здесь называется call frame)
    
  • доступ к данным из activation record идет через регистры, которые для каждой функции нумеруются от lr0
  • lr0 и lr1 зарезервированы, в первом адрес возврата, во втором — activation record вызывающей функции
  • регистровые окна вызывающей и вызываемой функций пересекаются параметрами аналогично SPARC
  • если для вызова новой функции не хватает свободных регистров, происходит trap SPILL, обработчик которого выталкивает часть значений регистров в память, освобождая их
  • наоборот, когда свободных регистров становится слишком много, срабатывает FILL
  • чтобы это происходило, компилятор вставляет инструкции
    

            sub gr1,gr1,16                ;function prologue, lr0+lr1+2 local variables 
            asgeu SPILL,gr1,rab           ;compare with top of window 
    . . .                                 ;function body
            jmpi lr0                      ;return 
            asleu FILL,lr1,rfb            ;compare with bottom of window gr127
    

  
  

Какие интересные идеи следует здесь отметить?

1. Нумерация регистров для каждой функции своя, это особенность Berkeley RISC
2. А вот расщепление стека — особенность именно этой архитектуры. В SPARC’е регистровые окна сохраняются в тот же самый стек, где лежат и обычные (не быстрые) переменные. И fill/spill делаются с разрывами — каждое окно из своего фрейма.

Вот это разделение стека на “большой, но медленный” и “маленький, но быстрый” весьма важно. Разберемся с мотивами.

Передача параметров, вызов функций

Идея стека как хранилища локальных переменных (и параметров) прекрасна в своей логичности и завершенности. Слабое место — производительность системы упирается в задержки и производительность памяти. Во времена PDP-11 с этим ничего нельзя было поделать, но с тех пор ситуация изменилась.

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

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

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

1. Закрепление за определенными регистрами специальной роли. Например, в MSVC(x86-64) принято первые четыре целочисленных аргумента передавать через регистры RCX, RDX, R8, R9. Из этого следует единая нумерация регистров для всех функций. К архитектурам, использующим эту технику, можно отнести также MIPS, PPC, ARM, DEC Alpha … Понятно, что в цепочке вызовов сохранять параметры всё равно больше негде, кроме как на стеке. Тут вся надежда на кэш. Или на оптимизатор, который может решить что конкретный параметр в данной функции больше не используется и сохранять его вовсе не нужно.
2. Техника регистровых окон. Эта ветка архитектур растет из проекта Berkeley Risc. Сюда относится уже разобранный нами AMD29K, а также i960, Itanium, SPARC. Суть в том, что ограниченные количества параметров и локальных данных вызванной функции располагаются в регистровом окне, при вызове следующей функции окно сдвигается, таким образом эти данные образуют стек. В каждой функции своя нумерация регистров. Всё что не влезло в окно, попадает в обычный стек, глобальные регистры под временные данные также могут быть использованы. Так вот в случае i960 и SPARC, регистровый стек вкраплен в обычный, а для AMD29K & Itanium — это разные стеки. Фактически, AMD29K & Itanium предлагают компилятору выбрать, какие данные он считает достойными оказаться в “быстром стеке”, всё остальное произойдет само собой. Это напоминает устаревшее ныне ключеве слове “register” в С, только решение принимает компилятор, язык высокого уровня всё же.

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

Но мы несколько увлеклись, пора вернуться к сохранению контекста текущей функции в проектируемой архитектуре.

Сохранение контекста функции

А что входит в этот контекст? Занятые на момент вызова дочерней процедуры регистры.
При этом регистры недовычисленных выражений связаны между собой через топологическую сортировку, но для вызываемой функции это не имеет значения. На момент захвата моп’ами выходных регистров уже неважно в каком порядке они были захвачены.

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

Теперь стоит определиться с нумерацией регистров.
Пусть нумерация общая, т.е. мы пошли по пути MIPS, а не SPARC.

• Если цепочка вызовов достаточно длинная, очевидно, что все регистры заняты. И речь идет о том, какие из них мы будем сгружать в память (SPILL). Т.е. порядок захвата всё же важен.
• порядок захвата зависит от предыстории вызовов
• внутри функции он определяется динамически
• нет никаких гарантий, что вернув результат работы функции в некотором регистре, мы не получим (во время обратного выполнения FILL) конфликт с этим регистром
• автор не видит путей избежать подобных конфликтов, что, конечно, не означает, что их (путей) действительно нет

Попробуем регистровые окна.

• нумерация регистров в каждой функции начинается заново и это просто замечательно т.к. избавляет нас от учета предыстории
• обычная техника — кольцевой буфер регистров, FILL&SPILL
• будем использовать два физических стека — для регистровых окон и всего остального
• нужно запомнить какие регистры использованы на момент вызова дочерней функции. И такая информация у нас есть. Допустим, заняты регистры r0, r5 и r11. Фактически, используется только четверть от использованного диапазона регистров и есть соблазн как-то “упаковать” их. Но тогда при возврате из дочерней функции придется “распаковывать” их обратно. Так что пул регистров текущей функции (в данном случае) останется размером в 12 регистров (+служебная информация: адрес возврата, предыдущий frame). Тем более, что само по себе количество регистров не так уж и критично, гораздо дороже обходится количество одновременных операций чтения/записи, а оно не изменится
• а вот с сохранением регистров в память, пожалуй, что-то можно сделать, попробуем не сохранять в память заведомо ненужные данные из незанятых регистров
• для этого после записи занятых регистров функции, сохраним маску их занятости
• а для этого, в свою очередь, придется FILL&SPILL делать не по количеству необходимых регистров, а по-фреймно: всё, что касается одного вызова за раз
• тогда в текущем начале кольцевого буфера регистров всегда будет описатель фрейма (следующего кандидата на SPILL)
• а первый регистр, который мы достаем при FILL’е будет содержать маску (или ее часть) использованных регистров, с использованием которой мы достанем из памяти и нужное количество регистров, что и требовалось

Однако, сосредоточившись на внешней стороне вызова функций мы упустили из вида то, как всё это будет исполняться внутри. Автор не считает себя специалистом по “железу”, но проблемы всё же предвидит.
К счастью, разбираться с ними мы будем в следующей статье.