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

Доказательство корректности. Оценка сложностиПокажем, что алгоритм всегда завершает свою работу. В течение одной итерациианализа могут быть обработаны не все линейные участки: обработаны будут только теузлы, у которых уже обработаны все предшественники, не считая предшественников пообратным дугам. Когда операция обрабатывается, ей назначается какой-либо номер значения. После того, как операции назначен неопределённый номер значения, он измениться уже не может.

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

Значит, число итераций ограничено не может быть больше, чем удвоенноечисло операций в процедуре. Мы получили верхнюю оценку числа итераций. Но этоочень грубая оценка; для более точной оценки обратимся к [4].Алгоритм внутрипроцедурного анализа, который был приведён выше – это, по существу, модификация алгоритма (SSA-based value numbering with hashes), предложенного в[4]. В том алгоритме вводятся псевдооперации – ϕ-функции, имеющие аргументами значения объекта с разных ветвей управления, которые претерпевают слияние в этой ϕфункции.

Для алгоритма в [4] приводится и формально доказывается оценка сложностиO(S×D), где S – это число операций в процедуре плюс число ϕ-функций. D – это среднийуровень вложенности циклов; это число в любом случае не превышает S, но на практикеограничено небольшой константой.Ключевое различие между нашим алгоритмом и алгоритмом в [4] состоит в том, что валгоритме, представленном в [4], предполагается введение псевдоопераций ϕ-узлов и этипсевдооперации со своими аргументами – объектами, для которых происходит слияниезначений – уже построены. В нашем алгоритме вместо псевдоопераций используютсяузлы слияния управляющего графа.

И множество объектов, претерпевающих слияние,строится во время обхода, когда во время обработки операций записи мы обходим всеIDF текущего узла. Число IDF для узла ограничено средней ветвистостью управляющегографа (число последователей или преемников у узла в среднем по всему графу). Такоечисло ограничено небольшой константой. К тому же обход по всем IDF достаточно провести всего один раз во время первой итерации анализа. Поэтому сложность алгоритмавнутрипроцедурного анализа, представленного в данной работе, не хуже сложности алгоритма, представленного в [4]: O(S×D).3. МЕЖПРОЦЕДУРНЫЙ ОБХОД3.1.

Общие положенияОсновная идея межпроцедурного обхода заключается в том, что мы проводим анализдля всех возможных в программе ветвей исполнения, как будто срабатывают все вызовыв программе. Нам понадобится поддерживать стек вызовов. Начинаем обход с процедуры Main. Перед тем, как начать обход, помещаем процедуру в стек. Производим обходопераций процедуры, как это было описано в разделе 2. Если встречается операцияCALL, помещаем в стек вызываемую процедуру, и начинаем её обход. После того, какобход вызываемой процедуры завершён, извлекаем процедуру из стека и продолжаемобход исходной процедуры с операции, следующей за CALL. Когда из стека будет извлечена последняя процедура (это должна быть процедура Main), межпроцедурный обход окончен.Использование стека позволит обнаружить рекурсивные вызовы процедур.

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

Случай, когда в языке программирования, имеется возможность вызова процедуры по адресу, и заранее неизвестно какая процедура будет вызвана,будет рассмотрен в конце раздела.3.2. Передача параметров и возврат значенияЕсли игнорировать факт передачи параметров из процедуры в процедуру и возможный возврат значения из процедуры, то, по существу, будет проведён внутрипроцедурный анализ для определённого множества процедур. Это означает, что пропадёт смыслмежпроцедурного обхода. Поэтому следует поддерживать специальную структуру данных, в которую будут записаны номера значений параметров, которые известны к моменту вызова. При внутрипроцедурной нумерации значений в вызываемой процедуреэти номера значений будут являться инициализацией для локальных переменных, соответствующих параметрам.В ходе внутрипроцедурного обхода может встретиться операция RET – возврат значения из процедуры.

