Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 79
Текст из файла (страница 79)
Разбиение графа управления на непересекающиеся интержалы. Вход. Граф управления Р. Выход. Множество непересекакицнхся интервалов, объединение которых содержит все вершины гйгафе Р. Метод. (1) С каждой вершиной в Р свяжем два параметра: счетчик и дастижюяогть. Счетчик для и вначале равен числу дуг, входящих в и. В ходе выполнения алгоритма счетчик для и равен числу еще ие пройденных дуг, входящих в л. Достижимость для и либо не определена, либо ягвляется некоторой вершиной из Р. Вначале достижимость нс определена для всех вершин, кроме начальной, достнжнмость которой есть ана сама. В конечном итоге постижимостью для и станет псрный найденный заголовок интервала й, такой, чта нз некоторой вершины интервала 1(й) ведет дуга в и. (2) Образуем список вершин, гзазываемый сииском заголомгоа.
Вначале список заголовков содержит только начальную вершину графа Р. (3) Если список заголовков пукт, остановиться. В противном случае пусть и †следующ вер!Пина списка заголовков. Уда. лаем и из списка заголовков, (4) Затем применяем шаги (бр †(7) для построения интервала 1(и). На этих шагах к списку заголовков добавляются прямые потомки вершин из !(и). (5) 1(и) строится как список вершин. Вначале 1(л) содержит только вершину и и она „не памегчена".
(6) Выбираем в 1(и) не!гомеченшую вершину и', помечаем ме и для каждой вершины и", в которую ведет дуга из и', выполняем такие операции: (а) 4'меныиаем на 1 счетчиж для и'. (б) (1) Если достижимость для и" не определена, полагаем ее равной и и делаем с.ледующее. Если счетчяк для и равен теперь О (перед эт им был равен 1), та добавляем вершину и" к'1(л) и переходим к шагу (7); иначе добавляем вершину и' к си!иску заголовков, если ее тэм не было, и переходим к шагу (7). (П) Если достижимасть лля и" равна и, а счетчик вершины и" равен О, добав„аяем вершину и' к 1(и) и уда- ~ьь анализ потока данных лаем ее из списка заголовков, если она там есть.
Переходим к шагу (7). Если ни (1), ни (П) не применимы, в (б) не делается ничего. (7) Если в 1(и) остается непомеченная вершина, возвращаемся к шагу (6). Иначе список 1(и) заполнен; возвращаемся к п~агу (3). С) Определение. Из интервалов графа управления Р можно построить другой граф управления 1(Р), который будем называть производным графом от Р. Производный граф определяется так: (1) 1(Р) имеет по одной вершине для каждого интервала, построенного алгоритмом 11.6. (2) Начальной вершиной для 1(Р) служит интервал, содержащий начальную вершину для Р.
(3) Иа интервала 1 в интервал ! ведет дуга тогда и только тогда, йогда 1~! и из вершины в 1 ведет дуга в заголовок интерната ! Производный граф 1(Р) графа управления Р показывает поток управления между интервалами в Р. Поскольку граф 1(Р) сам является графом управления, можно также построить граф !(1[Р)), производный от 1(Р). Таким образом, если дан граф управления Р„ можно построить последовательность графов управления Р„ Ро ,.., Р„, называемую производной иаследоаоимльиостью от Р, в которой Рㄠ— производный граф от Ри О ( ! ( и, а Р„ †гр, производный от самого себя (т. е, 1(Р„) =. Р„). Граф Р, йазывают !-м производным графом ог Р,. Граф Г„ нааывается пределом графа Р,. Нетрудно показать, что Р„ всегда существует и единствен.
Если Р„состоит из одной вершины, то граф Р называют сводимым. Интересно отметить, что если граф Р, строится по реальной программе, то с большой вероятностью он будет сводимым. В равд. 11.4.3 мы изложим метод расщепления вершин, с помощью которого любой несводимый граф управления можно превратить в сводимый. Пример !!.40. Воспользуемся алгоритмом 11.6 лли построения интервалов графа управления, изображенного на рис. 11.38. Начальной верн!иной служит и,. Вначале список заголовков со. держит толька и,. Для построения 1(и,) включаем и, в 1(и,] как непомеченную вершину.
Помечаем вершину и, ее прямым потомком и,. Для этого уменьшаем счетчик и, с 2 до 1, полагаем достижимость для нее равной и, и добавляем ее к списку заголовков. К этому моменту в Ци,) йе остается непомеченных вершин, так что список 1(иг) (и,) заполнен.
егт ГЛ. ВВ. ОПТИМИЗАЦИЯ КОДА ВВЛ. АНАЛИЗ ПОТОКА ДАННЫХ (л,) О ("т ° ° "а) (и, л„...,п ) (и,) (пе) (пз "е) Рпс !!.88 Граф упре лепна. Список заголовков содержит потомка л, вершины из Цл ), Для вычисления Цпв) включаем и, е Цл,) и рассматриваем вершину п,, счетчик для которой равен 2. Уменьшаем счетчик ва 1, полагаем достнжимость для нее равной л, и добавляем ее к списку заголовков. Находим, такиы образом, что Цп,)= (н,), Списан заголовков содержит теперь потомка и, вершины нз Цл,). Вычисление Цл,) начинаем с занесения и, в Цп,) Рас.
сматриваем вате с ! о О, пол Р м вершийы и, и и, уменьшая счетчики для н х в и ляя их к 1 л д, полагая достижимости для них равными л б , и до ав- ( П как непомеченные вершавы. Помечаем и, умень шая счетчик я для и, с 2 ло 1, полагая достнжимость для л„рав. в. пой п, и добавляя и, к списку заголовков. Помечая и в Цп ), уменьшаем счетчик к для нв с 1 до О, удаляем ее из списка зато. в ловкав и добавляем к Цп,). Чтобы пометить и, в 1(л,), делаем счетчик для л, р О, ем достижимость для нее равной и, и добавляем ее к Цл,). ази Следующей рассьватривается вершина н„поскольку есть дуга из л, в пп Так как достижимость для и, равна л„, вершина и, в данный момент не изменяет.
Цп,) и списка заголовков. Чтобы пометить л„ делаем счетчик для и, равным О, полагаем достнжимасть для нее равной и, н добавляем ее к Цп,). Вершина п, также является потомком вершины НО но так как достижимость для и, равна п„то п, не добавляется ни к Цп,), ни к списку заголовков. Наконец, чтобы пометить л„ не надо производить никаких операций, поскольку пв не имеет потомков. К этому моменту в Цп,) не остается непомеченных вершин, так что Цлв)= (пв Пв Пв Нв щ ввв) е Рпс. 11.39. Песлелеытельпесть грвфсе укрепление. Список заголовков теперь пуст, так что алгоритм заканчивается.
В результате граф управления оказался разбитым на следующие три непересекающихся интервала: Цп,) =(пв) Цл,) =-(и,) Цгтв) (лв лв пв ттв пв лв) Из этих интервалов можно построить первый производный граф рт. Затем к Рт можно применить алгоритм 1!.6 и получить ега иитерпалы. Повторяя весь этот процесс, строим гюследовательность производных графов, изображевную на рис. !1.39. С) Пример 11.41. Рассмотрим граф управления г на рис.
11.40. Интервалы для него таковы: 1(пт) = (твв) Цл,) = (н,) Цп,) = (пв) Од,Ш Чта ЦР)=-й, ТаК Что ГРаФ Г НЕСВОДИМ ь) Гл и Оптимизлш<я кОлл П,< АНАЛИЗ ПОТОКА,<АННЫХ Ркс 11.40. Граф уоразлеияя Р. Теорема 1!.16. Алгоритм 11.6 строит милжестго нелгресекилхиилсл интграолог, обьсдингииг которых совпадает сл всем графом. Лома за тельство. Ясно, чта интервалы не пересекаются Если вершина добавлена к интервалу на шаге (бб<) алгоритма 11.6, то она не будет включена в список заголовков.
Если вершина добавлена к интервалу на шаге (ббй), то она удаляется из списиа заголовков. Аналогично, легко помазать, что объелинение всех построенных списков !(<>) †э множество вершин графа Р. Предполагая, что Р†гр управления, можно считать, чта каждая вершина доствжимз из начальной вершины в Р и потому попадает либо в спвсок заголовиов, либо в некоторый интервал.
Гели вершина ие добавляется к интервалу, она становится заголовкам своего собственного интервала. Наконец, надо показать, что каждый построенный список 1(п) есть интервал. На шаге (6) вершина л" добавляется к 1(п) тогда и только тогда, иогда дастижимость для вее равна п, а счетчик уменьшен до О. Таким образом, каждая дуга, входящая в и", идет из вершины, уже содержащейся в 1(л), и в соответствии с определением интервала вершину и' можно добавить к 1(п). (З Заметим, что на машине с произвольным доступом алгоритм 11.6 может выполняться за время, пропорциональное числу дуг графа управления. Поскольку в графе управления, вершины которого являются участками программы, ни из канай вершины не выходит более двух дуг, это равносильно тому, что алгоритм 11.6 линейно зависит от числа участков программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
