Abstract Compilation
by Taegyoon Kim
2008.04.09
Introduction
Static analyses typically use abstract interpretaion to achieve speed-up of program analyses. The problem is that abstract execution is slow. Even if the syntax tree of the source code to be analyzed is available, you convert them to machine codes as you interpret them.
Most slowdowns occur in loops because of interpreting the same code. The idea came from this phenomenon, which is why compilers are preferable to interpreters when speed is very important limiting factor.
Our method is a kind of partial-evaluation. There are two ways to optimize the abstract execution. First, the speed-up of our method currently relies heavily on the off-the-shelf compiler’s optimizations. The idea is letting the compiler do the most of the optimizations. Second, if optimization of the compiler is not so good, we should implement needed optimizations in our abstract compiler. (I think the latter is the way to go. The optimization can be configured flexibly to meet our needs.)
In this paper, I will describe a simple abstract compilation technique, using high-level functional language OCaml as both implementation language and intermediate language. The target language is so simple that it does not have loops. But the idea will be clearly shown.
abstract-compilation.pdf
abstract-compilation.tex