Виды адресации

Одна из задач ЭВМ — работа с массивами данных, в простом случае — с набором ячеек, последовательно лежащих в памяти. В системе команд УМ-3 поддерживается единственный способ обращения к ячейке — прямая адресация, при которой адрес ячейки явно указывается в поле команды.

Самомодификация кода

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

В частности, для последовательного прохождения памяти необходимо прибавлять по 1 к соответствующему полю команды. Рассмотри пример программы, заполняющей отрезок памяти числами от 1 до N.

.cpu mm-3

; ввести N<=0x100 и заполнить N ячеек, начиная с 0x1000, числами от 1 до N
; вывести первые 6 ячеек
.input 0x103
.output 0x1000, 0x1001, 0x1002, 0x1003, 0x1004, 0x1005


.code
        00 0100 0000 0102 ; 0 ; move 1 I
        00 0104 0000 0003 ; 1 ; move definstr inst
        86 0102 0103 0007 ; 2 ; next: sjg I > N -> halt
        00 0102 0000 1000 ; 3 ; instr: move I Array[I-1]
        01 0003 0100 0003 ; 4 ; add inst 1 =: inst
        01 0102 0100 0102 ; 5 ; add I 1 =: I
        80 0000 0000 0002 ; 6 ; jump next
        99 0000 0000 0000 ; 7 ; halt

.code 0x0100
        00 0000 0000 0001 ; 0 ; 1
        00 0000 0000 0000 ; 1 ; 0
        00 0000 0000 0000 ; 2 ; I
        00 0000 0000 0000 ; 3 ; N
        00 0102 0000 1000 ; 4 ; move I Array[0]

.enter 16

• Команда по адресу 0003 (00 0102 0000 1000) изначально заносит содержимое 0102 в 1000

• Команда по адресу 0004 (01 0003 0100 0003) модифицирует содержимое ячейки 0003, прибавляя к ней 1, что соответствует увеличению на 1 адреса результата

Согласно канонической схеме цикла «все ячейки, изменяемые в цикле, должны быть предварительно инициализированы». Поэтому начальные значения записываются не только в счётчик (команда по адресу 0000), но и в ячейку 0003 (команда по адресу 0001). Начальное содержимое этой ячейки (команда пересылки счётчика в нулевой элемент массива) хранится по адресу 0104. Обратите внимание на то, что команда по адресу 0104 никогда не выполняется, это именно что данные , которыми надо инициализировать одну из ячеек выполняемой программы. (мы уже задавали этот вопрос, но всё-таки) Зачем записывать 00 0102 0000 1000 по адресу 0003, если при старте программы там и так лежит 00 0102 0000 1000?

В комментариях к этой программе есть неформально понимаемые метки inst, halt и next (а также I, 1 и т. п.). Дело в том, что во время написания программы заранее неизвестны адреса переходов, так что изначально её текст выглядел так:

        00 0100 0000 0102 ; 0 ; move 1 I
        00 0104 0000 inst ; 1 ; move definstr inst
        86 0102 0103 halt ; 2 ; next: sjg I > N -> halt
        00 0102 0000 1000 ; 3 ; instr: move I Array[I-1]
        01 inst 0100 inst ; 4 ; add inst 1 =: inst
        01 0102 0100 0102 ; 5 ; add I 1 =: I
        80 0000 0000 next ; 6 ; jump next
        99 0000 0000 0000 ; 7 ; halt

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

Пример: ввести 10 чисел по адресам 0x1000 — 0x1009, заполнить адреса 0x2000 — 0x2009 удвоенными значениями в обратном порядке, вывести 0x2000 — 0x2009. Поскольку предполагается отладка программы и переписывание адресов, повторим трюк: заменим неизвестные адреса на последовательности вида "_***", где *** — любые символы. В конце работы заменим их на адреса автоматически.

.cpu mm-3

; ввести 10 чисел по адресам 0x1000 — 0x1009
; заполнить адреса 0x2000 — 0x2009 удвоенными значениями в обрaтном порядке
; вывести 0x2000 — 0x2009
.input  0x1000, 0x1001, 0x1002, 0x1003, 0x1004, 0x1005, 0x1006, 0x1007, 0x1008, 0x1009
.output  0x2000, 0x2001, 0x2002, 0x2003, 0x2004, 0x2005, 0x2006, 0x2007, 0x2008, 0x2009

.code
___s    00 ___1 0000 ___I ; move 1 I
        00 ___p 0000 ___m ; move ___p ___m
