Регистры и модель памяти

Копипаста базовой лекция на Moodle

Вступление: понятие о конвенциях

Регистры

• Только два регистра особенные — zero (r0, всегда равен 0) и ra (r31, автоматически заполняется некоторыми командами)

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

  • ⇒ возникает понятие конвенции (договорённости)

• Регистр at (r1) используется псевдоинструкциями (например, для адреса при косвенной адресации)

• Регистры a0 - a3 (r4 - r7) используются для передачи параметров подпрограммам

  • Очевидно, у подпрограмм может быть более 4 параметров, так что здесь тоже вступают в силу конвенции, и очень разнообразные

• Регистры v0, v1 (r2, r3) используются для возврата значений (почему два?)

• Регистры t0 - t9 (r8-r15, r24,r25) можно использовать без ограничений

• Регистры s0 - s8 (r16 - r23, r30) по договорённости необходимо восстанавливать в исходные значения перед выходом из подпрограммы. При этом даже если они не используются вне подпрограммы, код сохранения и восстановления обязан присутствовать.

• Регистры k0, k1 (r26, r27) используются для взаимодействия с ядром

• Регистр sp (r29) содержит ссылку на вершину стека (stack pointer)

• Регистр gp (r28) хранит адрес области глобальных данных (global pointer). Нужен, например, для хранения «глобальных переменных», доступных в том числе и из подпрограмм (конвенция!), или для передачи данных со стороны операционной системы

• Регистр s8 (r30) в некоторых конвенциях организации подпрограмм используется для хранения ссылки на область данных текущей подпрограммы, поэтому он носит ещё одно название — fp (frame pointer)

Ещё два регистра — HI и LO — используются в командах деления и умножения

Плоская модель памяти

• Резервированная память (до 0x400000) может быть использована операционной системой для различных нужд. Например, в MARS директивы .text и .data приводят к заполнению памяти непосредственно по указанным адресам. На самом деле чаще всего результат трансляции записывается в исполняемый файл, который имеет довольно сложный формат, а при необходимости загружается в память в соответствии со специальными таблицами размещения, динамической компоновкой и т. п. Некоторые из этих данных нужны для работы программы под управлением ОС, они-то и размещаются в младших адресах памяти. Чтение и запись в эту область запрещены.

• Text base — область для инструкций программы. Теоретически никто не мешает иметь несколько директив .text, размещающих код по различным адресам в пределах 0x400000 - 0x1000000. Обычно после загрузки программы, когда она начала работать, запись по адресам 0x400000 - 0xffffff запрещена.

• Extern — область для внешних данных (нужна для взаимодействия с ОС). Кроме того, метки в этой области оказываются «видны» при сборке программ из нескольких файлов.

• Data base — область, в которую обычно раскладываются данные директивами .data. Именно там лежат переменные, объявленные массивы и прочее. Традиционно имеется зазор между началом области данных (0x10000000) и непосредственно статическими данными (0x10010000 - 0x10040000). Обычно в процессе работы программы нельзя переходить по адресам из области данных и декодировать их как инструкции.

• Heap (Куча) — область данных, в которую принято помещать динамические данные. Идея в повторном использовании одних и тех же областей памяти для различных нужд. Для этого служат процедуры выделения памяти, в которых запоминается размер и адрес запрошенного фрагмента, и освобождения, в которых эти данные объявляются устаревшими (можно совсем забыть, а можно область пометить как свободную), после чего очередная процедура выделения вполне может выдать ту же самую область. Механизмы выделения/освобождения памяти (т. н. memory managment) обычно довольно непросты, и соответствующие функции предоставляет ОС. Добавление и освобождение данных в куче обычно происходит в сторону увеличения адреса.

• Stack — область динамических данных особого вида, реализующая абстракцию «стек» и используемая при вызове подпрограмм и передачи им параметров. Добавление и освобождение данных в стеке обычно происходит в сторону уменьшения адреса. Бесконтрольное снятие данных со стека может привести к тому, что регистр стека начнёт указывать за пределы пользовательской памяти, поэтому (и по каким-то ещё соображениям) изначально $sp указывает не на самое «дно» стека, а существенно ниже (под 0x7ffff000). Стек и куча растут навстречу друг другу, и могут занимать друг дружкину память, лишь бы не пересекались.

• KText и KData. Начиная с адреса 0x80000000 идёт область, недоступная программе пользователя. Это область кода и данных ядра. Безотносительно к тому, запущена программа под управлением ОС или «на голом железе», для исполнения кода и доступа к памяти требуется особый режим работы процессора. Чтение, запись и переход с использованием адресов ядра пользовательской программе запрещены.

• Среди прочего программного кода ядра выделяется адрес обработчика прерываний (0x80000180). По этому адресу передаётся управление при возникновении исключительной ситуации (наподобие переполнения или обращение к «не своей» памяти)
• Область MMIO служит для адресации ячеек, вообще не принадлежащих оперативной памяти. Обращение по этим адресам приведёт к взаимодействию с данными на внешних устройствах (обычно с регистрами ввода-вывода или собственной памятью устройств)

Задание: проверить, можно ли в MARS прочитать байт из раздела .text по нечётному адресу? (Почему ?)

Директивы размещения данных в памяти

В программе на языке ассемблера возникает необходимость описать содержимое сегмента памяти. Для этого код программы помечается .text, а данные — .data . При трансляции в MARS код размещается с адреса 0x400000 (если не сказано иное), а данные — с адреса 0x10010000 (опять-таки, если не сказано иное).

• В секции .data помещают директивы (указания ассемблеру) по размещению данных в памяти.

  • .word ­число — одно или несколько 4-байтовых чисел

• .half число — одно или несколько 2-байтовых чисел

• .byte число — одно или несколько однобайтовых чисел

• .ascii "строка" — последовательность символов в кодировке ASCII

