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

Комбинированные методыВ реальных компиляторах возможно использование методов, в которыхкомбинируются точные и не точные алгоритмы описания областей массивов. Наиболее известным комбинированным методом является FIDA (FullInterprocedural Data Dependence Analysis) Майкла Хинда (Hind [8]) из IBM.В этом методе использованы алгоритмы линеаризации и образов. Для определения зависимости производится частичная подстановка процедурногокода на место вызова (результирующий код содержит вызовы без подстановки, подстановка производится только для анализа). Данные, которыепри этом не являются необходимыми (для анализа зависимости), отбрасываются (вычисляется срез [7]).

Линеаризация используется в тех случаях,когда размерность массива изменяется при вызове процедуры, или используются смещения начала массива. За счёт использования подстановки алгоритм позволяет использовать стандартные методы нахождения зависимости(во многих случаях).2.4. Анализ контекста использования процедурыАнализ контекста использования направлен на уточнение оптимизацийпутём анализа различных вариантов использования процедуры.

Информация о совмещениях, диапазоны изменения переменных и, как следствие,набор возможных оптимизаций зависят от контекста вызова процедуры.Рассмотрим следующий пример:function a(a,b,c)beginif (c=1) a=sin(b);else b=asin(a);endВ этом примере подпрограмма может изменять параметр b или параметр a в зависимости от значения параметра c. Контекст вызова процедурыопределяется набором параметров совмещений (alias) и информацией оИдрисов Р.

И. Методы межпроцедурного анализа53возможных значениях переменных, которая генерируется в процессе протягивания констант. В данном примере оптимизирующий компилятор можетпринять решение о замене этой процедуры двумя следующими:function a_1(a,b)begina=sin(b);endfunction a_2(a,b)beginb=asin(a);endБудет произведена замена вызовов процедуры a на вызовы процедурa_1 и a_2 в зависимости от значения параметра c. Оговоримся, что такоерешение принимается только в результате анализа контекста использованияпроцедуры a, потому что возможны такие варианты программы, при которых такая оптимизация не будет возможной.

Например:Случай 1:....a(a,b, rand(0, 5))Случай 2:a(a,b,1);a(c,d,1);В первом случае явная разделимость процедуры a на две разные процедуры не даёт ничего, а во втором — просто не требуется (при условии, чтоэто все вызовы a в программе), потому что используется только при c = 1,что даёт возможность найти и удалить «мёртвый код» ветви c <> 1. Заменаодной процедуры несколькими называется клонированием (procedurecloning). Предельный случай клонирования процедур (когда процедура клонируется столько раз, сколько вызывается) является аналогом прямой подстановки (inlining).

Клонирование процедур уменьшает огрубление информации о поведении процедуры в конкретном контексте. Решение о клонировании принимается на основе анализа контекстов возможного использования и тела процедуры. Разработчики SUIF утверждают, что таким обра-54Методы и инструменты конструирования программзом они достигают точности прямой подстановки без излишнего увеличения размера анализируемого кода. В случае, если выполняется частичнаяподстановка, решение о подстановке принимается на основе анализа графавызовов. Подстановка применяется к висячим процедурам.Клонирование процедур и частичную подстановку относят к межпроцедурным оптимизациям [6], также медпроцедурной оптимизацией считаетсяперенос кода за границы процедуры, который является промежуточнымвариантом подстановки.3. ЗАКЛЮЧЕНИЕРассмотренные алгоритмы позволяют сказать, что для каждого из видованализа не существует какого-либо универсального и точного решения поставленной задачи.

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

Межпроцедурный анализ на сегодняшний день является обязательной частью современного оптимизирующего компилятора.СПИСОК ЛИТЕРАТУРЫ1. Steensgaard B. Points-to analysis in almost linear time // Proc. of POPL'96. — St.Petersburg Beach, Florida, January 1996. — P. 32–41.2. Heintze N., Tardieu O. Ultra-fast Aliasing Analysis using CLA: A Million Lines of CCode in a Second // Proc. of 2001 ACM SIGPLAN Conf. on Programming LanguageDesign and Implementation, Snowbird, Utah, USA, June 20-22, 2001.

— ACM Press,2001 — P. 254–263.3. Li Z., Yew P.-Ch. Efficient Interprocedural Analysis for Program Parallelization andRestructuring // Proc. of the ACM/SIGPLAN PPEALS 1988, Parallel Programming:Experience with Applications, Languages and Systems, New Haven, Connecticut,July 19-21, 1988. — SIGPLAN Notices. — 1988. — Vol. 23(9). — P. 85–994.

Schouten D.A. An Overview of interprocedural analysis technologies for high performance parallelizing compilers — Illinois, 1990 — 62 p. — (Tech. Rep. / Center forSupercomputing Research and Development. Univ. of Illinois; N 1005).5. Евстигнеев В.А., Серебряков В.А. Методы межпроцедурного анализа (обзор) //Программирование. — 1992 — № 3. — С. 4–15.Идрисов Р. И. Методы межпроцедурного анализа556. Keryell R.

et al. PIPS — A Workbench for Interprocedural Program Analyses andParallelization / R. Keryell, C.Ancourt, F.Coelho, B.Creusillet, F.Irigoin, P.Jouvelot— Paris, 1996 — 24 p. — (Tech. Rep. / Centre de Recherche en Informatique. EcoleNationale Sup'erieure des Mines de Paris)7. Касьянов В.Н., Мирзуитова И.Л. SLICING: Срезы программ и их использование— Новосибирск, 2002 — 116 с.8. Hind М. et al. An Empirical Study of Precise Interprocedural Array Analysis / M.Hind, M.

Burke, P. Carini, S. Midkiff // Scientific Programming — 1994 — Vol. 3,N 3 — P. 255–2719. Callahan D., Kennedy K. Analysis of Interprocedural Side Effects in a Parallel Programming Environment // J. of Parallel and Distributed Computing. — 1988. — Vol.5. — P. 517–550.10. Balasundaram V., Kennedy K. A technique for summarizing data access and its use inparallelism enhancing transformations // Proc. of the SIGPLAN '89 Conf. on ProgramLanguage Design and Implementation.

— Portland, Orgen. June 1989. —Vol. 24 (7).— P. 41–53.11. Антонов А.С. Современные методы межпроцедурного анализа программ // Программирование. — 1998. — № 5. — С. 3–14.12. Triolet R., Irigoin F., Feautrier P. Direct Parallelization of Call Statements // Proc. ofthe SIGPLAN Symp. on Compiler Construction. — SIGPLAN Notices. — 1986. —Vol. 21 (7). — P. 176–185.13. Burke M., Cytron R. Interprocedural dependence analysis and parallelization // Proc.of the SIGPLAN Symp. on Compiler Construction — SIGPLAN Notices. — 1986. —Vol.

26 (6). — P. 145–156.14. Pugh W. The Omega Test: a fast and practical integer programming algorithm fordependence analysis — Univ. of Maryland, 1991 — 10 p. — (ACM 0-89791-4597/91/0004).15. Tang P. Exact Side Effects for Interprocedural Dependence Analysis // Proc. of theACM Internat. Conf. on Supercomputing, Tokyo, Japan, July 1993 — P. 137–146..