Теория языков программирования методов трансляции (стр. 29 )

read p

read q

цикл: r remainder(p, q) (остаток от деления)

if r = 0 goto выход

p q

q r

goto цикл

выход: write q

halt.

Если, например, входным переменным p и q присвоить значения 72 и 76 соответственно, то при обычной интерпретации выходная переменная к моменту выполнения оператора записи будет иметь значение 8. Таким образом, значением этой программы для входного присвоения p 72, q 56 служит «последовательность», вырабатываемая выходной переменной q.

Если заменить оператор goto цикл на if q¹0 goto цикл, то получим эквивалентную программу. Это следует из того, что оператора goto цикл нельзя достичь, если в четвертом операторе не выполняется условие r¹0. Поскольку в шестом операторе q принимает значение r, то выполнение седьмого оператора равенство q=0 невозможно.

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

Пример. Для некоторых типов данных можно считать, что a*a=0, тогда и только тогда, когда a=0. Если принять такой закон, то новая эквивалентная программа будет:

read p

read q

цикл: r remainder(p, q)

t r * r

if t = 0 goto выход

p q

q r

goto цикл

выход: write q

halt

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

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

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

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

6.3.2.  Анализ потока управления

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

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

1)  первый оператор в P или

2)  помечен идентификатором, появляющимся после goto в операторе перехода либо в условном операторе, или

3)  непосредственно следует за условным оператором.

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

1)  вплоть до оператора останова и включая его, или

2)  вплоть до входа в следующий линейный участок, но не включая его.

Пример.

Участок 1 read p

read q

Участок 2 цикл:r remainder(p, q)

if r = 0 goto выход

Участок 3 p q

q r

goto цикл

участок 4 выход: write q

halt

Из участков программы сконструировать граф, весьма похожий на блок-схему программы.

Определение. Графом управления назовем помеченный ориентированный граф G, содержащий выделенную вершину n, из которой достижима каждая вершина G. Вершину n назовем начальной.

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

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

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

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

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

Пример. Граф управления программой изображен на рис. 11.14.

Рис. 11.14. Граф управления.

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

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

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

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

Последовательность участков ℬ1, ℬ2, . ℬn из D назовем путем вычисления (участков) в F, если

1)  ℬ1- начальная вершина в F,

2)  для 1< i £ n существует дуга, ведущая из ℬi-1 в ℬi.

Другими словами, путь вычисления ℬ1, ℬ2, . ℬn – это путь в F из ℬ1 в ℬn в котором ℬ1 - начальная вершина.

Будем говорить, что участок ℬ¢ доминирует над участком ℬ, если ℬ¢ ¹ ℬ и каждый путь, ведущий из начальной вершины в ℬ, содержит ℬ¢.

Будем говорить, что ℬ¢ прямо доминирует над ℬ, если

1)  ℬ¢ доминирует над ℬ и

2)  если ℬ² доминирует над ℬ и ℬ² ¹ ℬ¢, то ℬ² доминирует над ℬ¢.

Таким образом, участок ℬ¢, прямо доминирует над ℬ, если – «ближайший» к ℬ¢ участок, доминирующий над ℬ.

Пример. На рис. ??? – это путь вычисления. Участок 1 прямо доминирует над участком 2 и доминирует над участками 3 и 4. Участок 2 прямо доминирует над участком 3 и 4.

Лемма.

1)  Если ℬ1 доминирует над ℬ2, а ℬ2 над ℬ3, то ℬ1 доминирует над ℬ3 (транзитивность).

2)  Если ℬ1 доминирует над ℬ2, то ℬ2 не доминирует над ℬ1 (асимметричность).

3)  Если ℬ1 и ℬ2 доминируют над ℬ3, то либо ℬ1 доминирует над ℬ2, либо ℬ2 над ℬ1.

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

Алгоритм вычисления прямого доминирования

Вход. Граф управления F и множество D = {ℬ1, ℬ2, . ℬ}.

Выход. Прямой доминатор DOM(ℬ) участка ℬ для которого ℬ'D, кроме начальной вершины.

Метод. DOM(ℬ) вычисляется рекурсивно для каждого из D–{ℬ1}. В любой момент DOM(ℬ) будет участком ближайшим к ℬ. Среди всех участков, для которых уже известно, что они доминируют над ℬ. В конечном итоге DOM(ℬ), будет прямым доминатором участка ℬ. Вначале DOM(ℬ) – это ℬ1 для всех из D–{ℬ1}. Для i =1,2,3..n выполняются следующие два шага:

1)  Исключаем участок ℬi из F. Находим все участки ℬ, ставшие теперь недостижимыми из начальной вершины F. Участок ℬi доминирует над ℬ тогда и только тогда, когда ℬ становится недостижимым из начальной вершины после исключения ℬi из F. Снова заносим ℬi в F.

2)  Предположим, что на шаге 1) обнаружено, что ℬi доминирует над ℬ. Если DOM(ℬ)=DOM(ℬi ), берем ℬi в качестве DOM(ℬ). В противном случае DOM(ℬ) не меняем.

Пример. Применим данный алгоритм к графу управления алгоритма Евклида. Здесь D={ℬ1, ℬ2, ℬ3, ℬ4}. Последовательные значения DOM(ℬ) после исследований участков ℬi 2£ i £ 4 приведены в табл. 11.5.