insn-selector_32.brg

/*
 * Instruction selector Monoburg specification for IA-32.
 *
 * Copyright (C) 2006  Pekka Enberg
 *
 * This file is released under the GPL version 2. Please refer to the file
 * LICENSE for details.
 */

#include <jit/basic-block.h>
#include <jit/compilation-unit.h>
#include <jit/compiler.h>
#include <jit/emulate.h>
#include <jit/expression.h>
#include <jit/statement.h>
#include <jit/bc-offset-mapping.h>
#include <jit/exception.h>

#include <arch/instruction.h>
#include <arch/stack-frame.h>
#include <arch/thread.h>

#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <vm/class.h>

#include <../jamvm/lock.h>

#define MBCGEN_TYPE struct basic_block
#define MBCOST_DATA struct basic_block
#define MBTREE_TYPE struct tree_node
#define MBTREE_OP(t) tree_op(t)
#define MBTREE_LEFT(t) tree->kids[0]
#define MBTREE_RIGHT(t) tree->kids[1]
#define MBREG_TYPE struct var_info *

#define MBMAX_OPCODES STMT_LAST

#define MONOBURG_LOG 1
#define HAVE_ARRAY_ELEM_INIT 1

static void select_insn(struct basic_block *bb, struct tree_node *tree,
			struct insn *instruction);
static void select_exception_test(struct basic_block *bb,
				  struct tree_node *tree);

static unsigned char type_to_scale(enum vm_type vm_type)
{
	unsigned char scale;

	switch (vm_type) {
	case J_BYTE:
	case J_CHAR:
		scale = 0;
		break;
	case J_SHORT:
		scale = 1;
		break;
	case J_INT:
	case J_REFERENCE:
		scale = 2;
		break;
	default:
		assert(!"Not supported yet");
	}

	return scale;
}

static void method_args_cleanup(struct basic_block *bb, struct tree_node *tree,
				unsigned long args_count)
{
	struct var_info *stack_ptr;
	unsigned long args_size;

	stack_ptr = bb->b_parent->stack_ptr;
	args_size = args_count * sizeof(uint32_t);

	select_insn(bb, tree, imm_reg_insn(INSN_ADD_IMM_REG, args_size, stack_ptr));
}

struct _MBState;

static void __binop_reg_local(struct _MBState *, struct basic_block *, struct tree_node *, enum insn_type, struct var_info *, long);
static void binop_reg_local_high(struct _MBState *, struct basic_block *, struct tree_node *, enum insn_type);
static void binop_reg_local_low(struct _MBState *, struct basic_block *, struct tree_node *, enum insn_type);
static void binop_reg_value_high(struct _MBState *, struct basic_block *, struct tree_node *, enum insn_type);
static void binop_reg_value_low(struct _MBState *, struct basic_block *, struct tree_node *, enum insn_type);
static void shift_reg_local(struct _MBState *, struct basic_block *, struct tree_node *, enum insn_type);

static enum insn_type br_binop_to_insn_type(enum binary_operator binop)
{
	enum insn_type ret;

	switch (binop) {
	case OP_EQ:
		ret = INSN_JE_BRANCH;
		break;
	case OP_NE:
		ret = INSN_JNE_BRANCH;
		break;
	case OP_LT:
		ret = INSN_JL_BRANCH;
		break;
	case OP_GE:
		ret = INSN_JGE_BRANCH;
		break;
	case OP_GT:
		ret = INSN_JG_BRANCH;
		break;
	case OP_LE:
		ret = INSN_JLE_BRANCH;
		break;
	default:
		assert(!"not a branch operator");
	};
	return ret;
}

%%

%termprefix EXPR_ OP_ STMT_

%start stmt

reg:	EXPR_VALUE	0
{
	struct expression *expr;
	struct var_info *result;

	expr = to_expr(tree);

	result = get_var(s->b_parent);
	state->reg1 = result;

	select_insn(s, tree, imm_reg_insn(INSN_MOV_IMM_REG, expr->value & ~0UL, result));

	if (expr->vm_type == J_LONG) {
		result = get_var(s->b_parent);
		state->reg2 = result;
		select_insn(s, tree, imm_reg_insn(INSN_MOV_IMM_REG, expr->value >> 32, state->reg2));
	}
}

reg:	EXPR_LOCAL	1
{
	struct compilation_unit *cu = s->b_parent;
	struct expression *expr;
	struct stack_slot *slot;
	struct var_info *result;

	expr = to_expr(tree);
	slot = get_local_slot(cu->stack_frame, expr->local_index);

	result = get_var(s->b_parent);
	state->reg1 = result;

	select_insn(s, tree, memlocal_reg_insn(INSN_MOV_MEMLOCAL_REG, slot, result));

	if (expr->vm_type == J_LONG) {
		slot = get_local_slot(cu->stack_frame, expr->local_index + 1);

		result = get_var(s->b_parent);
		state->reg2 = result;

		select_insn(s, tree, memlocal_reg_insn(INSN_MOV_MEMLOCAL_REG, slot, result));
	}
}

reg:   EXPR_TEMPORARY
{
	struct expression *expr;

	expr = to_expr(tree);

	state->reg1 = expr->tmp_low;

	if (expr->vm_type == J_LONG) {
		state->reg2 = expr->tmp_high;
	}
}

reg:	OP_ADD(reg, EXPR_LOCAL) 1
{
	struct expression *expr;

	expr = to_expr(tree);

	binop_reg_local_low(state, s, tree, INSN_ADD_MEMBASE_REG);

	if (expr->vm_type == J_LONG) {
		binop_reg_local_high(state, s, tree, INSN_ADC_MEMBASE_REG);
	}
}

