Pull to refresh

Компиляция. 5 и 1/2: llvm как back-end

Reading time 10 min
Views 6.1K
В серии статей от tyomitch «Компиляция» (тут, тут, тут, тут, тут и здесь) было рассмотрено построение транслятора игрушечного языка jsk, описанного в 4 части.
В качестве back-end для этого транслятора tyomitch предложил реализацию байт-кода и интерпретатор этого байт-кода.

На мой взгляд, более разумным подходом было бы использование существующих решений для backend, например llvm, и следуя принципу «Критика без конкретных предложений — критиканство», я предлагаю вариант реализации этого маленького языка jsk с llvm.

Что это даст для jsk? Настоящую компиляцию, то есть результатом будет исполняемый файл, который не зависит ни от каких runtime, возможность серьезной оптимизации, профилирования кода и автоматически получим документацию по back-end (что облегчит сопровождение).

Как устроен llvm с точки зрения разработчика front-end?

Для работы llvm необходимо создать context, с помощью него создать модуль. В каждом модуле может быть несколько функций. Поскольку jsk не поддерживает функции, мы создадим одну функция — main().
В каждой функции может быть несколько блоков кода.
Что такое блок кода

Часто в программах создается необходимость передать управление вперед, на метку, которая еще не определена. libjit позволяет сначала создать и использовать метку, а определить ее позже, Gnu llightning позволяет писать передачу управления в код, и позже пропатчить этот код, чтобы подставить нужный адрес, а llvm использует совсем другой подход — блоки кода.

То есть llvm API вообще не знает такого понятия как метка. Если надо передать управление, то в команду передается ссылка на блок кода. Например для конструкции

if условие then какой то код else код endif


В LLVM API нужно создать блоки кода для then ветки, блок кода для else ветки, и в команде условного перехода указать эти блоки. Что то типа

BasicBlock *ThenBB = BasicBlock::Create(context, "");
BasicBlock *ElseBB = BasicBlock::Create(context, "");
BasicBlock *AfterIfBB = BasicBlock::Create(context, "");
Builder.CreateCondBr(CondV, ThenBB, ElseBB);

И после этого заполнить кодом ThenBB, ElseBB, завершив и тот и другой безусловным переходом на AfterIfBB.


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

После того, как создали весь код, что дальше?


Это на наше усмотрение. Мы можем просто распечатать полученный байткод в читаемом виде с помощью метода dump() у llvm модуля, выполнить код (то есть использовать llvm как JIT компилятор), или, что правильней для нашего случая, сохранить байткод в файле. Это позволит в дальнейшем оптимизировать этот байт код и преобразовать его в исполняемый файл с помощью штатных инструментов llvm.

Итак,

Цели определены, задачи поставлены, за работу товарищи (с)


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

#include "llvm/DerivedTypes.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/Analysis/Verifier.h"
#include "llvm/Support/IRBuilder.h"
#include <llvm/Support/raw_ostream.h>
#include <llvm/Bitcode/ReaderWriter.h>
using namespace llvm;
 


Этого должно быть достаточно. Далее инициализируем контекст, модуль, создаем функцию main и IRBuilder для добавления кода в функцию

В декларации:
 
 static Module *TheModule;
 static IRBuilder<> Builder(getGlobalContext());
 


и в начало кода следующее:

  LLVMContext &Context = getGlobalContext();
  TheModule = new Module("jsk", Context);   
  const Type* voidType = Type::getVoidTy(Context);
 
  func_main = cast<Function>(TheModule->getOrInsertFunction("main", voidType, NULL));
  func_main->setCallingConv(CallingConv::C);
  BasicBlock* block = BasicBlock::Create(getGlobalContext()"code", func_main);
  Builder.SetInsertPoint(block);
 
 


После генерации кода мы генерируем ret void для выхода из нашей фиктивной функции и сбрасываем байткод в файл a.out.bc
 
  Builder.CreateRetVoid();
 
  std::string ErrStr;
  raw_fd_ostream bitcode("a.out.bc",ErrStr,0);
  WriteBitcodeToFile(TheModule, bitcode);
  bitcode.close();
 


Теперь насчет генерации кода для конкретных операция нашего jsk языка

Переменные


Для каждой переменной мы резервируем место в стеке с помощью инструкции

