Special Compiler Olympics

[love5an]

Оказывается в ЖЖ время от времени проходят специальные олимпиады на тему погромирования:
http://metaclass.livejournal.com/662100.html

Там по ссылке, правда, какая-то скучная, унылая, энтерпрайз-олимпиада.

А вот я предлагаю такую:

Я тут написал игрушечную виртуальную RISC-машину с некоторой периферией.
Вернее, еще не дописал, но осталось совсем немного.

https://github.com/Lovesan/SpecialVM

Так вот, я предлагаю написать под нее рантайм и компилятор простого, игрушечного лиспа, похожего на Scheme.

Со сборщиком мусора, естественно, и всем таким прочим. Но, без арифметики с плавающей точкой, потому что в VM нет FPU :)

Короче, говоря: минимальные типы: symbol, cons, string, char, integer, ratio, vector, и, естественно, function.
Числа должны быть неограниченной точности(bignums).
Функции должны уметь замыкания. Естественно, область видимости должна быть лексической.
В стандартной библиотеке должны быть разные функции для сравнения, проверки на эквивалентность, конструирования объектов и т.п. - как в минимальной Scheme, вобщем. Естественно, должны быть define и присваивание (set!)

Минимальный синтаксис:

expression <- datum
              / LPAREN parenExpression
              / VLPAREN vectorList
parenExpression <- RPAREN
                   / DOT expression RPAREN
                   / expression parenExpression
vectorList <- RPAREN
              / expression vectorList
datum <- SYMBOL
         / STRING
         / CHAR
         / RATIO
         / INTEGER
         / QUOTE expression

