One CFG-Generator to Rule Them All

Abstract

This paper introduces two independent yet synergistic contributions related to control-flow graphs in programming tools. Our first contribution is a language-modular design for the construction of CFG generators. In this paper, we use this technique to build a complete CFG-generator for a small language with 17 distinct node types in only 19 lines of language-specific code. Our full implementation creates complete control-flow graphs for 5 industrial languages in only 1100 SLOC (averaging 122 language-specific SLOC), compared to 2400 for combined competitors. Our second contribution is a new program transformation primitive, CFG-based insertion, which provides the operation “insert statement S such that it always executes before expression E.” This operation makes it possible to build 1-line program transformations that handle special cases across multiple languages. Both contributions have been implemented in Haskell in the extsc{Cubix} framework, with support for C, Java, JavaScript, Lua, and Python. Together, the two contributions of this paper make it substantially easier to build high-fidelity CFG generators for many languages and use them in language-parametric program transformations.

Type
Publication
In submission
Date
Avatar
James Koppel
Ph. D. Candidate