Register reassignment for mixed-width ISAs is an NP-complete problem

Bor Yeh Shen, Wei Chung Hsu, Wuu Yang

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

Abstract

Code size is an important issue in many embedded systems. In order to reduce code size, newer embedded RISC processors employ a mixed-width instruction set, where processor architectures support interleaved execution between normal (usually 32-bit) and narrow (usually 16-bit) instructions without explicit mode switch. However, because of the restriction of the encoding length, narrow instructions can only access a limited set of registers. Therefore, for a mixed-width instruction set, proper register allocation can reduce code size. One approach is to re-assign the registers after traditional register allocation. In this paper, we prove that this register reassignment problem is NP-complete by showing that the 0-1 knapsack problem is a special case of this problem. We also propose a method for register reassignment for a mixed-width instruction set with the main goal of code size reduction.

Original languageEnglish
Title of host publicationIMCIC 2010 - International Multi-Conference on Complexity, Informatics and Cybernetics, Proceedings
EditorsJorge Baralt, Michael J. Savoie, Hsing-Wei Chu, C. Dale Zinn, Nagib C. Callaos
PublisherInternational Institute of Informatics and Systemics, IIIS
Pages139-143
Number of pages5
ISBN (Electronic)9781934272916
StatePublished - 1 Jan 2010
EventInternational Multi-Conference on Complexity, Informatics and Cybernetics, IMCIC 2010 - Orlando, United States
Duration: 6 Apr 20109 Apr 2010

Publication series

NameIMCIC 2010 - International Multi-Conference on Complexity, Informatics and Cybernetics, Proceedings
Volume1

Conference

ConferenceInternational Multi-Conference on Complexity, Informatics and Cybernetics, IMCIC 2010
CountryUnited States
CityOrlando
Period6/04/109/04/10

Keywords

  • Code size reduction
  • Knapsack problem
  • Mixed-width ISA
  • NP-complete
  • Register reassignment
  • Thumb-2

Fingerprint Dive into the research topics of 'Register reassignment for mixed-width ISAs is an NP-complete problem'. Together they form a unique fingerprint.

  • Cite this

    Shen, B. Y., Hsu, W. C., & Yang, W. (2010). Register reassignment for mixed-width ISAs is an NP-complete problem. In J. Baralt, M. J. Savoie, H-W. Chu, C. D. Zinn, & N. C. Callaos (Eds.), IMCIC 2010 - International Multi-Conference on Complexity, Informatics and Cybernetics, Proceedings (pp. 139-143). (IMCIC 2010 - International Multi-Conference on Complexity, Informatics and Cybernetics, Proceedings; Vol. 1). International Institute of Informatics and Systemics, IIIS.