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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aho, A., Sethi, R., and Ullman, J. Compilers, Principles, Techniques and Tools. Addison Wesley, Boston, 1986.
Analog Devices. ADSP-2100 Family User’s Manual.
Araujo, G., Sudarsanam, A., and Malik, S. Instruction set design and optimizations for address computation in DSP processors. In 9th International Symposium on Systems Synthesis (November 1996), IEEE, pp. 31–37.
Briggs, P., Cooper, K., Kennedy, K., and Torczon, L. Coloring heuristics for register allocation. In Proc. of the ACM SIGPLAN’89 on Conference on Programming Language Design and Implementation (June 1982), pp. 98–105.
Chaitin, G. Register allocation and spilling via graph coloring. In Proc. of the ACM SIGPLAN’82 Symposium on Compiler Construction (June 1982), pp. 98–105.
Chow, F., and Hennessy, J. L. The priority-based coloring approach to register allocation. ACM Trans. Program. Lang. Syst. 12, 4 (October 1990), 501–536.
Cintra, M., and Araujo, G. Array reference allocation using SSA-Form and live range growth. In Proceedings of the ACM SIGPLAN LCTES 2000 (June 2000), pp. 26–33.
Cytron, R., Ferrante, J., Rosen, B., Wegman, M., and Zadeck, F. An efficient method of computing static single assignment form. In Proc. of the ACM POPL’89 (1989), pp. 23–25.
Eckstein, E., and Krall, A. Minimizing cost of local variables access for DSP-processors. In LCTES’99 Workshop on Languages, Compilers and Tools for Embedded Systems (Atlanta, July 1999), Y. A. Liu and R. Wilhelm, Eds., vol. 34(7) of SIGPLAN, ACM, pp. 20–27.
Garey, M., and Johnson, D. Computers and Intractability. W. H. Freeman and Company, New York, 1979.
Gebotys, C. DSP address optimization using a minimum cost circulation technique. In Proceedings of the International Conference on Computer-Aided Design (November 1997), IEEE, pp. 100–103.
Gupta, R., Soffa, M., and Ombres, D. Efficient register allocation via coloring using clique separators. ACM Trans. Programming Language and Systems 16, 3 (May 1994), 370–386.
Leupers, R., Basu, A., and Marwedel, P. Optimized array index computation in DSP programs. In Proceedings of the ASP-DAC (February 1998), IEEE.
Liao, S., Devadas, S., Keutzer, K., Tjiang, S., and Wang, A. Storage assignment to decrease code size. ACM Transactions on Programming Languages and Systems 18, 3 (1996), 235–253.
Motorola. DSP56000/DSP56001 Digital Signal Processor User’s Manual, 1990.
Muchnick, S. S. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.
Pohua P. CHANG SCOTT A. Mahlke William Y. Chen, N. J. W., and Mei W. Hwu, W. Impact: An architectural framework for multiple-instruction-issue processors. 266–275.
Potkonjak, C. L. M., and Mangione-Smith, W. H. Mediabench: A tool for evaluating and synthesizing multimedia and communications systems.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ottoni, G., Rigo, S., Araujo, G., Rajagopalan, S., Malik, S. (2001). Optimal Live Range Merge for Address Register Allocation in Embedded Programs. In: Wilhelm, R. (eds) Compiler Construction. CC 2001. Lecture Notes in Computer Science, vol 2027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45306-7_19
Download citation
DOI: https://doi.org/10.1007/3-540-45306-7_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41861-0
Online ISBN: 978-3-540-45306-2
eBook Packages: Springer Book Archive