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

Далее все перечисленные формы представления рассматриваются более подробно.

Синтаксические деревья

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

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

Синтаксические деревья могут быть преобразованы в другие формы внутренне­го представления программы, представляющие собой линейные списки, с учетом семантики входного языка. Алгоритмы такого рода преобразований рассмотрены далее. Эти преобразования выполняются на основе принципов СУ-компиляции.

Многоадресный код с явно именуемым результатом (тетрады)

Тетрады представляют собой запись операций в форме из четырех составляю­щих: операция, два операнда и результат операции. Например, тетраэдры могут выглядеть так: <операция>(<операнд1>,<операнд2>,<результат>).

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

---

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

Глава 2.Оптимизация кода.

2.2. Основные методы оптимизации

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

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

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

---

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

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

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

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

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

---

% медленнее¹.

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

---

Смотрите также файлы

• План недели психологии.odt

• Протокол 1 от 30 августа 2021 года утверждаю директор гбпоу ро бтитиР Яковлева Н. Р.doc

• Экономика (часть 11).docx

• Терапия стандарттар жауабы.docx

• Администрация Плюсского района Псковской области Муниципальное бюджетное общеобразовательное учреждение Лядская средняя общеобразовательная школа.odt