Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 80
Текст из файла (страница 80)
В качестве упражнения предлагаем показать, что каждый производный граф, построенный повторным прил<енением алгоритма 11.6 из программы, состоящей из и участков, имеет не более 2п дуг. 43О 11.4.3. Днаанз патака даннык с помощью интервалов Покажем, как анализ интервалов может использоваться для определения потока данных внутри сводимого графа.
Про. блема, которую мы будем исслелавать, заключается в том, что для каждого участка Я и для каждой переменной Л сводимого графа управления выясняется, в каких операторах программы могла определяться переменная Л в последний раз перед тем, как управление достигло участка Я. Затем основной алгоритм. анализа интервалов мы распространим на несводииые графы управления. Важно отметить, что отчасти преимущество подхода и анализу пот<>ка данных с помощью интервалов связано с трактовкой множеств как упакованньж веиторов битов. Для вычисления пересечения< объединения и дополнения множеств используются логические операции А%Э, ОК и 1(ОТ на векторах битов, обычно весьма эффективно выполняющиеся на большинстве л<ашин. Построим тзбдицы, да>ощие для каждого участка З программы нсе позиции 1, где определяется данная переменная Л н откуда существует путь в Я, вдоль которого А не переопрслсляется.
Эта информация может пригодиться для выявления возможных аначений А при входе в участок З. Начнем с определения четырех функций, отображюощих участки в множества. Определение. Путем зимне>гний из опгрлтора з, г оператор з, назовем последовательность операторов, начинающуюся с з, и заканчивающуюся в з„которая в данном порядке может выполняться в процессе исполнения программы. 1)усть З вЂ” участок программы Р.
Определим четыре множества, связанные с операторамв определения: (1) !Н(Я) = (й Е Р( существует такой путь вычислений из оператора определения й в первый оасратор в З, что пикамой из операторов иа этом пути, кроме, быть может, первого оператора в З, не переоиределяст переменную, определяеыую оператором д). (2) ООТ(З) = (бб Р( существует такой путь вычислений изб в последний оператор в Я, что никакой нз операторов на нем не переопределяет перемеаную, определяемую д1. (3) ТКАНЗ(З) = (д Е Р ( переменная, определяемая б, не определяется никаким оператором в З). (4) ОЕН(З) = (бЕЯ( переменная, определяемая д, не определяется впоследствии нигде в З).
Говоря неформально, !М(З) содержит определения, которые могут быть активными при входе в З, ООТ(Я) содержит опре- 431 Гл, н Оптимнздпня КОЛА деления, которые могут быть активными при выходе из Я, ТКАХЯ(З) содержит определения, передаваемые через З без определения в Я, ОГХ(З) содержит определения, создаваемые в З, которые остаются активными прн выходе нз З. Легко показать, что ОПТ(З) = (!Х(З) П ТКАХЯ(Я)) () ОЕХ(З) Пример 11.42. Рассмотрим программу 5)е ( — 1 52: У 0 ЯЗе У У ->-1 54 е геад / 55е П ( < 100 йо(о 38 56: шгИе з' 571 ЛаИ 58: ! (ь! 59: йо(о 53 Для удобства все операторы помечены.
Граф управления этой программы изображен на рис. 1151. Каждый участок помечен явно. Определим для З, множества 1Х, ООТ, ТКАХЯ и ОЕХ. Рнс. 11Л1. Граф унрнеленея. Оператор 5! определяет 1, а 51, 52, 53 — путь вычислений, на котором У не определяется (кроме как в 5!).
Поскольку этот путь ведет из 51 в первый оператор участка Зш ясно, 432 ил дндлнз потоке данных что 5! Е1Х(Я,). Аналогично можно показать, что !Х(З,) = (51, Яг, 53, 53> Отметим, что 54 не принадлежит 1Х(Я,), поскольку нет пути вычислений из 54 в 53, не переопредсляющего ! после 54. ОСТ(З,) не содержит 51, поскольку все пути вычислений из 51 в 55 переопределяют У. Предоставляем чнтатетю проверить, что ООТ(З,) =-(53, 54> ТКАХ5(З,) = Ы ОЕХ(Я,) =- (53, 54> Д Остаток этого раздела посвящен разработке алгоритма вычисления 1Х(Я) для всех участков программы. Предположим, что Я„..., Яс — все прямые предки участка З в Р (одним из них может быть сам участок Я). Ясно, что !Х(Я) =- () ООТ(Я,) г=! = 0 [(1Х(З1) ПТКАХЯ(Я,)) ПОЕХ(З,)] с=! Для вычисления 1Х(Я) можно было бы выписать это уравнение для каждого участка программы вместе с уравнением ! Х(Я) = я, где Яе — начальный участок, а затем попытаться разрешить систему уравнений' ).
Однако мы дадим другой метод решения, учитывающий преимущества представления графов управления в виде интервалов. Определим сначала, что мы понимаем под входом и выходом из интервала. Определение. Пусть Р— программа, а Р, — ее граф управле- ния. Пусть Р„ Р„ ..., Р„ †производн последовательность от Р . Каждая вершина в Р,, 1 е1, является интервалом в Рг „ е' н называется интервалом порядка 1. Ыжчдом интервала порядка 1 служит заголовок интервала (отметим, что этот заголовок — участок программы). Вход интер- вала порядка 1 ) ! вЂ Э нход в заголовок этого интервала. Та- ким образом, вход любого интервала — это линейный участок исходной программы Р. Выксдом интервала !(и) порядка 1 служит такой последний оператор участка З в 1(л), что З имеет прямого потомка, ко- торый является либо заголовком интервала л, чнбо участком вне !(я).
Вьиод интервала 1(л) порядка 1 > ! †э последний '1 Кех я е случае уравнений нед регулнремнн енрелсеннннн р зд е 22, ешенне может бмть не едннстееннмм. Здесь нен хогслсс бн иметь оеннень- шсе решение. 433 гл. (г оптнмнз*ггня коле. оператор участка З, содсржагцегося в 1 (н) ') и такого, что в Р, есть дуга, ведущая из З либо в заголовок интервала п, либо в участок вие !(и). Отметим, что каждый интервал имеет олин ахал н пуль нлн более выходов. Пример 11.43, Пусть Р,— граф управления на рнс.
!1.41. С помощью алгоритма 11.3 построньг его рззбиение на интервалы: (г-1(Зт) = (Зг) !т ! РЗт) (Зе Зе Из этих интервалов можно построить первый производный граф Р„показанный па рис. 1!.42. Из Р, можно построить его интервалы (в данном случае толька один): !е !(!г)=(!т 1)=(З( З» З Зе) и получить предельный граф управления, также показанный на рис.
11.42. О гг.е днялнз потоке денных щне рекурсивные определения! 1!4(З), если 1 имеет порядок 1, а З вЂ” заголовок для 1, 1В (1'), если ! имеет порядок 1) 1, а 1' — заголовок для 1, В (2) — (4) ниже з — выхол для 1. (2) ОПТ(1, з) =-ОПТ(З), где участок ЗЕ1 таков, чта з— ега последний оператор (3) (а) ТКАЧЕ(З, з)=ТКАЧЕ(З), если з — последний оператор в З. (б) ТКАБ(3(1, з) — множество таких операторов г(ЕР, что существуют путь без циклов 1„(ю ..., (, состоящий исключительна нз вершин в 1, и такая последовательность выходов з„..., зе для 1,, ..., 1„соответственно, что (1) 1,— заголовок для 1, [П) в Р„участок 3 является прямым предком входа для 1(т, цри !щ.
! < й, (й() с(ЕТКА)43(!(, з() для 1()ежй, ((ч) зл=з. Эти условия проиллюстрированы па рнс, 11,43, Флтгрул 1(;. Г, Рнс. !1.42. Пронвводпвя последоввюлмгость от Ре. Интервалами порядка 1 являются 1, н 1,. Вход для 1,— зто Зт Вхол лля 1,— это Зн Единственный выход для 1,— опера. тор 32.
Епннственный выход для 1,— оператор 59. Интервалом порядка 2 является 1, с входом З,. Интервал 1, не имеет выхолов. П Продолжим теперь функции !р(, ОПТ, ТКАБ(3 н ОЕр( на интервалы. Пусть ЄЄ..., Є— производная последователь. ность от Рю где Р— граф управления для Р. Пусть З вЂ” участок в Р, а 1 — интервал некоторого графа Ро 1) 1.
Введем следую- г) (."троса гонора, ннтсрввл 1 иорядкв ( > ! состоит не янжрввлов по. рядка ( — !. Будем неформельно говорясь, что уяесток ез содержнтся в (, если он прннвллежнт одному не интервалов, вкодяжпт в (. 1вкнм варевом, множество участков, предсгеяляюшнк интервал произвольного порядке, апределеяо твк. «вн етого в слтедовело ожндеть. р(лмсрйглм 1(;, Рнс. (!.43. Тйджз(1 б (4) (а] ОЕБ((З, з) =ОЕ)ч(З), если в — последний оператор в З. (б) ОЕХ(1, з) — множество таних операторов бЕ Р, что существуют путь без циклов (м ..., 1, состоящий 455 гл ц оптимизация кода исключ)тельно иэ верпшп в Г, и такая последователь- ность выходов и„..., зе для Г„..., Га соответственно, по (1) дЕОЕХ(Г„зс), (Л) в Р, участок зг является прямым предком входа для Г „„1() (й, (гЛ) 1ЕРТКАХ5(11, з ) при 2 ~)(/г, (Х) з„=з.
Отметим, что здесь интервал Гг не обязан быть заголов- ком для Г. Таким образом, ТКАХ5(Г, з) — это множество определений, которые можно передать со входа в Г на выход з без переопределения в Г, ОЕХ(Г, з) — это множество определений в Г, кото. рые беэ переопределений могут достичь з. Пример !1.44. Рассмотрим Р, на рис. 11.41 и Р, и Р„на рис. 1)Х2. В Рг интервал Г,— это (З„З„З,), и оц имеет выход 59. Таким образом, !'.ч(Г,).=1Х(З,) =-(51, 52, 53, 58) и ОПТ(Гм 59) = О(1Т(З,) = (53, 58).
ТКАХ5(Г„59) =)3, поскольку ТКАХ5(Я,) = 27. ОЕХ(Го 59) содержит 58, поскольку существует последовательность участков, состоящая только из Ям в которой 58 Е ЕОЕХ(Ям 59). Кроме того, 5386ЕХ(1„59), поскольку суще. ствует последовательность участков З„З, с выходамн 53 и 59. Это означает, что 53 86ЕХ(Ям 53), ߄— прямой предок участка Ям 538 ТКАХ5(З„59). (3 Ладим теперь алгоритм вычисления !Х(З) для всех участков программы Р. Он обрабатывает толька программы со сводимым графом управлеяия. Модификации, необходимые для обработки программ с несводимыми графами, приведены в следующем разделе. Алгоритм 11.7.
Вычисление функции 1Х. Вход. Сводимый граф управления Р„ для программы Р. Выход. !Х(Я) для каждого участка Я Е Р. Метод. (1) Пусть Р„Ро .,., Є— производная последовательность от' Р,. Вычисляем ТКАХ5(З) н ОЕХ(Я) для всех участков З из Р,. (2) Лля 1=1, ..., й послеловательна вычисляем ТКАХ5(1, з) и 6ЕХ(Г, з) для всех интервалов порядка 1' и выходов з для Г. Рекурсивное определение этих фуниций гарантирует, что это можно сделать. пл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
