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.

Improved Register Usage for Functional Programs through Multiple Function Versions

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.

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.

The following versions of the article are available:

• 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)
• Source materials for custom formatting
  • 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)

You can find this article also on the ftp-server of The MIT Press (access may be faster from some sites).

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}
    }

Main page