37. Фаза генерации кода. Основные принципы.

38. Фаза оптимизации кода.

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

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

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

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

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

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

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

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

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

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

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

□ циклов;

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

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

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

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

Оптимизация линейных участков программы

Принципы оптимизации линейных участков

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

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

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

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

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

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

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

Удаление бесполезных присваиваний заключается в том, что если в составе линейного участка программы имеется операция присваивания значения некоторой произвольной переменной А с номером i, а также операция присваивания значения той же переменной А с номером j, i<j, и ни в одной операции между i и j не используется значение переменной А, то операция присваивания значения с номером i является бесполезной. Фактически, бесполезная операция присваивания значения дает переменной значение, которое нигде не используется. Такая операция может быть исключена без ущерба для смысла программы. В общем случае бесполезными могут оказаться не только операции присвоения, но и любые другие операции линейного участка, результат выполнения которых нигде не используется. Например, во фрагменте программы:

А := В * С;

D := В + С;

А := D * С;

операция присваивания А := В * С; является бесполезной и может быть удалена. Вместе с удалением операции присвоения здесь может быть удалена и операция умножения, которая в результате также окажется бесполезной.

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

Р := @А:

А := В * С;

D := Р^ + С;

А := D * С;

операция присваивания А := В * С; уже не является бесполезной, хотя это и не столь очевидно. В этом случае неверно следовать простому принципу, заключающемуся в том, что если переменная, которой присвоено значение в операции с номером i, не встречается ни в одной операции между i и j, то операция присваивания с номером i является бесполезной.

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

Исключение избыточных вычислений (лишних операций) заключается в нахождении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды. Операция линейного участка с порядковым номером i считается лишней, если существует идентичная ей операция с порядковым номером j, j<i, и никакой операнд, обрабатываемый этой операцией, не изменялся никакой операцией, имеющей порядковый номер между i и j. Свертка объектного кода — это выполнение во время компиляции тех операций исходной программы, для которых значения операндов уже известны. Тривиальным примером свертки является вычисление выражений, все операнды которых являются константами. Более сложные варианты алгоритма свертки принимают во внимание также и переменные, и функции, значения для которых уже известны. Не всегда компилятору удается выполнить свертку, даже если выражение допускает ее выполнение. Например, выражение А :=2*В*С*3: может быть преобразовано к виду А := 6 * В * С:, но при порядке вычислений А := 2 * (В * (С * 3)): это не столь очевидно. Для более эффективного выполнения свертки объектного кода возможно совместить ее выполнение с другим методом — перестановкой операций.

Хорошим стилем программирования является объединение вместе операций, производимых над константами, чтобы облегчить компилятору выполнение свертки. Например, если имеется константа PI = 3.14, представляющая соответствующую математическую постоянную, то операцию b - sin(2na): лучше записать в виде В := sin(2*PI *А); или даже В :=sin(<2*PI) * А);, чем в виде В :=sin(2 * А * PI):. Перестановка операций заключается в изменении порядка следования операций, которое может повысить эффективность программы, но не будет влиять на конечный результат вычислений

Например, операции умножения в выражении А:=2*В*3*С: можно переставить без изменения конечного результата и выполнить в порядке А := (2*3) * (В * С):. Тогда представляется возможным выполнить свертку и сократить количество операций.

Другое выражение А := (В + С) + (D + Е); может потребовать, как минимум, одной ячейки памяти (или регистра процессора) для хранения промежуточного результата. Но при вычислении его в порядке А := В + (С + (D + Е)): можно обойтись одним регистром, в то время как результат будет тем же. Особое значение перестановка операций приобретает в тех случаях, когда порядок их выполнения влияет на эффективность программы в зависимости от архитектурных особенностей целевой вычислительной системы (таких, как использование регистров процессора, конвейеров обработки данных и т. п.). Эти особенности рассмотрены далее в подразделе, посвященном машинно-зависимым методам оптимизации.

Арифметические преобразования представляют собой выполнение изменения характера и порядка следования операций на основании известных алгебраических и логических тождеств.

Например, выражение A :=B*C + B*D: может быть заменено на А := В * (С + D);. Конечный результат при этом не изменится, но объектный код будет содержать на одну операцию умножения меньше.

К арифметическим преобразованиям можно отнести и такие действия, как замена возведения в степень на умножение; а целочисленного умножения на константы, кратные 2, — на выполнение операций сдвига. В обоих случаях удается повысить быстродействие программы заменой сложных операций более простыми. Далее подробно рассмотрены два метода: свертка объектного кода и исключение лишних операций.