Editing Control-flow graph (section)

== Definition ==
In a control-flow graph each [[Vertex (graph theory)|node]] in the [[Graph (discrete mathematics)|graph]] represents a [[basic block]], i.e. a straight-line sequence of code with a single entry point and a single exit point, where no branches or jumps occur within the block. Basic blocks start with jump targets and end with jumps or branch instructions. Directed [[edge (graph theory)|edge]]s are used to represent jumps in the [[control flow]]. There are, in most presentations, two specially designated blocks: the ''entry block'', through which control enters into the flow graph, and the ''exit block'', through which all control flow leaves.<ref>{{cite conference |chapter=Masking wrong-successor Control Flow Errors employing data redundancy  |last1=Yousefi |first1=Javad |title=2015 5th International Conference on Computer and Knowledge Engineering (ICCKE) |date= 2015|publisher=IEEE |pages=201–205 |doi=10.1109/ICCKE.2015.7365827 |url=https://ieeexplore.ieee.org/document/7365827|isbn=978-1-4673-9280-8 }}</ref>

Because of its construction procedure, in a CFG, every edge A→B has the property that:
: [[outdegree]](A) > 1 or indegree(B) > 1 (or both).<ref name="TarrWolf2011">{{cite book|author1=Peri L. Tarr|author2=Alexander L. Wolf|title=Engineering of Software: The Continuing Contributions of Leon J. Osterweil|year=2011|publisher=Springer Science & Business Media|isbn=978-3-642-19823-6|page=58}}</ref>

The CFG can thus be obtained, at least conceptually, by starting from the program's (full) flow graph—i.e. the graph in which every node represents an individual instruction—and performing an [[edge contraction]] for every edge that falsifies the predicate above, i.e. contracting every edge whose source has a single exit and whose destination has a single entry. This contraction-based algorithm is of no practical importance, except as a visualization aid for understanding the CFG construction, because the CFG can be more efficiently constructed directly from the program by [[Basic block#Creation algorithm|scanning it for basic blocks]].<ref name="TarrWolf2011"/>