3. Машинно-независимая оптимизация.

Цель машинно-независимой оптимизации – исключить из компилируемой программы избыточные вычисления, мертвый и недостижимый код, оптимизировать поток управления, исключив избыточные передачи управления, оптимизировать циклы и гнезда циклов, оптимизировать вызовы функций (процедур) и возвраты из них.

3.1. Построение графа потока управления.

Машинно-независимая оптимизация выполняется над графом потока управления (ГПУ) процедуры. Посмотрим на простом примере, как строится ГПУ. В качестве такого примера можно взять фрагмент процедуры (функции) quicksort(a, m, j). Этот фрагмент в исходном представлении на языке C показан на рисунке 1, а в промежуточном представлении – на рисунке 2.

{ int i, j; int v, x; if (n <= m) return; /* Начало фрагмента */ i = m - 1; j = n; v = a[n]; while (1) { do i = i + 1; while (a[i] < v); do j = j - 1; while (a[j] > v);	if (i >= j) break; /* Обмен a[i], a[j] */ x = a[i]; a[i] = a[j]; a[j] = x; } /* Обмен a[i], a[n] */ x = a[i]; a[i] = a[n]; a[n] = x; /* Конец фрагмента */ quicksort(a,m,j); quicksort(a,i+1,n); }
Рисунок 1. Исходное представление фрагмента процедуры quicksort на языке C.

Большая часть инструкций выполняется в «естественном» порядке, т.е. в порядке их написания. Для нарушения естественного порядка используются инструкции перехода, условного (инструкции (8), (12) и (13) на рисунке 2) или безусловного (инструкция (22) на рисунке 2), и помеченные инструкции (инструкции (5), (9) и (23) на рисунке 2), определяющие места, на которые передается управление. Участки процедуры, не содержащие помеченных инструкций и/или инструкций перехода, называются базовыми блоками (или линейными участками).

Определение 1. Базовый блок представляет собой последовательность инструкций, обладающую следующими свойствами:

1. поток управления может входить в базовый блок только через его первую инструкцию, т.е. нет переходов в средину базового блока (единственный вход);

2. управление покидает блок без останова или ветвления, за исключением, возможно, в последней инструкции блока (единственный выход).

Из определения 1 следует, что первой инструкцией, или началом базового блока (НББ) может быть либо первая инструкция процедуры, либо помеченная инструкция, либо инструкция, следующая за инструкцией перехода.

(1)	i = m-1 НББ	(16)	t7 = 4*i
(2)	j = n	(17)	t8 = 4*j
(3)	tl = 4*n	(18)	t9 = a[t8]
(4)	v = a[tl]	(19)	a[t7] = t9
(5)	L1: i = i+1 НББ	(20)	t10 = 4*j
(6)	t2 - 4*i	(21)	a[t10] = x
(7)	t3 = a[t2]	(22)	goto L1
(8)	if t3<v goto L1	(23)	L3: t11 = 4*i НББ
(9)	L2: j = j-1 НББ	(24)	x = a[t11]
(10)	t4 = 4*j	(25)	t12 = 4*i
(11)	t5 - a[t4]	(26)	t13 = 4*n
(12)	if t5>v goto L2	(27)	t14 = a[t13]
(13)	if i>=j goto L3 НББ	(28)	a[t12] = tl4
(14)	t6 = 4*i НББ	(29)	t15 = 4*n
(15)	x = a[t6]	(30)	a[t15] = x
Рисунок 2. Промежуточное представление фрагмента процедуры quicksort. (НББ – начало базового блока; номера инструкций добавлены для ссылок).

Блок A		Блок E				Блок F
(1)	i = m-1	(14)		t6 = 4*i		(23)	L3:t11 = 4*i
(2)	j = n	(15)		x = a[t6]		(24)	x = a[t11]
(3)	tl = 4*n	(16)		t7 = 4*i		(25)	t12 = 4*i
(4)	v = a[tl]	(17)		t8 = 4*j		(26)	t13 = 4*n
Блок B		(18)		t9 = a[t8]		(27)	t14 = a[t13]
(5)	L1:i = i+1	(19)		a[t7] = t9		(28)	a[t12] = tl4
(6)	t2 - 4*i	(20)		t10 = 4*j		(29)	t15 = 4*n
(7)	t3 = a[t2]	(21)		a[t10] = x		(30)	a[t15] = x
(8)	if t3<v goto L1	(22)		goto L1
Блок D			Блок C
(13)	if i>=j goto L3		(9)		L2:j = j-1
Рисунок 3. Базовые блоки рассмат-риваемого фрагмента процедуры quicksort.			(10)		t4 = 4*j
			(11)		t5 - a[t4]
			(12)		if t5>v goto L2

Чтобы выделить базовый блок, достаточно к первой инструкции (такие инструкции помечены на рисунке 2 словом НББ) этого блока приписать все инструкции, расположенные между ней и первой инструкцией следующего базового блока (следующим НББ). На рисунке 2 отмечено 6 инструкций, являющихся началами базовых блоков (НББ). Это инструкции (1), (5), (9), (13), (14) и (23). Следовательно, рассматриваемый фрагмент процедуры состоит из 6 базовых блоков A, B, C, D, E, F (см. рисунок 3). Выделив базовые блоки, можно построить граф потока управления (ГПУ).

Вершинами графа потока управления процедуры являются базовые блоки, а направленные дуги соединяют каждый базовый блок с базовыми блоками, которые могут выполняться после этого блока. ГПУ рассматриваемого примера представлен на рисунке 4. Отметим, что для удобства в ГПУ добавляются две дополнительные вершины (не содержащие инструкций): entry (единственный вход в процедуру) и exit (выход из процедуры). Для задания ГПУ нужно задать множество N его вершин и множество E  N  N его направленных дуг.

Рисунок 4. ГПУ рассматриваемого фрагмента процедуры quicksort.

3.2. Локальная оптимизация.

Различают следующие виды оптимизации

• Локальная оптимизация – оптимизация в пределах одного базового блока (при этом каждый базовый блок рассматривается независимо от остальных).

• Оптимизация области – оптимизация в пределах части процедуры.

• Глобальная оптимизация – оптимизация в пределах процедуры.

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

• Межмодульная оптимизация – оптимизация всей программы (включая используемые ею библиотеки).

Рассмотрим сначала локальную оптимизацию.

3.2.1. Задачи локальной оптимизации.

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

• Сворачивание констант.

• Удаление избыточных подвыражений.

• Удаление мертвого кода.

• Изменение порядка инструкций, там, где это возможно, чтобы сократить время хранения временных значений на регистрах.

Сворачивание констант состоит в замене выражений, операндами которых являются константы с известными значениями, на константы, полученные в результате выполнения соответствующих операций. Например, следующие 3 инструкции:

a = 8

b = aa