Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 78
Текст из файла (страница 78)
*11.3.14. Обобщите алгоритм из упр. 11.3.13, чтобы можно было обрабатывать не только области с одним входам. 11.3.16. Приведите алгоритм для перемещения вычислений, не зависящих от области, за пределы области (ие обязательно с одним входом). Указание: В участках ане области, из которых можао достичь области ие через вход в область, допускается менять переменные, участвующие и вычислениях, инвариантных относительно области. Возможно, между участкамн вие области и учасгками внутри области потребуется поместить новые участки. "*11.3.16.
Покажите, что проблема эквивалентности двух программ неразрешима. Указание: Выберите подходящие типы данных н интерпретации для операций. гл и гтптимизаггия кодА г| з. АИАлиз пОтОка Алиных *" 11.3.17. Покажите, что проблема, индуктивна ли данная переменная, неразрешима.
11.3.18. Обобщите понятие области действия переменных и операторов на программы с циклами, Приведите алгоритм, вычисляющий область действия переменной в программе с циклами. *11 ли(9, Расширьте преобразования Тг — з ч пз разя. 11.1 с тгм, чтобы их можно было применить к программам без циклов назад (программам с операторами присваивания и условными операторами вила К у)?у йо1о Е, где Ь ссылается на оператор, расположенный после условного оператора).
*11.3.20. Покажите, что проблема, окончится ли когда-нибудь программа, неразрешима. Проблемы для исслздоааимд 11.3.21, Охарантеризуйте модели машин, для которых Описанные преобразования будут приводить к более быстро выполнимым программам. 11.3.22. Разработайте алгоритмы, которые будут опрсделять широкий класс явлений, исследованных в настоящем разделе (например, инвариаитные в цикле вычисления или индуктивные переменные). Отметим, что для большивглва этих явлений нет алгоритма, определяющего ясе их вхождения. Опжрышая проблема 11.3.23.
Можно ли вычислить прямые доминаторы графа управления с и вершинами менее чем за 0(пз) шагов? Разумно предположить, что О (и') — лу ппее, чего можно достичь для получения всего отношения доминирования, поскольку зтз каи раз столько, сколько требуется для печати ршзультата в матричной форме. Замечания по литературе В ряде озбп ры ла лютея разлнчные опт мпэнруюшке прспбраэапанпа поограмм. 11нвергельт (1165), Марклл (П621, Мак.Ккман Птбб! н Кларк 11967) перечисляют некоюрые ° нно-незавнснмыс преобразование Гнр 119об( предлагает опткмнзатор, пгособпый н всключенню некотормх обшнк подвы. раженпй, размножению констант и к некоторым онтнм зацпям цнклов, таким, «ак замена сложных операций н удаление внваркзнгпых нычкслекпй. Бузам н Энглунд ! В691 оцксывают аналогпчные преабрэзовэннн в рамках Фортрана. Аллен к Кок (15721 дают хороший обзор зтнх методов.
Аллен 11969! приво. дкт схему глобальной оптпмкэлцкн, осаоаанной на нахождевнк сильна сваз. кых областей программы Подтод к оптнмнзапкк с тачки зрения доминаторов впервые предложили Лоурп н Мсдлок !Пбу), хотя ндея отаошення домпннраванкя пришла от Прассера (1959!. Много теореткчсскнх работ посввщена схемам программ, аналогнчкым графам унравлен я, но с е пецкф цнрованнымк мвожествамн значений пере. менных н нм:псцнфнцнрованпммв функцнямн дла знаков операций. Лэе фундаментальные р боты, в которых рассматрнваетса экннеа е тность между тьккмн схемами незавнскмо от реальных множеств н функций, прннад ежвт йнову (1958! и Лакхэму н др (Ю761.
Обзор этих ксследованпй содер китса в работах Каплана 11970! н Манам (1973! '). 11.4. АНАЛИЗ ПОТОКА ДАННЫХ В предыдущем разделе мы нспопьзоаадн ИнфОРмапню о вычислениях в участках программ, ие описывая, как ее можно эффективно получить. В частности, мы использовали: (1),ылоступные" при входе в участок выражения. Быраженке А -(- В называют доступным при входе в участок, если Л + В всегда вычисляется до достижения участка, ио не ранее, чем оирелеляются Л и В.
(2) Миожество участков, в которых переменная могла определяться в последний раз перед тем, ках поток»правления достиг текущего участка. Вта информация полезна для размножения констант и выявления бесполезных вычислений. Оиа используется также для выявления возможных ошибок программно~а, заключающихся в том, что на переменную лелается ссылка до того, иак оиа Определена. Иггформаиия третьего типа, для вычисления которой можно применить методы настоящего раздела, связана с выявлением активных переменных, т.е. переменных, значения которых должны сохраняться при выходе из участка.
Эта информация полезна, когда участки преобразуются в машинный код, поскольку оиа указывает переменные, которые при выходе из участка должиы либо запоминаться, либо сохраняться в быстром регистре. В терминах равд. 11.1 зта информация нужна для выявления выхолиых переменных, Отметим, что переменная может вычисляться не в рассматриваемом участке, а в каком-нибудь предыдущем, ио быть тем не менее входной и выходной переменной участка. Из трех этих проблем мы исследуем только вторую в установление участка, где могла определяться переменная перед тем, как был достигнут данный участок. Предлагаемый метод, назван- ') Б работах советскнх авторов задача опткмпззцкк циклов рассмнтрввалась нз ранних эшпах автоматнзацнп програмннроввннн.
Задана раэвертыванна цкклав была впервые поставлена в работе Ьршова к Курочкина П9611, Развсртмванпе циклов, основанное ва апалнзе н преобрааоваквн графа управ. ленка, резлкэовано в АЛЬФА-трансляторе (Бежаноаа, Поттоснн, 1965!. Аналнэ ьавнснмостк индексного аыраженн» от параметра инала, основанный по сушеству н» поннтнн ннлуктввной переменноа, ровпдклся в рнбатзх Великаконой н др. !19611, Китова н Крккнцкого (19591, Каыыппнв, Любкмскаго к Шура-Буры 119551,— Лркм. пермь 423 ГЛ П ОПТИМИЗАЦИЯ КОДА ный „анализом интервалов", заилючается в разбиении графа управления па все болыпнс и ббльшие множества вершин; тем самым с графом связывается иерархическая структура.
С помощью этой струнтуры мажпа будет дать эффективный алгоритм для класса графов управления, называемых „сводимыми"; такие графы очень часто встречаются в качестве графов управления, вазника>о>цнх нз реальных программ. Затем мы укажем расширения, необходимые для обработки несводимых графов. В упражнениях рассмотрим изменения, которые нада сделать, чтобы прн анализе интервалов учитывалась информация дэух других гидов.
11.4.1. Интврввпы Начнем с определения типа подграфв, полезного прн анализе потока данных. Определение. Если й †верши графа управления р, определим интервал Цй) с заголовком й как такое множество вершин графа р, что (1) 6 принадлежит Цй), (2) если вершина п, еще не включенная в Цй), не является начальной и все луги, входящие в и, выходят из вершин, принадле>каших Цй), добаоляем и к Цй), (3) повторяем шаг (2) до тех пор, пока не Останется вер>нин, которые можно добавить к Цй). Пример 11.32. Рассмотрим граф управления, изображенный на рис. 11.37.
Рассмотрим интервал с начальной вершиной п, в качестве заголовка. Согласно шагу (1), Цп,) включает п,. Поскольку единственная дуга, входящая в и„ выходит из и„ добавляем и, к Цл,). Верн>ину и, нельзя добавить к Цп,), так как в нее можно попасть не тольно из п„но и из и,. Никаких других вершин добавить к Цп,) нельзя. Таким образом, Цпа)=.(п„п„). Рассааотрим теперь Цп„). Согласно шагу (1), п, пр>ьнадлежит Цп,).
Однако и нельзя добавить к Цп,), так как в п, аиожно попас>ь >чрез п„(как и через п,), а п, нс принадлежит Цп,). Никаких других вершин добавить к Цп,) нельзя, так что Цп,) -(и,). Продолжая в том же духе, разбиваем нап> граф управления на интервалы Цпд = (п, и,) Цяа) = (па) Цп,) =(по па, п,) Цпа) = (и„ пм и,) ГЗ и а.
АБАлиз пОтОкА ДАнных Пр, алгоритм выделения заголовков интервалов и по. риведем бивает г аф строения соответствую 1 инте валы. Сначала сделаем уира равления на непересекающиеси интервалы. н три и замечания относительно интервалов. Теорема 11.12. (П Зоголоеок й доминирует над всели жтоаьямми еершинами е Цй) (хотя ие обязав>алано осе гаршины, нпд которыми доминирует й, принадлежат Цй)). (2) Для каждой вершины 6 грофа упр оеления Р иппыреол Цй] опредеАлетоя одиозна«по и яе зависит от и орядха, е кол«ором яа шлге (2) опрея- иделения пптереила еыбнраюжся кадида>пы для и. (3) Каждый цикл е ояаереале Цй) еклю«аеаз еоголоеок намерзало й. Доказательство. Утверждения (1) и (2] оставляем в качестве упражнений; докажем (3).
Предположим, что Цй) имеет цикл и„..., яа, не вкл>рчающий й. Это означает, что существуют дуга нз и, в п>а О 1('(й, и д)та из и в и,. Пусть 1 и вершина и, первая среди пм ..., добавляется к Цй]. Тогда вершина и,, (нли па, если а —.-1) должна к этому времени уже быть в Цй) вопреки предположению.
Г] Одни из интересных аспектов анализа интерва лов заключается в мож- Рас. 1>.37. Граф упрааааааа. том, «то графы управления можно едииственн р ного г афа управления можно > >а интервалы, а интервалы одного графа упр рассматривать как вершины дру р ф > гого г а а уйравлсння, в ром из иитерва.ча 1 ведет ду р „е га в д угой интервал „е - нб ь га ведет из вершины интервала, в заг какая-нибудь дуг уга не может вести из 1„ интервала,, (Я а 1.
Ясно, что никакая дуга не м ю от заголовка.] Новый граф чна таким же Образом снова разбить на интервалы, и шин инте вала 1„отличную от считать, что граф управлении состоит нв из участков, а из 4ЗЗ 14 А.А«.ДЫ.Уаа «, .З гл, 1ь оптимизация кОдА шип, тип которых нс специфипмрован. Итак, вершины могут представлять структуры произволвной сложности. Дадим теперь алгоритм разбиения графа управления на непересекающиеся интервалы. Ллгарнтьг 11 б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
