Текст книги "Системное программное обеспечение. Лабораторный практикум"

Ранее был описан принцип СУ-перевода, позволяющий получить линейную последовательность команд результирующей программы или внутреннего представления программы в компиляторе на основе результатов синтаксического анализа. Теперь построим вариант алгоритма генерации кода, который получает на входе дерево синтаксического разбора и создает по нему последовательность триад (далее – просто «триады») для линейного участка результирующей программы. Рассмотрим примеры схем СУ-перевода для бинарных арифметических операций. Эти схемы достаточно просты, и на их основе можно проиллюстрировать, как выполняется СУ-перевод в компиляторе при генерации кода.

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

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

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

При этом возможны четыре ситуации:

• левая и правая вершины указывают на непосредственный операнд (это можно определить, если у каждой из них есть только один нижележащий узел, помеченный символом какой-то лексемы – константы или идентификатора);

• левая вершина является непосредственным операндом, а правая указывает на другую операцию;

• левая вершина указывает на другую операцию, а правая является непосредственным операндом;

• обе вершины указывают на другую операцию.

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

1. Проверяется тип левой вершины узла. Если она – простой операнд, запоминается имя первого операнда, иначе для этой вершины рекурсивно вызывается процедура порождения триад, построенные ею триады добавляются в конец общего списка и запоминается номер последней триады из этого списка как первый операнд.

2. Проверяется тип правой вершины узла. Если она – простой операнд, запоминается имя второго операнда, иначе для этой вершины рекурсивно вызывается процедура порождения триад, построенные ею триады добавляются в конец общего списка и запоминается номер последней триады как второй операнд.

3. В соответствии с типом средней вершины в конец общего списка добавляется триада, соответствующая арифметической операции. Ее первым операндом становится операнд, запомненный на шаге 1, а вторым операндом – операнд, запомненный на шаге 2.

4. Процедура закончена.

Процедуры такого рода должен создавать разработчик компилятора, так как только он может сопоставить по смыслу узлы синтаксического дерева и соответствующие им последовательности триад. Для разных типов узлов синтаксического дерева могут быть построены разные варианты процедур, которые будут вызывать друг друга в зависимости от принятого порядка обхода синтаксического дерева (в описанном выше варианте – рекурсивно).

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

Кроме того, в случае арифметических операций код, порождаемый для узлов синтаксического дерева, зависит только от типа операции, то есть только от текущего узла дерева. Такие схемы можно построить для многих операций, но не для всех. Иногда код, порождаемый для узла дерева, может зависеть от типа вышестоящего узла: например, код, порождаемый для операторов типа Break и Continue (которые есть в языках C, C++ и Object Pascal), зависит от того, внутри какого цикла они находятся. Тогда при рекурсивном построении кода по дереву вышестоящий узел, вызывая функцию для нижестоящего узла, должен передать ей необходимые параметры. Но код, порождаемый для вышестоящего узла, никогда не должен зависеть от нижестоящих узлов, в противном случае принцип СУ-перевода неприменим.

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

Как уже говорилось, в подавляющем большинстве случаев генерация кода выполняется компилятором не для всей исходной программы в целом, а последовательно для отдельных ее конструкций. Для построения результирующего кода различных синтаксических конструкций входного языка используется метод СУ-перевода. Он объединяет цепочки построенного кода по структуре дерева без учета их взаимосвязей.

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

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

Теперь дадим определение понятию «оптимизация».

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

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

Но даже выбрав критерий оптимизации, в общем случае практически невозможно построить код результирующей программы, который бы являлся самым коротким или самым быстрым кодом, соответствующим входной программе. Дело в том, что нет алгоритмического способа нахождения самой короткой или самой быстрой результирующей программы, эквивалентной заданной исходной программе. Эта задача в принципе неразрешима. Существуют алгоритмы, которые можно ускорять сколь угодно много раз для большого числа возможных входных данных, и при этом для других наборов входных данных они окажутся неоптимальными [1, 2]. К тому же компилятор обладает весьма ограниченными средствами анализа семантики всей входной программы в целом. Все, что можно сделать на этапе оптимизации, – это выполнить над заданной программой последовательность преобразований в надежде сделать ее более эффективной.

Чтобы оценить эффективность результирующей программы, полученной с помощью того или иного компилятора, часто прибегают к сравнению ее с эквивалентной программой (программой, реализующей тот же алгоритм), полученной из исходной программы, написанной на языке ассемблера. Лучшие оптимизирующие компиляторы могут получать результирующие объектные программы из сложных исходных программ, написанных на языках высокого уровня, почти не уступающие по качеству программам на языке ассемблера. Обычно соотношение эффективности программ, построенных с помощью компиляторов с языков высокого уровня, и программ, построенных с помощью ассемблера, составляет 1,1–1,3. То есть объектная программа, построенная с помощью компилятора с языка высокого уровня, обычно содержит на 10–30 % больше команд, чем эквивалентная ей объектная программа, построенная с помощью ассемблера, а также выполняется на 10–30 % медленнее.[6]6
  Обычно такое сравнение выполняют для специальных тестовых программ, для которых код на языке ассемблера уже заранее известен. Полученные результаты распространяют на все множество входных программ, поэтому их можно считать очень усредненными.


[Закрыть]

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

Оптимизацию можно выполнять на любой стадии генерации кода, начиная от завершения синтаксического разбора и вплоть до последнего этапа, когда порождается код результирующей программы. Если компилятор использует несколько различных форм внутреннего представления программы, то каждая из них может быть подвергнута оптимизации, причем различные формы внутреннего представления ориентированы на различные методы оптимизации [1–3, 7]. Таким образом, оптимизация в компиляторе может выполняться несколько раз на этапе генерации кода.

