Реферат: Оптимизация программ

Блок (линейный участок) - выполняемая по порядку последо­вательность операторов, имеющая единственную точку входа - первый оператор с меткой, на который может быть передано уп­равление, и единственную точку выхода - последний оператор.

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

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

блок B - это тройка вида (P,I,U),где

(1) P - список операторов S1,S2,...Sn (n>=0),

(2) I - множество входных переменных,

(3) U - множество выходных переменных.

При этом оператором называется цепочка (в общем случае) вида

A <--QB1...Br,

где A,B1,...,Br - переменные,Q - операция.

Здесь оператор присваивает значение переменной А и ссыла­ется на B1,...,Br.

Если оператор Sj ссылается на А, то либо А--входная пере­менная, либо осуществлено присваивание ей значения некоторым оператором до Sj, (т. е. некоторым оператором Si,(i<j) . Таким образом, внутри ,блока все переменные, на которые ссылаются, к этому моменту определены либо внутренним образом как перемен­ные, которым присвоены значения, либо внешним как входные пе­ременные. Аналогично каждая выходная переменная либо является входной переменной, либо ей присвоено значение некоторым опе­ратором.

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

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

3.2. Сильно связанная область

Для каждого блока B=(P,I,U) можно найти ориентированный ациклический граф , представляющий этот блок. При этом каждый лист графа (концевая вершина) соответствует одной входной пе­ременной в I, а каждая его внутренняя вершина - оператору из

P. Граф отражает порядок выполнения операторов программы и да­ет более наглядное представление, чем линейная последователь­ность операторов.

Если вершины i и j графа соответствуют участкам i и j программы, то дуга идет из i в j, если

1) последний оператор участка i не является ни оператором перехода, ни оператором останова, а участок j следует в программе за участком i или

2) последний оператор участка i является оператором пере­хода на метку L, которой помечен первый оператор участка j.

Сильно связанной областью направленного графа называется такое множество его вершин, что для любых двух вершин x и y (x != y) существует путь из x в y.

Будем рассматривать сильно связанные области Ri, обладаю­щие следующими свойствами:

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

2) Ri != Rj;

3) для каждого i<j или пересечение Ri и Rj пусто, или Ri является подобластью Rj (включена в нее).

4. Способы оптимизации

Различают две категории оптимизирующих преобразований: преобразования исходной программы в ее внутренней форме, кото­рые не зависят от объектного языка (машинно-независимые) и преобразования, осуществляемые на уровне объектной программы (машинно-ориентированные).

Методы первой категории применимы почти к любому алгебра­ическому языку - ФОРТРАНу, АЛГОЛу, PL/1 и.т.д.

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

- разгрузка участков повторяемости;