Лекция 01. Неоптимизирующий компилятор (1157459)

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

Текст из файла

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 Снижение стоимости вычисленийЕще один класс алгебраических оптимизаций включает локальноеснижение стоимости вычислений, т.е.

заменяет более дорогие соперации более дешевыми (см. таблицу)Дорогиеx2Дешевыеx  x2  xx + xx/2x  0.5221.6 Локальная оптимизация1.6.9 Удаление мертвого кодаПреобразование ОАГ, соответствующее удалению мертвого кода,состоит в удалении из ОАГ любого корня (Op), с которым не связаныживые переменные.Живыми называются переменные, значения которых, вычисленные врассматриваемом базовом блоке, используются в других базовых блокахДля полноценного удаления мертвого кода необходимо уточнитьопределение базового блока.Определение.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций