QBE

QBE IL (QBE intermediate language) — промежуточный язык, является языком более высокого уровня, чем язык ассемблера. Он сглаживает большинство проблем базового оборудования и позволяет использовать бесконечное количество временных конструкций. Этот более высокий уровень абстракции позволяет сторонним программистам сосредоточиться на проблемах разработки языка.

The intermediate language (IL) is a higher-level language than the machine's assembly language. It smoothes most of the irregularities of the underlying hardware and allows an infinite number of temporaries to be used. This higher abstraction level allows frontend programmers to focus on language design issues.

Входные файлы

Промежуточный язык предоставляется QBE в виде текста. Как правило, один файл создается для каждой программы с входного языка интерфейса. IL-файл представляет собой последовательность определений для данных, функций и типов. После обработки QBE полученный файл может быть собран и связан с использованием стандартного инструментального ПО (например, GNU_binutils).

The intermediate language is provided to QBE as text. Usually, one file is generated per each compilation unit from the frontend input language. An IL file is a sequence of Definitions for data, functions, and types. Once processed by QBE, the resulting file can be assembled and linked using a standard toolchain (e.g., GNU binutils).

Ниже приведено полное содержимое IL-файла "Hello World", в котором определена функция, выводящая на экран "hello world". Поскольку строка не является объектом первого класса (им является только указатель), она определяется вне тела функции. Комментарии начинаются с символа # и заканчиваются концом строки.

Here is a complete "Hello World" IL file which defines a function that prints to the screen. Since the string is not a first class object (only the pointer is) it is defined outside the function's body. Comments start with a # character and finish with the end of the line.

# Объявление константной строки "hello world"
data $str = { b "hello world", b 0 }

function w $main() {
@start
        # Вызов функции puts с аргументом $str.
        %r =w call $puts(l $str)
        ret 0
}

Если вы прочитали справочник по языку LLVM, вы можете понять вышеприведенный код. В сравнении, QBE предоставляет гораздо более простое использование типов и синтаксиса.

If you have read the LLVM language reference, you might recognize the example above. In comparison, QBE makes a much lighter use of types and the syntax is terser.

Запись БНФ

Синтаксис языка, который Вы сможете найти в разделах данной Wiki (и в оригинальной документации), описан с использованием БНФ. Различные используемые конструкции БНФ перечислены ниже.

Ключевые слова заключены в кавычки; ... | ... выражает дизъюнкции; [ ... ] обозначает некоторый синтаксис как необязательный; ( ... ), обозначает разделенный запятыми список прилагаемого синтаксиса; ...* и ...+ используются для произвольных обозначений и для повторений соответственно.

Символы

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

The intermediate language makes heavy use of sigils, all user-defined names are prefixed with a sigil. This is to avoid keyword conflicts, and also to quickly spot the scope and nature of identifiers.

: используется для определенных пользователем составных типов данных $ используется для глобальных переменных (представленных в виде указателя) % используется для переменных внутри функций @ используется для обозначения меток блоков

В этом синтаксисе БНФ мы используем ?IDENT для обозначения идентификатора, начинающегося с символа ?.

---

Источник: c9x.me

Сравнение с LLVM

QBE и LLVM являются компиляторами, использующими представление SSA. В этом документе объясняется, почему LLVM не делает QBE лишним. Очевидно, что все следующее предвзято, потому что написано мной (разработчиком).

Both QBE and LLVM are compiler backends using an SSA representation. This document will explain why LLVM does not make QBE a redundant project. Obviously, everything following is biased, because written by me.

Объем

QBE — проект гораздо меньшего масштаба с отличными от LLVM целями.

QBE is a much smaller scale project with different goals than LLVM.

• QBE предназначен для для любительской разработки своего языка.

QBE is for amateur language designers.

Он не затрагивает все проблемы, возникающие при разработке языка промышленного уровня. Если вы "играете" с какими-то идеями разработки языка, использование LLVM будет походить на таскание вашего рюкзака с грузовиком, а использование QBE будет больше похоже на катание на велосипеде.

It does not address all the problems faced when conceiving an industry-grade language. If you are toying with some language ideas, using LLVM will be like hauling your backpack with a truck, but using QBE will feel more like riding a bicycle.

• QBE — это первые 70%, а не последние 30%.

QBE is about the first 70%, not the last 30%.

QBE пытается точно определить в многочисленной литературе о компиляции те оптимизации, которые дают вам 70% производительности в 10% кода в полномасштабных компиляторах.

It attempts to pinpoint, in the extremely vast compilation literature, the optimizations that get you 70% of the performance in 10% of the code of full blown compilers.

Например, распространение копий в форме SSA реализовано в 160 строках кода в QBE!

