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

Множество локализаций вида 0,1 будем называть максимальным, ибо оноописывает всю возможную память некоторого блока имен.Теперь описание того, как операции некоторой процедуры работают с памятью, можноосуществлять с помощью имен или их объединения (блоков имен). Множество всех техимен, с которыми работают операции процедуры, назовем пространством имен этойпроцедуры. Из определения следует, что каждой переменной соответствует некоторыйблок имен, и что разным переменным соответствуют разные блоки. Каждому блокуимен соответствует определенный тип. Если блок имен это переменная, то типнаследуется от этой переменной следующим образом:•формальный тип –приписывается блоку, который есть переменная –формальный параметр процедуры;•локальный тип – приписывается блоку, соответствующему локальнойпеременной процедуры;•глобальный тип − приписывается блоку, соответствующему глобальнойпеременной.Однако не вся память, с которой работает программа, соответствует какой-топоименнованой переменной.

Для единообразия описания работы с памятью введем ещеодин тип:•динамический тип – приписывается блоку имен, через который происходитработа с памятью, выделенной одной из процедур захвата памяти malloc(), calloc(),realloc()…Все вышеперечисленные типы блоков имен будем называть пользовательскимитипами. Для наглядности, в соответствии с [3], приведем следующую таблицу (рис.2), вкоторой указано, чему во введенных терминах соответствуют некоторые языковыеконструкции.Типtype *pstruct {type *F;}rtype *a[i]type *p;struct {type *F[];} rstruct {type *F;} a[]ВыражениеPr.Fa[i]*(p op X)r.F[i]a[i].FСоответствующее имя[p,<0,0>][r,<f,0>][a,<0,s>][p,<0,1>][r,<f(mod s),s>][a,<f,s>]Рис. 2.

Пример того, в какие имена переходят языковые выражения.f – смещение поля F от начала структуры.s – размер элемента структуры.Два имени пересекаются [одно имя содержит другое], если это имена одного блока имножества их локализаций пересекаются [множество локализаций первого содержитмножество локализаций второго]. Объединением двух имен одного блока будемназывать минимальное имя, которое содержит оба исходных имени.

В большинствеслучаев объединение двух имен в смысле данного выше определения, будет содержатьимена, которые не принадлежали ни первому, ни второму имени. Поэтомупредставление используемой памяти в виде имен часто является неточным, однако онопозволяет совершать теоретико-множественные операции (объединение, пересечение,разность …) с потенциально бесконечными множествами за время, не зависящее отразмеров конкретных множеств (другими словами, за константное время).Частичная трансферная функцияТрансферная функция процедуры отражает поведение этой процедуры в зависимостиот той точки, в которой она была вызвана. Далее точку вызова процедуры будемназывать её вызывающим контекстом. Частичная трансферная функция процедуры(ЧТФ) (Partial Transfer Function, PTF [2]) отражает её поведение только на некоторомподмножестве вызывающих контекстов.

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

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

Нелокальные блокиимен, как и любые другие, должны удовлетворять тому требованию, что два различныхблока имен представляют непересекающиеся фрагменты памяти. Каждому РПсоответствует ровно один нелокальный блок. Если значения, представляемые какимито расширенными параметрами, пересекаются, то им должен соответствовать один итот же нелокальный блок. Для демонстрации введенный понятий, рассмотрим пример(рис. 3).Примерint x, y, z, *p, *q;int foo( int **par1,int **par2){int *swap = *par1;*par1 = *par2;*par2 = swap;}main(){if ( cond )q = &y;p = &x;elseq = &x;p = &z;Связывающая функция для процедуры foo( )объекты ЧТФзначение ф-циисоответствиесвязыванияРП → НЛБРП(par1){p}N0РП(par2){q}N1РП(name1){x, z}N2РП(name2){x, y}N2N0{p}РП(par1)N1{q}РП(par2)N2{x, y, z}РП(name1),РП(name2)foo(&p, &q);}Рис.

3. Пример, демонстрирующий понятия РП, нелокального блока (НЛБ)и функции связывания на них.namei – имя блока Ni, i=1,2,Кроме уже описанного свойства ЧТФ (отображать вносимые процедурой изменения вpoints-to функцию вызывающей процедуры в зависимости от вызывающего контекста),она обладает также и еще одним свойством: содержать информацию о points-toфункции той процедуры, для которой она построена. Выражена эта информация в такназываемой структуре присваиваний, описанию которой посвящен следующий раздел.Анализ одной процедурыДля нужд анализа произведем дополнительное разбиение CFG процедуры так, чтобыкаждый узел CFG содержал не более одного присваивания, не более одной операцииCALL, а узлы схождения управления не содержали бы никаких операций.

