Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 65
Текст из файла (страница 65)
Тогда суи(сствует такой блок Уд,', что Зл~лЯ;елЗл. Доказательство. Упражнение. С) Теперь мы готовы к таму, чтобы дать общую схему оптимизации блокоа в соответстаии с любой приемлемой оценкой. Теорема 11 б подаодит базис для втой оптимизация. Теорема 11.б. Пусть З вЂ люб блох. Существует блок Я', зкоиеалентлмй Я и осакой, юпо ети С вЂ” ориемлемия оценка, то найдутся такие блоки Я, и Ям юпо (1) Я' фоло (2] Я, с:лЯ„ л (3) Я, оптимален относительно С. Доказательство. Пусть Я" — любой приведенный блок, эквивалентный Я.
Можно преобразовать З" в открытый блок Я', экаивалеитный Уд", с помощью только Т,. Па лемме 11.б блок Я' приведен и открыт. и ь оптнмизлпия линейного учлслкл Пусть Я,— оптимальный приведенный блок, эквивалентный Я. По лельл|е 11.5 Я, существует. Таким образом, 0(Ял) = 0(З') в силу следствия теоремы 11.3. По теореме 11.2 Я' ел Я,. Заметим, что Ть н Т, взаимна „обратимы", т.
е. 6 ~л л Ю тогда и только тогда, когда 6 ~,, Я. Следовательно, наидется такая последовательность блокоо $*„ ..., 6„, чта З' = М'„ Я„ = э„ и Ф, алл, И, „для 1 ( ! . л. Миагокра~ но применяя лемму 11.7, можно перенести нсе Т, перед ясеин Т, и найти такой блок я,, чта Я' илЗ, ла.Яе Если яннмательно присмотреться к теорелле 11.б, можно заметить, что она разбнзает весь про~гесс оптимизации нв три стадии. Допус ~лги, мы хотим оптилплзирояать данный блок Я (1) сначала можно исключить из Я лишние и бесполезные вычисления и переименовать переменные с тем, чтобы получать приееденпыа открытый блок .Я', (2) затем в Я можно переупорядачить операторы с помощью перестановки и делать это ло тех пор, пока не сформируется блок Я,, в котором операторы расположены в наилучшем порядке, (3) йакопец, в Я, можно переименовывать переменные до тех пор, пока не будет найден оптимальный блок Я,.
Отметим, что шаг(1] можно выполнить эффективно (кяк функцию длины блока). Читателю предлагаем разработать алгоритм для шага (1], обрабатываюплий блок из и операторов за время 0(гг 1ой и). Один из шаьоа (2) или (3) часто оказывается тривиальным Приведем пример, показывающий, как преобразовать операторы прол|ежуючного языка в язык ассемблера, тобы число выпал. пяемых команд языка ассемблера было чинимальнылл. Мы увидим, что этот алгоритм оптимизации не нуждается в шаге (3).
Дальнейшее переименование переменных ие будет ваниль на оценку. Пример 1(.й. Наш пример содержит несколько интересных идей, которые не затрагиваются ни в какой другой части книги Читателю настоятельно рекомендуем подробно разобраться залом примере. Рассмотрим машинный код, генерируемый для блоков. Вычислительная машина имеет одни сумматор и следующий набор команд языка ассемблера, сллысл которых мы кратко расшифруем: (1) СОАО гИ, Содержимое ячейки памяти М помещается иа су.мматор. (2) ВТОВЕ М. Содержимое сумматора запоминается в ячейке памяти М. (3) ОМ,Мх ...
~И,. В этой команде й — имя г-местной операции. Ее пераый аргумент †суммат, второй — ячейка намял и ьИм гл о пптиьгизчцня Колл ил. оптимизация яиненного гчлсткх третий — ячейка памяти Мг и т. д. Результат применения опера- ции О к своим аргументам размещается на сумматоре. Генератор колов должеа переводить оператор аида А - ОВ, ... В, а последовагельиосгь машинных команд !.ОАО В, й В„В, БТОКЕ Л Однако если значение В, уже находится ня сумматоре (г.
е. перед этим был оператор, присванвающий значение В,), то пер. вую команлу ЕОАО генериронать не надо. Аналогично, если значение А не требуется нигде, кроче первого аргумео!а сле- дующего оператора, то заключительная команда 5!ОЙГс не нужна. Оценивать оператор Л вЂ” ОВ,...В„можно числамн 1, 2 и 3. Оценка равна 3, если В, нет на сумматоре и э дальнейшем есть ссылка на новое значение А, отличная от первого аргу- мента следующего оператора (т. е.
Л надо запомнить). Оценка равна 1, если В, уже на сумматоре и ает ссылки на А, отлич- ной от первого аргумента следующего оператора. В остальных случаях оценка равна 2. Заметим, что гакой способ оценки полностью исчерпывает асс случаи, заслужиаающие рассмотрения. Чтобы показать, что он правильно отражает число команд, требующихся для выпол- нения блока на нашей машине, надо сначала точно определить эффект последоиагсльпостн команд языка ассемблсра.
Если зто сделано должным образом, то каждую программу па языке ассемблера можно сопоставить с блоком на промежуточном языке путем отождествления команд языка ассемблера типа(3), т. е. операций, с опсраторвми блока. Бес эти детали мы прел- лагаем в качестве упражнения. В настоящем примере мы будем пользоваться оценкой блоков а том виде, как мы ее определили. Рассмотрим блок Эйг = (Р,(Л, В, С), (Р, 6)), который мог бы получитьси, скажем, из операторов Фортрана Р=(Л ф В) я (А — В) 6 — (А — В)я(А — С) э( — С] Список операторов э Р, таков: Т вЂ” А+В 5 А —  Р— Тэ5 Т -А — В 5 — А — С В В вЂ” С Т Тэ5 6 ТчВ Бесполезных операторов здесь нет. Есть, однако, повторення— второй н четвертый операторы.
Эту избыточность можно удалить, а затем переименовать ао всех операторах переменные, которым нрисэаиваются значения. В результате получится прииеденный открыгыи блок 33г — (Р„(А, В, С), (Х,, Хг)). Он играст здесь роль блока,Я' в теореме 1).б. Операторами э Р, будут Х, — АФВ Х,+ — А -В Х, Х,эХ„ Х, А — С Х„В вЂ” С Х.-х,ях, Х» Хггг Хг Рас. !!А.! раф хля Я,, !'раф для 3), изображен иа рис. 11сй Вершина и, соответстяует оператору списка Р„прнсэаивающему значение перемгн.
ной Хс Ыы видим, что существует много программ, в которые можно преобразовать лгг с помощью только Т,. Предлагаем в качестве упражнения доказать, что их столько, сколько сущестя) ет 349 Гл г! Оптимизлция кОлА линейнмх порядков, в которых выполняется частичный порядок, представленный на рис. 11.4. Верхняя граница эгого числа равна 71, т, е, число нереста. новак из семи операторов. Но в действительности это число булет меньше, так как операторы ив Р, не могут располагаться а !набом порядке. Например, третий оператор а Р, всегда должен следонать за вгорым, поскольку третий ссмлается на переменную Х,, а второй определяет ее Отметим, что применение 7', может изменить пмя Х„но то же отношение будет выполняться и с поныл! именем. 7(ругая интерпретация ограничений на возыажности гг переупорядочивать блок заклгочается в том, что при любом таком переупарядочснии каждая вершина в В(бй!) будет саотаетствовагь некоторому оператору.
Опергшор, соответствующий внутренней вершине и, не может предшествовать никакому опера. тору, соответствующему внутренней вер!пине, являю!церюя потомком верн!ины л. Этот пример достаточно прост для того, чтобы просмотреть асс линейные порядки в Р„ но для произвольного блока этого сделать нельзя, поскольку это связано с болыпими затратами времени 7(л» гого чтобы быстро вырабатывать хорошее, но нс обязателыю оптимальное упорядочение, нужна некоторая звристика Злесь мы предлагаем один такой способ. Следуюгций алгоритм дает линейное упорядочение вершин графа.
В требуемом блоке операторы, соответствующие этим вер!швам, расположены а обратно!! порядке. (1) Строим список В. Вначале он пуст. (2) Выбираем вершину л графа так, чта л6~ и, если существуют входящие а л дуги, они должны выходить из вершин, уже принадлежащих С Добавляем и к Е. Если такой вершины нет, то ос'гааавливаемся. (3) Если и, — послепнЯЯ аеРшииа, добаялениая к 1., самая левая дуга, выхаднщая из ли указывает иа внутренню!о вершину », нс прнпадлежащуга 1., и все прямые предки л уже припаллежат С, то добавляем л к 7. и повторяем шаг (3). В прошганом случае перехалим к шагу (2).
Например, испольвуя граф рис. 11.4,можно начать с Е =лл. Согласна шагу (3), к С добавляем и,. Затем выбираем и добав. лясм к С вершину л„ а потом и, и и,. В реаультате еще двух применений правила (2) добавляются л, и л„, так что С имеет вид л„ ли л„ ли л„, и,, л,. Вспамшин, что оператор, прнсаанвающий значение Хг, порождает вершину л! и что список Е соответствует операторам в абра~нам порядне, получаем блок 3)г=(Р„(А, В, С), (Х„ХГ)).
Легко проверить, что ЯлслЯ!. 550 и,!. ОптимизАция линеЙБОГО участка Список операторов в Р, таков: Х,  — С Х, — А — С Х, — А — В Х, Х,эХ, Х, Х, Х, — А(-В Х, Х, Х, Програмлгы на языке ассемблера, созданные иа блоков Я! и Я„ приведены на рис. 11.б. — Иза б — ИАШ! Рис. П б. Программы иа языке Ассемблера. 4(м,б.
Алгебраические преобразовании Известно, что во многих языках программирования нека!орые операции и операнды подчиняются определенным алгебраи. ческим законам. Учитыван этн законы, можно проводить такие улучшения програмлгы, какие ненозможно одела~~ с использованием лишь четырех рассмотренных выше ~ннов преобразований. 551 СОЛО А ЛОО В 5ТОКС К ЬОАО А щ;Втк в 5ТОКЕ Х! СОЛО Х, игл.т х 5ТОКБ Х! 10АО А 5ОВТК С 5ТОКЕ Х, 1,ОЛО В 5ОВТК С 5ТОКЕ Лл 1.0ЛО К, ЛЦГ 1 Л., МО!.Т 5ТОКЕ Х, 1.ОЛО В 5ОВ1К С 5?ОКГ.
Х, СОЛО А 5ОВТК С 5ТОКС Х, СОЛО А 51!ВТК В 5ТОКЕ Х, МОПТ Л, Могст Х„ 5ТОКБ Х, 1.0ЛО А ЛОО В мог х 5ТОКБ Х, гл. н. оптимнзхпня кодл 352 зээ 12 л. д*с. дж. уаькен, с. з Перечислим несколько полезных н распространенных алгебрзнчссккх законов: (!) Бинарная операпия 0 называется коммжлсюаеной, если ООО-.-ООО для всек выражений ц и (). Прнмерамп коммутатквных операций служат сложение н умножение целых чнсст'). (2) Бинарная операцця О называется нссацпалнтена/н если ОО (Ойу) = (ООБ] О! для всех сх, Б и у.
Напрнмер, сложенне ассоцнатнвпо, так как а ф [О ф У] = (ц + О] '- У ') (3) Бинарная операция О, вазывзстсн дахпрнбуюпзлои атно сительно бинарной операция Ою если аб, [ООсу) =.(абхО)От(ОО,У). Например, умноженне днстрнбутнвно относительно сложеши, так как он[О-ху)=п О-(-ану. Предосторожности здесь теме, что н в (!) и (2).
(1) Унарная операция О называется идсхглотсн~лнай, если ООО=О для всех и. Например, логическое нс и унарный цян]с ндемпотептпи. (О) Выраженне я нааывается нейтролвным относя~ельца [бгиарной) операция О, если еОО=ООе=-и для всех и. Вот примеры нейтральных выражений; (а) Константа О нейтральна относительно сложения Нейтрально я лкбое выражение, имеющее значение О, такое, например, как о — О, а О, [ — ц)-[-и н т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
