Original:http://felixangell.com/blog/an-introduction-to-llvm-in-go

<- home

Введение в LLVM в Go

Новости Hacker Dicussion Обсуждение статьи о новостях Hacker

Японский перевод Вот японский перевод этой статьи!

Введение

LLVM - это инфраструктура для создания компиляторов. Он был первоначально создан Крисом Лэттнером в 2000 году и выпущен в 2003 году. С тех пор он превратился в зонтичный проект с широким набором инструментов, таких как LLVM lld , LLVM Debugger lldb и т. Д.

Баннерной особенностью LLVM является его промежуточное представление, обычно называемое LLVM IR . Идея LLVM заключается в том, что вы можете скомпилировать этот IR, а затем этот IR может быть скомпилирован, интерпретирован или скомпилирован в собственную сборку для машины, на которой он запущен. Основной целью этого IR является компилятор, на самом деле есть много компиляторов, которые используют LLVM: clang и clang ++ для C и C ++ соответственно, ldc2 для языка программирования D, язык Rust, Swift и т. Д. Есть даже проекты, такие как emscripten , который может скомпилировать LLVM BC (бит-код LLVM) в javascript для выполнения в браузере.

Как правило, в дизайне компилятора вам придется беспокоиться о распределении регистров, генерации кода для разных архитектур, а также создании хорошего кода, который хорошо оптимизирован. Красота LLVM заключается в том, что она делает это за вас. LLVM обладает обширной коллекцией оптимизаций, может ориентироваться на различные архитектуры и имеет хороший API, который значительно упрощает создание кода.

LLVM IR

Теперь давайте быстро взглянем на LLVM IR. Если вы возьмете свою среднюю программу C и запустите ее через clang с -emit-llvm и -S флагом, она .ll файл .ll . Это расширение файла означает, что это LLVM IR.

Вот код C, который я собираюсь скомпилировать в LLVM IR:

int main() {
  int a = 32;
  int b = 16;
  return a + b;
}

Я стартовал clang test.c -S -emit-llvm -O0 его через clang, указав, что ничего не оптимизировать: clang test.c -S -emit-llvm -O0 :

define i32 @main() #0 {
  %1 = alloca i32, align 4
  %a = alloca i32, align 4
  %b = alloca i32, align 4
  store i32 0, i32* %1
  store i32 32, i32* %a, align 4
  store i32 16, i32* %b, align 4
  %2 = load i32, i32* %a, align 4
  %3 = load i32, i32* %b, align 4
  %4 = add nsw i32 %2, %3
  ret i32 %4
}

Я просто пропустил лишний код для простоты. Если вы посмотрите на IR, это очень похоже на более подробный, читаемый сборник. Что-то, что вы можете заметить, это то, что IR строго типизирован. Во всем мире есть аннотации типов, инструкции, значения, функции и т. Д.

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

В нашей функции есть куча значений и инструкций. В IR мы видим 5 инструкций, alloca , store , load , add и ret .

Давайте разобьем IR по частям, чтобы понять, как это работает. Обратите внимание, что я проигнорировал несколько вещей, а именно выравнивание и флаги nsw . Вы можете больше узнать о документах LLVM, я просто объясню лежащую в основе семантику.

Местные жители

Прежде чем мы перейдем к инструкциям, вы должны знать, что такое местный. Местные жители похожи на переменные. Они обозначаются символом процента % . Как следует из названия, они являются локальными для функции, в которой они определены. Это означает, что они не могут быть изменены / указаны за пределами функции, объявляющей их.

alloca

Эта инструкция будет выделять память в фрейме стека. Эта память освобождается при возврате функции. Команда возвращает значение, поэтому мы назначаем его %a и т. Д. Возвращаемое значение является указателем на выделенную память. Например:

%a = alloca i32, align 4

Эта команда выделяет пространство для 32-разрядного целого числа со знаком в стеке. Указатель хранится в локальном a .

store

Инструкция store изменит значение на указанном указателе, чтобы оно содержало заданное значение. Вот пример, чтобы упростить объяснение:

 store i32 32, i32* %a, align 4 

Здесь мы i32 LLVM для хранения значения 32 типа i32 в локальном a типа i32* (указатель на i32). Эта команда возвращает void, т. Е. Ничего не возвращает и не может быть назначена локальному.

