Artículos de revistas
Address Register Allocation For Arrays In Loops Of Embedded Programs
Registro en:
Microelectronics Journal. , v. 34, n. 11, p. 1009 - 1018, 2003.
262692
10.1016/S0026-2692(03)00169-1
2-s2.0-0142185114
Autor
Ottoni G.
Araujo G.
Institución
Resumen
Efficient address register allocation has been shown to be a central problem in code generation for processors with restricted addressing modes. This paper extends previous work on Global Array Reference Allocation (GARA), the problem of allocating address registers to array references in loops. It describes two heuristics to the problem, presenting experimental data to support them. In addition, it proposes an approach to solve GARA optimally which, albeit computationally exponential, is useful to measure the efficiency of other methods. Experimental results, using the MediaBench benchmark and profiling information, reveal that the proposed heuristics can solve the majority of the benchmark loops near optimality in polynomial-time. A substantial execution time speedup is reported for the benchmark programs, after compiled with the original and the optimized versions of GCC. © 2003 Published by Elsevier Ltd. 34 11 1009 1018 The GNU Compiler Collection Project, , http://gcc.gnu.org Aho, A., Johnson, S., Optimal code generation for expression trees (1976) Journal of the ACM, 23 (3), pp. 488-501 Aho, A., Sethi, R., Ullman, J., (1986) Compilers, Principles, Techniques and Tools, , Boston: Addison-Wesley Araujo, G., Sudarsanam, A., Instruction, M.S., Instruction set design and optimizations for address computation in DSP processors (1996) Ninth International Symposium on Systems Synthesis, pp. 31-37. , IEEE Bartley, D.H., Optimizing stack frame accesses for processors with restricted addressing modes (1992) Software Practice and Experience, 22 (2), p. 101 Bodik, R., Gupta, R., Array data-flow analysis for load-store optimizations in superscalar architectures (1996) International Journal of Parallel Programming, 24 (6), pp. 481-512 Bradlee, D., Eggers, S., Henry, R., Integrating register allocation and instruction scheduling for RISCs (1991) Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 122-131. , April Briggs, P., Cooper, K., Kennedy, K., Torczon, L., Coloring heuristics for register allocation (1989) Proceedings of the ACM SIGPLAN'89 on Conference on Programming Language Design and Implementation, pp. 275-284. , July Callahan, D., Carr, S., Kennedy, K., Improving register allocation for subscripted variables (1990) ACM SIGPLAN Conference on Programming Languages Design and Implementation, pp. 53-65. , June Callahan, D., Koblenz, B., Register allocation via hierarchical graph coloring (1991) Proceedings of the ACM SIGPLAN'91 Conference on Programming Languages Design and Implementation, pp. 192-203. , June Chaitin, G., Register allocation and spilling via graph coloring (1982) Proceedings of the ACM SIGPLAN'82 Symposium on Compiler Construction, pp. 98-105. , June Chow, F., Hennessy, J.L., The priority-based coloring approach to register allocation (1990) ACM Transactions on Programming Language and Systems, 12 (4), pp. 501-536 Cintra, M., Araujo, G., Array reference allocation using SSA-Form and live range growth (2000) Proceedings of the ACM SIGPLAN LCTES 2000, pp. 26-33. , June Cytron, R., Ferrante, J., Rosen, B., Wegman, M., Zadeck, F., An efficient method of computing static single assignment form (1989) Proceedings of the ACM POPL'89, pp. 23-25 Eckstein, E., Krall, A., Minimizing cost of local variables access for DSP-processors (1999) Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, pp. 20-27. , May Gebotys, C., DSP address optimization using a minimum cost circulation technique (1997) Proceedings of the International Conference on Computer-Aided Design, pp. 100-103. , November IEEE Goodman, J., Hsu, A., Code scheduling and register allocation in large basic blocks (1988) Proceedings of the Conference on Supercomputing, pp. 442-452. , July Gupta, R., Soffa, M., Ombres, D., Efficient register allocation via coloring using clique separators (1994) ACM Transactions on Programming Language and Systems, 16 (3), pp. 370-386 Hitchcock C.Y. III, (1986) Addressing Modes for Fast and Optimal Code Generation, , PhD Thesis, Carnegie-Mellon University, Pittsburgh, PA, Dec Lee, C., Potkonjak, M., Mangione-Smith, W.H., (1997) Mediabench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems Leupers, R., Basu, A., Marwedel, P., Optimized array index computation in DSP programs (1998) Proceedings of the ASP-DAC, , IEEE Leupers, R., David, F., A uniform optimization technique for offset assignment problems (1998) Proceedings of the ACM SIGDA 11th International Symposium on System Synthesis, pp. 3-8. , December Leupers, R., Marwedel, P., (2001) Retargetable Compiler Technology for Embedded Systems, , Dordrecht: Kluwer Liao, S., Devadas, S., Keutzer, K., Tjiang, S., Wang, A., Storage assignment to decrease code size (1995) Proceedings of 1995 ACM Conference on Programming Language Design and Implementation (1998) Digital Signal Processor, , DSP1611/17/18/27/28/29 Muchnick, S.S., (1997) Advanced Compiler Design and Implementation, , Los Altos, CA: Morgan Kaufmann Ottoni, G., Rigo, S., Araujo, G., Rajagopalan, S., Malik, S., Optimal live range merge for address register allocation in embedded programs (2001) LNCS, 2027, pp. 274-288. , Proceedings of the 10th International Conference on Compiler Construction, CC2001 Berlin: Springer Rao, A., Pande, S., Storage assignment optimizations to generate compact and efficient code on embedded DSPs (1999) Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 128-138. , May Sethi, R., Complete register allocation problems (1975) SIAM Journal of Computing, 4 (3), pp. 226-248 Sethi, R., Ullman, J., The generation of optimal code for arithmetic expressions (1970) Journal of the ACM, 17 (4), pp. 715-728 Wolfe, M.J., (1996) High Performance Compilers for Parallel Computing, , Boston: Addison-Wesley