Browsing by Author "Hsu, Wei Chung"

Now showing 1 - 1 of 1

Register Reassignment for Mixed-width ISAs is an NP-Complete Problem
(2010)
Shen, Bor-Yeh
;
Hsu, Wei Chung
;
Yang, Wuu
;
資訊工程學系
;
Department of Computer Science
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.