Тема 07(2016)Анализ на основе областей (1161802), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Анализ потока данных на основе областей7.2.1. Схема анализа потока данных на основе областейНа каждом уровне иерархии областей: Область R  R называется выходной подобластью области R,если у R есть выходное ребро к некоторой области,не принадлежащей области R. Для каждой выходной области R  R вычисляется передаточнаяфункцияf R ,Out R, суммирующая влияние всех возможныхпутей в R, ведущих от выхода из R к выходу из R. Например, для области R6и её выходных подобластейR3 и R4 будут вычисленыпередаточные функцииf R6 ,OutR3  f R6 ,OutR4 327.2.

Анализ потока данных на основе областей7.2.1. Схема анализа потока данных на основе областей Первый этап. Построение передаточных функций всехобластей (от листьев к корню дерева управления). Сначала обрабатываются области-листья (отдельные блоки):для каждой области-листа R, состоящей из блока B,f R , InB   I (тождественная функция)f R ,Out B   f B (передаточная функция блока B).337.2. Анализ потока данных на основе областей7.2.1. Схема анализа потока данных на основе областей Первый этап.

Построение передаточных функций всехобластей (от листьев к корню дерева управления). Сначала обрабатываются области-листья (отдельные блоки):для каждой области-листа R, состоящей из блока B,f R , InB   I (тождественная функция)f R ,Out B   f B (передаточная функция блока B). Перемещение вверх по иерархии:R – область-тело: ребра, принадлежащие R, образуютациклический граф на подобластях R, что позволяетпри вычислении передаточных функций использоватьтопологический порядок областей.R – область-цикл: учитывается только влияниеобратных ребер, ведущих к заголовку R.347.2.

Анализ потока данных на основе областей7.2.1. Схема анализа потока данных на основе областей Первый этап. Построение передаточных функций всехобластей (от листьев к корню дерева управления). Сначала обрабатываются области-листья (отдельные блоки). Перемещение вверх по иерархии:R – область-тело: ребра, принадлежащие R, образуютациклический граф на подобластях R, что позволяетпри вычислении передаточных функций использоватьтопологический порядок областей.R – область-цикл: учитывается только влияниеобратных ребер, ведущих к заголовку R. В конце обработки достигается вершина иерархии ивычисляются передаточные функции области Rn,представляющей собой весь граф потока.357.2.

Анализ потока данных на основе областей7.2.1. Схема анализа потока данных на основе областейВторой этап. Анализ иерархии областей (от корня к листьямдерева управления). Области просматриваются в обратном порядке, начиная собласти Rn и далее, опускаясь вниз по иерархии. Для каждойобласти вычисляются значения потока данных на входе. Чтобы получить значения потока данных на входе R  Rnиспользуется передаточная функцияf Rn , In [ R ] Вычисления повторяются, до тех пор, пока не будут достигнутыобласти-листья (базовые блоки).367.2. Анализ потока данных на основе областей7.2.2.

Вычисление передаточных функцийДля анализа потока данных с использованием итеративногоалгоритма в базовых блоках потребовалась замкнутость структурыпотока данных относительно операции композиции функций.Для анализа потока данных на основе областей к передаточнымфункциям применяется уже не только операция композиции, но ещедве операции, позволяющие вычислять передаточные функции дляобластей по передаточным функциям для их подобластей: операция сбора (для входов в компоненты подобластей) и операция замыкания (для циклов).Для применимости указанных операций требуется, чтобы структурапотока данных (множество передаточных функций) была замкнутаотносительно трех операций: композиции, сбора и замыкания.377.2. Анализ потока данных на основе областей7.2.2.

Вычисление передаточных функций 1. Замкнутость относительно композицииЗамкнутость множества F относительно композицииозначает, что композиция двух передаточных функций,принадлежащих множеству F, является передаточной функцией,принадлежащей множеству F.Утверждение. Множество GK передаточных функций видаgen-kill, замкнуто относительно композиции:если f1GK f2GK , а f = f1 ° f2, то и f  GKДоказательство.(f1 ° f2)(x)= gen2  ((gen1  (x – kill1)) – kill2) == gen2  (gen1 – kill2))  (x – (kill1  kill2)) == gen  (x – kill),gen = gen2  (gen1 – kill2)kill = kill1  kill2.387.2. Анализ потока данных на основе областей7.2.2.

Вычисление передаточных функций 2. Операция сбораОперация сбора F на множестве передаточных функций Fопределяется с помощью операции  сбора значений потокаданных следующим образом:(f1 F f2) (x) = f1(x)  f2(x),Множество передаточных функций F замкнуто относительнооперации сбора F, если для любых двух передаточныхфункций f1 Fи f2  F, их сбор f = f1 F f2  F .Замечание.

Множество передаточных функций F, замкнутоеотносительно операции сбора F является полурешеткой соперацией сбора F .397.2. Анализ потока данных на основе областей7.2.2. Вычисление передаточных функций 3. Замкнутость относительно операции сбораУтверждение. Множество GK передаточных функций видаgen-kill, замкнуто относительно операции сбора GK.Доказательство:(f1 GK f2)(x)= f1(x)  f2(x) == gen1  (x – kill1)  gen2  (x – kill2) == (gen1  gen2)  (x – (kill1  kill2)) == gen  (x – kill),gen = gen1  gen2, kill = kill1  kill2.407.2. Анализ потока данных на основе областей7.2.2.

