Compositional Verification of Flow-directed Transformations
Compilers typically restrict optimizations such as dead-parameter elimination, uncurrying, and arity raising to \emph{known} functions; functions — those that are exclusively applied, rather than passed as arguments to higher-order functions or stored within data structures. To do better, compilers employ flow analysis to gather semantic insights about program execution, and leverage these results to drive more aggressive optimizations. Consequently, classical optimizations can be made \emph{flow-directed}, allowing them to target higher-order functions with non-local behavior. However, for separate compilation, the compiler must guarantee that these transformations do not alter the behavior of exported values. We call these immutable-behavior values \emph{exposed}, and present a framework for verifying such flow-directed optimizations \emph{compositionally}. To achieve this, we design a novel family of logical relations parameterized over the particular optimization to be verified. We prove that any instantiation of this relation yields a traditional notion of semantic equivalence for top-level terms. We instantiate our framework to verify three case studies of flow-directed transformations: dead-parameter elimination, constant propagation, and a form of defunctionalization. Finally, we prove the compositional correctness of our compiler pipeline. Our results are mechanized in the Rocq prover.