Часть 3. Первые шаги

[thedeemon]

Итак, получив работающую виртуальную машину, я принялся за написание компилятора снизу-вверх. Первым делом система команд ВМ была описана в виде набора типов:

type dst = RegDest of int | PntDest of int;; 
type src = Reg of int | Pnt of int | Val of int;; 
 
type 'loc command =  
  | Arith of oper * dst * src * src 
  | Mov of dst * src 
  | Movb of dst * src 
  | Jmple of 'loc * src * src 
  | Jmpeq of 'loc * src * src 
  | Jmp of 'loc 
  | Print of src 
...

Сделал вывод ее в текст в форме, которую можно вставить в текст на Си: int prg[] = { ... };
Тут оказался очень полезен окамловский паттерн-матчинг, особенно когда появились команды, являющиеся частными случаями других:

let cmd_to_text = function 
  | Arith(Add, RegDest dr, Reg r1, Val 1) when dr = r1 -> Printf.sprintf "INC, %d, 0, 0,\n" dr   
  | Arith(Add, RegDest dr, Reg r1, Val 4) when dr = r1 -> Printf.sprintf "INC4, %d, 0, 0,\n" dr    
  | Arith(Add, RegDest dr, Reg r1, Val v2) -> Printf.sprintf "ADD_RRV, %d, %d, %d,\n" dr r1 v2   
  | Arith(Add, RegDest dr, Reg r1, Reg r2) -> Printf.sprintf "ADD_RRR, %d, %d, %d,\n" dr r1 r2   
  | Arith(op, d, a1, a2) -> Printf.sprintf "%s|%c%c%c, %d, %d, %d,\n" (oper_s op) (dst_pr d) (src_pr a1) (src_pr a2) (dst_n d) (src_n a1) (src_n a2)   
  | Mov(RegDest dr, Reg r1) -> Printf.sprintf "MOV_RR, %d, %d,\n" dr r1 
  | Mov(RegDest dr, Val v1) -> Printf.sprintf "MOV_RV, %d, %d,\n" dr v1 
  | Mov(d, a1) -> Printf.sprintf "MOV|%c%cR, %d, %d,\n" (dst_pr d) (src_pr a1) (dst_n d) (src_n a1) 
...

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

type name = string 
type code = statement list 
and statement =  
  | Arith of oper * dst * src * src 
  | Mov of dst * src 
... 
  | Call of name * int 
  | Defun of name * code 
  | If of condition * code * code 
  | While of condition * code 
... 
 
and condition =  
  | Less of code * src * code * src 
  | Eq of code * src * code * src 
  | And of condition * condition 
  | Or of condition * condition 
  | Not of condition 

Теперь чтобы описать цикл или условие не нужно расставлять метки и делать на них переходы, можно их записать в таком структурированном виде. Условия состоят из сравнений А < Б, А = Б и их комбинаций. Сравнения содержат код вычисления аргументов и сами аргументы. Такой древовидный ассемблер (tree-like asm) получил название Трясм. Он компилировался в описанный ранее обычный Асм. Схематично:

If (A_Computation, A) < (B_Computation, B) then Code1 else Code2

превращается в

A_Computation
B_Computation
Jmple Then_Label A B
Code2
Jmp End_Label
Then_Label: Code1
End_Label.

If Not cond then Code1 else Code2

превращается в

If cond then Code2 else Code1.

If And cond1 cond2 then Code1 else Code2

превращается в что-то вроде

If cond1 then
 If cond2 then
  Code1
 else
  Else_Label: Code2
else
 goto Else_Label

и т.д.
Поскольку у условий частенько вторая альтернатива пустая (например, у циклов), часто в результате компиляции условий и циклов получались последовательности из безусловных переходов JMP A; A: JMP B; B: JMP C. Чтобы не генерить такой позорный код, в модуле Асм было сделано специальное оптимизирующее преобразование, которое для переходов и вызовов находило их конечную цель (метку) и ставило ее в исходную команду перехода или вызова. При этом получилось, что есть куски кода, куда управление никогда не попадает, т.к. исполнитель их перепрыгивает. Поэтому было добавлено dead code elimination:

let remove_dead_code prg = 
  let labels = label_indices prg in 
  let live = Array.make (DynArray.length prg) false in 
  let threads = Queue.create () in 
  Queue.add 0 threads; 
  let rec go ip = 
    if ip >= DynArray.length prg || live.(ip) then () else 
      (live.(ip) <- true; 
      match DynArray.get prg ip with 
      | Jmp lab -> let target = M.find lab labels in 
                   if target = ip + 1 then (live.(ip) <- false; go (ip+1)) else Queue.add target threads 
      | Ret -> () 
      | Jmple(lab, _, _) | Call(lab, _)    
      | Jmpeq(lab, _, _) -> Queue.add (M.find lab labels) threads; go (ip+1) 
      | _ -> go (ip+1)) in         
  while not (Queue.is_empty threads) do 
    go (Queue.take threads) 
  done; 
  prg |> DynArray.enum |> Enum.mapi (fun i cmd -> live.(i), cmd)  
  |> Enum.filter_map (fun (live, cmd) -> if live then Some cmd else None) |> DynArray.of_enum;;   

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

Трясм позволил писать структурированные программы, но все еще требовал ручного указания номеров регистров и разбиения арифметических выражений на серии простых действий. Поэтому следующим шагом повышения уровня было введение переменных и древовидных арифметических выражений. Это уже напоминало Си, поэтому следующий уровень был назван LeoC. Его структура:

type code = statement list 
and statement =  
  | DefVar of name (* определить локальную переменную (все переменные - инты, но могут содержать указатели) *) 
  | Assign of lvalue * rvalue (* копирование инта *) 
  | Assignb of lvalue * rvalue (* копирование одного байта *) 
  | Call of name * rvalue list (* вызов функции по имени со списком значений аргументов *) 
  | Defun of name * name list * code (* определение функции *) 
  | Ret of rvalue list (* возврат из функции набора значений *) 
  | If of condition * code * code  
  | While of condition * code 
  | Print of rvalue 
  | Alloc of lvalue * rvalue (* выделение памяти *) 
  | Comp of code   (* составной оператор *) 
  | Break (* прерывание цикла *) 
   
(* куда можно писать: в переменную, в память по указателю в переменной, в заданный регистр *) 
and lvalue = Local of name | PLocal of name | LReg of int  
 
and rvalue =  (* какие бывают значения: *) 
  | Var of name (* значение переменной *) 
  | Val of int (* число *) 
  | Arith of oper * rvalue * rvalue (* результат арифметической операции *) 
  | FCall of name * rvalue list (* вызов функции *) 
  | PVar of name (* обращение по указателю в переменной *) 
  | Byte of rvalue (* взятие одного байта из инта *) 
  | PArith of oper * rvalue * rvalue (* обращение по адресу, вычисленному арифметической операцией *) 
 
and condition =  
  | Less of rvalue * rvalue 
  | Eq of rvalue * rvalue 
  | And of condition * condition 
  | Or of condition * condition 
  | Not of condition 

Программа на LeoC компилировалась в Трясм путем рекурсивного обхода с протаскиванием контекста. Контекст содержал Map с именами описанных переменных и назначенных им регистров (вернее, смещений от FP), и Set с индексами занятых регистров. Если встречалось описание переменной, то находилось минимальное натуральное число, не входящее во множество занятых регистров, и назначалось этой переменной, добавляясь в то множество. Если компилировалось арифметическое выражение, то выбирался свободный регистр, помечался как занятый и использовался как назначение в арифметической операции. Результатом компиляции любого значения (rvalue) был не только код (список Triasm.statement'ов), но и значение типа src, говорящее где искать значение вычисленного выражения, когда оно понадобится:

type src = Tmp of int | TmpPnt of int | Src of Asm.src 

Значение может быть либо константой, либо храниться в регистре с некоторым номером, либо по указателю в таком регистре. Кроме того, оно может быть или условно постоянным (в описанной переменной), или временным. Временное значение используется один раз (например, в выражении a*b+c результат a*b должен быть записан в какой-то регистр, и тут же однократно использован). После использования временного значения соответствующий регистр убирается из множества занятых.

Компиляция определения функции довольно прямолинейна, только при этом еще запоминается число аргументов и возвращаемых значений, чтобы при вызове функции было ясно сколько места для них отводить. При компиляции вызова во множестве занятых регистров находился максимальный индекс, к нему прибавлялся максимум из числа аргументов и возвращаемых значений функции, это число становилось аргументом команды Call - смещением, на которое будет сдвинут FP. При компиляции оператора Ret возвращаемые значения, согласно описанному в предыдущей части соглашению о вызовах, сохранялись слева от FP вместо аргументов функции. Именно для этого в тип lvalue был добавлен вариант LReg, чтобы можно было обратиться по произвольному смещению. Если какие-то аргументы функции использовались при вычислении возвращаемых значений, то они сперва сохранялись во временных переменных.

Помимо собственно компиляции в Трясм, в модуле LeoC была реализована одна оптимизация - constant folding. Арифметические операции над константами заменялись их результатом:

and simp_rvalue = function 
  | Var _ as x -> x  
  | Val _ as x -> x 
  | Arith(Mul, Val a, Val b) -> Val (a * b)  
  | Arith(Add, Val a, Val b) -> Val (a + b)  
  | Arith(Sub, Val a, Val b) -> Val (a - b)  
  | Arith(Div, Val a, Val b) -> Val (a / b)  
  | Arith(Mod, Val a, Val b) -> Val (a mod b)  
  | Arith(Xor, Val a, Val b) -> Val (a lxor b)  
  | Arith(Add, rv1, Val 0) -> simp_rvalue rv1  
  | Arith(Add, Val 0, rv2) -> simp_rvalue rv2
  | Arith(Sub, rv1, Val 0) -> simp_rvalue rv1
  | Arith(Mul, rv1, Val 1) -> simp_rvalue rv1  
  | Arith(Mul, Val 1, rv2) -> simp_rvalue rv2  
  | Arith(Div, rv1, Val 1) -> simp_rvalue rv1  
  | Arith(op, rv1, rv2) ->  
...

Тут паттерн-матчинг опять оказался очень полезен.

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

  Defun("sumbytes", ["arr"; "len"], [ 
    DefVar "i"; 
    DefVar "sum"; 
    Assign(Local "i", Val 0); 
    Assign(Local "sum", Val 0); 
    While(Less(Var "i", Var "len"), [ 
      Assign(Local "sum", Arith(Add, Var "sum", Byte( PArith(Add, Var "arr", Var "i" ) ) )); 
      Assign(Local "i", Arith(Add, Var "i", Val 1)) 
    ]); 
    Ret [ Var "sum" ] 
  ]);   
  DefVar "m"; 
  Alloc(Local "m", Val 2); 
   
  Assignb(PLocal "m", Val 33); 
 
  DefVar "p"; 
  Assign(Local "p", Arith(Add, Var "m", Val 1)); 
  Assignb(PLocal "p", Val 44); 
   
  Print(FCall("sumbytes", [ Var "m"; Val 2 ]));

Дальше: Часть 4. ФВП, полиморфизм и вывод типов без матана

Comments

[udpn.livejournal.com]

Что я вижу:
1) Оптимизация на стадии разработки. Констант фолдинг и прочие оптимизации по одиночке дают краповое ускорение. 2*a+3*a ваш алгоритм не сфолдит. А f()+f() для чистой функции тем более.
2) Реквестирую condition для
bool a, b, c;
c = a And b;
По вашему определению он разбирать это не должен вообще, требуя < или >.
3) lvalue = Local of name | PLocal of name | LReg of int
ОЛОЛО?!?!

И ещё. Вот вы говорите о разработке сверху, снизу. Серебряные пули это всё. Разрабатывать надо в первую очередь логично, в лоичном порядке. А если выбирать бредоассемблеры и бредосинтаксисы по желанию своей левой ноги, получится как всегда. Язык задается не синтаксисом или платформой, а _идеей_. Вот какбы.

[thedeemon.livejournal.com]

1) Каждая оптимизации была продиктована теми косяками, которые появлялись как эффект от более высокоуровневых фич. Т.е., например, в одном месте генерились переходы без оглядки на наличие кода между ними, получался лишний код, от него сделана такая оптимизация. В другом месте генерились константные выражения типа 10+1-1 - когда считалась длина range'a или масива, а потом из нее вычислялась граница для цикла. Т.е. всегда сначала появлялась необходимость, потом делалась оптимизация. Но поскольку я описываю не совсем хронологически, то местами забегаю вперед. 2*a+3*a сам компилятор делать не будет, а в человеческих исходниках такое тоже вряд ли встретится. Тут оптимизации больше от косяков самого компилятора.

2) В Leo нет типа bool, нет и проблемы.

3) Ага. :) Но надо понимать, что на LeoC человек писать не будет, это лишь промежуточный слой внутри компилятора.

4) Для меня это был логичный порядок - постепенное повышение уровня. До этого, полгода назад, я пытался идти иначе - от AST исходного языка и понял, что не имею представления как от него двигаться дальше, разница в уровне его и ВМ была слишком большой.

Идея была, но она в самом Leo, а не описанном здесь LeoC, см. часть 0. Точнее не столько четкая идея, сколько набор хотелок: хочется лаконичный язык для решения ряда вполне определенных задач, хочется не объявлять типы, хочется иметь ФВП, ибо с ними очень удобно, хочется максимально простой рантайм.

[nponeccop.livejournal.com]

> набор хотелок: хочется лаконичный язык для решения ряда вполне
> определенных задач, хочется не объявлять типы, хочется иметь ФВП,
> ибо с ними очень удобно,

любопытно, но у меня в HN0 те же самые хотелки.

Но у вас ещё хотелка в виде обфсцированности выходного кода а ля security through obscurity, а у меня - наоборот, максимальная человекочитаемость

Ещё интересно, что ваша модель с фреймами - это один в один сишная модель. В старых Сях вроде было положено локальные переменные в начале функции объявлять. В С++ понятно, этого нет, но и в С99, если мне не изменяет память, это ограничение тоже отменили.

[thedeemon.livejournal.com]

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

Модель, разумеется, не оригинальна и инспирирована "настоящими" системами и языками.

[nponeccop.livejournal.com]

> В Leo нет типа bool, нет и проблемы.

То есть, логические выражения не являются first class и не могут быть использованы вне conditionals?

[thedeemon.livejournal.com]

Да, сейчас так. Если вдруг появится необходимость, добавить тип bool с представлением true/false в виде 1/0 будет несложно.

[udpn.livejournal.com]

Приятно, конечно, видеть, что ещё есть программисты компиляторов, которые не только пишут, но ещё и понимают, что именно они, собственно, пишут. Очень продуманно для набора хотелок.