___c    86 ___I ___8 ___e ; sjg I N -> ___e
___m    03 1000 ___2 2009 ; mul A[0] 2 -> B[9]
        01 ___I ___1 ___I ; add I 1
        01 ___m __o1 ___m ; add ___m 100000000
        02 ___m ___1 ___m ; sub ___m 1
        80 0000 0000 ___c ; jump ___c

___e    99 0000 0000 0000 ; halt
___1    00 0000 0000 0001 ; 1
___2    00 0000 0000 0002 ; 2
___8    00 0000 0000 000A ; 10
___I    00 0000 0000 0000 ; I
___p    03 1000 ___2 2009 ; mul A[0] 2 -> B[9]
__o1    00 0001 0000 0000 ; ОП1[1]

.enter 1 2 3 4 3 2 1 0 -1 -2

Ячейка ___m изначально содержит команду пересылки из начала первого массива в конец второго (инициализируется из ячейки ___p), а по ходу программы модифицируется дважды: адрес источника увеличивается на 1, а адрес результата уменьшается на 1. При этом используется константа 0x100000000, добавление которой к ячейке эквивалентно добавлению 1 к полю первого операнда.

После обработки вручную или вот такой программой на Python

$ python3 mmlabel.py < selfmod2.mm3 > selfmod2.mmach

Программа примет вид

.cpu mm-3

; ввести 10 чисел по адресам 0x1000 — 0x1009
; заполнить адреса 0x2000 — 0x2009 удвоенными значениями в обрaтном порядке
; вывести 0x2000 — 0x2009
.input  0x1000, 0x1001, 0x1002, 0x1003, 0x1004, 0x1005, 0x1006, 0x1007, 0x1008, 0x1009
.output  0x2000, 0x2001, 0x2002, 0x2003, 0x2004, 0x2005, 0x2006, 0x2007, 0x2008, 0x2009

.code
        00 0009 0000 000c ; move 1 I
        00 000d 0000 0003 ; move ___p ___m
        86 000c 000b 0008 ; sjg I N -> ___e
        03 1000 000a 2009 ; mul A[0] 2 -> B[9]
        01 000c 0009 000c ; add I 1
        01 0003 000e 0003 ; add ___m 100000000
        02 0003 0009 0003 ; sub ___m 1
        80 0000 0000 0002 ; jump ___c

        99 0000 0000 0000 ; halt
        00 0000 0000 0001 ; 1
        00 0000 0000 0002 ; 2
        00 0000 0000 000A ; 10
        00 0000 0000 0000 ; I
        03 1000 000a 2009 ; mul A[0] 2 -> B[9]
        00 0001 0000 0000 ; ОП1[1]

.enter 1 2 3 4 3 2 1 0 -1 -2

Недостатки самомодификации кода

• Обычного арифметического сложения недостаточно для модификации команд:
  • При добавлении/вычитании надо следить за переполнением поля адреса (например, из fffe+4 не должно получаться 10002)

  • Для того, чтобы «вырезать» поля команд в отдельные ячейки или подменять их, необходимы TODO [[.|побитовые операции]], которых в системе команд УМ нет

• Модификация кода многократно усложняет отладку программы
• Модификация кода делает практически невозможной верификацию (исследование на наличие ошибок) и оптимизацию (перегруппировку/замену команд для повышения эффективности работы)

Какой из этих недостатков привёл к тому, что в современных компьютерах cамомодификация практически не используется?

(А ещё надо заметить, что мы начали изобретать язык ассемблера для нашей модельной машины… возможно, не стоит слишком увлекаться?)

Двухадресная машина

Недостатки трёхадресной машины:

• несоответствие размера ячейки адресуемой памяти
  • для передачи адреса достаточно двух байтов, для передачи содержимого нужно 7 — различные каналы передачи?
• большие команды вообще, в т. ч.
  • команды с неиспользуемыми полями (типа move, halt)
  • команды вида 01 0103 0107 0103 (операнд совпадает с результатом)

  • ⇒ Неэффективное использование памяти (низкая т. н. плотность кода)

Двухадресная машина

Два поля операции — источник (он же приёмник) и операнд

Размер ячейки 8+2*16 == 40 битов (на одно целое число хватает). Формат ячейки:

• КК ИИИИ ОООО

Например, арифметические операции изменяют первый операнд:

01 0100 0200 ; add 0100 0200 -> 0100 или просто add 0100 0200

• Такую запись можно читать как «прибавим к ячейке 0100 ячейку 0200»

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

