Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 82
Текст из файла (страница 82)
Грзф уереегеииз. 447 443 !а) Гь !У) Ге Рее. Ы,4а, Нееееаеиме трефы уереелееея. ственную входящую дугу. Таким образом, лрн построении ннтерваяов каждый из них окажется в интервале с другой вершиной в качестве заголовка, Из этого можно заключить, что следующее обращение к шагу !2) будет на графе, имеющем по крайней мере на одну вершину меньше, так что алгоритм 11.8 должен закончиться. С) Теорема 11.16.
А егор/глен 11.3 празильно змеислягт функцию !Х. До к а з а тел ь с т з о. Достаточно за негнть, что ОЕХ и ТКАХЗ для /„..., // иа шаге !2) те же, что н для /. Кроме того, ясно, ! что 1Х//)= 0 !Х///) и О!/Т //) =- )/ ОПТ, Поскольку каждый интервал /г связывает те же вершины, что н /, функция !Х для вершин в 64, отличных от /, та же, что и в 6'. Таким образом, простая индукция по числу обращений к шагу !2) показывает, что )Х вычисляется правильно. ьз 11.4.4. Обзор содержания главы При построении оптимизирующего компилятора сначала надо решить, какие лучше всего применить оптимизации. Решение должно базироваться на характеристиках того класса программ, которые, как предполагается, должны компилироваться. К сожалению, часто эти характеристики трудно определить, а работ по этому вопросу опубликонано мало.
В этой главе мы рассматривали о!жимизацию кода с довольно общей точки зрения, и разумно было бы спросит!и как связаны друг с другом различные обсуждаемые нами оптимизаг!ии кода. /бетодами равд. 11.2, касающимися арифметических выражений,можно пользоватьсн при построении окончательной объектной программы. Однако некоторые аспехты алгоритмов равд. )1.2 можно внести также и в генерацию промежуточного кода. Иными словами, отдельные части алгоритмов равд. 11,2 мгекно ястроить в выход синтаксического анализатора.
Это приведет к тому, что на линейных участцах будут эффективно использоваться регистры. На фазе компилятора, генерирующей код, у нас есть промежуточная программа, которую можно рассматривать как нечто аналогичное „программам" из равд. 11.3. Наша первая зццача †построи граф управления способом, описанным в этом разделе. Следующий возможный шаг †оптимизирова циклы, как описано в равд. 1!.3, сначала внутренние, а затем и внешние.
Когда это сделано, можно вычислить глобальную информацию относительно потока данных, например, как в алтари~не !1.8 и/или в упр. !1.4.19 и 1!ОК20. Зная зту информацию, можно выполнить „глобальные" оптимизации из равд, !1.3, например размножение констант н исключение общих подвыражений. На этой стадии, однако, надо проявлять осторожность, чтобы не увеличить размера внутренних циклов. Для этого можно по. местить участки во внутренних циклах и избегать в таких участках дополнительных действий, связанных с запоминанием значения выражения, даже если зто выражение используется позднее в участке вне цикла.
Если машина, для которой генернрч. гл ~~ Оптимнзлцяя кодл упулжпкния ется кад, имеет более одного регистра, можно выивнть активные переменные (упр. 11.4.20), чтобы определить, панис переменные должны занимать регистры при выходе из участков. Наконец, линейные участки можно преобразовать методами равд. 1! .1 или анаяогичными методами в зависимости от конкретного промежуточного языка. На этой стадия ссуществлиется также распределение регистров внутри участка, удовлетворяющее упомянутым выше ограничениям на глобальное распределение регистров.
Здесь обычно требуются эвристические методы. кпзлжпвнмн 11А.1. Постройте производную последовательность графов управления, иаображенных иа рнс. 11.32 и 1!.36. Сводимы ли этн графы? 11.4.2, Приведите дополнительные примеры несводимых графов управления. 11.4.3. Донажите утвержденна (!) и (2] теоремы 1!.12. "11.4.4. Покажите, что алгоритм 11,0 можно выполнить так, что ан будет тратить время, пропорциональное числу дуг графа управления Р. 11.4.5. Докажите теорему 11.14.
11.4.В. Закончите доказательство теоремы 1!.!б. !1.4.7. Используйте анализ интервалов (алгоритм 11.7) как основу алгоритма, выисияющего по дкнному оператору, ссылающемуся на переменную А, определена ли она явно тзк, что будет принимать в качестве значения одну и ту же константу при наждом выполнении оператора. 3?каяалае: Необходимо найти, какие нз операторов, Определяющих А, могут быть предыдущими определениями А до очередиога выполнения рассматриваемого оператора. Зто легко выяснить, если предыдущий оператор, определяющий А, встречается в том же участке, что и рассматриваемый оператор. Если нет, нужно вычислить 1/4(Я) для участка, в мотором встречается оператор.
В последнем случае говорят, что А имеет значением константу тогда и только тогда, когда все операторы определения в 1?/(Я), определяющие А, присваивают А одну и ту же константу. 11.4.3. Приведите алгоритм, использующий анализ интервалои как основу для выяснения, бесполезен ли оператор 3, т. е. существует ли оператор, употребляющий значение, определяе. мое 3. 11.4.9. Пусть Я вЂ” участок графа управления с д>гамп в Я, н Я„ а 3 †операт управления в Я, значение которого в Я 444 не употребляется. Если никакой из участков, достижимых вз Я„ нс употребляет значения, определяемого оператором г(, то б можно переместить в Я,.
Используйте анализ интервалов как основу для алгоритма, выявлишщего такие сигуа~!ни. 11.4.10. Вычислите /Ы для каждого участка программы /У 2 'г': ( 2 )Р, И ! < Дг йо(о Х мгИе М ?2 Лг й/ — , '1 йо1о )л Х: ! геша1пдег ((т', /) И 7=-0 йош г ! !+1 до(о й/ 1!А.1!. Вычислите Вл/ для каждого участка программы гевб l И /=! йсбо Х 2: 1!!>10 йо1ОГ Х: ./ (+3 итИе ./ 0'. / (+1 йо(о 2 У: ! ! — 1 И / > !5 йо(о 0/ ИаИ 4!1.4.12. Пусть Т, и ҄— преобразования, следующим образом определенные на графах управления; Тб Если вершина л имеет дугу в себя, удаляем зту дугу.
Т;. Если в вершину л входит единственная дуга, выходя. щая из вершины т, и л не является начальной вершиной, сливаем т и и, заменяи дугу из т в л дугами нэ пл в каждую вершину и', в которую раньше шла дуга на п, Зателг исключаем я. Паиажите, что если Т, и Т, применяются к графу управления Г до тех пар, пока они применимы, то результатом будет предел графа Р. 44З гл. и. оптичизлиля кодл гпелжнения *11.4.!3. Примените преобразования 7, и Т, длн вычисления функции )Н другим способом, не использующим анализа интервалов.
'*11.4.14. Пусть  — граф управлении с начальной вершиной ~,, Покажите, что 0 несводим тогда и только тогда, когда он имеет такие вершины п„н, и п„что существуют пути из п в ла из и, в и, и в л„из л, в и, и из л, в и, [рис. 1!.48), сав- Рнс. П.4З. Структура вмеаго несводимого графа. падавшие толька в их конечных тачках. Все л„ла и, н и, должны быть различны, только л, может совпадать с н,. 11А.15. Покажите, что любая б.схема (см. Равд. 1.3.2) сводима. Указание: Воспользуйтесь упр. 11.4.!4.
11.4.16. Покажите, что любая программа на Фортране, в которой каждый переход на предыдущий оператор вызывается циклоы ОО, имеет сводимый граф управления. **11А.!7. Покажите, что можно зз время 0(п!ойи) выяснить, сводим ли данный граф управления. Указание: Воспользуйтесь упр. 11.4.12. *1!.4.18. Какая существует связь между поннтиями интервала и области с одним входом? *11.4.19. Приведите основанный на понятии интервала алгоритм, выясняющий для каждого выражения (скажем, А+В) и каждого участив Я, г~рн каждом ли выполнении программы достигается оператор, вычисляющий А+В (т.
е. существует ли оператор вида С А+В] и не переопределяющий впоследствии ни А, ни В. Укизаииег Если Я не являетси начальным участком, то наложим )Н(Я)=- ПОИТ(Я?), где ясе Яг — прямые предки участка Я. Пусть ОПТ (я) = (1?( (я) П Х) В у где Х вЂ множест выражений, „убиваемых" в Я (мм „убиваем" А 1- В, переопределяя А или В), а У вЂ множест выражений, вычисляемых участком и иеубиваемых.
Для каждого интервала! различных производных графов и каждого его выхода з вычисляем СтЕлУ (/, В) как множество выражений, вычисляемых и впоследствии не убиваемых ни на какам пути иа входа в интервал 7 в его выход. Вычисляем также Т)(АМ3'(А з) как множества выражений, которые, будучи убитыми, генерируются затем на лю. бом таком пути. Отметим, что ОЕ(л)'(1, з) щТЕАгл)8'(1, з). *11.4.20. Приведите алгоритм, основанный нз анализе интервалов, который для каждой переменной А и каждого участка Я выясняет, есть ли выполнение, которое паоле прохождения через Я будет ссылаться иа переменную А перед ее переопределением. 11.4.21.
Пусть Š— граф с и вершинами и е дугалти. Г!окажите, что г-й производный граф от Е имеет ие более чем е — г дуг. *11.4.22. Приведите пример графа управления с и вершинами и 2л дугами, производная последовательность которого имеет длину и. *1!.4.23. Покажите, что алгоритм 11.7 и алгоритмы нз упр. 11.4 !9 и 1!.4.20 тратят не более 0(л') элементарных векторных шагов на графах управления с л вершинамн и не более чем 2п дугами. Существует другой подход к анализу патона данных, таблич. ный ио своей природе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
