Sidetable.v3

// Copyright 2023 Wizard. All rights reserved.
// See LICENSE for details of Apache 2.0 license.

// Representation of the sidetable used for fast interpretation.
type Sidetable(entries: Array<int>) #unboxed {
	// Get an entry for a branch at the given sidetable position.
	def getBrEntry(stp: int) -> SidetableBrEntry {
		return SidetableBrEntry(
			entries[Sidetables.dpc_pos + stp],
			entries[Sidetables.valcount_pos + stp],
			entries[Sidetables.popcount_pos + stp],
			entries[Sidetables.dstp_pos + stp]);
	}
	// Get an entry for a rethrow at the given sidetable position.
	def getRethrowEntry(stp: int) -> SidetableRethrowEntry {
		return SidetableRethrowEntry(entries[stp + 0]);
	}
	// Get an entry for a catch at the given sidetable position.
	def getCatchEntry(stp: int) -> SidetableCatchEntry {
		var sidetable_pos = stp + entries[stp + Sidetables.dstp_pos];
		return SidetableCatchEntry(entries[stp + Sidetables.dpc_pos], entries[stp + Sidetables.valcount_pos], sidetable_pos);
	}
	// Get an entry for a resume at the given sidetable position.
	def getResumeEntry(stp: int) -> SidetableResumeEntry {
		return SidetableResumeEntry(entries[stp + Sidetables.nargs_pos], entries[stp + Sidetables.nhandlers_pos]);
	}
	def size() -> int {
		return entries.length * 4;
	}
}
// A sidetable entry associated with a branch.
type SidetableBrEntry(dpc: int, valcount: int, popcount: int, dstp: int) #unboxed;
// A sidetable entry associated with a (lexical) rethrow.
type SidetableRethrowEntry(catch_slot: int) #unboxed;
// A sidetable entry associated with a catch or suspension handler entry.
type SidetableCatchEntry(handler_pc: int, val_stack_top: int, sidetable_pos: int) #unboxed;
// A sidetable entry associated with a {resume} opcode.
type SidetableResumeEntry(nargs: int, nhandlers: int) #unboxed;


// Global constants associated with sidetables.
component Sidetables {
	def rethrow_entry_size = 4;
	def ex_entry_size = 4;
	def dpc_pos = 0;
	def valcount_pos = 1;
	def popcount_pos = 2;
	def dstp_pos = 3;
	def resume_nargs_pos = 0;
	def resume_hsize_pos = 1;
	def rhandler_tag_pos = 1;

	// resume
	def nargs_pos = 0;
	def nhandlers_pos = 1;

	def NO_SIDETABLE = Sidetable([]);

	def putBrEntry(v: Vector<int>, dpc: int, valcount: int, popcount: int, dstp: int) {
		v.put(dpc)      // delta pc
		 .put(valcount) // value count
		 .put(popcount) // pop count
		 .put(dstp);    // delta stp
	}
	def putCatchEntry(v: Vector<int>, handler_pc: int, val_stack_top: int, sidetable_pos: int) {
		v.put(handler_pc)
		 .put(val_stack_top)
		 .put(0)
		 .put(sidetable_pos);
	}
	def putResumeEntry(v: Vector<int>, nargs: int, nhandlers: int) {
		v.put(nargs)		// number of arguments to be pushed
		 .put(nhandlers)	// number of handlers (for sidetable lookup)
		 .put(0)			// reserved
		 .put(0);			// reserved
	}
}

// Implements an efficient mapping from program counter to sidetable position.
// The sidetable itself is stored in a {FuncDecl} without this mapping (to save space).
class SidetableMap(func: FuncDecl) {
	private def pairs = Vector<PcPair>.new();

	new() {
		var bi = BytecodeIterator.new().reset(func);
		var visitor = SidetableMapperVisitor.new(this, bi);
		while (bi.more()) {
			bi.dispatch(visitor);
			bi.next();
		}
	}

	// Get the sidetable entry position
	def [pc: int] -> int {
		// XXX: use a binary search
		var i = 0;
		var stp = 0;
		while (i < pairs.length) {
			var e = pairs[i];
			if (e.pc > pc) break;
			stp = e.stp;
			i++;
		}
		return stp;
	}
}

private type PcPair(pc: int, stp: int) #unboxed { }
private class SidetableMapperVisitor(map: SidetableMap, bi: BytecodeIterator) extends BytecodeVisitor {
	var cur: int;