• .asciiz "строка" — то же, только после последнего символа обязательно записывается нулевой байт (конец строки, договорённость, например, для языка Си) Пример размещения данных различного размера:

     1 .data
     2         .word   0xbad0feed
     3         .half   0x1234, 0x5678
     4         .byte   12, 13, 14, 15
     5         .half   0x3344
     6         .byte   0x66, 0x77
  

  Результат трансляции пословно (секция .data начинается по умолчанию с адреса 0x10010000). Обратим внимание на little endian: младший байт в слове имеет меньший адрес!

     1 10010000: bad0feed 56781234 0f0e0d0c 77663344
  

  Для того, чтобы обращаться к соответствующим ячейкам памяти, можно использовать и адреса. и метки. Метка — символическое имя, оно заменяет адрес в программе на языке ассемблера и транслируется в соответствующий адрес в машинных кодах.

     1 .data
     2         .word   0x12345
     3 var:    .word   0x6789A
     4         .word   0xBCDEF
     5 
     6 .text
     7         lw      $t1, 0x10010000
     8         lw      $t2, var
     9         lw      $t3, var+4
  

  Обратите внимание на то, что все псевдоинструкции раскрываются в одинаковые команды (разное только смещение):

     1  Address    Code        Basic               Source
     2 
     3 00400000: 3c011001  lui $1,0x00001001       lw  $t1, 0x10010000
     4 00400004: 8c290000  lw $9,0x00000000($1)
     5 00400008: 3c011001  lui $1,0x00001001       lw  $t2, var
     6 0040000c: 8c2a0004  lw $10,0x00000004($1)
     7 00400010: 3c011001  lui $1,0x00001001       lw  $t3, var+4
     8 00400014: 8c2b0008  lw $11,0x00000008($1)
  

  Загружать во временный регистр $at (он же $1) адреса начала секции данных, а прибавлять смещение относительно её начала — типичное поведение ассемблера MIPS. получается чуть более читаемый машинный код, а такой «круглый» адрес, как 0x10010000 (с нулевым младшим полусловом) можно загружать одной командой загрузки старшего полуслова lui. Начиная со значения, указанного в директиве .data (или с адреса по умолчанию), ассемблер высчитывает адрес, который будет соответствовать метке, каждый раз прибавляя размер очередной отведённой ячейки. Обращение к ячейке памяти размером N байтов в архитектуре MIPS возможно только при условии, что адрес этой ячейки кратен N (следствие little endian). Поэтому при размещении ассемблером ячеек разного размера происходит выравнивание: если очередная ячейка имеет размер, которому не кратен текущий предполагаемый адрес её размещения, к этому адресу дополнительно прибавляется от одного до трёх байтов, чтобы обеспечить кратность. Пример разнообразных данных в памяти с автоматическим и ручным выравниванием.

     1 .data
     2         .word   0x76543210
     3         .half   0x2468
     4         .word   0x76543210
     5         .byte   1
     6         .word   0x76543210
     7         .byte   3
     8         .half   0x2468, 0x0ac4
     9         .byte   5, 7, 9
    10         .align  2
    11         .byte   1, 3, 5
    12         .align  3
    13         .byte   7
    14         .align  1
    15         .byte   9
  

  Выравнивание можно вызвать директивно, с помощью .align номер (где номер 0,1,2 и 3 соответствует байту, полуслову, слову и двойному слову соответственно). Вот во что превращается пример выше. Цветом выделены байты, добавленные для выравнивания; не забываем про little endian: для выравнивания на границу двойного слова к адресу 0x10010023 пришлось добавить пять байтов!

  • 

     1 10010000: 76543210 00002468 76543210 00000001 76543210 24680003 07050ac4 00000009
     2 10010020: 00050301 00000000 00090007 00000000 00000000 00000000 00000000 00000000
  

  Директива .data автоматически заполняет область данных, начиная с 0x10010000, причём последующие директивы .data продолжают заполнение с последнего незанятого адреса. Однако можно указывать адрес размещения данных явно в виде параметра .data. Директивы .data можно перемежать с директивами .text, это никак не повлияет на размещение данных:

     1 .data
     2         .word 0x123456
     3         .word 1
     4 .text
     5         move    $t1, $zero
     6 .data
     7         .word 0x7890a
     8         .word 2
     9 
    10 .data   0x10010100
    11         .word 0x334455
  

  Память в результате:

     1 10010000: 00123456 00000001 0007890a 00000002 00000000 00000000 00000000 00000000
     2 10010020: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
     3 . . .
     4 100100e0: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
     5 10010100: 00334455 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  

Адресация в секции кода

Размер ячейки команды в MIPS всегда 4 байта, поэтому

• Попытка перехода на адрес,не кратный четырём, вызывает ошибку
• Непосредственный адрес, используемый в инструкциях I и J типов, хранится без двух последних битов, которые и так всегда равны 0. Можно условно считать, что адресация происходит «по номерам ячеек», это удобно для относительных переходов

• Адресация в командах «b» (branch) — относительная, адрес представляет собой смещение относительно счётчика команд, которое надо к нему прибавить для перехода. Переход назад — отрицательное число в дополнительном коде (напоминаем, используется младшие 16 битов ячейки). Это позволяет адресовать ±128 килобайтов кода, что вполне достаточно для повседневного программирования

• Адресация в командах «j» (jump) — абсолютная (используется младшие 26 битов ячейки). Этого достаточно для адресации четверти всей секции пользовательского кода Вопрос: а точно ли четверти? Проверьте! Пример (в меру бессмысленного) кода с различными переходами:

     1 .text
     2         li      $t0, 20
     3 start:  li      $t1, 5
     4         move    $t2, $t0
     5 loop:   beqz    $t2, fin
     6         subu    $t2, $t2, $t1
     7         b       loop
     8 fin:    sra     $t0, $t0, 1
     9         bnez    $t0, end
    10         j       start
    11 end:    nop
  

  Результат трансляции (li ассемблер, как обычно, заменил на сложение с нулём):

     1 00400000: 24080014  addiu $8,$0,0x00000014          li    $t0, 20
     2 00400004: 24090005  addiu $9,$0,0x00000005  start:  li    $t1, 5
     3 00400008: 00085021  addu $10,$0,$8                  move  $t2, $t0
     4 0040000c: 11400002  beq $10,$0,0x00000002   loop:   beqz  $t2, fin
     5 00400010: 01495023  subu $10,$10,$9                 subu  $t2, $t2, $t1
     6 00400014: 0401fffd  bgez $0,0xfffffffd              b     loop
     7 00400018: 00084043  sra $8,$8,0x00000001    fin:    sra   $t0, $t0, 1
     8 0040001c: 15000001  bne $8,$0,0x00000001            bnez  $t0, end
     9 00400020: 08100001  j 0x00400004                    j     start
    10 00400024: 00000000  nop                     end:    nop
  

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