%varname = alloca i32

Или, в терминах API

Builder.CreateAlloca(IntegerType::get(context,32), 0, VarName.c_str());

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

Поэтому нам нужно иметь список уже определенных переменных, и когда мы встречаем в тексте переменную, проверить, и если она встретилась первый раз, разместить выделение памяти для нее в самом верху кода функции. То есть, у текущей функции взять первый блок, и добавить туда alloca команду сверху этого блока. На наше счастье llvm позволяет писать команды не только в конец, но и в начало блока. Как это сделано, можно посмотреть в исходном тексте — функция CreateEntryBlockAlloca();

Присваивание переменной значения

Value *result = value->emit();
Builder.CreateStore(result,varreference);

т.е.

store i32 %result, i32* %varreference


Соответственно, получить значение переменной


return Builder.CreateLoad(varref);
то есть
%val = load i32* %varref


Бинарные и унарные операции.


Тут все просто

 
 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 '<': tmp =  Builder.CreateICmpSLT(L, R); return Builder.CreateZExt(tmp, IntegerType::get(getGlobalContext(),32));
      case '>': tmp =  Builder.CreateICmpSGT(L, R); return Builder.CreateZExt(tmp, IntegerType::get(getGlobalContext(),32));
      case 'L': tmp =  Builder.CreateICmpSLE(L, R); return Builder.CreateZExt(tmp, IntegerType::get(getGlobalContext(),32));
      case 'G': tmp =  Builder.CreateICmpSGE(L, R); return Builder.CreateZExt(tmp, IntegerType::get(getGlobalContext(),32));
      case 'N': tmp =  Builder.CreateICmpNE(L, R);  return Builder.CreateZExt(tmp, IntegerType::get(getGlobalContext(),32));
      case '=': tmp =  Builder.CreateICmpEQ(L, R);  return Builder.CreateZExt(tmp, IntegerType::get(getGlobalContext(),32));
 
      default: return ErrorV("invalid binary operator ");
      }
 


IF и WHILE


Как уже описывалось, используем блоки кода. Например для IF:

     Value *CondV=cond->emit();
      // Сравнили выражение условия с 0
      CondV = Builder.CreateICmpNE(CondV,zero,"ifcond");
      // Блоки кода для веток IF
      BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext()"thenblock");
      BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext()"elseblock");
      BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext()"afterifblock");
      // Собственно ветвление для IF
      Builder.CreateCondBr(CondV, ThenBB, ElseBB);
 
      // Далее код добавляем в ветку THEN
      Builder.SetInsertPoint(ThenBB);
      this->thenops.emit();
      // В конце THEN переход на "после IF"
      Builder.CreateBr(MergeBB);
 
      TheFunction->getBasicBlockList().push_back(ElseBB);
      // Далее код добавляем в веку ELSE 
      Builder.SetInsertPoint(ElseBB);
      this->elseops.emit();
      // В конце else переход на "After IF" 
      Builder.CreateBr(MergeBB);
 
      TheFunction->getBasicBlockList().push_back(MergeBB);
      // После IF код добавлять только в MergeBB  
      Builder.SetInsertPoint(MergeBB);
      return zero;
 


Для WHILE:

      BasicBlock *CondBB = BasicBlock::Create(getGlobalContext(),"whilexpr",TheFunction);
      BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext()"loop");
      BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext()"after");
      Builder.CreateBr(CondBB);
 
      // Блок условия. Добавляем код сюда. генерируем код условия, Сравниваем результат с 0
      // И если условие не выполняется - переходим на AfterBB 
      Builder.SetInsertPoint(CondBB);
      Value *CondV=cond->emit();
      if (CondV == 0) return 0;
      // Convert condition to a bool by comparing equal to 0.
      CondV = Builder.CreateICmpNE(CondV,zero,"whilecond");
      Builder.CreateCondBr(CondV,LoopBB,AfterBB);
 
 
      //  Блок тела while. Пишем код тела сюда, затем переход на условие WHILE
      TheFunction->getBasicBlockList().push_back(LoopBB);
      Builder.SetInsertPoint(LoopBB);
      Value *Ops = this->ops.emit();
      Builder.CreateBr(CondBB);
 
 
      // Блок "После WHILE', В данный момент, просто говорим, 
      // что весь следующий код писать именно в этот блок 
      TheFunction->getBasicBlockList().push_back(AfterBB);
      Builder.SetInsertPoint(AfterBB);
 