load

Наконец, инструкция load . Эта команда вернет значение по указанному адресу памяти:

 %2 = load i32, i32* %a, align 4 

В приведенном выше примере мы загружаем значение типа i32 из адреса памяти a (который является указателем на i32 ). Это значение сохраняется в локальном 2 . Мы должны загружать значения, потому что мы не можем просто разыскивать

Теперь мы знаем, что означают инструкции, поэтому, надеюсь, вы сможете прочитать и понять больше половины IR выше. Что касается остальных инструкций, они должны быть относительно простыми. add будет выполнять добавление по заданным значениям и возвращать результат. Команда ret указывает значение, возвращаемое функцией.

API LLVM

LLVM предоставляет API для построения этого IR. Исходный API находится в C ++, хотя есть привязки к различным языкам от Lua, до OCaml, C, Go и многих других.

В этой статье я буду использовать привязки Go. Хотя, прежде чем мы начнем создавать IR, нам нужно знать и понять несколько деталей:

Модули

Модуль представляет собой группу определений и деклараций. Это контейнер, и мы должны его создать. Обычно модули создаются для каждого файла, поэтому в нашем примере C этот файл был модулем.

Мы создаем такой модуль. Мы передаем строку как имя модуля, мы будем называть наш «основной», поскольку он является основным модулем:

 module := llvm.NewModule("main") 

Типы

LLVM предоставляет широкий спектр типов, от примитивных типов, таких как байты, целые числа, с плавающей запятой, до более сложных типов, таких как структуры, массивы и типы функций.

Существуют некоторые встроенные типы в формате TypeWidthType() , поэтому, например, Int16Type представляет собой целое число с шириной 16 бит.

foo := llvm.Int16Type()
bar := llvm.Int32Type()

Мы также можем указать произвольные битовые ширины:

 fupa := llvm.IntType(32) 

Массив выглядит так:

 ages := llvm.ArrayType(llvm.Int32Type(), 16) 

Это массив из 16 32-битных целых чисел.

Значения

Значения LLVM могут быть возвращены из инструкций, хотя они также могут быть константами, функциями, глобальными ...

Ниже мы создаем постоянное целое число типа i32 со значением 666 . Логический параметр в конце состоит в том, следует ли подписать расширение.

 foo := llvm.ConstInt(llvm.Int32Type(), 666, false) 

Мы можем создавать константы с плавающей запятой:

 bar := llvm.ConstFloat(llvm.FloatType(), 32.5) 

И мы можем присвоить эти значения переменным или передать их функциям и т. Д. Здесь мы создаем инструкцию add, которая добавляет два постоянных значения:

a := llvm.ConstInt(llvm.Int32Type(), 12)
b := llvm.ConstInt(llvm.Int32Type(), 24)
c := llvm.ConstAdd(a, b)

Основные блоки

Это немного отличается от того, как вы можете ожидать. В сборке мы используем метки для функций и поток управления. LLVM очень похож на это, хотя у нас есть явный синтаксис для функций. Но как мы контролируем поток нашей программы? Мы используем базовые блоки. Таким образом, IR будет выглядеть так:

define i32 @main() {
entry:
	...
0:
	...
1:
	...
}

У нас есть наша основная функция, и внутри этой функции мы имеем три основных блока. Блок ввода, а затем блок 0 и 1. Вы можете иметь столько базовых блоков, сколько хотите. Они используются для таких вещей, как прыжки вокруг, например, цикл, если утверждения и т. Д.

В привязках Go для LLVM мы определяем базовый блок следующим образом:

 llvm.AddBasicBlock(context, "entry") 

Где контекст - это функция, к которой мы хотим добавить блок. Это не тип функции. Однако мы поговорим об этом позже.

IR Builder

IR Builder создаст наш IR для нас. Мы кормим его ценностями, инструкциями и т. Д., И они объединят их все вместе. Ключевая часть строителя заключается в том, что мы можем использовать его для перемещения, где мы строим, и добавляем инструкции в разных местах.

Мы можем использовать этот конструктор для добавления инструкций в наш модуль. Ниже мы создаем конструктор, создаем функцию и блок ввода, а затем добавляем некоторые простые инструкции для хранения константы:

