Развитие методов статического анализа программ, используемых в оптимизирующих компиляторах для архитектур с явно выраженной параллельностью тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Дроздов, Александр Юльевич

• Дроздов, Александр Юльевич
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Дроздов, Александр Юльевич

Введение

1. Методы статического анализа программ

1.1. Основные понятия и определения

1.2. Анализ потока управления

1.2.1. Предикаты и анализ потока управления

1.2.2. Факторизация потока управления

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

1.3. Анализ потока данных

1.3.1. Внутрипроцедурный анализ потока данных

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

1.4. Анализ зависимостей в гнездах циклов

1.5. Использование результатов анализа потока данных и потока управления для вычисления отношения зависимости

1.6. Способы представления информации о зависимостях в оптимизирующих компиляторах

1.7. Применение результатов анализа в оптимизациях

1.8. Аппаратные и программные методы ослабления зависимостей

1.9. Постановка задачи

1.10. Выводы

2. Внутрипроцедурный анализ потока данных без учета предикатных вычислений

2.1. Эффективный алгоритм построения формы статического единственного присваивания

2.1.1. Алгоритмы построения ф-функций

2.1.2. Решение задачи построения ф-функций для множества переменных

2.1.3. Групповое построение ф-функций в контексте линейного алгоритма

2.1.4. Доказательство корректности и оценка сложности модифицированного алгоритма

2.1.5. Экспериментальные результаты

2.2. Дерево значений: новая структура данных, объединяющая информацию о потоке управления и доминировании

2.2.1. Дерево значений

2.2.2. Алгоритм построения дерева значений

2.2.3. Доказательство корректности

2.2.4. Оценка сложности

2.2.5. Результаты тестирования

2.2.6. Оптимизации, использующие дерево значений

2.3. Выводы

3. Внутрипроцедурный анализ потока данных с учетом предикатных вычислений

3.1. Предикатная форма статического единственного присваивания 40 3.1.1. Описание пути в программе

3.2. Эффективный алгоритм преобразования потока управления в поток данных на основе предикатной формы статического единственного присваивания

3.2.1. Преобразование у-функции в предикатное выражение

3.2.2. Построение предикатного выражения

3.2.3. Хеширование предикатного выражения

3.2.4. Предикатное выражения произвольного пути

3.2.5. Пример работы алгоритма

3.3. Анализ предикатных выражений и его использования для проведения оптимизаций

3.3.1. Алгоритмы анализа предикатов

3.3.2. Распространение анализа предикатов за пределы ациклических регионов

3.3.3. Использование результатов анализа предикатов в оптимизирующих компиляторах

3.4. Выводы

4. Анализ зависимостей в цикловых регионах программы

4.1. Основные определения

4.2. Поиск гнезд циклов, для которых возможен анализ

4.3. Поиск индуктивных переменных

4.4. Поиск инвариантов гнезда циклов

4.5. Сохранение информации об измерениях

4.6. Подготовка данных гнезда циклов.

4.7. Подготовка данных для анализа на зависимость двух операций обращения к массиву в цикле

4.8. Вызов драйвера алгоритма анализа зависимостей

4.9. Подготовка данных к вызову алгоритма анализа зависимостей

4.10. Особенности алгоритма анализа зависимостей

4.11. Минимальное расстояние зависимости

4.12. Интерпретация и использование результатов анализа в целях оптимизации

4.13. Экспериментальные результаты

4.14. Выводы

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

5.1. Промежуточное представление

5.2. Пространство имен.

5.3. Частичная трансферная функция

5.4. Анализ внутри процедуры

5.5. Межпроцедурный анализ

5.6. Распространение констант, диапазонов значений переменных и выравниваний объектов

5.7. Межпроцедурный анализ методом нумерации значений

5.8. Экспериментальные результаты

5.9. Выводы

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