LPAREN       <- [(] WS
RPAREN       <- [)] WS
DOT          <- [.] WS
QUOTE        <- ['] WS
STRING       <- ["]( !["] . )*["] WS
CHAR         <- '#\' .
INTEGER      <- SIGN? UINT WS
SIGN         <- [-+] WS
RATIO        <- INTEGER [/] UINT WS
UINT         <- [0-9]+ WS
SYMBOL       <- SYMBOL_START SYMBOL_CONT WS
SYMBOL_START <- [-+~/=@!$%^&*?<>A-Za-z] WS
SYMBOL_CONT  <- SYMBOL_START / [0-9] WS
WS           <- SPACE / COMMENT / ML_COMMENT
SPACE        <- [ \r\t\n]*
COMMENT      <- [;] ( ![\n\r] . )* 
ML_COMMENT   <- '#|' ( !'|#' . )* '|#'

Обратная кавычка, или, там, полноценный reader-алгоритм - на усмотрение.



Победитель будет определяться по результатам соотношения навороченности лиспа к производительности и объему используемой памяти, и получит почет, славу и уважение, а также печеньки.

Полная спецификация машины:

Вернее почти полная - на днях определюсь, к каким портам, и как, подключена периферия - дополню описание.

[ Из файла SVM.c, с репозитория на github ]

/*

Special [Olympics] VM is a 32 bit load/store RISC processor with some periphery.

Registers:

32 32-bit GPR.
IPR - instruction pointer; cannot be referenced directly.
FLR - flags register.
ARR - arithmetic register; contains overflows from MUL etc.
IRR - interrupt return register;
      holds address of instruction where interrupt has occurred;
IFLR - holds value of FLR before interrupt.

FLR layout: [ EQ | LT | GT | OV | IF | PG | ... ]
            0    1    2    3    4    5    6     31       
       ... = reserved

SVM has no FPU, because i'm too lazy to implement one.

Peripheral devices are managed through I/O ports.
`in' and `out' instructions handle port I/O.

Port mappings and hardware control will be described a bit later.

SVM has a MMU with support for paging. Pages are 1 MB in size.
loadpt instruction loads page table from physical address pointing to array of 4096 2-byte entries.
  First 12 bits of each entry is 1MB aligned physical address and bit 13 is a `present' flag.

SVM interrupt handler pointers are stored in 256-word long interrupt vector table(like in x86 real mode).
loadivt instruction loads IVT from physical address.
IVT entries point to physical addresses.

Interrupt mapping is fixed:

nonmaskable interrupts (exceptions):
0 division by zero
1 invalid instruction
2 page fault
3 double fault
4 alignment fault
5-15 reserved

maskable interrupts (can be disabled by IF FLR bit):
16 timer
17 keyboard
18 disk controller
19-31 reserved
32-255 free for use for other devices

Each instruction fits in 32-bit word.
load/store offsets must be aligned to byte/halfword/word addresses, or otherwise alignment fault will occur.

Instructions list:
(numbers are stored in LSB-first manner)

jump rDst  -- jump indirectly to absolute address
  NOTE: JUMP OFFSETS, unlike load/store data offsets ARE MEASURED IN WORD, NOT IN BYTES
[ 0 | rDst | 0 | ... ]
    5     10   11    

iret  -- jump to address in IRR register, restore FLR from IFLR and IPR from IRR
  NOTE: JUMP OFFSETS, unlike load/store data offsets ARE MEASURED IN WORDS, NOT IN BYTES
[ 0 | ... | 1 | ... ]
    5    10   11     

jumpr siOffset  -- jump to address relative to next instruction.
  NOTE: JUMP OFFSETS, unlike load/store data offsets ARE MEASURED IN WORDS, NOT IN BYTES
[ 1 | signed immediate ]
    5

jumpf flrBit rDst -- jump conditionally to absolute address.
  NOTE: JUMP OFFSETS, unlike load/store data offsets ARE MEASURED IN WORDS, NOT IN BYTES
[ 2 | FLR index | rDst | ... ]
    5           7      13

jumpfr flrBit siOffset -- jump conditionally to address relative to next insruction.
  NOTE: JUMP OFFSETS, unlike load/store data offsets ARE MEASURED IN WORDS, NOT IN BYTES
[ 3 | FLR index | signed immediate ]
    5           7

loadil rDst imm -- load immediate to low halfword of rDst.
[ 4 | rDst | 0 | ... | immediate ]
    5      10  14    16

loadilz rDst imm -- load immediate to low halfword of rDst with zero extension.
[ 4 | rDst | 1 | ... | immediate ]
    5      10  14    16

loadils rDst imm -- load immediate to low halfword of rDst with sign extension.
[ 4 | rDst | 2 | ... | immediate ]
    5      10  14    16

loadih rDst imm -- load immediate to high halfword of rDst.
[ 4 | rDst | 3 | ... | immediate ]
    5      10  14    16

loadihz rDst imm -- load immediate to high halfword of rDst while zeroing low halfword.
[ 4 | rDst | 4 | ... | immediate ]
    5     10   14

loadfl rSrc -- load FLR from rSrc.
[ 4 | rSRc | 5 | ... ]
    5     10   14

loadar rSrc -- load ARR from rSrc.
[ 4 | rSrc | 6 | ... ]
    5      10  14

loadivt rSrc -- load iterrupt vector table from address contained in rSrc.
[ 4 | rSrc | 7 | ... ]
    5      10  14

loadpt rSrc -- load page table from address contained in rSrc.
[ 4 | rSrc | 8 | ... ]
    5      10  14

loadb rDst rBase siOffset -- load byte from [rBase + siOffset] into low byte of rDst.
[ 5 | rDst | rBase | 0 | signed immediate ]
    5      10      15  18

loadbz rDst rBase siOffset -- load byte from [rBase + siOffset] into low byte of rDst with zero extension.
[ 5 | rDst | rBase | 1 | signed immediate ]
    5      10      15  18

loadbs rDst rBase siOffset -- load byte from [rBase + siOffset] into low byte of rDst with sign extension.
[ 5 | rDst | rBase | 2 | signed immediate ]
    5      10      15  18

loadh rDst rBase siOffset -- load halfword from [rBase + siOffset] into low halfword of rDst.
[ 5 | rDst | rBase | 3 | signed immediate ]
    5      10      15  18

loadhz rDst rBase siOffset --load halfword from [rBase + siOffset] into low halfword of rDst with zero extension.
[ 5 | rDst | rBase | 4 | signed immediate ]
    5      10      15  18

loadhs rDst rBase siOffset --load halfword from [rBase + siOffset] into low halfword of rDst with sign extension.
[ 5 | rDst | rBase | 5 | signed immediate ]
    5      10      15  18

loadw rDst rBase siOffset -- load word from [rBase + siOffset] into rDst.
[ 5 | rDst | rBase | 6 | signed immediate ]
    5      10      15  18

loadrb rDst siOffset -- load byte from [next IP + siOffset] into low byte of rDst.
[ 6 | rDst | 0 | signed immediate ]
    5      10  13 

loadrbz rDst siOffset -- load byte from [next IP + siOffset] into low byte of rDst with zero extension.
[ 6 | rDst | 1 | signed immediate ]
    5      10  13 

loadrbs rDst siOffset -- load byte from [next IP + siOffset] into low byte of rDst with sign extension.
[ 6 | rDst | 2 | signed immediate ]
    5      10  13 

loadrh rDst siOffset -- load halfword from [next IP + siOffset] into low halfword of rDst.
[ 6 | rDst | 3 | signed immediate ]
    5      10  13 

loadrhz rDst siOffset -- load halfword from [ next IP + siOffset ] into low halfword of rDst with zero extension.
[ 6 | rDst | 4 | signed immediate ]
    5      10  13

loadrhs rDst siOffset -- load halfword from [ next IP + siOffset ] into low halfword of rDst with sign extension.
[ 6 | rDst | 5 | signed immediate ]
    5      10  13

loadrw rDst siOffset -- load word from [ next IP + siOffset ] into rDst.
[ 6 | rDst | 6 | signed immediate ]
    5      10  13

storeb rSrc rBase siOffset -- store byte from rSrc into [ rBase + siOffset ].
[ 7 | rSrc | rBase | 0 | signed immediate ]
    5      10      15  17

storeh rSrc rBase siOffset -- store halfword from rSrc into [ rBase + siOffset ].
[ 7 | rSrc | rBase | 1 | signed immediate ]
    5      10      15  17

storew rSrc rBase siOffset -- store word from rSrc into [ rBase + siOffset ].
[ 7 | rSrc | rBase | 2 | signed immediate ]
    5      10      15  17

storefl rDst -- store FLR into rDst.
[ 7 | rDst | ... | 3 | ... ]
    5      10    15  17

storerb rSrc siOffset -- store byte from rSrc into [ next IP + siOffset ].
[ 8 | rSRc | 0 | signed immediate ]
    5      10  12 

storerh rSrc siOffset -- store halfword from rSrc into [ next IP + siOffset ].
[ 8 | rSRc | 1 | signed immediate ]
    5      10  12

storerw rSrc siOffset -- store word from rSrc into [ next IP + siOffset ].
[ 8 | rSRc | 2 | signed immediate ]
    5      10  12

storear rDst -- store ARR into rDst.
[ 8 | rDst | 3 |  ... ]
    5      10  12

in rDst rPort -- input word from port designated by rPort into rDst.
[ 9 | rDst | rPort | 0 | ... ]
    5      10      15 16

in rDst uiPort -- input word from port designated by uiPort into rDst.
[ 9 | rDst | ... | 1 | unsigned immediate ] 
    5      10    15  16

out rSrc rPort -- output word from rSrc into port designated by rPort.
[ 10 | rSrc | rPort | 0 | ... ]
     5      10      15  16

out rSrc uiPort -- output word from rSrc into port designated by uiPort.
[ 10 | rSrc | ... | 1 | unsigned immediate ]
     5      10    15  16

neg rDst rSrc -- negate signed word from rSrc and store result in rDst.
[ 11 | rDsr | rSrc | ... ]
     5      10     15

add  rDst rSrc1 rSrc2 -- add rSrc1 to rSrc2 and store result in rDst.
  This instruction sets OV flag to 1 on overflow and 0 otherwise.
[ 12 | rDst | rSrc1 | rSrc2 | 0 | ... ]
     5      10     15       20  22

addc rDst rSrc1 rSrc2 -- add rSrc1 to rSrc2 with carrying(i.e. OV) and store result in rDst
  This instruction sets OV flag to 1 on overflow and 0 otherwise.
[ 12 | rDst | rSrc1 | rSrc2 | 1 | ... ]
     5      10     15       20  22

sub rDst rSrc1 rSrc2 -- subtract rSrc2 from rSrc1 and store result in rDst.
  This instruction sets OV flag to 1 on overflow and 0 otherwise.
[ 12 | rDst | rSrc1 | rSrc2 | 2 | ... ]
     5      10     15       20  22

sub rDst rSrc1 rSrc2 -- subtract rSrc2 from rSrc1 with carrying(i.e. OV) and store result in rDst.
  This instruction sets OV flag to 1 on overflow and 0 otherwise.
[ 12 | rDst | rSrc1 | rSrc2 | 3 | ... ]
     5      10     15       20  22

mul rDst rSrc1 rSrc2 -- multiply signed words from rSrc1 and rSrc2.
  Store lower 32 bits in rDst and high 32 bits in ARR.
  This instruction sets OV flag to 1 on overflow and 0 otherwise.
[ 13 | rDst | rSrc1 | rSrc2 | 0 | ... ]
     5      10      15      20  22

mulu rDst rSrc1 rSrc2 -- multiply unsigned words from rSrc1 and rSrc2.
  Store lower 32 bits in rDst and high 32 bits in ARR.
  This instruction sets OV flag to 1 on overflow and 0 otherwise.
[ 13 | rDst | rSrc1 | rSrc2 | 1 | ... ]
     5      10      15      20  22

div rDst rSrc1 rSrc2 -- divide signed 64-bit word from ARR:rSrc1 by signed word in rSrc2.
  Store quotient in rDst and remainder in ARR.
  This instruction sets OV flag to 1 on overflow and 0 otherwise.
  This instruction can cause division by zero interrupt.
[ 13 | rDst | rSrc1 | rSrc2 | 2 | ... ]
     5      10      15      20  22

divu rDst rSrc1 rSrc2 -- divide unsigned 64-bit word from ARR:rSrc1 by unsigned word in rSrc2.
  Store quotient in rDst and remainder in ARR.
  This instruction sets OV flag to 1 on overflow and 0 otherwise.
  This instruction can cause division by zero interrupt.
[ 13 | rDst | rSrc1 | rSrc2 | 3 | ... ]
     5      10      15      20  22

cmp rSrc1 rSrc2 -- compare signed word from rSrc1 to signed word from rSrc2 and set FLR bits.
[ 14 | rSrc1 | rSrc2 | 0 | ... ]
     5       10      15  16

cmpu rSrc1 rSrc2 -- compare unsigned word from rSRc1 to unsigned word from rSRc2 and set FLR bits
[ 14 | rSrc1 | rSrc2 | 1 | ... ].
     5       10      15  16

not rDst rSrc -- bitwise complement rSrc and store result in rDst.
[ 15 | rDst | rSrc | ... ]
     5      10     15

and rDst rSrc1 rSrc2 -- perform bitwise and on operands from rSrc1 and rSrc2 and store result in rDst.
  First 4 bits of FLR is cleared then EQ bit is set according to sources.
[ 16 | rDst | rSRc1 | rSrc2 | ... ]
     5      10      15      20

or rDst rSrc1 rSrc2 -- perform bitwise or on operands from rSrc1 and rSrc2 and store result in rDst.
  First 4 bits of FLR is cleared then EQ bit is set according to sources.
[ 17 | rDst | rSRc1 | rSrc2 | ... ]
     5      10      15      20

xor rDst rSrc1 rSrc2 -- perform bitwise xor on operands from rSrc1 and rSrc2 and store result in rDst.
  First 4 bits of FLR is cleared then EQ bit is set according to sources.
[ 18 | rDst | rSrc1 | rSrc2 | ... ]
     5      10      15      20

shl rDst rSrc1 rSrc2 -- shift unsigned rSrc1 left according to first 6 bits of rSrc2 and store results in rDst.
[ 19 | rDst | rSrc1 | rSRc2 | 0 | ... ]
     5      10      15      20  22

shli rDst rSrc uiShift -- shift unsigned rSrc left according to uiShift and store results in rDst.
[ 19 | rDst | rSrc | ... | 1 | uiShift | ... ]
     5      10     15    20  22        28

sal rDst rSrc1 rSrc2 -- shift signed rSrc1 left according to first 6 bits of rSrc2 and store results in rDst.
  Shifted bits are stored in ARR.
  OV is set according to result.
[ 19 | rDst | rSrc1 | rSRc2 | 2 | ... ]
     5      10      15      20  22

sali rDst rSrc uiShift -- shift signed rSrc left according to uiShift and store results in rDst.
  Shifted bits are stored in ARR.
  OV is set according to result.
[ 19 | rDst | rSrc | ... | 3 | uiShift | ... ]
     5      10     15    20  22        28

shr rDst rSrc1 rSrc2 -- shift unsigned rSrc1 right according to first 6 bits of rSrc2 and store results in rDst.
[ 20 | rDst | rSrc1 | rSRc2 | 0 | ... ]
     5      10      15      20  22

shri rDst rSrc uiShift -- shift unsigned rSrc right according to uiShift and store results in rDst.
[ 20 | rDst | rSrc | ... | 1 | uiShift | ... ]
     5      10     15    20  22        28

sar rDst rSrc1 rSrc2 -- shift signed rSrc1 right according to first 6 bits of rSrc2 and store results in rDst.
  Shifted bits are stored in ARR.
[ 20 | rDst | rSrc1 | rSRc2 | 2 | ... ]
     5      10      15      20  22

sari rDst rSrc uiShift -- shift signed rSrc right according to uiShift and store results in rDst.
  Shifted bits are stored in ARR.
[ 20 | rDst | rSrc | ... | 3 | uiShift | ... ]
     5      10     15    20  22        28

halt -- halts processor execution until interrupt occurs.
[ 21 | ... ]
     5

*/

Comments

[dmitry-vk.livejournal.com]

Забавно-забавно.
0) Совсем иной уровень контеста, я должен сказать. Конечно, оргвопросы:
0.1) сроки? Очевидно же, что это дело не одних выходных (как у _darkus_)
0.2) как оцениваться будет? По бенчмаркам, субъективно, какие-то более четкие критерии?
1) Надо писать kernelspace + userland или только userland? Как программа попадает в SVM и запускается? Откуда берет память? Куда идет IO? Есть ли ФС? Ну т.е., нужны подробности о запуске программ, взаимодействии с ОС/железом и т.п., а не только спека на CPU.
2) Компилятор работать внутри SVM или предполагается кросскомпиляция?
2) Для этой VM надо будет писать инструментацию (хотя бы пошаговый отладчик с просмотром состояния и дамп/восстановление). Не очень-то хорошо/удобно все это писать каждому участнику.

