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

Представим,что в узле 1 мы пишем в объект x значение A, в узле 2 пишем в объект x значение B, сливаем управление от узлов 1 и 2 в узел 3 (узел слияния), а в узле 4 происходит чтение x.Какую запись считать доминирующей?Решение проблемы заключается в том, что в узлах слияния мы будем имитироватьзапись (вызовом SetObjValNum) для каждого объекта, по которому происходит слияние.Таким образом, ближайшей доминирующей записью для чтения в узле 4, будет запись вузле 3. Заметим, что так мы всегда будем получать единственную ближайшую доминирующую запись, поскольку все слияния упираются в узлы слияния, а в этих узлах строятся записи.Рассмотрим пример (рис.

4). В узле слияния будем имитироваться запись в объект x.Но какое значение будет записано: A или B? В таких случаях будет применяться принцип “слияния номеров значений”: если оба значения, имеют один номер, то этот номер ител./факс: (095) 917-24-70-5-a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------будет результатом слияния; иначе, результатом слияния будет номер UNDEF_VAL. Этотпринцип реализован в функцииint JoinValNums(val_num1, val_num2);Рис.

4. Слияние значений.2.3. Описание алгоритмаПредставленный здесь алгоритм проведения анализа нумерации значений являетсяодной из реализаций техники проведения анализа с использованием хеширования операций, предложенной в [4] (Hash Based Value Numbering).Обрабатываем узлы управляющего графа процедуры в таком порядке, при котором,узел может быть обработан только тогда, когда обработаны все его предшественники, заисключением предшественников по обратным дугам. Каждый узел может быть либо узлом слияния, либо обычным узлом.Рассмотрим сначала обработку обычного узла.

Проходим последовательно, начиная спервой, по всем операциям узла. До раздела 3 исключим из рассмотрения операциюCALL. Нерезультативные операции также пропускаем.Будем использовать две хеш-таблицы. Первая из них − ConstHash, хеш-таблица констант. Каждая запись имеет ключ и данные (в качестве данных выступает номер значения).

Ключ – это константа, которую вырабатывает операция. Вторая хеш-таблица,OpersHash – это хеш-таблица операций. Каждая запись имеет составной ключ и данные, вкачестве которых выступает номер значения. Составной ключ – имя операции и номеразначений всех её аргументов.Для операций, вырабатывающих константное значение, (например MOV 0x0 → R1;ADD 0x1 0x2 → R2) нужно лишь запоминать в хеш-таблице, какие значения константуже встречались и какие номера им были назначены. Если константа ещё не встречалась,назначаем ей любой ранее не использованный номер значения.

В любом случаем полученный номер значения присваиваем операции.Для операций чтения просто получаем номер значения, которое было записано в объект ближайшей доминирующей записью. Этот номер значения присваиваем операции.тел./факс: (095) 917-24-70-6-a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------EvalConstOper( oper){/* получаем константу – результат операции */const = GetOperConstResult( oper);/* ищем номер значения в таблице */if ( val_num is not found in ConstHash by const ){/* получаем ещё не использованный номер */val_num = GetNewValNum();/* создаём новую запись */CreateEntryWithValNumByConst( ConstHash, val_num, const);}}EvalReadOper( oper){/* получаем объект, который читает операция READ */obj = GetOperReadObj( oper);/*** получаем номер значения, которое находится в объекте* (было в объект записано) к моменту исполнения узла node*/val_num = GetObjValNum( node, obj);}Для операций записи получаем val_num = номер значения регистра-аргумента, которое мы хотим записать, и запоминаем тот факт, что в текущем узле производится записьв объект значения с номером val_num.

Номер значения присваиваем операции.Кроме того, во множество объектов каждого узла слияния из множества IDF для текущего узла нужно добавить объект (в описании обработки узлов слияния будет показано, для чего это нужно).EvalWriteOper( oper){/* получаем объект, в который пишет операция WRITE */obj = GetOperWriteObj( oper);/* получаем номер значения, которое пишет операция WRITE */val_num = GetNthArgValNum( oper, 1);/* запоминаем, что была запись в узле node */SetObjValNum( node, obj, val_num);/* "проталкиваем" объект дальше по всем IDF узла */PushObjToAllIDFs( node, obj);}Для прочих результативных операций справедливо: если у двух операций с одинаковыми именами соответствующие аргументы-регистры имеют один номер значения, тоэти операции вырабатывают одинаковый результат (в силу независимости семантикиимени операции от контекста, см.

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

Если по этому ключу есть номер значения, то его и назначаем операции. Иначе, генерируемнеиспользованный ранее номер значения, и добавляем в таблицу запись ключ-номер.Операции присваиваем этот номер.EvalOper(oper){/*** составной ключ содержит имя операции и номера значений* всех аргументов операции*/key = MakeCompoundKey(oper);/* ищем запись в хэш таблице по ключу */if (val_num is not found in ConstHash by key ){/* получаем ещё не использованный номер */val_num = GetNewValNum();/* и запоминаем этот номер значения */CreateEntryWithValNumByKey( val_num, key);}}При назначении номера значений операции может оказаться, что этой операции ужебыл назначен номер.

Тогда, если уже назначенный номер и новый номер не совпадают,назначаем неопределённый номер.SetOperValNum(oper, val_num){old_num = GetOperValNum(oper);if (old_num != UNDEF_VAL){if (old_num != val_num ){SetOperNewValNum(oper, UNDEF_VAL);/* если произошли изменения, устанавливаем флаг */is_changed = TRUE;}}}Теперь рассмотрим, как производится обработка узла слияния. С каждым таким узлом связано множество объектов, значения которых сливаются в этом узле. Каждый объект в данном множестве имеет назначенный ему номер значения.Функции для работы с таким множеством:obj_set = GetObjsSetByJoinNode( node);val_num = GetValNumInObjSetByObj( obj_set, obj);тел./факс: (095) 917-24-70-8-a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------SetValNumInObjSetByObj( obj_set, val_num);Множество формируется следующим образом.

Первоначально оно пусто. Каждыйраз, когда встречается операция записи, мы обходим все узлы, входящие в её IDF и добавляем объект, в который записываем в соответствующие множества.При обработке узла слияния обходим все объекты в указанном множестве. И для каждого объекта производим “слияние” номеров значений, приходящих от предшественников узла слияния. Получив результирующий номер значения, имитируем запись в объект, то есть вызываем SetObjValNum, тем самым запоминая факт записи результирующего номера значения в данном узле в данный объект./* === обработка узла слияния === */EvalJoinNode( node){/* обходим множество объектов, чьи значения проходят через узел */foreach( obj in objs ){/* "сливаем" приходящие значения в phi_val_num */phi_val_num = JoinValNumsFromPredecessors( obj);/* имитируем запись в объект obj значения с номером phi_val_num */SetObjValNum( node, obj, phi_val_num);/* "проталкиваем" объект дальше по всем IDF узла */PushObjToAllIDFs( node, obj);}}Алгоритм внутрипроцедурного анализа:do{is_changed = FALSE;/* обход всех узлов управляющего графа */foreach( node in graph ){if ( not all predecessors evalued )continue;if ( GetNodeType( node) == CFG_BLOCK_JOIN )EvalJoinNode( node);elseEvalCFGNode( node, &is_changed);}/* до тех пор, пока процесс не стабилизируется */} while ( is_changed );2.4.