Compilation framework for code size reduction using reduced bit-width ISAs (rISAs)

ABSTRACT

For many embedded applications, program code size is a critical design factor. One promising approach for reducing code size is to employ a “dual instruction set”, where processor architectures support a normal (usually 32-bit) Instruction Set, and a narrow, space-efficient (usually 16-bit) Instruction Set with a limited set of opcodes and access to a limited set of registers. This feature however, requires compilers that can reduce code size by compiling for both Instruction Sets. Existing compiler techniques operate at the routine-level granularity and are unable to make the trade-off between increased register pressure (resulting in more spills) and decreased code size. We present a compilation framework for such dual instruction sets, which uses a profitability based compiler heuristic that operates at the instruction-level granularity and is able to effectively take advantage of both Instruction Sets. We demonstrate consistent and improved code size reduction (on average 22%), for the MIPS 32/16 bit ISA. We also show that the code compression obtained by this “dual instruction set” technique is heavily dependent on the application characteristics and the narrow Instruction Set itself.

REFERENCES

• 1: Advanced RISC Machines, Ltd. 2003. ARM7TDMI (Rev 4) Technical Reference Manual. Advanced RISC Machines, Ltd. Cambridge, England, http://www.arm.com/pdfs/DDI0234A_7TDMIS_R4.pdf.
• 2: ARC Cores. 2005. ARCtangent-A5 Microprocessor Technical Manual. ARC Cores, Herts, England, http://www.arc.com/documentation/productionbriefs.
• 3: Luca Benini , Alberto Macii , Alberto Nannarelli, Cached-code compression for energy minimization in embedded processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.322-327, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383177]
• 4: Briggs, P., Cooper, K., and Torczon, L. 1994. Improvements to graph coloring register allocation. In Proceedings of PLDI.
• 5: Ashok Halambi , Peter Grun , Vijay Ganesh , Asheesh Khare , Nikil Dutt , Alex Nicolau, EXPRESSION: a language for architecture exploration through compiler/simulator retargetability, Proceedings of the conference on Design, automation and test in Europe, p.100-es, January 1999, Munich, Germany [doi>10.1145/307418.307549]
• 6: Halambi, A., Shrivastava, A., Dutt, N., and Nicolau, A. 2001. A customizable compiler framework for embedded systems. In Proceedings of SCOPES.
• 7: Khare, A., Savoiu, N., Halambi, A., Grun, P., Dutt, N., and Nicolau, A. 1999. V-SAT: A visual specification and analysis for system-on-chip exploration. In Proceedings of EUROMICRO.
• 8: Arvind Krishnaswamy , Rajiv Gupta, Enhancing the performance of 16-bit code using augmenting instructions, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 9: Kwon, Y.-J., Ma, X., and Lee, H. J. 1999a. PARE: Instruction set architecture for efficient code size reduction. Electronics Letters 25th Nov'99, 35, 24, 2098--2099.
• 10: Kwon, Y.-J., Parker, D., and Lee, H. J. 1999b. Toe: Instruction set architecture for code size reduction and two operations execution. In Proceedings of CASES.
• 11: Haris Lekatsas , Jörg Henkel , Wayne Wolf, Code compression for low power embedded system design, Proceedings of the 37th conference on Design automation, p.294-299, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337423]
• 12: LSI LOGIC. 2000. TinyRISC LR4102 Microprocessor Technical Manual. LSI LOGIC, Milpitas, CA, http://www.lsilogic.com/files/docs/techdocs/microprocessors/MIPSTinyRISC/4102/lr4102ds_3000.pdf.
• 13: Nicolau, A. and Novack, S. 1993. Trailblazing: A hierarchical approach to percolation scheduling. In Proceedings of ICPP.
• 14: Novack, S. and Nicolau, A. 1997. Resource directed loop pipelining: Exposing just enough parallelism. The Comput. J.
• 15: Aviral Shrivastava , Nikil Dutt, Energy efficient code generation exploiting reduced bit-width instruction set architectures (rISA), Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.475-477, January 27-30, 2004, Yokohama, Japan
• 16: ST Microelectronics. 2004. ST100 Technical Manual. ST Microelectronics, Geneva, Switzerland, http://www.st.com/stonline/books/pdf/docs/10538.pdf.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
Code generation, code compression, codesize reduction, compilers, dual instruction set, narrow bit-width instruction set, optimization, rISA, register pressure-based code generation, retargetable compilers, thumb