以整數線性規劃作為在混合指令集架構下之暫存器重指派方法達成程式碼減量

Abstract

在嵌入式系統中，程式碼大小是與效能一樣重要的議題，特別是針對記憶體受限制之系統，因此減少記憶體使用之相關研究亦是蓬勃發展。而其中一種減少記憶體使用的方式為使用混合指令集架構。這種架構通常提供二種不同長度的指令集，一般為 16 位元的短指令及32位元的長指令。在商業化的產品中，如ARM、MIPS、Andes都提出此種指令集架構，用來減少精簡指令集架構所產生之機器碼過大問題。我們的研究數據顯示，約有49% 的指令其指令格式需至暫存器指定完後，才能決定其指令格式為16位元短指令或32位元長短令；因此如何在混合指令架構下，妥善指派暫存器是非常重要的。暫存器重指派主要是藉由重新指定暫存器編號來達成不同目的之優化；在先前的研究中，在混合指令集架構下之暫存器重指派問題已經被證明是NP問題，因此解決的方法大多也是用Heuristic的方式來得出可行解。在此篇論文研究中，我們使用了整數線性規劃來求解在混合指令架構下之暫存器重指派問題。在不考慮編譯時間的條件下，我們約可減少34.4% 的機器碼大小。

Code size issue for a memory constrained embedded system is as important as performance. There are many researches that devote to this issue. One way of reducing code size is to exploit compact instruction formats. A mixed-width ISA may provide this kind of feature for the Reduce Instruction Set Computer (RISC) processors. In general, it usually provides two different widths of instruction formats: short and long instruction format. In commercial, ARM, MIPS and Andes all support this feature in their products. From our research, the formats of 49% instructions can be decided only after register assignment. Therefore, the register assignment policy is very important for mixed-width ISA. Register reassignment renumbers the registers in each instruction for specific goals. Register reassignment for mixed-width ISA has been proved to be an NP problem. Some researches have devoted to design heuristic algorithms to find the feasible solutions. In this thesis, we use integer linear programming to solve the register reassignment problem in mixed-width ISA for reducing the code size. On the average, we reduce about 34.4% code size compared to the original program.