Актуальность работы. Несколько последних десятилетий вычислительная техника развивалась бурными темпами, затрагивая все более широкий круг проблем. И если в 60-е и 70-е годы прошлого века был только обозначен потенциал применения этой отрасли, проводились исследования фундаментальных принципов выполнения вычислений, то к началу XXI века ареал распространения вычислительной техники, ее значение практически для всех областей деятельности человека достигли огромных масштабов. Уровень развития и применения вычислительных технологий в настоящее время является одним из важнейших стратегических факторов развития не только научного потенциала страны, но и всего общества в целом.

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

Динамическое распараллеливание вычислений наиболее распространено в современных микропроцессорах и продолжает обеспечивать достаточную производительность исполнения вычислительных задач и совместимость программного обеспечения на ряде архитектур. Но дальнейшее увеличение параллельности на уровне операций в архитектурах процессоров может быть ограничено квадратичным усложнением логики проверок в аппаратуре при планировании команд. Поэтому статический подход к реализации пооперационной параллельности в процессе компиляции сейчас активно развивается как альтернатива суперскалярным (с динамическим планированием вычислений) процессорам. Для обозначения такого рода архитектур во второй половине 90-х годов появился термин EPIC (Explicitly Parallel Instruction Computing) [1-3] или архитектура с явно выраженной параллельностью на уровне команд.

В архитектурах с явно выраженной параллельностью эффективное использование машинных ресурсов в большей степени определяется процессом компиляции исходной программы. Другими словами, нахождение максимального параллелизма программы на уровне операций, выражение его в промежуточном представлении и отображение в статически спланированный код - это главные задачи оптимизирующего компилятора, позволяющие получать эффективный результирующий код и обеспечивающие оптимальную загрузку процессора в архитектурах типа EPIC. Развитие методов статического анализа программ является одним из главных резервов, позволяющих находить в программах независимые вычисления и выполнять их в параллельном режиме. Эти методы позволяют оптимизирующему компилятору эффективно применять оптимизирующие преобразования, направленные на максимально эффективное использование аппаратных ресурсов ЕР/С-архитектур в целях получения высокоэффективного кода и увеличения производительности вычислений. Особое внимание в данной работе уделено таким методам статического анализа программ, как внутрипроцедурный анализ потока данных, межпроцедурный анализ потока данных, анализ зависимостей в цикловых регионах программы, анализ предикатных вычислений и его использование для успешного применения оптимизаций. Использование этих методов позволяет добиваться полноценного использования таких архитектурных особенностей ЕР1С-архитектур как широкая команда, предикатный и спекулятивный режимы исполнения инструкций. Следует отметить, что использование методов статического анализа позволяет применять преобразования программы на любом уровне факторизации, начиная от отдельной операции и заканчивая преобразованиями на межпроцедурном уровне.

Цель диссертационной работы

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

• исследование современного уровня развития методов статического анализа программ и возможностей их использования в промышленных оптимизирующих компиляторах;

• разработка быстрого алгоритма построения формы статического единственного присваивания;

• разработка интегральной структуры данных, удобной для проведения многих преобразований программы;

• разработка эффективного алгоритма перевода программы в предикатную форму;

• улучшение метода анализа предикатных выражений и усиление эффективности применения оптимизаций, работающих на основе предикатного анализа;

• улучшение метода анализа зависимостей в цикловых регионах программы, с целью повышения его точности и расширения области применимости;

• развитие метода межпроцедурного анализа потока данных, позволяющего расширить область применимости межпроцедурного анализа с высокой степенью детализации результатов на приложения большого объема;

• реализация указанных алгоритмов в составе оптимизирующего компилятора для архитектуры «Эльбрус-ЗМ».

Предмет исследования составляют алгоритмические аспекты разработки оптимизирующих компиляторов для высокопроизводительных вычислительных систем:

