Машинно-независимая оптимизация. Источники оптимизации. Семантически-эквивалентные трансформации

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

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

Выделяют два типа машинно-независимой оптимизации:

  • Локальная оптимизация
  • Глобальная оптимизация

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

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

Разбиение трёхадресных команд на базовые блоки

Для разбиения потока трёхадресных команд на базовые блоки, необходимо сначала найти т.н. лидеров – т.е. команды, являющиеся первыми в базовых блоках. Правила поиска лидеров следующие:

  1. Первая трёхадресная команда промежуточного кода является лидером.
  2. Любая команда, являющаяся целью перехода (условного или безусловного), является лидером.
  3. Любая команда, следующая непосредственно за условным или безусловным переходом, является лидером.

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

Например, рассмотрим следующий трёхадресный код, призванный установить матрицу 10х10 в единичную (т.е. все элементы = 0, диагональ = 1). Считается, что элементы матрицы имеют тип с плавающей точкой длиной 8 байт, и что матрица хранится построчно:

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)

Применим алгоритм поиска базовых блоков. По первому правилу, команда (1) является лидером. По второму правилу, команды (3), (2) и (13) являются лидерами. По третьему правилу, команды (10) и (12) являются лидерами (если бы в коде была команда (18), она тоже была бы лидером по этому правилу). Соответствующие базовые блоки показаны в листинге:

  I [ 1) i = 1
 II [ 2) j = 1
    ⎡ 3) t1 = 10 * i
    ⎢ 4) t2 = t1 + j
    ⎢ 5) t3 = 8 * t2
III ⎢ 6) t4 = t3 - 88
    ⎢ 7) a[t4] = 0.0
    ⎢ 8) j = j + 1
    ⎣ 9) if j <= 10 goto (3)
 IV ⎡ 10) i = i + 1
    ⎣ 11) if i <= 10 goto (2)
  V [ 12) i = 1
    ⎡ 13) t5 = i - 1
    ⎢ 14) t6 = 88 * t5
 VI ⎢ 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 (где ? – произвольный оператор):

  1. Добавляем к i-й инструкции информацию о времени жизни x, y, z.
  2. Устанавливаем в таблице символов x как “не живая” и “не используемая”
  3. Устанавливаем в таблице символов y и z как “живые” и в качестве следующего использования указываем i-ю команду.

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

Например, рассмотрим базовый блок III из предыдущего примера:

3) t1 = 10 * i         (t1 -- живая(4), i -- живая(*))
4) t2 = t1 + j         (t2 -- живая(5), t1 -- мёртвая)
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) if j <= 10 goto (3)

Эта информация позволяет, например, в строках 4-6 переиспользовать переменную, которая становится “мёртвой”, например:

3) t1 = 10 * i
4) t1 = t1 + j
5) t1 = 8 * t1
6) t1 = t1 - 88
7) a[t1] = 0.0
8) j = j + 1
9) if j <= 10 goto (3)

Графы потоков

После того, как программа разбита на базовые блоки, поток управления представляется в виде графа. Узлами являются базовые блоки. Рёбрами связаны каждые два блока, первая команда одного из которых может в процессе исполнения следовать непосредственно за последней командой другого. Существует ровно две ситуации, когда это возможно:

  1. Существует условный или безусловный переход от конца одного блока к началу другого.
  2. Один блок следует непосредственно за вторым в коде, и второй не заканчивается безусловным переходом.

Неизбежно, существуют рёбра, начинающиеся и заканчивающиеся на одном и том же узле, как, например, в базовом блоке III в примерах выше.

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

Трёхадресный код в примерах выше даёт следующий граф потока:

Циклы в графе потока

Многие преобразования кода зависят от идентификации циклов в потоке управления. Мы будем говорить, что множество узлов L является циклом, если:

  1. В L существует узел, именуемый входом в цикл. Никакие другие узлы в L не имеют предшественников вне L, т.е. любой путь из входа в граф потока, проходящий через L, проходит и через вход в цикл.
  2. Каждый узел в L имеет непустой, полностью содержащийся в L (т.е. проходящий только по элементам L), путь ко входу в L.

