Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 73
Текст из файла (страница 73)
Некоторые ае интересные аопектм обсуждеютс» Грэкеиом 1!972)'). 14.3. ПРОГРАММЫ С ЦИКЛАМИ При рассмотрении программ, содержащих циклы, мы не ыожем осуществлять автоматическую шп нмизацию. Основные трудности связаны с проблемами иеразрешиьюсти. Для двух произвольных программ не существует алгоритма, выясняющего, вквивалевтны ли онн в каком-нибудь смысле.
Как следствие этого не существует алгоритма, который находил бы по данной программе эквн вален сную ей и оптимальную относительно какой нибудь оценки. Эти результаты станоиятся понятными, если вспомнить, что сугцествует, вообще говоря, сколько угодно способов вычисления одной и той же функции. Таким образом, существует бес. конечное мвожество алгоритмов, поторые можно использовать для реализации функции, определяемой исходной программой. Если мы хотим получить полную оптимизацию, то компилятор должен быть способен найти наиболее эффективный алгоритм для функции, вычнслнсмой исходной программой, а затем сгенерировать для него наиболее эффективный код.
Излишне говорить, что как с теоретической, так и с практической точек зрения таких оптимизирующих компиляторов ие может быть. Тем ие мепее во многих ситуацинх ыожно указать набор преобразований, применимых к исходной программе дли уменьшения размера и!нли увеличении скорости результирующей объектной программы. Б этом разделе мы исследуем нескольно таких преобразований. Благодаря их широкому распространению, они стали известны как „оптимизирующие" преобрааования. Точнее было бы называть их преобразованиями „улучшения кода".
Однако мы будем следовать традиции и пользоваться более популярным, хотя и менее точным термином аоптимизируюп!ее преобразование". Главной нашей целью будет уменьшение вре. мени выполнения объектной програмыы. Начнем с определения промежуточных программ с циклами. Эти программы будут весьма примитивными, так что основные концепции мы изложим, не вдаваясь в кучу мелких подробностей. Затем определим граф управления программы.
Граф управле- ') Оптимизация арифметических вырэженнй, включэющвя выделение общих подвырэжений ° тэк е преобразование программы, чта эти общие падвырвжени» вычисляются тольно один рээ, описэи» о реботэк: [Ершов, 196661, Р К мынии, Любимо»из, Шура.Бтр, 1966), !Ершов, 1969е), !Китов, Криницкий, Шй), [Ершова, Мостинсквя, Руднева, )9611, [Поттосин, 1966!. При этом полностью учнтывэлвсь наммутэтивнасть сложения и умнажени».
Б работая Ершов» [19666! н Поттоснш 119651 приведены алгоритмы экономы» вырэженнй, рябатвющне ав линейное время — Прим. щреэ. Гл. 11. Оптимизлпия кОдл И 3. ПРОГРЛММЫ С ПИКЛЛМИ нин — это двумерное представление программы, отражающее порядок выполнения операторов программы. Обычно двумерная структура дает более наглядное представление, нежели линейная последовательность операторов.
В оставшейся части этого раздела мы опишем ряд важных преобразований, применимых к программе с целью уменьшить время выполнения объектной программы. В следующем рааделе рассмотрим, как собран, вместе всю информацию, необходимую для применения некоторых из преобразований, описанных в этом разделе.
11.3.1. Модель программы Мы будем испольэовать для программ представление, промежуточное между исходной программой и языком ассемблера. Программа состоит из последовательности операторов. Каждый оператор можно пометить идентификатором, за которым следует двоеточие. Существует пять основных типов операторов: при. сваивание, переход, условный, ввод-вывод и останов. (1) Оператор лрисэпиэанил — это цепочка вала А . — ВВ,...
В„ где А †переменн, В„ ..., В, †переменн или константы,  — г-местная операция. Как и в предыдущих разделах, для бинарных операций обычно будем пользоваться ннфнксной записью. Оператор вида А В также будем относить к этой категории. (2) Операглор перехода — это цепочка вида йо(о <метка> где <метка> †цепоч букв. Будем предполагать, что если в про. грамме употребляется оператор перехода, то метка, следующая за йо1о, появлнется в качестве метки только одного оператора программы. (3) Условный оператор имеет вид И А <отношение> В йо1о <метка> где А н  †переменн нли константы, а <отношение> †бинарное отношение, такое, как С, (~, =, Ф.
(4) Оператор езсда-выведи — это либо оператор чтения вида геаб А где А — переменная, либо оператор записи вида мгые В 314 где  — переменная или константа. Для удобства последователь- ность операторов геад А, геад А, геаб А„ будем изображать в виде геаб Ао Ао, .., А, Аналогичное соглашение у нас будет и для операторов записи. (5) Наконец, Огмратор Осгпансэи — это команда Ьаы. Интуитивный смысл операторов каждого типа должен быть ясен. Например, условный оператор вида И АРВ йо1о Б означает, что если между текущими значениями Л и В выполняется отношение г, то управление должно передаваться на оператор, помеченный й. В противном случае управление переходит к следующему оператору. Оператор Олредгления (илн просто Олредиенпс) — это оператор вида геаб А или А ВВ,...В,.
Про оба этя оператора говорят, что они определяют переменную А. Сделаем еп[е несколько предположений относительно программ. Переменные — эголибо простые переменные, например А, В, С,..., либо переменные, нядекснрованные одной простой перелгенной или константой, например А(1], А(2), А()) илн Л(У).
Далее будем считать, что все переменные, на которые в программе есгь ссылки, либо должны быть входиымя переменными (т. е появляться в предыдущем операторе чтения), либо должны ранее определяться с помощью оператора присваивания. Наконец, будем предполагать, что каждая программа содержит хотя бы один оператор останова и, если программа заканчивается, последний выполненный оператор — это оператор останова. Выполнение программы начинается с перво~о оператора програмиы и продолжается, пока не встретится оператор потапова.
Предполагается, что каждая переменная имеет известный тнп (например, целое, вещесгвенное) и ее зншмниг в любой момент в процессе выполневия либо не определено, либо представляет собой некоторую величину подходящего типа. (Будем считать, что все используемые операторы соответствуют типам переменных, к которым онн применяютсл, и, когда надо, происходи~ преобразование типов.) зээ гл ы, оптимиэдция кодл Вообще говоря, входные переменные программы — это те, которые связаны с операторами чтения, а выходные — с операторами записи.
Присваивание значения каждой входной переменной прн каждом чтении называется акодмым лрисааидинисм. Зкакние программы при некотором входном присваивании — это последовательность заачений, записанных выходными переменными в процессе выполнения программы. Две программы будем считать зкзизалентлыми, если для каждого входного присваивания оии имеют одинаковые значения '), Это определение эквивалентности обобщает определение эквивалентности блоков (равд.
11.!). Чтобы убедиться в этом, предположим, что два блока Вг =(Р„ I„ (уг) и Мд =-(Р„ !„ У,) эквивалентны в смысле равд. !1.1. Преобразуем очевидным образом блоки Яь и ю, в программы Р, и Ую Иными славами, поставим операторы чтения для переменных в (г и (ь перед Р, и Р, соответственно, а операторы записи для перемейных в (7, и ((ь — после Р, и Рк Затем к каждой программе присоединим оператор астапова. Операторы записи н Р, и Р, нужно добавлять так, чтобы каждая выходная переменная печаталась хоти бы один раз и последовательности напечатанных значений для бьг и Уь были одинаковыми. Поскольку блоки льг и мь эквивалентны, это всегда можно сделать.
Легко видеть, что программы уг и уь, эквивалентны независимо от того, что именно берется в качестве множества входных присваиваний и как интерпретируются функции, представленные операциями, входящими в 5', и Уь. Напричер, иожно взять в качестве входного множсство префиксаых выражений и считать, что применение операции 0 и выражснинм з„..., з, дает Ое,... е,. Однако, если Зг и Юг не эквивалентнй, то всегда найдется множество типов данных для переменных и интерпретации для операций, приводящие к тому, что соответствующие блокам про.
граммы Уг и Р, будут вырабатывать различные выходные по. следовательиости. В частности, пусть „типом" переменных будут префиксные выражения, а результатом применения операции 0 к префнксным выражениям е„ ..., ед будет префиксное выра. жение Оь, г„. Ясно, что относительно типов данных и алгебры, связанной с функциями и знаками отношений, можно сделать такие пред. положения, что програымы У, и У, окажутся эквивалЕнтными.
'> Предаадьгаетсд, что смысл «аждая операнди я задка атэашеая», а также тяя данных вждоа иьреченная зафядсиравьэ. Такая образом, эта пааятие эязнеадеятаасть~ атддчдетсд ат даэясяя, ааьдеяеаго ранее, например Пьтерсаяои Ирбэ) яля Ладдэмаи я др. ( Ш701, геи, чта аня требуют, чтобы две прогремим дава и ад акад е з дчсяяэ е только для,каждого эхадяага ярясзаяезняя, яа я ддя каждого тядз даддих ддя дерен«язых я ддждага множества фуикаж> я агкашеяяв, которые ям подставляем вместо аяераияв ь знадаз атдошеядз. ~~ з, прогрдммы с циклдми В таком случае блоки Юг и лть будут эквивалентными относи.
тельно соотаетств>ющего множества алгебраических законов. Пример 11.26. Рассмотрии следующую программу для алгоритма Евклида, описанного в гл. О (том 1). Выходом должен быть нзибольший общий делитель двух положительных целых чисел Р и ф геаб Р геаб 0 цикл: г гегпа(пает (р, д) П г.= О йо1о выход 0 0 йо1о цикл эыхадг итИе 0 Ьаж Еслгг, например, входным переменным Р н д присвоить зна. чения 72 и 66 соогветственпо, то при обычной интерпретации операций выходная переиенная О к моменту выполнения оператора записи будет виеть значение 8. Таким образом, значением этой программы для входного присваивания р 72, 0 56 служит „последовательносгьь 8, вырабатываемая выходной переменной 0. Если заменить оператор йа1о цикл на П бтьО йа1о цикл, то получим эквивалентную программу, Это следует нз того, что оператора йа1о цикл нельзя достичь, если в четвертом операторе не выполняется условие гть О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
