Теория компиляторов-1. Л.61 Классическая теория компиляторов Лекция 6. - презентация

1 Теория компиляторов-1. Л.61 Классическая теория компиляторов Лекция 6

2 Теория компиляторов-1. Л.62 ОБ ОПЕРАТОРАХ И ВЫРАЖЕНИЯХ Базовые синтаксические категории: программа оператор выражение Например, в языке Си выражения считаются операторами void main(void) { int a, b; 3-4*b; 1+2; for(2+a;1;) b+1; } Что такое пустой оператор? Как сделать так, чтоб была возможность ставить или не ставить разделитель операторов (;) перед закрывающей операторной скобкой?

3 Теория компиляторов-1. Л.63 ОПТИМИЗАЦИЯ ПРОГРАММ Оптимизации подлежат: время выполнения; емкостные ресурсы (память). МЗО связана с типом генерируемых команд и включается в фазу генерации кода (т.е. оптимизации подлежат машинные коды). МЗО напрямую зависит от архитектуры вычислительной машины. МНЗО – отдельная фаза компилятора, предшествующая генерации кода. Она включается на этапе генерации промежуточного кода – внутренней формы представления программы.

4 Теория компиляторов-1. Л.64 Исключение общих подвыражений Оптимизация линейных участков Процедура, позволяющая не рассчитывать одно и то же выражение несколько раз, исключая общие подвыражения: представить выражение в форме, пригодной для обнаружения общих подвыражений; определить эквивалентность двух и более подвыражений; исключить повторяющиеся; изменить команды так, чтобы учесть это исключение. Пример: A = c*d*(d*c+b) * c d T1 * d c T2 + T2 b T3 * T1 T3 T4 = A T4 1. Упорядочим операнды: 1)* c d T1 2)* c d T2 3)+ T2 b T3 4)* T1 T3 T4 5)= A T4 2. Определим границы операторов и найдем общие подвыражения (это (1) и (2)) и затем исключим подвыражение (2). После чего заменим далее везде T2 на T1: * c d T1 + T1 b T3 * T1 T3 T4 = A T4 Опасности: побочные эффекты, затраты на поиск и анализ

5 Теория компиляторов-1. Л.65 Примеры Пример: if( a[y*3] 10) a[y*3] = 0; Выражения "y*3" и "a[y*3]" являются общими подвыражениями. T1 = y*3; A1 = &a[T1]; A2 = &b[T1]; if( *A1 10) *A1 = 0; Пример: if(a == 0) a = y * 3; else b = y * 3; приводит к логическому эквиваленту: T1 = y * 3; if(a == 0) a = T1; else b = T1;

6 Теория компиляторов-1. Л.66 Вычисления на этапе компиляции Если в программе есть участки, в которых присутствуют подвыражения, состоящие из констант, то эти подвыражения можно просчитать на этапе компиляции. Метод "свертки констант" (константная арифметика) Например: A := 1.5 * 2/3; => A := 1; Но: A := 3*b/4/d*2 ? #define TWO 2 a = 1 + TWO; => a = 3; "Алгебраические упрощения" (вид свертки констант, который удаляет арифметические тождества) x := y + 0;=> x := y; x := y * 0;=> x := 0; x := y / 1.0; => x := y; x := y / 0; => x :???; A := 1; Но: A := 3*b/4/d*2 ? #define TWO 2 a = 1 + TWO; => a = 3; "Алгебраические упрощения" (вид свертки констант, который удаляет арифметические тождества) x := y + 0;=> x := y; x := y * 0;=> x := 0; x := y / 1.0; => x := y; x := y / 0; => x :???;">

7 Теория компиляторов-1. Л.67 Размножение констант Любая ссылка на константное значение замещается самим значением: x = 2; if( a < x && b < x) c = x; => x = 2; if(a < 2 && b < 2) c = 2;

8 Теория компиляторов-1. Л.68 Оптимизация булевых выражений Использование свойств булевых выражений. Например, вместо if (a and b and c) then endif надо сгенерировать команды таким образом, чтобы исключались лишние проверки: if not a then goto Label if not b then goto Label if not c then goto Label Label://метка перехода Проблемы: могут проявиться побочные эффекты в тех случаях, когда аргументами являются функции "оптимизированный" код может получиться более громоздким по сравнению с оригиналом.