reg:	OP_ADD(reg, EXPR_VALUE) 1
{
	struct expression *expr;

	expr = to_expr(tree);

	binop_reg_value_low(state, s, tree, INSN_ADD_IMM_REG);

	if (expr->vm_type == J_LONG) {
		binop_reg_value_high(state, s, tree, INSN_ADC_IMM_REG);
	}
}

reg:	OP_ADD(reg, reg) 1
{
	struct expression *expr;

	expr = to_expr(tree);

	state->reg1 = state->left->reg1;
	binop_reg_reg_low(state, s, tree, INSN_ADD_REG_REG);

	if (expr->vm_type == J_LONG) {
		state->reg2 = state->left->reg2;
		binop_reg_reg_high(state, s, tree, INSN_ADC_REG_REG);
	}
}

reg:	OP_SUB(reg, EXPR_LOCAL) 1
{
	struct expression *expr;

	expr = to_expr(tree);

	binop_reg_local_low(state, s, tree, INSN_SUB_MEMBASE_REG);

	if (expr->vm_type == J_LONG) {
		binop_reg_local_high(state, s, tree, INSN_SBB_MEMBASE_REG);
	}
}

reg:	OP_SUB(reg, EXPR_VALUE) 1
{
	struct expression *expr;

	expr = to_expr(tree);

	binop_reg_value_low(state, s, tree, INSN_SUB_IMM_REG);

	if (expr->vm_type == J_LONG) {
		binop_reg_value_high(state, s, tree, INSN_SBB_IMM_REG);
	}
}

reg:	OP_SUB(reg, reg) 1
{
	struct expression *expr;

	expr = to_expr(tree);

	state->reg1 = state->left->reg1;
	binop_reg_reg_low(state, s, tree, INSN_SUB_REG_REG);

	if (expr->vm_type == J_LONG) {
		state->reg2 = state->left->reg2;
		binop_reg_reg_high(state, s, tree, INSN_SBB_REG_REG);
	}
}

reg:	OP_MUL(reg, EXPR_LOCAL) 1
{
	struct var_info *eax;

	eax = get_fixed_var(s->b_parent, REG_EAX);

	state->reg1 = eax;

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state->left->reg1, eax));
	__binop_reg_local(state, s, tree, INSN_MUL_MEMBASE_EAX, eax, 0);
}

reg: 	OP_MUL_64(reg, reg) 1
{
	struct var_info *eax, *edx, *tmp1;

	eax = get_fixed_var(s->b_parent, REG_EAX);
	edx = get_fixed_var(s->b_parent, REG_EDX);

	state->reg1 = eax;
	state->reg2 = get_var(s->b_parent);

	tmp1 = get_var(s->b_parent);
	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state->right->reg2, tmp1));
	select_insn(s, tree, reg_reg_insn(INSN_MUL_REG_REG, state->left->reg1, tmp1));
	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state->left->reg2, state->reg2));
	select_insn(s, tree, reg_reg_insn(INSN_MUL_REG_REG, state->right->reg1, state->reg2));
	select_insn(s, tree, reg_reg_insn(INSN_ADD_REG_REG, tmp1, state->reg2));

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state->right->reg1, eax));
	select_insn(s, tree, reg_reg_insn(INSN_MUL_REG_EAX, state->left->reg1, eax));

	select_insn(s, tree, reg_reg_insn(INSN_ADD_REG_REG, edx, state->reg2));
}

reg:	OP_DIV(reg, EXPR_LOCAL) 1
{
	div_reg_local(state, s, tree);
}

reg:	OP_DIV_64(reg, reg) 1
{
	emulate_op_64(state, s, tree, emulate_ldiv, J_LONG);
}

reg:	OP_REM(reg, EXPR_LOCAL) 1
{
	struct var_info *result, *remainder;

	div_reg_local(state, s, tree);

	result = get_fixed_var(s->b_parent, REG_EAX);
	remainder = get_fixed_var(s->b_parent, REG_EDX);

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, remainder, result));
}

reg:	OP_REM_64(reg, reg) 1
{
	emulate_op_64(state, s, tree, emulate_lrem, J_LONG);
}

reg:	OP_NEG(reg) 1
{
	struct expression *expr;
	struct var_info *result;

	expr = to_expr(tree);

	result = state->left->reg1;
	state->reg1 = result;

	select_insn(s, tree, reg_insn(INSN_NEG_REG, result));

	if (expr->vm_type == J_LONG) {
		result = state->left->reg2;
		state->reg2 = result;

		select_insn(s, tree, imm_reg_insn(INSN_ADC_IMM_REG, 0, result));
		select_insn(s, tree, reg_insn(INSN_NEG_REG, result));
	}
}

reg:	OP_SHL(reg, reg) 1
{
	struct var_info *ecx;

	ecx = get_fixed_var(s->b_parent, REG_ECX);

	state->reg1 = state->left->reg1;

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state->right->reg1, ecx));
	select_insn(s, tree, reg_reg_insn(INSN_SHL_REG_REG, ecx, state->left->reg1));
}

reg:	OP_SHL(reg, EXPR_LOCAL) 1
{
	shift_reg_local(state, s, tree, INSN_SHL_REG_REG);
}

reg:	OP_SHL_64(reg, reg) 1
{
	assert(!"SHL_64 todo");
}

reg:	OP_SHR(reg, EXPR_LOCAL) 1
{
	shift_reg_local(state, s, tree, INSN_SAR_REG_REG);
}

reg:	OP_SHR_64(reg, reg) 1
{
	assert(!"SHR_64 todo");
}

reg:	OP_USHR(reg, EXPR_LOCAL) 1
{
	shift_reg_local(state, s, tree, INSN_SHR_REG_REG);
}

reg:	OP_USHR_64(reg, reg) 1
{
	assert(!"USHR_64 todo");
}

reg:	OP_OR(reg, EXPR_LOCAL) 1
{
	struct expression *expr;

	expr = to_expr(tree);

	binop_reg_local_low(state, s, tree, INSN_OR_MEMBASE_REG);

	if (expr->vm_type == J_LONG) {
		binop_reg_local_high(state, s, tree, INSN_OR_MEMBASE_REG);
	}
}

reg:	OP_AND(reg, EXPR_LOCAL) 1
{
	struct expression *expr;

	expr = to_expr(tree);

	binop_reg_local_low(state, s, tree, INSN_AND_MEMBASE_REG);

	if (expr->vm_type == J_LONG) {
		binop_reg_local_high(state, s, tree, INSN_AND_MEMBASE_REG);
	}
}

reg:	OP_XOR(reg, EXPR_LOCAL) 1
{
	struct expression *expr;

	expr = to_expr(tree);

	binop_reg_local_low(state, s, tree, INSN_XOR_MEMBASE_REG);

	if (expr->vm_type == J_LONG) {
		binop_reg_local_high(state, s, tree, INSN_XOR_MEMBASE_REG);
	}
}

reg:	EXPR_INVOKE(arg) 1
{
	struct var_info *eax, *edx = NULL;
	struct compilation_unit *cu;
	struct methodblock *method;
	struct expression *expr;
	struct insn *call_insn;
	bool is_compiled;
	void *target;

	expr	= to_expr(tree);
	method	= expr->target_method;
	cu	= method->compilation_unit;

	if (cu == s->b_parent) {
		/*
		 * This is a recursive method invocation. Threfore, we are
		 * already holding cu->mutex here because we entered
		 * instruction selection through jit_magic_trampoline().
		 */
		is_compiled = false;
		target = method_trampoline_ptr(method);
	} else {
		pthread_mutex_lock(&cu->mutex);
		is_compiled = cu->is_compiled;

		if (is_compiled)
			target = method_native_ptr(method);
		else
			target = method_trampoline_ptr(method);

		pthread_mutex_unlock(&cu->mutex);
	}

	eax = get_fixed_var(s->b_parent, REG_EAX);
	state->reg1 = get_var(s->b_parent);

	if (get_method_return_type(method->type) == J_LONG) {
		edx = get_fixed_var(s->b_parent, REG_EDX);
		state->reg2 = get_var(s->b_parent);
	}

	call_insn = rel_insn(INSN_CALL_REL, (unsigned long) target);
	select_insn(s, tree, call_insn);

	if (!is_compiled) {
		struct fixup_site *fixup;

		fixup = alloc_fixup_site();
		fixup->cu = s->b_parent;
		fixup->relcall_insn = call_insn;

		trampoline_add_fixup_site(method->trampoline, fixup);
	}

	if (method->args_count)
		method_args_cleanup(s, tree, method->args_count);

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, eax, state->reg1));
	if (edx != NULL)
		select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, edx, state->reg2));
}

reg:	EXPR_INVOKEVIRTUAL(arg) 1
{
	struct var_info *eax, *edx = NULL;
	struct var_info *call_target;
	struct compilation_unit *cu;
	unsigned long method_offset;
	struct methodblock *method;
	struct var_info *stack_ptr;
	unsigned long args_count;
	struct expression *expr;

	expr	= to_expr(tree);
	method	= expr->target_method;
	cu	= method->compilation_unit;

	method_offset = expr_method_index(expr) * sizeof(void *);

	eax = get_fixed_var(s->b_parent, REG_EAX);
	state->reg1 = get_var(s->b_parent);

	if (get_method_return_type(method->type) == J_LONG) {
		edx = get_fixed_var(s->b_parent, REG_EDX);
		state->reg2 = get_var(s->b_parent);
	}

	call_target = get_var(s->b_parent);
	stack_ptr = get_fixed_var(s->b_parent, REG_ESP);

	/* object reference */
	select_insn(s, tree, membase_reg_insn(INSN_MOV_MEMBASE_REG, stack_ptr, 0, call_target));

	/* object class */
	select_insn(s, tree, membase_reg_insn(INSN_MOV_MEMBASE_REG, call_target, offsetof(struct object, class), call_target));

	/* vtable */
	select_insn(s, tree, membase_reg_insn(INSN_MOV_MEMBASE_REG, call_target, sizeof(struct object), call_target));

	/* native ptr */
	select_insn(s, tree, imm_reg_insn(INSN_ADD_IMM_REG, method_offset, call_target));

	/* invoke method */
	select_insn(s, tree, reg_insn(INSN_CALL_REG, call_target));

	args_count = nr_args(to_expr(expr->args_list));
	if (args_count)
		method_args_cleanup(s, tree, args_count);

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, eax, state->reg1));
	if (edx != NULL)
		select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, edx, state->reg2));
}

reg:	OP_CMP(reg, reg) 1
{
	emulate_op_64(state, s, tree, emulate_lcmp, J_INT);
}

reg:	OP_CMP(reg, EXPR_VALUE) 1
{
	struct expression *expr, *right;
	struct var_info *eax;

	expr = to_expr(tree);
	right = to_expr(expr->binary_right);

	state->reg1 = get_var(s->b_parent);
	eax = get_fixed_var(s->b_parent, REG_EAX);

	if (right->vm_type != J_LONG) {
		assert(!"OP_CMP implemented for J_LONG only");
	}

	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, (unsigned long) (right->value >> 32)));
	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, (unsigned long) (right->value & ~0UL)));

	select_insn(s, tree, reg_insn(INSN_PUSH_REG, state->left->reg2));
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, state->left->reg1));

	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) emulate_lcmp));
	method_args_cleanup(s, tree, 4);
	select_exception_test(s, tree);

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, eax, state->reg1));
}

reg:	OP_EQ(reg, EXPR_LOCAL) 1
{
	binop_reg_local_low(state, s, tree, INSN_CMP_MEMBASE_REG);
}

reg:	OP_EQ(reg, EXPR_VALUE) 1
{
	binop_reg_value_low(state, s, tree, INSN_CMP_IMM_REG);
}