	def entry(size: int) {
		cur += size / 4;
		map.pairs.put(PcPair(bi.pc + 1, cur));
	}

	def visit_IF(btc: BlockTypeCode)				{ entry(Sidetable_GotoEntry.size); }
	def visit_ELSE()						{ entry(Sidetable_GotoEntry.size); }
	def visit_RETHROW(label: u31)					{ entry(Sidetable_LexicalRethrowEntry.size); }
	def visit_BR(label: u31) 					{ entry(Sidetable_BrEntry.size); }
	def visit_BR_IF(label: u31) 					{ entry(Sidetable_BrEntry.size); }
	def visit_BR_TABLE(labels: Range<u31>)				{ entry((1 + labels.length) * Sidetable_BrEntry.size); }
	def visit_TRY_TABLE(btc: BlockTypeCode, catches: Range<BpCatchCode>)	{ entry(catches.length * Sidetable_CatchEntry.size); }
	def visit_BR_ON_NULL(label: u31)				{ entry(Sidetable_BrEntry.size); }
	def visit_BR_ON_NON_NULL(label: u31)				{ entry(Sidetable_BrEntry.size); }
	def visit_BR_ON_CAST(imm: BrOnCastImm)				{ entry(Sidetable_BrEntry.size); }
	def visit_BR_ON_CAST_FAIL(imm: BrOnCastImm)			{ entry(Sidetable_BrEntry.size); }
}

// Entries for branches (if, br, br_if, br_table, br_null, etc) contain information for control
// transfers, which includes:
//   - {pc_delta}	adjustment to program counter
//   - {stp_delta}	adjustment to sidetable pointer
//   - {valcount}	number of values to transfer
//   - {popcount}	number of values to pop (discard)
layout Sidetable_BrEntry {
	+0	pc_delta:	i32;
	+4	valcount:	i32;
	+8	popcount:	i32;
	+12	stp_delta:	i32;
	=16;
}

// Entries for control transfers that don't alter value stack (like a goto).
layout Sidetable_GotoEntry {
	+0	pc_delta:	i32;
	+12	stp_delta:	i32;
	=16;
}

// Entries for (legacy) lexical rethrow use a slot in the value stack that is determined by code
// validation and stored in the sidetable as the {catch_slot}.
layout Sidetable_LexicalRethrowEntry {
	+0	catch_slot:	i32;
	=16;
}

// Entries for catch store the handler pc, destination value stack top, and the sidetable pointer.
layout Sidetable_CatchEntry {
	+0	handler_pc:	u32;
	+4	val_stack_top:	u32;
	+8	stp:		u32;
	=16;
}

// Entries for storing the metadata of a resume instruction.
layout Sidetable_ResumeEntry {
	+0	n_binds:	i32;
	+4	n_handlers: i32;
	=16;
}

// Entries for suspension handlers to store the pc, the tag and the stp.
layout Sidetable_SuspendHandlerEntry {
	+0	handler_pc:	u32;
	+4  valcount:	u32;
	+8  popcount:		u32;
	+12	stp:		u32;
	=16;
}

// Entries for memory accesses store the access kind, which classifies how complex it is to decode
// the immediates and caches information from the associated memory declaration.
layout Sidetable_MemArg {
	+0	mem_access_kind:	MemAccessKind;
	=1;
}

// Entries for struct field access include the kind of the field and its offset, which is cached
// from the module definition.
layout Sidetable_StructFieldAccess {
	+0	struct_access_kind:	StructAccessKind;
	+1	field_offset:		u24;
	=4; // XXX: cache the immediate length as well?
}

// Memory accesses are classified by how complex it is to decode them and properties of the
// declared memory.
enum MemAccessKind {
	SIMPLE_32,		// memory 0, 32-bit index, offset=0, one byte LEB
	OFFSET_32,		// memory 0, 32-bit index, offset != 0
	MEM_INDEX_32,		// memory N, 32-bit index
	SIMPLE_64,		// memory 0, 64-bit index, offset=0, one byte LEB
	OFFSET_64,		// memory 0, 64-bit index, offset != 0
	MEM_INDEX_64,		// memory N, 64-bit index
	BOUNDS_CHECK_32		// memory N, 32-bit index, offset != 0, custom page size
}

// Struct field access kinds determine the size and tag of the data stored in the field.
enum StructAccessKind {
	COMPLEX, I8, U8, I16, U16, I32, U32, I64, F32, F64, V128, REF
}