Из предыдущего параграфа видно, что для удовлетворения всех требований, которые предъявляются к промежуточному языку с точки зрения оптимизации, в триадную форму представления программ необходимо внести ряд существенных изменений.
Рассмотрим вначале возможности представления в триадной записи всех элементарных вычислений из выражений или подвыражений, в которых имеется несколько соседних знаков операций с одинаковыми приоритетами. В рассуждениях для простоты используем выражения, в которых имеется подряд только два знака, арифметических операций с одинаковыми приоритетами. Однако наши рассуждения будут справедливы и в тех случаях, когда число соседних операций с одинаковыми приоритетами больше двух.
Рассмотрим выражение общего вида
A=B Q1 C Q2 D, (*)
где Q1 и Q2 — знаки обобщенных арифметических операций с одинаковыми приоритетами. ОПЗ этого выражения будет иметь вид
ABC Q1 D Q2=
Заметим, что для выявления идентичности двух элементарных вычислений не имеет значения, какой вид имеет соответствующая триадная строка: mi Q a, b или mi Q b, a.
Если Q1 не является операцией деления или вычитания, то (*) может быть преобразовано в триадную форму тремя различными способами. В результате получим следующие триадные формы:
Если Q1 и Q2 — соответственно операции деления и умножения или вычитания и сложения, то формы 1) и 3) остаются без изменения, а форма 2) будет иметь вид:
Если Q1 и Q2 — обе операции деления или операции вычитания, то опять изменится только форма 2), которая будет иметь вид:
Форма 1) получается обычным методом получения триад из ОПЗ. Для получения из ОПЗ форм 2) и 3) необходимо придерживаться следующего простого правила. При просмотре ОПЗ, если рассматриваемый элемент и после него второй по счету элемент (обозначим его через J) являются знаками арифметической операции приоритеты этих знаков одинаковы, то для формы 2) первой выполняется операция Q2 (она представлена элементом J) над элементами (J—3) и (J—1), если операция Q1 (представленная элементом (J—2)) является знаком * или +. В случае, когда Q1 и Q2 — знаки операции/или —, то вместо операции Q2 выполняется операция 
. Если же Q1 и Q2 соответственно знаки / и * или — и +, то для формы 2) первой выполняется операция 
над элементами (J—1) и (J—3). Для формы 3) первой выполняется операция Q2 над элементами (J–4) и (J–1).
Каким бы способом ни представлять в триадной форме рассматриваемое выражение (*), конечный результат будет одним и тем же — вычисление значения А. Это обстоятельство позволяет представлять арифметические выражения в триадной форме описываемом ниже способом, который дает возможность установить идентичность максимального числа выражений и (или) подвыражений, выполняющих одно и то же вычисление. Если при просмотре ОПЗ какого-нибудь арифметического выражения в нем не окажется подвыражений, содержащих соседние знаки операций с одинаковым приоритетом, то эти подвыражения и рассматриваемое выражение в целом преобразуются в триады обычным способом. В противном случае те подвыражения, в которых имеются два соседних знака операций с одинаковыми приоритетами, преобразуются в триады способами 1), 2) или 3) одно за другим. Эти формы являются различными триадными записями одного и того же выражения. Чтобы в процессе анализа учитывать это обстоятельство, при записи каждой из этих форм используются одни и те же номера строк, но они снабжаются различными признаками, например @, @@, @@@. Поэтому в триадах должно быть предусмотрено поле для этих признаков.
Рассмотрим этот способ триадной записи на примере фрагмента исходной программы:
Обратная польская запись этого фрагмента имеет вид:
После преобразования в триадную форму фрагмент будет иметь вид (здесь и далее рамкой выделены общие выражения):
В процессе собственно оптимизации те триадные представления одного и того же подвыражения или выражения, в которых обнаружатся более общие вычисления относительно других выражении и подвыражений, будут в триадном представлении оставлены, а остальные будут исключены. Для рассматриваемого фрагмента после обнаружения неэффективных участков программы окончательное триадное представление будет выглядеть следующим образом:
Благодаря такой трансформации программы рассматриваемый фрагмент исходной программы после от оптимизации может выглядеть следующим образом:
Здесь может возникнуть следующий естественный вопрос. Как при преобразовании исходной программы в триадную форму учитывается то обстоятельство, что различные способы представления выражения (*) могу дать различные результаты вычисления в случаях, когда операнды существенно отличаются друг от друга по значению?
Нетрудно убедиться, что данный вопрос не имеет ничего общего с проблемой оптимизации.
Например, если в рассмотренном выше фрагменте программы переменные D и Е— очень малые числа а С—очень большое число, то при выбранном способе 2) представления выражения D*C/E в триадной форме может возникнуть ситуация переполнения. Данная форма записи этого выражения выбрана из-за того, что в программе имеется подвыражение С/Е. Однако независимо от способа представления выражения D*C/E в триадной форме все равно из-за выражения С/Е возникнет ситуация переполнения. А это должен учитывать программист при написании программы.
При конструировании реальных систем оптимизации можно ограничиться рассмотрением возможности появления одного за другим только двух знаков арифметических операций с одинаковыми приоритетами. Во-первых, появление одного за другим четырех и более знаков арифметических операций с одинаковыми приоритетами встречается вообще крайне редко. Во-вторых, рассматривая случай двух знаков, можно выявить одинаковые вычисления и при появлении подряд трех и более знаков арифметических операций с одинаковыми приоритетами. Например, при анализе операторов
все вычисления в правых частях будут определены как одинаковые, если, конечно, между этими операторами ни один из операндов не переопределяется.
Следует также заметить, что если при учете двух знаков рассматриваемое подвыражение можно представить тремя способами, то при учете трех знаков — уже двенадцатью способами. Это предъявляет повышенные требования к объему ЗУ и увеличивает затраты времени на обработку программы.
По этим же соображениям для выявления максимального числа повторных выражений подвыражения типа В**К, где К — целое число, 2£К£7, в триадной форме следует представлять с помощью К—1 строки операций умножения.
Для анализа всех типов элементарных вычислений промежуточный язык должен обеспечивать возможность, представлять не только выражения с простыми переменными, но и индексированные переменные и их индексы а также встроенные (стандартные) функции и их аргументы.
Для обеспечения такой возможности введем операции ВЫБОР ЭЛЕМЕНТА МАССИВА (ЭМ), операндами которой являются идентификатор массива и значения индексных выражений, а также операцию ФУНКЦИЯ (Ф), операндами которой являются идентификатор функции и идентификаторы аргументов. Кроме того, запятую «,» будем считать также знаком операции. Её аргументы — идентификаторы или индексы, которые она разделяет.
Покажем использование этих новых операций на примере. Пусть имеется фрагмент исходной программы
Обратная польская запись этого фрагмента будет следующей (Здесь унарный минус для отличия от обычного минуса представлен символом «И»):
Соответствующая триадная запись будет иметь вид
Такая запись программы позволит представить рассматриваемый фрагмент исходной программы в следующей оптимизированной форме:
Рассмотрим, как можно удовлетворить другое важное требование к промежуточной триадной форме — сохранить все конструкции исходного языка и тем самым структуру исходной программы. Так как процесс трансляции исходной программы нас не интересует, то нет никакой необходимости детализировать в промежуточной форме конструкции исходного языка. В частности, не надо представлять оператор цикла или условный оператор эквивалентными группами операторов. Другими словами, при преобразовании исходной программы в промежуточную форму все конструкции исходного языка можно оставить без каких-либо существенных изменений.
Рассмотрим следующий фрагмент исходной программы:
Его обратная польская запись имеет вид
Для возможности анализа хода выполнения программы при преобразовании в промежуточную триадную форму конструкции языка, нарушающие линейную последовательность выполнения программы, а также метки при операторах следует представлять с помощью отдельных строк. Тогда рассматриваемый фрагмент программы будет в промежуточной форме иметь следующий вид:
Пользуясь такой формой записи, легко установить, что линейность выполнения программы нарушается в строках т3, т6, т10, т14 и т25. Кроме того используемая форма развертывания оператора цикла позволяет легко определить его параметры и тип, что имеет большое значение для сбора начальной информации и выполнения оптимизирующих преобразовании над циклами.
Триадная запись удобна для определения поведения элементов данных в каждом участке программы. В частности, анализируя триадное представление программы, можно установить в каждом операторе и (или) участке программы и во всей программе и целом множества элементов данных, которые определяются и которые используются. Однако для получения полной и достоверной начальной информации промежуточная триадная форма должна отражать не только внутренние переменные, но также вводимые и выводимые данные, фактические параметры, содержащиеся в операторах вызова процедур и процедур-функций, а также - формальные параметры процедур и процедур-функций. Для выполнения этого требования введем некоторые дополнительные операции. Для представления в промежуточной форме фактических параметров операторов вызова процедур введем операцию ФАКТИЧЕСКИЙ ПАРАМЕТР (ФАП), операндами которой являются имя вызываемой процедуры и идентификаторы передаваемых фактических параметров, а для представления . формальных параметров в операторах процедур—операцию ФОРМАЛЬНЫЙ ПАРАМЕТР (ФОП), аргументами которой служат ключевое слово PROCEDURE и идентификаторы формальных параметров.
Тогда например, фрагмент исходной программы
' в ОПЗ будет иметь вид
Используя описанные выше новые операции, получаем следующее триадное представление этого фрагмента:
Для разделения друг от друга операторов программ мы в промежуточной триадной форме после записи каждого очередного оператора используется разделитель «;». Например, mi _; _
Требования, которым для обеспечения оптимизации должен удовлетворять промежуточный язык, и принципы, положенные и основу усовершенствования промежуточного представления, являются общими для различных языков программирования высокого уровня. Тем не менее точно так же, как при трансляции программ, процесс преобразования исходной программы промежуточную форму зависит от конкретного исходного языка программирования.
Для подтверждения вышесказанного рассмотри следующий фрагмент исходной программы, составленный на языке Фортран-IV:
Для этого фрагмента усовершенствованная триадная форма имеет следующий вид:
Здесь для явного указания в промежуточной форме нарушений линейности выполнения программы в условные операторы, в частности в логический условный оператор, введена операция ВЫБОР ПО УСЛОВИЮ (ВПУ), операндами которой являются ключевое слово IF и последующее за ним логическое выражение. Несмотря на то что язык программирования Фортран не содержит знака конца оператора в промежуточной форме после каждого оператора предусмотрена отдельная строка для представления знака конца оператора «; » точно так же, как в языке ПЛ/1. Это значительно облегчает последующие этапы оптимизации. Введение знака «; » при преобразовании программы в ОПЗ необходимо для очистки стека операций по окончании преобразования каждого оператора.
0 коммент.:
Отправить комментарий