Разработка компиляторов и интерпретаторов

LLVM - это набор библиотек и инструментов для разработки компиляторов. В состав LLVM входят компиляторы C и С++, которые можно использовать как отдельные инструменты, так и в форме библиотек для получения промежуточных результатов компиляции.

В основе LLVM лежит промежуточное представление кода (Intermediate Representation, IR), которое можно обработать в памяти, используя функции библиотек LLVM, либо выгрузить его в виде бинарного представления (bitcode, файлы с расширением .bc) или ассемблерного кода (файлы с расширением .ll). Из этого представления можно либо сгенерировать оптимизированный машинный код для целого ряда аппаратных платформ, либо выполнить его, непосредственно интерпретируя или получив машинный код в памяти (JIT-компиляция).

LLVM IR является статически типизированным, при этом диапазон разрядности операндов является произвольным. С точки зрения генерации кода команды LLVM IR являются тетрадами в форме:
%результат = операция %операнд1, %операнд2
где %результат, %операнд1, %операнд2 являются именами регистров для хранения временных значений. Количество регистров не ограничено, более того - каждому регистру выполняется присваивание только один раз, что упрощает статический анализ потока данных.

Модуль LLVM состоит из глобальных переменных, констант и функций. Определение функции содержит один или более базовых блоков, которые являются последовательностью команд, не являющихся командами перехода. Ключевая идея базового блока состоит в том, что если одна команда базового блока выполняется, то выполняются все остальные команды базового блока. Это упрощает анализ потока исполнения. В конце каждого базового блока есть команда перехода, ret возвращает поток управления вызывающей функции, а br выполняет переход, условный или безусловный.

В LLVM используется 2 способа добавления команд LLVM IR в генерируемый код.

• С помощью набора классов, производных от Instruction: UnaryOperator, BinaryOperator, CallInst, LoadInst, StoreInst, AllocaInst, CastInst, BranchInst и т.д. Например:
  Value *res=BinaryOperator::Create(Instruction::Add, left, right, "", context.currentBlock());
• С помощью набора класса IRBuilder. Например:
  Value *res=builder.CreateAdd(left, right);

IRBuilder предоставляет более простой API для генерации кода (например, не нужно указывать явно место для вставки команды), но поддерживается не весь набор команд.

Для операндов арифметических команд используется класс Value и производный от него Constant. В IRBuilder есть следующие методы для добавления команд в текущий базовый блок:

Value* CreateAdd(Value* L, Value* R); // L+R int
Value* CreateSub(Value* L, Value* R); // L-R int
Value* CreateMul(Value* L, Value* R); // L*R int
Value* CreateUDiv(Value* L, Value* R); // L/R unsigned
Value* CreateSDiv(Value* L, Value* R); // L/R signed
Value* CreateURem(Value* L, Value* R); // L%R unsigned
Value* CreateSRem(Value* L, Value* R); // L%R signed
Value* CreateShl(Value* L, Value* R); // L<<R int
Value* CreateLShr(Value* L, Value* R); // L>>R unsigned
Value* CreateAShr(Value* L, Value* R); // L>>R signed
Value* CreateAnd(Value* L, Value* R); // L&R int
Value* CreateOr(Value* L, Value* R); // L|R int
Value* CreateXor(Value* L, Value* R); // L^R int
Value* CreateFAdd(Value* L, Value* R); // L+R float
Value* CreateFSub(Value* L, Value* R); // L-R float
Value* CreateFMul(Value* L, Value* R); // L*R float
Value* CreateFDiv(Value* L, Value* R); // L/R float
Value* CreateFRem(Value* L, Value* R); // L%R float
Value* CreateBinOp(Instruction::BinaryOps Opc, Value* L, Value* R);
Value* CreateLogicalAnd(Value* L, Value* R); // L&&R
Value* CreateLogicalOr(Value* L, Value* R); // L||R
Value* CreateNeg(Value* V); // -V int
Value* CreateFNeg(Value* V); // -V float
Value* CreateNot(Value* V); // ~V int
Value* CreateUnOp(Instruction::UnaryOps Opc, Value* V);
Value* CreateICmp(CmpInst::Predicate P, Value* L, Value* R); // сравнение целых
Value* CreateFCmp(CmpInst::Predicate P, Value* L, Value* R); // вещественных

Дополнительными аргументами можно указать префикс для имени регистра и флаги обработки переполнения. Для сравнения целых чисел первым аргументом нужно указать ICMP_EQ, ICMP_NE, ICMP_UGT, ICMP_UGE, ICMP_ULT, ICMP_ULE, ICMP_SGT, ICMP_SGE, ICMP_SLT, ICMP_SLE; вещественных - FCMP_OEQ, FCMP_OGT, FCMP_OGE, FCMP_OLT, FCMP_OLE, FCMP_ONE. Также имеются команды для преобразования из целого в вещественный и обратно, расширения и обрезки целых и вещественных значений.

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

Constant* getInt1(bool V); // константы
Constant* getInt32(uint32_t C); 
Constant* getInt64(uint64_t C);
Constant* CreateGlobalStringPtr(StringRef Str); // i8*
Value* CreateLoad(Type* Ty, Value* Ptr); // загрузка из памяти
StoreInst* CreateStore(Value* Val, Value* Ptr); // сохранение
AllocaInst* CreateAlloca(Type* Ty, Value* ArraySize=nullptr); // размещение на стеке
Value* CreateGEP(Type* Ty, Value* Ptr, Value* Idx); // доступ к элементу массива или структуры (указатель на память)
Value* CreateInBoundsGEP(Type*Ty, Value* Ptr, ArrayRef<Value*> IdxList); // доступ к элементу массива или структуры с проверкой
CallInst* CreateCall(Function* Callee, ArrayRef<Value*> Args=None); // вызов функции

где тип можно получить с помощью методов:

Type* getInt1Ty(); // типы
Type* getInt32Ty();
Type* getInt64Ty();
Type* getFloatTy();
Type* getDoubleTy();

Завершающие команды добавляются с помощью следующих методов:

ReturnInst* CreateRetVoid();
ReturnInst* CreateRet(Value* V);
BranchInst* CreateBr(BasicBlock* Dest);
BranchInst* CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False);

Для создания блока используется функция класса BasicBlock:
BasicBlock* BasicBlock::Create(LLVMContext& Context, const Twine &Prefix="", Function *Parent=nullptr);
а для переключения блоков метод
void SetInsertPoint(BasicBlock* block);

Пример компилятора Basic для LLVM:

%option locations case-insensitive
%operator <yfx> '+' '-'
%operator <yfx> '*' '/' "mod"
%operator <fy> '-'
%type <int> ?число? ?идент? ?строка?
%type <Statement> оператор
%type <Expr> выр
%{
#include <string>
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cctype>
using namespace std;
int find_id(string name);
extern vector<pair<string,void*>> tc;
void arginit(int &argc, char ** &argv);
#define YYARGINIT(argc,argv) arginit(argc,argv)
}
%code lex {
%{
static string s;
%}
}
%% // правила для лексического анализатора
[ \t\r]                 ; // пропустить пробелы
R"("/'"(.|\n)*?"'/"|'.*)"                ; // пропустить комментарий
\d+                     ?число?  <stoi(yytext)>
[a-zA-Z]\w*                ?идент?  <find_id(yytext)>
R"(\")"                    { BEGIN(S_STRING); s=""; }
<S_STRING>R"(\"\")"                { s+='"'; }
<S_STRING>R"(\")"                { BEGIN(INITIAL); 
                                      $$=tc.size(); 
                                        tc.push_back(make_pair(s,nullptr));
                                          return ?строка?; 
                                        }
<S_STRING>.                { s+=yytext; }
<S_STRING>\n                { yyerror(&@$,this,"Ошибка в строке"); }
%% // правила для синтаксического анализатора
программа = код              <$1>
      ;
код = { оператор '\n' }
      ;
оператор =                     
  | ?идент? '=' выр             <assign($1,$3)>
  | "input" ?идент?              <input($2)>
  | "print" выр              <print($2)> 
  | "print" ?строка?              <printstr($2)> 
  | "while" выр '\n' код "wend"     <whilestmt($2,$4)>     
  | "if" выр ["then"] '\n'  код
     [ "else" '\n' код             
     ] "end" "if"             <ifstmt($2,$5,$6)>     
  ;
выр = выр '+' выр            <binop('+',$1,$3)>
    | выр '-' выр             <binop('-',$1,$3)>
    | выр '*' выр             <binop('*',$1,$3)>
    | выр '/' выр             <binop('/',$1,$3)>
    | выр "mod" выр             <binop('%',$1,$3)>
    | '-' выр                 <neg($2)>
    | '(' выр ')'
    | ?число?                 <number($1)>
    | ?идент?                <ident($1)>
    ;
%%
#include "llvm/ADT/APInt.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/TargetRegistry.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/Support/Host.h"
#include "llvm/Support/CodeGen.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Bitcode/BitcodeWriter.h"
#include "llvm/ExecutionEngine/ExecutionEngine.h"
#include "llvm/ExecutionEngine/GenericValue.h"
#include "llvm/ExecutionEngine/MCJIT.h"

#include <system_error>
using namespace llvm;

static LLVMContext theContext;
static IRBuilder<> builder(theContext);
static std::unique_ptr<Module> theModule;
static Value* theMemory;
static Function* main_func;
static Function* printf_func;
static Function* scanf_func;
Value* generate(Expr e)
{
   match e {
      rule binop(op,x, y):
        auto L = generate(x);
        auto R = generate(y);
        switch (op) {
          case '+':
            return builder.CreateAdd(L, R);
          case '-':
            return builder.CreateSub(L, R);
          case '*':
            return builder.CreateMul(L, R);
          case '/':
            return builder.CreateSDiv(L, R);
          case '%':
            return builder.CreateSRem(L, R);
        }
      rule neg(x): 
        auto V=generate(x);
        return builder.CreateNeg(V);
      rule number(x):  
        return builder.getInt32(x);
      rule ident(x):
        auto Ptr=builder.CreateGEP(builder.getInt32Ty(), theMemory, builder.getInt32(x));
        return builder.CreateLoad(builder.getInt32Ty(), Ptr);
   }
}
void generate(List<Statement> p)
{
  for(auto s:p)
    match s {
      rule assign(v, e): 
        auto V=generate(e);
        auto Ptr=builder.CreateGEP(builder.getInt32Ty(), theMemory, builder.getInt32(v));
        builder.CreateStore(V, Ptr);
      rule input(v):
        auto Ptr=builder.CreateGEP(builder.getInt32Ty(), theMemory, builder.getInt32(v));
        builder.CreateCall(scanf_func, vector<Value *>{(Constant*)tc[0].second, Ptr});
      rule print(e):
        auto V=generate(e);
        builder.CreateCall(printf_func, vector<Value *>{(Constant*)tc[0].second,V});
      rule printstr(e):
        builder.CreateCall(printf_func, vector<Value *>{(Constant*)tc[1].second,(Constant*)tc[e].second});
      rule whilestmt(e,p1):
        auto condBlock=BasicBlock::Create(theContext, "cond", main_func);
        auto bodyBlock=BasicBlock::Create(theContext, "body", main_func);
        auto nextBlock=BasicBlock::Create(theContext, "next", main_func);
        builder.CreateBr(condBlock);
        builder.SetInsertPoint(condBlock);
        auto Cond=generate(e);
        builder.CreateCondBr(
           builder.CreateICmp(CmpInst::ICMP_NE,Cond,builder.getInt32(0)),
           bodyBlock,nextBlock);
        builder.SetInsertPoint(bodyBlock);
        generate(p1);
        builder.CreateBr(condBlock);
        builder.SetInsertPoint(nextBlock);
      rule ifstmt(e,p1,p2): 
        auto Cond=generate(e);
        auto thenBlock=BasicBlock::Create(theContext, "then", main_func);
        auto elseBlock=BasicBlock::Create(theContext, "else", main_func);
        auto nextBlock=BasicBlock::Create(theContext, "next", main_func);
        builder.CreateCondBr(
           builder.CreateICmp(CmpInst::ICMP_NE,Cond,builder.getInt32(0)),
           thenBlock,elseBlock);
        builder.SetInsertPoint(thenBlock);
        generate(p1);
        builder.CreateBr(nextBlock);
        builder.SetInsertPoint(elseBlock);
        if(p2) { 
          generate(p2);
        }
        builder.CreateBr(nextBlock);
        builder.SetInsertPoint(nextBlock);
    }
}
map<string,int> ti; // таблица идентификаторов
int find_id(string name) // поиск в таблице
{ for(auto &ch:name) ch=toupper(ch);
  int k=ti[name];
  if(k==0) k=ti[name]=ti.size();
  return k;
}
vector<pair<string,void*>> tc{{"%d\n"s,nullptr},{"%s\n"s,nullptr}}; // таблица констант
int outmode=0;
void arginit(int &argc, char ** &argv) {
   if(argc>1 && argv[1]=="-o"s) {
      argc--;
      argv++;
      outmode=1;
   }
   else if(argc>1 && argv[1]=="-bc"s) {
      argc--;
      argv++;
      outmode=2;
   }
}
void yyinterpret(List<Statement> p) 
{ 
  string modname;
  modname=yyinputfile;
  size_t pos=modname.rfind('/');
  if(pos!=string::npos) modname=modname.substr(pos+1);
  pos=modname.rfind('\\');
  if(pos!=string::npos) modname=modname.substr(pos+1);
  pos=modname.rfind('.');
  if(pos!=string::npos) modname=modname.substr(0,pos);
  if(modname=="") modname="a";

  theModule = make_unique<Module>(modname, theContext);
  FunctionType *main_type = FunctionType::get(builder.getInt32Ty(), false);
  main_func = Function::Create(
      main_type, Function::ExternalLinkage, "main", theModule.get());

   FunctionType *printf_type =
      FunctionType::get(builder.getInt32Ty(), 
         vector<Type *>{builder.getInt8PtrTy()}, true);
  printf_func=Function::Create(
      printf_type, Function::ExternalLinkage, "printf", theModule.get());
  printf_func->setCallingConv(CallingConv::C);
  scanf_func=Function::Create(
      printf_type, Function::ExternalLinkage, "scanf", theModule.get());
  scanf_func->setCallingConv(CallingConv::C);

  builder.SetInsertPoint(BasicBlock::Create(theContext, "entry", main_func));
  theMemory=builder.CreateAlloca(builder.getInt32Ty(),builder.getInt32(ti.size()));
  for(int i=0;i<tc.size();++i)
  { tc[i].second=builder.CreateGlobalStringPtr(tc[i].first.c_str());
  }

  generate(p);

  builder.CreateRet(builder.getInt32(0));
  std::error_code err_code;

  if(outmode==2)
  {
      raw_fd_ostream dest(modname+".bc", err_code, sys::fs::OF_None);
      WriteBitcodeToFile(*theModule, dest);

  }
  else
  {
     InitializeAllTargetInfos();
     InitializeAllTargets();
     InitializeAllTargetMCs();
     InitializeAllAsmParsers();
     InitializeAllAsmPrinters();
     if(outmode==0)
     {
        ExecutionEngine *ee = EngineBuilder(move(theModule)).create();
        if (!ee) {
           std::cerr << "Error: execution engine creation failed.\n";
           exit(1);
        }
        GenericValue gv = ee->runFunction(main_func, vector<GenericValue>{});
     }
     else {
        raw_fd_ostream dest(modname+".o", err_code, sys::fs::OF_None);
        std::string TargetTriple = sys::getDefaultTargetTriple();
        theModule->setTargetTriple(TargetTriple);

        std::string err;
        const Target* Target = TargetRegistry::lookupTarget(TargetTriple, err);
        if (!Target) {
          std::cerr << "Failed to lookup target " + TargetTriple + ": " + err;
          exit(1);
        }

        TargetOptions opt;
        TargetMachine* theTargetMachine = Target->createTargetMachine(
            TargetTriple, "generic", "", opt, Optional<Reloc::Model>());

        theModule->setTargetTriple(TargetTriple);
        theModule->setDataLayout(theTargetMachine->createDataLayout());

        if (err_code) {
          std::cerr << "Could not open file: " << err_code.message();
          exit(1);
        }

        legacy::PassManager pass;
        if (theTargetMachine->addPassesToEmitFile(pass, dest, nullptr, CGFT_ObjectFile)) {
          std::cerr << "TheTargetMachine can't emit a file of this type\n";
          exit(1);
        }
        pass.run(*theModule);
        dest.flush();
     }
   }
}

