Using the heap to eliminate stack accesses

Zoltan Somogyi, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

The value of a variable is often given by a field of a heap cell, and frequently the program will pick up the values of several variables from different fields of the same heap cell. By keeping some of these variables out of the stack frame, and accessing them in their original locations on the heap instead, we can reduce the number of loads from and stores to the stack at the cost of introducing a smaller number of loads from the heap. We present an algorithm that finds the optimal set of variables to access via a heap cell instead of a stack slot, and transforms the code of the program accordingly. We have implemented this optimization in the Mercury compiler, and our measurements show that it can reduce program runtimes by up to 12% while at the same time reducing program size. The optimization is straightforward to apply to Mercury and to other languages with immutable data structures; its adaptation to languages with destructive assignment would require the compiler to perform mutability analysis.

Original languageEnglish
Title of host publicationProceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)
PublisherAssociation for Computing Machinery (ACM)
Pages121-132
Number of pages12
ISBN (Print)1581135289, 9781581135282
Publication statusPublished - 1 Jan 2002
EventProceedings of the Fourth ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02) - Pittsburg, PA, United States of America
Duration: 6 Oct 20028 Oct 2002

Publication series

NameProceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)

Conference

ConferenceProceedings of the Fourth ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)
CountryUnited States of America
CityPittsburg, PA
Period6/10/028/10/02

Keywords

  • Heap cells
  • Maximal matching
  • Stack accesses
  • Stack frames

Cite this