以執行監測爲基礎之別名分析

Profile-based Alias Analysis

鄭宇修(Yu-Hsiu Cheng)

指導教授 ： 劉邦鋒

共同指導教授 ： 游本中

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.01112

摘要

在許多程式分析中，別名分析扮演了一個重要的角色。跟傳統缺乏動態資訊的靜態別名分析相比，使用執行監測的方法具有極大的潛力，因爲並不需要做過度的預測。在這篇論文中，我們提出一個用執行監測的框架以用來做別名分析。我們發現使用執行監測的方法可以比傳統的靜態別名分析獲得更多的非別名答案。儘管我們可以獲得更準確的別名分析，但執行時間並沒有太多的成長。我們也針對文本性質和域性質分別做了探討，並發現在文本性質中，非環式的方式較其他的方法有效以及域性質對別名分析是有很大的影響等結論。

關鍵字

別名分析 ； 執行監測 ； Open64 ； 記憶體分辨 ； 文本性質 ； 域性質

並列摘要

Alias analysis plays an important role in various program analyses Comparing to traditional static alias analysis which struggles for precision under the lack of dynamic information, profile techniques show a great potential in this area since they don't need to make any over-approximation. In this paper, we propose an framework which uses profile techniques to perform alias analysis. We can get more 52 % queries than the worst case for 429.mcf. We also find that although we have a more accurate alias analysis, the performance has insignificance gain. And we simulate several schemes in context sensitivity and field sensitivity. We find that acyclic scheme in context sensitivity is useful and field sensitivity is important for alias analysis.

並列關鍵字

Alias analysis ； Profiling ； Open64 ； Memory disambiguation ； Context sensitivity ； Field sensitivity

參考文獻

[6] R. Ghiya, D. Lavery, and D. Sehr. On the importance of points-to analysis and other memory disambiguation methods for c programs. SIGPLAN Not., 36:47–58, May 2001.

[15] C. Lattner, A. Lenharth, and V. Adve. Making context-sensitive points-to analysis with heap cloning practical for the real world. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 278–289, New York, NY, USA, 2007. ACM.

[16] T.W. Sheng,W.G. Chen, andW.M. Zheng. A context-sensitive poiner analysis phase in open64 compiler. In Open64 Workshop in conjunction with IEEE/ACM International Symposium on Code Generation and Optimization, 2009.

[18] J. Whaley and M.S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 131–144, New York, NY, USA, 2004. ACM.

[19] D.J. Pearce, P.H.J. Kelly, and C. Hankin. Online cycle detection and difference propagation for pointer analysis. In Third IEEE International Workshop on Source Code Analysis and Manipulation, pages 3–12, 2003.