Вычисление передаточных функций 4. Операция замыканияПусть f – передаточная функция тела цикла.Тогда двум итерациям цикла будет соответствовать функцияf 2(x) = f F f,а n итерациям цикла – функцияf n = f n-1F f.Если количество итераций цикла неизвестно, его передаточнаяфункция представляется как замыкание f.Пусть I – тождественная функция. Тогда f 0 = I , f 1 = fЗамыканием передаточной функции f F называетсяфункция f*, определяемая формулойnf *  I F Λfn0417.2. Анализ потока данных на основе областей7.2.2.

Вычисление передаточных функций 5. Замкнутость относительно операции замыканияМножество передаточных функций F замкнуто относительнооперации замыкания.Утверждение. Множество GK передаточных функций видаgen-kill замкнуто относительно операции замыкания:если  f  GK то и f*  GK .Доказательство:= f(f(x)) = gen  (gen  (x – kill) – kill) == (gen  gen)  (x – (kill  kill)) = gen  (x – kill).fn(x) = gen  (x – kill) (по индукции)f 2(x)f *(x) = I  f 1(x)  f 2(x)  … = x  (gen  (x – kill)) == gen  (x  (x – kill)) = gen  x427.2. Анализ потока данных на основе областей7.2.2. Вычисление передаточных функций 5. Замкнутость относительно операции замыканияИтак, если f(x) = (gen  (x – kill)) , то f *(x) = gen  xСледовательно, для  f  GKgen f *  gen fkill f *  Таким образом, циклы не влияют на анализ достигающихопределений437.2.

Анализ потока данных на основе областей7.2.3. Алгоритм анализа на основе областей Вход:структура потока данных, замкнутая относительноопераций композиции, сбора и замыкания,приводимый граф потока управления G. Выход:значения потока данных In[B] для каждого блока B  G. Метод:выполнить следующие действия:1)С помощью алгоритма 7.1.3 определить областии их топологический порядок (снизу-вверх)2)Восходящий просмотр для вычисленияпередаточных функций областей R1, R2, ..., Rn:(Rn – область самого верхнего уровня).2a) R – область-лист, соответствующая блоку В:fR,In[B] = I, fR,Out[B] = fB.447.2.

Анализ потока данных на основе областей7.2.3. Алгоритм анализа на основе областей Метод:выполнить следующие действия:2)Восходящий просмотр для вычисленияпередаточных функций областей R1, R2, ..., Rn:2b) R – область-тело:for each S  R (в топологическом порядке){f R, In S  Λ   f R,Out BB  Pred S/* Если S – заголовок области R, то fR,In[S]= I */for each (выходной блок В  S) fR,Out[B] = fS,Out[B] ° fR,In[S];}457.2. Анализ потока данных на основе областей7.2.3. Алгоритм анализа на основе областей Метод:выполнить следующие действия:2)Восходящий просмотр для вычисленияпередаточных функций областей R1, R2, ..., Rn:2с)R – область-цикл:*f R, In S    Λ f R,Out B   B  Pred S /* Если S – заголовок области R, то fR,In[S] = I */for each (выходной блок В  S) fR,Out[B] = fS,Out[B] ° fR,In[S];467.2.

Анализ потока данных на основе областей7.2.3. Алгоритм анализа на основе областей Метод:выполнить следующие действия:3)Нисходящий просмотр для вычислениязначений In[R] в начале каждой области:In[Rn] = Out[Entry];for each S  R (в нисходящем порядке)In[R] = fR',In[R](In[R']),/* R' – область, непосредственноохватывающая область R */477.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Применим алгоритм 7.2.3 для поиска достигающих определений спомощью анализа на основе областей в рассматриваемой программе.B1B2B3B4B5ijaiaj..- m, 1nu1+ i, 1u2u3.

.d1d2d3d4d5d6487.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Замечание: поиск достигающих определенийобычным способом (с помощью итерационногоалгоритма, который изучался в прошломсеместре) дает следующие результатыIn[ B1 ]  In[ B2 ]  d1 , d 2 , d 3 , d 4 , d 5 , d 6 In[ B3 ]  d 2 , d 3 , d 4 , d 5 , d 6 In[ B4 ]  d 2 , d 3 , d 4 , d 5 , d 6 In[ B5 ]  d 2 , d 3 , d 4 , d 5 , d 6 497.2. Анализ потока данных на основе областей7.2.4.

Пример: применение алгоритма 7.2.3 Применим алгоритм 7.2.3 для поиска достигающихопределений с помощью анализа на основеобластей в рассматриваемой программе. Шаг 1: с помощью алгоритма 7.1.3 определимобласти и пронумеруем их в восходящемтопологическом порядке (слайды 20 – 27):получим области R1, R2, R3, R4, R5, R6, R7, R8507.2. Анализ потока данных на основе областей7.2.4. Пример: применение алгоритма 7.2.3 Применим алгоритм 7.2.3 для поиска достигающихопределений с помощью анализа на основеобластей в рассматриваемой программе. Шаг 1: с помощью алгоритма 7.1.3 определимобласти и пронумеруем их в восходящемтопологическом порядке (слайды 20 – 27):получим области R1, R2, R3, R4, R5, R6, R7, R8ОбластиR1, R2, R3, R4, R5являютсяобластямилистьями исоответствуютбазовым блокамB1, B2, B3, B4, B5517.2.

Характеристики

Список файлов лекций