Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 74
Текст из файла (страница 74)
Поскольку в шестом операторе 0 принимает значение г, то прн выполнении седьмого оператора равенство 0 =- О невозможно. Е) Следует отметить, что преобразования, которые чы можем применять, в значительной степени определнются теми алгебраическими законами, которые мы считаем справедливыми. Пример 11.27. Для некоторых типов данных можно считать, что и еи =О тогда и только тогда, когда а-..-О. Если принять такой закон, то программе из примера 11.26 эквивалентна про.
грамма геаб р геад О цикл: г геша!пбег (р, 0) г гаг П 1--0 йо1о мкход Р 9 о г йа(а цикл эыходг чтце 0 ЬаИ гл.и. Оптимизация кОдл 11 з, ПРОГРхммы с пнктхми Конечно, при любых мыслимых обстоятельствах э1а программа ничем не лучше, но если сформулированный нышс закон неверен, то эта программа и программа из примера 1!.26 могут оказаться и не экВивалентными. П Если дана программа Р,то наша цель заключается в нвхож' денни эквивалентной программы Р',для которой ожидаемое время выполнения в машинноч языке мепыпе, чем для Р. Разуияым приближением нашей задачи будет нахождение такой эквивалентной программы Р", что ожидаемое число команд машинного языка, которые предстоит выполнить в Р", мсвьше числа коканд, выполняемых в Р.
Эта задача яиляетси приближением, поскольку различные машинные команды могут выполняться за различное машинное время. Например, такая операция, как умножение ияи деление, обычно занимают болыпе времени, чем сложение или вычитание. Тем не менее мы сначала займемся уменьшением только 1исла выполняемых команд машинного яаыка. В большинстве программ одни последоватсльнос1и операторов исполняются значительно чаще, чем другие. Кнут 11971] на большом числе программ Фортрана обнаружил,что в типичной программе около половины времени тратится менее чем на 4эй программы.
Таким образом, иа практике часто достаточно применять оптимизирующие процедуры только к этям многократно проходимым участкам программы. В частности, оптимизация может состоять в том, что операторы перемещаются из многократно проходимых областей вобласти, редкопроходимые, а число операторов в самой программе не меняется или даже увеличивается. Во многих случаях ножно определить, иакой кусок исходной программы будет выполниться чаще других, и вместе с исходной программой передать эту информаци1о оптимизирующему компялятору.
В других случаях довольно просто написать подпрограмму, подсчитывающую,сколько раз исполняется данный оператор. С помощью такого счетчика можно получить „частотный профиль" программы и выявить те ее куски, на которые надо направить основные усилия по Оптимизации. 11.3.2. Аианнз натана управления !1ервый п1аг иа пути оптимизации программ заключается в опрЕделении потока управлЕния внутри программы. Для того чтобы сделать это, разобьем программу на группы операторов так, чтобы внутри группы управление передавалось только на первый оператор, и если уж оп выполиился, все остальные операторы группы выполняются последовательно.
Такую группу операторов будем называть яияейяым участком или просто учасшкам. Определение. Оператор 5 в програмые Р иззываетси входом в линейный участок, если он (!) первый оператор в Р или (2) помечен идентификатором, появляющимся после йшо в опе. раторе перехода либо в условном операторе, или (3) непосредственно следует за условным оператором. Линейный участок, отяосже(ийся к входу в участок 5, состоит из 5 и всех операторов, следующих за 5, (1) вплоть до оператора останова и включая его или (2) вплоть до входа в следучощий участок, но ие включая его.
Отметим, что программа, построенная из блока в смысле равд. 11.1, будет линейным участком в смысле настоящего раздела. Пример 11,28. Рассмотрим программу из примера 1!.26. В неи четыре входа в участок, а именно первый оператор про. граммы, оператор, помеченный цикл, оператор присваивания р у и оператор, помеченный выход. Таким образом, в этой программе четыре линейных участка: У!веток 1 геай Р геаб д Участок 2 цика: г гепга)пйег(Р, у) П е = 0 йо!о выход Участок 3 Р У йа!о цикл Участок 4 вь1ход: жгые у Ьаы П Из участков программы можно сконструировать граф, весьма похожий на блок-схему программы. Определение.
Графом уяравявяия назовем помеченный ориентированный граф С, содержащий выделенную вершину я, из которой достижима каждая вершина в 6. Вершину и назовем начальной. Граф управления лрвграямы †э граф »правления, з котором каждая вершина соответствует какому-нибудь участку программы. ~рсдположим, что вершины 1 и ! графа управления соответств>ют участиам !' и ! программы. Тогда дуга идее из вершины ! в вершину 1, если (1) последний оператор участка 1 не является ни оператором перехода, ни оператором астапова, а участои ! следует в программе эа участком 1, нли Гл. 11. ОптимнзАция кадА 11.3.
ПРОГРАММЫ С НИКЛАМИ (2) послепний оператор участка 1' является оператором йо1о Е либо оператором Б ... уо1о Е, где Š— метка первого оператора участка !. Участок, содержащий первый оператор программы, назовем начальной вершиной. Ясно, что любой участок, недостижимый из начальной вершины, можно удалить из данной программы, ие меняя ее значения. Отныне будем считать, что все такие участки рассматриваемой программы уже удалены. Пример 11.29. Граф управления программы ') примера 11.26 изображен на рис. 11.22, Начальной вершиной является участок 1.
лз У»вазов 4 Рас. 1!.22. Граф управления. Многие оптимизирующие преобразования программ требуют знания тех мест в програмыс, где переменная определяется, и тех, где на ее определение есть ссылка. Эти связи между апре- делением и ссылкой зависят от последовательностей выполняемых участков. Первым участком в такой последовательности будет начальная вершина, а в каждый последующий участок должна вести дуга из предыдущего. Иногда предикаты, испольЗуемые в условных операторах, могут запрещать проход по некоторым путям в графе управления.
Однако алгоритма для выяввения всех таких ситуапий нет, и мы будем предполагать, что нет „запрещенных" путей. Удобно также знать, существует ли для участка З такой участок З , что всякий раз, когда ныполняется Я, перед пим ') Возле в лзльнсвшеы граф уоравленвч ьраграчыы бульв назывзть ллв воз»кости просто Грн)юы уораьленьи — прим. А»рев, выполняется З'. Б частности, если мы знаем зта и если в обоих участках З н З' вычисляется одно н та же аначение, можно запомнить его после вычисления в З' и избежать тем самым неревычисления его вЗ . Формализуем теперь зги иден.
Определение. Пусть Р†гр управления, имена участков которого выбира»атея из некоторого множества й. ПоследоватЕЛЬНОСтЬ уЧаСтКОВ Я,...Я„ НЗ йь НаваВЕМ ЛутВМ ВМЧиолеиий (участков) в Е, если (1] З,— начальная вершина в Р, (2) для 1 (1(и существует дуга, ведущая из З,, в ЯО )(ругнми словами, путь вычислений Я,...DŽ— зто путь в Р из Я, в З„, в котором Я,— начальная верн»ина.
Будем говорить, что участок З' доминирует аад участкол»З, если З'~З и каждый путь, ведущий из начальной вершины в З, содержит З'. Будем говорить, чта З' прямо доминируал нал З, если (1) Я' доминирует над Я и (2) если З" доминирует над Я и З'ФЗ', то З доминирует над З'. Таким образом, участок З' пряма доминирует иад З, если З' — „ближайший" к З участок, доминирующий над З. Пример 11.39. На рис. 11.22 последовательность 1232324— это путь вычислений. Участок 1 пряма доминирует над участкам 2 и доминирует над участками 3 и 4.
Участок 2 прямо доминирует над участками 3 и 4. 0 Приведем некоторые алгебраические свойства отношения доминирования. Лемма 11.13. Если З, доминирует над Зм а З, доминирует нод З„то Я, доминирует нод Я, (транзитивность). (2) Если З, доминирует нод Зм то З, нв доминирует над Я (осиммгтри«ность) (3) Если Я, и З, доминир»рот нод З„то либо З, доминирует над Зм либо З, доминирует над З».
Доказательство. Утверждения (1) и (2) ос~валяем в качестве упражнений. )(Окажел» (3). Пусть Ж».. Я„З,— любой путь вычислений без циклов (т. е. К»чьЗ» и 6»ФЖ» при !ОФь!), Один такой путь существует, так как мы предполагали, чта все першины достижимы из начальной першины. По условию Б»=З» и 6 =З, для неноторых 1 и !. Без потери общности можно считать, что »С !. Мы утверждаем, что З, доминирует иад Зм 401 ГЛ И. ОПТИМИЗАЦИЯ КОДА Предположим противное, т. е.
что Я, не доминирует над Я,. Тогда найдется путь вычислений Ю,,Ю ЯО в котором среди Ю„..., Ю„нет Я,. Отсюда следует, чта й>,.. Ю„'„В „'0 . » ...й„Я» †так путь вычислений. Но среди символов, предшествующих Я„нет Я„а это противоречит предположению о том, что Я, доминирует над Я». Лемма 11.14. Каждый Вчтток, кроме начильиой вершины (ие имеющей домилтпорое), имеет единсглеенпый прямой дом»»отар, До казах ел ьс те о. Пусть д' — множество участков, доминирующих над пекотарым участком Я.
Па яемме 11.!3 отношение доминировании устанавливает (строгий] линейный поря. док на О. Таким образом, д' обладает наименьшим элементом, который должен быть прямым домннатором участка Я (см. упр. 0.1.23). П Изложим теперь алгоритм, вычисляющий отношение прямого доминирования для графов управления. Алгоритм 11.5. Вычисление прямого доминирова. ния. Вход. Граф управления Р н множества й =(Зо Зи, .., Я„) его участков. Предполагается, чта Я, — начальная вершина. Выход. Прямой доминатор РОМ(З) участка Я для каждого Я Е йо кроме начальной вершины.
Метод. РОМ(З) вычисляется рекурсиано для каждого Я из Ь вЂ” (Зг). В любой момент РОМ(З] будет участком, ближайшим к З среди всех участков, для которых уже известно, что оии доминируют над З. В конечном итоге РОМ(З) будет прямым доминатором участка Я. Вначале РОМ(Я) — это Я, для всех Я из Ь вЂ” (Я,). Для(=2, 3, ...,Ивыполиясм следующие два шага: (1) Исключаем участок Я, из Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
