TY - GEN
T1 - Optimal live range merge for address register allocation in embedded programs
AU - Ottoni, Guilherme
AU - Rigo, Sandro
AU - Araujo, Guido
AU - Rajagopalan, Subramanian
AU - Malik, Sharad
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84958968812&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958968812&partnerID=8YFLogxK
U2 - 10.1007/3-540-45306-7_19
DO - 10.1007/3-540-45306-7_19
M3 - Conference contribution
AN - SCOPUS:84958968812
SN - 354041861X
SN - 9783540418610
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 274
EP - 288
BT - Compiler Construction - 10th International Conference, CC 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001, Proceedings
A2 - Wilhelm, Reinhard
PB - Springer Verlag
T2 - 10th International Conference on Compiler Construction, CC 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001
Y2 - 2 April 2001 through 6 April 2001
ER -