Различия между версиями 12 и 13
Версия 12 от 2019-03-18 01:18:47
Размер: 32280
Редактор: FrBrGeorge
Комментарий:
Версия 13 от 2019-03-18 01:19:33
Размер: 32280
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 357: Строка 357:
 * <<EJCMC(121, RecursiveGCD, Наибоьлший общий делитель)>>  * <<EJCMC(121, RecursiveGCD, Наибольший общий делитель)>>

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

Разбор Д/З

Базовая страница 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   $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
    • Вопрос: какие регистры не стоит инициализировать до вызова подпрограммы в надежде, что после вызова они сохранятся?

Стек

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

  • Хранилище «объектов»
  • Основные операции — положить на стек, снять со стека
  • Основной доступ — последовательный, к верхнему элементу стека
    • Иногда разрешается относительный доступ к 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:  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
  • Строго говоря, подпрограмма 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:   addiu   $sp $sp -4      # спасём $ra
            sw      $ra ($sp)
            addiu   $sp $sp -4      # спасём $s0
            sw      $s0 ($sp)
    
            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:   move    $v0, $s0        # возвращаемое значение
            lw      $s0 ($sp)       # вспомним $s0
            addiu   $sp $sp 4
            lw      $ra ($sp)       # вспомним $ra
            addiu   $sp $sp 4
            jr      $ra

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

    fact:   addiu   $sp $sp -4      # спасём $ra
            sw      $ra ($sp)
    
            move    $t0 $a0
            subi    $a0 $a0, 1
            ble     $a0 1 done
    
            addiu   $sp $sp -4      # Спасём N
            sw      $t0 ($sp)
            jal     fact
            lw      $t1 ($sp)       # Восстановим N
            addiu   $sp $sp 4
            mul     $t0 $t1 $v0
    
    done:   move    $v0, $t0        # возвращаемое значение
            lw      $ra ($sp)       # вспомним $ra
            addiu   $sp $sp 4
            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», снос стека) — непростая задача для программиста.

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

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

Д/З

  • TODO Задания на EJudge

  • 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
  • TODO ещё задача

TODO Задания

LecturesCMC/ArchitectureAssembler2019/04_SubroutinesAndConventions (последним исправлял пользователь FrBrGeorge 2019-05-17 15:18:17)