Тема 06(2016)Глобальная нумерация значений (Лекции)
Описание файла
Файл "Тема 06(2016)Глобальная нумерация значений" внутри архива находится в папке "Лекции". PDF-файл из архива "Лекции", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
6. Глобальная нумерациязначений16.1. Базовый алгоритм локальной нумерации значений6.1.1. Вводные замечанияНумерация значений – классический метод анализа ипреобразования промежуточного представления (трехадресногокода) в ОАГ – ориентированный ациклический граф(лекция 1, п. 1.6.2)Идея: алгоритм присваивает индивидуальный номер каждомузначению, которое будет вычислено во время выполнениякомпилируемой программы, при этом два выражения ei и ejполучают один и тот же номер тогда и только тогда, когдаудается доказать, что значения выражений ei и ej равны для всехвозможных значений их операндов.26.1.
Базовый алгоритм локальной нумерации значений6.1.1. Вводные замечанияПри построении ОАГ удобно представить его в виде таблицызначений (ТЗ), каждая строка ТЗ (массива структур) представляетодин узел ОАГ.Терминальные узлы ОАГ – идентификаторы (id) переменных,определенных вне рассматриваемого базового блока, иконстанты (nm) представляются в ТЗ структурами из двух полейop, ref_ST (ссылка ref_ST отсылает к таблице символов).Нетерминальные узлы ОАГ – выражения представляются своимисигнатурами: выражению op, left, right, где ор – кодоперации, а left и right – левый и правый операнды,соответствует сигнатура op, #left, #right,где #left и #right – номера значений левого и правогооперандов (если op – унарная операция, то #right = 0).Номер значения – это номер строки ТЗ, в которой находитсясигнатура операции, определяющей это значение36.1.
Базовый алгоритм локальной нумерации значений6.1.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ОАГ46.1. Базовый алгоритм локальной нумерации значений6.1.2Представление ОАГ в виде таблицы значенийТаблица значений рассматриваемого примера имеет вид:t15t26t37t48t55t66t79a10-,*,+,*,-,*,+,+,y3, z4t15, b2b2, t26y3, t37y3, z4t55, b2t48,t66a1, t79Верхние индексы уидентификаторов –номерасоответствующихзначений12345678910idididid*+*++# зна- КОПченияссылкассылкассылкассылка352381вввв# операндаТСТСТСТС426769abyzt1, t5t2, t6t3t4t7a# операндаПрисоединенныепеременныеОпределение значения(сигнатура)56.1.
Базовый алгоритм локальной нумерации значений6.1.3Алгоритм построения ТЗАлгоритм (на псевдокоде) построения ТЗ для базового блока 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)66.1. Базовый алгоритм локальной нумерации значений6.1.3.
Модификация подходаЧтобы ускорить алгоритм нумерации значений для отображенияпеременных, констант и вычисляемых значений (выражений) на ихномера значений используется хэш-таблица.Для переменных и констант в качестве аргумента функции #Val(s)используются их имена по таблице символов.Для выражения вида op, opnd1, opnd2 сигнатура (аргумент функции#Val(s)) имеет вид:op, #Val(opnd1), #Val(opnd2)где #Val(opndi) – номер значения операнда opndi,а op – знак операции (например, +).В инструкциях присваивания и копированияномер значения правой части становится номером значениялевой части.76.1.
Базовый алгоритм локальной нумерации значений6.1.3Алгоритм построения ТЗИзвестно несколько подходов к построению алгоритмаглобальной нумерации значений.Мы хотим получить алгоритм глобальной нумерациизначений, распространив базовый алгоритм на всюанализируемую процедуру.86.2. Нумерация значений в суперблоках6.2.1 Расширенные базовые блоки (суперблоки).Определение. Расширенный базовый блок или суперблок Eопределяется как множество базовых блоков B1, B2, …, Bn, где ублока B1 может быть несколько предшественников, а каждый изблоков Bi, 2 i n имеет в суперблоке единственногопредшественника.Блоки Bi E формируют дерево с корнем B1.У суперблока E может быть несколько выходов на блоки (илисуперблоки), не входящие в состав E.Алгоритм нумерации значений в суперблоках будем называтьрасширенным алгоритмом локальной нумерации значений.96.2. Нумерация значений в суперблоках6.2.1 Суперблоки.
Пример.B1m +, a, bn +, a, bB2p +, c, dr +, c, dB3y +, a, bz +, c, dB4q +, a, br +, c, dB5e +, b, 18s +, a, bu +, e, fB6e +, b, 17t +, c, du +, e, fB7v +, a, bw +, c, dx +, e, fВ коде, показанном на рисунке можновыделить три суперблока:B1B2{B1, B2, B4, B5, B6}, {B7} и {B3}.B4B5Блоки B7 и B3 имеют по два предшественника,поэтому их нельзя включить в суперблокбольших размеровB6B7B3106.2. Нумерация значений в суперблоках B16.3.1 Суперблоки. Пример.B2B1m +, a, bn +, a, bB2p +, c, dr +, c, dB4q +, a, br +, c, dB5e +, b, 18 s +, a, bu +, e, fB4B5B6B6e +, b, 17 t +, c, du +, e, fВ суперблоке {B1, B2, B4, B5, B6} можно выделить три пути:{B1, B2}, {B1, B4, B5} и {B1, B4, B6}.Пронумеруем значения вдоль каждого из этих путей.116.2.
Нумерация значений в суперблоках B16.2.1 Суперблоки. Пример.B2B1m +, a, bn +, a, bB2p +, c, dr +, c, dB4q +, a, br +, c, dB5e +, b, 18 s +, a, bu +, e, fB4B5B6B6e +, b, 17 t +, c, du +, e, fa) Путь {B1, B4, B5}:строится (хэш) таблица значений для блока B1таблица значений для пути {B1, B4} строится какпродолжение таблицы значений для блока B1таблица значений для пути {B1, B4, B5} строитсякак продолжение хэш-таблицы таблица значений для пути{B1, B4} .126.3. Нумерация значений в суперблоках B16.3.1 Суперблоки. Пример.B2B1m +, a, bn +, a, bB2p +, c, dr +, c, dB4q +, a, br +, c, dB5e +, b, 18 s +, a, bu +, e, fB4B5B6B6e +, b, 17 t +, c, du +, e, fa) Путь {B1, B4, B5}:строится (хэш) таблица значений для блока B1таблица значений для пути {B1, B4} строится какпродолжение таблицы значений для блока B1таблица значений для пути {B1, B4, B5} строитсякак продолжение таблицы значений для пути {B1, B4} .путь {B1, B4, B5} рассматривается как единый базовыйблок136.2.
Нумерация значений в суперблоках B16.2.1 Суперблоки. Пример.B2B1m +, a, bn +, a, bB2p +, c, dr +, c, dB4q +, a, br +, c, dB5e +, b, 18 s +, a, bu +, e, fB4B5B6B6e +, b, 17 t +, c, du +, e, fб) Путь {B1, B4, B6}:таблица значений для пути {B1, B4, B6} строитсякак продолжение таблицы значений для пути {B1, B4} .путь {B1, B4, B6} рассматривается как единый базовыйблокв) Путь {B1, B2}:таблица значений для пути {B1, B2} строитсякак продолжение таблицы значений для блока B1 .146.2.
Нумерация значений в суперблоках6.2.2 Контекстные таблицы значенийЧтобы нумерация значений над суперблокамибыла эффективной, компилятор должен повторно использоватьрезультаты для блоков, которые входят в несколько путей:После обработки ТЗ для {A, C, D} необходимовоссоздать состояние ТЗ в конце обработки {A, C},чтобы можно было использовать ТЗ для {A, C} приобработке E из {A, C, E}.Оценка размера ТЗ для каждого контекста (очевидная):в рассматриваемом промежуточном представлении(последовательность трехадресных инструкций) числоимен не может более чем в три раза превышать числоинструкций, так как в инструкции используется не болеетрех имен.
Это соображение позволяет сразу выделитьдостаточно памяти под каждую ТЗ и исключить15возможность переполнения ТЗ.6.2. Нумерация значений в суперблоках6.2.2 Контекстные таблицы значенийОбеспечивается это, естественно, с помощью стэка:В нашем примере сначала в стэке строится ТЗ для B1, потом –ТЗ для B2, как продолжение ТЗ для B1, потом выталкивается ТЗдля B2, и на ее месте строится ТЗ для {B1, B2, B4, B5, B6}, и т.д.,пока не будут обойдены все блоки.Объединенные ТЗ образуют текущийB1B2контекст.B4B5B6После того как будут обработаны всепути из суперблока {B1, B2, B4, B5, B6}будут обработаны блоки B7 и B3.
При ихобработке не удастся использовать ТЗдругих блоков, так как каждый из нихдостижим по двум путям, что можетпривести к путанице при объединении16ТЗ.6.2. Нумерация значений в суперблоках6.2.3 ЗатруднениеЕсли в нескольких базовых блоках, входящих в состав суперблока(например, в блоках B1 и B4), определяются номера значенийодной и той же переменной (используется одно и то же имяпеременной) результат его определения в одном блоке (B4) можетпопасть в контекст, связанный с другим блоком (B1).В этом случае при удалении ТЗ блока B4 из стэка в стэке могутсохраниться записи об этой переменной в ТЗ блока B1.