• методы статического анализа программ с точки зрения их эффективности и возможности применения в контексте промышленных оптимизирующих компиляторов;

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

Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов, теории абстрактной интерпретации, теории диофантовых уравнений и неравенств, математической логики. Эффективность предложенных методов оценивалась путем вычисления значений ключевых параметров, определяющих эффективность предложенных подходов. Для проведения замеров использовался инструментальный комплекс в составе оптимизирующего компилятора и потактной модели архитектуры «Эльбрус-ЗМ». Замеры производились на пакетах задач Spec92 и Spec95 [7, 8].

Научная новизна

Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, по преимуществу, составляют:

• разработка быстрого алгоритма построения формы статического единственного присваивания;

• разработка интегральной структуры данных, удобной для проведения многих преобразований программы;

• разработка эффективного алгоритма перевода программы в предикатную форму;

• улучшение метода анализа предикатных выражений и усиление эффективности применения оптимизаций, работающих на основе предикатного анализа;

• улучшение метода анализа зависимостей в цикловых регионах программы, с целью повышения его точности;

• разработка единого метода решения задач межпроцедурного анализа потока данных, в том числе задачу межпроцедурной нумерации значений.

Практическая ценность результатов работы состоит в том, что на основе предложенных в работе методов была разработана аналитическая часть промышленного оптимизирующего компилятора для архитектуры «Эльбрус-ЗМ» [4-6].

В процессе выполнения диссертационной работы получены следующие практические результаты:

1) Все разработанные алгоритмы реализованы в составе оптимизирующего компилятора для архитектуры «Эльбрус-ЗМ».

2) Выявились дальнейшие направления исследований в области развития методов статического анализа программ и их использования в целях оптимизации.

Апробация

Результаты работы докладывались на IX Санкт-Петербургской Международной конференции «Региональная информатика-2004 (РИ-2004)» в 2004 г., на Международной молодежной научной конференции «XXX Гагаринские чтения» (Москва, 2004 г.), XXI Научно-технической конференции войсковой части 03425 (Москва, в/ч 03425, 2003 г.), а также докладывались и обсуждались на семинарах и научно-технических совещаниях ЗАО "МЦСТ" и Института Микропроцессорных вычислительных систем РАН.

Публикации

По теме диссертации опубликованы 8 печатных работ:

• Дроздов А.Ю. Методы анализа программ, предлагаемые для использования в современных оптимизирующих компиляторах // Тезисы докладов XXI научно-технической конференции войсковой части 03425. - М.:, в/ч 03425, 2003.

• Боханко A.C., Дроздов А.Ю. Оптимизация «Расширенное удаление излишних операций чтения из памяти» // Тезисы докладов Международной молодежной научной конференции «XXX Гагаринские чтения», т. 5. - М.: МАТИ, 2004.

• Боханко A.C., Дроздов А.Ю. Обобщенное представление информации о потоке данных и доминировании // IX Санкт-Петербургская Международная конференция "Региональная Информатика-2004". Тезисы докладов. - СПб.: СПИИ РАН, 2004.

• Дроздов А.Ю., Владиславлев В.Е. Эффективный алгоритм межпроцедурного анализа указателей // IX Санкт-Петербургская Международная конференция "Региональная Информатика-2004". Тезисы докладов. - СПб.: СПИИ РАН, 2004.

• Дроздов А.Ю., Новиков C.B. Улучшение алгоритмов построения формы статического единственного присваивания // IX Санкт-Петербургская Международная конференция "Региональная Информатика-2004". Тезисы докладов. - СПб.: СПИИ РАН, 2004.

• Боханко А.С., Дроздов А.Ю., Корнев P.M. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8, 2004 г.

• Дроздов А.Ю., Ровинский Е.В. Технология использования векторных операций для получения оптимального кода // Компьютеры в учебном процессе, № 9, 2004.

• Дроздов А.Ю., Степаненков A.M. Методы оптимизации цикловых участков процедур, основанные на аппаратной поддержке архитектуры // Компьютеры в учебном процессе, № 10,2004.

