Лекция 02. Построение множеств Input и Output (Лекции (2015))

2. Построение множествInput и Output12.1 Нумерация вершин ГПУ2.1.1 Остовное деревоНеобходимо перенумеровать вершины ГПУ. Для этого построимостовное дерево ГПУ с корнем в вершине Entry и обойдем его«сначала в глубину», используя «обратную нумерацию» (остовноедерево с так пронумерованными вершинами называется «глубиннымостовным деревом» – DFST).Пример 1.AGCDHFBE22.1 Нумерация вершин ГПУ2.1.1 Остовное деревоПример 1.AAGCDDHFGCBEHFBE32.1 Нумерация вершин ГПУ2.1.1 Остовное деревоПример 1.AAGCBEB3HFB6B2DHFGCDB1BEB5B4B7B842.1 Нумерация вершин ГПУ2.1.1 Остовное деревоПример 1.AB1GCDB3HFB6B2BEB4B5B7B852.1 Нумерация вершин ГПУ2.1.1 Остовное деревоПример 2EEntryEntryАB1BB2CB3DB4FExitB5B6Exit62.1 Нумерация вершин ГПУ2.1.2 Алгоритм построения глубинного остовного дерева и нумерациивершин ГПУАлгоритм= N, E с корнем Entry NВход:ГПУ GВыход:глубинное остовное дерево графа G (TDFS(G)) и нумерацияузлов графа G, соответствующая упорядочению в глубину.Метод:все узлы n  N помечаются как nv (not visited)вызывается рекурсивная процедура search(n0)когда процедура search завершится, будут построены:массив номеров узлов dfnмножество Т ребер глубинного остовного дереваTDFS(G)72.1 Нумерация вершин ГПУ2.1.2 Алгоритм построения глубинного остовного дерева и нумерациивершин ГПУРекурсивный алгоритм построения DFSTФункция main() :main() {T = ;for all n  N n.vst = nv;c = |N|;DFST(n0);}82.1 Нумерация вершин ГПУ2.1.2 Алгоритм построения глубинного остовного дерева и нумерациивершин ГПУФункция DFST():void DFST(n) {Отмечаем n как v;for all s  Succ(n)if (s.vst == nv){Т = {ns};DFST(s);}dfn[c] = n;c--;}Замечание.

Для каждой вершины n  N определено множество Succ(n),содержащее все вершины s  N , в которые входят дуги, выходящие из n.92.2 Анализ потока данных2.2.1 Поток данныхСостояние программы – множество значений всех переменныхпрограммы, включая переменные в кадрах стека времени выполнения,находящихся ниже текущей вершины стекаТочки программы (…, pj , pj+1 , pj+2 , …) расположены между ееинструкциями (…, Ij , Ij+1 , …). .

