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

исполняемость–возможностьотследитьходисполненияпрограммы;2. возможностьдобавлятькструктурамданныхразличнуюинформацию о зависимостях по данным, управлению, статистикеисполнения и т.д.;3. представление циклов в явном виде;Практикум «оптимизирующие компиляторы»4. компактность (трансляция средней по размеру программы можеттребовать до 16Мбайт ОЗУ, очень большой – может превыситьадресное пространство процесса в 32-х разрядной модели памяти).К наиболее совершенным на сегодняшний день формам можно отнестиуправляющий граф программы (содержащий в себе информацию озависимостях по данным и управлению).

В большинстве компиляторовиспользуетсяграфзависимостейпоуправлению,содержащий в себе графы зависимостей по данным.дополнительноПрактикум «оптимизирующие компиляторы»RTLБольшаячастьработыкомпилятораGCCосуществляетсянадпромежуточным представлением называемым Register Transfer Language(RTL).RTLГенераторкодаFront endРисунок 4Register Transfer Language используется для представления инструкций.При этом инструкции подробно описываются в духе списка LISP.RTL оперирует пятью типами объектов:• Выражения (expressions)• Целые числа (integers)• Длинное целое (wide integers)• Строки (strings)• Вектора (vectors)Практикум «оптимизирующие компиляторы»RTL форматКаждый элемент RTL имеет:• GET_CODE: код операцииo GET_RTX_CLASS: тип RTLo GET_RTX_FORMAT: строка с типом каждого параметраo GET_RTX_LENGTH: количество операндов• GET_MODE: режимo SImode: 4-х байтное целоеo QImode: 1 байтное целоеo SFmode: 4-х байтное с плавающей точкой• Список операндов• ФлагиПример RTL( plus:ОперацияSIтип( reg : SI 8 )первый аргумент( const_int 128 ) )ворой аргументРисунок 5• Суммирует два операнда ( plus : SI (<операнд 1>) (<операнд 2>))o Операнды рассматриваются как четырехбайтные целые ( plus :SI …)• Первый операнд – это регистр ( reg : SI 8 )o Регистр хранит 4-х байтное целое ( reg : SI 8 )Практикум «оптимизирующие компиляторы»o Номер регистра – 8 ( reg : SI 8 )• Второй операнд – целое число ( const_int 128 )o Значение – число ‘128’ ( const_int 128 )o Режим VOIDmode (не указан)Представление констант в RTLПодробный список допустимых описаний вы можете найти в разделеConstant Expression Types главы RTL Representation в документации GCCInternals.Мы рассмотрим:(const_int i)Этот тип выражения представляет целочисленноезначение i.

Пример: (const_int 128)(const_vector:m [x0 x1 …])Представляет вектор констант. В квадратных скобкахуказаны значения, хранящиеся в векторе. M собственноуказывает тип значений.В GCC Internals вы найдете описание для: const_int, const_double,const_vector, const_string, symbol_ref, label_ref, const, high.Представление регистров и памяти в RTLПодробный список допустимых описаний вы можете найти в разделеRegisters and Memory главы RTL Representation в документации GCCInternals.Мы рассмотрим:(reg:m n)Для малых значений n (меньших константыFIRST_PSEUDO_REGISTER) эта запись будет означатьссылку на конкретный аппаратный регистр. Длябольших значений n это будет означать временноезначение или псевдорегистр.(mem:m addr alias)Означает ссылку на основную память по адресу addr.

Mозначает тип объекта к которому ведется обращение(размер). Alias означает имя переменной.Практикум «оптимизирующие компиляторы»В GCC Internals вы найдете описание для: reg, subreg, scratch, cc0, pc, mem,addressof.Представление арифметических выражений в RTLПодробный список допустимых описаний вы можете найти в разделе RTLExpressions for Arithmetic главы RTL Representation в документации GCCInternals.Мы рассмотрим:(plus:m x y)Представляет сумму значений представленных x и y длятипа m.(compare:m x y)Представляет результат вычитания y из x с цельюсравнения.В GCC Internals вы найдете описание для: plus, lo_som, minus, ss_plus,us_plus, ss_minus, us_minus, compare, neg, mult, div, udiv, mod, umod, smin,smax umin, umax not, and, ior, xor, ashift, lshiftrt, ashiftrt, rotate, rotatert, abs,sqrt, ffs, clz, ctz, popcount, parity.Прочие инструкцииЗа информацией по представлению других инструкций обращайтесьнепосредственно к GCC Internals: Представление операций сравнения вRTL, Представление битовых полей в RTL, Представление векторныхопераций,Представлениепреобразованийтипов,Представлениевекторных операций, Представление процедур и функций, Представлениевекторных операций, Ассемблерные инструкции, Insns, Вызовы функций.Практикум «оптимизирующие компиляторы»SSA форма в GCCStatic Single Assignment Form (SSA Form) – форма представленияпрограммы в которой любой переменной значение присваивается не болееодного раза.SSA форма и граф управления потоком были предложены дляпредставления потока данных и потока управления в программе.

Каждаяиз этих ранее независимых технологий использовалась в классеоптимизаций. Большое число современных алгоритмов оптимизациипрограмм основаны на совместном использовании графа управления иSSA-формы.Минусы представления RTL и дерева, используемого front end,как промежуточных представлений при работе оптимизатораRTLFront endПроходоптимизацииГенераторкодаРисунок 6Большинство проходов работают с RTL представлением.Почему ни RTL представление, ни дерево в Front end не подходит длясовременных методов оптимизации.RTL обладает рядом минусов. Основные из них:• Не подходит для высокоуровневых преобразованийПрактикум «оптимизирующие компиляторы»• Потеряна оригинальная структура программыМожно попробовать проводить оптимизацию на деревьях Front end. Рядалгоритмов так и делают.

Особенно, если оптимизация зависит от языкапрограммирования.Деревья:• Отражают структуру исходной программы• Поддерживают высокоуровневые (близкие к исходному коду)преобразованияНО:• Каждый front end использует свой диалект дерева.Представление Tree SSATree SSA – это новая система оптимизации основанная на SSAпредставлении и действующая на GCC Tree представлении. Идеязаключается в использовании специального представление в целом оченьпохожего на дерево, используемое в Front end, но унифицированное длявсех поддерживаемых языков. Разработчики обещают внедрить данноепредставление в ближайших версиях GCC.

Мы рассмотрим корни этойидеи: SSA-представление и управляющий граф.SSASSA – это форма программы в которой значение каждой переменнойприсваивается только один раз, но может читаться сколько угодно раз.На рисунках 7 и 8 показаны типичные примеры преобразования в SSAформу.Практикум «оптимизирующие компиляторы»VÅÅVÅÅ4V+56V+7ОбычныйV1 ÅÅV2 ÅÅ4V1 + 56V2 + 71. Каждое присваиваниезначения переменнойдает ей новоеуникальное имяКод в SSAРисунок 7If Pthen V Å 4else V Å 6If Pthen V1 Å 4else V2 Å 6V3 Å Ф(V1, V2)/*используемдалее V*//*используемдалее V3*/Обычный код2.

В местах соединениядобавляем специальноеприсваиваниеКод в SSA формеРисунок 8Управляющий графПредложения программы организуются в базовые блоки (не обязательномаксимальные). Базовым блоком может быть любой фрагмент кода несодержащий переходов. Программа входит в первое предложение такогоблока и выходит из последнего.Управляющий граф (control flow graph) – это направленный граф, ввершинах которого расположены базовые блоки, а дуги соответствуютпереходам.Практикум «оптимизирующие компиляторы»вход11: I Å 1; J Å 1;1: K Å 1; L Å 1;22: repeat2:3:if (P)3then do3:J Å I3:if (Q)44:then L Å 25:else L Å 376K Å K + 16:6:end7:else K Å K + 28:print(I, J, K, L)9:repeat9:589if (R)then L Å L + 410:11:until (S)12:I Å I + 6101112: until (T)12выходРисунок 10Преобразование в SSAПусть программа представлена в виде control flow graph.Каждое предложение внутреннего представления вычисляет некотороевыражение и использует результат для присваивания или перехода.Преобразование программы в SSA форму – двухэтапный процесс:1.

На первом этапе добавляются тривиальные Ф-функции в некоторыевершины графа управляющей логики.Практикум «оптимизирующие компиляторы»2. На втором этапе генерируются новые переменные (находятсязависимости, переменные получают «версии»).Массивы«Хитрость» работы с массивами заключается в том, что все обращения кэлементам массивом оборачиваются специальными функциями.Исключение составляет тот случай, если язык поддерживает операции смассивами как со скалярами (поэлементное копирование и пр.).

В этомслучае переменная массива обрабатывается как обычный скаляр.Рассмотрим случай обращения к элементу массива.Исходный код, использующий массивы:ÅA(i)A(j) ÅA(i)ÅA(k) + 2Эквивалентный код, в котором использованы специальные операторыдоступа:ÅA(j) ÅTAccess(A, i)Update(A, j, V)ÅAccess(A, k)ÅT+2SSA форма:ÅA9(j) ÅT1Access(A8, i7)Update(A8, j6, V5)ÅAccess(A9, k4)ÅT1 + 2Практикум «оптимизирующие компиляторы»Применение SSA• Продвижение констант• Удаление «мертвого кода»• SSAпредставлениетакжеиспользуетсядляопределенияэквивалентности программ.Пример продвижения констант и удаления «мёртвого кода» представлен вТаблице 3.Оригинальный кодТаблица 3Код после продвиженияконстантa1 = 10;a1 = 10;b1 = 3;b1 = 3;c1 = a1 + b1;c1 = 13;if(c1 < V1)if(13 < V1)a2 = a1 + 3;elsea3 = b1 + 10;a2 = 13;elsea3 = 13;a4 = Ф(a2, a3);a4 = Ф(a2, a3);c2 = a4 – b1;c2 = 10;printf(“%d\n”, c2);printf(“%d\n”, 10);Код после удаления «мёртвогокода».printf(“%d\n”, 10);Практикум «оптимизирующие компиляторы»Анализ исходной программыАнализ исходной программы на языке высокого уровня обычно состоит изтрех логических этапов:• Лексический анализ – линейный анализ, при котором поток символовисходной программы считывается слева направо и группируется втокены(token),представляющиесобойпоследовательностисимволов с определенным совокупным значением.• Синтаксический анализ – иерархический анализ, при которомсимволы или токены иерархически группируются во вложенныеконструкции с совокупным значением.• Семантическийанализ–позволяетпроверитькорректностьсовместного размещения компонентов программы (например, типыданных).ЯзыкиТ.