2006. Межпроцедурная нумерация значений

ООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------АНАЛИЗ “МЕЖПРОЦЕДУРНАЯНУМЕРАЦИЯ ЗНАЧЕНИЙ”А.Ю.Дроздов,А.В.КанИнститут микропроцессорных вычислительных систем РАН, МоскваE-mail: sasha@mcst.ru; akan@mcst.ru1. ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕКомпилятор – это программа, которая переводит программу, представленную на одном языке, на семантически эквивалентную программу на другом языке. В процессе такого преобразования компилятором, как правило, используются одно или несколькопромежуточных представлений программы [1]. Именно над промежуточным представлением производятся различные виды анализов и оптимизаций. В статье будет описанопромежуточное представление, используемое для анализа “Межпроцедурная нумерациязначений”.За основу промежуточного представления взято представление EIR, которое применяется в языковом оптимизирующем компиляторе ecf_opt, разрабатываемом компаниейElbrus Inc.

(Россия) [2, 3].EIR (Elbrus Intermediate Representation) является высокоуровневым машиннонезависимым промежуточным представлением семантики, предназначенным для представления семантики ряда входных универсальных языков высокого уровня с возможностью последующей генерации машинно-зависимых представлений ряда платформ.1.1. Управляющий графУправляющий граф процедуры является аналитической структурой данных, отражением результатов анализа топологии и семантики программы. Каждый узел управляющего графа соответствует некоторому линейному участку.

Управляющий граф являетсяориентированным. Каждая дуга такого графа соответствует возможности передачиуправления в программе между линейными участками.Линейным участком называется упорядоченное множество операций. Если множество не пусто, то выделяются входная и выходная операции и выдвигаются требования, которым должен удовлетворять линейный участок:– Связность: все операции линейного участка, включая конечную, достижимы из начальной операции без выхода за пределы линейного участка; из всех операций линейногоучастка, включая начальную достижима конечная операция.– Замкнутость: выход из линейного участка минуя конечную операцию или вход влинейный участок минуя начальную операцию невозможен.– Полнота: линейному участку принадлежат все операции проходимые при обходесверху от начальной операции к конечной и при обходе снизу от конечной операции кначальной.– Одноуровневость: линейный участок не содержит внутри себя других линейныхучастков.тел./факс: (095) 917-24-70-1-a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------– Однозначность: каждой операции множества конечных операций взаимно однозначно соответствует операция множества начальных операций и наоборот; линейныйучасток, которому принадлежит операция, определяется однозначно обходом в любомнаправлении.– Ацикличность: ни одна операция линейного участка не может быть достигнута припроходе по управлению от самой себя без выхода за пределы линейного участка.– В линейном участке может быть не более одной операции записи.Все узлы графа делятся на два типа: обычные узлы и узлы слияния.

Обычный узелможет иметь не более одного предшественника. Узлы слияния могут иметь произвольноечисло предшественников. Линейные участки, соответствующие узлам слияния не содержат операций, кроме псевдоопераций JOIN.Один узел графа помечен как стартовый, такой узел не имеет входных дуг. Стартовыйузел соответствует линейному участку, с которого начинается выполнение процедуры.Один узел графа помечен как стоповый, в него сведены все дуги, по которым может происходить выход из процедуры.Граф может содержать циклы. Представим, что мы обходим граф “вширь” помечаяуже рассмотренные узлы. В процессе такого обхода могут встретиться дуги, ведущие куже помеченному узлу. Такие дуги будем называть обратными.Рис. 1.

Управляющий граф.тел./факс: (095) 917-24-70-2-a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------Для дальнейшего изложения необходимо ввести понятие множество IDF (immediatedominant frontiers) для узла.

IDF для узла x – это множество ближайших узлов слияния,встречающихся на всех путях от узла x до стопового узла.Рис. 2. Множества IDF.1.2. Операционная семантикаОперации делятся на две группы – те, которые вырабатывают результат (результативные), и те, которые результата не вырабатывают.

Будем считать, что операция может вырабатывать не более одного результата. Операции будут записываться в виде:OP_NAME Ri1 Ri2 ... Rin → Rim,где Ri1 Ri2 ... Rin – регистры-аргументы операции, Rim – результат.Имя операции имеет контекстно-независимую семантику: при любых условиях, еслиоперации с одним именем подавать в соответствующие аргументы одинаковые значения,будет получаться одинаковое значение результата.Вызов процедуры осуществляется операцией CALL.тел./факс: (095) 917-24-70-3-a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------CALL Ri0 Ri1 Ri2 ...