reg:	OP_EQ(reg, reg) 1
{
	binop_reg_reg_low(state, s, tree, INSN_CMP_REG_REG);
}

reg:	OP_NE(reg, EXPR_LOCAL) 1
{
	binop_reg_local_low(state, s, tree, INSN_CMP_MEMBASE_REG);
}

reg:	OP_NE(reg, EXPR_VALUE) 1
{
	binop_reg_value_low(state, s, tree, INSN_CMP_IMM_REG);
}

reg:	OP_NE(reg, reg) 1
{
	binop_reg_reg_low(state, s, tree, INSN_CMP_REG_REG);
}

reg:	OP_LT(reg, EXPR_LOCAL) 1
{
	binop_reg_local_low(state, s, tree, INSN_CMP_MEMBASE_REG);
}

reg:	OP_LT(reg, EXPR_VALUE) 1
{
	binop_reg_value_low(state, s, tree, INSN_CMP_IMM_REG);
}

reg:	OP_LT(reg, reg) 1
{
	binop_reg_reg_low(state, s, tree, INSN_CMP_REG_REG);
}

reg:	OP_GT(reg, EXPR_LOCAL) 1
{
	binop_reg_local_low(state, s, tree, INSN_CMP_MEMBASE_REG);
}

reg:	OP_GT(reg, EXPR_VALUE) 1
{
	binop_reg_value_low(state, s, tree, INSN_CMP_IMM_REG);
}

reg:	OP_GT(reg, reg) 1
{
	binop_reg_reg_low(state, s, tree, INSN_CMP_REG_REG);
}

reg:	OP_GE(reg, EXPR_LOCAL) 1
{
	binop_reg_local_low(state, s, tree, INSN_CMP_MEMBASE_REG);
}

reg:	OP_GE(reg, EXPR_VALUE) 1
{
	binop_reg_value_low(state, s, tree, INSN_CMP_IMM_REG);
}

reg:	OP_GE(reg, reg) 1
{
	binop_reg_reg_low(state, s, tree, INSN_CMP_REG_REG);
}

reg:	OP_LE(reg, EXPR_LOCAL) 1
{
	binop_reg_local_low(state, s, tree, INSN_CMP_MEMBASE_REG);
}

reg:	OP_LE(reg, EXPR_VALUE) 1
{
	binop_reg_value_low(state, s, tree, INSN_CMP_IMM_REG);
}

reg:	OP_LE(reg, reg) 2
{
	binop_reg_reg_low(state, s, tree, INSN_CMP_REG_REG);
}

reg:	EXPR_CLASS_FIELD 1
{
	struct expression *expr;
	struct var_info *field;
	long offset;

	expr   = to_expr(tree);
	offset = offsetof(struct fieldblock, static_value);

	state->reg1 = get_var(s->b_parent);
	field = get_var(s->b_parent);

	select_insn(s, tree, imm_reg_insn(INSN_MOV_IMM_REG, (unsigned long) expr->class_field, field));
	select_insn(s, tree, membase_reg_insn(INSN_MOV_MEMBASE_REG, field, offset, state->reg1));

	if (expr->vm_type == J_LONG) {
		state->reg2 = get_var(s->b_parent);

		select_insn(s, tree, membase_reg_insn(INSN_MOV_MEMBASE_REG, field, offset+4, state->reg2));
	}
}

reg:	EXPR_INSTANCE_FIELD(reg) 1
{
	struct var_info *base, *index;
	struct expression *expr;

	expr = to_expr(tree);

	base = state->left->reg1;
	index = get_var(s->b_parent);
	state->reg1 = get_var(s->b_parent);

	select_insn(s, tree, imm_reg_insn(INSN_ADD_IMM_REG, sizeof(struct object), base));
	select_insn(s, tree, imm_reg_insn(INSN_MOV_IMM_REG, expr->instance_field->offset, index));
	select_insn(s, tree, memindex_reg_insn(INSN_MOV_MEMINDEX_REG, base, index, 2, state->reg1));

	if (expr->vm_type == J_LONG) {
		state->reg2 = get_var(s->b_parent);

		select_insn(s, tree, imm_reg_insn(INSN_ADD_IMM_REG, 1, index));
		select_insn(s, tree, memindex_reg_insn(INSN_MOV_MEMINDEX_REG, base, index, 2, state->reg2));
	}
}

reg:	EXPR_NEW
{
	struct expression *expr;
	struct var_info *var;

	expr = to_expr(tree);

	var = get_fixed_var(s->b_parent, REG_EAX);
	state->reg1 = var;

	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, (unsigned long) expr->class));
	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) allocObject));
	method_args_cleanup(s, tree, 1);
	select_exception_test(s, tree);
}

reg:	EXPR_NEWARRAY(reg)
{
	struct var_info *var, *size;
	struct expression *expr;

	expr = to_expr(tree);

	var = get_fixed_var(s->b_parent, REG_EAX);
	state->reg1 = var;

	size = state->left->reg1;

	select_insn(s, tree, reg_insn(INSN_PUSH_REG, size));
	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, expr->array_type));
	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) allocTypeArray));

	method_args_cleanup(s, tree, 2);
	select_exception_test(s, tree);
}

reg:	EXPR_NULL_CHECK(reg)
{
	struct var_info *ref;

	ref = state->left->reg1;
	state->reg1 = ref;

	select_insn(s, tree, membase_reg_insn(INSN_TEST_MEMBASE_REG, ref, 0, ref));
}

