面向C2VHDL编译器的基本块级指针分析算法

吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (02): 417-423.

面向C2VHDL编译器的基本块级指针分析算法

郭振华, 吴艳霞, 张国印, 杨杰, 顾国昌

哈尔滨工程大学计算机科学与技术学院, 哈尔滨 150001

收稿日期:2012-01-14 出版日期:2013-03-01 发布日期:2013-03-01
通讯作者: 吴艳霞(1979-),女,副教授,博士.研究方向:计算机体系结构,编译技术,可重构计算.E-mail:wuyanxia@hrbeu.edu.cn E-mail:wuyanxia@hrbeu.edu.cn
作者简介:郭振华(1988-),男,博士研究生.研究方向:计算机体系结构,可重构计算.E-mail:hrbeu.guozhenhua@gmail.com
基金资助:
国家自然科学基金项目(61003036);黑龙江省自然科学基金项目(QC2010049);黑龙江省教育厅基金项目;中央高校基本科研业务费专项项目(HEUCF100606).

Basic block-level pointer analysis algorithm for C2VHDL compiler

GUO Zhen-hua, WU Yan-xia, ZHANG Guo-yin, YANG Jie, GU Guo-chang

College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China

Received:2012-01-14 Online:2013-03-01 Published:2013-03-01

摘要/Abstract

摘要： 针对现有的C2VHDL编译器中指针编译技术所存在的缺陷,通过对传统指针分析算法进行研究,在基于低级虚似机(LLVM)面向CPU-FPGA应用的可重构编译器ASCRA架构上,设计并实现了一种以基本块为分析粒度的基于控制流图的流敏感上下文敏感指针分析算法。在可重构编译器ASCRA生成硬件VHDL程序时提供指针访存控制辅助信息。实验结果表明:在保证C2VHDL结果正确的前提下,该算法在简化了分析过程的同时,能够达到与流敏感指针分析相同的精度。与指针还原技术相比,该算法能够支持更多的指针数据类型。采用该算法的编译器ASCRA生成的硬件程序在硬件资源占用情况和运行速度两方面与指针还原技术相比都能够达到相同的硬件效果。

关键词: 计算机系统结构, 可重构编译, 指针分析算法, 低级虚拟机

Abstract: To overcome the shortcoming of existing C2VHDL compiler dealing with pointer, based on the investigation of traditional algorithm, a block-based pointer analysis algorithm was designed and realized in the ASCRA compiler, which is developed for the application of CPU-FPGA based on LLVM. Experiment results show that this algorithm can simplify the pointer analysis process, meanwhile, achieve the same precision as the flow sensitive pointer algorithm. This algorithm also can support more pointer data types than pointer reduction technology. The VHDL programs generated by ASCRA using this algorithm can achieve the same resource consumption and processing speed as the pointer reduction technology.

Key words: computer architecture, compiler for reconfigurable computing, pointer analysis algorithm, low level virtual machine (LLVM)

中图分类号:

TP312

郭振华, 吴艳霞, 张国印, 杨杰, 顾国昌. 面向C2VHDL编译器的基本块级指针分析算法[J]. 吉林大学学报(工学版), 2013, 43(02): 417-423.

GUO Zhen-hua, WU Yan-xia, ZHANG Guo-yin, YANG Jie, GU Guo-chang. Basic block-level pointer analysis algorithm for C2VHDL compiler[J]. 吉林大学学报(工学版), 2013, 43(02): 417-423.

参考文献

[1] Li J, He H, Man H, et al. A general-purpose FPGA-based reconfigurable platform for video and image processing//Proceedings of the 6th International Symposium on Neural Networks: Advances in Neural Networks-Part Ⅲ, 2009: 299-309.

[2] Bjarne Steensgaard. Points-to analysis in almost linear time//Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1996: 32-41.

[3] Andersen L O. Program analysis and specialization for the C programming language. Copenhagen:University of Copenhagen, 1994.

[4] Choi J, Burke M, Carini P. Efficient flow-sensitive inter-procedural computation of pointer-induced aliases and side effects//In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages, 1993: 233-245.

[5] Emami M. A practical inter-procedural alias analysis for an optimizing/paralleling C compiler. Montreal:School of Computer Science, McGill University. Montreal, Canada, 1993.

[6] Guo Zhi, Najjar Walid, Buyukkurt Betul. Efficient hardware code generation for FPGAs[J]. ACM Transactions on Architecture and Code Optimization (TACO), ACM, 2008.

[7] Gupta S, Dutt N D, Gupta R K, et al. SPARK: a high-level synthesis framework for applying parallelizing compiler transformations//Proceedings of the 16th International Conference on VLSI Design (VLSI), Paul Chow, 2003: 461-466.

