Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления

Библиотека Sage++ реализована в виде иерархии классов C++, которые позволяют получить доступ к дереву разбора, таблице имен и таблице символов для каждого файла, входящего в исходное приложение. Классы объединены в пять семейств: “Проекты и файлы” – хранят информацию обо всех файлах приложения, “Операторы” – ссылаются на базовые операторы языков, “Выражения” – указывают на выражения, содержащие

ся внутри операторов, “Символы” – определенные в программе идентификаторы, “Типы” – сопоставленные с каждым идентификатором и выражением типы. Библиотека обеспечивает средства как всестороннего изучения исходной программы, так и различной ее модификации – добавление к ней новых файлов, создание и изменение операторов, входящих в файлы, вставка и модификация содержащихся в операторах выражений и др. Рассмотрим основные возможности Sage++, представляющие для нас интерес в рамках первого аспекта.

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

Для получения доступа к данным проекта существует класс SgProject:

SgProject(char *proj_file_name) - конструктор, proj_file_name - имя файла проекта;

int numberOfFiles() – количество файлов в проекте;

SgFile &file(int i) – i-й файл проекта.

Класс SgFile представляет файл, входящий в исходное приложение:

SgStatement *firstStatement() – указатель на первый оператор файла;

SgSymbol *firstSymbol() – указатель на первый элемент таблицы имен файла;

SgType *firstType() - указатель на первый элемент таблицы типов файла.

Каждый определенный в файле идентификатор содержится в таблице имен и представляется объектом одного из наследников класса SgSymbol:

int variant() – тэг, определяющий класс символа;

int id() - уникальный номер символа в таблице ;

char *identifier() - текстовое представление символа

SgType *type() - тип символа;

SgStatement *declaredInStmt() - оператор объявления;

SgSymbol *next() - указатель на следующий элемент таблицы.

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

SgVariableSymb – переменная программы;

SgConstantSymb - константа;

SgFunctionSymb - процедура, функция или главная программа.

С каждым идентификатором и выражением соотнесен его тип – скалярный или сложный, представленный объектом класса SgType или одного из его наследников:

int variant() - тэг типа, соответствующий либо скалярному типу, либо классу-наследнику;

int id() - уникальный номер типа в таблице типов;

SgType *baseType() - указатель на базовый тип для сложных типов;

SgType *next() – указатель на следующий элемент таблицы типов.

Пример производного от SgType класса – SgArrayType, объект которого создается для каждого определенного в программе массива. Основные члены этого класса:

int dimension() - размерность массива;

SgExpression *sizeInDim(int i) - выражение, характеризующее длину по i-му измерению.

Каждый файл программы разбит на операторы, для представления которых используется класс SgStatement и его производные:

int variant() - тэг оператора;

int id() - уникальный номер оператора;

int lineNumber() - номер строки в исходном тексте;

SgExpression *expr(int i) - i-е выражение, входящее в оператор (i = 0,1,2);

SgStatement *lexNext() - следующий в лексическом порядке оператор;

SgStatement *lexPrev() - предыдущий в лексическом порядке оператор;

SgStatement *controlParent() - охватывающий управляющий оператор;

SgStatement *lastNodeOfStmt() – для операторов, не являющихся листом дерева разбора, возвращает указатель на последний оператор поддерева.

Аналогично другим классам Sage++ тэг объекта SgStatement позволяет определить класс-потомок SgStatement, соответствующий рассматриваемому оператору. В каждом из них существуют данные и методы, специфические для представляемого этим классом оператора. Эти классы объединены в несколько семейств:

· заголовочные операторы;

· операторы объявления;

· управляющие операторы;

· исполняемые и другие операторы.

Примеры классов, относящихся к этим семействам.

Заголовочные:

§ SgProgHedrStmt – заголовок программы (Fortran);

§ SgProcHedrStmt – заголовок подпрограммы (Fortran);

§ SgBlockDataStmt – оператор блока данных (Fortran).

Операторы объявления:

§ SgVarDeclStmt – оператор объявления переменной;

§ SgParameterStmt – оператор объявления констант (Fortran);

§ SgImplicitStmt – оператор Implicit (Fortran).

Управляющие:

§ SgForStmt – цикл FOR;

§ SgIfStmt - оператор ветвления If-Then-Else (Fortran), if (C);

§ SgLogIfStmt - оператор логического If (Fortran);

§ SgArithIfStmt - оператор арифметического If (Fortran).

Исполняемые и другие:

§ SgAssignStmt - оператор присваивания (Fortran);

§ SgCallStmt - оператор Call (Fortran);

§ SgContinueStmt - оператор Continue;

§ SgControlEndStmt - обозначает конец одного из основных блоков (напр. ENDIF);

§ SgReturnStmt - оператор Return;

§ SgGotoStmt - оператор Goto.

Большинство операторов программы содержат некоторые выражения. Класс SgExpression является базовым для выражений всех видов:

int variant() - тэг вида выражения;

SgExpression *lhs() - левое поддерево выражения;

SgExpression *rhs() - правое поддерево выражения;

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

§ SgValueExp - представляет значение одного из базовых типов;

§ SgVarRefExp - ссылка на переменную или на массив;

§ SgArrayRefExp - ссылка на элемент массива;

§ SgFunctionCallExp - вызов функции.

Разработчиками Sage++ предлагается следующий алгоритм разбора исходной программы. Производится последовательный перебор файлов, входящих в проект. Начиная с указателя SgStatement* SgFile:: firstStatement() осуществляется обход операторов текущего файла. При этом анализируется оператор, входящие в него выражения, тело(а) – для операторов, содержащих таковое (например, управляющей группы). Переход на следующий оператор реализуется кодом cur_stmt=cur_stmt->lastNodeOfStmt()->lexNext() для операторов, не являющихся листом дерева разбора, и cur_stmt=cur_stmt->lexNext() для остальных (где cur_stmt – указатель на текущий оператор). Использование рекурсивного подхода к просмотру дерева представляется достаточно естественным.

2.2 Внутреннее представление программы высокого уровня

 Скачать реферат