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

Р. И. ИдрисовМЕТОДЫ МЕЖПРОЦЕДУРНОГО АНАЛИЗА*1. ВВЕДЕНИЕМежпроцедурный анализ относится в первую очередь к анализу потокаданных, который поступает при вызове в процедуру и из неё. Анализ используется для отслеживания передачи константных значений, данных,которые содержатся в одной ячейке, областей массивов. Такой вид анализаиспользуется для контролирования системы типов в средах разработки ипри выполнении преобразований в оптимизирующем компиляторе. Можнообойтись без межпроцедурного анализа, если осуществлять подстановкутела процедуры на место вызова (inlining).

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

Межпроцедурный анализ приобретает особую ценность в распараллеливающих компиляторах. Если не анализировать кодвызываемых процедур, придётся предположить, что все параметры и глобальные переменные могут измениться в результате вызова. Это существенно снизит эффективность результирующего кода, потому что, например,циклы, содержащие вызовы, не будут распараллелены никогда. Алгоритмымежпроцедурного анализа зачастую являются трудоёмкими. Требуется сохранить баланс между скоростью проведения анализа и эффективностьюраспараллеливания, что сейчас и демонстрируют основные распараллеливающие системы. Целью данной работы является обзор существующихметодик, выбор наиболее перспективных алгоритмов и направлений дляразвития в межпроцедурном анализе.*Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант № 07-07-12050).Идрисов Р.

И. Методы межпроцедурного анализа39При подготовке обзора использовались публикации по основным системам автоматического распараллеливания FIAT, Polaris, PIPS, Fida, Parafrase-2, RN, Parascope, PTRAN.2. ОСНОВНЫЕ МЕТОДИКИ МЕЖПРОЦЕДУРНОГО АНАЛИЗАМежпроцедурный анализ можно разбить на четыре части: анализ совмещений (alias analysis), протягивание констант (constant propagation), анализ использования переменных и анализ контекста использования. Такоеразбиение условно. Эта информация может быть вычислена для каждойпроцедуры в программе, что позволяет уменьшить объём компиляции, необходимой при изменении кода одной из процедур.

В визуальных системахпрограммирования полезно получать эту информацию как можно быстрейдля того, чтобы давать пользователю своевременные подсказки.2.1. Анализ совмещенийАнализ совмещений. (Alias Analysis) [1], [2] помогает предотвратитьпоявление неверного кода в результате оптимизационных преобразований.Например, последовательность присвоений a = 5; b = 3; c = a * b; можнооптимизировать как с = 15 при условии, что a и b нигде далее не используются, но это будет неверно, если a и b хранятся в одной ячейке памяти.

Втаком случае, после присвоения b значения 3, переменная a тоже приметзначение 3, и результат будет равен 9. Также анализ совмещений можетбыть использован в системах разработки программного обеспечения. Приразработке больших программных проектов иногда возникает необходимость изменения типа переменной или объекта, для сохранения корректности программы и исключения нежелательных конверсий типов используютанализ совмещений. Обычно выделяют три типа совмещений:1.2.Статическое совмещение (explicit aliasing) — возникает, когда двепеременные с помощью конструкций языка обозначаются как указывающие на одну ячейку памяти (например union в языке С илиequivalence в языке Fortran). Анализ таких совмещений не вызываетсложностей.Совмещение через параметры (parameter aliasing) — возникает,когда переменная передаётся в функцию в качестве нескольких изформальных параметров или выступает в качестве параметра, нотакже доступна из глобального окружения.40Методы и инструменты конструирования программ3.Динамическое совмещение или совмещение указателей (pointeraliasing) — возникает вследствие неизвестных значений переменных типа “указатель”, которые могут отвечать также за одну ячейку памяти.Рассмотрим совмещение по параметрам и динамические совмещенияболее подробно.2.1.1.

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

Не все эти совмещения могут возникать на практике, потому что алгоритм не учитывает условных переходов и различныхконтекстов вызова процедуры. В случае если в графе присутствуют контуры, можно использовать итеративный вариант алгоритма.Для демонстрации алгоритма рассмотрим следующий пример программы:Procedure p(var a,b,c,d,e: integer)BeginIf e=0 then exit;B=a+b;P(d,a,b,c,e-1);End;Begin…For i=0 to 9 doP(a[i*3], a[i*3+1], a[i*3+2], a[i*3+3],4);End.В данном примере процедура P, при входном параметре e = 4 вычисляет ряд частичных сумм (a, a + b, a + b + c, a + b + c + d). В результате работы данного участка программы каждый элемент массива будет дополненсуммой предшествующих элементов. Совмещений по параметрам в этомИдрисов Р.

И. Методы межпроцедурного анализа41случае не возникает, но если изменить вызов процедуры следующим образом:Begin…For i=0 to 9 doP(a[i*3], a[i*3+1], a[i*3+1], a[i*3+2],4);End.Возникает совмещение b и c при первом вызове. Продемонстрируемдействие итеративного алгоритма поиска совмещений. Граф вызовов дляданной программы содержит петлю в вершине, относящейся к процедуре p,алгоритм при рассмотрении каждой процедуры строит множество совмещений, которое получается при её вызове, и протягивает эти данные длявызываемых процедур. Завершение происходит, когда на каком-то из шаговне происходит изменения множества совмещений. На первом шаге анализапроцедуры множества совмещений выглядят следующим образом:a->ab->b,cc->c,bd->de->eПри анализе рекурсивного вызова процедуры множества меняются следующим образом:a->a,b,cb->a,b,cc->a,b,cd->de->eПеременная a добавляется к множеству совмещаемых переменных b и c,потому что используется вторым аргументом при вызове функции.

Алгоритм завершается после следующего шага и в результате получается, чтопервые четыре аргумента могут быть совмещены друг с другом.Этот алгоритм не является точным, поскольку не учитывает возможности вызова процедуры из различных контекстов; реального совмещениявсех аргументов при каждом вызове не происходит. Результат нужно рас-42Методы и инструменты конструирования программсматривать как множество возможных совмещений переменной. Если переменные не содержатся в одном множестве совмещений, они не могутсоответствовать одной ячейке памяти в ходе выполнения программы, а если содержатся — могут соответствовать, но не обязательно соответствуют.Можно увидеть, что результирующие множества никак не зависят от параметра e, но если задать e = 0 реального совмещения параметров a и b в ходевыполнения программы не будет, для выявления таких случаев анализ совмещений иногда объединяют с алгоритмом протягивания констант. Значения констант протягиваются вглубь графа вызова аналогично информациио совмещениях, что делает удобным объединение этих двух видов анализа[3].Вернёмся к случаю e = 4.

Если учитывать контексты вызова, можно разделить процедуру на несколько, значения совмещений для которых будутразличными, а тела — одинаковыми. Такой анализ называется контекстночувствительным.Можно заметить, что стандартный итеративный алгоритм имеет достаточное количество минусов.2.1.2. Динамическое совмещениеНаибольший интерес и сложность представляет анализ динамическихсовмещений (совмещений указателей). Информация о совмещениях по параметру действительна на всём протяжении процедуры, а динамическиесовмещения могут быть различны; они могут быть вычислены для каждогоузла (оператора) отдельно. Такой подход даёт более точные результаты, ноимеет большие накладные расходы. Его называют узловым (flow-sensitive)анализом. Динамические совмещения могут быть вычислены для процедуры в целом.

Такой алгоритм анализа менее точен, но осуществляется с гораздо меньшими затратами (flow-insensitive alias analysis). Как и в случаесовмещений по параметру, алгоритмы могут быть чувствительны к путиисполнения (context-sensitive). Такие алгоритмы в русскоязычной литературе называются контекстно-чувствительными. Нечувствительные к путиисполнения алгоритмы дают большой выигрыш в скорости анализа, ониисполняются за линейное время, это объясняет их большую распространённость.Реализовать алгоритм можно при помощи alias-переменных, которыесопоставляются также всем переменным, с которыми данная переменнаяможет быть совмещена в ходе выполнения программы.