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

УДК 004.4'416

На правахрукописи

Дроздов Александр Юльевич

РАЗВИТИЕ МЕТОДОВ СТАТИЧЕСКОГО АНАЛИЗА ПРОГРАММ, ИСПОЛЬЗУЕМЫХ В ОПТИМИЗИРУЮЩИХ КОМПИЛЯТОРАХ ДЛЯ АРХИТЕКТУР С ЯВНО ВЫРАЖЕННОЙ ПАРАЛЛЕЛЬНОСТЬЮ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва - 2004

Работа выполнена в Институте микропроцессорных вычислительных систем РАН

Научный руководитель кандидат технических наук

Волконский В. Ю.

Официальные оппоненты: доктор физико-математических наук

Крюков В. А.

Защита состоится «¿¿>> декабря 2004 г. в 14 ч. 1<?МИН. на

заседании диссертационного совета Д 002.043.01 при Институте микропроцессорных вычислительных систем РАН по адресу: 117218, ГСП-7, г. Москва, Нахимовский проспект, д. 36, корп. 1.

С диссертацией можно ознакомиться в библиотеке Института микропроцессорных вычислительных систем РАН.

Автореферат разослан? » ноября 2004 г. Ученый секретарь диссертационного совета

кандидат технических наук Зотов С. М.

Ведущая организация Институт проблем информатики

РАН

Общая характеристика работы

Актуальность работы

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

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

Динамическое распараллеливание вычислений наиболее распространено в современных микропроцессорах и продолжает

"Исполнения

обеспечивать достаточную

БИБЛИОТЕКА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация

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

Публикации

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

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

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

Краткое содержание работы

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

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

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

Форма статического единственного присваивания (Static Single Assignment, SSA) является одной из самых распространенных форм представления потока данных программы и активно используется в большинстве современных оптимизирующих компиляторов. Ключевым шагом в ее построении является нахождение мест размещения ф-функции в предположении, что задано множество узлов управляющего графа, которые содержат записи в некоторую переменную программы. Напомним, что в программе, представленной в SSA-форме, любая переменная может быть определена только один раз. Для того чтобы соблюсти это ограничение и, тем самым, перевести программу в SSA-форму, необходимо выполнить следующие действия:

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

• Переименовать все переменные, так чтобы каждому определению соответствовала своя, уникальная переменная.

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

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

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

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

минимального элемента реализации пакета битовых векторов (в нашей реализации size(word)=32).

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

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

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

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

Для переменных, всю работу с которыми можно точно описать статически, ф-узлов и операций одного линейного участка достаточно. Но есть переменные, работу с которыми точно описать статически невозможно. Это составные переменные (структуры, объединения, массивы), глобальные переменные, и переменные, на которые брался адрес.

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

Рис. 1. Пример неявного изменения значения переменной.

Далее в работе приведен алгоритм построения дерева значений. Алгоритм обладает алгоритмической сложностью O(M1+M2*N), где M1 -число операций и ф-узлов SSA-формы, М2 - число операций, N - число линейных участков в управляющем графе. Результаты тестирования показали, что дерево значений имеет хорошие характеристики по объему занимаемой памяти и подходит для использования в промышленных компиляторах. Далее показывается, как использование дерева значений позволяет эффективно проводить целый ряд оптимизирующих преобразований программы, таких как глобальное распространение копий (Global Copy Propagation, далее GCP), удаление излишних чтений (Redundant Loads Elimination, далее RLE), удаление мертвого кода (Dead Code Elimination, далее DCE) и удаление излишних записей (Redundant Stores Elimination, далее RSE).

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

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

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

Одной из основных задач, которую должен решать оптимизирующий компилятор для платформ с поддержкой предикатных вычислений, является построения предиката операции. Предикатными вычислениями называется условное исполнение команд, зависящих от значения условного операнда данной команды, называемого предикатом. Когда значение предиката есть истина (TRUE), команда исполняется нормально; а когда значение предиката есть ложь (FALSE), команда игнорируется. Поддержка предикатных вычислений в EPTC-архитектурах позволяет выполнять операции раньше перехода, идущего на ее исходный участок, если выполнение операции осуществлять под условием (предикатом) этого перехода. При переносе операции выше нескольких переходов, предикат операции должен быть вычислен на основании условий этих переходов. Приведем пример, в котором благодаря предикатным вычислениям был удален переход. На рис. 2 приведено преобразование безусловных вычислений в предикатный код. Условие для операции будем записывать в квадратных скобках рядом с операцией. Для каждого условия существует возможность задания маски, с которой оно влияет на операцию. Если условие используется явно, то маска равна TRUE и записывается как .t. Если условие используется, инвертировано, то маска равна FALSE и записывается как .f.

