Editing Control-flow graph (section)

{{Short description|Graphical representation of a computer program or algorithm}}
{{multiple issues|
{{More citations needed|date=January 2009}}
{{expert needed|Computer science|reason=many bad/unclear definitions and dubious claims.|date=February 2015}}
}}

[[File:Some types of control flow graphs.svg|thumb|Some CFG examples:<br />(a) an [[if-then-else]]<br />(b) a [[while loop]]<br />(c) a natural loop with two exits, e.g. while with an if...break in the middle; non-structured but reducible<br />(d) an irreducible CFG: a loop with two entry points, e.g. goto into a while or for loop]]
[[File:Rust_MIR_CFG.svg|thumb|A control-flow graph used by the [[Rust (programming language)|Rust]] compiler to perform codegen.]]
In [[computer science]], a '''control-flow graph''' ('''CFG''') is a [[Depiction|representation]], using [[directed graph|graph]] notation, of all paths that might be traversed through a [[computer program|program]] during its [[execution (computing)|execution]]. The control-flow graph was conceived by [[Frances E. Allen]],<ref>{{cite journal
| author = Frances E. Allen
| title = Control flow analysis
| journal = SIGPLAN Notices
| volume = 5
| issue = 7
|date=July 1970
| pages = 1–19
| doi=10.1145/390013.808479
| author-link = Frances E. Allen
}}</ref> who noted that [[Reese Prosser|Reese T. Prosser]] used [[Adjacency matrix|boolean connectivity matrices]] for flow analysis before.<ref>{{cite conference 
| author = Reese T. Prosser
| title = Applications of Boolean matrices to the analysis of flow diagrams
| book-title = Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference
| year = 1959
| pages = 133–138
| doi=10.1145/1460299.1460314
| author-link = Reese Prosser
}}</ref>

The CFG is essential to many [[compiler optimization#Data-flow optimizations|compiler optimization]]s and [[static code analysis|static-analysis]] tools.