reg:	EXPR_NULL_CHECK(EXPR_LOCAL)
{
	struct var_info *reg;
	struct stack_slot *slot;
	struct expression *expr;
	struct expression *local;

	reg = get_var(s->b_parent);
	state->reg1 = reg;

	expr = to_expr(tree);
	local = to_expr(expr->null_check_ref);

	slot = get_local_slot(s->b_parent->stack_frame, local->local_index);

	select_insn(s, tree, memlocal_reg_insn(INSN_MOV_MEMLOCAL_REG, slot, reg));
	select_insn(s, tree, membase_reg_insn(INSN_TEST_MEMBASE_REG, reg, 0, reg));
}

reg:	EXPR_MULTIANEWARRAY(arg)
{
	struct var_info *var;
	struct var_info *stack_ptr;
	unsigned int dimension;
	struct expression *expr;

	expr = to_expr(tree);

	var = get_fixed_var(s->b_parent, REG_EAX);
	state->reg1 = var;

	stack_ptr = get_fixed_var(s->b_parent, REG_ESP);

	dimension = nr_args(to_expr(expr->multianewarray_dimensions));

	select_insn(s, tree, reg_insn(INSN_PUSH_REG, stack_ptr));
	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, dimension));
	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, (unsigned long) expr->multianewarray_ref_type));
	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) allocMultiArray));

	method_args_cleanup(s, tree, dimension + 3);
	select_exception_test(s, tree);
}

reg:    EXPR_ANEWARRAY(reg)
{
        struct var_info *var, *size;
        struct expression *expr;

        expr = to_expr(tree);

        var = get_fixed_var(s->b_parent, REG_EAX);
        state->reg1 = var;

        size = state->left->reg1;

        select_insn(s, tree, imm_insn(INSN_PUSH_IMM, sizeof(struct object *)));
        select_insn(s, tree, reg_insn(INSN_PUSH_REG, size));
        select_insn(s, tree, imm_insn(INSN_PUSH_IMM, (unsigned long) expr->anewarray_ref_type));
        select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) allocArray));

        method_args_cleanup(s, tree, 3);
	select_exception_test(s, tree);
}

reg:    EXPR_ARRAYLENGTH(reg)
{
	struct var_info *arrayref, *arraylength;

	arrayref = state->left->reg1;

	arraylength = get_fixed_var(s->b_parent, REG_EAX);
	state->reg1 = arraylength;

	select_insn(s, tree, membase_reg_insn(INSN_MOV_MEMBASE_REG, arrayref, sizeof(struct object), arraylength));
}

reg:	EXPR_INSTANCEOF(reg)
{
	struct var_info *ref, *instanceof_result;
	struct expression *expr;

	expr = to_expr(tree);

	ref = state->left->reg1;

	instanceof_result = get_fixed_var(s->b_parent, REG_EAX);
	state->reg1 = instanceof_result;

	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, (unsigned long) expr->instanceof_class));
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, ref));
	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) is_object_instance_of));

	method_args_cleanup(s, tree, 2);
	select_exception_test(s, tree);
}

reg:	EXPR_CONVERSION(reg)
{
	struct expression *expr, *src;

	expr = to_expr(tree);
	src = to_expr(expr->from_expression);

	if (src->vm_type == J_INT && expr->vm_type == J_LONG) {
		state->reg1 = get_var(s->b_parent);
		state->reg2 = get_var(s->b_parent);

		select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state->left->reg1, state->reg1));
		select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state->left->reg1, state->reg2));
		select_insn(s, tree, imm_reg_insn(INSN_SAR_IMM_REG, 0x1f, state->reg2));
	} else if (src->vm_type == J_LONG && expr->vm_type == J_INT) {
		state->reg1 = state->left->reg1;
	} else {
		assert(!"conversion not implemented");
	}
}

arg:	EXPR_NO_ARGS
{
}

arg:	EXPR_ARG(EXPR_VALUE)
{
	struct expression *expr, *arg_expr;
	unsigned long long imm;

	expr = to_expr(tree);
	arg_expr = to_expr(expr->arg_expression);
	imm  = arg_expr->value;

	if (arg_expr->vm_type == J_LONG) {
		select_insn(s, tree, imm_insn(INSN_PUSH_IMM, imm >> 32));
	}

	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, imm & ~0UL));
}

arg:	EXPR_ARG(reg)
{
	struct var_info *src;
	struct expression *expr, *arg_expr;

	expr = to_expr(tree);
	arg_expr = to_expr(expr->arg_expression);

	if (arg_expr->vm_type == J_LONG) {
		src = state->left->reg2;
		select_insn(s, tree, reg_insn(INSN_PUSH_REG, src));
	}

	src = state->left->reg1;
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, src));
}

arg:	EXPR_ARGS_LIST(arg, arg)
{
}

reg:	EXPR_EXCEPTION_REF
{
	struct var_info *result;
	struct stack_slot *slot = s->b_parent->exception_spill_slot;

	result = get_var(s->b_parent);
	state->reg1 = result;

	select_insn(s, tree, memlocal_reg_insn(INSN_MOV_MEMLOCAL_REG, slot, result));
}

stmt:	STMT_RETURN(reg)
{
	struct expression *expr;
	struct var_info *src, *eax, *edx;

	expr = to_expr(tree);
	expr = to_expr(expr->unary_expression);

	eax = get_fixed_var(s->b_parent, REG_EAX);
	src = state->left->reg1;

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, src, eax));

	if (expr->vm_type == J_LONG) {
		edx = get_fixed_var(s->b_parent, REG_EDX);
		src = state->left->reg2;

		select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, src, edx));
	}

	select_insn(s, tree, branch_insn(INSN_JMP_BRANCH, s->b_parent->exit_bb));
}

stmt:	STMT_VOID_RETURN
{
	select_insn(s, tree, branch_insn(INSN_JMP_BRANCH, s->b_parent->exit_bb));
}

stmt:	STMT_EXPRESSION(reg)
{
}

