Тема 03(2016)Анализ потока данных (Лекции)

3. Анализпотока данных1Запись на курсДля регистрации необходимо прислать наbmk-compilers@ispras.ruписьмо со следующей информацией:•1. Фамилия, Имя, Отчество.•2. Номер студенческого билета.•3. Свой адрес электронной почты.На указанный Вами e-mail будет зарегистрированаккаунт в системе курса и отправлено письмо с даннымиаккаунта и адресом портала курса.3.1 Доступные выражения3.1.1 ОпределениеВыражение e доступно в точке p, если e вычисляется на любомпути от Entry до p причем переменные, входящие в состав eне переопределяются между последним таким вычислением иточкой p.Пример.

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

Пусть точка p – вход в блок B3.t1 *,4,ik +,i,7B1B2t2 *,4,it1 *,4,ii +,i,7B3На рисунке присваивание неубивает выражение *,4,i.Поэтому t2*,4,i можнозаменить на t2t1B1B2t2 *,4,iB3Присваивание убиваетвыражение *,4,i.Замена t2*,4,i наt2t1 будет некорректной.43.1 Доступные выражения3.1.1 ОпределениеВыражение e доступно в точке p, если e вычисляется на любомпути от Entry до p причем переменные, входящие в состав eне переопределяются между последним таким вычислением иточкой p.Пример. Пусть точка p – вход в блок B3.t1 *,4,ik +,i,7B1B2t2 *,4,it1 *,4,ii +,i,7B3Присваивание не убиваетвыражение *,4,i.Замена t2*,4,i наt2t1 корректна.B1i +,i,7t1 *,4,iB2t2 *,4,iПрисваивание убиваетвыражение *,4,i.Замена t2*,4,i наt2t1 некорректна.t1 *,4,iB3B1B2t2 *,4,iB3Перевычисление в B2выражения *,4,iобеспечивает корректность замены5t2*,4,i на t2t13.1 Доступные выражения3.1.1 ОпределениеДля каждого базового блока B определиммножество e_killB выражений, убиваемых в блоке B(пример – присваивание i  +,i,7 в блоке B2убивает выражение *,4,i),множество e_genB выражений, порождаемых в блоке B(пример – присваивание t1  *,4,i в блоке B2порождает выражение *,4,i).63.1 Доступные выражения3.1.2 Уравнения потока данных Для того, чтобы найти доступные выражения, можно использоватьметод, напоминающий метод вычисления достигающих определений.U – множество всех выражений программы.In[В] – множество выражений из U, доступных на входе в В,Граничное условие:Out[Entry] = Система уравнений:Out[ B]  e _ genB  ( In[ B]  e _ killB )In[ B]  Out[ P]PPred ( B )In[ Bi ]  (e _ genP  ( In[ P]  e _ killP ))PPred ( Bi )73.1 Доступные выражения3.1.3 Итеративный алгоритм вычисления доступных выражений Вход:граф потока, в котором для каждого блока В вычисленымножества e_genB и e_killB Выход:множества выражений, доступных на входе (In[В])каждого базового блока В графа потока.

. Метод:выполнить следующую программуIn[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 )83.2 Полурешетки3.2.1 Анализ потока данныхПри анализе потока данных рассматриваются множествапеременных для описания состояния и такие операции какобъединение () и пересечение () множеств.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отношение частичногопорядка, связанное соперацией103.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=113.2 Полурешетки3.2.2 Определение полурешеткиПолурешетка – это абстрактная алгебраическая структура, надэлементами которой определена абстрактная операция  (мыбудем называть ее «сбор»), обладающая свойствами операций и .Определение.

Полурешетка представляет собой множество L, накотором определена бинарная операция «сбор» , такая, чтодля всех х, у и z L:xx=x(идемпотентность)xу=уx(коммутативность)x  (y  z) = (x  y)  z(ассоциативность)Полурешетка имеет верхний элемент (или верх) Т  L такой, чтодля всех x  L выполняется Т  x = x123.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.133.2 Полурешетки3.2.4 Наибольшая нижняя границаОпределение.

Пусть L,  – частично упорядоченноемножество (в частности, полурешетка).Наибольшей нижней границей inf (х, у) элементов x и у  Lназывается элемент g  L, такой, что g  х; g  у;и если z  L, такой, что z  x и z  у, то z  g.Утверждение. Если x и у  L , где L,  – полурешетка, тоinf (х, у) = x  у.Доказательство. Пусть g = x  у. Тогдаg  x = ((x  y)  x) = (x  (y  x)) = (x  (x  y)) == ((x  x)  y) = (x  y) = g, откуда следует g  х.Точно таким же образом доказывается, что g  y.Пусть z  L, z  x и z  у.

