臺灣博碩士論文加值系統

由於系統資源有限，機械碼大小在嵌入式系統是一個重要的議題。嵌入式處理器現在常常有長指令和短指令的設計像是 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%的機械碼縮減。

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%.

Contents
Acknowledgements i
Abstract ii
Contents iv
List of Figures vi
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Thesis overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Machine Instruction Set Architecture 6
2.1 Architecture Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 The 16-bit Instruction Set . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Register–based code size reduction problem 11
3.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Proof of NP-hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Heuristic Algorithm 16
4.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
iv
4.2 Pseudo codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5 Compilation Framework for Code Size Reduction 21
5.1 Framework overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 The configuration file . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3 Post optimizer commands . . . . . . . . . . . . . . . . . . . . . . . . 25
6 Experiments 26
6.1 Potential reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.2 EEMBC Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
7 Conclusion 29
7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

[1] The embedded mcroprocessor benchmark consortium. http://www.eembc.org.
[2] Gcc, the gnu compiler collection. http://gcc.gnu.org/.
[3] ′Arp′ad Besz′edes, R. Ferenc, T. Gyim′othy, A. Dolenc, and K. Karsisto. Survey
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,
1992.
[5] G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and
P. W. Markstein. ”Register allocation via coloring”. Computer Languages, 6:47–
57, 1981.
[6] J.-M. Daveau, T. Thery, T. Lepley, and M. Santana. A retargetable register
allocation framework for embedded processors. SIGPLAN Not., 39(7):202–210,
2004.
[7] F. M. Q. Pereira and J. Palsberg. Register allocation after classical ssa elimination
is np-complete. In Proc. of the 9th International Conference on Foundations
of Software Science and Computation Structure (FoSSaCS ’06), pages 79–93,
March 25-31, 2006.
[8] P. Petrov and A. Orailoglu. Transforming binary code for low-power embedded
processors. Micro, IEEE, 24(3):21–33, May-June 2004.
[9] M. Ros and P. Sutton. A post-compilation register reassignment technique for
improving hamming distance code compression. In CASES ’05: Proceedings of
the 2005 international conference on Compilers, architectures and synthesis for
embedded systems, pages 97–104, New York, NY, USA, 2005. ACM.
[10] S. Thammanur and S. Pande. A fast, memory-efficient register allocation framework
for embedded systems. ACM Trans. Program. Lang. Syst., 26(6):938–974,
2004.
[11] K. Zhang, T. Zhang, and S. Pande. Binary translation to improve energy efficiency
through post-pass register re-allocation. In EMSOFT ’04: Proceedings of
the 4th ACM international conference on Embedded software, pages 74–85, New
York, NY, USA, 2004. ACM.
[12] X. Zhuang, T. Zhang, and S. Pande. Hardware-managed register allocation for
embedded processors. SIGPLAN Not., 39(7):192–201, 2004.