[8] Alex Jones, Debabrata Bagchi, Satrajit Pal. PACT HDL: A C Compiler Targeting ASICs and FPGAs with Power and Performance Optimizations//Proceedings of the 2002 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, 2002: 188-197.

[9] Séméria L, Micheli G De. SPC: synthesis of pointers in C: application of pointer analysis to the behavioral synthesis from C//In Proc Int Conf Computer-Aided Design ICCAD’98, San Jose, CA,1998:321-326.

[10] Lau D, Pritchard O, Molson P. Automated generation of hardware accelerators with direct memory access from ANSI/ISO Standard C Functions//FCCM’06,2006:45-54.

[11] Franke B, O'Boyle M F. A complete compiler approach to auto-parallelizing C programs for multi-DSP systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2005: 234-245.

[12] Hardekopf B, Lin C. Semi-sparse flow-sensitive pointer analysis//In POPL'09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principle of Programming Languages, New York, NY, USA, 2009: 226-238.

[13] 王甜甜,苏小红,马培军. 程序标准化转换中的指针分析算法研究[J]. 电子学报,2009, 37(5):1104-1108. Wang Tian-tian, Su Xiao-hong, Ma Pei-jun. Research on pointer analysis algorithm for program standardization[J]. Chinese Journal of Electronics. 2009, 37(5): 1104-1108.

[14] 吴艳霞,顾国昌,孙延腾,等. 面向应用的可重构编译ASCRA[J]. 计算机科学与探索,2011, 5(3): 267-279. Wu Yan-xia, Gu Guo-chang, Sun Yan-teng, et al. Application-specific compiler for reconfigurable architecture ASCRA[J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(3): 267-279.

[15] Cheng Ben-Chung, Hwu Wen-Mei W. Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation//In proceedings of the ACM SIGPLAN'00 Conference on Programming Language Design and Implementation. ACM Press, 2000: 57-69.

相关文章 15

[1]	余宜诚, 胡亮, 迟令, 初剑峰. 一种改进的适用于多服务器架构的匿名认证协议[J]. 吉林大学学报(工学版), 2018, 48(5): 1586-1592.
[2]	董坚峰, 张玉峰, 戴志强. 改进的基于狄利克雷混合模型的推荐算法[J]. 吉林大学学报(工学版), 2018, 48(2): 596-604.
[3]	赵博, 秦贵和, 赵永哲, 杨文迪. 基于半陷门单向函数的公钥密码[J]. 吉林大学学报(工学版), 2018, 48(1): 259-267.
[4]	刘磊, 刘利娟, 吴新维, 张鹏. 基于ECPMR的编译器测试方法[J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267.
[5]	董立岩, 王越群, 贺嘉楠, 孙铭会, 李永丽. 基于时间衰减的协同过滤推荐算法[J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272.
[6]	于斌斌, 武欣雨, 初剑峰, 胡亮. 基于群密钥协商的无线传感器网络签名协议[J]. 吉林大学学报(工学版), 2017, 47(3): 924-929.
[7]	邓昌义, 郭锐锋, 张忆文, 王鸿亮. 基于平衡因子的动态偶发任务低功耗调度算法[J]. 吉林大学学报(工学版), 2017, 47(2): 591-600.
[8]	魏晓辉, 刘智亮, 庄园, 李洪亮, 李翔. 支持大规模流数据在线处理的自适应检查点机制[J]. 吉林大学学报(工学版), 2017, 47(1): 199-207.
[9]	郝娉婷, 胡亮, 姜婧妍, 车喜龙. 基于多管理节点的乐观锁协议[J]. 吉林大学学报(工学版), 2017, 47(1): 227-234.
[10]	魏晓辉, 李翔, 李洪亮, 李聪, 庄园, 于洪梅. 支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议[J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.
[11]	车翔玖, 梁森. 一种基于大顶堆的SPIHT改进算法[J]. 吉林大学学报(工学版), 2016, 46(3): 865-869.
[12]	董悦丽, 郭权, 孙斌, 康玲. 药物分子对接动态任务迁移优化[J]. 吉林大学学报(工学版), 2015, 45(4): 1253-1259.
[13]	匡哲君，师唯佳，胡亮. 基于无线传感器网络的角色成员关系剩余能量新算法[J]. 吉林大学学报(工学版), 2015, 45(2): 600-605.
[14]	张忆文，郭锐锋. 实时系统混合任务低功耗调度算法[J]. 吉林大学学报(工学版), 2015, 45(1): 261-266.
[15]	张忆文^{1, 2}, 郭锐锋¹. 制的容错节能调度算法[J]. 吉林大学学报(工学版), 2014, 44(4): 1112-1117.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed