问题背景:题主正在做的编译器习作的源语言的C的子集(某种C-Minus?),而实现语言是Java。
并且IR的设计是想用龙书系的三地址指令(TAC,three-address code)来做。
龙书讲前端的部分感觉还比较直观,而且有第二章以及附录A的实际代码例子,就算是初学者也应该比较好着手学习;但是讲后端的部分由于没多少配合演示的代码,确实容易感到怎么读都似懂非懂,然后又不知道应该如何组织实际代码去实现书上讲的知识点。
对此我自己深有体会,头几次读龙书都觉得后端的部分似乎读懂了但还是不知道该怎么下手写代码。所以很乐意来回答题主的问题,好让后人少走弯路。
而
【Crafting a Compiler】(编译器构造)我觉得写得详细是挺详细,就是有点浅所以读得很不过瘾;而且在前端花了太多篇幅,有很严重的虎头蛇尾感。
不过这个配置或许正好符合原本作者的目标读者群的需求吧。它前面讲得详细的部分真的很详细,可操作性很强,倒是挺适合初学用。
=======================================================
内存还是文件?
现代编译器的(主要)都是在内存里一口气完成整个编译流程,而不向外写中间文件的。所以题主可以主要考虑in-memory形式的IR。
例外之一是微软的Visual C++编译器。它继承了以前内存极其紧张时的分阶段式设计,将编译器前端(c1.dll/c1xx.dll)与编译器后端(c2.dll)分开在两个不同的进程里,两者由一个驱动进程(cl.exe)协调;前端用中间临时文件来传递AST/IR给后端。这个设计一直延续了下来…
像
PCC这种老爷编译器也是前后端分离,中间用临时文件传递IR。
如果想易于开发/调试的话,配套设计一种文本形式的IR也是极好的。LLVM IR就是这方面一个非常好的例子。这样会很利于单独测试编译器里的某些IR变换。
受LLVM IR启发的MicroVM的
Mu IR也设计为有in-memory形式和配套文本形式。其中一些IR指令的in-memory版的Scala实现可以看这里:
https:// github.com/microvm/micr ovm-refimpl2/blob/master/src/main/scala/uvm/ssavariables/ssavariables.scala就是不知道下面的三地址形式的中间代码不知道如何存放,是直接放到一个文件还是放在内存中的数据结构
所以回答这个问题:请先考虑以in-memory形式为主,这个是主干;然后可选的,作为利于调试的手段配套设计一种文本形式;两种形式之间最好能做到无损的相互转换。
=======================================================
IR设计
然后具体要怎么设计IR便于优化…这个水就深了,而且虽然有些选择非常重要,更多的buzzword选择其实并不真的很影响功能,而更多的是个人代码风格的问题。就像大括号写行末还是换行写还是换行+缩进写一样…
我不想在「个人偏好」方面乱放炮,总之题主自己摸索一下选择自己喜欢的就好 >_<
下面针对龙书系的三地址IR来展开。以虎书为代表的树形IR就按下不表了。
TAC的典型实现方式是Quad(四元组),一个operator加上3个operand。其典型形式是:
op
src1
,
src2
,
dest
或者有些记法把它记为:
dest
=
op
src1
,
src2
两种记法指的是同一种东西。
四元组,顾名思义,其实就是一个数据结构把四个字段打包起来:
(op, src1, src2, dest)
不过实际写代码时这里有许多东西要选择:
别着急,上面这些问题都不是「致命选择」。条条道路通罗马,虽然有些路走起来会有点崎岖…题主不要害怕,一开始每个地方都随便选一种做法就好了。后面写得多了就会慢慢体会到某些选择或许选别的路更好,重要的是最初要迈出第一步做出第一个选择。
采用最最最传统的方式来做的话,可能会写成:
enum
Opcode
{
// add, sub, mul, div, load, store, if, goto, call, return, label ...
}
// 变量
class
Var
{
// ...
}
// 一条IR指令
class
Quad
{
// 四元组
Opcode
op
;
// 单独把opcode写做一个字段挺不Java的,许多C/C++写的编译器喜欢这样,Java可以用继承
Var
src1
;
Var
src2
;
Var
dest
;
Quad
prev
,
next
;
// 双向链
}
// 整体IR
class
IR
{
Quad
head
;
// 用一个线性链表来表示整个函数的逻辑;没有显式CFG,用label来指定跳转目标
}
这样用单一结构体(例中Quad类)作为IR的指令的做法常见于用C写的编译器。Java的话可以对IR类型创建一套类层次,通过不同的子类来表达不同opcode的语义;这些子类也不需要采用同样的layout——有些子类可以只要更少的字段(例如实现单目运算符就只需要1个src operand),而有些可能需要更多字段。
龙书的第二章和附录A所演示的前端范例生成的中间代码是一种用label表达控制流的线性代码,没有显式构造CFG。这种代码可以很直观的映射到上面的IR设计。
但是后续要做优化需要控制流信息时,还是得遍历一次这个线性IR去显式构造CFG,我觉得反而麻烦…
如果是要做一个非常非常简单的编译器,其middle-end到back-end只有一种IR贯穿其中的话,那采用这种IR也有一定道理:它在从AST翻译过来的时候不需要显式创建CFG,而最终要生成目标机器代码时对应关系比较好——目标机器也多半不会有显式的CFG概念,而是用label+有fallthrough语义的branch来实现条件控制流,正好跟这种IR一样。这就可以让中间需要CFG的优化变得完全是可选的,而不必一开始就非得实现CFG不可。
但是,一旦开始想认真做更多优化,这种IR就会让人感到特别蛋疼…
然后假如不要变量、要CFG、要SSA的话,可能会写成:
enum
Opcode
{
// add, sub, mul, div, load, store, if, goto, call, return, phi ...
}
// 一条IR指令
class
Quad
{
// 四元组
Opcode
op
;
Quad
src1
;
// 直接使用别的指令作为operand
Quad
src2
;
// 不需要指定dest; 自身就代表了运算和值
Quad
prev
,
next
;
// 双向链
}
// 一个基本块
class
BasicBlock
{
Quad
head
;
// 用一个线性链表来表示整个基本块的逻辑;末尾必须是控制流指令;中间不包括phi
ArrayList
<
Quad
>
phis
;
// 记录该基本块开头所需的phi指令
// ArrayList<BasicBlock> successors;
// 后继基本块;该信息可以从该基本块末尾的控制流指令提取,不需要显式用字段记录
// ??? flags;
// 可选的额外信息,可以用来记录诸如按reverse post-order(RPO)遍历CFG的序号,是否是循环开头(loop header),等等
}
class
IR
{
BasicBlock
start
;
// 起始基本块
// List<BasicBlock> blocks; // 所有基本块
// 虽然从start肯定能顺着CFG遍历到所有活着的基本块,但也有些实现为方便而在一个列表里记录下所有基本块的引用;
// 有时候(例如要处理异常的话)有可能有活着的基本块会无法直接从start到达,此时也最好显式记录所有block。
}
是不是有点区别?
许多编译器都会选择直接从AST直接生成带CFG的IR。要参考例子的话,LLVM Tutorial的Kaleidoscope是个好去处。
我写这段的时候LLVM官网正好挂了,所以放个镜像网站的链接:
LLVM Tutorial: Control FlowIR的形式显式的信息越多(例如有显式CFG,采用SSA形式之类),在最初构造这种IR时所需的处理就越多,但是相应的后面做分析的时候就越方便,特别是如果要做稀疏分析(sparse analysis)的话。
这些记录在IR里的额外信息很多都可以看作是一种「缓存」——即便不记录在IR里也可以在后续分析需要的时候从头遍历一次IR来计算出来。但是缓存起来就不用每次重新算,所以比较方便——然而缺点也很明显:这些信息存在IR里是得维护的,有维护成本;每次IR发生变化,缓存的信息可能都得跟着更新。
就看IR的设计者想如何取舍了…
=======================================================
实际项目的例子
龙书系的Quad设计,一种实际实现是JoeQ里的IR。
请参考Stanford CS243课程的资料:
http:// suif.stanford.edu/~cour ses/cs243/joeq/#quads现在可用的一份JoeQ的代码可以从这里下载:
http:// suif.stanford.edu/~cour ses/cs243/hw2/hw2.zip,其中lib/joeq.jar里既包含程序的 class文件也包含源码。
JoeQ是一个用Java实现的「元循环JVM」,内含一个用Java写的、能把Java字节码编译为机器码的编译器。
JoeQ IR就是这个编译器里的IR,实现形式为显式CFG+Quad。Quad可以是传统形式也可以是SSA形式。
@啥玩应啊的回答提醒了我,
Soot的Jimple IR也是TAC。有很多静态代码分析工具基于Soot框架实现,甚至也有直接把Soot用在编译器里作为前端的(例如
RoboVM)。Jimple IR的设计也可以参考,源码在Soot的Github站上可以找到。
我比较熟悉和习惯的一种IR是HotSpot Client Compiler(C1)的HIR。它原本用C++实现,不过有个Java移植版C1X,可供题主参考。C1X的HIR实现源码在此:
https:// kenai.com/projects/maxi ne/sources/maxine/show/com.oracle.max.c1x/src/com/sun/c1x/ir?rev=8809C1 / C1X的一些设计选择是:
值得提醒的是,虽然上面的文档把C1/C1X HIR叫做VDG,它这么叫只是为了突出「一个值直接依赖于别的值,而没有变量结构」的特点,而并不是指那种专门叫做VDG的IR形式:
https:// courses.cs.washington.edu /courses/cse501/06wi/reading/weise-popl94.pdf我比较熟悉、习惯和喜欢的另一种IR是HotSpot Server Compiler(C2)的Sea-of-nodes IR。这是个PDG(Program Dependence Graph)的变种,在编译器中很非主流。PDG更多见于非编译器的静态分析器中,所以就不在这帖多说…
但是为了安利一下Sea-of-nodes形式,还是放个Cliff Click大神读PhD时写的论文的传送门好了:
From Quads to Graphs: An Intermediate Representation's Journey (1993)。
等题主在Quad里摸爬滚打足够时间后再读这篇论文可能会有更多体会 >_<