• sub уменьшаемое вычитаемое разность → move разность уменьшаемое; sub разность вычитаемое (не забываем о порядке операндов)

• jeq a b адрес → ?

  • Можно заменить на move c a; sub c b; jump-zero с адрес

  • При этом придётся хранить результат вычитания в отдельной ячейке c

Флаги

Флаги

однобитные ячейки для отображения свойств данных или состояния ЭВМ.

• изменяются автоматически в процессе выполнения команд
  • арифметических
  • сравнения
  • …

• хранятся в виде битов регистра флагов РФ

• используются для проверки свойств командами
  • условного перехода
  • условного присваивания (нет в системе команд УМ-) и т. п.

Команда сравнения 05 — это команда вычитания, которая не изменяет значения приёмника. но устанавливает флаги.

• Ноль (Zero, ZF) возникает всякий раз, когда результат равен нулю

• Перенос (Carry, CF) за пределы ячейки возникает при получении слишком большого числа (например, 0xfffffffff8+9) или при вычитании большего числа из меньшего (без учёта знака, что приводит к заёму бита за пределами ячейки)

• Знаковое переполнение (Overflow, OF) фиксирует неожиданную смену знакового бита (например, если при сумме двух положительных чисел получается отрицательное или при вычитании положительного из отрицательного — положительное)

• Знаковый бит (Sign, SF) результата также запоминается в флаге

Таким образом ZF==1 отражает сравнение равных чисел (ZF==0 — неравных), а CF==1 — сравнение беззнакового меньшего с большим.

Для знаковых чисел сравнение меньшего с большим (то есть вычитание большего из меньшего) приведёт

• для двух неотрицательных или двух отрицательных чисел — к отрицательному результату без переполнения (ZF==1 and OF == 0),
• для отрицательного и положительного чисел
  • к отрицательному результату без переполнения, если сумма модулей чисел не превосходит наибольшее для данной целое число
  • либо к положительному с переполнением (ZF==0 and OF==1),
  • что в целом соответствует неравенству этих флагов.

В каких ситуациях удобно использовать флаги CF / OF ?

Выставление флагов при сравнении

Флаги в эмуляторе хранятся в следующих битах (цитата из исходного кода на Python3)

• CF = 2 ** 0
• OF = 2 ** 1
• SF = 2 ** 2
• ZF = 2 ** 3
• HALT = 2 ** 4 (это не свойство данных, а статус самого процессора — состояние после останова)

Для примера рассмотрим в отладчике программу flags.mm2, состоящую только из сравнений.

.cpu mm-2

.input 0x1000,0x1001,0x1002,0x1003,0x1004,0x1005
.output 0x1000,0x1001,0x1002,0x1003,0x1004,0x1005

.code
05 1000 1000
05 1000 1001
05 1000 1002
05 1003 1004
05 1003 1005
99 0000 0000

.enter 25 20 31 0x8000000004 0x8000000002 1234

• Числа по адресам 1003 и 1004 содержат знаковый бит и могут быть интерпретированы как большие отрицательные (-549755813884 и -549755813886 соответственно).

Запустим отладчик: modelmachine debug flags.mm2, будем вводить команду step и посмотрим, как инструкции выставляют флаги (напомним, что в отладчике цветом выделяется следующая, ещё не исполненная инструкция):

• [0510001000] Сравнение равных установило флаг ZF (третий бит РФ); FLAGS  0x0000000008,

• [0510001001] сравнение 25 с меньшим 20 сбросило все флаг; FLAGS  0x0000000000;

• [0510001002] сравнение 25 с большим 31 установило флаг переноса (нулевой бит) и знаковый флаг (второй бит); FLAGS  0x0000000005 ,

• [0510031004] сравнение отрицательного 0x8000000004 с меньшим 0x8000000002 снова сбросило все биты;

• [0510031004] а сравнение большого отрицательного 0x8000000004 с положительным 1234 дало в силу знакового переполнения OF (первый бит) положительное число 0x7ffffffb32 (ZF==0); FLAGS  0x0000000002.

Примеры программ для УМ-2

Определить максимум из дух чисел:

.cpu mm-2

; ввести два числа, вывести максимум
.input 0x101, 0x102
.output 0x103

.code
00 0103 0101 ; по умолчанию максимум — 0101
05 0101 0102 ; comp 0101 0102 — команда сравнения
86 0000 0004 ; если 0101 и вправду больше, перейти на 0004
00 0103 0102 ; иначе максимум — 0103
99 0000 0000 ;

.enter 723 234

Ввести число и вычислить его факториал:

