Rc-lang开发周记2 VM相关

本周主要先对tac的函数进行了简单的测试，以确保能够正确运行我的vm demo，修正了function的一些问题，之后就是处理对vm指令的生成，处理了一下符号相关的信息，还做了一点函数的相关的以及生成C++的解析代码（都没做完，还是下周吧

本周vm的代码都在ir/vm中，translator用于转换，inst是指令定义，vm.rb是入口

Function转换

这是我目前的Function的ast定义

class Function
    attr_reader :name, :args, :stmts
end

在修改function生成代码的时候发现了一个问题，因为我有默认最后一个值直接返回的设计，所以或许应该在高层添加一个将stmt显式抽出

return的操作。这个步骤现在看来大概分为简单两步

1. 消除不可达代码，比如说一个return后面还有好几个值
2. 消除后就可以放心将最后一个语句的结果转换为一个返回值了

但是第二步实际实现的时候可能没有这么简单，这里就暂提个思路，以后再回头看这个设计是否有需要

无意义的tac to vm inst

之后做了一些将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指令

关于这一点，我询问了朋友，最后的结论大概有以下两点。如果读者对这方面很了解希望能科普一下

1. 转成tac做优化以后，尤其是部分针对全局的优化会以及其他的变换会剔除掉一些JIT时所需要的信息。

   关于这点我问了很久，我觉得还要尽可能地多做优化再到jit，应该要通过控制不做哪些优化来避免剔除所需信息。因为我对这几个层面所能做的优化了解不深，不知道所能做的优化有哪些差异，也没法举出例子或者说明收益

   后续我又了解了一些信息，发现jit中还有一个名叫的deoptimize技术，这个出现在multi tiered jit中。关于这个的内容在我另一篇博客中

2. 如果直接显式执行的是源码而不是字节码，先转成tac做处理再到vm指令会影响到了启动时间

   Ruby是在内部对源码解析之后再由vm来执行。Java可能给大多数人的印象是必须要先编译到字节码，然后再单独加载执行字节码，但调查发现Java9开始可以通过jshell来直接执行。将这个过程封装到一起实际上也不麻烦，只是不需要你显式操作罢了

所以经过了这些结论，前面做的tac到vm指令的就白费了，只能重新写一套从ast生成vm指令代码。生成tac这个过程并没有白费，编写的过程中让我有对这个东西有了更深的理解，以及后续可能会用tac实现优化算法。

VM简介

至于VM的实现，很自然的就会选择栈式VM。以学习为目的肯定要做寄存器分配，但是因为后续想做jit，所以寄存器分配就留到那个时候再做，或者说可以再从tac做成aot，反正目前还是以实现学习为目的。

搞一个VM本质是什么？我觉得本质是对运行时的环境进行处理。那么我们首先要来谈及这个环境都有哪些部分

我觉得简单可以分为以下两种

1. 数据（代码与计算的数据）
2. 当前状态（寄存器与栈帧）

数据

数据牵扯到的问题有很多，比如说数据排布、对象布局、地址分配等等。这也是我第一次动手做这些，这里就先从最简单的只有int32做起。如果后面做完善了可以再单独出一期把这些东西串起来（咕咕咕咕咕咕

当前状态

寄存器

寄存器就从目前来说，我们需要一个pc寄存器来表明当前执行到哪条语句了。至于vm那边的实现目前使用一个数组保存，pc保存下数组索引就好

栈帧

栈帧根据不同的需求内容也各不相同

我们来看一下龙书中提到的常见栈帧成员（不论什么书其实大都差不多

1. 局部变量
2. 临时变量的位置（牵扯到临时变量？
3. 机器状态（保存的特殊寄存器值，这个和调用约定也有一定关联。调用约定决定了哪些寄存器是需要保存的，哪些是不需要保存的，关于调用约定更多详情还请自行查询
4. rbp指针（用于管理访问链
5. 指向调用者的地址
6. 返回值（我选择统一放到一个寄存器中）
7. 实参

要注意的是书中提到的基本上是针对非VM的栈帧，VM的栈帧可以根据需求做出不一样的设计，比如说Ruby中采用了双栈的设计，一个调用栈用于管理调用链，一个计算栈用于存放各种变量与计算，而对于非VM栈帧絕大多说都是一个栈（我没听说过有使用双栈的，但是说不定也存在呢）通过栈中保存的rbp寄存器中的值来处理访问链

就目前从头开始实现而言，我们需要什么再加什么就好了，后续每个东西怎么加，为什么加我都会有一定说明。

VM指令转换

计算赋值

先从普通的运算赋值做起。这里其实有点问题，我还没有处理好单独的语句，所以都放到了一个函数里（写完这篇就去改），以及对于函数定义该如何处理我也没想好。

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

这么设计的原因是

1. 针对一个简单的数值我们可以直接将值push到栈上
2. 针对一个名字我们需要去符号表中找到这个名字所在的位置，再将对应的值push到栈上

同时也有不同的“push操作”

1. 针对简单的值直接push
2. 针对名字我们通过GetLocal来获取（对于vm那边的实现，需要根据局部变量的基址和偏移量以及类型找到对应的值再放上去，但是类型目前不考虑，统一int32）

这里暂时不考虑访问外部作用域的问题，这会涉及到符号表的访问以及栈的修改两部分内容。

针对这样的设计，我们需要开始增加栈的功能了

1. 简单数值的运算，我们需要能将值放上去，再进行运算取出或者留在栈里（这些临时变量）

因此就有了如下最最最简单的栈

----------
  临时变量
----------

1. 我们需要留有局部变量的位置，能够在里面存取数据。临时变量是会随着当前函数结束而销毁，因此我们需要添加临时变量的位置在栈上，栈回退的时候也会直接销毁掉

   由于1需要反复修改栈指针的操作需要所以放在当前栈帧的最顶端比较合适

因此就有了如下最最简单的栈

----------
  临时变量
----------
  局部变量
----------

op处理

这个没什么好说的，简单从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

全局表目前保存三个东西

1. 各种定义（类定义、函数定义等），这个设计是比较早的时候写的，可能并不合适，后续再好好想一下该怎么做
2. 常量表
3. 函数的符号表，根据函数名找到对应函数的符号表

条目

针对生成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

1. 将函数名字关联到结点
2. 从每个函数开始分析时初始化各参数的状态
3. 将参数merge进当前函数的符号表中
4. 访问函数体
5. 将函数名关联到对应的符号表

最后

今天写的太久有点写不下去了，所以到后面内容比较潦草，还请见谅。（目前以保证更新频率为主）有疑惑的地方可以联系我