機械碼縮減之編譯器設計

Compilers for Code Size Reduction

賴韋志(Wei-Chih Lai)

指導教授 ： 李政崑

國立清華大學/電機資訊學院/資訊工程學系/碩士(2008年)

摘要

由於系統資源有限，機械碼大小在嵌入式系統是一個重要的議題。嵌入式處理器現在常常有長指令和短指令的設計像是 ARM/THUMB 和 MIPS32/MIPS16。短指令通常有所限制，像是只能存取暫存器的部份子集以及立即值的範圍有限制。本研究提出一個為32位元嵌入式處理器的機械碼縮減編譯框架，同時我們為了縮減更多機械碼空間，我們設計了使用重新命名技巧的暫存器配置方法。我們的平台架構上有32位元和16位元短指令集，32位元指令集可以存取所有的32個暫存器，而16位元指令集分別可以對32/16/8個暫存器作存取，立即值也有較小的編碼空間。對於立即值符合標準但暫存器不符合的指令群，如果我們能正確的選取暫存器，32位元指令可以轉換成16位元短指令。我們定義這個問題為，如何重新指定暫存器讓32位元指令轉換成16位元短指令，使得機械碼可以最小？本論文證明了這個問題是 NP-hard ，並且提出一個經驗式法則的演算法來解決本問題。這個演算法的法則是，選擇暫存器的時候只要選剛好符合16位元限制的暫存器就好，並且限制搜尋空間。我們的實驗平台是建立在 EEMBC 上，平均可以達到 23.10% 和最高 26.73%的機械碼縮減。

關鍵字

編譯器 ； 機械碼縮減 ； 暫存器重新命名方法 ； HASH(0x1d1f11c0)

並列摘要

Code density is an important issue in embedded systems due to limited resources. It
is a trend that embedded micro-controllers have both normal and short instruction
set for code density, e.g. ARM/Thumb and MIPS32/MIPS16. Short instructions
usually have some limitations compared to normal instructions, e.g. less register file
accessibility or less immediate value range. In this work, we propose a compilation
framework for code size reductions with 32-bit embedded micro-controllers. We also
devise plans to further reduce code size for our target architecture by code-size-aware
register re-number techniques. The target architecture has both 32/16-bit instructions
set, and each of 16-bit instructions can map to subset of 32-bit instructions.
The 16-bit instructions have 5/4/3-bit register index, and they might have immediate
value constraint. Therefore, if we could allocate register properly, the 32-bit instructions
could be transformed to 16-bit form for saving code size. With the flat register
file, we can re-number the register without any performance loss. Our problem is to
minimize code size for the given program using register re-numbering technique. In
this paper, we prove the problem is NP-hard and give a heuristic algorithm to solve
the problem. In picking up the register to replace the original register, we employ
the small enough principle. This principle chooses register that can just fit into register
index of 16-bit instruction making register usage more effective. The algorithm
first builds def-use chain for the given program, and then find the register re-number
solution making code size reduction by bounding the search space. The experiments
ii
is based on EEMBC benchmark suite [1] where the average reductions is 22.94% and
highest is 26.75%.

並列關鍵字

Compilers ； Code size reductions ； Code compaction ； Register re-number

參考文獻

[2] Gcc, the gnu compiler collection. http://gcc.gnu.org/.

of code-size reduction methods. ACM Comput. Surv., 35(3):223–267, 2003.

[4] P. Briggs. Register allocation via graph coloring. PhD thesis, Houston, TX, USA,

P. W. Markstein. ”Register allocation via coloring”. Computer Languages, 6:47–

57, 1981.