Rin → (Rim),где Ri0 – адрес вызываемой процедуры, либо символьное имя вызываемой процедуры; Ri1Ri2 ... Rin – регистры-аргументы операции – параметры, передающиеся в вызываемуюфункцию; Rim – возвращаемое процедурой значение.Имя операции CALL имеет контекстно-независимую семантику; тем не менее, еслиоперации с одним именем подавать в соответствующие аргументы одинаковые значения,возможны различные значения результата.Работа с памятью осуществляется посредством чтения/записи объектов. Объект – этонепрерывная последовательность N байт в памяти, причём если объект записан начиная садреса X, то в диапазон адресов [X, X+N–1] другие объекты не попадают.

Таки образом,вся работа с памятью осуществляется через операции READ x→Ri1 и WRITE Ri1→x (читать значение объекта x в регистр Ri1 и записать значение в регистре Ri1 в объект x). Объекты могут быть глобальными и локальными (иметь признак глобальности/не иметь этого признака).

Глобальный объект доступен из любой процедуры программы. Локальныйобъект доступен только из процедуры, в которой он описан.Рис. 3. Код на Си – промежуточное представление.Итак, в рамках анализа нас будут интересовать только результативные операции, которые, в свою очередь, могут быть четырех типов: READ, WRITE, CALL и др.Повторим, что описанное промежуточное представление является необходимым дляпроведения анализа “Межпроцедурная нумерация значений” алгоритмом, приведенным внастоящей работе.

Вместе с тем, оно является достаточно общим, − так, всегда (почтивсегда) удаётся отобразить любое используемое промежуточное представление к вышеуказанному, без потери семантики программы.2. НУМЕРАЦИЯ ЗНАЧЕНИЙ2.1. Основные понятияНумерация значений есть технология, суть которой заключается в следующем: каждому значению, вычисляемому в программе, ставится в соответствие число, называемое“номер значения”, таким образом, что два значения получают один номер, если компилятор может доказать, что эти значения равны для всех возможных входных данных в программу [4].тел./факс: (095) 917-24-70-4-a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------Номера присваиваются значениям, но значения в программе вырабатываются операциями.

Таким образом, можно говорить о присвоении номеров значений операциям (длярезультативных операций). Операции, вырабатывающие одинаковые значения, называются эквивалентными. Такие операции получат один номер значения. Всё множество результативных операций, разбивается на подмножества – классы эквивалентности (конгруэнтности).Номера значений будут представляться целыми числами, начиная с UNDEF_VAL=−1.Номер UNDEF_VAL=−1 будет обозначать неопределённый номер, когда ничего нельзясказать о значении, которое вырабатывает операция. Две операции с одним и тем же номером, равным UNDEF_VAL, не являются эквивалентными.Функция int GetNewValNum(void) будет вырабатывать номер значения, который ещёне был использован.Сформулируем задачу анализа: имеется управляющий граф процедуры (см.

раздел 1),требуется присвоить операциям номера значений, в рамках ограничений, указанных впредыдущем абзаце.Известны различные алгоритмы для нумерации значений в процедуре. Опишем алгоритм, использующий хеширование операций.2.2. Моделирование работа с памятьюРабота с памятью на промежуточном представлении была описана в разделе 1.2 (через записи/чтения объекта). Для нужд анализа будем поддерживать структуру, моделирующую работу с памятью. Она позволит запоминать когда (в каком узле), куда (в какойобъект) и что (какой номер значения) было записано. Соответственно, когда встретитсяоперация чтения, можно будет узнать, какое значение было записано, в ближайшем узлезаписи, доминирующим узел чтения.Для работы с такой моделью будут использоваться функции:void SetObjValNum(node, obj, val_num) – запоминание того факта, что в узле nodeпроисходит запись в объект obj, значения, которое имеет номер значения val_num.int GetObjValNum(node, obj) – получает номер значения, которое было записано вобъект в ближайшем узле, доминирующем узел node.Если происходит чтение объекта, в который не было записи, то GetObjValNum возвращает UNDEF_VAL.Проблема возникает в местах слияния ветвей исполнения программы.