'

Оптимизация управляющего графа программ, имеющих избыточные условные вычисления

Понравилась презентация – покажи это...





Слайд 0

Оптимизация управляющего графа программ, имеющих избыточные условные вычисления Выполнил: Степнов Денис, 816 гр. Научный руководитель: Бучнев А.Ю. Выпускная квалификационная работа


Слайд 1

Общие понятия Нумерация значений – разбиение множества операций промежуточного представления на классы конгруэнтности (эквивалентности); Класс конгруэнтности – подмножество операций, безусловно имеющих одинаковый результат; Гиперблок – непрерывная последовательность инструкций, имеющая одну точку входа; CTP – операция подготовки передачи управления; Станок – регистр, необходимый для выполнения операции CTP.


Слайд 2

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


Слайд 3

Постановка задачи Реализовать отдельную оптимизацию, устраняющую избыточные вычисления предикатов Внедрить оптимизацию в оптимизирующий компилятор «Эльбрус» Определить место в линейке оптимизаций Провести верификацию на стандартных пакетах тестов Поддержка оптимизации Провести оценку эффективности на пакете SPEC


Слайд 4

Подход к решению задачи Поиск избыточных условных вычислений Используя результаты анализа «Нумерация значений», выявить избыточные условные вычисления; Применение оптимизации Дублировать If-узел с избыточным условием по всем входящим в него дугам, по которым оно однозначно определяется, и перенаправить на копии исходящие дуги; Удалить невыполнимые исходящие дуги из полученных копий If-узла и быть может оригинала (если у него осталась одна входящая дуга по которой условие однозначно определяется), преобразовать If-узлы в Simple-узлы.


Слайд 5

Простейший пример Если в узлах 2, 3, 4 нет операций, изменяющих переменные a или b, то вычисление предиката в узле 4 является избыточным ? нужно создать копию узла 4 (узел 7) и упростить узлы 4 и 7


Слайд 6

Нет Да Нет Да 1. Поиск избыточных условных вычислений Осуществить обход по всем возможным парам If-узлов рассматриваемой процедуры Осуществить обход по всем исходящим дугам доминатора и входящим дугам доминируемого узла Один из узлов доминирует над другим Преемник исходящей дуги доминирует над предшественником входящей дуги & класс конгруэнтности операций, вырабатывающих предикат, совпадает Занести доминируемый узел, входящую дугу, значение предиката в специальный список Алгоритм


Слайд 7

В данном примере существует единственная подходящая для рассмотрения пара If-узлов: If-узел 1 доминирует If-узел 4. Осуществив обход по дугам, можно выявить две входящие в узел 4 дуги, в предшественниках которых значение предиката точно известно. Однако оптимизацию возможно применить только по одной из входящих в узел 4 дуг, так как переменная «a» переопределяется в узле 2. 1. Поиск избыточных условных вычислений Пример


Слайд 8

Осуществить обход списка, полученного анализирующим алгоритмом Нет Да В узел входит более одной дуги Удалить лишнюю исходящую дугу и вычисление предиката Дублировать узел со всеми исходящими дугами Удалить у копии лишнюю исходящую дугу и вычисление предиката Перенаправить на копию дугу, содержащуюся в списке 2. Применение оптимизации Алгоритм


Слайд 9

Создаём узел 7 — копию узла 4. При копировании узла CFG-графа средствами компилятора «Эльбрус» (функция graph_GetNodeCopy), автоматически копируются исходящие из него дуги. Входящие дуги не копируются. 2. Применение оптимизации Пример


Слайд 10

Перенаправляем входящую дугу, по которой значение предиката точно известно, на скопированный узел. 2. Применение оптимизации Пример


Слайд 11

Удаляем дугу, исходящую из узла 7, соответствующую отрицательному значению предиката. Удаляем вычисление предиката и преобразовываем узел 7 из If-узла в Simple-узел. 2. Применение оптимизации Пример


Слайд 12

Оценка эффективности Ускорение, полученное на пакете тестов spec2000, в среднем составило 0,5%


Слайд 13

Результаты исследования Оптимизация реализована и внедрена в линейку оптимизирующего компилятора «Эльбрус»: Применение на 3-м уровне оптимизации Применение перед объединением базовых блоков в гипер-узлы (оптимизация if_conversion) Проведена верификация на пакетах дневного тестирования при вливе в основную ветку компилятора, а так же на генераторе тестов Проведена оценка эффективности на пакете тестов spec2000


×

HTML:





Ссылка: