Стек, подпрограммы и конвенции относительно использования регистров

Базовая страница Moodle:

• Стек и подпрограммы

• Универсальные подпрограммы

Копипаста (слегка ужатая):

Подпрограммы

Подпрограмма — часть программного кода, оформленная таким образом, что

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

• переход на этот участок кода (вызов подпрограммы) возможен из произвольных мест кода

• после выполнения подпрограммы происходит переход «обратно» в место вызова (выход из подпрограммы)

Аппаратное решение: атомарная команда записи адреса возврата и перехода:

jal

• Адрес следующей ячейки записывается в регистр $ra ($r31)

• Происходит переход на адрес

Возврат из подпрограммы — команда перехода на адрес, находящийся в регистре $ra

jr $ra

Пример: подпрограмма проверки, является ли фигура со сторонами $t1, $t2 и $t3 треугольником. Ответ — 0 или 1 в регистре $t0

# какие-то значения
        li    $t1 5
        li    $t2 6
        li    $t3 7
# вызов подпрограммы
        jal    treug
# какой-то ещё код
    …
# Выход из основной программы
        li     $v0 10
        syscall
    …
# Возможно, другие подпрограммы
    …
# Подпрограмма
treug:  move
 $zero
        add
 $t1 $t2
        add
 $t2 $t3
        add
 $t3 $t1
        bgt    $t3 $t4 not
        bgt    $t1 $t5 not
        bgt    $t2 $t6 not
        li     $t0 1
not:    jr     $ra

Решённые задачи:

• атомарного вызова
• произвольного вызова и возврата

Нерешённые задачи

• «прозрачности» повторного использования
  • сохранение регистров
  • передача параметров
  • возвращение значения
  • локальности меток (переменных/адресов перехода)

• вложенного вызова

• рекурсивного вызова

Обратите внимание на то, что в примере выше изменяются значения регистров $t4, $t5 и $t6, а значения регистров $t0 - $t3 используются для передачи параметров и возврата значения.

Подпрограмма — это самый обычный программный код, находящийся в памяти там, куда его поместил транслятор. Выполняться она должна только по команде jal, непосредственный переход на подпрограмму смысла не имеет. В частности, надо предпринять специальные меры, чтобы счётчик команд не дошагал до подпрограммы естественным путём (в примере используется специальный системный вызов «завершить прогармму»).

Прозрачность требует

• отдельной конвенции
• механизма сокрытия локальных меток

Проблема вложенного вызова возникает, когда подпрограмма вызывается из другой подпрограммы:

• текущий адрес возврата надо сохранять перед вложенным вызовом и восстанавливать перед возвратом;

• конвенция должна предусматривать цепочку вложенных вызовов

  • ⇒ регистров на всю цепочку не хватит, их тоже надо где-то сохранять/восстанавливать

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

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

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