Optimal Live Range Merge for Address Register Allocation in Embedded Programs [abstract] (SpringerLink, PDF, PostScript)
Guilherme Ottoni, Sandro Rigo, Guido Araujo, Subramanian Rajagopalan, and Sharad Malik
Proceedings of the 10th International Conference on Compiler Construction, LNCS 2027 (CC), April 2001.
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
instance of the problem. Experimental results reveal that this
instance is surprisingly common in embedded programs, and that its
solution can result in fewer update instructions, when compared with
the known heuristic.