Косвенная адресация и массивы

Отступление об особенностх работы псевдоинструкций с длинными константами.

Мы знаем, что для больших (больше 12 битов) констант инструкция li раскладывается на две: lui для старших 20 битов, и addi для младших 12.

0x00400000  0xfffed2b7  lui x5,0xffffffed            1          li      t0 0xfffed234
0x00400004  0x23428293  addi x5,x5,0x00000234             
0x00400008  0xfffee2b7  lui x5,0xffffffee            2          li      t0 0xfffedcbb
0x0040000c  0xcbb28293  addi x5,x5,0xfffffcbb

Почему в примере в одном случае старшие 20 битов в lui равны 0xfffed, а в другом — 0xfffee, хотя в исходных константах они совпадают?

Дело в распространении знака. Обе больших константы — отрицательные, так что число, которое образуется в регистре t0 после инструкции lui, — тоже отрицательно.

Но распространение знака актуально и для второй части константы — 12 младших битов:

• В числе 0xfffed234 это 0x234, положительное число 564 (11-й бит равен 0)

• В числе 0xfffedcbb это 0xcbb, отрицательное число -837 (11-й бит равен 1)

Таким образом, как это видно по работе дизассемблера, в первом случае, чтобы получить желаемое значение надо сложить некоторую большую константу с 0x00000234, а во втором — с 0xfffffcbb.

• 0xfffed234 = 0xfffed000 + 564

• 0xfffedcbb = 0xfffee000 + -837

Косвенная адресация

   1 .data
   2         .word   0x1223344
   3 var:    .word   0xdeadbeef
   4 addr:   .word   var
   5 .text
   6         lw      t1 var
   7         lw      t2 addr
   8         lw      t3 (t2)
   9         lw      t4 4(t2)
  10         lw      t5 -4(t2)
  11         sw      t5 var t0

Address     Code        Basic                        Line Source

0x00400000  0x0fc10317  auipc x6,0x0000fc10          6            lw      t1 var
0x00400004  0x00432303  lw x6,4(x6)
0x00400008  0x0fc10397  auipc x7,0x0000fc10          7            lw      t2 addr
0x0040000c  0x0003a383  lw x7,0(x7)
0x00400010  0x0003ae03  lw x28,0(x7)                 8            lw      t3 (t2)
0x00400014  0x0043ae83  lw x29,4(x7)                 9            lw      t4 4(t2)
0x00400018  0xffc3af03  lw x30,0xfffffffc(x7)        10           lw      t5 -4(t2)
0x0040001c  0x0fc10297  auipc x5,0x0000fc10          11           sw      t5 var t0
0x00400020  0xffe2a423  sw x30,0xffffffe8(x5)

   1 .data
   2 array:  .space  64
   3 arrend:
   4 .text
   5         la      t0 array
   6         la      t1 arrend
   7         li      t2 1
   8 loop:   sw      t2 (t0)
   9         addi    t2 t2 1
  10         addi    t0 t0 4
  11         bltu    t0 t1 loop

0x10010000    0x00000001 0x00000002 0x00000003 0x00000004 0x00000005 0x00000006 0x00000007 0x00000008
0x10010020    0x00000009 0x0000000a 0x0000000b 0x0000000c 0x0000000d 0x0000000e 0x0000000f 0x00000010

   1 .data
   2 sep:    .asciz  "--------\n"    # Строка-разделитель (с \n и нулём в конце)
   3 .align  2                       # Выравнивание на границу слова
   4 array:  .space  64              # 64 байта
   5 arrend:                         # Граница массива
   6 .text
   7         la      t0 array        # Счётчик
   8         la      s1 arrend
   9         li      t2 1            # Число, которое мы будем записывать в массив
  10 fill:   sw      t2 (t0)         # Запись числа по адресу в t0
  11         addi    t2 t2 1         # Изменим число
  12         addi    t0 t0 4         # Увеличим адрес на размер слова в байтах
  13         bltu    t0 s1 fill      # Если не вышли за границу массива
  14 
  15         la      a0 sep          # Выведем строку-разделитель
  16         li      a7 4
  17         ecall
  18         la      t0 array
  19 out:    li      a7 1
  20         lw      a0 (t0)         # Выведем очередной элемент массива
  21         ecall
  22         li      a7 11           # Выведем перевод строки
  23         li      a0 10
  24         ecall
  25         addi    t0 t0 4
  26         blt     t0 s1 out
  27 
  28         li      a7 10           # Останов
  29         ecall

