Л.Е. Карпов - Системы программирования (1114903), страница 11
Текст из файла (страница 11)
В особенности триады удобны для трансляции в объектный кодтаких вычислительных машин, в командах которых первый операнд часто хранится водном из регистров.Инфиксная запись. Запись операций и операндов в традиционном видеприменяется только в программах, подаваемых на вход компиляторов. Это наиболееудобная для людей, но наименее удобная для автоматической обработки запись.Префиксная запись.
Префиксная запись иначе называется польской записьюили прямой польской записью. В такой записи операторы (операции) предшествуютсвоим операндам. Некоторое неудобство прямой польской записи, которое привело киспользованию обратной записи, состоит в том, что операторы в ней следуют не в томпорядке, в каком они должны выполняться в вычислительной машине:= A - + * B C D * B 10Постфиксная (инверсная, обратная, суффиксная) запись. В отличие о тпрямой польской записи инверсная польская запись (ПОЛИЗ) обладает следующимиважными свойствами:•••Идентификаторы в обратной польской записи следуют в том же порядке, вкаком они следуют в инфиксной записи.Операторы в обратной польской записи следуют в том порядке, в каком онидолжны вычисляться (слева направо).Операторы следуют непосредственно за своими операндами.Обратная польская запись является наиболее удобным видом представленияпрограмм в компиляторах.
Эта запись не требует учитывать приоритеты операций, вней не используются скобки. ПОЛИЗ наиболее удобна при трансляции арифметическихвыражений:A B C * D + B 10 * – =Обычно в компилятор ха для пр дставленияепр ор гммав виде ПОЛИЗразрабатывается специальное представление не только арифметических операций, но ивсех других исполняемых операторов, что позволяет полностью автоматизироватьпроцесс преобразования стандартного представления на исходном языке40программирования в ПОЛИЗ.
У этой записи имеются и недостатки. Программы,представленные в виде ПОЛИЗ трудно поддаются анализу, поэтому оптимизирующиекомпиляторы создают ПОЛИЗ после проведения глобальных оптимизирующихпреобразований, когда требуется преобразовать уже оптимизированную древовиднуюструктуру в линейную. Работа с обратной польской записью в компиляторах подробнорассмотрена в пособии “Формальные грамматики и языки. Элементы теориитрансляции”.Язык ассемблера и машинные команды. По определению компилятора, какчастного случая транслятора с языка программирования высокого уровня на машинныйязык или язык ассемблера, понятно, что представление программы в виде машинныхкоманд или ассемблерной записи является обязательным. Однако некоторыекомпиляторы преобразованием программ к такому виду не заканчивают свою работу, алишь продолжают ее.
Именно в таком виде наиболее удобно проводить машиннозависимую оптимизацию, при которой легче всего учесть семантические особенностивыполнения отдельных связок команд и получить дополнительный выигрыш впроизводительности программы.Иногда в компиляторах, даже очень сложных и проводящих глубокуюоптимизацию, тоже возникает потребность на некотором этапе преобразованиятранслируемой программы перевести программу к виду, более приближенному к ееокончательному представлению. При этом запись на языке ассемблера может не сразуоказаться наиболее удобным представлением.
В таких случаях часто используютпредставление программы с помощью псевдокода. От языка ассемблера он отличаетсятем, что в нем могут не приниматься во внимание некоторые архитектурныеособенности целевой машины, в частности, для псевдокода является обычнымпредположение о том, что объектная машина обладает неограниченной памятью ибесконечным числом регистров общего назначения. В псевдокодах более вольноиспользуются форматы генерируемых команд, а все уточнения об ограниченияхделаются на этапах распределения памяти и регистров, а также при проведениимашинно-зависимой оптимизации, когда уже точно становится известна окончательнаяпоследовательность команд, реальные номера регистров и адреса операндов в памяти.3.3.4.
Оптимизация в компиляторахПереход от трансляции всей программы как целого к трансляциипоследовательности относительно независимых операторов (в синтаксическом плане вконтекстно-свободных грамматиках операторы действительно не зависят друг от друга)приводит к потере информации о взаимосвязи этих операторов. Описанные ранееметоды анализа программ и генерации этих программ на других языках позволяютрешить главную задачу компиляции – отыскать эквивалентное представление исходнойпрограммы в терминах выходного языка.
Вторая задача – поиск эффективногоэквивалента серьезно отличается от первой и требует других подходов и методоврешения. Под оптимизацией программ имеется в виду обработка, связанная спереупорядочением и изменением операций в компилируемой программе в целяхполучения более эффективной объектной программы.Оптимизация программ – вынужденная мера, прибегать к которой приходитсяпотому, что компилятор не в состоянии выполнить семантический анализ всейисходной программы как единого объекта, оценить и понять смысл программы.Оптимизация программ проводится в компиляторах в различных местах:41ОбъектнаяпрограммаИсходнаяпрограммаАнализирующая Промежуточное Оптимизатор Промежуточное Генераторчастьпрограмм представлениепредставлениекодакомпилятораIIIИнформационныеIIIтаблицыПервичную оптимизацию может проводить сам пользователь (пометка I).Некоторые системы программирования предлагают поддержку пользовательскойоптимизации, в частности, имеют в своем составе профилировщики, помогающиевыявить те фрагменты программ, которые для своего выполнения требуютмаксимальной доли времени работы программы.
В целом оптимизация на уровнеисходной программы может дать наибольший эффект для улучшения техническиххарактеристик программы. К таким техническим характеристикам относят обычно две:объем памяти, необходимый для выполнения объектной программы (для храненияданных и самих команд программы), и скорость выполнения программы (еебыстродействие).
Очень часто сокращение используемых в программе данныхприводит к увеличению времени работы программы, а попытки повыситьбыстродействие приводят к увеличению используемой памяти. Поэтому часто дляоптимизации выбирается один, главный критерий, либо некоторый интегрированныйкритерий, основанный на сбалансированном подходе к достижению многих целейодновременно.При выборе используемых в компиляторе оптимизирующих преобразованийруководствуются следующими критериями:•••все преобразования должны быть эквивалентными (для всех наборовданных, даже неправильных).
Эквивалентные преобразования сохраняютсемантику исходной программы;“стоимость” преобразования должна быть сопоставима с затрачиваемымиусилиями и полученными эффектами. Время компиляции от включенияоптимизирующих преобразований всегда растет, но иногда это не оченьважно. Важнее, чтобы при оптимизации не вносились дополнительныеошибки, на исправление которых затрачиваются дополнительные усилия,в результате преобразований программы в среднем должны “улучшаться”(почти для всех допустимых данных), лишь на каких-то (редковстречающихся) комбинациях данных допускается обратный эффект(ухудшение характеристик).Некоторые преобразования считаются удовлетворяющими этим критериям ир комендуютсяедля включения в любой компилятор.
Другие преобразования,основанные на сложном анализе потока управления и потока данных, а также наиспользовании результатов этого анализа при модификации программ, требуютдополнительного анализа представительного набора реальных программ на данномязыке программирования. Различаются два основных вида оптимизации:42••Машинно-независимая оптимизация, то есть проведение преобразованийисходной программы (в форме некоторого внутреннего представления), независящих от выходного языка компилятора (без учета конкретных свойствобъектной машины).
Эта оптимизация обычно выполняется на специальновыделенной фазе компиляции (пометка II на рисунке),Машинно-зависимая оптимизация, то есть преобразование программы навыходном языке компилятора. Этот вид оптимизации обычно проводитсяодновременно с генерацией объектной программы или уже после этойгенерации на дополнительной стадии (пометка III на рисунке).Машинно-независимая оптимизация получила такое название потому, чтопроводимые в рамках этого процесса преобразования не зависят от архитектурывычислительной системы, для которой предназначена объектная программа. Дляпроведения таких преобразований разработан целый ряд формальных математическихметодов.
При проведении преобразований машинно-зависимой оптимизации можетоказаться необходимым учитывать аппаратные особенности вычислительных систем –число и способ организации взаимодействия центральных процессоров, иерархиюустройств памяти, количество и размеры регистров, а также многое другое.Обычно оптимизирующим преобразованиям подвергается внутреннеепредставление программы, а не текст на исходном языке. Во-первых, операции,необходимые для реализации высокоуровневых операций становятся на языкахвнутреннего представления программ более явными, что облегчает их обнаружение иоптимизацию.
Например, исходный оператор s=s+a[i]*b[i] скрывает, чтовычисление адресов для элементов a[i] и b[i] содержит общие подвыраженияsizeof(тип)*i. Во-вторых, внутреннее представление может оказатьсяотносительно независимым от объектной машины, что делает оптимизатор достаточноустойчивым к изменениям при переносе на другую машину.3.3.4.1. Машинно-независимая оптимизацияОсновные преобразования машинно-зависимой оптимизации выполняются дляотдельных выражений, линейных участков программ, циклов, вызовов процедур ифункций.Оптимизация однократно выполняемых участков программы практически неоказывает влияния на быстродействие программы и может сказываться только наобъеме занимаемой программой памяти, поэтому наиболее тщательно всегдаоптимизируется самый внутренний цикл программы. Для проведения оптимизациипрограммы делят на линейные участки, то есть на выполняемые по порядкупоследовательности операций.
Линейные участки имеют один вход и один выход.Линейные участки имеются в любой программе и чаще всего содержатпоследовательности вычислений, состоящие из арифметических выражений иоператоров присваивания значений переменным программы. Ни одна операциялинейного участка не может быть выполнена большее число раз, чем смежные с неюоперации.
Для линейных участков проводятся следующие преобразования:•••вычисление выражений из констант на стадии компиляции,арифметические преобразования,устранение общих подвыражений (избыточных вычислений),43••••удаление ненужных присваиваний и других операций, распространениекопий значений,перестановка независимых смежных участков программ,удаление недостижимых фрагментов программы,оптимизация вычисления логических выражений.Вычисление выражений из известных операндов (свертка операций):•непосредственное использование констант программистом:A = sin (2 * 3.14 * B);•возникновение констант-операндов после макрорасширений,#define Pi 3.1415926A = sin (2 * Pi * B);•возникновение констант-операндов в результате компиляции языковыхконструкций, например, многомерных массивов:int a [10][10][10], b [10][10][10], c [10][10][10];a [3][4][i] = b [8][3][k] * c [3][2][j];a’ [((3 * 10) + 4) * 10 + i] := b’ [((8 * 10) + 3) * 10 + k] *c’ [((3 * 10) + 2) * 10 + j];Компилятор должен выполнить вычисления и внести записи о новыхлитеральных константах в таблицу констант, как если бы эти константы были введенысамим программистом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
