Разработка и реализация методов потокового анализа распараллеливаемых программ в Преобразователе программ СБкЗ_ПП

1.2 Представление программ

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

Внутреннее представление программы в компиляторе -- это специальная структура, в форме которой хранится информация о преобразуемой (компилируемой, оптимизируемой, конвертируемой) программе. Внутреннее представление должно быть удобно для преобразований программ. В это внутреннее представление должны преобразовываться программы на языках ФОРТРАН, ПАСКАЛЬ, Си. Поскольку большинство описанных в статьях преобразований программ ориентированы на ФОРТРАН, внутреннее представление также ближе к ФОРТРАНу.

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

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

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

· Указатель на запись в основной базе

· Имя счетчика цикла

· Левая граница

· Правая граница

· Шаг

· Метка последнего оператора тела цикла

· Идентификатор последнего оператора тела цикла

· Список счетчиков циклов, содержащих данный

· Канонизирован ли этот цикл

· Содержит ли этот цикл внутри себя другие циклы

· Распараллеливается ли этот цикл

Канонический вид операторов и выражений

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

Всякий цикл с параметром (фортрановский DO, паскалевский FOR) может быть приведен к виду, в котором левая граница счетчика-- 1 и шаг-- 1.

Любые условные операторы могут быть сведены к блочному условному оператору «IF THEN ELSE ENDIF». При этом ELSE во внутреннем представлении удобно тоже считать оператором.

Для некоторых преобразований важно, чтобы выражения программы были приведены к некоторому стандартному виду. Особенно это необходимо при построении графа информационных связей. Без такого стандарта трудно, например, понять, что вхождения Х(2*I +1), Х(1 + I*2), Х(2*I + 2 - 1) и Х(I + 1 + I) информационно зависимы. В данной работе предлагаются следующие стандартные требования к записи выражений:

Аргументы коммутативной бинарной операции должны следовать в алфавитном порядке. Например, P*Q а не Q*P.

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

Сумма двух одинаковых выражений с может быть, разными числовыми множителями заменяется таким выражением с множителем, который равен сумме исходных. 3*I -- I > 2*I.

Можно выносить общий множитель-переменную, пользуясь законом дистрибутивности. Но при вызове такой процедуры следует указывать, какие множители следует выносить. Такая процедура может выполняться благополучно лишь тогда, когда исходное выражение линейно зависит от совокупности указанных переменных (если их несколько). Например, А*В + А*С + В*С >> А*В + (А + В)*С, если выражение надо приводить относительно переменной С. Заметим, что в этом примере невозможно привести исходное выражение относительно переменных А и В одновременно, поскольку выражение нелинейно зависит от их совокупности. Если выносимый множитель является не константой, а переменной или подвыражением, то он пишется слева или справа в зависимости от алфавитного порядка с переменной, относительно которой множитель выносится.

При записи отношений будем использовать «<» вместо «>» и «<=» вместо «>=». (х + 2) < О вместо 0 > (х + 2).

Булевы выражения следует приводить к ДНФ (дизъюнктивной нормальной форме), в которой аргументы конъюнкций и дизъюнкций расположены в алфавитном порядке. При этом, выражение без отрицания должно записываться раньше такого же выражения с отрицанием. Например, Not(A) and В and Z or В and Y or not(B) and C.

Арифметические подвыражения над константами следует заменять их числовыми значениями. Например, числом -5 можно заменить выражение (3 -- 4*2).

Унарный «--» можно выносить, как множитель, если это особо оговорено в параметрах процедуры.

Пример.

Х(I)*2 - 2*Х(I - 1) > 2*Х(I) - 2*Х(I - 1)

-2*Х(I) > (А(I) - 2))* Х(I)

-2*X(I) > X(I) *(Y(I) - 2))

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

Пример.

5*(X-Y) + (A + 1)*(X + Y) > 5*X-5*Y+(A+ 1)*X + (A+ 1)*Y> > (5 + (А +

1))*Х + (-5 + (А + l))*Y > (А + 6)*Х + (А - 4)*Y.

В арифметических выражениях, особенно в индексных, могут быть «приведены подобные». Последние два слова взяты в кавычки, поскольку это понятие четко не определено, хотя и знакомо всем со школьных лет. В данной системе под приведением подобных понимается функция, у которой на входе арифметическое выражение F и список переменных {Al, A2, ..., As}. На выходе -- равносильное выражение А 1*F1 + A2*F2 +...+ As*Fs + F(s + 1) (здесь Fl, F2, ..., F(s + 1) - некоторые арифметические выражения, не зависящие от Al, A2, ..., As) или сообщение о невозможности такого представления. Такое приведение необходимо, в первую очередь, в индексных выражениях. Только после этого может строиться какой-либо информационный граф. Оно может быть также использовано для приведения рекуррентных циклов к виду

DO 99 I = 1, N 99 X(I)=F1*X(i-1)+...+Fs*X(I-s)+F(s+1)

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

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

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

Эквивалентность перестановки операторов присваивания может быть описана с помощью графа информационных связей Лампорта, а эквивалентность перестановки циклов -- с помощью направлений зависимости. Из-за того, что вхождение переменной в текст программы может многократно обращаться к памяти, граф информационных связей Лампорта теряет некоторую информацию об информационных зависимостях. Направление зависимости тоньше в том смысле, что оно отражает последовательность обращений к памяти различных циклов гнезда, содержащего данное вхождение. Направление зависимости часто рассматривается между операторами, а не вхождениями - это более грубое допущение, чем в графе Лампорта. Самый тонкий анализ зависимости дает решетчатый граф, активно исследуемый в работах В.В. Воеводина и P. Feautrier (следует отметить, что этот граф концептуально рассматривался и ранее, начиная с работы Лампорта о «методе гиперплоскостей»). Но анализ эквивалентности преобразований программ на основе этого фа-фа пока недостаточно разработан. Омега-тест и тест Банерджи - это средства для построения дуг графа информационных связей или направлений зависимости. Тест Банерджи более быстрый, а Омега-тест - более тонкий.[17]

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

Абстрактные синтаксические деревья

Листья - терминалы, остальные узлы - нетерминалы грамматики языка.

Корень AST - стартовый символ грамматики.

Дуги AST - правила вывода грамматики.

Из AST обычно исключается «синтаксический сахар», т.е. разделители и другие грамматические символы, не несущие семантической информации.

Листья и узлы AST помечаются атрибутами, характеризующими их свойства.

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

Язык описания преобразований

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

· вставить поддерево/узел,

· удалить поддерево/узел,

· изменить поддерево/узел,

· скопировать поддерево/узел,

· изменить его атрибуты поддерева/узла, …

Такое представление может помочь избежать синтаксических ошибок при проведении преобразований.

Язык описания преобразований должен оперировать поддеревьями AST или аналогичным древовидным представлением.

Язык должен быть близким к предметной области, чтобы максимально облегчить использование разработчиками преобразований.

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

Язык описания преобразований ASTOL

Язык ASTOL (AST Operating Language - язык оперирования AST) разрабатывается в настоящее время.

Язык является императивным;

Язык содержит операторы, модифицирующие поддеревья AST программы (элементарные преобразования), а также операторы модификации атрибутов отдельных узлов;

Язык позволяет описывать структуру дерева AST конкретного языка;

Для программ на языке ASTOL разрабатывается конвертор, переводящий код с ASTOL в классы языка Си++.

ASTOL: раскрутка цикла

transformation unroll(for_stmt src)

{

// блок операторов, который заменит собой цикл

declvar block_stmt block = createBlock();

/* создаем переменную с именем и типом, совпадающим со счетчиком цикла src */

createVarDeclaration(block, src[counter][type], src[counter][name], src[min]);

rcopy(block.last_stmt, src.increment_stmt);

// в цикле по всем итерациям исходного цикла…

for(int index=src[min], src[max], src[step])

{

// копируем в конец блока тело исходного цикла…

rcopy(block.last_stmt, src.body);

// затем копируем оператор, инкрементирующий счетчик

rcopy(block.last_stmt, src.increment_stmt);

}

// заменяем исходный for на созданное поддерево…

rreplace(src, block);

}

ASTOL

В примере элементарными преобразованиями являются:

· createBlock (создание составного оператора),

· createVarDeclaration (создание описания переменной),

· rcopy (рекурсивное копирование узла и всех потомков),

· rreplace (рекурсивная замена узла и всех потомков).

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

Логические спецификации для описания статической семантики

· Правила статической семантики задаются логическими предикатами и функциями.

· Правила могут быть двух видов - правила-определения и правила-ограничения.

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

Правила-определения

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

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

· Например, для дерева-выражения правило-определение может рекурсивно вычислять тип выражения, основываясь на типах поддеревьев:

Правила-ограничения

Правила-ограничения собственно и задают статическую семантику.

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

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

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

Если не удаётся, то программа считается некорректной. Причем нарушившееся правило и определяет причину ошибки.

Априорная проверка корректности преобразований

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

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

Априорная проверка корректности преобразований

Основная идея:

· Если программа изначально семантически корректна, то после применения преобразования она может стать некорректной, т.е. нарушится одно или более правил-ограничений.

· Преобразование состоит из последовательности элементарных преобразований.

· Необходимо определить, какие элементарные преобразования могут привести к нарушению какого типа правила.

· Каждое ограничение статической семантики принадлежит одному из 5 типов.

· Для каждого элементарного преобразования можно автоматически определить правила какого типа оно может нарушить.

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

Например, удаление узла может нарушить правила о необходимости его существования и т.д.

Пусть рассматриваемое правило принадлежит типу «многие-к-одному»:

A B P(A, B)

Отрицание правила имеет вид:

A | B P(A, B)



Условие P(A, B) будет нарушено, если требуемый узел B не существует хотя бы для одного узла A.

Т.к. изначально программа была корректной, то это означает, что:

· какой-то узел (узлы) B был удален;

· были изменены атрибуты узлов, используемые для вычисления предиката P;

· был добавлен новый узел A;

· изменены атрибуты существующего узла, участвующие в вычислении P.

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

Условия нарушения типов правил

· Программа-преобразование состоит из композиции элементарных преобразований.

· Автоматически проверяем каждое его элементарное преобразование и делаем вывод об ошибках во всем преобразовании.

· Разработчик преобразования должен проанализировать предупреждения системы о нарушениях его преобразованием правил статической семантики и сделать необходимые исправления в программе-преобразовании.

Автоматический перевод программы-преобразования в С++/Java

Программы, записанные на языке описания преобразования ASTOL, можно при необходимости перевести в код на языке С++ или Java.

При этом потребуется поддержка со стороны системы, ориентированной на использование древовидного внутреннего представления, например Открытой распараллеливающей системы. [13], [17]

Знаменитый компилятор GNU GCC использует следующее внутреннее представление программ [14]:

RTL

Большая часть работы компилятора GCC осуществляется над промежуточным представлением называемым Register Transfer Language (RTL).

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 1

Register Transfer Language используется для представления инструкций.При этом инструкции подробно описываются в духе списка LISP.

RTL оперирует пятью типами объектов:

· Выражения (expressions)

· Целые числа (integers)

· Длинное целое (wide integers)

· Строки (strings)

· Вектора (vectors)

RTL формат

Каждый элемент RTL имеет:

· GET_CODE: код операции

o GET_RTX_CLASS: тип RTL

o GET_RTX_FORMAT: строка с типом каждого параметра

o GET_RTX_LENGTH: количество операндов

· GET_MODE: режим

o SImode: 4-х байтное целое

o QImode: 1 байтное целое

o SFmode: 4-х байтное с плавающей точкой

· Список операндов

· Флаги

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Пример RTL

· Суммирует два операнда (plus: SI (<операнд 1>) (<операнд 2>))

o Операнды рассматриваются как четырехбайтные целые (plus: SI…)

· Первый операнд - это регистр (reg: SI 8)

o Регистр хранит 4-х байтное целое (reg : SI 8)

o Номер регистра - 8 (reg: SI 8)

· Второй операнд - целое число (const_int 128)

