Из прошлой статьи мы знаем, что я разрабатываю свой компилятор - Onyx. С того момента язык активно развивался, теперь он поддерживает:
Создание структур
Инициализация структур
Получение полей структур
Изменение полей структур
Создание имплементаций (методы экземпляра структуры)
Вызов методов структур
Неявные декларации функций
В корне репозитория появилась директория Examples, в которой можно посмотреть примеры кода на языке (в том числе и текущие изменения).
Планы на будущее
Статические поля структур
Статические методы
Трейты
Модули
Система сборки и пакетный менеджер
Примеры кода
// simple structure
struct Human {
pub var age: i32; // public field -> you can access of this field
var height: f32; // private field -> you cannot access of this field
}
fun main() : i32 {
var human: Human = Human { age: 16, height: 1.75f }; // it's me :)
human.age = 16;
return 0;
}// simple implementation for structure
struct Human {
var age: i32;
var height: f32;
}
impl Human {
pub fun GetAge() : i32 {
return this.age;
}
pub fun GetHeight() : f32 {
return this.height;
}
}
fun main() : i32 {
var h: Human = Human { age: 16, height: 1.76f }; // its me :)
var age: i32 = h.GetAge();
var height: f32 = h.GetHeight();
return age;
}Так как мы уже знаем как работает парсинг, то не будем лишний раз к нему возвращаться (для тех, кто не знает, жмякайте). Сразу перейдем к семантике и кодогенератору.
Изменения в AST
Теперь ASTType поддерживает не только примитивы, но и структуры, а его поле _val будет хранить имя структуры:
ASTTypeKind
enum class ASTTypeKind {
// ...
Struct,
// ...
};Декларации функций
Начнем с самого простого и довольно нужной вещи - деклараций функций. Важно отметить, что Onyx не предоставляет синтаксис для деклараций функций, потому что это boilerplate. Вместо этого функции могут вызываться перед их явным определением без дополнительного синтаксиса:
Пример
fun main() {
var sum: i32 = add(2, 3);
}
fun add(a: i32, b: i32) {
return a + b;
}Чтобы такое сделать можно хитрить. Мы можем пройтись по всему AST, найти определения функций (FunDeclStmt) и сделать вид, как будто мы определяем их и сохранить в _functions, а при вызове такой функции она будет найдена, так как предварительно была сохранена в мапу с функциями. Такая процедура проводится и в семантике и в кодгене:
Семантика
void
SemanticAnalyzer::DeclareFunctions(std::vector<Stmt *> &ast) {
for (auto &stmt : ast) {
if (stmt->GetKind() == NkFunDeclStmt) {
FunDeclStmt *fds = llvm::dyn_cast<FunDeclStmt>(stmt);
if (_functions.find(fds->GetName().str()) != _functions.end()) {
_diag.Report(llvm::SMLoc::getFromPointer(fds->GetName().data()), ErrRedefinitionFun)
<< getRange(llvm::SMLoc::getFromPointer(fds->GetName().data()), fds->GetName().size())
<< fds->GetName();
continue;
}
Function fun { .Name = fds->GetName(), .RetType = fds->GetRetType(), .Args = fds->GetArgs(), .Body = fds->GetBody() };
_functions.emplace(fds->GetName().str(), fun);
}
}
}std::optional<ASTVal>
SemanticAnalyzer::VisitFunDeclStmt(FunDeclStmt *fds) {
if (_vars.size() != 1) {
_diag.Report(fds->GetStartLoc(), ErrCannotBeHere)
<< llvm::SMRange(fds->GetStartLoc(), fds->GetEndLoc());
}
if (fds->GetAccess() == AccessPub && _vars.size() != 1) {
_diag.Report(fds->GetStartLoc(), ErrCannotHaveAccessBeHere)
<< llvm::SMRange(fds->GetStartLoc(), fds->GetEndLoc());
}
// раньше проверяли, создается ли переопределение
// если нет, то создавали функцию и делали то, что внизу
// сейчас функия 100% создана в DeclareFunctions
_vars.push({});
for (auto arg : fds->GetArgs()) {
_vars.top().emplace(arg.GetName(), Variable { .Name = arg.GetName(), .Type = arg.GetType(), .Val = ASTVal::GetDefaultByType(arg.GetType()),
.IsConst = arg.GetType().IsConst() });
}
_funRetsTypes.push(fds->GetRetType());
bool hasRet;
for (auto stmt : fds->GetBody()) {
if (stmt->GetKind() == NkRetStmt) {
hasRet = true;
}
Visit(stmt);
}
_funRetsTypes.pop();
_vars.pop();
if (!hasRet && fds->GetRetType().GetTypeKind() != ASTTypeKind::Noth) {
_diag.Report(fds->GetStartLoc(), ErrNotAllPathsReturnsValue)
<< llvm::SMRange(fds->GetStartLoc(), fds->GetEndLoc());
}
return std::nullopt;
}Кодген
void
CodeGen::DeclareFunctionsAndStructures(std::vector<Stmt *> &ast) {
for (auto &stmt : ast) {
if (FunDeclStmt *fds = llvm::dyn_cast<FunDeclStmt>(stmt)) {
std::vector<llvm::Type *> args(fds->GetArgs().size());
for (int i = 0; i < fds->GetArgs().size(); ++i) {
args[i] = typeToLLVM(fds->GetArgs()[i].GetType());
}
llvm::FunctionType *retType = llvm::FunctionType::get(typeToLLVM(fds->GetRetType()), args, false);
llvm::Function *fun = llvm::Function::Create(retType, llvm::GlobalValue::ExternalLinkage, fds->GetName().str(), *_module);
if (fds->GetRetType().GetTypeKind() == ASTTypeKind::Struct) {
llvm::MDNode *metadata = llvm::MDNode::get(_context, llvm::MDString::get(_context, fds->GetRetType().GetVal()));
fun->setMetadata("struct_name", metadata);
}
_functions.emplace(fun->getName(), fun);
}
// ...
}
}llvm::Value *
CodeGen::VisitFunDeclStmt(FunDeclStmt *fds) {
// раньше создавали аргументы и тип структуры
// теперь функция 100% создана и занесена в _functions
llvm::Function *fun = _functions.at(fds->GetName().str());
llvm::BasicBlock *entry = llvm::BasicBlock::Create(_context, "entry", fun);
_builder.SetInsertPoint(entry);
_vars.push({});
_funRetsTypes.push(fun->getReturnType());
int index = 0;
for (auto &arg : fun->args()) {
arg.setName(fds->GetArgs()[index].GetName());
_vars.top().emplace(arg.getName().str(), &arg);
++index;
}
for (auto &stmt : fds->GetBody()) {
Visit(stmt);
}
if (fds->GetRetType().GetTypeKind() == ASTTypeKind::Noth) {
_builder.CreateRetVoid();
}
_funRetsTypes.pop();
_vars.pop();
return nullptr;
}Как можно заметить, в кодгене этим занимается не просто DeclareFunctions, а DeclareFunctionsAndStructures. Через некоторое время мы перейдем к структурам и увидим полную версию этого метода.
Таким образом мы смогли сделать декларации функций, и теперь код:
fun main() : i32 {
return add(2, 3);
}
fun add(a: i32, b: i32) : i32 {
return a + b;
}успешно компилируется и завершается кодом 5 (сумма 2 и 3).
Структуры
Начнем с создания структур как типов и инициализации структур. Мы опять же опустим парсинг, так как он ничем не отличается от того, что было раньше. Мы перейдем сразу в семантику и кодген. Немного теории про структуры в Onyx: структуры хранят только поля, причем по умолчанию поля приватные. При желании можно пометить поле публичным с помощью кейворда pub:
struct Human {
var age: i32;
pub var height: f32;
}Мы стремимся к коду, как в примере здесь. Чтобы представить структуру в удобном для нас формате в семантике, давайте определим несколько структур:
Field, Method, Struct
// где-то в SemanticAnalyzer...
struct Field {
const llvm::StringRef Name;
std::optional<ASTVal> Val;
ASTType Type;
const AccessModifier Access;
bool ManualInitialized;
};
struct Method {
const Function Fun;
const AccessModifier Access;
};
struct Struct {
const llvm::StringRef Name;
std::unordered_map<std::string, Field> Fields;
std::unordered_map<std::string, Method> Methods;
};
std::unordered_map<std::string, Struct> _structs;На будущее будем хранить ещё и методы. Поле ManualInitialized нужно для того, чтобы понять, проинициализировали ли мы уже поле. Это нужно для того, чтобы мы не могли в одном инициализаторе структуры инициализировать одно и то же поле дважды.
Семантика определения структуры
std::optional<ASTVal>
SemanticAnalyzer::VisitStructStmt(StructStmt *ss) {
if (_vars.size() != 1) {
_diag.Report(ss->GetStartLoc(), ErrCannotBeHere)
<< llvm::SMRange(ss->GetStartLoc(), ss->GetEndLoc());
}
if (_structs.find(ss->GetName().str()) != _structs.end()) {
_diag.Report(ss->GetStartLoc(), ErrRedefinitionStruct)
<< llvm::SMRange(ss->GetStartLoc(), ss->GetEndLoc())
<< ss->GetName();
return std::nullopt;
}
Struct s { ss->GetName(), {}, {} };
for (int i = 0; i < ss->GetBody().size(); ++i) {
if (ss->GetBody()[i]->GetKind() != NkVarDeclStmt) {
_diag.Report(ss->GetStartLoc(), ErrCannotBeHere)
<< llvm::SMRange(ss->GetStartLoc(), ss->GetEndLoc());
continue;
}
VarDeclStmt *vds = llvm::dyn_cast<VarDeclStmt>(ss->GetBody()[i]);
if (s.Fields.find(vds->GetName().str()) != s.Fields.end()) {
_diag.Report(vds->GetStartLoc(), ErrRedefinitionField)
<< llvm::SMRange(vds->GetStartLoc(), vds->GetEndLoc())
<< vds->GetName();
continue;
}
std::optional<ASTVal> val = vds->GetExpr() != nullptr ? Visit(vds->GetExpr()) : ASTVal::GetDefaultByType(vds->GetType());
if (vds->GetExpr()) {
implicitlyCast(val.value(), vds->GetType(), vds->GetExpr()->GetStartLoc(), vds->GetExpr()->GetEndLoc());
}
s.Fields.emplace(vds->GetName().str(), Field { vds->GetName(), val, vds->GetType(), vds->GetAccess(), false });
}
_structs.emplace(s.Name, s);
return std::nullopt;
}Структура может определяться только в глобальной области видимости (_vars.size() == 1), поэтому мы проверяем, находимся ли мы не в глобальной области. Если да, то создаем ошибку ErrCannotBeHere. Дальше нудные проверки на переопределение и всё такое. Теперь мы начинаем проверять тело структуры. Мой парсер сохраняет тело как вектор Stmt *, поэтому нам нужно проверить, являются ли эти стейтменты полями (VarDeclStmt). Затем сохраняем структуру и идем дальше, уже в инициализацию структур:
Семантика инициализации структуры
std::optional<ASTVal>
SemanticAnalyzer::VisitStructExpr(StructExpr *se) {
if (_structs.find(se->GetName().str()) == _structs.end()) {
_diag.Report(se->GetStartLoc(), ErrUndeclaredStructure)
<< llvm::SMRange(se->GetStartLoc(), se->GetEndLoc())
<< se->GetName();
return ASTVal(ASTType(ASTTypeKind::I32, "i32", false),
ASTValData { .i32Val = 0 });
}
Struct s = _structs.at(se->GetName().str());
for (int i = 0; i < se->GetInitializer().size(); ++i) {
std::string name = se->GetInitializer()[i].first.str();
if (s.Fields.find(name) != s.Fields.end()) {
if (s.Fields.at(name).ManualInitialized) {
_diag.Report(se->GetStartLoc(), ErrFieldInitialized)
<< llvm::SMRange(se->GetStartLoc(), se->GetEndLoc())
<< name;
}
else {
s.Fields.at(name).Val = Visit(se->GetInitializer()[i].second);
s.Fields.at(name).ManualInitialized = true;
}
}
else {
_diag.Report(se->GetStartLoc(), ErrUndeclaredField)
<< llvm::SMRange(se->GetStartLoc(), se->GetEndLoc())
<< name
<< s.Name;
}
}
return ASTVal(ASTType(ASTTypeKind::Struct, s.Name, false),
ASTValData { .i32Val = 0 });
}Самое главное здесь это то, чтобы инициализировать поля структуры и вернуть значение структуры (это просто затычка, которая ничего не значит, поэтому ASTValData инициализируется нулем для поля i32Val). Семантика на этом заканчивается, так что переходим к кодгену.
Кодген определения структур
llvm::Value *
CodeGen::VisitStructStmt(StructStmt *ss) {
return nullptr;
}Смешно, да? Это всё потому что структуры будут инициализироваться в DeclareFunctionsAndStructures. Почему структуры будут инициализироваться в самом начале? Ну, всему свое время, друзьяшки :)
DeclareFunctionsAndStructures и вспомогательные структуры
// где-то в CodeGen...
struct Field {
const llvm::StringRef Name;
llvm::Type *Type;
ASTType ASTType;
llvm::Value *Val;
bool ManualInitialized;
long Index;
};
struct Struct {
const llvm::StringRef Name;
llvm::StructType *Type;
std::unordered_map<std::string, Field> Fields;
};
std::unordered_map<std::string, Struct> _structs;void
CodeGen::DeclareFunctionsAndStructures(std::vector<Stmt *> &ast) {
for (auto &stmt : ast) {
// ...
else if (StructStmt *ss = llvm::dyn_cast<StructStmt>(stmt)) {
std::vector<llvm::Type *> fieldsTypes(ss->GetBody().size());
std::unordered_map<std::string, Field> fields(ss->GetBody().size());
for (int i = 0; i < fieldsTypes.size(); ++i) {
VarDeclStmt *vds = llvm::dyn_cast<VarDeclStmt>(ss->GetBody()[i]);
fieldsTypes[i] = typeToLLVM(vds->GetType());
fields.emplace(vds->GetName(), Field { vds->GetName(), typeToLLVM(vds->GetType()), vds->GetType(), vds->GetExpr() ? Visit(vds->GetExpr()) : nullptr,
false, i });
}
llvm::StructType *structType = llvm::StructType::create(_context, fieldsTypes, ss->GetName(), false);
Struct s { ss->GetName(), structType, fields };
_structs.emplace(ss->GetName().str(), s);
}
}
}Меня одного раздражает, что метод Create обыно называется с большой буквы, а в llvm::StructType с маленькой?..
Теперь поле хранит индекс, но почему? Прикол в том, что в пределах low-level структуры и массивы примерно схожи между собой. Поэтому поля структур получают по индексу, прям как в массивах. Структуры при инициализации выравнивают поля, поэтому это работает.
Кодген инициализации структур
llvm::Value *
CodeGen::VisitStructExpr(StructExpr *se) {
Struct s = _structs.at(se->GetName().str());
if (_vars.size() != 1) {
llvm::AllocaInst *alloca = _builder.CreateAlloca(s.Type, nullptr, s.Name + ".alloca");
for (int i = 0; i < se->GetInitializer().size(); ++i) {
std::string name = se->GetInitializer()[i].first.str();
llvm::Value *fieldPtr = _builder.CreateStructGEP(s.Type, alloca, s.Fields.at(name).Index, name + ".gep");
_builder.CreateStore(Visit(se->GetInitializer()[i].second), fieldPtr);
s.Fields.at(name).ManualInitialized = true;
}
for (auto &field : s.Fields) {
if (!field.second.ManualInitialized) {
llvm::Value *fieldPtr = _builder.CreateStructGEP(s.Type, alloca, field.second.Index, field.second.Name + ".gep");
llvm::Value *val;
if (field.second.ASTType.GetTypeKind() == ASTTypeKind::Struct) {
val = defaultStructConst(field.second.ASTType);
}
else {
val = llvm::Constant::getNullValue(field.second.Type);
}
_builder.CreateStore(val, fieldPtr);
}
}
return _builder.CreateLoad(s.Type, alloca, s.Name + ".alloca.load");
}
else {
std::vector<llvm::Constant *> fields;
for (int i = 0; i < se->GetInitializer().size(); ++i) {
std::string name = se->GetInitializer()[i].first.str();
fields.push_back(llvm::dyn_cast<llvm::Constant>(Visit(se->GetInitializer()[i].second)));
s.Fields.at(name).ManualInitialized = true;
}
for (auto &field : s.Fields) {
if (!field.second.ManualInitialized) {
if (field.second.ASTType.GetTypeKind() == ASTTypeKind::Struct) {
fields.push_back(llvm::dyn_cast<llvm::Constant>(defaultStructConst(field.second.ASTType)));
}
else {
fields.push_back(llvm::Constant::getNullValue(field.second.Type));
}
}
}
return llvm::ConstantStruct::get(s.Type, fields);
}
}У нас есть два варианта инициализации структуры: в глобальной области и в локальной. В глобальной области мы можем создать только константный инициализатор (строки 28-44), иначе сегфолт и куча дебага. В локальной области всё проще: создание экземпляра, загрузка переданных значений в поля и возврат значения этой структуры. Самая главная состовляющая здесь это CreateStructGEP. GEP (Get Element Pointer) - получение указателя по индексу и указателю на начало. На этом строятся и массивы в том числе. CreateStructGEP это штучка для получения тех самых полей структуры через индекс. Мы загружаем в них переданные в инициализатор значения. Осталось только сделать так, чтобы глобальные переменные с типом структуры инициализировались по умолчанию правильным образом:
Кодген
llvm::Value *
CodeGen::defaultStructConst(ASTType type) {
Struct s = _structs.at(type.GetVal().str());
std::vector<llvm::Constant *> fields(s.Fields.size());
int i = 0;
for (auto &field : s.Fields) {
if (field.second.Val) {
fields[i] = llvm::cast<llvm::Constant>(field.second.Val);
}
else {
if (field.second.ASTType.GetTypeKind() == ASTTypeKind::Struct) {
fields[i] = llvm::dyn_cast<llvm::Constant>(defaultStructConst(field.second.ASTType));
}
else {
fields[i] = llvm::Constant::getNullValue(field.second.Type);
}
}
}
return llvm::ConstantStruct::get(s.Type, fields);
}llvm::Value *
CodeGen::VisitVarDeclStmt(VarDeclStmt *vds) {
llvm::Value *initializer = nullptr;
if (vds->GetExpr()) {
initializer = Visit(vds->GetExpr());
initializer = implicitlyCast(initializer, typeToLLVM(vds->GetType()));
}
else {
// если выражение не передано и тип - не структура
// инициализация нулем
// иначе вызываем defaultStructConst
if (vds->GetType().GetTypeKind() != ASTTypeKind::Struct) {
initializer = llvm::Constant::getNullValue(typeToLLVM(vds->GetType()));
}
else {
initializer = defaultStructConst(vds->GetType());
}
}
llvm::Value *var;
if (_vars.size() == 1) {
var = new llvm::GlobalVariable(*_module, typeToLLVM(vds->GetType()), vds->IsConst(), llvm::GlobalValue::ExternalLinkage, llvm::cast<llvm::Constant>(initializer),
vds->GetName());
}
else {
var = _builder.CreateAlloca(typeToLLVM(vds->GetType()), nullptr, vds->GetName());
_builder.CreateStore(initializer, var);
}
// тут ещё кое что есть, но это потом :)
_vars.top().emplace(vds->GetName().str(), var);
return nullptr;
}Теперь базовые структуры готовы, правда они мягко говоря бесполезны, ведь мы не можем получить или изменить значения полей. Давайте это исправим.
Получение полей
Опять же мы не уделяем время парсеру, но если нужно узнать, как реализовать парсинг цепочек вызовов, загляните сюда по адресу parseChainExpr. Семантика полей предельно проста: объект, из которого мы получаем поле, является структурой, поле содержится в объекте, поле публичное.
Семантика
std::optional<ASTVal>
SemanticAnalyzer::VisitFieldAccessExpr(FieldAccessExpr *fae) {
std::optional<ASTVal> obj = Visit(fae->GetObject());
if (obj->GetType().GetTypeKind() != ASTTypeKind::Struct) {
_diag.Report(fae->GetStartLoc(), ErrAccessFromNonStruct)
<< llvm::SMRange(fae->GetStartLoc(), fae->GetEndLoc());
}
else {
bool objIsThis = false;
if (fae->GetObject()->GetKind() == NkVarExpr) {
VarExpr *ve = llvm::cast<VarExpr>(fae->GetObject());
if (ve->GetName() == "this") {
objIsThis = true;
}
}
Struct s = _structs.at(obj->GetType().GetVal().str());
auto field = s.Fields.find(fae->GetName().str());
if (field == s.Fields.end()) {
_diag.Report(fae->GetStartLoc(), ErrUndeclaredField)
<< llvm::SMRange(fae->GetStartLoc(), fae->GetEndLoc())
<< fae->GetName()
<< s.Name;
}
else {
if (field->second.Access == AccessPriv && !objIsThis) {
_diag.Report(fae->GetStartLoc(), ErrFieldIsPrivate)
<< llvm::SMRange(fae->GetStartLoc(), fae->GetEndLoc())
<< fae->GetName();
}
return s.Fields.at(fae->GetName().str()).Val;
}
}
return ASTVal(ASTType(ASTTypeKind::I32, "i32", false), ASTValData { .i32Val = 0 });
}std::optional<ASTVal>
SemanticAnalyzer::VisitFieldAsgnStmt(FieldAsgnStmt *fas) {
if (_vars.size() == 1) {
_diag.Report(fas->GetStartLoc(), ErrCannotBeHere)
<< llvm::SMRange(fas->GetStartLoc(), fas->GetEndLoc());
}
std::optional<ASTVal> obj = Visit(fas->GetObject());
if (obj->GetType().GetTypeKind() != ASTTypeKind::Struct) {
_diag.Report(fas->GetStartLoc(), ErrAccessFromNonStruct)
<< llvm::SMRange(fas->GetStartLoc(), fas->GetEndLoc());
}
else {
Struct s = _structs.at(obj->GetType().GetVal().str());
auto field = s.Fields.find(fas->GetName().str());
if (field == s.Fields.end()) {
_diag.Report(fas->GetStartLoc(), ErrUndeclaredField)
<< llvm::SMRange(fas->GetStartLoc(), fas->GetEndLoc())
<< fas->GetName()
<< s.Name;
}
else {
if (field->second.Access == AccessPriv) {
_diag.Report(fas->GetStartLoc(), ErrFieldIsPrivate)
<< llvm::SMRange(fas->GetStartLoc(), fas->GetEndLoc())
<< fas->GetName();
}
implicitlyCast(Visit(fas->GetExpr()).value(), s.Fields.at(fas->GetName().str()).Type,
fas->GetStartLoc(), fas->GetEndLoc());
}
}
return std::nullopt;
}objIsThis нам пока что не пригодится, но когда появятся методы, то this-контекст будет решать всё.
Кодген
llvm::Value *
CodeGen::VisitFieldAccessExpr(FieldAccessExpr *fae) {
createLoad = false;
llvm::Value *obj = Visit(fae->GetObject());
createLoad = true;
if (!obj->getType()->isPointerTy()) {
llvm::AllocaInst *tempAlloca = _builder.CreateAlloca(obj->getType(), nullptr, "rvalue.tmp");
_builder.CreateStore(obj, tempAlloca);
obj = tempAlloca;
}
Struct s = _structs.at(resolveStructName(fae->GetObject()));
Field field = s.Fields.at(fae->GetName().str());
llvm::Value *gep = _builder.CreateStructGEP(s.Type, obj, field.Index);
if (_vars.size() == 1) {
if (auto *globalVar = llvm::dyn_cast<llvm::GlobalVariable>(obj)) {
if (globalVar->hasInitializer()) {
obj = globalVar->getInitializer();
}
else {
return nullptr;
}
}
if (auto *constantVal = llvm::dyn_cast<llvm::Constant>(obj)) {
return constantVal->getAggregateElement(field.Index);
}
return nullptr;
}
return _builder.CreateLoad(s.Type->getTypeAtIndex(field.Index), gep, fae->GetName() + ".load");
}llvm::Value *
CodeGen::VisitFieldAsgnStmt(FieldAsgnStmt *fas) {
createLoad = false;
llvm::Value *obj = Visit(fas->GetObject());
createLoad = true;
Struct s = _structs.at(resolveStructName(fas->GetObject()));
Field field = s.Fields.at(fas->GetName().str());
llvm::Value *gep = _builder.CreateStructGEP(s.Type, obj, field.Index);
_builder.CreateStore(Visit(fas->GetExpr()), gep);
return nullptr;
}Кодген предельно простой, это просто GEP и либо CreateLoad, либо CreateStore. Но есть один нюанс. Объект, из которого мы получаем поле, это переменная или функция. Кодген расчитан на то, что переменные загружаются и возвращается именно загруженное значение. Но GEP ожидает указатель. Поэтому мы не должны производить загрузку. createLoad - статическая булевая переменная, которая равна true, если мы будем загружать переменную, и равна false, если мы не хотим производить загрузку.
Логика для createLoad
// в CodeGen.cpp
static bool createLoad = true;llvm::Value *
CodeGen::VisitVarExpr(VarExpr *ve) {
auto varsCopy = _vars;
while (!varsCopy.empty()) {
if (auto var = varsCopy.top().find(ve->GetName().str()); var != varsCopy.top().end()) {
// теперь проверяем, можно ли производить загрузку
if (createLoad) {
if (auto glob = llvm::dyn_cast<llvm::GlobalVariable>(var->second)) {
if (_vars.size() == 1) {
return glob->getInitializer();
}
return _builder.CreateLoad(glob->getValueType(), glob, var->first + ".load");
}
if (auto local = llvm::dyn_cast<llvm::AllocaInst>(var->second)) {
return _builder.CreateLoad(local->getAllocatedType(),
local, var->first + ".load");
}
}
// в противном случае вернем указатель
return var->second;
}
varsCopy.pop();
}
return nullptr;
}Однако, если всё-таки obj не указатель - создаем аллокацию и загружаем в неё значение из obj, а затем obj приравниваем к этой аллокации. Отлично, мы можем делать GEP. Или нет?.. На самом деле ещё нет, ведь нам нужен тип структуры (llvm::StructType), который мы нигде не возьмем, кроме как получить из _structs. Мы не можем получить имя структуры из объекта, потому что llvm::Type не предоставляет такого функционала. Однако мы можем воспользоваться другой интересной фичей дракончика (теперь я так буду называть LLVM) - метаданные. Мы будем привязывать имя структуры в переменные и функции, причем оно будет хранится под именем struct_name, потому что я так решил (вы можете назвать их как угодно).
Привязка метаданных в переменные и функции
void
CodeGen::DeclareFunctionsAndStructures(std::vector<Stmt *> &ast) {
for (auto &stmt : ast) {
if (FunDeclStmt *fds = llvm::dyn_cast<FunDeclStmt>(stmt)) {
std::vector<llvm::Type *> args(fds->GetArgs().size());
for (int i = 0; i < fds->GetArgs().size(); ++i) {
args[i] = typeToLLVM(fds->GetArgs()[i].GetType());
}
llvm::FunctionType *retType = llvm::FunctionType::get(typeToLLVM(fds->GetRetType()), args, false);
llvm::Function *fun = llvm::Function::Create(retType, llvm::GlobalValue::ExternalLinkage, fds->GetName().str(), *_module);
// вот и метаданные
if (fds->GetRetType().GetTypeKind() == ASTTypeKind::Struct) {
llvm::MDNode *metadata = llvm::MDNode::get(_context, llvm::MDString::get(_context, fds->GetRetType().GetVal()));
fun->setMetadata("struct_name", metadata);
}
_functions.emplace(fun->getName(), fun);
}
// ...
}
}
llvm::Value *
CodeGen::VisitVarDeclStmt(VarDeclStmt *vds) {
llvm::Value *initializer = nullptr;
if (vds->GetExpr()) {
initializer = Visit(vds->GetExpr());
initializer = implicitlyCast(initializer, typeToLLVM(vds->GetType()));
}
else {
if (vds->GetType().GetTypeKind() != ASTTypeKind::Struct) {
initializer = llvm::Constant::getNullValue(typeToLLVM(vds->GetType()));
}
else {
initializer = defaultStructConst(vds->GetType());
}
}
llvm::Value *var;
if (_vars.size() == 1) {
var = new llvm::GlobalVariable(*_module, typeToLLVM(vds->GetType()), vds->IsConst(), llvm::GlobalValue::ExternalLinkage, llvm::cast<llvm::Constant>(initializer),
vds->GetName());
}
else {
var = _builder.CreateAlloca(typeToLLVM(vds->GetType()), nullptr, vds->GetName());
_builder.CreateStore(initializer, var);
}
// метаданные
if (vds->GetType().GetTypeKind() == ASTTypeKind::Struct) {
llvm::MDNode *metadata = llvm::MDNode::get(_context, llvm::MDString::get(_context, vds->GetType().GetVal()));
if (_vars.size() == 1) {
llvm::cast<llvm::GlobalVariable>(var)->setMetadata("struct_name", metadata);
}
else {
llvm::cast<llvm::AllocaInst>(var)->setMetadata("struct_name", metadata);
}
}
_vars.top().emplace(vds->GetName().str(), var);
return nullptr;
}Теперь, когда мы раздали метаданные объектам, которые могут хранить структуры, можно реализовать механизм получения названия структуры из этих метаданных (метод resolveStructName):
Кодген
std::string
CodeGen::resolveStructName(Expr *expr) {
switch (expr->GetKind()) {
case NkVarExpr: {
std::string name = llvm::dyn_cast<VarExpr>(expr)->GetName().str();
auto varsCopy = _vars;
while (!varsCopy.empty()) {
for (auto var : varsCopy.top()) {
if (var.first == name) {
if (auto *glob = llvm::dyn_cast<llvm::GlobalVariable>(var.second)) {
if (auto *metadata = glob->getMetadata("struct_name")) {
if (auto *mdStr = llvm::dyn_cast<llvm::MDString>(metadata->getOperand(0))) {
return mdStr->getString().str();
}
}
}
else if (auto *local = llvm::dyn_cast<llvm::AllocaInst>(var.second)) {
if (auto *metadata = local->getMetadata("struct_name")) {
if (auto *mdStr = llvm::dyn_cast<llvm::MDString>(metadata->getOperand(0))) {
return mdStr->getString().str();
}
}
}
else if (auto *arg = llvm::dyn_cast<llvm::Argument>(var.second)) {
llvm::Function *parent = arg->getParent();
if (auto *metadata = parent->getMetadata("this_struct_name")) {
if (auto *mdStr = llvm::dyn_cast<llvm::MDString>(metadata->getOperand(0))) {
return mdStr->getString().str();
}
}
}
}
}
varsCopy.pop();
}
return "";
}
case NkFunCallExpr: {
std::string name = llvm::dyn_cast<FunCallExpr>(expr)->GetName().str();
llvm::Function *fun = _functions.at(name);
if (auto *metadata = fun->getMetadata("struct_name")) {
if (auto *mdStr = llvm::dyn_cast<llvm::MDString>(metadata->getOperand(0))) {
return mdStr->getString().str();
}
}
return "";
}
case NkFieldAccessExpr: {
auto *fae = llvm::dyn_cast<FieldAccessExpr>(expr);
std::string parentStructName = resolveStructName(fae->GetObject());
if (parentStructName.empty()) {
return "";
}
if (_structs.count(parentStructName)) {
Struct &s = _structs.at(parentStructName);
std::string fieldName = fae->GetName().str();
if (s.Fields.count(fieldName)) {
Field &f = s.Fields.at(fieldName);
if (f.ASTType.GetTypeKind() == ASTTypeKind::Struct) {
return f.ASTType.GetVal().str();
}
}
}
return "";
}
case NkMethodCallExpr:
return resolveStructName(llvm::dyn_cast<MethodCallExpr>(expr)->GetObject());
default: {
return "";
}
}
}24-31 строки нас пока что не интересуют, ведь они связаны с this-контекстом. Поля готовы, даже удивительно, что это было так легко. А теперь методы...
Теория о методах
Давайте попробуем описать методы структур с помощью C, так как он будет наглядно отражать то, как методы будут выглядеть в LLVM IR.
typedef struct Human {
int age;
float height;
}
int Human_GetAge(Human *this) {
return this->age;
}Вот откуда и берется this - это неявный указатель на структуру, к которой привязан метод. Также стоит отметить, что метод GetAge называется Human_GetAge. Это искажение имени нужно для того, чтобы итоговая функция получила уникальное имя и не возникало пересечений с другими функциями (если вдруг будет функция с таким же именем, что и метод). Это называется манглинг - изменение имени, чтобы оно получилось 100% уникальным.
Методы
Именно таких принципов мы и будем следовать, чтобы создать методы для структур (в моем языке это называется имплементации). По традиции сразу перейдем к семантике.
Семантика определения имплементаций
std::optional<ASTVal>
SemanticAnalyzer::VisitImplStmt(ImplStmt *is) {
if (_vars.size() != 1) {
_diag.Report(is->GetStartLoc(), ErrCannotBeHere)
<< llvm::SMRange(is->GetStartLoc(), is->GetEndLoc());
}
Struct s = _structs.at(is->GetStructName().str());
std::vector<FunDeclStmt *> methods;
for (auto &stmt : is->GetBody()) {
if (stmt->GetKind() != NkFunDeclStmt) {
_diag.Report(stmt->GetStartLoc(), ErrCannotBeHere)
<< llvm::SMRange(stmt->GetStartLoc(), stmt->GetEndLoc());
continue;
}
FunDeclStmt *method = llvm::dyn_cast<FunDeclStmt>(stmt);
if (s.Methods.find(method->GetName().str()) != s.Methods.end()) {
_diag.Report(stmt->GetStartLoc(), ErrRedefinitionMethod)
<< llvm::SMRange(stmt->GetStartLoc(), stmt->GetEndLoc())
<< method->GetName();
}
else {
methods.push_back(method);
Function fun { .Name = method->GetName(), .RetType = method->GetRetType(), .Args = method->GetArgs(), .Body = method->GetBody() };
s.Methods.emplace(method->GetName().str(), Method { .Fun = fun, .Access = method->GetAccess() });
}
}
_structs.at(is->GetStructName().str()).Methods = s.Methods;
for (auto &method : methods) {
_vars.push({});
ASTType thisType = ASTType(ASTTypeKind::Struct, s.Name.str(), false);
_vars.top().emplace("this", Variable { .Name = "this", .Type = thisType, .Val = ASTVal::GetDefaultByType(thisType), .IsConst = false });
for (auto arg : method->GetArgs()) {
_vars.top().emplace(arg.GetName(), Variable { .Name = arg.GetName(), .Type = arg.GetType(),
.Val = ASTVal::GetDefaultByType(arg.GetType()),
.IsConst = arg.GetType().IsConst() });
}
_funRetsTypes.push(method->GetRetType());
bool hasRet;
for (auto stmt : method->GetBody()) {
if (stmt->GetKind() == NkRetStmt) {
hasRet = true;
}
Visit(stmt);
}
_funRetsTypes.pop();
_vars.pop();
if (!hasRet && method->GetRetType().GetTypeKind() != ASTTypeKind::Noth) {
_diag.Report(method->GetStartLoc(), ErrNotAllPathsReturnsValue)
<< llvm::SMRange(method->GetStartLoc(), method->GetEndLoc());
}
}
return std::nullopt;
}Как мы уже выяснили, метод это функция, поэтому в теле имплементаций также не может быть ничего кроме определения функций. Правила методов такие же, как и у полей: объект - структура, публичные методы можно вызывать за пределами имплементаций. Метод по сематике - это та же функция, но только с одним отличительным свойством: при входе в тело метода помимо аргументов добавляется ещё и переменная this, которая имеет тип структуры, которой мы создаем имплементации. Благодаря этому мы сможем внутри имплементации получать другие методы структуры, а также её поля.
Семантика вызова методов
std::optional<ASTVal>
SemanticAnalyzer::VisitMethodCallExpr(MethodCallExpr *mce) {
std::optional<ASTVal> obj = Visit(mce->GetObject());
if (obj->GetType().GetTypeKind() != ASTTypeKind::Struct) {
_diag.Report(mce->GetStartLoc(), ErrAccessFromNonStruct)
<< llvm::SMRange(mce->GetStartLoc(), mce->GetEndLoc());
}
else {
bool objIsThis = false;
if (mce->GetObject()->GetKind() == NkVarExpr) {
VarExpr *ve = llvm::cast<VarExpr>(mce->GetObject());
if (ve->GetName() == "this") {
objIsThis = true;
}
}
Struct s = _structs.at(obj->GetType().GetVal().str());
auto method = s.Methods.find(mce->GetName().str());
if (method == s.Methods.end()) {
_diag.Report(mce->GetStartLoc(), ErrUndeclaredMethod)
<< llvm::SMRange(mce->GetStartLoc(), mce->GetEndLoc())
<< mce->GetName()
<< s.Name;
}
else {
if (method->second.Access == AccessPriv && !objIsThis) {
_diag.Report(mce->GetStartLoc(), ErrMethodIsPrivate)
<< llvm::SMRange(mce->GetStartLoc(), mce->GetEndLoc())
<< mce->GetName();
}
_vars.push({});
if (method->second.Fun.Args.size() != mce->GetArgs().size()) {
_diag.Report(mce->GetStartLoc(), ErrFewArgs)
<< llvm::SMRange(mce->GetStartLoc(), mce->GetEndLoc())
<< mce->GetName().str()
<< method->second.Fun.Args.size()
<< mce->GetArgs().size();
return std::nullopt;
}
ASTType thisType = ASTType(ASTTypeKind::Struct, s.Name.str(), false);
_vars.top().emplace("this", Variable { .Name = "this", .Type = thisType,
.Val = ASTVal::GetDefaultByType(thisType), .IsConst = false });
for (int i = 0; i < method->second.Fun.Args.size(); ++i) {
std::optional<ASTVal> val = Visit(mce->GetArgs()[i]);
implicitlyCast(val.value_or(ASTVal::GetDefaultByType(ASTType::GetNothType())), method->second.Fun.Args[i].GetType(),
mce->GetArgs()[i]->GetStartLoc(), mce->GetArgs()[i]->GetEndLoc());
_vars.top().emplace(method->second.Fun.Args[i].GetName(), Variable { .Name = method->second.Fun.Args[i].GetName(),
.Type = method->second.Fun.Args[i].GetType(),
.Val = val,
.IsConst = method->second.Fun.Args[i].GetType().IsConst() });
}
for (auto stmt : method->second.Fun.Body) {
if (stmt->GetKind() == NkRetStmt) {
Expr *expr = llvm::dyn_cast<RetStmt>(stmt)->GetExpr();
std::optional<ASTVal> val = expr ? Visit(expr) : ASTVal::GetDefaultByType(ASTType::GetNothType());
implicitlyCast(val.value_or(ASTVal::GetDefaultByType(ASTType::GetNothType())), method->second.Fun.RetType, mce->GetStartLoc(),
mce->GetEndLoc());
_vars.pop();
return val;
}
else {
Visit(stmt);
}
}
_vars.pop();
_diag.Report(mce->GetStartLoc(), ErrMethodCannotReturnValue);
return ASTVal(ASTType(ASTTypeKind::I32, "i32", false), ASTValData { .i32Val = 0 });
}
}
return ASTVal(ASTType(ASTTypeKind::I32, "i32", false), ASTValData { .i32Val = 0 });
}std::optional<ASTVal>
SemanticAnalyzer::VisitMethodCallStmt(MethodCallStmt *mcs) {
if (mcs->GetAccess() == AccessPub) {
_diag.Report(mcs->GetStartLoc(), ErrCannotHaveAccessBeHere)
<< llvm::SMRange(mcs->GetStartLoc(), mcs->GetEndLoc());
}
MethodCallExpr *expr = new MethodCallExpr(mcs->GetObject(), mcs->GetName(), mcs->GetArgs(), mcs->GetStartLoc(), mcs->GetEndLoc());
VisitMethodCallExpr(expr);
delete expr;
return std::nullopt;
}
Первые строк ~10 такие же, как и у полей, ведь смысл тот же - проверить соблюдение правил методов. В остальном всё то же самое, что и у функций, за исключением неявного добавления this (мы уже знаем зачем он нужен).
Правила манглинга
В IR дракончика есть одна интересная особенность: имена могут содержать не только a-z, A-Z, 0-9, _, но и специальные символы: ., $. Именно этим я и воспользуюсь: буду разделять имя структуры и имя метода точкой. Например метод GetAge в структуре Human будет выглядеть в IR как Human.GetAge.
Кодген методов
Кодген декларации методов
void
CodeGen::DeclareFunctionsAndStructures(std::vector<Stmt *> &ast) {
for (auto &stmt : ast) {
// ...
else if (ImplStmt *is = llvm::dyn_cast<ImplStmt>(stmt)) {
for (auto stmt : is->GetBody()) {
FunDeclStmt *fds = llvm::cast<FunDeclStmt>(stmt);
std::vector<llvm::Type *> args(fds->GetArgs().size() + 1);
args[0] = llvm::PointerType::get(_structs.at(is->GetStructName().str()).Type, 0);
for (int i = 0; i < fds->GetArgs().size(); ++i) {
args[i + 1] = typeToLLVM(fds->GetArgs()[i].GetType());
}
llvm::FunctionType *retType = llvm::FunctionType::get(typeToLLVM(fds->GetRetType()), args, false);
llvm::Function *fun = llvm::Function::Create(retType, llvm::GlobalValue::ExternalLinkage,
is->GetStructName() + "." + fds->GetName().str(), *_module);
if (fds->GetRetType().GetTypeKind() == ASTTypeKind::Struct) {
llvm::MDNode *metadata = llvm::MDNode::get(_context, llvm::MDString::get(_context, fds->GetRetType().GetVal()));
fun->setMetadata("struct_name", metadata);
}
llvm::MDNode *metadata = llvm::MDNode::get(_context, llvm::MDString::get(_context, is->GetStructName()));
fun->setMetadata("this_struct_name", metadata);
_functions.emplace(fun->getName(), fun);
}
}
// ...
}
}Тут всё также, как и с функциями, ну кроме дополнительного неявного аргумента - указатель на структуру для имплементации (this). Как раз из-за того, что мы должны знать тип структуры, мы также создаем структуры в DeclareFunctionsAndStructures. Метадата с именем this_struct_name нужна для того, чтобы метод знал, какой структуре он пренадлежит. Эта информация хранится в самой функции, а не в аргументе this, потому что аргументам нельзя выдавать метаинформацию :( Но да ладно.
Кодген для вызова методов
llvm::Value *
CodeGen::VisitMethodCallExpr(MethodCallExpr *mce) {
createLoad = false;
llvm::Value *obj = Visit(mce->GetObject());
createLoad = true;
if (!obj->getType()->isPointerTy()) {
llvm::AllocaInst *tempAlloca = _builder.CreateAlloca(obj->getType(), nullptr, "rvalue.tmp");
_builder.CreateStore(obj, tempAlloca);
obj = tempAlloca;
}
Struct s = _structs.at(resolveStructName(mce->GetObject()));
std::vector<llvm::Value *> args(mce->GetArgs().size() + 1);
args[0] = obj;
for (int i = 0; i < mce->GetArgs().size(); ++i) {
args[i + 1] = Visit(mce->GetArgs()[i]);
}
llvm::Function *method = _functions.at(s.Name.str() + "." + mce->GetName().str());
return _builder.CreateCall(method, args, method->getName() + ".call");
}llvm::Value *
CodeGen::VisitMethodCallStmt(MethodCallStmt *mcs) {
MethodCallExpr *expr = new MethodCallExpr(mcs->GetObject(), mcs->GetName(), mcs->GetArgs(), mcs->GetStartLoc(), mcs->GetEndLoc());
Visit(expr);
delete expr;
return nullptr;
}Чего-то сверхнового тут нет - это смесь получения полей и вызова функций. За исключением манглинга в 17 строке VisitMethodCallExpr.
Заключение
Вроде бы это всё. Спасибо всем читателям, жду ваши комментарии и критику) Можете накидать идей для будущих фич, я буду только рад (попробую реализовать всё, что смогу и будет уместно). Всем удачи в дальнейших проектах ;)
