Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 77
Текст из файла (страница 77)
А вот иеремениая Х не индуктивная, так как она принимает значения Т+1, 2Т+3, 3Т+6 ° Е) Важная особенность индуктивных переменных — их линейная связь друг с другом прн передаче управления внутри области, которой оии принадлежат. Например, на рис. !1.27 каждый раз при выходе из Я, справедливы соотношения Б == Т-1- 1 и 1=5 — Т. Если, как на рис. 11.27, какая-та индуктивная переменная используется только для управления в области (на это указывает тот факт, что ее значение ие требуется за пределами области н что непосредственно перед входом в область ей присваивается всегда одна н та же константа), то ее можно исключить. )лаже если за пределами Области требуются все индуктивные переменные, внутри области можно испольэовать только Одну, а остальные вычислять при выходе из области.
Пример 11.37. Рассмотрим рис. 11.27. Исключим индуктивную переменную 1, удовлетворяющую перечисленным выше критериям. Ее роль будет играть 5. Заметим, что после участка Я, переменная 5 принимает значение Т + 1, так что, когда управление возвращается от Я, к Ям должно выполняться со. отношение 5=-Т+1 — 1. Таким образом, оператор Б Т+1 можно заменить на Б 5+1. Но затем в Я; надо правильно вннцннронать Б, так что, ногда управление церсйдет нз Я; в Я„ значением Б после оператора Б Б+1 будет Т+1. ))Оио, что в Я; после оператора Т У -1- 1 надо ввести новый оператор Б Т. Затем мы должны исправить проверку 1=10002 так, чтобы получить эквивалентную проверку относнтьтьно Б, При выполненни этой проверки 5 имеет значение Т + 1.
Следовательно, эквивалентной проверкой будет )! Т-(-1000 5=й? и.з, пРОГРАммы с циклАми Гл.и. Оптимизация кадА Рнс !! 29. Окиэчательиий граф УЭРАЭЛЕЭИЯ. Рас. 1!.26. диль ейим Ореибрэ. эоиаиие графа уериилеиия, 4!5 4!4 Поскольку й не зависит от области, вычисление й Т+ 1000 можно вынести в участок З;. Тогда можно полностью избавиться ат 1.
Новый граф управления изображен иа рис. 11.28. Из рис. 1!.28 видао, что участок З, исключен полностью, а область укорочена на адин оператор. Конечно, размер участка З; увеличился, ва, по-видимому, области исполняются значительно чаще, чем участки вне области. Таким образом, рис. 11 28 представляет ускоренный вариант рис. 1!.27. Шаг 5 Т в З; можно исключить, если отождествить В и Т. Это возможно талька потому, что значения переменных Я и Т никогда не будут разлнчнымн, но несмотря на это обе оии будут „активнымщ в том смысле, чта абе будут использоваться н даль. нейших вычислениях.
Иными словами, в З, активна только переменная 3, ни одна нз них ие активна в З„ а в З; обе активны между операторами В Т и  †. Тф 1000. В этот момент онн, разумеется, принимают одно и то же значение. Если Т заменить иа 5, получим граф управления на рис. 11.29. Для того чтобы понять, чем граф на рис. 11.29 лучше графа на рис. !1.28, превратим каждый из них в программу на языке ассемблера для абстрактной машины с одним сумматором. Колы операций должны быть понятны (12ЕКО означает „переход в случае нулевого сумматора", а !膄переход в случае ненулевого сумматора").
Две этн программы приведены на рис. 11.30. 1.ОАО О ЬОАО =.О 5ТОКЕ К 5ТОКЕ К ЬОАО =- ! ЬОАО ! Чм ВТОКЕ ! АОО =- ! ЬОАО ! ВТОйЕ 5 АОО =! АОО НЮО АОО ! ВТОК Е АОО К циилг ЬОАО 5 5ТОКЕ К АОО =! ЬОАО 1 5ТОйц 5 50ВТК = !Оао АОО К АЛЕКО иииид 5ТОКЕ К ЬОАО ЬОАО 5 АОО ВОВТК й АОМР ц !ИЕ чим еииид: ЕК О ВКО 4 б Рис. !!.ВО. Зканээлеитние эрограиии: и — ирограииа для графа уирэвлеииэ иа рис. !1.26; б — вригреиии для графи увраэлении на рис.
!! 29 Заметим, что длина программы на рис. 11.30,и такая же, как н на рис. 11.30,б, Однако цикл иа рис. 11.30,5 короче, чем на рис, 11.30,а (8 команд вместо !2), а вто важно с точка зрения времени. Е) 3. Замена сложнмл операций Внутри областей возможна интересная форма замены сложных операцин. Если внутри области есть оператор вида А — В и!, в котором значение В ве зависит от области, а 1 — индуктивная переменная, то можно заменить умножение сложением илн вычитанием величины, равной произведению значения, не зависящего от области, и разности арифметической прогрессии, порождаемой иадуктивнай переменной. При этом надо соответствующим образом инициировать величину, вычисляемую в предыдущем операторе умножения.
Пример 11.38. Рассмотрим фрагмент исходной программы РО 5.1=1, ГУ 0031=1,М б А (1, !) = В (1, й) делающий массив А равным массиву В в предположении, что А и В име~от одинаковый размер М ук Аг. Пусть А (1, !) запомииаетсн в ячейке А+Ми(4' — 1)-1-1 для ! (1«,М, ! (уг Аг! гл. ц оптнмизлция кодл 11.В. ПРОГРАММЫ С ЦИХЛАМИ 434 А (100) В (100) 411 аналогичное предположение относится и к В(1, л').
Для удобства обозначив! ячейку А гь через А (ь). Тогда из этой исходной Рне 11 31. Граф уврввлеввя. Рве. 1! 32. Новый граф укрввлеквв. программы можно получить частичнооптимизированную программу йг' дг — 1 у — ! лиеиет л' л'+ ! / 0 К Мел' цикл: ( (+! К+( А (!.) В (ь) И ) ( М йа(а цикл И л <йг' йа10 анею ЬаИ Граф управления новой программы изображен на рис. 11,31.
В этом графе (Я„Я„луе) — область, в которой переменная М инвариантна, а л' — индуктивная переменная, возрастающая на 1. Поэтому оператор К Мел' можно заменить иа К К+М, предварительна присвоив К значение — М вне области. Новый граф управления показан на рис. 11.32. Программа, представляемая этим новым графом, длиннее прежней, во области, соответствующие участкам З,", б)4 и лу„ могут исполняться быстрее, поскольку умножение заменено сложением. Рве 11.33 Окончательный граф уврввлеиня. Интересно отметить, чта можно получить еще более зканомную программу, заменив всю область (лу;, Я„лге) одним участ- КаМ, В КОтОрОМ А (Е ) ПрИНИМаЕт ЗНаЧЕНИЕ В (Е) дпя 1 (К (М в йу. Окончательный граф управления изображен на рис.
11.33. (2 4. Разверщмвалие циклов Последнее преобразование по улучшению кода, которое мы изучим, чрезвычайно просто, ио часта остается незамеченным. Эта раэеерюомаяие цихлае. рассмотрим граф управления на рис. 11.34. Участки Як и Яе исполняются па 100 раз. Таким образам, выполняется 100 команд проверки. От всех этих 100 ка. манд можно избавиться, „развернув" цикл. Иными словами, цикл можно превратить в линейный участок, состоящий из 100 операторов присваивания А (1) В(!) А (2) В (2) ГЛ. П. ОПГИМИЗАЦИЯ КОДА Упражнения УПРАЖНЕНИЯ елд (в) ))О о /= !, ту 5 А(/, /)=С«А(/, /) ЖР 4!В Не допуская таких вольностей, можно было бы развернуть цикл только»на один щаг" и получить граф управления, изображенный иа рис.
11.35. Программа, представленная рис. !1.35, длиннее, на в ней исполняется менынс команд. На рис. 11.35 достаточно 50 команд проверки (вместо !00 команд иа рис. !1.34). Рнс. 11.34. Грвф упревлення, Рнс 11.щ, Граф Гпрявленяя пссле резеертывен в пннлв. 1!.3.1. Постройте промежуточные программы, эквивалентные слелующим исходным программам: (а) Е=-(А+В+С)».5 В .= Е» ( — А) «( — В) «(Š— С) ДВЕА 5()/(Т(/?) (б) 1ог/:=.
! в(ер ! ип1Н йт до Ьей1п А И: =- В(/)+С/ ° )1 !!(АГ/1=0) гйеп Ьаы е(яе А!/!:= / П.3.2. Какие функции вычисляются следующими двумя программами на промежуточном языке? (а) геад /У В 0 / ! цикл: Б В+/ !! /)~ М йо!о ныхад /=/+1 йо(о цикл выход! иг!1е Б Ьа!1 (б) геад йт Т вЂ” й/-?1 Т Тв?/ Т Т«.5 мг!1е Т ЬаН Эквивалентны ли эти две программы, если йт и / представляют целые, а Е и / -вещественные числа? 11.3.3. Рассмотрим программу Тп геад А, В В ! С А«А В В«В И С< В йо(о Х Е А»А /? /?+1 Е Е+/? мг1!е Е ЬаН Х: Š« /? /?+2 Е Е+/? мгые Е И Е > 100 йо1о 1' Ьащ )" /? /? — 1 йо1о. Х Постройте длн нее граф управления. ГПРАЖИГИИЯ Гл. 11. оптимизАция кодА Рне. !1.33.
Граф управление. 421 11.3.4. Найдите домннаторы и прямые доминаторы каждой яершины З в графе управления на рис. 11.36. 11.3.3. Пусть ОН(З1, З„) — множество участков, которые могут появиться в графе управления на пути из З, в З, (через За нельзя проходить повторно, а через З„можно). Покажите, что если З, доминирует над З„то ОН(З„З,) =(З ( существует путь из З а З„ когда участок З, удален из графа управления). Сколько времени займет вычнслейие ОН(З„За)? 11.3.6.
Докажите утверждения [1) и (2) из леммы !1.!3. 11.3РХ Можно следующим образом определить отношение постдоминироввния. Пусть Р-граф управления и З вЂ” вершина в Р. Вершину З' назовем лостдолииалюрол для З, если ласбой путь из З в оператор Ьа!1 проходит через З'. Прядай лопидо. минатор для З яостдомннируется любым другим постдомииато. ром для З. Покажите, что если вершина графа управления имеет постдомннатор, та оиа имеет и прямой постдоиинатор.
11.3.8. Разработайто алгоритм построения прямых постдоминаторов всех вершин графа управления. 11.3.9. Найдитс все сильно саязные области на рис. !!.36. Какие области максимальиыр 11.3.10. Пусть Р†програм из упр. 11.3.3. (а) Исклгачите из Р все общие подвыражения. (б) Исключите из Р все ненужные аычнслеиия констант. (а) Удалите из цикла в Р все инвариантные вычисления. 11.3.11. Найдите индуктивные переменные в следующей программе: ! ! геад 7, К Х: А Ка) В /и( С А+В игйе С 7+-!+! 11 1 < 100 йо1о Х ЬаИ Исключите их столько, сколько сможете, и замените насколько возможно умножения сложениями. 11.3.12. Приведитс алгоритм для нахождения и графе управлеаия всех (а) областей, [б) областей с одним входом и (в) маисимальных областей. *11.3.13. Приведите алгоритм, выявляющий некоторые яндуктианые переменные в области с одним входом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
