首页 » 技术文章 » 【源码解读】lua源码分析之编译器部分I(lua编译表达式)

【源码解读】lua源码分析之编译器部分I(lua编译表达式)

 

研究目的

  • 对当前项目写的lua代码最终生成的操作码,和可能执行的C操作有一个大体的了解,为后续实现高效的代码及代码优化做准备;
  • 了解不同的代码书写方式可能产生的执行效率差异,比如频繁使用全局变量造成的额外开销,对table的错误访问方式造成的额外数组扩展(如果对OP_SETLIST指令有一定的理解可能可以对其进行优化);
  • 了解lua编译器部分源码,可以更容易理解lua虚拟机lvm.c对lua操作指令的解释执行过程;

大体流程

当我们在linux命令行中执行luac test.lua时,会执行编译过程(使用luac -l test.lua命令,甚至可以观察编译器编译出来的lua指令),其调用的函数过程如下: luaY_parser --> chunk --> statement,其中statement函数是一个while循环,不停的读取lua代码行(姑且认为其按行来分析),然后根据代码行特征做处理,statement具体实现为:

static int statement (LexState *ls) {
  int line = ls->linenumber;  /* may be needed for error messages */
  switch (ls->t.token) {
    case TK_IF: {  /* stat -> ifstat */
      ifstat(ls, line);
      return 0;
    }
    case TK_WHILE: {  /* stat -> whilestat */
      whilestat(ls, line);
      return 0;
    }
    case TK_DO: {  /* stat -> DO block END */
      luaX_next(ls);  /* skip DO */
      block(ls);
      check_match(ls, TK_END, TK_DO, line);
      return 0;
    }
    case TK_FOR: {  /* stat -> forstat */
      forstat(ls, line);
      return 0;
    }
    case TK_REPEAT: {  /* stat -> repeatstat */
      repeatstat(ls, line);
      return 0;
    }
    case TK_FUNCTION: {
      funcstat(ls, line);  /* stat -> funcstat */
      return 0;
    }
    case TK_LOCAL: {  /* stat -> localstat */
      luaX_next(ls);  /* skip LOCAL */
      if (testnext(ls, TK_FUNCTION))  /* local function? */
        localfunc(ls);
      else
        localstat(ls);
      return 0;
    }
    case TK_RETURN: {  /* stat -> retstat */
      retstat(ls);
      return 1;  /* must be last statement */
    }
    case TK_BREAK: {  /* stat -> breakstat */
      luaX_next(ls);  /* skip BREAK */
      breakstat(ls);
      return 1;  /* must be last statement */
    }
    default: {
      exprstat(ls);
      return 0;  /* to avoid warnings */
    }
  }
}

statement根据代码行特征进入相应的分支,例如,我们定义一个 function f的函数时,会进入分支TK_FUNCTION,定义一个local a = 1时,会进入TK_LOCAL分支。接下来会以几个小例子详解LUA代码生成过程。

local a = 1;

在test.lua中输入上述代码,然后调用luac test.lua,其执行流程为,进入statement的TK_LOCAL分支,然后会调用localstat,该函数实现源码如下:

static void localstat (LexState *ls) {
  /* stat -> LOCAL NAME {`,' NAME} [`=' explist1] */
  int nvars = 0;
  int nexps;
  expdesc e;
  do {
    new_localvar(ls, str_checkname(ls), nvars++);
  } while (testnext(ls, ','));
  if (testnext(ls, '='))
    nexps = explist1(ls, &e);
  else {
    e.k = VVOID;
    nexps = 0;
  }
  adjust_assign(ls, nvars, nexps, &e);
  adjustlocalvars(ls, nvars);
}

首先调用new_localvar创建局部变量,会将变量名保存在proto的locvars数组中(后续引用变量时,会搜索该数组),同时会设置fs->nactvar,fs->nactvar非常重要,它的意思是表示在当前上下文中活跃的局部变量数,当进入一些block时及退出block(例如for循环block),会调整fs->nactvar。 调用完new_localvar后,会调用explist1来解释后续的表达式,这里表达式为1,则计算出来的expdesc e中的信息如下:

