Return value placement and tail call optimization in high level languages

This paper discusses the interaction between tail call optimization and the placement of output values in functional and logic programming languages. Implementations of such languages typically rely on fixed placement policies: most functional language implementations return output values in registers, while most logic programming systems return outputs via memory. Such fixed placement policies incur unnecessary overheads in many commonly encountered situations: the former an unable to implement many intuitively iterative computations in a truly iterative manner, while the latter incur a performance penalty due to additional memory references. We describe an approach that determines, based on a low-level cost model for an implementation together with an estimated execution profile for a program, whether or not the output of a procedure should be returned in registers or in memory. This can be seen as realizing a restricted form of inter-procedural register allocation, and avoids the disadvantages associated with the fixed register and fixed memory output placement policies. Experimental results indicate that it provides good performance improvements compared to existing approaches. (C) 1999 Elsevier Science Inc. All rights reserved.