Практикум «Оптимизирующие компиляторы» (на примере GCC) (1157417), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Оператор степени k имеет вид Si(I1,I2,…,Ik), где Ij,Lj≤Ij≤Uj, – индексная переменная j-го цикла, Lj и Uj – нижняя и верхняяграницы изменения индексной переменной. Индексированный операторSi(I1,I2,…,Ik) имеет∏kj =1N j , где Nj = Uj – Lj + 1, разных экземпляров(исполнения) по одному для каждого значения Ij, j=1,…,k. Первый ипоследний экземпляры оператора степени k имеют вид Si(L1,L2,…,Lk) иSi(U1,U2,…,Uk).Порядок исполнения между двумя операторами Si и Sj определяетсяследующим образом:скалярныйоператорSiисполняетсяраньшескалярного Sj (обозначается Si p Sj), если оператор Si лексическипредшествует Sj (i<j). Для индексированных операторов степени k имеетместо:если Si и Sj не имеют общих индексов, то Si p Sj, если i≤j;Практикум «оптимизирующие компиляторы»если у них одни и те же индексы, то (обозначая как Si(i1,…,ik) конкретныйэкземпляр оператора Si при I1=i1,…,Ik=ik: Si(i1,…,ik) p Sj(j1,…,jk) если i≤j исуществует такое m (0≤m≤k), что il=jl для l=1,…,m и im+1<jm+1.

Если жеi<j, всё остаётся аналогично, но с условием m<k;если Si и Sj имеют m<k общих индексов и il=jl (l=1,…,m), то Si p Sj толькотогда, когда i≤j.Определим также множества IN(S) и OUT(S) входных и выходныхпеременных оператора Si соответственно. Определим через OUT(Si(i1,…,ik))множествоэкземпляровопределяющихсяпеременных(необязательноразных),экземпляром Si(i1,…,ik) оператора Si. Аналогично,определим через IN(Si(i1,…,ik)) множество экземпляров переменных,которые используются тем же экземпляром оператора.

Считаем, чтооператор Siпростой (содержит не более одного присваивания)если||OUT(Si)||≤1.Два оператора Si(I1,I2,…,Ik) и Sj(J1,J2,…,Jk) будут в потоковой зависимости Siδ Sj, только если существуют значения индексов (i1,i2,…,ik) и (j1,j2,…,jk)такие, что справедливы два условия:1)Si(i1,i2,…,ik)pSj(j1,j2,…,jk);2)OUT(Si(i1,i2,…,ik))∩ IN(Sj(j1,j2,…,jk))≠ ∅.Антизависимость от Si к Sj (обозначается SiδaSj) определяется аналогичнопотоковой, но условие (2) имеет вид IN(Si(i1,i2,…,ik))∩OUT(Sj(j1,j2,…,jk))≠∅.Выходная зависимость от Si к Sj (обозначается Siδ°Sj) определяетсяаналогичнопотоковой,сусловием(2):OUT(Si(i1,i2,…,ik))∩ OUT(Sj(j1,j2,…,jk))≠ ∅.Граф зависимостей по управлению формируется следующим образом.Каждая вершина, которая может определять последующее исполнениеПрактикум «оптимизирующие компиляторы»операторов проверкой логического условия (вершина-распознаватель),имеет не более двух дуг к подчинённым вершинам (т.е.

куда передаётсяпоток управления). Этим дугам сопоставлены атрибуты T («истина») и F(«ложь») – фактически – куда переходить по результатам проверкиусловия.Вершина v постдоминируется вершиной w (w≠ v) в графе программы (иливершина w – обязательный наследник v), если каждый путь из v в tсодержит в себе w (начальная вершина пути исключается – вершина непостдоминирует сама себя).Вершина y зависит по управлению от x, если:1)существует путь P из x в y, в котором любая вершина x (заисключением x и y) постдоминируется вершиной y;2)вершина x не постдоминируется вершиной y.Граф зависимостей по данным и граф зависимостей по управлению вместесоставляют граф программных зависимостей (или управляющий графпрограммы).Практикум «оптимизирующие компиляторы»Примеры оптимизацииПродвижение константЦель оптимизации: Уменьшение избыточных вычислений.Пути достижения: Продвижение константных значений вниз по коду.Обращение к переменной заменяется её константным значением.Оригинальный кодПосле продвижения константint i,n,c;int i;int a[64];int a[64];n = 64;for( i = 0; i < 64; i++ )c = 3;a[i] = a[i] + 3;for( i = 0; i < n; i++ )a[i] = a[i] + c;Свертка константЦель оптимизации: Уменьшение избыточных вычислений.Путидостижения:Вычислениеконстантныхзначенийнаэтапекомпиляции.Оригинальный кодПосле свертки константint i;int i;i = 3*2+1;i = 7;Распространение копийЦельоптимизации:Уменьшениечислаизбыточныхпеременныхсодержащих одно и то же значение.Пути достижения: Использование оригинала вместо копий значения.Оригинальный кодint a[15];После распространения копийint a[15];Практикум «оптимизирующие компиляторы»int t = i * 4;int t = i*4;int s = t;int c = 3;int c = 3;cout << a[t];cout << a[s];a[t] = a[t] + c;int r;r = t;a[r] = a[r] + c;Подстановка операторовЦель оптимизации: Изменение зависимостей между переменными илиулучшение возможностей анализа индексов в циклах.Пути достижения: Использование переменной заменяется выражением.Оригинальный кодint np1 = n + 1;for( i = 0; i < n; i++ )После подстановки операторовfor( i = 0; i < n; i++ )a[n+1] = a[n+1] + a[i];a[np1] = a[np1] + a[i];Прямое преобразованиеЦель оптимизации: Снижение стоимости выполнения операций.Пути достижения: Замена операций эквивалентными с меньшейстоимостью исполнения.Оригинальный кодПосле прямого преобразованияint x;int x,y;double y;double y;y = y * 2;y = y + y;x = x * 4;x = x << 2;x = x / 2;x = x >> 1;Удаление неиспользуемого кодаЦель оптимизации: Сокращение объема программы за счет удалениянеиспользуемого кода.Практикум «оптимизирующие компиляторы»Пути достижения: Неиспользуемые блоки могут быть обнаружены послеиспользования продвижения констант, анализа неиспользуемых констант.Оригинальный кодint x = 0;После продвижения констант, сверткиконстантных выражений и удалениянеиспользуемого кодаfunction3();if( 0 > 1 ) {function1();}while( x > 0 ) {function2();}function3();Упрощение булевых выражений в серию переходовЦель оптимизации: Сокращение вычислений.Пути достижения: Значение некоторых булевых выражений может бытьопределено по первому операнду.Примечание: Подобная интерпретация условного выражения должнабыть либо стандартизована в языке (например C/C++), либо выполнятся вслучае, когда второе и последующие условия не изменяют переменных ине вызывают функций.

