kontrollflytgrafer

Kontrollflytgrafer (CFG) er en grafisk representasjon av mulig kontrollflyt i et program eller en funksjon. I en CFG er hver node en grunnblokk, som er en sekvens av instruksjoner uten avbryting i midten, og kantene viser hvordan kontrollen kan flyte fra en blokk til en annen. Startnoden representerer program- eller funksjonens start, mens en avslutningsnode representerer slutten. Kantene tar hensyn til fall-through ved vanlig rekkefølge, betingede og ubetingede hopp, samt unntakshåndtering og kall til andre funksjoner i utvidede varianter.

Bygging og struktur: En CFG genereres vanligvis fra en mellomliggende representasjon av programmet. Grunnblokker identifiseres gjennom kontrollstrømmen, og kantene kobler blokker basert på kontrolloverføringer som betingede grener, ubetydelige hopp og etter hvert programkall. Enkelte språk og verktøy inkluderer også kanter for unntakshåndtering, noe som gir et mer nyansert bilde av kontrollflyten.

Bruksområder og egenskaper: CFG-er brukes i kompilatorer og statiske analyseverktøy for å støtte optimeringer (som dødkode-eliminering, konstantpropagering og registerallokering), feilsøking, programforståelse og måling av kompleksitet. En vanlig måling er sirkulær kompleksitet, som kan beregnes fra antall kanter og noder i grafen. CFG-er kan også brukes i interprosedyre analyser, der hele programmet sees som en samling av koblede CFG-er.

Begrensninger: CFG-er er en kontekstfri representasjon av kontrollflyt og fanger ikke alle dataflyt- eller avhengighetsaspekter ved programmet. De kan også trenge utvidelser for å håndtere komplekse unntakshåndteringsmønstre eller asynkron kontrollflyt. Til tross for begrensningene er CFG en grunnleggende byggestein i moderne programanalyse og kompilering.