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

Reducing Code Size by Graph Coloring Register Allocation and Assignment Algorithm for Mixed-Width ISA Processors

王志先(Jyh-Shian Wang)

指導教授 ： 單智君

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00605

摘要

由於現今的嵌入式系統需要越來越多的程式功能，但又不希望增加記憶體大小，因此減少程式碼大小即成為一個關鍵性的問題。其中一種解決辦法是使用"混合寬度指令集架構"，這類架構通常包含一個正常寬度指令集(通常是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.

並列關鍵字

Register Allocation ； Compiler ； Instruction Set Architecture (ISA) ； Mixed-width ISA ； Code size ； Embedded System

參考文獻

[5] Bor-Sung Liang, June-Yuh Wu, Jih-Yiing Lin, Ming-Chuan Huang, Chi-Shaw Lai, Yun-Yin Lien. Ching-Hua Chang, Pei-Lin Tsai, and Ching-Peng Lin, “Instruction set architecture scheme for multiple fixed-width instruction sets and conditional execution”, International Symposium on VLSI Design, Automation and Test, Sunplus Technol. Co., Ltd., Hsinchu, Taiwan, 2005.

[7] T. Zeitlhofer, and B. Wess, "A comparison of graph coloring heuristics for register allocation based on coalescing in interval graphs", Proceedings of the 2004 International Symposium on Circuits and Systems, 4: IV-529-32 Vol. 4, May 2004

[9] Andrew W. Appel, Modern Compiler Implementation in Java: Basic Techniques, Cambridge University Press, 1997.

[11] Jonathan S. Turner, “Almost all k-colorable graphs are easy to color”, Journal of Algorithms, March 1988, 9(1):63–82.

[12] Chris Lattner, and Vikram Adve, “LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation”, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, PaloAlto, California, March 20-24, 2004, p.75.