Методы межпроцедурного анализа. Идрисов, страница 2

Таким образомстроятся классы эквивалентности. Здесь усматривается аналогия с анализомсовмещений по параметрам, только для сбора данных о возможных совме-Идрисов Р. И. Методы межпроцедурного анализа43щениях нужно проанализировать не только вызовы процедур, но и их код.В случае присутствия операций именования/разыменования вводятся дополнительные фиктивные переменные.Int *b,*c, *d, e;b=&c;e=*d;d=b;В данном случае совмещаются *b и c, *d и *b, для *d и &c будут созданы дополнительные фиктивные переменные.

Динамические совмещенияможно анализировать при помощи итеративного алгоритма, аналогичногоалгоритму анализа совмещений по параметру, описанного в 2.1.1. Различиязаключаются в определении наличия совмещения, например:Int a[20],*p, i;p=&a[0];For (i=0;i<10;i++) {*p=i*5;p++;}В данном случае при выполнении программы указатель p будет совмещён с первыми 10 элементами массива a, простой анализ совмещений укажет только на первый элемент, а более сложный, но не учитывающий значения констант/границ циклов покажет на возможное совмещение указателя p со всеми элементами массива.

Анализ получается более сложным, еслипытаться точно вычислить совмещения в случаях прямого изменения указателя p. В случае, если к значению указателя добавляется число, котороепрограмма получает в качестве входных данных, или случайное число, совмещения не могут быть вычислены точно на этапе статического анализа.Это не единственный случай, в котором невозможно точно вычислить множества совмещений, как и для совмещений по параметру наличие переменной во множестве указывает только на возможное совмещение в ходе выполнения программы, но не на обязательное.

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

Это производится для контроля типов. Например:44Методы и инструменты конструирования программInt a,b,c,d;A=5;B=7;C=a+b;D=c*b;При изменении типа переменной c на real желательно изменить тип переменной d для того, чтобы избежать нежелательной конверсии типов. Такой анализ не является анализом совмещений в чистом виде, но называетсятак же. Алгоритмы в этом случае классифицируются как отождествляющие (unification-based), для которых наличие присвоения y = x в теле программы вызывает отождествление вершин y и x в графе совмещений(points-to graph), и «не отождествляющие» (subset-based) алгоритмы, длякоторых аналогичный случай создаёт зависимость y ∈ x в графе совмещений. Обычно отождествляющие алгоритмы хранят информацию о совмещениях в виде множеств, alias- переменных или пар возможных совмещений, построение ориентированного графа совмещений характерно для неотождествляющих алгоритмов.

Эта информация позволяет проследить цепочку получения значения другого типа. Отождествляющие алгоритмы дают более грубый результат, но исполняются за линейное время. «Не отождествляющие» имеют полиномиальную сложность O(n3) [7], но предоставляют гораздо более детальную информацию о совмещениях переменной. В системах визуального программирования предпочтительно использование «не отождествляющих» алгоритмов, поскольку по такой информации пользователю будет гораздо проще ориентироваться в динамическихсовмещениях, возникающих в коде программы. В системах, которые предназначены для анализа больших объёмов кода, иногда используются индексированные базы данных [2] для хранения межпроцедурной информации ибыстрого доступа оптимизирующих алгоритмов.2.2.

Распространение константВ некоторых случаях значения или множество возможных значенийпеременных может быть определено на стадии компиляции программы.Строго говоря, множество значений переменной всегда ограничено её типом и может быть определено на стадии компиляции, но в данном изложении будем считать, что множество значений переменной в таких случаях неопределено. Рассмотрим следующий пример:Идрисов Р. И.

Методы межпроцедурного анализа45Procedure P(var a,b:integer);BeginIf a<50 then exit;b=a+b;End;…Begin…i=5;P(i,j);…For i=1 to 20 doP(i,j);End.В этом примере процедура всегда вызывается с параметром a < 50, и,следовательно, может быть полностью удалена, потому что суммированиеb = a + b не выполняется никогда. В случаях, когда значение переменнойможет быть определено на стадии компиляции, используется следующаяметодика:Распространение констант (constant propagation) — распространениеинформации о возможных значениях переменной внутрь процедуры, осуществляемое на стадии компиляции. В случае, когда значение единственное, осуществляется замена переменной её значением в теле процедуры[4, 5].Информация о значениях используется при анализе индуктивных переменных, границ и шагов циклов. Через границы циклов могут быть определены используемые области массивов [6]. В работах PIPS информация овозможных значениях переменной называется начальными условиями (preconditions) и вычисляется для каждого из анализируемых контекстов.

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

Преобразо-46Методы и инструменты конструирования программватель — функция, определённая для каждого изменяемого параметрафункции, определённой в языке программирования, преобразующая множество значений параметра до выполнения функции во множество возможных значений после её выполнения. Начальные условия для следующей изпоследовательно исполняемых команд получаются в результате действияпреобразователя предыдущей команды на начальные условия для неё.

Например, если задано начальное условие i > 0 для операции i = i + 1, тогданачальные условия для следующей операции будут i > 1. Начальные условия распространяются в прямом направлении, а преобразователи — в обратном.Простейший алгоритм анализа начальных условий и преобразователей,при отсутствии в графе вызовов циклов, можно осуществить в два прохода.На первом (обратном) проходе можно получить все преобразователи, затемна втором (прямом) проходе получить все начальные условия.

Конечно,здесь не имеется в виду, что преобразователи вычисляются точно, это невсегда возможно, потому что в точную функцию преобразователя войдутпараметры, которые невозможно вычислить на стадии компиляции, и самафункция будет являться срезом процедуры относительно параметра [7].Для распространения констант можно использовать итеративный алгоритм, аналогичный 2.1.2, основные отличия алгоритмов, используемых воптимизирующих компиляторах, заключаются в представлении множествавозможных значений переменной.1) значения переменных представлены с помощью единственногозначения, если такое может быть вычислено,2) значения переменных представлены в виде интервала, например[0, 9] — означает, что переменная может принимать значения внутри этого интервала,3) значения переменных представлены в виде множественных интервалов,4) значения переменных представлены в форме kx + b с заданным шагом k, смещением b и диапазоном изменения х в виде интервала;Также должна быть определена операция объединения двух множествзначений переменной и преобразователи для функций языка.Иногда распространение констант объединяют с анализом совмещений,называя протягиванием межпроцедурной информации, а остальную частьмежпроцедурного анализа — анализом использования данных.

Особуюважность распространение констант имеет вследствие того, что границыИдрисов Р. И. Методы межпроцедурного анализа47массивов отсчитываются по границам изменения индексных переменных,которые могут быть переданы внутрь процедуры в качестве параметра.2.3. Анализ использования переменныхПри анализе процедуры нам будут интересны четыре множества переменных:1) READ — множество переменных, используемых для чтения в телеподпрограммы,2) WRITE — множество переменных, используемых для записи в телеподпрограммы,3) IN –множество используемых для чтения внешних переменных ипараметров процедуры,4) OUT — множество переменных, вычисляемых и записываемых впроцедуре, используемых последующем коде.Первые три множества могут быть получены при анализе тела подпрограммы и вызываемых ею подпрограмм, а четвёртое множество — толькопутём анализа всего кода, который исполняется после процедурного вызова.