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

Долги за прошлую лекцию:

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

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

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

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

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

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

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

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

   1         jal адрес

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

   1         ret

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

   1 .data
   2 ping:   .asciz  "Ping\n"
   3 .text
   4         jal     subr
   5         call    subr
   6         li      a7 10           # Останов
   7         ecall
   8 
   9 subr:   la      a0 ping
  10         li      a7 4
  11         ecall
  12         ret

<!> Внешний вызов 10 (останов) здесь обязателен. В самом деле, если бы его не было, после инструкции call subr выполнилась бы следующая инструкция — la a0 ping — затем следующая, и так весь код подпрограммы. Метка subr: никакой дополнительной нагрузки не имеет, это просто метка.

FrBrGeorge/MyDict/speech_balloon_question.png А что произошло бы после выполнения ret?

В коде: 

Address     Code        Basic                        Line Source
0x00400000  0x014000ef  jal x1,0x00000014            4            jal     subr
0x00400004  0x00000317  auipc x6,0                   5            call    subr
0x00400008  0x010300e7  jalr x1,x6,16                     
0x0040000c  0x00a00893  addi x17,x0,10               6            li      a7 10
0x00400010  0x00000073  ecall                        7            ecall
0x00400014  0x0fc10517  auipc x10,0x0000fc10         8    subr:   la      a0 ping
0x00400018  0xfec50513  addi x10,x10,0xffffffec           
0x0040001c  0x00400893  addi x17,x0,4                9            li      a7 4
0x00400020  0x00000073  ecall                        10           ecall
0x00400024  0x00008067  jalr x0,x1,0                 11           ret

Из примера видно, что в отсутствие атомарного jal каждый вызов подпрограммы занимал бы три инструкции: две на загрузку адреса возврата в регистр и одну на переход. Поскольку вызов подпрограммы — очень частая операция в программировании, такая тройная экономия времени за счёт усложнения системы команд весьма разумна.

Смещение 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

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

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

Инструкция jal помогла решить задачи:

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

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

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

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

  2. вложенного вызова (подпрограммы из подпрограммы)

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

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

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

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

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

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

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

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

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

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

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

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

  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-регистров непосредственно меняются (или не меняются).

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

<!> Разложение псевдоинструкции call неявно использует регистр t1. Содержимое этого регистра при вызове подпрограммы изменится, а сам регистр нигде в ассемблерном тексте тексте не упомянут! От неразберихи частично спасает конвенция относительно регистров t* — они не обязаны сохранять своё значение после возврата из подпрограммы. Несколько расстраивает, что t1 не сохраняет значения даже при вызове, но, с другой стороны, в конвенции сказано: регистры t* не используются и для передачи параметров в подпрограмму.

Пример, концевой подпрограммы, которой передаётся три целых числа, а возвращает они наибольшее из них 

        li      a0 5
        li      a1 6
        li      a2 7
        call max3
        li      a7 1
        ecall
        li      a7 10
        ecall

# максимум из трёх чисел
max3:   bgt     a0 a1 max31
        mv      a0 a1
max31:  bgt     a0 a2 max32
        mv      a0 a2
max32:  ret

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

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

   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         bnez    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         sltz    a0 a0
  40 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», снос стека) — непростая задача для программиста.

Д/З

LecturesCMC/ArchitectureAssembler2024/03_StackSubroutines (последним исправлял пользователь FrBrGeorge 2024-07-13 19:02:34)