计算机工程

• 体系结构与软件技术 • 上一篇    下一篇

上下文敏感的纵向传播算法

邓朝日,张玉萍,陈 雄,梁 辰   

  1. (上海师范大学信息与机电工程学院,上海 200234)
  • 收稿日期:2012-12-17 出版日期:2014-02-15 发布日期:2014-02-13
  • 作者简介:邓朝日(1987-),男,硕士研究生,主研方向:程序静态分析,计算机辅助设计;张玉萍,教授;陈 雄、梁 辰,硕士研究生
  • 基金项目:
    上海市教委创新基金资助项目(11ZZ124)

Context-sensitive Deep Propagation Algorithm

DENG Zhao-ri, ZHANG Yu-ping, CHEN Xiong, LIANG Chen   

  1. (College of Information, Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai 200234, China)
  • Received:2012-12-17 Online:2014-02-15 Published:2014-02-13

摘要: 通过基于包含的指针分析在线优化技术中的纵向传播方法,改进基于调用图上下文敏感指针分析的环消除技术,提出一种上下文敏感的纵向传播算法。初始化约束图,在约束图中进行环探测及其合并,执行差异传播并循环处理复杂约束,直到一次调用纵向传播例程后图中所有结点指向集不变为止,从而得到图中各结点到其指向集的映射。应用CIL工具的实验结果表明,该算法能有效地对源程序进行上下文敏感的指针分析,与环消除技术相比,在分析大规模程序时具有更高的时间效率。

关键词: 在线优化, 纵向传播, 调用图, 上下文敏感指针分析, 环消除, 约束图

Abstract: Through using Deep Propagation(DP) algorithm, which is the techniques of inclusion based pointer analysis on-line optimization technology, to optimize the technology of cycle elimination based on invocation graph context-sensitive pointer analysis, and then puts forward a new context-sensitive DP algorithm. It initializes constraint graph, explores and merges ring, executes difference propagation and circulates processing complex constraints in the diagram, until all the point-to set of all nodes no longer change after executive vertical transmission routines for once, then gets mapping of each node in the graph to the point-to set. Using the CIL tool for experiment, results show that the proposed algorithm has higher time efficiency when analyzing the same large scale program compared with cycle elimination technology.

Key words: on-line optimization, Deep Propagation(DP), invocation graph, context-sensitive pointer analysis, cycle elimination, constraint graph

中图分类号: