Lua Register Assignment

寄存器分配算法

Lua 5.x 是基于寄存器的虚拟机，寄存器分配是在编译时确定的。

缺省时，Lua 具有 250 的最大栈帧尺寸，在 llimits.h 中编码为 MAXSTACK 。
它进而限制了每函数的局部变量的最大数目，200，在 luaconf.h 中编码为 LUAI_MAXVARS 。
该文件中的其他限制包括每函数的最大 upvalue 数（ 60 ） ， 编码为LUAI_MAXUPVALUES，调用深度，最小 C 栈尺寸，等等。
并且，囿于 18 位的 sBx 字段，跳转和控制结构不能超出大约131071 的跳转距离。

反编译时，我们可以逆向寄存器分配算法来得到 strip 掉的 f->sizelocvars 和 f->locvars (varname, startpc, endpc)。 并且猜测出 block 结尾

Lua寄存器分配算法中最重要的两个变量 tmpreg 和 freereg ，对于某一个 pc， 这把 stack 分成3个区域， 变量区，临时寄存器区，未分配区
变量区是紧密排列的，临时变量中间可能有空洞

• freereg , reg>=freereg 的是未分配寄存器
• tmpreg , reg>=tmpreg 的不可能是变量
• tmpreg <= freereg

我们应该把 lua vm OpCode 分类

• 读 ra
  一次写后读多次的必然是变量 tmpreg > ra
  只读写一次暂时认为是临时寄存器(可能被改成变量)
• 写 rb
  第一次写 设为变量定义 startpc
  以后的使用（读，写）只能在变量定义所在 block 的 子 block
  暂时认为一次写为一个变量的开始(可能导致一个变量被拆成多个)
  只写一次没有读，必然是变量
• 只能使用 临时寄存器 rc OP_SETLIST
  必然导致 tmpreg <= rc
• OP_CLOSE rx
  必然导致 freereg == tmpreg == rx
• 必然分配变量 FOR
• 此时 临时寄存器区 必须为空

tmpreg 减少意味着 block 结尾

如何使用 f->locvars
应该可以使用 lfunc.c 的 luaF_getlocalname
也可以使用下面的算法

currlocvar = 0
vars = new stack
for (pc=0; ;pc++) {
  // pop 所有 endpc < pc 的
  while (vars.size > 0 && var.top.endpc < pc) {
    vars.pop()
  }
  // push 所有 startpc <= pc 的，移到下一个未使用的变量
  while (currlocvar < sizelocvars && locvars[currlocvar].startpc <= pc) {
    var.push(locvars[currlocvar++]
  }
  // 那么此时 vars[r] 即对应 reg[r] 的变量
}

lparse 生成的 f->locvars endpc 必然为 block 结尾
guess 生成的 f->locvars endpc 目前只能确定到 最后一次读

当一条指令解析完成后，还存在临时变量，就不能输出任何 statement
当一条指令解析完成后，没有临时变量了，除了 jmp close 等，必须有输出，例如 {1,2}[3]=4