Я много думал о том, как проектируются промежуточные представления (IR) для компилятора. В этом посте я поделюсь с вами некоторыми идеями, к которым я пришёл, и поясню, почему считаю их важными.

Главенствующая идея заключается в способности принимать решения, располагая лишь локальной информацией.

Она существует примерно в паре трактовок. Исходим из того, что в каждый момент времени компилируем один какой-то метод, а не занимаемся чем-то сближающимся с трассировкой (трассировка, трейслеты, версионирование базовых блоков, т.д.).

Графы потока управления

Как правило, у функции есть поток управления, состоящий из if, while, for и включающий любое количество переходов внутри функции. Рассмотрим в качестве примера функцию на языке, в котором содержатся продвинутые конструкции для выражения такого потока:

int sumto(int n) {
  int result = 0;
  for (result = 0; n >= 0; n -= 1) {
    result += n;
  }
  return result;
}

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

int sumto(int n) {
  entry:
    int result = 0
  header:
    if n < 0, jumpto end
    result = result + n
    n = n - 1
    jumpto header
  end:
    return result
}

Язык напоминает псевдоассемблер. Его высокоуровневые языковые конструкции декомпозируются во множество мелких инструкций. Кроме того, в нём предусмотрено простое проваливание между помеченными участками (например, из entry в header).

Я упоминаю здесь эти вещи, поскольку они, как и другие феномены, рассмотренные в оставшейся части этого поста, относятся к пространству, в котором проектируется промежуточное представление. Решение представить код в такой форме — всегда осознанный выбор, а не данность. Например, можно сделать переходы явными, добавляя jumpto header в конце entry.

Как только мы добавим эту инструкцию, код становится позиционно-независимым. Если мы начинаем с entry, то фрагменты кода между метками могут идти в каком угодно порядке; они адресуются по имени, и никаких неявных требований к их упорядочиванию не предъявляется.

Это может показаться вольностью, но, благодаря такому подходу, оптимизатор получает дополнительную гибкость. Если в соответствии с некоторым правилом оптимизации решается, что выполнение лишь изредка может ответвиться в сторону block4, то эту инструкцию вполне можно переставить ближе к концу функции (или даже перенести на другую страницу памяти!), чтобы в одну кэш-линию удалось поместить больше «горячего» кода.

Благодаря явным переходам и меткам, удаётся превратить код из строго линейного ассемблера в граф потока управления (CFG). Любая последовательность кода, внутри которой отсутствует внутренний контроль управления, называется «базовым блоком» и является одной из вершин этого графа. Ориентированные рёбра соответствуют переходам между блоками. Вот, например, такое грубое представление, сделанное в GraphViz:

Кстати, мы уже перешли к рассмотрению так называемых расширенных базовых блоков (EBB), в которых предусматривается несколько точек на блок для выхода из потока управления, но точка для входа в поток управления на блок всего одна. Строгое представление базового блока, выраженное в вышеприведённом коде, в текстовой форме выглядит примерно так:

int sumto(int n) {
  entry:
    int result = 0
    condbranch n < 0, iftrue: end, iffalse: header
  header:
    result = result + n
    n = n - 1
    condbranch n < 0, iftrue: end, iffalse: header
  end:
    return result
}

Обратите внимание: в каждом блоке есть ровно один завершитель (это инструкция потока управления), у которого может быть от 0 до 2 целей.

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

Промежуточные представления на основе регистров

Некоторые промежуточные представления основаны на стеке. В конкатенативных языках программирования или некоторых сравнительно новых динамических компиляторах промежуточные представления форматируются таким образом, что каждый опкод считывает свои операнды из стека, а результаты проделанных операций записывает в стек. Это напоминает «бесточечный» стиль программирования, практикуемый, например, в Haskell или OCaml.

inc = (+ 1)

В таком стиле неявно подразумевается разделяемость состояния в стеке. Поток данных явный (значения вкладываются в стек и выталкиваются из него), а инструкции можно переупорядочивать лишь при условии, что сохраняется структура стека. Для этого нужно мыслить нелокально: чтобы переместить инструкцию, также потребуется переупорядочить стек.

PUSH 1
PUSH 2
ADD

Напротив, основанные на регистрах промежуточные представления устроены понятнее. Инструкции принимают на вход именованные значения (v0, v12, т.д.) и на выход также выдают именованные значения. Перемещать инструкции чуть проще (эффект модуля), при условии, что ввод остаётся определённым. Стека не существует. Локальных переменных не существует. Всё, что входит в промежуточное представление — это «переменные».

v1 = CONST 1
v2 = CONST 2
v3 = ADD v1 v2

Ограничения (определяемые имена) входят в состав промежуточного представления. Ситуация немного усложняется, если одни и те же имена можно определить по несколько раз.

