Учебное пособие 800492

На рис. 2.15 показан стек до, во время и после вызова функции diffofsums из вышеизложенного примера кода

Рис. 2.15. Стек до (a), во время (b) и после (c) вызова функции diffofsums

Функция diffofsums выделяет пространство на стеке для трёх слов, уменьшая указатель стека $sp на 12. Затем она сохраняет текущие значения $s0, $t0 и $t1 в выделенном пространстве. Дальше выполняется остальная часть функции, которая меняет значения этих трёх регистров. В завершение, функция diffofsums восстанавливает значения регистров $s0, $t0 и $t1 из стека, освобождает пространство на стеке и возвращается в main. Когда функция выполняет возврат, в регистре $v0 находится её результат, но другие побочные эффекты отсутствуют: в регистрах $s0, $t0, $t1 и $sp находятся те же значения, которые там и были до вызова функции.

Оберегаемые регистры

В примере кода 6.26 предполагается, что временные регистры $t0 и $t1 следует сохранять и восстанавливать. Если вызывающая функция не использует эти регистры, то усилия по

81

сохранению и восстановлению их значений тратятся впустую. Чтобы избежать этих

издержек, в архитектуре MIPS регистры разделены на две категории: оберегаемые (англ.: preserved) и необерегаемые (англ.: nonpreserved).

Оберегаемые регистры включают $s0–$s7 (отсюда их название: сохраняемые, англ.: saved). Необерегаемые регистры включают $t0–$t9 (отсюда их название: временные, англ.: temporary). Функция должна сохранять и восстанавливать любые оберегаемые регистры, с которыми она собирается работать, но может свободно менять значения необерегаемых регистров.

В представленном ниже примере кода показана улучшенная версия функции diffofsums, которая сохраняет на стеке только регистр $s0. Регистры $t0 и $t1 являются необерегаемыми регистрами, поэтому их сохранять не обязательно

Пример. Функция, сохраняющая оберегаемые регистры на

стеке

Код на языке ассемблера MIPS

# $s0 = result diffofsums:

addi $sp, $sp, −4 # make space on stack to store one regis-

ter

addi $sp, $sp, 4 # deallocate stack space jr $ra # return to caller

82

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

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

В таблице 2.1 приведены все оберегаемые регистры. Регистры $s0–$s7 обычно используют для хранения локальных переменных внутри функции, поэтому они должны быть сохранены. Регистр $ra также следует сохранять, чтобы функция знала, куда возвращаться. Регистры $t0–$t9 используют для хранения временных результатов перед тем, как присвоить эти значения локальным переменным. Вычисления, использующие временные результаты, обычно завершаются до того, как вызывается функция, поэтому эти регистры не оберегаются, а необходимость сохранять их в вызывающей функции возникает крайне редко. Регистры $a0–$a3 часто перезаписываются в процессе вызова функции, поэтому вызывающая функция должна сохранять их, если эти значения могут понадобиться ей после завершения вызванной функции.

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

83

Стек выше указателя стека автоматически остаётся в сохранности, если только вызываемая функция не осуществляет запись в память по адресам выше $sp. При таком подходе она не меняет кадры стека (англ.: stack frames) других функций. Сам указатель стека остаётся в сохранности потому, что вызываемая функция перед завершением работы освобождает свой кадр стека, прибавляя к $sp то же значение, которое вычла из него в начале.

Рекурсивные вызовы функций

Функция, которая не вызывает другие функции, называется листовой, или терминальной, функцией (англ.: leaf function); пример – функция diffofsums. Функция, которая вызывает другие функции, называется нелистовой (или, соответственно, нетерминальной, англ.: nonleaf function). Как было замечено ранее, нелистовые функции устроены более сложно, потому что перед вызовом других функций им приходится сохранять необерегаемые регистры на стеке и затем восстанавливать эти регистры. А именно, вызывающая функция сохраняет любые необерегаемые регистры ($t0–$t9 и $a0–$a3), значения которых будут нужны ей после вызова. Вызываемая функция сохраняет любые оберегаемые регистры ($s0–$s7 и $ra), которые собирается изменять.

Рекурсивная функция – это нелистовая функция, вызывающая сама себя. Функция вычисления факториала может

84

быть реализована в виде рекурсивной функции. Вспомним, что factorial(n) = n × (n – 1) × (n – 2) ×… × 2 × 1. Функция factorial

в рекурсивном представлении выглядит как factorial(n) = n × factorial(n – 1).

Факториал от 1 – это просто 1. В примере следующем примере показана функция factorial, записанная в рекурсивном виде. Для удобства предполагаем, что программа начинается с адреса 0x90.

Пример Рекурсивный вызов функции factorial Код на языке высокого уровня

int factorial(int n) { if (n <= 1)

return 1; else

return (n * factorial(n − 1));

}

Код на языке ассемблера MIPS

Функция factorial изменяет регистры $a0 и $ra, поэтому она сохраняет их на стеке. Затем она проверяет условие n < 2. Если условие выполнено, она помещает значение 1 в регистр

85

$v0, восстанавливает указатель стека и возвращается к вызывающей функции. В этом случае нет необходимости восстанавливать регистры $ra и $a0 потому, что они не менялись. Если n > 1, функция рекурсивно вызывает factorial(n–1). Затем она восстанавливает значение n ($a0) и адрес возврата ($ra) из стека, выполняет умножение и возвращает результат. Инструкция умножения (mul $v0, $a0, $v0) умножает $a0 и $v0 и помещает результат в $v0.

