Лекция 07. Выбор команд (Лекции (2015))

7. Выбор команд17.1 Вводные замечания7.1.1 Постановка задачиОптимизатор работает над промежуточным представлениемпрограммы, и когда процесс оптимизации закончится, получитсяоптимизированная программа в промежуточном представлении.На следующем этапе необходимо перевести программу изпромежуточного представления в код целевого процессора.Отображение инструкций промежуточного представления вкоманды целевого процессора называется выбором команд.Существует несколько подходов к решению этой задачи.Рассмотрим подход, использующий сопоставление шаблоновна абстрактном синтаксическом дереве, построенномпо оптимизированному промежуточному представлению.27.1 Вводные замечания7.1. 2 Вход и выход генератора кодаВходной поток генератора кода:промежуточное представление исходной программы(последовательность трехадресных инструкций)таблица символов, которая используется дляопределения адресов времени выполнения объектовданных, обозначаемых в промежуточном представленииименами.Выходной поток генератора кода: объектный код(последовательность команд целевого процессора)Объектный модуль – часть программы в объектном коде,соответствующая исходному модулюКомпоновщик объединяет объектные модули и библиотекив единую программу, которая и выполняется на целевомпроцессоре.37.2 Объектный код7.2.1 Общая характеристикаПредположения о целевом процессоре (ядре)RISC-архитектураТолько целочисленная арифметика.Байтовая адресация памятиn регистров общего назначения R0, R1, ..., Rn–1Команда: op, dst, src1, src2Операции:загрузки и сохранения регистров,вычислительные,условные и безусловные переходы.47.2 Объектный код7.2.2 Система командLD, r, xЗагрузка значения из ячейки памяти х на регистр rLD, r1, r2Копирование значения регистра r1 на регистр r2ST, х, rCохранение значения регистра r в ячейке памяти хOP1 dst, src1, src2 Бинарная операция: dst = src1 ОР src2OP2 dst, src1Унарная операция: dst = ОР src1BR LПереход на команду с меткой L (goto L).Bcond3 r, LВетвление: переход на команду с меткой L, еслизначение на регистре r удовлетворяет условиюcond: if(cond)goto L1определены арифметические, булевы и поразрядные операции2определены арифметические, булевы и поразрядные операции3формирование условий выполняется с помощью операций отношения иарифметических операций57.2 Объектный код7.2.3 Режимы адресацииРежим прямой адресации – адрес задаетсянепосредственно значением xРежим индексированной адресации а(r), а – переменная,r – регистр.

Адрес а(r) вычисляется путем прибавления кl -значению а значения из регистра r.Этот режим адресации полезен для обращения к массивам:а – базовый адрес массива, r – смещение.Режим косвенной адресации:*r ссылка на ячейку памяти, находящуюся по адресуcontents(r)*c(r) ссылка на ячейку памяти, находящуюсяпо адресу c + contents(r)(c – константа, contents – операция разыменования)Режим адресации с использованием констант,для указания которых используется префикс #.Например, команда LD r,#n загружает в регистр rцелое число n67.3 Основные фазы генерации кодаРаспределение памятиВыбор командРаспределение регистровВыбор оптимального порядка команд (планирование кода)Распределение памяти в данном курсе не рассматривается, так как оносвязано с работой системы поддержки времени выполнения.77.4 Выбор команд7.4.1.

Постановка задачиЕсли не требовать эффективности целевой программы,выбор команд предельно прост:для каждого типа трехадресных инструкций определяетсяшаблон целевого кода, генерируемого для такихинструкций;каждая трехадресная инструкция заменяетсясоответствующим шаблономРассмотрим несколько простых примеров87.4 Выбор команд7.4.2. Примеры шаблоновПример 1. При генерации кода для трехадресной инструкцииx  +, y, z, где память под x, y и z выделяетсястатически (static), можно использовать следующий шаблон:LDR0,yADDR0,R0,STx,R0// загрузить у в R0z// сложить z и R0// сохранить R0 в хПрименим этот шаблон к последовательности из двухинструкций a  +, b, c; d  +, a, e;//R0  bLDR0,bADDR0,R0,STa,R0//a  R0LDR0,a//R0  aADDR0,R0,STd,R0ce//R0  +, R0, c//R0  R0 + e//d  R097.4 Выбор команд7.4.2. Примеры шаблоновПример 2.

Многие компьютеры под влиянием языка Си имеюткоманду INC x:Ей соответствует шаблонINCx// x++Очевидно, что использование шаблона INC дает лучший код,чем использование шаблона из примера 1LDR0,xADDR0,R0,STx,R0// загрузить x в R01// сложить 1 и R0// сохранить R0 в х107.4 Выбор команд7.4.2.

