藉由暫存器配置與指派演算法減少程式碼大小於混合寬度指令集架構處理器

Abstract

由於現今的嵌入式系統需要越來越多的程式功能，但又不希望增加記憶體大小，因此減少程式碼大小即成為一個關鍵性的問題。其中一種解決辦法是使用"混合寬度指令集架構"，這類架構通常包含一個正常寬度指令集(通常是32 位元)以及一個短指令集(通常是16 位元)，且短指令集僅有部分Opcodes 以及僅能存取部分的暫存器。在以往傳統的混合指令集架構中，一段連續程式碼僅能被編碼在相同的格式(寬度)，無法使用多種格式穿插其中，但越來越多的混合指令集架構使用了指令編碼來告知處理器該指令的寬度，如此便可在程式之中任意穿插長短指令，不再是一個一個分開的區塊。對於這樣的架構，有多少指令能夠被編碼成較短的格式高度依賴於如何配置這些短指令格式能存取到有限的暫存器。在這篇論文中，我們提出了兩個基於著色演算法的暫存器配置與分派演算法，它們使用一個估計的方法去找出適合被指派到短指令格式能存取到之暫存器的程式變數，而適合的變數意味著如果指派它們到這些暫存器可以有效增加可以被編碼成短指令的指令數量。透過模擬結果顯示，使用此論文所提出的演算法可以減少大約31.90%的程式碼大小。

Reducing program size is a critical issue in many embedded systems which require more program functionalities without increasing the memory size. One of the approaches is the “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 the code size reduction is achieved 31.90% by the proposed algorithm.