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

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

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

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

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

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

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

Базовая статья спецификации: Полные конвенции по вызову

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

   1         jal адрес

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

   1         ret

Вместо команды типа U — jal — можно использовать команду типа S — jalr в которой адрес хранится в регистре (см. прошлую лекцию относительно того, почему команды перехода выделяют в отдельные типы команд — J и B соответственно). Рассмотрим пример, в котором подпрограмма сначала вызывается с помощью jal, а затем — с помощью jalr: 

   1 .data
   2 ping:   .asciz  "Ping\n"
   3 .text
   4         jal     subr
   5         la      s1 subr
   6         jalr    s1
   7         li      a7 10
   8         ecall
   9 subr:   la      a0 ping
  10         li      a7 4
  11         ecall
  12         ret

В коде: 

Address     Code        Basic                        Line Source

0x00400000  0x018000ef  jal x1,0x00000018            4          jal     subr
0x00400004  0x00000497  auipc x9,0                   5          la      s1 subr
0x00400008  0x01448493  addi x9,x9,20
0x0040000c  0x000480e7  jalr x1,x9,0                 6          jalr    s1
0x00400010  0x00a00893  addi x17,x0,10               7          li      a7 10
0x00400014  0x00000073  ecall                        8          ecall
0x00400018  0x0fc10517  auipc x10,0x0000fc10         9    subr: la      a0 ping
0x0040001c  0xfe850513  addi x10,x10,0xffffffe8
0x00400020  0x00400893  addi x17,x0,4                10         li      a7 4
0x00400024  0x00000073  ecall                        11         ecall
0x00400028  0x00008067  jalr x0,x1,0                 12         ret

Смещение ret можно использовать для более высокоуровневых трюков. Пример: подпрограмма, которая проверяет, что регистры s1, s2 и s3 содержат значения, удовлетворяющие неравенству треугольника. 

   1 .data
   2 yes:    .asciz  "Is a triangle\n"
   3 no:     .asciz  "Not a triangle\n"
   4 .text
   5         jal     input
   6         mv      s1 a0
   7         jal     input
   8         mv      s2 a0
   9         jal     input
  10         mv      s3 a0
  11         jal     check           # проверка неравенства треугольника
  12         la      a0 no           # запись адреса no в регистр a0 (занимает две инструкции)
  13         li      a7 4            # вывод строки в a0 (сюда происходит возврат в случае успеха)
  14         ecall
  15         li      a7 10
  16         ecall
  17 .data
  18 prompt: .ascii  "Enter triangle side: "
  19 .text
  20 input:  la      a0 prompt
  21         li      a7 4
  22         ecall
  23         li      a7 5
  24         ecall
  25         ret
  26 check:  add     t3 s1 s2
  27         add     t1 s2 s3
  28         add     t2 s1 s3
  29         ble     t1 s1 notri
  30         ble     t2 s2 notri
  31         ble     t3 s3 notri
  32         la      a0 yes
  33         jalr    zero ra 8
  34 notri:  ret

К сожалению, даже такой немудрёный трюк слишком сложен для программирования на языке Ассемблера (хотя, возможно, полезен для компиляторов высокоуровневых языков, в которых, например, предусмотрено понятие «статус ошибки в подпрограмме»).

Необходимость конвенций для подпрограмм

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

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

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

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

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

  2. вложенного вызова

  3. в т. ч. рекурсивного вызова (это частный случай вложенного, но он накладывает дополнительные требования)

Обратите внимание на то, что в примере выше изменяются значения регистров t*, а значения регистров s* используются для передачи параметров и возврата значения.

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

  1. Прозрачность требует
    • отдельной конвенции (о протоколе передачи параметров и возвращаемых значений)
    • механизма сокрытия локальных меток

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

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

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

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

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

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

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

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

  1. Подпрограмма вызывается с помощью инструкций jal/jalr (которые сохраняют обратный адрес в регистре ra).

  2. Подпрограмма не будет вызывать другую подпрограмму

  3. Подпрограмма возвращает управление вызывающей программе с помощью инструкции ret (пример с «трюком» выше нарушает эту конвенцию).

  4. Регистры используются следующим образом:

    • t0 - t6: подпрограмма может изменить эти регистры.

    • s0 - s11: при выходе из подпрограммы эти регистры должны содержать те же данные, которые были в них при входе

      • можно либо вовсе не трогать их, либо сохранить их содержимое, а перед выходом — восстанавливать

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

    • a0 - a7: эти регистры содержат параметры для подпрограммы. Подпрограмма может изменить их.

    • a0, a1: эти регистры содержат значения, возвращаемые из подпрограммы:

    • The base integer calling convention provides eight argument registers, a0-a7, the first two of which are also used to return values

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

Разумеется, между вызовами подпрограмм можно пользоваться всеми регистрами (чем же ещё?). Конвенция не ограничивает модификацию оперативной памяти (т. н. «побочный эффект» подпрограммы).

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