Структура и объем работы

Диссертация состоит из введения, пяти глав, и заключения. Диссертация содержит 108 страниц, 25 рисунков, 6 таблиц. Список литературы насчитывает 93 наименования.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Дроздов, Александр Юльевич

5.9. Выводы

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

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

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

Предлагаемый подход тестировался на задачах из пакетов 5РЕСлги92 и 5РЕСт195. На входящих в эти пакеты приложениях предложенный метод показал хорошее время работы с минимальными потерями в точности вычисляемой информации.

Использование результатов распространения констант позволяет улучшать производительность на некоторых задачах на 40%. Ниже приведены основные результаты данной главы:

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

2) Показано, как с помощью предложенного подхода решаются задачи межпроцедурного распространения указателей, констант, выравниваний объектов, диапазонов значений переменных.

3) Предложен алгоритм решения задачи межпроцедурной нумерации значений.

Заключение

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

В процессе исследований и в ходе решения поставленных задач автором были получены следующие результаты, выносимые на защиту:

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

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

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

4) Предложен метод, расширяющий применимость анализа предикатов в программе, переведенной в предикатную форму, на случай произвольного региона. Этот метод позволяет включить в рассмотрение поток данных, входящих в регион через ср-узлы.

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

6) Предложен оригинальный интерфейс решателя систем диофантовых уравнений и неравенств, позволивший снять многие ограничения на применимость анализа зависимостей в циклах.

7) Разработано понятие минимального вектора расстояния зависимости и предложен метод его вычисления.

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

9) Разработана реализация решателя систем диофантовых неравенств на основе Симплекс-метода. Показано, что Симплекс-метод имеет преимущество перед методом Фурье по скорости работы на задачах, работающих с многомерными массивами.

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

11) Показано, как с помощью предложенного подхода решаются задачи межпроцедурного распространения указателей, констант, выравниваний объектов, диапазонов значений переменных.

12) Предложен алгоритм решения задачи межпроцедурной нумерации значений.

Все представленные в диссертационной работе алгоритмы и методы, реализованы в составе оптимизирующего компилятора с языков высокого уровня С, С++, ¥11 для архитектуры «Эльбрус-ЗМ» и составляют основу аналитической части данного компилятора. Некоторые из предложенных методов внутрипроцедурного анализа программы работают в составе двоичного компилятора для архитектуры «Эльбрус-ЗМ» с кодов Ые1-Х86.

Список литературы диссертационного исследования кандидат технических наук Дроздов, Александр Юльевич, 2004 год

1. M. S. Schlansker, B. R. Rau. EPIC: An Architecture for Instruction-Level Parallel Processors: Technical Report HPL-1999-1II / Compiler and Architecture Research Hewlett-Packard Laboratories, Palo Alto, February 2000. 80 p.

2. Boris Babayan. E2K Technology and Implementation. // in Proceedings of the Euro-Par 2000 Parallel Processing: 6th International. - Volume 1900 / 2000. -January, 2000.-P. 18-21.

3. M. Кузьминский. Отечественные микропроцессоры: Elbrus E2K // Открытые системы, № 05-06, 1999. С. 8-13.

4. К. Dieffendorf. The Russians Are Coming. Supercomputer Maker Elbrus Seeks to Join x86/IA-64 Melee // Microprocessor Report, V.13, №.2. February 15, 1999. -P. 1-7.7. httpV/open.specbench org/cpu928. http://open specbench orp/cpu95

5. В.Н.Касьянов, В.А.Евстигнеев, Графы в программировании: обработка, визуализация и применение. Санкт-Петербург «БХВ-Петербург»,2003.

6. В.В. Воеводин, Вл. В. Воеводин, Параллельные вычисления. Санкт-Петербург «БХВ-Петербург», 2002.

7. Alfred V. Aho, Ravi Sethi, Jeffrey D. UHman, "Compilers: Principles, Techniques, and Tools", Addison-Wesley, Reading, 1986.

8. John R. Ellis. Bulldog: A compiler for VLIW Architectures. MIT Press, 1985

9. Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs and Koen G. Langendoen, Modern Compiler Design, by John Wiley & Sons,Ltd, 2000.

10. Randy Allen, Ken Kennedy, Optimizing Compilers for Modern Architectures. 2002 by Academic Press.

11. Steven S. Muchnick, "Advanced Compiler Design and Implementation", Morgan Kauffman, San Francisco, 1997.

12. Utpal Banerjee, Loop Transformations for Restructuring Compilers. Kluwer academic Publishers, 1993.

13. Utpal Banerjee. Dependence Analysis. Kluwer Acadmic Publishers. 1997

14. Miling Girkar, Constantine D.PolychronopouIos. "Extracting Task-Level Parallelism" ACM, July 1995.

15. Stephen Alstrup, Dov Harel, Peter W.Lauridsen, Mikkel Thorup, Dominators in Linear Time. Department of Computer Science, University of Copenhagen, 1985.

16. G. Ramalingam, On Loops, Dominators, and Dominance Frontier. PLDI 2000, Vancouver, Canada.

17. Vugranam C. Sreedhar, Yong-fong Lee, Guang R.Gao. DJ-Graphs and Their Applications to Flowgraph Analyses. ACAPS Tchnical Memo 70, May 11, 1994.

18. Vugranam C. S. Sreedhar, Guang R.Gao. Computing phi-nodes in Linear Time Using DJ-graphs. ACAPS Tchnical Memo 75, January 18, 1994.

19. Keshav Pingali, Gianfranco Bilardi, Optimal Control Dependence Computation and the Roman Chariots Problem. ACM, 1997.

20. Richard Johnson and Michael Schlansker, "Analysis Techniques for Predicated Code", In Proc. Of the 29th Annual Int'l Symp. On Microarchitecture, December 1996.

21. Fohn W. Sias, Wen-mei W. Hwu, David I. August. Accurate and Efficient Predicate Analysis with Binary Decision Diagrams. Proceedings of the 22rd Annual ACM/IEEE Internationsl Symposium on Microarchitecture, December 2000.

22. Nancy J. Wärter, Scott A. Mahlke, Wen-mei W.Hwu, B. Ramakrishna Rau. Reverse If-Con\ersion. ACM-SIGPLAN-JLDI-6/93/Albuquerque, N.M.

23. Johnson, Richard Craig. Efficient Program Analysis Using Dependence Flow Graphs Ph.D. dissertation, Cornell University. August, 1994.

24. Alexandra Nicolau and Steven Novack, Trailblazing: A Hierarchical Approach to Percolation Scheduling. Department of Information and Computer Science University of California, Proceedings of the 1993 International Conference on Parallel processing.

25. Maryam Emami "A practical interprocedural alias analysis for optimizing/parallelizing C compiler". Master's thesis, School of Computer Science, McGill University, August 1993.

26. P. Cousot, R. Cousot, "Abstract interpretation framework". Journal of logic and Computation, 2(4) 511-547, August 1992.

27. Eric James Stoltz, Intermediate Compiler Analysis via reference Chaining. Portland State University, Thesis, January 1995.

28. William Blume, Rudolf Eigenmann. Symbolic Range Propagation. University of Illinois at Urbana-Champaign, September 20, 1994.

29. William Blume, Rudolf Eigenmann. Demand-driven, Symbolic Range Propagation. University of Illinois at Urbana-Champaign.

30. Loren Taylor Simson, Value-Driven Redundancy Elimination, Thesis, Rice University, Houston, Texas, April, 1996.

31. Fend Tu, David Padua. Efficient Building and Placing of Gating Functions Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaingn, 1995.

