Analýza toku dat Tomáš Havlát, Mojmír Křetínský Katedra matematické informatiky PřF MU Brno 1 Před výpočtová analýza programu V tomto příspěvku se budeme převážně zabývat metodami předvýpočtové analýzy a příklady aplikací jejích výsledků. Nezůstaneme u některé ze základních, relativně jednoduchých metod, ale budeme prezentovat celou jejich škálu, i když ne zdaleka vyčerpávající. Tento záměr, spolu s rozsahem příspěvku a jeho orientací na programátorskou obec, nás nutí k poněkud méně formálnímu či intuitivnímu vyjadřování i tam, kde se předkládané metody zcela opírají o matematický aparát. Úplný popis jednotlivých metod, včetně důkazu správnosti a analýzy složitosti algoritmů najde čtenář v doporučené literatuře. Předvýpočtová analýza programu spočívá ve vyšetřování některých vlastností programu, aniž by byl program prováděn. Analýze je podrobena některá ze statických forem zápisu programu (proto je někdy používán termín statická analýza programu) a cílem je jejím jednorázovým provedením získat o programu informace globálního charakteru, které často nelze získat ani opakovaným prováděním výpočtu programu pro různá vstupní data. Do předvýpočtové analýzy patří dvě základní oblasti: verifikace programů a analýza toku dat. Mají do jisté míry podobné cíle, liší se však svými prostředky a metodami, kterými analýzu provádějí. Verifikace programů se obvykle prezentuje jako proces nalezení vhodných invariantů umožňujících formálními logickými prostředky dokázat správnost programu ([Flo67], [Man81]), či (z našeho hlediska vhodnější charakterizace) jako proces hledání úplné charakteristiky chování programu popisem vlastností všech možných výpočtů. Tyto cíle jsou vzhledem ke snaze provádět tuto analýzu automaticky příliš ambiciózní a už i z teoretického hlediska jsou předurčeny k selhání (snad s výjimkou těch nej triviálnějších modelů programů). Analýza toku dat (ATD) je orientována pragmatičtěji než verifikace programů a lze ji charakterizovat jako přibližnou, aproximující analýzu programu, kdy za cenu ztráty určité informace či přesnosti, ne však za cenu nepravdivé informace, jsme sto nalézt algoritmy, které požadované řešení poskytují. (Analýzu toku řízeni zde nebudeme považovat za samostatnou oblast, ale za jednu z fází analýzy toku dat.) 1 Motivaci pro tuto analýzu lze rozdělit opět zhruba do dvou oblastí. První z nich je orientována na odvození informace o programu (jeho objektech a způsobech jejich užití), kterou posléze využívá člověk. Typickými příklady z této oblasti jsou např. automatická dokumentace programu, ladění a testování a další, o nichž se zmíníme později. Druhou typickou oblastí (z historického hlediska první) je optimalizace (či spíše "vylepšení") cílového programu generovaného kompilátorem. Pragmatičtější orientace ATD spočívá v tom, že si klade za cíl extrahovat z textu programu jen relativně jednoduché, přesně definované vlastnosti (objektů) programu; úkoly nalézt ty nejjednodušší z nich jsou známy jako tzv. základní problémy ATD. Jejich důležitost vidíme jednak z hlediska metodologického (snadná formulace i hledání řešení, přičemž nejde o triviální zjednodušení), zejména však v tom, že řešení těchto základních problémů je obvykle částí i složitějších problémů ATD. Analýze toku dat se budeme proto věnovat především. 2 Základní pojmy Orientovaný graf G je dvojice (N,E), kde N je konečná množina uzlů, E je konečná množina hran; každá hrana e má počáteční uzel source(e) g Na, koncový uzel target(e) g N; hrana e vede z uzlu source(e) do uzlu target(e). Uzel source(e) je (bezprostředním) předchůdcem uzlu target(e) a uzel target(e) je (bezprostředním) následníkem uzlu source(e). Označme PRED (v), resp. SUCC(v) množinu všech předchůdců, resp. následníků uzlu v. Cesta v grafu G je posloupnost p = e±, e2,..., e& hran takových, že target(ei) = source(ei+i) pro 1 < i < k. Říkáme, že cesta p vede z uzlu source(ei) do uzlu target(ek), je tvořena hranami e±, 62, ■ ■ ■, resp. uzly source{e\), sourcefa), ■ ■ ■, source(ek),target(ek); číslo k nazýváme délkou cesty p. Cykl v grafu je cesta nenulové délky, která vede z uzlu do téhož uzlu (source(e\) = target(ek) ). Cesta je k-jednoduchá (k > 1), jestliže neobsahuje žádný uzel více než k krát. 1-jednoduchá cesta se nazývá jednoduchá. Cesta p je k-semijednoduchá, jestliže p = r, e, q, kde r je jednoduchá cesta, e je hrana a g je ft-jednoduchá cesta. Strom je orientovaný graf, v němž existuje uzel s (kořen) takový, že z něj vede právě jedna cesta do libovolného uzlu. Uzly stromu, které nemají následníka, se nazývají listy. Graf toku řízení(GTŘ) je trojice (N, E, s), kde (N, E) je orientovaný graf, s g N počáteční uzel, existuje právě jeden koncový uzel h g ./V takový, že z něj nevede žádná hrana, a pro libovolný uzel v existuje cesta z počátečního do koncového uzlu obsahující uzel v. Uzly grafu toku řízení programu P reprezentují (elementární) příkazy programu, hrany možnost předání řízení mezi jednotlivými příkazy. Protože mnoho metod analýzy toku dat pracuje s grafem toku řízení programu, patří transformace programu na jeho GTR mezi základní techniky analýzy programu. Algoritmy ATD opakovaně 2 procházejí graf toku řízení a jejich složitost závisí vedle struktury GTŘ i na počtu jeho hran a uzlů. Je tedy snaha do uzlu GTŘ sdružovat více než jeden příkaz (a redukovat tak počet uzlů i hran), ovšem tak, aby analýza toku dat uvnitř uzlu (lokální analýza) se dala snadno provést před analýzou celého programu (globální analýza). Tento požadavek jednoduchosti (obvykle lineární časové složitosti vzhledem k počtu hran) splňují tzv. bloky příkazů. Uvažujme program P s GTŘ, jehož uzly reprezentují elementární příkazy. Blok s jediným vstupním příkazem (vstupem bloku) a s jedním či více výstupními příkazy (výstupy bloku) je část programu P splňující tyto podmínky: 1. do příkazu bloku, který není vstupním příkazem, vede hrana pouze z příkazu bloku, který není výstupní; 2. z příkazu bloku, který není výstupní, nevede hrana do příkazu mimo blok; 3. graf toku řízení odpovídající bloku je strom, který dostaneme z GTŘ programu P vypuštěním všech příkazů mimo blok a všech hran, které vedou z příkazů mimo blok a z výstupních příkazů bloku. Kořenem tohoto stromu je vstupní příkaz bloku a jeho listy jsou právě výstupní příkazy bloku. Má-li blok právě jeden výstupní příkaz, nazývá se základním blokem (je tvořen sekvencí elementárních příkazů). Elementární příkaz je rovněž (základním) blokem a je současně vstupním i výstupním příkazem. Předpokládejme, že uzly GTŘ reprezentují bloky příkazů a hrana vede z uzlu (bloku) i do uzlu (bloku) j, je-li možnost předání řízení z výstupu bloku i na vstup do bloku j. Na obr.l uzly GTŘ reprezentují (elementární) příkazy a), základní bloky b), bloky c). S každým blokem b, přesněji řečeno s každým výstupem w bloku b, jsou spjaty některé elementární informace o toku dat na cestě ze vstupu bloku do výstupu w. Uveďme některé z nich. Jednak proto, abychom hned z počátku podpořili tvrzení, že blok byl volen tak, aby šel snadno analyzovat (čtenáři bude jasné, jak tyto informace získat), jednak proto, že se na ně hodláme později odkazovat. Obr. 1 3 Df(b,w) je množina proměnných, které mají na výstupu w hodnotu přiřazenou jim na cestě blokem b do w. Rf(b,w) je množina proměnných, nad nimiž je první akcí na cestě blokem b do w referencování jejich hodnoty. Undf(b,w) je množina proměnných, které mají na výstupu w nedefinovanou hodnotu jako důsledek akce na cestě blokem b do w. Je-li b základní blok, pak informace nezávisí na výstupu (je právě jeden). Kostra grafu toku řízení G = (N, E, s) je takový podgraf G' = (N, E'), E' C E, že G' je strom s kořenem s. rPostorder je úplné uspořádání na množině uzlů N takové, že vždy, když v kostře GTŘ vede hrana z uzlu u do uzlu v, pak (u, v) GrPostorder. Algoritmy pro nalezení kostry GTŘ a uspořádání rPostorder lze nalézt např. v [Hec77]. Postorder je reverzí uspořádání rPostorder. Uzel x grafu toku řízení dominuje vzhledem k počátku uzlu y, x ^ y, jestliže x leží na každé cestě z počátečního uzlu do uzlu y. Uzel x grafu toku řízení dominuje vzhledem ke konci uzlu y, x ^ y, jestliže x leží na každé cestě z uzlu y do koncového uzlu. Obě dominance jsou ostrá částečná uspořádání na množině uzlů, algoritmy pro jejich nalezení jsou uvedeny např. v [Tar74]. Hrana e je zpětná hrana GTŘ, jestliže target(e) dominuje vzhledem k počátku uzlu source(e). Cyklická souvislost d(G) GTŘ G je rovna maximálnímu počtu zpětných hran na libovolné acyklické cestě v G. Poznamenejme, že metody analýzy toku dat berou do úvahy všechny cesty grafem toku řízení, tedy i ty, které nejsou částí žádného možného výpočtu podle programu (neproveditelné cesty). To je nutno mít vždy na paměti při posuzování výsledků těchto metod. 3 Základní problémy analýzy toku dat Obecně jsou (základní) problémy ATD formulovány následovně. Definuje se vlastnost V objektu (např. proměnné) O v bodě b GTŘ (bod je vstup či výstup bloku). Tuto vlastnost V objekt O nabude v závislosti na tom, co se s ním děje podél (máme na vybranou jednu ze čtyř základních alternativ) 1. alespoň jedné cesty do bodu b (označení: "3,dopředu ") 2. alespoň jedné cesty z bodu ^(označení: ÍL3,zpět") 3. všech cest z počátečního uzlu GTŘ do bodu b (označení: 'V,dopředu ") 4. všech cest z bodu b do koncového uzlu GTŘ (označení: "V,zpět "). Řešením problému ATD je stanovení množiny objektů, které mají v daném bodě vlastnost V-, a to pro všechny uzly GTŘ. Řešení problému ATD zadaného alternativami 1, resp. 2 vypovídá o tom, co se s objektem může stát předtím, resp. potom co výpočet dospěje do, resp. bude 4 pokračovat z daného bodu. Tyto problémy označujeme jako 3-problémy. Naproti tomu řešení problémů zadaných alternativami 3, resp. 4 vypovídají o tom, co se s objektem stane (musí se stát) předtím, resp. potom co výpočet dospěje do, resp. bude pokračovat z daného bodu. Označujeme je jako V-problémy. Při řešení problémů zadaných alternativami 1 nebo 3 se (jak uvidíme později) informace o vlastnostech objektů šíří od předchůdce k následníkovi, tj. ve směru hran GTŘ, tzn. "dopředu". Naproti tomu při řešení problémů zadaných alternativami 2 nebo 4 se informace o vlastnostech objektů šíří proti směru hran GTŘ, tj. od následníka k předchůdci, tzn. "zpět". Rozlišujeme tedy čtyři základní problémy ATD. Poznamenejme, že řešení kteréhokoliv z nich lze použít k řešení zbývajících: 3-problém je ekvivalentní s —>V—i-problémem, a problémy "dopředu" lze převádět na zpětné prostřednictvím inverze (obrácení orientace hran) GTŘ. Metody řešení ukažme na následujícím příkladu. Máme zjistit, zda v průběhu dalšího výpočtu existuje (potenciální) možnost použití momentální hodnoty proměnné. Proměnnou nazveme živou v bodě p GTŘ, právě když existuje cesta z p do nějakého uzlu w, podél níž není proměnná definována a první akcí nad touto proměnnou ve w je použití její hodnoty. Problém nalezení živých proměnných se nazývá LIVE problém a je typu "3, zpět ". Abychom mohli pro libovolnou proměnnou určit zda a kde je živá, musíme vycházet z informací o akcích, které jsou nad touto proměnnou prováděny v jednotlivých uzlech (pro jednoduchost v základních blocích) GTŘ. Bude nás zajímat 1. množina všech proměnných, nad nimiž je první akcí v bloku u redefinování jejich hodnoty; označme je (pro daný uzel u) KILL{u) a jejich doplňky NOTKILL{u). 2. množina Rf(u) všech proměnných, nad nimiž je první akcí v bloku u referen-cování jejich hodnoty; označme je GEN{u). Reprezentuje-li blok u např. zdrojový text x := x + 1; y := x, pak GEN{u) = {x} a KILL{u) = {y}. Je evidentní, že proměnná x je (lokálně) živá na vstupu bloku u. Libovolný problém analýzy toku dat, a tedy i hledání živých proměnných lze chápat jako problém šíření informace: lokální informaci (GEN) danou uzlem šíříme (zde proti orientaci hran) po grafu toku řízení tak, že zpráva o živosti proměnné je předána dál pokud v momentálně zpracovávaném uzlu není živost proměnné "zabita" (KILĽ), resp. zpráva je obohacena o živost nějaké další proměnné, patří-li tato do GEN uzlu. Z lokální informace se tak stává hledaná globální vlastnost. Než přejdeme k prezentaci algoritmů pro živé proměnné, uveďme představitele zbývajících typů základních problémů ATD. Problémem typu "3,dopředu" je například dosažitelnost definic (REACHESproblém): definice d proměnné v v uzlu u dosahuje vstupu do uzlu m, jesliže oř je v uzlu u a existuje cesta z m do m na níž není v redefinována. Problém dostupných výrazů (AVAIL problém) je typu "V, dopředu": výraz v je dostupný v bodě p, právě když na všech cestách z počátečního uzlu do p byla hodnota 5 výrazu v spočtena a po tomto výpočtu již nebyla hodnota žádného z operandů výrazu v redefinována. Problém využitelných výrazů (Very Busy Ľxpression problém) je typu V, "zpětný ": výraz v je využitelný v bodě p, právě když na všech cestách z p do koncového uzlu je v referencován, aniž by byla na některé z těchto cest redeŕmována hodnota některé jeho složky (operandu). 3.1 Řešení problému živých proměnných (LIVE problém) Označme hledanou množinu proměnných, které jsou živé na vstupu, resp. výstupu uzlu u jako LVTOP(u), resp. LVBOT(u). K dispozici máme lokální informace GEN (u) o tom, které proměnné se stávají v uzlu živými a KILL(u), která obsahuje ty proměnné, jež jsou v uzlu "zabity" (definicí jejich hodnoty). Z obr.2 je patrno, že proměnná je živá za tohoto předpokladu: 1. je živá na vstupu uzlu, je-li živá na výstupu tohoto uzlu a není tímto uzlem zabita, nebo její živost je tímto uzlem generována (obr.2a); 2. je živá na výstupu uzlu, je-li živá na vstupu některého z následníků tohoto uzlu (obr.2b), tj.: (LI) LVTOP(u) = (LVBOT(u)nNOTKILL(u))UGEN(u) VueiV (L2) LVBOT{u)= (J LVTOP(v) VueiV vesucc(u) je - li SUCC{u) = 0, pak LVBOT{u) = 0 či stručněji (dosadíme-li (L2) do (LI)) (LIVE) LVTOP{u) = ( (J LVTOP(v) n NOTKILL(u)) U GEN (u) vesucc(u) a dále (L3) řešením LIVE problému je nejmenší řešení (vzhledem k inklusi) splňující (LIVE), resp. (LI) a (L2). x : __LVBOT(x) --LVTOP(y) a) b) Obr. 2 Požadavek (L3) si zasluhuje několik poznámek. Označme LIVE(u,p) množinu těch živých proměnných v uzlu u, jejichž hodnoty budou použity na cestě p vychá- 6 zející z uzlu u. Množinu všech cest z uzlu u označme PATH(u) - tato je obecně nekonečná. LIVE problém lze pak psát ve tvaru "nekonečného sjednocení" takto: (*) LIVE{u) = (J LIVE {u, p) , p£PATH(u) který jsme reprezentovali (konečným způsobem) jako systém (LIVE) vzájemně rekurzívních rovnic majících obecně více řešení (viz následující příklad). Sjednocení nekonečného systému množin (*) je ovšem definováno jako nejmenší množina (LIVE (u)) obsahující všechny sčítance, což je (na intuitivní úrovni) důvod pro podmínku (L3). Správnost řešení (LIVE) nemůžeme ověřovat vůči (*) kontrolou jednotlivých sčítanců - je jich nekonečně mnoho. Příklad: 1 read(x) x = 0 v := x stop GEN(1) = 0, NOTKILL(l) = {v}, SUCC(l) = {1,2} SUCC(2) = 0 => LVBOT(2) = 0 GEN(2) = {x}, NOTKILL(2) = {x} => LVTOP(2) = {x} a) LVTOP(l) = {v}, LVBOT(l) = LVTOP(l) U LVTOP(2) = {v,x} b) LVTOP (1) = 0, LVBOT(l) = LVTOP(l) U LVTOP {2) = {x} Jak a) tak i b) splňují rovnice (LIVE), řešení LIVE problému je ad b). Zbývá objasnit, jak systém (LIVE) řešit. Jedna z možných ideí již byla naznačena: na každý uzel (resp. rovnici pro tento uzel) můžeme nahlížet jako na proces, který čeká až mu každý jeho následník v zašle zprávu LVTOP(v). Poté proces zprávu zpracuje tak, že vyhodnotí rovnici (jako přiřazení) a výsledek LVTOP(u) posílá všem svým předchůdcům. Po přijetí nových vstupních zpráv a výpočtu nové hodnoty LVTOP proces zkontroluje, zda nově vypočítaná LVTOP zpráva není totožná s posledně zasílanou zprávou. Jestliže ano, pak zprávu, která nepřináší žádnou novou informaci, dále nešíří a převede se do stavu "ukončení schopný". V opačném případě zprávu s novým (bohatším) informačním obsahem posílá dál. Výpočet končí, jsou-li všechny procesy ve stavu "ukončení schopný", což, jak ukážeme později při přesnější (,sekvenční) realizaci myšlenky, musí po jistém čase vskutku platit. Poznamenejme, že (pomineme-li otázku časové efektivity), nezáleží na pořadí v jakém jsou procesy (např. na monoprocesorovém systému) aktivovány. Jediné co musí být splněno je spravedlivé provádění, tj. provedení žádného z procesů nesmí být do nekonečna odkládáno. Korektnost tohoto principu (formálně ji dokážeme později) souvisí mj. s inicializací informace šířené procesy. K jejímu splnění (včetně požadavku minimality řešení) stačí, abychom na začátku udělali "nejhorší" předpoklad, a to, že žádná proměnná není živá na vstupu žádného uzlu: LVTOP (u) = 0. Označíme-li totiž jako 7 PATHl{u) cesty z uzlu u délky nejvýše i a LIVEi{u)= |J LIVE(u,p) , p£PATHi(u) pak můžeme zapsat i nerekurzívní specifikací pro LIVE: LIVE°(u) = 0, Vi > 0 : LIVE\u) = |J ZJVEi_1(i;) D NOTKILL(u) U GW(u) uest7CC(u) Zřejmě každé částečné řešení LIVE1 bude obsaženo v konečném řešení LIVE, tj. pro i > 0 je LIVE1 C ZJVE, a tedy i Uť>o Wtf' C Z/VE. Na druhé straně (platí pro LIVE, nikoliv však obecně), je-li nějaká proměnná x v LIVE, pak musí existovat i > 0 takové, že x je v LIVE\ tj. LIVE C |Ji>o ^VEť a tudíž L7F£; = U>o ^/VEť. Z toho plyne, že := GEN(u) je rovněž korektní inicializací. Uvedená idea řešení je jednoduchá i v sekvenčním podání: po inicializaci LVTOP = 0 (resp. GEN{u) ) vyhodnocujeme rovnice pro jednotlivé uzly v libovolném pořadí a z hlediska korektnosti a ukončení se nabízí tyto možnosti: 1. Udržovat seznam uzlů, kterým byla zaslána nová (různá od předešlé) informace. Vyhodnocování končí, jakmile je seznam prázdný (už není co nového šířit - informace se stabilizovala). 2. Uzly libovolným způsobem uspořádat a vyhodnocovat jim odpovídající rovnice cyklicky v daném pořadí (systémem round-robin). Jestliže po průchodu přes všechny uzly nezaznamenáme ani u jednoho změnu nově vypočtené informace, pak se systém stabilizoval a další průchody by už nic nového nepřinesly. (Jelikož u LIVE problému se informace šíří zpětně od uzlu k jeho předchůdcům, je vhodným - z hlediska efektivity - uspořádáním uzlů Postorder). Algoritmus - Iterativní LIVE Vstup: pro všechny uzly u GEN(u), NOTKILL(u) Výstup: pro všechny uzly u LVTOP(u) begin {uzly z N jsou očíslovány l,2,...,n v pořadí Postorder} {inicializace:} for i:=l to n do LVTOP(i) := 0 od; {iterace:} change := true; while change do change := falše; for i:=l to n do NEWLVTOP := U {LVTOP(k); keSUCC(i)} D NOTKILL(i) U GEN(i); if NEWLVTOP ž LVTOP(i) then change:=true; LVTOP(i) := NEWLVTOP ň; od; od; end; 8 Ukončení a korektnost algoritmu "Iterativní LI VE" je intuitivně zřejmá; formálně bude ukázána v čl.6.3 (algoritmus je instancí obecného modelu). Jeho složitost je 0(d(G). | E |) operací U a Pl (viz [Hec77]); while se provede nejvýše (d + 2)krát, šíří-li se GEN po acyklické cestě s d zpětnými hranami; for představuje | E \ — \ N \ operací U a n pro NOTKILL a GEN). 4 Eliminační metody Iterativní algoritmy řešení problémů ATD jsou výhodné z hlediska porozumění principu, z hlediska snadné implementace a v neposlední řadě proto, že se dají aplikovat na libovolné GTR bez omezení jejich struktury. Avšak při šíření informace nevyužívají téměř žádná fakta o struktuře GTŘ. Na základě těsné analogie s řešením systému lineárních rovnic, který lze řešit jak iterativně, tak eliminací, vzniká otázka, zda podobný přístup nelze uplatnit i zde (viz [Tar81]). Navíc lze očekávat, že tyto (nerekurzivní) eliminační metody mohou poskytnout řešení i u těch složitějších problému ATD, kdy iterace sice konverguje, ale ne dostatečně rychle (přesné řešení nenalezneme v konečném čase). Výhodou eliminačních algoritmů je jejich obvykle lepší časová složitost (až lineární), někdy poskytují přesnější řešení. Jsou však podstatně komplikovanější (i k implementaci). Společnou ideou eliminačních algoritmů je využít struktury grafu toku řízení tak, aby byl sumarizován efekt šíření informace pro nějakou (obecně nekonečnou) množinu cest mezi dvěma uzly, např. pro nějaký vhodný model (jednoduchého) cyklu. Pak lokální informaci GEN, KILL, která udává lokální vlastnost (např. živost) na vstupech jednotlivých bloků postupně globalizujeme: začneme u nej vnitřnějšího cyklu a skládáním efektů lokálních GEN a KILL najdeme výsledné GEN a KILL pro vstupní bod celého cyklu. Množinu uzlů tvořících tento cyklus pak nahradíme jediným uzlem (GEN a KILL pro jeho vstup jsme již našli) a celá situace se opakuje až dospějeme k triviálnímu grafu (tvořenému jediným uzlem) a jeho GEN a KILL. Pro triviální graf nyní platí LI VE = GEN. Po tomto průchodu 1 (přenos informace ve směru lokální —>• globální) provádíme průchod 2 (globální —>• lokální), při kterém na základě sumarizované informace v GEN a KILL počítáme postupně detailnější informaci LIVE: expandujeme triviální graf v obráceném pořadí až dospějeme k původnímu grafu toku řízení a informaci LIVE pro každý jeho uzel. Nej jednodušším modelem cyklu je tzv. silně souvislý (pod)graf, kdy požadujeme, aby z každého uzlu vedla cesta do libovolného uzlu. Tento model je však dosti obecný a nestrukturovaný, což se projeví jak na komplikovanosti algoritmu, tak hlavně na jeho časové složitosti. Přesto takové algoritmy existují [Ear72]. Výhodnější se ukazuje omezit se na programy, kde každý cyklus má právě jeden vstup (duplikací kódu ve vnitřní reprezentaci programu lze splnění této podmínky dosáhnout i pro programy, které obsahují cykly s více vstupy - viz obr.3). Uveďme dvě metody založené na modelech cyklu s jedním vstupem. První z nich (intervalová analýza) je relativně nejnázornější ilustrací eliminace, druhá (algoritmus Grahamové 9 Obr. 3 3 a Wegmana) si zaslouží pozornost díky své časové složitosti. 4.1 Intervalová analýza Modelem cyklu je tzv. interval, což je množina uzlů / definovaná takto: 1. existuje právě jeden uzel h g I (hlava intervalu I), který leží na každé cestě z uzlu nepatřícího do / do uzlu v / (jediný vstup do cyklu); 2. I je souvislý; 3. I — {h} neobsahuje cykl (tj. všechny cykly v / musí obsahovat h). Uveďme algoritmus, který pro daný graf toku řízení G a daný uzel h konstruuje maximální interval s hlavou h. Zde i dále pro množinu uzlů M označíme SUCC(M) = (JxeM SUCC(x). Algoritmus MI - konstrukce maximálního intervalu Vstup: graf toku řízení G; jeho uzel h Výstup: MAXI(h) - maximální interval s hlavou h begin I:={h}; while 3 x g SUCC(ľ)-{l} takový, že PRED(x) c I do I:=I U {x} od; MAXI(h):=I end; Stojí za povšimnutí pořadí, v jakém jsou uzly do intervalu / přidávány. Toto tzv. intervalové pořadí je linearizací částečného uspořádání daného orientací hran v intervalu (bez hran vedoucích do hlavy h). Pro průchod 1 analýzy toku dat bude důležité, že při zpracování uzlů v intervalovém pořadí analyzujeme daný uzel x ^ h až když jsou analyzováni všichni jeho předchůdci. Analogicky v průchodu 2 při zpracování uzlů v obráceném intervalovém pořadí je uzel analyzován až po analýze všech svých následníků. Budeme se snažit o nalezení úplného uspořádání s uvedenými vlastnostmi pro všechny uzly GTŘ. Pomůže nám v tom následující algoritmus, který GTŘ rozdělí na vzájemně disjunktní intervaly (uvnitř každého je intervalové pořadí známo). 10 Algoritmus IP - rozdělení GTŘ na intervaly Vstup: graf toku řízení G Výstup: INTS(G) - množina disjunktních intervalů tvořících rozklad uzlů grafu G Pomocné proměnné a procedury: H množina potenciálních hlav intervalů DONE množina hlav nalezených intervalů MI(h) procedura, která nalezne maximální interval MAXI(h) s hlavou h, (viz algoritmus MI) beginH := {počáteční uzel GTŘ G}; DONE := 0; INTS(G) := 0; while H ^ 0 do nechť x je libovolný uzel z H; H := H - {x}; DONE := DONE U{x}; call MI(x); INTS(G) := INTS(S) U MAXI(I); {přidej nové potenciální hlavy:} H := H U (SUCC(MAXI(x)) - MAXI(x) -DONE) od end; Příklad: Pro GTŘ na obr.4 je výstupem z algoritmu IP tento rozklad na intervaly: 1(1) = {1}, 1(2) = {2, 3,4}, 1(5) = {5, 6, 7}. Uvnitř každého intervalu je dáno intervalové pořadí uzlů. K dosažení úplného uspořádání celé množiny uzlů GTŘ musíme ještě nalézt (intervalové) uspořádání mezi jednotlivými intervaly. Vhodnou metodou je uvažovat graf, jehož uzly jsou zkonstruované intervaly a celý postup opakovat. Pro GTŘ G definujeme odvozený GTŘ I(G) takto: 1. Uzly grafu I(G) jsou intervaly grafu G, tj. INTS(G). 2. Počátečním uzlem grafu I(G) je MAXI(s), kde s je počáteční uzel grafu G. 3. V grafu I(G) vede hrana z uzlu J do uzlu K, právě když v G vede hrana z nějakého uzlu intervalu J do hlavy intervalu K. ({W}) =>• ({{!}, {2,3,4}, {5,6žť}}) ^({5,6,7}) Obr. 5 11 Posloupnost grafů Gq, G\,..., Gm nazveme odvozenou posloupnostípro GTŘ G, jestliže G = Go, Gi+1 = I(G) (0 < i < m - 1), Gm.x ± Gm a I(Gm) = Gm. Graf G i nazveme odvozeným grafem řádu i, Gm limitním grafem a číslo m + 1 intervalovým řádem grafu G. GTŘ G se nazývá reducibilní, právě když jeho limitní graf je triviální. V opačném případě hovoříme o nereducibilním GTŘ. Obr.5 navazuje na obr.4 a ilustruje zbytek odvozené posloupnosti. Intervalové pořadí uzlů reducibilního GTŘ G získáme opakovaným odvozováním intervalového pořadí grafu Gj ze známého intervalového pořadí grafu Gj+i (intervalové pořadí triviálního grafu Gm je předem dáno): interval J v pořadí grafu G i nahradíme jeho uzly v tom pořadí, jak byly do J přidávány. Při ATD založené na intervalové analýze je nutno pracovat s lokální informací KILL, která je sdružena nikoli s uzly, ale s hranami (intervaly mají více než jeden výstup). Tedy NOTKILL(x,y) je množina všech proměnných takových, pro něž existuje cesta ze vstupu uzlu x do vstupu uzlu y neobsahující redefinice těchto proměnných. Rovnice pro LIVE mají pak tento tvar: (LIVE) LIVE(x)= (J (LIVE (y) íl NOTKILL(x,y)) U GEN (x) yeSUCC(x) Intervalová analýza - průchod 1 (lokální —>• globální): Jádrem tohoto průchodu je algoritmus II, který určí pro interval / jeho GEN(I) a NOTKILL(I,J) na základě GEN a NOTKILL uzlů tohoto intervalu. Průchod 1 spočívá ve volání procedury II pro každý interval grafu G0 (v jejich intervalovém pořadí), posléze se tento proces opsakuje pro G\ atd. až je aplikován na Gm_i, který je tímto procesem redukován na limitní graf odvozené posloupnosti Gm = ({x*},0,x*) a určena jeho GEN(x*). Intervalová analýza - průchod 2 (globální —>• lokální): V tomto průchodu počítáme LIVE pro stále menší oblasti původního grafu. Postupujeme od Gm, pro který je evidentně korektní přiřazení LIVE(x*) := GEN(x*), přes Gm_i,Gi až při G0 dostáváme LIVE pro každý uzel GTŘ G0. Celá druhá fáze spočívá v opakovaném volání procedury 12, která, na základě LIVE pro interval I(h) a množin LIVE pro jeho následníky J, určí (s pomocí GEN a NOTKILL) množiny LIVE pro jednotlivé uzly tohoto intervalu. Poznamenejme, že GEN a NOTKILL byly určeny již v průchodu 1 a předpoklad o existenci (tj. již vypočtených) LIVE(I) a LIVE(J) je splněn díky pořadí, v němž je 12 postupně aktivována, tj. od Gm po Vlastní 12 je založena na tom, že uzly z I(h) — {h} jsou zpracovávány v reverzi intervalového pořadí: při aktivaci pro LIVE(x) máme již vypočteny LIVE(y) pro y G SUCC(x) a můžeme tedy použít výše uvedenou rovnici (LIVE); nastává totiž právě jeden z těchto případů: 1. y G I — {h}, pak LIVE (y) již bylo určeno díky zpracování uzlů v reverzi intervalového pořadí; 12 Algoritmus II Vstup: (1) Interval I s hlavou h (2) Vx G / : GEN (x), Vx G /.V?/ G SUCC(x) : NOTKILL(x, y) Výstup: GEN(I), V J G SUCC(J) : NOTKILL(I,J) Pomocné proměnné: Vx G I: množina PATH(x) těch proměnných, pro které existuje cesta ze vstupu hlavy intervalu do vstupu uzlu x neobsahující redefinice těchto proměnných. begin {inicializace : } GEN(Í):= GEN(h); PATH(h):=Var; {Var je množina všech proměnných v daném programu} {globalizace GEN.} for V xG I-{h} v intervalovém pořadí do PATH(x) := (J {PATH(y) n NOTKILL(y,x); y G PRED(x) }; GEN(ľ) := GEN(ľ) U (GEN(x) U PATH(x) ) od; {dále hJ značí hlavu intervalu J} {globalizace NOTKILL:} for VJ taková, že hJ G SUCC(Í) do NOTKILL(I,J) := U {PATH(y) n NOTKILL(j,hJ); jePRED(hJ)f]I} od end; 2. y je hlavou Jav tom případě LIVE(y) = LIVE(I), která byla určena již v grafu o jeden řád vyšším; 3. y je hlavou nějakého intervalu J, který je následníkem intervalu Jav tom případě použijeme, analogicky jako v bodu 2, množinu LIVE(J). Při úvahách o složitosti musíme nejprve uvážit složitost nalezení odvozené posloupnosti grafů (analýzy toku řízení). Algoritmus rozkladu GTŘ G = (N, E, s) na intervaly pracuje zřejmě v čase úměrném počtu hran vstupního GTŘ, tj. 0(| E |) a je-li m intervalový řád G (předpokládáme navíc | E |^> m ), pak dostáváme celkem 0(| E j .m). Poznamenejme, že existují anomální grafy s m = 0(\ E |2), v praxi však zřídka bývá m > 6 a v průměru je 2,75 [Knu71]. Uvažujme složitost vlastní analýzy toku dat. Značí-li n počet uzlů a e počet hran v odvozené posloupnosti, pak tato analýza má složitost O (e). Existují sice grafy s e = 0(| E |2), avšak pro reálné programy je typické O (e) = 0(\ E |). Z teoretického hlediska je tedy nejhorší případ intervalové analýzy lepší než nej-horší případ iterativních metod, avšak na reálných programech je jejich složitost přibližně stejná, přičemž iterativní metody jsou snáze implementovatelné. 4.2 Komprese cest - algoritmus Grahamové a Wegmana 13 Algoritmus 12 Vstup: (1) Interval I s hlavou h (2) Vx g / : GEN (x), Vx g IXy g SUCC(x) : NOTKILL(x, y) (3) LIVE(I), V J g SUCC(I) : LIVE(J) Výstup: Vx g / : LIVE(x) begin ZJVE(h) := ZJVE(I); {viz bod 2.} {dále hJ značí hlavu intervalu J} for VJ g SUCC(I) do LIVE(hJ) := LIVE(J) od; {viz bod 3.} for Vx 6 / - {/í} v reverzi intervalového pořadí do LIVE(x) := U{£JVE(í/) n NOTKILL(x,y);y g SUCC(x)} U GW(x) od; {viz bod 1.} end; Eliminační metody nejsou triviální, ale mohou být co do složitosti velmi efektivní (až téměř lineární), což ilustruje metoda Grahamové a Wegmana. Algoritmy založené na kompresi cest pracují opět jen nad reducibilními grafy a vyznačují se tím, že definují vždy několik relativně jednoduchých transformací, jež zachovávají reducibilitu grafu a řešení pro původní graf je z transformovaného (odvozeného) grafu snadno získatelné. Postupnou aplikací základních transformací dostaneme z původního, reducibilního GTŘ, limitní triviální graf. Tyto algoritmy, tak jako všechny eliminační metody, pracují opět dvouprůchodově, přičemž nezbytnou analýzu toku řízení (tj. nalezení posloupnosti transformací redukující daný graf na limitní) lze provádět souběžně s prvním průchodem analýzy toku dat. Z metodologických důvodů však tyto dva úkoly od sebe oddělíme. Typickým a rychlým reprezentantem těchto metod je algoritmus [Gra76], který používá tyto transformace TI až T3 (viz též obr. 6): TI odstraňuje hranu tvořící cyklus délky 1; T2 zkracuje cestu délky 2 obsahující uzly x, y, z na cestu délky 1, přičemž nastávají tyto dvě možnosti: (a) T2a eliminuje prostřední uzel y, jestliže jeho jediným následníkem je třetí uzel, to jest z; Obr. 6 14 (b) T2b zkracuje cesty bez eliminace uzlů v ostatních případech; T3 eliminuje následníka y uzlu s, má-li y za následníka nejvýše sebe sama. Nechť G = (N, E, s) je GTŘ. Pak transformace TI až T3 definujeme takto: Transformace TI: jestliže pro nejaký x G N existuje hrana e = (x, x) G E a existuje právě jeden u G N — {x} takový, že (u, x) G E, pak TI (G, e) =f (N, E — {e}, s); Transformace T2: jestliže pro nějaký y G N — {s} existuje právě jeden x G N — {y} takový, že (x, y) G E1 a existuje-li libovolná hrana e = (y, z) G E (y ^ z), pak T2(G,e) = (N', E', s) kde (a) nemá-li y jiného následníka než uzel z, pak N' = N — {y} a E' = E U {(x, z)} — {(x, y), (y, z)}; (b) v opačném případě N' = N, E' = E U {(x, z)} - {(y, z)}; Transformace T3: nechť v G každá hrana, která není cyklem délky 1, vychází z uzlu s. Existuje-li x G N takový, že e = (s, x) je jedinou hranou vstupující do x, pak T3(G,e)d=lf (N-{x},E-{e},s). Lze ukázat, že graf toku řízení G je reducibilní v intervalovém smyslu, právě když je redukovatelný opakovanými aplikacemi transformací TI až T3 na triviální graf. Je-li dán GTŘ G, pak nejprve provádíme analýzu toku řízení: na G postupně aplikujeme uvedené transformace a současně konstruujeme tzv. rozbor grafu G -uchováváme pořadí použitých transformací ve tvaru posloupnosti prvků (t,S), kde t G {TI,T2a,T2b,T3} udává typ transformace a S specifikuje uzly, na něž je t aplikována (viz též příklad na obr. 7). Obr. 7 Tyto transformace lze na graf toku řízení aplikovat ad hoc, avšak složitost algoritmu provádějícího analýzu toku dat je závislá na jejich pořadí. Autoři uvádí (viz [Gra76]) velice důmyslný algoritmus (využívající mimo jiné relace dominance - viz například [Tar74]) tak, aby byl minimalizován počet transformací T2, které jsou, díky výpočtu globálnějších GEN a NOTKILL i lokálnějších LIVE, z hlediska časového nej náročnější. Máme-li k dispozici rozbor GTŘ G, můžeme opět použít dvouprůchodového algoritmu: Fáze 1 počítá množiny GEN a NOTKILL podle níže uvedených pravidel, a to v pořadí, jak udává rozbor grafu G. Fáze 2 začíná opět přiřazením LIVE(s) := GEN(s), kde s je jediný uzel limitního grafu. Následně, v revezi pořadí daného rozborem, počítáme postupně stále lokálnější množiny LIVE dle dále uvede- 15 ných pravidel. Po skončení této fáze máme určeny množiny LIVE pro všechny uzly původního, reducibilního grafu toku řízení G. Pravidla pro výpočet GEN a NOTKILL při redukci grafu (fáze 1): TI: žádný výpočet (skip) T2a: GEN(x) := GEN(x) U (NOTKILL(x, y) n GEN (y)) (NOTKILL(x, z) := NOTKILL(x, y) U (NOTKILL(x, y) n NOTKILL(y, z)) T2b: (NOTKILL(x, z) := NOTKILL(x, y) U (NOTKILL(x, y) n NOTKILL(y, z)) T3: GEN(s) := GW(s) U (NOTKILL(s, x) n GEN (x)) (při čtení pravidel doporučujeme konzultovat obr. 6) Pravidla pro výpočet LIVE při zpětné expanzi grafu (fáze 2): TI: žádný výpočet (skip) T2a: LIVE(y) := GEN(y) U (NOTKILL(y, z) n LIVE (z)) T2b: LIVE(y) := LIVE(y) U (NOTKILL(y, z) n LIVE(z)) T3: LIVE{x) := GW(x) (při čtení pravidel pro LIVE je vhodné obrátit orientaci šipek =>• na obr.6) Algoritmus GW - komprese cest Vstup: (1) Reduciblní GTŘ G = (N, E, s) (2) VxeiV: GEN (x); Vi 6 iV : Vy g SUCC(x) : NOTKILL(x, y) . (3) seznam ROZBOR = < (ŕi,Si),(tr,Sr) > redukující graf G, kde r =| ROZBOR | ; Výstup: VxeTV: LIVE(x); begin {fáze 1: lokální —> globálni} for i := 1 to r do (t,S) := ROZBOR(i) od; case t of TI: skip; T2a: with S do GEN(x) := GEN(x) U ( NOTKILL(x,y) f] GEN(j) ); NOTKILL(x,z) := NOTKILL(x,z) U (NOTKILL(x,y) n NOTKILL(y,z)) od; T2b: with S do NOTKILL(x,z) := NOTKILL(x,z) U (NOTKILL(x,y) n NOTKILL(y,z)) od; T3: GW(s) := GW(s) U (NOTKILL(s, S.x) n GEN($.x) ) end {case} od; {for} {konec fáze 1; fáze 2: globálni —>• lokálni :} LIVE(s) := GW(s); for i := r downto r do (t,S) := ROZBOR(i) od; case t of TI: skip; T2a: with S do LIVE(y) := GEN(y) U (NOTKILL(y,z)f]LIVE(z)) od; T2b: with S do LIVE(y) := GEN(y) U (NOTKILL(y,z)f]LIVE(z)) od; T3: with S do LIVE(x) := GEN(x) od; 16 end {case} od; {for} end; Algoritmus GW je časové složitosti 0(| E \ . log \ E |) a na strukturovaných programech je lineární, tj.O(| E |), přičemž pro reálné (a tím spíše pro strukturované) programy je \ E \= 0(\ N \). Důkazy uvedených tvrzení viz [Gra76]. Existuje dokonce efektivnější implementace (založená na [Tar75] - viz [Tar81]), která je složitosti 0(| E | .a(\ E \,\ N j)), kde funkce a je vztažena k inverzi Ackermannovy funkce; je tudíž z praktického hlediska (asymptoticky) lineární, avšak implementačně velmi náročný. Navíc není dosud známo, zda je tato efektivnější verze aplikovatelná na problémy ATD typu "zpět". 4.3 Eliminační metody založené na grafových gramatikách S cílem zjednodušit a zrychlit analýzu toku řízení (a tím i analýzu toku dat) se mnoho autorů snaží dále omezit třídu grafů, které by byly danou metodou redu-kovatelné. Zde budeme prezentovat nástin jedné z těchto metod, detailní popis lze najít v [Far76]. Pomocí grafové gramatiky (GG) se definuje třída tzv. téměř strukturovaných grafů (odpovídá třídě REi - viz [HaK77] či, zhruba, řídícím strukturám jazyka Ada, Modula). Pravidla GG slouží k nalezení rozboru daného téměř strukturovaného GTŘ. Vlastní ATD probíhá (po nalezení rozboru grafu) ve známém dvouprůcho-dovém algoritmu, kdy s každým pravidlem GG je spojen výpočet globalizace GEN a NOTKILL (krok 1) a též lokalizace LIVE (krok 2). Algoritmus je na uvedené třídě lineární, v ostatních případech selhává. Vzhledem k tomu, že pravidel GG je celkem devět a algoritmus hledání rozboru je poněkud komplikovaný (důkaz jeho korektnosti velmi komplikovaný), uvádíme na obr.8 pouze příklad pravidla pro cyklus s dvěma výstupy: Obr. 8 Pravidla pro výpočet GEN a NOTKILL při redukci grafu: krok 1: GEN(x) := GEN(x) U (NOTKILL(x, y) D GEN(y)) NOTKILL(x, z) := NOTKILL(x, z) D NOTKILL(x, y) NOTKILL(x,w) := NOTKILL(x, y) D NOTKILL(y,w) 17 Pravidla pro výpočet LIVE při zpětné expanzi grafu: krok 2: LIVE(y) := GEN(y) U (NOTKILL(y, x) n LIVE(x)) U U (NOTKILL(y,w) n LIVE(w)) 5 Analýza toku dat vyšší úrovně Všechny dosud zmíněné metody pracovaly s detailní (nízko-úrovňovou) reprezentací programu - grafem toku řízení. Vzniká otázka, zda lze uvedené analýzy provádět na vyšší úrovni reprezentace programu, například na syntaktickém stromu programu. Mnoho takových metod skutečně bylo navrženo ([Ros77], [Bab8], [Ros80], [Ros82], [Zad84]). Jejich filosofie staví na faktu, že většina současných programovacích jazyků má bohatý repertoár řídicích struktur, které explicitně (již v době definice jazyka) udávají tok řízení. U dříve uvedených metod se tato informace při budování grafu toku řízení ztrácí a pak ji více či méně pracně získáváme (v době kompilace) zpět konstrukcí rozboru GTŘ nebo ji (u iterativních metod) nebereme v úvahu a platíme za to ztrátou časové efektivity. Metody analýzy toku dat vyšší úrovně pracují pro základní problémy ATD na strukturovaných programech v lineárním čase a oproti eliminačním metodám mají další výhodu ve své robustnosti: není-li graf toku řízení (téměř) struturovaný či reducibilní, pak neselhávají, ale stále poskytují řešení, i když - zhruba řečeno -s rostoucím počtem "vhodně volených" příkazů goto roste jejich časová složitost. Neposlední výhodou je, že lokální změna v programu (způsobená například kompilátorem provádějícím optimalizační transformace) má za následek opakování analýzy jen pro ten podstrom syntaktického stromu, v němž byla změna provedena; tzv. analýza na žádost (např. [Bab78a], [Zad84]). Nevýhodu lze spatřovat v tom, že jisté optimalizace vyžadují reprezentaci programu na velmi nízké úrovni - pak je nutno syntaktický strom uchovávat v podstatě po celou dobu překladu. Základní rysy metod analýzy toku dat vyšší úrovně jsou založeny na vzájemně rekurzívních procedurách, analogicky jako například syntaktická analýza metodou rekurzívního sestupu. S každým symbolem gramatiky sdružíme množiny (atributy) GEN, NOTKILL a LI VE, LVBOT, kde GEN a NO TKILL pro terminály v syntaktickém stromu jsou dány - čtenář obeznámený s atributovými gramatikami (viz např. [Knu68]) na ně může nahlížet jako na syntetizované atributy. Globalizaci GEN a NOTKILL jistého strukturovaného příkazu odpovídá syntetizování těchto atributů z lokálních GEN a NOTKILL jeho složek. Analogickou úvahou pro LI VE a LVBOT šířícím se od příkazu k jeho složkám, dospějeme k chápání LIVE a LVBOT jako dědičných atributů. Ilustrujme základní rysy analýzy toku dat vyšší úrovně na příkladové gramatice s těmito pravidly: 18 (1) p (2) co (3) c0 (4) co (5) c begin c end ci; C2 if e then c\ else c2 while e do c\ (6) c0 (7) c0 (8) c (9) c = /label/ : Ci = goto /label/ = /read — command/ = /write — command/ = e Blíže nespecifikované neterminály (e, /read - command/,... ) lze pro naše účely považovat za terminálni symboly - jejich GEN a NOTKILL je snadné zjistit lokální analýzou. Tedy pro příkazy popsané pravidly (1), (5), (8) a (9) je situace jednoduchá: za předpokladu, že známe LVBOT těchto příkazů, platí tato rovnice: (LIVE) LIVE(c) := GEN(c) U (LVBOT(c) n NOTKILL(c)) U ostatních případů je situace složitější; ilustrujme ji na sekvenci - viz pravidlo (2) a obr. 9. Co "— C\, C2 GEN (co) ,■ NOTKILL(cq) co --LIVE (co) --LIVE (a) --LVBOT (a) --LIVE(c2) --LVBOT(c2) ----LVBOT(cQ) Obr. 9 a) syntaktický strom b) tok řízení a informace ATD Z obr. 9 je zřejmé, že platí rovnosti: LVBOT(c2) = LVBOT(c0) (SEKVENCE) LVBOT (d) = LIVE(c2) LIVE(co) = LIVE(cí) Na rozdíl od jednoduchých příkazů je naše situace komplikovanější tím, že neznáme GEN a NOTKILL příkazu co a nemůžeme použít rovnici (LIVE) přímo. Podle způsobu řešení této situace lze metody analýzy toku dat vyšší úrovně rozdělit na tyto dva typy: (1) Globalizovaná informace se hledá analogicky jako u eliminačních metod. V průchodu 1 globalizuje lokální informaci: GEN(c0) := GEN(Cl) U (NOTKILL(Cl) n GEN(c2)) NOTKILL(co) := NOTKILL(Cl) n NOTKILL(c2) . 19 V průchodu 2 (nyní shora-dolů) se globální LIVE(cq) a LVBOT (cq) lokalizují do c\ a do C2 : LVBOT(c2) := LVBOT(c0) LIVE(c2) := GEN(c2) U (NOTKILL(c2) n LVBOT{c2)) LVBOT(Cl) := LIVE(c2) LIVE(ci) := GEN (a) U (NOTKILL(cľ) n LVBOT{Cl)) (První a třetí pravidlo plyne ze (SEKVENCE), druhé a čtvrté jsou dány vztahem (LIVE) ). Úplný výčet pravidel pro metody tohoto typu lze nalézt například v [Ken81] pro strukturované příkazy (bez goto, v [Ros80] je prezentována metoda umožňující analýzu i v případech, kdy jazyk obsahuje jak příkazy goto, tak i jeho omezené varianty (exit, leave, ...), ovšem za cenu vyšších nároků na čas. (2) GEN a NOTKILL se neglobalizuje, a tyto metody vykazují jisté iterativní rysy. Je-li volána procedura, která má za úkol analyzovat sekvenci se skutečným parametrem co, musí se pro každou jeho složku volat procedura, jež ji analyzuje. Zřejmě je výhodnější volat nejprve proceduru pro analýzu c2, a pak pro c\: za předpokladu, že známe LVBOT(cq) a přijmeme konvenci, že po výpočtu LIVE daného uzlu se tato hodnota posílá do LVBOT jeho předchůdce, můžeme určit LIVE(c2); volání pro c± má již k dispozici LVBOT (a) a davá LIVE (a), což je hledaná LIVE{cq) (a LVBOT jeho předchůdce). Pravidla pro sekvenci jsou tedy dána rovnicemi (SEKVENCE), kde výskyt LIVE(.) na pravé straně odpovídá rekurzívnímu volání procedury LIVE pro daný typ příkazu. Pravidla pro větvení if e then c\ else c2 jsou dána tím, že e má dva následníky ci a c2 a s nimi sdružené množiny LIVE(ci) a LIVE(c2), jejichž sjednocení je rovno LVBOT'(e), a tím, že vyhodnocení výrazu e nezabíjí žádnou proměnnou: Pravidla pro co ::= while e do c\ nalezneme na základě analogických úvah (viz též obr. 10): V první rovnici se na pravé straně vyskytuje dosud neznámá hodnota LIVE(c\). Pro výpočet LVBOT argumentu c\ položíme při inicializaci "nejhorší předpoklad" LIVE(ci) = 0. Po výpočtu dle první rovnice a následném výpočtu LIVE(c\) se tento výsledek porovnává s předpokladem, s nímž jsme výpočet provedli, což je zároveň test na ukončení iterace (v případě rovnosti). Jinak provádíme další iteraci, tentokrát již s aktualizovaným předpokladem - poslední vypočtenou hodnotou LIVE(ci) (obr. (IF) LVBOT (a) LVBOT (c2) LIVE(co) LVBOT (co) LVBOT'(o) GEN(e) U LIVE (d) U LIVE(c2) (WHILE) LVBOT(Cl) LIVE(cq) GEN (e) U LIVE (a) U LVBOT(cQ) GEN (e) U LIVE(cí) U ĽVBOT{cq) 10). 20 Co ::= while e do c\ ----LIVE(cq) "Co ----LVBOT(a) Obr. 10 a) syntaktický strom - LIVE(ci) - LVBOT{ci) - LVBOT(c0) b) tok řízení a informace ATD Pro pravidlo c0 ::= /label/ : C\ je situace velice jednoduchá: (LABEL) := ™W v y LIVE(c0) := LIVEiyCi) Příkazu co ::= goto /label/ odpovídá v syntaktickém stromu list, a tedy nepotřebujeme specifikovat rovnice pro LVBOT{ složka ) . Musíme však nalézt rovnice pro LIVE(cq), protože tuto hodnotu má příkaz posílat svému předchůdci. Je-li tímto příkazem řízení předáno na příkaz c, pak je zřejmě LVBOT(cq) = LIVE(c), a protože co žádnou proměnnou ani nepoužívá ani nezabíjí, dostáváme LIVE(cq) = LVBOT(cq). Rovnice pro toto pravidlo je tedy tvaru (GOTO) LIVE(c0) LIVE(c), kde Cq je tvaru goto n a c je tvaru n: c . Z tvaru výpočetních pravidel pro (a) příkaz while a pro (b) příkaz goto je vidět, že nemůžeme mluvit o atributové gramatice. V případě (a) by totiž byla atributová gramatika definována kruhem: LVBOT(Cl) := GEN(e)ULIVE(c1)ULVBOT(c0) viz(WHILE) LIVE(Cl) := GEN(ci) U (NOTKILL(ci) Pl LVBOT(c\)) viz(LIVE) V případě (b) není splněna podmínka závislosti atributů, kdy k výpočtu atributu smíme použít jen atributů předchůdce, sousedů či následníků, což však pro rovnici (GOTO) neplatí. Navíc i zde by případ zpětného skoku znamenal definici kruhem. Tedy i pro zpětné skoky musíme pracovat s předpoklady - stejným způsobem jako u příkazu while. Algoritmus tudíž iteruje, dokud se všechny předpoklady nestabilizují, tj. ve dvou po sobě jdoucích průchodech si nejsou rovny. Pro analýzu složitosti uvedeného algoritmu je vhodné si uvědomit, že pro libovolný uzel u syntaktického stromu programu platí, že je-li proměnná v G LI VE (u) po j—té iteraci, pak v G LIVE(u) po každé další iteraci. (Dokáže se indukcí, 21 uvážíme-li, že GEN a NOTKILL jsou konstantní a iteraci začínáme s předpokladem LIVE(u) = 0. ) Důsledek je tento: Pro každý program obsahující W příkazů cyklu a L příkazů s návěštím, na něž předává řízení zpětný skok, skoněí algoritmus nejpozději po W+L+2 iteracích. Nástin důkazu: Množiny předpokladů mají W + L prvků. Pro libovolný průchod j(j > 1) platí, že předpoklady pro (j — 1)—ní a j—tý průchod jsou si rovny (a v tom případě algoritmus končí) nebo aspoň jeden předpoklad, který, řekněme proměnnou v, neobsahoval, ji nyní obsahuje. To značí, že po k—těm průchodu alespoň k — 1 předpokladů proměnnou v obsahuje, a tedy po provedení W + L + 1 průchodů musí všechny předpoklady proměnnou v obsahovat. Jinými slovy, množina předpokladů pro iteraci W + L + 1 musí být rovna výsledkům této iterace a algoritmus končí. Poznamenejme, že uvedený nejhorší případ nastává, musí-li se "dobrá zpráva" GEN o živosti nějaké proměnné šířit po acyklické cestě obsahující W + L zpětných hran reprezentujících návraty v cyklech while a zpětné příkazy goto. Jelikož pomocí pouze cyklů while nelze (při vhodném modelování) vytvořit acyklickou cestu složenou ze zpětných hran délky větší než 1, lze ukázat, že neobsahuje-li program příkazy skoku, pak algoritmus končí po dvou průchodech - [Bab78]. 6 Obecný model analýzy toku dat Dosud jsme se zabývali jediným konkrétním problémem analýzy toku dat. Jelikož problémy ATD, jak ukážeme dále, jsou velmi podobné, je vhodné vybudovat jejich obecnější model a studovat jeho vlastnosti s tím, že algoritmy a jejich vlastnosti (ukončení, korektnost, složitost) pro konkrétní problémy dostaneme jako instance obecného modelu, u nichž již zmíněné vlastnosti nemusíme (problém od problému) dokazovat. 6.1 Řešení dalších základních problémů ATD Dosažitelnost definic Definice d proměnné x (např. x:= ..., read(x) ) dosahuje vstupu (resp. výstupu) uzlu v právě když d je v uzlu u takovém, že existuje cesta z m do u podél níž není x redefinována. Je vidět, že dosažitelnost definice d (proměnné x) je generována v uzlu u, jestliže d je v uzlu u a není v tomto uzlu následována svou redefinicí. Množinu takových definic v uzlu u označíme GEN(u). Dosažitelnost definice d proměnné x je zabita uzlem u, jestliže x je v uzlu u redefinována; množinu všech proměnných (uvažovaného programu), které nejsou v uzlu u redefinovány označíme NOTKILL(u). Konečně RDTOP(u), resp. RDBOT(u) značí hledanou informaci, tj. množinu všech definic dosažitelných na vstupu, resp. výstupu uzlu u. Pak problém dosažitel- 22 nosti definic pro GTŘ G=(N,E,s) lze specifikovat systémem (vzájemně rekurzívních) rovnic (RDI) až (RD3), resp. systémem (REACH) a (RD3). (RDI) RDBOT(u) = (RDTOP(u) n NOTKILL(u)) U GEN (u) VueiV (RD2) RDTOP(u)= \J RDBOT(v) Vu G N v£PRED(u) je-li PRED(s) = 0 , pak RDTOP(u) = 0 (RD3) řešením RE A CHES problému je nejmenší řešení (vzhledem k in-klusi) splňující (RDI) a (RD2). (REACH) RDTOP(u) = ( \J RDTOP(v) íl NOTKILL(v)) U GEN(v) vePRED(u) Problém dostupných výrazů Výraz e je dostupný na vstupu, resp. výstupu uzlu v právě když na každé cestě z počátečního uzlu s do uzlu u byl již e vyhodnocen a dále již nebyla hodnota žádného jeho operandu měněna. Dostupnost výrazu je generována jeho vyhodnocením v uzlu, například jeho výskytem na pravé straně přiřazovacího příkazu. Množinu všech výrazů vyhodnocovaných v uzlu u označíme GEN(u). Naopak dostupnost výrazu je zabita v uzlu, jestliže některý z jeho operandů je v tomto uzlu redefinován. Množinu výrazů, které nejsou zabity v uzlu u označíme NOTKILL(u). Problém dostupných výrazů specifikuje systém (vzájemně rekurzívních) rovnic (AVI) až (AV3), resp. (AVAIL) a (AV3), kde AVTOP(u), resp. AVBOT(u) označuje hledanou informaci - množinu výrazů dostupných na vstupu, resp. výstupu uzlu u. (AVI) AVBOT(u) = (AVTOP(u) n NOTKILL(u)) U GEN (u) VměíV (AV2) AVTOP(u)= f| AVBOT(v) VueiV vePRED(u) AVTOP(u) = 0 (AV3) řešením AVAIL problému je největší řešení (vzhledem k inklusi) splňující (AVI) a (AV2). (AVAIL) AVTOP(u) = ( f| AVTOP(v) n NOTKILL(v)) U GEN (v) vePRED(u) Problém využitelných výrazů 23 Výraz e je využitelný v bodě p (tj.na vstupu, resp. výstupu uzlu), právě když na všech cestách z p do koncového uzlu je e referencován a na žádné z těchto cest není redeŕinována hodnota některého jeho operandu). Množiny NOTKILL(u) jsou definovány jako u problému dostupných výrazů a GEN(u) je množina všech výrazů, které jsou v uzlu u vyhodnoceny, avšak mezi vstupem do u a jejich vyhodnocením v u není měněna hodnota žádného jejich operandu. Problém využitelných výrazů specifikuje systém (VB1) až (VB3), resp. (BUSY) a (VB3), kde VBTOP(u) resp. VBBOT(u) značí množinu výrazů využitelných na vstupu, resp. výstupu uzlu u. (VB1) VBTOP{u) = (VBBOT{u) n NOTKILL(u)) U GEN (u) VueiV (VB2) VBBOT{u)= f| VBTOP(v) VueiV vesucc(u) je-li SUCC(s) = 0 , pak VBBOT(u) = 0 (VB3) řešením BUSY problému je největší řešení (vzhledem k inklusi) splňující (VB 1) a (VB2). (BUSY) VBBOT(u) = ( \J VBBOT(v) n NOTKILL(v)) U GEN (v) vePRED(u) Systémy (REACH), (AVAIL) a (BUSY) lze řešit iterativní metodou, jak byla uvedena ve 3.1, kterou je však nutno problém od problému modifikovat tak, jak udávají jednotlivé systémy. V 6.3 uvedeme obecný algoritmus, jehož konkrétními instancemi dostaneme algoritmy řešící nejen dosud uvedené, ale i další problémy analýzy toku dat. Problém adaptace eliminačních metod může být komplikovanější (v závislosti na metodě a zejména pro problémy ATD typu "zpět"); obecný model uvedeme v 6.4. 6.2 Informace v analýze toku dat (1) Informaci (např. množiny LIVE) lze modelovat pomocí prvků polosvazu. Často potřebujeme popsat prvek Z, který by nesl informaci obsaženou buď v nějakém prvku X nebo v nějakém prvku Y, či duálně, informaci, která je společná prvku X i Y. Takový prvek budeme nazývat spojením (či duálně průsekem) la ľ. U LIVE-problému chceme, aby živost na výstupu byla spojením Z informací od následníků X,...,Y. Dvojici (S, C) nazveme částečně uspořádanou množinou (posetém), je-li na S definována relace C částečného uspořádání ("je menší nebo rovno než" či "má menší nebo stejný informační obsah než"); x C y značí x C y a x ^ y. Spojením prvků x a, y nazveme, pokud existuje, prvek z G S1 takový, že x C z, y C z, přičemž neexistuje prvek z' G S, takový, že x C z' C z a y C z' C z. Duálně - záměnou C 24 za □ definujeme průsek. Mají-li x,y G S jediné spojení (resp. průsek), značíme jej \/{x, y} (resp. /\{x, y}), či infixově x V y (resp. x A y). Svazem (S, V, A) nazveme poset (S, C), kde každé dva prvky mají jediné spojení a jediný průsek. Jestliže navíc spojení V H prvků množiny H a průsek /\ H existují pro všechna H, H C S, nazýváme 5 úplným svazem. Tento má nejmenší prvek (infimum, nulu) _L = A S a největší prvek (supremum, jedničku) T = V S a značíme jej S(C,V,A,-L,T). Příklad la : Nechť V(S) je množina všech podmnožin množiny S. Je-li S konečná, pak V(S)(C, (J, D, 0, S) je úplný svaz. Tedy i množiny LIVE, resp. LVBOT, LVTOP (tj. systém podmnožin konečné množiny proměnných libovolného daného programu) s operacemi U a fl, tvoří úplný svaz. Je-li dán svaz (S, V, A), pak k výchozímu posetu (S, C) lze dospět tak, že položíme x C y právě když x V y = y, resp. x A y = x. Často vystačíme s jednodušší strukturou - polosvazem (S,*), kde S je neprázdná množina a * binární operace, která je idempotentní (x * x = x), komutativní a asociativní na 5". Je-li (S1, V, A) svaz, pak (S, V) a (S, A) jsou spojový a průsekový polosvaz. Nejvýše spočetnou podmnožinu CCS, C = {xq,xi, ... ,xn,...} nazveme rostoucím řetězcem, jestliže x0 C. x± C. ... C. xn C. .... (S,C.) nazveme dobře založená množina (spňující podmínku rostoucích řetězců), jestliže pro x, G S, i = 0,1,... a xq C. xi C. ... existuje m takové, že xm = xm+\ = ... . Duálně lze definovat klesající řetězec. Příklad lb : Problém šíření konstant (CP-problém). Tento problém spočívá v tom, že máme pro každý uzel GTŘ určit ty proměnné, jimž je na vstupu do daného uzlu (při libovolném výpočtu podél libovolné cesty od počátečního uzlu do uzlu daného) vždy přiřazena stejná konstantní hodnota. Nechť Var je konečná množina proměnných (daného programu) a C je množina možných hodnot konstant. Pro CP-problém zvolíme za informaci sdruženou se vstupem do uzlu podmnožinu množiny Var x C; například množina {(A, 1), (B, 2)} sdružená s nějakým uzlem značí, že podél libovolné cesty z počátečního uzlu do daného uzlu nabývá proměnná A vždy hodnotu laß hodnotu 2. Zřejmě pro L = V( Var x C) je (L, A) polosvaz: L je množina funkcí z konečné množiny Var do C a A je množinový průnik nad uspořádanými dvojicemi tvaru (V, r) e L; L má infimum 0 a nemá supremum. Tedy s každým bodem (vstupem, resp. výstupem uzlu) grafu toku řízení sdružujeme jistý prvek polosvazu; operace spojení reprezentuje efekt spojení informace pocházející od následníků/předchůdců (analogicky pro průsek). Zbývá modelovat efekt výpočtu v uzlu (efekt lokální informace). Jde vlastně o funkci, která transformuje informaci (prvek polosvazu) na vstupu/výstupu uzlu na informaci na výstupu/vstupu uzlu. (2) S každým uzlem (hranou) sdružíme funkci f : S —>• S, kde S je polosvaz. 25 Příklad 2 a : (pokračování la) Pro určování živých proměnných platí rovnice (LIVE) transformující LVBOT - spojení LIVE následníků na LIVE uzlu, kde pro libovolný, ale pevně daný uzel jsou jeho GEN a NOTKILL konstantní. Označme je g a k. Pak uvedená transformace je vlastně funkcí f takovou, že f<9,k> ■ S ->• S, kde f(x) = (x n k) U g Je-li každému uzlu u přiřazena odpovídající lokální funkce fu, pak LIVE-problém lze modelovat spojovým polosvazem (S,\J), kde S = V(Var) a rovnice (LIVE) je nyní tohoto tvaru: (LIVE) LIVE(x) = \J{fy(LIVE(y)); y G SUCC(x)} Příklad 2b : (pokračování lb) Přiřaďme každému uzlu funkci definovanou následovně. Pro jednoduchost předpokládejme, že uzly obsahují příkazy tvaru A:=B op C nebo A:=r, kde r G C, op G {+, —,*,/} a A, B, C G Var. Funkce reprezentující uzel je kompozicí funkcí reprezentujících jednotlivé příkazy uvnitř uzlu. Pro x G L položme: 1- f(x) = y , kde y(V) = x(V), W G Var - {A} a y(A) = r tj. y dostaneme z x tak, že vypustíme dvojici s první složkou A a přidáme dvojici (A, r). 2. f(x) = y,kde y(V) = x(V), W G Var - {A} a y (A) = b op c , je — li x(B) = b a x(C) = c , y (A) není definováno - v ostatních případech . Je-li s každým uzlem u sdružena funkce fu uvedeného tvaru, pak CP problém lze modelovat průsekovým polosvazem (L, A) - viz příklad lb - a rovnice určující množinu CP proměnných konstantních na vstupu do uzlu x lze psát v tomto tvaru: (CP) CP(x) = /\{fy(CP(y)); y G PRED(x)} V uvedených příkladech (i u ostatních problémů ATD) by funkce fu reprezentující efekt výpočtu v uzlu měly být konzistentní se sémantikou daného jazyka. U základních problémů ATD je tato konzistence ověřitelná na syntaktické úrovni, proto se tyto problémy někdy nazývají syntakticky orientované; ostatní problémy ATD se nazývají sémanticky orientované (např. CP problém). Sémantika analýzy toku dat je speciální (a jednoduchým) příkladem tzv. předvýpočtové sémantiky; podmínky konzistence těchto sémantik se standardní sémantikou jazyka lze nalézt v [Kře85b]. V konkrétním a jednoduchém případě analýzy toku dat však lze, alespoň na intuitivní úrovni požadovat, aby funkce fu byly z tohoto hlediska "rozumně navržené". Nechť (S, C) je poset. Funkci / : S —» S nazveme monotónní, jestliže Vx, y G S : (a C b) =>• (f (x) C f (y))- Snadno se nahlédne, že / je monotónní na polosvazu (S, C) právě když Vx, y G S : f(xAy) C f(x)ŕ\f(y).U-\\\ix,y G S : f(xAy) = f (x) A f (y), nazveme fukci / distributivní, f je (A) spojitá funkce, jestliže pro každý klesající 26 řetězec CCS platí f(l\C) = f\f(C). Platí-li uvedená rovnost pro libovolnou množinu CCS, pak / je aditivní (nekonečně distributivní) funkce. Zřejmě aditivita indikuje spojitost, která implikuje distributivitu, která indikuje monotonii. Je-li (L, C) poset, funkce / : L —> L monotónní, pak x G L nazveme pevným bodem funkce f právě když x = f (x). Nejmenším pevným bodem funkce / nazveme (pokud existuje) prvek £ L; f(x) C x}, největším pevným bodem / nazveme prvek \/{x G L; f (x) □ x}. 27 6.3 Model pro iterativní metody Je-li dán dobře založený polosvaz (L, C) s nejmenším prvkem _L a množina funkcí F = L —>• L, pak F nazveme prostorem monotónních funkcí sdruženým s L, právě když jsou splněny tyto podmínky: (Ml) Vx,y G L. V/ G F : f (x A y) C f (x) A f (y) (tj. každá funkce z F je monotónni); (M2) 3id G F. Vx G L : id(x) = x (v F existuje identická funkce id); (^M5j Vf,gčF =>• f .g e F (F je uzavřena vzhledem ke kompozici); fM^) Vx G L. 3/ G F : x = /(-L) (X je roven uzávěru {_L} vzhledem ke kompozici a průseku). Dvojici (L,F) nazveme (algebraický) monotónní kontext analýzy toku dat. (Duálně definujeme prostor F pro spojový polosvaz.) Podmínka (Ml) odpovídá intuitivnímu požadavku, aby většímu informačnímu obsahu argumentu x odpovídal i větší informační obsah funkční hodnoty f(x); (M2) odpovídá situaci, kdy uzel neobsahuje žádný příkaz, který by ovlivňoval informaci při průchodu tímto uzlem. (MS) uvažuje zpracování informace při průchodu sekvencí dvou po sobě následujících uzlů a (M4) zabraňuje tomu, aby L obsahoval irelevantní informaci (nadbytečné prvky) - infimum _L reprezentuje prázdnou informaci na vstupu vstupního uzlu před započetím analýzy. Instancí (monotónního) kontextu nazveme čtveřici I = (L, F, G, M), kde (L, F) je (monotónní) kontext, G = (N, E, s) je GTŘ a M : N —> F je funkce přiřazující každému uzlu z N operaci z F. (Pro eliminační případ obvykle M : E —> F.) Důležitou podtřídu monotónních kontextů tvoří distributivní kontexty, tzn., že všechny funkce z F jsou distributivní: (Dl) Vx,yeL.VfeF: f(x A y) = f(x)Af(y). Intuitivně lze uvedenou rovnost interpretovat tak, že při operaci průseku nedochází ke ztrátě informace. V podmínce (Ml), která je implikována podmínkou (Dl), nerovnost C reprezentuje pouze konzervativní, tj. bezpečnou aproximaci "přesného" řešení. Příklad 3a : Model pro LIVE problém, prezentovaný v příkladu 2a, tvoří distributivní kontext. Příklad 3b : Model pro CP problém z příkladu 2b je monotónní kontext, který není distributivní. Ilustrujme to následujícím protipříkladu instance monotónního kontextu z obr. 11). Kontexty tohoto typu jsou monotónní a distributivity lze dosáhnout volnou interpretací operátorů, tj. jestliže výsledek aplikace n-árního operátoru na dvě různé n-tice není nikdy stejný - [Kam77]. Odlišný přístup je uveden v [Kil73], kdy za cenu časové složitosti je uvažována i komutativita operací. 28 x = { (B,l), (C,2) } B ■= 1 C ■= 2 B ■= 2 C ■= 1 A := B+C y = { (B,2), (C,l) } kde < A := B + C > (x A y) = 0, ale < A := B + C > (x) A < A := B + C > (y) {(A 3)} Obr. 11 Konečně poznamenejme, že podmínka dobré založenosti L v definici monotónního kontextu umožňuje nalézt průsek řetězce C = {ci,c2,...} v konečném čase; pak totiž existuje přirozené m takové, že A{q; c g C} = A{q; 1 < i < Máme-li formulován problém ve tvaru systému rovnic (srovnej příklady 2a a 2b) Xl = fi(xi,...,xn) resp. X = f(X) (6.1) X n — fn(xi, ■ ■ ■ , Xn) můžeme použít k nalezení extremálního (pro spojení minimálního - viz LIVE problém, požadavek (L3) ) pevného bodu funkce / základní iterační algoritmus MFP: 1. inicializuj X ; 2. while f (X) ^ X do X := f (X) od ; 3. return X {= f (X)} . Je-li totiž funkce / monotónní, tj. všechny z (4.1) jsou monotónní, pak množina C = {Xl;i > 0}, kde (v případě spojového polosvazu): X° = (_L,...,_L) a Xi+1 = f(Xi), i>0 (6.2) tvoří řetězec, a tedy algoritmus MFP končí. Ukažme ještě, že supremum řetězce C je vhodné považovat za řešení systému (4-1) (srovnej s definicí LIVE): Označíme-li X-lteT řešení systému (4-1), pak Vi.i > 0 : X1 C. Xjter, tj. každé X1 nese částečnou informaci konzistentní s konečným řešením XiteT zadaným specifikací (4-1)- Obráceně, obsahuje-li XiteT jistý fakt, pak musí existovat nějaké (a zde konečné) i > 0 takové, že tento fakt je v X1 obsažen, což dává Xjter C y {X1; i > 0}, a tedy X-lteT = y {X1; i > 0}. Systém (4-1), jak vime z LIVE problému, může mít více řešení (pevných bodů), ale iterace (4-2) najde nejmenší z nich: je-li totiž Xyib nějakým řešením (4-1), pak musí být pevným bodem (4-1)- Indukcí ověříme, že X1 C X\ih,i = 0,1,... (_L = X° C X\ih z definice _L; pro 1 > 0 předpoklad Xl~l jZ X\ih a monotonie / dává žádané X1 = f(Xl~l) jZ f(X\ih = Xyib). Je tedy Xlib horní závorou C - viz (4-2), ovšem XiteT je supremum C, což značí ^iter E X]ib. Na základě těchto úvah je tedy korektní algoritmus VMFP. 29 Algoritmus - VMFP Vstup: Instance / = (L, F, G, M) monotónního kontextu. Výstup: Řešení pro instanci / begin {uzly grafu G očíslovány l,2,...,n } {inicializace:} for i:=l to n do X(i) := _L od; {iterace:} change := true; while change do change := false; for i:=l to n do NEW := V{fk(X(k));kGPS(i)} if NEW ^ X(i) then change:=true; X(i) := NEW fi; od; od; return ( X(l), ... , X(n) ) end. V algoritmu VMFP zkratka PS značí a) pro problémy typu vpřed předchůdce uzlu, tj. P$::=PRED, b) pro problémy typu zpět následníky, tj. P$::=SUCC. V případě a) je vhodné volit pořadí uzlů rPostorder, v b) pořadí Postorder. (Je tedy vidět, že algoritmus Iterativní LIVE z 3.1 je instancí obecného algoritmu VMFP.) Algoritmus VMFP lze snadno modifikovat na algoritmus AMFP; za zmínku stojí fáze inicializace: Nechť v G = (N, E, s) má uzel s pořadové číslo 1. Pak inicializace má tento tvar: X(l) := _L; {při startu žádná informace na vstupu s } for i:=2 to n do X(i):=T od {T je duální k _L } Nemá-li L supremum T, lze takový prvek přidat uměle - viz např. [Kam76], [Hec77]. Všimněme si složitosti uvedených algoritmů. Případ /\MFP je zřejmě díky možné neexistenci suprema (viz inicializace) obecnější (transformace výsledků na duální případ je triviální). Musíme se omezit jen na konstatování faktů, důkazy lze nalézt v [Kam77] - jsou obdobné jako naše úvahy o složitosti v čl. 3.1. Je-li dána libovolná instance / = (L, F, G, M) distributivního kontextu pro problém ATD typu vpřed a uspořádání rPostorder pro G = (N, E, s), pak algoritmus AMFP končí nejvýše po d(G) + 3 iteracích právě když pro (L, F) platí: VxeL.Vf,geF: fg(±) □ • L, eval(f, x) = f(x), kterou používají i iterační metody). vali s tzv. spojitými kontexty, kdy pro prostor funkcí F platí tyto podmínky: (6.4), resp. (6.3). Uvažujme jednoduchý příklad z obr. 12 a mějme instanci kontextu / = (L, F, G, M). Zobrazení M rozšířené z hran na cesty značme opět M. Je vidět, že z uzlu m do uzlu n existuje nekonečná množina cest: P = {d, (c, d), (c, c, d),...} = {c*d}. Je-li instancí / hraně c přiřazena funkce /, hraně d funkce g, pak hledaná množina Obr. 12 31 (51) F obsahuje identickou funkci id; (52) F je uzavřena na kompozici, průsek a na operaci *, kde ľ(x) = Mf(x);i>0}; (53) každá funkce / G F je spojitá. Problém eliminační metod spočívá v nalezení funkce /* sumarizující efekt cyklu v konečně mnoha krocích. Zřejmě nejslabší rozumný a reálný model je (eliminační) monotónní kontext, kdy pro prostor funkcí F platí tyto podmínky: (EM1) F obsahuje identickou funkci id; (EM2) F je uzavřena na kompozici a průsek; (EM3) každá funkce / G F je monotónní; (EM4) aproximace /*: V/ G F. 3fa G F : (i) Vx G L. Vi > 0 : fa(x) C f* (x) (U) f (x) □ x fa(x) □ x. Prezentujme další (postupně slabší) podmínky kladené na monotónní prostor F. Nej jednodušším řešením úkolu aproximace F* (sumarizace M (P)) je předpokládat idempotentní kontext (L,F), kdy platí podmínky (EM) a navíc platí podmínka (11) V/ G F : /./ = /, tedy f* = f (srovnejte s (6.5)). Intuitivně odpovídá idempotence tomu, že cykl stačí projít jedenkrát. V příkladě z obr. 12 je pak M (P) = {g, g f} a lze ji sumarizovat jako 9 A (g-f)- Klasickým případem, který využívá idempotence, je intervalová analýza uvedená v čl. 4.1. Pro některé problémy ATD idempotentní kontext nenalezneme a hledáme tudíž slabší podmínku pro aproximaci /*, a to i za cenu jisté (avšak bezpečné) ztráty informace. Monotónní kontext (L,F) nazveme rychlý (fast), jestliže platí: (Fl) V/GF: /./□ f Aid . Pak aproximujeme g.(f A id C f\M(P), neboť (/A id) C fl, i > 0 (srovnejte s (6.6)). CP problém (jak lze ověřit) však není ani rychlý. Pro práci s takovými kontexty lze využít triku z [Gra77]: rychlým uzávěrem f+ libovolné funkce f E F nazveme /+ = /\{(f Aid)1; i > 0}. Předpoklad, že platí f e F =>■ /+ G F a že /+ lze najít v konečně mnoha krocích dovoluje pracovat s kontexty, které nejsou ani rychlé. V našem příkladě dostaneme g.f+ C f\M(P) jako bezpečnou aproximaci řešení. Pojmy idempotentního (kdy = nahradíme □ - viz též (6.5)) a rychlého kontextu lze zobecnit na (12) k-ohraničený kontext: V/ G F : fk □ f\{fl; 0 0} a ^ g@f lze získat z f a g pomocí nejvýše t@ aplikací operací . a A . V [Ros80] je uvedena metoda ADT vyšší úrovně využívající spěšných kontextů, která v některých případech, kdy g.f+ C g@f, získává přesnější řešení než rychlé kontexty. Například LIVE problém je 1-semi-ohraničený; problémy tzv. binární relační ATD (detekce společných podvýrazů, metoda pro CP problém poskytující MOP řešení - viz [Kil73]) jsou 2-ohraničené, ne však 1-semi-ohraničené. Složitost n-ární relační ATD je studována v [Jon81]. Typová analýza nemusí být ^-ohraničená pro žádné k. K zajímavému kontextu lze dospět zobecněním pojmu aproximace z rychlých kontextů. (L, F) nazveme spěšný (rapid) kontext, právě když existuje binární operace @ na F a přirozené t@ takové, že platí: (Rl) Vf,geF: g.f+ C g@f C J\{g-ľ;i > 0} a ^ g@f lze získat z f a g pomocí nejvýše t@ aplikací operací . a A . V [Ros80] je uvedena metoda ADT vyšší úrovně využívající spěšných kontextů, která v některých případech, kdy g.f+ C g@f, získává přesnější řešení než rychlé kontexty. 7 Aplikace výsledků analýzy toku dat Dosud jsme se převážně věnovali metodám řešení problémů ATD. Slíbenou motivací pro vynaložené úsilí byla praktická aplikace výsledků získaných jejich řešením. Skutečně, již formulace některých problémů použití v praxi přímo nabízela, nebo praktické využití řešených problémů bylo v textu stručně uváděno v zájmu udržení pozornosti pragmaticky zaměřeného čtenáře. Zopakujme hlavní oblasti aplikace ATD. Již klasickou aplikací, která byla zároveň motivací pro teoretický výzkum ATD a dlouhodobou doménou její aplikace je optimalizace kódu generovaného při překladu. Dalšími oblastmi, do kterých aplikace ATD později pronikly, je proces vývoje programu, zejména pak fáze testování a ladění. Expanze aplikací ATD do procesu vývoje programu je jen logickým důsledkem faktu, že každý programátor je sám o sobě analyzátorem toku dat. Připomeňme proces lokalizace a zjištění příčiny chyby v programu nebo provádění modifikací v programu. Programátor analýzu toku dat provádí na základě intuice a zkušeností, modelem programu je mu obvykle balík výpisu programu ve zdrojovém textu. Provedení metod ATD prezentovaných v této práci lze svěřit počítači a připravit tak rychle a přesně podklady pro vlastní tvůrčí úsilí programátora. 33 7.1 Informační graf programu Ke grafu toku řízení G, jehož uzly reprezentují příkazy programu, je informační graf (IG) definován takto: 1. množina uzlů IG je totožná s množinou uzlů GTR; 2. z uzlu u vede do uzlu v hrana označená proměnnou x právě tehdy, když proměnná x je v uzlu u definována, v uzlu v referencována a v grafu G existuje cesta z uzlu u do uzlu v taková, že v žádném vnitřním uzlu této cesty není proměnná x definována. Globální informace o toku dat potřebná k sestrojení informačního grafu je informace o dosažitelnosti jednotlivých definic proměnných na vstupech uzlů grafu toku řízení. Pro každý uzel u nás zajímá množina REACHES (u) příkazů, v nichž je vypočtena hodnota, která je stále ještě dostupná i na vstupu do uzlu u. Požadované množiny obdržíme řešením systému rovnic (RDI) až (RD3), resp. (REACH) a (RD3) (viz čl. 6.1). Na základě množin REACHES(u) snadno sestrojíme pro každý příkaz p a každou proměnnou x v něm referencovanou množinu DEFS(x,p) příkazů, které mohou počítat hodnotu proměnné x použitou v příkazu p. V informačním grafu tedy vede hrana označená proměnnou x z příkazu u do příkazu v právě tehdy, když u g DEFS(x, v). Informačním grafem je pak pro každý příkaz p a proměnnou x, jíž je příkazem p přiřazena hodnota, dána množina USES(x,p) příkazů, které mohou referencovat tuto hodnotu proměnné x. Mezi množinami DEFS a USES je tento vztah: p g DEFS (x, r) O r g USES (x, p). Poznamenejme, že informaci obsaženou v množinách REACHES můžeme vztáhnout místo k uzlům grafu toku řízení k jeho hranám. Pro libovolnou hranu e s počátečním uzlem u platí Obr. 13 Graf toku řízení Informační graf (IG) REACHES (e) = REACHES (u) n NOTKILL(u) U GEN (u). 34 Takto pojatá informace může být důležitá například při modifikaci programu vsouváním nového příkazu. Je ihned patrno, které toky dat tím případně přerušujeme. 7.2 Šíření konstant Ukažme si použití globálních informací o toku dat obsažených v informačním grafu pro řešení problému šíření konstant, který spočívá v nalezení příkazů produkujících konstantní hodnotu (všechny referencované proměnné mají konstantní -a předem známou - hodnotu). Problém šíření konstant byl již použit jako příklad v předchozích kapitolách. Zde ukážeme jeho řešení na základě informací obsažených v množinách DEFS a US ES. Algoritmus CP - šíření konstant Vstup: PRIK - množina příkazů programu, množiny DEFS a US ES všech příkazů z PRIK, boolevské hodnoty CONST(x,p) pro všechny příkazy p a proměnné x G Rf{p) U Df{p): CONST(x,p) = true právě tehdy, když x G Df(p) a Rf{p) = 0 (výraz na pravé straně příkazu p je složen výhradně z literálů), hodnoty výrazů z pravých stran příkazů p uložené va VAL(x,p) vždy, když CONST{x,p) = true. Výstup: modifikované hodnoty CONST(x,p) : CONST(x,p) = true právě tehdy, když proměnná x při provádění příkazu p nabývá pouze známé konstatní hodnoty (taje pak uložena ve VAL(x,p) ). Pomocné procedury: COMPUTE pro výpočet hodnoty výrazu u něhož známe hodnoty referencovaných proměnných. begin POM:={uGPPJK| CONST(£/(u),u)}; {příkazy produkující zřejmě konstantní hodnotu} while POM ^ 0 do nechť u je libovolný příkaz z POM; POM:=POM - {u}; for each r G USES(Df(u),u) do konst:=true; for each q G DEFS(Df(u),r) - {u} while konst do if not(CONST(£/(u),q) and VAL(D/(u),q) = VAL(D/(u),u) ) then konst :=false fi od; if konst then CONST(£/(u),r):=true; VKL(Df(u),r) := VAL(D/(u),u); if (V y G Rf{r) : CONST(y,r) ) then CONST(i3/(r),r) := true; VKL(Df(r),r) := COMPUTE(r); POM := POM U {r}; fi fi od od end. 35 7.3 Anomálie toku dat Známou aplikací ATD je problém detekcí anomálií toku dat ([Kře79], [BeŠ84]). Rozeznáváme tři druhy anomálií toku dat. Nej častější je anomálie ur- referencování proměnné, která nemá definovanou hodnotu. Další anomálie souvisejí s nevyužitím hodnoty přiřazené proměnné - aniž by proměnná byla referencována, je jí buď přiřazena nová hodnota - anomálie dd, anebo se její hodnota stává nedefinovanou -anomálie du. Anomálie toku dat je příznakem možné chyby v programu. Z informací o toku dat, které jsou obsaženy v informačním grafu, můžeme odvodit následující výskyty anomálií. Na všech cestách do uzlu u, v němž je referencována proměnná x, se vyskytuje anomálie ur právě tehdy, když x G Rf(u) A DEFS(x,u) = 0. Na všech cestách z uzlu u, v němž je definována proměnná x, se vyskytuje anomálie du nebo dd právě tehdy, když x G Df{u) A USES(x,u) = 0. Další informace o výskytu anomálií můžeme získat jednoduchou modifikací problému dosažitelnosti (REACHES). Řešením systému rovnic pro REACHES (viz čl.6.1.) se změněnými lokálními informacemi GEN a NOTKILL obdržíme pro každý uzel u množiny REACHESl(u) příkazů, v nichž se hodnota nějaké proměnné stává nedefinovanou a existuje z nich cesta do uzlu u, podél níž hodnota této proměnné není definována, resp. REACHES2(u) příkazů, v nichž je definována hodnota nějaké proměnné a existuje z nich cesta do uzlu u, na níž nad touto proměnnou není provedena žádná akce (referencování, definování, oddefinování). V případě REACHES1 ponecháme množiny NOTKILL{v) beze změny, množiny GEN{y) nahradíme množinami GENl{y) = {v}, jestliže Undf(v) ^ 0; jinak GENl(v) = 0. V případě REACHES2 naopak ponecháme beze změny množiny GEN (v) a množiny NOTKILL{v) nahradíme množinami NOTKILL2{u) příkazů, v nichž je definována hodnota těch proměnných, které nejsou redefinovány ani referencovány v uzlu v. Na alespoň jedné cestě do uzlu u, v němž je definována resp. oddefinována proměnná x, se vyskytuje anomálie dd, resp. du právě tehdy, když x G Df(u) A {p | p G REACHES2(u) A x G Df(p)} ^ 0 , resp. x G Undf(u) A {p | p G REACHES2{u) A x G Df(p)} ^ 0. Na alespoň jedné cestě do uzlu u, v němž je referencována proměnná x, se vyskytuje anomálie ur právě tehdy, když x G Ä/(u) A {p | p G REACHESl{u) A x G Undf(u)} ^ 0. 7.4 Graf vlivu větvení 36 Analogicky tomu, jak jsme v informačním grafu zaznamenali potencionální vliv příkazů přiřazujících vypočtenou hodnotu na příkazy, které tuto hodnotu mohou referencovat, bychom chtěli zachytit vliv větvících příkazů na ty příkazy, jejichž provedení či neprovedení je jistým způsobem ovlivněno výběrem větve ve větvícím příkazu. Nejde tedy o problém toku dat, ale o problém toku řízení. Oba problémy však spolu úzce souvisí, informace o toku dat v kontextu informací o toku řízení umožní další aplikace. Označme DK(u) příkaz, který je nejbližším dominátorem vzhledem ke konci příkazu u. Graf vlivu větveni (GVV) programu s grafem toku řízení G je definován takto: 1. množina uzlů GVV je totožná s množinou uzlů GTR 2. z uzlu u vede do uzlu v (v ^ u) hrana právě tehdy, když v grafu toku řízení existuje cesta z uzlu u do uzlu v taková, že DK(u) neleží na této cestě. Informaci potřebnou pro sestrojení grafu vlivu větvení získáme analogickým způsobem jako pro informační graf. Pro každý příkaz u nás zajímá množina INFL(u) příkazů p z nichž vede cesta do příkazu u taková, že neobsahuje příkaz DK(p). Řešíme tedy systém Obr. 14 Graf toku řízení Graf vlivu větvení INFL(s) = 0 INFL(u) (J {(INFL(v) n NOTKILLiyv)) U GEN (v)} vePRED(u) kde 1. s je počáteční uzel GTŘ 2. NOTKILL{v) je množina příkazů p, pro něž DK(p) ^ v 3. GEN (v) = {v} pro větvící příkazy v, jinak GEN (v) = 0 37 Z množin INFL(u) pak snadno sestrojíme pro každý příkaz p množinu BRANCH(p) = (INFL(p) n NOTKILL(p)) - {p} V grafu vlivu větvení vede hrana z uzlu u do v právě tehdy, když u G BRANCH(v). 7.5 Výřezy programů Výřez programu je (na intuitivní úrovni) program, který bude obsahovat z příkazů původního programu jen ty, které mají vliv na jisté zvolené vlastnosti programu v době běhu. Při konstrukci výřezu S programu P vycházíme z nějaké množiny příkazů původního programu, jejichž potřebnost bude apriori explicitně či implicitně indukována sledovanými hledisky. Úspěšné provedení těchto příkazů může záviset na provedení jiných příkazů, které počítají hodnoty proměnných v nich referencovaných či vybírají větev, po které se dospěje, resp. nedospěje k jejich provedení. Potřebnost příkazů vzhledem ke sledovaným aspektům se tedy bude šířit grafem toku řízení opět prostřednictvím informací obsažených v informačním grafu a v grafu vlivu větvení. Nepotřebné (z daného hlediska) příkazy pak z programu P vypustíme tak, aby vzniklý výřez S byl programem, který má zvolené vlastnosti (téměř) totožné s původním programem. Uveďme algoritmus, který k množině AUST apriori potřebných příkazů nalezne množinu UST všech potřebných příkazů. Všimněme si, že za vždy potřebné budeme považovat všechny příkazy zastavení. Algoritmus SUST-hledání potřebných příkazů Vstup: 1) A t/5T-množina apriori potřebných příkazů 2) množiny DEFS(x,v), BRANCHfa) Výstup: množina UST všech potřebných příkazů begin UST:= 0; POM := AUST; while POM ^ 0 do nechť p je libovolný příkaz z POM; POM := POM {p}; UST:= UST U {p}; for each q G DEFS(x,v) U BRANCHfa) do if q i UST then POM := POM U {q} fi; od; od; UST := UST U {p : p je koncový příkaz (zastavení)} end. Vyjasněme otázku, jak vypouštět z grafu toku řízení G = (N, E, s) programu P příkazy, které nepatří do množiny potřebných příkazů UST. Je dokázáno, že (je- 38 li N — UST ^ 0 ) existuje a dá se nalézt rozklad množiny N — UST s těmito vlastnostmi: 1. neexistuje hrana e, která v G vede z uzlu patřícího do jedné třídy rozkladu do uzlu patřícího do jiné třídy; 2. pro každou třídu T rozkladu existuje právě jeden uzel u g UST takový, že do něj vedou hrany z uzlů množiny T. Vypuštění nepotřebných příkazů z grafu toku řízení G můžeme tedy realizovat tak, že pro každou třídu T vypustíme podgraf indukovaný množinou uzlů T, hrany, které vedou z uzlů množiny T do nějakého (právě jednoho) uzlu u z UST, a hrany, které vedou z uzlů množiny UST do uzlů množiny T nahradíme hranami vedoucími do uzlu u. Tím je výřez programu zkonstruován. Konstrukce je korektní, výřez je programem. Ilustrujme nyní zavedené pojmy a postupy. Uvažujme program P na obr. 15 a množinu apriori potřebných příkazů AUST = {1,7,8,11,13}. Algoritmem SUST nalezená množina všech potřebných příkazů je UST = {1, 3,4, 7, 8,11,12,13,14}. Hledaný rozklad množiny N — UST je {2}, {5,6}, {9,10}. Odpovídající výřez je rovněž na obr. 16. ® readjx,y) (2) z:=f(x) ® t:=f(y)- ® read(x,y) © s(x) -© halt(y,z) @ halt Obr. 15 Program P Obr. 16 Výřez S programu P 39 První důležitou vlastností libovolného výřezu S programu P (odvoditelnou z konstrukce výřezu) je, že pro libovolná vstupní data vždy, když program P zastaví, pak výřez S rovněž zastaví (pro tatáž vstupní data). Obrácená implikace neplatí: zacyklí-li se např. program P na obr. 15 v cyklu tvořeném příkazy 5 a 6, jeho výřez S může zastavit. Tuto vlastnost výřezů musíme mít vždy na paměti při aplikacích výřezů. Při formulaci dalších vlastností výřezů budeme pracovat s pojmem výpočetní posloupnosti programu P pro daná vstupní data. Pro tento účel budeme výpočetní posloupností rozumět posloupnost stavů, kde stav je dán hranou (místem v programu) GTŘ (vedoucí z příkazu, který byl právě proveden, do příkazu, který má být právě proveden), uzlem do kterého tato hrana vede a posloupností momentálních hodnot proměnných. Stav výpočtu je tedy dán čítačem instrukcí (zdvojeným) a stavem paměti. Vraťme se k vlastnostem výřezů. Uvažujme výpočetní posloupnost L programu P pro nějaká vstupní data a výpočetní posloupnost T jeho výřezu S pro táž data. Vypusťme z posloupnosti L programu P všechny stavy, které v čítači instrukcí obsahují uzly (nepotřebné příkazy), které nejsou ve výřezu S. Pokud se program P nezacyklil v nepotřebných příkazech, pak takto upravená posloupnost —označme ji LL— koresponduje s posloupností T výřezu S následujícím způsobem. V i-tém prvku posloupnosti LL je v čítači instrukcí tentýž uzel jako v i-tém prvku posloupnosti T, tudíž je v obou případech prováděn týž příkaz a navíc hodnoty proměnných referencovaných v tomto příkazu jsou opět v obou stavech shodné. Tato vlastnost, spolu s prvně uvedenou, již umožňují některé aplikace výřezů. Klasická optimalizační metoda, eliminace mrtvého kódu, spočívá v konstrukci výřezu programu, přičemž za množinu apriori potřebných příkazů zvolíme množinu všech výstupních příkazů programu. Výřez, oproštěný od neproduktivního kódu je pak v důsledku vlastností výřezu funkčně ekvivalentní výchozímu programu, až na ano-mální případy, kdy se program zacyklí právě v neproduktivním kódu. Aplikace výřezů (odvozené z dosud uvedených vlastností) v procesu testování a ladění programů jsou vhodné zejména v situacích, kdy programátora nezajímají ani tak výstupní hodnoty produkované programem, ale spíše tok řízení a příkazy, které tok řízení přímo či zprostředkovaně ovlivňují. Testujeme-li pouhé zastavení programu pro různá vstupní data, poskytne nám stejné služby jako program, ale v mnoha případech laciněji tzv. stop-výřez programu. Stop-výřez programu je výřez, který obdržíme, když za množinu apriori potřebných příkazů zvolíme množinu všech východů z cyklů. Východem z cyklu nazveme uzel v takový, že v GTŘ existuje cesta z uzlu v do uzlu v taková, že neobsahuje uzel DK(v) - nejbližší dominátor vzhledem ke konci. Pro daná vstupní data stop-výřez zastaví právě tehdy, když zastaví původní program pro tatáž data. Stop-výřez programu z obr. 15 je [1] read(x); repeat [11] x:=f(x) until [12] s(x); [14] halt. Zajímá-li nás v daném okamžiku, které příkazy a jakým způsobem souvisí s tokem řízení při výpočtu, pak je k dispozici tzv. řídící výřez programu, což je výřez, který obdržíme, vezmeme-li za množinu apriori potřebných příkazů množinu všech 40 testovacích příkazů. Řídící výřez stejně jako stop-výřez zastaví pro daná data právě tehdy, když pro tato data zastaví program a je vhodný pro testování i studium řídící části programu. Může být např. nápomocen i při hledání vhodných množin vstupních dat. Podaří-li se nám totiž nalézt takovou množinu vstupů pro řídící výřez, že každá hrana jeho GTŘ se vyskytuje ve výpočetní posloupnosti pro nějaká data z této množiny, pak máme zaručeno, že i každá hrana (a tedy i příkaz) původního programu se vyskytuje ve výpočetní posloupnosti pro nějaká data z nalezené množiny. V mnoha situacích, s nimiž se setkáváme při testování a ladění, nás v první řadě zajímají vedle toku řízení i proměnné, speciálně pak čím jsou ovlivňovány hodnoty, kterých mohou nabývat, když výpočet dospěje do určitých míst programu. Předpokládejme, že náš zájem tohoto druhu je specifikován kritériem C, což je množina tzv. elementárních kritérií c=(e,V), kde e je hrana GTŘ (místo v programu), V nějaká množina proměnných. I nyní můžeme použít výřezů programu, ale na rozdíl od předešlých aplikací v tomto případě z formulace požadavku nevyplývá tak přímočaře charakteristika množiny apriori potřebných příkazů. Pro její nalezení použijeme informace poskytnuté ATD. Protože elementární kriterium c = (e, V) vyjadřuje zájem o hodnoty proměnných množiny V v místě programu e, budou nutně součástí množiny potřebných příkazů AUST všechny příkazy p, které přiřazují hodnotu nějaké proměnné z V a jsou dosažitelné na hraně e (p G REACHES(e) ). Ze zřejmých důvodů bude třeba zařadit do AUST ty testovací příkazy p, z nichž vede v GVV hrana do počátečního uzlu hrany e (označme ho w) a příkaz w v případě, že je testovacím příkazem. Formálně zapsáno, definujme pro elementární kriterium c množinu AUST(c) = {p\pe REACHES(e) A Df (p) n V ^ 0} u BRANCH(w) U U if w je testovací příkaz then {w} else 0. Množina apriori potřebných příkazů AUST pro zadané kriterium C je AUST(C) = = \J{AUST(c) | c G C}. Pro ilustraci se vraťme k programu na obr. 15 a zvolme kriterium C = {(e, {x, y}), (c, {x})}. Pak AUST ((e, {x, y})) = {1,7,13} U {12} U {8}, AUST((c, {x})) = {1,11} U {8,12} U 0, AUST(C) = {1, 7, 8,11,12,13}. Příslušný výřez S je na obr. 16. Po nalezení množiny AUST ke kriteriu C, což umožňuje zkonstruovat příslušný výřez, zbývá řešit ještě další problém. V uvedeném příkladě si všimněme, že ve výřezu není např. hrana c, která figuruje v kriteriu C. Vyvstává otázka, která místa (hrany) ve výřezu S odpovídají hraně c programu P. Každé hraně e programu P proto přiřadíme podmnožinu CORE(e) množiny hran výřezu S takto: Hrana g výřezu S je prvkem CORE(e) právě tehdy, když v GTŘ programu P existuje cesta z počátečního uzlu hrany g do koncového uzlu hrany g taková, že hrana e leží na této cestě a žádné vnitřní uzly této cesty nepatří do výřezu S. Z definice vyplývá, že patří-li hrana e rovněž do výřezu S, pak CORE(e) = {e}. Jako příklad vezměme opět program P a jeho výřez S na obr. 15 a 16. Zde platí CORE(d) = {d}, CORE(c) = {a}, CORE(e) = {e}, CORE(ť) = {a,e}, atd. Uvažujme výpočetní posloupnost L programu P pro nějaká vstupní data a vý- 41 početní posloupnost T (pro tatáž data) jeho výřezu S, zkonstruovaného na základě kriteria C. Pro libovolné elementární kriterium c = (e, V) z C označme jako L(c) posloupnost, kterou obdržíme z posloupnosti L vypuštěním všech stavů, které v čítači instrukcí obsahují hranu různou od hrany e, a jako T(c) posloupnost, kterou obdržíme z T, vypuštěním všech stavů, které v čítači instrukcí obsahují hranu nepatřící do CORE(e). Pak pro i-té prvky posloupností L(c) a T(c) platí, že v nich hodnoty proměnných množiny V jsou totožné. Zajímají-li nás hodnoty proměnných množiny V vždy před provedením příkazu p programu P nezávisle na tom, po které hraně výpočet k příkazu p dospěl, zařadíme do kritéria C elementární kritéria pro všechny vstupní hrany uzlu p, vždy ve dvojici s množinou V. Vlastnost příslušného výřezu musíme formulovat poněkud komplikovaněji s ohledem na to, že příkaz p nemusí být obsažen ve výřezu (viz např. uzel 10 na obr. 15). Označme L(p) posloupnost obdrženou z L vypuštěním stavů, které neobsahují v čítači instrukcí uzel p, a jako T(p) posloupnost obdrženou z T vypuštěním stavů, které v čítači instrukcí obsahují hranu nepatřící do CORE(e) pro žádnou vstupní hranu e příkazu p. Pro i-té prvky posloupností L(p) a T(p) platí, že hodnoty proměnných množiny V jsou totožné. Neformálně lze vlastnosti výřezu S programu P formulovat tak, že prohlížíme-li výpočetní posloupnosti L programu P a T výřezu S komparativním mikroskopem, který provádí příslušné selekce výpočetních posloupností a navíc umožňuje vidět pouze hodnoty určených proměnných, nerozlíšime je navzájem. Všechny uvedené vlastnosti výřezů otevírají široké aplikační možnosti vždy, kdy nás z nejrůznějších důvodů zajínají ty aspekty chování programu, které lze charakterizovat prostřednictvím množiny apriori potřebných příkazů resp. nějakým výře-zovým kritériem. Za těchto okolností je výhodnější z hlediska vynakládaného intelektuálního úsilí a strojového času pracovat s příslušným výřezem, který je co do sledovaných aspektů chování ekvivalentem původního programu a může být co do počtu příkazů a proměnných podstatně jednodušší než program sám. Nezbytnou podmínkou aplikace výřezů v praxi je ovšem existence automatického generátoru výřezů. V tomto směru se jeví jako perspektivní využití (existujících) systémů pro manipulaci s programy ve formě grafů, jejichž představitelem je např. systém TPT [BeŠ84]. Nadstavbové komponenty tohoto systému realizují převod programů zapsaných v jazycích Pascal nebo Fortran do sítě, která obsahuje odpovídající graf volání, grafy toku řízení a graf syntaktický a lexikální se všemi atributy potřebnými k provádění analýzy toku dat. Systém rovněž umožňuje po manipulaci s těmito grafy zpětnou tranformaci do zdrojových jazyků, což je v případě výřezů dosti podstatné: výřezy je nutné produkovat ve formě vhodné jak pro uživatele, tak pro další zpracování na počítači, a tou je právě zdrojový text. Literatura [Aho76] Aho,A. V.-Ullman,J.D: Node Listing for Reducible Flow Graphs. JCSS,13, 1976. 42 [A1172] Allen,F.E.-Cocke, J.: A Catalogue of Optimizing Transformation. In:Randall,R.(ed.): Design and Optimization of Compilers, Prentice-Hall, 1972. [A1176] Allen,F.E.-Cocke,J.\ A Program Data Flow Procedure, CACM 19, 1976. [Bab78] Babich, W.A.-Jazayeri,M.\ The Method for Data Flow Analysis. Acta In-formatica,10, 1978, s.265-272. [Bar78] Barth, J.M.: A Practical Interprocedural Data Flow Analysis Algorithm. CACM,21, 1978. [BeŠ84] Benešovský,M.-Smídek,M.\ Testování programů. In: sborník SOFSEM'84, VUSEI-AR Bratislava, 1984. [Cho82] Chow,A.-Rudmik,A.\ The Design of Data Flow Analyzer. SIGPLAN Not.,17, 1982, č.6, s.106-113. [Cla81] Clarke,L.A.-Richardson,.