Наконец, мы можем попробовать наш компилятор



#make
bison -d jsk.y
flex jsk.lex
g++ -O2 jsk.tab.c lex.yy.c `llvm-config --cxxflags --libs` -lrt -ldl -o jskc
jsk.tab.c: In function ‘int yyparse()’:
jsk.tab.c:2026: warning: deprecated conversion from string constant to ‘char*’
jsk.tab.c:2141: warning: deprecated conversion from string constant to ‘char*’
jsk.lex: In function ‘int yylex()’:
jsk.lex:34: warning: deprecated conversion from string constant to ‘char*’
jsk.lex:35: warning: deprecated conversion from string constant to ‘char*’
jsk.lex:39: warning: deprecated conversion from string constant to ‘char*’


Так. Компилятор готов. Давайте попробуем его на каком-нибудь тестовом задании. Например на
a=b=88;
b=b+1;
echo("test4=",a," ",b,"\n");


Выполяем:

./jskc <test3.jsk

И получаем a.out.bc в текущем каталоге. Мы можем его дизассемблировать:

llvm-dis <a.out.bc
; ModuleID = ''

@.format1 = internal constant [3 x i8] c"%d\00" ; <[3 x i8]*> [#uses=1]
@.format2 = internal constant [3 x i8] c"%s\00" ; <[3 x i8]*> [#uses=1]
@0 = internal constant [7 x i8] c"test4=\00" ; <[7 x i8]*> [#uses=1]
@1 = internal constant [2 x i8] c" \00" ; <[2 x i8]*> [#uses=1]
@2 = internal constant [2 x i8] c"\0A\00" ; <[2 x i8]*> [#uses=1]

define void @main() {
code:
%a = alloca i32 ; <i32*> [#uses=2]
%b = alloca i32 ; <i32*> [#uses=4]
%int_for_scanf___ = alloca i32 ; <i32*> [#uses=0]
store i32 88, i32* %b
store i32 88, i32* %a
%0 = load i32* %b ; [#uses=1]
%1 = add i32 %0, 1 ; [#uses=1]
store i32 %1, i32* %b
call void (i8*, ...)* @printf(i8* getelementptr inbounds ([3 x i8]* @.format2, i32 0, i32 0), i8* getelementptr inbounds ([7 x i8]* @0, i32 0, i32 0))
%2 = load i32* %a ; [#uses=1]
call void (i8*, ...)* @printf(i8* getelementptr inbounds ([3 x i8]* @.format1, i32 0, i32 0), i32 %2)
call void (i8*, ...)* @printf(i8* getelementptr inbounds ([3 x i8]* @.format2, i32 0, i32 0), i8* getelementptr inbounds ([2 x i8]* @1, i32 0, i32 0))
%3 = load i32* %b ; [#uses=1]
call void (i8*, ...)* @printf(i8* getelementptr inbounds ([3 x i8]* @.format1, i32 0, i32 0), i32 %3)
call void (i8*, ...)* @printf(i8* getelementptr inbounds ([3 x i8]* @.format2, i32 0, i32 0), i8* getelementptr inbounds ([2 x i8]* @2, i32 0, i32 0))
ret void
}

declare void @printf(i8*, ...)

declare void @scanf(i8*, ...)

declare void @exit(i32)


Мы можем интерпретировать при помощи lli, или (что нас интересует) - странслировать его в выполняемый файл:

$ llvmc a.out.bc

Получаем (УРА!) a.out, первый в мире бинарник, скомпилированный из программы на языке JSK:

$ ls -al ./a.out
-rwxr-xr-x 1 walrus walrus 4639 2010-08-25 16:49 ./a.out

$ file a.out
a.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.15, not stripped

$ ldd a.out
linux-gate.so.1 => (0x00762000)
libc.so.6 => /lib/tls/i686/cmov/libc.so.6 (0x00456000)
/lib/ld-linux.so.2 (0x00ee4000)


Запускаем,
$ ./a.out
test4=88 89


Что нам и требовалось.
Tags:
Hubs:
+38
Comments 9
Comments Comments 9

Articles