- PVSM.RU - https://www.pvsm.ru -
Продолжение серии статей, разбирающих идею суперскалярного [1] процессора с
OoO [2] и фронтендом [3] стековой машины.
Тема данной статьи — вызов функций, вид изнутри.
Предыдущие статьи:
1 [4] — описание работы на линейном куске
2 [5] — вызов функций, сохраняем регистры
Сосредоточившись в прошлой статье на внешней стороне вызова функций мы упустили из вида то, как всё это будет исполняться внутри. Автор не считает себя специалистом по “железу”, но проблемы всё же предвидит.
Мы упоминали о том, что после возврата из функции хочется получить процессор в том же состоянии что и до него. И именно для этого озаботились сохранением состояния регистров. Но ведь состояние процессора это не только регистры. но и очереди мопов, состояние конвейеров …
Представим себе ситуацию, когда на момент вызова функции мы имеем:
В результате нельзя просто так начать исполнение новой функции т.к.
Может показаться, что мы предприняли определенные меры, чтобы избежать описанных проблем когда декларировали вызов функции обобщенной инструкцией, которая должна перед вызовом дождаться вычисления всех своих аргументов.
Однако, есть проблема с тем, что декодер успеет обработать код после вызова функции, если он независим по данным. Например:
int i, j, k;
…
i = foo (i + 1);
j += k;
bar (i, j);
После возврата из foo мы не можем полагаться ни на то, что j успела вычислиться и сохранена (а потом восстановлена) в контексте текущей задачи, ни на то, что сохранились мопы от j += k; если вычислиться она не успела.
Допустим, увидев вызов функции декодер прекращает свою работу вплоть до возврата из этой функции. Тогда как быть с такой ситуацией:
int i, j, k;
…
bar (foo (i + 1), j += k);
Одним декодером здесь не обойдешься. Похоже, после возврата из функции надо просто начинать декодирование и исполнение дальнейшего кода заново.
Но ведь в основном, эти проблемы, вызванные суперскалярностью, не уникальны для нашей архитектуры, может не нужно изобретать велосипед, а стоит посмотреть как это уже решено ранее.
Хорошо, давайте взглянем на Sandy Bridge [6] от Intel (спасибо Таситу Мурки aka Felid [7])
а также здесь [8]
Предположительно, фронтенд Sandy Bridge,
Как же происходит вызов функции?
Разберем следующий пример
int i, j, k, l, m, n;
...
i = 1 + foo (1 + bar (1 + biz (1 + baz (1 + j) + k) + l) + m) + n;
Будем наивно предполагать, что весь этот код разместится в одну 32 байтовую порцию и порядок генерации кода (при отключенном оптимизаторе) будет соответствовать порядку текста. Разметим код в соответствии с тем, в какой экземпляр секции он попадет в кэше L0m:
int i, j, k, l, m, n;
...
1> i = 1 +
4> foo (
1> 1 +
3> bar (
1> 1 +
2> biz (
1> 1 +
1> baz (1 + j)
2> + k)
3> + l)
4> + m)
5> + n;
Этот фрагмент займет по видимому 5 строк кэша из 256 имеющихся.
Неудивительно, что компилятор изо всех сил старается инлайнить небольшие функции.
Итак, мы рассмотрели как вызываются функции в одной из весьма изощренных микро-архитектур, какую пользу можно из этого извлечь?
Выделим объективные моменты:
Может показаться, что всё это сработает и для нашей архитектуры со стековым фронтендом. Но есть нюанс.
Поясним на примере. Вот функция Аккермана [13]:
int a(int m, int n)
{
if (m == 0)
return n + 1;
if (n == 0)
return a(m - 1, 1);
return a(m - 1, a(m, n - 1));
}
Выглядит просто, но демонстрирует чудеса рекурсии. Нижеследующий график показывает динамику глубины вложенности для вызова a(3, 5), по x — номер шага, по y — глубина вызова.
Поскольку мы решили рассматривать вызов функции как обобщенную инструкцию с произвольным количеством параметров, в случае m*n != 0, первый аргумент (m-1) останется в стеке мопов, в то время как будет вычисляться второй аргумент: a(m, n-1). Хорошо, если первый аргумент успеет вычислиться и его значение будет сохранено при вызове в регистровом стеке. Но может так случиться, что выражение для первого аргумента будет вычисляться дольше, чем аргументы дочернего вызова во втором аргументе. И тогда у нас зависнут в немалых количествах недоработавшие мопы.
Моп родительского вызова тоже будет ждать, пока не отработает дочерний вызов. Глубина вызовов легко может достигнуть (десятков) тысяч единиц, в SandyBrige, к примеру, просто нет столько мопов.
Суть проблемы в том что, признав вызов обобщенной инструкцией мы тем самым признали программу обобщенным выражением. А дерево этого выражения благодаря рекурсии может быть любой высоты. С другой стороны, стек выражения у нас ограничен. А элементами стека являются индексы мопов, коих тоже ограниченное количество.
Но мы не привыкли так легко сдаваться, поэтому в дело вступает план Б.
Регистровые суперскалярные процессоры не имеют подобных проблем т.к. выявление связей между мопами происходит позднее — на этапе переименования регистров.
У нас же эти связи хранятся в стеке индексов мопов.
Может быть сохранить состояние стека? Сохранять индексы мопов мало, как мы выяснили, сами мопы тоже нуждаются в нашей заботе. Кажется естественным организовать сохранение мопов через стек, выделенный или нет, вопрос совершенно отдельный.
И тут мы сталкиваемся с теми же самыми проблемами, которые встречали при попытке сохранить регистры. А именно, при единой (для всех функций) идентификации мопов:
Способ решения этих проблем предлагается тот же самый:
На первый взгляд необходимость прогонять через память декодированные мопы представляется чудовищной. Но когда катехоламины [14] догорают, становится понятно, что масштаб катастрофы не так уж и велик.
До сих пор мы не обращали внимания на слабое место всех стековых машин — избыточные обращения к памяти.
Вот ими и займемся в следующей статье.
Автор: zzeng
Источник [16]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/stek/116254
Ссылки в тексте:
[1] суперскалярного: http://www.ixbt.com/cpu/cpu-pedia.shtml#superscal
[2] OoO: http://www.ixbt.com/cpu/cpu-pedia.shtml#OoO
[3] фронтендом: http://www.ixbt.com/cpu/cpu-pedia.shtml#front-end
[4] 1: https://habrahabr.ru/post/278575/
[5] 2: https://habrahabr.ru/post/279123/
[6] Sandy Bridge: http://www.ixbt.com/cpu/sandy-bridge-1.shtml
[7] Таситу Мурки aka Felid: http://forum.ixbt.com/users.cgi?id=info:Felid
[8] здесь: http://www.realworldtech.com/sandy-bridge
[9] декодер: http://www.ixbt.com/cpu/cpu-pedia.shtml#ID
[10] кэш мопов: http://www.ixbt.com/cpu/cpu-pedia.shtml#mop-cache
[11] буфера мопов: http://www.ixbt.com/cpu/cpu-pedia.shtml#mop-buffer
[12] предсказатель переходов: http://www.ixbt.com/cpu/cpu-pedia.shtml#BPU
[13] функция Аккермана: https://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%90%D0%BA%D0%BA%D0%B5%D1%80%D0%BC%D0%B0%D0%BD%D0%B0
[14] катехоламины: https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B5%D1%85%D0%BE%D0%BB%D0%B0%D0%BC%D0%B8%D0%BD%D1%8B
[15] volatile регистры: https://msdn.microsoft.com/en-us/library/9z1stfyw.aspx
[16] Источник: https://habrahabr.ru/post/280087/
Нажмите здесь для печати.