Межпроцедурный анализ указателей. Дроздов (1157404), страница 5
Текст из файла (страница 5)
Каждыйблок имен глобального или формального типа находятся в отношении с самим собой.Далее, это отношение итерационно пополняется парами нелокальных блоков, причемпервый элемент каждой такой пары из ρ будет нелокальным блоком ЧТФ в новомконтексте ptf′, а второй – нелокальным блоком существующей ЧТФ ptf. Кроме того,создается множество имен, называемое рабочим множеством, в которое помещаютсявсе те имена формального и глобального типа, по которым в ptf были созданы РП.Шаг. По именам из рабочего множества алгоритм пытается создать РП в ptf′.Возможно, что по некоторым из этих имен создать РП в новом вызывающем контекстенельзя, ибо они ничего в нем не представляют.
Если же РП удалось создать, емусопоставляется нелокальный блок, исходя из значения функции связывания на этом РП.А множество значений функции связывания на нелокальном блоке пополняетсязначениями созданного РП. Если в ptf′ и ptf существуют РП по именам, блоки которыхнаходятся в отношении ρ, а множества локализаций равны, то пара нелокальныхблоков, поставленных им в соответствие, добавляется в отношение ρ. После чегопроисходит очистка рабочего множество имен, для того, чтобы сформировать егозаново. Теперь в него войдут имена ЧТФ нового контекста ptf′.Для формирования рабочего множества рассматриваются все имена ptf, созданные понелокальным блокам, которые являются вторыми элементами только что добавленныхв отношение ρ пар. Для каждого такого имени name рассматривается множество всехимен ptf′, которые созданы на основе нелокальных блоков, находящихся в отношенииρ с блоком имени name, и имеющие то же множество локализаций, что и name.Объединение таких множеств для всех указанных имен из ptf и составляет новоерабочее множество.Если в процессе вычисления функции связывания её значение изменилось хотя бы дляодного нелокального блока, то шаг повторяется для всех тех пар блоков, которые былидобавлены в ρ на текущем шаге.Решение.
Когда процесс создания копии ЧТФ для нового вызывающего контекстаокончен, необходимо, как и в случае обработки процедуры, провести процессканонизации нелокальных блоков ptf′. Объединение нескольких нелокальных блоков водин должно найти свое отражение в структуре отношения ρ. После этогорассматривается двудольный граф, узлами которого являются нелокальные блоки, адуги отображают наличие пары блоков в построенном отношении. Если существуетузел, соответствующий нелокальному блоку ptf′, степень которого больше единицы,это означает, что некоторые РП ptf, которые раньше представляли непересекающиесямножества имен, в новом контексте представляют пересекающиеся.
А значит ptf неможет быть применима без пересчета в новом контексте.Следует заметить, что если некоторая ЧТФ была выбрана для переиспользования илипересчета в контексте, в котором не все из её РП, представляют имена вызывающегоконтекста, то такие РП не удаляются и имена, по которым они были созданы, непереводятся во множество NPI. Вместо этого таким РП функция связывания ставит всоответствие пустое множество. Таким образом, число РП любой ЧТФ никогда неуменьшается.С помощью построенного графа можно вывести числовую эвристику для оценкистепени близости нового контекста к области определения имеющейся ЧТФ. Например,это может быть средняя степень узлов графа, соответствующих РП воссозданной ЧТФptf′. Если, наоборот, существует несколько ЧТФ, подходящих для переиспользования вновом контексте, то схожим образом можно оценить, применение какой из них в новомконтексте будет давать наименее грубый результат.
Для этого можно рассмотреть ту жеэвристическую функцию, но на узлах, соответствующих РП существующей ЧТФ ptf.Далее приведено описание того, как обрабатывается рекурсивный вызов – процедураEvalRecur(). Первая проблема, которая возникает при рассмотрении рекурсии, связана стем, что в некоторых случаях правило, по которому определяется, что значения двухуказателей пересекаются, нуждается в уточнении. В нерекурсивном случае дляопределения этого факта достаточно было выяснить: пересекаются ли в вызывающемконтексте множества имен, которые они представляют. В случае рекурсии это не так.Рассмотрим следующий пример (рис. 7).void recurse (struct ListN *tail) {struct ListN head, *tmp;head.next = tail;if ( condition ) {recurse( &head);}tmp = &head;while( tmp != NULL ) {tmp->data=0;tmp = tmp->next;}}Рис.
7. Пример рекурсии, для которой определениепересечения требует глобализации имени.Если не вносить никаких изменений в существующую схему, то обработкарекурсивного вызова каждый раз будет создаваться новое нелокальный блок дляпредставления локальной переменной head из очередной активации процедуры recurse.Строго говоря, несмотря на то, что все эти нелокальные блоки, в конечном счете,представляют фрагмент памяти, соответствующий одной и той же переменной, онидействительно не пересекаются. Но так как статически алгоритм не может делатьникаких утверждений о глубине рекурсии, число нелокальных имен будетнеограниченно расти и на каждой итерации цикла значение указателя tmp будетпредставлено уникальным нелокальным именем.
Для того, чтобы избежать этойситуации и обеспечить сходимость алгоритма, предлагается следующий подход:разным локальным переменным, соответствующим разным активациям процедурысопоставляется один и тот же блок имен. Тогда в приведенном примере нелокальноеимя пересекается с локальным. Однако для того, чтобы определить, что эти блоки именпересекаются, необходимо выразить все нелокальные имена в терминах именпрограммы (тех, которые не являются нелокальными).
Для этого производится такназываемая глобализация: все локальные и формальные имена процедур рекурсивногоцикла делаются глобальными в рамках этого рекурсивного цикла. Это достигаетсяпосредством приписывания им нового циклового типа. Цель этого – сделать всеприсваивания в имена нового типа видимыми во всех процедурах цикла.В результате работы анализа ЧТФ любой процедуры из рекурсивного цикла должнасодержать информацию о том, как цикл в целом меняет points-to функциювызывающего (относительно всего цикла) контекста.
Поэтому алгоритм анализавынужден совершать итерации по процедурам цикла до тех пор, пока ЧТФ каждой изних не перестанет изменяться. Однако подобный итерационный процесс требуетбольших временных затрат. Решение, которое предлагается в этой работе, состоит втом, чтобы рассматривать весь рекурсивный цикл как единую процедуру и вычислятьдля неё единственную ЧТФ, содержащую информацию о points-to функции всехпроцедур цикла. Такую ЧТФ будем называть ЧТФ рекурсивного цикла.Этот подход не требует разделения вызывающих контекстов на рекурсивные инерекурсивные, не требует держать несколько функций связывания, не требуеттрансляции результатов анализа из рекурсивного контекста внутрь цикла, а такжеускоряет сходимость.
Кроме того, с помощью рекурсивного цикла можно создатьтакую же ситуацию, что возникает при обработке внутрипроцедурного цикла:неограниченный рост имен одного блока. Предложенный подход позволяет не вводитьнового межпроцедурного оператора расширения значений в головах рекурсивногоцикла, а уложить решение в существующую схему.Еще одна сложность в обработке рекурсивных циклов состоит в том, что заранеенеизвестно, какие именно процедуры будут составлять рекурсивный цикл.
Этоопределяется «на лету» во время работы алгоритма. Начиная обрабатывать процедуру,алгоритм не знает, окажется она рекурсивной или нет.Как только в процессе анализа обнаруживается рекурсивный вызов, все ЧТФ,находящиеся в стеке активаций от его верхушки до головы рекурсии изымаются, исоздается ЧТФ рекурсивного цикла, в которой фиксируется множество процедур,входящих в этот цикл. Пусть, для начала, все изъятые ЧТФ были построены дляпроцедур.
Созданная ЧТФ помещается в стек активаций и начинается обработкапроцедуры, являющейся текущей головой рекурсивного цикла. Если встречается вызовпроцедуры, принадлежащей рекурсивному циклу, то вместо того, чтобы считатьфункцию связывания, создается присваивание в рамках этой же ЧТФ в цикловыеимена, соответствующие параметрам процедуры тех значений, с которыми былавызвана процедура и начинается обработка вызванной процедуру. При этом создаютсяприсваивания в той же ЧТФ. Если же встречается вызов процедуры не из цикла, онобрабатывается обычным образом (как было описано выше).
Если же при обнаружениирекурсивного цикла в стеке активаций от верхушки до головы рекурсии содержатсяЧТФ, построенных не только для процедур, но и для рекурсивных циклов, необходимообъединить их в одну ЧТФ. Для этого выбирается некоторая ЧТФ рекурсивного цикла,которая пополняется множеством процедур, входящих в текущий элементарныйрекурсивный цикл и во все рекурсивные циклы, ЧТФ которых находятся в стеке.
А кпространству цикловых имен добавляются имена, созданные по локальным иформальным переменным всех этих процедур.Настройки анализаПриведенная схема анализа во многих случаях даёт достаточно точный результат.Однако при обработке больших программ такая схема требует затрат за времявыполнения анализа. Ниже описываются те подходы, которые позволяют путемснижения точности проводимого анализа существенно снизить временные затраты.•Отказ от различных имен одного блока. Это предполагает, что множестволокализаций любого имени является максимальным. Такое решение, кроме того, чтоэкономит память в структурах приваиваний, позволяет существенно ускорить операциис множествами имен.•Отказ от чувствительности анализа к управлению процедуры (или flowinsensitive версия анализа). Это означает, что все присваивания происходят в стартовомузле CFG процедуры.
Нет необходимости вычислять φ-функции и любое присваиваниесразу же становится видимым в каждой точке процедуры. Такой подход существенноуменьшает число итераций по процедуре, необходимых для вычисления points-toфункции в текущем вызывающем контексте. В ЧТФ для рекурсивного цикла также всеприсваивания производятся в одной точке.•Моноверсия анализа – для каждой процедуры создается только одна ЧТФ,которая при необходимости обобщается для новых вызывающих контекстов.
Это даетзначительную экономию памяти и не требует сравнения текущего вызывающегоконтекста с областью определения существующих ЧТФ, что позволяет ускоритьпроведение анализа.Так как ЧТФ рекурсивного цикла содержит информацию обо всем цикле, её пересчетвесьма критичен по скорости анализа. Ниже приводятся ситуации, которые заставляютпересчитывать ЧТФ рекурсивных циклов и указываются способы избежать этого.Число процедур, которые могут являться входами в рекурсивный цикл, бывает весьмавелико. Каждый раз, когда алгоритм попадает на обработку рекурсивного цикла черезновый вход, необходимо, вообще говоря, заново пересчитать его ЧТФ, так как еще невозникала ситуация, когда формальные параметры этой процедуры представляли бычто-либо в вызывающем контексте (вызывающем – относительно всего цикла). Однакоможем считать, что любая процедура рекурсивного цикла может быть входом в этотцикл и уже при первой обработке создать присваивания в текущем (для всегорекурсивного цикла) вызывающем контексте, которые каждому формальному имениЧТФ поставят в соответствие фиктивные имена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
