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.