@inproceedings{fedfdbffe1904ac18b4c5738f68ab01e,
title = "Register reassignment for mixed-width ISAs is an NP-complete problem",
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.",
keywords = "Code size reduction, Knapsack problem, Mixed-width ISA, NP-complete, Register reassignment, Thumb-2",
author = "Shen, {Bor Yeh} and Hsu, {Wei Chung} and Wuu Yang",
year = "2010",
month = apr,
language = "English",
series = "IMCIC 2010 - International Multi-Conference on Complexity, Informatics and Cybernetics, Proceedings",
publisher = "International Institute of Informatics and Systemics, IIIS",
pages = "139--143",
editor = "Jorge Baralt and Savoie, {Michael J.} and Hsing-Wei Chu and Zinn, {C. Dale} and Callaos, {Nagib C.}",
booktitle = "IMCIC 2010 - International Multi-Conference on Complexity, Informatics and Cybernetics, Proceedings",
note = "International Multi-Conference on Complexity, Informatics and Cybernetics, IMCIC 2010 ; Conference date: 06-04-2010 Through 09-04-2010",
}