一种面向向量化的动态指针别名分析框架

doi:10.11896/j.issn.1002-137X.2015.03.005

摘要/Abstract

摘要： 指针别名分析是数据流分析中的关键性技术,其分析结果是编译优化和程序变换的基础。在向量化方法和动态指针别名分析相关研究的基础上,设计了一种面向向量化的动态指针别名分析框架。该框架通过动态插桩和试运行提取指针别名信息,并反馈到向量化阶段指导向量化代码生成。从提取候选别名分析集、插桩及试运行和反馈优化3个方面对整体框架进行分析和研究。该框架基于Open64实现,并以通用测试集GCC-VECT和典型应用进行了实验评估,结果表明,该框架相比静态指针别名分析具有更精确的别名分析结果,该结果能够有效改进向量化程序的加速比。

关键词: 指针别名分析,向量化,动态分析,依赖分析

Abstract: Pointer alias analysis is a key technology in data-flow analysis,whose results are the basis of compiler optimization and program transformation.Based on the related research of vectorization method and dynamic pointer alias analysis,a dynamic pointer alias analysis framework oriented to vectorization was designed.The dynamic pointer alias information is extracted by dynamic instrument and test run,and the vectorization code generation is guided by the feedback information.The whole framework was studied from three aspects,which are candidate alias analysis set extraction,instrument and test run.The framework was implemented on Open64 and evaluated in benchmark GCC-VECT and typical applications.The experimental results show that the framework has the more precise alias analysis results compared with static pointer alias analysis,and can significantly improve the speedup of vectorization program.

Key words: Pointer alias analysis,Vectorization,Dynamic analysis,Dependence analysis

刘鹏,赵荣彩,李朋远. 一种面向向量化的动态指针别名分析框架[J]. 计算机科学, 2015, 42(3): 26-30. https://doi.org/10.11896/j.issn.1002-137X.2015.03.005

LIU Peng, ZHAO Rong-cai and LI Peng-yuan. Dynamic Pointer Alias Analysis Framework for Vectorization[J]. Computer Science, 2015, 42(3): 26-30. https://doi.org/10.11896/j.issn.1002-137X.2015.03.005

参考文献

[1] Pryanishnikov I,Krall A,Horspool N.Pointer Alignment Ana-lysis for Processors with SIMD Instructions[C]∥Proceedings of the 5th Workshop on Media and Streaming Processors.San Diego,CA,2003.50-57
[2] Fink S J,Yahay E,Dor N,et al.Effective typestate verification in the presence of aliasing[J].ACM Transaction on Software Engineering and Methodology(TOSEM),2008,17(2):133-144
[3] Li Lian,Cifuentes C,Keynes N.Practical and effective symbolic analysis for buffer overflow detection[C]∥Proceedings of the Eighteenth ACM SIGSOFT International Symposium on Foundations of Software Engineering(FSE’10).ACM,2010:317-326
[4] Zhu Jian-wen.Towards scalable flow and context sensitivepointer analysis[C]∥Proceedings of the 42nd annual Design Automation Conference(DAC ’05).ACM,2005:831-836
[5] Salcianu A,Rinard M.Pointer and escape analysis for mul-tithreaded programs[C]∥Proceedings of the Eighth ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming(PPoPP ’01).ACM,2001:12-23
[6] Rei T.Expression Data Flow Graph:Precise Flow-SensitivePointer Analysis for C Programs[D].Diss.University of Alberta,2011
[7] Yu Hong-tao,Xue Jing-ling,Huo Wei,et al.Levelby Level:Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code[C]∥Proceedings of the 8^th Annual IEEE/ACM International Symposium on Code Generation and Optimization(CGO’10).ACM,2010:218-229
[8] Hardekopf B,Lin C.Semi-Sparse Flow-Sensitive Pointer Analy-sis[C]∥Proceedings of the 36^th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages(POPL’09).ACM,2009:226-238
[9] Yan Da-cong,Xu Guo-qing,Rountev A.Demand-Driven Con-text-Sensitive Alias Analysis for Java[C]∥Proceedings of the 2011 International Symposium on Software Testing and Analysis(ISSTA’11).ACM,2011:155-165
[10] Li Xin,Ogawa M.An ahead-of-time yet context-sensitive points-to analysis for Java[J].Electronic Notes in Theoretical Computer Science,2009,253(5):31-46
[11] Chris L,Lenharth A,Adve V.Making context-sensitive points-to analysis with heap cloning practical for the real world[J].ACM SIGPLAN Notices,ACM,2007,42(6):278-289
[12] Pearce D J,Kelly P H J,Hankin C.Efficient Field-SensitivePointer Analysis of C[J].ACM Transactions on Programming Languages and Systems(TOPLAS),2007,30(1):4
[13] Yu Hong-tao,Zhang Zhao-qing.An Aggressively Field-Sensitive Unification-Based Pointer Analysis[J].Chinese Journal of Computers,2009,32(9):1722
[14] Experiences coding Non-Uniform Parallem using the CUDA GPGPU Architecture[C]∥NJPLS2.August 2008
[15] Randy A,Kennedy K.Optimizing Compilers For Modern Architectures:A Dependence-based Approach[M].Morgan Kaufmann,2001:790
[16] Samuel L,Amarasinghe S.Exploiting superword level paralle-lism with multimedia instruction sets[J].Sigplan Notices-SIGPLAN,2000,35(5):145-156
[17] Transforming and parallelizing ANSI C programs using pattern recognition[C]∥7th Interational Conference,HPCN Earope 1999 Amsterdam.1999:673-682
[18] Ralf K,Hack S.Whole-function vectorization.Code Generation and Optimization[C]∥2011 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization(CGO).IEEE,2011:141-150
[19] Rajkishore B,Zhao Ji-sheng,et al.Efficient selection of vectorinstructions using dynamic programming[C]∥2010 43rd AnnualIEEE/ACM International Symposium on Microarchitecture (MICRO).IEEE,2010
[20] Markus W,Luk W.Pipeline vectorization.Computer-Aided Design of Integrated Circuits and Systems[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and System,2001,20(2):234-248
[21] Markus M,et al.Dynamic points-to sets:A comparison withstatic analyses and potential applications in program understanding and optimization[C]∥Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering.ACM,2001
[22] Mock M,Berryman M,Chambers C,et al.Calpa:A tool for automating dynamic compilation[C]∥2nd Workshop on Feedback-Directed Optimization.1999:291-302
[23] Manuvir D.Unification-based pointer analysis with directional assignments[J].Acm Sigplan Notices,2000,35(5):35-46
[24] Axel G.Evaluation of dynamic Points-To Analysis[M].2004
[25] Wu Jing-yue,et al.Effective dynamic detection of alias analysis errors[C]∥Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering.ACM,2013
[26] Zhang Kun.Dynamic pointer tracking and its applications[M].2010
[27] Maydan,Dror E,Amarasinghe S P,et al.Array-data flow analysis and its use in array privatization[C]∥Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages.ACM,1993
[28] Hao Yun-long.Research on Profile-Guided SIMD Vectorization Identification and Optimization[D].Information Engineering University,2011

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed