|
TranslatortoLLVMHowTO
Трансляция в Human-Readed Low Level Virtual Machine Code Разработаем простейший транслятор в целевой код [http://llvm.orgLevel Virtual Machine] . Разработку транслятора разделим на несколько этапов: - Определение грамматики языка - Разработка лексического анализатора - Разработка семантического анализатора - Разработка генератора промежуточного кода Определение грамматики языка Наш язык будет выполнять простейшие арифметические операции над целыми числами и вывод на экран, составим несколько примеров нашего будуюего языка: Пример 1 a = 2 + 2 print a+1 Пример 2 print 2+2 Пример 3 a = 5 b = 6 c = 2 print a*b*c+1 Как видно из примеров, нам необходимо:
2. определить оператор присваивания = 3. определить функцию для вывода значения переменной на экран Разработка лексического анализатора Определим основные токены для нашего языка: - tNUM - целое число - tPLUS - плюс - tMINUS - минус - tMULT - умножение - tDIV - деление - tASSIGN - оператор присваивания - tID - идентификатор И так, токены определены, можно приступить к написанию лексического анализатора, для этого воспользуемся средством [http://flex.sf.netflex] , которое является генератором лексических анализаторов на языке c. Далее приведен текст лексического анализатора, описанного во входном формате flex'a: sample.l %option noyywrap%{#include "sample.h"int yyparse();
%}DIGIT [0-9]ID [a-zA-Z]+[a-zA-Z0-9]%%{DIGIT}+= ={= =yylval.value= = =atoi(yytext);= =return VALUE;= =}print { return tPRN; }{ID} {
="==" { return tASN; } "+" { return tPLS; }"-" { return tMNS; }"" { return tMLT; }"/" { return tDIV; }\t\n+ {}%% Разработка семантического анализатора %{%}%union{
}%{%}%token VALUE%token IDENTIFIER%token tPLS%token tMNS%token tMLT%token tDIV%token tASN%token tPRN%left tPLS tMNS%left tMLT tDIV%start program%%program : /empty/
;statement : assign_statement
;assign_statement : IDENTIFIER tASN math_expression
;print_statement : tPRN math_expression
;identifier : IDENTIFIER
;value : VALUE
;math_expression : value { }
;%%
Генерация промежуточного кода Обзор LLVM LLVM предоставляет llvm human readed language для лучшей читабельности кода для данной виртуальной машины. Каждая llvm программа имеет свою точку входа, которая как и в языках java c++ , представлена функцией main, декларация ф-ции в llvm выглядит следующим образом: define i32 @main() { } define - ключевое слово, i32 - имя типа (32 битное целое), @main - название функции операторы в языке llvm записываются следующим образом: %tmp = op type1 value1, type2 value2, ... %tmp - переменная, в которую заноситься результат выполнения операции; type1, type2 - типы данных переменных, к которым применяется оператор; value1, value2 - константные значения либо названия переменных, к котрым применяется данный оператор Пример %tmp = add %x, i32 1 ; К значению переменной %x прибавляется единица Для инициализации переменной, необходимо выделить для нее область памяти и записать в эту область начальное значение переменной, в следующем примере показана инициализация переменной x и присвоение ей значения 0: Пример %x = alloca i32 store i32 0, i32 %x alloca - оператор выделения памяти, в данном случае мы выделяем память для типа i32, возвращает указатель на выделеную область памяти; store - инструкция для записи в память, 1й параметр - значение записываемое в область памяти, 2й параметр - указатель на область памяти Работа со строками Для инициализации строки в llvm необходимо объявить глобальную переменную, которая будет иметь тип массива с элементами типа i8: Пример @str8 = internal constant x i8 c"mama\00" Строка должна быть null-terminated, т.е. заканчиваться на \00. Глобальные переменные в llvm объявляются вначале программы. Далее, для использования данной строки необходимо получить указатель на эту строку, что делается с помощью инструкции getelementptr: Пример %str8_addr = getelementptr x i8 @str8, i64 0, i64 0 В данном примере получается указатель на константную строку @str8 и записывается в переменную %str8_addr Вызов функций Для вызова функции используется инструкуция call, параметром которой является имя функции и параметры для запуска этой функции: Пример call i32 @puts(i8 %str8_addr) ; Пример вызова функции для печати строки на экран Генерация кода Инициализация модуля Для начала необходимо создать модуль, для этого создадим заголовочный файл sample.h, пропишем библиотеки, которые необходимы для работы с llvm api и некоторые стандартные библиотеки : sample.h # ifndef SAMPLE_H # define SAMPLE_H # include < iostream > # include < map > # include < string > # include < stdio.h > # include < stdlib.h > # include < string.h > # include < llvm/Module.h > # include < llvm/Function.h > # include < llvm/DerivedTypes.h > # include < llvm/Constants.h > # include < llvm/PassManager.h > # include < llvm/CallingConv.h > # include < llvm/Analysis/Verifier.h > # include < llvm/Assembly/PrintModulePass.h > # include < llvm/Support/LLVMBuilder.h > # include "parser.h" using namespace llvm; using namespace std; int yyerror(const char *msg); //ф-ция для обработки ошибок int yylex();//ф-ция лексического анализатора bison'a void initModule(); void releaseModule(); Далее создадим точку входа в приложение в файле с правилами для лексического анализатора sample.l: int main(int argc, char *argv[]){
yyin = stdin;
FILE *f;
if(argc>1){
f = fopen(argv[ 1 ], "r");
yyin = f;
}else{
return 0;
}
initModule(); //обработка инициализации модуля
yyparse();
releaseModule(); //обработка завершения модуля
if(argc>1){
fclose(f);
}
return 0;
}В файле sample.y опишем основные переменные, для работы с модулем: %{
include "sample.h"
using namespace llvm;
using namespace std;
Module *module;
BasicBlock *block;
LLVMBuilder builder;
%}Module - класс llvm api для работы с модулем, модуль в языке llvm представляет собой саму программу. LLVMBuilder - класс, который предоставляет средства для создания операций и инструкций в блоке BasicBlock - представляет блок программы, в которой находяться инструкции и операции Value - основной класс llvm api, представляет собой некую сущность, которая может являться переменной, инструкцией, блоком, и т.д. мы будем использовать её для сохранения значения математичсеких выражений =map<string, Value>= - карта, в которой будут храниться значения переменных Далее определим функцию initModule которая будет инициализировать модуль: void initModule(){
module = new Module("test"); //создаем модуль с названием "test"
Constant *c = module->getOrInsertFunction("main", //создам функцию - точку входа в программу
IntegerType::get(32), //тип возвращаемого значения ф-ции - i32
NULL); //параметров нету, но в конце их перечисления должен быть NULL
Function *func = cast<Function>(c); //Приводим константу к типу Function
block = new BasicBlock("entry", func); //создаем блок, внутри функции - в этом блоке будет находиться весь основной код
builder = LLVMBuilder(block); //создаем объект LLVMBuilder для работы с созданным блоком
}Соответственно после синтаксического анализа должна выполниться ф-ция releaseModule, которая добавит в конце блока инструкцию ret i32 0 для завершения приложения и выведет код приложения на языке llvm на экран: void releaseModule(){
new ReturnInst(ConstantInt::get(IntegerType::get(32), 0), block);
verifyModule(*module, PrintMessageAction);
PassManager PM;
PM.add(new PrintModulePass(&llvm ::cout));
PM.run( *module);
}Обработка синтаксических выражений Далее нам необходимо обработать выражения, т.е. привязать добавление какой-то операции к каждому правилу, определим тип Variable в секции union в sample.l:
%union{
int value
char * string
Value * node
}
Далее определим типы правил math_expression, value, identifier, как node, для того , что бы передавать значения математических выражений в стеке bison'a: %type < node > math_expression %type < node > value %type < node > identifier Далее опишем правило value для добавления в стек целочисленного значения. Для этого нам требуется выделить память для типа i32, установить значение в выделеной области памяти. Для этого воспользуемся классами из llvm api : AllocaInst и StoreInst. В стек bison'a мы отправим указатель на выделенную с помощью инструкции alloca область памяти: value : VALUE
{
llvm::Value * value_ = new AllocaInst(IntegerType::get(32), "tmp", block);
new StoreInst(ConstantInt::get(IntegerType::get(32), $1), value_, block);
$$ = value_ ;
}
Затем необходимо описать правило для присваивания ( assign_statement ) в данном правиле мы добавим/установим значение переменной , переданой по стеку bison'a с помощью карты ( map < string, Value > variables ), : assign_statement : IDENTIFIER tASN math_expression
{
string str($1);
variables[str]=$3;
}
;Опишем правила для identifier , сдесь нам необходимо покласть в стек bison'a значение, которое соответствует заданой переменной, данное значение мы можем взять из карты variables, в случае необнаружения объекта в карте, вывести ошибку, иначе - покласть в стек значение, соответствующее заданой переменной : identifier : IDENTIFIER
{
string str($1);
if(variables[str]==NULL){
string str = "Variable "+string($1)+" is not defined";
yyerror(str.c_str());
}else{
$$ = variables[str];
}
}
;Компиляция и запуск У нас есть обрабока правил для переменной и целочисленного значения, при отсутствии остальных правил мы можем скомпилировать приложение, для этого создадим Makefile: all: bison --defines=parser.h -o parser.cpp sample.y flex -o lexer.cpp sample.l g++ lexer.cpp parser.cpp `llvm-config --cppflags --ldflags --libs core jit native` -o sample Затем выполним команду make , далее создадим файл sample.s: a = 2 b = 3 и запустим sample с параметром sample.s: ; ModuleID = 'test'
define i32 @main() {
entry:
%tmp = alloca i32 ; <i32*> [#uses=1]
store i32 2, i32* %tmp
%tmp1 = alloca i32 ; <i32*> [#uses=1]
store i32 3, i32* %tmp1
ret i32 0
}Мы видим 4 операции - это результат выполнения двух правил value, которые выделяли память для переменной и записывали туда значения 2 и 3 Обработка выражений Далее необходимо "научить" наш компилятор обрабатывать выражения, для это мы определим правило math_expression для каждого случая: math_expression : value { //для получения целочисленного значения необходимо
//загрузить его , делаем это при помощи экземпляра класса
//LoadInst , куда передаем указатель на выделенную область
//памяти, которая находиться в стеке bison'a
$$ = new LoadInst($1,"tmp", false, 4, block); }
=|= identifier { $$ = $1;// получаем значение переменной из стека bison'a }
//при помощи экземпляра класса LLVMBuilder создаем операцию сложения для 2х выражений
=|= math_expression tPLS math_expression { $$ = builder.CreateAdd($1, $3, "add"); }
// вычитания
=|= math_expression tMNS math_expression { $$ = builder.CreateSub($1, $3, "sub"); }
// умножения
=|= math_expression tMLT math_expression { $$ = builder.CreateMul($1, $3, "mul"); }
// деления
=|= math_expression tDIV math_expression { $$ = builder.CreateUDiv($1, $3, "div"); }
;Теперь наш транслятор умеет выполнять арифмитические операции, для проверки создадим файл sample.s со следующим содержанием: a = 2+2-2*2 b = 3+3+a откомпилируем и запустим приложение с параметром sample.s ( ./sample sample.s ): ; ModuleID = 'test'
define i32 @main() {
entry:
%tmp = alloca i32 ; <i32*> [#uses=2]
store i32 2, i32* %tmp
%tmp1 = load i32* %tmp, align 4 ; <i32> [#uses=1]
%tmp2 = alloca i32 ; <i32*> [#uses=2]
store i32 2, i32* %tmp2
%tmp3 = load i32* %tmp2, align 4 ; <i32> [#uses=1]
%add = add i32 %tmp1, %tmp3 ; <i32> [#uses=1]
%tmp4 = alloca i32 ; <i32*> [#uses=2]
store i32 2, i32* %tmp4
%tmp5 = load i32* %tmp4, align 4 ; <i32> [#uses=1]
%tmp6 = alloca i32 ; <i32*> [#uses=2]
store i32 2, i32* %tmp6
%tmp7 = load i32* %tmp6, align 4 ; <i32> [#uses=1]
%mul = mul i32 %tmp5, %tmp7 ; <i32> [#uses=1]
%sub = sub i32 %add, %mul ; <i32> [#uses=1]
%tmp8 = alloca i32 ; <i32*> [#uses=2]
store i32 3, i32* %tmp8
%tmp9 = load i32* %tmp8, align 4 ; <i32> [#uses=1]
%tmp10 = alloca i32 ; <i32*> [#uses=2]
store i32 3, i32* %tmp10
%tmp11 = load i32* %tmp10, align 4 ; <i32> [#uses=1]
%add12 = add i32 %tmp9, %tmp11 ; <i32> [#uses=1]
%add13 = add i32 %add12, %sub ; <i32> [#uses=0]
ret i32 0
}Мы видим набор инструкций alloca, store , load , add, sub, mul. Со всеми инструкциями, кроме load мы познакомились ранее, инструкция load предназначена для загрузки значения переменной из памяти, её параметром является указатель на область памяти, выделенную для данной переменной, возвращаемое значение - значение данной переменной. Обработка правила для вывода на экран LLVM позволяет получить доступ к функциям стандартной библиотеки stdlib.h языка с, для вывода на экран значения мы воспользуемся функцией printf, для начала её использования в llvm, необходимо объявить данную функцию: declare i32 @printf(i8, i32)Для этого мы создадим функцию в sample.y void createPrintf() и будем вызывать её при инициализации модуля: void createPrintf(){
Constant * c = module->getOrInsertFunction("printf", // создаем декларацию функции
IntegerType::get(32), // возвращаемое значение
PointerType::get(IntegerType::get(8)), // 1й параметр - формат вывода
IntegerType::get(32), // 2й параметр - целое число
NULL); // завершаем перечисление параметров NULL'ом
pf = cast<Function>(c); //pf - глобальная переменная типа Function*, присваиваем ей значение полученое при создании ф-ции , преведенное к классу Function*
}Далее нам необходимо создать 2 вспомогающие функции: 1. =Value createStringConstant(Module mod, string value)= - для создания глобальной переменной , которая содержит строку 2. =Value createStringValue(Value value, BasicBlock block)= - для создания указателя на глобальную переменную Начнем с 1й. Для создания глобальной переменной воспользуемся классом GlobalValiable : Value * createStringConstant(Module * mod, string value){
vector < Constant * > values; //вектор для хранения значений массива, в котором будет храниться строка
for(int i=0;i<value.size();i++){ //заполняем вектор значениями
values.push_back(ConstantInt::get(IntegerType::get(8), value[i]));
}
values.push_back(ConstantInt::get(IntegerType::get(8), 0)); //в конце добавляем 0,т.к. в llvm строка должна быть null-terminated
GlobalVariable * var = new GlobalVariable(ArrayType::get(IntegerType::get(8),value.size()+1),//тип - в данном случае тип - массив с элементами i8, где храняться символы, размер - размер входной строки + 1, т.к. в конце добавлен 0
true, //является ли константой
GlobalValue::InternalLinkage,//тип
ConstantArray::get(ArrayType::get(IntegerType::get(8),value.size()+1), values),//определяем константное значение массива - это вектор с символами value
"str", //имя переменной глобальной переменной
mod);//имя текущего модуля
return var;
}createStringValue должна вернуть указатель на глобальну переменную в llvm узказатель можно получить с помощью инструкции getelementptrinst в llvm api данная инструкция записывается при помощи класса GetElementPtrInst : Value * createStringValue(Value * value, BasicBlock *block){
vector < Value * > vars;//массив с параметрами
vars.push_back(ConstantInt::get(Type::Int64Ty, 0)); //1й параметр
vars.push_back(ConstantInt::get(Type::Int64Ty, 0)); //2й параметр
//выполняем инструкцию getelementptr и результат её выполнения заносим в переменную str_addr
GetElementPtrInst * ptr = new GetElementPtrInst(value, vars.begin(), vars.end(),"str_addr", block);
return ptr;
}Т.к. выводить нам требуется целое значение, то 1й параметр printf уже известен - это "%d\n", для него можно завести глобальную переменну, для этого воспользуемся функцией createStringConstant, допишем к initModule ( ) fmtStr = createStringConstant(module, "%d\n"); fmtStr - глобальная переменная типа Value У нас все готово для вызова функции printf. Нам осталость определить правило для print_statement, создадим еще 1ну функцию, которая будет вызываться при обработке данного правила, назовем её callPrintf, входной параметр будет 1н - выражение, которое необходимо вывести на экран, для этого мы вызовем функцию printf с параметрами ("%d\", expr), где expr - переменная типа i32, в которой храниться значение выражения. Ссылку на значение выражения добавляет в стек обработчик правила math_expression. Для вызова функции в языке llvm существует инструкция call, в llvm api она представлена классом CallInst, которым мы воспользуемся для запуска: void callPrintf(Value *expr){
Value* fmtPtr = createStringValue(fmtStr, block) ;
vector< Value * > params ;
params.push_back(fmtPtr) ;
params.push_back(expr) ;
new CallInst ( pf, params.begin(), params.end(), "", block);
}Далее добавим вызов данной функции в правилах для print_statement :
print_statement : tPRN math_expression
{
callPrintf($2);
}
;Добавление циклов Теперь добавим циклы к нашему языку. Циклы будут выглядеть следующим образом: loop math_expression times .... end math_expression - математическое выражение. Опишем в файле синтаксического анализатора несколько токенов, для добавления циклов к языку: sample.y: % token tLOOP % token tTIMES % token tEND Далее нам необходимо "научить" лексический анализатор определять данные токены, для этого в файл описания граматики языка, мы добавим следующие лексемы: sample.l loop { return tLOOP; }
times { return tTIMES; }
end { return tEND; }Далее нам необходимо описать правила для цикла в файле синтаксического анализатора: sample.y loop_header : tLOOP math_expression tTIMES
{
}
;
loop_statement : loop_header program tEND
{
}
;Для создания цикла необходимо создать 3 блока: 1. Блок "верхушки" цикла; в котором будет объявляться переменная, которая впоследствии будет увеличиваться на 1, после объявления переменной (выделения памяти для нее и установки начального значения) , выполняется оператор безусловного перехода к блоку 3 2. Блок "тела" циклa; может содержать в себе все допустимые операции, после выполнения данных операций выполняется безусловный переход к блоку 3 3. Блок "условия"; вначале выполняется инкремент переменной, определенной в 1. , затем, если значение данной переменной меньше , чем значение выражения, то осуществляется переход к 2. иначе - переход к следующему блоку. Так же создадим дополнительный блок, блок, который будет следовать после цикла. Для представления цикла создадим класс, который будет содержать необходимые блоки, данный класс мы будем передавать от правила loop_header правилу loop_statement при помощи стека bison'a для того, что бы закрыть блоки инструкциями условного и безусловного перехода. sample.h class LoopNode {
public:
LoopNode(){}
BasicBlock * condBlock; //блок 3.
BasicBlock * entryBlock; //блок 2.
BasicBlock * nextBlock; //дополнительный блок
Value * incrVar; // переменная, которую следует увеличивать после каждого "прохода"
Value * cond; //выражение, сравнивающее значение переменной с значением математического выражения
};Опишем типы правил loop_header и loop_statement: sample.y % type < loopNode > loop_header % type < loopNode > loop_statement Далее нам необходимо инициализировать функции : - LoopNode createDefHeader(Value times) - ф-ция возвращает указатель на экземпляр класса LoopNode, с заполненными полями, создает основные блоки и безусловные переходы - BasicBlock getNextBlock ( BasicBlock cur ) - ф-ция возвращает указатель на блок следующий за данным - void buildIncrInst(LoopNode node, BasicBlock block) - ф-ция создает инструкцию загрузки переменной для подсчета количества пройденных циклов , инструкцию её увеличиения на 1н и установки нового значения Далее необходимо определить данные функции. Начнем с getNextBlock: sample.y BasicBlock * getNextBlock(BasicBlock * cur){
Function * func = cur->getParent(); //получаем функцию, в которой находится данный блок
if(cur!=func->end()){
Function::iterator blocks = cur; //итератор функции по блокам
return blocks++; //возвращаем следующий
}
return NULL;
}Определим buildIncrInst() void buildIncrInstr(LoopNode *node, BasicBlock *block){
Value* li = new LoadInst(node->incrVar, "ival", false, 4, block); //получаем значение переменной
LLVMBuilder(block).CreateAdd(li, ConstantInt::get(IntegerType::get(32), 1), "addv"); //создаем оператор сложения
new StoreInst(li, node->incrVar, false, 4, block); //сохранить новое значение
}Далее определим функцию createDefHeader() LoopNode* createDefHeader(Value * *times){
Function* func = curBlock->getParent(); //получаем функцию, в которой находиться данный блок
BasicBlock* condBlock = new BasicBlock("for_cond", func); //создаем блок "условия"
BasicBlock* entryBlock = new BasicBlock("for_entry", func); //создаем исполняемый блок цикла
BasicBlock* mainBlock = new BasicBlock("main_block", func); //создаем дополнительный блок
BasicBlock* forHead = new BasicBlock("for_head", func);//создаем блок "шапки" функции
Value *alloci = new AllocaInst(IntegerType::get(32),(Value*)0, 4, "ifi", forHead); //выделяем память для переменной для инкремента
new StoreInst(ConstantInt::get(IntegerType::get(32), 0), alloci,false, 4, forHead);//устанавливаем нулевое значение для для переменной
new BranchInst(condBlock, forHead);//создаемм безусловный переход из блока в "шапки" цикла в блок с условием
forHead->moveAfter(curBlock); //помещаем блок с шапкой цикла после текущего
entryBlock->moveAfter(forHead); //помещаем исполняемый блок функции после "шапки"
condBlock->moveAfter(entryBlock); //помещаем блок с проверкой условия после исполняемого
Value * ilval = new LoadInst(alloci, "tmp", false, 4, condBlock); //загружаем значение переменной для инкремента для проверки условия
Value * cond = new ICmpInst(ICmpInst::ICMP_SLE, ilval, times, "tmp", condBlock); //создаем условие при котором цикл продолжает работу
if(curBlock->getTerminator()==0) new BranchInst(forHead, curBlock); //помещаем безусловный переход к "шапке" цикла из текущего блока
mainBlock->moveAfter(condBlock); //помещаем дополнительный блок после блока с условием
LoopNode * loopNode = new LoopNode(); //возвращаем экземпляр класса LoopNode с установленными параметрами
loopNode->condBlock = condBlock;
loopNode->cond = cond;
loopNode->incrVar = alloci;
loopNode->entryBlock = entryBlock;
loopNode->nextBlock = mainBlock;
return loopNode;
}Далее необходимо описать правила для loop_header и loop_statement: loop_header : tLOOP math_expression tTIMES
{
$$ = createDefHeader($2); //помещаем в стек bison'a заголовок цикла
curBlock = $$->entryBlock; //текущий блок - выполняемый блок цикла
}
;
loop_statement : loop_header program tEND
{
$$ = $1;
buildIncrInstr($1, curBlock); //построение инструкции инкремента функции
BasicBlock * bb = getNextBlock($1->condBlock); //получаем блок, который следует за блоком с условием
if(bb!=0){ //если за блоком с инструкцией следует блок, то устанавливаем условный переход к выпоняемому блоку, если условие выполнения цикла выполняются
new BranchInst($1->entryBlock, bb, $1->cond, $1->condBlock);
}
if(curBlock->getTerminator()==0){
new BranchInst($1->condBlock, curBlock); //устанавливаем безусловный переход текущего блока к блоку проверки условия выполнения
}
curBlock = $1->nextBlock; //текущим блоком становиться блок, который является "дополниьельным"
}
;
Все, транслятор полностью готов, исходные тексты находятся в архиве [[sample.zip][sample.zip]] Компиляция в исполняемый код Для компиляции построеного приложения в бинарный код можно написать скрипт compile: # ! /bin/bash llvm-as $1 -o $1.bc llc $1.bc -o $1.s gcc $1.s -o $1.native далее $ chmod +x compile $ ./compile your.llvm.hr.coed Сылки на источники по теме: [http://www.gnu.org/software/bison/manual/[Мануал по инструментальному средству Bison]] [http://llvm[Вся документация по llvm находиться только сдесь и больше нигде]] [http://google.com[по-моему , ни один перечень источников информации не обходиться без данного]] |