.pjIjpj+1Ij+1pj+2. . .Инструкция программы Ij описывается парой состояний:состоянием в точке программы pj перед инструкцией Ijсостоянием в точке программы pj+1 после инструкции Ij.102.2 Анализ потока данных2.2.1 Поток данныхБазовый блок B описывается паройсостояний:состоянием In[B] в точке входа в B(перед первой инструкцией),состоянием Out[B] в точке выхода из B(после последней инструкции)In[Bj]BjOut[Bj]In[B]BOut[B]С дугой от блока Вj к блоку Вk связаны дветочки программы :точка выхода из блока Вj (ейсоответствует состояние Out[Вj])точка входа в блок Вk (ей соответствуетсостояние In[Вk] )In[Bk]BkOut[Bk]112.2 Анализ потока данных2.2.3 Передаточные функции инструкцийСоотношениеfIJмежду значениями данных до и после инструкции Ijназывается передаточной функцией инструкции Ij.Передаточные функции работают в прямом и обратном направлениях:Out[ I j ]  f I j ( In[ I j ])В задаче прямого обхода:В задаче обратного обхода: In[ I j ] f b (Out[ I j ])IjЕсли Ij и Ij+1 – последовательные инструкции блока B, тоВ задаче прямого обходаВ задаче обратного обходаIn[ I j 1 ]  Out[ I j ]Out[ I j 1 ]  In[ I j ]122.2 Анализ потока данных2.2.3 Передаточные функции базовых блоков Рассмотрим базовый блокB = P, Input, Output,где P = I1, ..., In (в указанном порядке) По определениюIn[B] = In[I1], Out[B] = Out[In]. Передаточная функция fB блока B по определению равна композициипередаточных функций его инструкций I1,..., Inf B ( x)  f I n ( f I n1 (...

f I1 ( x)...))  ( f I1  f I 2  ...  f I n )( x)илиf B  f I1  f I 2  ...  f I n132.2 Анализ потока данных2.2.4 Передаточные функции базовых блоковПри прямом обходе:Соотношение между потоком данных при выходе из блока B и потокомданных при входе в него имеет видOut B  f B InBПри обратном обходе:Соотношение между потоком данных при входе в блок B и потокомданных при выходе из него имеет видInB  f Bb Out B142.3 Достигающие определения2.3.1 ТерминологияОпределением переменной х называется инструкция, котораяприсваивает значение переменной х.Использованием переменной х является инструкция, одним изоперандов которой является переменная х.Каждое новое определение переменной х убивает ее предыдущееопределение.Определение d достигает точки p, если существует путь от точки,непосредственно следующей за d, к точке p, такой, что вдоль этого пути dостается живым.152.3 Достигающие определения2.3.2 ПримерB1i  –, m, 1j  na  u1B2i  +, i, 1j  -, j, 1 aB3a  u2B4i  u3Начало блока B2 достигается определениями:EntryB1B2(i, B1), (j, B1), (a, B1),(j, B2) (других определений j на пути от(j, B2) до начала блока B2 нет)(a, B3)(i, B4)(i, B2) не достигает начала B2, так как его убивает (i, B4)(j, B2) убивает (j, B1), не позволяя ему достичь блоков B3и B4B3B4Exit162.3 Достигающие определения2.3.3 Передаточные функции для достигающих определенийРассмотрим инструкцию Id: u = v + wрасположенную между точками p1 и p2 программы.Пустьx – множество определений, достигающих точки p1genI – множество определений, порождаемых инструкцией IkillI – множество определений, убиваемых инструкцией Iy – множество определений, достигающих точки p2genI = {d}для определения killI нужно иметь все другие определенияu, т.е.

всю процедуру (а иногда и всю программу)172.3 Достигающие определения2.3.3 Передаточные функции для достигающих определенийРассмотрим инструкцию Id: u = v + wрасположенную между точками p1 и p2 программы.По определению передаточной функцииy = fI(x)Инструкция I сначала убивает все предыдущие определенияu , а потом порождает d – новое определение u.Следовательноy = genI (x – killI)Следовательно, передаточная функция fI инструкции I можетбыть записана в виде:f I ( x)  genI  ( x  killI )182.3 Достигающие определения2.3.4. Передаточные функции вида gen-killОпределение.Передаточные функции, определяемые соотношениемf ( x)  gen  ( x  kill)будем называть передаточными функциями вида gen-kill.Утверждение 1.Композиция двух функций вида gen-kill является функцией вида gen-kill.192.3 Достигающие определения2.3.4. Передаточные функции вида gen-killУтверждение 2.Пусть базовый блок B содержит n инструкций, каждая из которых имеетпередаточную функцию f i ( x)  geni  ( x  killi )i = 1, 2, ..., n.

