Basheyev1 июн 2021 в 14:23

Разработка стековой виртуальной машины и компилятора под неё (часть I)

8 мин

17K

C++ * Виртуализация * Компиляторы * C *

+12

Комментарии 17

kuza2000 2 июн 2021 в 06:10

Некоторое время назад делал что-то родственное habr.com/ru/post/431932
Материал остался еще на одну статью, заключительную, с тестами. Никак руки не дойдут написать.

Вывод таков — стековая машина сильно тормозит. У меня там на каждой команде переход по адресу в регистре — сброс конвеера.
В этой машине такого перехода нет, но есть ветвление. Интересно было бы сравнить быстродействие.
Вообще, у меня складывается впечатление, что на современных процессорах любая виртуальная машина будет тормозить. Из-за конвеера. Поэтому лучше такой байт-код компилировать в нативный или делать JIT-компиляцию.

Basheyev 2 июн 2021 в 12:34

Почитал вашу статью - очень интересно. У меня нет такого глубокого знания ассемблера x86. Сейчас как раз дописал разбор и генерацию кода простых арифметических выражений с константами. В следующей части опубликую, очень интересно ваше мнение и опыт.

Basheyev 2 июн 2021 в 13:35

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

iboltaev 2 июн 2021 в 13:48

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

kuza2000 3 июн 2021 в 10:57

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

iboltaev 2 июн 2021 в 10:09

switch-based диспетчеризация — не лучший способ написать интерпретатор. Помимо того, что компилятор может не соптимизировать switch в таблицу, на каждую инструкцию байт-кода приходится минимум 2 перехода: в начало цикла и по адресу обработчика инструкции. Direct-threading подход заметно лучше, там в каждом обработчике идет чтение следующей инструкции и переход, так что одна инструкция — один переход. Еще есть на основе базовых блоков диспетчеризация, но это уже к компиляции ближе.
Вот тут можно почитать (применительно к java-байткоду): webdocs.cs.ualberta.ca/~amaral/cascon/CDP05/slides/CDP05-berndl.pdf
Это если будете развивать дальше эту историю.

Basheyev 2 июн 2021 в 12:35

О супер! Спасибо.

JerryI 15 янв 2024 в 16:29

Вот это интересный вопрос! Я правильно ли понимаю, что DDT это в роде того, что есть хэш таблица (упрощенная -> табличка с адресами) с указателями на функции, исполняющие инструкции, а интерпретатор просто бежит по коду коду который ему дали и дергает по указателям функции со ссылкой на текущий стек и т.п.?

UPD: а, уже ответили...

Worky 2 июн 2021 в 14:04

Поздравляю! Вы написали свою Forth машину!

axe_chita 3 июн 2021 в 01:43

Ждем продолжения, надеюсь что оно будет скоро.

Basheyev 4 июн 2021 в 17:16

Готово - https://m.habr.com/ru/post/560986/

axe_chita 6 июн 2021 в 14:02

Спасибо, будем читать!

tonyk_av 3 июн 2021 в 04:14

switch-case работают медленней, чем вызов функций-обработчиков через массив указателей на функции. С ростом числа опкодов это становится заметней. Хотя показанный способ будет понятней читающим.

ИМХО, полезней было бы реализовать интерпретатор байт-кода для виртуальной машины, соответствующей стандарту МЭК 61131-3 и написать транслятор с языка ST.

Basheyev 3 июн 2021 в 04:21

Спасибо! Даже не подозревал о существовании такого стандарта. Почитаю.

tonyk_av 3 июн 2021 в 06:19

Так это стандарт на программирование промышленных ПЛК. Просто если нет разницы на чём разминать мозги, то можно было бы попробовать сделать что-нибудь полезное с далеко идущими последствиями.

Jijiki 8 дек в 01:38

ИИ предложил вашу статью, обьяснив стейк-фреймы, но перед этим запутавшись в стек-фреймах в другом диалоге, эх придётся отлаживать ) спасибо, это я прошел ), у вас локальные переменные планировались?)

точку входа в вм придётся найти и забиндить в (jit можно будет закидывать байт код как есть чтоли, но до этого надо отладить фп - эх), и с глоабльными локальными переменными там дальше еще работа, но да в целом так на С летит пока что

у меня глобальный компилятор-интерпретатор в из байт кода и вот отлаживаю стековые фреймы для локальности переменных )

Скрытый текст

TEST test2      // Отладочный вывод компилятора: 'test2' имеет индекс 0
TEST n  // Отладочный вывод компилятора: 'n' имеет индекс 1
TEST result     // Отладочный вывод компилятора: 'result' имеет индекс 2
TEST i  // Отладочный вывод компилятора: 'i' имеет индекс 3
TEST j  // Отладочный вывод компилятора: 'j' имеет индекс 4
TEST bb         // Отладочный вывод компилятора: 'bb' имеет индекс 5
TEST test       // Отладочный вывод компилятора: 'test' имеет индекс 6
TEST test1      // Отладочный вывод компилятора: 'test1' имеет индекс 7
Function: wm
DEBUG GEN: Variable test2 has offset 0

