Удаление общих подвыражений

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

Пример:

X, Y: ARRAY [1..10, 1..10] OF INTEGER

…

FOR I:=1 TO 10 DO

X[I, 2*J-1]:= Y[I, 2*J]

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

Общие подвыражения обычно обнаруживаются при анализе промежуточной формы представления программы.

Примеру соответствует следующая последовательность четверок:

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

(2) JGT I #10 (20)

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

(4) * i₁ #10 i₂

(5) * #2 J i₃

(6) - i₃ #1 i₄

(7) - i₄ #1 i₅

(8) + i₂ i₅ i₆

(9) * i₆ #2 i₇

(10) - I #1 i₈ {вычисление индексов для Y}

(11) * i₈ #10 i₉

(12) * #2 J i₁₀

(13) - i₁₀ #1 i₁₁

(14) + i₉ i₁₁ i₁₂

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

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

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

(18):= i₁₄ I

(19) J (2)

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

Четверки (5) и (12) совпадают, за исключением имени получаемого промежуточного результата. Операнд J не меняет своего значения между четверками (5) и (12). Таким образом, четверки (5) и (12) вычисляют одно и то же значение. Это означает, что мы можем удалить четверку (12) и заменить любые обращения к ее результату (i₁₀) на обращение к переменной i₃.

После замены i₁₀ на i₃ мы обнаружим, что четверки (6) и (13) также совпадают, за исключением имени результата. Следовательно, мы можем удалить четверку (13) и заменить i₁₁ на i₄.

Аналогично четверки (10) и (11) также могут быть удалены, поскольку они эквивалентны четверкам (3) и (4).

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.