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

Question

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

Я могу представить себе пару инструкций, которые (я считаю) всегда должны присутствовать на любом языке ассемблера, например MOV для перемещения байтоввокруг и JP для отправки указателя инструкций на другой адрес.

Не могли бы вы предложить набор самых основных и необходимых инструкций по сборке?Спасибо!

Answer 1

Управляющие структуры составляют базовую особенность, без которой нет языка. Это означает, что ваш язык должен обеспечивать арифметические операции над двумя переменными; а затем разрешить программе изменять счетчик программ - то есть переходить - в зависимости от результата операции. Очень часто ключевой операцией является SUB для вычитания одного операнда из другого. И условия, на которых вы бы позволили филиал:

1. результат равен нулю;
2. результат больше нуля;
3. результат меньше нуля.
4. без условий, т.е. безусловная ветвь

Вам также нужны инструкции для перемещения данных: скажем, LOAD и STORE.

Эти три условия и соответствующие им ветви (или пропуски, что является другим способом сделать это) необходимы для любой программы. Мало того, но только эти три простые операции плюс инструкции по перемещению данных достаточны для выполнения всего в программе, кроме ввода-вывода. Если вы хотите, и с учетом организации совместной работы с памятью, вы можете переписать Linux, используя просто LOAD, STORE, ADD, SUB и три условных ветви.

PDP-8 был гораздо более мощной машиной, чем этот: он имел богатый набор из восьми инструкций , включая ввод / вывод.

HTH

Answer 2

Наименьший набор команд требует без инструкции или, может быть, нулевая инструкция .Я не знаю, входили ли они в реальные устройства или нет, но компьютер с одним набором команд (OISC) был реализован и успешно работает в компьютеры с углеродными нанотрубками и MAXQ .

На самом деле x86 также может использоваться в качестве архитектуры OISC, поскольку можно сделать что угодно столько один mov, потому что это было , оказалось, что полная по Тьюрингу .Есть даже компилятор с именем movfuscator для компиляции допустимого кода C в программу только с MOV (или только с одним из XOR, SUB, ADD, XADD, ADC, SBB, AND / OR, PUSH / POP, 1-сдвиги битов, или CMPXCHG / XCHG)

---

Однако ИМО архитектура должна быть достаточно "быстрой" (или не требовать слишком много инструкций, таких как OISC, для выполнения задачи по сравнению с другими архитектурами) считается полезным .

Основными типами команд для компьютера являются перемещения данных, логические / арифметические операции и ветвления.Для арифметических операций достаточно add/subtract.Для логики мы можем вычислить любые функции только с NOR или NAND, поэтому нужна только одна.Для прыжка нам понадобится одна jump on "<=" или jump on "<" инструкция.Движения данных можно эмулировать с помощью add / sub.Таким образом, мы можем использовать 2 бита для кодирования 3 кодов операций (add, nand, jump on "<=") и оставить один для дальнейшего расширения.Но поскольку в нем нет отдельных инструкций загрузки / сохранения , он должен работать непосредственно с большим регистровым файлом вместо памяти, или инструкции должны иметь возможность использовать память в качестве операндов.

Если большенужна скорость, тогда можно добавить еще немного логики, инструкции ветвления и, возможно, загрузить / сохранить, увеличив пространство кода операции до 3 бит.Набор инструкций может быть:

1. загрузка
2. сохранение
3. добавление
4. и
5. или
6. перейти менее чем на
7. перейти на равном

Сдвиг влево можно выполнить с помощью add, но сдвиг вправо сложнее, поэтому вы можете также добавить правый сдвиг, чтобы облегчитьнекоторые общие операции

Answer 3

Удивительно, но существует такая вещь, как компьютер с одним набором команд .

Answer 4

Ну, это очень широкий вопрос. Полагаю, вам нужно ознакомиться с машиной произвольного доступа . Я не эксперт, но трудно сказать, какие инструкции должны поддерживаться этим самым базовым микропроцессором. Например: вычитание и умножение могут быть смоделированы операцией сложения. Умножение возможно, если микропроцессор поддерживает переходы и условные инструкции, а вычитание возможно путем добавления отрицательного числа.

Answer 5

Вы можете прекрасно выжить с минимальным набором команд, состоящим только из SOB:, вычитания единицы и ответвления. Целые программы могут и были написаны с этим.

Answer 6

Посмотрите на коммерческие реализации

Лучший ответ, вероятно, будет смотреть на существующие коммерческие реализации.

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

Каково определение инструкции?

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

Будет ли это коммерчески привлекательным, однако? Маловероятно, поскольку это оборудование, вероятно, будет слишком специализированным, чтобы оправдать затраты на разработку.

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

В конце концов, «эффективное оборудование» означает:

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

Возможные причины, по которым очень маленькие полные ISA Тьюринга могут быть неэффективными

• несколько инструкций, которые у них есть, очень сложны и требуют больших затрат каждый раз, когда их вызывают, например, Вы не можете выполнить определенную оптимизацию конвейерной обработки
• плотность кода очень мала, что подразумевает:
  • производительность может быть связана с извлечением инструкций
  • не подходит для встроенных устройств с небольшим объемом ПЗУ

Известные реализации OISC

Было бы интересно проанализировать их, чтобы получить более конкретный ответ.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Компилятор Toy C для x86, который использует только инструкции mov x86, показывая очень конкретным образом, что достаточно одной инструкции.

Полнота Тьюринга, кажется, доказана в статье: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

subleq

Образовательная OSIC, ранее упомянутая в https://stackoverflow.com/a/9439153/895245, но без названия:

• https://github.com/hasithvm/subleq-verilog Verilog, Xilinx ISE.
• https://github.com/purisc-group/purisc Verilog и VHDL, Altera. Возможно, у этого проекта есть бэкэнд Clang, но я не могу его использовать: https://github.com/purisc-group/purisc/issues/5
• http://mazonka.com/subleq/sqasm.cpp | http://mazonka.com/subleq/sqrun.cpp C ++ - ассемблер и эмулятор на основе.

Смотри также: https://esolangs.org/wiki/Subleq

См. Также

https://softwareengineering.stackexchange.com/questions/230538/what-is-the-absolute-minimum-set-of-instructions-required-to-build-a-turing-comp/325501

Answer 7

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

MOV mem1 mem1 - скопировать содержимое ячейки памяти mem1 в ячейку памяти mem2, оставив mem1 без изменений

NAND mem1 в mem2 в mem3 - выполнить побитовое логическое NAND между данными в mem1 и mem2 и записать результат в mem3

BITSHIFTR mem1 mem2 mem3 - битовое смещение вправо данных в местах mem1 mem2 и записьвывод в mem3

JMPcond mem1 mem2 - проверить младший значащий бит в mem1 и, если оно истинно (1), перейти к mem2

Теперь он не будет очень быстрым и будет съедатьПропускная способность памяти вроде бы сумасшедшая, но ее можно использовать для реализации виртуальной машины с любым произвольным набором инструкций.Кроме того, существуют определенные программные ограничения, такие как необходимость программирования всех начальных данных или, по крайней мере, место в памяти, где только LSB установлен в 1. аппаратные периферийные устройства должны будут использовать DMA для доступа к вводу / выводу, и, если реализовано наГарвардская архитектура У программы не будет прямого доступа к таким вещам, как указатели.

Answer 8

Вы также можете посмотреть полноту Тьюринга.

http://en.wikipedia.org/wiki/Turing_completeness

http://c2.com/cgi/wiki?TuringComplete

Что такое полный Тьюринг?

Это означает, что языка достаточно для вычисления всего, что может быть вычислено.