Kontrollflödesgraf ( engelska c control flow graph , CFG ) - i kompileringsteori - uppsättningen av alla möjliga sätt att exekvera ett program, representerade som en graf .
I kontrollflödesgrafen motsvarar varje nod (vertex) i grafen ett grundblock - en rätlinjesektion av kod som inte innehåller vare sig kontrollöverföringsoperationer eller punkter till vilka kontroll överförs från andra delar av programmet. Det finns bara två undantag:
Riktade bågar används i en graf för att representera hoppinstruktioner. I de flesta implementeringar läggs två specialiserade block till:
CFG-strukturen är viktig för många kompilatoroptimeringar och för statiska kodanalysverktyg .
Två fall är möjliga: ett block eller subgraf saknas:
Ett block som inte är associerat med ett inmatningsblock anses vara oåtkomligt ("död" kod). Reachability är en av grafegenskaperna som används vid optimeringar. Ett oåtkomligt block kan tas bort från programmet.
Ett block som inte är associerat med ett utgångsblock innehåller en oändlig loop. Att förlita sig på detta uttalande är det inte möjligt att upptäcka alla oändliga loopar på grund av stoppproblemet .
När du utför optimeringar kan kompilatorn skapa både "död" kod och oändliga slingor, även om programmeraren inte uttryckligen kodade den. Till exempel , efter att ha utfört konstant vikning och konstant fortplantning , kan optimering av hoppgängning slå samman flera block till ett; som ett resultat kan vissa kanter försvinna och vissa block kanske inte är kopplade till grafen.
Följande termer används ofta när man arbetar med kontrollflödesdiagram.
kant riktade kant (eller båge) anslutande grafblock. Entry block , entry block, start block blocket från vilket en väg börjar. Exit block , exit block blocket som slutar vilken väg som helst. Bakkant en kant som pekar mot föregående block, det vill säga blocket som skulle ha passerats tidigare i processen att korsa grafen på djupet . kritisk kant en kant som kommer från ett block med flera utgående kanter och går in i ett block med flera inkommande kanter. Onormal kant en kant som går ut från ett block och inte går in i ett annat block på grund av omöjligheten att beräkna det senare. Uppstår till exempel efter transformationen av en undantagshanteringskonstruktion . Sådana kanter stör optimeringar. Omöjlig kant en kant som läggs till en graf enbart för att bevara grafens egenskap att utdatablocket är postdominerat över vilket annat block som helst. Denna kant kan inte passeras. Dominator , dominator, obligatorisk föregångare Block M sägs vara dominant över block N om någon väg från ingångsblocket till block N går genom block M. Ingångsblocket dominerar alla andra block i grafen. Postdominator , postdominator Block M sägs vara postdominant över block N om någon väg från N till utgångsblocket passerar genom block M. Utmatningsnoden postdominerar över alla block i grafen. Omedelbar dominator , omedelbar dominator Ett block M sägs vara direkt dominant block N om block M dominerar block N, och det inte finns något annat mellanblock P som domineras av block M och dominerar block N. Med andra ord är M den sista dominatorn i några vägar från ingångsblocket till block N Varje block utom ingången har en enda omedelbar dominator. Omedelbar postdominator en analog till termen omedelbar dominator , men för en postdominator. Dominatorträd _ en extra träddatastruktur som innehåller information om dominansförhållanden. En gren från block M till block N skapas om och endast om block M är den omedelbara dominatorn för N. Datastrukturen är ett träd, eftersom vilket block som helst har en unik omedelbar dominator. Trädets rot är ingångsnoden. Den effektiva Lengauer-Tarjans algoritm används för konstruktion . Postdominatorträd _ analog till dominatorträdet , men för postdominatorer. Trädets rot är utgångsblocket. Loop header , loop header, loop ingångspunkt ett block anslutet med kanter till alla block i cykelkroppen. Blocket dominerar alla noder i slingkroppen. Loop pre-header ett block förbundet med en kant till slinghuvudblocket ; omedelbar dominator för loop-ingångspunkt. Låt blocket M vara ingångspunkten för slingan. För vissa optimeringsfaser är det fördelaktigt att M-blocket delas upp i två block: M pre (loophuvud) och M loop (loophuvud). Efter att blocket M har delats, överförs dess innehåll och bakkanter till M - loopblocket , och de återstående kanterna överförs till M - förblocket ; sedan skapas en ny kant som förbinder M - förblocket med M - loopblocket ; sålunda blir M - förblocket den direkta dominatorn för M - loopblocket . M - förblocket kommer inte att innehålla någon kod förrän vissa optimeringar, såsom loop-invariant kodrörelse , slutför innehållet .För kodavsnitt:
0: (A)t0 = read_num 1: (A) om t0 mod 2 == 0 går till 4 2: (B) skriv ut t0 + " är udda." 3: (B) gå till 5 4: (C) skriv ut t0 + "är jämnt." 5: (D) slutprogramStyrflödesdiagrammet kommer att bestå av 4 grundläggande block: A för linje 0-1, B för linje 2-3, C för linje 4 och D för 5:e raden. Grafen kommer att ha bågar A -> B, A -> C, B -> D, C -> D.