Chinaunix首页 | 论坛 | 博客
  • 博客访问: 959530
  • 博文数量: 104
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1868
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(104)

文章存档

2013年(1)

2012年(9)

2011年(41)

2010年(3)

2009年(3)

2008年(47)

分类:

2008-03-26 18:44:04

今天在看这篇文章,有一个地方很不明白。
在文章的3.1.3部分,RHS(A)为什么是MayUse(S)+(MayMod(S)-MustMod(S))?我觉得应该只是MayUse(S)。

这篇文章终于看完了,好长。也许这是我认真看完的最长的论文了。
不过,它的内容还是蛮值得看的。
首先说一下形式。我觉得这篇文章的形式很好,很像真正的论文。它给出定义,给出算法。每一个算法有正确性的证明和复杂度的评估。并且在大量实际程序上进行了实验并给出了结果。很严谨,很不错,很值得学习。

好的,它的内容比较老,还是当年提出SSA不久的时候给出的。
当时,大家都比较普遍的认为SSA的确是一种比较好的中间表示,并且,有很多优化和分析可以在其上方便的进行。但是,将一个程序转换成SSA的形式却不简单,尤其是要找出插入PHI函数的节点的算法。
如果在每一个汇合节点为每一个变量都插入PHI函数,显然,算法简单,但是得到的结果将含有大量的无用的PHI函数,如果只是插入必须的PHI节点,算法的复杂度有比较高。
本文章提出了DominaceFronter的概念,通过计算节点的DominanceFronter集合来找出需要插入PHI函数的节点。同时,DF这个概念对于构造控制依赖也很有帮助。
文章通过证明和实验指出,对于绝大部分实际的程序,使用DF计算SSA形式和控制依赖的复杂度和程序的长度成线性关系,并且得到的SSA的代码的大小也和程序的长度成线性关系。充分证明了,在实际的使用中可以使用SSA作为编译器的中间表示。
文章同时也给出了从SSA形式转换成一般形式的算法。这个算法是平凡算法(将每一个PHI函数用多个赋值替换)加上两个额外的优化:平凡算法之前进行死代码消除,平法算法中使用图染色的方法分配变量。据称,这样可以生成高效的代码。
该文章值得一看。
阅读(1000) | 评论(0) | 转发(0) |
0

上一篇:memory ssa

下一篇:我对《code reading》的评价

给主人留下些什么吧!~~