在嵌入式系統中，程式碼大小是與效能一樣重要的議題，特別是針對記憶體受限制之系統，因此減少記憶體使用之相關研究亦是蓬勃發展。而其中一種減少記憶體使用的方式為使用混合指令集架構。這種架構通常提供二種不同長度的指令集，一般為 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.

摘 要 i
Abstract ii
誌 謝 iii
Table of Content iv
List of Figures vi
List of Tables viii
Chapter 1 Introduction 1
1.1 Observation 4
1.2 Motivation and Objective 5
1.3 Organization of this thesis 6
Chapter 2 Background and Related Work 7
2.1 Background 7
2.1.1 Register Reassignment Problem 7
2.1.2 Calling Convention 8
2.1.3 Integer Linear Programming 8
2.2 Related Work 9
2.2.1 Ku’s Method 10
2.2.2 Discussion of Ku’s Method 13
Chapter 3 ILP Formulation for Register Reassignment MethodⅠ 15
3.1 Overview 15
3.2 Description of Register Reassignment 16
3.3 Notations 17
3.3.1 ISA Features 17
3.3.2 Function Features 19
3.3.3 Reassignment Matrix 20
3.4 Formulation 20
3.4.1 Objective Function 20
3.4.2 Constraints 33
3.4.3 Summary 35
3.5 Example 37
3.5.1 Objective Function 40
3.5.2 Register Usage Constraints 40
3.5.3 Register Reassignment Constraints 41
3.5.4 Instruction Operands Constraints 41
3.5.5 Reassigning to Small Set Register Constraints 43
Chapter 4 ILP Formulation for Register Reassignment MethodⅡ 45
4.1 Notation 45
4.1.1 ISA Features 46
4.1.2 Function Features 47
4.1.3 Reassignment Matrix 48
4.2 Formulation 49
4.2.1 Objective Function 49
4.2.2 Constraints 51
4.3 Example 52
4.3.1 Objective Function 55
4.3.2 Web Usage Constraints 55
4.3.3 Register Reassignment Constraints 56
4.3.4 Web Interference Constraints 56
4.3.5 Instruction Operands Constraints 60
4.3.6 Reassigning to Small Set Register Constraints 61
4.3.7 Callee-Saved Registers Overheads Constraints 62
Chapter 5 Experiments 65
5.1 Environment 65
5.1.1 IBM ILOG CPLEX 65
5.1.2 LLVM 66
5.1.3 Target Architecture 66
5.2 Benchmark Evaluation Results 67
5.3 Experiments Discussion 70
5.3.1 Discussion of MethodⅠ 70
5.3.2 Discussion of MethodⅡ 73
Chapter 6 Conclusions and Future Works 75
Reference 77

[1] Advanced RISC Machine Ltd. http://www.arm.com.
[2] MIPS Technology http://www.mips.com/.
[3] Andes Technology. Andes Instruction Set Architecuture Specification, 2008. Available: http://www.andestech.com
[4] "microMIPS Instruction Set Architecture. Uncompromised Performance, Minimum System Cost. MD00690 Revision 01.00. Oct. 2009."
[5] R. Phelan, "Improving Arm Code Density and Performance -- New Thumb Extensions to the Arm Architecture. Arm Thumb-2 Core Technology Whitepaper," June, 2003 2003.
[6] A. Krishnaswamy and R. Gupta, "Mixed-width instruction sets," Commun. ACM, vol. 46, pp. 47-52, 2003.
[7] The SPEC2000 Benchmark, http://www.spec.org/cpu2000/.
[8] MediaBench, http://euler.slu.edu/~fritts/mediabench/.
[9] MiBench, http://www.eecs.umich.edu/mibench/.
[10] T.-Y. Yang, "Register Allocation of JIT Compiler for Mixed-Width ISA for Code Size Reduction," Master Thesis, Department of Computer Science, National Chiao-Tung University, HisnChu,Taiwan, R.O.C, 2009.
[11] J.-S. Wang, et al., "Reducing Code Size by Graph Coloring Register Allocation and Assignment Algorithm for Mixed-Width ISA Processor," the Proceedings of the 2009 International Conference on Computational Science and Engineering, 2009, Volume 2,pp. 174-181.
[12] Bor-Yeh Shen, Wei-Chung Hsu, and Wuu Yang, "Register Reassignment for Mixed-Width ISAs is an NP-Complete Problem," the Proceedings of the International Multi-Conference on Complexity, Informatics and Cybernetics (IMCIC 2010), Orlando, Florida, USA, April 6-9, 2010, pp. 139-143.
[13] S. Lee, et al., "Selective code transformation for dual instruction set processors," ACM Trans. Embed. Comput. Syst., 2007 ,Vol. 6, p. 10,.
[14] A. Halambi, et al., "An Efficient Compiler Technique for Code Size Reduction Using Reduced Bit-Width ISAs," the Proceedings of the conference on Design, automation and test in Europe (DATE), 2002, pp. 402-408.
[15] L. Xianhua, et al., "Efficient code size reduction without performance loss," presented at the Proceedings of the 2007 ACM symposium on Applied computing (SAC), Seoul, Korea, 2007, pp.666-672.
[16] A. Krishnaswamy and R. Gupta, "Profile guided selection of ARM and thumb instructions," SIGPLAN Not. , 2002,vol. 37, pp. 56-64.
[17] T. J. K. E. v. Koch et al., "Integrated instruction selection and register allocation for compact code generation exploiting freeform mixing of 16- and 32-bit instructions," presented at the Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization (CGO 2010), Toronto, Ontario, Canada, 2010, pp. 180-189.
[18] Y.-L. Ku, "Code Size Reduction with Register Reassignment for Mixed-Width ISA Processsors," Master Thesis, Department of Computer Science, National Chiao Tung University, HsinChu, 2009.
[19] P. Barth, Logic-based 0-1 constraint programming: Kluwer Academic Publishers, 1996.
[20] S. S. Muchnick, Advanced compiler design and implementation: Morgan Kaufmann Publishers Inc., 1997.
[21] IBM. (2010, ILOG CPLEX 12.2) http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/.
[22] C. Lattner. The LLVM Compiler Infrastructure. http://llvm.org