Лекция 03. Анализ потока данных (Лекции (2015))

3. Анализпотока данных13.1 Доступные выражения3.1.1 ОпределениеВыражение e доступно в точке p, если e вычисляется на любомпути от Entry до p причем переменные, входящие в состав eне переопределяются между последним таким вычислением иточкой p.t1 *,4,ik +,i,7B1B2t2 *,4,iB3Пусть точка p – вход в блок B3.На рисунке присваивание не убивает выражение *,4,i.Поэтому t2*,4,i можно заменить на t2 t123.1 Доступные выражения3.1.1 ОпределениеВыражение e доступно в точке p, если e вычисляется на любомпути от Entry до p причем переменные, входящие в состав eне переопределяются между последним таким вычислением иточкой p.t1 *,4,ik +,i,7B1B2t2 *,4,it1 *,4,ii +,i,7B3B1B2t2 *,4,iB3Точка p – вход в блок B3.На втором рисунке присваивание убивает выражение *,4,i, так какменяет значение i.

Так что в этом случае замена t2*,4,i на3t2 t1 будет некорректной.3.1 Доступные выражения3.1.1 ОпределениеВыражение e доступно в точке p, если e вычисляется на любомпути от Entry до p причем переменные, входящие в состав eне переопределяются между последним таким вычислением иточкой p.t1 *,4,ik +,i,7B1B2t2 *,4,it1 *,4,ii +,i,7B3B1B2t2 *,4,it1 *,4,ii +,i,7t1 *,4,iB3B1B2B3t2 *,4,iТочка p – вход в блок B3.Если в блоке перевычислить выражение *,4,i после изменения i,замена t2*,4,i на t2 t1 после снова станет возможной.43.1 Доступные выражения3.1.1 ОпределениеДля каждого базового блока B определиммножество e_killB выражений, убиваемых в блоке B(пример – присваивание i +,i,7 в блоке B2убивает выражение *,4,i),множество e_genB выражений, порождаемых в блоке B(пример – присваивание t1 *,4,i в блоке B2порождает выражение *,4,i).53.1 Доступные выражения3.1.2 Уравнения потока данных Для того, чтобы найти доступные выражения, можно использовать метод,напоминающий метод вычисления достигающих определений.U – множество всех выражений программы.In[В] – множество выражений из U, доступных на входе в В,Out[В] – множество выражений из U, доступных на выходе из В.Граничное условие:Out[Entry] = Система уравнений:Out[ B]  e _ genB  ( In[ B]  e _ killB )In[ B]  Out[ P]PPred ( B )63.1 Доступные выражения3.1.3 Итеративный алгоритм вычисления доступных выражений Алгоритм «Доступные выражения»Вход: граф потока, в котором для каждого блока В вычисленыe_genB и e_killBВыход: множества выражений, доступных на входе (In[В]) и выходе(Out[В]) каждого базового блока В графа потока.

.Метод: выполнить следующую программуOut[Entry] = ;for (каждый базовый блок B, отличный от Entry) Out[B]= U;while (внесены изменения в Out)for (каждый базовый блок B, отличный от Entry) {Out[ B]  e _ genB  ( In[ B]  e _ killB )In[ B] } Out[ P]PPred ( B )73.2 Полурешетки3.2.1 Анализ потока данныхПри анализе потока данных рассматриваются множествапеременных для описания состояния и такие операции какобъединение () и пересечение () множеств.83.2 Полурешетки3.2.1 Анализ потока данныхПри анализе потока данных рассматриваются множествапеременных для описания состояния и такие операции какобъединение () и пересечение () множеств.Свойства операций  и :AA= AAB = BAA(BC) = (AB)C)AA= AAB = BAA (BC) = (AB) C(идемпотентность)(коммутативность)(ассоциативность)Если AB = A, то BAЕсли AB = A, то BAотношение частичногопорядка, связанное соперацией93.2 Полурешетки3.2.1 Анализ потока данныхПри анализе потока данных рассматриваются множествапеременных для описания состояния и такие операции какобъединение () и пересечение () множеств.Свойства операций  и :AA= AAB = BAA(BC) = (AB)C)AA= AAB = BAA (BC) = (AB) C(идемпотентность)(коммутативность)(ассоциативность)Если AB = A, то BAЕсли AB = A, то BAотношение частичногопорядка, связанное соперациейЕсли множество U содержит все элементы, то любое множество A  U иAU=UA=UДля пересечения () роль U играет : любое множество A   иA=A=103.2 Полурешетки3.2.2 Определение полурешеткиПолурешетка – это абстрактная алгебраическая структура, надэлементами которой определена абстрактная операция  (мыбудем называть ее «сбор»), обладающая свойствами операций и .Определение.

