Rc-lang开发周记1 中间代码表示
Homura 我摸到了!

本周前面的时间主要选择了重新整理项目结构以及修正了自己滥用require_relative的问题,后面的话则是开始对ast to tac进行测试,尝试通过TDD的方式在开发效率和质量确保找到一个平衡点。

比起测试,更主要的目的是重新回顾自己tac的设计决策,前面写的时候更多是一时兴起,完全不顾结构与正确性就往下写,比起急急忙忙往后赶进度还是应该将当前的内容做好才行。

当前的项目结构

1
2
3
4
5
6
7
8
9
.github # CI 尽管代码不多,但是依然要依靠单元测试和CI保证每次修改的正确性
analysis # 代码分析的内容,目前并没有做过多的内容
interface # 编译器、解释器和REPL的入口
compiler # compiler的实现
interpreter # 解释执行的实现
ir # 多级ir的实现,ast, tac, vm指令
lib # 编译器相关的一些简单的库,比如env, log或者错误处理之类
parser
spec # 专门用于测试

解释执行实现的部分由于其他内容快速修改,暂无法顾及,因此暂时无法正常工作

Rc-lang的多层IR结构

  1. 高层IR:AST
  2. 中层IR:四元式
  3. 底层IR:VM指令

本周内容主要以中层IR为主

中间代码表示

IR主要分为两类

  1. 线性IR
  2. 图IR

要注意的是树IR也是一种DAG图,因此也属于图IR,而高层的AST也是属于图IR

选择IR的时候最主要的一点是我们要用它来做什么、需要什么信息,我想也没有什么绝对的设计正确,只要提供了所需信息,方便后续测试就足够了。在这里对比一下常见的IR实现(以线性IR为主)

线性IR的概念

三地址码是指 指令右侧只能有一个运算,不允许出现组合的形式

1
2
3
4
a2 = (b + c) * 4
需要被翻译为
a1 = b + c
a2 = a1 * 4

龙书中选择了线性IR的方式,使用了传统的三地址码。而虎书采用了树形IR(最后会简单提及)

四元式

具有四个字段,类似于 op arg1 arg2 result的形式,但是存在一些特例

  1. op仅需要一个参数
  2. param的运算不使用args2和result(这里的param是龙书中用于传递函数参数的指令,龙书针对每一个参数产生一个param,仅传递参数也不需要返回值)
  3. 转移指令将跳转地址放入result

这些特例是针对虎书中的指令,实际可以根据需求进行一些变动

定义

这是我的四元式定义 在文件ir/tac/quad.rb中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Quad
attr_accessor :op, :result, :lhs, :rhs

def initialize(op, result, lhs, rhs)
@op, @result, @lhs, @rhs = op, result, lhs, rhs
end

def to_s
"#{@result} = #{@lhs} #{@op} #{@rhs}"
end

def ==(other)
@op == other.op && @result == other.result && @lhs == other.lhs && @rhs == other.rhs
end
end

以及我个人觉得没必要全都严格按照这种方式来,还是以自己的需求为准。按照常规的四元式op可以是各种类型的

比如说我实现的Assign和Call(其他的op目前还没有修改以及做更多测试,本周先介绍这两个最基本的)

通过类型来获取更多的信息,而不是仅仅通过字符串判别。还可以做到像call一样设置一个别名,能够显得更加直观

1
2
3
4
5
6
7
8
class Assign < Quad
def initialize(result, lhs)
@op = 'assign'
@result = result
@lhs = lhs
@rhs = EmptyValue.new
end
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Call < Quad
def initialize(result, target, args)
@op = 'call'
@result = result
@lhs = target
@rhs = args
end

def target
@lhs
end

def args
@rhs
end
end

Assign没什么可说的。但是Call比较特殊

args并不是只有一个地址,所以Call并不算严格意义上的四元式。上面也提及过龙书中的Call的参数是通过一个param指令传递的,然后单独调用一个call。但就我目前来说这样做比较方便,等到后续做其他功能发现这么做的坏处的时候再修改也不晚

转换

实现

转换代码在ir/tac/translator.rb中

