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

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

• Разбиение задачи на подзадачи, часть из которых имеют готовые решения
  • вывод текстового сообщения и числа,
  • сортировка массива,
  • вычисление функции
  • …

• Параметризация этих решений (количество и значение исходных данных)
  

  • текст и число
  • размер и адрес массива (возможно, и критерий сортировки)
  • параметры функции
  • …

• Возможность использования исходного кода без его изучения

• ⇒ Конвенции об использовании/неиспользовании ресурсов ЭВМ
  • Значения регистров (в т. ч. счётчика инструкций и т. п.) и состояние памяти до и после выполнения соотв. кода
  • Способ передачи параметров
  • Способ получения результатов работы

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

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

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

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

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

• переход на этот участок кода (вызов подпрограммы) возможен из произвольных мест кода

• после выполнения подпрограммы происходит переход «обратно» в место вызова (выход из подпрограммы)

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

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

   1         jal адрес

• Адрес следующей ячейки записывается в регистр ra (x1)

• Происходит переход на адрес

Возврат из подпрограммы — команда перехода на адрес, находящийся в регистре 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: никакой дополнительной нагрузки не имеет, это просто метка.

А что произошло бы после выполнения 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, и jalr можно применять в позиционно-независимом коде (см. прошлую лекцию). В jal формируется смещение относительно адреса текущей инструкции. В jalr в регистре формируется полный (абсолютный) адрес перехода с помощью уже известного нам auipc, но в самом коде абсолютного адреса не содержится: задействован опять-таки адрес текущей инструкции и корректирующее сложение.

• Во всех командах пропущен регистр, в котором по умолчанию ожидается адрес перехода

  • вместо ra можно, формально говоря, использовать любой регистр

  • однако конвенция устроена так, что оптимизация процессора (например, добавление аппаратного хранилища возвратов из подпрограмм) рассчитывает на использование именно ra в качестве регистра адреса

• Полный формат команды jalr (как и полагается S/B):

  • jalr регистр_адреса_возврата регистр адреса_перехода смещение Смещение позволяет, например, вызывать несколько подпрограмм (или несколько разных точек входа в подпрограмму) без изменения адреса перехода

• Разложение псевдоинструкции call использует регистр x6 (t1) для формирования адреса, но явно он нигде не упомянут. В разговоре о конвенциях о вызове подпрограмм мы обсудим, почему это не так уж страшно

• Разложение псевдоинструкции call (auipc + jalr со смещением) оказалось эффективнее «наиболее логичного» варианта la + jalr ( почему?)

• Разложение псевдоинструкции ret — это… jalr! Как это работает:

  • В качестве регистра перехода используется ra

  • В качестве регистра возврата используется zero (это позволяет разработчику оптимизированного процессора сразу определять, что перед нами инструкция не перехода, а именно возврата из подпрограммы)

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

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

• Подпрограмма input работает вполне стандартно — возвращает а a0 введённое число (отличается от соответствующего системного вызова предварительным выводом подсказки).

• Подпрограмма check — нестандартная:

  • Использует регистры s* для передачи параметров (это противоречит части конвенции, но не нарушает «неизменности» регистров s*)

  • Использует трюк со смещённым адресом возврата:
    • В случае отрицательного ответа происходит обычный возврат из подпрограммы

    • В случае положительного ответа в регистр a0 записывается адрес строки «"Is a triangle\n"» и происходит возврат по адресу на две инструкции дальше стандартного адреса возврата (смещение 8).

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

   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, a1 и a2 — это передаваемые параметры, a0 — возвращаемое значение, регистры s* не изменяются, возврат по ret с использованием ra.

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

Нам необходимо проверить неравенство. Следовательно, подпрограмма должна возвращать (согласно конвенции — в 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