Using higher-order functional programming to do register allocation on a functional language

Abstract

We show how to translate a call by value functional language to a RISC architecture in a uniform way that encompasses register alloca tion and spill code placement avoids unnecessary copy instructions provides short circuit translation of Boolean expressions and can make use of inter procedural information The translation is directed by the source language structure It uses higher order functional programming extensively Prelimi nary measurements suggest that this method can compete with graph colouring the framework in which most contemporary register allocators are cast The translation is implemented in the ML Kit a region inference based SML compiler On average our back end compiles our benchmarks to code that runs in of the time of the code generated by SML NJ version.