Введение в компиляторы для начинающих: следите за тем, как мы создаем компилятор с нуля, или разветвите код на GitHub и добавьте свои собственные оптимизации!

В прошлый раз на Compiler Adventures мы написали оптимизацию, которая устраняет инструкции без операций, такие как деление на единицу: div x 1. В конце поста я предложил вам найти другие инструкции, которые всегда не работают, независимо от значения регистра. Есть как минимум еще два: добавить ноль (например, add x 0) и умножить на единицу (например, mul x 1) — ни один из этих примеров не влияет на регистр x независимо от его значения.

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

Напомним, что при запуске программы MONAD все значения w, x, y, z равны нулю. Давайте посмотрим на начало нашей программы ввода MONAD и смоделируем вручную, что происходит с четырьмя регистрами:

Ух ты! Кроме чтения входного числа с помощью inp w, почти ничего не происходит до этой инструкции add x 11. Инструкции add x z и mod x 26 не влияют на значения регистров, поэтому мы нашли больше инструкций, которые можно оптимизировать!

В эпизоде ​​1 наш компилятор распознал, что div z 1 не работает, потому что оно делится на единицу. Ну и почему наш компилятор тоже не заметил, что соседние инструкции не выполняются?

Это потому, что они не всегда не работают: div z 1 не работает независимо от значения z, но add x z не работает, только если z равно нулю. . Точно так же инструкции mul x 0 и mod x 26 здесь не являются операциями только потому, что x = 0 перед выполнением инструкции: результат операции равен нулю и записывается в x, поэтому x = 0 остается без изменений.¹ Чтобы оптимизировать такие инструкции, нам понадобится чтобы научить компилятор отслеживать возможные значения регистров.

Отслеживание значений регистра

Значение регистра может быть либо известно точно, либо точно неизвестно. Если известно, что регистр содержит номер n, назовем его Exact(n). Если значение регистра не является каким-либо конкретным числом, допустим, регистр содержит Unknown. Для удобства чтения и отладки давайте также введем третий тип значений, которые может хранить регистр: Input(i), представляющий ith ввод в программу. (Для тех, кто еще не освоился с Rust, напомню, что usize — это беззнаковый целочисленный тип, который Rust предпочитает для подсчета.)

Когда программа запускается, все четыре регистра содержат Exact(0). Затем для каждой инструкции мы оцениваем набор правил, чтобы определить, каким должно быть следующее состояние регистра. Например, после чтения первого ввода программы с помощью инструкции inp w значение регистра w становится Input(0). В противном случае:

  • Если инструкция работает с двумя значениями Exact, мы оценим операцию с этими значениями и запишем результат Exact. Например, add x 11 вместо x = Exact(0) даст Exact(11).
  • Если инструкция представляет собой умножение и один из операндов равен Exact(0), результатом будет Exact(0) независимо от значения другого операнда.
  • В противном случае мы не сможем определить точный результат, поэтому вместо этого запишем Unknown. Например, eql x w ниже сравнивает Input(0) и Exact(11) и дает результат Unknown. Точно так же следующая инструкция eql x 0 сравнивает Unknown с Exact(0) и снова выдает результат Unknown.

Применяя эти правила, мы получаем следующие значения регистров, начиная с начала программы:

В сторону: учебник по синтаксису Rust

Мы собираемся использовать некоторый синтаксис, который может показаться незнакомым людям, еще не привыкшим к Rust, поэтому давайте сначала объясним его:

Реализация правил значения регистра

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

Поиск недействующих инструкций по значениям регистров

Ранее мы заметили, что для определения того, является ли add x z неоперативным, нам нужно было знать, равны ли x или z нулю — и теперь мы можем! В целом мы видим, что:

  • add x y не работает, если y = Exact(0). Однако это не означает отсутствие операции, если x = Exact(0), так как в этом случае x перезаписывается значением y.
  • mul x y не работает, если x = Exact(0) (умножьте ноль на что угодно, и он останется нулем) или y = Exact(1) (умножьте что-нибудь на единицу, и результат не изменится). То же правило запрета операций применимо и к div x y.
  • Для mod x y язык MONAD указывает, что x ≥ 0 и y > 0. Таким образом, mod x y является нулевой операцией всякий раз, когда x < y, так как остаток при делении меньшего числа на большее и есть само меньшее число.
  • eql x y может не работать двумя способами. Если x = y, мы получим результат x = Exact(1), поэтому у нас нет операции, если x = y = Exact(1). Если x != y, то мы получим результат x = Exact(0), поэтому у нас нет операции, если x = Exact(0) и y является любым значением Exact, кроме Exact(0). Таким образом, eql x y не работает, если x = y = Exact(1) или если x = Exact(0) и y != Exact(0).
  • Для форм этих инструкций, которые используют буквенное число вместо второго регистра, такого как add x 11, мы просто рассматриваем литеральное число как соответствующее ему значение Exact, а затем применяем те же правила, что и выше.