На рис. 2.16 показан стек в процессе выполнения функции factorial(3). Мы предполагаем, что $sp изначально указывает на 0xFC, как показано на Рис. 2.16 (a). Функция создаёт кадр стека из двух слов для хранения $a0 и $ra. При первом вызове factorial сохраняет $a0 (содержащий n = 3) по адресу 0xF8 и $ra по адресу 0xF4, как показано на Рис. 2.16

(b). Затем функция меняет $a0 на n = 2 и рекурсивно вызывает factorial(2), при этом значение $ra меняется на 0xBC. При втором вызове функция сохраняет $a0 (содержащий n = 2) по адресу 0xF0 и $ra по адресу 0xEC. В этот раз мы знаем, что $ra содержит 0xBC. Затем функция меняет $a0 на n = 1 и рекурсивно вызывает factorial(1). При третьем вызове она сохраняет $a0 (содержащий n = 1) по адресу 0xE8 и $ra по адресу 0xE4. На этот раз $ra опять содержит 0xBC. Третий вызов factorial возвращает значение 1 в регистре $v0 и освобождает кадр стека перед тем, как вернуться ко второму вызову. Второй вызов восстанавливает значение n=2, восстанавливает значение 0xBC в $ra (так получилось, что он уже содержит это значение), освобождает кадр стека и возвращает $v0 = 2 × 1 = 2 первому вызову. Первый вызов восстанавливает n = 3, восстанавливает адрес возврата к вызывающей функции в $ra, освобождает кадр стека и возвращает $v0 = 3 × 2 = 6.

На рис. 2.16 (c) показан стек после завершения рекурсивно вызванных функций. Когда функция factorial возвращает управление вызвавшей ее функции, указатель стека находится в своём изначальном положении (0xFC), содержимое стека выше

86

значения указателя стека не менялось и все оберегаемые регистры содержат свои изначальные значения. Регистр $v0 содержит результат вычисления (6).

Рис. 2.16. Стек до (a), после последнего рекурсивного вызова (b) и после завершения (c) вызова

функции factorial при n = 3

Дополнительные аргументы и локальные переменные

У функций могут быть более четырёх аргументов и локальных переменных. Стек используют для хранения этих временных значений. Следуя соглашениям архитектуры MIPS, если у функции больше четырёх аргументов, то первые четыре из них, как обычно, передаются через регистры для аргументов. Дополнительные аргументы передаются на стеке, прямо над указателем стека $sp. Вызывающая функция должна расширить стек для дополнительных аргументов.

На рис. 2.16 (a) показан стек вызывающей функции при вызове функции, принимающей более четырёх аргументов. Функция также может объявлять локальные переменные или массивы.

С локальными переменными, объявленными внутри функции, может работать только сама эта функция. Локальные переменные хранятся в регистрах $s0–$s7; если локальных пе-

87

ременных слишком много, их можно хранить в кадре стека функции. В частности, локальные массивы хранятся в стеке.

На рис. 2.17 (b) показана структура стека вызываемой функции.

Рис. 2.17. Использование стека перед вызовом (a) и после вызова (b)

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

2.7. Режимы адресации

В архитектуре MIPS используются пять режимов адресации: регистровый (англ.: register-only), непосредственный (англ.: immediate), базовый (англ.: base), относительно счетчика команд (англ.: PC-relative) и псевдопрямой (англ.: pseudodirect). Первые три режима (регистровый, непосредственный и базовый) определяют способы чтения и записи операндов. Последние два (режим адресации относительно счетчика команд и

88

псевдопрямой режим) определяют способы записи счётчика команд (англ.: program counter, PC).

Регистровая адресация

При регистровой адресации регистры используются для всех операндов-источников и операндов-назначений (иными словами – для всех операндов и результата). Все инструкции типа R используют именно такой режим адресации.

Непосредственная адресация

При непосредственной адресации в качестве операндов наряду с регистрами используют 16-битные константы (непосредственные операнды). Этот режим адресации используют некоторые инструкции типа I, такие как сложение с константой (addi) и загрузка константы в старшие 16 бит регистра (lui).

Базовая адресация

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

Адресация относительно счетчика команд

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

Смещение со знаком прибавляется к счетчику команд (PC) для определения нового значения PC, поэтому тот адрес, куда будет осуществлен переход, называют адресом относительно счетчика команд.

В приведённом ниже примере кода показана часть функции factorial из предыдущего примера.

89

Пример Вычисление целевого адреса ветвления

0xB4 else: addi $a0, $a0, −1

0xB8 jal factorial

На рис. 2.18 показан машинный код для инструкции beq. Целевой адрес ветвления (англ.: branch target address,

BTA) – это адрес инструкции, которая будет выполнена следующей в том случае, если случится ветвление. На Рис. 2.18 у инструкции beq целевой адрес ветвления равен 0xB4 – это адрес инструкции с меткой else.

Рис. 2.18. Машинный код для инструкции beq

16-битный непосредственный операнд задаёт число инструкций между целевым адресом ветвления и инструкцией, находящейся сразу после инструкции перехода (т.е. инструкции по адресу PC + 4). В нашем случае непосредственный операнд равен 3 потому, что целевой адрес ветвления (0xB4) расположен через 3 инструкции после инструкции с адресом PC +

4 (0xA8).

Процессор вычисляет целевой адрес ветвления, выполняя знаковое расширение 16-битного непосредственного операнда до 32 бит и умножая полученное значение на 4 (чтобы преобразовать слова в байты), после чего добавляя это произведение к значению PC+4.

90