  Compilers use control flow graph (CFG) representations of low-level programs
because they are suited to program analysis and optimizations. However,
formalizing the behavior and metatheory of CFG programs is non-trivial: CFG
programs don't compose well, their semantics depends on auxiliary state, and,
as a consequence, they do not enjoy a simple equational theory that can be used
for reasoning about the correctness of program transformations.
Lambda-calculus-based intermediate representations, in contrast, have
well-understood operational semantics and metatheory, including rich equational
theories, all of which makes them amenable to formal verification.
  This paper establishes a tight equivalence between (a variant of) Levy's
call-by-push-value (CBPV) calculus and a control flow graph machine whose
instructions are in static single assignment (SSA) form. The correspondence is
made precise via a series of abstract machines that align the transitions of
the structural operational semantics of the CBPV language with the computation
steps of the SSA form.
  The target machine, which is derived from the CBPV language, accurately
captures the execution model of control flow graphs, including direct jumps,
mutually recursive code blocks, and multi-argument function calls, and the
closure-free subset is similar to the SSA intermediate representations found in
modern compilers such as LLVM and GCC. The definitions of all the
language/abstract machine semantics and the theorems relating them are fully
verified in Coq.
