JIT-компилятор и виртуальная машина на Go

Leviathan — учебный системный проект, в рамках которого я в команде из трех человек принял участие в разработке JIT-компилятора и стековой виртуальной машины для языка LFA.

Проект написан на Go и охватывает полный пайплайн исполнения программы: от лексического анализа до выполнения оптимизированного байткода.

Что реализовано

• Lexer и parser для языка LFA
• построение AST
• компилятор в байткод
• стековая виртуальная машина (VM)
• compile-time оптимизации:
  • constant folding
  • peephole optimization
• runtime-оптимизации:
  • JIT-профилирование горячих участков
  • superinstructions
  • type profiling
• generational garbage collector
• набор unit-, integration- и benchmark-тестов

Архитектура

Проект разбит на несколько подсистем:

• lexer/ — лексический анализ
• parser/ — синтаксический разбор
• ast/ — узлы AST
• compiler/ — компиляция AST в байткод
• opcode/ — описание инструкций VM
• vm/ — виртуальная машина
• jit/ — runtime JIT-оптимизации, profiling, superinstructions
• gc/ — generational garbage collector и статистика
• object/ — runtime-объекты языка
• examples/ — примеры программ и бенчмарки
• cmd/run/ — CLI для запуска .lfa файлов

Возможности языка LFA

Поддерживаются:

• целые числа, включая большие значения
• числа с плавающей точкой
• булевы значения
• арифметика: +, -, *, /, %
• сравнения: ==, !=, <, >, <=, >=
• префиксные операции: -, !
• переменные через let
• присваивания
• if / else
• циклы while и for
• функции и рекурсия
• массивы, индексация и запись по индексу
• встроенные функции, включая sqrt и abs
• создание массивов через makeArray

JIT и runtime-оптимизации

Реализовано:

• отслеживание числа выполнений функций
• определение hot functions
• фиксация обратных переходов для обнаружения горячих циклов
• кэширование оптимизированного байткода
• замена частых последовательностей инструкций на superinstructions
• type profiling для распознавания сценариев, где возможна специализация под small integers

JIT умеет оптимизировать паттерны вида:

• GetLocal + GetLocal + Add
• GetLocal + GetLocal + Sub
• GetLocal + GetLocal + Mul
• сравнения между локальными переменными
• комбинации локальных или глобальных значений с константами

Это уменьшает количество интерпретируемых инструкций и снижает overhead VM на горячих участках.

Generational GC

В проекте есть собственная реализация поколенческого сборщика мусора:

• разделение объектов на поколения
• настройка порогов для Gen0 и Gen1
• minor и major collection
• promotion объектов между поколениями
• сбор статистики по количеству запусков, времени работы и числу помеченных/освобождённых объектов
• вспомогательная оценка потребления памяти

Производительные сценарии и n-body benchmark

В репозитории есть не только базовые примеры вроде факториала и сортировки, но и examples/nbody.lfa — вычислительно тяжёлый сценарий для моделирования n-body системы:

• использует float-арифметику
• содержит вложенные циклы
• создаёт устойчивую вычислительную нагрузку
• хорошо подходит для проверки VM и runtime-оптимизаций
• позволяет тестировать поведение системы не только на игрушечных примерах

Тестирование

В проекте покрыты тестами ключевые части пайплайна.

Проверяется:

• lexer: токенизация, комментарии, пробелы, операторы, ошибки
• parser: выражения, приоритеты операций, return, функции, управляющие конструкции
• compiler: генерация байткода, функции, вызовы, условия, рекурсия
• compile-time оптимизации: constant folding, chained folding, peephole optimization
• runtime JIT: hot-path detection, loop detection, type profiling, cache, superinstructions
• VM + JIT integration: корректность исполнения с оптимизациями и без них
• GC: пороги поколений, minor/major GC, promotion, reset, статистика

Также в проекте есть benchmark-тесты для JIT, GC, VM и числовых оптимизаций.

Запуск

Требования

• Go 1.24+

Установка зависимостей

go mod tidy

Запуск примера

go run ./cmd/run examples/factorial.lfa

CLI выводит:

• исходный код
• токены
• AST
• байткод
• константы и инструкции функций
• результат выполнения VM
• статистику generational GC

Отключение compile-time оптимизаций

go run ./cmd/run --no-constfold examples/factorial.lfa
go run ./cmd/run --no-peephole examples/factorial.lfa
go run ./cmd/run --no-constfold --no-peephole examples/factorial.lfa

Запуск тестов

Все тесты:

go test ./...

С подробным выводом:

go test ./... -v

Только JIT:

go test ./jit -v

Только GC:

go test ./gc -v

Только compiler:

go test ./compiler -v

Бенчмарки

Запуск всех benchmark-тестов:

go test ./... -bench=. -benchmem

Например, отдельно для JIT:

go test ./jit -bench=. -benchmem