Publikation
A Graph-Based Higher-Order Intermediate Representation
Roland Leißa; Marcel Köster; Sebastian Hack
In: Proceedings of the International Symposium on Code Generation and Optimization (CGO). International Symposium on Code Generation and Optimization (CGO-2015), February 7-11, San Francisco, CA, USA, ACM, 2/2015.
Zusammenfassung
Many modern programming languages support both imperative and functional idioms. However, state-of-the-art imperative intermediate representations (IRs) cannot natively represent crucial functional concepts (like higher-order functions). On the other hand, functional IRs employ an explicit scope nesting, which is cumbersome to maintain across certain transformations. In this paper we present Thorin: a higher-order, functional IR based on continuation-passing style that abandons explicit scope nesting in favor of a dependency graph. This makes Thorin an attractive IR for both imperative as well as functional languages. Furthermore, we present a novel program transformation to eliminate the overhead caused by higherorder functions. The main component of this transformation is lambda mangling: an important transformation primitive in Thorin. We demonstrate that lambda mangling subsumes many classic program transformations like tail-recursion elimination, loop unrolling or (partial) inlining. In our experiments we show that higher-order programs translated with Thorin are consistently as fast as C programs.