《Walk On LuaJIT》 (上篇)
作者：Tweyseo
概要：经历了一段时间的打磨，Tweyseo老师在Lua.ren首发了他的新文章《Walk On LuaJIT》。因为微信公众号对群发文章有字数限制，我们把文章分多次发布。
国内关于LuaJIT原创文章不多，深耕细节的更少，Tweyseo老师经过自己的实践与思考完成这篇文章的同时，也将文中的一些关键细节与Openresty团队的老师进行了交流沟通，感谢Openresty团队的各位老师。但同时文章中也留下了难解的伏笔课题。
欢迎读者老师们参考阅读， 如果您对文中提到的一些不解的课题很了解的话，还请赐下您留言，帮我们解开迷雾见晴天，多谢！
0. 背景 a. 目的 这里主要研究LuaJIT的Trace的相关原理，并且展示如何使用LuaJIT提供的
v.lua和dump.lua工具来分析LuaJIT的行为，方便后续使优化工作在LuaJIT下的lua代码。当然，遵守Performance-Guide的规则，一定不会出现性能太差的代码。 b. 准备工作 首先配置调试LuaJIT-v2.1.0-beta3)源码的环境（Windows 64位 + VS 2019）： 1. 如果要得到精确的栈，需要修改\src\msvcbuild.bat，将`/O2`替换为`/Od`； 2. 在64位版本的vs命令行里执行`msvcbuild.bat debug`，生成luajit.exe，luajit.lib和lua51.lib； 3. 在VS里建立个命令工程（64位），设置\src为工作目录，指定\src为附加包含目录和附加库目录，并且在附加依赖项里加入luajit.lib和lua51.lib 4. 新建main.cpp，内容如下：
int main() {
lua_State *L = luaL_newstate(); /*创建一个解释器句柄*/
luaL_openlibs(L); /*打开所有的Lua库*/
luaL_loadfile(L, "../LuaJIT-Debug/t1.lua"); /*调入Lua脚本文件，注意路径*/
lua_pcall(L, 0, 0, 0); /*执行Lua脚本*/
lua_close(L); /*关闭句柄*/
return 0;
}可以先简单的调试下，测试lua脚本是否成功载入。 1. LuaJIT介绍 a. LuaJITVM概览 首先通过下面的图了解大概的LuaJITVM的模型，link表示静态的映射行为，而bind表示动态的映射行为（因为main lua_State是会切换的）。其中CTState涉及到ffi相关知识，在后续文章中会介绍。
b. LuaJIT的解释模式 要知道，所有的lua文件都会被LuaJIT编译成字节码（BC，bytecode），然后在LuaJIT的解释模式（interpreter）下执行。LuaJIT使用一个指令数组保存所有编译后生成的BC，在解释执行时，会从数组里逐条取出BC，使用其对应的操作码（opcode，在该BC的最低字节）作为索引在ASMFunction数组中取出对应内部汇编函数，执行具体操作（使用该BC中指定的寄存器里的内容作为操作参数），这样就把所有的BC都衔接了起来，而且这个过程中大多数操作都是使用机器指令直接编码的，所以，LuaJIT的解释模式比lua原生的解释器效率高好几倍。 c. trace的生成 解释执行字节码的时同时，LuaJIT会统计一些运行时的信息，如每个循环的实际执行次数，每个函数的实际调用次数等。当这些HotCount（low-overhead hashed profiling counters）超过某个阈值时（这里其实是先初始化为阈值，然后通过递减来计算的，而且对于（递归）函数和循环有所不同，具体见commit，便认为对应的代码段足够的“热”，此时就会触发lj_trace_hot开始tracing（提前是当前LuaJIT没有在做其它tracing）。 tracing的过程就是通过lj_trace_ins里的循环，驱动trace_state状态机，逐条记录（recording）对应代码段内即将执行的BC，其中记录的过程就是把BC转换成LuaJIT自定义中间码（[IR](https://en.wikipedia.org/wiki/Intermediate_representation)，Intermediate Representation），引入IR的目的是为了描述便于快速且有效进行优化的代码路径。要注意的是，IR并没有包含对应代码段内的所有BC，而是记录过程中，此代码段内实际执行的代码对应的BC：
require("jit.v").on("t1.log")
---
local a = 0
for i = 1, 58 do
if i <= 56 then -- i == 56 trigger hotcount, start tracing
a = 13
else
a = function() end -- 只尝试转换这部分代码对应的BC到IR
end
end
for i = 1, 58 do
if i <= 56 then -- i == 56 trigger hotcount, start tracing
a = function() end
else
a = 13 -- 只尝试转换这部分代码对应的BC到IR
end
end对应vlog：
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:8]
[TRACE 1 t1.lua:11 loop]同时也说明了，trace abort（后面将会介绍）只会发生在tracing阶段；而触发hotcount阈值的统计里，则仅仅只是循环/调用次数的统计，而不会有trace abort的。 成功记录完成后，再对生成的IR进行优化（使用启发式算法进行快速优化）；优化完成后，把最终的IR翻译为对应目标体系结构的机器码（MC，machine code），然后在打完补丁后最终提交MC，最后停止tracing，成功生成trace。 2. trace介绍 a. trace 首先，trace是线性的，这意味着一个trace对应一个代码路径，也就是说不能包含条件代码或内部跳转。trace又分为roottrace（一般就叫trace）和sidetrace（会在后面介绍），上面描述的生成trace的过程，其实是roottrace的生成过程：
require("jit.v").on("t1.log")
---
local function f1(v)
if v == 0 then
return
end
f1(v - 1)
end
local function f2(v)
if v == 0 then
return
end
return f2(v - 1) -- return (f2(v - 1))就变成了普通递归（up-recursion）
end
for i = 1, 58 do end
f1(112)
f2(114)对应的vlog：
[TRACE 1 t1.lua:19 loop]
[TRACE 2 t1.lua:3 up-recursion]
[TRACE 3 t1.lua:11 tail-recursion]观察此log可以知道，TRACE 1是一个roottrace，是由包含for循环的代码段（第19行）足够热而生成的；TRACE 2也是一个roottrace，是由包含递归的函数f1所在的代码段（第3行）足够“热”而生成的；同样地，TRACE 3也还是一个roottrace，是由包含尾递归的函数f2所在的代码段（第11行）足够“热”而生成的。 前面讲的都是trace生成的过程，下面再来看看trace运行的过程。 trace的运行，其实就是运行对应代码段的MC。前面提到，trace是线性的，为了保持这个特性，会在tracing的记录的时候（用IR描述），在trace对应的代码段中的分支（同代码段，但是与当前trace有着不同代码路径，如if，循环的结束，等）上，建立快照（snapshot），用于储存trace运行时的所有更新的一致性视图（补偿代码的形式），并且设置相应的守卫（guard）。在运行该trace的时候，一旦条件发生改变（包含循环的结束），进入了分支，就会触发守卫失败，从而使得当前trace退出（exit），最后根据trace退出之前，最近的快照（快照里的内容实际是相关的寄存器的地址信息（tracing时确定），真正的更新内容是在对应的寄存器里的信息（trace运行时确定））更新Snapshot Restore解释模式下的LuaJITVM的状态，并且切换到解释模式。要注意，无论是在解释模式，还是运行trace的模式，LuaJITVM的状态都必须保持执行时的一致。使用下面代码来说明此过程（使用dump的时候，s表示snapshot，i表示IR，x表示trace exit）：
require("jit.dump").on("six", "t1.dlog")
---
local a
for i = 1, 100 do
if i == 80 then
a = 13
else
a = 67
end
end对应的dumplog：
---- TRACE 1 start t1.lua:4
---- TRACE 1 IR
.... SNAP #0 [ ---- ]
0001 int SLOAD #2 CI
.... SNAP #1 [ ---- ---- 0001 ---- ---- 0001 ]
0002 > int NE 0001 +80
0003 + int ADD 0001 +1
.... SNAP #2 [ ---- +67 ]
0004 > int LE 0003 +100
.... SNAP #3 [ ---- +67 0003 ---- ---- 0003 ]
0005 ------ LOOP ------------
.... SNAP #4 [ ---- +67 0003 ---- ---- 0003 ]
0006 > int NE 0003 +80
0007 + int ADD 0003 +1
.... SNAP #5 [ ---- +67 ]
0008 > int LE 0007 +100
0009 int PHI 0003 0007
---- TRACE 1 stop -> loop
---- TRACE 1 exit 4
---- TRACE 1 exit 5
观察日志可以知道，trace 1在`i == 80`的时候，分支条件发生改变（生成的trace 1的代码路径里没有包含`i == 80`里的代码路径），守卫`0006 > int NE 0003 +80`失败，此时trace1退出，然后根据快照4里的内容，更新解释模式下的LuaJITVM的状态，然后切换到解释模式，对应`TRACE 1 exit 4`；类似地，trace 1在`i > 100`的时候，分支条件发生改变（生成的trace 1的代码路径里没有包含`i > 100`后的代码路径），守卫`0008 > int LE 0007 +100`失败，此时trace1退出，然后根据快照5里的内容，更新解释模式下的LuaJITVM的状态，然后切换到解释模式，对应`TRACE 1 exit 5`。 这里为什么if和循环结束都对应了2个guard（1和4，2和5） 通过调试上述代码，发现lj_trace_exit确实是被调用了2次，而且在此函数中，会调用lj_snap_restore获取对应快照中的内容，然后通过lj_vmevent_send更新相应内容到解释模式下的LuaJITVM的状态，最后带着运行trace产生的返回值（如果有的话）一起切换到解释模式。 实际上，LuaJIT为了效率考虑，并且由于快照的事务性的特点（每个快照就相当于一个提交，在守卫失败，trace退出的时候，只需要获取在这之前的，最后一次提交，进行回滚），所以对那些失败概率比较低的守卫是不会生成快照的，此特性叫做稀疏快照。 再来看看前面例子中的vlog：
[TRACE 1 t1.lua:19 loop]
[TRACE 2 t1.lua:3 up-recursion]
[TRACE 3 t1.lua:11 tail-recursion]这里，每个trace的最后（loop，up-recursion和tail-recursion）部分，表示trace的连接（link），成功生成trace后，紧接着（的BC）就是该trace的运行，那么这个生成的trace就会连接到该trace的运行(的BC)，当这些trace全部运行结束后，仅会有一次（但是多次非尾递归的情况下，有多次其它出口的该trace退出日志，不大理解）该trace退出的行为（lj_trace_exit），表现为连接到自身；反之，如果只有trace的生成，没有trace的运行（循环表现为产生leaving loop in root trace的trace abort而生成trace失败；递归则是需要trace的运行次数到达一定阈值的），自然也不会有trace的退出行为，表现为连接到return（对应LJ_TRLINK_RETURN，即return到解释模式）。连接是在lj_record_stop的时候设置的，它有好几种类型。 所以，这里的的log表示trace 1，2，3都分别各自连接到自身（循环和递归）。但是注意，如果把f1的调用次数修改为[109, 111]：
require("jit.v").on("t1.log")
---
local function f1(v)
if v == 0 then
return
end
f1(v - 1)
end
f1(111) -- 109和110也是link return的vlog
vlog就会显示连link return：
[TRACE 1 t1.lua:3 return]先来分析其生成trace的过程（***要提前说明的是，对于普通递归，在此测试环境编译出来的LuaJIT执行jit.v（jit.v的日志和在此测试环境中调试该LuaJIT时的行为一致）和jit.dump的日志有偏差（jit.dump分别在110，111，112出现link return的日志）的情况，具体原因还没搞明白，这里暂时按照调试的过程来说明***）：普通递归函数触发tracing的阈值是109，可是开始记录的时候，v的值已经为0了，此时就直接走BC RET0对应的处理函数lj_record_re，设置连接到return后，停止记录和tracing，成功生成trace：
lj_record_stop(J, LJ_TRLINK_RETURN, 0); /* Return to interpreter. */而在调用值为大于109的时候，在记录的时候，v的值不为0，还会再递归调用f1，所以会在BC CALL对应的处理函数lj_record_call里，递增调用帧的深度以后，再在BC FUNCF对应的处理函数的逻辑中，调用check_call_unroll。此函数对于非递归调用，会检测调用展开的限制；而对于递归调用，（从记录开始）超过递归调用要求的最小调用次数2（也就是前面提到的需要达到的trace运行次数的最小阈值），就会设置连接到递归自身（Up-recursion），然后停止记录和tracing，成功生成trace（尾递归f2也类似，但由于尾递归不会在当前函数展开调用堆栈的缘故，所以对应尾递归会设置连接到尾递归自身，即Tail-rec，具体见BC CALLT对于的处理函数lj_record_tailcall。还有一点是，尾递归触发tracing的阈值是111）：
if (J->framedepth + J->retdepth == 0)
lj_record_stop(J, LJ_TRLINK_TAILREC, J->cur.traceno); /* Tail-rec. */
else
lj_record_stop(J, LJ_TRLINK_UPREC, J->cur.traceno); /* Up-recursion. */而上面由于110和111都没有超过tracing的记录过程中，递归调用要求的最小调用次数，所以在递归调用结束后进入了BC RET0的逻辑（lj_record_ret），从而设置连接到return后，停止记录和tracing，当然，也还是成功生成了trace。 对于link return和link self的trace，在trace运行上面也有很大的区别（这里使用尾递归来分析，递归会涉及dowe-recursion，这个稍后介绍）：
require("jit.dump").on("six", "t1.dlog")--require("jit.v").on("t1.log")--
---
local function f1(v)
if v == 0 then
return
end
return f1(v - 1)
end
f1(114) -- link self
-- f1(113) -- link return
f1(30)对应的link self的dumplog：
---- TRACE 1 start t1.lua:3
---- TRACE 1 IR
.... SNAP #0 [ ---- ---- ]
0001 > num SLOAD #1 T
.... SNAP #1 [ ---- ---- ]
0002 > num NE 0001 +0
.... SNAP #2 [ ---- ---- ]
0003 fun SLOAD #0 R
0004 > fun EQ 0003 t1.lua:3
0005 num SUB 0001 +1
.... SNAP #3 [ t1.lua:3|---- ]
0006 > num NE 0005 +0
0007 num SUB 0005 +1
.... SNAP #4 [ t1.lua:3|---- ]
0008 > num NE 0007 +0
0009 + num SUB 0007 +1
.... SNAP #5 [ t1.lua:3|0009 ]
0010 ------ LOOP ------------
.... SNAP #6 [ t1.lua:3|0009 ]
0011 > num NE 0009 +0
0012 num SUB 0009 +1
.... SNAP #7 [ t1.lua:3|0009 ]
0013 > num NE 0012 +0
0014 num SUB 0012 +1
.... SNAP #8 [ t1.lua:3|0009 ]
0015 > num NE 0014 +0
0016 + num SUB 0014 +1
0017 num PHI 0009 0016
---- TRACE 1 stop -> tail-recursion
---- TRACE 1 exit 1
---- TRACE 1 exit 6对应的link return的dumplog：
---- TRACE 1 start t1.lua:3
---- TRACE 1 IR
.... SNAP #0 [ ---- ---- ]
0001 > num SLOAD #1 T
.... SNAP #1 [ ---- ---- ]
0002 > num NE 0001 +0
.... SNAP #2 [ ---- ---- ]
0003 fun SLOAD #0 R
0004 > fun EQ 0003 t1.lua:3
0005 num SUB 0001 +1
.... SNAP #3 [ t1.lua:3|---- ]
0006 > num NE 0005 +0
0007 num SUB 0005 +1
.... SNAP #4 [ t1.lua:3|0007 ]
0008 > num EQ 0007 +0
.... SNAP #5 [ t1.lua:3|]
---- TRACE 1 stop -> return
---- TRACE 1 exit 4
---- TRACE 1 exit 4
---- TRACE 1 exit 4
---- TRACE 1 exit 4
---- TRACE 1 exit 4
---- TRACE 1 exit 4
---- TRACE 1 exit 4
---- TRACE 1 exit 4
---- TRACE 1 exit 4
---- TRACE 1 exit 4
---- TRACE 2 start 1/4 t1.lua:8
---- TRACE 2 abort t1.lua:12 -- NYI: bytecode 50对比上面2个dumplog可以发现，link self的trace，只有两次退出，紧邻trace生成的trace运行完毕（`f(114)`）退出，和第二次调用f触发的trace运行完毕（`f(30)`）退出；而link return的trace，在`f(113)`的时候只有trace的生成，没有trace的运行，由于生成的是link return的trace，所以在第二次调用f中，每次trace运行完毕就会退出（这里的trace1在exit4退出达到了hot side exit的阈值，产生了sidetrace的tracing，虽然tracing由于NYI而trace abort了。而至于这个第二`f(30)`，是跟`f(113)`生成的该trace的tracing递归了3次而结束tracing，成功生成该trace的行为对应的，hot side exit的阈值是30/3，所以`f(112)`对应`f(20)`，`f(111)`对应`f(10)`。这里先简单了解下这个概念，后面会详细介绍）。 循环的连接则没有link return的行为，取而代之的是直接生成trace失败，这一点后面会介绍。 还有个比较特殊的连接类型 —— LJ_TRLINK_DOWNREC（Down-recursion），但是目前还不是很理解down-recursion的行为。 b. trace abort 如果tracing的过程中产生了错误，就会导致trace abort，从而停止tracing，当然也不会生成trace。一般地，这些错误都是通过lj_trace_err递出来，触发LJ_TRACE_ERR状态以后在trace_abort函数中处理。 当生成roottrace的tracing过程中产生了trace abort，且此tracing起始的BC的操作码不是return类操作码（RETM，RET，RET0，RET1）的情况下，就会对该tracing的起始BC进行“惩罚”。 “惩罚”的过程，即在jit_State的惩罚数组中查找是否对应BC已经被记录过（没有就记录下来），有记录就按特定算法增加其惩罚因子，增加后的惩罚因子如果超过阈值就把该BC列入黑名单，即直接修改该BC的操作码。一旦某个BC被加入黑名单，就不会再对该BC进行解释时的hotcount的统计，而只对该BC做单纯的解释执行（这也意味着比普通的解释会更快）：
require("jit.v").on("t1.log")--require("jit.dump").on("six", "t1.dlog")--
---
local a
local function f1()
for _ = 1, 1e5 do
a = function() end
end
end
f1()
f1() -- debug发现不会触发lj_trace_hot
local function f2()
f1()
end
f2() -- debug发现不会触发lj_trace_hot而且如果在其它hotcount触发的tracing过程中，遇到被列入黑名单的BC，相应地，也会产生LJ_TRERR_BLACKL的trace abort：
require("jit.v").on("t1.log")--require("jit.dump").on("six", "t1.dlog")--
---
local function f1()
for i = 1, 1e5 do
if i >= 57 then
local a = function() end
end
end
end
f1()
for i = 1, 58 do
if i == 57 then
f1()
end
end对应的vlog为：
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:4 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:11 -- blacklisted at t1.lua:4]还有一点要注意的是，如果该BC的惩罚因子没超过黑名单的阈值，则会修改其对应的hotcount的阈值（也就是说，tracing起始的BC的操作码不是return类操作码，且未进入黑名单的情况下，会更改该BC的hotcount的阈值）：
require("jit.v").on("t1.log")--require("jit.dump").on("six", "t1.dlog")--
---
for i = 1, 168 do
if i == 57 then
-- 生成trace的时候产生trace abort,修改hotcount的阈值为72(循环/2),
local a = function() end
end
if i == 94 then
-- 57 + 72/2 + 1的时候生成trace的时候再次产生trace abort,修改hotcount的阈值为144(循环/2),
local a = function() end
end
-- 所以94 + 144/2 + 1 = 167的时候再次tracing成功(注意,168才成功的生成trace,具体原因下面介绍)
endvlog的内容很好的说明了这一点：
[TRACE --- t1.lua:3 -- NYI: bytecode 51 at t1.lua:6]
[TRACE --- t1.lua:3 -- NYI: bytecode 51 at t1.lua:10]
[TRACE 1 t1.lua:3 loopSelf-link is blacklisted的情况怎么理解 trace abort中还有两种特殊的的情况分别是：当引起trace abort的错误是LJ_TRERR_DOWNREC的话，就会尝试调用trace_downrec函数针对down-recursion的情况来生成新的roottrace（过程和生成普通的roottrace一样）；如果TraceError是LJ_TRERR_MCODELM，也会进行重试，不同的是，这种情况是从LJ_TRACE_ASM状态开始重试。 导致trace abort的原因很多（具体可以参考lj_traceerr.h，这里主要介绍一些常见的类型以及避免办法： - NYI，这个应该是最常见的trace abort了，NYI也有很多具体很多，具体可以参考官方的wiki。由于vlog提供的NYI都是id，不熟悉的话，可以使用bc.lua找出对应的BC，然后再去官方Bytecode-2.0中对照查看。 - leaving loop in root trace，往往出现在生成循环类roottrace的时候。虽然循环的hotcount的阈值是56，但是由于额外的记录闭合循环的规则，所以循环次数为56的时候无法成功生成trace；而对于57，虽然满足了记录闭合循环的规则，但是由于for循环对应的trace，其主要工作就是模拟FOR循环迭代器的运行时行为（可以认为循环类的trace，是在`i == 57`的时候生成的，注意和递归的情况的区别），而到达57以后，循环就结束了，模拟也就没有意义，所以这里也无法成功生成trace，具体细节见循环中BC FORL的相关处理函数rec_for_iter。这里要注意区分，与前面提到的递归类trace中的link return的行为的不同。 - inner loop in root trace，不是很理解。 - loop unroll limit reached，在tracing的过程（包括用于生成sidetrace的tracing）中，如果遇到了未生成trace的循环或者递归（包括尾递归，如果不希望尾递归，可以使用括号包装返回值来避免，如，`return funccall()`改为`return (funccall())`），就会尝试把循环或者递归展开来记录，如果展开的次数超过了阈值15减去初始的1次和<的要求，实际值是17），就会产生此trace abort。比较特殊的地方是，导致的该trace abort的循环或者递归，可能在后面生成其它的trace。 - call unroll limit reached，前面提到，在触发tracing的时候，对于非递归的函数调用，会对其做展开限制检查，如果调用帧的深度（在BC CALL对应的处理函数lj_record_call里递增）超过了阈值3，就会产生LJ_TRERR_CUNROLL的trace abort，而无法成功生成trace。 - down-recursion, restarting，不是很理解。 - NYI: return to lower frame，不是很理解。 - blacklisted，tracing中遇到了被列入黑名单的BC而产生的trace abort。要注意的是，被列入黑名单的BC虽然是在纯解释执行，性能会比普通的解释执行要好，但是由它带来的trace abort还是会使得生成trace失败的。
未完待续...