Low Level Virtual Machine

Low Level Virtual Machine (LLVM) - універсальна система аналізу, трансформації та оптимізації програм, що реалізує віртуальну машину з RISC -подібними інструкціями. Може використовуватися як оптимізуючий компілятор цього байткод в машинний код для різних архітектур або для його інтерпретації та JIT -компіляції (для деяких платформ).

LLVM (за допомогою різних фронтенді, в тому числі сторонніх) дозволяє компілювати програми, написані на мовах З, C + +, Objective-C, Fortran, Ada, Haskell, Java, Python, Ruby, JavaScript, GLSL. В рамках проекту LLVM був розроблений фронтенд Clang для мов C і C + + і версія GCC, що використовують llvm в якості бекенда. В Glasgow Haskell Compiler також реалізована компіляція допомогою llvm. Існує безліч програм, що використовують дану інфраструктуру.


1. Історія

Історія LLVM почалася в 2000 році в Університеті Іллінойсу. В даний час LLVM використовується, зокрема, в компаніях Adobe, Apple і Google. Зокрема, на LLVM заснована підсистема OpenGL в Mac OS X 10.5, а iPhone SDK використовує фронтенд GCC з бекенда на LLVM. Apple і Google є одними з основних спонсорів проекту, а натхненник LLVM - Кріс Латтнер - тепер працює в Apple.


2. Особливості

В основі LLVM лежить проміжне представлення коду ( Intermediate Representation, IR ), Над яким можна проводити трансформації під час компіляції, компонування і виконання. З цього уявлення генерується оптимізований машинний код для цілого ряду платформ, як статично, так і динамічно ( JIT -компіляція). LLVM 3.1 підтримує статичну генерацію коду для x86, x86-64, ARM, PowerPC, SPARC, MIPS, Qualcomm Hexagon. JIT (генерація машинного коду під час виконання) підтриманий для архітектур x86, x86_64, PowerPC, MIPS і частково ARM (тільки цілочисельні, без NEON та Thumb) [1]

LLVM написана на C + + і перенести на більшість * Nix -систем і Windows. Система має модульну структуру, окремі її модулі можуть бути вбудовані в різні програмні комплекси, вона може розширюватися додатковими алгоритмами трансформації і кодогенераторамі для нових апаратних платформ.

У LLVM включена обгортка API для OCaml.


3. Платформи

LLVM підтримує роботу на наступних платформах:

Операційна система Архітектура Компілятор
FreeBSD x86 GCC, Clang
FreeBSD AMD64 GCC, Clang
Linux AMD64 GCC, Clang
Linux x86 GCC, Clang
Mac OS X PowerPC GCC
Mac OS X x86 GCC, Clang
Solaris UltraSPARC GCC
Cygwin / Win32 x86 GCC 3.4.X, Binutils 2.15
MinGW / Win32 x86 GCC 3.4.X, Binutils 2.15


LLVM має часткову підтримку наступних платформ:

Операційна система Архітектура Компілятор
Windows x86 MSVC
AIX PowerPC GCC
Linux PowerPC GCC

4. Типи даних

4.1. Прості типи

Цілі числа довільної розрядності i розрядність
  • i1 - булеве значення - 0 або 1
  • i32 - 32-розрядне ціле
  • i17
  • i256
  • Генерація машинного коду для типів дуже великої розрядності не підтримується. Але для проміжного представлення ніяких обмежень немає.
  • Числа вважаються представленими в додатковому коді. Відмінностей між знаковими і беззнаковими цілими на рівні типів не робиться: у тих випадках, коли це має значення, з ними працюють різні інструкції.
Числа з плаваючою крапкою float, double, типи, специфічні для конкретної платформи (наприклад, x86_fp80)
Порожнє значення void

4.2. Похідні типи

Покажчики тип * i32 * - покажчик на 32-бітове ціле
Масиви [Число елементів x тип]
  • [10 x i32]
  • [8 x double]
