Программный разрыв зависимостей между операциями обращения в память в двоичном оптимизирующем компиляторе Магистерская диссертация студента 212 группы ФРТК Волкова Павла Москва 2008

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

Суть проблемы Статически нераспознаваемые зависимости между операциями обращения в память ограничивают возможности компилятора в применении оптимизаций над кодом Статически нераспознаваемые зависимости между операциями обращения в память ограничивают возможности компилятора в применении оптимизаций над кодом mov G1 -> V1 mov G2 -> V2 … store V1 1 load V2 -> V4 add V4 1 -> V4 mov G1 -> V1 mov G2 -> V2 load V2 -> V4 … store V1 1 add V4 1 -> V4

Динамическое развязывание адресов памяти mov G1 -> V1 mov G2 -> V2 … store V1 1 load V2 -> V4 add V4 1 -> V4 load V2 -> V4 … store V1 1 add V4 1 -> V4 mov G1 -> V1 mov G2 -> V2 If V1 != V2 … store V1 1 load V2 -> V4 add V4 1 -> V4 y n

Ранее реализованный алгоритм динамического развязывания адресов памяти Распознавание адресов операций обращения в память и законы их изменения (только индуктивные с постоянным шагом и инвариантные адреса) Распознавание адресов операций обращения в память и законы их изменения (только индуктивные с постоянным шагом и инвариантные адреса) Объединение в диапазоны одноименных операций работы с памятью со смежными адресами Объединение в диапазоны одноименных операций работы с памятью со смежными адресами Построение развязывающих выражений Построение развязывающих выражений 1.Поиск самых вложенных циклов 2.Для каждого из них:

Недостатки алгоритма Неоптимальная частота перехода на цикл с развязанными операциями из-за построения грубых динамических проверок Анализ причин: 1. Не учитывается внутренняя структура цикла при построении развязывающих выражений 2. Избыточное развязывание

Отображение виртуального адресного пространства на физическую память 4096 … MMU Виртуальные адреса Физическая память

Построение проверок в прежнем алгоритме dist = N*шаг индукции= 2*4 = 8 с1 = a1 + 3/2 c2 = a2 + 3/2 c_dist = f(c1,c2) = min( c1-c2, c2-c1) mod 4096 c_dist >= dist + 4/2 + 4/2 = 12 f(a1,a2) = f(c1,c2) = c_dist >= 12 d = (a1-a2) mod 4096 d = [12, 4084] a1 a1+3 a2a2+3 dist с1 с d 4084

Предложенный алгоритм построения проверок Для каждой пары диапазонов [a1, a1+s1] и [a2, a2+s2]: Для каждой пары диапазонов [a1, a1+s1] и [a2, a2+s2]: Построение развязывающих выражений Построение развязывающих выражений Для всех пар операций load(a1+d1) и store(a2+d2): Для всех пар операций load(a1+d1) и store(a2+d2): Пересечение получившихся решений Пересечение получившихся решений Построение уравнения развязывания операций на N итераций: Построение уравнения развязывания операций на N итераций: если операция чтения выше записи, то если операция чтения выше записи, то [a1 + d1, a1 + d1 + ld_size -1] [a2 + d2 - N*h, [a1 + d1, a1 + d1 + ld_size -1] [a2 + d2 - N*h, a2 + d2 – h + st_size -1] = 0 в противном случае: в противном случае: [a1 + d1, a1 + d1 + ld_size -1] [a2 + d2 - N*h, [a1 + d1, a1 + d1 + ld_size -1] [a2 + d2 - N*h, a2 + d2 + st_size -1] = 0 Замена переменных: d = (a1-a2) mod 4096 Замена переменных: d = (a1-a2) mod 4096 Определение решения для d Определение решения для d

Пример построения развязывающих выражений в предложенном алгоритме [a1, a1+3] [a2-8, a2-1] mod 4096=0 d = (a1 – a2) mod 4096 [d, d+3] [-8, -1] = 0 d

Сравнение старой и новой схем на тестовых задачах Spec95 Spec2000

Результаты работы Реализован новый алгоритм динамического развязывания операций обращения в память. Его отличия: Реализован новый алгоритм динамического развязывания операций обращения в память. Его отличия: построение условий, увеличивающих частоту переходов на оптимизированный цикл построение условий, увеличивающих частоту переходов на оптимизированный цикл уменьшение числа операций, необходимых для построения развязывающих выражений уменьшение числа операций, необходимых для построения развязывающих выражений Улучшение времени исполнения на задачах Spec95/2000 Улучшение времени исполнения на задачах Spec95/2000 Реализованный алгоритм войдет в следующую версию двоичного компилятора Реализованный алгоритм войдет в следующую версию двоичного компилятора

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