Сучасні компілятори дуже добре вміють оптимізувати код. Вони видаляють умовні переходи, які ніколи не виконуються, обчислюють костянтні вирази, позбавляються від безглуздих арифметичних дій (множення на 1, додавання з 0). Вони оперують даними, відомими на момент компіляції.
У момент виконання інформації про оброблювані дані набагато більше. На її підставі можна виконати додаткові оптимізації і прискорити роботу програми.
Оптимізований для приватного випадку алгоритм завжди працює швидше універсального (принаймні, не повільніше).
Що якщо для кожного набору вхідних даних створювати оптимальний для обробки цих даних алгоритм?
Очевидно, частина часу виконання піде на оптимізацію, але якщо оптимізований код виконується часто, витрати окупляться з лишком.
Як же технічно це зробити? Досить просто - в програму включається міні-компілятор, що генерує необхідний код. Ідея не нова, технологія називається «компіляція часу виконання» або JIT-компіляція. Ключову роль JIT-компіляція відіграє у віртуальних машинах та інтерпретаторах мов програмування. Часто використовувані ділянки коду (або байт-коду) перетворюються на машинні команди, що дозволяє сильно підвищити продуктивність.
Java, Python, C #, JavaScript, Flash Ac^ Script - неповний (зовсім неповний) список мов, в яких це використовується. Я пропоную вирішити конкретну задачу з використанням цієї технології і подивитися, що вийде.
Завдання
Завданням візьмемо реалізацію інтерпретатора математичних виразів. На вході у нас рядок виду
і число - значення x. На виході повинні отримати число - значення виразу при цьому значенні x. Для простоти будемо обробляти тільки чотири оператори - «+», «-», «*», «/».
На даному етапі ще не зрозуміло, як взагалі можна скомпілювати цей вираз, адже рядок - не найзручніший для роботи спосіб представлення. Для аналізу та обчислень краще підійде дерево розбору, в нашому випадку - бінарне дерево.
Для вихідного виразу він виглядатиме так:
Кожен вузол дерева являє собою оператор, його діти - операнди. У листях дерева виявляються константи і змінні.
Найпростішим алгоритмом побудови такого дерева є рекурсивний спуск - на кожному етапі ми знаходимо оператор з найменшим пріоритетом, розбиваємо вираз на дві частини - до цього оператора і після, і рекурсивно викликаємо для цих частин операцію побудови. Покрокова ілюстрація роботи алгоритму:
Реалізацію алгоритму я тут приводити не буду з простої причини - він досить об'ємний, та й стаття не про це.
Дерево складається з вузлів, кожен з яких буде представлений структурою TreeNode
typedef struct TreeNode TreeNode;
struct TreeNode
{
TreeNodeType type ;//тип вузла
TreeNode * left ;//посилання на лівого нащадка
TreeNode * right ;//посилання для правого нащадка
float value ;//значення (для вузла константи)
};
Ось всі можливі типи вузлів:
typedef enum
{
OperatorPlus ,//Оператор плюс
OperatorMinus ,//Оператор мінус
OperatorMul ,//Оператор помножити
OperatorDiv ,//Оператор розділити
OperandConst ,//Операнд - константа
OperandVar ,//Операнд - змінна
OperandNegVar ,//Операнд - змінна, взята з мінусом (для обробки унарного мінуса)
} TreeNodeType;
Значення виразу при вказаному x обчислюється дуже просто - за допомогою обходу в глибину.
Це теж реалізується за допомогою рекурсії.
float calcTreeFromRoot(TreeNode* root, float x)
{
if(root->type == OperandVar)
return x;
if(root->type == OperandNegVar)
return -x;
if(root->type == OperandConst)
return root->value;
switch(root->type)
{
case OperatorPlus:
return calcTreeFromRoot(root->left, x) + calcTreeFromRoot(root->right, x);
case OperatorMinus:
return calcTreeFromRoot(root->left, x) - calcTreeFromRoot(root->right, x);
case OperatorMul:
return calcTreeFromRoot(root->left, x) * calcTreeFromRoot(root->right, x);
case OperatorDiv:
return calcTreeFromRoot(root->left, x) / calcTreeFromRoot(root->right, x);
}
}
Що на поточний момент?
- Для виразу створюється дерево
- При необхідності обчислити значення виразу викликається рекурсивна функція calcTreeFromRoot
Як би виглядав код, якби ми знали вираз ще на етапі збірки?
float calcExpression(float x)
{
return x * x + 5 * x - 2;
}
Обчислення значення виразу в такому випадку зводиться до виклику однієї дуже простої функції - в рази швидше, ніж рекурсивний обхід дерева.
Час компіляції!
Хочу зауважити, що я буду генерувати код для платформи x86 орієнтуючись на процесори архітектури, схожої з IA32. Крім того, я прийму розмір float рівним 4 байтам, розмір int рівним 4 байтам.
Теорія
Отже, наше завдання отримати звичайну функцію мови C, яку можна буде викликати при необхідності.
Для початку, визначимо її прототип:
typedef float _cdecl (*Func)(float);
Тепер тип даних Func є покажчиком на функцію, що повертає значення типу float і приймає один аргумент, теж типу float.
_ cdecl вказує на те, що використовується угода про виклик C-declaration.
Це стандартна угода про виклик для мови C:
- аргументи передаються через стек праворуч на ліворуч (при виклику на вершині стека повинен виявитися перший аргумент)
- цілисні значення повертаються через регістр EAX
- значення з плаваючою точкою повертаються через регістр st0
- За збереження регістрів eax, edx, ecx відповідає зухвала функція
- решта регістрів повинна відновлювати викликану функцію
Виклик функції виглядає приблизно так:
push ebp//Зберігаємо курсор скляного кадру
push arg3//Клацніть у стек аргументи в порядку праворуч на ліворуч (перший аргумент наприкінці)
push arg2
push arg1
call func//Сам виклик
add esp, 0xC//Відновлюємо вказівник на стек (3 аргументи по 4 байти якраз займуть 0xC байт)
pop ebp//Відновлюємо стікельний кадр
Стан стека в момент виклику:
Як ми будемо генерувати код, що обчислює вираз? Час згадати, що є така штука як скловий калькулятор. Як він працює? На вхід подаються числа і оператори. Алгоритм роботи елементарний:
- Зустріли константу або змінну - поклали в стек
- Зустріли оператор - зняли зі стека 2 операнда, зробили операцію, поклали результат у стек
Але годувати скловий калькулятор треба певним чином - він працює з виразами, представленими у зворотній польській нотації. Її особливість полягає в тому, що в записі спершу йдуть операнди, потім оператор. Таким чином наш вихідний вираз постане в наступному вигляді:
Програма для склового калькулятора відповідає виразу:
push x
push x
mul
push 5
push x
mul
add
push 2
sub
Дуже нагадує програму на асемблері, чи не так?
Виходить, достатньо перевести вираз у зворотну польську нотацію і створювати код дотримуючись елементарних правил.
Переклад виконати дуже просто - у нас вже є побудоване дерево розбору, треба тільки виконати обхід в глибину і при виході з вершини генерувати відповідну їй дію - вийде послідовність команд в потрібному нам порядку.
Псевдокод цього дійства:
static void generateCodeR(TreeNode* root, ByteArray* code)
{
if(root->left && root->right)
{
generceCodeR (root- > right, code) ;//Спочатку слід створити
generceCodeR (root- > left, code) ;//код обчислення дочірніх елементів
}
//Генеруємо код батьківського елемента
if(root->type == OperandVar)
{
code + = "" push x ";//Клацніть у стек значення аргументу (змінна)
}
else if(root->type == OperandNegVar)
{
code + = "" push -x ";//Клацніть у стек значення аргументу зі зміною знака
}
else if(root->type == OperandConst)
{
code + = "" push "+ root- > value ;//Кладіть у стек константу
}
else
{
code + = "" pop ";//Знімаємо зі стека
code + = "" pop ";//два значення
switch(root->type)
{
case OperatorPlus:
code + = «add» ;//Виконуємо додавання
break;
case OperatorMinus:
code + = "" sub ";//Виконуємо віднімання
break;
case OperatorMul:
code + = "" mul ";//Виконуємо множення
break;
case OperatorDiv:
code + = "" div ";//Виконуємо поділ
break;
}
code + = "" push result "//Зберігаємо результат математичної операції
}
}
Реалізація
Для початку визначимося зі стеком: з ним все просто - регістр esp містить покажчик на вершину. Щоб покласти що-небудь туди, достатньо виконати команду
push {значення}
або відняти з ESP число 4 і записати за отриманою адресою потрібне значення
sub esp, 4
mov [esp], {значення}
Зняття зі стека виконує команда pop або додавання до esp число 4.
Раніше я згадав угоду про виклик. Завдяки йому ми можемо точно знати, де буде знаходитися єдиний аргумент функції. За адресою esp (на вершині) буде адреса повернення, а за адресою esp - 4 якраз буде знаходитися значення аргументу. Оскільки звернення до нього буде відбуватися порівняно часто можна помістити його в регістр eax:
mov eax, [esp - 4];
Тепер, трохи про роботу з числами з плаваючою комою. Ми будемо використовувати набір інструкцій x87 FPU.
FPU має 8 регістрів, що утворюють стек. Кожен з них вміщує 80 біт. Звернення до вершини цього стека відбувається через регістр st0. Відповідно, регістр st1 адресує наступне за вершиною значення в цьому стеку, st2 - наступне і так далі до st7.
Стек FPU:
Для завантаження на вершину значення використовується команда fld. Операндом цієї команди може бути тільки зберігається в пам'яті значення.
fld [esp ]//Завантажити до st0 значення, що зберігається за адресою esp
Команди для виконання арифметичних операцій дуже прості: fadd, fsub, fmul, fdiv. У них може бути багато різних комбінацій аргументів, але ми будемо використовувати їх тільки так:
fadd dword ptr [esp]
fsub dword ptr [esp]
fmul dword ptr [esp]
fdiv dword ptr [esp]
У всіх цих випадках завантажується значення з [esp], виконується необхідна операція, результат зберігається в st0.
Зняти значення зі стека теж просто:
fstp [esp ]//Вилучити значення з верхівки FPU стека і зберегти його в комірку пам'яті за адресою esp
Згадаймо, що у вираженні може зустрітися змінна x з унарним мінусом. Для її обробки треба змінити знак. Для цього гам стане в нагоді команда FCHS - вона інвертує біт знака регістру st0
Для кожної з цих команд визначимо за функцією, що генерує необхідні опкоди:
void genPUSH_imm32(ByteArray* code, int32_t* pValue);
void genADD_ESP_4(ByteArray* code);
void genMOV_EAX_PTR_ESP_4(ByteArray* code);
void genFSTP(ByteArray* code, void* dstAddress);
void genFLD_DWORD_PTR_ESP(ByteArray* code);
void genFADD_DWORD_PTR_ESP(ByteArray* code);
void genFSUB_DWORD_PTR_ESP(ByteArray* code);
void genFMUL_DWORD_PTR_ESP(ByteArray* code);
void genFCHS(ByteArray* code);
Щоб код-обчислювач нормально відпрацював і повернув значення треба додати перед ним і після нього відповідні інструкції. Вся ця справа разом збирає функція-обгортка generceCode:
void generateCode(Tree* tree, ByteArray* resultCode)
{
ByteArray* code = resultCode;
genMOV_EAX_ESP_4 (code) ;//Розміщуємо значення аргументу eax
generceCodeR (tree- > root, code) ;//Генеруємо код-обчислювач
genFLD_DWORD_PTR_ESP(code);
genADD_ESP_4 (code) ;//Знімаємо зайве подвійне слово зі стека
genRET (code) ;//Виходимо з функції
}
Кінцевий вигляд функції генерації коду, що обчислює значення виразу:
void generateCodeR(TreeNode* root, ByteArray* resultCode)
{
ByteArray* code = resultCode;
if(root->left && root->right)
{
generateCodeR(root->right, code);
generateCodeR(root->left, code);
}
if(root->type == OperandVar)
{
genPUSH_EAX (code) ;//eax лежить аргумент функції
}
else if(root->type == OperandNegVar)
{
genPUSH_EAX (code) ;//Завантажуємо у стек
genFLD_DWORD_PTR_ESP (code) ;//Змінюємо
genFCHS (code) ;//знак
genFSTP_DWORD_PTR_ESP (code) ;//Повертаємо до стек
}
else if(root->type == OperandConst)
{
genPUSH_imm32(code, (int32_t*)&root->value);
}
else
{
genFLD_DWORD_PTR_ESP (code) ;//Завантажуємо лівий операнд FPU.
genADD_ESP_4 (code) ;//... і знімаємо його зі стека
switch(root->type)
{
case OperatorPlus:
genFADD_DWORD_PTR_ESP (code) ;//Виконуємо додавання (результат зберігається у st0)
break;
case OperatorMinus:
genFSUB_DWORD_PTR_ESP (code) ;//Виконуємо віднімання (результат збережеться у st0)
break;
case OperatorMul