Computer Science Department
School of Computer Science, Carnegie Mellon University
Generating Code for High-Level Operations through Code Composition
James M. Stichnoth
An alternative strategy is to generate a call to a runtime library for each high-level language construct. This approach is attractive if the source language contains complex, powerful constructs, like the distributed array assignment statement in High Performance Fortran (HPF). The decision between custom code generation and use of a runtime library involves tradeoffs between efficiency (performance of the generated code), maintainability (ease of developing and maintaining the algorithm), and generality (implementation of the general case, rather than merely a simplified canonical case).
I introduce a new compilation strategy, high-level code composition, which combines the advantages of custom code generation and runtime libraries. The compilation of each construct is controlled by code templates, which contain both target code to be generated and compile-time control instructions that specify how the templates are composed together. The templates are external to the compiler, making them easy to write and modify. The composition system executes the control code at compile time, automatically generating and optimizing the code to be executed at run time.
In this dissertation, I motivate and explore the language and implementation issues of code composition. I describe Catacomb, my implementation of a composition system, which integrates with a high-level compiler to generate custom C code. I describe the challenges in enabling Catacomb to automatically generate the best code without sacrificing a clean user model. In addition, I develop a framework for the HPF array assignment, allowing an arbitrary array assignment algorithm to be coupled with an arbitrary communication architecture to form a complete implementation. This framework leads to the first compilation system that can incorporate and compare several array assignment algorithms on several communication architectures, for the fully general array assignment statement.