v1 = CONST 1
v2 = CONST 2
x = ADD v1 v2
x = ADD x v2
v3 = MUL x 12

Что означает x в инструкции v3? К какому определению он относится? Чтобы судить об инструкции v3 = MUL x 12, нужно предусмотреть для неё какой-то контекст. Это нетривиальная задача, поскольку в таком случае разработчикам компиляторов придётся постоянно таскать c собой таблицы для подсчёта ссылок (side-tables) и обновлять их по мере выполнения анализа. Получается медленно, и такой метод чреват ошибками. К счастью, если принять в качестве обязательных ряд интересных правил, то такую аналитическую работу удастся делать с опережением на один шаг…

SSA

Статическое представление с однократным присваиванием значения переменной (SSA) было предложено командой разработчиков из IBM (в этом посте рассказано о различных реализациях такого представления). В SSA-подобных промежуточных представлениях любую переменную можно определить всего один раз. Иными словами, переменная – это и есть определяющая её инструкция. Также верно, что и переменная, и определяющая её инструкция адресуются по одному и тому же имени. На практике мне впервые довелось увидеть подобное в серии статей Карла-Фридриха Больц-Терика об игрушечном оптимизаторе, там, где он рассказывает о трассировке динамической компиляции. Этот материал заставил меня полностью переосмыслить мои представления об IR. Далее я также рекомендую почитать раздел 2 в документе Design of the Java HotSpot™ Client Compiler for Java 6 (PDF). 

Вышеприведённый пример не является полноценным SSA, так как у x — два определения.

Если превратить предыдущий пример в SSA, то можно предусмотреть отдельное имя для каждой инструкции. Это связано с допущением об уникальности имён или глобальностью имён — в таком случае имена не зависят от контекста.

v1 = CONST 1
v2 = CONST 2
x0 = ADD v1 v2
x1 = ADD x0 v2

Теперь можно идентифицировать каждую отдельную инструкцию ADD по той переменной, которую она определяет. Это полезно при анализе…

CPS

Было бы упущением не упомянуть здесь промежуточные представления, которые пишутся в стиле передачи продолжений (CPS). Промежуточные представления, написанные в таком стиле, обычно применяются при анализе и оптимизации функциональных программ, например, в компиляторах OCaml и Racket. Но это требование не является обязательным; так, в компиляторе MLton для языка Standard ML используется SSA.

Можно примерно с равным успехом представить в виде SSA и CPS одни и те же программы, но ощущается так, словно каждый из этих стилей уместен с одними языками программирования более, чем с другими (и по-разному подходит разным авторам компиляторов). Полагаю, что недостаточно квалифицирован, чтобы развивать эту тему. Если вас интересует более информированное мнение, то можете почитать статью Энди Уинго, в которой он разбирает солянку cps. Особенно интересен раздел о достоинствах и недостатках (ближе к концу).

Информация о типах

Изучая CPS, я проходил курс Олина Шиверса, где он описывает абстрактную интерпретацию как «автоматизированное нахождение теорем». В отличие от инструментов, доказывающих теоремы, таких, как Lean и Rocq, при работе с которыми вам приходится вручную доказывать интересующие вас свойства, статический анализ позволяет изыскать интересные аспекты, уже присутствующие в вашей программе (а затем оптимизировать их, чтобы программу ускорить).

При проходах вашего статического анализа можно аннотировать узлы промежуточного представления небольшими справочными данными, например, указывать, что сущность:

• Относится к типу int

• Равна 5

• Имеет значение от 2 до 5

• Эквивалентна выражению y*z

• Не имеет побочных эффектов

• Инвариантна от цикла к циклу

• Не экранирует

• …

Если ваш статический анализ делается через SSA, то, как правило, упрощается как сам статический анализ, так и (потенциально) хранение фактов. Дело именно в этом свойстве, которое называется «разреженность» (sparseness). Если статический анализ применяется в программах, собранных не по SSA, то приходится хранить информацию обо всех переменных, каковы они во всех точках программы. При анализе по модели SSA требуется просто хранить информацию обо всех переменных, независимо от контекста.

Иногда я называю это «нанизыванием промежуточного представления на время», но не уверен, насколько понятна такая формулировка.

Потенциально здесь есть более тонкий момент, заключающийся в следующем: можно представить вышеприведённый фрагмент промежуточного представления как список кортежей, где инструкции соотносятся через какую-то другую таблицу (допустим, «окружение переменных»):

code = [
  ("v1", "CONST", 1),
  ("v2", "CONST", 2),
  ("x0", "ADD", "v1", "v2"),
  ("x1", "ADD", "x0", "v2"),
]