9 Теория компиляторов-1. Л.69 Оптимизация циклов Вынесение инвариантов за пределы цикла Причины, которые могут привести к уменьшению скорости работы программы в циклах Итерации цикла зависимы и не могут исполняться параллельно. Тело цикла большое и требуется слишком много регистров. Тело цикла или количество итераций мало и выгоднее совсем отказаться от использования цикла. Цикл содержит вызовы функций и процедур из сторонних библиотек. Цикл интенсивно использует какое-то одно исполняющее устройство процессора. В цикле имеются условные переходы.

10 Теория компиляторов-1. Л.610 Вынесение инвариантных вычислений за пределы цикла Один из наиболее эффективных методов оптимизации, дающий весьма ощутимые результаты. Для реализации метода необходимо: распознать инвариант; определить место переноса; перенести инвариант. Неудобства метода: отследить инвариант нелегко, т.к. аргументы могут косвенно зависеть от переменной цикла; не учитываются побочные эффекты, если аргументы инварианта являются функциями (или зависимыми от них).

11 Теория компиляторов-1. Л.611 Оптимизация циклов Развертка циклов Такая оптимизация выполняется, когда тело цикла мало. Необходимо более эффективно использовать исполняющие устройства на каждой итерации. Поэтому многократно дублируют тело цикла в зависимости от количества исполняющих устройств. Такая оптимизация может вызвать зависимость по данным. Чтобы избавиться от нее, вводятся дополнительные переменные.

12 Теория компиляторов-1. Л.612 Подсчет единиц // Медленная, но простая процедура // подсчета единиц R00 = R11; for(i=0;i>4); r1=((R11&Mask)>>4); Mask=0b ; R00 &= Mask; R11 &= Mask; R00 += r0; R11 += r1; // Быстрая, но сложная процедура подсчета единиц Mask=0b ; r0=((R00&Mask)>>1); r1=((R11&Mask)>>1); Mask=0b ; R00 &= Mask; R11 &= Mask; R00 += r0; R11 += r1;

13 Теория компиляторов-1. Л.613 Развертка циклов Такая оптимизация выполняется, когда тело цикла мало. Многократно дублируют тело цикла в зависимости от количества исполняющих устройств Такая оптимизация может вызвать зависимость по данным => вводятся дополнительные переменные.

14 Теория компиляторов-1. Л.614 Объединение циклов В цикле могут быть долго выполняющиеся инструкции (например, извлечение корней, логарифмы...). Или есть несколько циклов, которые выполняются по одинаковому интервалу индексов. Целесообразно объединить циклы для более сбалансированной нагрузки исполняющих устройств.

15 Теория компиляторов-1. Л.615 Дополнительно Что эффективнее: ++x или x++? Для пользовательских типов ++x лучше, т.к. постинкремент сопровождается созданием копии объекта, хранящего старое состояние, и возвратом его по значению. for(i=0;i2

16 Теория компиляторов-1. Л.616 Проблемы, связанные с оптимизацией Необходимо сопоставлять ожидаемый выигрыш с дополнительными накладными расходами Возможное ухудшение кода, сложность трассировки оптимизированных программ. Сложность выявления возникающих "побочных" эффектов. Например A := pop(); B := pop(); C := A || B; push(C); "Компактный" вариант push(pop() || pop()), Может быть некорректно оптимизирован в push(pop(), т.к. A || A A).

17 Теория компиляторов-1. Л.617 Выводы Необходимо сопоставлять затраты на оптимизацию с ожидаемым эффектом. Оптимизация не всегда приводит к улучшению кода – могут появиться побочные эффекты. Либо после оптимизации получается более громоздкий код. Чем больше вычислительной работы перекладывается на этап компиляции, тем эффективнее будет выполняться программа. Более предпочтительной для МНЗО является внутренняя форма представления программы в виде тетрад. Лучший метод оптимизации – писать хорошие (грамотные) программы.