Пример схемы су-перевода дерева операций в последовательность триад
Как и в случае с порождением команд ассемблера, функцию, реализующую перевод узла дерева в последовательность триад, назовем Code. Входные и выходные данные у этой функции будут те же, что и при работе с командами ассемблера. Триады являются машинно-независимой формой внутреннего представления в компиляторе результирующей объектной программы, а потому не требуют оговорки дополнительных условий при генерации кода. Триады взаимосвязаны между собой, поэтому для установки корректной взаимосвязи функция генерации кода должна учитывать также текущий номер очередной триады (i).
Будем рассматривать те же варианты узлов дерева, что и для команд ассемблера. Тогда четырем формам текущего узла дерева будут соответствовать последовательности триад объектного кода, приведенные в табл. 14.3.
Для триад не требуется учитывать операцию присваивания как отдельный тип узла дерева. Она преобразуется в триаду обычного вида.
Рассмотрим в качестве примера то же самое выражение A:=B*C+D-B*10. Соответствующее ему дерево вывода уже было приведено на рис. 14.5. Построим последовательность триад, соответствующую дереву операций на рис. 14.5. Согласно принципу СУ-перевода, построение начинается от корня дерева.
Следует обратить внимание, что в данном алгоритме последовательные номера триад (а следовательно, и ссылки на них) устанавливаются не сразу. Это не имеет значения при рекурсивной организации процедуры, но если используется другой способ обхода дерева операций, при реализации генерации кода лучше увязывать триады между собой именно по ссылке (указателю), а не по порядковому номеру.
Использование триад позволяет сократить количество рассматриваемых вариантов узлов дерева операций. B этом случае не требуется принимать во внимание типы операндов и ориентироваться на архитектуру целевой вычислительной системы. Все эти аспекты необходимо будет принимать во внимание уже на этапе преобразования триад в последовательность команд ассемблера или непосредственно в последовательность машинных команд результирующей программы.
Как и последовательность команд ассемблера, последовательность триад можно оптимизировать. Для триад разработаны универсальные (машинно-независимые) алгоритмы оптимизации кода. Уже после их выполнения (оптимизации внутреннего представления) триады могут быть преобразованы в команды на языке ассемблера.
Оптимизация кода.
Основные методы оптимизации
Общие принципы оптимизации кода
Как уже говорилось выше, в подавляющем большинстве случаев генерация кода выполняется компилятором не для всей входной программы в целом, а последовательно для отдельных ее конструкций. Полученные для каждой синтаксической конструкции входной программы фрагменты результирующего кода также последовательно объединяются в общий текст результирующей программы. При этом связи между различными фрагментами результирующего кода в полной мере не учитываются.
B свою очередь, для построения результирующего кода различных синтаксических конструкций входного языка используется метод СУ-перевода. Он также объединяет цепочки построенного кода по структуре дерева без учета их взаимосвязей (что видно из примеров, приведенных выше).
Построенный таким образом код результирующей программы может содержать лишние команды и данные. Это снижает эффективность выполнения результирующей программы. B принципе компилятор может завершить на этом гене-
рацию кода, поскольку результирующая программа построена и она является эквивалентной по смыслу (семантике) программе на входном языке. Однако эффективность результирующей программы важна для ее разработчика, поэтому большинство современных компиляторов выполняют еще один этап компиляции — оптимизацию результирующей программы (или просто «оптимизацию»), чтобы повысить ее эффективность насколько это возможно. Важно отметить два момента: во-первых, выделение оптимизации в отдельный этап генерации кода — это вынужденный шаг. Компилятор вынужден производить оптимизацию построенного кода, поскольку он не может выполнить семантический анализ всей входной программы в целом, оценить ее смысл и, исходя из него, построить результирующую программу. Оптимизация нужна, поскольку результирующая программа строится не вся сразу, а поэтапно. Во-вторых, оптимизация — это необязательный этап компиляции. Компилятор может вообще не выполнять оптимизацию, и при этом результирующая программа будет правильной, а сам компилятор будет полностью выполнять свои функции. Однако практически все компиляторы так или иначе выполняют оптимизацию, поскольку их разработчики стремятся завоевать хорошие позиции на рынке средств разработки программного обеспечения. Оптимизация, которая существенно влияет на эффективность результирующей программы, является здесь немаловажным фактором.
Теперь дадим определение понятию «оптимизация».
Оптимизация программы — это обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе с целью получения более эффективной результирующей объектной программы. Оптимизация выполняется на этапах подготовки к генерации и непосредственно при генерации объектного кода.
B качестве показателей эффективности результирующей программы можно использовать два критерия: объем памяти, необходимый для выполнения результирующей программы (для хранения всех ее данных и кода), и скорость выполнения (быстродействие) программы. Далеко не всегда удается выполнить оптимизацию так, чтобы удовлетворить обоим этим критериям. Зачастую сокращение необходимого программе объема данных ведет к уменьшению ее быстродействия, и наоборот. Поэтому для оптимизации обычно выбирается либо один из упомянутых критериев, либо некий комплексный критерий, основанный на них. Выбор критерия оптимизации обычно выполняет непосредственно пользователь в настройках компилятора.
Ho, даже выбрав критерий оптимизации, в общем случае практически невозможно построить код результирующей программы, который бы являлся самым коротким или самым быстрым кодом, соответствующим входной программе. Дело в том, что нет алгоритмического способа нахождения самой короткой или самой быстрой результирующей программы, эквивалентной заданной исходной программе. Эта задача в принципе неразрешима. Существуют алгоритмы, которые можно ускорять сколь угодно много раз для большого числа возможных входных данных, и при этом для других наборов входных данных они окажутся неоптимальными [6, т. 2]. K тому же компилятор обладает весьма ограниченными средствами анализа семантики всей входной программы в целом. Все, что можно сделать на этапе оптимизации, — это выполнить над заданной программой последовательность преобразований в надежде сделать ее более эффективной.
Чтобы оценить эффективность результирующей программы, полученной с помощью того или иного компилятора, часто прибегают к сравнению ее с эквивалентной программой (программой, реализующей тот же алгоритм), полученной из исходной программы, написанной на языке ассемблера. Лучшие оптимизирующие компиляторы могут получать результирующие объектные программы из сложных исходных программ, написанных на языках высокого уровня, почти не уступающие по качеству программам на языке ассемблера. Обычно соотношение эффективности программ, построенных с помощью компиляторов с языков высокого уровня, к эффективности программ, построенных с помощью ассемблера, составляет 1,1-1,3. To есть объектная программа, построенная с помощью компилятора с языка высокого уровня, обычно содержит на 10-30 % больше команд, чем эквивалентная ей объектная программа, построенная с помощью ассемблера, а также выполняется на.10-30 % медленнее1.
Это очень неплохие результаты, достигнутые компиляторами с языков высокого уровня, если сравнить трудозатраты на разработку программ на языке ассембле-раи языке высокого уровня. Далеко не каждую программу можно реализовать на языке ассемблера в приемлемые сроки (а значит, и выполнить напрямую приведенное выше сравнение можно только для узкого круга программ).
Оптимизацию можно выполнять на любой стадии генерации кода, начиная от завершения синтаксического разбора и вплоть до последнего этапа, когда порождается код результирующей программы. Если компилятор использует несколько различных форм внутреннего представления программы, то каждая из них может быть подвергнута оптимизации, причем различные формы внутреннего представления ориентированы на различные методы оптимизации [6, т. 2, 74, 82]. Таким образом, оптимизация в компиляторе может выполняться несколько раз на этапе генерации кода.
Принципиально различаются два основных вида оптимизирующих преобразова-I ний:
--- преобразования исходной программы (в форме ее внутреннего представления в компиляторе), не зависящие от результирующего объектного языка;
--- преобразования результирующей объектной программы.
Первый вид преобразований не зависит от архитектуры целевой вычислительной системы, на которой будет выполняться результирующая программа. Обычно он основан на выполнении хорошо известных и обоснованных математических и логических преобразований, производимых над внутренним представлением программы (некоторые из них будут рассмотрены ниже).
Второй вид преобразований может зависеть не только от свойств объектного языка (что очевидно), но и от архитектуры вычислительной системы, на которой
Обычно такое сравнение выполняют для специальных тестовых программ, для которых код на языке ассемблера уже заранее известен. Полученные результаты распространяют на все множество входных программ, поэтому их можно считать очень усредненными.
будет выполняться результирующая программа. Так, например, при оптимизации может учитываться объем кэш-памяти и методы организации конвейерных операций центрального процессора. B большинстве случаев эти преобразования сильно зависят от реализации компилятора и являются «ноу-хау» производителей компилятора. Именно этот тип оптимизирующих преобразований позволяет существенно повысить эффективность результирующего кода.
Используемые методы оптимизации ни при каких условиях не должны приводить к изменению «смысла» исходной программы (то есть к таким ситуациям, когда результат выполнения программы изменяется после ее оптимизации). Для преобразований первого вида проблем обычно не возникает. Преобразования второго вида могут вызывать сложности, поскольку не все методы оптимизации, используемые создателями компиляторов, могут быть теоретически обоснованы и доказаны для всех возможных видов исходных программ. Именно эти преобразования могут повлиять на «смысл» исходной программы. Поэтому большинство компиляторов предусматривает возможность отключать те или иные из возможных методов оптимизации.
Нередко оптимизация ведет к тому, что смысл программы оказывается не совсем таким, каким его ожидал увидеть разработчик программы, но не по причине наличия ошибки в оптимизирующей части компилятора, а потому, что пользователь не принимал во внимание некоторые аспекты программы, связанные с оптимизацией. Например, компилятор может исключить из программы вызов некоторой функции с заранее известным результатом, но если эта функция имела «побочный эффект» — изменяла некоторые значения в глобальной памяти, — смысл программы может измениться. Чаще всего это говорит о плохом стиле программирования исходной программы. Такие ошибки трудноуловимы, для их нахождения следует обратить внимание на предупреждения разработчику программы, выдаваемые семантическим анализом, или отключить оптимизацию. Применение оптимизации также нецелесообразно в процессе отладки исходной программы.
У современных компиляторов существуют возможности выбора не только общего критерия оптимизации, но и отдельных методов, которые будут использоваться при выполнении оптимизации.
Методы преобразования программы зависят от типов синтаксических конструкций исходного языка. Теоретически разработаны методы оптимизации для многих типовых конструкций языков программирования.
Оптимизация может выполняться для следующих типовых синтаксических конструкций:
а линейных участков программы;
--- логических выражений;
--- циклов;
--- вызовов процедур и функций;
--- других конструкций входного языка.
Bo всех случаях могут использоваться как машинно-зависимые, так и машинно-независимые методы оптимизации.
Далее будут рассмотрены только некоторые машинно-независимые методы оптимизации, касающиеся в первую очередь линейных участков программы. Перечень их здесь далеко не полный. C остальными машинно-независимыми методами можно более подробно ознакомиться в [6, т. 2]. Что касается машинно-зависимых методов, то они, как правило, редко упоминаются в литературе. Некоторые из них рассматриваются в технических описаниях компиляторов. Здесь эти методы будут рассмотрены только в самом общем виде.