Interprocedural register allocation for lazy functional languages
Urban Boquist · 1995
The aim of this paper is two-fold; first, we develop an interprocedural register allocation algorithm, an extended variant of Briggs' optimistic graph colouring. We use interprocedural coalescing as an elegant way to achieve a custom-made calling convention for each function. We add a restricted, and cheap, form of live range splitting in a way that is particularly useful for call intensive languages. Second, we apply our interprocedural register allocation algorithm to code generated from a lazy functional language. In doing this we use a monadic intermediate code, well suited for analysis and program transformation. We use program transformation techniques and the result of an abstract interpretation analysis on the intermediate code to eliminate all unknown control flow in the program. This will improve the chances of the register allocator to produce good results. Preliminary measurements show that we are able to eliminate up to 95% of all stack references compared to the Chalmers ...