Оптимизирующая компиляция

Производительность Параллелизм на уровне операций (ILP) – параллельное исполнение команд в процессоре Параллелизм на уровне процедур (Multithreading) – параллельное исполнение потоков команд Параллелизм на уровне задач (Multitasking, Multicore ) – параллельное исполнение задач

Оптимизация программы Оптимизация цепочек вычислений – преобразование последовательности операций (локальные оптимизации) Оптимизация циклических участков – преобразование циклов (цикловые оптимизации) Оптимизация вычислений в процедуре – преобразование управления и потока данных (глобальные оптимизации) Оптимизация вычислений в программе – преобразование процедур (межпроцедурные оптимизации)

Структуры данных CFG – граф управления программы DUG – граф потока данных Loop Tree – дерево циклов Call Graph – граф вызовов Index Analysis – результаты анализа индуктивных переменных в циклах IPA – результаты межпроцедурного анализа чтений-записей в память

Локальные оптимизации Expression Balancing – балансировка арифметических выражений Применимость: 1)Наличие коммутативных арифметических выражений 2)Результаты коммутативных подвыражений используются единожды x=(((((a+b)+c)+d)+e)+f)+g)+h x=((a+b)+(c+d))+((e+f)+(g+h))

Локальные оптимизации Local Reassociation – локальные реассоциации Применимость: 1)Рассматриваются локальные выражения в циклах, к которым применимы правила (A +- k1) +- k2 = A +- (k1 +- k2), где k1,k2-const (A +- k1) +- (B +- k2) = (A +- B) +- (k1 +- k2)

Локальные оптимизации Common Subexpression Elimination – преобразование общих подвыражений i = x + y j = x + y t1 = x + y i = t1 + 1 j = t1

Локальные оптимизации Dead Code Elimination – удаление неиспользуемых вычислений int i = 0;... i = 2; Алгоритм разметки DUG: 1)Изначально все операции считаются «мёртвыми» 2)По узлам DUG совершается пропагация вверх «живых» операций

Локальные оптимизации Constant Substitution (Propagation) – подстановка константных значенийx = 3; y = 7; y = x + 4;y = 7; Peephole – подстановка тождественных равенств a + 0 = aa * 1 = a a * 0 = 0a * 2 = a

Локальные оптимизации Redundant Load Elimination – удаление избыточных чтений из памяти Применимость: 1)Операции LOAD/STORE доминируют над операцией LOAD 2)Между операциями нет операций с побочным эффектомa[i] = v;… b[i] = v; b = a[i];b[i] = v;

Локальные оптимизации Redundant Store Elimination – удаление избыточных записей в память Применимость: 1)Имеется несколько операций STORE в одну и ту же область памяти, одна из которых доминирует над другой 2)Между операциями нет операций чтения из этого участка памяти и операций с побочным эффектом ; a[i] = f;;…a[i] = g;

Локальные оптимизации Memory Access Widening – оптимизация запросов в память char a[1000];... j = a[i] + a[i+1] short t[500] R0 = Load (short) a[i] j = R0[hi] + R0[lo]

Локальные оптимизации Objects Renaming (Reduce Virtual Registers Pressure) – переименование объектов Применимость: 1)Рассматриваются каждая связанная компонента DUGa = 1;a = a + a; a = 2;a1 = 2; a = a * a;a1 = a1 * a1;