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 的 ，注意 endpc is 1-based
  while (vars.size > 0 && var.top.endpc < pc+1) {
    vars.pop()
  }
  // push 所有 startpc <= pc 的，startpc is 1-based, 移到下一个未使用的变量
  while (currlocvar < sizelocvars && locvars[currlocvar].startpc <= pc+1) {
    var.push(locvars[currlocvar++]
  }
  // 那么此时 vars[r] 即对应 reg[r] 的变量
}

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

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

关于 luac 中 locvars 部分

• 没有记录对应 reg
• startpc endpc 对应的 pc 是从 1 开始的
• startpc = 0 时， 对应函数参数
• 5.1 nil 优化的 local 也是 startpc = 0
  • 包括 do 内部 nil 优化的
  • do 内部 local 被 nil 优化而没用过，导致 startpc=endpc=0
• 5.1 endpc 不包括最后强制插入的 return
• 5.2/5.3 endpc 包括最后强制插入的 return
• 5.1 endpc 不包括所在作用域的 close
• 5.2/5.3 endpc 包括所在作用域用于 close 的 jmp
• 有可能一个 reg 在一条指令中既用作临时变量又用作 local

f->locvars
typedef struct LocVar {
  TString *varname;
  // 对应的 pc 是从 1 开始的
  int startpc;  /* 1-based first point where variable is active, 0 means function arguments and nil optimization */
  int endpc;    /* 1-based first point where variable is dead */
} LocVar;

/*
** local_number and pc are 1-based not 0-based
** Look for n-th local variable at line `line' in function `func'.
** Returns NULL if not found.
*/
const char *luaF_getlocalname (const Proto *f, int local_number, int pc) {
  int i;
  for (i = 0; i<f->sizelocvars && f->locvars[i].startpc <= pc; i++) {
    if (pc < f->locvars[i].endpc) {  /* is variable active? */
      local_number--;
      if (local_number == 0)
        return getstr(f->locvars[i].varname);
    }
  }
  return NULL;  /* not found */
}

Local type	5.1 startpc	5.1 endpc	5.2 startpc	5.2 endpc
function parameter
firstline
write once
write once in do
in do
in for
in tfor
in while
in repeat
in if then
in if else