На курсе будут рассматриваться
Разработку ПО можно разделить на две части:
Существенной проблемой при разработке является трудность управления памятью в так называемых неуправляемых языках (например, C и C++). Поэтому появились
Позже в 90-ых начали появляться управляемые языки: Java, C#, JavaScript. Как следствие появились виртуальные машины, которые управляли памятью и исполняли байт-код
Теперь условно можно выделить два типа языков:
Каждый язык соответствовал одной из этих целей:
В компиляторе берется исходный код, он представляется в виде промежуточных структур, таких как абстрактное синтаксическое дерево (Abstract Syntax Tree, AST) и граф потока управления (Control Flow Graph, CFG), а потом превращается в нативный для процессора/ОС код, который исполняется процессором
Термин AOT-компиляция (Ahead-of-Time) предполагает, что код обрабатывается до непосредственного выполнения. Напротив, JIT-компиляция (Just-in-Time) - это компиляция байт-кода в машинный код прямо во время выполнения программы. Это позволяет применять оптимизации на основе данных о реальном выполнении программы (профилирование)
В случае с виртуальной машиной исходный код превращается в промежуточный код, которой после исполняется виртуальной машиной
За последние два десятка лет очень изменилось то, как мы используем наши устройства - сейчас мы работаем с большой комбинацией устройств, и это создает множество совместных сценариев работы с устройствами
В индустрии стремятся сделать так, чтобы приложения разрабатывались под разные устройства
Так как бизнес хочет наилучшее решение за наименьшие деньги и время, нужно, чтобы устройства имели одну кодовую базу. Для запуска приложения на разных устройствах нужны виртуальные машины, фреймворки и библиотеки, реализованные для каждой из целевых платформ
Оказывается, что количество выручки с продаж потребительской электроники растет, а люди ценят наличие экосистемы среди своих устройств
Из-за возникшей дуополии Google и Apple это кажется простой задачей, однако существует огромное количество производителей, которые имеют свои маркеты приложений (около 400). С пользовательской точки зрения, когда на рынке 400 маркетов, становится больно пользоваться экосистемами
Появилась альтернатива - миниприложения. Такие миниприложения, написанные на JavaScript, встроены в мессенджер WeChat. Оказалось, что миниприложения начали преобладать над этими 400 маркетами, так как они были намного удобнее
Для разработчика мобильных приложений это означает:
Маленькому бизнесу становится дорого это поддерживать, поэтому нам нужен инструмент, который позволит решить эту проблему более эффективно. Проще всего сделать одну виртуальную машину под разные устройства
Многие производители телефонов в первую очередь зарабатывают с продажи аппаратного обеспечения. Они имеют широкую линейку продуктов и данные использования от реальных пользователей.
Разработчикам приложений важно минимизировать усилия на разработку приложений, поэтому для их привлечения нужна знакомая экосистема разработки и простой доступ к заработку
А пользователям важно, чтобы приложения были быстрыми, а батарея держалась долго, поэтому нужно, чтобы приложения были мгновенными, энергоэффективными и работали внутри экосистемы устройств
Не всегда разработка кроссплатформенных решений облегчает создание новых продуктов, например Oracle с агрессивным лицензированием Java и появившийся в ответ на это C#. Потребность в большинстве языках программирования появилась с ростом рынка потребительской электроники, такие как Go, Swift, Kotlin, Dart. Например, Kotlin появился как ответ на медленные обновления языка Java. Swift - как современная альтернатива Objective-C. React - как попытка сделать кроссплатформенное решение для JavaScript
Кроссплатформенные решения поддерживаются ограниченным набором компании (Google, Apple, Microsoft и так далее). Такие компании заинтересованы, потому что они получают основную выгоду
Разберем примеры кроссплатформенных решений:
Платформа .NET и фреймворк Xamarin как единая кодовая база для разработки
Для Android виртуальная машина Dalvik (позже Android Runtime, ART). Изначально Dalvik был простым интерпретатором. Позже в него добавили JIT- и AOT-компиляцию. Далее сборка профилей использования кода позволила компилировать приложения на серверной инфраструктуре
Для браузеров есть виртуальная машина (например, V8 для JavaScript), пользовательский интерфейс и движок для рендера
LLVM - платформа для построения компиляторов. Она предоставляет универсальное промежуточное представление (Intermediate Representation, IR), на котором проводятся оптимизации, и бэкенды для генерации машинного кода под разные архитектуры. Например, на основе LLVM разработан компилятор Clang для C/C++
Разработка языков программирования началась с создания языка для машины ЭНИАК (ENIAC, Electronic Numerical Integrator and Computer)
Программирование на ЭНИАК осуществлялось соединением нужных разъемов на панели проводами и зачастую занимало недели
ЭНИАК использовалась для расчета вычисления, связанных с ядерным оружием, прогнозирования погоды, инженерных расчетов
Первым широкоиспользуемым языком стал FORTRAN, созданный в 1950-ых Джоном Бэкусом в IBM. Далее в 1956-1958 создается LISP при участии Джона Маккарти
Большинство популярных языков, таких как Go, Rust, Typescript, Kotlin, используемых в индустрии, были разработаны в течение нескольких лет (4-6 лет), что подтверждает, что создание промышленного языка программирования - задача нетривиальная
Целями создания языка программирования могут быть разными. Например,
Поэтому у конкретного языка может быть ограниченная область применения
Так что же нужно для создания языка:
Разработка языка программирования - огромная работа, которая может не прекращаться. Разработка начинается с формулировки требований и приоритетов:
Также нужно выбрать:
Что бы разработчик не выбрал, кому-то это можно не понравится. Нельзя уверенно сказать, какая комбинация решений приведет к наилучшему исходу без прототипирования, а функции языка могут взаимодействовать друг с другом
Пример взаимодействия функций языка из языка Go:
package main
import "fmt"
type IM interface {
Method()
}
type SM struct {i int}
fune (x *SM) Method() {
x.i = 1
}
func check(im IM) {
if im != nil {
im.Method()
}
fmt.Println("checked")
}
func main() {
check(nil) // checked
var S_nil *SM = nil
check(S_nil) // segfault
}
Здесь функция check правильно обработает значение nil, однако при передачи указателя на объект SM интерфейса IM, равного nil, выбрасывается ошибка доступа к адресу, так как по адресу nil нет объекта с методом Method()
Современная система программирования или приложение содержит компоненты, написанные на нескольких языках, так как ни один язык не удовлетворяет все потребности. Части системы, такие как бизнес-логика, фреймворки, UI, требуют разных языков, которые отличаются в управлении памятью, параллелизмом, системе типом и так далее
Тогда появилась идея создания семейства языков, которые будут хорошо вместе взаимодействовать, вместо языка, который будет встраиваться с другими
Тогда для этих языков нужно писать компилятор, значит, нужно выбрать язык, на котором нужно написать этот компилятор
При этом, в нашем семействе должен быть язык, на котором будет приятно писать следующие версии нашего компилятора, чтобы снизить зависимость и влияние от сторонних языков
В начале этот первый язык должен быть легко читаемым, легко понимаемым, иметь все нужные простые функции и механизмы и ничего того, что выходит за нашу область. Также в нем должно быть уменьшено число ошибок времени исполнения, безопасность null-типов, системы типов, сборщик мусора и модульность
Производительность первого языка не должна быть приоритетной для нас
Название языка должно быть простым для понимания. После этого можно начать предварительный дизайн: дизайн грамматики и система типов
Шаг второй - разработка компилятора на другом языке и исполнения скомпилированного кода. Далее компилятор пишется на самом языке, что позволяет протестировать наш язык в прикладной задаче
Грамматика и синтаксис языка должна быть простой, а семантика - очевидной, не должно быть скрытой семантики и “злой магии”
Среди базовых типов можно выбрать байт (8-битное целое число), 64-битное целое число, 64-битное вещественное число, логический тип, символ, строка. Для создания компилятора могут также понадобиться вектор (динамический массив), опциональный тип (вместо null) и классы
Другие продвинутые механизмы могут вызвать дополнительные трудности в разработке:
foreach может потребовать другие функции, такие как итераторы и кортежиСейчас большинство веб-приложений написаны на JavaScript - динамически типизируемом языке для скриптов с похожим на язык C синтаксисом
Код на JavaScript могут исполнять множество движков (виртуальных машин)
Хотя в JavaScript есть примитивные типы, многие операции заставляют их вести себя как объекты через автоматическую упаковку в объекты. У объекта в JavaScript есть свойства, у свойства - имя и значения, а сами свойства могут добавляться и удаляться во время исполнения
В JavaScript вместо наследование использованы прототипы: каждый объект хранит в себе ссылку на прототип другого объекта, тем самым наследуя его свойства. Объекты могут представлять собой цепочку прототипов, которую можно изменять во время исполнения
Конвертация типов в JavaScript позволяют выполнять такие операции:
var x = 1 + 2; // 3
x = 1 + "2"; // "12"
x = 1 + {}; // "1[object Object]"
x = +"23"; // 23
Из-за прототипов, свойств и динамической типизации JavaScript очень динамический, что представляет трудность для реализации виртуальной машины. Из-за этого появляются проблемы в разработке: приходящий тип объекта не соответствует ожидаемому
Далее появился TypeScript, позволяющий аннотировать типы и проверять их перед исполнением программы
Движок JavaScript работает так:
Спецификация JavaScript не указывает формат промежуточного кода, поэтому разработчик движка волен сам выбрать его формат. Интерпретатор также содержит сборщик мусора, который управляет памятью, и совершает оптимизации над кодом
Внутри компилятора:
После этого интерпретатор исполняет байткод
Из-за того, что JavaScript - динамически типизированный, выражение x + y может представлять из себя:
Из-за этого JavaScript обладает низкой производительностью
Главная цель для JavaScript - мгновенно исполнять код, чтобы веб-страницы загружались быстро. Поэтому парсер и интерпретатор не должны тратить ресурсы на оптимизации. Другой путь - компиляция после парсера, что замедляет время запуска
Сейчас в браузерах байткод после парсера сразу исполняется интерпретатором, а в другом потоке горячие регионы - часто вызывающиеся участки кода - компилируются и исполняются нативно
Всего можно выделить 4 уровня:
Если кусок кода вызывается больше какого-то выбранного числа, то далее выбирается нужные оптимизации исходя из информации о выполнении кода
Большая часть веб-приложений и мобильных приложений используют такую гибридную модель: часть кода исполняется в интерпретаторе, часть кода нативно как машинные инструкции
Старая версия движка JavaScriptCore использовала три уровня исполнения
В новой версии добавился новый уровень:
Позднее поняли, что с таким конвейером тяжело работать, поэтому упростили инфраструктуру
Интерпретатор имеет ряд достоинств
И недостатков: большое потребление памяти и низкая скорость по сравнению с машинным кодом
Интерпретацию можно ускорить с помощью AOT- и JIT-компиляций, скрытых классов (структур, с помощью которых можно быстрее обрабатывать сложные объекты). Также можно применить такие оптимизации:
Для определения операции из инструкции байткода не следует использовать блоки if/switch. Вместо этого можно использовать:
Прямое перенаправление (Direct Threading) - изменение указателя на текущую инструкцию на значение, равное коду инструкции (opcode)
Непрямое перенаправление (Indirect Threading) - переход делается не напрямую по коду инструкции, а через уровень косвенной адресации (сначала берётся адрес в таблице, затем по нему происходит переход)
Перенаправление токенов (Token Threading) - использование токенов-указателей
Встроенное кеширование (Inline Caching)
Вместо того, чтобы заново проверять типы для исполнения операции, можно для часто применяющихся ситуаций (например, для сложения двух чисел) перенаправлять на другой поток инструкций
Встроенное кеширование имеет несколько состояний
Интерпретатор проще реализовать, чем компилятор. Он исполняет исходный код построчно, без предварительного преобразования в машинный код
Главное преимущество - портируемость: один и тот же исходный код может выполняться на разных устройствах, если для каждой платформы есть интерпретатор
Недостаток интерпретации — низкая скорость выполнения, поскольку анализ и исполнение происходят во время работы программы
Чтобы ускорить выполнение, придумали JIT-компиляцию (Just-In-Time) - гибридный подход, который совмещает интерпретацию и компиляцию
JIT-компилятор во время исполнения анализирует программу и определяет, какие участки кода выполняются чаще всего (так называемые “горячие” участки)
Эти участки компилируются в машинный код на лету, чтобы повысить производительность. При этом редко исполняемые части кода остаются интерпретируемыми, что экономит время и память.
Примеры сред, использующих JIT:
Процесс компиляции делится на три основные стадии:
Фронтенд представляет из себя:
Миддленд:
Бекенд:
Промежуточное представление - это форма кода, удобная для анализа и преобразования. Хорошее промежуточное представление обладает следующими свойствами:
Примеры IR:
SSA - особое представление промежуточного кода, где каждая переменная имеет только одно место присваивания. Если в коде встречаются ветвления, то значения объединяются через специальные фи-функции (φ-functions)
Преимущества SSA: упрощение анализа потока данных, повышение эффективности оптимизаций, облегчение удаления ненужных переменных
Оптимизации компилятора - это преобразования программы, которые делают её быстрее, компактнее или экономичнее, не изменяя поведение. Оптимизации компилятора бывают:
Приведем несколько простых оптимизаций:
Глазок (Peephole) - локальная оптимизация, рассматривающая маленькие фрагменты кода (2–5 инструкций) и заменяющая их на более эффективные эквиваленты. Например, такой код:
int a = b + 3;
int d = a + 5;
int c = d * 2;
заменяется на:
int d = b + 5;
int c = d * 2;
Схлопывание (или свертка) констант (Constant Folding) - вычисление выражений на этапе компиляции
int x = 2 * 3; // заменяется на int x = 6;
Удаление мертвого кода (Dead Code Elimination) - удаление кода, результат которого не используется, а также кода после return или неиспользуемых переменных
Устранение общих подвыражений (Common Subexpression Elimination) - устранение общих подвыражений, таким образом, их вычисление производится один раз. Например,
a = ((b - c) % d) * ((b - c) / e);
превращается в:
f = (b - c);
a = (f % d) * (f / e);
Встраивание (Inlining) - подстановка тела функции вместо вызова. Например:
int square(int x) {
return x * x;
}
int y = square(5); // заменяется на int y = 5 * 5;
Loop Invariant Code Motion - вынос из цикла выражений, не зависящих от итерации. Например,
for (int i = 0; i < N; i++) {
int x = N * N;
int j = x * i;
}
превращается в:
int x = N * N;
for (int i = 0; i < N; i++) {
int j = x * i;
}
Induction Variable Elimination - устранение или объединение переменных, изменяющихся линейно с номером итерации. Например,
for (int i = 0; i < N; i++) {
j = 2 * i + 1;
A[j] = 0;
}
превращается в:
for (int j = 1; j < 2 * N; j += 2) A[j] = 0;
Раскрутка цикла (Loop Peeling) - отделение первых итераций цикла для оптимизации граничных условий. Например,
for (int i = 0; i < N; i++) A[i] = f(i);
превращается в:
A[0] = f(0);
for (int i = 1; i < N; i++) A[i] = f(i);
Loop Unrolling (развёртывание цикла) - выполнение нескольких итераций за одну, чтобы уменьшить количество сравнений
for (int i = 0; i < N; i++) A[i]++;
превращается в:
for (int i = 0; i < N; i += 4) {
A[i]++; A[i+1]++; A[i+2]++; A[i+3]++;
}
Loop Fission - один цикл на два для улучшения кэш-локальности или параллелизма. Например,
for (int i = 0; i < N; i++) {
A[i] = f(i);
B[i] = g(A[i]);
}
превращается в:
for (int i = 0; i < N; i++) A[i] = f(i);
for (int i = 0; i < N; i++) B[i] = g(A[i]);
Loop Fusion - слияние два цикла, проходящих по тем же данным. Например,
for (int i = 0; i < N; i++) A[i] = B[i] + 1;
for (int i = 0; i < N; i++) C[i] = A[i] * 2;
превращается в:
for (int i = 0; i < N; i++) {
A[i] = B[i] + 1;
C[i] = A[i] * 2;
}
Для большинства оптимизаций используется анализ граф управления потоком (Control Flow Graph, CFG) программы. Для него применяются обходы графа:
Блок V доминирует над блоком W, если любой путь от входа в функцию до W проходит через V. Блок V называют доминатором. Начальный блок доминирует над всеми
Дерево доминаторов строится при помощи DFS и служит для оптимизаций, анализа циклов и построения SSA-формы
Цикл в графе потока управления определяется через наличие обратного ребра (back-edge) - перехода из блока B в блок A, где A доминирует над B.
Основные понятия:
for (int i = 0; i < N; i++)Алгоритм анализа циклов обычно выполняется так:
B -> A проверяется, доминирует ли A над B. Если да, то это обратное реброКогда виртуальная машина компилирует программу, она не преобразует её напрямую из байткода или AST в машинный код. Реализация современных JIT/AOT-компиляторов устроена иначе: они используют промежуточное представление программы - IR (Intermediate Representation). Промежуточное представление - это набор инструкций, графов, блоков, который достаточно далёк от конкретных особенностей аппаратной платформы, но уже достаточно формален для того, чтобы над ним выполнять оптимизации
Промежуточное представление надо превратить в реальный машинный код - набор инструкций процессора с конкретной архитектурой (arm, x86, RISC-V и других). Программа, которая переводит промежуточное представление к конкретному бинарному коду называется бекендом компилятора
Бекенд состоит из нескольких ключевых фаз, каждая из которых решает строго определённую задачу. Чтобы понимать, как компилятор действительно порождает код, нужно разбираться в логике этих фаз:
Высокоуровневое промежуточное представление - это представление программы, свободное от особенностей конкретной машины. Однако на практике даже промежуточное представление создаётся с оглядкой на целевую платформу, например, для упрощенного перевода инструкций под основную архитектуру
Высокоуровневое промежуточное представление:
И именно здесь возникает фундаментальная проблема: в промежуточном представлении значений может быть сотни, а аппаратных регистров - меньше тридцати, например, ARM64 предоставляет 31 регистр общего назначения
В промежуточном представлении легко создать 300 временных значений, но в реальном процессоре такое невозможно
Компилятору требуется понять:
Если некоторая инструкция создала значение A, то это значение имеет время жизни с момента определения до последнего использования. Но, так как программа состоит из блоков, между которыми есть переходы, циклы, ветвления, то нельзя просто определить, в какой момент значение A больше не нужно; нужно понять:
Это приводит к важному определению: значение A живо в точке P, если существует путь от P до какого-либо использования A
Не важно, реальный ли это путь или потенциальный, поэтому говорят, что статическая живость - это приближение реального поведения программы
Настоящий жизненный цикл значения на конкретном запуске может быть короче, но статический анализ обязан учитывать худший случай. Отсюда возникают понятий:
Чтобы анализ живости был возможен, нужно упорядочить базовые блоки графа потока управления в линейную последовательность.
Это не просто список блоков, а порядок, в котором:
Алгоритм расчёта живости работает с конца в начало, а регистровый аллокатор типа линейного сканирования ожидает, что программа развёрнута в линейную последовательность инструкций. Линейная нумерация - это своего рода временная шкала, вдоль которой мы будем измерять жизнь значений
Далее анализ живости выполняется в несколько фаз:
Обход графа потока управления идёт в обратном линейном порядке блоков
Для каждого блока вычисляется набор живых значений (live-set) - множество значений, которые должны быть живы в начале блока.
Набор живых значений блока складывается из:
Вход фи-функции выбирается в зависимости от того, из какого блока пришёл контроль, поэтому значение, необходимое фи-функции, должно быть живо в конце блока-предшественника его ветви
После определения набора живых значений блока каждая инструкция из набора получает живой диапазон, включающий весь блок: [block.begin, block.end)
Теперь внутри блока мы анализируем инструкции, начиная с конца:
Здесь впервые начинает образовываться структура живых интервалов: значения, которые используются позже, живут дольше; значения, которые не используются, постепенно покидают набор живых значений
После полного анализа всех инструкций блока необходимо удалить значения, которые участвуют в фи-инструкциях в этом же блоке, поскольку их жизнь фактически начинается в начале блока, а не продолжается в его конце
Если блок является заголовком цикла, то все значения, находящиеся в наборе живых значений в начале блока, обязаны перекрывать весь цикл. Это означает, что отрезок времени жизни расширяется до [loop_header.begin, loop_end).
Если значение живо во входе цикла и живо в одном из его тел, оно должно быть непрерывно живым для всей кольцевой структуры, чтобы не возникло разрывов, нарушающих моделирование циклического контроля
Этот шаг обеспечивает целостность данных в циклах для любого алгоритма распределения регистров
Теперь, когда мы знаем, где каждое значение живёт, можно распределять регистры.
У процессора мало регистров. Например:
Если бы регистров было 200–300, аллокация регистров не была бы нужна, но добавление регистров дорого само по себе:
Основная цель аллокатора регистров - минимизировать обращения к памяти, то есть вытеснений значений с регистров (spill) и внесений значений (fill)
Тут есть несколько подходов, но самым простым является линейное сканирование (Linear Scan). Линейное сканирование:
Простая версия линейного сканирования выглядит так:
Когда начинается новый интервал:
Самый простой способ выбрать, кого вытеснять - выбрать интервал с максимально дальним концом. Но это приводит к ужасному количеству вытеснений и внесений, потому что алгоритм не смотрит на ближайшее использование значения
Лучше выбирать интервал с самой далёкой следующей точкой использования. Это позволяет:
Ещё одна важная оптимизация: не нужно вытеснять весь интервал целиком, можно разбить его на части. Это радикально уменьшает количество вытеснение и внесение и часто спасает производительность
Выбор стратегии вытеснения должен быть правильным. Если алгоритм выбрал неудачное значение для вытеснения, начинается эффект домино:
Генерация кода - последняя стадия бекенда. Она использует ранее полученные артефакты:
Генерация кода работает так:
Инструкции промежуточного представления преобразуются в инструкции целевой архитектуры, учитывая:
Создаётся метаинформация для виртуальной машины и сборщика мусора:
Стековый фрейм (или фрейм вызова) содержит:
Особенно важно то, что адресация к слотам происходит через регистры sp или fp, поэтому генератор кода обязан аккуратно работать с этими регистрами
Однако, вместо бекенда можно использовать LLVM () - проект программной инфраструктуры для создания компиляторов, однако есть ключевые проблемы:
Рассмотрим, как компилятор оптимизирует код, который кажется корректным с точки зрения семантики, но избыточен с точки зрения выполнения, и как эти оптимизации тесно связаны с работой виртуальной машины и деоптимизацией
Удаление мертвого кода (Dead Code Elimination, DCE) - одна из базовых оптимизаций компилятора. Ее цель - убрать инструкции и даже целые блоки, которые не влияют на наблюдаемое поведение программы.
Мертвой считается инструкция, если ее результат нигде не используется и при этом она не имеет побочных эффектов. Например:
int Foo(int a, int b) {
int c = a + b;
int d = a - b;
return d;
}
Значение c вычисляется, но нигде не используется, поэтому вычисление a + b можно удалить без изменения результата функции
Бывают и мертвые блоки кода. Они возникают, когда управление никогда не может попасть в этот участок:
int Foo(int a, int b) {
int c = a + b;
if (0) {
c = a - b;
}
return c;
}
Условие всегда ложно, значит весь блок if бесполезен. Такие оптимизации часто выделяют в отдельный проход и называют устранением ветвлений (branch elimination)
Чтобы реализовать удаление мертвого кода и другие анализы, компилятору нужно обходить граф потока управления, помечать инструкции и блоки как обработанные или живые. Делать это простыми булевыми флагами неудобно, потому что после каждого прохода пришлось бы очищать эти флаги у всех объектов, что дорого. Поэтому вводится механизм маркеров
Маркер - это специальное значение, которым помечают инструкции или блоки во время анализа. Идея в том, что объект считается помеченным не просто по факту наличия флага, а по совпадению версии маркера
Каждый маркер состоит из двух частей: номера слота и номера маркера. У каждой инструкции есть массив слотов, в каждом из которых хранится номер последнего маркера, который туда записывали
Когда начинается новый проход оптимизации, компилятор не очищает старые маркеры, а просто увеличивает глобальный номер. Старые значения автоматически становятся неактуальными
Пример создания и использования маркера:
Marker NewMarker() {
current_index_++;
for (uint32_t i = 0; i < SLOTS_NUM; i++) {
if (!slots_[i]) {
Marker mrk = (current_index_ << SLOT_BITS) | i;
slots_[i] = true;
return mrk;
}
}
ERROR("No free slots");
}
Проверка маркера сводится к сравнению чисел, без очистки структур данных
Используя маркеры, можно реализовать удаление мертвого кода следующим образом.
Сначала компилятор проходит по всем инструкциям в порядке RPO (Reverse Post Order), что удобно для анализа зависимостей. Он помечает как живые все инструкции, которые нельзя удалить. К таким относятся вызовы функций, переходы управления, записи в память, инструкции, которые могут бросить исключение, и вообще любые инструкции с побочными эффектами
После этого компилятор рекурсивно помечает все входные операнды этих инструкций. Например, если жива инструкция store, то все инструкции, вычисляющие адрес и значение, тоже живы
Во втором проходе все инструкции, не помеченные как живые, удаляются
После удаления мертвого кода идет переход к проверкам. “Проверка” (Check) - это инструкция, которая проверяет некоторое условие и при его нарушении либо бросает исключение, либо инициирует деоптимизацию. В отличие от обычных инструкций, проверки часто вставляются компилятором автоматически.
Типичные примеры:
Пример:
NullCheck(a)
a.x = 0
Если a == nullptr, выполнение не может продолжаться
С точки зрения оптимизации все проверки делятся на несколько категорий.
Рассмотрим полностью избыточные проверки.
Если одна проверка доминирует над другим таким же, второй не нужен:
NullCheck(a)
a.x = 0
NullCheck(a)
a.y = 1
Второй NullCheck(a) избыточен, потому что первый гарантирует, что a не равен null.
Другой случай - когда логика программы уже гарантирует условие:
if (a != nullptr) {
NullCheck(a)
a.x = 0
}
Здесь NullCheck можно удалить полностью
Интуитивно кажется, что проверки всегда можно вынести из циклов, но это не так. Рассмотрим пример:
for (int i = 0; i < 10; ++i) {
print("hello");
NullCheck(a);
a.x = 0;
}
Если вынести NullCheck(a) перед циклом, изменится поведение программы: раньше print мог выполниться несколько раз до падения, теперь не выполнится ни разу. Поэтому при оптимизации проверки всегда нужно учитывать побочные эффекты
Частично избыточные проверки чаще всего возникают в циклах, особенно при проверке границ массива:
for (int i = X; i < Y; ++i) {
BoundsCheck(i, len);
a[i] = 0;
}
Формально проверка нужна на каждой итерации, но если мы знаем, что i изменяется линейно, можно проверить диапазон один раз до цикла.
Один из подходов - использовать деоптимизацию:
DeoptimizeIf(X < 0);
DeoptimizeIf(Y > len);
for (int i = X; i < Y; ++i) {
a[i] = 0;
}
Теперь в оптимизированном коде нет проверок внутри цикла, но если предположение неверно, выполнение откатится в интерпретатор
Для таких оптимизаций компилятор сначала выполняет анализ границ (BoundsAnalysis), затем проходит по всем проверкам в порядке RPO, удаляет доминируемые проверки и собирает информацию о частично избыточных проверок
Для циклов с известным числом итераций компилятор может сгруппировать проверки по массиву и индексу и вычислить минимальные и максимальные возможные значения
Если цикл неконтролируемый, оптимизация все равно возможна, но только если это дает выигрыш - например, когда несколько проверок можно заменить парой DeoptimizeIf
Важно, что некоторые проверки должны приводить именно к исключению, а не просто к деоптимизации. В таких случаях компилятор заменяет инструкцию на deoptimize, но при этом перестраивает граф управления так, чтобы корректно восстановить все кадры, включая встроенные методы
После обсуждения оптимизаций рассмотрим то, как компилятор и среда исполнения работают вместе
В виртуальной машине методы могут выполняться:
Метод обычно сначала интерпретируется, затем, если он становится “горячим”, компилируется JIT-компилятором. При этом компилированный код может быть более агрессивно оптимизирован, но содержит проверки и точки деоптимизации
Интерпретатор и компилированный код используют разные соглашения о вызовах, поэтому между ними существуют специальные мосты:
Эти мосты написаны на ассемблере и отвечают за:
Чтобы не проверять каждый раз, скомпилирован ли метод, каждый метод хранит указатель compiled_entry_point_. По умолчанию он указывает на C2I-мост. После компиляции туда записывается адрес скомпилированного кода. Компилированный код всегда вызывает этот указатель, не зная, что именно за ним стоит
Наконец, центральным механизмом, связывающим оптимизации и среду исполнения, является деоптимизация. Деоптимизация - это контролируемый возврат выполнения из оптимизированного кода в интерпретатор, когда предположения компилятора оказываются неверными
Во время деоптимизации:
Это позволяет компилятору быть агрессивным в оптимизациях, не жертвуя корректностью программы