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

Базовая страница 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, непосредственный переход на подпрограмму смысла не имеет. В частности, надо предпринять специальные меры, чтобы счётчик команд не дошагал до подпрограммы естественным путём (в примере используется специальный системный вызов «завершить прогармму»).

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

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

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

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

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

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

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

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

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

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

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-регистрами можно (чем же ещё?).

   Конвенция не ограничивает модификацию оперативной памяти (т. н. «побочный эффект» подпрограммы)

   Пример той же подпрограммы (неравенство треугольника), оформленной в соответствие с конвенцией

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

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

Стек

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

• Хранилище «объектов»

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

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

• «Объект» — обычно ячейка
• в некоторых архитектурах можно было бы хранить объекты разной длины (байты, полуслова, слова и т. п.), но задача доступа к N-му элементу стека из константной становится линейной сложности, и надо хранить где-то размеры ячеек

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

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

• Отдельный небольшой стек на регистровой памяти (а чем лучше того же числа регистров?)

• Атомарные операции добавления/снятия (в обычном случае действия два: чтение/запись значения и изменение указателя)
  • например, автоувеличение/автоуменьшение указателя прямо в процессе взятия значения

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

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

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

• стек растёт вниз по одному слову (4 байта)

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

• пример:
  

  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

• Это довольно эффективный код, не содержащий ни одной составной псевдоинструкции:

  00400000: 2409007b  addiu $9,$0,0x0000007b  li  $t1, 123
  00400004: 23bdfffc  addi $29,$29,0xfffffffc addi $sp, $sp, -4
  00400008: afa90000  sw $9,0x00000000($29)   sw  $t1, ($sp)
  0040000c: 212a0064  addi $10,$9,0x00000064  addi $t2, $t1, 100
  00400010: 23bdfffc  addi $29,$29,0xfffffffc addi $sp, $sp, -4
  00400014: afaa0000  sw $10,0x00000000($29)  sw  $t2, ($sp)
  00400018: 8fab0000  lw $11,0x00000000($29)  lw  $t3, ($sp)
  0040001c: 8fac0004  lw $12,0x00000004($29)  lw  $t4, 4($sp)
  00400020: 8fa80000  lw $8,0x00000000($29)   lw  $t0, ($sp)
  00400024: 23bd0004  addi $29,$29,0x00000004 addi $sp, $sp, 4
  00400028: 23bd0004  addi $29,$29,0xfffffffc addi $sp, $sp, -4
  0040002c: afa00000  sw $0,0x00000000($29)   sw  $zero, ($sp)

• Операция доступа к N-му элементу стека полностью аналогична доступу к вершине стека (просто смещение не нулевое, а +N*4)
  • Наверное, поэтому стек растёт вниз — смещения проще читать

  • Если использовать другую конвенцию (поменять местами чтение/запись и сдвиг указателя), затруднится адресная арифметика: указатель будет отмечать неиспользованную ячейку, а вершина окажется по адресу 4($sp)

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

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

• Несколько более эффективно, чем в произвольном месте памяти (lw/sw не превращаются в псевдоинструкции)

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

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

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

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

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

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

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

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

  .text
          …код программы
          jal     subr1
          …код программы
  
  subr1:
  
          …код подпрограммы 1
          jal     subr2           # вызов изменяет значение $ra
          …код подпрограммы 1
          jr      $ra
  
  subr2:  a
  
          …код подпрограммы 2
          jr      $ra

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

  По всей видимости, надо исключить любые попытки подпрограмм сохранять какие-то данные не на стеке, т. к. в случае рекурсивного вызова не только $ra и сохраняемые регистры

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

  .data
  n:      .word 7
  res:    .word 0
  # … ещё данные
  
  .text
  # … какой-то код
  # вызов fact:
          lw      $a0 n
          jal     fact
          sw      $v0 res
  # …ещё какой-то код
  
  fact:
  
          move    $s0 $a0         # Сформируем n-1
          subi    $a0 $a0, 1
          ble     $a0 1 done      # Если n<2, готово
  
          jal     fact            # Посчитаем fact(n-1)
          mul     $s0 $s0 $v0     # $s0 пережил вызов
  
  done:
          jr      $ra

  Здесь мы формально воспользовались конвенцией о сохранении регистров. Сохранив регистр $s0, мы обеспечили себе право использовать его как динамическую переменную.

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

  Очень похожий код получился бы без использования сохраняемого регистра. Значение из $t0 мы сами сохраним на стек перед вызовом подпрограммы, а после — обратимся к нему, сняв со стека.

  fact:
  
          move    $t0 $a0
          subi    $a0 $a0, 1
          ble     $a0 1 done
          jal     fact
          mul     $t0 $t1 $v0
  
  done:
          jr      $ra

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Некоторые требования конвенции выглядят неоправданно строгими, например, чёткое предписание, где хранить переменные и регистры. Однако такая строгость резко упрощает повторное использование и отладку программ: даже не читая исходный текст программист точно знает, где искать адрес возврата, сохранённые регистры и локальные переменные.

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

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

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

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

Д/З