Пример косвенной адресации со смещением: вывести сумму четырёх пар чисел.

   1 .data
   2 pairs:  .word   1 2 3 4 5 6 7 8
   3 pairs_end:
   4 .text
   5         la      t2 pairs        # Инициализация: начало массива пар
   6         la      t3 pairs_end    # Инициализация: Конец массива пар
   7 loop:   bgeu    t2 t3 done      # Проверка условия: беззнаковое сравнение адресов
   8         lw      t4 (t2)         # Первое слагаемое
   9         lw      t5 4(t2)        # Второе слагаемое
  10         add     a0 t4 t5        # Сумма
  11         li      a7 1            # Вывод целого
  12         ecall
  13         li      a0 '\n'
  14         li      a7 11           # Вывод байта
  15         ecall
  16         addi    t2 t2 8         # Изменение: прибавляем размер пары
  17         j       loop
  18 done:   li      a7 10           # Останов
  19         ecall

• Размер пары чисел — два машинных слова, то есть 8 байтов
• Сравнение адресов беззнаковое

Работа с отладчиком в RARS

Отлаживать сколько-нибудь сложные алгоритмы в машинных кодах — и просто, и сложно. Просто, потому что все инструкции выполняют строго подряд и имеют одинаковый (или как минимум предсказуемый размер) в памяти; кроме того, не только эмуляторы, наподобие RARS, но и настоящие процессоры обычно имеют режим отладки, позволяющий задавать т. н. «точки останова» (breakpoints). Каждая точка останова задаёт некоторое свойство контекста выполнения, и программа выполняется штатным образом до тек пор, пока контекст не обладает ни одним из этих свойств. Breakpoint в собственном смысле — это ситуация, когда счётчик команд pc становится равен заданному значению (говорят «программа дошла до точкиадреса останова»). Есть также watchpoint — останов, когда некоторое выражение становится истинным (например, содержимое некоторого регистра — равным заданному значению), и catchpoint — останов при штатном или нештатном обращении к окружению (ловушке, внешнему вызову и т. п.).

В RARS поддерживаются только breakpoints — точки останова по достижению адреса.

• Частный случай точки останова — пошаговый проход кода (с паузой на каждой инструкции — кнопка «>₁»)

  • 

• Сама точка останова задаётся «галочкой» на соответствующей инструкции в колонке «Bkpts»

  • 

• Теперь можно нажимать кнопку запуска («>») — выполнение остановится на отмеченной инструкции (если, конечно, дойдёт до него)

  • 

• Намного более сложный в плане реализации инструмент — т. н. «обратная отладка» (reverse debugging). Фактически, для того, чтобы «сделать шаг назад» при отладке программы, нужно однозначно восстановить контекст выполнения на момент до выполнения предыдущей инструкции, и, стало быть, запоминать изменения в контексте (регистров, памяти и т. п.). Многие отладчики так умеют, а в RARS сохранение контекста сделать было относительно несложно (напомним, что окружением для RISC-V кода, выполняемого в RARS, является сам RARS — приложение на языке Java). Шаг назад в отладке задаёт кнопка «₁<»

  • 

На каждом шаге выполнения эмулятор отслеживает. что изменилось в регистрах и оперативной памяти, и подсвечивает такие изменения (в примере выше это регистр t3)

Вложенные циклы

Вспомним каноническую схему цикла:

1. Инициализация
2. Проверка условия
3. Тело
4. Изменение

Сообразуясь с ней напишем программу, которая выводит числа от 1 до N2, по N в строке. Это можно сделать просто заменяя пробел на перевод строки после каждого кратного N числа, но мы используем вложенные циклы: N строк, в каждой строке — числа от N * (номер строки - 1) + 1 до N * (номер строки). Для простоты возьмём N=6.

   1         li      s1 6            # N
   2         li      s2 1            # Инициализация: номер строки
   3 rows:   bgt     s2 s1 done      # Проверка: конец вывода
   4         li      s3 1            # Инициализация: номер столбца
   5 cols:   bgt     s3 s1 next      # Проверка: конец строки
   6         li      a7 11
   7         li      a0 ' '          # Вывод пробела
   8         ecall
   9         addi    a0 s2 -1
  10         mul     a0 a0 s1
  11         add     a0 a0 s3        # N * (строка - 1) + столбец
  12         li      a7 1            # Вывод числа
  13         ecall
  14         addi    s3 s3 1         # Изменение: номер столбца
  15         j       cols
  16 next:   li      a0 '\n'         # Вывод перевода строки
  17         li      a7 11
  18         ecall
  19         addi    s2 s2 1         # Изменение: номер строки
  20         j       rows
  21 done:   li      a0 10
  22         ecall

В этом примере каноническая схема цикла строго соблюдена:

0. Инициализация внешнего цикла
1. Проверка условия внешнего цикла
2. Тело внешнего цикла
   0. Инициализация внутреннего цикла
   1. Проверка условия внутреннего цикла
   2. Тело внутреннего цикла
   3. Изменение внутреннего цикла
