本周主要先对tac的函数进行了简单的测试,以确保能够正确运行我的vm demo,修正了function的一些问题,之后就是处理对vm指令的生成,处理了一下符号相关的信息,还做了一点函数的相关的以及生成C++的解析代码(都没做完,还是下周吧
本周vm的代码都在ir/vm中,translator用于转换,inst是指令定义,vm.rb是入口
这是我目前的Function的ast定义
class Function
attr_reader :name, :args, :stmts
end
在修改function生成代码的时候发现了一个问题,因为我有默认最后一个值直接返回的设计,所以或许应该在高层添加一个将stmt显式抽出
return的操作。这个步骤现在看来大概分为简单两步
但是第二步实际实现的时候可能没有这么简单,这里就暂提个思路,以后再回头看这个设计是否有需要
之后做了一些将tac转到vm指令。在做这个的过程我才意识到其实不需要转成tac,对于tac和vm指令的表达力应该是同等级的,都比较偏向于中层IR。查看了一下其他语言的做法,Ruby和Java都是从AST转到了字节码
深入理解Java虚拟机310页:
字节码生成阶段不仅仅是把前面各个步骤所生成的信息(语法树、符号表)转换成字节码写到磁盘中,编译器还进行了少量的代码添加和转换工作
Ruby原理剖析36页:
在解析完 词条生成AST之后,Ruby1.9和Ruby2.0继续把代码编译成一系列的底层指令,叫做YARV指令
这里的YARV是Ruby的字节码解释器,而YARV指令自然就是对应的字节码。而Ruby1.9之前是直接解释执行ast的,甚至不会考虑到tac这样的东西
关于这一点,我询问了朋友,最后的结论大概有以下两点。如果读者对这方面很了解希望能科普一下
所以经过了这些结论,前面做的tac到vm指令的就白费了,只能重新写一套从ast生成vm指令代码。生成tac这个过程并没有白费,编写的过程中让我有对这个东西有了更深的理解,以及后续可能会用tac实现优化算法。
至于VM的实现,很自然的就会选择栈式VM。以学习为目的肯定要做寄存器分配,但是因为后续想做jit,所以寄存器分配就留到那个时候再做,或者说可以再从tac做成aot,反正目前还是以实现学习为目的。
搞一个VM本质是什么?我觉得本质是对运行时的环境进行处理。那么我们首先要来谈及这个环境都有哪些部分
我觉得简单可以分为以下两种
数据牵扯到的问题有很多,比如说数据排布、对象布局、地址分配等等。这也是我第一次动手做这些,这里就先从最简单的只有int32做起。如果后面做完善了可以再单独出一期把这些东西串起来(咕咕咕咕咕咕
寄存器就从目前来说,我们需要一个pc寄存器来表明当前执行到哪条语句了。至于vm那边的实现目前使用一个数组保存,pc保存下数组索引就好
栈帧根据不同的需求内容也各不相同
我们来看一下龙书中提到的常见栈帧成员(不论什么书其实大都差不多
要注意的是书中提到的基本上是针对非VM的栈帧,VM的栈帧可以根据需求做出不一样的设计,比如说Ruby中采用了双栈的设计,一个调用栈用于管理调用链,一个计算栈用于存放各种变量与计算,而对于非VM栈帧絕大多说都是一个栈(我没听说过有使用双栈的,但是说不定也存在呢)通过栈中保存的rbp寄存器中的值来处理访问链
就目前从头开始实现而言,我们需要什么再加什么就好了,后续每个东西怎么加,为什么加我都会有一定说明。
先从普通的运算赋值做起。这里其实有点问题,我还没有处理好单独的语句,所以都放到了一个函数里(写完这篇就去改),以及对于函数定义该如何处理我也没想好。
def foo
a = 3 * 2
end
在Ruby的虚拟机中扫描到类似的函数定义则是会产生一行调用 definemethod :foo, foo
而foo本身的内容则是
== disasm: #<ISeq:f@<compiled>:1 (1,0)-(3,3)> (catch: FALSE)
local table (size: 1, argc: 0 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 1] a@0
0000 putobject 3 ( 2)[LiCa]
0002 putobject 2
0004 opt_mult <calldata!mid:*, argc:1, ARGS_SIMPLE>
0006 dup
0007 setlocal_WC_0 a@0
0009 leave ( 3)[Re]
这里出现了一个点,由于函数体中是一个assign,值会pop走,但是这个assign又是作为一个返回值,因此ruby中对结果调用了dup,创建一个重复的值用于返回。在写博客的时候看到Ruby指令的结果刚意识到这个问题,不过这个是属于关于函数体与函数调用相关的内容,这里目前暂不修改。
作为参考,进行编写测试。
context 'assign' do
it 'normal expr' do
s = <<SRC
def foo
a = 1 * 2
end
SRC
inst = get_vm_inst(s)
expect(inst).to eq [Rc::VM::Push.new(1), Push.new(2), Mul.new, SetLocal.new(0), Return.new]
end
end
对于一个普通的a = 1 * 2,我们期望的行为是将两个参数push到栈上,之后进行mul操作,最后设置本地变量的值
class Binary # Rc::AST::Binary
attr_reader :op, :lhs, :rhs
end
def on_binary(node)
[
push(visit(node.lhs)),
push(visit(node.rhs)),
translate_op(node.op),
]
end
指令操作数目前分了两种,一种是直接可以保存值的,一种是引用某个名字
module VMInstOperand
class Value < Struct.new(:value)
end
# Ref a exist var
class Ref < Struct.new(:ref)
end
def push(node)
if node.is_a? Value
Push.new(node.value)
elsif node.is_a? Ref
GetLocal.new(node.ref)
else
raise "Unsupported node type #{node.class}"
end
end
end
# 下面两个都是visit结点的函数
def on_number_constant(node)
Value.new node.val.to_i
end
# Get or Set, so need return a id
def on_identifier(node)
Ref.new cur_fun_env[node.name].id
end
这么设计的原因是
同时也有不同的“push操作”
这里暂时不考虑访问外部作用域的问题,这会涉及到符号表的访问以及栈的修改两部分内容。
针对这样的设计,我们需要开始增加栈的功能了
因此就有了如下最最最简单的栈
----------
临时变量
----------
因此就有了如下最最简单的栈
----------
临时变量
----------
局部变量
----------
这个没什么好说的,简单从op字符串转换到不同类型的运算指令
def translate_op(op)
case op.op
in '+'
Add.new
# ...以下省略
就之前的代码而言,符号表信息之类的记录的并不够。在实际考虑栈帧以及执行之前我对符号表的认识仅仅停留在作为解释器的env以及他的功能的“概念”上。由于是之前写过的,就直接拿来用了,没有 再来认真反思设计以及其他的问题,回头再重新设计吧,先能用就行
考虑局部变量如何保存这个问题,引出了我对符号表更多的实际理解,所以还是要自己动手做才能更有助于理解,只是看一些理论讲还是不够,至少对我而言是这样的
关于扫描分析的代码在analysis/global_env中
符号表相关的定义在lib/env中
class GlobalEnv < Struct.new(:define_env, :const_table, :fun_env)
end
全局表目前保存三个东西
针对生成VM指令的阶段,需要知道一个临时变量的位置,因此有了这样的一个东西作为符号表的条目。
class EnvItemInfo < Struct.new(:id, :type)
end
id的话在一个函数中是自增的,用于GetLocal和SetLocal中计算具体的offset(这个设计对于后续可能不够用,先这样)。类型肯定也是需要的,但是目前并没有考虑类型的问题,就留了这么一个坑在这里
def on_function(node)
@define_env.define_symbol(node.name, node)
@cur_fun_sym = Env.new
@cur_fun_var_id = 0
@cur_fun_sym.merge(node.args.map{ |arg| [arg, EnvItemInfo.new(cur_fun_var_id, '')]}.to_h)
visit(node.stmts)
@fun_env[node.name] = @cur_fun_sym
end
今天写的太久有点写不下去了,所以到后面内容比较潦草,还请见谅。(目前以保证更新频率为主)有疑惑的地方可以联系我