--- Сгенерированный байт-код ---
1       // PUSH 0
18      // STORE 0
7       // LOAD 0
29      // PRINT_STRING
1       // PUSH 0
0       // HALT
30      // RET
Function: main
DEBUG GEN: Variable test1 has offset 7
DEBUG GEN: Variable i has offset 3
DEBUG GEN: Variable n has offset 1
DEBUG GEN: Variable result has offset 2
DEBUG GEN: Variable i has offset 3
DEBUG GEN: Variable j has offset 4
DEBUG GEN: Variable i has offset 3
DEBUG GEN: Variable test has offset 6
DEBUG GEN: Variable result has offset 2

--- Сгенерированный байт-код ---
1       // PUSH 0
18      // STORE 0
7       // LOAD 0
29      // PRINT_STRING
1       // PUSH 0
0       // HALT
30      // RET
1       // PUSH 5
18      // STORE 1
1       // PUSH 1
18      // STORE 2
1       // PUSH 1
18      // STORE 3
1       // PUSH 0
18      // STORE 4
1       // PUSH 1
18      // STORE 5
1       // PUSH 13
18      // STORE 6
1       // PUSH 20
18      // STORE 7
7       // LOAD 7
29      // PRINT_STRING
7       // LOAD 3
7       // LOAD 1
23      // CMPLE
15      // JUMP_IF_FALSE 72
7       // LOAD 2
7       // LOAD 3
4       // MUL
18      // STORE 2
7       // LOAD 4
1       // PUSH 1
2       // ADD
18      // STORE 4
7       // LOAD 3
1       // PUSH 1
2       // ADD
18      // STORE 3
16      // JUMP 42
7       // LOAD 6
29      // PRINT_STRING
7       // LOAD 2
6       // PRINT
9       // CALL
0       // HALT
1       // PUSH 0
0       // HALT
0       // HALT
//PUSH val 5
STORE 5 in index 1
//PUSH val 1
STORE 1 in index 2
//PUSH val 1
STORE 1 in index 3
//PUSH val 0
STORE 0 in index 4
//PUSH val 1
STORE 1 in index 5
//PUSH val 13
STORE 13 in index 6
//PUSH val 20
STORE 20 in index 7
LOAD 7
PRINT_STRING: Start Loop
LOAD 3
LOAD 1
CMP_LE: 1 <= 5 result 1
JUMP_IF_FALSE to 72 if 1 is false?
LOAD 2
LOAD 3
//MUL
STORE 1 in index 2
LOAD 4
//PUSH val 1
//ADD
STORE 1 in index 4
LOAD 3
//PUSH val 1
//ADD
STORE 2 in index 3
JUMP to 42
LOAD 3
LOAD 1
CMP_LE: 2 <= 5 result 1
JUMP_IF_FALSE to 72 if 1 is false?
LOAD 2
LOAD 3
//MUL
STORE 2 in index 2
LOAD 4
//PUSH val 1
//ADD
STORE 2 in index 4
LOAD 3
//PUSH val 1
//ADD
STORE 3 in index 3
JUMP to 42
LOAD 3
LOAD 1
CMP_LE: 3 <= 5 result 1
JUMP_IF_FALSE to 72 if 1 is false?
LOAD 2
LOAD 3
//MUL
STORE 6 in index 2
LOAD 4
//PUSH val 1
//ADD
STORE 3 in index 4
LOAD 3
//PUSH val 1
//ADD
STORE 4 in index 3
JUMP to 42
LOAD 3
LOAD 1
CMP_LE: 4 <= 5 result 1
JUMP_IF_FALSE to 72 if 1 is false?
LOAD 2
LOAD 3
//MUL
STORE 24 in index 2
LOAD 4
//PUSH val 1
//ADD
STORE 4 in index 4
LOAD 3
//PUSH val 1
//ADD
STORE 5 in index 3
JUMP to 42
LOAD 3
LOAD 1
CMP_LE: 5 <= 5 result 1
JUMP_IF_FALSE to 72 if 1 is false?
LOAD 2
LOAD 3
//MUL
STORE 120 in index 2
LOAD 4
//PUSH val 1
//ADD
STORE 5 in index 4
LOAD 3
//PUSH val 1
//ADD
STORE 6 in index 3
JUMP to 42
LOAD 3
LOAD 1
CMP_LE: 6 <= 5 result 0
JUMP_IF_FALSE to 72 if 0 is false?
LOAD 6
PRINT_STRING: Euklid
LOAD 2
PRINT 120
CALL 0
//PUSH val 0
STORE 0 in index 0
LOAD 0
PRINT_STRING: WM function!
//PUSH val 0
//HALT 

Время выполнения ВМ: 0.575000 мс
Байт-код сохранен в

Jijiki 8 дек в 18:03

вот что-то типо такого но не до конца

Скрытый текст

[IP: 31: FP: 0]   PUSH val 0
[IP: 33: FP: 0]   PUSH val 0
[IP: 35: FP: 0]   PUSH val 0
[IP: 37: FP: 0]   PUSH val 0
[IP: 39: FP: 0]   PUSH val 0
[IP: 41: FP: 0]   PUSH val 15
[IP: 43: FP: 0] Stack (SP=6, FP=0): [0, 0, 0, 0, 0, 15]
  STORE 15 in offset 1
[IP: 45: FP: 0]   PUSH val 100
[IP: 47: FP: 0] Stack (SP=6, FP=0): [0, 15, 0, 0, 0, 100]
  STORE 100 in offset 2
[IP: 49: FP: 0]   PUSH val 20
[IP: 51: FP: 0] Stack (SP=6, FP=0): [0, 15, 100, 0, 0, 20]
  STORE 20 in offset 3
[IP: 53: FP: 0]   PUSH val 30
[IP: 55: FP: 0] Stack (SP=6, FP=0): [0, 15, 100, 20, 0, 30]
  STORE 30 in offset 4
[IP: 57: FP: 0]   PUSH val 0
[IP: 59: FP: 0] Stack (SP=6, FP=0): [0, 15, 100, 20, 30, 0]
  STORE 0 in offset 5
[IP: 61: FP: 0] [IP: 0: FP: 6]   PUSH val 150
[IP: 2: FP: 6] Stack (SP=8, FP=6): [0, 15, 100, 20, 30, 63, 0, 150]
  STORE 150 in offset 2
[IP: 4: FP: 6]   PUSH val 1000
[IP: 6: FP: 6] Stack (SP=8, FP=6): [0, 15, 100, 20, 30, 63, 0, 1000]
  STORE 1000 in offset 3
[IP: 8: FP: 6]   PUSH val 200
[IP: 10: FP: 6] Stack (SP=8, FP=6): [0, 15, 100, 20, 30, 63, 0, 200]
  STORE 200 in offset 4
[IP: 12: FP: 6]   PUSH val 300
[IP: 14: FP: 6] Stack (SP=8, FP=6): [0, 15, 100, 20, 30, 63, 0, 300]
  STORE 300 in offset 5
[IP: 16: FP: 6] Stack (SP=7, FP=6): [0, 15, 100, 20, 30, 63, 0]
  LOAD 1000 in offset 3
[IP: 18: FP: 6]   PRINT 1000
[IP: 19: FP: 6] Stack (SP=7, FP=6): [0, 15, 100, 20, 30, 63, 0]
  LOAD 150 in offset 2
[IP: 21: FP: 6]   PRINT 150
[IP: 22: FP: 6] Stack (SP=7, FP=6): [0, 15, 100, 20, 30, 63, 0]
  LOAD 200 in offset 4
[IP: 24: FP: 6]   PRINT 200
[IP: 25: FP: 6] Stack (SP=7, FP=6): [0, 15, 100, 20, 30, 63, 0]
  LOAD 300 in offset 5
[IP: 27: FP: 6]   PRINT 300
[IP: 28: FP: 6]   PUSH val 0
[IP: 30: FP: 6] Stack (SP=8, FP=6): [0, 15, 100, 20, 30, 63, 0, 0]
[IP: 63: FP: 0] Stack (SP=5, FP=0): [0, 15, 100, 20, 30]
  LOAD 100 in offset 2
[IP: 65: FP: 0]   PRINT 100
[IP: 66: FP: 0] Stack (SP=5, FP=0): [0, 15, 100, 20, 30]
  LOAD 15 in offset 1
[IP: 68: FP: 0]   PRINT 15
[IP: 69: FP: 0] Stack (SP=5, FP=0): [0, 15, 100, 20, 30]
  LOAD 20 in offset 3
[IP: 71: FP: 0]   PRINT 20
[IP: 72: FP: 0] Stack (SP=5, FP=0): [0, 15, 100, 20, 30]
  LOAD 30 in offset 4
[IP: 74: FP: 0]   PRINT 30
[IP: 75: FP: 0]   PUSH val 0
[IP: 77: FP: 0]   HALT 

Время выполнения ВМ: 0.322000 мс

вдруг кому-то будет интересно, стек-фреймы геморны в понимании при перехое из глобальной концепции

Зарегистрируйтесь на Хабре, чтобы оставить комментарий