stmt:	STMT_STORE(EXPR_CLASS_FIELD, reg)
{
	struct expression *store_dest;
	struct expression *store_src;
	unsigned long field_offset;
	struct var_info *offset;
	struct statement *stmt;
	struct var_info *src;

	stmt = to_stmt(tree);
	store_dest = to_expr(stmt->store_dest);
	store_src  = to_expr(stmt->store_src);

	field_offset = offsetof(struct fieldblock, static_value);
	src = state->right->reg1;

	offset = get_var(s->b_parent);

	select_insn(s, tree, imm_reg_insn(INSN_MOV_IMM_REG, (unsigned long) store_dest->class_field, offset));
	select_insn(s, tree, reg_membase_insn(INSN_MOV_REG_MEMBASE, src, offset, field_offset));

	if (store_src->vm_type == J_LONG) {
		src = state->right->reg2;
		select_insn(s, tree, imm_reg_insn(INSN_ADD_IMM_REG, 4, offset));
		select_insn(s, tree, reg_membase_insn(INSN_MOV_REG_MEMBASE, src, offset, field_offset));
	}
}

inst_field: EXPR_INSTANCE_FIELD(reg) 1
{
	struct var_info *src, *base, *index;
	struct expression *expr;

	expr = to_expr(tree);

	src = state->left->reg1;

	base = get_var(s->b_parent);
	state->reg1 = base;

	index = get_var(s->b_parent);
	state->reg2 = index;

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, src, base));
	select_insn(s, tree, imm_reg_insn(INSN_ADD_IMM_REG, sizeof(struct object), base));
	select_insn(s, tree, imm_reg_insn(INSN_MOV_IMM_REG, expr->instance_field->offset, index));
}

stmt:	STMT_STORE(inst_field, reg)
{
	struct var_info *src, *base, *index;
	struct expression *store_src;
	struct statement *stmt;

	stmt = to_stmt(tree);
	store_src = to_expr(stmt->store_src);
	src = state->right->reg1;

	base = state->left->reg1;
	index = state->left->reg2;

	select_insn(s, tree, reg_memindex_insn(INSN_MOV_REG_MEMINDEX, src, base, index, 2));

	if (store_src->vm_type == J_LONG) {
		src = state->right->reg2;
		select_insn(s, tree, imm_reg_insn(INSN_ADD_IMM_REG, 1, index));
		select_insn(s, tree, reg_memindex_insn(INSN_MOV_REG_MEMINDEX, src, base, index, 2));
	}
}

stmt:	STMT_STORE(EXPR_LOCAL, reg)
{
	struct compilation_unit *cu = s->b_parent;
	struct expression *local;
	struct stack_slot *slot;
	struct statement *stmt;
	struct var_info *src;

	src = state->right->reg1;

	stmt = to_stmt(tree);
	local = to_expr(stmt->store_dest);
	slot = get_local_slot(cu->stack_frame, local->local_index);

	select_insn(s, tree, reg_memlocal_insn(INSN_MOV_REG_MEMLOCAL, src, slot));

	if (local->vm_type == J_LONG) {
		src = state->right->reg2;

		slot = get_local_slot(cu->stack_frame, local->local_index+1);

		select_insn(s, tree, reg_memlocal_insn(INSN_MOV_REG_MEMLOCAL, src, slot));
	}
}

stmt:  STMT_STORE(EXPR_TEMPORARY, reg)
{
	struct expression *temp;
	struct var_info *src, *dest;
	struct statement *stmt;

	stmt = to_stmt(tree);

	temp = to_expr(stmt->store_dest);

	dest = temp->tmp_low;
	src = state->right->reg1;
	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, src, dest));

	if (temp->vm_type == J_LONG) {
		dest = temp->tmp_high;
		src = state->right->reg2;
		select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, src, dest));
	}
}

array_deref:	EXPR_ARRAY_DEREF(reg, reg) 2
{
	struct var_info *base, *index, *state_base, *state_index;
	struct expression *expr;

	expr = to_expr(tree);

	state_base = state->left->reg1;
	state_index = state->right->reg1;

	base = get_var(s->b_parent);
	state->reg1 = base;

	index = get_var(s->b_parent);
	state->reg2 = index;

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state_base, base));
	select_insn(s, tree, imm_reg_insn(INSN_ADD_IMM_REG, sizeof(struct object) + sizeof(uint32_t), base));
	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state_index, index));
}

stmt:	STMT_STORE(array_deref, reg)
{
	struct var_info *src, *base, *index;
	struct expression *dest_expr;
	struct statement *stmt;
	unsigned char scale;

	stmt = to_stmt(tree);
	dest_expr = to_expr(stmt->store_dest);

	scale = type_to_scale(dest_expr->vm_type);

	base = state->left->reg1;
	index = state->left->reg2;
	src = state->right->reg1;

	select_insn(s, tree, reg_memindex_insn(INSN_MOV_REG_MEMINDEX, src, base, index, scale));
}

stmt:	STMT_STORE(reg, array_deref)
{
	struct var_info *dest, *base, *index;
	struct expression *src_expr;
	struct statement *stmt;
	unsigned char scale;

	stmt = to_stmt(tree);
	src_expr = to_expr(stmt->store_src);

	scale = type_to_scale(src_expr->vm_type);

	base = state->right->reg1;
	index = state->right->reg2;
	dest = state->left->reg1;

	state->reg1 = dest;

	select_insn(s, tree, memindex_reg_insn(INSN_MOV_MEMINDEX_REG, base, index, scale, dest));
}

stmt:	STMT_ATHROW(reg)
{
	struct var_info *reg_eax = get_fixed_var(s->b_parent, REG_EAX);

	select_insn(s, tree, reg_insn(INSN_PUSH_REG, state->left->reg1));
	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, (unsigned long)s->b_parent));
	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long)throw_exception));
	method_args_cleanup(s, tree, 2);

	/* Jump where throw_exception() told us to jump */
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, reg_eax));
	select_insn(s, tree, insn(INSN_RET));
}