32. Kwangkeun Yi and Williams Ludwell Harrison III, Interprocedural Data Flow Analysis for Compile-time Memory Management. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign.

33. Evelyn Duesterwald, Rajiv Gupta, Mary Lou Soffa, Demand-driven Computation of Interprocedural Data Flow. Department of Computer Science, University of Pittsburg, POPL'95 1/95 San Francisco, CA USA.

34. Evelyn Duesterwald, Rajiv Gupta, and Mary Lou Soffa, A Practical Framework for Demand-Driven Interprocedural Data Flow Analysis. University of Pittsburg, ASM SISPLAN-SIGACT Symposium on Principles of Programming Languages, 1995.

35. Susan Horvvitz, Thomas Reps, and Mooly Sagiv, Demand Interprocedural Dataflow Analysis. University of Wisconsin, Proceedings of the Third ASM SIGSOFT Symposium on Foundations of Software Engineering, Washington DC, October 10-13, 1995.

36. David R.Chase, Mark Wegman, F.Kenneth Zadeck, Analysis of Pointers and Structures. ASM SIGPLAN'90 PLDI, June 20-22, 1990.

37. Yuan-Shin Hwang, Joel Saltz, Compile-Time Analysis on Programs with Dynamic Pointer-Linked Data Structures. Depatment of Computer Science, University of Maryland, Nobember 8, 1996.

38. Rakesh Ghiya and Laurie J.Hendren, Connection Analysis: A Practical Interprocedural Heap Analysis for C. School of Computer Science, McGill University,

39. Proceedings of the Eigth Workshop on Languages and Compilers fo rParallel Computing, Columbus, Ohio, August 10-12, 1995.

40. Xinan Tang, Rakesh Ghiya, Laurie J. Hendren, Guang R.Gao, Heap Analysis and Optimizations for Threaded Programs. School of Computing Science, McGill University, 1997.

41. Rakesh Ghiya, Practical Techniques for Interprocedural Heap Analysis. School of Computing Science, McGill University, Montreal, January 1996.

42. Keith D.Cooper, Ken Kennedy, Fast Interprocedural Alias Analysis. Rice University, 1989.

43. Bjarne Steensgaard, Points-to Analysis in Almost Linear Time, Microsoft Research, 1996.

44. Keith D.Cooper, Ken Kennedy, Interprocedural Side-Effect Analysis in Linear Time. Rice University, 1988.

45. Robert P.Wilson, Monika S.Lam. Efficient context-sensitive pointer analysis for С programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language and Implementation, pages 1-12, June 1995.

46. Kleanthis Psarris and Konstantinos Kyriakopoulos, Data Dependence Testing in Practice. Division of Computer Science, The University of Texas at San Antonio, San Antonio, TX 78249.

47. Paul M.Petersen and David A.Padua, Experimental Evaluation of Some Data Dependence Tests (Extended Abstract), Center for Supercomputing Research and De\elopment, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801.

48. Paul M.Petersen, David A.Padua, Static and Dynamic Evaluation of Data Dependence Analysis. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign.

49. Keshav Pingali, Micah Beck, Richard Johnson, Mayan Moudgill, Paul Stodghill,

50. Dependence Flow Graph: An Algebraic Approach to Program Dependencies. Department of Computer Science, Cornell University, Ithaca, NY 14853.

51. Jay Hoeflinger, Run-Time Dependence Testing by Integer Sequence Analysis. Center for Supercomputing Research & Development, University of Illinois at Urbana-Champaign, Urbana, Illinois, 61801.

52. Paul M.Petersen, David A.Padua, Dynamic Dependence Analysis: A Novel Method for Data Dependence Evaluation. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, Urbana, Illinois, 618012932.

53. Sreedhar, Vugranam C. and Gao, Guang R. A linear time algorithm for placing 9-nodes // Conference Record of POPL'95: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Francisco, California, January 1995. Pp. 62-73.