e->f = e->t = NO_JUMP;
e->k = VK_NUM;
e->u.s.info = 1;

explist1的源码如下:

static int explist1 (LexState *ls, expdesc *v) {
  /* explist1 -> expr { `,' expr } */
  int n = 1;  /* at least one expression */
  expr(ls, v);
  while (testnext(ls, ',')) {
    luaK_exp2nextreg(ls->fs, v);
    expr(ls, v);
    n++;
  }
  return n;
}

explist1中调用expr来解释单个表达式,单个表达式是指以逗号分隔开的每个表达式,例如:a+1, 2则是两个子表达式(lua支持 a,b = 1,2这种赋值方式的原理也是由于上述实现)。而expr会调用subexpr,subexpr的源码如下:

static BinOpr subexpr (LexState *ls, expdesc *v, unsigned int limit) {
  BinOpr op;
  UnOpr uop;
  enterlevel(ls);
  uop = getunopr(ls->t.token);
  if (uop != OPR_NOUNOPR) {
    luaX_next(ls);
    subexpr(ls, v, UNARY_PRIORITY);
    luaK_prefix(ls->fs, uop, v);
  }
  else simpleexp(ls, v);
  /* expand while operators have priorities higher than `limit' */
  op = getbinopr(ls->t.token);
  while (op != OPR_NOBINOPR && priority[op].left > limit) {
    expdesc v2;
    BinOpr nextop;
    luaX_next(ls);
    luaK_infix(ls->fs, op, v);
    /* read sub-expression with higher priority */
    nextop = subexpr(ls, &v2, priority[op].right);
    luaK_posfix(ls->fs, op, v, &v2);
    op = nextop;
  }
  leavelevel(ls);
  return op;  /* return first untreated operator */
}

首先调用getunopr来获取前缀(是否有取反或取负等前缀符号),我们定义的local a = 1,1前面并没有前缀,因此会进入simpleexp函数,其源码如下:

static void simpleexp (LexState *ls, expdesc *v) {
  /* simpleexp -> NUMBER | STRING | NIL | true | false | ... |
                  constructor | FUNCTION body | primaryexp */
  switch (ls->t.token) {
    case TK_NUMBER: {
      init_exp(v, VKNUM, 0);
      v->u.nval = ls->t.seminfo.r;
      break;
    }
    case TK_STRING: {
      codestring(ls, v, ls->t.seminfo.ts);
      break;
    }
    case TK_NIL: {
      init_exp(v, VNIL, 0);
      break;
    }
    case TK_TRUE: {
      init_exp(v, VTRUE, 0);
      break;
    }
    case TK_FALSE: {
      init_exp(v, VFALSE, 0);
      break;
    }
    case TK_DOTS: {  /* vararg */
      FuncState *fs = ls->fs;
      check_condition(ls, fs->f->is_vararg,
                      "cannot use " LUA_QL("...") " outside a vararg function");
      fs->f->is_vararg &= ~VARARG_NEEDSARG;  /* don't need 'arg' */
      init_exp(v, VVARARG, luaK_codeABC(fs, OP_VARARG, 0, 1, 0));
      break;
    }
    case '{': {  /* constructor */
      constructor(ls, v);
      return;
    }
    case TK_FUNCTION: {
      luaX_next(ls);
      body(ls, v, 0, ls->linenumber);
      return;
    }
    default: {
      primaryexp(ls, v);
      return;
    }
  }
  luaX_next(ls);
}

由于1是一个整数,直接进入TK_NUMBER,设置表达式的值并返回,否则就进行其他操作。比如,我们如果定义个local a = c,假设其中c是一个全局变量,那么会进入 primaryexp,然后会搜索变量c,最终判定出c是一个全局变量(下文介绍时也会附带介绍这个执行流)。 我们继续回到localstat函数,当执行完explist1后,得到了表达式的值,然后会执行adjust_assign函数,其源码为:

