Теормин (2015) (Теормин)

1. Инструкция внутреннего представления программы current_pos=initial_pos+16*stepТаблица символов (ТС)Внутреннее имяВнешнее имяАнализатор лексикиАтрибутыid1current_posintid2initial_posintnm316intid4stepint〈id,1〉〈=〉〈id,2〉〈+〉〈nm,3〉〈*〉〈id,4〉Внутреннее представление 1(2):инструкции вида: х ← op, y, zгде х, y, z – абстрактныеобласти памяти, отведенные подсоответствующие переменныеПоследовательность токеновАнализатор синтаксисаДерево разбораДерево разбораАнализатор семантикиАбстрактное синтаксическоедерево(АСД – Внутреннеепредставление 1)=〈id,1〉+〈id,2〉*〈nm,3〉Внутреннее представление 2(3):операции вида: OP X, Y, Z,где Х, Y, Z – регистры илиадреса ячеек памяти;операции объединяются в командыСтрока исходной программы〈id,4〉Генератор внутреннегопредставленияt1 ← *,nm3,id4t2 ← +,id2,t1id1 ← t2Внутреннее представление 22.

Виды инструкций◊ Инструкции присваивания(х, y и z – имена (адреса) переменных или константы):х ← op, y, zвыполнить бинарную операцию ор над операндами y и zи поместить результат в хх ← op, yвыполнить унарную операцию ор над операндом yи поместить результат в хх ← yскопировать значение переменной y в переменную хх[i] ← yпоместить значение y в i-ю по отношению к х ячейку памятих ← y[i]поместить значение i-ой по отношению к y ячейки памяти в х Инструкции перехода:goto LБезусловный переход: следующей будет выполнена инструкция сметкой LifTrue x goto LУсловный переход: если х истинно, следующей будет выполненаинструкция с меткой LifFalse x goto LУсловный переход: если х ложно, следующей будет выполненаинструкция с меткой L◊ Процедуры:param хПередача фактического параметра вызываемой процедуре (если вызываемаяпроцедура имеет n параметров, то инструкции ее вызова предшествует n нструкцийparamcall p, nВызов процедуры p, имеющей n параметровreturn yВозврат из процедурыy – необязательное возвращаемое значение3.

Базовый блок (определение)Базовым блоком (или линейным участком) называетсяпоследовательность следующих друг за другом трехадресных команд,обладающая следующими свойствами:(1)поток управления может входить в базовый блок только черезего первую инструкцию, т.е. в программе нет переходов всредину базового блока;(2)поток управления покидает базовый блок без останова иливетвления, за исключением, возможно, в последней инструкциибазового блока.4. Как выделить базовый блок••Строится упорядоченное множество НББ (начало базового блока, либо перваяинструкция программы, либо место, куда указывает оператор условного/безусловногоперехода, либо первая инструкция после инструкции перехода)Каждому НББ соответствует ББ, который определяется как последовательностьинструкций, содержащая само НББ и все инструкции до следующего НББ (не включаяего) или до конца программы.5.

Множества Input и output для базового блока Каждый базовый блок задается тройкой объектов: B = 〈P, Input, Output〉,где P – последовательность инструкций блока B, Input – множество переменных,определения которых достигают блока B, Output –множество переменных, живыхпосле блока B.6. Локальная оптимизацияОптимизация в пределах одного базового блока.Оптимизация – это выполнение следующих преобразований:• Удаление общих подвыражений (инструкций, повторно вычисляющих ужевычисленные значения).• Удаление мертвого кода (инструкций, вычисляющих значения, которыевпоследствии не используются).• Сворачивание констант.• Изменение порядка инструкций, там, где это возможно, чтобы сократить времяхранения временного значения на регистре.Все указанные преобразования можно выполнить за один просмотр ББ, еслипредставить его в виде ориентированного ациклического графа (ОАГ).• Все задачи локальной оптимизации позволяет решить метод локальнойнумерации значений.• Избыточные вычисления внутри базового блока автоматически удаляются впроцессе построения ОАГ (ориентированного ациклического графа).• Множества Input и Output позволяют фиксировать использованиенеинициализированных переменных и исключить присваивание значениймертвым переменным.8.

Локальный метод нумерации значенийПредставление ОАГ в виде таблицы значений•Каждая строка таблицы значений представляет один узел ОАГ.•Первое поле каждой записи представляет собой код операции••Каждой правой части операции 〈op, left, right〉, где ор – код операции, а leftи right – левый и правый операнды, соответствует ее сигнатура〈op,#left, #right〉, где ор – код операции, а #left и #right – номера значенийлевого и правого операндов (у унарных операций #right равен 0).Унарные операции id и nm определяют соответственно имена переменных иконстанты (листовые узлы).• (7) Номер значения – это номер строки таблицы значений (ТЗ), в которой•определяется это значениеАлгоритм (на псевдокоде) построения ОАГ для базового блока 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)9.

Ориентированный ациклический граф - ОАГ, в котором в одну вершинуобъединены вершины синтаксического дерева, представляющие общиеподвыражения для базового блока. a = а + y*(b +(y-z)*b)+(y-z)* bt15t26t37t48t55t66t79a10←←←←←←←←-,*,+,*,-,*,+,+,y3, z4t15, b2b2, t26y3, t37y3, z4t55, b2t48,t66a1, t79Выражение в промежуточномпредставлении+aссылка в ТСссылка в ТСссылка в ТСссылка в ТС352381idididid*+*++# зна- КОПчения# операнда426769# операндаОпределение значения (сигнатура)+t7a* t6y t3 +t5 -b t2 * yt1yabyzt1, t5t2, t6t3t4t7aПрисоединенныепеременные+ t7at4 *Таблица значений(ТЗ)12345678910+at4 *+ t3bz- t1,t5zbyz* t2,t6bАСДОАГТаблица символов (ТС)Внутреннее имяВнешнее имяАтрибутыid1current_posintnm316int10. Граф потока управления - множество всех возможных путейисполнения программы, представленное в виде ориентированногографа, вершинами которого являются ББ.11.

Как построить ГПУВход: последовательность трехадресных инструкций.Выход: список базовых блоков для данной последовательностиинструкций, такой что каждая инструкция принадлежит толькоодному базовому блоку.Метод:1. Строится упорядоченное множество НББ (начало базового блока, либо перваяинструкция программы, либо место, куда указывает оператор условного/безусловногоперехода, либо первая инструкция после инструкции перехода)2. Каждому НББ соответствует ББ, который определяется как последовательностьинструкций, содержащая само НББ и все инструкции до следующего НББ (не включаяего) или до конца программы.3.

Строится множество дуг графа потока управления:• если последняя инструкция ББ не является инструкцией перехода, строитсядуга, соединяющая ББ со следующим ББ;• если последняя инструкция ББ является инструкцией безусловного перехода,строится дуга, соединяющая ББ с ББ, НББ которого имеет соответствующую метку;• если последняя инструкция ББ является инструкцией условного перехода, строятсяобе дуги.12. Региональная оптимизация - оптимизация в пределах нескольких базовыхблоков (например, суперблока).B113.

Суперблок - расширенный базовый блок Eопределяется как множество базовых блоков B1, B2,…, Bn, где у блока B1 может быть несколькопредшественников, а каждый из блоков Bi, 2 ≤ i ≤ nB2B4B5имеет в суперблоке единственного предшественника.Блоки Bi ∈ E формируют дерево с корнем B1. Усуперблока E может быть несколько выходов на блокиB6B7B3(или суперблоки), не входящие в состав E.Можно выделить три суперблока: {B1, B2, B4, B5, B6}, {B7} и {B3}. Блоки B7 и B3 имеютпо два предшественника, поэтому их нельзя включить в суперблок больших размеров14.

Глобальная оптимизация - оптимизация в пределах процедуры.15. Точки программы (…, pj , pj+1 , pj+2 , …) расположены между ее инструкциями(…, Ij , Ij+1 , …) и характеризуют соответствующие состояния программы.pj. . .Ijpj+1Ij+1pj+2. . .In[B]16. Входной точкой ББ является входная точка его первойBинструкции. Выходной точкой ББ является выходная точкаего последней инструкции.Out[B]17. Состояние программы – множество значений всех переменных программы,включая переменные в кадрах стека времени выполнения, находящихся нижетекущей вершины стека.18-20. Передаточная функцияПара состояний во входной и выходной точках фрагмента определяет передаточныефункции этого фрагмента: передаточная функция прямого обхода ( f ) переводитсостояние во входной точке в состояние в выходной точке, а передаточная функцияобратного обхода ( fb ) переводит состояние в выходной точке в состояние во входной точке.Для инструкций:Out[ I j ] = f I j ( In[ I j ]),Для ББ: по определениюIn[ I j ] = f b (Out[ I j ])IjIn[B] = In[I1], Out[B] = Out[In].

Передаточнаяфункция fB блока B по определению равна композиции передаточных функций егоинструкций I1,...,In :илиf B ( x) = f I n ( f I n−1 (... f I1 ( x)...)) = ( f I1  f I 2  ...  f I n )( x)f B = f I1  f I 2  ...  f I nи, соотв.,fB = fI  fIbbbnn −1b ... f I121. Определением переменной х называется инструкция, которая присваиваетзначение переменной х. Каждое новое определение переменной х убивает еепредыдущее определение.22. Использованием переменной х является инструкция, одним из операндовкоторой является переменная х.23. Определение d достигает точки p, если существует путь от точки,непосредственно следующей за d, к точке p, такой, что вдоль этого пути dостается живым. Для достигающих определений передаточная функция fIинструкции I может быть записана в виде: f I ( x ) = genI ∪ ( x − kill I )24.