Тогда передаточная функция для базового блока B можетбыть записана какf B ( x)  genB  ( x  killB ),гдеkillB  kill1  kill2  ...  killngenB  genn  ( genn1  killn )  ( genn2  killn1  killn )  ... ( gen1  kill2  kill3  ...  killn )202.3 Достигающие определения2.3.5. Передаточные функции вида gen-killЕсли какая-либо переменная определяется в блоке B несколько раз, то вgenB войдет только ее последнее определение,т.е.только последнее определение переменной будетдействительно вне блока.212.3 Достигающие определения2.3.6. Система уравненийТаким образом, для каждого базового блока Bi можно выписатьуравнениеOut[ Bi ]  f B ( In[ Bi ])или в случае анализа достигающих определенийOut[ Bi ]  genB  ( In[ Bi ]  killB )Если граф потока содержит n базовых блоков,получится n уравнений относительно 2n неизвестныхIn[Bi] и Out[Bi], i = 1, 2, …, n.Еще n уравнений получится с помощью сбора вкладов путей.222.3 Достигающие определения2.3.6 Сбор вкладов путейОпределение достигает точки программы, тогда и только тогда, когдасуществует по крайней мере один путь, вдоль которого эта точка можетбыть достигнута.Следовательно, с одной стороныP  Pred ( B) : Out[ P]  In[ B]откуда Out[ P]  In[ B]а с другой стороныPPred ( B )In[ B] Таким образом Out[ P]PPred ( B )In[ B]  Out[ P]PPred ( B )232.3 Достигающие определения2.3.7 Итеративный алгоритм для вычисления достигающих определенийПолучается система уравненийOut RD [ Bi ]  genBi  ( InRD [ Bi ]  killBi )InRD [ Bi ] (i Out RD [ P]PPred ( Bi )= 1, 2, …, n).(RD - Reaching definitions)– множество переменных, определенных на входе в блок BInRD [B]Out RD [B]В дальнейшем индекс RD будет опускаться– множество переменных, определенных на выходе из блока B242.3 Достигающие определения2.3.7 Итеративный алгоритм для вычисления достигающих определенийПолученную систему уравненийOut[ Bi ]  genBi  ( In[ Bi ]  killBi )In[ Bi ] (i Out[ P]PPred ( Bi )= 1, 2, …, n) будем решать методом итераций.При этом потребуется граничное условие («самый первый Out[B]»)Out[Entry] = В качестве начальных приближений Out[Bi] можно взять пустыемножества: (Out[Bi])0 =.252.3 Достигающие определения2.3.7 Итеративный алгоритм для вычисления достигающих определенийАлгоритм «Достигающие определения» Вход: граф потока, в котором для каждого базового блока Вi вычисленымножества kill B и gen Bii Выход: множества достигающих определений для входа и выходакаждого блока Bi графа потока: In[Вi] и Out[Вi] (i= 1, 2, …, n) Метод: Используется метод итераций с начальным приближением(Out[Bi])0 = .Итерации продолжаются до тех пор, пока множества (In[Bi])r и(Out[Bi])r (r – номер итерации) не перестанут изменяться.262.3 Достигающие определения2.3.7 Итеративный алгоритм для вычисления достигающих определений1) Out[Entry] = ;3) change = true;2) /*установка начального значения множества Out */4) for (каждый базовый блок B, отличный от Entry)Out [B] = ;5)/* основной цикл*/6)while (change) do {7)change = false;8)for (каждый базовый блок B, отличный от Entry) {9)/* вычисление новых значений Out[B] и In[B] */OutNew[ B]  genB  ( In[ B]  killB )10)11)12)13)14)15)16)17) }In[ B]  Out[ P]PPred [ B ]if (OutNew[B]  Out[B]){Out[B] = OutNew[B];change = true;}}272.3 Достигающие определения2.3.8 ПримерB1i  –, m, 1j  na  u1B2i  +, i, 1j  -, j, 1 aB3a  u2B4i  u3EntryB1B2B3B4Exit282.3 Достигающие определения2.3.8 ПримерB1i  –, m, 1j  na  u1B2i  +, i, 1j  -, j, 1 aB3a  u2B4i  u3Вычислим множества gen и kill для каждого базового блокаДля блока B1 genB1  d1 , d 2 , d3  killB1  d 4 , d5 , d 6 , d 7 EntryB1B2B3B4Exit292.3 Достигающие определения2.3.8 ПримерB1i  –, m, 1j  na  u1B2i  +, i, 1j  -, j, 1 aB3a  u2B4i  u3Вычислим множества gen и kill для каждого базового блокаРезультаты вычислений сведены в таблицуB genBkillBB1 {(i,B1), (j,B1), (a,B1)}=(1110000){(i,B2), (j,B2), (a,B3), (i,B4)}= (0001111)B2 {(i,B2), (j,B2)}=(0001100){(i,B1), (j,B1), (i,B4)}= (1100001)B3 {(a,B3)} =(0000010){(a,B1)} =B4 {(i,B4)} =(0000001){(i,B1), (i,B4)} =(1001000)(0010000)EntryB1B2B3B4Exit302.3 Достигающие определения2.3.8 ПримерBgenBEntrykillBB1{(i,B1), (j,B1), (a,B1)}=(1110000){(i,B2), (j,B2), (a,B3), (i,B4)}= (0001111)B2{(i,B2), (j,B2)}=(0001100){(i,B1), (j,B1), (i,B4)}= (1100001)B3{(a,B3)} =(0000010){(a,B1)} =B4{(i,B4)} =(0000001){(i,B1), (i,B4)} =(1001000)(0010000)B1B2B3Начальное приближение(Out[Bi])0 = =(0000000), i = 1,2,3,4.B4Exit312.3 Достигающие определения2.3.8 ПримерBgenBEntrykillBB1B1{(i,B1), (j,B1), (a,B1)}=(1110000){(i,B2), (j,B2), (a,B3), (i,B4)}= (0001111)B2{(i,B2), (j,B2)}=(0001100){(i,B1), (j,B1), (i,B4)}= (1100001)B3{(a,B3)} =(0000010){(a,B1)} =B4{(i,B4)} =(0000001){(i,B1), (i,B4)} =(1001000)(0010000)Начальное приближениеB2B3B4(Out[Bi])0 = =(0000000), i = 1,2,3,4.(In[Bi])000In[B]Out[P]вычисляется по формулеPPred [ B ]ExitНапример, (In[B2])0 = (Out[B1])0(Out[B4])0=    = 322.3 Достигающие определенияEntry2.3.8 ПримерBgenBkillBB1{(i,B1), (j,B1), (a,B1)}=(1110000){(i,B2), (j,B2), (a,B3), (i,B4)}= (0001111)B2{(i,B2), (j,B2)}=(0001100){(i,B1), (j,B1), (i,B4)}= (1100001)B3{(a,B3)} =(0000010){(a,B1)} =B4{(i,B4)} =(0000001){(i,B1), (i,B4)} =(1001000)B1(0010000)B2B3B4Следующее приближение(In[B1])1 = Out[Entry] =  = (0000000)Exit(Out[B1])1 = genB1  (( In( B1 ))1  killB1 )  genB1 (1110000)332.3 Достигающие определения2.3.8 ПримерBgenBEntrykillBB1B1{(i,B1), (j,B1), (a,B1)}=(1110000){(i,B2), (j,B2), (a,B3), (i,B4)}= (0001111)B2{(i,B2), (j,B2)}=(0001100){(i,B1), (j,B1), (i,B4)}= (1100001)B2B3{(a,B3)} =(0000010){(a,B1)} =(0010000)B3B4{(i,B4)} =(0000001){(i,B1), (i,B4)} =(1001000)B4Следующее приближение(In[B1])1 = Out[Entry] =  = (0000000)Exit(Out[B1])1 = genB1  (( In( B1 ))1  killB1 )  genB1 (1110000)(In[B2])1 = (Out[B1])1  (Out[B4])0 = (1110000)(1100001)= (1110000)(Out[B2])1 = genB2  (( In( B2 ))  killB2 ) (0001100)((1110000)-(1100001)== (0011100).1342.3 Достигающие определенияEntry2.3.8 ПримерBgenBkillBB1{(i,B1), (j,B1), (a,B1)}=(1110000){(i,B2), (j,B2), (a,B3), (i,B4)}= (0001111)B2{(i,B2), (j,B2)}=(0001100){(i,B1), (j,B1), (i,B4)}= (1100001)B3{(a,B3)} =(0000010){(a,B1)} =B4{(i,B4)} =(0000001){(i,B1), (i,B4)} =(1001000)B1(0010000)Следующее приближение])1(In[B1= Out[Entry] =  = (0000000)B2B3B4Exit(Out[B1])1 = genB1  (( In[ B1 ])  killB1 )  genB1  (1110000)1(In[B2])1 = (Out[B1])1  (Out[B4])0 = (1110000)(1100001)= (1110000)(Out[B2])1 = genB2  (( In[ B2 ])1  killB2 )  (0001100)((1110000)-(1100001)== (0011100)Дальнейшие вычисления ведутся аналогично.352.3 Достигающие определения2.3.8 ПримерB(Out[B])0(In[B] )1(Out[B] )1(In[B] )2(Out[B] )2(In[B] )3(Out[B] )3B10000000 0000000 1110000 0000000 1110000 0000000 1110000B20000000 1110000 0011100 1110111 0011110 1110111 0011110B30000000 0011100 0001110 0011110 0011110 0011110 0011110B40000000 0011111 0010111 0011110 0010111 0011110 0010111Exit0000000 0010111 0010111 0010111 0010111 0010111 0010111Процесс завершается, так как ((In[B] )3, (Out[B] )3) совпадают с ((In[B] )2, (Out[B] )2)2.3.9 МножестваInput для базовых блоковМножество Input[B] для базового блока B – это множество InRD[B],которое строится при исследовании достигающих определений362.4 Живые переменные2.4.1 МножестваOutput для базовых блоковМножества Output для базовых блоков строятся как результатанализа, позволяющего выявить живые переменные, т.е.переменные, используемые в базовых блоках, в которые управлениепопадает после выхода из исследуемого базового блока.Анализ очень похож на предыдущий, но ГПУ просматривается не сначала, а с конца: от Exit к Entry.2.4.2.