1
2
3
4
5
6
7
8
9
10
11
12
class Assign # Rc::AST::Assign
attr_reader :var_obj, :expr
def initialize(var_obj, expr)
@var_obj, @expr = var_obj, expr
end
end

def on_assign(node)
name = visit(node.var_obj)
expr = visit(node.expr)
Assign.new(name, expr).tap { |assign| @tac_list.push assign }
end

转换ast::assign的时候会将原来的名字作为tac::assign一个目标地址(尽管设计上留有了这个空间,但是目前先不考虑成员变量这种复杂的情况),然后再将表达式返回的内容设置为assign的operand。因此我们需要看一下expr的转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Expr # Rc::AST::Expr
attr_reader :expr
end
# Rc::AST::Expr -> Operand
def on_expr(node)
expr = visit(node.expr)
if expr.is_a? Operand
expr
elsif expr.is_a? Quad
expr.result
else
raise 'unknown expr type'
end
end

存在两种情况

  1. 转换为一个operand(比如说常量的情况)

  2. 转换为了一个quad

    比如说c = a * b,a * b 会先存到一个临时变量再赋值。关于这个,龙书6.1.1中提到了这样的内容

    为什么我们需要复制指令?
    通常,每个子表达式都会有一个它自己的新临时变量来存放运算结果。只有处理赋值运算符=时,我们才知道将把整个表达式的结果赋到哪里,一个代码优化过程将会发现可以发生替换

    我没完全理解,也许只有做优化的时候才会明白,就先沿用这样的设计了

quad的时候需要返回对应的临时变量,因为返回值会直接用于assign的operand

测试

然后我们再来看一下测试代码 spec/ir/tac_spec.rb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
context 'assign' do
it 'succeed' do
s = <<SRC
def f1
a = 1
b = 2
c = a * b
end
SRC
tac = get_tac(s)
list = tac.first_fun_tac_list
expect(list[1]).to eq Assign.new(Name.new('a'), Number.new(1))
expect(list[2]).to eq Assign.new(Name.new('b'), Number.new(2))
expect(list[3]).to eq Quad.new('*', TempName.new('0'), Name.new('a'), Name.new('b'))
expect(list[4]).to eq Assign.new(Name.new('c'), TempName.new('0'))
end
end

可以看到有简单的assign, 还有一个表达式的运算。

表达式的运算转换为了一个quad,并且保存在了临时变量中,最后再将这个临时变量assign给c

线性IR的存储方式

对于线性IR来说,保存的方式也是一个比较重要的实现决策,很大程度会影响到后续各种操作。

而实际实现无外乎数组和链表两种保存方式,在上周做重排if的时候也能看到数组的方式插入删除比较麻烦,而且效率会比较低。数组插入删除的方式也有对应的优化实现,但是对于其他优点目前没什么了解,后续做到优化的时候可能会需要考虑到这些实现方式的差别。

我当前所有指令都保存在了一个数组,所以上面的四元式并没有指向前后的指令。之所以这么选择是因为当时没考虑太多,很自然的会想到一组指令会存到一个数组中。不过需要时在ast全部转为tac以后再做一下转换即可,需要做其他优化时再添加。当前目的是直接生成下一步的指令,所以现在这样就够了。

名称与地址

对于线性ir来说名称和地址是非常重要的事情。名称与地址是对应了三地址码的操作数,可以是常数,可以是一个地址,也可以是一个名字(间接索引到地址)

所以有了一个operand的定义,在文件ir/tac/operand.rb中

1
2
class Operand
end

1.名字

通过名字确定一个地址,实际实现可以通过符号表来索引到对应地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Name < Operand
attr_accessor :name

def initialize(name)
@name = name
end

def to_s
@name.gsub(/:/, '')
end

def ==(other)
@name == other.name
end
end


class TempName < Name
end

2.常量

如果是数字类型的常量可以直接放入,这也符合CPU指令的行为。(bool本质也是数字)

