有没有可能直接遍历AST生成SSA形式的中间代码,而不是先生成quad四元式,再转换为SSA形式?

我看的代码lcc, ucc,分别都是生成的DAG和传统的quad四元式,而书上,比如龙书,data flow analysis: theory and pratice都是讲的将普通的四元式转换成SSA形式。据我所知,hotspot的client compiler将HIR改成了SSA形式,但是有没有文档参考。。。 求问有什么资料参考的?
关注者
96
被浏览
1439
嗯这个问题问得好。答案是:可以从AST直接生成SSA,而且这是种很好的做法。
——前提是,输入语言是一种遵守结构化编程思想的语言。Wiki传送门:Structured programming

(我最近业余在做的一个编译器就是直接从AST进SSA的。回头等进展更多之后我再把链接更新到这个回答)

龙书和其它一些编译原理的书在介绍进入SSA形式的算法时,以四元式为输入,原因我猜有这么几个:
  • 从线性代码(四元组)转换为SSA比较general。读者学习了比较general的做法后可以自己演化出针对自己需要的特化做法;
  • 线性代码(四元组)是传统编译器里很常用的IR形式,而SSA相对来说则是新事物。有很多历史比较久的编译器原本已经实现得很完整了,已经有非SSA形式的IR,后来才加入基于SSA形式的优化,所以需要从传统IR转换到SSA形式;
  • 作者就喜欢这么搞(逃

事实上,比较新一点的编译器有不少都是让SSA形式尽可能贯穿整个编译流程的。

例如说LLVM,除了最终的code gen之外,都使用同一种IR——LLVM IR,而它就是始终都是SSA形式的。同时它留了个后门给编译器前端:前端可以选择用alloca来“声明”局部变量,然后让LLVM的mem2reg pass把这些局部变量转进SSA形式,这样前端就不总需要担心生成SSA的负担了。

又例如说HotSpot Client Compiler (C1)、V8 Crankshaft、ART Optimizing Compiler这仨同源兄弟都采用了SSA形式的HIR用于优化,和传统形式的LIR用于寄存器分配和代码生成,
  • ART Optimizing Compiler是从线性的Dex字节码先转成带控制流图(CFG)、带LoadLocal/StoreLocal的线性形式(HGraph),然后计算支配树(dominator tree)和逆后序(reverse post-order)之后,以逆后序遍历控制流图构造SSA形式。
  • HotSpot Client Compiler (C1) 是直接在线性Java字节码上扫描两次,先找到基本块边界、计算逆后序并找出循环之后,直接从字节码构造SSA形式。
  • V8 Crankshaft则是直接从AST构造SSA形式,不用计算什么支配关系或逆后序啥的。

(更新:哈哈,我才回答这个问题,ART就准备把SsaBuilder合并到HGraphBuilder里了——就变得跟C1的结构一样了。参考这里:Change 202670: ART: Run SsaBuilder from HGraphBuilder

这仨兄弟进入SSA形式的方式,ART Optimizing虽然比C1多了一个中间步骤(生成了非SSA形式的HIR),但本质上差别不大,前者可能只是比后者在处理irreducible loop要略好一些;但V8 Crankshaft则跟另外俩兄弟都不一样。差异在哪里?

我觉得最重要的差异在于:
  • ART与HotSpot输入给编译器的代码都是不带CFG、使用显式label的线性代码。这种代码形式不保证控制流是结构化的(structured,或者说没有irreducible control flow),因而编译器拿到代码首先得重新找出基本块边界,并且在了解了控制流图的情况后对它做深度优先遍历来计算逆后序,然后再以逆后序遍历CFG来构造SSA。
  • V8 Crankshaft以AST为输入。由于JavaScript自身是结构化的编程语言,使用JavaScript无法写出irreducible loop,而且结构化的控制流仍然隐藏于AST中(包括结构化的分支和循环)——这样控制流的汇合点(join point)都是已知的,而且除了循环之外处理到其它控制流汇合点时它的支配块肯定都已经处理了,循环保守处理一下就好。可以直接利用这些信息来构造SSA。

讲述直接从AST(或者甚至从源码)构造SSA形式的论文,有这么几篇是我比较喜欢的(从老到新):
上面第三篇论文其实也提到了,构造SSA的简易做法其实很容易从只能处理结构化控制流扩展为可以处理任意控制流(包括irreducible loop)。不过,如果已知输入的程序是结构化的,就不用那么高端的方法而可以用更简单的做法了,何乐而不为。