54. Дроздов А.Ю., Новиков C.B. Улучшение алгоритмов построения формы статического единственного присваивания // IX Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

55. Bilardi G., Pingali К. The Static Single Assignment Form and its Computation -Cornell University Technical Report, July, 1999.

56. Tarjan, Robert E. Depth first search and linear graph algorithms // SIAM Journal on Computing, 1(2), June 1972. Pp. 146-160.

57. Боханко A.C., Дроздов А.Ю. Обобщенное представление информации о потоке данных и доминировании // IX Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.

58. Боханко А.С., Дроздов А.Ю. Оптимизация «Расширенное удаление излишних операций чтения из памяти» // В трудах Международной молодежной научной конференции «XXX Гагаринские чтения», Москва, 2004.

59. David I. August, Wen-mei W. Hwu, and Scott A. Mahlke. A Framework for Balancing Control Flow and Predication // Proceedings of the 30th annual IEEE/ACM International Symposium on Microarchitecture. December, 1997. P. 92-103.

60. Joseph С. H. Park; Mike Schlansker. On Predicated Execution Software and System Laboratory HPL-91-58, May, 1991.

61. Pend Tu, David Padua. Efficient Building and Placing of Gating Functions Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaingn, 1995.

62. L. Carter, B. Simon, B. Calder, L. Carter, and J. Ferrante, "Predicated single static assignment ", in Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, October 1999.

63. J.R. Allen, K. Kennedy, C. Porterfield, J. Warren. Con\ersion of control dependences to data dependences, Conf. Record of POPL-IO, 1983.

64. Joseph A. Fisher. Trace Scheduling: A technique for global microcode compaction // Transactions on Computers, IEEE. July, 1981. V. C-30. P. 478-490.

65. S. A. Mahlke, D. C. Lin, W. Y. Chen, R. E. Hank, and R. A. Bringmann. Effective Compiler Support for Predicated Execution Using the Hyperblock. // in Proceedings of the 25th International Symposium on Microarchitecture. December, 1992. P. 45-54.

66. Дроздов А.Ю., Новиков C.B. Методы совместного планирования путей программы, предлагаемые для использования в современных оптимизирующих компиляторах. "Сборник тезисов XXI научно-технической конфренции войсковой части 03425" Москва, в/ч 03425, 2003г.

67. John Wollenburg, "Condition awareness support for predicate analysis optimization

68. University of Illinois, 1997.

69. R.E. Bryant. Symbolic Boolean manipulation with ordered binary decision diagrams. Technical Report CMV-CS-92-160, School of Computer Science, Carnegie Mellon University, Pittsburgh, РЛ, October 1992.

70. D.I. August, J.W. Sias, J. Puiatti, S.A. Mahlke, D.A. Connors, K.M. Crozier, and W.W. Hwu, 'The program decision logic approach to predicated execution", in Proceedings of the 26th International Symposium on Computer Architecture, pp. 208219, May 1999.

71. J. Ferrante, K. J. Ottenstein, and J.D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9(3):319-349, July 1987.

72. Le-Chun Wu, Wen-mei W. Hwu. A New Data-Location Tracking Scheme for the Recovery of Expected Variables Values. Technical Report IMPACT-98-07.

73. Le-Chun Wu, Rajiv Mirani, Harlsh Patil, Bruce Olsen, Wen-mei W. Hwu. A New Framework for Debugging Globally Optimized Code. ACM SIGPLAN Conference on Programming Language Design and Implementation, Atlanta, Georgia, May 1-4, 1999.

74. R. Gupta, "Debugging code reorganized by a trace scheduling compiler", Structred Programming, vol. 11, pp. 141-150, July 1990.

75. Боханко A.C., Дроздов А.Ю., Корнев P.M. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8,2004 г.

76. Vadim Maslov, "Delinearisation: an Efficient Way to Break Multiloop Dependence Equations", Proceedings of PLDI'92, ACM, 1992.