Предикатный код

cmp a, b -» Р а = а+ 1 [P.t]

b = b + 1 [P.f] {

b = b+ 1;

}

Рис. 2. Предикатные вычисления.

Исходный тест Безусловный код

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

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

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

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

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

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

Метод, расширяющий применимость этого вида анализа на случай произвольного региона позволяет включить в рассмотрение поток данных, входящих в регион через ф-узлы. На рис. 3 представлен пример, в котором на основе анализа предикатов удаётся определить, что операция store a, v [рО] доминирует над операцией use гО [р4], следовательно, оптимизация удаления избыточных чтений применима.

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

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

and рО pi р2

store a, v [рО] load а -> i0 and р2 рЗ р4 use гО [р4] and р5 рб р7_

move р5 -> рО move р7 р2

II

Рис.3. Пример предикатного кода.

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

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

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

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

Одной из основных составляющих технологии анализа зависимостей в циклах является технология сохранения информации о длинах измерений массивов.

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

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

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

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

Ключевыми параметрами в постановке задачи межпроцедурного анализа являются:

- множество объектов программы, для которых проводится анализ;

- степень детализации результатов анализа.

Все объекты программы можно разделить на два класса:

1. Статические объекты, которые пользователь явно определил статически, и память под которые отводиться во время компиляции. Эти объекты составляют символьную таблицу программы.

2. Объекты, память под которые заказывается в процессе исполнения программы. Эти объекты иногда называют динамически заказываемыми объектами или Heap-объектами.

Статические объекты делятся на скалярные, структурные и объекты-массивы.

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

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

Как правило, для статических объектов структурного типа различают поля структур и не различают отдельные элементы объектов-массивов.

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

1. Все динамические объекты рассматриваются как единый объект.

2. Разбивают на классы эквивалентности по части статической цепочки вызовов.

3. Разбивают на классы эквивалентности по размеру заказываемого объекта.

4. Разбивают на классы эквивалентности по способу доступа к таким объектам (k-limiting).

Степень детализации результатов анализа имеет 2 измерения:

1. Внутрипроцедурное (flow sensitivity).

2. Межпроцедурное (context sensitivity).

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

Межпроцедурная детализация определяет, как мы оцениваем вклад конкретного вызова процедуры в результаты анализа. Фактически это определяет, каким образом мы различаем результаты анализа для одной и той же процедуры в зависимости от места ее вызова и отличаем ли вообще (полное отсутствие детализации).

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

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

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

Решающее продвижение в сторону применимости высокой степени детализации анализа на практике было сделано в работе Уилсона и Лэм (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.). В этой работе был предложен подход к управлению степенью детализации с помощью частичных трансферных функций (ЧТФ, Partial Transfer Function). Каждая такая функция может переприменяться в тех местах вызова функции, для которой она создана, где текущие результаты анализа согласуются с внутренней структурой частичной трансферной функции. Этот механизм позволил избавиться от необходимости применения графа активаций, позволяя при желании получить такую же степень детализации анализа как в подходе с его использованием. В работе Уилсона и Лэм этот подход был использован для решения проблемы межпроцедурного анализа указателей. Однако авторам не удалось применить этот подход к задачам большого размера из-за проблем с длительной работой анализа в рекурсивных циклах. Эта проблема была успешно решена в диссертационной работе путем использования комбинированного подхода к проведению анализа. Для нерекурсивных процедур используется подход аналогичный подходу, описанному в работе Уилсона и Лэм, а для случая,

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

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

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

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

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

Выводы по результатам диссертации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

работают в составе двоичного компилятора для архитектуры «Эльбрус-ЗМ» с кодов 1Л:е1-х86.

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

Список работ, опубликованных по теме диссертации

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

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

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

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

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

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

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

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

Принято к исполнению 05/11/2004 Исполнено 05/11/2004

Заказ № 431 Тираж 100 экз

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Балаклавский пр-т, 20-2-93 (095) 747-64-70 (095)318-40-68 www autoreferat ru

Ï2331B

РНБ Русский фонд

2005-4 23145

Введение

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.

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 требует глобализации имени.