Domain-Specific Type Inference for Library Generation in a Telescoping Compiler

Telescoping languages is a strategy for allowing users to develop code in high-level, domain-specific languages and still achieve high performance. It uses extensive offline processing of the library defining the language. This process speculatively determines the possible uses of the library subroutines and generates variants specialized toward those uses. LibGen is a telescoping-language system for generating high-performance Fortran or C libraries with multiple specialized variants from a single version of MATLAB prototype code. LibGen uses variable types to guide specialization. Previously, we have shown that the generated code has comparable performance to hand-coded and optimized Fortran libraries and that specialization on type is important for achieving high performance. In this paper, we describe the type inference system necessary for LibGen to speculate on the possible variants of library procedures and to generate code. We develop the concept of type jump-functions, which describe the transfer of type information through and across procedures. To compute these type jump-functions, we develop a static type-inference approach that uses a constraint-based formulation and a graph-theoretical algorithm shown to be efficient under conditions met in most practical cases