Тема 01(2015) (10) (Лекции)

1. Введение.Неоптимизирующийкомпилятор11.1 Компиляторы1.1.1. Неоптимизирующий компиляторИсходный код (поток символов)Таблица символовПередний план:Анализ исходного кодаГенерация внутреннегопредставленияВнутреннее представлениеЗадний план:Генерация кода целевоймашиныКод целевой машиныСтруктура неоптимизирующего компилятора21.1 Компиляторы1.1.2. Оптимизирующий компиляторТаблица символовИсходный кодПередний планВнутреннее представление 1Машинно-независимая оптимизацияВнутреннее представление 2Машинно-ориентированнаяоптимизацияВнутреннее представление 3Генератор кодаКод целевой машины31.2 Цель курсаЦель курса – изучение методов оптимизации программ (как машиннонезависимой, так и машинно-ориентированной и принципов конструированияоптимизирующих компиляторов.Основное учебное пособие:А. В.

Ахо, М. С. Лам, Р. Сети, Дж. Д. Ульман. Компиляторы: принципы,технологии и инструменты, 2-е издание. М.: «И.Д. Вильямс», 2008(в конце 2014 года был выпущен дополнительный тираж)В тех случаях, когда излагаемый материал в указанном учебном пособииотсутствует, используется еще два учебных пособия:Keith D. Cooper, Linda Torczon. Engineering a Compiler (Second Edition)Elsevier, Inc. 2012Steven S. Muchnick. Advanced Compiler Design and ImplementationMorgan Kaufmann Publishers199741.3 Генерация внутреннего представленияcurrent_pos=initial_pos+16*stepСтрока исходной программыАнализатор лексикиid,1=id,2+nm,3*id,4Последовательность токеновАнализатор синтаксисаТаблица символовВнутреннее имяВнешнее имяДерево разбораАтрибутыid1current_posintid2initial_posintnm316intid4stepintДерево разбораАнализатор семантикиАбстрактное синтаксическоедерево(АСД – Внутреннеепредставление 1)=id,1+id,2*nm,3id,4Генератор внутреннегопредставленияt1  *,nm3,id4t2  +,id2,t1id1  t2Внутреннее представление 251.4.

Внутреннее представление1.4.1. Определение внутреннего представления 2◊ Инструкции присваивания(х, y и z – имена (адреса) переменных или константы):х  op, y, zвыполнить бинарную операцию ор над операндами y и zи поместить результат в хх  op, yвыполнить унарную операцию ор над операндом yи поместить результат в хх  yскопировать значение переменной y в переменную хх[i]  yпоместить значение y в i-ю по отношению к х ячейкупамятих  y[i]поместить значение i-ой по отношению к y ячейки памятивх61.4. Внутреннее представление1.4.1.

Определение внутреннего представления 2 Инструкции перехода:goto LБезусловный переход:следующей будет выполнена инструкция с меткой LifTrue x goto LУсловный переход:если х истинно,следующей будет выполнена инструкция с меткой LifFalse x goto LУсловный переход:если х ложно,следующей будет выполнена инструкция с меткой LНа рисунке справа – схема трансляцииоператораif (expr) then stmt1;71.4.

Внутреннее представление1.4.1. Определение внутреннего представления 2◊ Процедуры:param хПередача фактического параметра вызываемой процедуре(если вызываемая процедура имеет n параметров, тоинструкции ее вызова предшествует n инструкций paramcall p, nВызов процедуры p, имеющей n параметровreturn yВозврат из процедурыy – необязательное возвращаемое значениеЗамечание.

Это внутреннее представление – учебное и не содержит некоторыхдеталей, важных для реализации. Соответствующее внутреннее представление2системы GCC называется Gimple.Для выполнения задания будет использоваться внутреннее представление(биткод) IR системы LLVM, которое является внутренним представлением3.Описание – на сайте …, полное описание – на сайте …81.4. Внутреннее представление1.4.2. Пример{int i, j;int v, x;if (n <= m) return;/* Начало фрагмента */i = m - 1;j = n;v = a[n];while (1) {do i = i + 1;while (a[i] < v);do j = j - 1;while (a[j] > v);if (i >= j) break;/* Обмен a[i], a[j] */x = a[i];a[i] = a[j];a[j] = x;}/* Обмен a[i], a[n] */x = a[i];a[i] = a[n];a[n] = x;/* Конец фрагмента */(1)i  -, m, 1(16)t7  *, 4, i(2)j  n(17)t8  *, 4, j(3)tl  *, 4, n(18)t9  a[t8](4)v  a[tl](19)a[t7]  t9(20)t10  *, 4, j(5)L1: i  +, i, 1(6)t2  *, 4, i(21)a[t10]  x(7)t3  a[t2](22)goto L1(8)(9)ifTrue t3<vgoto L1L2: j  -, j, 1(23)L3: t11  *, 4, i(24)x  a[t11](10)t4  *, 4, j(25)t12  *, 4, i(11)t5  a[t4](26)t13  *, 4, n(12)(27)t14  a[t13](28)a[t12]  tl4(14)ifTrue t5>vgoto L2ifTrue i>=jgoto L3t6  *, 4, i(29)t15  *, 4, n(15)x  a[t6](30)a[t15]  x(13)quicksort(a,m,j); quicksort(a,i+1,n);}91.5.

Граф потока управления1.5.1. Базовый блок (определение)Базовым блоком (или линейным участком) называетсяпоследовательность следующих друг за другом трехадресных команд,обладающая следующими свойствами:(1)поток управления может входить в базовый блок только черезего первую инструкцию, т.е.

в программе нет переходов всредину базового блока;поток управления покидает базовый блок без останова иливетвления, за исключением, возможно, в последней инструкциибазового блока.Пример базового блока – инструкции (14) – (22) из примера 1.4.2(2)(14)(15)(16)(17)(18)(19)(20)(21)(22)t6  *, 4, ix  a[t6]t7  *, 4, it8  *, 4, jt9  a[t8]a[t7]  t9t10  *, 4, ja[t10]  xgoto L1101.5.

Граф потока управления1.5.4. Алгоритм построения графа потока управления (ГПУ)◊ Вход:последовательность трехадресных инструкций.◊ Выход:список базовых блоков для данной последовательностиинструкций, такой что каждая инструкция принадлежит толькоодному базовому блоку.◊ Метод:Строится упорядоченное множество НББКаждому НББ соответствует ББ, который определяется какпоследовательность инструкций, содержащая само НББ и всеинструкции до следующего НББ (не включая его) или до концапрограммы.Строится множество дуг графа потока управления:если последняя инструкция ББ не является инструкциейперехода, строится дуга, соединяющая ББ со следующимББ;если последняя инструкция ББ является инструкциейбезусловного перехода, строится дуга, соединяющая ББ сББ, НББ которого имеет соответствующую метку;если последняя инструкция ББ является инструкциейусловного перехода, строятся обе дуги.111.5.

Граф потока управления1.5.5. ПримерПрименим алгоритм 1.5.4 для построения графа потока программы изпримера 1.4.2(1)i  -, m, 1(16)t7  *, 4, i(2)j  n(17)t8  *, 4, j(3)tl  *, 4, n(18)t9  a[t8](4)v  a[tl](19)a[t7]  t9(20)t10  *, 4, j(5)L1: i  +, i, 1НББНББ(6)t2  *, 4, i(21)a[t10]  x(7)t3  a[t2](22)goto L1(8)ifTrue t3<v goto L1(23)L3: t11  *, 4, i(24)x a[t11](9)L2: j  -, j, 1НББ(10)t4  *, 4, j(25)t12  *, 4, i(11)t5  a[t4](26)t13  *, 4, n(12)ifTrue t5>v goto L2(27)t14  a[t13](13)ifTrue i>=j goto L3 НББ(28)a[t12]  tl4(14)t6  *, 4, j(29)t15  *, 4, n(15)x  a[t6](30)a[t15]  xНББНББ121.5. Граф потока управления1.5.5.

ПримерНББ позволяют построить следующие ББ:Блок A(1)i  -, m, 1Блок E(14)Блок Ft6  *, 4, i (23) L3:t11  *, 4, i(2)j  n(15)x  a[t6](24) x  a[t11](3)tl  *, 4, n(16)t7  *, 4, i (25) t12  *, 4, i(4)v  a[tl](17)t8  *, 4, j (26) t13  *, 4, nБлок B(18)t9  a[t8](27) t14  a[t13](5) L1: i  +, i, 1(19)a[t7]  t9(28) a[t12]  tl4(6)t2  *, 4, i(20)t10 *, 4, j (29) t15  *, 4, n(7)t3  a[t2](21)a[t10]  x(8)ifTrue t3<v goto L1 (22)Блок D(13)Блок CifTrue i>=j goto L3 (9)L2: j  -, j, 1(10)t4  *, 4, j(30) a[t15]  xgoto L1(11)t5  a[t4](12)ifTrue t5>v goto L2131.5. Граф потока управления1.5.5.

Пример. Построив дуги согласно алгоритму, получим следующий ГПУ. Дляудобства анализа к ГПУ добавлены два дополнительных узла: entry (вход) и exit(выход).EntryАBCDEFExit141.6 Локальная оптимизация (оптимизация базовых блоков)1.6.1 Постановка задачи локальной оптимизацииОптимизация – это выполнение следующих преобразований:Удаление общих подвыражений (инструкций, повторновычисляющих уже вычисленные значения).Удаление мертвого кода (инструкций, вычисляющих значения,которые впоследствии не используются).Сворачивание констант.Изменение порядка инструкций, там, где это возможно,чтобы сократить время хранения временного значения на регистре.1.6.2Представление базового блока в виде ориентированногоациклического графаВсе указанные преобразования можно выполнить за один просмотр ББесли представить его в виде ориентированного ациклического графа(ОАГ).151.6 Локальная оптимизация1.6.2Представление базового блока в виде ориентированногоациклического графаПример.

Выражение в исходном коде:a = а + y*(b +(y-z)*b)+(y-z)* bt1t2t3t4t5t6t7a-,*,+,*,-,*,+,+,y, zt1, bb, t2y, t3y, zt5, bt4, t6a, t7+a+a+t7at4 ** t6y t3 +t5 -b t2 * yt1-Выражение впромежуточномпредставленииyt4 *+ t3bbzbz+ t7aАСДy* t2,t6- t1,t5zОАГ161.6 Локальная оптимизация1.6.2Представление базового блока в виде ориентированногоациклического графаПример (окончание).На ОАГ для выражения видно (в отличие от АСД):переменная b используется в двух вычисленияхвыражение y-z можно вычислить только один развыражение (y-z)* b можно вычислить только один разt1t2t3t4t5t6t7a-,*,+,*,-,*,+,+,y, zt1, bb, t2y, t3y, zt5, bt4, t6a, t7+a+ t7at4 *+ t3by* t2,t6- t1,t5zОАГ171.6 Локальная оптимизация1.6.3 Представление ОАГ в виде таблицы значенийКаждая строка таблицы значений представляет один узел ОАГ.Первое поле каждой записи представляет собой код операцииКаждой правой части операцииop, left, right,где ор – код операции, а left и right – левый и правый операнды,соответствует ее сигнатураop, #left, #right,где ор – код операции, а #left и #right – номера значенийлевого и правого операндов (у унарных операций #right равен 0).Унарные операции id и nm определяют соответственноимена переменных и константы (листовые узлы).Номер значения – это номер строки таблицы значений (ТЗ), в которойопределяется это значение181.6 Локальная оптимизацияАлгоритм (на псевдокоде) построения ОАГ для базового блока B,содержащего n инструкций вида ti  Opi, li, ri.Функция #val(s) определяет номер значения, определяемогосигнатурой s = (Op, #val(l), #val(r)) .for each "ti  Opi, li, ri" dosi = (Opi, #val(li), #val(ri))if(ТЗ содержит sj == si)thenвернуть j в качестве значения #val(si)elseзавести в ТЗ новую строку ТЗkзаписать сигнатуру si в строку ТЗkвернуть k в качестве значения #val(si)191.6 Локальная оптимизация1.6.3 Представление ОАГ в виде таблицы значенийТаблица значений рассматриваемого примера имеет вид:t15t26t37t48t55t66t79a10-,*,+,*,-,*,+,+,y3, z4t15, b2b2, t26y3, t37y3, z4t55, b2t48,t66a1, t7912345678910idididid*+*++# зна- КОПченияссылкассылкассылкассылка352381вввв# операндаТСТСТСТС426769abyzt1, t5t2, t6t3t4t7a# операндаПрисоединенныепеременныеОпределение значения(сигнатура)201.6 Локальная оптимизацияt1t2t3t4t5t6t7a-,*,+,*,-,*,+,+,y, zt1, bb, t2y, t3y, zt5, bt4, t6a, t7(a) Блок Eдо оптимизацииt15t26t37t48t55t66t79a10-,*,+,*,-,*,+,+,y3, z4t15, b2b2, t26y3, t37y3, z4t55, b2t48,t66a1, t79(c) Блок Eпосле нумерации значенийt1t2t3t4t5t6t7a-,*,+,*,t1t2+,+,y, zt1, bb, t2y, t3t4, t6a, t7(c) Блок Eпосле оптимизации211.6 Локальная оптимизация1.6.6 Удаление общих подвыраженийОбщие подвыражения обнаруживаются при построении узлов ОАГс помощью алгоритма 1.6.4 (нумерация значений).1.6.7 Сворачивание константСворачивание констант заключается в вычислении констант впроцессе компиляции и замене константных выражений их значениями.Например, выражение 2 * 3.14 можно заменить значением 6.28.1.6.8 Снижение стоимости вычисленийЕще один класс алгебраических оптимизаций включает локальноеснижение стоимости вычислений, т.е.