Optimal live range merge for address register allocation in embedded programs

Guilherme Ottoni, Sandro Rigo, Guido Araujo, Subramanian Rajagopalan, Sharad Malik

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

The increasing demand for wireless devices running mobile applications has renewed the interest on the research of high performance low power processors that can be programmed using very compact code. One way to achieve this goal is to design specialized processors with short instruction formats and shallow pipelines. Given that it enables such architectural features, indirect addressing is the most used addressing mode in embedded programs. This paper analyzes the problem of allocating address registers to array references in loops using auto-increment addressing mode. It leverages on previous work, which is based on a heuristic that merges address register live ranges. We prove, for the first time, that the merge operation is NP-hard in general, and show the existence of an optimal linear-time algorithm, based on dynamic programming, for a special case of the problem.

Original languageEnglish (US)
Title of host publicationCompiler Construction - 10th International Conference, CC 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001, Proceedings
EditorsReinhard Wilhelm
PublisherSpringer Verlag
Pages274-288
Number of pages15
ISBN (Print)354041861X, 9783540418610
DOIs
StatePublished - Jan 1 2001
Event10th International Conference on Compiler Construction, CC 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001 - Genova, Italy
Duration: Apr 2 2001Apr 6 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2027
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Conference on Compiler Construction, CC 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001
CountryItaly
CityGenova
Period4/2/014/6/01

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal live range merge for address register allocation in embedded programs'. Together they form a unique fingerprint.

  • Cite this

    Ottoni, G., Rigo, S., Araujo, G., Rajagopalan, S., & Malik, S. (2001). Optimal live range merge for address register allocation in embedded programs. In R. Wilhelm (Ed.), Compiler Construction - 10th International Conference, CC 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001, Proceedings (pp. 274-288). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2027). Springer Verlag. https://doi.org/10.1007/3-540-45306-7_19