2. Удаление инвариантов цикла

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

Примером инварианта цикла является вычисление выражения 2*J (четверка 5).

Значение J в цикле не изменяется. Поэтому четверку (5) можно поместить непосредственно перед циклом. Аналогичные соображения справедливы относительно четверок (6) и (7).

Получится:

(1) * #2 J i₃ {вычисление инвариантов цикла}

(2) - i₃ #1 i₄

(3) - i₄ #1 i₅

(4) := #1 I {инициализация цикла}

(5) JGT I #10 (16)

(6) - I #1 i₁ {вычисление индексов для X}

(7) * i₁ #10 i₂

(8) + i₂ i₅ i₆

(9) * i₆ #2 i₇

(10) + i₂ i₄ i₁₂ {вычисление индексов для Y}

(11) * i₁₂ #2 i₁₃

(12) := Y[i₁₃] X[i₇]

(13) + #1 I i₁₄ {конец цикла}

(14) := i₁₄ I

(15) J (5)

(16) {следующее предложение}

Количество четверок внутри тела цикла уменьшилось, с 14 до 11. Тело цикла выполняется 10 раз, поэтому общее количество операций, необходимых для выполнения FOR, сократилось со 141 до 114.

3. Замена операций на более эффективные

Рассмотрим в качестве примера фрагмент программы на Фортране:

DO 10 I = 1, 20

10 TABLE (I) = 2 ** I

Цикл DO порождает таблицу, содержащую первые 20 степеней двойки.

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

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

Подобные модификации могут быть осуществлены при вычислении относительного адреса элемента массива TABLE (I).

Если каждый элемент массива занимает 2 байта, то смещение вычисляется по формуле 2*(I - 1).

Dычисление требуемого смещения может быть получено путем сложения предыдущего смещения с 2. Поскольку сложение выполняется быстрее умножения, подобное преобразование приведет к более эффективному объектному коду.

4. Свёртка операндов

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

Пример:

При компиляции предложений:

S := ’TE’+’XT’;

X := 3 + Length(S)*2;

будет скомпилирован код эквивалентный

S := ’TEXT’;

X := 11;

Если выражением индекса массива была константа, то адрес элемента вычисляется во время компиляции. Доступ к элементу массива A[5,5] будет таким же эффективным, как доступ к отдельной переменной.

5. Короткое вычисление выражений

При коротком вычислении логических выражений код генерируется таким образом, что операция логического сложения (OR) не вычисляется, если один из операндов имеет значение ИСТИНА.

Аналогично:

- операция логического умножения (AND) не вычисляется, если один из операндов имеет значение ЛОЖЬ.

- операция умножения (*) не вычисляется, если один из операндов имеет значение 1.

- операция сложения не вычисляется, если один из операндов имеет значение 0.

6. Сдвиг вместо умножения

Операция X*C может быть заменена на X shl Y, если С = 2^Y.

Аналогично, если размер элементов массива равен степени 2, то для вычисления индекса массива используется инструкция SHL, а не MUL.

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

16