Эта операция может встретиться только в стоповом узле. Обработкатакой операции будет заключаться в том, что в специально структуре будет запомненномер возвращаемого значения. Этот номер будет являться номером значения операцииCALL вызывающей процедуры.Рис. 5.

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

Совокупность в) и г) называется эффектом вызова. Название ЧТФ заимствовано нами из [5]. ЧТФ показывает, какойбудет реакция вызываемой процедуры (какие значения в какие объекты запишутся) назаданный контекст вызова.Помимо того, что ЧТФ – это средство передачи информации в вызываемую процедуру и обратно, это также позволит нам в определённых случаях экономить ресурсы, избегая избыточных обходов процедур. Действительно, если для некоторого контекста вызова ЧТФ уже подсчитана, то обход вызываемой процедуры необязателен, ведь эффектпроцедуры на заданный контекст уже известен (а значит, был когда-то вычислен, значитобход процедуры уже проводился и номера значений вызываемой процедуры уже расставлены).3.4. Вызовы по адресу процедуры.

Рекурсивные вызовыПредставим ситуацию, когда может происходить вызов процедуры по адресу. Тогдана этапе компиляции, вообще говоря, заранее неизвестно какая именно процедура вызывается. Эта проблема будет решаться заменой операции вызова по адресу на последовательность из явных операций вызова для множества процедур, которые потенциальномогут в данной точке быть вызваны. В худшем случае во множество попадут все процедуры программы. Существуют методы (например, анализ указателей) позволяющие этомножество сократить.Рис.

6. Устранение вызовов по адресу.Если вызываемая процедура уже присутствует в стеке вызовов, то нам придётсяиметь дело с рекурсивным вызовом. Чтобы избежать бесконечных циклов в межпроцедурном обходе, нужно такие вызовы идентифицировать и обрабатывать особым образом.А именно, каждому объекту в эффекте ЧТФ запишем неопределённый номер значения.EvalCall( oper){if ( IsRecursiveCall( oper) ){EvalRecursiveCall( oper);return;}context = PrepareCallContext( oper);if ( MatchingPTFExists( context) == FALSE ){EvalProcValNum( callee_proc);тел./факс: (095) 917-24-70- 12 -a88@narod.ru; http://a88.narod.ruООО "ИНТЕРСОЦИОИНФОРМ"*** КОМПЬЮТЕРЫ В УЧЕБНОМ ПРОЦЕССЕ *** № 5, май 2005 ***--------- СТРАННЫЙ СПЕЦИАЛЬНЫЙ ЖУРНАЛ ДЛЯ ПЫТЛИВЫХ УМОВ ЛЮБОГО ВОЗРАСТА---------}return;}4.

ПРИМЕНЕНИЕ РЕЗУЛЬТАТОВ АНАЛИЗА “МЕЖПРОЦЕДУРНАЯНУМЕРАЦИЯ ЗНАЧЕНИЙ”4.1. Удаление избыточных вычисленийОдно из очевидных применений результатов нумерации значений – это удаление избыточных операций.Действительно, если две операции получили один номер значения, то это означает,что они вырабатывают одно и то же значение.

Это доказано анализом уже на этапе компиляции. В таком случае будем говорить, что операции эквивалентны. Одна из операцийявляется избыточной: её можно удалить и все использования её результата заменить наиспользование результата эквивалентной операции.Рис. 7. Удаление избыточных вычислений.4.2. Инлайн-подстановки процедурИнлайн-подстановка процедур позволяет улучшить время исполнения скомпилированных программ, но при этом увеличивается размер исполняемого кода. Обычно алгоритм инлайн-подстановок старается найти компромисс, при котором достигается выигрыш производительности и увеличение размера исполняемого кода остаётся в разумныхпределах. Задают некую эвристическую оценку, показывающую максимально допустимое приращение размера программы в процентах.При заданном пороге приращения размера кода программы, чем больше подстановокбудет произведено (с приоритетом для более вероятных вызовов), тем эффективнее получится код.Под размером процедуры будем понимать число операций этой процедуры.