Kontrolflowgraf ( engelsk c control flow graph , CFG ) - i kompileringsteori - sættet af alle mulige måder at udføre et program på, repræsenteret som en graf .
I kontrolflowgrafen svarer hvert knudepunkt (vertex) af grafen til en grundlæggende blok - et lige linjeafsnit af kode, der ikke indeholder hverken kontroloverførselsoperationer eller punkter, hvortil kontrol overføres fra andre dele af programmet. Der er kun to undtagelser:
Rettede buer bruges i en graf til at repræsentere springinstruktioner. I de fleste implementeringer tilføjes to specialiserede blokke:
CFG-strukturen er vigtig for mange compiler-optimeringer og for statiske kodeanalyseværktøjer .
To tilfælde er mulige: en blok eller undergraf mangler:
En blok, der ikke er knyttet til en inputblok, anses for at være uopnåelig ("død" kode). Reachability er en af de grafegenskaber, der bruges i optimeringer. En uopnåelig blok kan fjernes fra programmet.
En blok, der ikke er knyttet til en outputblok, indeholder en uendelig sløjfe. Ved at stole på denne erklæring er det ikke muligt at detektere alle uendelige sløjfer på grund af standsningsproblemet .
Når du udfører optimeringer, kan compileren skabe både "død" kode og uendelige loops, selvom programmøren ikke eksplicit kodede det. For eksempel , efter at have udført konstant foldning og konstant udbredelse , kan jump threading optimering flette flere blokke til én; som følge heraf kan nogle kanter forsvinde, og nogle blokke er muligvis ikke forbundet med grafen.
Følgende udtryk bruges ofte, når man arbejder med kontrolflowgrafer.
kant rettet kant (eller bue) forbinder grafblokke. Indgangsblok , indgangsblok, startblok den blok, hvorfra enhver sti starter. Udgangsblok , udgangsblok den blok, der afslutter enhver sti. Bagkant en kant, der peger på den foregående blok, det vil sige den blok, der ville være blevet krydset tidligere i processen med at krydse grafen i dybden . kritisk kant en kant, der stammer fra en blok med flere udgående kanter og går ind i en blok med flere indgående kanter. Unormal kant en kant, der går ud fra en blok og ikke går ind i en anden blok på grund af umuligheden af at beregne sidstnævnte. Opstår for eksempel efter transformationen af en undtagelseshåndteringskonstruktion . Sådanne kanter forstyrrer optimeringer. Umulig kant en kant tilføjet til en graf udelukkende for at bevare grafens egenskab, at outputblokken er postdomineret over enhver anden blok. Denne kant kan ikke krydses. Dominator , dominator, obligatorisk forgænger Blok M siges at være dominerende over blok N, hvis nogen vej fra inputblokken til blok N går gennem blok M. Inputblokken dominerer alle andre blokke i grafen. Postdominator , postdominator Blok M siges at være post-dominant over blok N, hvis en hvilken som helst vej fra N til outputblokken passerer gennem blok M. Outputknudepunktet post-dominerer over alle blokke i grafen. Umiddelbar dominator , umiddelbar dominator En blok M siges at være direkte dominerende blok N, hvis blok M dominerer blok N, og der ikke er nogen anden mellemblok P, der er domineret af blok M og dominerer blok N. Med andre ord er M den sidste dominator i nogen stier fra inputblokken til blok N Hver blok undtagen input har en enkelt umiddelbar dominator. Umiddelbar postdominator en analog af udtrykket umiddelbar dominator , men for en postdominator. Dominator træ en hjælpetrædatastruktur , der indeholder information om dominansforhold. En gren fra blok M til blok N oprettes, hvis og kun hvis blok M er den umiddelbare dominator af N. Datastrukturen er et træ, da enhver blok har en unik øjeblikkelig dominator. Træets rod er inputknudepunktet. Den effektive Lengauer-Tarjans algoritme bruges til konstruktion . Postdominator træ analog til dominatortræet , men for postdominatorer. Træets rod er outputblokken. Loop header , loop header, loop indgangspunkt en blok forbundet med kanter til alle blokke af cykellegemet. Blokken dominerer alle noder i løkkelegemet. Loop pre-header en blok forbundet med en kant til løkkehovedblokken ; umiddelbar dominator for sløjfeindgangspunkt. Lad blokken M være sløjfeindgangspunktet. For nogle optimeringsfaser er det fordelagtigt, at M-blokken opdeles i to blokke: M pre (loop header) og M loop (loop header). Efter blok M er opdelt, overføres dens indhold og bagkanter til M -løkkeblokken , og de resterende kanter overføres til M - præblokken ; derefter oprettes en ny kant, der forbinder M - præblokken med M -løkkeblokken ; således bliver M pre -blokken den direkte dominator af M -løkkeblokken . M - præblokken vil ikke indeholde nogen kode, før nogle optimeringer, såsom loop-invariant kodebevægelse , fuldfører dens indhold .For kodestykke:
0: (A)t0 = read_num 1: (A) hvis t0 mod 2 == 0 går til 4 2: (B) print t0 + " er ulige." 3: (B) gå til 5 4: (C) print t0 + "er lige." 5: (D) slutprogramKontrolflowgrafen vil bestå af 4 grundlæggende blokke: A for linje 0-1, B for linje 2-3, C for linje 4 og D for 5. linje. Grafen vil have buer A -> B, A -> C, B -> D, C -> D.