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

Наличие же подобной информацииможет привести к более точной работе некоторых оптимизаций.Тем не менее, не следует рассматривать информацию о том, с какими фрагментамипамяти работает операция, как безусловное уточнение унаследованной информации.Ниже приведен пример (рис. 8), который показывает, что информация опользовательских именах в операции может давать более консервативный ответ озависимости между операциями.int a, b;voidh(void){f(&a, &b);f(&b, &a);}voidf(int*p, int*q){g(p, q);}voidg(int *par1, int *par2){*par1=0;*par2=0;}Рис. 8.

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

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

Множество вершинполучившегося графа взаимнооднозначно со множеством ЧТФ, которые былипостроены в процессе проведения анализа. Получившийся граф являетсяациклическим. В узел этого графа, который соответствует ЧТФ главной процедурепрограммы не входит ни одна дуга. Начиная с этого узла, на графе проводится RPOнумерацию. После чего запускается процедура InheritUserNames (её псевдокодприведен на рис. 9), которая реализует алгоритм наследования в операцияхпользовательских имен.func InheritUserNames( ptf_graph){foreach i = 1 to NodeNumber(ptf_graph) {ptf = GetPtfByNumber(ptf_graph, i);foreach proc ∈ ptf and each node n ∈ ptf.proc.cfg {if ( n is call ) {/* Наследуем результаты для операции n.call */InheritNamesForNodeOpers(n);/* Для процедур, вызываемых из ЧТФ, строимфункцию связывания для нелокальных блоков.

*/foreach proc ∈ n {tgt_ptf = GetPtfByProc(proc);ConstructBindingFunction( n, tgt_ptf);endfor;} else if ( n is assign ) {/* Для операций работы с памятью, принадлежащихузлу n, наследуем результаты в терминахпользовательских имен */InheritNamesForNodeOpers(n);}endfor;endfor;}Рис. 9. Псевдокод функции наследования результатов анализав терминах пользовательских имен.В силу ацикличности графа и упомянутого ранее свойства RPO-нумерации, любой узелбудет обрабатываться лишь после того, как будут обработаны все егопредшественники, а, следовательно, станут известны объединенные значения всехфункций связывания во всех возможных вызывающих контекстах.

За вычисление такойфункции связывания отвечает процедура ConstructBindingFunction. Кроме того, всезначения функции связывания могут быть выражены в терминах пользовательскихимен. В самом деле, в ЧТФ, которая содержит главную процедуру программы, нетникаких имен, кроме пользовательских. Следовательно, для ЧТФ тех процедур,которые вызываются из неё, функция связывания будет содержать толькопользовательские имена.

Пусть теперь есть процедура, объединенная функциясвязывания которой содержит только пользовательские имена. Тогда для любой ЧТФпроцедуры, вызываемой из рассматриваемой процедуры, функцию связываниястроится так, как это делалось во время анализа. После этого все нелокальные имена,которые вошли во множество её значений, заменяются на пользовательские имена изфункции связывания рассматриваемой ЧТФ. Когда для каждого нелокального имениизвестно множество пользовательских имен, которое оно выражает, в операцияхпроцедуры (READ, WRITE, CALL) производятся соответствующие замены.РезультатыВ этой части работы приводятся результаты работы алгоритма анализа на некоторыхзадачах из тестовых пакетов SpecInt92 и SpecInt95.

Замеры проводились на машине соследующими характеристиками: Pentium Xeon CPU 3.06Hz, cashe size 512KB. Та версияалгоритма анализа, которая использовалась для получения нижеприведенныхрезультатов, обладал следующими характеристиками:••••моноверсия (единственная ЧТФ для процедуры);flow-insensitive (нечувствительность к потоку управления процедуры);не различаются имена одного блока имен;включены эвристики, ускоряющие сходимость анализа на рекурсивных циклах.Сложность каждой из приведенных в табл.

1 задачи характеризуется такимипараметрами, как:•число строк исходного кода задачи (строки).•число пользовательских процедур в задаче (проц.).•число процедур в самом большом рекурсивном цикле задачи (ССК – сильносвязная компонента).Работа алгоритма анализа на указанных задачах характеризуется следующимипараметрами:•временем работы алгоритма на указанной машине, выраженное в секундах(время);•степень переиспользования ЧТФ без дополнительного анализа (переисп.). Этотпараметр показывает среднее значение по всем обработанным процедурам отследующей величины: процентное отношение числа вызывающих контекстов, вкоторых ЧТФ процедуры была переиспользована без дополнительного анализа, к числувсех вызывающих контекстов этой процедуры, которые встретились в процессеанализа.•степень порывов зависимостей (разрывы). Этот параметр показывает среднеезначение по всем процедурам от следующей величины: процентное отношение числапорванных зависимостей к числу всех возможных пар операций READ, WRITE и CALLданной процедуры.Табл.1Результаты анализа на тестах из пакетов SpecInt92 и SpecInt95.Название тестаSpecInt92008.espresso022.li023.eqntott026.compress072.sc085.gccSpecInt95099.go124.m88ksim129.compress130.li134.perl147.vortexстрокипроц.ССКвремяпереисп.разрывы1350074133376150380868452438238062161661689231311735091621124150879.5%88.5%70.9%61.5%64.8%51.4%72.9%52.5%84.4%62.3%28547179391420691623678526333942863037329810721110311263792011895429075.2%83.7%68.5%87.9%89.5%79.3%71.2%64.0%47.8%53.0%68.1%50.9%Анализируя приведенные результаты, не сложно заметить, что время работы алгоритмазависит, во многом, не столько от величины анализируемой задачи (число её строк ипроцедур), сколько от размеров рекурсивных циклов этой задачи.

Именно это являетсяобоснованием того особого внимания, которое в описанной схеме их обработки. Крометого, следует отметить, что степень переиспользования ЧТФ весьма высока. Этосвидетельствует о том, что предложенные эвристики позволяют довольно быстрообобщить область определения ЧТФ процедур задачи для применения её во всехвызывающих контекстах данной процедуры.ЗаключениеНа сегодняшний день существует много хороших алгоритмов, которые решают задачумежпроцедурного анализа указателей с достаточной степенью детализации на уровнеодной процедуры [6].

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

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

Основная идея модификации состоит в том, что сильно-связныекомпоненты графа вызовов рассматривается как единое целое. Для всех процедур,входящих в цикл используется одна и та же ЧТФ. В результате этого теряется степеньдетализации результатов анализа, но происходит выигрыш в скорости его работы.Другими новшествами данной работы следует считать:•механизм наследования результатов анализа при таких межпроцедурныхпреобразованиях, как inline-подстановка и cloning.•механизм наследования результатов, выраженных в терминах пользовательскихимен.•гибкий механизм управления чувствительности анализа к контексту (contextsensitivity level).•алгоритм сравнения вызывающих контекстов и принятия решения опереприменимости ЧТФ.•система эвристик, ускоряющая сходимость алгоритма.Предлагаемый алгоритм тестировался на задачах из пакетов SPECint92 и SPECint95 [7].На входящих в эти пакеты приложениях модифицированный алгоритм показалхорошее время работы с минимальными потерями в точности вычисляемойинформации.Список литературы1.

Steven S. Muchnik “Advanced Compiler Design and Implementation”, MorganKaufmann Publishers, San Francisco CA.2. Brian R. Murphy, Monica S. Lam “Program Analysis with Partial TransferFunction”, Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluationand semantics-based program manipulation, January, 1999, pages 94-103.3.

Robert P. Wilson, Monica S. Lam “Efficient Context-Sensitive Pointer Analysis CPrograms”, ACM SIGPLAN, Conference on Programming Language Design andImplementation, June 1995.4. Maryam Emami “A practical interprocedural alias analysis foroptimizing/parallelizing C compiler”. Master’s thesis, School of Computer Science,McGill University, August 1993.5. P. Cousot, R. Cousot, “Abstract interpretation framework”. Journal of logic andComputation, 2(4) 511-547, August 1992.6.

Marc Shapiro, Susan Horwitz “Fast and Flow-Insensitive Points-To Analysis”.Proceedings of 24th ACM SIGPLAN-SIGACT symposium of programming language,pp.1-14, Paris, France, January (1997).7. Standard Performance Evaluation Corporation (www.spec.org)..