.cpu mm-2

; факториал
.input 0x100
.output 0x101

.code
00 0102 0100 ; 0; Заносим N в счётчик
00 0101 0008 ; 1; Заносим 1 в результат
05 0102 0008 ; 2; Сравниваем счётчик и 1
85 0000 0007 ; 3; Если ≤, цикл окончен
03 0101 0102 ; 4; Домножаем результат на счётчик
02 0102 0008 ; 5; Уменьшаем счётчик на 1
80 0000 0002 ; 6; Переход на начало цикла
99 0000 0000 ; 7; конец
00 0000 0001 ; 8; 1

.enter 6

Уже говорилось, но всё равно обратите внимание: в двухадресной машине изменяется первый операнд (приёмник), а не последний, как в трёхадресной.

Одноадресная учебная машина

Классический цикл работы процессора включает в себя чтение данных из памяти и запись результата в память. Операции чтения и записи считаются довольно медленными по сравнению с арифметическими действиями. Если, следом за фон Нейманом, полагать что обменом данными занимается единственное устройство — шина — получим, что чем меньше адресов упомянуто в команде, тем быстрее она работает. Тем не менее принципиальное разницы между работой трёхадресной и двухадресной машины нет.

Почему такт работы трёхадресной и двухадресной машины занимает примерно одинаковой время?

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

В одноадресной УМ:

• Размер ячейки — 8 разрядов КОП + 16 разрядов ОП = 24 бита

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

• Появляется инструкция выгрузки (записи) аккумулятора по определённому адресу (10 адрес)

• Появляется инструкция обмена содержимым между аккумулятором и дополнительным регистром S1, в который попадает остаток про делении (20)

  • Операция целочисленного деления в принципе особенная, и возвращает два результата — частное и остаток — но такое поведение не укладывается в наш вариант УМ-3 и УМ-2

• Остальные команды не нуждаются в реогранизации

Пример:

.cpu mm-1

; ввести два числа, вывести максимум
.input 0x100, 0x102
.output 0x104

.code
00 0100 ; прочитать (здесь и далее — в аккумулятор, он же S1) 0100
10 0104 ; записать в 0104 (это максимум по умолчанию)
05 0102 ; сравнить с 0102
86 0006 ; перейти, если больше, на 0006 (всё хорошо)
00 0102 ; прочитать 0102
10 0104 ; записать в 0104 (это настоящий максимум)
99 0000 ; КОНЕЦ

.enter 123 234

Команд в программе стало больше, но байтов она занимает меньше. Что ещё важнее, в одноаресной машине можно практически избежать «паразитных» операций чтения из памяти. Например, в данной программе после чтения ячейки в регистр и записи в другую ячейку сразу следует сравнение с регистром, в то время как на предыдущих архитектурах было бы сравнение с содержимым ячейки (следовательно, ещё одно чтение).

В УМ1 возникает понятие планирования вычислений.

Пример: вычислить b²-4ac. Если запрограммировать формулу как она есть, получится примерно следующее:

.cpu mm-1

.input 0x000B, 0x000C, 0x000D
.output 0x000E

.code
        00 000C ; <- b
        03 000C ; *  b
        10 000F ; -> b²
        00 0011 ; <- 4
        03 000B ; *  a
        03 000D ; *  c
        10 0010 ; -> 4ac
        00 000F ; <- b²
        02 0010 ; -  4ac
        10 000E ; -> d
        99 0000 ; halt
        000000 ; a
        000000 ; b
        000000 ; c
        000000 ; d
        000000 ; b²
        000000 ; 4ac
        000004 ; 4
.enter 2 5 3

Если же обратить внимание на то, что хранить b²не обязательно, программа получится на две инструкции короче (причём обе — «медленные» инструкции работы с памятью):

.cpu mm-1

.input 0x0009, 0x000A, 0x000B
.output 0x000C

.code
        00 000E ; <- 4
        03 0009 ; *  a
        03 000B ; *  c
        10 000D ; -> 4ac
        00 000A ; <- b
        03 000A ; *  b
        02 000D ; -  4ac
        10 000C ; -> d
        99 0000 ; halt
        000000 ; a
        000000 ; b
        000000 ; c
        000000 ; d
        000000 ; 4ac
        000004 ; 4

.enter 2 5 3

Замечание. Если регистр всего один, сэкономить можно только на последовательных модификациях этого регистра, для более сложных вычислений надо предусмотреть дополнительные регистры и возможность указать в инструкции, с какими из них идёт работа.