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

Межпроцедурный анализ указателейДроздов А.Ю, Владиславлев В.Е.Институт микропроцессорных вычислительных систем РАНsasha@mcst.ru, vladisla@mcst.ruВведениеМежпроцедурный анализ указателей [3, 4] необходим для того, чтобы уже на стадиикомпиляции программы определить возможные значения указателей, которые в нейиспользуются. Наличие такой информации помогает компилятору в определении того,какие группы операций могут выполняться параллельно. Это, в свою очередь, даетвозможность для более эффективной работы многих оптимизирующих преобразований.Отсутствие же информации о значениях указателей заставляет делать самое грубоепредположение: любые два указателя пересекаются.

Если в редких частных случаяхинформацию о значении указателей еще удается получить и без межпроцедурногоанализа, то выявить независимость пары операций, одна из которых являетсяоперацией вызова, без межпроцедурного анализа нельзя.На более формальном уровне задачей межпроцедурного анализа указателей являетсявычисление так называемой points-to функции, которая в каждой точке программы длякаждого указателя выдает множество фрагментов памяти, адреса которых в этой точкеон может содержать. Задача межпроцедурного анализа укладывается в рамки идеиабстрактной интерпретации [5]. Суть её в построении такого приближения семантикипрограммы, которое отображало бы интересующее нас свойство поведения этойпрограммы на стадии исполнения.Предлагаемый алгоритм анализа обладает такими характеристиками, как потоковаязависимость (flow-sensitivity) и контекстная зависимость (context-sensitivity) [3].

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

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

Сначала программист выражает эту семантикуна языке программирования. Затем компилятор переводит её в форму, более удобнуюдля проведения анализов и преобразований. Такая форма называется промежуточнымпредставлением. Для проведения глобального анализа указателей было выбраносмешанное контекстно-потоковое промежуточное представление. Это значит, чтопередать значение от одной операции к другой можно двумя способами. Первый(контекстный) способ заключается в том, что результат первой операции записываетсяв некоторую переменную или по некоторому указателю, а аргументом второй операцииявляется операция чтение этого объекта или по этому указателю.

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

Ниже показано (рис.1), чему в промежуточномпредставлении соответствуют основные (с точки зрения проводимого анализа)языковые выражения.Языковое выражениеp=xp = *xp = &x*p = *xp = *(x+8)Промежуточное представлениеop1 READ(x)op2 WRITE(p,op1)op1 READ(x)op2 READ(op1)op3 WRITE(y,op2)op1 OBJ_PTR(x)op2 WRITE(p,op1)op1 READ(p)op2 READ(x)op3 READ(op2)op4 WRITE(op1,op3)op1 READ(x)op2 CONST(8)op3 ADD_P(op1,op2)op4 READ(op3)op5 WRITE(p,op4)Рис.

1. Примеры соответствия промежуточного представления языковым выражениям.Аналитические структурыТеперь кратко перечислим некоторые аналитические структуры, которые необходимыдля проведения анализа. Первая из них – CFG (control flow graph или граф управленияпотоком) процедуры [1], который строится на основе промежуточного представления иотображает поведение процедуры с точки зрения потока управления.

Узлы графапронумерованы в соответствии с так называемой RPO-нумерацией (Reverse Post Order)[1], причем поддержан механизм быстрого получения узла по его номеру. Обход узловCFG в соответствии с указанной нумерацией обладает тем свойством, что обработкалюбого узла происходит после того, как обработаны все его предшественники, заисключением предшественников по обратным дугам.На основе CFG строится дерево доминаторов (Dominator-Tree) [1], которое задаетчастичный порядок доминирования на узлах CFG.

Также на основе CFG для каждогоузла строится так называемый IDF (Iterated Dominants Frontier или итерационныйфронт доминирования) [1]. Эта аналитическая структура позволяет для любого узлаCFG быстро находить все узлы схождения управления, которые достижимы из этогоузла. Это, в свою очередь, дает возможность эффективно и экономно распространять поCFG интересующее нас свойство посредством построения φ-функций в узлахсхождения управления.Ещё одна структура данных, необходимая для проведения анализу, это стек активаций[4].

С его помощью моделируется стек, который возникнет при исполнениианализируемой программы. Каждая запись этого стека содержит два поля: частичнуютрансферную функцию с информацией о points-to функции вызванной процедуры иузел CFG вызывающей процедуры, из которого произошел вызов.

В начале анализа вверхушку стека помещается ЧТФ стартовой процедуры (в случае С-программы этоmain), и нуль в качестве точки вызова. С помощью стека активаций легко определить,что функции принадлежат рекурсивному циклу: как только в процессе анализавстречается вызов процедуры, ЧТФ которой уже находится в стеке, все процедуры встеке от его верхушки до вызванной процедуры, которую назовем головой рекурсии,принадлежат рекурсивному циклу. Множество этих процедур назовем простымрекурсивным циклом (ПРЦ). Однако рекурсивный цикл, возникающий при исполнениипрограммы, может состоять не только из процедур одного ПРЦ.

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

Тогда простым рекурсивным циклом будет множество процедур,составляющих любой простой цикл в графе вызовов, а рекурсивным циклом будетмножество процедур, составляющих его сильносвязную компоненту (strong connectedcomponent, SCC).Пространство именКаждой переменной программы соответствует свой собственный фрагмент памяти. Длятого, чтобы, с одной стороны, обобщить понятие переменной, а с другой – уточнитьего, введем необходимые определения.Определение 1. Блок имен это переменная или объединение имен. Имя это блок имен,уточненный множеством локализаций.

Разные блоки имен должны представлятьнепересекающиеся фрагменты памяти.Определение 2. Множеством локализаций блока имен будем называть подмножествомножества целых чисел, которое задается парой f , s ∈ Ζ × Ν следующим образом:f , s = { f + i ⋅ s | i ∈ Z } . Первый элемент этой пары называется смещением множествалокализаций, а второй – его шагом. Множество локализаций, у которого шаг равеннулю, назовем точечным. Очевидно, что неточечное множество локализаций можетбыть задано бесконечным множеством различных пар. Поэтому для взаимнойоднозначности между множествами локализаций и парами, которые их задают,потребуем дополнительно, чтобы для пар с ненулевым шагом выполнялось условие0 ≤ f < s.Если множество локализаций имеет ненулевой шаг, это означает, что анализ не всостоянии определить, с каким именно конечным фрагментом памяти будет работатьоперация.