Отслеживание своевременной компиляции - Tracing just-in-time compilation

Отслеживание своевременной компиляции - это метод, используемый виртуальными машинами для оптимизации выполнения программы во время выполнения . Это делается путем записи линейной последовательности часто выполняемых операций, компиляции их в собственный машинный код и их выполнения. Это отличие от традиционных точно в срок (JIT) компиляторов, работа на основе каждого метода.

Обзор

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

Технические подробности

JIT-компилятор трассировки проходит различные фазы во время выполнения. Сначала собирается информация о профилировании петель. После определения «горячего» цикла начинается специальная фаза трассировки , на которой записываются все выполненные операции этого цикла. Эта последовательность операций называется трассировкой. Затем трассировка оптимизируется и компилируется в машинный код (трассировка). Когда этот цикл выполняется снова, вместо аналога программы вызывается скомпилированная трассировка.

Эти шаги подробно описаны ниже:

Фаза профилирования

Цель профилирования - выявить горячие петли. Часто это делается путем подсчета количества итераций для каждого цикла. После того, как счетчик цикла превышает определенный порог, цикл считается горячим, и начинается фаза трассировки.

Фаза отслеживания

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

Поскольку трассировка записывается по одному конкретному пути выполнения цикла, последующие выполнения этой трассировки могут отличаться от этого пути. Чтобы определить места, где это может произойти, в след вставляются специальные инструкции по охране . Одним из примеров такого места являются операторы if. Guard - это быстрая проверка, чтобы определить, выполняется ли исходное условие. В случае отказа защиты выполнение трассировки прерывается.

Поскольку трассировка выполняется во время выполнения, трассировка может содержать информацию времени выполнения (например, информацию о типе ). Эта информация может позже использоваться на этапе оптимизации для повышения эффективности кода.

Этап оптимизации и генерации кода

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

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

Исполнение

После компиляции трассировки в машинный код ее можно выполнять в последующих итерациях цикла. Выполнение трассировки продолжается до отказа охранника.

История

В то время как идея JIT восходит к 1960-м годам, отслеживание JIT стало чаще использоваться только в последнее время. Первое упоминание об идее, аналогичной сегодняшней идее отслеживания JIT, было в 1970 году. Было замечено, что скомпилированный код может быть получен из интерпретатора во время выполнения, просто сохраняя действия, выполняемые во время интерпретации.

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

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

В 2006 году был разработан HotpathVM, первый JIT-компилятор трассировки для языка высокого уровня. Эта виртуальная машина была способна динамически идентифицировать часто выполняемые инструкции байт-кода, которые отслеживаются, а затем компилируются в машинный код с использованием конструкции статического одиночного присваивания (SSA). Мотивация для HotpathVM заключалась в том, чтобы иметь эффективную JVM для мобильных устройств с ограниченными ресурсами.

Другой пример JIT-трассировки - TraceMonkey , одна из реализаций JavaScript в Mozilla для Firefox (2009 г.). TraceMonkey компилирует часто выполняемые трассировки циклов на динамическом языке JavaScript во время выполнения и специализирует сгенерированный код для фактических динамических типов, встречающихся на каждом пути.

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

Трассировка JIT также была исследована Microsoft в проекте SPUR для их Common Intermediate Language (CIL). SPUR - это общий трассировщик для CIL, который также можно использовать для трассировки с помощью реализации JavaScript.

Пример следа

Рассмотрим следующую программу Python, которая вычисляет сумму квадратов последовательных целых чисел, пока эта сумма не превысит 100000:

def square(x):
    return x * x

i = 0
y = 0
while True:
    y += square(i)
    if y > 100000:
        break
    i = i + 1

След для этой программы может выглядеть примерно так:

 loopstart(i1, y1)
 i2 = int_mul(i1, i1)		# x*x
 y2 = int_add(y1, i2)		# y += i*i
 b1 = int_gt(y2, 100000)
 guard_false(b1)
 i3 = int_add(i1, 1)		# i = i+1
 jump(i3, y2)

Обратите внимание, как вызов функции squareвстроен в трассировку и как оператор if превращается в guard_false.

Смотрите также

Внешние ссылки

Официальный сайт LuaJIT

Languages

In other projects