计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (10): 35-39.

• 理论研究、研发设计 • 上一篇    下一篇

需求驱动的流敏感别名检查

马晓东,匡碧英,尉红梅   

  1. 江南计算技术研究所,江苏 无锡 214083
  • 出版日期:2013-05-15 发布日期:2013-05-14

Demand-driven flow-sensitive alias checking

MA Xiaodong, KUANG Biying, WEI Hongmei   

  1. Jiangnan Institute of Computing Technology, Wuxi, Jiangsu 214083, China
  • Online:2013-05-15 Published:2013-05-14

摘要: 别名分析的精度影响着很多其他编译优化的效果。在对展开后的循环体做指令调度的时候,不精确的别名分析结果会导致冗余数据依赖的产生,从而限制了调度。流敏感的别名分析因为代价过高而扩展性不好。在流不敏感别名信息的基础上,提出了一种需求驱动的流敏感别名检查方法,能够以流敏感的方式判断两个表达式在某程序点上是否为别名。该方法假设两个表达式之间具有别名关系,从而获取初始的数据流事实。用数据流分析技术计算逆向程序点上的数据流事实。如果在所有逆向路径上的数据流事实中都产生了矛盾,则认为别名关系不成立。实验结果表明,该方法能较好地提高别名分析的精度。

关键词: 别名检查, 流敏感, 需求驱动

Abstract: The precision of alias analysis determines the effects of many other compiler optimizations. While scheduling the instructions in the unrolled loop body, imprecise results of alias analysis can lead to redundant data dependence which restricts the scheduling. Because flow-sensitive alias analysis is very expensive, it doesn’t have good scalability. Based on the flow-insensitive alias information, it proposes a demand-driven, flow-sensitive alias checking method that can report whether two expressions are aliased at any given program point in a flow-sensitive way. It is supposed that these two expressions are aliased and the initial dataflow fact is computed. The dataflow facts at the backward program points are computed using dataflow analysis technique. If contradictions occur in the dataflow fact on all the backward paths, it can be concluded that these tow expressions are not aliased. Experimental result shows that the method can improve the precision of alias analysis.

Key words: alias checking, flow-sensitive, demand-driven