Написание компилятора на Haskell + LLVM07.10.2021 01:16

На работе я пишу почти исключительно на Python, с университетской скамьи остались некоторые знания C/C++, в одном pet-project использовал Haskell. С таким багажом знаний я взялся за написание компилятора на основе LLVM — зачем и что получилось я уже рассказывал в предыдущей статье.

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

Я кратко расскажу про необходимый минимум знаний Haskell, про свои ошибки и к каким решениям я пришел -, а так же про решения, о которых я узнал позже — и как их можно интегрировать в ваш pet-компилятор. На всё это я по возможности дам ссылки на изучение.

Оглавление

1. Haskell — настраиваем проект и необходимые знания языка

2. Основы языка — синтаксис, парсер, AST

3. Кодогенерация с LLVM

4. Заключение

Код из этой статьи, разложенный по шагам: https://github.com/VoidDruid/habr-hs-llvm

Репозиторий по этой ссылке можно использовать как «интерактивный учебник» в паре со статьей.

Haskell — необходимые знания языка и настройка проекта

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

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

• Базовый синтаксис языка

• Модули и импорты

• Как работать с монадами (не обязательно уметь писать свои), хотя бы поверхностно

• do-нотация

• IO монада

• Рекурсия, частичное применение функций, объявление типов

• Желательно: typeclasses, алгебраические типы данных, records

Я попытаюсь объяснить, зачем и как используется каждая фича языка, указанная в пункте »желательно», но будет проще, если вы с ними знакомы.

Собирать проект мы будем с помощью stack — установить его довольно просто (инструкция), пользоваться тоже. Создавать проект с нуля не придется — можно клонировать этот репозиторий, и идти в нем по шагам параллельно со статьей (readme есть в каждой папке плюс глобальный — ознакомьтесь с ними, чтоб упростить сборку и запуск кода). Или можно делать все самостоятельно, все же создав новый проект — с помощью самого stack (инструкция) или используя этот шаблон для cookiecutter.

Неплохая статья для начинающих про stack на русском

Книга про haskell на английском, которую можно использовать как онлайн-справочник

Если вы решили работать со статьей совместно с кодом из репозитория с пошаговым разбором, то перед тем как мы пойдем дальше, зайдите в папку step-00, и запустите stack run. Если программа с вами поздоровалась, то мы готовы идти дальше. Сейчас мы находимся в директории step-00, соответствующей ШАГ 0. В дальнейшем, переходы к следующему шагу (и, соответственно, к другой папке с кодом) будут отмечены именно так — ШАГ Х.

Основы языка — синтаксис, парсер, AST

Базовый парсинг

ШАГ 1

Первое, что мы попробуем сделать — это написать простой парсер. В стандартной библиотеке хаскеля есть отличный модуль Parsec (Parser Combinators — описание и документация; туториал, по которому учился я), позволяющий в декларативном стиле описывать парсеры. Для сборки необходимо добавить его в .cabal файл в секцию build-depends.

Туториал по Parsec на русском

На данном этапе, весь код все еще будет помещаться в модуле Main. Добавим несколько импортов:

import Text.Parsec (parse)
import Text.Parsec.String (Parser)
import Text.Parsec.Language (emptyDef)
import qualified Text.Parsec.Token as Tok

Что мы импортировали:

• parse — функция, прогоняющая парсер на входном потоке данных

• Parser — определение типа простого парсера, принимающего на вход строки

• emptyDef — «пустое» определение синтаксиса языка, на основе которого мы сделаем свое

• Text.Parsec.Token — основной модуль с функциями-парсерами

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

lexer :: Tok.TokenParser ()
lexer = Tok.makeTokenParser style
  where
  ops = [ "+", "*", "-", "/"]
  names = ["if", "else"]
  style = emptyDef {
  Tok.commentLine = "//"
  , Tok.commentStart = "/*"
  , Tok.commentEnd = "*/"
  , Tok.caseSensitive = True
  , Tok.reservedOpNames = ops
  , Tok.reservedNames = names
  }

Тут мы создали новый record под названием style, в котором описали базовый синтаксис нашего языка, пока что крайне простого — си-подобные комментарии, базовые операции (+, -, *, /) и зарезервированные слова if и else. Получившийся лексер мы теперь можем передать конструкторам парсеров из Tok, чтобы получить конкретный функции-парсеры для нашего языка:

integer    = Tok.integer lexer
float      = Tok.float lexer
-- и так далее, полный код - https://github.com/VoidDruid/habr-hs-llvm/blob/master/step-01/app/Main.hs

Попробуем написать парсер, который понимает простую операцию сложения целых чисел и возвращает результат.

Для парсеров определены монадные операторы, и если посмотреть определение типа, то видно что мы можем использовать их совместно с собственными монадами, state-ами и т.д. Когда я только начинал работать с Parsec, я этого не знал, и просто использовал do-нотацию, потому что так было написано в туториалах. Выше я вставлял ссылки на документацию, там можно увидеть что ParserT это на самом деле монадный трансформер, для которого определена куча инстансов монадных тайп классов, большинство из которых я до сих пор не понимаю. Для наших целей достаточно знать, что сами парсеры возвращают значения, а парсер-комбинаторы принимают одни парсеры и возвращают новые.

Зная это, определеить парсер для сложения можно так:

sumParse :: Parser Integer
sumParse = do
  first <- integer
  reservedOp "+"
  second <- integer
  return (first + second)

runSumParse = parse sumParse ""

Вернуть из парсера можно по-большому счету что угодно, тип просто поменяется на Parser ЧтоУгодно. Функция sumParse принимает строку, и разбирает ее как бы по инструкции, соответствущей последовательности операции в do-блоке:

• Берет первое число first <- integer

• Считывает зарезервированный оператор »+»

• Берет второе число second <- integer

• Возвращает результат сложения return (first + second)

У функции runSumParse один входной параметр — строка, которую она передает на разбор sumParse. "" — указание на «источник» входных данных, используется это для сообщений об ошибках, например.

Если войти в ghci (команда stack ghci), и запустить runSumParse "1 + 2" — вернется Right 3. Это значит что наш парсер отработал без ошибок, и вернул результат 3 — у функции parse тип возвращаемого значения Either ParseError a — где a — тип, возвращаемый sumParse, то есть Integer.

В качестве подведения черты под этим этапом, перепишем функцию main так, чтобы она читала строку из консоли, парсила сложение, и выводила результат или ошибку:

main = do
  line <- getLine
  case runSumParse line of
  	Right result -> putStrLn ("Result: " ++ show result)
  	Left error -> print error

Упражнение — парсер инкремента '1++'. Решение под спойлером

incrParse = do
	first <- integer
  reservedOp "++"
  return (first + 1)

Описание AST

ШАГ 2

Один из самых интересных этапов в проектировании языка, по-моему опыту — это описание формата синтаксического дерева. Именно тут закладывается фундамент для всех конструкций языка.

В случае с хаскелем, описать «обычное» дерево легко — это рекурсивный алгебраический тип данных:

data Tree a
	= Leaf  -- тупик
	| Node a (Tree a) (Tree a)  -- узел дерева - значение и две "ячейки" под ветки
	deriving Show

Тут Leaf и Node — конструкторы данных типа Tree a, где a — тип данных, которые содержат узлы дерева. Аналогичным образом мы можем описать и структуру выражения в нашем языке (еще раз напомню, что хоть синтаксис и похож на Си, мы пишем не сишный компилятор, а реализацию «учебного» си-подобного языка):

data Expr
  = Int Integer  -- значение типа Integer
  | Var Name  -- обращение к переменной
  | Def ExprType Name  -- объявление переменной
  | Block (CodeBlock Expr)  -- блок кода
  | Call String [Expr]  -- вызов функции с указанными аргументами
  | Function ExprType Name [Expr] (Maybe Name) (CodeBlock Expr)  -- объявление функции (разберем подробно далее)
  | BinaryOp String Expr Expr  -- бинарная операция над двумя выражениями
  | If Expr (CodeBlock Expr) (CodeBlock Expr)  -- if - условие и две ветки исполнения
  deriving (Eq, Ord, Show)

Таким образом, мы объявили самые базовые конструкции (см. комментарии в коде). Можно заметить, что здесь есть ссылки на дополительные типы данных — ExprType, CodeBlock. Первый — это просто «enum» с типами, поддерживаемыми нашей программой. Сейчас это только инты и функции, но оставим задел на будущее и объявим несколько дополнительных:

data ExprType
  = VoidType
  | IntType
  | FloatType
  | BytesType
  | BooleanType
  | CallableType [ExprType] ExprType  -- [типы аргументов] тип возвращаемого значения
  | AutoType  -- тип должен быть выведен автоматически
  deriving (Eq, Ord)

CodeBlock — это массив выражений, определен просто как:

type CodeBlock term = [term]
-- [expr1, expr2] это CodeBlock Expr

Разница между типами [Expr] и CodeBlock Expr чисто формальная — CodeBlock я использую там, где список выражения является «телом» чего-либо (функции, цикла и пр.), а [Expr] — например, как список аргументов функции. Для такого же «семантического» удобства определим тип AST, который будем использовать только в высокоуровневых функциях:

type AST = [Expr]

В отличии от CodeBlock, AST определен строго для Expr . Мне это показалось логичным в контексте того, что каждый из них «представляет» в программе. Однако если читателю это кажется излишним нагромождением типов, от всего этого можно избавиться и просто везде использовать [Expr].

Как можно сделать круче

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

Кода в этой секции много, весь его я здесь приводить не буду, только основные моменты. Остальное, как всегда, можно посмотреть в репозитории туториала.

Определить Show для типов довольно просто:

instance Show ExprType where
	show VoidType = "void"
	show IntType = "int"
	-- и т.д.

Гораздо интереснее его определять для Expr. Довольно быстро я понял, что определять именно Show не слишком правильно — например, красиво распечатанный If может занимать несколько строк, что не подходит для Show, поэтому я создал аналогичный тайп класс:

{- 
тайп класс Pretty определяет функцию prettify, возвращающую массив строк -
для выражений, "красивая" распечатка которых может не помещаться в одну
-}
class Show e => Pretty e where
	prettify :: e -> [String]

Я хотел иметь функцию prettifyAST, которой я мог бы передать AST (массив выражений) и получить список отформатированных строк — дальше их можно печатать отдельно или соединить в большое текстовое представление структуры программы (intercalate "\n" — каждый String на отдельной строке). Определил я эти функции так:

joinN = intercalate "\n"

prettifyAST :: Pretty e => [e] -> [String]
prettifyAST = map (joinN . prettify)

joinedPrettyAST :: Pretty e => [e] -> String
joinedPrettyAST = joinN . prettifyAST

Теперь дело осталось только за определением инстанса Pretty Expr. Как это сделал я, можете посмотреть тут (некоторые используемые функции определены в модуле StringUtils), общая структура такая:

instance Pretty Expr where
  prettify expr = case expr of
    (Int i) -> [joinS ["Int", show i]]
    -- и так для каждого Expr

Парсинг

Все еще ШАГ 2

Теперь рассмотрим написание парсера. Для этого мы будем использовать лексер, объявленный в шаге 1. Для парсера я создал отдельный модуль Parser (parser.hs) и вынес все связанное с лексером из первого шага в модуль Lexer (lexer.hs). Тут не будет ничего принципиально нового, просто продолжение принципов парсер-комбинаторов, которые я уже показывал.

Вот что мы будем использовать (есть еще импорты из стандартной библиотеки, их я опускаю):

import qualified Text.Parsec.Expr as Ex
import qualified Text.Parsec.Token as Tok

import Lexer
import Syntax

Первая и самая запутанная часть — объявить парсеры операций. Её я вынес под спойлер, кому интересно — можете посмотреть, а остальным предлагаю сразу переходить к парсерам выражений, я до сих пор под впечатлением, насколько элегантно это можно сделать.

Как всегда, полный код этого модуля (для данного этапа) в репозитории.

Парсеры операций

op :: Parser String
op = do
  whitespace
  o <- operator
  whitespace
  return o

data Expr
=
  -- ...
  BinaryOp String Expr Expr  -- операция с двумя операндами

{-
binary - конструктор бинарных операций, вернет частично созданный BinaryOp
(без операндов типа Expr и Expr)
Принимает сам оператор (s) и ассоциативность (у нас - Ex.AssocLeft)
-}
binary s assoc = Ex.Infix (reservedOp s >> return (BinaryOp s)) assoc

-- Функция, возвращающая функцию-генератор парсеров с указанной ассоциативностью для списока операторов
opList arity = opList'
	where 
    opList' [op] = [arity op Ex.AssocLeft]
    opList' (op:ops) = arity op Ex.AssocLeft : opList' ops

binList = opList binary

-- Доступные бинарные операторы (точнее уже парсеры для них - применяется binList), в порядке убывания приоритета
binops = [
  binList ["*", "/", "//", "%"]
  , binList ["+", "-"]
  , binList ["<", "=", "<=", ">=", "==", "!="]
	]

Объявим сначала верхнеуровневую функцию-парсер для любого выражения — она нам понадобится для использования внутри других:

{-
Сгенерированния парсеком функция-парсер, возвращаящая Expr.
factor - функция которую мы объявим далее, она парсит "обычные" Expr
binops - таблица операторов (+, *, <, != и пр.), которая позволяет нам правильно парсить и операции над Expr (в нашем случае только бинарные - BinaryOp)
-}
expr :: Parser Expr
expr =  Ex.buildExpressionParser binops factor

Функция factor — это комбинация парсеров для всех существующих Expr. Она должна попытаться их применить с помощью try, и вернуть первый получившийся результат:

factor :: Parser Expr
factor = try cast
      <|> try block
      <|> try function
      -- и т.д.

Уже известным нам способом объявим утилитарные функции для прогона парсера, и можно переходить к написанию парсеров самих выражений.

Функции для запуска парсинга

-- парсит все до eof с помощью переданной функции
contents :: Parser a -> Parser a
contents p = do
  Tok.whiteSpace lexer
  r <- p
  eof
  return r

-- парсит верхнеуровневые объявления файла (в нашем случае - только функции)
toplevel :: Parser [Expr]
toplevel = many $ do
  def <- function
  reservedOp ";"
  return def

-- парсит одно выражение
parseExpr :: String -> Either ParseError Expr
parseExpr s = parse (contents expr) "" s

-- парсит много выражений (файл с кодом)
parseCode :: String -> Either ParseError AST
parseCode s = parse (contents toplevel) "" s

Здесь я не буду приводить все функции, только несколько примеров — остальные можно посмотреть в репозитории.

Самый простой пример — парсер интов. Библиотечной функцией integer мы достаем из входного потока число и создаем Exprс помощью конструктора Int:

int :: Parser Expr
int = Int <$> integer

Так же мы можем использовать парсеры внутри парсеров, совмещая их с библиотечными комбинаторами:

codeBlock :: Parser [Expr]
codeBlock = braces $ many $
  do e <- expr
  reserved ";"
  return e

Объединив все вместе, разберем чуть более сложный парсер:

ifelse :: Parser Expr
ifelse = do
  reserved "if"  -- ищем в потоке ключевое слово if
  cond <- parens expr  -- затем любое заключенное в круглые скобки выражение
  tr <- codeBlock  -- парсим codeBlock, это true-ветка ифа
  fl <- optionMaybe $ do  -- ветка else необязательная, поэтом maybe мы сможем найти "else" и еще один codeBlock
    reserved "else"
    code <- codeBlock
    return code
  return $ If cond tr (fromMaybe [] fl)  -- конструируем и возвращаем Expr

Осталось попробовать что-нибудь распарсить. Переопределим main так, чтоб он принимал на вход имя файла, и печатал результат парсинга кода в нем. Импорты я опускаю, а сам main выглядит теперь так:

main = do
  args <- getArgs  -- аргументы командной строки
  case args of
    []   -> putStrLn "Provide file name!"
    [filename] -> do  -- если получили один аргумент
      code <- readFile filename  -- читаем файл
      case parseCode code of  -- и парсим его содержимое
        Left err -> print err
        -- если успех - используем нашу joinedPrettyAST чтоб сделать результат читаемым
        Right ast -> putStrLn (joinedPrettyAST ast)  
    _ -> putStrLn "Provide one file name!"

Вот как выглядит main.hs и main.grt (файл с кодом) у меня (и у вас, если вы идете по шагам). Запустим это с помощью

stack run -- main.grt

и полюбуемся на результаты нашей работы — красиво распечатанное AST.

Текстовое представление AST

Function "main" int ; args [] ; returns Nothing {
  BinaryOp = (Def int "i") (Int 0)
  If (BinaryOp < (Var "i") (Int 1)) {
    Int 0
  }
  else {
    Int 1
  }
}

Теперь можно двигаться дальше — к типизации.

Типизация

ШАГ 3

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

{- Конструктор типизированного выражения, принимающий тип и 
собственно выражение - одно из тех, что мы объявляли ранее -}
data TypedExpr = TypedExpr ExprType Expr

Но такой код, естественно, не делает то что нужно — «внутри» TypedExpr все еще лежит обычный Expr. Решение, которое придумал я — не оптимальное, но делает все, что надо. Это добавление «промежуточного контейнера» TExpr и собственно определение TypedExpr. Исходники — тут. Прелесть такого способа в том, что он также позволяет добавлять любые аннотации (в том же месте где и ExprType), однако многословен и не совсем идиоматичен. Описание моего тернистого пути под спойлером, а мы идем дальше.

Мои ошибки с добавлением типов

data Expr' e
= Int Integer
| Call String [e]

Механизм аннотирования типами

Ради историчности, и чтоб сразу показать, где код можно улучшить, я оставил все свои первоначальные TODO-пометки в исходниках.

На этом шаге мы добавляем модуль AST, в котором находятся все функции для обработки синтаксического дерева. «Верхнеуровневая» функция — processAST — объявлена тут и либо превращает AST в типизированные дерево (TAST), либо возвращает список ошибок. Все, что она делает сама — это применяет по очереди функции-обработчики обычного AST (сейчас это только desugarFunc — удаление из определения функций «сахара» в виде объявления имени возвращаемой переменной и явного ее указания в конце тела), а затем передает получившееся в annotateTypes (которая просто делает deduceType рекурсивно для каждого expr), и возвращает ее результат.

Логика deduceType довольно простая — она принимает аннотируемый expr, который, если все пройдет успешно, «заменится» своим typed-аналогом, и «карту типов» — ассоциативный массив известных «языковых единиц» (переменных, функций) с их типами — изначально пустой, и заполняющйся по мере углубления в дерево. Большая часть типов просто подсматиривается в определении, либо выводится из операций (int + int = int, int / int = float и т.д.). auto разрешается максимально просто — если известно значение присваемого выражения (арифметическая операция или вызов функции), то назначается этот тип, иначе возвращается ошибка.

Полные исходники — тут, либо в файле step-03/AST/Typing.hs.

Добавим processAST в main и посмотрим что нам выведет наша программа теперь для простейшей функции.

Исходник:

int main() = {
    int i = 0;
    if (i < 1) {
        0;
    }
    else {
         1;
    };
};

Типизированное представление:

Function (() -> int) main [] {
  BinaryOp i= (Def int "i") (int 0)
  If int (BinaryOp b< (Var int "i") (int 1)) {
    int 0
  }
  else {
    int 1
  }
}

Тут i= — интовое присвоение, а b< — операция сравнения, которая (очевидно) возвращает bool.

Кодогенерация с LLVM

ШАГ 4

В этом разделе мы воспользуемся инфраструктурой LLVM для создания машинного когда из нашего синтаксического дерева. Для этого нам нужна библиотека llvm-hs (github, hackage), которую, вместе с некоторыми другими, надо добавить в зависимости нашего проекта. В моем stack.yaml это выглядит так:

extra-deps:
- llvm-hs-9.0.1
- llvm-hs-pure-9.0.0
- llvm-hs-pretty-0.9.0.0

Если же вы идете по туториалу по шагам из репозитория, то переходите в step-04.

Необходимо установить и саму LLVM — как это сделать, описано в документации llvm-hs. Инструкция. Соответствущие изменения в конфигурационных файлах проекта — stack.yaml и habrhs.cabal

Из TAST в IR

Это — финишная прямая. Тут мы добавим модуль Codegen, главная его функция — buildIR, выдающая промежуточное представление LLVM IR. Сразу добавим этот этап в main следующим образом, чтобы сосредоточиться только на кодогенерации (обратите внимание — появилось много импортов и флаг --emit).

