Control flow graph ( angolul c control flow graph , CFG ) - a fordításelméletben - a program végrehajtásának összes lehetséges módjának halmaza, gráfként ábrázolva .
A vezérlési folyamatgráfban a gráf minden csomópontja (csúcs) egy alapblokknak felel meg - egy egyenes vonalú kódszakasznak, amely nem tartalmaz sem vezérlésátviteli műveleteket, sem pontokat, amelyekre a vezérlés a program más részeiből kerül át. Csak két kivétel van:
Az irányított íveket a grafikonokban az ugrási utasítások ábrázolására használjuk. Ezenkívül a legtöbb megvalósításban két speciális blokkot adnak hozzá:
A CFG struktúra számos fordítóoptimalizálás és statikus kódelemző segédprogram számára fontos .
Két eset lehetséges: hiányzik egy blokk vagy részgráf:
A bemeneti blokkhoz nem társított blokk elérhetetlennek minősül ("halott" kód). Elérhetőség az optimalizálás során használt gráftulajdonságok egyike. Egy elérhetetlen blokk eltávolítható a programból.
A kimeneti blokkhoz nem társított blokk végtelen hurkot tartalmaz. Erre az állításra támaszkodva a leállási probléma miatt nem lehet minden végtelen hurkot észlelni .
Az optimalizálás végrehajtásakor a fordító képes "halott" kódot és végtelen ciklusokat is létrehozni, még akkor is, ha a programozó nem kódolta kifejezetten. Például az állandó hajtás és állandó terjedés végrehajtása után az ugrásos szálfűzés optimalizálása több blokkot egyesíthet egybe ; ennek eredményeként előfordulhat, hogy egyes élek eltűnnek, és egyes blokkok nem kapcsolódnak a gráfhoz.
A következő kifejezéseket gyakran használják a vezérlőfolyamat-grafikonokkal végzett munka során.
él irányított él (vagy ív) összekötő gráfblokkokat. Belépési blokk , belépési blokk, kezdőblokk az a blokk, ahonnan bármely út kiindul. Kilépési blokk , kilépési blokk a blokk, amely bármely utat lezár. Hátsó él egy él, amely az előző blokkra mutat, vagyis arra a blokkra, amelyet a gráf mélységi bejárása során korábban bejártak volna . kritikus él olyan él, amely több kimenő éllel rendelkező blokkból származik, és több bejövő éllel rendelkező blokkba lép be. Rendellenes él az egyik blokkból kilépő és egy másik blokkba be nem lépő él az utóbbi kiszámításának lehetetlensége miatt. Előfordul például egy kivételkezelő konstrukció átalakítása után . Az ilyen élek zavarják az optimalizálást. Lehetetlen él egy él, amelyet a gráfhoz csak azért adnak hozzá, hogy megőrizzék a gráf azon tulajdonságát, hogy a kimeneti blokk utódomináns legyen bármely más blokkhoz képest. Ezen az élen nem lehet áthaladni. Dominator , dominator, kötelező előd Az M blokkot dominánsnak mondjuk az N blokkkal szemben, ha a bemeneti blokktól az N blokkig tartó bármely út áthalad az M blokkon. A bemeneti blokk uralja a gráf összes többi blokkját. Posztdominátor , posztdominátor Az M blokkot utólagos dominánsnak nevezzük az N blokkhoz képest, ha az N-ből a kimeneti blokkba vezető bármely út áthalad az M blokkon. A kimeneti csomópont utódominál a gráf összes blokkja felett. Azonnali uralkodó , azonnali uralkodó Egy M blokkot közvetlenül domináns N blokknak mondjuk, ha az M blokk uralja az N blokkot, és nincs másik köztes P blokk, amelyet az M blokk uralna és dominálna az N blokkban. Más szóval, M az utolsó domináns bármely útvonalon a bemeneti blokk az N blokkhoz A bemenet kivételével minden blokknak egyetlen közvetlen dominátora van. Azonnali posztdominátor az azonnali dominator kifejezés analógja , de posztdominátorra. Dominator fa egy segédfa adatstruktúra , amely a dominancia kapcsolatokról tartalmaz információkat. Az M blokktól az N blokkig tartó elágazás akkor és csak akkor jön létre, ha az M blokk az N közvetlen dominánsa. Az adatstruktúra egy fa, mivel minden blokknak van egyedi közvetlen dominátora. A fa gyökere a bemeneti csomópont. A hatékony Lengauer-Tarjan algoritmust használjuk az építéshez . Posztdominátor fa a dominatorfa analógja , de posztdominátorok számára. A fa gyökere a kimeneti blokk. Hurokfejléc , hurokfejléc, hurok belépési pontja olyan blokk, amely élekkel kapcsolódik a ciklustest összes blokkjához. A blokk uralja a huroktest összes csomópontját. Hurok előfejléc egy blokk, amely éllel kapcsolódik a hurokfejléc blokkhoz ; hurok belépési pont közvetlen dominátora. Legyen az M blokk a hurok belépési pontja. Egyes optimalizálási fázisoknál előnyös, ha az M blokkot két blokkra osztjuk: M pre (hurok fejléc) és M loop (hurok fejléc). Az M blokk felosztása után annak tartalma és hátsó élei átkerülnek az M hurokblokkba , a fennmaradó élek pedig az M előblokkba ; ekkor egy új él jön létre, amely összeköti az M pre -blokkot az M hurokblokkkal ; így az M előblokk az M hurokblokk közvetlen dominánsává válik . Az M pre -blokk nem tartalmaz kódot mindaddig, amíg bizonyos optimalizálások, például a ciklusinvariáns kódmozgás be nem fejezik a tartalmát .A kódrészlethez:
0: (A)t0 = olvasási_szám 1: (A) ha t0 mod 2 == 0 lett 4 2: (B) print t0 + " páratlan." 3: (B) 5 4: (C) print t0 + "páros." 5: (D) program végeA vezérlőfolyamat grafikonja 4 alapvető blokkból áll: A a 0-1 sorokhoz, B a 2-3 sorokhoz, C a 4-hez és D az 5. sorhoz. A grafikon ívei A -> B, A -> C, B -> D, C -> D.