static void adjust_assign (LexState *ls, int nvars, int nexps, expdesc *e) {
  FuncState *fs = ls->fs;
  int extra = nvars - nexps;
  if (hasmultret(e->k)) {
    extra++;  /* includes call itself */
    if (extra < 0) extra = 0;
    luaK_setreturns(fs, e, extra);  /* last exp. provides the difference */
    if (extra > 1) luaK_reserveregs(fs, extra-1);
  }
  else {
    if (e->k != VVOID) luaK_exp2nextreg(fs, e);  /* close last expression */
    if (extra > 0) {
      int reg = fs->freereg;
      luaK_reserveregs(fs, extra);
      luaK_nil(fs, reg, extra);
    }
  }
}

其中nvars 和nexps都为1,分别表示变量及子表达式的个数。然后会进入分支if (e->k != VVOID) luaK_exp2nextreg(fs, e),从而进入luaK_exp2nextreg

void luaK_exp2nextreg (FuncState *fs, expdesc *e) {
  luaK_dischargevars(fs, e);
  freeexp(fs, e);
  luaK_reserveregs(fs, 1);
  exp2reg(fs, e, fs->freereg - 1);
}

luaK_dischargevars根据表达式的类型,为其生成不同的代码,例如如果定义的为local a = c ,则会进入luaK_dischargevars中的如下分支:

case VGLOBAL: {
  e->u.s.info = luaK_codeABx(fs, OP_GETGLOBAL, 0, e->u.s.info);
  e->k = VRELOCABLE;
  break;
}

生成一条指令,e->u.s.info是一个字符串"c",同时指定表达式目前状态变为未分配寄存器保存获取到的全局变量值,e->u.s.info此时保存的是OP_GETGLOBAL的指令指针(后续处理会回来修改指令,用来告诉OP_GETGLOBAL获取到值后保存在哪个寄存器中)。 然后调用freeexp,用来释放不需要分配寄存器的表达式占用的临时寄存器(可以先不理会这句,意思反正就是说释放表达式临时占用的寄存器而已)。然后调用luaK_reserveregs,分配一个寄存器。最后调用discharge2reg来为表达式的值保存到寄存器中。

static void discharge2reg (FuncState *fs, expdesc *e, int reg) {
  luaK_dischargevars(fs, e);
  switch (e->k) {
    case VNIL: {
      luaK_nil(fs, reg, 1);
      break;
    }
    case VFALSE:  case VTRUE: {
      luaK_codeABC(fs, OP_LOADBOOL, reg, e->k == VTRUE, 0);
      break;
    }
    case VK: {
      luaK_codeABx(fs, OP_LOADK, reg, e->u.s.info);
      break;
    }
    case VKNUM: {
      luaK_codeABx(fs, OP_LOADK, reg, luaK_numberK(fs, e->u.nval));
      break;
    }
    case VRELOCABLE: {
      Instruction *pc = &getcode(fs, e);
      SETARG_A(*pc, reg);
      break;
    }
    case VNONRELOC: {
      if (reg != e->u.s.info)
        luaK_codeABC(fs, OP_MOVE, reg, e->u.s.info, 0);
      break;
    }
    default: {
      lua_assert(e->k == VVOID || e->k == VJMP);
      return;  /* nothing to do... */
    }
  }
  e->u.s.info = reg;
  e->k = VNONRELOC;
}

local a = 1,进入了luaK_codeABx(fs, OP_LOADK, reg, luaK_numberK(fs, e->u.nval));生成了OP_LOADK指令。但如果是local a = c,则进入了:

case VRELOCABLE: {
  Instruction *pc = &getcode(fs, e);
  SETARG_A(*pc, reg);
  break;
}

直接修改前面的OP_GETGLOBAL指令,将寄存器保存在该指令中,从而OP_GETGLOBAL执行时会将全局变量的值加载到目标寄存器。 好了,到这里local a = 1就算介绍完毕了。唯一可能有疑惑的地方就是,local a = 1,并未看到未local a分配栈空间。当后续的代码比如定义如下:

local a = 1
local c = a

