Differences between revisions 18 and 19
Revision 18 as of 2019-04-20 13:10:36
Size: 32337
Comment: прогармму
Revision 19 as of 2019-05-17 12:18:17
Size: 32715
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 44: Line 44:
{{{ {{{#!highlight nasm
Line 52: Line 52:
{{{ {{{#!highlight nasm
Line 57: Line 57:
{{{ {{{#!highlight nasm
Line 128: Line 128:
 Согласно этой конвенции вызывающая (под)программа может рассчитывать на то, что регистры $s0 - $s7 не изменятся за время работы подпрограммы, и их можно использовать для хранения «быстрых» данных, переживающих вызов подпрограмм, например, для счётчиков циклов и т. п. Значения t-регистров могут меняться подпрограммой, а значения v- и a-регистров непосредственно меняются (или не меняются). Согласно этой конвенции вызывающая (под)программа может рассчитывать на то, что регистры $s0 - $s7 не изменятся за время работы подпрограммы, и их можно использовать для хранения «быстрых» данных, переживающих вызов подпрограмм, например, для счётчиков циклов и т. п. Значения t-регистров могут меняться подпрограммой, а значения v- и a-регистров непосредственно меняются (или не меняются).
Line 130: Line 130:
 {{{ {{{#!highlight nasm
Line 158: Line 158:
  . '''Вопрос: '''какие регистры не стоит инициализировать до вызова подпрограммы в надежде, что после вызова они сохранятся? '''Вопрос: '''какие регистры не стоит инициализировать до вызова подпрограммы в надежде, что после вызова они сохранятся?
Line 190: Line 190:
 . …регулируется соотв. конвенцией:
  * выделенный регистр $sp ($r29)
…регулируется соотв. конвенцией:
 * выделенный регистр $sp ($r29)
Line 201: Line 201:
 {{{
li    $t1,  123 # какое-то значение
addi  $sp, $sp, -4 # положить на стек - 1
sw    $t1,  ($sp) # положить на стек - 2
addi  $t2,  $t1,  100 # какое-то ещё значение
addi  $sp, $sp, -4 # положить на стек - 1
sw    $t2,  ($sp) # положить на стек - 2
lw    $t3,  ($sp) # доступ к вершине стека
lw    $t4,  4($sp) # доступ ко второму элементу стека
lw   $t0,  ($sp) # снятие со стека - 1
addi  $sp, $sp, 4 # снятие со стека - 2
addi  $sp, $sp, -4 # положить на стек - 1
sw    $zero, ($sp) # положить на стек - 2
 {{{#!highlight nasm
li
$t1,            123 # какое-то значение
addi            $sp, $sp, -4 # положить на стек - 1
sw              $t1,            ($sp) # положить на стек - 2
addi            $t2,            $t1,    100 # какое-то ещё значение
addi            $sp, $sp, -4 # положить на стек - 1
sw              $t2,            ($sp) # положить на стек - 2
lw              $t3,            ($sp) # доступ к вершине стека
lw              $t4,            4($sp) # доступ ко второму элементу стека
lw             $t0,            ($sp) # снятие со стека - 1
addi            $sp, $sp, 4 # снятие со стека - 2
addi            $sp, $sp, -4 # положить на стек - 1
sw              $zero,          ($sp) # положить на стек - 2
Line 216: Line 216:
 {{{  {{{#!highlight nasm
Line 253: Line 253:
{{{ {{{#!highlight nasm
Line 280: Line 280:
 Строго говоря, подпрограмма '''subr2''' — концевая, и в ней не обязательно сохранять и восстанавливать регистры. Но с точки зрения дисциплины программирования удобнее ''все'' подпрограммы оформлять одинаково. Возможно, в процессе работы над '''subr2''' из неё понадобится вызвать ещё подпрограмму, и она перестанет быть концевой. По всей видимости, надо исключить ''любые'' попытки подпрограмм сохранять какие-то данные не на стеке, т. к. в случае рекурсивного вызова не только '''$ra''' и сохраняемые регистры Рассмотрим пример подпрограммы, вычисляющей функцию факториала. Вопреки здравому смыслу напишем эту подпрограмму рекурсивно: f(n)! = f(n-1)*n . Возникает одно значение — n — которое должно «переживать» рекурсивный вызов. Воспользуемся конвенцией, гарантирующей нам неизменность регистров '''$s*''' , и запишем n в регистр '''$s0'''. Тогда для выполнения условий конвенции текущее значение этого регистра надо сохранять в стеке в начале подпрограммы, и восстанавливать перед возвратом из неё.
 {{{
Строго говоря, подпрограмма '''subr2''' — концевая, и в ней не обязательно сохранять и восстанавливать регистры. Но с точки зрения дисциплины программирования удобнее ''все'' подпрограммы оформлять одинаково. Возможно, в процессе работы над '''subr2''' из неё понадобится вызвать ещё подпрограмму, и она перестанет быть концевой. По всей видимости, надо исключить ''любые'' попытки подпрограмм сохранять какие-то данные не на стеке, т. к. в случае рекурсивного вызова не только '''$ra''' и сохраняемые регистры Рассмотрим пример подпрограммы, вычисляющей функцию факториала. Вопреки здравому смыслу напишем эту подпрограмму рекурсивно: f(n)! = f(n-1)*n . Возникает одно значение — n — которое должно «переживать» рекурсивный вызов. Воспользуемся конвенцией, гарантирующей нам неизменность регистров '''$s*''' , и запишем n в регистр '''$s0'''. Тогда для выполнения условий конвенции текущее значение этого регистра надо сохранять в стеке в начале подпрограммы, и восстанавливать перед возвратом из неё.
{{{#!highlight nasm
Line 314: Line 314:
 Здесь мы формально воспользовались конвенцией о сохранении регистров. Сохранив регистр '''$s0''', мы обеспечили себе право использовать его как динамическую переменную. '''Пролог '''и '''эпилог''' — начальная и завершающая части подпрограммы, которые обслуживают соблюдение конвенции, а к решаемой задаче имеют только косвенное отношение. Так, пролог в примере сохраняет а стеке два регистра, а использовалось бы их больше — сохранял бы больше; эпилог эти два регистра ($s0 и $ra) восстанавливает. В примере пролог и эпилог помечены зелёным. Загрузка возвращаемого значения традиционно считается частью эпилога, т. к. её нельзя пропускать :). Очень похожий код получился бы ''без'' использования сохраняемого регистра. Значение из '''$t0''' мы сами сохраним на стек перед вызовом подпрограммы, а после — обратимся к нему, сняв со стека.
 {{{
Здесь мы формально воспользовались конвенцией о сохранении регистров. Сохранив регистр '''$s0''', мы обеспечили себе право использовать его как динамическую переменную. '''Пролог '''и '''эпилог''' — начальная и завершающая части подпрограммы, которые обслуживают соблюдение конвенции, а к решаемой задаче имеют только косвенное отношение. Так, пролог в примере сохраняет а стеке два регистра, а использовалось бы их больше — сохранял бы больше; эпилог эти два регистра ($s0 и $ra) восстанавливает. В примере пролог и эпилог помечены зелёным. Загрузка возвращаемого значения традиционно считается частью эпилога, т. к. её нельзя пропускать :). Очень похожий код получился бы ''без'' использования сохраняемого регистра. Значение из '''$t0''' мы сами сохраним на стек перед вызовом подпрограммы, а после — обратимся к нему, сняв со стека.
{{{#!highlight nasm
Line 335: Line 335:
 Пролог и эпилог в примере уменьшились за счёт подготовки к (каждому!) вызову подпрограммы, называемой '''преамбулой. '''Кроме того, после возврата из подпрограммы, возможно, потребуется освободить стек. Преамбула и восстановление стека в примере помечены красным'''''.''''' Итак, локальная переменная лежит на вершине стека, откуда мы после вызова снимаем её. В принципе, можно было там и оставить, если регистров не хватает, а изменять вершину стека только перед возвратом из подпрограммы (точнее, перед тем, как восстанавливать из стека все сохранённые значения — $s*, $ra, …). Пролог и эпилог в примере уменьшились за счёт подготовки к (каждому!) вызову подпрограммы, называемой '''преамбулой. '''Кроме того, после возврата из подпрограммы, возможно, потребуется освободить стек. Преамбула и восстановление стека в примере помечены красным'''''.''''' Итак, локальная переменная лежит на вершине стека, откуда мы после вызова снимаем её. В принципе, можно было там и оставить, если регистров не хватает, а изменять вершину стека только перед возвратом из подпрограммы (точнее, перед тем, как восстанавливать из стека все сохранённые значения — $s*, $ra, …).

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

Разбор Д/З

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

Копипаста:

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

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

  • Разбиение задачи на подзадачи, часть из которых имеют готовые решения
    • вывод текстового сообщения и числа,
    • сортировка массива,
    • вычисление функции
  • Параметризация этих решений (количество и значение исходных данных)

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

  • ⇒ Конвенции об использовании/неиспользовании ресурсов ЭВМ
    • Значения регистров (в т. ч. счётчика инструкций и т. п.) и состояние памяти до и после выполнения соотв. кода
    • Способ передачи параметров
    • Способ получения результатов работы

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

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

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

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

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

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

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

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

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

Возврат из подпрограммы — команда перехода на адрес, находящийся в регистре $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-регистров непосредственно меняются (или не меняются).

  • Считается хорошим тоном без строгой необходимости не пользоваться v- и a- (а также и k-) регистрами не по назначению. Разумеется, между вызовами подпрограмм пользоваться t-регистрами можно (чем же ещё?). Конвенция не ограничивает модификацию оперативной памяти (т. н. «побочный эффект» подпрограммы) Пример той же подпрограммы (неравенство треугольника), оформленной в соответствие с конвенцией

   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

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

Стек

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

  • Хранилище «объектов»
  • Основные операции — положить на стек, снять со стека
  • Основной доступ — последовательный, к верхнему элементу стека
    • Иногда разрешается относительный доступ к N-му элементу стека от вершины
  • ⇒ «Первым вошёл — последним вышел»
  • Может расти бесконечно
  • Поведение при исчерпании (снятии с пустого стека) не определено

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

  • «Объект» — обычно ячейка
  • в некоторых архитектурах можно было бы хранить объекты разной длины (байты, полуслова, слова и т. п.), но задача доступа к N-му элементу стека из константной становится линейной сложности, и надо хранить где-то размеры ячеек
  • Хранилище — область памяти, ограниченная только с одной стороны («дно» стека), а с другой — «бесконечно» растущая (пока не достигнет занятой области памяти)
  • Рост/снятие: специальная ячейка памяти, хранящая адрес вершины стека + знание адреса дна сетка
    • Используется косвенная адресация
    • ⇒ Удобно (на некоторых архитектурах — единственно возможно) хранить в регистре
    • Переполнение надо как-то проверять
    • Исчерпание тоже надо как-то проверять

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

  • Отдельный небольшой стек на регистровой памяти (а чем лучше того же числа регистров?)
  • Атомарные операции добавления/снятия (в обычном случае действия два: чтение/запись значения и изменение указателя)
    • например, автоувеличение/автоуменьшение указателя прямо в процессе взятия значения
  • Двойная косвенная адресация позволяет напрямую обращаться к данным, адреса которых лежат в стеке (в случае MIPS — тяжёлое двойное обращение к памяти)

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

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

  • выделенный регистр $sp ($r29)
  • дно стека — 0x7ffffffc (непосредственно под областью ядра)
  • начальное значение 0x7fffeffc отделено от дна буфером
  • стек растёт вниз по одному слову (4 байта)

  • Предел стека — область кучи (0x10040000 или выше, если куча наросла), определяется вручную
  • Операции добавления и снятия — неатомарные:
    • при добавлении сначала уменьшается указатель, затем записывается значение
    • при снятии сначала считывается значение, затем увеличивается указатель
    • при такой организации не используется исходная ячейка стека — 7fffeffc
  • пример:

       1 li              $t1,            123          # какое-то значение
       2 addi            $sp,            $sp,    -4   # положить на стек - 1
       3 sw              $t1,            ($sp)        # положить на стек - 2
       4 addi            $t2,            $t1,    100  # какое-то ещё значение
       5 addi            $sp,            $sp,    -4   # положить на стек - 1
       6 sw              $t2,            ($sp)        # положить на стек - 2
       7 lw              $t3,            ($sp)        # доступ к вершине стека
       8 lw              $t4,            4($sp)       # доступ ко второму элементу стека
       9 lw              $t0,            ($sp)        # снятие со стека - 1
      10 addi            $sp,            $sp,    4    # снятие со стека - 2
      11 addi            $sp,            $sp,    -4   # положить на стек - 1
      12 sw              $zero,          ($sp)        # положить на стек - 2
    
  • Это довольно эффективный код, не содержащий ни одной составной псевдоинструкции:
       1 00400000: 2409007b  addiu $9,$0,0x0000007b  li  $t1, 123
       2 00400004: 23bdfffc  addi $29,$29,0xfffffffc addi $sp, $sp, -4
       3 00400008: afa90000  sw $9,0x00000000($29)   sw  $t1, ($sp)
       4 0040000c: 212a0064  addi $10,$9,0x00000064  addi $t2, $t1, 100
       5 00400010: 23bdfffc  addi $29,$29,0xfffffffc addi $sp, $sp, -4
       6 00400014: afaa0000  sw $10,0x00000000($29)  sw  $t2, ($sp)
       7 00400018: 8fab0000  lw $11,0x00000000($29)  lw  $t3, ($sp)
       8 0040001c: 8fac0004  lw $12,0x00000004($29)  lw  $t4, 4($sp)
       9 00400020: 8fa80000  lw $8,0x00000000($29)   lw  $t0, ($sp)
      10 00400024: 23bd0004  addi $29,$29,0x00000004 addi $sp, $sp, 4
      11 00400028: 23bd0004  addi $29,$29,0xfffffffc addi $sp, $sp, -4
      12 0040002c: afa00000  sw $0,0x00000000($29)   sw  $zero, ($sp)
    
  • Операция доступа к N-му элементу стека полностью аналогична доступу к вершине стека (просто смещение не нулевое, а +N*4)
    • Наверное, поэтому стек растёт вниз — смещения проще читать
    • Если использовать другую конвенцию (поменять местами чтение/запись и сдвиг указателя), затруднится адресная арифметика: указатель будет отмечать неиспользованную ячейку, а вершина окажется по адресу 4($sp)

  • Память, которую некоторое время занимал стек, а затем указатель ушёл выше, продолжает хранить значения, которые там лежали. Однако надеяться на то, что они там пребудут впредь, нельзя: память считается «свободной» и её, как минимум, меняют последующие добавления в стек.

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

  • Несколько более эффективно, чем в произвольном месте памяти (lw/sw не превращаются в псевдоинструкции)
  • Использует адресацию относительно постоянно меняющегося $sp, как следствие, требует аккуратного просчёта текущей глубины стека
  • Не требует явного указания адреса и заведения метки в программе на языке ассемблера
  • Может привести к сбоям в работе при переполнении/исчерпании стека

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

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

  • +надо сохранять $ra (при повторном вызове он изменится)

Неправильное решение: выделить для каждой функции ячейку, в которую сохранять $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», снос стека) — непростая задача для программиста.

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

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

Д/З

  • EJudge: RecursiveGCD 'Наибольший общий делитель'

    Написать полную программу, которая вводит два натуральных числа и выводит их наибольший общий делитель. Для вычисления НОД написать рекурсивную функцию, которая принимает два числа в $a0 и $a1 и возвращает значение в $v0.

    Input:

    2467080
    49360080
    Output:

    9240
  • EJudge: LeftDigits 'Левые цифры'

    Написать программу, которая вводит натуральное число N, а затем — N (возможно, отрицательных) целых чисел, после чего выводит (в строку) N самых левых цифр этих чисел. Для вычисления одной цифры написать функцию, которая в $a0 получает число, а в $v0 возвращает цифру.

    Input:

    5                             
    -2345
    7345623
    -4321
    2 
    7543
    Output:

    27427
  • EJudge: FuncSort 'Просто сортировка'

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

    Input:

    5
    -123
    34
    546
    0
    -100500
    Output:

    -100500 -123 0 34 546 

LecturesCMC/ArchitectureAssembler2019/04_SubroutinesAndConventions (last edited 2019-05-17 12:18:17 by FrBrGeorge)