Лекция 05. Глобальная нумерация значений (Лекции (2015))

5. Глобальная нумерациязначений15.1. Базовый алгоритм локальной нумерации значений5.1.1. Вводные замечанияНумерация значений – классический метод анализа ипреобразования промежуточного представления (трехадресногокода) в ОАГ – ориентированный ациклический граф(лекция 1, п. 1.6.2)Идея: алгоритм присваивает индивидуальный номер каждомузначению, которое будет вычислено во время выполнениякомпилируемой программы, при этом два выражения ei и ejполучают один и тот же номер тогда и только тогда, когдаудается доказать, что значения выражений ei и ej равны для всехвозможных значений их операндов.25.1. Базовый алгоритм локальной нумерации значений5.1.1.

Вводные замечанияПри построении ОАГ удобно представить его в виде таблицызначений (ТЗ), каждая строка ТЗ (массива структур) представляетодин узел ОАГ.Терминальные узлы ОАГ – идентификаторы (id) переменных,определенных вне рассматриваемого базового блока, иконстанты (nm) представляются в ТЗ структурами из двух полейop, ref_ST (ссылка ref_ST отсылает к таблице символов).Нетерминальные узлы ОАГ – выражения представляются своимисигнатурами: выражению op, left, right, где ор – кодоперации, а left и right – левый и правый операнды,соответствует сигнатура op, #left, #right,где #left и #right – номера значений левого и правогооперандов (если op – унарная операция, то #right = 0).Номер значения – это номер строки ТЗ, в которой находитсясигнатура операции, определяющей это значение35.1.

Базовый алгоритм локальной нумерации значений5.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ОАГ45.1. Базовый алгоритм локальной нумерации значений5.1.2Представление ОАГ в виде таблицы значенийТаблица значений рассматриваемого примера имеет вид:t15t26t37t48t55t66t79a10-,*,+,*,-,*,+,+,y3, z4t15, b2b2, t26y3, t37y3, z4t55, b2t48,t66a1, t79Верхние индексы уидентификаторов –номерасоответствующихзначений12345678910idididid*+*++# зна- КОПченияссылкассылкассылкассылка352381вввв# операндаТСТСТСТС426769abyzt1, t5t2, t6t3t4t7a# операндаПрисоединенныепеременныеОпределение значения(сигнатура)55.1. Базовый алгоритм локальной нумерации значений5.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)65.1.

Базовый алгоритм локальной нумерации значений5.1.3. Модификация подходаЧтобы ускорить алгоритм нумерации значений для отображенияпеременных, констант и вычисляемых значений (выражений) на ихномера значений используется хэш-таблица.Для переменных и констант в качестве аргумента функции #Val(s)используются их имена по таблице символов.Для выражения вида op, opnd1, opnd2 сигнатура (аргумент функции#Val(s)) имеет вид:op, #Val(opnd1), #Val(opnd2)где #Val(opndi) – номер значения операнда opndi,а op – знак операции (например, +).В инструкциях присваивания и копированияномер значения правой части становится номером значениялевой части.75.1. Базовый алгоритм локальной нумерации значений5.1.3Алгоритм построения ТЗИзвестно несколько подходов к построению алгоритмаглобальной нумерации значений.Мы хотим получить алгоритм глобальной нумерациизначений, распространив базовый алгоритм на всюанализируемую процедуру.85.2.

Нумерация значений в суперблоках5.2.1 Расширенные базовые блоки (суперблоки).Определение. Расширенный базовый блок или суперблок Eопределяется как множество базовых блоков B1, B2, …, Bn, где ублока B1 может быть несколько предшественников, а каждый изблоков Bi, 2  i  n имеет в суперблоке единственногопредшественника.Блоки Bi  E формируют дерево с корнем B1.У суперблока E может быть несколько выходов на блоки (илисуперблоки), не входящие в состав E.Алгоритм нумерации значений в суперблоках будем называтьрасширенным алгоритмом локальной нумерации значений.95.2. Нумерация значений в суперблоках5.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 имеют по два предшественника,поэтому их нельзя включить в суперблокбольших размеровB6B7B3105.2.

Нумерация значений в суперблоках B15.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}.Пронумеруем значения вдоль каждого из этих путей.115.2. Нумерация значений в суперблоках B15.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} .125.3. Нумерация значений в суперблоках B15.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} рассматривается как единый базовыйблок135.2. Нумерация значений в суперблоках B15.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 .145.2. Нумерация значений в суперблоках5.2.2 Контекстные таблицы значенийЧтобы нумерация значений над суперблокамибыла эффективной, компилятор должен повторно использоватьрезультаты для блоков, которые входят в несколько путей:После обработки ТЗ для {A, C, D} необходимовоссоздать состояние ТЗ в конце обработки {A, C},чтобы можно было использовать ТЗ для {A, C} приобработке E из {A, C, E}.Оценка размера ТЗ для каждого контекста (очевидная):в рассматриваемом промежуточном представлении(последовательность трехадресных инструкций) числоимен не может более чем в три раза превышать числоинструкций, так как в инструкции используется не болеетрех имен.

Это соображение позволяет сразу выделитьдостаточно памяти под каждую ТЗ и исключить15возможность переполнения ТЗ.5.2. Нумерация значений в суперблоках5.2.2 Контекстные таблицы значенийОбеспечивается это, естественно, с помощью стэка:В нашем примере сначала в стэке строится ТЗ для B1, потом –ТЗ для B2, как продолжение ТЗ для B1, потом выталкивается ТЗдля B2, и на ее месте строится ТЗ для {B1, B2, B4, B5, B6}, и т.д.,пока не будут обойдены все блоки.Объединенные ТЗ образуют текущийB1B2контекст.B4B5B6После того как будут обработаны всепути из суперблока {B1, B2, B4, B5, B6}будут обработаны блоки B7 и B3. При ихобработке не удастся использовать ТЗдругих блоков, так как каждый из нихдостижим по двум путям, что можетпривести к путанице при объединении16ТЗ.5.2.

Нумерация значений в суперблоках5.2.3 ЗатруднениеЕсли в нескольких базовых блоках, входящих в состав суперблока(например, в блоках B1 и B4), определяются номера значенийодной и той же переменной (используется одно и то же имяпеременной) результат его определения в одном блоке (B4) можетпопасть в контекст, связанный с другим блоком (B1).В этом случае при удалении ТЗ блока B4 из стэка в стэке могутсохраниться записи об этой переменной в ТЗ блока B1. Так как этонеобходимо учесть в алгоритме нумерации значений, алгоритмусложнится.Описанного затруднения легко избежать, если выполнятьнумерацию значений для суперблоков в SSA-форме:тогда каждое имя будет определяться только один раз, иописанные конфликты невозможны.175.2.

Нумерация значений в суперблоках5.2.4 Контекстные таблицы значений и SSA-формаB1 m0  +, a0, b0 B2 p0  +, c0, d0B3 r2  (r0, r1)n0  +, a0, b0r0  +, c0, d0y0  +, a0, b0z0  +, c0, d0B4q0  +, a0, b0r1  +, c0, d0B7e2  (e0, e1)u2  (u0, u1)v0  +, a0, b0w0  +, c0, d0x0  +, e2, f0B5e0  +, b0, 18s0  +, a0, b0u0  +, e0, f0B6e1  +, b0, 17t0  +, c0, d0u1  +, e1, f0B1B2 SSA-форма обладает двумя важнымисвойствами:(1) каждое имя определяется только водной инструкции(2) каждое использование значенияссылается только на одно определение.B4B5B6B7B3185.2.

Нумерация значений в суперблоках5.2.4 Контекстные таблицы значений и SSA-формаB1m0  +, a0, b0n0  +, a0, b0B2p0  +, c0, d0r0  +, c0, d0B3r2  (r0, r1)y0  +, a0, b0z0  +, c0, d0B4q0  +, a0, b0r1  +, c0, d0B5e0  +, b0, 18s0  +, a0, b0 u0  +, e0, f0B6e1  +, b0, 17t0  +, c0, d0 u1  +, e1, f0B7e2  (e0, e1)u2  (u0, u1)v0  +, a0, b0w0  +, c0, d0x0  +, e2, f0B1B2 Инструкции, удаляемые алгоритмом анализасуперблоков, выделены подчеркиванием ицветом Инструкции, помеченные  , не удаляютсяалгоритмом локальной нумерации значений.B4B5B6B7B3195.2. Нумерация значений в суперблоках5.2.5 Оценка расширенного алгоритма локальной нумерации значенийРасширенный алгоритм локальной нумерации значений отличноработает внутри суперблока.