Нам необходимо проверить неравенство. Следовательно, подпрограмма должна возвращать (согласно конвенции — в a0) один результат для треугольников, и другой — для нетреугольников. Конвенция нас ничем в этом плане не ограничивает, поэтому договоримся, что результат — это знаковый бит регистра a0. Это легко проверить, и легко вычислить из разностей вида «сторона-сумма_двух_других_сторон». Для ответа «не треугольник» достаточно, чтобы хотя бы одна из таких разностей была неотрицательной, т. е. имела 0 в знаковом бите. Соответственно, конъюнкция нам в помощь. 

   1 .data
   2 yes:    .asciz  "Is a triangle\n"
   3 no:     .asciz  "Not a triangle\n"
   4 .text
   5         jal     input
   6         mv      s1 a0
   7         jal     input
   8         mv      s2 a0
   9         jal     input
  10                                 # третья сторона уже в регистра a0
  11         mv      a1 s1           # первая сторона
  12         mv      a2 s2           # вторая сторона
  13         jal     check
  14         bltz    a0 true
  15         la      a0 no
  16         b       output
  17 true:   la      a0 yes
  18 output: li      a7 4
  19         ecall
  20         li      a7 10
  21         ecall
  22 .data
  23 prompt: .ascii  "Enter triangle side: "
  24 .text
  25 input:  la      a0 prompt
  26         li      a7 4
  27         ecall
  28         li      a7 5
  29         ecall
  30         ret
  31 check:  add     t0 a1 a2
  32         sub     t0 a0 t0
  33         add     t1 a2 a0
  34         sub     t1 a1 t1
  35         add     t2 a1 a0
  36         sub     t2 a2 t2
  37         and     a0 t0 t1
  38         and     a0 a0 t2
  39 done:   ret

Стек

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   1         li      a7 5
   2         ecall
   3         jal     fact            # Параметр уже в a0 )
   4         li      a7 1
   5         ecall                   # Параметр уже в a0 ))
   6         li      a7 10
   7         ecall
   8 
   9 fact:   addi    sp sp -8        ## Запасаем две ячейки в стеке
  10         sw      ra 4(sp)        ## Сохраняем ra
  11         sw      s1 (sp)         ## Сохраняем s1
  12 
  13         mv      s1 a0           # Запоминаем N в s1
  14         addi    a0 s1 -1        # Формируем n-1 в a0
  15         li      t0 1
  16         ble     a0 t0 done      # Если n<2, готово
  17         jal     fact            # посчитаем (n-1)!
  18         mul     s1 s1 a0        # s1 пережил вызов
  19 
  20 done:   mv      a0 s1           # Возвращаемое значение
  21         lw      s1 (sp)         ## Восстанавливаем sp
  22         lw      ra 4(sp)        ## Восстанавливаем ra
  23         addi    sp sp 8         ## Восстанавливаем вершину стека
  24         ret

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

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

Похожий код получился бы без использования сохраняемого регистра s*. Пролог и эпилог уменьшатся, но накапливающееся произведение всё равно надо запасать (на стеке, больше негде), и делать это придётся непосредственно перед вызовом подпрограммы, которая может испортить несохраняемые регистры. 

   1         li      a7 5
   2         ecall
   3         jal     fact            # Параметр уже в a0 )
   4         li      a7 1
   5         ecall                   # Параметр уже в a0 ))
   6         li      a7 10
   7         ecall
   8 
   9 fact:   addi    sp sp -4
  10         sw      ra (sp)         # Сохраняем ra
  11         mv      t1 a0           # Запоминаем N в t1
  12         addi    a0 t1 -1        # Формируем n-1 в a0
  13         li      t0 1
  14         ble     a0 t0 done      # Если n<2, готово
  15         addi    sp sp -4        ## Сохраняем t1 на стеке
  16         sw      t1 (sp)         ##
  17         jal     fact            # Посчитаем (n-1)!
  18         lw      t1 (sp)         ## Вспоминаем t1
  19         addi    sp sp 4         ##
  20         mul     t1 t1 a0        # Домножаем на (n-1)!
  21 done:   mv      a0 t1           # Возвращаемое значение
  22 
  23         lw      ra (sp)         # Восстанавливаем ra
  24         addi    sp sp 4         # Восстанавливаем вершину стека
  25         ret

Язык ассемблера и понятие «переменная»

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

Такое отношение к данным резко отличается от более высокоуровневого понятия «переменная», в котором предполагается, что представление объекта и способ работы с ним всегда одинаковы. Можно сказать, что в языке ассемблера нет переменных, а есть только метки, и это не одно и то же.

В тексте мы будем использовать понятие локальная переменная преимущественно для такого случая: 

   1 subr:   addi    sp sp -12       ## Выделяем три ячейки — под ra и две переменные
   2         sw      ra 8(sp)        ## Сохраняем ra
   3         sw      zero 4(sp)      ## Инициализируем первую переменную нулём
   4         sw      zero (sp)       ## Инициализируем вторую переменную нулём
   5         # …
   6         lw      t0 4(sp)        # Загружаем первую локальную переменную в t0
   7         # …
   8         sw      t1 (sp)         # Записываем t1 во вторую локальную переменную
   9         # …
  10         lw      ra 8(sp)        # Восстанавливаем ra
  11         addi    sp sp 12        # Освобождаем две ячейки стека
  12         ret

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Д/З

TODO

LecturesCMC/ArchitectureAssembler2022/03_StackSubroutines (последним исправлял пользователь FrBrGeorge 2022-02-21 19:33:55)