Докажем, что z  g. Имеем:(z  g) = (z  (x  у)) = ((z  x)  у); z  x (z  х) = z (z  g) = (z  у) = z.  (z  g) = z  z  g.143.2 Полурешетки3.2.5. Диаграммы полурешетокДиаграмма полурешетки L,   представляет собой граф,узлами которого являются элементы L, а ребра направленыот х к у, если у  х.Пример. На рисунке – диаграмма полурешетки U, , |U| = 8:элемент множества U представляется битовым 3-вектором.153.2 Полурешетки3.2.5.

Диаграммы полурешетокДиаграмма полурешетки L,   представляет собой граф,узлами которого являются элементы L, а ребра направленыот х к у, если у  х.Пример. На рисунке – диаграмма полурешетки U, , |U| = 8:элемент множества U представляется битовым 3-вектором.Замечание.

Определение элемента внизу диаграммы: для любогоx  L:   x = Этот элемент называется «низом»,так как по определению отношениядля любого x L   x.Полурешетка с операцией  необязательно содержит .163.2 Полурешетки3.2.6 Наименьшая верхняя границаВ частично упорядоченном множестве L,  можно поаналогии с inf (х, у) определить наименьшую верхнюю границуsup (x, y) как такой b  L, что х  b, у  b, и если дляz  L х  z и y  z, то b  z.В полурешетке L,  inf (х, у) существует для любойпары элементов x и у  L , а sup (x, y) нет.В частично упорядоченном множестве L, , в которомдля любых x и у  L существует sup (x, y), можноопределить бинарную операцию  (объединение)x  у = sup (x, y).Множество, в котором определены обе операции – (сбор) и  (объединение), – называется решеткой.173.3 Структура потока данных3.3.1 Определение Определение.

Структурой потока данных называется четверкаD, F, L,  ,гдеD – направление анализа (Forward или Backward),F – семейство передаточных функций,L – поток данных (множество элементов полурешетки), - реализация операции сбора. Примеры.1Структура потока данных для анализа достигающихопределений: Forward, GK, Def, ,где GK – семейство передаточных функций вида gen-kill,Def – множество определений переменных.183.3 Структура потока данных3.3.1 Определение Примеры.2Структура потока данных для анализа живых переменных:Backward, LV, Var, ,где LV – семейство передаточных функций вида,f  x   use  ( x  def )Def – множество определений переменных.3Структура потока данных для анализа доступных выражений:Forward, AE, Expr, ,где AE – семейство передаточных функций видаf  x   e _ gen  ( х  e _ kill) ,Expr – множество выражений программы.193.3 Структура потока данных3.3.2 Замкнутость Определение.

Семейство передаточных функций F называетсязамкнутым, если:F содержит тождественную функцию I: х L: I(х) = х.F замкнуто относительно композиции: f, g  F  h(x) = g(f(х)) F. Утверждение 1. Семейство передаточных функций F, используемоепри анализе достигающих определений (передаточные функции видаgen-kill), является замкнутым.203.3 Структура потока данных3.3.2 Замкнутость Утверждение 1. Семейство передаточных функций F, используемоепри анализе достигающих определений (передаточные функции видаgen-kill), является замкнутым.1) Замкнутость относительно композиции уже установлена.2) Тождественная функция I(х) = х является функцией вида gen-killс gen = kill = .213.3 Структура потока данных3.3.2 Замкнутость Утверждение 1. Семейство передаточных функций F, используемоепри анализе достигающих определений (передаточные функции видаgen-kill), является замкнутым.1) Замкнутость относительно композиции уже установлена.2) Тождественная функция I(х) = х является функцией вида gen-killс gen = kill = . Утверждение 2.

Семейство передаточных функций, используемоепри анализе живых переменных является замкнутым. Утверждение 3. Семейство передаточных функций, используемоепри анализе доступных выражений является замкнутым.223.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(у).233.3 Структура потока данных3.3.3 Монотонные структуры Определение 1. Структура потока данных D, F, L,  называетсямонотонной, если х, у  L, f  F (х  у)  f(x)  f(у). Определение 2.