JFLP: Volume 1998, Article 7
The Journal of Functional and Logic Programming
Volume 1998
Article 7
Published by The MIT Press . Copyright 1998 Massachusetts Institute of Technology.
Your institution may already be a subscriber to JFLP. If not, please subscribe for legitimate access to all journal articles.
M. Satpathy, A. Sanyal, and G. Venkatesh
10 December 1998
Abstract
To use registers effectively, functional programs rely on interprocedural register allocation. Existing interprocedural strategies adopt a naive approach in the presence of recursion, and spill registers whenever necessary. Moreover, such recursion-induced spills cannot be avoided, even by increasing the supply of registers. In this paper, we describe a strategy that reduces memory spills due to recursion by keeping multiple versions of the same function. Each version gets a different register assignment and has different spilling characteristics. Such a strategy shows better spilling behavior as compared to the original (single version) program, but the extent of gain is largely dependent on the control paths followed by the program during execution.The following versions of the article are available:We first determine the number of versions of each function, so that regardless of the execution path, the program with multiple function versions is guaranteed to perform better than the original program. Since some of these versions may be useless in the sense that they may never be called during any course of execution, we also have the problem of determining the number of meaningful versions. We solve this problem by casting it in terms of voltage graphs. We then show that by using properties of voltage graphs, we can reduce the number of versions even further without adding to the number of spills.
-
Preformatted versions of the article (compressed with
gzip
)- DVI (gzip'ped 57 kb)
- PostScript (gzip'ped 242 kb)
- PDF (gzip'ped 350 kb; uncompressed 499 kb)
-
LaTeX
(
JFLP-A98-07.tex
, gzip'ped 33 kb) -
BIBTeX
(
JFLP-A98-07.bib
, gzip'ped 2 kb) - Parameter settings for custom formatting ( cjropts.tex , 165 bytes)
Self citation
@article{jflp98-07, author={M. Satpathy and A. Sanyal and G. Venkatesh}, title={Improved Register Usage for Functional Programs through Multiple Function Versions}, journal={Journal of Functional and Logic Programming}, volume={1998}, number={7}, publisher={The MIT Press}, month={December}, year={1998} }