77. Г. П. Кюнци, В. Крелле, "Нелинейное программирование", Москва, Советское Радио, 1965.

78. Дроздов А.Ю., Степаненков A.M. Методы оптимизации цикловых участков процедур, основанные на аппаратной поддержке архитектуры // Компьютеры в учебном процессе, Кя 10,2004 г.

79. М. Wolfe, С. W. Tseng, 'The Power test for data dependence", IEEE Transaction on Parallel and Distributed Systems, Vol. 3, No. 5, pp. 591-601, September 1992.

80. W. Pugh, "A practical algorithm for exact array dependence analysis", Communication of the ACM, 35(8): 102-114, August 1992.

81. K. Psarris, K. Kyriakopoulos, "Data Dependence Testing in Practice", IEEE International Conference on Parallel Architectures and Compiler Techniques, October 12-16, 1999, California.

82. Brian R. Murphy, Monica S. Lam "Program Analysis with Partial Transfer Function", Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, January, 1999, pages 94-103.

83. 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).

84. Mooly Sagiv, Thomas Preps, Susan Horwotz "Precise Dataflow Analysis with Applications Constant Propagation". TAPSOFT 1995. pages 651-665.

85. Дроздов А.Ю., Владиславлев B.E. Эффективный алгоритм межпроцедурного анализа указателей // IX Санкт-Петербургская Международная конференция Региональная Информатика-2004 «РИ-2004» Санкт-Петербург, 22-24 июня 2004 года.1. Список иллюстраций

86. Рис. 2.1. Управляющий граф, DJ-граф и DF-граф. Стр. 22

87. Рис. 2.2. Битовый вектор. Стр. 23

88. Рис. 2.3. Пример перевода программы в SSA-форму Стр. 32

89. Рис. 2.4. Пример неявного изменения значения переменной Стр. 33

90. Рис. 2.5. Пример вхождения одной операции в два вектора Стр. 34

91. Рис. 2.6. Схема дерева значений ^1. Стр. 34

92. Рис. 2.7. Пример применения оптимизаций GCP и RLE Стр. 38

93. Рис. 3.1. Предикатные вычисления „1. Стр. 40

94. Рис. 3.2. Построение предикатов методом инициализаций в узлах с Стр. 42 выходящими CD-дугами.

95. Рис. 3.3. Условное ветвление. ^ .1. Стр. 44

96. Рис. 3.4. Представление предикатного выражения в виде списочной Стр. 48 структуры.

97. Рис. 3.5. Реализация предикатного выражения р1&Л(р2&Л(рЗ)) в видесписочной структуры. Стр. 49

98. Рис. 3.6. Фрагмент управляющего графа Стр. 53

99. Рис. 3.7. Построение предикатов двумя методами. Стр. 54

100. Рис. 3.8. Пример предикатного кода Стр. 58

101. Рис. 3.9. Пример применимости оптимизации, удаляющей избыточные Стр. 59операции записи в память. Рис.3.10. Пример применимости оптимизации, удаляющей избыточные предикатные вычисления на основе анализа предикатовпереходов. Стр. 60

102. Рис.3.11. Пример программы, содержащей избыточные вычисления. Стр. 61

103. Рис.3.12. Пример программы, переведенной в предикатный код. Стр. 61

104. Рис. 4.1. Структура ps-формы Стр. 64

105. Рис. 5.1. Примеры соответствия промежуточного представленияязыковым выражениям. Стр. 76

106. Рис. 5.2. Пример того, в какие имена переходят языковые выражения. Стр. 78

107. Рис. 5.3. Пример, демонстрирующий понятия РП, нелокального блока

108. HJIB) и функции связывания на них. Стр. 79

109. Рис. 5.4. Пример, поясняющий работу функции GetPointsTo. Стр. 82

110. Рис 5 5 Пример рекурсии, для которой определение пересечения Стр. 88 требует глобализации имени.