ФункцияEvalProc, отвечающая за обработку одной процедуры, получает на вход ptf – ЧТФпроцедуры. Суть обработки заключается в итерации по узлам CFG процедуры всоответствии с RPO-нумерацией до тех пор, пока points-to функция этой процедуры вданном вызывающем контексте не будет окончательно вычислена. Ниже приведенпсевдокод этой процедуры (рис. 4.), после которого даны необходимые пояснения.func EvalProc( PTF ptf) {do {changed = FALSE;foreach node n ∈ ptf.proc.cfgif ( n is assignment )EvalAssign( n, ptf);else if ( n is join )EvalJoin( n, ptf);else if ( n is call)EvalCall( n, ptf);endfor;} while (changed);}Рис. 4.

Псевдокод процедуры EvalProc.Обработка отдельной записи, осуществляемая процедурой EvalAssign, состоит изопределения тех имен, в которые может производиться запись (имена левой части), имножества имен, указатели на которые могут быть записаны в имена левой части (этоимена правой части); для определения этих множеств служит процедура EvalExpr,описанная ниже. Когда эти множества определены, создаются отношения, называемоеприсваиваниями, которые ставят в соответствие каждому имени из множества именлевой части всё множество имен правой части. Эти присваивания привязываются кузлу n CFG процедуры. Присваивания в каждое имя организованы в виде отдельногодерева, узлами которого являются все те узлы CFG, в которых была запись в это имя.Расположение узлов в этом дереве соответствует отношению доминирования, чтопозволяет эффективно искать ближайший доминирующий узел с присваиванием вданное имя. Если было создано новое присваивание с непустой правой частью, или жепроизошло пополнение правой части уже имеющегося присваивания, то поднимаетсяфлаг changed, который сообщает о необходимости новой итерации по процедуре.С помощью IDF находится множество узлов схождения управления в CFG, которыедостижимы из данного узла n и в эти узлы распространяется информация о том, что вданное имя было присваивание.

Когда в процессе очередной итерации алгоритмдоходит до обработки узла схождения управления, в нем уже сосредоточенаинформация о тех именах, для которых необходимо вычислить φ-функции. Вычислитьφ-функцию для некоторого имени name означает создать присваивание в это имя справой частью, равной объединению множеств правых частей присваиваний в name вкаждой из веток управления, сходящихся в данном узле.Вообще говоря, число имен одного блока может быть бесконечным. Если в циклепроисходит обход массива путем прибавления к указателю константы на каждойитерации, то на каждой же итерации будет появляться новое имя, отличающееся отпредыдущего смещением в его множестве локализаций.

Для сходимости этогоитерационного алгоритма необходимо произвести расширение значений присваивания[3]. Суть его состоит в том, что в голове каждого цикла, куда в виде φ-функцийстекается информация обо всех присваиваниях цикла, создаются присваивания, укоторых в правой части содержится не более одного имени каждого блока имен. Еслиимен больше, то они заменяются именем, которое содержит все имеющееся; такое имявсегда существует, так как имя с максимальным множеством локализаций содержит всеимена данного блока.Обработка выражения (EvalExpr) позволяет определить те множества имен, с которымиимеет дело EvalAssign. Как было сказано при описании промежуточногопредставления, каждое выражение имеет структуру дерева. Обходя рекурсивно деревоопераций, алгоритм каждой его вершине сопоставляем множество имен. Листовымиоперациями дерева выражения могут быть только следующие операции:•CONST; предполагается, что константа не может быть адресом никакого имени.Поэтому этой операции сопоставляется пустое множество имен.•OBJ_PTR(name); такой операции ставится в соответствие множество изединственного имени name.•READ(name); множество, которое следует поставить в соответствие этойоперации, зависит не только от name, но и от узла CFG, в котором находится операция.Для вычисления этого множества используем процедуры GetPointsTo(name,n,ptf).GetPointsTo(name,n,ptf) служит для получения в некоторой точке программы, а именнов узле n CFG процедуры ptf.proc, множества значений некоторого имени name.Принцип её работы таков: рассматривается структура присваиваний в данное имя nameв обрабатываемой процедуре.