Двигаемся вперед в два шага. Во-первых, давайте напишем функцию, которая принимает (не-inp) Instruction и два Value входа left и right и возвращает true, если инструкция не выполняется при выполнении с этими значениями:

Для удобства я уже определил некоторые вспомогательные методы для Instruction, которые просто возвращают индекс исходного/целевого регистра (функция register()) и литерал или регистровый операнд, если он есть в инструкции (функция operand()).

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

Вот так мы и реализовали постоянное распространение! Давайте переименуем remove_div_by_1 в constant_propagation, чтобы отпраздновать наше достижение!²

Анализ влияния наших оптимизаций

Давайте запустим наш компилятор в нашей программе ввода Advent of Code и измерим, насколько хорошо мы справились:

$ cargo run analyze sample_programs/aoc_challenge.txt
    Finished dev [unoptimized + debuginfo] target(s) in 0.02s
     Running `.../monad_compiler analyze sample_programs/aoc_challenge.txt`
Original vs optimized length:    252 vs 238 (-14)
Optimized is more efficient by:  5.88%

Добавление постоянного распространения сделало наше обнаружение отсутствия операций в два раза лучше, чем в части 1! Нам удалось исключить еще 7 инструкций по сравнению с прошлым разом, общее улучшение составило чуть менее 6%.

С другой стороны, может быть, постоянное распространение должно было иметь большее влияние? Давайте визуализируем нашу оптимизацию, чтобы понять, что происходит.

Мы будем использовать cargo run registers <monad_program> для создания распечатки значений регистров, определенных нашими оптимизациями для каждой инструкции в программе, вместе с указанием, была ли эта инструкция обнаружена как неоперативная. Я включу сюда несколько соответствующих фрагментов распечатки входной программы — полная распечатка доступна на GitHub.

Начало программы выглядит довольно хорошо: в первых 10 инструкциях большинство значений регистров равно Exact, а постоянное распространение помогает исключить 5 из этих 10 инструкций как пустые. Это намного лучше, чем 6%!

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

Оптимизация компилятора использует информацию о поведении программы, чтобы сделать ее более эффективной. Когда программа запускается, ее начальное состояние полностью известно: все регистры имеют Exact(0) значений, и единственными неизвестными являются значения, полученные из входных данных, считанных inp инструкциями. Это богатая идеями среда, и наш компилятор работает отлично!

К сожалению, наш компилятор еще недостаточно совершенен, чтобы продолжать генерировать информацию об остальной части программы, поэтому его производительность соответственно падает. Статистика в конце распечатки резюмирует, почему наши оптимизации до сих пор имели ограниченное влияние: в 91,6% случаев по крайней мере одно из значений, используемых инструкцией, было неизвестно, а в 22,3% случаев оба значения были неизвестны. Неудивительно, что с таким небольшим количеством известных значений для работы постоянное распространение имеет ограниченный эффект.

Total non-input instructions: 238
- with 1+ non-exact value: 218 (91.6%)
- without any exact values: 53 (22.3%)

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

Подведение итогов + контрольный вопрос

Как упоминалось в части 1, реализация одной оптимизации компилятора может открыть новые возможности для другой оптимизации, чтобы творить чудеса. Мы уже включили идею «устранить отсутствие операций из части 1» в постоянный код распространения этого эпизода. В следующем Compiler Adventure мы будем использовать постоянное распространение как часть увлекательной новой оптимизации, которая станет основой большей части нашей будущей работы!

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

inp w
add x w
eql w x

Прямо сейчас наш компилятор говорит, что последняя инструкция eql w x будет оцениваться как Unknown:

Посмотрите внимательно на значения регистров вокруг add x w и eql w x. Можете ли вы выяснить, что оценивает eql w x? Это действительно Unknown? Почему наша текущая функция constant_propagation() не работает лучше?

Все это и многое другое в следующем приключении компилятора — увидимся в следующий раз!

Если вам понравился этот пост, поделитесь им с друзьями — компиляторы для всех! Свяжитесь со мной в Твиттере или присоединитесь к обсуждению на Hacker News.

Благодарим Hillel Wayne, Russell Cohen, Jonathan Paulson, Jimmy Koppel, Aaron Brooks, Vincent Tjeng, James Logan и Akshat Bubna за их отзывы о черновиках этой публикации. Любые ошибки принадлежат только мне.

[1]: Неоперативные операции, которые мы рассматривали до сих пор, относятся к типу «математической операции, которая дала тот же результат, что и ее входной регистр, который уже удерживался». Существуют и другие способы, при которых инструкция может не влиять на остальную часть программы. Например, инструкция может вычислять значение, которое никогда не используется, и поэтому его не нужно вычислять с самого начала. Мы подробно рассмотрим эту идею в следующем эпизоде.

[2]: Примечание для опытных пользователей Rust: я знаю, что этот код не является идиоматичным Rust. Я намеренно структурирую код, чтобы его было легче понять людям любого происхождения.