Abstract interpretation for the compile-time optimization of logic programs
Thomas Walter Getzinger · University of Southern California Digital Library · 2017
Abstract interpretation is a powerful framework for describing data flow analyses of programs. These analyses can provide useful information for determining the applicability of compile-time optimizations. Many different types of analyses and optimizations have been suggested for Prolog. So far, this exploration has been rather ad hoc. Our goal is to locate the right set of analyses for Prolog compilation. Since everyone's interpretation of what constitutes right will vary, we begin by developing a taxonomy of global analyses for Prolog. We then describe the features that must be present in an abstract interpretation framework meant to be used in conjunction with a Prolog compiler. Using this taxonomy and the framework integrated into a compiler, we perform a systematic search, trading off analysis and compilation time for execution time and compiled code size. This taxonomy and the information we derive during this search should help others to focus and simplify their searches. It should be useful for applications of abstract interpretation in addition to just compilation, for example, program proof of correctness and partial evaluation. It should also provide many insights into abstract interpretation of other languages, such as concurrent logic languages and functional languages. We demonstrate a wide range of performances, varying by a factor of over 4.6 in code size and 4.4 in execution time. At the same time, the global analysis time varies by almost an order of magnitude, but the compile time only by a factor of two. We demonstrate an absolute improvement over previous Prolog compilers. By using a unified framework to perform global analysis and to maintain descriptions during code generation, we show a 42% reduction in compilation time. At the same time, we show a decrease in code size by 36% and a reduction in execution time by 28%. (Copies available exclusively from Micrographics Department, Doheny Library, USC Los Angeles, CA 90089-0182.)