![](https://habrastorage.org/webt/uc/uq/bo/ucuqbo4tluzynnptop1pdmdvjhc.jpeg)
Оптимизирующие компиляторы — основа современного ПО: они позволяют программистам писать код на понятном для них языке, затем преобразуя его в код, который сможет эффективно исполняться оборудованием. Задача оптимизирующих компиляторов заключается в том, чтобы понять, что делает написанная вами входная программа, и создать выходную программу, которая делает всё то же самое, только быстрее.
В этой статье мы рассмотрим некоторые из основных методик приведения (inference techniques) в оптимизирующих компиляторах: как спроектировать программу, с которой компилятору будет легко работать; какие приведения можно сделать в вашей программе и как использовать их для её уменьшения и ускорения.
Оптимизаторы программ могут выполняться где угодно: как этап большого процесса компилирования (Scala Optimizer); как отдельная программа, запускаемая после компилятора и перед исполнением (Proguard); или как часть runtime-среды, которая оптимизирует программу в ходе её исполнения (JVM JIT-компилятор). Ограничения в работе оптимизаторов варьируются в зависимости от ситуации, но задача у них одна: взять входную программу и преобразовать в выходную, которая делает то же самое, но быстрее.
Сначала мы рассмотрим несколько примеров оптимизаций программы-черновика, чтобы вы понимали, что обычно делают оптимизаторы и как всё это сделать вручную. Затем рассмотрим несколько способов представления программ, и наконец разберём алгоритмы и методики, с помощью которых можно проанализировать программы, а затем сделать их меньше и быстрее.
Программа-черновик
Все примеры будут приведены на Java. Этот язык очень распространён и компилируется в относительно простой ассемблер — Java Bytecode. Так мы создадим хорошую основу, благодаря которой сможем исследовать методики оптимизации компилирования на реальных, исполняемых примерах. Все описанные ниже методики применимы почти во всех остальных языках программирования.
Для начала рассмотрим программу-черновик. Она содержит различную логику, регистрирует стандартный результат внутри процесса и возвращает вычисленный результат. Сама по себе программа не имеет смысла, но будет использоваться в качестве иллюстрации того, что можно оптимизировать, сохранив существующее поведение:
static int main(int n){
int count = 0, total = 0, multiplied = 0;
Logger logger = new PrintLogger();
while(count < n){
count += 1;
multiplied *= count;
if (multiplied < 100) logger.log(count);
total += ackermann(2, 2);
total += ackermann(multiplied, n);
int d1 = ackermann(n, 1);
total += d1 * multiplied;
int d2 = ackermann(n, count);
if (count % 2 == 0) total += d2;
}
return total;
}
// https://en.wikipedia.org/wiki/Ackermann_function
static int ackermann(int m, int n){
if (m == 0) return n + 1;
else if (n == 0) return ackermann(m - 1, 1);
else return ackermann(m - 1, ackermann(m, n - 1));
}
interface Logger{
public Logger log(Object a);
}
static class PrintLogger implements Logger{
public PrintLogger log(Object a){ System.out.println(a); return this; }
}
static class ErrLogger implements Logger{
public ErrLogger log(Object a){ System.err.println(a); return this; }
}
Пока что будем считать, что эта программа — всё, что у нас есть, никакие другие части кода её не вызывают. Она просто вводит данные в
main
, выполняет и возвращает результат. Теперь давайте оптимизировать эту программу.Примеры оптимизаций
Приведение типов и инлайнинг
Вы могли заметить, что у переменной
logger
неточный тип: несмотря на метку Logger
, на основании кода можно сделать вывод, что это специфический подкласс — PrintLogger
:- Logger logger = new PrintLogger();
+ PrintLogger logger = new PrintLogger();
Теперь мы знаем, что
logger
— это PrintLogger
, и знаем, что вызов logger.log
может иметь единственную реализацию. Можно инлайнить:- if (multiplied < 100) logger.logcount();
+ if (multiplied < 100) System.out.println(count);
Это позволит уменьшить программу за счёт удаления ненужного класса
ErrLogger
, который не используется, а также за счёт удаления разных методов public Logger
log
, поскольку мы инлайнили его в единственное место вызова.Свёртывание констант
В ходе исполнения программы
count
и total
изменяются, а multiplied
— нет: она начинается с 0
и каждый раз умножается через multiplied = multiplied * count
, оставаясь равной 0
. Значит, можно заменить её во всей программе на 0
:static int main(int n){
- int count = 0, total = 0, multiplied = 0;
+ int count = 0, total = 0;
PrintLogger logger = new PrintLogger();
while(count < n){
count += 1;
- multiplied *= count;
- if (multiplied < 100) System.out.println(count);
+ if (0 < 100) logger.log(count);
total += ackermann(2, 2);
- total += ackermann(multiplied, n);
+ total += ackermann(0, n);
int d1 = ackermann(n, 1);
- total += d1 * multiplied;
int d2 = ackermann(n, count);
if (count % 2 == 0) total += d2;
}
return total;
}
В результате мы видим, что
d1 * multiplied
всегда равно 0
, а значит total += d1 * multiplied
ничего не делает и может быть удалено:- total += d1 * multiplied
Удаление мёртвого кода
После свёртывания
multiplied
и осознания, что total += d1 * multiplied
ничего не делает, можно убрать определение int d1
:- int d1 = ackermann(n, 1);
Это больше не часть программы, и поскольку
ackermann
является чистой функцией, удаление не повлияет на результат выполнения программы.Аналогично, после инлайнинга
logger.log
сама logger
больше не используется и может быть удалена:- PrintLogger logger = new PrintLogger();
Удаление ветви
Теперь первый условный переход в нашем цикле зависит от
0 < 100
. Поскольку это всегда верно, можно просто удалить условие:- if (0 < 100) System.out.println(count);
+ System.out.println(count);
Любой условный переход, который всегда верен, можно инлайнить в тело условия, а для переходов, которые всегда неверны, можно удалить условие вместе с его телом.
Частичное вычисление
Теперь проанализируем три оставшихся обращения к
ackermann
: total += ackermann(2, 2);
total += ackermann(0, n);
int d2 = ackermann(n, count);
- В первом два постоянных аргумента. Функция чистая, и при предварительном вычислении
ackermann(2, 2)
должно быть равно7.
- Во втором обращении есть один постоянный аргумент
0
и один неизвестныйn
. Можно передать его в определениеackermann
, и окажется, что когдаm
равно0
, функция всегда возвращаетn + 1.
- В третьем обращении оба аргумента неизвестны:
n
иcount
. Пока что оставим их на месте.
Учитывая, что обращение к
ackermann
определяется так:static int ackermann(int m, int n){
if (m == 0) return n + 1;
else if (n == 0) return ackermann(m - 1, 1);
else return ackermann(m - 1, ackermann(m, n - 1));
}
Можно упростить его до:
- total += ackermann(2, 2);
+ total += 7
- total += ackermann(0, n);
+ total += n + 1
int d2 = ackermann(n, count);
Поздняя диспетчеризация
Определение
d2
используется только в условном переходе if (count % 2 == 0)
. Поскольку вычисление ackermann
является чистым, можно перенести этот вызов в условный переход, чтобы он не обрабатывался до тех пор, пока не будет использован:- int d2 = ackermann(n, count);
- if (count % 2 == 0) total += d2;
+ if (count % 2 == 0) {
+ int d2 = ackermann(n, count);
+ total += d2;
+ }
Это позволит избежать половины обращений к
ackermann(n, count)
, ускорив выполнение программы.Для сравнения, функция
System.out.println
не является чистой, а значит её нельзя переносить внутрь или за пределы условных переходов без изменения семантики программы.Оптимизированный результат
Собрав все оптимизации, получим такой исходный код:
static int main(int n){
int count = 0, total = 0;
while(count < n){
count += 1;
System.out.println(count);
total += 7;
total += n + 1;
if (count % 2 == 0) {
total += d2;
int d2 = ackermann(n, count);
}
}
return total;
}
static int ackermann(int m, int n){
if (m == 0) return n + 1;
else if (n == 0) return ackermann(m - 1, 1);
else return ackermann(m - 1, ackermann(m, n - 1));
}
Хотя мы оптимизировали вручную, всё это можно сделать автоматически. Ниже приведён декомпилированный результат оптимизатора прототипа, который я написал для JVM-программ:
static int main(int var0) {
new Demo.PrintLogger();
int var1 = 0;
int var3;
for(int var2 = 0; var2 < var0; var2 = var3) {
System.out.println(var3 = 1 + var2);
int var10000 = var3 % 2;
int var7 = var1 + 7 + var0 + 1;
var1 = var10000 == 0 ? var7 + ackermann(var0, var3) : var7;
}
return var1;
}
static int ackermann__I__TI1__I(int var0) {
if (var0 == 0) return 2;
else return ackermann(var0 - 1, var0 == 0 ? 1 : ackermann__I__TI1__I(var0 - 1););
}
static int ackermann(int var0, int var1) {
if (var0 == 0) return var1 + 1;
else return var1 == 0 ? ackermann__I__TI1__I(var0 - 1) : ackermann(var0 - 1, ackermann(var0, var1 - 1));
}
static class PrintLogger implements Demo.Logger {}
interface Logger {}
Декомпилированный код чуть отличается от вручную оптимизированной версии. Кое-что компилятор не смог оптимизировать (например, неиспользуемый вызов
new PrintLogger
), а что-то сделано немного иначе (например, разделены ackermann
и ackermann__I__TI1__I
). Но в остальном автоматический оптимизатор сделал всё то же самое, что и я, используя заложенную в него логику.Возникает вопрос: как?
Промежуточные представления
Если вы попробуете создать собственный оптимизатор, то первый же возникший вопрос будет, пожалуй, самым важным: что такое «программа»?
Несомненно, вы привыкли писать и изменять программы в виде исходного кода. Вы точно исполняли их в виде скомпилированных бинарников, возможно, даже отлаживали бинарники. Вы могли сталкиваться с программами в виде синтаксического дерева, трёхадресного кода, A-Normal, передачи продолжения (Continuation Passing Style) или Single Static Assignment.
Существует целый зоопарк разных представлений программ. Здесь мы обсудим самые важные способы представления «программы» внутри оптимизатора.
Исходный код
static int ackermann(int m, int n){
if (m == 0) return n + 1;
else if (n == 0) return ackermann(m - 1, 1);
else return ackermann(m - 1, ackermann(m, n - 1));
}
Некомпилированный исходный код тоже является представлением вашей программы. Он относительно компактен, удобен для чтения человеком, но у него два недостатка:
- Исходный код содержит все подробности наименований и форматирования, которые важны для программиста, но бесполезны для компьютера.
- Ошибочных программ в виде исходного кода гораздо больше, чем корректных, и при оптимизации нужно удостовериться, что ваша программа из корректного входного исходного кода преобразуется в корректный выходный исходный код.
Эти факторы затрудняют оптимизатору работу с программой в виде исходного кода. Да, вы можете преобразовывать такую программу, например, с помощью регулярных выражений выявляя и заменяя паттерны. Однако первый из двух факторов затрудняет надёжное выявление паттернов обилием посторонних подробностей. А второй фактор сильно повышает вероятность запутаться и получить некорректную результирующую программу.
Эти ограничения приемлемы для преобразователей программ, которые исполняются под надзором человека, например, когда можно использовать Codemod для рефакторинга и преобразования кодовой базы. Однако использовать исходный код в качестве первичной модели автоматизированного оптимизатора нельзя.
Абстрактные синтаксические деревья
static int ackermann(int m, int n){
if (m == 0) return n + 1;
else if (n == 0) return ackermann(m - 1, 1);
else return ackermann(m - 1, ackermann(m, n - 1));
}
IfElse(
cond = BinOp(Ident("m"), "=", Literal(0)),
then = Return(BinOp(Ident("n"), "+", Literal(1)),
else = IfElse(
cond = BinOp(Ident("n"), "=", Literal(0)),
then = Return(Call("ackermann", BinOp(Ident("m"), "-", Literal(1)), Literal(1)),
else = Return(
Call(
"ackermann",
BinOp(Ident("m"), "-", Literal(1)),
Call("ackermann", Ident("m"), BinOp(Ident("n"), "-", Literal(1)))
)
)
)
)
![](https://habrastorage.org/getpro/habr/post_images/e01/019/324/e0101932411807ddb7abb9c120033f58.png)
Абстрактные синтаксические деревья (AST) — другой распространённый промежуточный формат. Они расположены на следующей ступени лестницы абстракции по сравнению с исходным кодом. Обычно AST отбрасывают всё форматирование исходного кода, отступы и комментарии, но сохраняют имена локальных переменных, которые отбрасываются в более абстрактных представлениях.
Как и исходный код, AST страдают от возможности кодирования ненужной информации, которая не влияет на фактическую семантику программы. Например, следующие два фрагмента кода семантически идентичны; они различаются только именами локальных переменных, но всё ещё имеют разные AST:
static int ackermannA(int m, int n){
int p = n;
int q = m;
if (q == 0) return p + 1;
else if (p == 0) return ackermannA(q - 1, 1);
else return ackermannA(q - 1, ackermannA(q, p - 1));
}
Block(
Assign("p", Ident("n")),
Assign("q", Ident("m")),
IfElse(
cond = BinOp(Ident("q"), "==", Literal(0)),
then = Return(BinOp(Ident("p"), "+", Literal(1)),
else = IfElse(
cond = BinOp(Ident("p"), "==", Literal(0)),
then = Return(Call("ackermann", BinOp(Ident("q"), "-", Literal(1)), Literal(1)),
else = Return(
Call(
"ackermann",
BinOp(Ident("q"), "-", Literal(1)),
Call("ackermann", Ident("q"), BinOp(Ident("p"), "-", Literal(1)))
)
)
)
)
)
static int ackermannB(int m, int n){
int r = n;
int s = m;
if (s == 0) return r + 1;
else if (r == 0) return ackermannB(s - 1, 1);
else return ackermannB(s - 1, ackermannB(s, r - 1));
}
Block(
Assign("r", Ident("n")),
Assign("s", Ident("m")),
IfElse(
cond = BinOp(Ident("s"), "==", Literal(0)),
then = Return(BinOp(Ident("r"), "+", Literal(1)),
else = IfElse(
cond = BinOp(Ident("r"), "==", Literal(0)),
then = Return(Call("ackermann", BinOp(Ident("s"), "-", Literal(1)), Literal(1)),
else = Return(
Call(
"ackermann",
BinOp(Ident("s"), "-", Literal(1)),
Call("ackermann", Ident("s"), BinOp(Ident("r"), "-", Literal(1)))
)
)
)
)
)
Ключевой момент в том, что хотя AST имеют структуру деревьев, они содержат узлы, которые семантически ведут себя не как деревья: значения
Ident("r")
и Ident("s")
определяются не содержимым их поддеревьев, а вышерасположенными узлами Assign("r", ...)
и Assign("s", ...)
. По сути, между Ident
’ами и Assign
’ами есть дополнительные семантические связи, которые столь же важны, как и ребра в древовидной структуре AST:![](https://habrastorage.org/getpro/habr/post_images/a17/62a/9a0/a1762a9a0a21d0b0e4fac6afb4f23335.png)
Эти связи формируют обобщённую графовую структуру, включающую циклы при наличии рекурсивных определений функций.
Байткод
Поскольку в качестве основного языка мы выбрали Java, скомпилированные программы сохраняются в виде Java—байткода в файлах .class.
Вспомним нашу функцию
ackermann
:static int ackermann(int m, int n){
if (m == 0) return n + 1;
else if (n == 0) return ackermann(m - 1, 1);
else return ackermann(m - 1, ackermann(m, n - 1));
}
Она компилируется в такой байткод:
0: iload_0
1: ifne 8
4: iload_1
5: iconst_1
6: iadd
7: ireturn
8: iload_1
9: ifne 20
12: iload_0
13: iconst_1
14: isub
15: iconst_1
16: invokestatic ackermann:(II)I
19: ireturn
20: iload_0
21: iconst_1
22: isub
23: iload_0
24: iload_1
25: iconst_1
26: isub
27: invokestatic ackermann:(II)I
30: invokestatic ackermann:(II)I
33: ireturn
Виртуальная машина Java (JVM), которая выполняет Java—байткод, представляет собой машину с комбинацией стека и регистров: есть стек операндов (STACK), в котором происходит оперирование значениями, и массив локальных переменных (LOCALS), в котором эти значения могут храниться. Функция начинается с N параметров в первых N слотах локальных переменных. По мере исполнения функция перемещает данные в стек, оперирует ими, кладёт обратно в переменные, вызывая
return
для возврата значения вызывающему из стека операндов.Если аннотировать приведённый выше байткод для представления значений, которые перемещаются между стеком и таблицей локальных переменных, то это будет выглядеть так:
BYTECODE LOCALS STACK
|a0|a1| |
0: iload_0 |a0|a1| |a0|
1: ifne 8 |a0|a1| |
4: iload_1 |a0|a1| |a1|
5: iconst_1 |a0|a1| |a1| 1|
6: iadd |a0|a1| |v1|
7: ireturn |a0|a1| |
8: iload_1 |a0|a1| |a1|
9: ifne 20 |a0|a1| |
12: iload_0 |a0|a1| |a0|
13: iconst_1 |a0|a1| |a0| 1|
14: isub |a0|a1| |v2|
15: iconst_1 |a0|a1| |v2| 1|
16: invokestatic ackermann:(II)I |a0|a1| |v3|
19: ireturn |a0|a1| |
20: iload_0 |a0|a1| |a0|
21: iconst_1 |a0|a1| |a0| 1|
22: isub |a0|a1| |v4|
23: iload_0 |a0|a1| |v4|a0|
24: iload_1 |a0|a1| |v4|a0|a1|
25: iconst_1 |a0|a1| |v4|a0|a1| 1|
26: isub |a0|a1| |v4|a0|v5|
27: invokestatic ackermann:(II)I |a0|a1| |v4|v6|
30: invokestatic ackermann:(II)I |a0|a1| |v7|
33: ireturn |a0|a1| |
Здесь я с помощью
a0
и a1
представил аргументы функции, которые в самом начале функции хранятся в таблице LOCALS. 1
представляет константы, загруженные через iconst_1
, а с v1
до v7
— вычисленные промежуточные значения. Здесь три инструкции ireturn
, возвращающие v1
, v3
и v7
. Эта функция не определяет другие локальные переменные, поэтому массив LOCALS хранит только входные аргументы.Выше мы видели два варианта нашей функции —
ackermannA
и ackermannB
. Так они выглядят в байткоде: BYTECODE LOCALS STACK
|a0|a1| |
0: iload_1 |a0|a1| |a1|
1: istore_2 |a0|a1|a1| |
2: iload_0 |a0|a1|a1| |a0|
3: istore_3 |a0|a1|a1|a0| |
4: iload_3 |a0|a1|a1|a0| |a0|
5: ifne 12 |a0|a1|a1|a0| |
8: iload_2 |a0|a1|a1|a0| |a1|
9: iconst_1 |a0|a1|a1|a0| |a1| 1|
10: iadd |a0|a1|a1|a0| |v1|
11: ireturn |a0|a1|a1|a0| |
12: iload_2 |a0|a1|a1|a0| |a1|
13: ifne 24 |a0|a1|a1|a0| |
16: iload_3 |a0|a1|a1|a0| |a0|
17: iconst_1 |a0|a1|a1|a0| |a0| 1|
18: isub |a0|a1|a1|a0| |v2|
19: iconst_1 |a0|a1|a1|a0| |v2| 1|
20: invokestatic ackermannA:(II)I |a0|a1|a1|a0| |v3|
23: ireturn |a0|a1|a1|a0| |
24: iload_3 |a0|a1|a1|a0| |a0|
25: iconst_1 |a0|a1|a1|a0| |a0| 1|
26: isub |a0|a1|a1|a0| |v4|
27: iload_3 |a0|a1|a1|a0| |v4|a0|
28: iload_2 |a0|a1|a1|a0| |v4|a0|a1|
29: iconst_1 |a0|a1|a1|a0| |v4|a0|a1| 1|
30: isub |a0|a1|a1|a0| |v4|a0|v5|
31: invokestatic ackermannA:(II)I |a0|a1|a1|a0| |v4|v6|
34: invokestatic ackermannA:(II)I |a0|a1|a1|a0| |v7|
37: ireturn |a0|a1|a1|a0| |
Поскольку исходный код берёт два аргумента и кладёт их в локальные переменные, то у байткода есть соответствующие инструкции загрузить значения аргументов из LOCAL-индексов 0 и 1 и сохранить их под индексами 2 и 3. Однако байткод не интересуют имена ваших локальных переменных: он работает с ними исключительно как с индексами в массиве LOCALS. Поэтому у
ackermannA
и ackermannB
будут идентичные байткоды. Это логично, ведь они семантически эквивалентны!Однако
ackermannA
и ackermannB
компилируются не в тот же байткод, что и исходная ackermann
: хотя байткод абстрагируется от имён локальных переменных, он всё же не полностью абстрагируется от загрузок и сохранений в/из этих переменных. Нам всё ещё важно, как значения перемещаются по LOCALS и STACK, хотя они и не влияют на фактическое поведение программы.Помимо отсутствия абстрагирования от загрузок/сохранений, у байткода есть другой недостаток: как и большинство линейных ассемблеров, он очень сильно оптимизирован с точки зрения компактности, и может быть очень трудно модифицировать его, когда речь заходит об оптимизациях.
Чтобы было понятнее, давайте рассмотрим байткод исходной функции
ackermann
: BYTECODE LOCALS STACK
|a0|a1| |
0: iload_0 |a0|a1| |a0|
1: ifne 8 |a0|a1| |
4: iload_1 |a0|a1| |a1|
5: iconst_1 |a0|a1| |a1| 1|
6: iadd |a0|a1| |v1|
7: ireturn |a0|a1| |
8: iload_1 |a0|a1| |a1|
9: ifne 20 |a0|a1| |
12: iload_0 |a0|a1| |a0|
13: iconst_1 |a0|a1| |a0| 1|
14: isub |a0|a1| |v2|
15: iconst_1 |a0|a1| |v2| 1|
16: invokestatic ackermann:(II)I |a0|a1| |v3|
19: ireturn |a0|a1| |
20: iload_0 |a0|a1| |a0|
21: iconst_1 |a0|a1| |a0| 1|
22: isub |a0|a1| |v4|
23: iload_0 |a0|a1| |v4|a0|
24: iload_1 |a0|a1| |v4|a0|a1|
25: iconst_1 |a0|a1| |v4|a0|a1| 1|
26: isub |a0|a1| |v4|a0|v5|
27: invokestatic ackermann:(II)I |a0|a1| |v4|v6|
30: invokestatic ackermann:(II)I |a0|a1| |v7|
33: ireturn |a0|a1| |
Сделаем черновое изменение: пусть вызов функции
30: invokestatic ackermann:(II)I
не использует свой первый аргумент. И тогда этот вызов можно заменить эквивалентным вызовом 30: invokestatic ackermann2:(I)I
, который берёт лишь один аргумент. Это распространённая оптимизация, которая позволяет с помощью «удаления мёртвого кода» выкинуть любой код, использующийся для вычисления первого аргумента 30: invokestatic ackermann:(II)I
.Чтобы это сделать, нам нужно не только заменить инструкцию
30
, но также нужно просмотреть список инструкций и понять, где вычисляется первый аргумент (v4
в STACK
), и тоже его удалить. Вернёмся от инструкции 30
к 22
, а от 22
к 21
и 20
. Финальный вариант: BYTECODE LOCALS STACK
|a0|a1| |
0: iload_0 |a0|a1| |a0|
1: ifne 8 |a0|a1| |
4: iload_1 |a0|a1| |a1|
5: iconst_1 |a0|a1| |a1| 1|
6: iadd |a0|a1| |v1|
7: ireturn |a0|a1| |
8: iload_1 |a0|a1| |a1|
9: ifne 20 |a0|a1| |
12: iload_0 |a0|a1| |a0|
13: iconst_1 |a0|a1| |a0| 1|
14: isub |a0|a1| |v2|
15: iconst_1 |a0|a1| |v2| 1|
16: invokestatic ackermann:(II)I |a0|a1| |v3|
19: ireturn |a0|a1| |
- 20: iload_0 |a0|a1| |
- 21: iconst_1 |a0|a1| |
- 22: isub |a0|a1| |
23: iload_0 |a0|a1| |a0|
24: iload_1 |a0|a1| |a0|a1|
25: iconst_1 |a0|a1| |a0|a1| 1|
26: isub |a0|a1| |a0|v5|
27: invokestatic ackermann:(II)I |a0|a1| |v6|
- 30: invokestatic ackermann:(II)I |a0|a1| |v7|
+ 30: invokestatic ackermann2:(I)I |a0|a1| |v7|
33: ireturn |a0|a1| |
Мы ещё можем сделать такое несложное изменение в простой функции
ackermann
. Но в больших функциях, используемых в реальных проектах, будет гораздо труднее делать многочисленные, взаимосвязанные изменения. В целом, любое маленькое семантическое изменение вашей программы может потребовать многочисленных изменений по всему байткоду.Вы могли заметить, что описанное выше изменение мы вносили, анализируя значения в LOCALS и STACK: смотрели, как
v4
передаётся в инструкцию 30
из инструкции 22
, а 22
берёт данные в a0
и 1
, которые поступают из инструкций 21
и 20
. Эти значения передаются между LOCALS и STACK по принципу графа: от инструкции, вычисляющей значение, в место его дальнейшего использования.Как и пары
Ident
/Assign
в наших AST, значения, которые передаются между LOCALS и STACK, формируют граф между точками вычислений значений и точками их использования. Так почему бы нам не начать работать напрямую с графом?Графы потоков данных
Графы потоков данных — это следующий уровень абстракции после байткода. Если расширить наше синтаксическое дерево связями
Ident
/Assign
, или если мы отследим, как байткод перемещает значения между LOCALS и STACK, то сможем построить граф. Для функции ackermann
он выглядит так:![](https://habrastorage.org/getpro/habr/post_images/5ad/217/5f7/5ad2175f73cf13fa7e47fb521a9aab1a.png)
В отличие от AST или стеко-регистрового байткода Java, графы потоков данных не используют концепцию «локальная переменная»: вместо этого граф содержит прямые связи между каждым значением и местом его использования. При анализе байткода часто приходится абстрактно интерпретировать LOCALS и STACK, чтобы понять, как движутся значения; анализ AST подразумевает отслеживание дерева и работу с символьной таблицей, содержащей связи
Assign
/Ident
; а анализ графов потоков данных часто представляет собой прямое отслеживание переходов — чистая идея «перемещения значения», без шелухи представления программы.Также графами легче манипулировать, чем линейным байткодом: замена узла с вызовом
ackermann
на вызов ackermann2
и отброс одного из аргументов — это всего лишь изменение узла графа (помечен зелёным) и удаление одной из входных связей вместе с транзитными связями узлами (помечены красным):![](https://habrastorage.org/getpro/habr/post_images/b70/c2d/90d/b70c2d90d886bd7c90cdfbb3cb03b42d.png)
Как видите, небольшое изменение в программе (замена
ackermann(int n, int m)
на ackermann2(int m)
) превращается в относительно локализованное изменение в графе потоков данных.В целом, работать с графами гораздо легче, чем с линейным байткодом или AST: их просто анализировать и менять.
В этом описании графов нет многих подробностей: кроме фактического физического представления графа существует много других способов моделирования состояния и управления потоком, работа с которыми сложнее и выходит за рамки статьи. Также я опустил ряд подробностей о преобразовании графов, например, о добавлении и удалении связей, прямых и обратных переходах, переходах горизонтальных и вертикальных (по ширине и глубине), и т. д. Если вы изучали алгоритмы, то всё это вам должно быть знакомо.
Наконец, мы опустили алгоритмы преобразования из линейного байткода в граф, а затем из графа обратно в байткод. Это сама по себе интересная задача, но оставляем её вам для самостоятельной проработки.
Анализ
После того, как мы получили представление программы, нужно её проанализировать: выяснить какие-то факты, которые позволят вам преобразовать программу без изменения её поведения. Многие рассмотренные выше оптимизации основаны именно на анализе программы:
- Свёртывание констант: результатом работы выражения является известное постоянное значение? Вычисление выражения является чистым?
- Приведение типов и инлайнинг: тип вызова метода является типом с единственной реализацией вызываемого метода?
- Удаление ветвей: является булево условное выражение постоянным?
- Удаление мёртвого кода: является результат компиляции «живым»? То есть он как-то влияет на результат работы программы? Вычисление чистое?
- Поздняя диспетчеризация: вычисление чистое, то есть его можно перенести на другое время?
Чем больше фактов мы знаем о программе, и чем они специфичнее, тем агрессивнее мы можем преобразовать программу, чтобы оптимизировать её без изменения семантики. В этой статье мы обсудим приведение типов, константы, жизнеспособность и доступность, а анализ чистоты будет вашим самостоятельным заданием.
Типы, константы, чистота, жизнеспособность — это некоторые из самых распространённых фактов, которые оптимизатор захочет узнать о вашей программе. Анализ в оптимизаторе выполняется очень похоже на приведение типов при фронтендной проверке типов компилятором.
Структура приведений (Inference Lattice)
Для начала давайте решим, как должны работать приводимые типы и константы. По сути, «тип» отражает какое-то наше знание о значении:
- Оно является
Integer
?String
?Array[Float]
?PrintLogger
?
- Это
CharSequence
? То есть значение может бытьString
, а может быть и чем-то вродеStringBuilder
?
- Или это
Any
, то есть мы не знаем, что это за значение?
Потенциальные типы значения в вашей программе могут быть представлены в виде такой структуры:
![](https://habrastorage.org/getpro/habr/post_images/258/4b1/b4d/2584b1b4d5769ebd78d1dcd84e4f686a.png)
Приведение постоянного значения очень похоже на приведение типов: в некотором смысле, постоянное строковое значение
"hello"
является подтипом String
, так же как String
является подтипом CharSequence
. Поскольку у нас есть только одна строка "hello"
, её можно назвать одиночным типом (Singleton Type) — синглтоном. Расширим нашу структуру синглтонами:![](https://habrastorage.org/getpro/habr/post_images/416/872/547/416872547323d84b9b682852ea1f4dcc.png)
Чем выше мы поднимаемся по структуре типа, присвоенного значению, тем меньше мы о нём знаем. Чем ниже спускаемся, тем больше узнаём. Если мы знаем, что значение относится к одному из двух типов, например,
String
или StringBuilder
, тогда можем консервативно предположить, что оно относится к ближайшему вышестоящему типу: CharSequence
. Если мы знаем, что значение равно 0
, или 1
, или 2
, то можно сделать вывод, что это Integer
.![](https://habrastorage.org/getpro/habr/post_images/76a/79c/cc2/76a79ccc288b609397bdc4013a33f7b5.png)
Можно создать ещё более гранулированную структуру, например, разделив чётные и нечётные числа:
![](https://habrastorage.org/getpro/habr/post_images/479/112/0ef/4791120ef75231854b348596b49ab700.png)
Чем гранулированней структура, тем точнее ваш анализ, но при этом на него уйдёт больше времени. Вам решать, насколько подробно вы будете анализировать.
Приведение count
Посмотрим на упрощённую версию программы
main
:static int main(int n){
int count = 0, multiplied = 0;
while(count < n){
if (multiplied < 100) logger.log(count);
count += 1;
multiplied *= count;
}
return ...;
}
Мы убрали разные обращения к
ackermann
, оставив использование только count
, multiplied
и logger
. Так выглядит граф потоков данных:![](https://habrastorage.org/getpro/habr/post_images/383/aa5/a19/383aa5a19df21ddbbe6f13555fb4ea1d.png)
Мы видим, что
count
инициализирован равным 0
в block0
. Затем поток управления сместился в block1
, где мы проверяем, выполняется ли условие count < n
: если да, то идём в block3
и return
, иначе идём в block2
, который инкрементирует count
на 1
и сохраняет результат в count
, возвращая управление в block1
для повтора проверки. Этот цикл работает до тех пор, пока <
не возвратит false
, тогда мы идём в block3
и завершаем программу.Как это проанализировать?
- Начинаем с
block0
. Нам известно, чтоcount = 0.
- Идём в
block1
, мы не знаем, чему равноn
(это вводимый параметр, он может быть любым числомInteger
), а значит мы не знаем, куда пойдётif
. Придётся рассмотретьblock2
иblock3.
- Игнорируем
block3
, поскольку это тривиально, и идём вblock1b
, который либо переносит напрямую вblock2
, либо не напрямую, сначала зажурналировав данные вblock1c
. Мы видим, чтоblock2
берётcount
, увеличивает его на 1 и кладёт значение обратно вcount.
- Мы знаем, что
count
может быть равен0
или1
: смотрим на созданную выше структуру и приводимcount
кInteger.
- Следующий круг: идём через
block1
и приводимn
иcount
кInteger
.
- Снова идём в
block2
, теперьcount
изменён наInteger + 1 -> Integer
. Мы уже знаем, чтоcount
являетсяInteger
, поэтому можем завершить анализ.
Приведение multiplied
Рассмотрим поблочно другой граф потоков данных, относящийся к
multiplied
:- Начинаем в
block0
. Мы знаем, чтоmultiplied
присвоено значение0.
- Переходим в
block1
, в котором есть условный переход, который мы не смогли раньше удалить. Переходим вblock2
иblock3
(здесь всё просто).
- В
block2
обнаруживаем, что мы умножилиblock2
(равный0
) наcount
(который ранее определили какInteger
). Поскольку0 * Integer -> 0
, можно оставитьmultiplied
приведённым к0.
- Снова проходим через
block1
иblock2
.multiplied
всё ещё приведён к0
, поэтому можно прекратить анализ.
Поскольку
multiplied
приведён к 0
, мы знаем, что:multiplied < 100
можно привести кtrue.
if (multiplied < 100) logger.log(count);
можно упростить доlogger.log(count)
.
- Можно убрать все вычисления, которые завершаются в
multiplied
, потому что мы уже знаем, что конечный результат всегда равен0
.
Эти изменения помечены красным:
![](https://habrastorage.org/getpro/habr/post_images/e9f/5f2/e95/e9f5f2e95c4dc3bfc64d54834c2a19ea.png)
Получается такой граф потоков данных:
![](https://habrastorage.org/getpro/habr/post_images/fd4/625/fdb/fd4625fdb669e5d9e0c4d28a71e67f85.png)
Сериализуем его в байткод и получаем программу:
static int main(int n){
int count = 0;
while(count < n){
logger.log(count);
count += 1;
}
return ...;
}
Смоделировав программу в виде подходящей структуры данных, нам хватает простых переходов по графу, чтобы упростить запутанный, неэффективный код, превратив его в маленький эффективный цикл.
Приведение
multiplied -> 0
может применяться и в других оптимизациях, например, при частичном вычислении. В целом, приведения позволяют делать новые приведения, а одни оптимизации открывают дорогу новым. Основная трудность в проектировании оптимизатора программ заключается в том, чтобы он эффективно использовал этот каскад возможностей по приведению и оптимизациям.В этом разделе я показал, как работает приведение в графе потоков данных. Мы рассмотрели:
- Как можно определить структуру приведений для представления наших знаний о каждом значении в программе.
- Как выглядит граф потоков данных для синтетических программ.
- Как идти по графу потоков данных для выполнения приведений каждого значения в программе.
- Как можно использовать эти приведения для выполнения оптимизаций: удаления ветвей или частичных вычислений по мере возможности.
В данном случае мы смогли проанализировать сначала
count
, а затем multiplied
. Это стало возможным потому, что multiplied
зависит от count
, но count
не зависит от multiplied
. При взаимной зависимости пришлось бы анализировать переменные вместе, в ходе одного прохода по графу.Обратите внимание, что приведение — процесс итеративный: вы раз за разом проходите по циклу, пока ваши приведения не перестанут изменяться. В целом, графы потоков данных без циклов (или рекурсий) всегда можно проанализировать за один проход. А программы с циклами или рекурсиями потребуют нескольких итераций анализа.
Сейчас нам хватило только два прохода по циклу
while
, но может случиться так, что анализ потребует O(глубина структуры приведений)
итераций. Поэтому более подробная структура (например, с разделением на чётные и нечётные числа) может улучшить точность анализа, но и увеличит его длительность, поэтому придётся искать компромиссы.Такой же подход можно использовать для приведения свойств произвольных рекурсивных функций, как мы сейчас увидим.
Межпроцедурное приведение функций
Выше мы приводили значения внутри единственного тела функции, ради простоты игнорируя вызовы других функций или методов. Но большинство программ содержать много функций, вызывающих друг друга, так что при работе с реальными программами вам придётся приводить свойства не только одного выражения в функции, но и самих функций, а также приводить их взаимодействие друг с другом в графе вызовов.
Простые нерекурсивные функции
В большинстве случаев обрабатывать другие функции несложно. Посмотрите на эту программу:
static int main(int n){
return called(n, 0);
}
static int called(int x, int y){
return x * y;
}
Граф потоков данных для этих двух функций выглядит так:
![](https://habrastorage.org/getpro/habr/post_images/45a/a32/471/45aa32471c28271c2755e5494a590891.png)
Приведём возвращаемое значение
main
:- Приводим
main(n)
- Приводим
called(n, 0)
- Приводим
x * y
кx = n
иy = 0
n * 0
равно0
- Приводим
called(n, 0)
равно0
- Приводим
main(n)
равно0
Когда в ходе приведения вы достигаете вызова функции, то сначала приведите вызываемого, прежде чем продолжить приведение вызывающего. Этот стек приведений может быть любой глубины и отражать стек вызовов при исполнении программы.
Мы знаем, что
called(n, 0)
равно 0
, и можем это использовать для упрощения графа потоков данных:![](https://habrastorage.org/getpro/habr/post_images/3e8/484/17d/3e848417db361dae9f39425ddeed1a13.png)
Сериализуем его в код:
static int main(int n){
return 0;
}
Теперь наши функции не рекурсивны: если A вызывает B, вызывает C, вызывает D, затем D возвращает своё приведение к C, B, D и A. Однако если функция A вызывает B и B вызывает A, или даже A рекурсивно вызывает A, то всё это разваливается, поскольку вызовы ничего не возвращают!
Рекурсивная факториальная функция
Рассмотрим простую рекурсивную функцию, написанную на псевдо Java:
public static Any factorial(int n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
Она берёт
n
и делает его int
, но возвращаемый тип помечен как Any
: объявление не соответствует возвращаемым данным. Мы видим, что factorial
возвращает int
(или Integer
в нашей структуре). Но если перед возвращением полностью анализировать тело factorial
, то мы проанализируем рекурсивный вызов factorial
до завершения нашего анализа самой factorial
, то есть столкнёмся с бесконечной рекурсией! Как нашему движку приведения определить это от нашего имени?Приведение с Bottom
Добавим в нашу структуру приведений специальное значение
Bottom
:![](https://habrastorage.org/getpro/habr/post_images/abe/520/44e/abe52044e569bfe201c2d0f6998761ec.png)
Оно означает «мы ещё не знаем, что это, но вернёмся сюда позднее и заполним». Применим
Bottom
в графе потоков данных для factorial
:![](https://habrastorage.org/getpro/habr/post_images/50b/347/73b/50b34773b36ec9470e3bdb03efaec5eb.png)
- Начинаем с
block0
.n
является неизвестнымInteger
,1
является1
, тогда результатn == 1
тоже неизвестен, поэтому придётся анализировать обе веткиtrue
иfalse
.
- С
true
всё понятно:return
возвращает1
.
- В ветке
false
результатn - 1
благодаряn
является неизвестнымInteger
.
factorial
— это рекурсивный вызов, поэтому пока что сделаем егоBottom
.
*
изn: Integer
иfactorial
:Bottom
тоже покаBottom
.
return
возвращаетBottom
.- Вся функция
factorial
возвращает1
илиBottom
, а в нашей структуре ближайшим верхнеуровневым приведением для них является1
.
- Вставим
1
в качестве приведения рекурсивного вызоваfactorial
, который ранее мы пометили какBottom
.
Integer * 1
теперьInteger
.
return
теперь возвращаетInteger
.factorial
теперь возвращаетInteger
или1
, а ближайшим верхнеуровневым приведением для них будетInteger
.
- Снова приведём рекурсивный вызов
factorial
, на этот раз в видеInteger
. Выражение*
берётn: Integer
иfactorial: Integer
, которые остались неизменнымиInteger
, и теперь приведения можно завершить.
Мы смогли привести возвращаемый
factorial
результат к Integer
, несмотря на то, что это рекурсивная функция без объявления возвращаемого типа.Хотя все эти примеры надуманы, они иллюстрируют способ приведения при наличии вызовов функций. С рекурсивными функциями вы можете делать для вызовов заглушки из
Bottom
, когда впервые с ними сталкиваетесь, а по завершении первого аналитического прохода замените заглушки первым приведением и передайте это изменение вверх по графу потока данных.В данном случае выражение
*
проанализировано трижды:(n: Integer) * (factorial: Bottom)
(n: Integer) * (factorial: 1)
(n: Integer) * (factorial: Integer)
Как и в случае с приведением константы
multiplied
из цикла, для завершения приведений может потребоваться выполнить до O(глубина структуры приведений)
проходов. Этот подход обобщает другие стили рекурсивных функций и позволяет приводить другие свойства, например, чистоту.Приведение жизнеспособности и доступности
Анализ жизнеспособности и доступности — это пара оптимизаций, которые относятся к категории «удаление мёртвого кода». При этом анализе мы ищем код, значения из которого влияют на финальный результат («живой код»), и код, который может быть достигнут потоком управления программы («доступный код»). Весь остальной код можно удалить.
Давайте рассмотрим другую упрощённую версию исходной функции
main
:static int main(int n){
int count = 0, total = 0, multiplied = 0;
while(count < n){
if (multiplied > 100) count += 1;
count += 1;
multiplied *= 2;
total += 1;
}
return count;
}
В отличие от предыдущих версий, здесь мы поменяли условный переход в
if (multiplied > 100)
и заменили multiplied *= count
на multiplied *= 2
. Так мы упростили графы программы без потери обобщённости.Обратные проходы для оценки жизнеспособности кода
Есть две проблемы, которые нужно обнаружить в приведённой выше программе:
multiplied > 100
никогда не бываетtrue
, поэтомуcount += 1
никогда не будет выполнено («недоступно»).
total
хранит некоторые вычисленные значения, но одно из них не используется («нежизнеспособно»).
В идеале, программа должна выглядеть так:
static int main(int n){
int count = 0;
while(count < n){
count += 1;
}
return count;
}
Теперь давайте посмотрим, как анализатор перепишет её автоматически.
Сначала взгляните на граф потоков данных:
![](https://habrastorage.org/getpro/habr/post_images/0f1/2a1/af5/0f12a1af57586674b9e1a7fb1ae13c86.png)
Он гораздо запутаннее графов, которые мы уже видели, но всё ещё читабелен: начинаем в
block0
, идём в block1
, если одно условие истинно, то идём в block1b
, если истинно другое условие, то идём в block1c
, и так далее, пока не завершаем в узле return
в block3
.Убираем мёртвый и недоступный код
Можем применить такое же приведение типов и констант, как и для поиска
multiplied -> 0
, и модифицировать граф:![](https://habrastorage.org/getpro/habr/post_images/92a/1dd/f90/92a1ddf903dcc52cc9966220c56db876.png)
Вот что получилось:
![](https://habrastorage.org/getpro/habr/post_images/906/1ef/09c/9061ef09c209275be5158a8b3184a5bc.png)
Мы видим, что условный переход в
block1b
(0 > 100
) никогда не бывает true
. Значит ветка false
из условия block1c
недоступна и может быть удалена (как и условие if
):![](https://habrastorage.org/getpro/habr/post_images/587/21e/8e4/58721e8e43fb326379c796593f9bd2a7.png)
Наконец, мы видим «тупиковые узлы»
total
и >
, которые что-то вычисляют, но не используются ни в одном нисходящем условном переходе, возвращении результатов или вычислении. Это можно понять, пройдя по графу вверх от узла return
, собирая все живые узлы и удаляя остальные: >
, 100
, 0
в block1b
, total
, 0
, и + 1
, передаваемый в total
из block0
и block2
. Вот что получилось:![](https://habrastorage.org/getpro/habr/post_images/55b/508/e16/55b508e164d0c4421aa525dcab56e122.png)
Сериализуем в байткод и получаем «идеальную» программу:
static int main(int n){
int count = 0;
while(count < n){
count += 1;
}
return count;
}
Заключение
В этой статье мы рассмотрели приведение программы внутри оптимизирующего компилятора:
- Рассмотрели ручные оптимизации программы-черновика.
- Поняли, что эти оптимизации можно делать автоматически с помощью оптимизатора.
- Рассмотрели разные способы, с помощью которых оптимизирующий компилятор может моделировать вашу программу в памяти в виде промежуточного представления. В дальнейшем применяли в статье представление в виде графа потоков данных.
- Рассмотрели методики приведения: «внутрипроцедурные» в рамках одной функции и «межпроцедурные» между несколькими функциями, возможно, рекурсивными.
- Рассмотрели анализ на жизнеспособность и доступность: поиск частей программы, не влияющих на результат её выполнения.
- Рассмотрели применение приведения и анализа для упрощения промежуточного представления, которое можно сериализовать в более простые и компактные программы.
Мы увидели, что можно превратить ручной процесс оптимизации программы в автоматизированный, применяя к простым структурам данных простые алгоритмы.
Это лишь небольшое введение в работу оптимизирующих компиляторов, которые делают наш код быстрее. В статью многое не вошло. Если хотите узнать больше, можете начать с этого:
Комментарии (14)
amarao
25.11.2019 16:07Программа — это описание закономерностей между входными сайд-эффектами и выходными. Если они не нарушаются, то компилятор может делать что угодно (хоть заменить весь код на GLUT).
… А ещё компилятору разрешено нарушать временные сайд-эффекты, но запрещено нарушать causality.
gearbox
25.11.2019 16:39>Теперь мы знаем, что logger — это PrintLogger
Как? type propagation или type inference? Если inference — то какой? Hindley-Milner или есть что поинтереснее?
>а multiplied — нет: она начинается с 0 и каждый раз умножается через multiplied = multiplied * count,
Ээээ, нееет. В смысле да, но как мы об этом узнали? Точнее не мы а компилятор. Что стоит за этим выводом — гвоздями прибитый эмпиризм или он на этой же логике выведет str += '' и int += 0?
ну и так далее и тому подобное. /зануда моде оффQuetzal
25.11.2019 19:11+1В Java, как и в Scala (автор статьи, Li Haoyi, хорошо известен Scala сообществу) не может быть использован алгоритм Hindley–Milner, так как HM не поддерживает sub-typing.
voidnugget
25.11.2019 20:27+1В статье про Optimization Pass'ы ни слова про SSA / mSSA / Array-SSA, зато куча байт-кода…
Слишком глубоко копнули без разъяснения теоретических основ, общих оптимизационных задач и практик.
tmaxx
25.11.2019 22:36+1Кое-что компилятор не смог оптимизировать (например, неиспользуемый вызов new PrintLogger)
Есть предположение, что компилятор вынужден был оставить не вызов пустого конструктора, а загрузку класса PrintLogger.
Кстати, что именно вы декомпилировали? Байт-код (результат javac) или результат JIT?
arTk_ev
26.11.2019 14:29-1Все равно, на лапше-коде этот компилятор помрет на первом же этапе, да и бессмысленно.
А вот solid код, с минимум побочных эффектов, — это довольно безопасно, масштабируемо, и эффективно. Тот же Burst Compiler — чудесное решение, хоть и сырое.
ice2heart
Не надо быть умнее компилятора. Красивый и понятный код легче поддерживать, а компилятор и сам неплохо выкинет лишнее.
Я некоторое время назад написал транспиллер из bf в llvm ir… И было очень интересно смотреть как компилятор выкидывал куски кода заменяя на константы…
ZaMaZaN4iK
К сожалению, компиляторы не идеальны и иногда таки приходится либо объяснять, что же я хочу тут получить (с помощью атрибутов, интринсиков и так далее). Ну или на худой конец просто садимся писать на ассемблере, если некогда ждать, когда там в компиляторе пофиксят очередное правило для оптимизации.
ice2heart
Ага, не спорю никто не идеален, но так надо делать только после профайлинга и понимания проблемы.
domix32
Кому-то же надо писать оптимизирующие компиляторы
khim
ice2heart
Ну если таблица используется как просто хранилище данных и не изменяется то компилятор может вытаскивать данные просто по смещению. Но в целом да. Максимум что может так оптимизировать обращение к структуре, тут вы правы.
khim
Сейчас как раз появляются первые попытки что-то такое сделать. Робкие и малополезные.
Может лет через 20 — это всё будет и не нужно. Но пока — о структурах данных приходится думать программисту