Машинно-независимая оптимизация. Оптимизация базовых блоков
- первичная генерация промежуточного кода не очень эффективна
- вводится большое количество временных переменных
- можно избежать
Два типа машинно-независимой оптимизации:
- Локальная оптимизация
- Глобальная оптимизация
Разбиение трёхадресных команд на базовые блоки
- Находятся лидеры:
- Первая трёхадресная команда
- Любая команда, являющаяся целью перехода (условного или безусловного)
- Любая команда, следующая непосредственно за переходом
- Базовый блок каждого лидера расширяется до следующего лидера (не включая его) или конца программы.
⎢ 1) i = 1
⎢ 2) j = 1
⎢ 3) t1 = 10 * i
⎢ 4) t2 = t1 + j
⎢ 5) t3 = 8 * t2
⎢ 6) t4 = t3 - 88
⎢ 7) a[t4] = 0.0
⎢ 8) j = j + 1
⎢ 9) if j <= 10 goto (3)⎢→
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢⎢→
⎢→
⎢
⎢
⎢
⎢
⎢
⎢
⎢⎢→
⎢→
⎢→
⎢
⎢
⎢
⎢
⎢
⎢⎢ 10) i = i + 1
⎢ 11) if i <= 10 goto (2)
⎢ 12) i = 1
⎢ 13) t5 = i - 1
⎢ 14) t6 = 88 * t5
⎢ 15) a[t6] = 1.0
⎢ 16) i = i + 1
⎢ 17) if i <= 10 goto (13)⎢→
⎢
⎢
⎢
⎢
⎢
⎢
⎢⎢→
⎢
⎢→
⎢
⎢
⎢
⎢
⎢⎢→
⎢
⎢→
⎢→
⎢
⎢
⎢
⎢⎢ [
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢⎢ [
⎢ [
⎢
⎢
⎢
⎢
⎢
⎢
⎢⎢ [
⎢ [
⎢ ⎡
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎢ ⎣⎢ ⎡
⎢ ⎣
⎢
⎢
⎢
⎢
⎢
⎢⎢ ⎡
⎢ ⎣
⎢ [
⎢
⎢
⎢
⎢
⎢⎢ ⎡
⎢ ⎣
⎢ [
⎢ ⎡
⎢ ⎢
⎢ ⎢
⎢ ⎢
⎢ ⎣Информация о времени жизни переменных
- один из основных способов оптимизации – устранение избыточных переменных
- требует информации времени жизни переменных
- дополнительно осложняется тем, что переменные изменяемые
- Пусть i-тая команда присваивает переменную x
- Если j-тая команда имеет x в качестве операнда, и есть переход от i-й к j-й команде, на котором нет присваиваний переменной x
- то j-ая команда использует значение x, вычисленное в i-й команде.
- переменная x “живая” или “активная” между командами i и j.
- ограничимся рассмотрением внутри одного базового блока
- будем считать, что вызов процедур начинает новый базовый блок
- (процедуры в общем случае могут иметь произвольные побочные эффекты)
Последовательно сканируем базовый блок от конца к началу. Для каждой инструкции присваивания вида i) x = y ? z (где ? – произвольный оператор):
- Добавляем к i-й инструкции информацию о времени жизни x, y, z.
- Устанавливаем в таблице символов x как “не живая” и “не используемая”
- Устанавливаем в таблице символов y и z как “живые” и в качестве следующего использования указываем i-ю (текущую) команду.
- алгоритм требует, чтобы в начале в таблице символов была информация о “живых” переменных на выходе из базового блока
- задача глобальной оптимизации
- будем считать, что все не временные переменные – “живые”.
Например, рассмотрим базовый блок III из предыдущего примера:
3) t1 = 10 * i ⎢
4) t2 = t1 + j ⎢
5) t3 = 8 * t2 ⎢
6) t4 = t3 - 88 ⎢
7) a[t4] = 0.0 ⎢
8) j = j + 1 ⎢
9) if j <= 10 goto (3) ⎢
⎢
⎢ ⎢
⎢
⎢
⎢
⎢
⎢
⎢
таблица символов ⎢ i -- живая, j -- живая, a -- живая
⎢ ⎢
⎢
⎢
⎢
⎢
⎢
⎢ ←
таблица символов ⎢ i -- живая, j -- живая, a -- живая
⎢ ⎢
⎢
⎢
⎢
⎢
⎢
⎢ ←
таблица символов ⎢ i -- живая, j -- живая (9), a -- живая
⎢ ⎢
⎢
⎢
⎢
⎢
⎢ ←
⎢
таблица символов ⎢ i -- живая, j -- живая (9), a -- живая
⎢ ⎢
⎢
⎢
⎢
⎢
⎢ ← (j -- живая (9))
⎢
таблица символов ⎢ i -- живая, j -- живая (9), a -- живая
⎢ ⎢
⎢
⎢
⎢
⎢
⎢ ← (j -- живая (9))
⎢
таблица символов ⎢ i -- живая, j -- !живая, a -- живая
⎢ ⎢
⎢
⎢
⎢
⎢
⎢ ← (j -- живая (9))
⎢
таблица символов ⎢ i -- живая, j -- живая (8), a -- живая
⎢ ⎢
⎢
⎢
⎢
⎢ ←
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i -- живая, j -- живая (8), a -- живая
⎢ ⎢
⎢
⎢
⎢
⎢ ← (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i -- живая, j -- живая (8), a -- живая
⎢ ⎢
⎢
⎢
⎢
⎢ ← (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i -- живая, j -- живая (8),
⎢ a -- живая (7), t4 -- живая (7) ⎢
⎢
⎢
⎢
⎢ ← (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (8), a (7), t4 (7)
⎢ ⎢
⎢
⎢
⎢ ←
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (8), a (7), t4 (7)
⎢ ⎢
⎢
⎢
⎢ ← (t4 -- живая (7), t3 -- !живая)
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (8), a (7), t4 (7)
⎢ ⎢
⎢
⎢
⎢ ← (t4 -- живая (7), t3 -- !живая)
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (8), a (7)
⎢ ⎢
⎢
⎢
⎢ ← (t4 -- живая (7), t3 -- !живая)
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (8), a (7), t3 (6)
⎢ ⎢
⎢
⎢ ←
⎢ (t4 -- живая (7), t3 -- !живая)
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (8), a (7), t3 (6)
⎢ ⎢
⎢
⎢ ← (t3 -- живая (6), t2 -- !живая)
⎢ (t4 -- живая (7), t3 -- !живая)
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (8), a (7), t2 (5)
⎢ ⎢
⎢ ←
⎢ (t3 -- живая (6), t2 -- !живая)
⎢ (t4 -- живая (7), t3 -- !живая)
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (8), a (7), t2 (5)
⎢ ⎢
⎢ ← (t2 -- ж (5), t1 -- !ж, j -- ж (8))
⎢ (t3 -- живая (6), t2 -- !живая)
⎢ (t4 -- живая (7), t3 -- !живая)
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (2), a (7), t1 (4)
⎢ ⎢ ←
⎢ (t2 -- ж (5), t1 -- !ж, j -- ж (8))
⎢ (t3 -- живая (6), t2 -- !живая)
⎢ (t4 -- живая (7), t3 -- !живая)
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i, j (2), a (7), t1 (4)
⎢ ⎢ ← (t1 -- живая (4), i -- живая)
⎢ (t2 -- ж (5), t1 -- !ж, j -- ж (8))
⎢ (t3 -- живая (6), t2 -- !живая)
⎢ (t4 -- живая (7), t3 -- !живая)
⎢ (a -- живая, t4 -- !живая)
⎢ (j -- живая (9))
⎢
таблица символов ⎢ i (1), j (2), a (7)
⎢Эта информация позволяет, например, в строках 4-6 повторно использовать переменную, которая становится “мёртвой”, например:
3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t2 = t1 + j ⎢ (t2 -- ж (5), t1 -- !ж, j -- ж (8))
5) t3 = 8 * t2 ⎢ (t3 -- живая (6), t2 -- !живая)
6) t4 = t3 - 88 ⎢ (t4 -- живая (7), t3 -- !живая)
7) a[t4] = 0.0 ⎢ (a -- живая, t4 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ ← (t1 -- живая (4), i -- живая)
4) t2 = t1 + j ⎢ (t2 -- ж (5), t1 -- !ж, j -- ж (8))
5) t3 = 8 * t2 ⎢ (t3 -- живая (6), t2 -- !живая)
6) t4 = t3 - 88 ⎢ (t4 -- живая (7), t3 -- !живая)
7) a[t4] = 0.0 ⎢ (a -- живая, t4 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t2 = t1 + j ⎢ ← (t2 -- ж (5), t1 -- !ж, j -- ж (8))
5) t3 = 8 * t2 ⎢ (t3 -- живая (6), t2 -- !живая)
6) t4 = t3 - 88 ⎢ (t4 -- живая (7), t3 -- !живая)
7) a[t4] = 0.0 ⎢ (a -- живая, t4 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t1 = t1 + j ⎢ ← (t1 -- ж (5), j -- ж (8))
5) t3 = 8 * t1 ⎢ (t3 -- живая (6), t1 -- !живая)
6) t4 = t3 - 88 ⎢ (t4 -- живая (7), t3 -- !живая)
7) a[t4] = 0.0 ⎢ (a -- живая, t4 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t1 = t1 + j ⎢ (t1 -- ж (5), j -- ж (8))
5) t3 = 8 * t1 ⎢ ← (t3 -- живая (6), t1 -- !живая)
6) t4 = t3 - 88 ⎢ (t4 -- живая (7), t3 -- !живая)
7) a[t4] = 0.0 ⎢ (a -- живая, t4 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t1 = t1 + j ⎢ (t1 -- ж (5), j -- ж (8))
5) t1 = 8 * t1 ⎢ ← (t1 -- живая (6))
6) t4 = t1 - 88 ⎢ (t4 -- живая (7), t1 -- !живая)
7) a[t4] = 0.0 ⎢ (a -- живая, t4 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t1 = t1 + j ⎢ (t1 -- ж (5), j -- ж (8))
5) t1 = 8 * t1 ⎢ (t1 -- живая (6))
6) t4 = t1 - 88 ⎢ ← (t4 -- живая (7), t1 -- !живая)
7) a[t4] = 0.0 ⎢ (a -- живая, t4 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t1 = t1 + j ⎢ (t1 -- ж (5), j -- ж (8))
5) t1 = 8 * t1 ⎢ (t1 -- живая (6))
6) t1 = t1 - 88 ⎢ ← (t1 -- живая (7))
7) a[t1] = 0.0 ⎢ (a -- живая, t1 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t1 = t1 + j ⎢ (t1 -- ж (5), j -- ж (8))
5) t1 = 8 * t1 ⎢ (t1 -- живая (6))
6) t1 = t1 - 88 ⎢ (t1 -- живая (7))
7) a[t1] = 0.0 ⎢ ← (a -- живая, t1 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t1 = t1 + j ⎢ (t1 -- ж (5), j -- ж (8))
5) t1 = 8 * t1 ⎢ (t1 -- живая (6))
6) t1 = t1 - 88 ⎢ (t1 -- живая (7))
7) a[t1] = 0.0 ⎢ (a -- живая, t1 -- !живая)
8) j = j + 1 ⎢ ← (j -- живая (9))
9) if j <= 10 goto (3) ⎢3) t1 = 10 * i ⎢ (t1 -- живая (4), i -- живая)
4) t1 = t1 + j ⎢ (t1 -- ж (5), j -- ж (8))
5) t1 = 8 * t1 ⎢ (t1 -- живая (6))
6) t1 = t1 - 88 ⎢ (t1 -- живая (7))
7) a[t1] = 0.0 ⎢ (a -- живая, t1 -- !живая)
8) j = j + 1 ⎢ (j -- живая (9))
9) if j <= 10 goto (3) ⎢ ←Графы потоков
поток управления между базовыми блоками – в виде графа
базовые блоки – узлы
Рёбрами связаны блоки, первая команда одного из которых может следовать непосредственно за последней командой другого:
- Существует переход от конца одного блока к началу другого.
- Один блок следует непосредственно за вторым в коде, и второй не заканчивается безусловным переходом.
- Неизбежно, существуют рёбра, начинающиеся и заканчивающиеся на одном и том же узле, как, например, в базовом блоке III в примерах выше.
- перед началом локальной оптимизации условные переходы к командам заменяют на условные переходы к базовым блокам (номера команд внутри базового блока могут меняться)
Циклы в графе потока
преобразования кода зависят от идентификации циклов
множество узлов L является циклом, если:
- В L существует узел, именуемый входом в цикл. Никакие другие узлы в L не имеют предшественников вне L, т.е. любой путь из входа в граф потока, проходящий через L, проходит и через вход в цикл.
- Каждый узел в L имеет непустой, полностью содержащийся в L (т.е. проходящий только по элементам L), путь ко входу в L.
Циклы:
- {III}
- {VI}
- {II, III, IV}
Оптимизация базовых блоков
Один из методов локальной оптимизации. Базовый блок – в виде ориентированного ациклического графа.
Построение
- Добавляются узлы для всех начальных значений переменных, появляющихся в базовом блоке
- Для каждой инструкции добавляется узел. Дочерние – узлы инструкций, последних присваиваний операндам
- Узел помечается оператором в инструкции. К узлу присоединяется список переменных, которым присваивается значение.
- Узлы, переменные которых живы при выходе из блока, помечаются как выходные. Нахождение живых переменных – глобальная оптимизация, и пока не рассматривается.
Позволяет применить следующие техники оптимизации:
- Устранение локальных общих подвыражений
- Устранение неиспользуемого кода
- Переупорядочение инструкций с целью снижения времени жизни временных переменных
- Применение алгебраических тождеств с целью сокращения объёма вычислений
Устранение локальных общих подвыражений и переупорядочение инструкций
Удобно применять при построении графа – вместо создания новых узлов, сперва осуществляется поиск эквивалентного существующего узла. Этот метод рассматривался ранее.
Пример:
a = b + c
b = a - d
c = b + c
d = a - dПрименим алгоритм определения времени жизни:
1. a = b + c (a -- живая, следующее использование 2, 4)
2. b = a - d (b -- живая, следующее использование -- 3)
3. c = b + c (с -- живая)
4. d = a - d (d -- живая)1. a = b + c (a -- живая, следующее использование 2, 4)
2. b = a - d (b -- живая, следующее использование -- 3)
3. c = b + c (с -- живая)
4. d = a - d (d -- живая)Построим граф:
Оптимизированный трёхадресный код – обходом этого графа в глубину:
a = b + c
b = a - d
d = b
c = b + cУстранение неиспользуемого кода
Если у узла нет предков и с ним не связано живых переменных, он удаляется. Повторять пока не закончатся такие узлы.
Например, пусть в предыдущем примере переменная a на выходе из блока является живой, а переменные b,c,d – мёртвыми.
Исходно:
a = b + c
b = a - d
c = b + c
d = a - dИсходно:
a = b + c
b = a - d
c = b + c
d = a - d
Исходно:
a = b + c
b = a - d
c = b + c
d = a - d
- Удалим узел
c
Исходно:
a = b + c
b = a - d
c = b + c
d = a - d
- Удалим узел
c
Исходно:
a = b + c
b = a - d
c = b + c
d = a - d
- Удалим узел
c - Удалим узлы
b,dиd0
Исходно:
a = b + c
b = a - d
c = b + c
d = a - d
- Удалим узел
c - Удалим узлы
b,dиd0
Исходно:
a = b + c
b = a - d
c = b + c
d = a - d
- Удалим узел
c - Удалим узлы
b,dиd0:
Результат: a = b + c
Применение алгебраических тождеств
Алгебраические тождества – при построении графа.
Например, если * – коммутативная операция, то при построении узла для a * b, проверяется, есть ли уже такой узел. В силу коммутативности также проверяется узел для b * a.
Другие алгебраические законы, напр. ассоциативности, тоже могут применяться для оптимизации.
Возможные оптимизации диктуются стандартом языка – машинная арифметика не всегда строго соответствует алгебраической, какие-то преобразования могут быть недопустимы.
Например, по стандарту Fortran, компилятор может производить любые алгебраические замены, не противоречащие указанным в исходном тексте скобкам. Так, он может вычислять x*y-x*z как x*(y-z), но не может вычислять a+(b-c) как (a+b)-c.
Обращения к массивам
При работе с массивами – осторожность. Например, рассмотрим
1. x = a[i]
2. a[j] = y
3. z = a[i]Может показаться, что в (1) и (3) – одинаковое подвыражение a[i], и (3) можно заменить на z = x.
Однако, (2) может изменить a[i], если j==i. Такая “оптимизация” – не семантически-эквивалентная, и скорее всего сломает логику программы.
Более корректная обработка работы с массивами выглядит следующим образом:
x=a[i]– специальный узел=[]с дочерними узламиa0иi.xприсоединяется к узлу.a[i]=v– специальный узел[]=с дочерними узламиa0,iиv. Переменные не присоединяются. Ключевое, при создании узла, все узлы, зависящие от массива аннулируются, т.е. помечаются так, что их нельзя использовать повторно.
Работа с указателями и вызов процедур
Прямая работа с указателями похожа на работу с массивами, но x=*p в качестве дочерних узлов должен иметь все ранее определённые переменные, а *p=x аннулирует все переменные.
Вызов процедур (при отсутствии глобальной информации о потоках данных) – аналогично указателям. Если процедура P находится в области видимости переменной x, то вызов этой процедуры одновременно и использует узел, помеченный переменной x, и аннулирует его.