Codegen состоит из трех файлов, главный — Builder.hs, где и происходит генерация IR, остальные содержат утилиты, по которым я предлагаю быстро пройтись (обратите внимание, что тут везде импортированы модули LLVM.*, функции с разными «компиляторными» названиями типо allocate или reference — это оттуда).

1) ASTBridge — разные утилиты для перевода типов и операции нашего TAST в соответствущие для LLVM

• typeMap — словарь из пар «наш идентификатор типа» — «тип в LLVM»

• функции вида allocateX — генераторы вызовов LLVM для аллокации памяти под сам тип или указатель на него.

• функции вида referenceX — генерации LLVM-ных «обращений» к ячейке памяти под какой-либо тип напрямую или по указателю

• convert — по нашим IntType и FloatType генерирует операции приведения типов для LLVM

• opTable и findOperation — соответственно словарь и функция для поиска в нем соответствующих операций. Словарь содержит для IntType и FloatType еще по вложенному словарю, с парами «строка операции» (+, -, …) — «LLVM операция соответствующего типа» (интовое умножение, дробное умножение и т.д.)

Каждая из этих функций (за исключением последней) возвращает Operand — это LLVM-примитив, обозначающий, как ни странно, операнд — не самостоятельное выражение, а некий объект, который должен быть или «записан в переменную» (store в llvm), или использован в составе другого операнда. findOperation же возвращает (а opTable — содержит) функции, принимающие два операнда и возвращающие третий — то есть бинарные операции.

Кроме уже упомянутых reference и allocate, тут используется еще несколько часто встречаемых конструкций из LLVM. Это named, генерирующий именованные выражения и AST.PointerType, оборачивающий любой другой LLVM-тип и объявляющий указатель. Особенно стоит отметить, что такое qualified имя обозначает что это не из «нашего» AST, а из модуля LLVM.AST.

2) Primitives — содержит сокращенные объявления функций LLVM. Например, объявлние типа указателя на int требует определить адресное пространство и вид инта (i16, i32, i64). Мы для простоты используем выравнивание по 4, i32 и дефолтное адресное пространство — поэтому удобно создать утилитарные функции, которые подобные параметры проставляют сразу. Такие сокращения и содержит этот модуль.

И, наконец, то, ради чего мы тут собрались — генерация IR из AST, модуль Builder.

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

TAST (то есть [TypedExpr]) -> buildIR -> LLVM Module, где

1) buildIR: применяет к каждому TypedExpr (который гарантированно фукция) buildFunction 
2) buildFunction: генерирует IR функции, то есть создает ее объявление, аллоцирует аргументы,
   и затем генерирует тело с помощью funcBodyBuilder -> buildCodeBlock
3) buildCodeBlock: применяет emit к каждому выражению и его частям рекурсивно, и делает возвращаемым значением последнее выражение
   (мы сделали возвращаемые переменные переменные "последним выражением" в блоке на этапе обработки AST, помните?)

Тип функции emit следующий — emit :: (MonadFix m, MonadIRBuilder m) => TypedExpr -> m Operand. То есть это функция, которая работает с монадой IRBuilder из LLVM — это крайне удобно, т.к. с помощью do-блока и специальных фунций LLVM мы, по сути, просто объявляем (с помощью паттерн-матчинга) для каждого нашего выражения какой ему соответствует IR-код почти один-в-один для человеческого глаза. Т.к. большинство из того что «возвращают» функции LLVM можно передать далее по монаде, написание emit — довольно тривиально.

Разберем пример (тут используется функция view в паттерне для удобства — она сразу достает тип и составные части выражения) — генерация для If:

-- type_ - тип результата блока
emit (view -> (type_, TIf cond blockTrue blockFalse)) = mdo
  -- генерируем IR для условия If (рекурсивно используем emit), например для выражения вида "x < y"
  condition <- emit cond
  -- создаем указатель на будущий результат, он будет результатом блока
  -- и в него запишется результат выполненной ветки
  resultPointer <- allocateT type_
  -- проверка условия и выбор ветки
  condBr condition trueBranch falseBranch
  -- генерация IR для ветки if (...) { }
  trueBranch <- buildBranch "true" blockTrue resultPointer $ Just mainBr
  -- генерация IR для ветки else { }
  falseBranch <- buildBranch "false" blockFalse resultPointer $ Just mainBr
  -- возвращаемся в "главную ветку" исполнения и возвращаем результат
  (mainBr, result) <- emitExit resultPointer
  return result

Тут есть несколько утилитарных функций. Самая простая — emitExit, она просто генерирует код выхода из блока с сохранением результата:

emitExit resultPointer = do
  mainBr <- block `named` bodyLabel
  result <- load resultPointer
  return (mainBr, result)

Вторая — buildBranch. Аналоги веток есть не только у If, но в некотором смысле и у циклов, просто там в конце происходит прыжок в начало.

-- тут мы получаем имя, список expr для генерации (codeBlock), и уже известный resultPointer - куда сохранить результат
buildBranch name codeBlock resultPointer mNext =
  do
    -- начинаем ветку - метка для LLVM
    branch <- block `named` name
    -- опять рекурсивно применяем emit, скрывающийся под buildCodeBlock
    blockR <- buildCodeBlock codeBlock
    -- сохраняем результат по указателю
    store resultPointer blockR
    -- если надо выйти из ветки - генерируем прыжок, иначе пропускаем
    case mNext of
      Nothing -> pure ()
      Just label -> br label
    -- возвращаем получившийся блок
    return branch

Расписав таким образом emit для каждого вида выражений (некоторые реализации занимают одну строку), мы получаем генератор IR кода. Посмотрим, что у нас получилось в итоге для все той же простейшей функции (те кто следуют по туториалу — это main.grt). Запустим stack run -- -e main.grt еще раз и полюбуемся на результат (флаг -e нужен для печати IR — ведь на этом этапе мы уже расчитываем скоро иметь компилятор, а они обычно не выводят на экран IR):

; ModuleID = 'program'

define external ccc  i32 @main()    {
Body_0:
  %i_0 = alloca i32, align 4 
  store  i32 0, i32* %i_0, align 4 
  %0 = load  i32, i32* %i_0, align 4 
  %1 = icmp slt i32 %0, 1 
  %2 = alloca i32, align 4 
  br i1 %1, label %true_0, label %false_0 
true_0:
  store  i32 0, i32* %2, align 4 
  br label %Body_1 
false_0:
  store  i32 1, i32* %2, align 4 
  br label %Body_1 
Body_1:
  %3 = load  i32, i32* %2, align 4 
  ret i32 %3 
}

Этот код сгенерирован без каких-либо оптимизаций, поэтому он многословнее чем «должен быть», но для нас это только лучше — нагляднее. Ура, мы наконец имеем LLVM IR из исходников нашей программы. Запустить его уже можно, например перенаправив вывод в файл, который затем дать на вход lli — интерпретатору IR.

Если хочется создать исполняемый файл, то дело за малым — обратиться к встроенному в LLVM функционалу компиляции модулей.

Бонус: создаем бинарник

writeWithDefaultTarget :: File -> Module -> IO ()
writeWithDefaultTarget file mod = withHostTargetMachineDefault (\t -> writeObjectToFile t file mod)

writeWithModuleFromAST :: File -> Context -> LLVM.AST.Module -> IO ()
writeWithModuleFromAST f c m = withModuleFromAST c m (writeWithDefaultTarget f)

writeObject :: File -> LLVM.AST.Module -> IO ()
writeObject file mod = withContext (\c -> writeWithModuleFromAST file c mod)

writeObject (File ("output.o" :: FilePath)) ir

#!/usr/bin/env bash
stack run -- main.grt

ld -lSystem output.o -o output
chmod +x output
./output

echo $?

Заключение

Итак, мы прошли все основные этапы написания компилятора — парсер, обработка AST, генерация IR, даже затронули генерацию финального машинного кода. Иначе говоря, мы разработали фронтенд компилятора и научились взаимодействовать с бэкендом (LLVM). Конечно, как я уже указывал, многое можно сделать лучше — надеюсь я дал достаточно ссылок на другие материалы, чтобы вы смогли избежать моих ошибок, а мой туториал стал хорошей стартовой точкой.

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

© Habrahabr.ru