Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 76
Текст из файла (страница 76)
(! означает конкатенацию цепочек. Реализовать копквтепацию цепочек довольно сложно. Предпалажимл однако, что мы заменяем этот оператор эквивалентным оператороч ! =15(4ПтН(З()+(.В(ЦПтн(32) 407 ГЛ. Ц, ОПТИМИЗАЦИЯ КОДА Ц 3. ПРОГРАММЫ С ЦИКЛАМИ С )с.«)с С.— С э)7 41.3.4. Оптимизация цмкпов Теперь мы должны дважды выполнить операцию определения длины и один раз сложение. Но эти операции занимают существенно меньше времени, чем конкатенация цепочек.
Другие примеры оптимизации такого типа: замена некоторых умножений сложениями и замена некоторых возведений в степень повторными умножениями. Например, оператор С )Г(3 можно заменить последовательностью при условии, что деп1евле вычислить )7«)7»)С, чем вызывать ПОдПрОГраММЫ дпя ВЫЧИСЛЕНИЯ )7А КаК АХТ!БОО[3э БОО()т)). В следующем разделе мы научим более интересную форму замены сложных операций в циклах, когда есть возможность заменять некоторые умножения сложениями. Грубо говоря, цикл в программе — это последовательность участков, которая может исполняться повторно. Циклы присущи большинству программ, а многие программы имеют циклы, испалвлемые много раз.
Во многих языках программирования есть конструкции, предназначенные специально для Организации циклов. Часто можнодобиться существенных улучшений в смысле времени исполнения программы, применяя преобравована я, уменьшающие только оценку циклов. Универсальные преобразования, которые мы только что рассматривали, а именно удаление бесполезных операторов, исключение избыточных вычислений, размножение констант, замена сложных операций, полезны, в частности, и в применении к циклам.
Существуют, однако, н другие преобразования, Ориентированные специально на циклы. Это вынесение вычислений из циклов, замена дорогих операций в циклах более дешевыми и развертывание циклов. Для того чтобы применить эти преобразования, цикл сначала надо выделить из данной программы. В случае циклов ОО в Фортране или промежуточного кода, образуемого из цикла ОО, найти цикл просто. Однако понятие цикла в графе управления более общо, чем понятие цикла, возникающего из операторов Я) Фортрана. Эти обобщенные циклы графов управления называют „сильна связными областямн". Любой цикл графа управления') с единственной точкой входа служит примером сильно связной области. Олнако и более общие структуры циклов также слу.
') поачерхээаем: „вака графа", т. е, замнаутмв путь э гэафе. — Прчм. вез. жат примерами сильно связных областей. Дадим определение сильно связнои Области. Определение. Пусть р †гр управления, а Гг" †подмножество его участков. Будем называть к сильно связной Областью (или, короче, областью) в р, если (1) в и" существует такой единственный участок Я (вход), что найдется путь из начальной вершины графа р в эг, не проходящий ин через какой другой участок из К, (2) существует путь (ненулевой Алины), лежащий целиком внутри г" и ведущий из любого участка в К в лкбой другой участок в г". Пример 11.34.
рассмотрим абстрактный граф управления (рис. 11.25). (2, 3 4, 5) †силь связная область с входом 2, Рэс. 1ЦЗВ. Граф Гэваэлеээя. (4) — сильно связная область с входом 4. (3, 4, 5, 5) — Область с входом 3. (2, 3, 7) †облас с входом 2. Еще одна область с входом 2 в (2, 3, 4, 5, 6, 7). Последняя максимальна в том смысле, что любая другая область с входом 2 содержится внутри этой области.
Г) Важной особенностью сильна связной области, благодаря которой она н помогает улучшать код, нвляетсн однозначность гл и, ОптимнзАция кодА П.г. ПРОГРАММЫ С ЦИКЛАМИ определения входного участка. Например, одна из оптимизаций. выполняемых на графах управления, заключается в перемещении инвариантного в области вычисления в участки, предшествующие нходиому для данной области (можно также построить новый участок, содерь.ащнй инвариантиые вычисления и предшествую- щий входу), Входные участки графов управления можно охарактеризо- вать в терминах отношения доминирования. Теорема 11.11. Пусть и — граф улроаеекмя.
)гчосшок Я и Р яеялешся еходяым участком аблисши тогда и толока шогдо, как)а сущестгует шомай учосшок Я', опо из него есшь дуга и Я и Я либо дожокируегл нод Я', либо совпадает с ЯС Доказательство. Необходимость. Предположим, что.З— входной участок области г". Если У=(З), то результат три- виален. Если нет, пусть Я'Е е, Я'~=Я. Тогда Я доминирует иад З', поскольку в противном случае найдется путь нз началь- ной вершины в Я', непроходящий через Я, вопреки предположе- нию атом, что Я вЂ” единственный входной участок. Таким образом, входной участок областидоминируетнадлюбымдругнм участком. Поскольку в Я ведет путь из любого элемента множества х, в У' — (З) должен быть хотя бы один участок Я', связанный не- посредственно с З.
Досшошочкосшь. Случай Я .=Я' тривиален, так что будем считать, что Я~ЯК Определим г ках объединение участка З с такими участками Я", что Я доминирует над Я' и существует путь из Я" в Я, проходящий ~олька через вершины, иад кото- рыми доминирует Я. По предположению Я и Я' оба принад- лежат и". Надо показать, что г" — область с входом Я. Ясно, что условие (2) определения области удовлетворяется, поэтому мы должны показать, что существует путь из начальной вер- шины в Я, не проходящий ни через какой другой участок в г".
Пусть Жг...'й„Я вЂ” кратчайший путь вычислений, ведущий в Я. Если 6 Е'г", то найдется такое число г, ! (!(), что Ег=Я, поскольку Я доминирует над 6. Пришли к противоречию, так как тогда 6,...6„53 не будет кратчайшим путем вычислений, ведущим в З. Итак, условие (1) определения сильно связной области удовлетворяется. С) Очевидно, что множество 'г", построенное в ходе доказатель- ства достаточности условия в теореме !1.11, является макси. мальиой областью с входом Я. Было бы очень хорошо, если бы область с входом Я была единственна, но, к сожалению, это не всегда так. В примере 11.34 три области с входом 2. Тем ие менее теорема !1.11 полезна при построении эффектив- ного алгоритма, вычисляющего максимальную область, которая единственна.
41В Если область ве максимальна, входной участок может дамииировать вад участками, не принадлежащими области, а из них могут быть достижимы участки области. В примере 11.34, ока. жем, область (2, 3, 7) может быть достижима через участок б. Поэтому говорят, что область имеет один икод, если каждая дуга, входящая в ее участок, отличный от входного, выходит нз участка внутри области.
В примере 11.34 область (2, 3, 4, 5, 6,7) имеет один вход. В дальнейшем будем предполагать, что области имеют один вход, хотя не трудно дать обобщение на любые области. !. Перемещении кода Существует несколько преобразований, в которых для улуч. шенин кода можно воспользоваться знанием обласшй, Одно нз важнейших †перемещен кодо. Вычисления, не зависящие от области, можно вывести за ее пределы.
Пусть, скажем, внутри некоторой области с одним входом переменные У и Л не меняются, но есть оператор Х у+У. Вычисление К+3 можно переместить в заново образованный участок, связанный только с входным участком области '). Все связи вне области, ранее шедшие во входной участок, теперь идут в новый участок. Пример 11.35. Может паказаться, что вычисления, инвариантиые относительно области, появляются только в неаккуратно написанной программе. Рассмотрим, однако, следующий внутренний цикл ОО исходной программы на Фортране, где переменная определена вие цикла: К=О ОО 3 ! = 1,1000 3 Кф 2+1+)+К Промежуточная програыма для этого фрагмента исходной программы может быть такой: К 0 ! ! цикл Т г' -1- 1 5 т-1- ! К 3+К И ! = 1000 йо1о иыход 1=!+1 йо10 цике еыхш) Ьа!1 Соответствующий граф управления изображен на рис.
11.2б. ') Дабяегеяяе тяяага участке может аряеестя я графу уарязгеяяя, яе аалучяюягемуся яя яз чеков арагргммм. но здесь яягле яе арезяаеягяе(ся, чта гр ф дагжея сбязгтельяо яаеучагься яз ярагряммы. 40 Гл. г! ОптимизАция кОлА ЫЛ ПРОГРАММЫ С ЦИКЛАМН Из рис. !1.26 видно, что (Я„Яе) — область с входоле Я,.
Оператор Т е'.1-1 инвариаитеи в области, таи что его можно переместить в новый участок, как показано на рнс. !1.27. Рне г! 26. Граф унреевення. Рне. 1!.27. Преабреееевнныа граф управления. Несмотря на то, что иа рис. 11.26 операторов столько же, сколько на рис, 11.27, операторы в области будут, па-видимому, выполняться часто, так что ожидаемое время выполнения уменьшится. Г) 2. Индуктивные иеременяые Лругое полезное преобразование связано с удалением переменных, которые мы будем называть индуктивными. Определение. Пусть д' †облас с одним входом я, а Х— переменная, появляющаяся в некотором операторе.
входящем В Однн Иэ уЧаетКОВ В Т. ПуСтЬ Яг...Я„ Яэг... 3„ — таКай ПутЬ ВЫЧИСЛЕНИЙ, Что Кг ПРНиаДЛЕжит й", ! (! (Ш, а Я„, ЕСЛИ СУ. шествует, не принадлежит Т. Огюаиачнм через Х„ Х„ ... значения, присваиваемые Х в последовательности ЯЖг...'э . Если Хы Х„ ... образуют арифметическую прогрессию (с йоложительной или отрицательной разностью) для любого пути вычислений типа указанного выше, то будем называть Х индуктивной переменной в АТ. Будем также называть Х индуктивной переменной, если в первый раз она в Я не определена и ее значения Образуют арифметическую прогрессию. Тогда может понадобиться подло. 412 дящим образом инициализировать ее при входе в участок извне, чтобы выполнить разбираемые здесь оптимизации. Отметим, что задача нахождении всех индуктивных переменных в области нетривиальна.
На самом деле можно доказать, что алгоритма для етого вообще нет. Тем ие менее в общих ситуациях можно выявить достаточно много индуктивных переменных, так что вто понятие заслуживает рассмотрения. Пример 11.36. На рис. 11.27 область (Ям Я,) имеет вход Я,. Если вход в Я, осуществляется из Я,' и управление повторно передается от Я, к Я, и сиона к Ям то переменная 1 принимает значения 1, 2, 3, .... Таким образом, 1 †индуктивная переменнан. Менее очевидно, но 5 †так индуктивная переменнан, поскольку она принимает значения Т + 1, Т + 2, Т + 3, ....
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
