А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 143
Текст из файла (страница 143)
+ Сброс представляет собой последовательность команд, которые сохраняют значение из регистра в ячейке памяти, чтобы освободить регистр для хранения другого значения. 8.13 Список литературы к главе 8 Многие методы, описанные в этой главе, были разработаны в первых компиляторах. Алгоритм меток Ершова (ЕгзЬоч) создан еше в 1958 году 17].
Сети (Яе1Ь!) и Ульман (1Л!тап) [16] использовали этот метод в алгоритме, который, как они доказали, генерирует оптимальный код для арифметических выражений. Ахо (АЬо) и Джонсон (1оЬпзоп) 1!] использовали динамическое программирование для генерации оптимального кода для деревьев выражений на С1ЯС-машинах. В книге Хеннеси (Неппеьяу) и Паттерсона (Рапегзоп) !12] можно найти неплохое описание эволюции С18С- и К1ЯС-архитектур и компромиссов при проектировании хороших наборов команд. Архитектуры ц1ЯС стали популярны после 1990 года, хотя их родословная ведет начало от компьютеров типа С!3С 6000 1964 года выпуска.
Большинство машин, разработанных до 1990 года, были С1ЯС-машинами, но и после 1990 года соотношение не изменилось в силу того, что машины на основе архитектуры 1п1е! 80х86 и их наследники, такие как Репбшп, являются С1ЯС-машинами. Разработанная в 1963 году Вцггоц8Ьз В5000 являлась стековой машиной. Многие эвристики для генерации кодов, предложенные в этой главе, использованы в разных компиляторах.
Наша стратегия распределения фиксированного количества регистров для хранения переменных при выполнении цикла использовалась в реализации Рог1гап Н Лоури (Еотггу) и Медлоком (Мед!оскс) !13]. Эффективные методы распределения регистров также изучались еше при разработке первых компиляторов. Раскраска графа как метод распределения регистров была предложена Коком (Соске), Ершовым (ЕгзЬоч) !8] и Шварцем (ЯсЬиаг1х) !!5].
Для распределения регистров предлагались различные варианты задачи о раскраске графа. Мы следовали в своем изложении Чаитину (СЬа!11п) !3 и 4]. Чоу (СЬотг) и Хеннеси (Неппеззу) описали свой алгоритм раскраски графа с приоритетами для распределения регистров в !5]. В 16] можно найти обзор 703 8.13. Список литературы к ~лаве 8 последних методов разделения графов и переписывания для распределения регистров. Генераторы лексических и синтаксических анализаторов стимулировали разработку выбора команд, управляемую шаблонами.
Гланвилль (О!апчй!е) и Грехем (ОгаЬаш) [111 использовали методы генерации ЕК-синтаксического анализатора для автоматизации выбора команд. Генераторы кода, управляемые таблицами, эволюционировали в различный инструментарий генерации кода [14]. Ахо (АЬо), Ганапати (Оапара!Ь!) и Тжянг (Т1!ап8) [21 скомбинировали эффективные методы поиска соответствия шаблонам и динамического программирования в инструменте для генерации кода под названием пч18. Фразер (Ргазег), Хансов (Напзоп) и Пробстинг (РгоеЬабп8) [1О1 усовершенствовали эти идеи в своем простом и эффективном генераторе генераторов кода.
1. АЬо, А. Ч. апд Я. С. 1оЬпзоп, "Орйпа) соде 8епегабоп Тог ехргезяоп !геев", Х АСМ 23:3, рр. 488 — 501. 2. АЬо, А. Ч., М. ОапарагЬ1, апд Я. %'. К. Т)!ап8, "Соде 8епегабоп пяп8 ггее шаге)йп8 апд дупагшс ргойгапппш8", АСМ Тгапх Рго8гаттт8 Еал8иа8ея апд Бухгетх 11:4 (1989), рр. 491 — 516. 3. СЬа!г!и, О. 1., М. А. Ацз!апдег, А.
К. СЬапдга, 1. Сос)ге, М. Е. Нор!дпа, апд Р. %. Маг)гаге!п, "Пей!згег айосагюп ч!а со!опп8", Сотригег Еап8иа8ех 6:1 (1981), рр. 47 — 57. 4. СЬа!Г!п, О. 1., "Ее8!з!ег аПосабоп апд зрййп8 тда 8гарЬ со!опп8", АСМ Я6- РЙА)Ч )чодеех 17:6 (1982), рр. 201 — 207. 5. СЬоъч, Е апд 1.
Е. Неппеззу, "ТЬе рпопгу-Ьазед со!опп8 арргоасЬ со ге8!згег айосагюп", АСМ Тгалк Ргоуаттш8 Еал8иа8ез апд Бузгетз 12:4 (1990), рр. 501-536. 6. Соорег, К. Р. апд 1.. Тогсхоп, Ел81леег1л8 а СотРГ)ег, Мог8ап Капйпапп, 8ап Ргапс!зсо СА, 2004. 7.
Егабоч, А. Р., "Оп рго8гапппш8 оТ апдппебс орега11опз", Сотт. АСМ 1:8 (1958), рр. 3 — 6. А!зо, Сотт. АСМ 1:9 (1958), р. 16. 8. ЕгзЬоч, А. Р., Тйе А)РЬа Ашотадс Рго8гаттГл8 Яухгет, Асадеппс Ргезз, Ыечч Уотерс, 1971. 9. Р!зсЬег, С. Ы. апд К. 1. 1.еВ!апс, Сга)дл8 а СотрГ)ег пай С, Веп)апппСшпш!п8з, Кедччоод С!1у, СА, 1991. 704 Глава 8. Генерация кода 10. Егавег, С.
%., 13. В. Напяоп, апд Т. А. РгоеЬвйп8, "Еп8юеег1п8 а а!пгр!е, ейс!епГ соде 8епегаГог Пепегагог", АСМ ЕеГГе«я ол Ргод«аттглд 7.ал8иадеи алИ Бузгетя 1:3 (1992), рр. 213 — 226. 11. б!апмИе, К. Я. апд Я. 1.. ОгаЬагп, "А пеяк гпегЬод Гог согпрдег соде депе- гаГ)оп'", Сол): Вес. Я)й АСМ ЯутрокГит ол РплсгР1ез о7 Р«од«атт1лд 1.ал8иа8ея (1978), рр.
231-240. 12. Неппевву, У. 1., апд 13. А. Рацегвоп, Сотриге«А«сЬ)гесги«ег А Диалйгаг1ке Арр«оасй, ТЬ)гд Ед)гюп, Мог8ап Кацйпап, Кап Егапс)ясо, 2003. 13. Ьоигу, Е. Я. апд С. %. Мед)ос)с, "ОЬ)есГ соде орйтпга11оп*', Сотт. АСМ 12:1 (1969), рр. 13-22. 14. Ре!е8п'-Е!орагГ, Е, апд Б. 1.. ОгаЬагп, "Оргона! соде 8епегадоп Гог ехргевгдопв !геев: ап аррПсайоп оГ В!ЖЕ 1Ьеогу'*, Сел~: Лес. РЯеелгл Аллиа! АСМ ЯутрояГит ол Рплс1р!ея о~Р«од«итти йалдиа8ек (1988), рр. 294-308. 15. 8сЬваг1г, 3. Т., Ол Р«од«аттт8с Ал 1лгепт Перо«г ол йе БЕТЕ Р«о7есг, ТесЬгдса! Й.еро«Г, СоцгапГ 1пвг)гцГе оГМагЬегпа11са! Ес!епсея, Хев Уо«1г, 1973.
16. ЯеИп, К. апд 3. П. 1)Ппьап, "ТЬе 8епегагюп оГ оргцпа1 соде Гог апдппедс ехргевгдопа", Х А СМ 17:4 (1970), рр. 715 — 728. ГЛАВА 9 Машинно-независимые оптимизации Если независимо транслировать каждую конструкцию высокоуровневого языка программирования в машинный код, то это может приводить к существенным накладным расходам времени выполнения программы.
В данной главе рассматривается, как можно этого избежать. Устранение излишних команд в объектном коде или замена последовательности команд более быстрой, выполняющей те же действия последовательностью обычно называется улучшением кода или оптимизацией кода. Локальная оптимизация кода (улучшения кода в пределах базового блока) рассматривалась в разделе 8.5. В этой главе мы поговорим о елобальной оптимизации, улучшения которой учитывают происходящее между базовыми блоками.
Начнем с рассмотрения в разделе 9.1 основных возможностей улучшения кода. Большинство глобальных оптимизаций основано на анализах логноков данных, которые представляют собой алгоритмы для сбора информации о программе. Все результаты анализов потоков данных имеют один и тот же вид: для каждой команды программы они указывают некоторое свойство, которое должно выполняться всякий раз при выполнении этой команды. Разные анализы отличаются вычисляемыми ими свойствами. Например, анализ распространения констант вычисляет для каждой точки программы и для каждой переменной, используемой в программе, имеет ли эта переменная в данной точке программы единственное константное значение или нет.
Эта информация может, например, использоваться для замены обращений к переменным непосредственными константными значениями. В качестве другого примера анализ живучести переменных для каждой точки программы определяет, будет ли перезаписано значение, хранящееся в переменной, перед его прочтением.
Если будет, то мы не должны заботиться о сохранении этого значения в регистре или ячейке памяти. Анализ потоков данных будет рассматриваться в разделе 9.2 и включать несколько важных примеров видов глобально собираемой информации, используемой затем для улучшения кода. В разделе 9.3 рассматривается обобщенная идея схемы потока данных, для которой анализ потоков данных из раздела 9.2 является частным случаем. Во всех рассматриваемых случаях анализа потоков дан- 7Об Глава 9.
Машинно-независимые оптимизации ных можно использовать, по сути, одинаковые алгоритмы, производительность которых может быть измерена, а корректность показана для всех случаев. Раздел 9А представляет собой пример обобщенной схемы, которая выполняет более мощный анализ, чем в рассмотренных ранее примерах. Затем в разделе 9.5 будет рассмотрен мощный метод оптимизации размещения вычислений выражений в программе под названием "устранение частичной избыточности". Решение этой задачи требует решения ряда различных задач, связанных с потоками данных. В разделе 9.6 речь пойдет о циклах в программах.
Идентификация циклов приводит к другому семейству алгоритмов для решения задач потоков данных, основанному на иерархической структуре циклов в хорошо согласованной ("приводимой") программе. Этот подход к анализу потоков данных рассматривается в разделе 9.7. Наконец, в разделе 9.8 используется иерархический анализ для устранения переменных индукции (в первую очередь, переменных, подсчитывающих количество итераций цикла).
Такое улучшение кода — одно из наиболее важных для программ, написанных на распространенных языках программирования. 9.1 Основные источники оптимизации Оптимизация, выполняемая компилятором, должна сохранять семантику исходной программы. За исключением очень редких случаев, если программист выбрал и реализовал конкретный алгоритм, компилятор не в состоянии достаточно хорошо разобраться в программе, чтобы заменить его совершенно иным более эффективным алгоритмом. Компилятор знает только о том, как применять относительно низкоуровневые семантические преобразования с использованием обобщенных фактов, таких как алгебраические тождества наподобие г + 0 = ~.
или семантика программы наподобие того факта, что выполнение одинаковых операций над одинаковыми значениями даст одинаковые результаты. 9.1.1 Причины избыточности В типичной программе имеется масса избыточных операций. Иногда избыточность проявляется на уровне исходного текста программы. Например, программист может счесть более удобным вычислить некоторый результат заново, оставляя компилятору распознать, что одно из вычислений излишне. Но более часто избыточность оказывается побочным действием написания программ на языке программирования высокого уровня. В большинстве языков программирования (отличных от С и С-н-, в которых разрешены арифметические действия с указателями), у программиста нет выбора вариантов обращения к элементам массива или полям структуры наподобие А [г] [)] или Х вЂ” г'1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
