Tutorial: next
and ITERN
Gotchas¶
Introduction¶
This article gathers bits and pieces around the mega-task of compiling generic for loops.
Semantics of the Generic for Loop¶
According to the Language Reference Manual, a generic for loop
for var_1, ..., var_n in explist do
block
end
is equivalent to:
do
local f, s, var = explist
while true do
local var_1, ..., var_n = f(s, var)
var = var_1
if var == nil then
break
end
block
end
end
Translating to Bytecode: General Case¶
In most general case, generic for
loops are translated into:
... ; Fetch f, s and var somehow (e.g. make a CALL to pairs)
JMP =>iter ; Enter the loop: jump to the first call to the iterator
body:
; ...
; block
; ...
iter:
HOTCNT ; Bump counter for the hot code
ITERC ; Call the iterator via regular VM calling convention (i.e. unstash f, s, var and CALL)
ITERL =>body ; Inspect iterator's return values:
; If the first variable is nil, fall through (= exit the loop).
; Otherwise update var and execute loop body once.
Please note:
ITERC
is recorded, like any otherCALL
-like instruction (in fact,ITERC
belongs to theCALL
family of byte codes).ITERL
is recorded, it is one of the entry points to the compiled code. Technically, we enter the trace inJLOOP
, andJITERL
is a thin wrapper around it.
Translating to Bytecode: Specialized Case¶
Whenever built-in next
is used as an iterator (directly or via pairs
), generic for
loops are translated into:
... ; Fetch f, s and var somehow (e.g. make a CALL to pairs)
ISNEXT =>iter ; Check that the actual iterator is built-in next:
; If it is not true, *dynamically* change ITERN to ITERC
; falling back to the general case.
; JMP =>iter.
body:
; ...
; block
; ...
iter:
HOTCNT ; Bump counter for the hot code
ITERN ; 1) Advance to the next element in s
; 2) If there are no more elements, JMP =>end_of_loop
; 3) Otherwise update var and JMP =>body
ITERL =>body ; Not called
end_of_loop:
Please note:
- Emission of
JMP
/ITERC
vs.ISNEXT
/ITERN
is done by the front end based on some heuristics (seelj_parse.c
).ITERN
is de facto an alternative VM-side implementation of the built-innext
function.ISNEXT
is not recorded.ITERN
is not recorded.- Additionally,
tab_next
inlj_tab.c
implements approximately the same semantics asITERN
, which are used e.g. inluaE_iterate
.
next
as a Built-in Function¶
Apart from the ITERN
byte-code, the platform obviously provides the next
function itself:
next
is a fast function implemented in assembly (look for something like.ffunc_1 next
in VM code).next
is not recorded.next
uses (slow)lj_tab_next
to iterate over the table. (TODO: Can we switch it to the fasterlj_tab_iterate
, by the way?)
ISNEXT
and Magic Constant 0xfffe7fff
¶
When ISNEXT
ensures that it is ok to iterate with ITERN
, it prepares the stack slot for the control variable in a special manner (TODO: Can we dump it accordingly?):
MSB LSB
64 bits 32 bits 32 bits
+----------------+--------+--------+
| LJ_TNUMX|fffe7fff| payload|
+----------------+--------+--------+
Now, when ITERN
traverses the table, only 32 payload
bits are de facto used to store either an index to the array part
or asize + index to the hash part
.
There is, however, a very rare use case for the magic constant 0xfffe7fff
: whenever ITERN
is despecialized to ITERC
on the fly, it is used as a signal to convert the control variable to the lj_tab_next
-compatible form. To understand this, please play with following code:
local t = { foo = 9, bar = 10, 4, 5, 6 }
local r = {}
local function dummy() end
local function f(next)
for k, v in next, t, nil do
r[#r + 1] = k
if v == 5 then
f(dummy)
end
end
end
f(next)
assert(#r == 5)
More Context¶
- An attempt to record
next
(the built-in) for LuaJIT: https://blog.cloudflare.com/luajit-hacking-getting-next-out-of-the-nyi-list/.