 |
Построение расширенного графа управления
|
|
|
|
Выполнение задач дипломной работы осуществлялось на языке C++ с использованием библиотеки Sage++ 2.0. В данном пункте приведены описания классов, составляющих программный код дипломной работы, использованные в их наиболее существенных методах алгоритмы, а также условия, которым должна удовлетворять входная программа для успешной ее обработки системой в целом, и реализованным в дипломной работе блоком в частности.
Ограничения на входную программу
Первое требование к входной программе заключается в ее корректности с точки зрения синтаксиса и семантики Fortran77. Заключенные в ней ошибки, не определенные на этапе разбора текста средствами Sage++, могут привести к непредсказуемым результатам.
Общим для всей системы ограничением является также ее достаточно высокая чувствительность к плохой структурированности программы, а именно:
· в программе не должны присутствовать операторы прекращения выполнения;
· запрещены операторы перехода, за исключением выхода из тела цикла на первый за концом цикла оператор по условию.
Другим существенным требованием является запрет на использование COMMON-областей.
Ограничения, накладываемые в данной дипломной работе:
· выражения в заголовках циклов (начальное, конечное, шаг) могут быть только линейными относительно некоторой переменной, т.е. иметь вид C1*V+C0, где C1 и C0 - константы, V - переменная;
· индексные выражения в обращениях к массивам должны удовлетворять тому же условию;
· отсутствие аппарата поиска зависимостей по данным влечет необходимость вставки пользователем комментария “DEPENDENCE” в теле цикла, содержащего зависимость.
Описание классов
В рамках дипломной работы реализовано два набора классов:
|
|
|
1. Классы, выполняющие построение внутреннего представления, экспорт данных для блока распределения вычислений и данных, последующий импорт результатов работы этого блока и генерацию текста на FortranDVM.
2. Классы, используемые в блоке распределения вычислений и данных. Выполняют импорт внутреннего представления и воссоздают его структуру, а также производят экспорт результатов работы этого блока.
Рассмотрим назначение классов 1-го набора и их наиболее важные члены.
1) Класс cSourceProgramSg - представляет исходную последовательную программу. Обработка входной программы должна начинаться с создания объекта этого класса.
cSourceProgramSg (char *projfile) - конструктор класса, projfile - имя файла проекта Sage++; в этом конструкторе происходит открытие проекта, разбор входящего в него файла исходной программы, создание незаполненных графа, списка циклов и таблицы символов.
SgStatement * FirstSt () - 1-й оператор программы.
SgStatement * LastSt () - последний оператор программы.
cProgramGraphSg * PrgGraph () - граф программы.
cLoopListSg * LpList () - список циклов.
cSymbolTabSg * SymTab () - таблица символов.
void PrepareConsts () - замена в теле программы обращений к константам на их значения.
void PrepareLoops () - конвертация циклов программы к виду DO-ENDDO.
void BuildLoopList () - построение списка циклов.
void BuildProgGraph () - построение графа программы.
void PrintLoopList (ostream&) - вывод в поток списка циклов для просмотра.
void PrintProgGraph (ostream&) - вывод графа.
void PrintSymbolTab (ostream&) - вывод таблицы имен.
void ExportData (char*) - экспорт данных в файлы.
void ImportData (char*) - импорт данных из файлов;
void Unparse (char*) - генерация результирующего текста в файле, имя которого определяется параметром метода.
При экспорте данных в файлы образуются следующие файлы:
filename.gr - узлы графа;
|
|
|
filename.gri - индексный файл;
filename.lp - список циклов;
filename.st - таблица символов, где filename - параметр метода ExportData(char*).
2) Класс cProgramGraphSg - представляет расширенный граф программы.
cProgramGraphSg (cSymbolTabSg*, cLoopListSg*) - конструктор класса, создает пустой граф управления. Параметры - таблица символов и список циклов, на которые будет ссылаться граф.
cLoopListSg * LpList () - список циклов, используемый графом.
cSymbolTabSg * SymTab () - таблица имен, используемая графом.
cProgramGraphNodeSg * CurNode () - текущий узел.
int IsStart () - является ли текущий узел начальным.
int GoStart (), GoDown (), GoUp (), GoLeft1 (), GoLeft2 (),
GoRight1 (), GoRight2 (), GoId (long int) - переместить указатель на текущий узел соответственно на 1-й узел, вниз, вверх, влево по 1-й ссылке, влево по 2-й ссылке, вправо по 1-й ссылке, вправо по 2-й ссылке, на узел с заданным номером. Возвращает 1 при удачном переходе, 0 в противном случае..
void CountOpers () - подсчет числа операций для каждого узла графа.
void ExportData (ofstream&, ofstream&) - экспорт графа и индексной информации в потоки.
void ImportData (ifstream&) - импорт данных от блока распределения вычислений, подлежащих вставке в граф;
void Build (SgStatement*, SgStatement*, int, int) - построение графа.
void Unparse () - произвести вставку добавленных в граф данных во внутреннее представление Sage++;
3) Класс cProgramGraphNodeSg - представляет узел графа управления.
cProgramGraphNodeSg () - конструктор класса, создает новый узел.
SgStatement * poSt1, * poSt2, * poSt3 - принимают значения после построения графа.
Для линейного участка: poSt1 - 1-й оператор блока, poSt2 - последний оператор.
Для цикла: poSt1 - оператор заголовка цикла, poSt2 - оператор, завершающий цикл (ENDDO)
Для ветвления: poSt1 - IF, poSt2 - ELSE, poSt3 - ENDIF.
int Level - уровень вложенности, внешнему уровню соответствует 0.
int IsParal - признак возможности распараллеливания.
long int LoopId - для элементов типа “цикл” содержит номер соответствующего цикла из списка.
float Ver1, Ver2 - для элементов типа “ветвление” вероятность перехода соответственно по 1-й и 2-й ветви.
float Opers [df_OPERS_COUNT] - массив, в каждом элементе которого содержится количество соответствующих индексу элемента операций в блоке. Например, Opers[0] - число сложений, Opers[1] - вычитаний.
long int Id () - уникальный номер узла.
|
|
|
int NodeType () - тэг типа узла.
long int ExportData (ofstream&) - экспорт узла в файловый поток, возвращает количество записанных байт.
void ImportData (ifstream&) - импорт данных из файлового потока.
void Unparse () - произвести вставку добавленных в узел данных во внутреннее представление Sage++.
4) Класс cLoopListSg - представляет список циклов программы.
cLoopListSg (cSymbolTabSg*) - конструктор класса, создает пустой список циклов, параметр - таблица символов, на которую будет ссылаться список.
cSymbolTabSg * SymTab () - таблица символов, используемая списком.
cLoopListNodeSg * CurNode () - указатель на текущий элемент списка.
int GoStart (), GoEnd (), GoRight (), GoLeft (), GoId (long int) - переместить указатель на текущий узел соответственно на 1-й узел, последний узел, влево, вправо, на узел с заданным номером. Возвращает 1 при удачном переходе, 0 в противном случае.
void Analyse () - произвести необходимый анализ элементов списка.
void Build (SgStatement*, SgStatement*, int) - построить список.
void ExportData (ofstream&) - экспорт списка в файловый поток.
5) Класс cLoopListNodeSg - представляет элемент списка циклов.
cLoopListNodeSg () - конструктор класса, создает новый элемент.
long int Id () - номер элемента.
SgStatement * poSt1, * poSt2 - ссылки соответственно на оператор заголовка цикла и на оператор завершения цикла.
cSymbolSg * poCounterSym - ссылка на переменную-счетчик цикла.
cExpressionSg * poStartExpr, * poEndExpr, * poStepExpr - начальное, конечное выражения счетчика и выражение шага цикла.
long int IterNum - количество итераций цикла.
int Level - уровень вложенности.
int IoOp, GotoOp - флаги наличия в теле цикла операторов ввода\вывода и операторов перехода за тело цикла.
cVarListElemSg * LVar [df_MAX_LRVAR_COUNT], * RVar [df_MAX_LRVAR_COUNT] - списки обращений к переменным и элементам массивов на модификацию и на чтение соответственно.
sReduct RedVar [df_MAX_REDVAR_COUNT] - список редукционных переменных, содержащихся в теле цикла.
void AnalyseHead (cSymbolTabSg *) - произвести анализ заголовка цикла.
void AnalyseBodyVars (cSymbolTabSg*) - произвести анализ обращений к переменным и элементам массивов в теле цикла.
void AnalyseRedVars (cSymbolTabSg*) - произвести поиск редукционных переменных в теле цикла.
void AnalyseIoOp () - определить присутствие в теле цикла операций ввода\вывода.
|
|
|
void AnalyseGotoOp () - определить присутствие в теле цикла операторов перехода за тело цикла.
long int ExportData (ofstream&) - экспорт элемента в файловый поток, возвращает количество записанных байт.
6) Класс cSymbolTabSg - представляет таблицу символов. Реализована в виде двунаправленного списка элементов класса cSymbolSg.
cSymbolTabSg () - конструктор класса, создает пустую таблицу.
cSymbolSg * FirstSym () - указатель на 1-й элемент списка.
void ExportData (ofstream&) - экспорт таблицы в файловый поток.
7) Класс cSymbolSg - представляет элемент таблицы символов.
cSymbolSg () - конструктор класса, создает новый элемент.
long int Id () - уникальный номер элемента.
SgSymbol * poSgSym - ссылка на соответствующий элемент таблицы символов Sage++.
int Variant () - тэг вида элемента: переменная или массив.
int Type - код типа.
char * Name - строка имени.
int Dim () - размерность (для массива).
int DimLen (int i) - длина по i-му измерению (для массива).
cSymbolSg * LinkRight () - следующий в списке элемент.
cSymbolSg * LinkLeft () - предыдущий в списке элемент.
long int ExportData (ofstream&) - экспорт элемента в файловый поток.
int operator == (cSymbolSg&), operator!= (cSymbolSg&)
8) Класс cExpressionSg - представляет выражение. Текущая реализация класса позволяет хранить только выражения вида c1*V+c0, где c1,c0 - константы, V - переменная.
cExpressionSg (SgExpression*, cSymbolTabSg*) - конструктор класса, параметрами являются подлежащее разбору выражение, представленное объектом Sage++, и таблица символов, которая будет дополнена входящим в состав выражения идентификатором.
int Variant () - тэг вида выражения.
cSymbolSg * poVariable - ссылка на переменную выражения.
int IntC0 (), IntC1 () - значения констант, приведенные к типу int.
float RealC0 (), RealC1 () - аналогично, float.
double DoubleC0 (), DoubleC1 () - аналогично, double.
long int ExportData (ofstream&) - экспорт выражения в файловый поток.
int operator == (cExpressionSg&), operator!= (cExpressionSg&)
9) Класс cArrayRefSg - представляет ссылку на элемент массива.
cArrayRefSg (SgArrayRefExp*, cSymbolTabSg*) - конструктор класса, параметрами являются подлежащая разбору ссылка на элемент массива, представленная объектом Sage++, и таблица символов, в которую будут добавлены входящие в ссылку переменные и имя массива.
SgArrayRefExp * poSgArrRef - исходный объект Sage++.
cSymbolSg * poSym - идентификатор массива.
int SubscrNum - количество индексных выражений в ссылке.
cExpressionSg* SubscrList [df_MAX_DIM] - массив индексных выражений.
long int ExportData (ofstream&) - экспорт в файловый поток.
int operator == (cArrayRefSg&)
int operator!= (cArrayRefSg&)
10) Класс cVarListElemSg - представляет элемент списка обращений к переменным и массивам.
cVarListElemSg (SgVarRefExp*, cSymbolTabSg*), cVarListElemSg (SgArrayRefExp*, cSymbolTabSg*) - конструкторы класса, 1-й для разбора обращения к переменной, параметрами являются ссылка на переменную, представленная объектом Sage++, и таблица символов, в которую будут добавлены идентификаторы; 2-й для разбора ссылки на массив, параметры имеют тот же смысл.
|
|
|
int Variant () - тэг вида элемента (ссылка на переменную или на массив).
cSymbolSg * poSym - идентификатор переменной для ссылки 1-го вида.
cArrayRefSg * poArr - ссылка на массив для 2-го вида.
long int ExportData (ofstream&) - экспорт в файловый поток.
int operator == (cVarListElemSg&)
int operator!= (cVarListElemSg&).
Для каждого из описанных классов существует его аналог во втором наборе, имеющий такое же имя за исключением постфикса “Sg”. В классах-аналогах отсутствуют методы для построения структур и конструкторы разбора. Корректная инициализация объектов этих классов производится только за счет введенных методов импорта из файлового потока. В классе cProgramGraphNode добавлены члены-данные для хранения директив FortranDVM, формирование которых осуществляет блок распределения вычислений и данных, и методы для их вставки, а также реализован экспорт этих комментариев в файл.
Алгоритмы
Реализованные в дипломной работе классы блока статического построения расширенного графа управления программы и вспомогательных структур данных содержат большое число членов-методов, решающих задачи разной сложности. Остановимся на деталях реализации некоторых из них.
На самом внешнем уровне программы построения и экспорта всех структур находится функция main(). Ее основное содержание заключается в следующих строках:
cSourceProgramSg TestProg(projfile);
TestProg.PrepareAll();
TestProg.BuildAll();
TestProg.PrintAll(cout);
TestProg.ExportData(trgfile);
В первую очередь создается объект класса cSourceProgramSg, параметром конструктора которого является имя файла-проекта Sage++. Далее вызываются методы этого класса:
PrepareAll() - предварительная обработка Sage++ представления исходного приложения;
BuildAll() - построение всех структур;
PrintAll(cout) - вывод в поток cout построенных структур для просмотра;
ExportData(trgfile) - экспорт данных в файлы.
|
|
|
