Kontrollflödesgraf

Ett kontrollflödesgraf (CFG) är en riktad graf som används inom programanalys och kompilatordesign för att representera ett programs kontrollflöde. I ett CFG motsvarar noderna basic blocks – sammanhängande sekvenser av instruktioner med en enda ingång och en enda utgång. Kant mellan noderna anger vilka block som kan följas i följd vid körning.

Grafen byggs genom att dela upp koden i basic blocks och lägga till en startnod och en slutnod. En kant från block A till block B finns om kontrollen kan övergå från A till B under exekvering, exempelvis efter en villkorssats, i följd av instruktioner eller när en funktionskall returneras. Vid hantering av undantag kan även undantagskanter läggas till.

Användningsområden: CFG används i statisk analys, optimeringar i kompilatorer, programverifiering och testgenerering. Genom att analysera vilka block som kan nås kan man identifiera död kod, möjliggöra konstantvärdespropagering och olika loopenalyser.

Variationer och begränsningar: CFG kan vara funktionellt på funktionsnivå eller interprocedurellt när grafen omfattar flera funktioner. Kantetiketter kan ange villkorsvärden (true/false) för villkorssatser. Hantering av undantag eller asynkrona anrop kräver ofta extra kanter eller alternativa representationer, särskilt i moderna språk där kontrollflödet kan bli komplext.