支援GCC RTL表示式之別名分析之實作

Implementation of an Alias Analysis for GCC RTL Representation

彭詠靖(Yung-Ching Peng)

指導教授 ： 陳鵬升

國立中正大學/工學院/資訊工程學系/碩士(2014年)

摘要

別名分析 (alias analysis) 在編譯器上，是用來決定兩次記憶體存取是否會參考到相同的記憶體位址的一個機制。編譯器在執行最佳化階段時會使用到別名分析的結果來產生有效率的程式碼。
GCC (GNU Compiler Collection) 是一個compiler infrastructure。由於GCC擁有一些特性像是開放原始碼、有效率的目的碼與可移植性，使得GCC廣泛應用在不同的領域上。在GCC編譯過程中，GCC會先剖析原始碼，然後轉換成高階中間語言 (intermediate language)，GENERIC與GIMPLE，接著轉換成低階中間語言RTL，最後由RTL產生目標組合語言。
我們的研究是在GCC的中間語言RTL (Register Transfer Language) 上實作intra-procedural flow-sensitive的別名分析。我們實作的別名分析演算法是基礎於Debray所提出的residue-based alias analysis並再加入RTL中的memory region的資訊用以協助判斷別名關係。我們在GCC中實作本研究提出的別名分析演算法並且整合分析結果於RTL的最佳化pass，像是dead store elimination與instruction scheduling。
我們從SPEC CPU2006中選擇7個benchmark程式做為實驗評估。由實驗分析結果得知，在效能上，我們提出的別名分析演算法與原來在GCC RTL-level的別名分析方法是相差無幾。此篇研究協助我們了解，在GCC RTL-level的alias analysis如何與RTL最佳化pass互動，並且提供了可用的資訊給未來在RTL-level的alias analysis研究。

關鍵字

編譯器最佳化 ； 別名分析

並列摘要

Alias analysis determines whether a memory address may be accessed by separate memory references. Many compiler optimizations rely on alias analysis results to provide better effectiveness. GCC (GNU compiler collection) is a popular compiler infrastructure with the features of open source (GNU GPLv3), high code quality, and portability. During the GCC compilation, a source program is parsed and transferred to the high-level intermediate representations (IR), GENERIC and GIMPLE, and then lowered to the low-level IR, RTL, and finally translated to target assembly codes.
In this thesis, we develop an intra-procedural, flow-sensitive alias analysis on GCC RTL. The proposed alias analysis algorithm is based on the residue-based global alias analysis. We enhance the method by adding memory region information to help memory disambiguation. The proposed algorithm is implemented based on GCC and properly integrated with GCC RTL-level optimizations: dead store elimination and instruction scheduling. Seven benchmark programs selected from SPEC CPU 2006 are used for the evaluation. The experimental results show that the proposed algorithm has similar results as the original GCC RTL-level alias analysis. This study can help us to understand the original GCC alias analysis and its interaction with RTL-level optimizations. In addition, this study provides useful information to further improve GCC RTL-level alias analysis.

並列關鍵字

GCC ； compiler optimization ； alias analysis ； RTL

參考文獻

[15] Sanjiv K. Gupta and Naveen Sharma, Alias Analysis for Intermediate Code. In Proceedings of the 2003 GCC Development’s Summit, pages 71-78, 2003.

[1] A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, vol. 1009. Addison-Wesley, 2nd ed., 2007.

[2] GCC. GCC, the GNU Compiler Collection - GNU project - Free software Foundation (FSF). http://gcc.gnu.org. [Online; accessed 17-June-2014].

[3] GCC. GNU Compiler Collection (GCC) Internals. https://gcc.gnu.org. [Online; accessed 17-June-2014].

[4] Jason Merrill, GENERIC and GIMPLE: A new tree representation for entire functions. In Proceedings of the 2003 GCC Development’s Summit, pages 171-193, 2003.