如果是字符串常量则需要记录到全局的一个表中,本质上我们还是使用字符串的地址。这个表里的东西在后续转vm指令和运行时会放入常量段,由于不会牵扯到改变,因此目前这里采用了一个普通的列表,通过索引来获取地址的方式。这里或许会牵扯到优化的问题,我觉得关于字符串常量这种优化可以放到转入这一步之前,如果遇到其他场合再做修改。

两种常量的定义

1
2
3
4
5
6
7
8
9
10
11
12
class Number < Operand  
attr_accessor :num
def initialize(num)
@num = num
end
def to_s
@num.to_s
end
def ==(other)
@num == other.num
end
end
1
2
3
4
5
6
7
8
9
10
11
class Memory < Operand
attr_reader :addr

def initialize(addr)
@addr = addr
end

def ==(other)
@addr == other.addr
end
end

常量的转换

1
2
3
4
5
6
7
8
9
10
11
def on_bool_constant(node)
Number.new(node.val.to_i)
end

def on_number_constant(node)
Number.new(node.val.to_i)
end

def on_string_constant(node)
Memory.new(@const_table.add(node.val))
end

在这里涉及到一个const_table的问题。字符串会放在常量区,因此我选择在这里转换为一个地址。关于Memory或许需要选择段的问题,但是目前还没有遇到需要区分的情况,后续添加其他类型的常量再考虑吧,因此也是先这样。

1
2
3
4
5
6
7
8
9
10
11
class Memory < Operand
attr_reader :addr

def initialize(addr)
@addr = addr
end

def ==(other)
@addr == other.addr
end
end

常量表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ConstTable
attr_reader :list

def initialize
@list = []
end

def add(constant)
i = @list.index(constant)
i.or_else do
@list.push constant
@list.size - 1
end
end

private def method_missing(symbol, *args)
@list.method(symbol).try { |x| x.call(*args) }
end

def ==(other)
list == @other.list
end
end

目前选择了这样简单的形式。没有用Set的原因是难以添加一个成员以后再返回对应的索引,可以作为后续优化的一个点。

or_else是一个hack, nil的情况会返回block中的代码

3.临时变量

临时变量会出现在各种表达式中,前面转换的实现中也能看到相关内容。这里不多赘述

其他IR形式

这里对于SSA(Static Single Assign)就暂不提及了,SSA更多的是用于优化方面,目前的目标是生成VM指令并且能在VM上运行,做到SSA的时候会讲的

其他的形式在这里大概一提,不讲过多细节(写不完了)

三元式

具有三个字段,类似于op arg1 arg2的形式。和四元式不同,不会显式保存返回结果,而是将每个结果存入列表中,因此三元式对结果的引用也是依靠于位置。很明显,这样就会导致如果添加或者减少指令则会变得很麻烦,因此引入间接三元式(在这里不赘述了,有兴趣自行搜索)

由于实现比较麻烦,所以我还是选择使用常规四元式

图IR

虎书采用了树形IR

由于我目前选择了线性的方式,暂无这方面的代码,姑且还是提一下虎书中的实现并且贴一下图

其实也比较接近于tac,只是结构变成了树状,同样会有各种常数,内存操作,调用等等,因为中层IR本质上都是要将AST转换为接近于机器表示,所以不管什么样子最终都是要接近于机器指令。不同的存储方式区别只是做优化的时候不同

Untitled

Untitled

最后

tac指令以及对应的operand过于繁琐,测试代码也有待改进,对于Ruby来说这些都可以利用元编程来精简代码,而且可以疯狂造dsl。只是每天的开发时间实在不多,还是以能做出来为最高优先级。

写了足足快俩小时,有点写的不耐烦了(有点时间焦虑,先以能写完为目标吧…)。写的过程中我会强迫自己反思和改进,上周写的时候最后还发现了一个bug,也算是不亏,下周也会更(在新建文件了,咕咕咕

参考

https://www.zhihu.com/question/33518780/answer/56731699

编译原理 第六章

现代编译原理 第七章

  • 本文标题:Rc-lang开发周记1 中间代码表示
  • 本文作者:Homura
  • 创建时间:2021-12-26 11:41:17
  • 本文链接:https://homura.live/2021/12/26/rc-lang-dev/rc-lang-dev-1/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!