Межпроцедурный анализ указателей. Дроздов, страница 4

Как было сказано выше,для оценки изменения, вносимого в points-to функцию обрабатываемой процедурывызовом другой процедуры, служит функция EvalCall. На рис. 6 приведен псевдокодэтой функции.func EvalCall( n, ptf){procedures = FindCallTarget(n, ptf);foreach proc ∈ procedures {bind = RecordActuals( n, proc);if ( proc ∉ CallStack ) {/* нерекурсивный вызов */tgt_ptf = GetPTF(bind, proc, n, ptf);if ( needVisit ) {push(tgt_ptf, bind, CallStack);EvalProc( tgt_ptf);pop( CallStack);}ApplySummury( tgt_ptf, bind, n, ptf);} else {/* рекурсивный вызов */tgt_ptf = GetPTFFromCallStack( proc);EvalRerursion(tgt_ptf, bind, n, ptf);}endfor;}Рис.

6. Псевдокод процедуры EvalCall , обрабатывающей операции вызова.Переменная bind служит для хранения информации о функции связываниявызывающего контексте (узла n CFG процедуры ptf.proc) с ЧТФ обрабатываемойпроцедуры proc. Функция RecordActuals служит для инициализации этой структуры иподсчета функции связывания для формальных параметров proc. Для нахождениямножества процедур, которые будут вызваны в данной точке, используется процедураFindCallTargets. При вызове по косвенности необходимо воспользоваться ужеимеющимися результатами анализа для определения возможных значений указателя,по которому происходит вызов. По этому указателю создается РП, в которомзапоминается множество процедур (в частности, пустое множество тоже), которое вданном контексте может быть через него вызвано.Для каждой из найденных процедур определяется, лежит ли ЧТФ этой процедуры встеке активаций или нет.

Если лежит, то вызов является рекурсивным, а вызваннаяпроцедура объявляется головой рекурсии. За обработку рекурсивного вызова отвечаетпроцедура EvalReсur, которая будет описана ниже. В случае нерекурсивного вызованеобходимо получить ЧТФ для этой процедуры. Возможны три случая:•В процессе анализа процедура встретилась впервые. Тогда для этой процедурысоздается новая ЧТФ и поднимается флаг необходимости обработки (needVisit=TRUE).•Процедура уже обрабатывалась и для неё существует ЧТФ (или даже несколькоЧТФ), но данный вызывающий контекст не лежит ни в одной из областей определенияэтих ЧТФ, то есть ни одна из них не может быть применена в данном вызывающемконтексте без дополнительной обработки.

Тогда, либо создается новая ЧТФ, либоберется одна из имеющихся и её область определения дополняется текущимвызывающим контекстом. Ниже этот процесс будет описан более детально. В любомслучае,поднимаетсяфлагнеобходимостидополнительнойобработки(needVisit=TRUE).•Наконец, если существует ЧТФ, область определения которой содержит данныйвызывающий контекст, то ЧТФ может быть применена к данному контексту бездополнительной обработки (needVisit=FALSE).Последним этапом обработки процедуры является собственно пополнение points-toфункции вызывающей процедуры – ApplySummary. Так как points-to функцияпроцедуры выражена в структуре присваиваний ЧТФ, необходимо в точке вызовапроцедуры создать присваивания, соответствующие изменениям, вносимым вызваннойпроцедурой.

Для каждого имени name ЧТФ вызванной процедуры (tgt_ptf), в котороебыло присваивание, собирается множество его значений в каждом из узлов выхода изпроцедуры (посредством функции GetPointsTo(name, exit_node, tgt_ptf)). Затем этимножества имен объединяются и с помощью функции связывания выражаются втерминах имен ЧТФ вызываемой процедуры (ptf). Получившееся множествоиспользуется в качестве правых частей присваиваний, которые создаются ввызывающем контексте во все имена ЧТФ ptf, которые соответствуют имени name ЧТФtgt_ptf.

Процесс выражения имен вызванной процедуры в терминах имен вызывающейс помощью функции связывания называется трансляцией.Осталось описать, как происходит трансляция присваиваний, содержащихдинамические имена. Подход, при котором существует единственное динамическоеимя (которое с точки зрения области его видимости является глобальным), не требуетдоработки описанной схемы пополнения points-to функции вызывающей процедуры.Напротив, подход, при котором динамическое имя лежит в пространстве имен толькотой ЧТФ, в которой оно было создано, требует уточнения процесса трансляции, ибопамять, описываемая этими именами, может использоваться и в вызывающем(относительно обрабатываемой процедуры) контексте.

А, следовательно, дляпредставления работы с этой памятью необходимо создать в вызывающем контекстесоответствующие динамические имена. Но делать это следует лишь для имен, работа скоторыми действительно возможна вне процедуры их создания. Множество таких именформируется следующим образом. Все имена динамического типа, которые попали вимена, возвращаемые оператором return, заносятся в это множество. Если существуетприсваивание, которое будет оттранслировано в вызывающий контекст, в правой частикоторого находится динамическое имя, оно также добавляется в формируемоемножество.

Если есть присваивание в динамическое имя, которое уже находится вформируемом множестве, то все динамические имена из правой части этогоприсваивания также добавляются в множество. Очевидно, в силу конечности числаприсваиваний в ЧТФ, этот итерационный процесс сходится.После того, как множество сформировано, в ЧТФ вызывающей процедуры по каждомуиз его имен создается динамическое имя, которые характеризуются тем же отрезкомпути в графе вызовов, что и имя-оригинал. Создание происходит лишь в том случае,когда имени с такой характеристикой в ЧТФ еще нет (иначе берется существующее).Таким образом, функция связывания пополняется соответствием междудинамическими блоками вызывающего контекста и текущей ЧТФ. И лишь после этогоосуществляет пополнение points-to функции вызывающего контекста, как это былоописано выше.Определенную сложность для предложенной схемы межпроцедурного анализапредставляют нелокальные переходы, которые в языке С, например, осуществляютсяпосредством вызова системных функций setjmp() и longjmp().

Подход к их обработкетакой: в процессе анализа процедуры запоминаются узлы CFG, в которых встречалисьвызовы этих функций. При трансляции результатов в вызывающий контекстпроисходит обход всех узлов, в которых встретилась функция longjmp(). В каждом изних, как и в узлах выхода из процедуры, собираются множества значений для всехимен, в которые были присваивания. Если в самой процедуре есть вызовы функцииsetjmp(), то в этих узлах создаются копии набранных присваиваний. Затем этомножество присваиваний транслируется в вызывающий контекст и пополняетсямножеством присваиваний вызывающей процедуры, со значениями в точке вызова.Если в вызывающей процедуре есть узлы с функцией setjmp(), то копии всехнабранных присваиваний создаются в этих узлах. Далее продолжается трансляциямножества присваиваний вверх по стеку с пополнением его присваиваниями изпроцедур в стеке со значениями в точках вызова.

При наличии узлов с функциейsetjmp(), в них создаются копии набранных присваиваний.Ниже описывается процесс выбора ЧТФ для обработки процедуры. Пусть в вызваннойпроцедуре существует набор ЧТФ (в частности, одна). Задача состоит в том, чтобысравнить текущий (новый) вызывающий контекст с областями определенийимеющихся ЧТФ. Для этого необходимо перечислить те характеристики, которыеформируют область определения ЧТФ.•Рассмотрим множество имен, которое ранее было обозначено, как NPI – это теимена, по которым алгоритм при обработке процедуры безуспешно пытался создатьРП.

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

Тогда для переиспользованияЧТФ необходимо, чтобы множество процедур, которые РП представляет в новомвызывающем контексте, было подмножеством множества процедур, сохраненных в РП.Если это не так, то ЧТФ снова неприменима.Возможен случай, когда у процедуры нет ЧТФ, подходящей для переиспользования вданном вызывающем контексте, и в соответствии с какими-то ограничениями на ихчисло нет возможности создать новую ЧТФ. Необходимо выбрать одну из множествасуществующих, область определения которой придется расширить, добавив к нейрассматриваемый вызывающий контекст. Это изменение сделает ЧТФ болееуниверсальной с точки зрения множества контекстов, в которых она применима, но,возможно, менее точной, с точки зрения тех контекстов, в которых она была примененабез обобщения. Решение о выборе носит эвристический характер и для построенияэвристики предлагается найти числовое выражение для сравнения контекстов, вкоторых ЧТФ были построены с текущим контекстом, в котором одну из нихнеобходимо будет пересчитать.Число вновь созданных РП по именам из множества NPI и число новых функций,которые добавляются к множеству процедур, приписанных РП – уже числовыехарактеристики.

Чем они меньше, тем меньше будет загрублена ЧТФ и тем быстрее онабудет пересчитана. Необходимо также учесть то, как число новых функцийраспределено по множеству РП – чем меньше РП, в которых произошло изменение, темлучше. Теперь перейдем к описанию того, как сравнивать контексты по степенипересечения РП.Пусть для некоторой процедуры существует ЧТФ ptf. В новом вызывающем контекстепо структуре этой ptf создается её копию – ptf′. Процесс этот итерационный; нижеприведены его этапы.База. На множестве блоков имен задается отношение ρ следующим образом.