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

Разбор Д/З

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

Копипаста:

Задача повторного использования исходного кода

запрограммировать однажды, использовать часто.

Решение на уровне трансляции — макросы

Решение на программном уровне — подпрограммы

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

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

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

   1 jal адрес

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

   1 jr $ra

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

   1 # какие-то значения
   2         li    $t1 5
   3         li    $t2 6
   4         li    $t3 7
   5 # вызов подпрограммы
   6         jal    treug
   7 # какой-то ещё код
   8     …
   9 # Выход из основной программы
  10         li     $v0 10
  11         syscall
  12     …
  13 # Возможно, другие подпрограммы
  14     …
  15 # Подпрограмма
  16 treug:  move   $t0 $zero
  17         add    $t4 $t1 $t2
  18         add    $t5 $t2 $t3
  19         add    $t6 $t3 $t1
  20         bgt    $t3 $t4 not
  21         bgt    $t1 $t5 not
  22         bgt    $t2 $t6 not
  23         li     $t0 1
  24 not:    jr     $ra

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

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

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

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

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

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

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

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

Простая конвенция для концевых подпрограмм

  1. Подпрограмма вызывается с помощью инструкции "jal"(которая сохранит обратный адрес в регистре $ra).
  2. Подпрограмма не будет вызывать другую подпрограмму
  3. Подпрограмма возвращает управление вызывающей программе с помощью инструкции "jr $rа".
  4. Регистры используются следующим образом:
    • $t0 - $t9 - подпрограмма может изменить эти регистры.
    • $s0 - $s7 - подпрограмма не должна изменять эти регистры.
    • $a0 - $a3 - эти регистры содержат параметры для подпрограммы. Подпрограмма может изменить их.
    • $v0 - $v1 - эти регистры содержат значения, возвращаемые из подпрограммы.

Согласно этой конвенции вызывающая (под)программа может рассчитывать на то, что регистры $s0 - $s7 не изменятся за время работы подпрограммы, и их можно использовать для хранения «быстрых» данных, переживающих вызов подпрограмм, например, для счётчиков циклов и т. п. Значения t-регистров могут меняться подпрограммой, а значения v- и a-регистров непосредственно меняются (или не меняются). 

   1 # какие-то значения
   2         li    $a0 5
   3         li    $a1 6
   4         li    $a2 7
   5 # вызов подпрограммы
   6         jal    treug
   7 # запомним результат, а то мало ли что
   8         move    $s1 $v0
   9 # какой-то ещё код
  10 #    …
  11 # Выход из основной программы
  12         li     $v0 10
  13         syscall
  14     …
  15 # Возможно, другие подпрограммы
  16     …
  17 # Подпрограмма
  18 treug:  move   $v0 $zero
  19         add    $t4 $a0 $a1
  20         add    $t5 $a1 $a2
  21         add    $t6 $a2 $a0
  22         bgt    $a2 $t4 not
  23         bgt    $a0 $t5 not
  24         bgt    $a1 $t6 not
  25         li     $v0 1
  26 not:    jr     $ra

Вопрос: какие регистры не стоит инициализировать до вызова подпрограммы в надежде, что после вызова они сохранятся?

Стек

Абстракция «стек»

Реализация стека в машинных кодах

Возможная аппаратная поддержка стека

Реализация стека в MIPS

…регулируется соотв. конвенцией:

Хранение данных в стеке

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

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

Неправильное решение: выделить для каждой функции ячейку, в которую сохранять $ra

Рекурсивный вызов — сохранение в стеке

Динамически выделять память удобнее всего на стеке. В начале подпрограммы все регистры, значения которых согласно конвенции следует сохранить до выхода из подпрограммы, а также регистр возврата $ra записываются в стек операцией push. Перед выходом эти значения снимаются со стека (в обратном порядке) операцией pop. Эти значения, как правило, не используются внутри подпрограммы, важна только последовательность сохранения и восстановления.

В самом простом случае сохранять надо только $ra: 

   1 .text
   2         …код программы
   3         jal     subr1
   4         …код программы
   5 
   6 subr1:  addiu   $sp $sp -4      # сохраним текущий $ra
   7         sw      $ra ($sp)       # на стеке
   8 
   9         …код подпрограммы 1
  10         jal     subr2           # вызов изменяет значение $ra
  11         …код подпрограммы 1
  12         jr      $ra
  13 
  14         lw      $ra ($sp)       # восстановим текущий $ra
  15         addiu   $sp $sp 4       # из стека
  16 
  17 subr2:  addiu   $sp $sp -4      # сохраним $ra
  18         sw      $ra ($sp)       # на стеке
  19 
  20         …код подпрограммы 2
  21 
  22         lw      $ra ($sp)       # восстановим $ra
  23         addiu   $sp $sp 4       # из стека
  24 
  25         jr      $ra

Строго говоря, подпрограмма subr2 — концевая, и в ней не обязательно сохранять и восстанавливать регистры. Но с точки зрения дисциплины программирования удобнее все подпрограммы оформлять одинаково. Возможно, в процессе работы над subr2 из неё понадобится вызвать ещё подпрограмму, и она перестанет быть концевой. По всей видимости, надо исключить любые попытки подпрограмм сохранять какие-то данные не на стеке, т. к. в случае рекурсивного вызова не только $ra и сохраняемые регистры Рассмотрим пример подпрограммы, вычисляющей функцию факториала. Вопреки здравому смыслу напишем эту подпрограмму рекурсивно: f(n)! = f(n-1)*n . Возникает одно значение — n — которое должно «переживать» рекурсивный вызов. Воспользуемся конвенцией, гарантирующей нам неизменность регистров $s* , и запишем n в регистр $s0. Тогда для выполнения условий конвенции текущее значение этого регистра надо сохранять в стеке в начале подпрограммы, и восстанавливать перед возвратом из неё. 

   1 .data
   2 n:      .word 7
   3 res:    .word 0
   4 # … ещё данные
   5 
   6 .text
   7 # … какой-то код
   8 # вызов fact:
   9         lw      $a0 n
  10         jal     fact
  11         sw      $v0 res
  12 # …ещё какой-то код
  13 
  14 fact:   addiu   $sp $sp -4      # спасём $ra
  15         sw      $ra ($sp)
  16         addiu   $sp $sp -4      # спасём $s0
  17         sw      $s0 ($sp)
  18 
  19         move    $s0 $a0         # Сформируем n-1
  20         subi    $a0 $a0, 1
  21         ble     $a0 1 done      # Если n<2, готово
  22 
  23         jal     fact            # Посчитаем fact(n-1)
  24         mul     $s0 $s0 $v0     # $s0 пережил вызов
  25 
  26 done:   move    $v0, $s0        # возвращаемое значение
  27         lw      $s0 ($sp)       # вспомним $s0
  28         addiu   $sp $sp 4
  29         lw      $ra ($sp)       # вспомним $ra
  30         addiu   $sp $sp 4
  31         jr      $ra

Здесь мы формально воспользовались конвенцией о сохранении регистров. Сохранив регистр $s0, мы обеспечили себе право использовать его как динамическую переменную. Пролог и эпилог — начальная и завершающая части подпрограммы, которые обслуживают соблюдение конвенции, а к решаемой задаче имеют только косвенное отношение. Так, пролог в примере сохраняет а стеке два регистра, а использовалось бы их больше — сохранял бы больше; эпилог эти два регистра ($s0 и $ra) восстанавливает. В примере пролог и эпилог помечены зелёным. Загрузка возвращаемого значения традиционно считается частью эпилога, т. к. её нельзя пропускать :). Очень похожий код получился бы без использования сохраняемого регистра. Значение из $t0 мы сами сохраним на стек перед вызовом подпрограммы, а после — обратимся к нему, сняв со стека. 

   1 fact:   addiu   $sp $sp -4      # спасём $ra
   2         sw      $ra ($sp)
   3 
   4         move    $t0 $a0
   5         subi    $a0 $a0, 1
   6         ble     $a0 1 done
   7 
   8         addiu   $sp $sp -4      # Спасём N
   9         sw      $t0 ($sp)
  10         jal     fact
  11         lw      $t1 ($sp)       # Восстановим N
  12         addiu   $sp $sp 4
  13         mul     $t0 $t1 $v0
  14 
  15 done:   move    $v0, $t0        # возвращаемое значение
  16         lw      $ra ($sp)       # вспомним $ra
  17         addiu   $sp $sp 4
  18         jr      $ra

Пролог и эпилог в примере уменьшились за счёт подготовки к (каждому!) вызову подпрограммы, называемой преамбулой. Кроме того, после возврата из подпрограммы, возможно, потребуется освободить стек. Преамбула и восстановление стека в примере помечены красным. Итак, локальная переменная лежит на вершине стека, откуда мы после вызова снимаем её. В принципе, можно было там и оставить, если регистров не хватает, а изменять вершину стека только перед возвратом из подпрограммы (точнее, перед тем, как восстанавливать из стека все сохранённые значения — $s*, $ra, …).

Конвенция для подпрограмм, обеспечивающих сохранение

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

  1. Передаваемые подпрограмме значения надо заносить в регистры $a

  2. Вызов подпрограммы должен производиться командой jal или jalr

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

  4. Подпрограмма обязана сохранить на стеке значение $ra

  5. Подпрограмма обязана сохранить на стеке все используемые ею регистры $s

  6. Подпрограмма может хранить на стеке произвольное количество переменных. Количество этих переменных и занимаемого ими места на стеке не оговаривается и может меняться в процессе работы подпрограммы.

  7. Возвращаемое подпрограммой значение надо заносить в регистры $v

  8. Подпрограмма должна освободить все занятые локальными переменными ячейки стека

  9. Подпрограмма обязана восстановить из стека сохранённые значения $s и $ra

  10. Подпрограмма обязана при возвращении восстановить значение $sp в исходное. Это случится автомагически при соблюдении всех предыдущих требований конвенции

  11. Возврат из подпрограммы должен производиться командой jr $ra

Некоторые требования конвенции выглядят неоправданно строгими, например, чёткое предписание, где хранить переменные и регистры. Однако такая строгость резко упрощает повторное использование и отладку программ: даже не читая исходный текст программист точно знает, где искать адрес возврата, сохранённые регистры и локальные переменные. Конвенции с хранением данных на стеке крайне чувствительны к нарушению его цельности. Стоит «промахнутся» на ячейку (например, забыть про атомарность процедуры снятия со стека и не увеличить $sp), и инструкции эпилога рассуют все значения не по своим местам: адрес возврата останется на стеке, в регистр $ra попадёт что-то из сохраняемого регистра, сохраняемые регистры получат «чужое» содержимое и т. д. При попытке выполнить переход на такой $ra в лучшем случае возникнет исключение перехода в запрещённую память (хорошо, что малые числа соответствуют зарезервированным адресам и переход на адреса в секции данных запрещён). В худшем случае содержимое $ra случайно окажется из допустимого диапазона секции кода, произойдёт возврат по этому адресу и начнётся выполнение лежащего там кода. Отладка такой ситуации (называемой «stack smash», снос стека) — непростая задача для программиста.

Кадр стека и промышленные конвенции

не успеем за сегодня

Д/З

LecturesCMC/ArchitectureAssembler2019/04_SubroutinesAndConventions (последним исправлял пользователь FrBrGeorge 2019-05-17 15:18:17)