Reducing code size by graph coloring register allocation and assignment algorithm for mixed-width ISA processor

Jyh Shian Wang, I. Wei Wu, Yu Sheng Chen, Jyh-Jiun Shann, Wei Chung Hsu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Reducing program size is a critical issue in many embedded systems which require more functionalities without increasing the memory size. One of the approaches is to adopt a mixed-width instruction set architecture (ISA) which usually has an instruction set in general formats (usually 32-bit long) as normal instruction set and an instruction set in shorter format (usually 16-bit long) with limited opcodes and set of registers. Traditionally, a code segment can be encoded in only one format, no multiple formats interleaved. However, more and more processors use instruction encoding to indicate the length of each individual instruction and take mixed-width ISA into instruction-level granularity. For this kind of ISAs, the number of instructions can be encoded in shorter format is highly dependent on the limited set of registers that can be accessed by shorter format instructions. In this paper, we present a register allocation and assignment algorithm based on graph coloring, which uses a heuristic model to find out which virtual variables in program should be assigned into the set of registers accessible by shorter instructions. The simulation results show that 63.34% of the instructions can be translated into shorter format on average.

Original languageEnglish
Title of host publicationProceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009 - 7th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2009
Pages174-181
Number of pages8
DOIs
StatePublished - 3 Dec 2009
Event7th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2009 - Vancouver, BC, Canada
Duration: 29 Aug 200931 Aug 2009

Publication series

NameProceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009
Volume2

Conference

Conference7th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2009
CountryCanada
CityVancouver, BC
Period29/08/0931/08/09

Fingerprint Dive into the research topics of 'Reducing code size by graph coloring register allocation and assignment algorithm for mixed-width ISA processor'. Together they form a unique fingerprint.

  • Cite this

    Wang, J. S., Wu, I. W., Chen, Y. S., Shann, J-J., & Hsu, W. C. (2009). Reducing code size by graph coloring register allocation and assignment algorithm for mixed-width ISA processor. In Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009 - 7th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2009 (pp. 174-181). [5284287] (Proceedings - 12th IEEE International Conference on Computational Science and Engineering, CSE 2009; Vol. 2). https://doi.org/10.1109/CSE.2009.100