Примеры шаблоновПример 3. Шаблон для +, x, y, z (x, y, z – адресаячеек памяти)LDLDADDSTR1, yR2, zR1, R1, R2x, R1Пример 4. Шаблон для ifTrue(y < z)gotoLLDR1, yLDR2, zSUBR1, R1, R2BLTZ R1, L117.4 Выбор команд7.4.2. Примеры шаблоновПример 5. Шаблон для(a)b  a[i] (a – массив 8-байтных значений)(b)LD R1, iMUL R1, R1, #8LD R2, a(R1)//R2contents(a+contents(i))ST b, R2a[k]  cLD R1, cLD R2, kMUL R2, R2, #8ST a(R2), R1// contents(a+contents(k))R1127.4 Выбор команд7.4.2. Примеры шаблоновПример 6. Шаблоны для(a)x  *pLDLDST(b)*pLDLDSTR1, pR2, 0(R1)x, R2//R2contents(0+contents(R1)) yR1,pR2,y0(R1), R2//contents(0+contents(R1))R2137.4 Выбор команд7.4.3 Стоимость командКаждая команда целевого языка имеет связанную с нейстоимость.Если считать стоимость команды равной единице плюсстоимости, связанные с режимами адресации операндов, тостоимость будет пропорциональна длине команды в словах:Стоимость операнда на регистре равна 0Стоимость операнда из ячейки памяти равна 1Стоимость операнда-константы равна 1Такой подход обосновывается тем, что адресаячеек памяти и константы хранятся в словах,следующих за командойСтоимость каждого разыменования равна 1147.4 Выбор команд7.4.3 Стоимость командПримеры.1)Стоимость команды LD R0, R1 равна 1.2)Стоимость команды LD R0, М (М – адрес ячейкипамяти) равна 2.3)Стоимость команды LD R0, *100(R1)(R0 contents(contents(100 + contents(R1))) равна 4.Стоимость программы (на целевом языке) равна сумместоимостей ее команд.

Чем меньше стоимость программы, тембыстрее она выполняетсяАлгоритм генерации кода должен минимизировать стоимостьпрограммы.157.5 Метод переписывания дерева7.5.1 Схема трансляции деревьевРассмотрим инструкцию присваиванияa[i]  +, b, 1Пусть(1)массив а хранится в стеке времени выполнения(адреса времени выполнения локальных переменныха и i заданы как смещения Ca и Сi относительноуказателя на начало текущей записи активации SP(адрес SP хранится на специальном регистре RSP)переменная b хранится в глобальной ячейке памяти Мb.В целевом коде инструкции (1) будет соответствоватьпоследовательность команд :167.5 Метод переписывания дерева7.5.1 Схема трансляции деревьевВ целевом коде инструкции a[i]  +, b, 1будет соответствовать последовательность команд :LDR1, Мb// R1 = bADDLDR1,R2,R1, #1Сi (RSP)// R1 = b + 1// R2 = contents(Сi + contents(RSP))MULSTR2, R2, 8// R2 = R2 * 8*R2(Ca (RSP)), R1// R1 = contents(contents(Ca +contents(RSP)) + contents(R2))Введем операцию индексмрования ind (index):ind(Ci + RSP) =contents(Ci + contents(RSP)) = contents(R2) = iind((Ca + RSP) + ind (Ci + RSP)) =contents(contents(Ca + contents(RSP))+contents(R2))17= a[i]7.5 Метод переписывания дерева7.5.1 Схема трансляции деревьевa[i]  +, b, 1ind(Ci + RSP) =contents(Ci + contents(RSP)) = contents(R2) = iind((Ca + RSP) + ind (Ci + RSP)) =contents(contents(Ca + contents(RSP))+contents(R2))= a[i]+(Mb C1) = +, b, #1+indMb++Car-значениеindRSPl-значениеC1+CiRSP187.5 Метод переписывания дерева7.5.1 Схема трансляции деревьевТаким образом, исходное дерево (выражение) на левом рисунке должнобыть преобразовано (переписано) в дерево на правом рисунке+a[i]b1+indMb++Car-значениеindRSPl-значениеC1+CiRSP197.5 Метод переписывания дерева7.5.2 Описание методаЦелевой код генерируется в процессе свертки входного деревав единый узел путем последовательного примененияправил преобразования дерева.Каждое правило преобразования дерева представляет собойинструкцию видаreplacement  template {action}где replacement – отдельный узел, template – шаблон(поддерево), action – действие (фрагмент генерируемого кода,соответствующий шаблону).Множество правил преобразования дерева именуетсясхемой трансляции дерева.Трансляция состоит из (возможно, пустой) последовательностимашинных команд, которые генерируются действием (action),связанным с шаблоном (template).207.5 Метод переписывания дерева7.5.3 Схема трансляции дереваСхема трансляции дерева – удобный способ описания схемывыбора команд в генераторе кода.Схема трансляции задается набором правил сверткиКаждое правило содержит:поддерево, соответствующее рассматриваемому шаблонуметку узла, на который заменяется поддерево при сверткекоманды, которые помещаются в объектную программупри сверткеПример правила: правило для команды сложения одногорегистра с другим имеет вид:Ri  +{ADD Ri, Ri, Rj}RiRjесли входное дерево содержит поддерево, соответствующееданному шаблону, то это поддерево можно заменить однимузлом с меткой Ri и сгенерировать командуADD Ri, Ri, Rj.Такая замена называется замещением поддерева.217.5 Метод переписывания дерева7.5.3 Схема трансляции дереваЛистья как входного дерева, так и шаблона могут иметь атрибутыс индексами; иногда к значениям индексов применяется рядограничений – семантических предикатов, которым долженудовлетворять шаблон при установлении соответствия.Пример предиката: значение константы должно находитьсяв определенном диапазоне.Выбор команд ведется в следующих предположениях:Любая инструкция промежуточного кода может бытьреализована с помощью одной или нескольких машинныхкоманд.Имеется достаточно регистров для вычисления каждогоузла.227.5 Метод переписывания дерева7.5.4 ПримерПравила сверткиНа рисунке приведеныправила свертки длянекоторых команд целевоймашины: правила 1) и 2) относятсяк инструкциям загрузки (LD) правила 3) и 4) –инструкциям сохранения(ST) правила 5) и 6) –индексированным загрузкам правила 7) и 8) сложениям(ADD)237.5 Метод переписывания дерева7.5.4 ПримерНачнем применять схему трансляции дерева к дереву из примера 7.5.1слева направо.Среди шаблонов нет шаблонаRi+(1)C1Mbесть только шаблонRi+(2)RiRjследовательно, чтобы свернуть шаблон (1) необходимо с помощьюправил 1) и 2) привести его к виду (2)правило 1) Ri  Ca {LD Ri #a} позволяет заменить C1 на R0правило 2) Ri  Mx {LD Ri x} позволяет заменить Mb на R1после этих замен шаблон принимает вид (2), что позволяет применитьправило 7)247.5 Метод переписывания дерева7.5.4 ПримерПрименим приведенную схему трансляции дерева для генерации кодадля примера 7.5.1.Правило 1) позволяет привести шаблонR0Ca+к видуRSPR0R0+RSPвыдав команду{LD R0 #a}Теперь можно с помощью правила 7)привести исходное дерево к виду(нижний рисунок) и выдать команду{ADD R0 R0 SP}Итак, дерево приведено к виду (нижнийрисунок) и выданы команды:LD R0 #aADD R0 R0 SP257.5 Метод переписывания дерева7.5.4 ПримерВ левом поддереве дерева (верхний рисунокслева)можно применить правило 5) к шаблонулибо правило 6) к шаблонуВыгоднее применить правило 6), так каконо сворачивает большую часть дерева.После применения правила 6) деревопримет видпри этом будет выдана командаADD R0 R0 i(SP)267.5 Метод переписывания дерева7.5.4 ПримерПрименив к правому поддереву деревасначала правило 2), а потом правило 8), получим деревоБудет выдано две команды:LD R1 bINC R1(правило 2))(правило 8))277.5 Метод переписывания дерева7.5.4 ПримерПоследнее деревосоответствует поддереву из правила 4); применение этого правилосворачивает дерево в единственный узел и выдает команду ST *R0 R1Таким образом в процессе свертки исходного дерева была сгенерированапоследовательность команд:LDADDADDLDINCSTR0R0R0R1R1*R0#aR0 SPR0 i(SP)bR1287.5 Метод переписывания дерева7.5.5 ПроблемыЕсли на каком-нибудь шаге не будет найдено соответствияни одному шаблону, процесс генерации кода блокируется.Для реализации процесса свертки, показанного на примере,необходимо решить два вопроса, связанных с поискомсоответствия деревьев шаблону:Каким образом выполняется поиск соответствия?Эффективность процесса генерации кода в процессекомпиляции зависит от того, насколько эффективенприменяющийся алгоритм поиска соответствий.Что делать, если оказалось, что можно применитьболее одного шаблона?Эффективность сгенерированного кода может зависетьот порядка, в котором выявлялось соответствиешаблонам, так как различные последовательностисоответствий будут приводить к разнымпоследовательностям машинных команд, одни изкоторых более эффективны, чем другие.297.5 Метод переписывания дерева7.5.6 Поиск соответствийПравила преобразования дерева и входное дерево можнопредставить в виде строк, используя префиксную польскуюзапись: сначала записывается операция (корень поддерева),потом ее первый операнд (левое поддерево), потом второйоперанд (правое поддерево).Для рассматриваемого примера правила преобразования деревабудут представлены в виде:1)Ri  ca{ LDRi#a }2)R i  Mx{ LDRix }3)M = Mx Ri{ STx4)M = ind Ri Rj{ ST5)Ri  ind + ca Rj{ LDRi a(Rj)}6)Ri  + Ri ind + ca Rj{ ADDRi Ria(Rj)}7)Ri  + Ri R j{ ADDRi RiRj }8)Ri  + Ri c 1{ INCRi }9)R  sp10)МmRi }*Ri Rj}307.5 Метод переписывания дерева7.5.6 Поиск соответствийДерево из примера 7.5.4 в префиксном представлении будетзадаваться следующей строкой:= ind + + Ca RSP ind + Ci RSP + Mb C1317.5 Метод переписывания дерева7.5.7 Поиск соответствий с помощью синтаксического анализаСодержимое второго столбца таблицы можно рассматривать какпродукции LR-грамматики.