Oberon space
General Category => Общий раздел => Тема начата: X512 от Январь 14, 2013, 04:38:00 am
-
У меня давно уже есть идея написать компилятор обероноподобного языка. Как писать лексер и парсер в принципе понятно, но где брать информацию о машинном коде x86 не совсем. Где можно найти информацию о генерации кода для x86? Документации Intel - слишком сложно, я на ассемблере почти не писал. Пока у меня есть своя стековая виртуальная машина и ассемблер для неё; программы выглядят как-то так
PROCEDURE^ Sort (8)
PROCEDURE Main
VAR a, len, i (* все переменные только INTEGER *)
CODE
STK a ->
5345235 -436 235 235 4 -53254 235 23 34 -325 342 523 35523 (* массив для сортировки *)
STK a& - 4 DIV len ->
a& PRINT len& PRINT -10000 PRINT
a& len& Sort!
0 i ->
:l i& len& < e?
a& i& 4 * + ^ PRINT
i& 1 + i ->
l@
:e
END Main
(*
Спецификация ассемблерного кода ниже
PROCEDURE Sort(VAR a: ARRAY OF INTEGER);
VAR i, j: INTEGER; x, t: INTEGER;
BEGIN
i := 0; j := LEN(a)-1;
x := a[(LEN(a)-1) DIV 2];
REPEAT
WHILE a[i] < x DO INC(i) END;
WHILE x < a[j] DO DEC(j) END;
IF i <= j THEN
t := a[i]; a[i] := a[j]; a[j] := t;
INC(i); DEC(j)
END
UNTIL i > j;
IF 0 < j THEN Sort(SPLIT(a, 0, j+1)) END;
IF i < LEN(a)-1 THEN Sort(SPLIT(a, i, LEN(a))) END
END Sort.
*)
PROCEDURE Sort(len, a)
VAR i, j, x, t
CODE
0 i -> len& 1 - j ->
len& 1 - 2 DIV 4 * a& + ^ x ->
:l1 a& i& 4 * + ^ x& < l2?
i& 1 + i ->
l1@
:l2 x& a& j& 4 * + ^ < l3?
j& 1 - j ->
l2@
:l3 i& j& <= l4?
a& i& 4 * + ^ t ->
a& j& 4 * + ^ a& i& 4 * + =>
t& a& j& 4 * + =>
i& 1 + i ->
j& 1 - j ->
:l4 i& j& > l1?
0 j& < l5?
a& j& 1 + Sort!
:l5 i& len& 1 - < l6?
i& 4 * a& + len& i& - Sort!
:l6
END Sort
SPLIT(array: ANYARR; beg, end: INTEGER): ANYARR - это встроенная функция моего языка для выделения подмассива.
-
1. В Интеле 3 режима: 16-битный, 32-битный, 64-битный.
2. Коды - это не самое сложное. В какой оси хотите работать? От этого зависит структура объектного-исполняемого файла.
3. Гораздо проще перевести в программу на ассемблере и запустить уже стандартный механизм формирования исполняемого модуля.
-
1. В Интеле 3 режима: 16-битный, 32-битный, 64-битный.
Мне нужен 32-х битный режим.
2. Коды - это не самое сложное. В какой оси хотите работать? От этого зависит структура объектного-исполняемого файла.
У меня проблема именно с кодами. Формат у меня будет свой, похожий на формат BlackBox'а. С этим проблем нет. Я уже писал свой загрузчик модулей PE и ocf(Oberon Code File, формат скомпилированных модулей BlackBox-а), ничего сложного там нет. Работать предполагается в Windows и Haiku (http://www.haiku-os.org/).
3. Гораздо проще перевести в программу на ассемблере и запустить уже стандартный механизм формирования исполняемого модуля.
Мне нужно генерировать машинный код напрямую. Руководств и примеров написания компиляторов в ассемблер в сети видел много, а вот с машинными кодами не густо. Нашёл только TCC (http://bellard.org/tcc/).
-
У меня проблема именно с кодами. Формат у меня будет свой, похожий на формат BlackBox'а. С этим проблем нет. Я уже писал свой загрузчик модулей PE и ocf(Oberon Code File, формат скомпилированных модулей BlackBox-а), ничего сложного там нет. Работать предполагается в Windows и Haiku (http://www.haiku-os.org/).
Круто! (я про Haiku). Моя любимая оська :-) Хотя BeOS была в свое время еще более любимой.
Помнится лет 5 назад я пытался туда перетащить Pow!, но не осилил.
-
Помнится лет 5 назад я пытался туда перетащить Pow!, но не осилил.
Это что? Google не умеет индексировать восклицательные знаки, так что не нашёл...
-
Помнится лет 5 назад я пытался туда перетащить Pow!, но не осилил.
Это что? Google не умеет индексировать восклицательные знаки, так что не нашёл...
Умеет, если заковычить строку.
http://www.fim.uni-linz.ac.at/pow/pow.htm
-
У меня давно уже есть идея написать компилятор обероноподобного языка. Как писать лексер и парсер в принципе понятно, но где брать информацию о машинном коде x86 не совсем. Где можно найти информацию о генерации кода для x86?
Ну я делал так: писал интересующий меня код на ассемблере, транслировал и смотрел в шестнадцатиричном редакторе, что сгенерировал ассемблер.
-
Какая-то странная логика у операций деления и умножения. Они почему-то работают с разными размерами и возвращают значение в фиксированные регистры. Как эффективно выделять регистры - непонятно. Посмотрел, что выдаёт GCC на выражение ((a+b+c)/(b-d))/((c-a)/(d*4-a)):
t = dword ptr -8
a = dword ptr 8
b = dword ptr 0Ch
c = dword ptr 10h
d = dword ptr 14h
push ebp
mov ebp, esp
push ebx
sub esp, 4
mov eax, [ebp+b] ; EAX := b
mov edx, [ebp+a] ; EDX := a
add edx, eax ; INC(EDX, EAX)
mov eax, [ebp+c] ; EAX := c
add eax, edx ; INC(EAX) + EDX
mov edx, [ebp+d] ; EDX := d
mov ecx, [ebp+b] ; ECX := b
mov ebx, ecx ; EBX := ECX
sub ebx, edx ; DEC(EBX, EDX)
mov [ebp+t], ebx ; t := EBX
idiv [ebp+t] ; EAX := EDX:EAX DIV [ebp+t]; EDX := EDX:EAX MOD [ebp+t];
mov ecx, eax ; ECX := EAX
mov eax, [ebp+a] ; EAX := a
mov edx, [ebp+c] ; EDX := c
mov ebx, edx ; EBX := EDX
sub ebx, eax ; DEC(EBX, EAX)
mov eax, ebx ; EAX := EBX
mov edx, [ebp+d] ; EDX := d
shl edx, 2 ; EDX := EDX*4
mov ebx, edx ; EBX := EDX
sub ebx, [ebp+a] ; DEC(EBX, a)
mov [ebp+t], ebx ; t := EBX
cdq ; EDX:EAX := EAX
idiv [ebp+t] ; EAX := EDX:EAX DIV [ebp+t]; EDX := EDX:EAX MOD [ebp+t];
mov [ebp+t], eax ; t := EAX
mov eax, ecx ; EAX := ECX
cdq ; EDX:EAX := EAX
idiv [ebp+t] ; EAX := EDX:EAX DIV [ebp+t]; EDX := EDX:EAX MOD [ebp+t];
add esp, 4
pop ebx
pop ebp
retn
Выходит он просто временную переменную заводит. Регистр нельзя?
Я предполагал такую архитектуру компилятора: сначала компилятор в лоб в один проход генерирует модуль с процедурами в формате стековой машины. Кроме процедур компилятор генерирует таблицу символов и метаинформацию. Потом этот модуль даётся оптимизатору. Он выдаёт эквивалентный модуль в том же формате, но оптимизированный. Оптимизатор платформо-независим и прозрачно интегрируется в цепочку компиляции и может быть убран или заменён при необходимости. Пока оптимизатора не будет. Затем оптимизированный модуль даётся "рекомпилятору", который конвертирует процедуры из стековой машины в машинный код i386.
Рекомпилятор поддерживает стек регистров примерно так:
stack machine program:
1 2 3 4 5 6 7 + + + + + +
x86 code:
mov eax, 1 ; eax
mov ebx, 2 ; eax, ebx
mov ecx, 3 ; eax, ebx, ecx
mov edx, 4 ; eax, ebx, ecx, edx
push eax
mov eax, 5 ; s[0], ebx, ecx, edx, eax
push ebx
mov ebx, 6 ; s[0], s[1], ecx, edx, eax, ebx
add ebx, 7 ; s[0], s[1], ecx, edx, eax, ebx
add eax, ebx ; s[0], s[1], ecx, edx, eax
add edx, eax ; s[0], s[1], ecx, edx
add ecx, edx ; s[0], s[1], ecx
pop ebx ; s[0], ebx, ecx
add ebx, ecx ; s[0], ebx
pop eax ; eax, ebx
add eax, ebx ; eax
Понятно, что исходная программа легко оптимизируется перестановкой и перегруппировкой слагаемых, но она специально составлена для демонстрации переполнения регистрового стека.
Но операции умножения и деления ломают этот механизм.
Также рекомпилятор должен уметь распознавать режимы адресации, используемые в x86:
stack machine
len& 1 - 2 DIV 4 * a& + ^ x ->
C:
x = a[(len-1)/2];
direct recompilation:
mov eax, [ebp+len] ; len len&
dec eax ; len len& 1 -
shr eax, 1 ; len len& 1 - 2 DIV
shl eax, 2 ; len len& 1 - 2 DIV 4 *
mov ebx, [ebp+a] ; len len& 1 - 2 DIV 4 * a&
add eax, ebx ; len len& 1 - 2 DIV 4 * a& +
mov eax, [eax] ; len len& 1 - 2 DIV 4 * a& + ^
mov [ebp+x], eax ; ~ len len& 1 - 2 DIV 4 * a& + ^ x ->
addressing modes detection:
mov eax, [ebp+len] ; len len&
dec eax ; len len& 1 -
shr eax, 1 ; len len& 1 - 2 DIV
mov ebx, [ebp+a] ; len len& 1 - 2 DIV &a
mov eax, [eax*4+ebx] ; len len& 1 - 2 DIV 4 * a& + ^
-
Не дописал последнюю строчку кода:
mov [ebp+x], eax ; ~ len len& 1 - 2 DIV 4 * a& + ^ x ->
-
Смотрю что выводит GCC и удивляюсь: почему так неэффективно? Или это какая-то магия с выравниванием кода и кэшем? Чувствую, что мой компилятор даже без модуля оптимизации обгонит GCC... А с модулем вообще всё обгонит :)
-
1. Распоределение регистров - стандартный алгоритм раскраски графов. Ершов в сое время решил эту задачу. Сейчас этот алгоритм применяется везде практически. И даже в учебниках по компиляторам описан.
В книжке Робина Хантера, например: http://www.ozon.ru/context/detail/id/1304237/
2. Чтобы сгенеировать правильно метод адресации, вам надо разобраться с байтом modR/M - это можно посмотреть, например, в книжке Григорьева по 486 процессору. Или в книжках по защищенному режиму 386 процессора.
-
1. Распоределение регистров - стандартный алгоритм раскраски графов. Ершов в сое время решил эту задачу. Сейчас этот алгоритм применяется везде практически. И даже в учебниках по компиляторам описан.
В книжке Робина Хантера, например: http://www.ozon.ru/context/detail/id/1304237/
Рекомпилятор должен быть простым, поэтому такие сложные оптимизации в нём не допустимы. Допустимы только оптимизации кода стековой машины. Там нет никаких регистров и распределять нечего.
-
Это не оптимизации - это стандартный алгоритм распределения регистров.
Который нормально работает.
Количество регистров - это и есть количество красок.
А алгоритм раскраски распределяет их так, чтобы один и тот же регистр не использовался "рядышком"... :)
-
Посмотрел, что выдаёт GCC на выражение ((a+b+c)/(b-d))/((c-a)/(d*4-a)):
В A2 есть декодеры объектных файлов, что очень удобно. Если в файловом менеджере щелкнуть по скомпилированному модулю, то откроется спец окно.
Например для процедуры Do
MODULE Test;
VAR
x,a,b,c,d: LONGINT;
PROCEDURE Do*;
BEGIN
x := ((a+b+c) DIV (b-d)) DIV ((c-a) DIV (d*4-a))
END Do;
END Test.
сформирован следующий код:
Do:
codeOffset = 00000007H
00000007H 55 PUSH EBP
00000008H 89 E5 MOV EBP, ESP
0000000AH 8B 3D F8 FF FF FF MOV EDI, [-8]
00000010H 03 3D F4 FF FF FF ADD EDI, [-12]
00000016H 03 3D F0 FF FF FF ADD EDI, [-16]
0000001CH 8B 35 F4 FF FF FF MOV ESI, [-12]
00000022H 2B 35 EC FF FF FF SUB ESI, [-20]
00000028H 81 FE 00 00 00 00 CMP ESI, 0
0000002EH 0F 8F 03 00 00 00 JNLE 3 (00000037H)
00000034H 6A 0C PUSH 12
00000036H CC INT 3
00000037H 89 F8 MOV EAX, EDI
00000039H 99 CDQ
0000003AH F7 FE IDIV ESI
0000003CH D1 E2 SHL EDX, 1
0000003EH 83 D8 00 SBB EAX, 0
00000041H 89 C7 MOV EDI, EAX
00000043H 8B 35 F0 FF FF FF MOV ESI, [-16]
00000049H 2B 35 F8 FF FF FF SUB ESI, [-8]
0000004FH 8B 1D EC FF FF FF MOV EBX, [-20]
00000055H C1 E3 02 SHL EBX, 2
00000058H 2B 1D F8 FF FF FF SUB EBX, [-8]
0000005EH 81 FB 00 00 00 00 CMP EBX, 0
00000064H 0F 8F 03 00 00 00 JNLE 3 (0000006DH)
0000006AH 6A 0C PUSH 12
0000006CH CC INT 3
0000006DH 89 F0 MOV EAX, ESI
0000006FH 99 CDQ
00000070H F7 FB IDIV EBX
00000072H D1 E2 SHL EDX, 1
00000074H 83 D8 00 SBB EAX, 0
00000077H 89 C6 MOV ESI, EAX
00000079H 81 FE 00 00 00 00 CMP ESI, 0
0000007FH 0F 8F 03 00 00 00 JNLE 3 (00000088H)
00000085H 6A 0C PUSH 12
00000087H CC INT 3
00000088H 89 F8 MOV EAX, EDI
0000008AH 99 CDQ
0000008BH F7 FE IDIV ESI
0000008DH D1 E2 SHL EDX, 1
0000008FH 83 D8 00 SBB EAX, 0
00000092H 89 C7 MOV EDI, EAX
00000094H 89 3D FC FF FF FF MOV [-4], EDI
0000009AH 89 EC MOV ESP, EBP
0000009CH 5D POP EBP
0000009DH C3 RET