array_check:	EXPR_ARRAY_DEREF(reg, reg) 2
{
	struct var_info *base, *index, *state_base, *state_index;
	struct expression *expr;

	expr = to_expr(tree);

	state_base = state->left->reg1;
	state_index = state->right->reg1;

	base = get_var(s->b_parent);
	state->reg1 = base;

	index = get_var(s->b_parent);
	state->reg2 = index;

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state_base, base));
	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, state_index, index));
}

stmt:	STMT_ARRAY_CHECK(array_check)
{
	struct var_info *ref, *index;

	ref = state->left->reg1;
	index = state->left->reg2;

	select_insn(s, tree, reg_insn(INSN_PUSH_REG, index));
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, ref));
	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) check_array));

	method_args_cleanup(s, tree, 2);
	select_exception_test(s, tree);
}

stmt:	STMT_IF(reg)
{
	struct expression *if_conditional;
	enum insn_type insn_type;
	struct statement *stmt;

	stmt = to_stmt(tree);
	if_conditional = to_expr(stmt->if_conditional);
	insn_type = br_binop_to_insn_type(expr_bin_op(if_conditional));

	select_insn(s, tree, branch_insn(insn_type, stmt->if_true));
}

stmt:	STMT_GOTO
{
	struct statement *stmt;

	stmt = to_stmt(tree);

	select_insn(s, tree, branch_insn(INSN_JMP_BRANCH, stmt->goto_target));
}

stmt:	STMT_MONITOR_ENTER(reg)
{
	struct var_info *ref;
	ref = state->left->reg1;

	select_insn(s, tree, reg_insn(INSN_PUSH_REG, ref));
	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) objectLock));

	method_args_cleanup(s, tree, 1);
	select_exception_test(s, tree);
}

stmt:	STMT_MONITOR_EXIT(reg)
{
	struct var_info *ref;
	ref = state->left->reg1;

	select_insn(s, tree, reg_insn(INSN_PUSH_REG, ref));
	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) objectUnlock));

	method_args_cleanup(s, tree, 1);
	select_exception_test(s, tree);
}

stmt:	STMT_CHECKCAST(reg)
{
	struct statement *stmt;
	struct var_info *ref;

	ref = state->left->reg1;

	stmt = to_stmt(tree);

	select_insn(s, tree, imm_insn(INSN_PUSH_IMM, (unsigned long) stmt->checkcast_class));
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, ref));
	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long)check_cast));

	method_args_cleanup(s, tree, 2);
}

%%

static void select_insn(struct basic_block *bb, struct tree_node *tree,
			struct insn *instruction)
{
	instruction->bytecode_offset = tree_bytecode_offset(tree);
	bb_add_insn(bb, instruction);
}

/*
 * Selects code checking whether exception occured. When this is the case
 * exception will be thrown.
 *
 * NOTICE: exception test should be always selected _after_
 * method args cleanup or stack overflow may occure if exceptions
 * are thrown locally in a loop.
 */
static void select_exception_test(struct basic_block *bb,
				  struct tree_node *tree)
{
	unsigned long exception_guard_offset;
	struct var_info *reg;

	reg = get_var(bb->b_parent);

	exception_guard_offset = get_thread_local_offset(&exception_guard);

	select_insn(bb, tree, imm_reg_insn(INSN_MOV_THREAD_LOCAL_MEMDISP_REG, exception_guard_offset, reg));
	select_insn(bb, tree, membase_reg_insn(INSN_TEST_MEMBASE_REG, reg, 0, reg));
}

static void __binop_reg_local(struct _MBState *state, struct basic_block *bb,
			      struct tree_node *tree, enum insn_type insn_type,
			      struct var_info *result, long disp_offset)
{
	struct var_info *frame_ptr;
	struct expression *expr;
	long disp;

	expr = to_expr(tree);
	disp = frame_local_offset(bb->b_parent->method, to_expr(expr->binary_right));
	if (disp < 0)
		/* local stack slot, decreasing offset values */
		disp -= disp_offset;
	else
		/* method argument slot, increasing offset values */
		disp += disp_offset;

	frame_ptr = bb->b_parent->frame_ptr;

	select_insn(bb, tree, membase_reg_insn(insn_type, frame_ptr, disp, result));
}

static void binop_reg_local_low(struct _MBState *state, struct basic_block *bb,
			    struct tree_node *tree, enum insn_type insn_type)
{
	state->reg1 = state->left->reg1;

	__binop_reg_local(state, bb, tree, insn_type, state->left->reg1, 0);
}

static void binop_reg_local_high(struct _MBState *state, struct basic_block *bb,
			    struct tree_node *tree, enum insn_type insn_type)
{
	state->reg2 = state->left->reg2;

	__binop_reg_local(state, bb, tree, insn_type, state->left->reg2, 4);
}

static void binop_reg_value_low(struct _MBState *state, struct basic_block *bb,
				struct tree_node *tree, enum insn_type insn_type)
{
	struct expression *expr, *right;

	state->reg1 = state->left->reg1;

	expr = to_expr(tree);
	right = to_expr(expr->binary_right);

	select_insn(bb, tree, imm_reg_insn(insn_type, right->value & ~0UL, state->reg1));
}

static void binop_reg_value_high(struct _MBState *state, struct basic_block *bb,
				struct tree_node *tree, enum insn_type insn_type)
{
	struct expression *expr, *right;

	state->reg2 = state->left->reg2;

	expr = to_expr(tree);
	right = to_expr(expr->binary_right);

	select_insn(bb, tree, imm_reg_insn(insn_type, right->value >> 32, state->reg2));
}

static void binop_reg_reg_low(struct _MBState *state, struct basic_block *bb,
			  struct tree_node *tree, enum insn_type insn_type)
{
	struct var_info *src, *dst;

	src = state->right->reg1;
	dst = state->left->reg1;

	select_insn(bb, tree, reg_reg_insn(insn_type, src, dst));
}

static void binop_reg_reg_high(struct _MBState *state, struct basic_block *bb,
			  struct tree_node *tree, enum insn_type insn_type)
{
	struct var_info *src, *dst;

	src = state->right->reg2;
	dst = state->left->reg2;

	select_insn(bb, tree, reg_reg_insn(insn_type, src, dst));
}

static void shift_reg_local(struct _MBState *state, struct basic_block *bb,
			    struct tree_node *tree, enum insn_type insn_type)
{
	struct var_info *result, *frame_ptr, *shift_count;
	struct expression *expr;
	unsigned long disp;

	result = state->left->reg1;
	state->reg1 = result;

	expr = to_expr(tree);
	disp = frame_local_offset(bb->b_parent->method, to_expr(expr->binary_right));

	frame_ptr = bb->b_parent->frame_ptr;
	shift_count = get_fixed_var(bb->b_parent, REG_ECX);

	select_insn(bb, tree, membase_reg_insn(INSN_MOV_MEMBASE_REG, frame_ptr, disp, shift_count));
	select_insn(bb, tree, reg_reg_insn(insn_type, shift_count, result));
}

static void div_reg_local(struct _MBState *state, struct basic_block *bb,
			  struct tree_node *tree)
{
	struct var_info *edx, *result, *frame_ptr;
	struct expression *expr;
	unsigned long disp;

	expr = to_expr(tree);
	disp = frame_local_offset(bb->b_parent->method, to_expr(expr->binary_right));

	edx = get_fixed_var(bb->b_parent, REG_EDX);
	result = get_fixed_var(bb->b_parent, REG_EAX);
	state->reg1 = result;

	frame_ptr = bb->b_parent->frame_ptr;

	select_insn(bb, tree, reg_reg_insn(INSN_MOV_REG_REG, state->left->reg1, result));
	select_insn(bb, tree, reg_reg_insn(INSN_CLTD_REG_REG, result, edx));
	select_insn(bb, tree, membase_reg_insn(INSN_DIV_MEMBASE_REG, frame_ptr, disp, result));

}

static void
emulate_op_64(struct _MBState *state, struct basic_block *s,
	      struct tree_node *tree, void *func, enum vm_type return_type)
{
	struct var_info *eax, *edx = NULL;

	eax = get_fixed_var(s->b_parent, REG_EAX);
	state->reg1 = get_var(s->b_parent);

	if (return_type == J_LONG) {
		edx = get_fixed_var(s->b_parent, REG_EDX);
		state->reg2 = get_var(s->b_parent);
	}
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, state->right->reg2));
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, state->right->reg1));
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, state->left->reg2));
	select_insn(s, tree, reg_insn(INSN_PUSH_REG, state->left->reg1));

	select_insn(s, tree, rel_insn(INSN_CALL_REL, (unsigned long) func));
	method_args_cleanup(s, tree, 4);

	select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, eax, state->reg1));
	if (edx)
		select_insn(s, tree, reg_reg_insn(INSN_MOV_REG_REG, edx, state->reg2));
}

static void emit_code(struct basic_block *bb, MBState *state, int goal)
{
	MBState *kids[2];
	int ern;
	const guint16 *nts;
	int i;

	ern = mono_burg_rule(state, goal);
	nts = mono_burg_nts_data + mono_burg_nts[ern];
	mono_burg_kids(state, ern, kids);

	for (i = 0; nts[i]; i++)
		emit_code(bb, kids[i], nts[i]);

	mono_burg_emit(ern, state, state->tree, bb);
}

static void free_state(MBState *state)
{
	if (!state)
		return;

	free_state(state->left);
	free_state(state->right);

	g_free(state);
}

static void eh_add_insn(struct basic_block *bb, struct insn *insn)
{
	insn->bytecode_offset = bb->start;
	bb_add_insn(bb, insn);
}

static void select_eh_prologue(struct basic_block *bb)
{
	struct var_info *reg_eax;

	reg_eax = get_fixed_var(bb->b_parent, REG_EAX);

	/* Save exception from exception_holder to exception stack slot */
	eh_add_insn(bb, imm_reg_insn(INSN_MOV_THREAD_LOCAL_MEMDISP_REG,
		get_thread_local_offset(&exception_holder), reg_eax));
	eh_add_insn(bb,	reg_memlocal_insn(INSN_MOV_REG_MEMLOCAL, reg_eax,
		bb->b_parent->exception_spill_slot));

	/* Clear exception */
	eh_add_insn(bb, rel_insn(INSN_CALL_REL, (unsigned long)clear_exception));
}

static void insn_select(struct basic_block *bb)
{
	struct statement *stmt;
	MBState *state;

	mono_burg_init();

	if (bb->is_eh)
		select_eh_prologue(bb);

	for_each_stmt(stmt, &bb->stmt_list) {
		state = mono_burg_label(&stmt->node, bb);
		emit_code(bb, state, MB_NTERM_stmt);
		free_state(state);
	}
}

int select_instructions(struct compilation_unit *cu)
{
	struct basic_block *bb;
	int err = 0;

	cu->frame_ptr = get_fixed_var(cu, REG_EBP);
	if (!cu->frame_ptr) {
		err = -ENOMEM;
		goto out;
	}

	cu->stack_ptr = get_fixed_var(cu, REG_ESP);
	if (!cu->stack_ptr) {
		err = -ENOMEM;
		goto out;
	}

	/*
	 * Let the liveness analysis pass know about caller saved registers.
	 */
	get_fixed_var(cu, REG_EAX);
	get_fixed_var(cu, REG_ECX);
	get_fixed_var(cu, REG_EDX);

	for_each_basic_block(bb, &cu->bb_list)
		insn_select(bb);

  out:
	return err;
}