3. Изменение внешнего цикла

что будет, если стадию инициализации внутреннего цикла вынести за его пределы и совместить с инициализацией внешнего цикла?

Двумерные массивы

Если массив — это набор элементов одного размера, размещённых в памяти подряд, что что такое двумерный массив? В языках высокого уровня двумерный массива представляется таблицей, элементы которого имеют два индекса — номер столбца (абсциссу?) и номер рада (ординату?). Поскольку оперативная память одномерна, и имеет только один индекс — адрес, в большинстве языков программирования такие «таблицы» хранятся в ней по рядам — сначала первый ряд, строго за ним — второй и т. д. Например, если в языке Си задан двумерный массив table, то конструкция table[y] означает адрес ряда № y, а table[y][x] — элемент № x в этом ряду. В языке Фортран массивы хранятся по столбцам — это позволяет сохранять естественный порядок индексов.

С точки зрения ассемблера определение двумерного массива ничем не отличается от определения одномерного. Отличается только способ индексации, в котором по имеющимся двум индексам надо по уже известной нам формуле строка * ширина + столбец вычисляется одномерный индекс, который умножается на размер элемента и прибавляется к адресу начала массива. Чтобы не путаться в индексах при умножении и упростить формулу, принято нумеровать ряды и столбцы с нуля.

Рассмотрим пример, в котором последовательность из 36 целых трактуется как массив 6×6, и в каждом ряду выводятся только нечётные элементы.

   1 .data
   2 array:  .word   1 3 7 2 6 23 74 12 56 2 28 22
   3         .word   23 78 34 67 34 67 89 45 3 56 78 2
   4         .word   24 36 4 734 53 57 345 86 34 567 218 8
   5 .text
   6         li      s1 6            # Ширина
   7         li      s2 6            # Высота
   8         la      s3 array        # Начало массива
   9         li      t1 0            # Инициализация: Y
  10 nxrow:  li      t2 0            # Инициализация: X
  11 next:   mul     t0 t1 s1        # Y * Ширина
  12         add     t0 t0 t2        # Y * Ширина + X
  13         slli    t0 t0 2         # Сдвиг на два бита — это умножение на 4
  14         add     t0 t0 s3        # Адрес элемента, array + (Y * Ширина + X) * 4
  15         lw      a0 (t0)
  16         andi    t0 a0 1         # Оставляем только младший бит
  17         beqz    t0 even
  18         li      a7 1            # Выводим число и пробел
  19         ecall
  20         li      a7 11
  21         li      a0 ' '
  22         ecall
  23 even:   addi    t2 t2 1         # Изменение: X
  24         blt     t2 s1 next      # Проверка X и переход
  25         li      a7 11
  26         li      a0 '\n'
  27         ecall
  28         addi    t1 t1 1         # Изменение: Y
  29         blt     t1 s2 nxrow     # Проверка Y и переход
  30         li      a7 10
  31         ecall

• Здесь мы воспользовались т. н. «циклом с постусловием», в котором проверка условия вынесена в самый конец цикла. Поскольку при этом можно совместить проверку и переход, читаемость кода и его эффективность слегка улучшаются.

• В секции .data мы намеренно представили массив array в виде трёх строк по 12 элементов, а не шести по шесть. В действительности, ничем, кроме значений регистров s1 и s2, размерность двумерного массива не определяется.

Будет ли программа работать, если задать другие значения ширины и высоты — 4×8, 12×3 и т. п.?

Нужна ли вторая инструкция li      a7 11 (вскоре после метки even) — ведь буквально незадолго до этой метки a7 уже заполнялся числом 11, и оно с тех пор не могло поменяться? (нажмите «Комментарии» в шапке страницы, чтобы прочитать спойлер) Нужна! А что, если все числа в первой строке чётные, а в регистре a7 изначально лежит какой-то мусор?

Так же моделируются и многомерные массивы: трёхмерные — как последовательность двумерных с умножением третьей координаты, аппликаты, на размер двумерного слоя, четырёхмерные — как последовательность трёхмерных и т. д.

О защите памяти

В программе выше легко ошибиться и указать размеры массива, превышающие объём данных, заданных в секции .data (например, 8×8), или неверно вычислить размер элемента. Никакой нештатной ситуации при этом не произойдёт: ни при трансляции, ни при обращении к памяти ничего ошибочного не делается! С точки зрения ассемблера «массив» — это просто некоторый адрес в памяти, все используемые программой адреса доступны для чтения и записи в плоской модели памяти.

Если при этом после массива array располагаются какие-то значимые для алгоритма данные, а мы не только читаем, но и записываем что-то в array, в результате мы можем сами того не желая «расписать» содержимое этих значимых данных.