Но, напротив, можно выделять по объекту на каждую инструкцию, после чего организовать, чтобы они ссылались друг на друга по указателю (или по индексу, если вы пишете на Rust или чём-то подобном). Тогда они ссылаются непосредственно друг на друга (таблица для подсчёта ссылок уже не нужна), и код может получиться быстрее и компактнее. Далее при оптимизации мы смотрим, какова информация о типе у данного операнда, и для этого прямо считываем поле (operands[N]->type или т.п.).

Что ещё хочется отметить: когда вы начинаете добавлять в ваше промежуточное представление информацию о типах, то и в рамках анализа начинают возникать вопросы, касающиеся типов. Например, «какого типа эта инструкция», в каких случаях «тип» может охватывать полурешётку, либо можно даже ссылаться на конкретный объект времени исполнения по его указателю. В данном случае важно задавать правильные вопросы, такие как:  

• Неверно: Является ли инструкция X Const?

• Верно: Известно ли, что тип X — это конкретный объект?

Вероятно, инструкции Const — не единственные коды операций, которые могут давать на выходе конкретные объекты. Например, в случае такой инструкции как GuardIsObject, которая пережигает конкретный ожидаемый указатель в сгенерированный код, тип (и, следовательно, указатель) будет поступать от инструкции GuardIsObject.

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

Как бы то ни было, в SSA сохраняется лишь та информация о типах, которая относится к инструкциям, но при этом не кодируется информация, которую мы позже можем узнать в IR. Если мы располагаем лишь элементарным SSA, то у нас нет хорошего способа кодировать уточнения…

SSI

В форме SSI (статическая разовая информация) открываются новые способы кодировать метаданные об инструкциях (переменных). Эту форму впервые предложил Скотт Ананян (C. Scott Ananian), описавший её в 1999 году в своей магистерской диссертации (PDF). Рассмотрим следующую программу в форме SSA, представленную в виде псевдо-Python:

# @0
x = int(...)
# @1
if x >= 0:
    # @2
    return x
else:
    # @4
    result = -x
    # @5
    return result

x является неопределённой в @0. x является определённой и при этом целым числом в @1. Но далее мы делаем кое-что интересное: расщепляем поток управления в зависимости от того, каково значение x во время выполнения. Благодаря такому расщеплению, можно добавить к x новую интересную информацию. При неразреженном анализе можем записывать некоторые факты «на полях». Это хорошо.

# @0
x = int(...)
# @1
if x >= 0:
    # @2
    LearnFact(x, nonnegative)
    # @3
    return x
else:
    # @4
    LearnFact(x, negative)
    # @5
    result = -x
    # @6
    return result

Анализируя поток данных, можно отследить, что в точке @3 переменная x неотрицательна, а в точке @5 переменная x отрицательна. Это радует: далее можно определить, что все пути к этой функции возвращают положительное целое число.

Важно, что LearnFact(x, nonnegative) не переопределяет уже имеющийся известный тип x. Нет, это уточнение: пересечение множеств. Стык решёток. Средняя часть диаграммы Венна, включающей две пересекающиеся окружности, Integer и Nonnegative.

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

# @0
x = int(...)
# @1
if x >= 0:
    # @2
    newx0 = LearnFact(x, nonnegative)
    # @3
    return newx0
else:
    # @4
    newx1 = LearnFact(x, negative)
    # @5
    result = -newx1
    # @6
    return result

Это сложно (выбирать, какие переменные расщеплять, заменять все их включения, поддерживать SSA, т.д.), зато у нас появляются новые места, где можно хранить информацию прямо внутри IR. Таким образом, всякий раз, ссылаясь на newx0, мы знаем, что оно неотрицательное, а ссылаясь на newx1 — знаем, что оно отрицательное. Эта информация не зависит от контекста!

Должен отметить, что из SSI можно извлечь огромную пользу, не реализуя «полное SSI». Нет никакой необходимости расщеплять все до одной переменные во всех ветвлениях, равно как не нужно и добавлять новую инструкцию слияния.

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

Море узлов

В традиционном представлении CFG инструкции уже распланированы или упорядочены. Как правило, этот порядок поступает от программиста, записанный в исходном коде, а затем тщательно поддерживается. В промежуточном представлении, например, в SSA, приходится иметь дело с рёбрами, характеризующими использование данных, но информация о потоке управления остаётся неявной. Но в некоторых вариантах промежуточного представления предпринимаются попытки материализовать в рамках IR как данные, так и зависимости управления ими. Один из таких вариантов промежуточного представления называется «море узлов» (sea of nodes, SoN) и был исходно предложен Клиффом Кликом в его докторской диссертации.

В море узлов каждой инструкции соответствует собственная вершина в графе. В операндах инструкциям приходится использовать рёбра, и ребро может кодировать либо данные, либо какое-то другое свойство, касающееся их порядка (контроль, эффекты, т.д.). Суть заключается в том, что по умолчанию узлы в промежуточном представлении являются неупорядоченными и упорядочиваются лишь после того, как в результате анализа удастся исключить многие рёбра, которые использоваться не будут.

Пер Вонгсен приводит в качестве мотивации ещё один пример использования моря узлов. В предыдущем примере с s SSI функцию LearnFact(x, nonnegative) нельзя корректно подвесить над проверкой n >= 0. В «нормальном» промежуточном представлении имеющийся порядок уже неявно заложен. Но в море узлов нужный нам порядок можно специально пометить, перебросив ребро от LearnFact к if n >= 0. Думаю, в Graal, например, такие узлы LearnFact называются «Pi-узлами».

Думаю, нужно перечитать оригинальную статью, изучить современную реализацию (создаётся впечатление, как будто она уже не используется точно так, как описано в оригинале), а затем вернуться к этой теме. Пока посмотрите Simple от Клиффа Клика и товарищей. Это реализация на Java, которая сопровождается небольшой книгой.

Схожие варианты проектирования — в том числе, графы зависимости значений (VDG), графы зависимости состояния значений (VSDG), графы зависимости состояния значений регионов (RVSDG) и графы зависимости программ (PDG).

Воплощение спецификаций

Продолжая разговор о Клиффе Клике, упомяну, что в связи с ним однажды услышал кое-что очень интересное. Грубо говоря, речь шла о идее «заложить в IR полную семантику операции — и пусть оптимизатор дальше сам с этим разбирается». То есть, предлагается «открыть код» или «встроить» вашу семантику.

Например, не выдавайте код для обобщённой операции сложения, если в дальнейшем вы собираетесь её специализировать:

v2 = GENERIC_ADD v0, v1

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

v1 = TYPE_OF v0
v2 = TYPE_OF v1
if (v1 == Fixnum && v2 == Fixnum) {
    v3 = FIXNUM_ADD v0, v1
}
else if (v1 == String && v2 == String) {
    v4 = STRING_CONCAT v0, v1
}
else {
    v5 = LOOKUP_METHOD v0, "add"
    v6 = CALL_METHOD v5, v0, v1
}
v7 = PHI v3, v4, v6

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

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

Разумеется, недостаток такого подхода в том, что у вас может получиться сравнительно крупное промежуточное представление, поэтому оптимизатор может работать с ним медленнее. Хуже того, может увеличиться и сам сгенерированный компилятором код. Но здесь могут помочь невстраивание ненужных функций, дедупликация (функционализация?) и, возможно, ещё какие-то хитрые методы.

Об этом же пишут (PDF) Максим Шевалье-Бойсвер и Марк Фрили в контексте версионирования базовых блоков. Если обобщённые функции сложения в среде записаны в промежуточном представлении, то вызыватели этих функций могут сделать «сквозную» специализацию, вызывая нужную функцию в контексте разных базовых блоков. Таким образом вы более-менее бесплатно получаете специализацию на уровне точек вызова функций. См. следующий листинг (рис. 4 из их статьи, немного отредактированный автором оригинала этого поста), где имена переменных с префиксом $ означают специальные функции, известные компилятору:

function $rt_add(x, y) {
    if ($ir_is_i32(x)) { // Если x — целое число 
        if ($ir_is_i32(y)) {
            var r = $ir_add_i32_ovf(x, y);
            if (r)
                return r;
            else // Обрабатываем случай с переполнением
                return $ir_add_f64($ir_i32_to_f64(x),
                                   $ir_i32_to_f64(y));
        } else if ($ir_is_f64(y))
            return $ir_add_f64($ir_i32_to_f64(x), y);
    } else if ($ir_is_f64(x)) { // Если x — число с плавающей точкой 
        if ($ir_is_i32(y))
            return $ir_add_f64(x, $ir_i32_to_f64(y));
        else if ($ir_is_f64(y))
            return $ir_add_f64(x, y);
    }
    // Вычисляем аргументы как строки, а затем сцепляем их
    return $rt_strcat($rt_toString(x), $rt_toString(y));
}

Такой вариант хорош, если вы создаёте среду выполнения с нуля, либо у вас есть ресурсы, чтобы переписать фрагменты вашей среды выполнения прямо на IR. В таком случае, даже при динамической компиляции методов, можно заложить семантику языка на уровне (частичного) встраивания функций.

Спасибо!

Спасибо Крису Фоллину, Хантеру Голдстейну и Перу Вонгсену за ценные комментарии по черновикам оригинала этого поста.