Структури {I32, i32, double}
Вектор - спеціальний тип для спрощення SIMD -операцій. Вектор складається з 2n значень примітивного типу - цілого або з плаваючою точкою.
<Число елементів x тип> <4 x float> - вектор XMM
Функції
  • i32 (i32, i32)
  • float ({float, float}, {float, float})

Система типів рекурсивних, тобто можна використовувати багатовимірні масиви, масиви структур, покажчики на структури та функції і т. д.


5. Операції

Більшість інструкцій у LLVM приймають два аргументи (операнда) і повертають одне значення (триадресну код). Значення визначаються текстовим ідентифікатором. Локальні значення позначаються префіксом %, а глобальні - @. Локальні значення також називають регістрами, а LLVM - віртуальною машиною з нескінченним числом регістрів. Приклад:

 % Sum = add i32% n, 5% diff = sub double% a,% b% z = add <4 x float>% v1,% v2; поелементне додавання% cond = icmp eq% x,% y; Порівняння цілих чисел . Результат має тип i1. % Success = call i32 @ puts (i8 *% str) 

Тип операндів завжди вказується явно, і однозначно визначає тип результату. Операнди арифметичних інструкцій повинні мати однаковий тип, але самі інструкції "перевантажені" для будь-яких числових типів і векторів.

LLVM підтримує повний набір арифметичних операцій, побітових логічних операцій і операцій зсуву, а також спеціальні інструкції для роботи з векторами.

LLVM IR суворо типізовані, тому існують операції приведення типів, які явно кодуються спеціальними інструкціями. Набір з 9 інструкцій покриває всілякі приведення між різними числовими типами: цілими і з плаваючою точкою, зі знаком і без, різної розрядності і пр. Крім цього є інструкції перетворення між цілими і покажчиками, а також універсальна інструкція для приведення типів bitcast (відповідальність за коректність таких перетворень покладається на програміста).


6. Пам'ять

Крім значень-регістрів, в LLVM є і робота з пам'яттю. Значення в пам'яті адресуються типізований покажчиками. Звернутися до пам'яті можна за допомогою двох інструкцій: load та store. Наприклад:

 % X = load i32 *% x.ptr; завантажити значення типу i32 за вказівником% x.ptr% tmp = add i32% x, 5; додати 5 store i32% tmp, i32 *% x.ptr; та покласти назад 

Інструкція malloc транслюється у виклик однойменної системної функції і виділяє пам'ять на купі, повертаючи значення - покажчик певного типу. У парі з нею йде інструкція free.

 % Struct.ptr = malloc {double, double}% string = malloc i8, i32% length% array = malloc [16 x i32] free i8 *% string 

Інструкція alloca виділяє пам'ять на стеку.

 % X.ptr = alloca double;% x.ptr має тип double *% array = alloca float, i32 8;% array має тип float *, а не [8 x float]! 

Пам'ять, виділена alloca, автоматично звільняється при виході з функції за допомогою інструкцій ret або unwind.


7. Операції з вказівниками

Для обчислення адрес елементів масивів, структур і т. д. з правильною типізацією виконується за допомогою інструкції getelementptr.

 % Array = alloca i32, i32% size% ptr = getelementptr i32 *% array, i32% index; значення типу i32 * 

getelementptr тільки обчислює адресу, але не звертається до пам'яті. Інструкція приймає довільну кількість індексів і може разименовивать структури будь-якої вкладеності.

Також існує інструкції extractvalue і insertvalue. Вони відрізняються від getelementptr тим, що приймають не покажчик на агрегатний тип даних (масив або структуру), а саме значення такого типу. extractvalue повертає відповідне значення піделементи, а insertvalue породжує нове значення агрегатного типу.

 % N = extractvalue {i32, [4 x i8 *]}% s, 0% tmp = add i32% n, 1% s.1 = insertvalue {i32, [4 x i8 *]}% s, i32% tmp, 0 

Примітки

  1. The LLVM Target-Independent Code Generator - llvm.org / docs / CodeGenerator.html # targetimpls розділ Target Feature Matrix