Сравнительный анализ промежуточных языков

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

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

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

Обратная польская запись операторов исходной программы безусловно отображает точную последовательность выполнения операций. Однако используемые при этом способы представления таких операторов исходной программы, как оператора безусловного перехода, ус­ловного оператора, оператора цикла и др., нарушающих линейность программы, существенно усложняют ОПЗ,.а, следовательно, и триадную запись с точки зрения ана­лиза логических и информационных связей в программе и собственно оптимизации. В то же время на уровне промежуточных языков, используемых в трансляторах не сохраняются все конструкции исходной программы Например, на уровне ОПЗ и триад оператор цикла представляется эквивалентной группой операторов присваивания, условного перехода и безусловного перехода (возврата к началу цикла). А оператор условного перехода заменяется оператором безусловного перехода на один метку по значению «ложь» и на другую метку по значению «истина».

Существующие методы получения триадной записи и; ОПЗ не могут отобразить все элементарные вычисления я подвыражения, которые должны быть подвергнуть оптимизации. В подтверждение этого утверждения рассмотрим, например, следующий фрагмент программы.

A=B*C*D–X**2; (1)

F=B+C–D+Y/Q1; (2)

P=(1-Z/Q)*(B–D+C); (3)

R=C*D; (4)

Обратная польская запись этого фрагмента имеет вид

ABC*D*X2**–=;

FBC+D–YQ1/+=;

P1ZQ/–BD–C+*=;

RCD*=;

Представим теперь этот фрагмент в виде последовательности триад обычным способом:

m₁ * B, C m₁₀ = F, m₉

m₂ * m₁, D m₁₁ / Z, Q

m₃ ** X, 2 m₁₂ – 1, m₁₁

m₄ – m₂, m₃ m₁₃ – B, D

m₅ = A, m₄ m₁₄ + m₁₃, C

m₆ + B, C m₁₅ * m₁₂, m₁₄

m₇ – m₆, D m₁₆ = P, m₁₅

m₈ / Y, Q₁ m₁₇ * C, D

m₉ + m₇, m₈ m₁₈ = R, m₁₇

Так как в этой последовательности нет ни одной группы одинаковых триад, то при оптимизации не будет обнаружено ни одного повторного вычисления, хотя на самом деле они в программе есть. Нетрудно видеть, что данном случае триадная форма не позволяет представить элементарное вычисление C*D в операторе (1) и всевозможные варианты вычисления подвыражения B–D+C в операторе (3). Между тем если бы триадная запись позволила представить все элементарные вычисления то после оптимизации рассматриваемый фрагмент исходной программы имел бы следующий вид:

T1=C*D;

T2=B+C–D;

A=B*T1–X**2;

F=T2+Y/Q1;

P=(1–Z/Q)*T2;

R=T1;

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

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

A=(B+X**4)/(C–X**3);

D=X**3–E+X**2;

обратная польская запись этого фрагмента имеетcя дующий вид:

ABX4**+CX3**–/=;

DX3**E–X2**+=;

Триадная запись этого фрагмента имеет вид

m₁ ** X, 4 m₇ = X, 3

m₂ + B, m₁ m₈ / m₇, E

m₃ ** X, 3 m₉ – X, 2

m₄ – C, m₃ m₁₀ – m₈, m₉

m₅ / m₂, m₄ m₁₁ + D, m₁₀

m₆ = A, m₅

Как видно из триадной записи, при просмотре этого фрагмента исходной программы в качестве повторных; вычислений могут быть обнаружены одинаковые триад m₃ и m₇, представляющие подвыражения Х**З в операторах (1) и (2).

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

m₁ * X, X m₉ = A, m₈

m₂ * m₁, X m₁₀ * X, X

m₃ * m₂, X m₁₁ * m₁₀, X

m₄ + B, m₃ m₁₂ – m₁₁, E

m₅ * X, X m₁₃ * X, X

m₆ * m₅, X m₁₄ + m₁₂, m₁₃

m₇ – C, m₆ m₁₅ = D, m₁₄

m₈ / m_4, m₇

Такой способ представления программ в триадной форме позволяет при оптимизации обнаружить в качестве повторных вычислений подвыражения Х**2 в триадах m₁, m₅, m₁₀, т₁₃ и Х**З в триадах m₂, m₆, m₁₁. После оптимизации рассматриваемый фрагмент исходной программы мог бы иметь следующий вид:

T1=X*X;

T2=T1*X;

A=(B+T2*X)/(C-T2);

D=T2–E+T1;

Предлагаю ознакомиться с аналогичными статьями: