b = b – 1

заменяются во время оптимизации на следующие 2 инструкции:

a = 8

b = 63

Избыточными подвыражениями называются инструкции, повторно вычисляющие уже вычисленные значения. Например, в инструкциях (14) и (16) блока E (рисунок 3) вычисляется одно и то же значение 4*i, так как значение между инструкциями (14) и (16) не меняется. Таким образом, вычисление в инструкции (16) является избыточным, и эту инструкцию можно заменить на t7 = t6.

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

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

3.2.2. Локальный метод нумерации значений.

Начнем с рассмотрения простого примера. Выражение

a = а + y*(b +(y-z)*b)+(y-z)* b (1)

можно представить в виде синтаксического дерева (рисунок 6a). Если вместо синтаксического дерева построить ориентированный ациклический граф (ОАГ) (рисунок 6б), то сразу станут видны одинаковые значения (в рассматриваемом примере это b, y и (y – z)*b).

(а) АСД для выражения (1)	(б) ОАГ для выражения (1)
Рисунок 5. Ориентированный ациклический граф (ОАГ)

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

Описание метода нумерации значений. Выражение (1) вычисляется в базовом блоке, содержащем согласно АСД следующие инструкции (рисунок 6a):

t1 = y – z t2 = t1 * b t3 = b + t2 t4 = y * t3 a = a + t4 t5 = y – z t6 = t5 * b a = a + t6		1	id	ссылка в ТС		a		t1 = y – z t2 = t1 * b t3 = b + t2 t4 = y * t3 a = a + t4 t5 = t1 t6 = t2 a = a + t6
		2	id	ссылка в ТС		b
		3	id	ссылка в ТС		y
		4	id	ссылка в ТС		z
		5	-	3	4	t1, t5
		6	*	5	2	t2, t6
		7	+	2	6	t3
		8	*	3	7	t4
		9	+	1	8	a
		10	+	9	6	a
		# значения	Определение значения (сигнатура)			Переменные
(a)Блок E до оптимизации		(b) Массив Val#[]. Обычно вместо массива используется хеш-таблица					(c)После оптимизации
Рисунок 6. Локальный метод нумерации значений

Заведем массив Val#[] (рисунок 6b) Каждая строка массива представляет один узел ОАГ. Первое поле каждой записи представляет собой код операции (метку узла ОАГ), причем операция id определяет переменную, а операция num – константу (листовые узлы). Эти операции имеют всего один операнд – ссылку на описание переменной (константы) в таблице символов.

Тройка áop, #left, #rightñ, где ор – метка узла (код операции), а #left и #right – номера значений левого и правого дочерних узлов, – называется сигнатурой внутреннего узла (если op – унарная операция, #right полагается равным 0).

Номер значения – номер элемента массива, в котором определяется это значение. Если вместо массива используется хеш-таблица с хеш-функцией Val#(s), то номер значения, соответствующего сигнатуре s = áop, #left, #rightñ равен значению хеш-функции Val#(s). Номер значения левой части оператора присваивания по определению равен номеру значения его правой части.

Алгоритм (на псевдокоде) построения ОАГ для базового блока B, содержащего n инструкций вида t_i = Op_i, l_i, r_i. Функция #val(s) (хеш-функция) определяет номер значения, определяемого сигнатурой s.

for each "t_i = l_i Op_i r_i" do

#v = hash (Op_i, #val(l_i), #val(r_i))

if(#v is present in the hash-table)

then

#val(t_i) = #val(Op_i,l_i,r_i) = #v

else

insert a new value number into the table at the hash key
location and record that new value number for Ti

Пример. Применим метод нумерации значений для оптимизации базового блока E с рисунка 3. На рисунке 6(a) представлена последовательность инструкций P этого блока

1	num	ссылка в ТС		4		t6 = 4*i
2	id	ссылка в ТС		a		x = a[t6]
3	id	ссылка в ТС		i		t7 = 4*i
4	id	ссылка в ТС		j		t8 = 4*j
5	id	ссылка в ТС		x		t9 = a[t8]
6	*	1	3	t6, t7		p1 = a[t7]
7	[]	2	6	a[t6], a[t7], x		p1 = t9
8	*	1	4	t8, t10		t10 = 4*j
9	[]	2	6	a[t8], a[t10], t9		p2 = a[t10]
10	+	1	8	a		p2 = x
11	+	9	6	a		goto L1
# значения	Определение значения (сигнатура)			Левые части выражений присваивания

t6 = 4*i

x = a[t6]

t7 = 4*i

t8 = 4*j

t9 = a[t8]

p1 = a[t7]

p1 = t9

t10 = 4*j

p2 = a[t10]

p2 = x

goto L1

t6 = 4*i x = a[t6] t7 = 4*i t8 = 4*j t9 = a[t8] a[t7] = t9 t10 = 4*j a[t10] = x goto L1
Рисунок 7. (a) Последовательность инструкций базового блока E, таблица номеров значений и ОАГ.

Продолжим рассмотрение примера (рисунок 6). Пусть номера значений переменных a, b, c, d уже известны и равны #val(a)==1, #val(b)==2, #val(c)==3, #val(d)==4.

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

Особенности реализации локального метода нумерации значений.

3.3. Глобальная оптимизация.

3.3.1. Анализ потока данных.

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

3.3.2. Пример анализа потока данных – достигающие определения.

3.3.3. Анализ живых переменных.

3.3.4. Доступные выражения.

3.3.5. Итерационный алгоритм анализа потока данных на полурешетках.

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

3.3.6. Монотонные и дистрибутивные структуры потока данных.

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

Оптимизация переходов и возвратов из функций.

Открытая вставка функций.

3.3.8. Оптимизация циклов.

Развертка циклов.

Анализ индуктивных переменных

7