Graf toku řízení ( anglicky c control f low graph, CFG ) - v teorii kompilace - množina všech možných způsobů provádění programu, znázorněná jako graf .
V grafu toku řízení každý uzel (vrchol) grafu odpovídá základnímu bloku - přímkovému úseku kódu, který neobsahuje ani operace přenosu řízení, ani body, na které se přenáší řízení z jiných částí programu. Existují pouze dvě výjimky:
Nasměrované oblouky se používají v grafu k znázornění instrukcí skoku. Ve většině implementací jsou také přidány dva specializované bloky:
Struktura CFG je důležitá pro mnoho optimalizací kompilátoru a pro nástroje pro analýzu statického kódu .
Jsou možné dva případy: chybí blok nebo podgraf:
Blok, který není spojen se vstupním blokem, je považován za nedosažitelný ("mrtvý" kód). Dosažitelnost je jednou z vlastností grafu používaných při optimalizacích. Nedosažitelný blok lze z programu odstranit.
Blok, který není spojen s výstupním blokem, obsahuje nekonečnou smyčku. Spoléháme-li se na toto prohlášení, není možné detekovat všechny nekonečné smyčky kvůli problému zastavení .
Při provádění optimalizací může kompilátor vytvořit jak „mrtvý“ kód, tak nekonečné smyčky, i když to programátor výslovně nekódoval. Například po provedení konstantního skládání a konstantního šíření může optimalizace přeskakování sloučit několik bloků do jednoho; v důsledku toho mohou některé hrany zmizet a některé bloky nemusí být spojeny s grafem.
Následující termíny se často používají při práci s grafy řídicích toků.
okraj orientovaná hrana (nebo oblouk) spojující bloky grafu. Vstupní blok , vstupní blok, startovací blok blok, ze kterého začíná jakákoli cesta. Výjezdový blok , výjezdový blok blok, který ukončuje jakoukoli cestu. Zadní okraj hrana směřující k předchozímu bloku, to jest blok, který by byl prošel dříve v procesu procházení grafu do hloubky . kritická hrana hrana, která pochází z bloku s více výstupními hranami a vstupuje do bloku s více vstupními hranami. Abnormální okraj hrana vycházející z jednoho bloku a nevstupující do jiného bloku kvůli nemožnosti vypočítat druhý blok. Vyskytuje se například po transformaci konstruktu zpracování výjimek . Takové hrany narušují optimalizace. Nemožná hrana hrana přidaná do grafu pouze pro zachování vlastnosti grafu, že výstupní blok je postdominován nad jakýmkoli jiným blokem. Tuto hranu nelze přejít. Dominátor , dominátor, povinný předchůdce Blok M je považován za dominantní nad blokem N, pokud jakákoli cesta ze vstupního bloku do bloku N prochází blokem M. Vstupní blok dominuje všem ostatním blokům v grafu. Postdominátor , postdominátor O bloku M se říká , že je post-dominantní nad blokem N, pokud jakákoli cesta z N do výstupního bloku prochází blokem M. Výstupní uzel post-dominuje nad všemi bloky grafu. Bezprostřední vládce , bezprostřední vládce O bloku M se říká , že je přímo dominantním blokem N, pokud blok M dominuje bloku N a neexistuje žádný jiný meziblok P, kterému dominuje blok M a dominuje bloku N. Jinými slovy, M je posledním dominátorem v jakékoli cestě od vstupní blok do bloku N Každý blok kromě vstupu má jednoho bezprostředního dominanta. Okamžitý postdominátor analoga termínu bezprostřední dominátor , ale pro postdominátora. Dominátorský strom pomocná stromová datová struktura obsahující informace o vztazích dominance. Větev z bloku M do bloku N se vytvoří tehdy a pouze tehdy, když je blok M bezprostředním dominátorem N. Datová struktura je stromová, protože každý blok má jedinečného bezprostředního dominanta. Kořenem stromu je vstupní uzel. Pro konstrukci je použit efektivní Lengauer-Tarjanův algoritmus . Postdominátorský strom analog dominátorského stromu , ale pro postdominátory. Kořenem stromu je výstupní blok. Záhlaví smyčky, záhlaví smyčky, vstupní bod smyčky blok spojený hranami se všemi bloky těla cyklu. Blok dominuje všem uzlům těla smyčky. Předzáhlaví smyčky blok připojený okrajem k bloku záhlaví smyčky ; okamžitý dominant pro vstupní bod smyčky. Nechť je blok M vstupním bodem smyčky. Pro některé fáze optimalizace je výhodné, aby byl blok M rozdělen na dva bloky: M pre (hlavička smyčky) a M smyčka (hlavička smyčky). Po rozdělení bloku M se jeho obsah a zadní hrany přenesou do bloku smyčky M a zbývající hrany se přenesou do předbloku M ; pak se vytvoří nová hrana spojující M předblok s M smyčkovým blokem ; tak se M preblok stává přímým dominantem M smyčkového bloku . Preblok M nebude obsahovat žádný kód, dokud jeho obsah nedokončí některé optimalizace , jako je pohyb kódu invariantní smyčky .Pro fragment kódu:
0: (A)t0 = read_num 1: (A) pokud t0 mod 2 == 0 goto 4 2: (B) tisk t0 + "je liché." 3: (B) přejděte na 5 4: (C) tisk t0 + "je sudé." 5: (D) ukončení programuGraf řídicího toku se bude skládat ze 4 základních bloků: A pro čáry 0-1, B pro čáry 2-3, C pro čáru 4 a D pro 5. řádek. Graf bude mít oblouky A -> B, A -> C, B -> D, C -> D.