Файл SciTE.properties

compile.libs=LLVMWindowsManifest LLVMXRay LLVMLibDriver LLVMDlltoolDriver LLVMCoverage\
 LLVMLineEditor LLVMX86Disassembler LLVMX86AsmParser LLVMX86CodeGen LLVMX86Desc LLVMX86Info\
 LLVMOrcJIT LLVMMCJIT LLVMJITLink LLVMInterpreter LLVMExecutionEngine LLVMRuntimeDyld\
 LLVMOrcTargetProcess LLVMOrcShared LLVMDWP LLVMSymbolize LLVMDebugInfoPDB LLVMDebugInfoGSYM\
 LLVMOption LLVMObjectYAML LLVMMCA LLVMMCDisassembler LLVMLTO LLVMPasses LLVMCFGuard\
 LLVMCoroutines LLVMObjCARCOpts LLVMipo LLVMVectorize LLVMLinker LLVMInstrumentation\
 LLVMFrontendOpenMP LLVMFrontendOpenACC LLVMExtensions LLVMDWARFLinker LLVMGlobalISel\
 LLVMMIRParser LLVMAsmPrinter LLVMDebugInfoMSF LLVMDebugInfoDWARF LLVMSelectionDAG LLVMCodeGen\
 LLVMIRReader LLVMAsmParser LLVMInterfaceStub LLVMFileCheck LLVMFuzzMutate LLVMTarget\
 LLVMScalarOpts LLVMInstCombine LLVMAggressiveInstCombine LLVMTransformUtils LLVMBitWriter\
 LLVMAnalysis LLVMProfileData LLVMObject LLVMTextAPI LLVMMCParser LLVMMC LLVMDebugInfoCodeView\
 LLVMBitReader LLVMCore LLVMRemarks LLVMBitstreamReader LLVMBinaryFormat LLVMTableGen\
 LLVMSupport LLVMDemangle uuid ole32

Архив с примером

Компиляция в объектный файл (.o):
basicllvm.exe -o test.bas

Создание выполняемого файла:
gcc -o test.exe test.o

Запуск выполняемого файла:
test.exe

JIT-интерпретация (без создания выполняемого файла):
basicllvm.exe test.bas