For example, copy propagation on SSA form is implemented in 160 lines of code in QBE!

• QBE чрезвычайно открыт, прост и удобен в изучении.

QBE is extremely hackable.

Во-первых, QBE есть и останется небольшим проектом (менее 8 KLOC, прим. 1 KLOCK (Kilo Lines Of Code) = 1000 строк кода.). Во-вторых, он реализован на простом C99 без каких-либо зависимостей. В-третьих, он может выводить промежуточный язык и отладочную информацию в едином формате после каждого прохода.

First, it is, and will remain, a small project (less than 8 kloc). Second, it is programmed in non-fancy C99 without any dependencies. Third, it is able to dump the IL and debug information in a uniform format after each pass.

Особенности

LLVM определенно содержит больше функций, но в QBE есть интересных несколько вещей.

LLVM is definitely more packed with features, but there are a few things provided in QBE to consider.

• LLVM НЕ обеспечивает вам полную совместимость с Си.

LLVM does NOT provide full C compatibility for you.

В техническом плане, любой язык, который обеспечивает хорошую совместимость с Си и использует LLVM в качестве платформы, должен переопределять большие куски ABI в своем интерфейсе! Эта хорошо известная проблема в сообществе LLVM вызывает много дублирования и ошибок. Реализация полного Си ABI (с возможностью передавать структуры как аргументы и возвращать их из функций) невероятно сложна, и не слишком весела. QBE предоставляет вам операции промежуточного языка для вызова (и вызывается с) без лишних проблем. Кроме того, реализация ABI в QBE была тщательно протестирована путем фаззинга и испытаний вручную.

In more technical terms, any language that provides good C compatibility and uses LLVM as a backend needs to reimplement large chunks of the ABI in its frontend! This well known issue in the LLVM community causes a great deal of duplication and bugs. Implementing a complete C ABI (with struct arguments and returns) is incredibly tricky, and not really a lot of fun. QBE provides you with IL operations to call in (and be called by) C with no pain. Moreover the ABI implementation in QBE has been thoroughly tested by fuzzing and manual tests.

• LLVM IL более загроможден операциями памяти.

LLVM IL is more cluttered with memory operations.

Реализация создания SSA сложна. Чтобы уберечь своих пользователей от необходимости его реализации, LLVM предоставляет части стека. Это означает, что одно увеличение на 1 переменной v будет состоять из трех инструкций LLVM: одна выгрузка, одно добавление и одно сохранение. QBE предоставляет простые типы переменных, отличные от SSA, поэтому увеличение v выполняется просто с помощью одной команды %v = w add% v, 1. Это может показаться поверхностным преимуществом, но уменьшение количества команд втрое упрощает для разработчиков выявление ошибок в сгенерированном коде.

Implementing SSA construction is hard. To save its users from having to implement it, LLVM provides stack slots. This means that one increment of a variable v will be composed of three LLVM instructions: one load, one add, and one store. QBE provides simple non-SSA temporaries, so incrementing v is simply done with one instruction %v =w add %v, 1. This could seem cosmetic, but dividing the size of the IL by three makes it easier for the frontend writers to spot bugs in the generated code.

• LLVM IL более загроможден с объявлениями и преобразованиями типов.

LLVM IL is more cluttered with type annotations and casts.

Для улучшения оптимизации и корректности LLVM имеет сложные типы промежуточного представления. Тем не менее, только несколько типов представляют объекты первого класса, и многие операции исходных языков требуют компиляции приведения типов. Поскольку QBE реализует гораздо более простое использование типов, промежуточное представление получается более читаемым и коротким. Разумеется, можно выносить вопрос о корректности QBE, но помните, что на практике большое количество преобразований, необходимых в ILL LLVM, подрывает общую эффективность системы типов.

For the sake of advanced optimizations and correctness, LLVM has complex IL types. However, only a few types are really first class and many operations of source languages require casts to be compiled. Because QBE makes a much lighter use of types, the IL is more readable and shorter. It can of course be argued back that the correctness of QBE is jeoparadized, but remember that, in practice, the large amount of casts necessary in LLVM IL is undermining the overall effectiveness of the type system.

Проекты, использующие QBE

• Интерфейс учебника включен в дистрибутив в каталоге minic/. В менее чем 1000 строк он компилирует упрощенный Си. Небольшие контрольные показатели также предоставляются.
• Амбициозный Си компилятор.
• Два интерфейса для brainfuck и Си были написаны в Myrddin Эндрю Чэмберсом.
• Свидетельством хорошей архитектуры QBE является компилятор PACC от Бенжамина Россо; он повторно использует как архитектуру IL, так и множество возможностей QBE.
• Некоторая текущая работа над компилятором Myrddin направлена на использование QBE в качестве backend.