[love5an.livejournal.com]

0.1) Ну, я бы не стал ставить какие-то четкие сроки пока. А какие будут предложения на эту тем?
0.2) По бенчмаркам, плюс объему кода, скорее всего. И, наверное, отчасти субъективно, по фичастости рантайма.

1) В процессоре практически нету механизмов защиты памяти, кроме страниц. Т.е. разделения на юзерспейс и кернел-спейс нет(да оно и не нужно для языков с управляемой памятью).

Программа будет запускаться из первого сектора(512 байт) первого диска, а потом делать что угодно.

Память берется из malloc, выделяется при старте, и указывается при запуске; в мегабайтах; по дефолту 32 МБ.

IO идет в порты, а через них - в консоль(через простой эмулятор экрана) и в диски(и чрез них в файлы). М.б. еще будут устройства. Загрузочный диск поставляется участником. М.б. и другие диски тоже(максимум поддерживается 4), но не уверен.

ФС соответственно, на дисках по усмотрению. М.б. и никакой ФС и не быть. Но я пока подумаю, как запускать бенчмарки - м.б. будет один диск с FAT-системой с кодом или что-либо в этом роде. М.б. бенчмарки будут получаться из портов :)

Попозже еще подробнее опишу "железо".

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

3) Да, надо бы написать инструментов. Сейчас там уже есть поддержка логгирования разнообразных вещей, м.б. еще будет что-либо. Форк репозитория и добавление фич только приветствуется, кстати.

[yoschi.livejournal.com]

Я думаю, участников соберётся полтора человека. Во-первых, не так уж много людей, способных это написать в свободное время, а во-вторых, не так уж много среди них согласится это делать за печеньки, к тому же, не гарантированные :о)

[love5an.livejournal.com]

Это, наверное, да :)