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

Делая в первой главе обзор процесса компиляции, мы уже выделили четыре основных направления оптимизации, которые не зависят от конкретной ЭВМ и ее машинного кода, а связанны только с языком программирования и алгоритмами, представленными на этом языке. К ним относятся:

• исключение общих подвыражений в арифметических и логических выражениях операторов присваивания или условий;

• вычисления во время компиляции;

• оптимизация булевских выражений с целью формирования эффективных условных переходов;

• вынесение инвариантных вычислений за цикл.

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

<операция> <операнд 1> <операнд 2> <результат>

<прямой указатель> <обратный указатель>

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

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

7.1. Исключение общих подвыражений

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

XAB  C) BB  2 YAB  C  )

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

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

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

BA ACD(DCB);

Матрица тетрад для этого фрагмента представлена на рис. 7.1 а.

Алгоритм исключения общих подвыражений может быть следующим:

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

2). Найти границы операторов - в данном случае конец каждого блока характеризуется тетрадой с операцией присваивания - ‘’. После шагов 1) и 2) матрица примет вид, представленный на рис. 7.1 б.

3). Найти общие подвыражения (совпадающие тетрады) и исключить одно из них (в нашем примере совпадают тетрады 2, 3 и мы исключаем третью тетраду, соединяя в цепочку тетрады с номерами 2 и 4). Если одинаковых тетрад не обнаружено перейти к пункту 6) алгоритма.

4). В результирующей матрице отразить исключение элемента, изменив ссылки на его результат (в нашем случае все ссылки к M2 меняются ссылками к M1). После шагов 3) и 4) мы получим матрицу представленную на рис. 7.1 в).

5). Повторить шаги 1) - 4) алгоритма.

6). Исключить из таблицы идентификаторов все элементы временной памяти, которые нам больше не нужны (в рассматриваемом примере элемент M2).