В данной работе представлена реализация бинарного транслятора, который позволяет произвести трансляцию бинарного кода виртуального процессора Trollessor в нативный код архитектуры x86-64. Объединяя предыдущие проекты с данным, был получен JIT-компилятор языка Trollanguage, на целевую архитектуру.
В первой части проекта представлена реализация JIT-компилятора, подробно рассказано о трансляции поддерживаемых инструкций, о ряде концепций, примененных при разработке бинарного транслятора.
Вторая часть посвящена созданию и изучению строения собственного исполнимого и компонуемого файла (ELF-format). По итогу был создан AOT-компилятор, который на выходе создавал исполняемый файл.
Перед тем как начинать процесс трансляции бинарного кода, нужно сказать пару слов о формате машинных команд процессора Trollessor.
В первом семестре мною был разработан собственный виртуальный процессор, с бинарного кода которого и будет производится трансляция.
Работа моего процессора, основана на принципе обратной польской записи, что позволяет производить все операции через внутренний стек виртуального процессора. Машинная команда состоит из маски кода операции, занимающей 5 бит, и маски-спецификатора аргумента, состоящей из 3 бит.
Все операции, поддерживаемые моим процессором, занумерованы и имеют соответствующие коды масок. Маска-спецификатор состоит из трех битовых флагов, показывающих, с каким типом аргумента работает текущая инструкция: регистр, память, константа. Данный процессор поддерживает работу с числами с плавающей запятой типа double.
После озвучивания информации о формате машинной команды виртуального процессора, перейдем к первому этапу проекта, процессу перевода бинарного кода в промежуточное представление (IR).
Процесс бинарной трансляции включает в себя перевод бинарного кода в промежуточное представление, которое позволяет представить весь код в виде некоторого набора таких структур, удобных для последующей трансляции на целевую архитектуру.
Я решил реализовать создать массив структур, в которых будет храниться вся информация об конкретной операции. Обработка исходного бинарного кода похожа на процесс его обработки виртуальным процессором - парсим гостевой код.
typedef struct IR
{
IR_node *buffer;
int size;
} IR;typedef struct IR_node
{
uint32_t command;
Imm_val imm_val;
Address address;
uint8_t reg_num;
unsigned int is_mem_access : 1;
} IR_node;Помимо банальной обработки инструкции и заполнения полей структур требовалось правильно изменить адресацию, так как в начале все адреса были относительно гостевой архитектуры. При этом абсолютная адресация, применяемая в исходной архитектуре, изменялась на относительную. С помощью двух последовательных проходов по текущему коду, адрес изменялся на номер той IR_node, на адрес инструкции которой он ссылался.
Когда было получено представление кода в промежуточном виде, требовалось перевести его в машинный целевой архитектуры. Нужно построить логику работы каждой операции и заменить каждую структуру на набор соответствующих инструкций.
Далее приведена трансляция всех поддерживаемых инструкций моего процессора:
Данная инструкция может оперировать с различными аргументами. Мы можем помещать в стек значение регистра, либо константное значение, либо значение определенной ячейки оперативной памяти - так назывался массив, в котором производилось хранение чисел типа double.
PUSH reg + imm -> mov R13, imm
add R13, reg
push R13
Отдельное внимание стоит уделить процессу трансляции инструкций, работающих с памятью. Изначально, указатель на выделенный заранее участок памяти, помещается в регистр R12. Значение данного регистра сохраняется на протяжении всей работы программы.
Когда инструкция обращается к N-ой ячейке оперативной памяти, фактически происходит обращение к R12[N] (эффективный адрес). Стоит отметить, что из-за того, что все значения хранятся в стеке в виде double, то и значение регистра будет в аналогичном формате. То есть при попытке обращения к N-ой ячейке, нужно перевести этот N в целочисленное представление.
Также относительный адрес требуется умножить на 8, чтобы учесть размер типа, в котором хранятся значения в памяти.
PUSH [reg + imm] -> mov R13, imm
push reg
push reg
movsd xmm0, [rsp]
add rsp, 8
CVTTSD2SI reg, xmm0
add R13, reg
pop reg
shl R13, 3
add R13, R12
mov R13, [R13]
push R13
Способ трансляции данной операции концептуально не отличается от PUSH, поэтому приведу лишь соответствующий набор инструкций архитектуры x86-64
POP reg -> pop reg
И операция с обращением к памяти соответственно:
POP [reg + imm] -> mov R13, imm
push reg
push reg
movsd xmm0, [rsp]
add rsp, 8
CVTTSD2SI reg, xmm0
add R13, reg
pop reg
shl R13, 3
add R13, R12
movsd xmm0, [rsp]
add rsp, 8
movsd [r13], xmm0
Стоит отметить, что некоторые аргументы в приведенных операциях могут и отсутствовать. Допустимы перемещения в стек значения лишь регистров или констант. От этого не поменяется логика работы набора транслированных инструкций.
Так как работа моего виртуального процессора основана на обратной польской записи, то было решено не менять концепцию и в конечном машинном коде целевой архитектуры, хотя такая реализация не является эффективной:
OP -> movsd xmm0, [rsp]
movsd xmm1, [rsp+8]
OP xmm1, xmm0 (addsd, subsd, mulsd, divsd)
add rsp, 8
movsd [rsp], xmm1
Самым сложным в трансляции инструкций являлось правильное изменение адресации, логика которой аналогична ранее приведенному процессу в IR. Требовалось изменить абсолютную адресацию на относительную, что было сделано с помощью двупроходной системы.
Безусловный переход:
JMP -> jmp addr
И условные соответственно:
J__ -> movsd xmm0, [rsp]
movsd xmm1, [rsp+8]
cmp xmm0, xmm1
j__ addr
CALL -> call addr
RET -> ret
Данная инструкция во много похожа на RET, но при этом требуется перед ней поместить адрес возврата, сохраненного в регистре R10 в самом начале работы программы.
HLT -> push R10
ret
Стандартный ввод и вывод поддерживался в моем виртуальном процессоре с помощью команд IN и OUT, которые содержали в себе стандартные функции ввода и вывода языка C.
Трансляция этих операций происходила следующим образом. Мною были написаны функции, которые использовали в себе стандартные функции ввода и вывода, при этом их аргументом являлся адрес выводимого числа, которое лежало в этот момент на верхушке стека.
void doublePrintf (double *value)
{
printf ("%0.1lf\n\n", *value);
}
void doubleScanf (double *value)
{
scanf ("%lf", value);
}Затем вызывались указанные мною функции, при этом сохранялись значения некоторых регистров.
IN -> sub rsp, 8
lea rdi, [rsp]
call addr (doubleScanf)
OUT -> lea rdi, [rsp]
call addr (doublePrintf)
add rsp, 8
После завершения трансляции бинарного кода менялись права на исполнение буфера, с помощью функции mprotect, в котором он лежал. После этого происходило его исполнение (фактически же вызывалась функция).
Теперь можно провести исследование, в котором можно сравнить скорость работы моего виртуального процессора и транслированного ранее кода.
Время работы транслятора не учитывалось.
Чтобы влияние времени трансляции было минимальным, проверка происходила на вложенных циклах - в сумме 4000000 повторений. В результате производительность была увеличена приблизительно в 100 раз.
| режимы | время | ускорение |
|---|---|---|
| виртуальный | 16260.3 msec | 1.0 |
| реальный | 150.4 msec | 102.7 |
Следующей частью моего проекта стало создание собственного ELF, в котором и будет располагаться транслированный код. При этом требуется внести некоторые доработки в процесс трансляции, так как требуется правильно обращаться к памяти, производить ввод и вывод.
С помощью библиотеки <elf.h>, которая позволяет работать с ELF-форматом в рамках структур языка C, были получены программные заголовки, заголовок самого файла.
В качестве памяти, в которой хранятся числа, был выделена была переработана система адресации.
Было решено использовать ранее написанный на языке ассемблера trolloprint, в качестве стандартного вывода. Бинарный код данной функции помещался в отдельную секцию, что позволяло избежать трудностей с неправильной адресацией.
После всех приготовлений записывался ранее транслированный код, который также помещался в отдельную секцию.
После завершения работы трансляции, получается готовый исполняемый файл, запуск которого приводит к выполнению программы, ранее написанной на Trollanguage.