Return Value Placement and Tail
Call Optimization in High Level Languages
Peter Bigot Saumya Debray
Department of Computer Science
University of Arizona
Tucson, AZ 85721, U.S.A.
Abstract
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
are 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.