階層式形狀分析之實作與評估

Implementation and Evaluation of Hierarchical Shape Analysis

李昀宙(YUN-ZHOU LI)

指導教授 ： 陳鵬升

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

摘要

階層式狀分析是一種技術，用來發掘c語言程式中由指標分配這一類的語句所產生的資料結構之形狀。階層式形狀分析的目的是要擷取資料結構中有用的形狀資訊來引導編譯器去實行進一步的程式平行或優化。在本論文中我們實作了一個階層式形狀分析的演算法。我們使用了Cetus這樣的編譯器基礎設施來輔助我們的實作。對於我們所測試的benchmark程式，其實驗結果顯示了我們所提出的實作能成功地獲得階層式形狀的資訊。

關鍵字

指標分析 ； 編譯器 ； 形狀分析 ； 程式分析

並列摘要

Hierarchical shape analysis is a technique that is used to discover the shape of the data structures generated by pointer assignments in C programs. The purpose of hierarchical shape analysis is to catch the useful shape information of data structures to guide compilers in further aggressive parallelization or optimization. In this thesis, we implement a hierarchical shape analysis algorithm. The compiler infrastructure Cetus is used to help our implementation. For the tested benchmark programs, the experimental results show that the proposed implementation can successfully obtain the hierarchical shape information.

並列關鍵字

Pointer Analysis ； Compiler ； Shape Analysis ； Program Analysis

參考文獻

[8] Larus, J. R. 1989. Restructuring Symbolic Programs for Concurrent Execution on. Tech. rep., Berkeley, CA.

[9] Stransky, J. 1992. A lattice for abstract interpretation of dynamic (LISP-like) structures. Inf. Comput. 101, 1, 70–102.

[10] Hwang, Y.-S. and Saltz, J. H. 2003. Identifying parallelism in programs with cyclic graphs. J. Parallel Distrib. Comput. 63, 3, 337–355.

[13] Hendren, L. J. 1990. Parallelizing programs with recursive data structures. Ph.D. thesis, Department of Computer Science, Cornell University, Ithaca, NY.

[14] Ghiya, R. and Hendren, L. J. 1996a. Connection analysis: A practical interprocedural heap analysis for C. Int. J. Parallel Program. 24, 6, 547–578.