По этому определению, граф потока имеет циклы:

  1. {III}
  2. {VI}
  3. {II, III, IV}

Оптимизация базовых блоков

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

Граф для базовых блоков строится следующим образом:

  1. В граф добавляются узлы для всех начальных значений переменных, появляющихся в базовом блоке
  2. Для каждой инструкции \(s\) в базовом блоке в граф добавляется связанный с ней узел \(N\). Дочерними узлами \(N\) являются узлы, соответствующие инструкциям, являющимся последними до \(s\) определениями операндов в \(s\) (эта информация получается из анализа времени жизни переменных)
  3. Узел \(N\) помечается оператором в \(s\). Кроме того, к каждому узлу присоединяется список переменных, последнее присваивания которым в блоке производится в команде, соответствующей данному узлу.
  4. Ряд узлов помечается как выходные. Это узлы, переменные которых живы при выходе из базового блока. Нахождение живых переменных относится к глобальной оптимизации и пока не рассматривается.

Такое представление базового блока позволяет применить следующие техники оптимизации:

  • Устранение локальных общих подвыражений
  • Устранение неиспользуемого кода
  • Переупорядочение инструкций с целью снижения времени жизни временных переменных
  • Применение алгебраических тождеств с целью сокращения объёма вычислений

Устранение локальных общих подвыражений и переупорядочение инструкций

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

Рассмотрим для примера трёхадресный код

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 -- живая)

Теперь построим граф:

Узлы для первых двух инструкций строятся прямолинейно. 3-я инструкция использует то же начальное значение c0, что и первая. Операнды 4-й инструкции – значение a, вычисленное в первой инструкции, и значение d0. Это те же операнды, что и в узле, соответствующем второй инструкции, и метки узлов совпадают, поэтому вместо добавления нового узла, мы повторно используем тот же узел.

На практике, построение графа удобно совместить с алгоритмом определения времени жизни.

Оптимизированный трёхадресный код несложно получить обходом этого графа в глубину:

a = b + c
b = a - d
d = b
c = b + c

Устранение неиспользуемого кода

Устранение неиспользуемого кода из графа можно произвести следующим образом: если у узла нет предков (т.е. результат операции не используется другими командами) и с ним не связано живых переменных, то удаляем этот узел. Повторное выполнение этой операции пока не закончатся такие узлы устранит весь неиспользуемый код.

Например, пусть в предыдущем примере переменная a на выходе из блока является живой, а переменные b,c,d – мёртвыми.

Тогда мы можем сразу удалить узел, которому соответствует c

Узел с переменными b,d теперь является корнем (не имеет предков), поэтому мы можем удалить теперь его, заодно удалив узел d0:

Применение алгебраических тождеств

Алгебраические тождества могут применяться непосредственно при построении графа. Так, в частности, если, например, операция * считается коммутативной, то при построении узла для операции 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], и последнюю команду можно оптимизировать, заменив на z = x.

Однако, команда (2) может изменить значение a[i], если j==i (что на момент компиляции может быть неизвестно). В таком случае такая “оптимизация” не будет являться семантически-эквивалентной, и скорее всего сломает логику программы.

Более корректная обработка работы с массивами выглядит следующим образом:

  1. Присваивание переменной элемента массива создаёт специальный узел с оператором =[] и двумя дочерними узлами, представляющими начальное значение массива и индекс. Переменная становится меткой узла.
  2. Присваивание элементу массива значения представляется специальным узлом []= и тремя дочерними узлами: начальным значением массива, индекс и значение. Этот узел не помечается переменными. Более того, при создании такого узла, все узлы, зависящие от массива аннулируются, т.е. помечаются таким образом, что их нельзя использовать повторно.

Работа с указателями и вызов процедур

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

Вызов процедур при отсутствии глобальной информации о потоках данных ведёт себя во многом аналогично указателям – если процедура P находится в области видимости переменной x, то вызов этой процедуры одновременно и использует узел, помеченный переменной x, и аннулирует его.