Принципиально различаются два основных вида оптимизирующих преобразований:

• преобразования исходной программы (в форме ее внутреннего представления в компиляторе), не зависящие от результирующего объектного языка;

• преобразования результирующей объектной программы.

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

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

Используемые методы оптимизации ни при каких условиях не должны приводить к изменению «смысла» исходной программы (то есть к таким ситуациям, когда результат выполнения программы изменяется после ее оптимизации). Для преобразований первого вида проблем обычно не возникает. Преобразования второго вида могут вызывать сложности, поскольку не все методы оптимизации, используемые создателями компиляторов, могут быть теоретически обоснованы и доказаны для всех возможных видов исходных программ. Именно эти преобразования могут повлиять на смысл исходной программы. Поэтому у современных компиляторов существуют возможности выбора не только общего критерия оптимизации, но и отдельных методов, которые будут использоваться при выполнении оптимизации.

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

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

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

• линейных участков программы;

• логических выражений;

• циклов;

• вызовов процедур и функций;

• других конструкций входного языка.

Во всех случаях могут использоваться как машинно-зависимые, так и машинно-независимые методы оптимизации.

В лабораторной работе используются два машинно-независимых метода оптимизации линейных участков программы. Поэтому только эти два метода будут рассмотрены далее. С другими машинно-независимыми методами оптимизации можно более подробно ознакомиться в [1, 2, 7]. Что касается машинно-зависимых методов, то они, как правило, редко упоминаются в литературе. Некоторые из них рассматриваются в технических описаниях компиляторов.

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

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

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

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

• удаление бесполезных присваиваний;

• исключение избыточных вычислений (лишних операций);

• свертка операций объектного кода;

• перестановка операций;

• арифметические преобразования.

Далее рассмотрены два метода оптимизации линейных участков: исключение лишних операций и свертка объектного кода.

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

Внимание!

Не следует путать оптимизацию по методу свертки объектного кода с рассмотренным в лабораторной работе № 3 алгоритмом «сдвиг-свертка». Свертка объектного кода и свертка по правилам грамматики при выполнении синтаксического разбора– это принципиально разные операции!

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

Алгоритм свертки для линейного участка программы работает со специальной таблицей Т, которая содержит пары (<переменная>,<константа>) для всех переменных, значения которых уже известны. Кроме того, алгоритм свертки помечает те операции во внутреннем представлении программы, для которых в результате свертки уже не требуется генерация кода. Так как при выполнении алгоритма свертки учитывается взаимосвязь операций, то удобной формой представления для него являются триады, поскольку в других формах представления операций (таких как тетрады или команды ассемблера) требуются дополнительные структуры, чтобы отразить связь результатов одних операций с операндами других.

Рассмотрим выполнение алгоритма свертки объектного кода для триад. Для пометки операций, не требующих порождения объектного кода, будем использовать триады специального вида С(К,0).

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

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

2. Если операнд есть ссылка на особую триаду типа С(К,0), то операнд заменяется на значение константы К.

3. Если все операнды триады являются константами, то триада может быть свернута. Тогда данная триада выполняется и вместо нее помещается особая триада вида С(К,0), где К – константа, являющаяся результатом выполнения свернутой триады. (При генерации кода для особой триады объектный код не порождается, а потому она в дальнейшем может быть просто исключена.)

4. Если триада является присваиванием типа А:=В, тогда:

• если В – константа, то А со значением константы заносится в таблицу Т (если там уже было старое значение для А, то это старое значение исключается);

• если В – не константа, то А вообще исключается из таблицы Т, если оно там есть.

Рассмотрим пример выполнения алгоритма.

Пусть фрагмент исходной программы (записанной на языке типа Pascal) имеет вид:

I:= 1 + 1;

I:= 3;

J:= 6*I + I;

Ее внутреннее представление в форме триад будет иметь вид:

1: + (1,1)

2::= (I, ^1)

3::= (I, 3)

4: * (6, I)

5: + (^4, I)

6::= (J, ^5)

Процесс выполнения алгоритма свертки показан в табл. 4.1.

Таблица 4.1. Пример работы алгоритма свертки

Если исключить особые триады типа C(K,0) (которые не порождают объектного кода), то в результате выполнения свертки получим следующую последовательность триад:

1::= (I, 2)

2::= (I, 3)

3::= (J, 21)

Видно, что результирующая последовательность триад может быть подвергнута дальнейшей оптимизации – в ней присутствуют лишние присваивания, но другие методы оптимизации выходят за рамки данной лабораторной работы (с ними можно познакомиться в [1, 2, 7]).

Алгоритм свертки объектного кода позволяет исключить из линейного участка программы операции, для которых на этапе компиляции уже известен результат. За счет этого сокращается время выполнения,[7]7
  Даже если принять во внимание, что время на выполнение операции будет потрачено компилятором при порождении результирующей программы, то все равно мы имеем выигрыш во времени. Во-первых, любая результирующая программа создается (а значит и компилируется окончательно) только один раз, а выполняется многократно; во-вторых, оптимизируемый линейный участок может входить в состав оператора цикла или вызова функции, и тогда выигрыш очевиден.


[Закрыть] а также объем кода результирующей программы.

Свертка объектного кода, в принципе, может выполняться не только для линейных участков программы. Когда операндами являются константы, логика выполнения программы значения не имеет – свертка может быть выполнена в любом случае. Если же необходимо учитывать известные значения переменных, то нужно принимать во внимание и логику выполнения результирующей программы. Поэтому для нелинейных участков программы (ветвлений и циклов) алгоритм будет более сложным, чем последовательный просмотр линейного списка триад.