Тема 06(2016)Глобальная нумерация значений (1161801)
Текст из файла
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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