В случае если это было предусмотрено языком, тодля компилятора подобная интерпретация является обязательной. Напримере ниже смысл преобразования показан «логически».Оригинальный кодПосле упрощенияint x,y,c;int x,y,c;if( x == 1 && y == 2 )if( x == 1 )c = 5;if( y == 2 )c = 5;Практикум «оптимизирующие компиляторы»Снижение мощности выражений с индексной переменнойЦель оптимизации: Уменьшение вычисленной сложности некоторыхвыражений с индексной переменной.Пути достижения: Замена “сложных” операций “простыми”. Например,замена операций умножения сложением, особенно важно для архитектур, вкоторых операция умножения выполняется дольше операции сложения.Исходный текстint n = 64;int a [64];void foo (void) {for (int i = 0; i < n; i++)a [i] = i * 7 ;}Оригинальный кодfoo:Код после снижения мощностиfoo:pushl%ebppushl%ebpmovl%esp, %ebpmovl%esp, %ebpsubl$4, %espsubl$4, %espmovl$0, -4(%ebp)movl$0, -4(%ebp).L2:.L2:movl-4(%ebp), %eaxmovl-4(%ebp), %eaxcmpln, %eaxcmpln, %eaxjge.L1jge.L1movl-4(%ebp), %eaxmovl-4(%ebp), %ecxmovl-4(%ebp), %ecxmovl-4(%ebp), %edximull$7, %eaxmovl%edx, %eaxmovl%eax, a(,%ecx,4)sall$3, %eaxleal-4(%ebp), %eaxsubl%edx, %eaxincl(%eax)movl%eax, a(,%ecx,4)jmp.L2leal-4(%ebp), %eaxincl(%eax)jmp.L2.L1:leaveret.L1:Практикум «оптимизирующие компиляторы»leaveretУдаление индексной переменнойЦель оптимизации: Уменьшение числа операций в теле цикла;освобождение регистра, использующегося для хранения индекснойпеременной.Пути достижения: Замена условия выхода из циклаИсходный текстint n = 64;int a[64];void foo (void) {for (int i = 0; i < n; i++) {a[i] = a[i] + 3;}}Оригинальный кодfoo:Код после удаления индексной переменнойfoo:pushlmovl%ebp%esp, %ebpmovl$4, %ecxmovln, %eaxsubl$4, %espmull%ecxmovl$0, -4(%ebp)leala, %ecxaddl%ecx, %eax.L2:movl-4(%ebp), %eaxmovl$4, %ecxcmpl%eax, %ecxmull%ecxjge.L1movl%eax, %ebxaddl$3, (%ecx)movl-4(%ebp), %eaxaddl$4, %ecxcmpln, %eaxjmp.L2jge.L1movla(%ebx), %eaxleaveaddl$3, %eaxretmovl%eax, a(%ebx).L2:.L1:Практикум «оптимизирующие компиляторы»leal -4(%ebp), %eaxincl(%eax)jmp.L2.L1:leaveretРаскрутка цикловЦель оптимизации: Увеличение параллелизма инструкций (увеличениеколичества инструкций, которые потенциально могут выполнятьсяпараллельно), “улучшение” использования регистров и кэша данных.Пути достижения: Повторение тела цикла несколько раз.Оригинальный кодПосле раскрутки циклаfor (i = 1; i < n-1; i++)for (i = 1; i < n-2; i+=2) {a[i]=(a[i-1]+a[i+1])/2;a[i]=(a[i-1]+a[i+1])/2;a[i+1]=(a[i]+a[i+2])/2;}if ((n–2) % 2 == 1)a[n-2] =(a[n-3]+a[n-1])/2;Программная конвейеризацияЦель оптимизации: Увеличение параллелизма инструкций – используетсявнесуперскалярныхпроцессорах,суперскалярныепроцессорысамостоятельно конвейеризируют цикл с помощью информации опредсказании переходов.Пути достижения: Выполнение операций одной итерации цикларазбивается на несколько этапов.

Итерации выполняются следующимобразом: на i-ой итерации выполняется 1 этап i-ой итерации, 2 этап (i-1)-ойитерации и т.д. Часто это преобразование используется совместно сраскруткой цикла.Практикум «оптимизирующие компиляторы»Исходный текстint n = 16;int p [16];void foo (void) {int s = 0;for (int i = 0; i < 16; i++)s+=abs(((p[i]-p[i-1])+1)<<1);}Запишем тело этого цикла на псевдоассемблере:1: R1 = Mem (++i)2: R2 = R0 – R13: R3 = ++R24: R4 = R3 << 15: R5 = abs (R4)6: R6 = R6 + R57: R0 = R1Пусть каждая строка-инструкция выполняется один такт, ограничений надлину команды и количество регистров нет; R0 содержит значение p[0], R6– значение s.Нижеприведенатаблицаинструкций,которыеполучаютсяприпрограммной конвейеризации.

Характеристики

Список файлов книги