Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 75
Текст из файла (страница 75)
С помощью алгоритма 0.3 находим все участки Я, ставшие теперь недостижимыми из начальной вершины в Р. Участок З, доминирует над 2! тогда и толька тогда, когда Я становится недостижимым из начальной вершины после нснлючения Я, из Р, Снова заносим Яг в Р. (2) Предположим, что па шаге (1) обнаружено, что Яг доминирует над й!. Если РОМ(Я] =-РОМ(Я,), берем Я, в качестве РОМ(Я). В противном случае РОМ(Я) не меняем. С) Пример 11.31. С помощью алгоритма 11.5 вычислим прямые доминаторы для графа управления рис.
11.22. Здесь й =(Зи Я„ Я„ Я,). Последовательные значения РОМ(З) после исследования участков ЯО 2 щ 1 (4, приведены в таба. 11.8. Вычнс. лим строку 2. После исилючеиии участка Я, участки Я„ и Я4 становятся недостижимыми. Таким образом, Я, доминирует пал З, и З». Перед этим было РОМ(Я,) =РОМ(Я,) =Ям так что в 4ах ~г з, пгоггх»4 Ы г эл ча )! з оом(т,) оом(.в,) оом(п„) 'в» 'в» ж, лэ» Вначале з 3 4 403 соответствии с шагом (2) атгоритма ! !.5 берем дг)4 РОМ(Я»), Аналогично па)ахаем Я РОМ(Я,). "!сьлючсипе участков 2), и Я» не летает никакой участок гтехо "" так что никаких изменеггггй больше нс требуется.
Теорема ! 1.10. Во окончании работы илга рит чи 1 ирямой домиишпор участки я До к а затея ьст во, Заметим сначала, что ив шаге (1) пра- вильно опРеделЯютсЯ те Участки З, над „'От, ги дамипиРУет Яг, поскольку Я, домиииру ад я, да только тогда когда любой путь в Я из Начальной вершины р проходит че- рез ЯО Индуккней по 1 покажев, что после шага (2] РОМ(Я) — эта участок Я„, 1» 5~1, который доминирует над,Я и над кото- рым в свою очередь даминнрукгт все З ! ~]е.
х', также доми- нирующие над Я. Существование такого участка Я„вытекает непосРедственно вз леммы 1! 13 Вазис г 2 тривиален. ПЕРЕВЛЕМ К ДаКаэатЕЛЬСтву шага индукции. ЕСЛИ Яою НЕ доминиРУет над Я, то заклпченне вытекает непойредстееггно из пРедположениЯ ивдУкции. Если З „„„„ ,ет над Я, но СУЩЕСтзУЕт таКОй УЧаСтОК Я 1 ()Ш Ггх'что З домиинРУЕт НаД З, а Яг, дамиинРУет над дх 0051(Я) ~10054(Яг»»). Таким образом, РОМ(Я) не меняется, что вполне соо ватствует пред- положению индукции. Есле Я', „ „„„„„„ „ )х Я и ломипи- рустся всеми Яи даминирующггми над я ! ~1 щ1, то перед эгим шагом РОМ(Я)=РОМ(я ] В „„,', е, если бы это было ие так, та нашелса бй угг стон Я 1(йл'г, ДоминиРУю. ший иал Я,, но не пал Я что невозможно по Лемме 1 .
3(1), г 1 Слеловательно, РОМ(я) прхнимает именно зиачен е Зг»О с- рема показана. С) Отметим, чта если Р строится из программы то число дуг не более чем влвое пРсвасходит число участков Поэтом) шаг (1) аЛГОРИтМа 11.5 ВЫПОЛэяется за время п стПОРЦИОНаЛЬНОЕ квадрату числа участков. Требуемая емкость п]тапорциональва числу участков, гл. и. оптимизация кодл Ы.Э. ПРОГРАММЫ С ЦИЛЛАМН Рнс !! ЭЗ Грэй уэрээаеэая, Если Я„Я,, ..., Я,— участки программы (кроме началь.
ного), то их ламинаторы можнО запоминать как последовательность Жо В„..., 4Г„, где бг--прямой домннатар для Яп 1 <г<п. Все домннаторы для Я, легко выбрать из этой последовательности, вычисляя ООМ(Я,), ООМ(ООМ(ЯГ)) и т. д. вплоть до начального участка. !1.3.3. Примеры преобразований программ Займемся теперь преобразованиями, которые можно применить к программе нли ее графу управления, чтобы уменьшить время выполнения получающейся в конце концов объектной программы. В этом разделе мы рассмотрим примеры таких преобразований. Хотя полного каталога оптимизирующих преобраЗований программ с циклами не существует, рассматриваемые здесь преобразования полезны для широкого класса программ.
1. Уболгниз бесполезных огггрэторсч Зто — обобщение преобразования Т, из равд. 116, Без оператора, не влияющего на значение программы, можно обойтись, так что его можно удалггть. Линейные участки, недостижимые из начальной вершины, очевидно, бесполезны, и нх можно удалить. Операторы, вычисляющие значения, не используемые в конечном итоге при вычислении выходной переменной, также попадают в зту категорию, В равд. !1.4 мы опишем технииу применения этих преобрааований к программам с циклами. 2 Исктгочгние избыточных еычнслгиий Зта преобразование обобщает преобразование Т, нз равд, 11.1.
Предположим, что у нас есть программа, в которой участок я дол~иГГируетнздЯ', ичтоЯи Я' содержатоператоры А В+С и А' В -~;С саответствеано. Если ни В, ни С не переопределены на паком-нибудь (не обязателыю без циклов) пути иэ я в я' (выясаать это нетрудно; см. упр, 11.3.3), та значешгя, вычисляемые этими двумя выражениями, совпадают. Тогда в Я после А В -~- С можно вставить оператор Х А, где Х вЂ нов переменная.
Затем А' В+С можно заменвть на А' Х, Крометого,если А нигде на пути нвЯ вЯ' не переопределяется, то оператор Х А не нужен, а А' -В+С мажпа заменить на А' А. Здесь предполагается, что выгоднее сделать два присваивания Х А и А' Х, чем вычислять А' В+С, это предположение справедливо для многик моделей машин. Пример 11.32. Рассмотрим граф управления, изображенный на рис. !1.23. В этом графе участок Я, доминврует над Ям Я, и Я,.
Предположим, что все операторы присваивания, в которые входят переменные А, В, С и Р, таковы, кзк показано на рис. 11.23. Тогда В+С принимает одно и та же значение прн вычислениях в участках Я„Я, и Я,. Поэтому в Я, и Я, не обязательно перевычислять выражение В +С. В Я, после оператора А В -1-С' можно поместить оператор прнсваинзння Х А. Здесь Х. -новое имя переменной. Тогда в Я, и Я, опе. раторы А В -1-С и 6 — В +С можно заменить ва простые операторы присваивания А Х и 6 Х соответственно, н зго не повлияет на значение программы. Отметим, что, поскольку А вычисляется в Я„ вместо Х нельзя использовать А. Преобра. эованвый такимабраэом граф управления изображен нарна.
11 24. Теперь в Я, прГгсваиззнне А Х станонится нзбыточньГлг н его можно исключать. Отметим также, что если в Я, опсратор (г А -1-6 заменить иа В А -1-6, то в я, нельзя уже заменять 6 В+С на 6 Х. Г ! Для исключения из программы избыточных вычислений (оби!их подвыражений) надо выявить вычисления, общие для двух Гл ~ ! Оптимизация колА !Л.З ПРОГРАММЫ С ЦИКЛАМИ нли более участков программы. Избыточные вычисления, общие для участка и каната-нибудь из его доминаторов, ыы уже рассмотрелв. Выражения типа А + В могут вычнсяяться и нескольких участках, нн один из которых не доминирует над данныи учасгкоы Я (где также требуется выражение А + В].
Вообще Рве. П.24. Преобразованный граф управлвнвв. вычисление выражения А -1- В считается избышо«иым а участке аз, если (1) любой путь из начального участка в 2) (в том числе в прахоЛящнй через Я несколько раз) проходит череа вычислепие А+В, (2) влоль ллобого такого пути между последним вычислением А + В и использованием А -л- В в зз не встречается опредсле.
ния ни А, пи В. В равд. 11.4 мы изложим некоторые методы опрелеления втой наиболее Общей ситуации. Отметим, что как и в линейном случае, применение алтей. раических закопав может увеличить число общих подвыражений. 3. Зомгио им«исленей периода выполнения ввмиолениями периода компиляции !!ели это возможно, то имеет смысл выполнить вычисление один раз при компиляции, а не повторять его многократно при исполнении объектной программы. Простой пример — размножение констант, т. е. замена переменной иа константу, когда значение переменной постоянно и известно.
Пример 11.33. Рассмотрим участок геай В Р( 3.14159 А 4)3  — А*Р! С В',3 (г В*С нтйе )г В четвером операторе вместо Р! можно подставить значение 3.14159 и получить оператор В А »3.14159.Можно также вычислить 4)3 и, подставив найденное значение в В А » 3.14159, по. лучить В 1.33333» 3.14159. Можно вычислить!.33333» 3.14159= 4.18878 и, подставив 4.18878 в Оператор Р В+С, получить )г 4.18878»С.
Наконец, можно удалить получившиеся бесполезные операторы. В результате у вас будет более короткая эквиваленгнаи программа геай )7 С )713 4.18878» С мН1е р лл 4. Замани сложных операций Замена сложных операций представляет собой замещение одной операции, занимающей довольна много машиниога врелленн, более быстрой последовательнагтью. Например, пусть исходная программа на ПЛ)! солержит оператор 7 = 1ЕН(СГТН (31(32) где 31 и 32 †цепоч переменной длины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