builder := llvm.NewBuilder()
// create a function "main"
// create a block "entry"

foo := builder.CreateAlloca(llvm.Int32Type(), "foo")
builder.CreateStore(foo, llvm.ConstInt(llvm.Int32Type(), 12, false))

Это приводит к тому, что IR:

define i32 @main() {
entry:
	%foo = alloca i32
	store i32 12, i32* %foo
}

функции

Функции - это тип LLVM. Нам нужно указать несколько вещей, когда мы определяем этот тип функции: тип возврата, типы параметров, и если функция является переменной, т. Е. Если она принимает переменное количество аргументов.

Вот наша главная функция, как мы ее видели до сих пор:

main := llvm.FunctionType(llvm.Int32Type(), []llvm.Type{}, false)
llvm.AddFunction(mod, "main", main)

Первым параметром является тип возврата, поэтому 32-битное целое число. Наша функция не принимает никаких параметров, поэтому мы просто передаем пустой массив типов. И функция не является вариационной, поэтому мы передаем false в последнем аргументе. Легко ли?

AddFunction добавит функцию к данному модулю в качестве данного имени. Затем мы можем ссылаться на это позже (он хранится в карте ключа / значения) следующим образом:

 mainFunc := mod.NamedFunction("main") 

Это будет искать функцию в модуле.

Теперь мы можем собрать все, что мы узнали до сих пор:

 // setup our builder and module builder := llvm.NewBuilder() mod := llvm.NewModule("my_module") // create our function prologue main := llvm.FunctionType(llvm.Int32Type(), []llvm.Type{}, false) llvm.AddFunction(mod, "main", main) block := llvm.AddBasicBlock(mod.NamedFunction("main"), "entry") // note that we've set a function and need to tell // the builder where to insert things to builder.SetInsertPoint(block, block.FirstInstruction()) // int a = 32 a := builder.CreateAlloca(llvm.Int32Type(), "a") builder.CreateStore(llvm.ConstInt(llvm.Int32Type(), 32, false), a) // int b = 16 b := builder.CreateAlloca(llvm.Int32Type(), "b") builder.CreateStore(llvm.ConstInt(llvm.Int32Type(), 16, false), b) 

Пока все хорошо, но поскольку alloca возвращает указатель, мы не можем просто добавить их вместе. Мы должны сгенерировать некоторые нагрузки для «разыменования» нашего указателя.

 aVal := builder.CreateLoad(a, "a_val") bVal := builder.CreateLoad(b, "b_val") 

А затем арифметическая часть. Мы будем делать a + b , это прямолинейно, так как нам просто нужно создать инструкцию add:

 result := builder.CreateAdd(aVal, bVal, "ab_value") 

Теперь нам нужно вернуть это, так как наша функция возвращает i32 .

 builder.CreateRet(result) 

И это все! Но как мы это выполним? У нас есть несколько вариантов: мы можем:

  • Используйте механизм JIT / выполнения LLVM
  • Перевести на IR -> BitCode -> Assembly -> Object -> Executable

Поскольку первый вариант немного более краткий, чтобы вписаться в исполняемый файл, я собираюсь на этот маршрут. Я оставлю это упражнением для читателя, чтобы сделать второй маршрут. Если вы создаете исполняемый файл, если вы проверите код состояния после его запуска, это будет 48 который является результатом. Чтобы сделать это в Bash, эхо вне $? экологическая переменная:

$ ./a.out
$ echo $?
$ 48

Если вы хотите напечатать это стандартное значение, вам нужно будет определить функцию printf , putch или какой-либо эквивалент. Надеюсь, этот урок предоставит вам достаточно для этого. Если вы застряли (бесстыдный плагин), я работаю над языком под названием Ark, который построен поверх LLVM и написан на Go. Здесь вы можете проверить наш генератор кода .

Здесь также есть документация, доступная для привязок LLVM. У этого есть почти все, что вам нужно знать.

Помимо спецификации LLVM , которая подробно описывает все детали. Сюда входят инструкции, внутренности, атрибуты и все остальное.

Запуск нашего кода!

Достаточно рассвет, давайте доберемся до него. Вот обзор того, что включает этот раздел:

  • Проверка нашего модуля
  • Инициализация механизма выполнения
  • Настройка вызова функции и ее выполнение!

Сначала давайте проверим, что наш модуль верен.

if ok := llvm.VerifyModule(mod, llvm.ReturnStatusAction); ok != nil {
	fmt.Println(ok.Error())
	// ideally you would dump and exit, but hey ho
}
mod.Dump()

Это приведет к ошибке, если наш модуль недействителен. Недействительный модуль может быть вызван множеством вещей, хотя неправильный IR является наиболее вероятной причиной. mod.Dump() выведет модуль IR на стандартный выход.

Теперь для инициализации механизма выполнения:

engine, err := llvm.NewExecutionEngine(mod)
if err != nil {
	fmt.Println(err.Error())
	// exit...
}

И, наконец, запуск нашей функции и печать результата на stdout. Мы передаем пустой массив GenericValues, так как наша функция не принимает аргументов:

funcResult := engine.RunFunction(mod.NamedFunction("main"), []llvm.GenericValue{})
fmt.Printf("%d\n", funcResult.Int(false))

Сборка

Вам необходимо установить LLVM. К счастью для меня это так просто:

 $ pacman -S llvm 

Если вы находитесь в Windows, это может быть сложнее. В любом другом дистрибутиве Linux найдите llvm в своем диспетчере пакетов. На Mac вы можете использовать Homebrew.

И затем мы устанавливаем привязки go. Переменная release равна 362, хотя, если вы используете say llvm 3.7.0, это должно быть 370 и т. Д. Ниже будет клонировать репозиторий LLVM в GOPATH, а затем строить и устанавливать привязки.

$ release=RELEASE_362
$ svn co https://llvm.org/svn/llvm-project/llvm/tags/$release/final $GOPATH/src/llvm.org/llvm
$ cd $GOPATH/src/llvm.org/llvm/bindings/go
$ ./build.sh
$ go install llvm.org/llvm/bindings/go/llvm

Теперь в файле go убедитесь, что вы import "llvm.org/llvm/bindings/go/llvm" . Как только это будет сделано, вы можете запустить свой файл go и распечатать результат:

Готово! Надеюсь, вы научились новому. И, надеюсь, вы можете увидеть, как это можно использовать для написания языка программирования. Следующим шагом здесь будет проверка учебника Калейдоскопа, или эксперимент, и попытка реализовать свою собственную вещь.

Если вам понравилась эта статья, пишите мне @felix_angell ! Спасибо за прочтение!

Полный код

package main

import (
	"fmt"
	"llvm.org/llvm/bindings/go/llvm"
)

func main() {
	// setup our builder and module
	builder := llvm.NewBuilder()
	mod := llvm.NewModule("my_module")

	// create our function prologue
	main := llvm.FunctionType(llvm.Int32Type(), []llvm.Type{}, false)
	llvm.AddFunction(mod, "main", main)
	block := llvm.AddBasicBlock(mod.NamedFunction("main"), "entry")
	builder.SetInsertPoint(block, block.FirstInstruction())

	// int a = 32
	a := builder.CreateAlloca(llvm.Int32Type(), "a")
	builder.CreateStore(llvm.ConstInt(llvm.Int32Type(), 32, false), a)

	// int b = 16
	b := builder.CreateAlloca(llvm.Int32Type(), "b")
	builder.CreateStore(llvm.ConstInt(llvm.Int32Type(), 16, false), b)

	// return a + b
	bVal := builder.CreateLoad(b, "b_val")
	aVal := builder.CreateLoad(a, "a_val")
	result := builder.CreateAdd(aVal, bVal, "ab_val")
	builder.CreateRet(result)

	// verify it's all good
	if ok := llvm.VerifyModule(mod, llvm.ReturnStatusAction); ok != nil {
		fmt.Println(ok.Error())
	}
	mod.Dump()

	// create our exe engine
	engine, err := llvm.NewExecutionEngine(mod)
	if err != nil {
		fmt.Println(err.Error())
	}

	// run the function!
	funcResult := engine.RunFunction(mod.NamedFunction("main"), []llvm.GenericValue{})
	fmt.Printf("%d\n", funcResult.Int(false))
}