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

Разбор Д/З

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

Копипаста:

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

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

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

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

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

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

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

jal адрес

Возврат из подпрограммы — команда перехода на адрес, находящийся в регистре $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   $t0 $zero
        add    $t4 $t1 $t2
        add    $t5 $t2 $t3
        add    $t6 $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
    • Вопрос: какие регистры не стоит инициализировать до вызова подпрограммы в надежде, что после вызова они сохранятся?

Стек

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

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

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

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

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

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

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

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

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

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

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

.text
        …код программы
        jal     subr1
        …код программы

subr1:  addiu   $sp $sp -4      # сохраним текущий $ra
        sw      $ra ($sp)       # на стеке

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

        lw      $ra ($sp)       # восстановим текущий $ra
        addiu   $sp $sp 4       # из стека

subr2:  addiu   $sp $sp -4      # сохраним $ra
        sw      $ra ($sp)       # на стеке

        …код подпрограммы 2

        lw      $ra ($sp)       # восстановим $ra
        addiu   $sp $sp 4       # из стека

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

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

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

Д/З