Полурешетка представляет собой множество L,на котором определена бинарная операция «сбор» , такая, чтодля всех х, у и z L:xx=x(идемпотентность)xу=уx(коммутативность)x  (y  z) = (x  y)  z(ассоциативность)Полурешетка имеет верхний элемент (или верх) Т  L такой, чтодля всех x  L выполняется Т  x = x113.2 Полурешетки3.2.3 Решеточное отношение частичного порядка Для всех пар x, у  L определим отношение :x  у тогда и только тогда, когда x  у = xОтношение  является отношением частичного порядка.(1) Рефлексивность  следует из идемпотентности :xx  xx=x(2) Антисимметричность  следует из коммутативности :пусть x  у и у  x; тогда x = x  у = у  x = у(3) Транзитивность  следует из ассоциативности :пусть x  у и у  z; тогда по определению x  у = x и у  z = у;(x  z) = ((x  у)  z) = (x  (у  z)) – (x  у) = x,(x  z) = x  x  z.123.2 Полурешетки3.2.4. Диаграммы полурешетокДиаграмма полурешетки L,   представляет собой граф,узлами которого являются элементы L, а ребра направлены от х ку, если у  х.Пример.

Диаграмма полурешетки U, , |U| = 8:элемент множества U представляется битовым 3-вектором.133.3 Структура потока данных3.3.1 Терминология Определение. Структурой потока данных называется четверкаD, F, L,  ,гдеD – направление анализа (Forward или Backward),F – семейство передаточных функций,L – поток данных, - операция сбора. Определение. Семейство передаточных функций F называетсязамкнутым, если:F содержит тождественную функцию I: х L: I(х) = х.F замкнуто относительно композиции: f, g  F  h(x) = g(f(х)) F.143.3 Структура потока данных3.3.2 Замкнутость Утверждение 1. Семейство передаточных функций F, используемоепри анализе достигающих определений (передаточные функции видаgen-kill), является замкнутым.153.3 Структура потока данных3.3.2 Замкнутость Утверждение 1.

Семейство передаточных функций F, используемоепри анализе достигающих определений (передаточные функции видаgen-kill), является замкнутым.1) Замкнутость относительно композиции уже установлена.2) Тождественная функция I(х) = х является функцией вида gen-killс gen = kill = .163.3 Структура потока данных3.3.2 Замкнутость Утверждение 1.

Семейство передаточных функций F, используемоепри анализе достигающих определений (передаточные функции видаgen-kill), является замкнутым.1) Замкнутость относительно композиции уже установлена.2) Тождественная функция I(х) = х является функцией вида gen-killс gen = kill = . Утверждение 2. Семейство передаточных функций, используемоепри анализе живых переменных является замкнутым. Утверждение 3.

Семейство передаточных функций, используемоепри анализе доступных выражений является замкнутым.173.3 Структура потока данных3.3.3 Монотонные структуры Определение 1. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F (х  у)  f(x)  f(у). Определение 2. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F f(x  у)  f(x)  f(у).183.3 Структура потока данных3.3.3 Монотонные структуры Определение 1. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F (х  у)  f(x)  f(у). Определение 2. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F f(x  у)  f(x)  f(у). Утверждение.

Определения 3.3.3.1 и 3.3.3.2 эквивалентны.193.3 Структура потока данных3.3.3 Монотонные структуры Определение 1. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F (х  у)  f(x)  f(у). Определение 2. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F f(x  у)  f(x)  f(у). Утверждение.

Определения 3.2.3.1 и 3.2.3.2 эквивалентны.Из определения 1 следует определение 2:х  у = inf(x, y)  х  у  х и х  у  у (1)f(х  у)  f(х) и f(х  у)  f(y) f(х  у) = inf(f(х),f(y))= f(x)  f(у)203.3 Структура потока данных3.3.3 Монотонные структуры Определение 1. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F (х  у)  f(x)  f(у). Определение 2.