А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 217
Текст из файла (страница 217)
617 — 640. 3. АПеп, Е Е. апс( 3. Сос1се, "А СаСа!ойие оГ оргишгйп8 СгапвГоппаС!опв'*, сп Оев(8п апс( Орйтсеагсап о/' Сотрйегз (К. Кикс!о, есс.), рр. 1 — 30, Ргепбсе-На!1, 1972. 4. Айеп, К. апг( К. Кеппес)у, "Аисоспабс сгапв!айоп оГ Рогсгал ргойгагпв со чессог СЬстп", АСМ Тгапвасйопв оп Ргодгатт!п8 Еапйаайев аль Бувсетв 9:4 (1987), рр. 491-542.
5. Валет)ее, ()., Оага Оерепг7епсе т Опйпагу Рга8гатв, Мавгег'в сЬеяв, Перагс- шепс оГ Сошрисег Яс!епсе, Ьспсчегясу оГ Пйпосв ЬсгЬапа-СЬашра18п, 1976. 1ОбО Глава 11. Оптимизация параллелизма и локальности 18. Маус)ап, Р. Е., 1. Ь. Неппевву, апс1 М. 8. 1.аш, "Ап ейс)епг гпейос! Гог ехасг беренс!епсе апа1уяв", Ргос. АСМ ЯОРТА1ч' 1991 Сол1егепсе оп Рю8гатт!л8 1ап8иа8е Рея!дп апа! 1тр1етепгаг!оп, рр. 1 — 14. 19.
МсКе11ег, А. С. апс( Е. б. Со%пап, "ТЬе ог8ап!гагюп о!' шагпсев апс( шагпх орегагюпв 1п а ра8ед пш!брго8гапцгцп8 епч!гопшепг", Сотт. АСМ, 12:3 (1969), рр. 153 — 165. 20. Моччгу, Т. С., М. Б. 1.аш, апс! А. бар!а, "Рея8п апс) еча1цабоп оТ а сошр1!ег а18опйш Гог ргеТегсЛ(п8", Ргос. Рфб 1пгегпаг!опа! Соп~егепсе оп Агс)лгесгига! Биррогг 7ог Рю8гаттт8 Ьап8иа8ее апс! Орегаг!лд Яулгетя (1992), рр.
62 — 73. 21. Райна, Р. А. апс! М. Е %о!Ге, "Ас!чапсес( сошр!!ег орбпцгабопв Тог апрегсошрцГегв", Сотт. АСМ, 29:12 (1986), рр. 1184-1201. 22. Роггегйе16, А., Бо1гччаге Мейос!л (ог 1тргоч!л8 Саебе Рег1огтапсе оп Бирегсотрисег Арр!!сас!опе, РЬ.Р. ТЬеяя РерагГшепГ оГ Сошрцсег 8с!епсе, 8!се Ып(чегяГу, 1989. 23. Рц8Ь, %. апс! Р.%оппасогг, "Ейпцпабп8 Га!зе роябчев цяп8 йе огпе8а гезг", Рпк. А СМ Б!ОРТАМ! 992 Соп~егелсе оп Рю8гаттт8 Ьап8иа8е Рея!8л ат1 1тр!ет ел!а!!оп, рр.
140 — 151. 24. Баг1саг, Ч. апс1 б. бао, "Оргпп!хагюп оТ аггау ассезвез Ьу со1!есбче 1оор ггапв1оппагюпв", Ргос. 5г1г !лгегпаг!ола! Соп/егепсе ол Бирегсотриг!л8 (199!), рр. 194-205. 25. К. Яюяа1с, "Рес)йп8 11пеаг !пес)ца1!г!ез Ьу сошрцбп8 1оор гевМцез", Х АСМ, 28:4 (1981), рр. 769-779. 26. Точч!е, К. А., Сопла! аги1 Рога Ререпс(елее ~ог Рю8гат ТгаллТогтаг!оп РЬ.Р. йеяв, Рерагппепг оТ Сошрпгег 8с!епсе, Ып!чегз!гу оГ !1!1по!в ЫгЬапаСЬяпра18п, 1976. 27. %о!1, М.
Е. апд М. Б. Ьаш, "А с!ага !оса!1гу орг)ш(х)п8 а!8опйш", Рюс. 510- Р1АИ1991 Соп/егепсе оп Рго8гатт!л8 1.ап8иа8е Рег!8п апс1 1тр!етепгаг!оп, рр. 30-44. 28. %о11е, М. 1., Тесбп!с!иее 1ог 1тргоч!п8 йе 1л1гегелг Рага!!е!ит !л Рю8гатз, Маагег'а йеяв, Рерагппепг о!'Сошрцгег 8с)епсе, Ып!чегягу оТ 118погв БгЬапаСЬашра18п, 1978. ГЛАВА 12 Межпроцедурный анализ В этой главе в ходе рассмотрения ряда важных задач оптимизаций, которые не могут быть решены с помогцью лишь внутрипроцедурного анализа, будет обоснована важность межпроцедурного анализа.
Мы начнем с описания распространенных видов межпроцедурного анализа и сложностей их реализации, после чего перейдем к применениям межпроцедурного анализа. В широко используемых языках программирования наподобие С и )ача ключом к любому межпроцедурному анализу является анализ псевдонимов указателей. Поэтому ббльшая часть главы будет посвящена именно технологиям, необходимым для вычисления псевдонимов указателей. Начнем мы с представления Рага!оя — системы обозначений, позволяющей скрывать сложность эффективного анализа указателей.
Затем будет описан алгоритм анализа указателей и показано, как воспользоваться абстракцией диаграмм бинарного выбора (о|пату оес)з)оп йадгаша — ВОР) для эффективной реализации алгоритма. Большинство оптимизаций, включая описанные в главах 9-11, выполняются одновременно над одной процедурой.
Такой анализ называется влутрипропедурным ()п1гаргоседцга!). Он консервативно предполагает, что вызываемая процедура может изменять состояние всех переменных, видимых процедуре, и что при этом могут осуществляться любые побочные действия, такие как изменение любой видимой процедуре переменной или генерация исключения, приводящая к развертыванию стека вызовов. Внутрипроцедурный анализ относительно прост, но при этом весьма неточен. Для ряда оптимизаций внутрипроцедурного анализа достаточно, в то время как другие оптимизации без межпроцедурного анализа не дают практически ничего. Межпроцедурный анализ работает со всей программой, следуя за информацией, передаваемой от вызывающей процедуры вызываемой и обратно. Одним относительно простым, но полезным методом является встраивание (~п!)п)пя) процедур, т.е. замена вызова процедуры ее телом с соответствующими изменениями для корректной передачи параметров и возврата значений.
Этот метод применим, только если нам известен целевой код вызова процедуры. Если процедуры вызываются косвенно, посредством указателя или через механизм диспетчеризации методов в объектно-ориентированном программировании, то в ряде случаев определить целевой код вызова позволяет анализ указателей 1062 Глава 12. Межпропедурный анализ или ссылок программы. Если такой целевой код единственный, можно применить встраивание. Но даже в этом случае пользоваться встраиванием следует с осторожностью. В общем же случае невозможно, например, встраивание рекурсивных процедур, да и при отсутствии рекурсии встраивание, как минимум, приводит к существенному увеличению размера кода.
12.1 Базовые концепции В этом разделе будут рассмотрены графы вызовов — графы, которые говорят нам о том, какие процедуры и из каких процедур могут быть вызваны. Мы также рассмотрим идею "контекстной чувствительности", когда анализу потока данных требуется информация о последовательности выполненных вызовов процедур. Иначе говоря, контекстно-чувствительный анализ при рассмотрении "местоположения" в программе наряду с текущей точкой программы включает и последовательность записей активации в стеке.
12.1.1 Графы вызовов Граф вызовов (са1! ягарЬ) программы представляет собой множество узлов и ребер, такое, что 1. каждой процедуре программы соответствует один узел; 2. каждой точке вызова (са!1 з1!е), т.е. месту в программе, где осуществляется вызов процедуры, соответствует один узел графа; 3. если точка вызова с может вызывать процедуру р, в графе имеется ребро от узла с к узлу р. Многие программы, написанные на таких языках программирования, как С и Еог1гап, осуществляют вызовы процедур непосредственно, так что целевой код каждого вызова может быть определен статически. В этом случае каждая точка вызова в графе имеет единственное ребро ровно к одной процедуре.
Если же программа включает использование процедурных параметров или указателей на функции, то в общем случае до момента выполнения целевой код неизвестен и для разных вызовов может варьироваться. Таким образом, точка вызова может быть связана со многими (или даже всеми) процедурами графа вызовов. Косвенные вызовы весьма распространены в объектно-ориентированных языках программирования. В частности, при перекрытии методов в подклассе использование метода т может означать любой из большого количества разных методов, зависящих от конкретного подкласса объекта.
Использование вызовов таких виртуальньп методов означает, что мы должны знать тип объекта до того, как сможем определить, какой именно метод будет вызван. 1063 12.1. Базовые концелцнн Пример 12.1. На рис. 12.1 показана программа на языке программирования С, в которой объявлен глобальный указатель рй на функцию, которая получает в качестве параметра и возвращает целое число. Имеются две функции данного типа— йип1 и йип2 — и функция тафп, тип которой не соответствует указателю рй. На рисунке указаны три точки вызова, обозначенные как с1, с2 и сЗ; эти метки не являются частью программы. з.пс (*рй) (з.пс) г 1пГ йип1(фпГ х) ( И (х < 10) гесигп (*рй)(х+1); е1ае гесигп х; с1: 1пг Еип2(1пг у) ( рГ = ййип1г гесигп (*рй)(у)' згойс( тайп() р~ = ййип2; (*рй)(5); сЗ: Рнс.
12.!. Программа с указателем на функцию Простейший анализ того, на что может указывать рй, состоит в исследовании типов функций. Функции йип1 и йип2 имеют тот же тип, что и указатель рй, в то время как функция ва1п имеет другой тип. Таким образом, консервативный граф вызовов показан на рис. 12.2, а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
