Control-flow graph
= Control-flow graph
A <control-flow graph> is a <directed graph> whose vertices represent program regions, commonly <basic blocks>, and whose edges represent possible immediate control transfers. It describes which execution paths the representation permits, rather than which path one particular run takes. <Compiler optimization> and <data-flow analysis> use this structure.
For `if c then x=1 else x=2; return x`, use an entry vertex with edges to separate true and false <basic blocks>, each leading to one join <basic block>. The graph has a diamond shape. The join needs the incoming value selected by the executed path; <static single-assignment form> represents that choice using a <phi node>. LLVM's tutorial constructs precisely this branch-and-join structure.<Kaleidoscope: Extending the Language: Control Flow in the LLVM documentation>[§5.2.4, LLVM IR for If/Then/Else and control-flow graph]{ref} Loops add backward edges, so a <control-flow graph> need not be acyclic.