К практике

• Умножение и деление. Умножение двух регистров с помощью инструкции mult приводит к заполнению произведением двойного слова, находящегося в специальных регистрах hi и lo (потому что произведение может не поместиться в одно слово). Достать оттуда значение можно только с помощью инструкций mflo регистр и mfhi регистр (Move From LO / Move From HI). Никакой длинной арифметики в MIPS нет. Деление регистра на регистр приводит к заполнению lo и hi частным и остатком соответственно. Пройдите пошагово в Mars:

     1         li      $t0 6
     2         li      $t1 7
     3         li      $t2 5
     4         mult    $t0 $t1
     5         mflo    $t3
     6         div     $t3 $t2
     7         mflo    $t6
  

• Организация цикла с предусловием. Обратите внимание на вывод перевода строки с помощью системного вызова № 11 (понадобится для Д/З!):

     1         li      $t0 10          # инициализация
     2 loop:   blez    $t0 final       # проверка условия
     3         move    $a0 $t0
     4         li      $v0 1           # тело цикла: вывод числа
     5         syscall
     6         li      $v0 11
     7         li      $a0 0x0a        # вывод перевода строки
     8         syscall
     9         addiu   $t0 $t0 -1      # изменение
    10         b       loop
    11 final:  move    $a0 $t3         # вывод суммы
    12         li      $v0 10          # останов
    13         syscall
  

• Организация массива слов. Обратите внимание, куда попадает в памяти число 0xdeadbeef, и что прибавлять к «индексу» (на самом деле — адресу) надо 4.

     1 .data
     2 Array:  .space  40              # 40 байтов памяти
     3 NoNeed: .word   0xdeadbeef      # просто, чтобы было видно конец)
     4 
     5 .text
     6         li      $t0 10          # инициализация
     7         la      $t1 Array       # la — то же самое, что и li, просто для удобства понимания
     8 loop:   blez    $t0 final       # проверка условия
     9         sw      $t0 ($t1)       # записываем слово в память
    10         addiu   $t1 $t1 4       # Увеличиваем адрес на 4
    11         addiu   $t0 $t0 -1      # изменение
    12         b       loop
    13 final:  li      $v0 10          # останов
    14         syscall
  

Д/З

0. Всем, кто ещё не успел, зарегистрироваться на EJudge и решить задачку с прошлой лекции !

1. EJudge: DigitSum 'Сумма цифр'

   Ввести целое число (возможно, отрицательного) и посчитать сумму его цифр в десятичной записи; вывести как целое.

   Input:

   -12345

   Output:

   15

2. EJudge: PlusMinus 'Плюс-минус'

   Ввести натуральное N, затем N целых чисел a_i; посчитать формулу a₀-a₁+a₂-…±a_N-1 . Вывести результат.

   Input:

   4
   22
   13
   14
   15

   Output:

   8

3. EJudge: EvenBack 'Чётные назад'

   Ввести целое N, затем N целых чисел. Вывести из этих чисел только чётные, причём в обратном порядке (стеком пользоваться запрещается )

   Input:

   6
   12
   -11
   3
   88
   0
   1

   Output:

   0
   88
   12

4. EJudge: NoDups 'Без повторений'

   Ввести целое N, затем N целых чисел. Вывести эти числа, пропуская уже выведенные, если встретятся повторы.

   Input:

   8
   12
   34
   -12
   23
   12
   -12
   56
   9

   Output:

   12
   34
   -12
   23
   56
   9