o Значение - число `128' (const_int 128)

o Режим VOIDmode (не указан)

Представление констант в RTL

(const_int i) Этот тип выражения представляет целочисленное значение i. Пример: (const_int 128)

(const_vector:m [x0 x1 …]) Представляет вектор констант. В квадратных скобках указаны значения, хранящиеся в векторе. M собственно указывает тип значений

Представление регистров и памяти в RTL

(reg:m n) Для малых значений n (меньших константы FIRST_PSEUDO_REGISTER) эта запись будет означать ссылку на конкретный аппаратный регистр. Для больших значений n это будет означать временное значение или псевдорегистр.

(mem:m addr alias) Означает ссылку на основную память по адресу addr. M означает тип объекта к которому ведется обращение (размер). Alias означает имя переменной.

Представление арифметических выражений в RTL

(plus:m x y) Представляет сумму значений представленных x и y для типа m.

(compare:m x y) Представляет результат вычитания y из x с целью сравнения.

SSA форма в GCC

Static Single Assignment Form (SSA Form) - форма представления программы в которой любой переменной значение присваивается не более одного раза.

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

Минусы представления RTL и дерева, используемого front end, как промежуточных представлений при работе оптимизатора

Большинство проходов работают с RTL представлением.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 2

Почему ни RTL представление, ни дерево в Front end не подходит для современных методов оптимизации.

RTL обладает рядом минусов. Основные из них:

· Не подходит для высокоуровневых преобразований

· Потеряна оригинальная структура программы

Можно попробовать проводить оптимизацию на деревьях Front end. Ряд алгоритмов так и делают. Особенно, если оптимизация зависит от языка программирования.

Деревья:

· Отражают структуру исходной программы

· Поддерживают высокоуровневые (близкие к исходному коду) преобразования

НО:

Каждый front end использует свой диалект дерева.

Представление Tree SSA

Tree SSA - это новая система оптимизации основанная на SSA представлении и действующая на GCC Tree представлении. Идея заключается в использовании специального представление в целом очень похожего на дерево, используемое в Front end, но унифицированное для всех поддерживаемых языков. Разработчики обещают внедрить данное представление в ближайших версиях GCC. Мы рассмотрим корни этой идеи: SSA-представление и управляющий граф.

SSA

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

Ниже показаны типичные примеры преобразования в SSA форму.

If P then V 4 else V 6 /* используем далее V*/

If P then V1 4 else V2 6

V3 Ф(V1, V2) /* используем далее V3*/

В местах соединения добавляем специальное присваивание.

V 4

V + 5

V 6

V + 7

V1 4

V1 + 5

V2 6

V2 + 7

Каждое присваивание значения переменной дает ей новое уникальное имя.

Управляющий граф

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

Управляющий граф (control flow graph) - это направленный граф, в вершинах которого расположены базовые блоки, а дуги соответствуют переходам.

Преобразование в SSA

Пусть программа представлена в виде control flow graph.

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

Преобразование программы в SSA форму - двухэтапный процесс:

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

На втором этапе генерируются новые переменные (находятся зависимости, переменные получают «версии»).

Массивы

«Хитрость» работы с массивами заключается в том, что все обращения к элементам массивом оборачиваются специальными функциями.

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

Рассмотрим случай обращения к элементу массива.

Исходный код, использующий массивы:

A(i)

A(j) A(i)

A(k) + 2

Эквивалентный код, в котором использованы специальные операторы доступа:

Access(A, i)

A(j) Update(A, j, V)

T Access(A, k)

T + 2

SSA форма:

Access(A8, i7)

A9(j) Update(A8, j6, V5)

T1 Access(A9, k4)

T1 + 2

Применение SSA

· Продвижение констант

· Удаление «мертвого кода»

· SSA представление также используется для определения эквивалентности программ.

Fortran-DVM [9] использует следующее описание:

Дерево разбора

Таблица символов и Таблица типов

Элементы Таблицы символов и Таблицы типов

признак
идентификационный номер
индекс
глобальный номер строки
локальный номер строки
спецификатор
указатель на метку
указатель на следующий оператор
указатель на имя файла
указатель на родителя по управлению
список свойств
список вершин(список процедур)
указатель на комментарий
указатель на Таблицу символов
L-дерево выражения
R-дерево выражения
запасное поле для выражения
do-метка (используется для do)
список-по-управлению-1
список-по-управлению-2 (для if)
запасное поле

Вершина дерева разбора, представляющая оператор (bif node)

признак
идентификационный номер
указатель на следующую вершину
указатель на элемент Таблицы типов
значение костанты
указатель на элемент Таблицы символов
L-дерево выражения
R-дерево выражения

Вершина дерева разбора, представляющая выражение (ll -node)

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

Элементы Таблицы типов и Таблицы символов

1.3 Задачи потокового анализа

Анализ потоков данных предложен в работах [8], [16].

Задача:

· определение глобальных свойств программы

· проверка контекстных условий оптимизирующих преобразований

Идея:

· определение свойств исполнения программы для каждого пути в графе управления

· выделение общей части

Способ:

· итеративный алгоритм анализа потоков данных

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

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

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

Пример:

struct S {int a; int b};

int F (int n, struct S * v)

{

int i, s = 0;

for (i=0; i<n; i++)

{

int q = (v+i)->a - (v+i)->b;

if (q < 0) s += (v+i)->a + (v+i)->b;

else (v+i)->b = q;

(v+i)->a = (v+i)->b;

}

return s;

}

Выше приведен фрагмент программы. Вхождения одного и того же выражения (v+i)->b, обведенные сплошной линией, являются эквивалентными. В то же время вхождение того же самого выражения, обозначенное пунктирной линией, не эквивалентно первым двум, поскольку else-часть условного оператора содержит разрушающее присваивание.

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

Достижимые определения

struct S {int a; int b};

int F (int n, struct S * v)

{

int i, s = 0;

for (i=0; i<n; i++)

{

int q = (v+i)->a - (v+i)->b;

if (q < 0) s += (v+i)->a + (v+i)->b;

else (v+i)->b = q;

(v+i)->a = (v+i)->b;

}

return s;

}



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

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

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

На слайде показан пример программы, в котором выделены вхождения некоторых переменных и некоторые присваивания. Стрелки ведут от определений (присваиваний) к вхождениям переменных.

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

Живые переменные:

struct S {int a; int b};

int F (int n, struct S * v)

{

int i, s = 0; {n, v}

for (i=0; i<n; i++) {i, s, n, v}

{

int q = (v+i)->a - (v+i)->b; {i, s, n, v}

if (q < 0) s += (v+i)->a + (v+i)->b; {i, s, n, v, q}

else (v+i)->b = q;

(v+i)->a = (v+i)->b;{i, s, n, v, q}

}

return s;

}

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

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

Пример решения данной задачи для конкретной программы показан на слайде.

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

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

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

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

Разметки и потоковые функции:

(X, <) - множество «фактов» с отношением частичного порядка

G = (V, E, start, stop) - граф потока управления

: V X - разметка

Отношения на разметках:

1= 2 vV 1(v)=2(v)

1< 2 vV 1(v)<2(v)

1 2 vV 1(v)<2(v) или 1(v)=2(v)

F: (V X) (V X) - функция перехода

s - неподвижная точка F F(s)= s

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

· формализовать решение задачи с помощью подходящей полурешетки

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

· применить итеративный алгоритм.

1.4 Методы потокового анализа

В работе [16] предложен следующий подход:

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

Функцией перехода называется отображение F, которое переводит одну разметку в другую. Разметка s называется неподвижной точкой отображения F тогда и только тогда, когда F(s)=s.

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

Итеративный алгоритм

(X, <) - множество конечной высоты N:

{x1, x2, ....}, xiX, xi<xi+1 k, l (k>N)&(l>N) xk=xl

F - функция перехода:

F()

Итеративный алгоритм:

0 - начальная разметка

c=0

while (F(c) c) do c =F(c);

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

Частично-упорядоченное множество X называется множеством конечной высоты N тогда и только тогда, когда длины всех строго возрастающих последовательностей элементов X ограничены N. Это означает, что для произвольной возрастающей последовательности начиная с некоторого места все элементы становятся одинаковыми.

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

Полурешетки

L - множество c операцией :

xx = x

· xy = yx

· xyz)=(xy)z

Индуцированное отношение порядка:

xy xy=x

Ограниченная полурешетка:

верхняя и нижняя грани:

L: xL L x

TL: xL x TL

Монотонные функции:

f : LL: xy f(x)f(y)

Дистрибутивные функции:

f : LL: f(xy) = f(x)f(y)

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

Полурешетка L называется ограниченной тогда и только тогда, когда в ней существуют наибольший TL и наименьший L элементы.

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

Неподвижные точки монотонной функции

L - ограниченная полурешетка конечной высоты

f : LL - монотонная функция

· xL : f(x)=x

Lf={xL : f(x)=x} - ограниченная полурешетка конечной высоты

TLf=fn() - наименьшая неподвижная точка, где

f0(x)=x

fn(x)=f(fn-1(x))

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

· функция f обладает хотя бы одной неподвижной точкой

· множество всех неподвижных точек f является ограниченной полурешеткой конечной высоты

· наименьшая неподвижная точка f может быть получена итерированием функции f начиная с наименьшего элемента L

Пример

A={a, b, c, d, ..., z}

L=2A - ограниченная полурешетка конечной высоты |A|

· xy=xy

· TL=A

· L=

f(x)=x{a} - монотонная функция

· TLf=A

· Lf={a}

Lf={x : ax}

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

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

Произведение полурешеток

L1, L2, ...., Lk - ограниченные полурешетки конечной высоты

L=L1L2....Lk={<x1, x2, ..., xk>, xiLi}

- ограниченная полурешетка конечной высоты:

· <x1,x2,...,xk><y1,y2,...,yk>=<x1y1,x2y2,...,xkyk>

· <x1,x2,...,xk> <y1,y2,...,yk>(x1y1)&(x2y2)&...&(xkyk)

· TL=<TL1,TL2,...,TLk>

· L=<L1,L2,...,Lk>

f1,f2,...,fk - монотонные функции на L1, L2, ..., Lk

f(<x1,x2,...,xk>)=<f(x1),f(x2),...,f(xk)> - монотонная функция на L

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

Набор монотонных функций f1,f2,...,fk соответственно на полурешетках L1,L2,...,Lk аналогичным образом индуцирует монотонную функцию на их декартовом произведении.

Формализация задачи анализа потоков данных

граф потока управления G

ограниченная полурешетка конечной высоты L

vV fv : LL- монотонная функция перехода

разметка before : VL

разметка after : VL

· наименьшее решение системы уравнений

/before(v)=wpred(v)after(w) /

/after(v)=fv(before(v)) /(*)

Пусть есть ограниченная полурешетка конечной высоты L, граф потока управления G и набор монотонных на L потоковых функций fv для каждой вершины v графа G.

Тогда решением задачи анализа потоков данных называется пара наименьших разметок before, after, являющихся решением системы уравнений (*), приведенной на слайде.

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

1.5 Теоретические свойства методов

Свойства итеративного подхода [16]:

· Нахождения точного решения задачи анализа потоков данных неразрешимо

Если все fv - дистрибутивны, то наименьшая неподвижная точка F есть точное решение задачи анализа потоков данных

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

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

Алгоритм с рабочим списком:

void Traverse (W: list<Vertex>) {

if (W is empty) return;

else {

Vertex v = any of W;

W = W \ {v};

after = fv(wpred(v)after(w));

if (after after (v)) {

after (v) = after;

W = W succ(v);

}

}

Traverse (W);

}

void DFA (G: CFG, L: Semilattice) {

for vV do before(v)=after(v)=L;

Traverse ({start});

}

1.6 Опыт реального применения распараллеливающего компилятора

Рассмотрим некоторые компиляторы.

Достижения компилятора Intel [10]:

Согласно результатам прогона тестов SPEC CPU2000, опубликованным на сервере ixbt.com, компиляторы Intel версии 6.0 практически везде оказались лучше по сравнению с компиляторами gcc версий 2.95.3, 2.96 и 3.1, и PGI версии 4.0.2. Эти тесты проводились в 2002 году на компьютере с процессором Pentium 4/1.7 ГГц и ОС RedHat Linux 7.3.

Согласно результатам тестов, проведенных компанией Polyhedron, компилятор Intel Fortran версии 7.0 почти везде оказался лучше по сравнению с другими компиляторами Fortran 77 для Linux (Absoft, GNU, Lahey, NAG, NAS, PGI). Только в некоторых тестах компилятор Intel незначительно проигрывает компиляторам Absoft, NAG и Lahey. Эти тесты были проведены на компьютере с процессором Pentium 4/1.8 ГГц и ОС Mandrake Linux 8.1.

Поддержка стандартов

Компилятор Intel C++ Compiler 7.0 for Linux поддерживает стандарт языка Си ANSI/ISO (ISO/IEC 9899/1990). Возможно установка строгой совместимости со стандартом ANSI C (-ansi) или расширенного диалекта ANSI C (-Xa). При использовании опции -c99 поддерживается некоторое подмножество стандарта C99: ключевое слова restrict, массивы переменной длины, комплексные числа, объявления переменных в произвольных местах кода, макро-определения с переменным числом аргументов, inline-функции, булевский тип и др.

Поддерживается стандарт ISO/IEC 14882:1998 языка С++.

Компилятор Intel Fortran Compiler 7.0 for Linux поддерживает спецификацию ISO Fortran 95, а также совместим на уровне исходных текстов с компилятором Compaq Visual Fortran 6.6.

Несомненно, в настоящее время среди свободно распространяемых открытых компиляторов самым развитым является компилятор GCC [14]. Это перенацеливаемый (как по входному языку, так и по целевой архитектуре) компилятор доступный по лицензии GPL.

Отметим некоторые характерные черты данного компилятора:

· Поддерживает большое число языков и машинных архитектур:

o Языки: С, С++, Ada95 (GNAT), Fortran 77, Fortran 95, Pascal, Modula-2, Modula-3, Java, Cobol, Chill (Cygnus).

o Архитектуры: ARM, Alpha (DEC), Intel x86, Motorola 680x0, 68C11, DSP56000, Hitachi SH и H8300, MIPS, IBM PowerPC, HP PA-RISC, SUN SPARC, IA64, AMD x86-64.

· По качеству не уступает многим известным компиляторам (в том числе и коммерческим). Так, на Alpha результаты работы GCC сравнимы с компилятором от DEC.

· GCC является постоянно развивающимся проектом. Отметим основные направления работы по развитию компилятора:

o реализация новых языков программирования;

o реализация новых алгоритмов оптимизации;

o введение поддержки новых платформ;

o улучшение библиотек времени исполнения;

o ускорение процесса отладки.

1.7 Средства реализации распараллеливающего компилятора

В качестве инструментального средства разработки компилятора Fortran-DVM [9] используется система Sage++.

Sage++ представляет собой объектно-ориентированную инструментальную систему для построения систем преобразования программ на языках Фортран, Си и Си++. Она является открытой библиотекой классов Си++, которая предоставляет пользователю набор синтаксических анализаторов, дерево разбора, таблицы символов и типов. Ядро системы составляет набор функций для реструктурирования дерева разбора и механизм (называемый unparsing) для генерации нового кода по реструктурированному внутреннему представлению.

Компилятор FDVM состоит из четырех компонент:

· Синтаксический анализ

· Преобразование дерева разбора

· Генерация кода на языке Фортран 77

· Генерация кода на языке HPF

Синтаксический анализ

Синтаксический анализатор системы Sage++ для Фортрана, который базируется на GNU Bison версии языка YACC, расширен средствами обработки директив DVM.

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

Преобразование дерева разбора

Вторая фаза компиляции включает анализ и реструктурирование внутреннего представления FDVM-программы. Директивы DVM заменяются последовательностями вызовов функций системы поддержки Lib-DVM. Затем новый код генерируется по модифицированному внутреннему представлению.

Программа “back-end” написана на языке C++ с использованием библиотеки классов Sage++.

Библиотека Sage++ организуется как иерархия классов, которая обеспечивает доступ к дереву разбора, Таблице символов и Таблице типов каждого файла из прикладного проекта. В библиотеке имеется пять основных семейств классов: Project и Files, Statements, Expressions, Symbols, Types.

Project и Files соответствуют исходным файлам. Statements соответствуют операторам языка Фортран и директивам DVM. Expressions - это выражения, содержащиеся в операторах. Symbols являются объявленными пользователем идентификаторами. Types представляют типы, которые ассоциируются с каждым идентификатором и выражением.

Описания всех классов содержатся в файле libSage++.h.

Семь модулей составляют транслятор:

· dvm.cpp - анализ и трансляция конструкций языка FDVM

· funcall.cpp - генерация вызовов функций библиотеки Lib-DVM

· stmt.cpp - реструктурирование дерева разбора

· io.cpp - трансляция операторов ввода-вывода

· debug.cpp - поддержка отладочного режима

· help.cpp - вспомогательные подпрограммы

· hpf.cpp - трансляция конструкций языка HPF-DVM

Генерация кода на языке Фортран 77

Генерация нового кода на языке Фортран 77 по модифицированному внутреннему представлению осуществляется посредством функции unparse( ) класса File из библиотеки классов Sage++.

Генерация кода на языке HPF

Когда исходная FDVM-программа конвертируется в программу на языке HPF, следующие подпрограммы и таблицы используются:

· unparse_hpf.c - подпрограммы генерации кода на языке HPF

· low_hpf.c - подпрограммы нижнего уровня, используемые для генерации

· unparse.hpf - таблица, управляющая генерацией кода на языке HPF2

· unparse1.hpf - таблица, управляющая генерацией кода на языке HPF1



1.8 Компиляция с переменным набором оптимизирующих преобразований

В компиляторе GCC оптимизация управляется с помощью флагов [23].

Перечисленные ниже опции управляют оптимизацией.

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

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

Компилятор производит оптимизацию, основываясь на том, что он знает о программе. На уровнях оптимизации -O2 и выше, в частности, становится доступен режим unit-at-a-time, позволяющий компилятору учитывать информацию о следующих функциях файла при компиляции текущей. Компиляция нескольких исходных файлов в один выходной в режиме unit-at-a-time позволяет компилятору использовать информацию, собранную при компиляции каждого файла в отдельности.

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

Флаги оптимизации -On (комбинации флагов -f флаг)Флаги оптимизации -On (комбинации флагов -fфлаг)

-O1

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

-O2

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

-O3

Больше оптимизаций. -O3 включает все оптимизации -O2 а так же

-finline-functions,

-funswitch-loops

-fgcse-after-reload options.

-O0

Не оптимизировать. По-умолчанию.

-Os

Оптимизация размера. -Os включает -O2 оптимизации, не увеличивающие размер исходного кода. Так же включает другие оптимизации, уменьшающие размер кода.

Оптимизация для архитектуры процессораОптимизация для архитектуры процессора

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

ACOVEA [18] использует генетический алгоритм для нахождения лучшего набора оптимизаций.

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

Код на C++ к этой статье основан на последней версии библиотеки классов Evocosm.

Сам генетический алгоритм AVOCEA прямой: начальная популяция состоит из случайных наборов опций компилятора («организмов»), как предусмотрено объектом компилятора. В AVOCEA 4.0.0 компилятор определятся XML-файлом.

В каждом поколении, gccacovea компилирует исполняемый файл для каждого набора опций. При выполнении, эталонные тесты замеряют время своих критических циклов внутренне, используя clock_gettime, отправляя результата обратно gccacovea как их «здоровье». Маленькое значение (меньшее время выполнения) означает большее «здоровье» и большую вероятность воспроизведения; мутация и миграция между популяциями вносит вариации для предотвращения стагнации популяции. В сущности, нахождение лучшего набора опций для GCC - это классическая задача минимизации.

XML-конфигурации компилятора

Файл конфигурации - это XML-документ, устанавливающий опции и команды, по умолчанию и эволюционирующие, для заданного компилятора и платформы. Например, конфигурация gcc34_opteron.acovea предназначена для GCC версии 3.4, работающего на 64-битной системе AMD Opteron.

Об анализе

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

Как определить, какие опции действительно важны среди шума «нулевых» опций?

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

Когда AVOCEA завершит прогон тестов, она отобразит «полезные» и «вредные» опции, набор предложенных решений и маленькую диаграмму сравнения производительности этих предложенных решений на базовых тестах. Например, когда тестируется компилятор, AVOCEA сравнивает результаты своих решений с результатами, полученными при использовании параметров компилятора -O1, -O2 и -O3. Генерируется изящно маленькая текстовая диаграмма, показывающая сравнительную производительность. Будущая версия AVOCEA-GTK будет предоставлять наглядные столбики.

Чтобы различать «полезные» и «вредные» опции, берутся финальные суммы и вычисляется «z-счет» для каждой опции. Z-счет измеряет разницу между значением и средним по популяции в единицах среднеквадратичного отклонения. Если z-счет опции больше единицы, считается, что она может быть полезна, когда z-счет меньше или равен -1 - это указывает на то, что опция вредна. В общем, большее число прогонов (большее число больших популяций развивается в течение большего числа поколений) будет усиливать разницы между «хорошими» и «плохими» опциями, причем некоторые достигнут z-счета равного 3 и более.

Управляемый пакет оптимизаций [5] - это пара <P,M>, где Р - пакет оптимизаций, а М - менеджер пакета оптимизаций. Пакет оптимизаций представляет собой набор оптимизаций с одним и тем же объектом применения. Менеджер оптимизаций определяет порядок запуска оптимизаций пакета. Он может выполнять дополнительный анализ на применимость и эффективность оптимизаций, входящих в пакет. Помимо этого, менеджер оптимизаций может сам выполнять ряд преобразований промежуточного представления, имеющих тот же тип, что и элементы пакета. Например, если объект оптимизации - операция, то менеджер пакета может преобразовать узел управляющего графа, если - цикл, то преобразуется дерево циклов. В этом случае у оптимизаций пакета есть возможность не выполнять преобразования, а заказать композицию преобразований своему менеджеру.