Рассмотрим, как компилятор оптимизирует код, который кажется корректным с точки зрения семантики, но избыточен с точки зрения выполнения, и как эти оптимизации тесно связаны с работой виртуальной машины и деоптимизацией
Удаление мертвого кода (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-мост. После компиляции туда записывается адрес скомпилированного кода. Компилированный код всегда вызывает этот указатель, не зная, что именно за ним стоит
Наконец, центральным механизмом, связывающим оптимизации и среду исполнения, является деоптимизация. Деоптимизация - это контролируемый возврат выполнения из оптимизированного кода в интерпретатор, когда предположения компилятора оказываются неверными
Во время деоптимизации:
Это позволяет компилятору быть агрессивным в оптимизациях, не жертвуя корректностью программы