МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ МОСКОВСКИЙ ФИЗИКО - ТЕХНИЧЕСКИЙ ИНСТИТУТ (государственный университет) Решение задачи восстановления профильной информации по неполным исходным данным в динамическом двоичном компиляторе. Магистерская диссертация студента 112 группы ФРТК Загребина Андрея Александровича Научный руководитель: старший научный сотрудник Гимпельсон Вадим Дмитриевич Москва, 2007

Цели работы и её применение. Исследование роли профильной информации (ПИ) в двоичной оптимизирующей трансляции. Разработка и реализация алгоритмов Использование готовых алгоритмов По результатам анализа: Некорректная ПИ Наилучшая возможная ПИ для оптимизации Проделанный анализ: Исследование проблем, связанных с ПИ. Корректность ПИ и её поддержание.

С = 10 C = 350 Счётчики узлов графа управления Счётчики дуг графа управления Вероятности дуг графа управления Профильная информация. C = 3 С = 10 C = 10 С = 7 P = 0.7 С = 3 P = 0.3 С = 10 P = 1 С = 7 P = 0.02 С = 343 P = 0.98 С = 3 P = 1 Двоичный оптимизирующий компилятор Граф управления Характеризует число исполнения кода. Применяется в качестве эвристик оптимизаций.

Intel x86 код Профильный Граф (ПГ) Двоичный оптимизирующий компилятор Выделение региона. Формирование профильной информации. Наборщик регионов Построение Узел с С пороговым Регион..... oper 1 oper 2 branch..... oper 3 oper oper 1 oper 2 branch oper 3 oper 4 oper 1 oper 2 branch oper 3 oper 4 C = 0 C ++ C = 1 C порога Узел региона Инкрементация при интерпретации Узел региона Узел региона Узел региона

Корректность профильной информации 1. С узла = Σ С входной дуги 2. Σ P выходной дуги = 1 3. С дуги = С узла предшественника × P дуги Формальная корректность где С – счётчик, Р – вероятность. Дополнительное требование: 4. Счётчики должны быть наиболее близки к их оригинальным значениям (насколько это возможно) C узла P дуги С дуги P дуги

После оптимизаций из-за удаления дуг c P 0 Возникновение некорректности. При изъятии ПИ из ПГ для узлов на границах другого региона Из-за прерываний N + 1 N произошло прерывание P=0,1 90 P=0 P=1 P=0,9 P= Регион Регион Регион исполнение не продолжается Вход 7 5 Профильный граф: Граф управления:

Метод классического восстановление ПИ. Пропогация профиля Старт 10 Узел 1 N1 P=0.7 Узел 2 N2 P=0.3 Стоп N3 P=0.1 P=1 N1 = 0.7 * * N1, N2 = 0.3 * 10, N3 = 0.1 * N1 + 1 * N2. Предусловия Корректность CFG Σ P выходной дуги = 1 Однозначность и разрешимость системы уравнений P=0.9 Старт 10 Узел 1 70 P=0.7 Узел 2 3 P=0.3 Стоп 10 P=0.1 С = 7 P=1 P=0.9 С = 63 Граф управления:

10 N P=1 P=0 0 N P=1 P=0 N = 10 + N 0 = 10 !!! N = 0 + N 0 = 0 !!! обнуление Неразрешимость Неоднозначность P=1 Оптимизации не будут применяться Корректор профиля Задача коррекции – преобразовать ПИ так, чтобы после неё и пропогации обеспечить формальную корректность ПИ и по возможности пункт 4. Система уравнений Случаи неприменимости классической пропогации. До пропогации после набора региона После пропогации P=1 P=0.1 P= P=1 P=0.9 P=0.1 Имеет смысл применить оптимизации Оптимизации не будут применяться Обнуление счётчиков

Коррекция входного счётчика цикла Для самых внешних циклов Для вложенных циклов Вход в регион Старт Другой цикл Вероятные пути от входов в регион Вход во внешний цикл Другой вложенный цикл Вероятные пути от входов во внешний цикл Узлы вне циклов Тело самого внешнего цикла Тело внешнего цикла Тело вложенного цикла Выход из внешнего цикла С 0С = 0

Методы коррекции для решения проблем с системой уравнений при пропогации Метод выкалывания узла во время пропогации 10 N P=1 P=0 N = 10 + N N = = = 110 !!! Недостаток: не полная корректность ПИ после пропогации в отличии от метода малого возмущения ПИ Метод малого возмущения профильной информации 10 N P=1 P=0 P= P=1 P= Выход из региона Недостаток: Неоптимальное выполнение требования 4 Корректности ПИ Выход из региона

Коррекция выходных из цикла дуг Этап 1 Поиск дуг для коррекции. P = 0, C узла-предшественника 0 Этап 2 Непосредственная коррекция. Коррекция одной дуги: С входной в цикл < C предшественника дуги P дуги = 0 P дуги = C входной в цикл C узла предшественника дуги Коррекция всех дуг: С входной в цикл < ΣC предшественника дуги P дуги = 0 P дуги = C входной в цикл Σ C узла предшественника дуги Этап 3 Метод малого возмущения Вход 1 в цикл P=0 Выход 2 из цикла Тело цикла С 0 С входной в цикл 0

Уменьшение времени работы результирующего кода после применения пропогации и коррекции профиля по сравнению с применением пропогации, c методом выкалывание узла. На пакете тестов SPEC 95 6 % на тесте 129.compress и 2 % на тесте 102.swim 3-й регион теста compress и 3-й регион теста swim Обнуление счётчиков после пропогации из-за нулевых счётчиков входов в регион после набора 4й регион теста compress Уменьшение порядка счётчиков в цикла на несколько порядков после пропогации из-за отсутствия вероятного выхода из цикла после набора региона

На пакете тестов SPEC 2000 G среднее = 1,12 Уменьшение времени работы результирующего кода после применения пропогации и коррекции профиля по сравнению с применением пропогации, с методом выкалывание узла.

Спасибо за внимание.