dymokomi/luce-js
Source of release 0.6.1
0.6.1 / src / engine / resolve_labels.lucb
#==============================================================================================
#
# resolve_labels - Phase 3 of the compiler: labels, jumps and the final bytecode
#
# DESCRIPTION:
# Port of quickjs.c resolve_labels (lines 34796-35697): the function's prologue
# (the pseudo variables and 'arguments'), label placement and relocation, tail
# calls, jump threading and the short jump forms, then the pc2line table. The
# peephole optimizations of the other opcodes are in resolve_labels_peephole.lucb.
#
# C's loop is one switch whose cases jump to four shared tails: `has_constant_test`
# (a constant followed by if_false/if_true), `has_goto` (jump threading),
# `has_label` (emit a jump) and `no_change` (copy the opcode). Here the state C
# keeps in locals lives in a ResolveLabelsState, each case answers the LabelStep
# it would jump to, and the loop runs the tails until one is done.
#
#==============================================================================================
# mark: State ===================================================================================
## The locals of resolve_labels that its cases and tails share.
struct ResolveLabelsState:
var ctx: Context*
var s: FunctionDef*
## The phase 2 bytecode.
var bc_buf: const u8*
var bc_len: i32
## The phase 3 bytecode being written.
var bc_out: cutils.DynBuf
var cc: CodeContext
## The opcode being resolved: its position and size; pos_next is where the next one
## starts, after what a transformation consumed.
var pos: i32
var len: i32
var pos_next: i32
## The opcode to emit: the one read, or the jump a transformation turned it into.
var op: i32
## The label of the jump to emit.
var label: i32
## The value of the constant tested by has_constant_test.
var val: i32
## The source position of the current opcode.
var line_num: i32
## Where a case of resolve_labels continues (the targets of its gotos).
enum LabelStep:
## The opcode was handled (C's `break`).
done
## Copy the opcode unchanged.
no_change
## Thread and emit the goto to `label`.
has_goto
## Emit the jump `op` to `label`.
has_label
## A constant `val` is followed by if_false/if_true (in `cc`).
has_constant_test
# The jump slot `idx` of fd.jump_slots (&fd->jump_slots[idx]).
func fd_jump_slot(fd: FunctionDef*, idx: i32) -> JumpSlot*:
let slots = fd.jump_slots else trap("FunctionDef: no jump slots")
return slots + (isize)idx
# The next jump slot (&s->jump_slots[s->jump_count++]); resolve_variables counted them in
# s.jump_size.
func next_jump_slot(s: FunctionDef*) -> JumpSlot*:
assert(s.jump_count < s.jump_size, "resolve_labels: more jumps than counted")
let jp = fd_jump_slot(s, s.jump_count)
s.jump_count += 1
return jp
# add_pc2line_info for the next opcode written.
func state_pc2line(p: ResolveLabelsState*):
add_pc2line_info(p.s, (u32)p.bc_out.size, (u32)p.line_num)
# Take the line number of the last code_match if it skipped one.
func state_match_line(p: ResolveLabelsState*):
if p.cc.line_num >= 0:
p.line_num = p.cc.line_num
# Emit `op` and its operand, an OPSpecialObjectEnum value.
func emit_special_object(bc: cutils.DynBuf*, kind: OpSpecialObject):
dbuf_op(bc, Op.special_object)
dbuf_byte(bc, (u8)kind)
# mark: Prologue ================================================================================
# Emit the initialization of the variables the function creates on entry.
func emit_function_prologue(s: FunctionDef*, bc_out: cutils.DynBuf*):
# initialize the 'home_object' variable if needed
if s.home_object_var_idx >= 0:
emit_special_object(bc_out, OpSpecialObject.home_object)
put_short_code(bc_out, (i32)Op.put_loc, s.home_object_var_idx)
# initialize the 'this.active_func' variable if needed
if s.this_active_func_var_idx >= 0:
emit_special_object(bc_out, OpSpecialObject.this_func)
put_short_code(bc_out, (i32)Op.put_loc, s.this_active_func_var_idx)
# initialize the 'new.target' variable if needed
if s.new_target_var_idx >= 0:
emit_special_object(bc_out, OpSpecialObject.new_target)
put_short_code(bc_out, (i32)Op.put_loc, s.new_target_var_idx)
# initialize the 'this' variable if needed. In a derived class constructor, this is
# initially uninitialized.
if s.this_var_idx >= 0:
if s.is_derived_class_constructor:
dbuf_op(bc_out, Op.set_loc_uninitialized)
dbuf_u16(bc_out, s.this_var_idx)
else:
dbuf_op(bc_out, Op.push_this)
put_short_code(bc_out, (i32)Op.put_loc, s.this_var_idx)
# initialize the 'arguments' variable if needed
if s.arguments_var_idx >= 0:
if ((i32)s.js_mode & js_mode_strict) != 0 or not s.has_simple_parameter_list:
emit_special_object(bc_out, OpSpecialObject.arguments)
else:
emit_special_object(bc_out, OpSpecialObject.mapped_arguments)
# the arguments are implicitly captured because references to them are
# created with the 'argument' object
for i in 0..<s.arg_count:
capture_var(s, fd_arg(s, i))
if s.arguments_arg_idx >= 0:
put_short_code(bc_out, (i32)Op.set_loc, s.arguments_arg_idx)
put_short_code(bc_out, (i32)Op.put_loc, s.arguments_var_idx)
# initialize a reference to the current function if needed
if s.func_var_idx >= 0:
emit_special_object(bc_out, OpSpecialObject.this_func)
put_short_code(bc_out, (i32)Op.put_loc, s.func_var_idx)
# initialize the variable environment object if needed
if s.var_object_idx >= 0:
emit_special_object(bc_out, OpSpecialObject.var_object)
put_short_code(bc_out, (i32)Op.put_loc, s.var_object_idx)
if s.arg_var_object_idx >= 0:
emit_special_object(bc_out, OpSpecialObject.var_object)
put_short_code(bc_out, (i32)Op.put_loc, s.arg_var_object_idx)
# mark: Labels and jumps ========================================================================
# OP_label: place the label here and patch the jumps that were waiting for it.
func place_label(p: ResolveLabelsState*):
let s = p.s
let label = (i32)cutils.get_u32(p.bc_buf + p.pos + 1)
assert(label >= 0 and label < s.label_count)
let ls = fd_label(s, label)
assert(ls.addr == -1)
ls.addr = (i32)p.bc_out.size
# resolve the relocation entries
var next = ls.first_reloc
while let re = next:
let diff = ls.addr - (i32)re.addr
next = re.next
let buf = dbuf_bytes_or_empty(&p.bc_out)
match re.size:
4:
cutils.put_u32(buf + re.addr, (u32)diff)
2:
assert(diff == (i32)(i16)diff)
cutils.put_u16(buf + re.addr, (u16)diff)
1:
assert(diff == (i32)(i8)diff)
cutils.put_u8(buf + re.addr, (u8)diff)
_:
_ = 0
js_free(p.ctx, re)
ls.first_reloc = none
# has_constant_test: `val` is followed by if_false/if_true (matched in cc).
func label_constant_test(p: ResolveLabelsState*) -> LabelStep:
state_match_line(p)
if p.val == p.cc.op - (i32)Op.if_false:
# transform null if_false(l1) -> goto l1
# transform false if_false(l1) -> goto l1
# transform true if_true(l1) -> goto l1
p.pos_next = p.cc.pos
p.op = (i32)Op.goto_
p.label = p.cc.label
return LabelStep.has_goto
# transform null if_true(l1) -> nop
# transform false if_true(l1) -> nop
# transform true if_false(l1) -> nop
p.pos_next = p.cc.pos
_ = update_label(p.s, p.cc.label, -1)
return LabelStep.done
# has_goto: thread the goto to `label`.
func label_goto(p: ResolveLabelsState*) -> LabelStep:
let s = p.s
var op1: i32 = 0
var line1: i32 = -1
# Use custom matcher because multiple labels can follow
p.label = find_jump_target(s, p.label, &op1, &line1)
if code_has_label(&p.cc, p.pos_next, p.label):
# jump to next instruction: remove jump
_ = update_label(s, p.label, -1)
return LabelStep.done
if op1 == (i32)Op.return_ or op1 == (i32)Op.return_undef or op1 == (i32)Op.throw:
# jump to return/throw: remove jump, append return/throw
# updating the line number obfuscates assembly listing
# if (line1 != -1) line_num = line1;
_ = update_label(s, p.label, -1)
state_pc2line(p)
dbuf_byte(&p.bc_out, (u8)op1)
p.pos_next = skip_dead_code(s, p.bc_buf, p.bc_len, p.pos_next, &p.line_num)
return LabelStep.done
# XXX: should duplicate single instructions followed by goto or return
# For example, can match one of these followed by return:
# push_i32 / push_const / push_atom_value / get_var /
# undefined / null / push_false / push_true / get_ref_value /
# get_loc / get_arg / get_var_ref
return LabelStep.has_label
# has_label: emit the jump `op` to `label`, in its short form when the distance allows.
func label_emit_jump(p: ResolveLabelsState*) -> !:
let s = p.s
let op = p.op
state_pc2line(p)
if op == (i32)Op.goto_:
p.pos_next = skip_dead_code(s, p.bc_buf, p.bc_len, p.pos_next, &p.line_num)
assert(p.label >= 0 and p.label < s.label_count)
let ls = fd_label(s, p.label)
let jp = next_jump_slot(s)
jp.op = op
jp.size = 4
jp.pos = (i32)p.bc_out.size + 1
jp.label = p.label
let is_short_jump = (op == (i32)Op.if_false or op == (i32)Op.if_true or op == (i32)Op.goto_)
if ls.addr == -1:
let diff = ls.pos2 - p.pos - 1
if diff < 128 and is_short_jump:
jp.size = 1
jp.op = (i32)Op.if_false8 + (op - (i32)Op.if_false)
dbuf_byte(&p.bc_out, (u8)jp.op)
dbuf_byte(&p.bc_out, 0)
_ = try add_reloc(p.ctx, ls, (u32)p.bc_out.size -% 1, 1)
return
if diff < 32768 and op == (i32)Op.goto_:
jp.size = 2
jp.op = (i32)Op.goto16
dbuf_op(&p.bc_out, Op.goto16)
dbuf_u16(&p.bc_out, 0)
_ = try add_reloc(p.ctx, ls, (u32)p.bc_out.size -% 2, 2)
return
else:
let diff = ls.addr - (i32)p.bc_out.size - 1
if diff == (i32)(i8)diff and is_short_jump:
jp.size = 1
jp.op = (i32)Op.if_false8 + (op - (i32)Op.if_false)
dbuf_byte(&p.bc_out, (u8)jp.op)
dbuf_byte(&p.bc_out, (u8)diff)
return
if diff == (i32)(i16)diff and op == (i32)Op.goto_:
jp.size = 2
jp.op = (i32)Op.goto16
dbuf_op(&p.bc_out, Op.goto16)
dbuf_u16(&p.bc_out, diff)
return
dbuf_byte(&p.bc_out, (u8)op)
dbuf_u32(&p.bc_out, (u32)(ls.addr - (i32)p.bc_out.size))
if ls.addr == -1:
# unresolved yet: create a new relocation entry
_ = try add_reloc(p.ctx, ls, (u32)p.bc_out.size -% 4, 4)
# with_get_var ... with_get_ref: the atom, the jump to the label past the with test, and
# the is_with flag.
func label_with_op(p: ResolveLabelsState*) -> !:
let s = p.s
let atom = cutils.get_u32(p.bc_buf + p.pos + 1)
var label = (i32)cutils.get_u32(p.bc_buf + p.pos + 5)
let is_with = p.bc_buf[p.pos + 9]
var op1: i32 = 0
label = find_jump_target(s, label, &op1, none)
assert(label >= 0 and label < s.label_count)
let ls = fd_label(s, label)
state_pc2line(p)
let jp = next_jump_slot(s)
jp.op = p.op
jp.size = 4
jp.pos = (i32)p.bc_out.size + 5
jp.label = label
dbuf_byte(&p.bc_out, (u8)p.op)
dbuf_u32(&p.bc_out, atom)
dbuf_u32(&p.bc_out, (u32)(ls.addr - (i32)p.bc_out.size))
if ls.addr == -1:
# unresolved yet: create a new relocation entry
_ = try add_reloc(p.ctx, ls, (u32)p.bc_out.size -% 4, 4)
dbuf_byte(&p.bc_out, is_with)
# mark: The jump opcodes ========================================================================
# The cases of resolve_labels' switch for labels, line numbers, calls, returns and
# jumps; the others are resolve_labels_peephole's.
func resolve_labels_op(p: ResolveLabelsState*) -> LabelStep!:
let s = p.s
let bc_buf = p.bc_buf
let pos = p.pos
let op = bc_buf[pos]
if is_temp_op(op):
match (TempOp)op:
.line_num:
# line number info (for debug). We put it in a separate compressed table
# to reduce memory usage and get better performance
p.line_num = (i32)cutils.get_u32(bc_buf + pos + 1)
return LabelStep.done
.label:
place_label(p)
return LabelStep.done
_:
return LabelStep.no_change
match (Op)op:
.call, .call_method:
# detect and transform tail calls
let argc = (i32)cutils.get_u16(bc_buf + pos + 1)
if code_match(&p.cc, p.pos_next, [(i32)Op.return_, -1]):
state_match_line(p)
state_pc2line(p)
put_short_code(&p.bc_out, (i32)op + 1, argc)
p.pos_next = skip_dead_code(s, bc_buf, p.bc_len, p.cc.pos, &p.line_num)
return LabelStep.done
state_pc2line(p)
put_short_code(&p.bc_out, (i32)op, argc)
return LabelStep.done
.return_, .return_undef, .return_async, .throw, .throw_error:
p.pos_next = skip_dead_code(s, bc_buf, p.bc_len, p.pos_next, &p.line_num)
return LabelStep.no_change
.goto_:
p.label = (i32)cutils.get_u32(bc_buf + pos + 1)
return LabelStep.has_goto
.gosub:
p.label = (i32)cutils.get_u32(bc_buf + pos + 1)
# QuickJS's removal of empty finally clauses (a gosub to a ret) is disabled
# here (`if (0 && OPTIMIZE)`).
return LabelStep.has_label
.catch_:
p.label = (i32)cutils.get_u32(bc_buf + pos + 1)
return LabelStep.has_label
.if_true, .if_false:
p.label = (i32)cutils.get_u32(bc_buf + pos + 1)
var op1: i32 = 0
p.label = find_jump_target(s, p.label, &op1, none)
# transform if_false/if_true(l1) label(l1) -> drop label(l1)
if code_has_label(&p.cc, p.pos_next, p.label):
_ = update_label(s, p.label, -1)
dbuf_op(&p.bc_out, Op.drop)
return LabelStep.done
# transform if_false(l1) goto(l2) label(l1) -> if_false(l2) label(l1)
if code_match(&p.cc, p.pos_next, [(i32)Op.goto_, -1]):
let pos1 = p.cc.pos
let line1 = p.cc.line_num
if code_has_label(&p.cc, pos1, p.label):
if line1 != -1:
p.line_num = line1
p.pos_next = pos1
_ = update_label(s, p.label, -1)
p.label = p.cc.label
p.op ^= (i32)Op.if_true ^ (i32)Op.if_false
return LabelStep.has_label
.with_get_var, .with_put_var, .with_delete_var, .with_make_ref, .with_get_ref:
try label_with_op(p)
return LabelStep.done
_:
return resolve_labels_peephole(p)
# mark: resolve_labels ==========================================================================
# The main loop of resolve_labels, which frees the new bytecode if it fails.
func resolve_labels_code(p: ResolveLabelsState*) -> !:
# fail:
# XXX: not safe
errdefer cutils.dbuf_free(&p.bc_out)
while p.pos < p.bc_len:
let op = p.bc_buf[p.pos]
p.op = (i32)op
p.len = (i32)op_info(op, true).size
p.pos_next = p.pos + p.len
var step = try resolve_labels_op(p)
while true:
match step:
.has_constant_test:
step = label_constant_test(p)
.has_goto:
step = label_goto(p)
.has_label:
try label_emit_jump(p)
break
.no_change:
state_pc2line(p)
_ = cutils.dbuf_put(&p.bc_out, p.bc_buf + p.pos, (usize)p.len)
break
.done:
break
p.pos = p.pos_next
# more jump optimizations: shrink the jumps whose target is near enough to the 1 or 2
# byte forms, then patch every jump offset.
func shorten_jumps(p: ResolveLabelsState*):
let s = p.s
var patch_offsets = 0
for i in 0..<s.jump_count:
let jp = fd_jump_slot(s, i)
var delta: i32 = 3
let op = jp.op
if (op == (i32)Op.goto16 or op == (i32)Op.if_false or op == (i32)Op.if_true or op == (i32)Op.goto_):
if op == (i32)Op.goto16:
delta = 1
let pos = jp.pos
let diff = fd_label(s, jp.label).addr - pos
let buf = dbuf_bytes_or_empty(&p.bc_out)
var shrink = false
if diff >= -128 and diff <= 127 + delta:
# put_u8(bc_out.buf + pos, diff);
jp.size = 1
if op == (i32)Op.goto16:
jp.op = (i32)Op.goto8
else:
jp.op = (i32)Op.if_false8 + (op - (i32)Op.if_false)
buf[pos - 1] = (u8)jp.op
shrink = true
elif diff == (i32)(i16)diff and op == (i32)Op.goto_:
# put_u16(bc_out.buf + pos, diff);
jp.size = 2
delta = 2
jp.op = (i32)Op.goto16
buf[pos - 1] = (u8)jp.op
shrink = true
if shrink:
# XXX: should reduce complexity, using 2 finger copy scheme
let count = (i32)p.bc_out.size - pos - jp.size - delta
_ = cutils.memmove(buf + pos + jp.size, buf + pos + jp.size + delta,
(usize)count)
p.bc_out.size -= (usize)delta
patch_offsets += 1
for j in 0..<s.label_count:
let ls = fd_label(s, j)
if ls.addr > pos:
ls.addr -= delta
for j in (i + 1)..<s.jump_count:
let jp1 = fd_jump_slot(s, j)
if jp1.pos > pos:
jp1.pos -= delta
for j in 0..<s.line_number_count:
let slots = s.line_number_slots else trap("shorten_jumps: no line numbers")
if slots[j].pc > (u32)pos:
slots[j].pc -= (u32)delta
if patch_offsets != 0:
let buf = dbuf_bytes_or_empty(&p.bc_out)
for j in 0..<s.jump_count:
let jp1 = fd_jump_slot(s, j)
let diff1 = fd_label(s, jp1.label).addr - jp1.pos
match jp1.size:
1:
cutils.put_u8(buf + jp1.pos, (u8)diff1)
2:
cutils.put_u16(buf + jp1.pos, (u16)diff1)
4:
cutils.put_u32(buf + jp1.pos, (u32)diff1)
_:
_ = 0
# peephole optimizations and resolve goto/labels
func resolve_labels(ctx: Context*, s: FunctionDef*) -> !:
let bc_buf = dbuf_bytes_or_empty(&s.byte_code)
let bc_len = (i32)s.byte_code.size
var state = ResolveLabelsState(ctx = ctx, s = s, bc_buf = bc_buf, bc_len = bc_len,
cc = CodeContext(bc_buf = bc_buf, bc_len = bc_len),
line_num = (i32)s.source_pos)
let p = &state
js_dbuf_bytecode_init(ctx, &p.bc_out)
if s.jump_size != 0:
let slots = try js_mallocz(s.ctx, memory.size_of(JumpSlot) * (usize)s.jump_size)
s.jump_slots = (JumpSlot*)slots
# XXX: Should skip this phase if not generating SHORT_OPCODES
if s.line_number_size != 0 and not s.strip_debug:
let slots = try js_mallocz(s.ctx, memory.size_of(LineNumberSlot) * (usize)s.line_number_size)
s.line_number_slots = (LineNumberSlot*)slots
s.line_number_last = (i32)s.source_pos
s.line_number_last_pc = 0
emit_function_prologue(s, &p.bc_out)
try resolve_labels_code(p)
# check that there were no missing labels
for i in 0..<s.label_count:
assert(fd_label(s, i).first_reloc == none)
shorten_jumps(p)
if let jump_slots = s.jump_slots:
js_free(ctx, jump_slots)
s.jump_slots = none
if let label_slots = s.label_slots:
js_free(ctx, label_slots)
s.label_slots = none
# XXX: should delay until copying to runtime bytecode function
compute_pc2line_info(s)
if let line_number_slots = s.line_number_slots:
js_free(ctx, line_number_slots)
s.line_number_slots = none
# set the new byte code
cutils.dbuf_free(&s.byte_code)
s.byte_code = p.bc_out
s.use_short_opcodes = true
if cutils.dbuf_error(&s.byte_code):
try js_throw_out_of_memory(ctx)