此时c究竟如何索引a呢?因为上文介绍时并未发现未a分配寄存器,将1保存到寄存器中后,代码就执行完了,并未有一条指令为a分配空间,并将寄存器的值保存到这个空间中。其实答案是,1这个表达式的值luaK_reserveregs分配的寄存器正是给a使用的。接下来简单介绍下lua编译器部分关于寄存器分配的原理,方便代码阅读。lua寄存器使用一个变量fs->freereg来表示可用的寄存器,当我们编译一个表达式时,有可能表达式比较复杂,例如我们定义local a = 5 + 3 * 8,计算表达式时需要使用寄存器来存储结果,最终将结果存储到a中,但当这个表达式执行完毕时,临时分配的寄存器就可以被释放,下一个表达式就可以复用这些寄存器。因此随着代码的编译过程逐渐递增,fs->freereg并不会一直增加,但是,当我们定义一个局部变量时,由于该变量在该语句后还可以被引用,因此这个局部变量占用的fs->freereg并不能释放,lua通过fs->nactvar变量来进行控制,只有fs->freereg>=fs->nactvar部分寄存器可以被释放,fs->nactvar用来标记当前上下文活动的局部变量数。当进入for循环语句,for循环语句定义个局部变量也会导致fs->nactvar递增,但当for循环block结束时,fs->nactvar会还原(for循环block引用的局部变量占用的寄存器从而被释放),每编译完一个lua代码块,在chunk函数代码中有ls->fs->freereg = ls->fs->nactvar;这行代码来恢复可用的寄存器。理解lua编译器执行过程中寄存器的分配释放过程对理解编译部分源码有较大帮助,因此这里做了特殊说明。 到这里基本上定义local a = xx的语句我们已经理解其执行流程了。接下来再分析一个语句,一个不带local开头的表达式:

a = 1 其他部分基本一致,稍微不同点在于,最后会调用luaK_storevar:

void luaK_storevar (FuncState *fs, expdesc *var, expdesc *ex) {
  switch (var->k) {
    case VLOCAL: {
      freeexp(fs, ex);
      exp2reg(fs, ex, var->u.s.info);
      return;
    }
    case VUPVAL: {
      int e = luaK_exp2anyreg(fs, ex);
      luaK_codeABC(fs, OP_SETUPVAL, e, var->u.s.info, 0);
      break;
    }
    case VGLOBAL: {
      int e = luaK_exp2anyreg(fs, ex);
      luaK_codeABx(fs, OP_SETGLOBAL, e, var->u.s.info);
      break;
    }
    case VINDEXED: {
      int e = luaK_exp2RK(fs, ex);
      luaK_codeABC(fs, OP_SETTABLE, var->u.s.info, var->u.s.aux, e);
      break;
    }
    default: {
      lua_assert(0);  /* invalid var kind to store */
      break;
    }
  }
  freeexp(fs, ex);
}

函数中运行到分支VGLOBAL,然后将表达式的值存储到一个新的寄存器中(通过调用luaK_exp2anyreg),然后将该寄存器的值生成OP_SETGLOBAL保存到全局变量中,最后释放该临时寄存器。 PS:在看lua编译表达式部分代码时,对于这种赋值稍微复杂一点:

local a = b < 3 lua编译器对<这种操作符,实现是通过跳转指令来实现。在跳转指令的后面,会生成两条LOADBOOL指令,将1或0加载到寄存器中,同时会生成OP_LT指令,该指令判定b 和 3的大小来决定是否跳转。最终其生成的指令如下:

1       [1]     LOADK           0 -1    ; 1
    2       [2]     LT              1 0 -2  ; - 3 判定大小
    3       [2]     JMP             1       ; to 5
    4       [2]     LOADBOOL        1 0 1   为真会跳到这里,注意最后一个1,表示不会执行第5条指令(具体看lvm的源码对LOADBOOL的处理),这里很关键,否则有些看不明白。
    5       [2]     LOADBOOL        1 1 0
    6       [2]     RETURN          0 1

编译表达式部分就介绍到这里,至于复杂的表达式,使用递归方式实现即可(部分类似的代码也没仔细的去研读,感觉必要性不大)。而对于函数调用这类表达式,后续单独章节介绍。

本文作者:马良

原文链接:【源码解读】lua源码分析之编译器部分I(lua编译表达式),转载请注明来源!

0