path: root/sparse-llvm.c

/*
 * Example usage:
 *	./sparse-llvm hello.c | llc | as -o hello.o
 */

#include <llvm-c/Core.h>
#include <llvm-c/BitWriter.h>
#include <llvm-c/Analysis.h>
#include <llvm-c/Target.h>

#include <stdbool.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>

#include "symbol.h"
#include "expression.h"
#include "linearize.h"
#include "flow.h"

struct function {
	LLVMBuilderRef			builder;
	LLVMValueRef			fn;
	LLVMModuleRef			module;
};

static LLVMTypeRef symbol_type(struct symbol *sym);

static LLVMTypeRef func_return_type(struct symbol *sym)
{
	return symbol_type(sym->ctype.base_type);
}

static LLVMTypeRef sym_func_type(struct symbol *sym)
{
	int n_arg = symbol_list_size(sym->arguments);
	LLVMTypeRef *arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
	LLVMTypeRef ret_type = func_return_type(sym);
	struct symbol *arg;
	int idx = 0;

	FOR_EACH_PTR(sym->arguments, arg) {
		struct symbol *arg_sym = arg->ctype.base_type;

		arg_type[idx++] = symbol_type(arg_sym);
	} END_FOR_EACH_PTR(arg);

	return LLVMFunctionType(ret_type, arg_type, n_arg, sym->variadic);
}

static LLVMTypeRef sym_array_type(struct symbol *sym)
{
	LLVMTypeRef elem_type;
	struct symbol *base_type;

	base_type = sym->ctype.base_type;
	/* empty struct is undefined [6.7.2.1(8)] */
	assert(base_type->bit_size > 0);

	elem_type = symbol_type(base_type);
	if (!elem_type)
		return NULL;

	return LLVMArrayType(elem_type, sym->bit_size / base_type->bit_size);
}

#define MAX_STRUCT_MEMBERS 64

static LLVMTypeRef sym_struct_type(struct symbol *sym)
{
	LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS];
	struct symbol *member;
	char buffer[256];
	LLVMTypeRef ret;
	unsigned nr = 0;

	snprintf(buffer, sizeof(buffer), "struct.%s", sym->ident ? sym->ident->name : "anno");
	ret = LLVMStructCreateNamed(LLVMGetGlobalContext(), buffer);
	/* set ->aux to avoid recursion */
	sym->aux = ret;

	FOR_EACH_PTR(sym->symbol_list, member) {
		LLVMTypeRef member_type;

		assert(nr < MAX_STRUCT_MEMBERS);

		member_type = symbol_type(member);

		elem_types[nr++] = member_type; 
	} END_FOR_EACH_PTR(member);

	LLVMStructSetBody(ret, elem_types, nr, 0 /* packed? */); 
	return ret;
}

static LLVMTypeRef sym_union_type(struct symbol *sym)
{
	LLVMTypeRef elements;
	unsigned union_size;

	/*
	 * There's no union support in the LLVM API so we treat unions as
	 * opaque structs. The downside is that we lose type information on the
	 * members but as LLVM doesn't care, neither do we.
	 */
	union_size = sym->bit_size / 8;

	elements = LLVMArrayType(LLVMInt8Type(), union_size);

	return LLVMStructType(&elements, 1, 0 /* packed? */);
}

static LLVMTypeRef sym_ptr_type(struct symbol *sym)
{
	LLVMTypeRef type;

	/* 'void *' is treated like 'char *' */
	if (is_void_type(sym->ctype.base_type))
		type = LLVMInt8Type();
	else
		type = symbol_type(sym->ctype.base_type);

	return LLVMPointerType(type, 0);
}

static LLVMTypeRef sym_basetype_type(struct symbol *sym)
{
	LLVMTypeRef ret = NULL;

	if (is_float_type(sym)) {
		switch (sym->bit_size) {
		case 32:
			ret = LLVMFloatType();
			break;
		case 64:
			ret = LLVMDoubleType();
			break;
		case 80:
			ret = LLVMX86FP80Type();
			break;
		default:
			die("invalid bit size %d for type %d", sym->bit_size, sym->type);
			break;
		}
	} else {
		switch (sym->bit_size) {
		case -1:
			ret = LLVMVoidType();
			break;
		case 1:
			ret = LLVMInt1Type();
			break;
		case 8:
			ret = LLVMInt8Type();
			break;
		case 16:
			ret = LLVMInt16Type();
			break;
		case 32:
			ret = LLVMInt32Type();
			break;
		case 64:
			ret = LLVMInt64Type();
			break;
		default:
			die("invalid bit size %d for type %d", sym->bit_size, sym->type);
			break;
		}
	}

	return ret;
}

static LLVMTypeRef symbol_type(struct symbol *sym)
{
	LLVMTypeRef ret = NULL;

	/* don't cache the result for SYM_NODE */
	if (sym->type == SYM_NODE)
		return symbol_type(sym->ctype.base_type);

	if (sym->aux)
		return sym->aux;

	switch (sym->type) {
	case SYM_BITFIELD:
		ret = LLVMIntType(sym->bit_size);
		break;
	case SYM_RESTRICT:
	case SYM_ENUM:
		ret = symbol_type(sym->ctype.base_type);
		break;
	case SYM_BASETYPE:
		ret = sym_basetype_type(sym);
		break;
	case SYM_PTR:
		ret = sym_ptr_type(sym);
		break;
	case SYM_UNION:
		ret = sym_union_type(sym);
		break;
	case SYM_STRUCT:
		ret = sym_struct_type(sym);
		break;
	case SYM_ARRAY:
		ret = sym_array_type(sym);
		break;
	case SYM_FN:
		ret = sym_func_type(sym);
		break;
	default:
		assert(0);
	}

	/* cache the result */
	sym->aux = ret;
	return ret;
}

static LLVMTypeRef insn_symbol_type(struct instruction *insn)
{
	if (insn->type)
		return symbol_type(insn->type);

	switch (insn->size) {
		case 8:		return LLVMInt8Type();
		case 16:	return LLVMInt16Type();
		case 32:	return LLVMInt32Type();
		case 64:	return LLVMInt64Type();

		default:
			die("invalid bit size %d", insn->size);
			break;
	}

	return NULL;	/* not reached */
}

static LLVMLinkage data_linkage(struct symbol *sym)
{
	if (sym->ctype.modifiers & MOD_STATIC)
		return LLVMPrivateLinkage;

	return LLVMExternalLinkage;
}

static LLVMLinkage function_linkage(struct symbol *sym)
{
	if (sym->ctype.modifiers & MOD_STATIC)
		return LLVMInternalLinkage;

	return LLVMExternalLinkage;
}

#define MAX_PSEUDO_NAME 64

static const char *pseudo_name(pseudo_t pseudo, char *buf)
{
	switch (pseudo->type) {
	case PSEUDO_REG:
		snprintf(buf, MAX_PSEUDO_NAME, "R%d.", pseudo->nr);
		break;
	case PSEUDO_PHI:
		snprintf(buf, MAX_PSEUDO_NAME, "PHI%d.", pseudo->nr);
		break;
	case PSEUDO_SYM:
	case PSEUDO_VAL:
	case PSEUDO_ARG:
	case PSEUDO_VOID:
		buf[0] = '\0';
		break;
	case PSEUDO_UNDEF:
		assert(0);
		break;
	default:
		assert(0);
	}

	return buf;
}

static LLVMValueRef get_sym_value(LLVMModuleRef module, struct symbol *sym)
{
	const char *name = show_ident(sym->ident);
	LLVMTypeRef type = symbol_type(sym);
	LLVMValueRef result = NULL;
	struct expression *expr;

	assert(sym->bb_target == NULL);

	expr = sym->initializer;
	if (expr && !sym->ident) {
		switch (expr->type) {
		case EXPR_STRING: {
			const char *s = expr->string->data;
			LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) };
			LLVMValueRef data;

			data = LLVMAddGlobal(module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str");
			LLVMSetLinkage(data, LLVMPrivateLinkage);
			LLVMSetGlobalConstant(data, 1);
			LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true));

			result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
			return result;
		}
		default:
			break;
		}
	}

	if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) {
		result = LLVMGetNamedFunction(module, name);
		if (!result)
			result = LLVMAddFunction(module, name, type);
	} else {
		result = LLVMGetNamedGlobal(module, name);
		if (!result)
			result = LLVMAddGlobal(module, type, name);
	}

	return result;
}

static LLVMValueRef constant_value(unsigned long long val, LLVMTypeRef dtype)
{
	LLVMValueRef result;

	switch (LLVMGetTypeKind(dtype)) {
	case LLVMPointerTypeKind:
		if (val != 0) {	 // for example: ... = (void*) 0x123;
			LLVMTypeRef itype = LLVMIntType(bits_in_pointer);
			result = LLVMConstInt(itype, val, 1);
			result = LLVMConstIntToPtr(result, dtype);
		} else {
			result = LLVMConstPointerNull(dtype);
		}
		break;
	case LLVMIntegerTypeKind:
		result = LLVMConstInt(dtype, val, 1);
		break;
	case LLVMArrayTypeKind:
	case LLVMStructTypeKind:
		if (val != 0)
			return NULL;
		result = LLVMConstNull(dtype);
		break;
	default:
		return NULL;
	}
	return result;
}

static LLVMValueRef val_to_value(unsigned long long val, struct symbol *ctype)
{
	LLVMValueRef result;
	LLVMTypeRef dtype;

	assert(ctype);
	dtype = symbol_type(ctype);
	result = constant_value(val, dtype);
	if (result)
		return result;
	sparse_error(ctype->pos, "no value possible for %s", show_typename(ctype));
	return LLVMGetUndef(symbol_type(ctype));
}

static LLVMValueRef pseudo_to_value(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
{
	LLVMValueRef result = NULL;

	switch (pseudo->type) {
	case PSEUDO_REG:
		result = pseudo->priv;
		break;
	case PSEUDO_SYM:
		result = get_sym_value(fn->module, pseudo->sym);
		break;
	case PSEUDO_VAL:
		result = val_to_value(pseudo->value, ctype);
		break;
	case PSEUDO_ARG: {
		result = LLVMGetParam(fn->fn, pseudo->nr - 1);
		break;
	}
	case PSEUDO_PHI:
		result = pseudo->priv;
		break;
	case PSEUDO_VOID:
		result = NULL;
		break;
	case PSEUDO_UNDEF:
		result = LLVMGetUndef(symbol_type(ctype));
		break;
	default:
		assert(0);
	}

	return result;
}

static LLVMValueRef pseudo_to_rvalue(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
{
	LLVMValueRef val = pseudo_to_value(fn, ctype, pseudo);
	LLVMTypeRef dtype = symbol_type(ctype);
	char name[MAX_PSEUDO_NAME];

	pseudo_name(pseudo, name);
	return LLVMBuildBitCast(fn->builder, val, dtype, name);
}

static LLVMValueRef value_to_ivalue(struct function *fn, struct symbol *ctype, LLVMValueRef val)
{
	const char *name = LLVMGetValueName(val);
	LLVMTypeRef dtype = symbol_type(ctype);

	if (LLVMGetTypeKind(LLVMTypeOf(val)) == LLVMPointerTypeKind) {
		LLVMTypeRef dtype = LLVMIntType(bits_in_pointer);
		val = LLVMBuildPtrToInt(fn->builder, val, dtype, name);
	}
	if (ctype && is_int_type(ctype)) {
		val = LLVMBuildIntCast(fn->builder, val, dtype, name);
	}
	return val;
}

static LLVMValueRef value_to_pvalue(struct function *fn, struct symbol *ctype, LLVMValueRef val)
{
	const char *name = LLVMGetValueName(val);
	LLVMTypeRef dtype = symbol_type(ctype);

	assert(is_ptr_type(ctype));
	switch (LLVMGetTypeKind(LLVMTypeOf(val))) {
	case LLVMIntegerTypeKind:
		val = LLVMBuildIntToPtr(fn->builder, val, dtype, name);
		break;
	case LLVMPointerTypeKind:
		val = LLVMBuildBitCast(fn->builder, val, dtype, name);
		break;
	default:
		break;
	}
	return val;
}

static LLVMValueRef adjust_type(struct function *fn, struct symbol *ctype, LLVMValueRef val)
{
	if (is_int_type(ctype))
		return value_to_ivalue(fn, ctype, val);
	if (is_ptr_type(ctype))
		return value_to_pvalue(fn, ctype, val);
	return val;
}

/*
 * Get the LLVMValue corresponding to the pseudo
 * and force the type corresponding to ctype.
 */
static LLVMValueRef get_operand(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
{
	LLVMValueRef target = pseudo_to_value(fn, ctype, pseudo);
	return adjust_type(fn, ctype, target);
}

/*
 * Get the LLVMValue corresponding to the pseudo
 * and force the type corresponding to ctype but
 * map all pointers to intptr_t.
 */
static LLVMValueRef get_ioperand(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
{
	LLVMValueRef target = pseudo_to_value(fn, ctype, pseudo);
	return value_to_ivalue(fn, ctype, target);
}

static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValueRef off)
{
	LLVMTypeRef type = LLVMTypeOf(base);
	unsigned int as = LLVMGetPointerAddressSpace(type);
	LLVMTypeRef bytep = LLVMPointerType(LLVMInt8Type(), as);
	LLVMValueRef addr;
	const char *name = LLVMGetValueName(off);

	/* convert base to char* type */
	base = LLVMBuildPointerCast(builder, base, bytep, name);
	/* addr = base + off */
	addr = LLVMBuildInBoundsGEP(builder, base, &off, 1, name);
	/* convert back to the actual pointer type */
	addr = LLVMBuildPointerCast(builder, addr, type, name);
	return addr;
}

static LLVMRealPredicate translate_fop(int opcode)
{
	static const LLVMRealPredicate trans_tbl[] = {
		[OP_FCMP_ORD]	= LLVMRealORD,
		[OP_FCMP_OEQ]	= LLVMRealOEQ,
		[OP_FCMP_ONE]	= LLVMRealONE,
		[OP_FCMP_OLE]	= LLVMRealOLE,
		[OP_FCMP_OGE]	= LLVMRealOGE,
		[OP_FCMP_OLT]	= LLVMRealOLT,
		[OP_FCMP_OGT]	= LLVMRealOGT,
		[OP_FCMP_UEQ]	= LLVMRealUEQ,
		[OP_FCMP_UNE]	= LLVMRealUNE,
		[OP_FCMP_ULE]	= LLVMRealULE,
		[OP_FCMP_UGE]	= LLVMRealUGE,
		[OP_FCMP_ULT]	= LLVMRealULT,
		[OP_FCMP_UGT]	= LLVMRealUGT,
		[OP_FCMP_UNO]	= LLVMRealUNO,
	};

	return trans_tbl[opcode];
}

static LLVMIntPredicate translate_op(int opcode)
{
	static const LLVMIntPredicate trans_tbl[] = {
		[OP_SET_EQ]	= LLVMIntEQ,
		[OP_SET_NE]	= LLVMIntNE,
		[OP_SET_LE]	= LLVMIntSLE,
		[OP_SET_GE]	= LLVMIntSGE,
		[OP_SET_LT]	= LLVMIntSLT,
		[OP_SET_GT]	= LLVMIntSGT,
		[OP_SET_B]	= LLVMIntULT,
		[OP_SET_A]	= LLVMIntUGT,
		[OP_SET_BE]	= LLVMIntULE,
		[OP_SET_AE]	= LLVMIntUGE,
	};

	return trans_tbl[opcode];
}

static void output_op_binary(struct function *fn, struct instruction *insn)
{
	LLVMValueRef lhs, rhs, target;
	char target_name[64];

	lhs = get_ioperand(fn, insn->type, insn->src1);
	rhs = get_ioperand(fn, insn->type, insn->src2);

	pseudo_name(insn->target, target_name);

	switch (insn->opcode) {
	/* Binary */
	case OP_ADD:
		target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
		break;
	case OP_SUB:
		target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
		break;
	case OP_MUL:
		target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
		break;
	case OP_DIVU:
		target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name);
		break;
	case OP_DIVS:
		assert(!is_float_type(insn->type));
		target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
		break;
	case OP_MODU:
		assert(!is_float_type(insn->type));
		target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
		break;
	case OP_MODS:
		assert(!is_float_type(insn->type));
		target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
		break;
	case OP_SHL:
		assert(!is_float_type(insn->type));
		target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
		break;
	case OP_LSR:
		assert(!is_float_type(insn->type));
		target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
		break;
	case OP_ASR:
		assert(!is_float_type(insn->type));
		target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
		break;

	/* floating-point */
	case OP_FADD:
		target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name);
		break;
	case OP_FSUB:
		target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name);
		break;
	case OP_FMUL:
		target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name);
		break;
	case OP_FDIV:
		target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name);
		break;
	
	/* Logical */
	case OP_AND:
		assert(!is_float_type(insn->type));
		target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
		break;
	case OP_OR:
		assert(!is_float_type(insn->type));
		target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
		break;
	case OP_XOR:
		assert(!is_float_type(insn->type));
		target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
		break;
	default:
		assert(0);
		break;
	}

	target = adjust_type(fn, insn->type, target);
	insn->target->priv = target;
}

static void output_op_compare(struct function *fn, struct instruction *insn)
{
	LLVMValueRef lhs, rhs, target;
	char target_name[64];

	lhs = pseudo_to_value(fn, NULL, insn->src1);
	if (insn->src2->type == PSEUDO_VAL)
		rhs = constant_value(insn->src2->value, LLVMTypeOf(lhs));
	else
		rhs = pseudo_to_value(fn, NULL, insn->src2);
	if (!rhs)
		rhs = LLVMGetUndef(symbol_type(insn->type));

	pseudo_name(insn->target, target_name);

	LLVMTypeRef dst_type = insn_symbol_type(insn);

	switch  (LLVMGetTypeKind(LLVMTypeOf(lhs))) {
	case LLVMPointerTypeKind:
		lhs = value_to_pvalue(fn, &ptr_ctype, lhs);
		rhs = value_to_pvalue(fn, &ptr_ctype, rhs);
		/* fall through */

	case LLVMIntegerTypeKind: {
		LLVMIntPredicate op = translate_op(insn->opcode);

		if (LLVMGetTypeKind(LLVMTypeOf(rhs)) == LLVMPointerTypeKind) {
			LLVMTypeRef ltype = LLVMTypeOf(lhs);
			rhs = LLVMBuildPtrToInt(fn->builder, rhs, ltype, "");
		}
		target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name);
		break;
	}
	case LLVMHalfTypeKind:
	case LLVMFloatTypeKind:
	case LLVMDoubleTypeKind:
	case LLVMX86_FP80TypeKind:
	case LLVMFP128TypeKind:
	case LLVMPPC_FP128TypeKind: {
		LLVMRealPredicate op = translate_fop(insn->opcode);

		target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name);
		break;
	}
	default:
		assert(0);
	}

	target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);

	insn->target->priv = target;
}

static void output_op_ret(struct function *fn, struct instruction *insn)
{
	pseudo_t pseudo = insn->src;

	if (pseudo && pseudo != VOID) {
		LLVMValueRef result = get_operand(fn, insn->type, pseudo);
		LLVMBuildRet(fn->builder, result);
	} else
		LLVMBuildRetVoid(fn->builder);
}

static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *insn)
{
	LLVMTypeRef int_type, addr_type;
	LLVMValueRef src, off, addr;
	unsigned int as;

	/* int type large enough to hold a pointer */
	int_type = LLVMIntType(bits_in_pointer);
	off = LLVMConstInt(int_type, insn->offset, 0);

	/* convert src to the effective pointer type */
	src = pseudo_to_value(fn, insn->type, insn->src);
	as = LLVMGetPointerAddressSpace(LLVMTypeOf(src));
	addr_type = LLVMPointerType(insn_symbol_type(insn), as);
	src = LLVMBuildPointerCast(fn->builder, src, addr_type, LLVMGetValueName(src));

	/* addr = src + off */
	addr = calc_gep(fn->builder, src, off);
	return addr;
}


static void output_op_load(struct function *fn, struct instruction *insn)
{
	LLVMValueRef addr, target;
	char name[MAX_PSEUDO_NAME];

	addr = calc_memop_addr(fn, insn);

	/* perform load */
	pseudo_name(insn->target, name);
	target = LLVMBuildLoad(fn->builder, addr, name);

	insn->target->priv = target;
}

static void output_op_store(struct function *fn, struct instruction *insn)
{
	LLVMValueRef addr, target_in;

	addr = calc_memop_addr(fn, insn);

	target_in = pseudo_to_rvalue(fn, insn->type, insn->target);

	/* perform store */
	LLVMBuildStore(fn->builder, target_in, addr);
}

static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
{
	if (LLVMTypeOf(value) != LLVMInt1Type())
		value = LLVMBuildIsNotNull(fn->builder, value, LLVMGetValueName(value));

	return value;
}

static void output_op_cbr(struct function *fn, struct instruction *br)
{
	LLVMValueRef cond = bool_value(fn,
			pseudo_to_value(fn, NULL, br->cond));

	LLVMBuildCondBr(fn->builder, cond,
			br->bb_true->priv,
			br->bb_false->priv);
}

static void output_op_br(struct function *fn, struct instruction *br)
{
	LLVMBuildBr(fn->builder, br->bb_true->priv);
}

static void output_op_sel(struct function *fn, struct instruction *insn)
{
	LLVMValueRef target, src1, src2, src3;
	char name[MAX_PSEUDO_NAME];

	src1 = bool_value(fn, pseudo_to_value(fn, NULL, insn->src1));
	src2 = get_operand(fn, insn->type, insn->src2);
	src3 = get_operand(fn, insn->type, insn->src3);

	pseudo_name(insn->target, name);
	target = LLVMBuildSelect(fn->builder, src1, src2, src3, name);

	insn->target->priv = adjust_type(fn, insn->type, target);
}

static void output_op_switch(struct function *fn, struct instruction *insn)
{
	LLVMValueRef sw_val, target;
	struct basic_block *def = NULL;
	struct multijmp *jmp;
	int n_jmp = 0;

	FOR_EACH_PTR(insn->multijmp_list, jmp) {
		if (jmp->begin <= jmp->end) {
			n_jmp += (jmp->end - jmp->begin) + 1;
		} else					/* default case */
			def = jmp->target;
	} END_FOR_EACH_PTR(jmp);

	sw_val = get_ioperand(fn, insn->type, insn->cond);
	target = LLVMBuildSwitch(fn->builder, sw_val,
				 def ? def->priv : NULL, n_jmp);

	FOR_EACH_PTR(insn->multijmp_list, jmp) {
		long long val;

		for (val = jmp->begin; val <= jmp->end; val++) {
			LLVMValueRef Val = val_to_value(val, insn->type);
			LLVMAddCase(target, Val, jmp->target->priv);
		}
	} END_FOR_EACH_PTR(jmp);
}

static void output_op_call(struct function *fn, struct instruction *insn)
{
	LLVMValueRef target, func;
	struct symbol *ctype;
	int n_arg = 0, i;
	struct pseudo *arg;
	LLVMValueRef *args;
	char name[64];

	n_arg = pseudo_list_size(insn->arguments);
	args = calloc(n_arg, sizeof(LLVMValueRef));

	PREPARE_PTR_LIST(insn->fntypes, ctype);
	if (insn->func->type == PSEUDO_REG || insn->func->type == PSEUDO_PHI)
		func = get_operand(fn, ctype, insn->func);
	else
		func = pseudo_to_value(fn, ctype, insn->func);
	i = 0;
	FOR_EACH_PTR(insn->arguments, arg) {
		NEXT_PTR_LIST(ctype);
		args[i++] = pseudo_to_rvalue(fn, ctype, arg);
	} END_FOR_EACH_PTR(arg);
	FINISH_PTR_LIST(ctype);

	pseudo_name(insn->target, name);
	target = LLVMBuildCall(fn->builder, func, args, n_arg, name);

	insn->target->priv = target;
}

static void output_op_phisrc(struct function *fn, struct instruction *insn)
{
	LLVMValueRef v;
	struct instruction *phi;

	assert(insn->target->priv == NULL);

	/* target = src */
	v = get_operand(fn, insn->type, insn->phi_src);

	FOR_EACH_PTR(insn->phi_users, phi) {
		LLVMValueRef load, ptr;

		assert(phi->opcode == OP_PHI);
		/* phi must be load from alloca */
		load = phi->target->priv;
		assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
		ptr = LLVMGetOperand(load, 0);
		/* store v to alloca */
		LLVMBuildStore(fn->builder, v, ptr);
	} END_FOR_EACH_PTR(phi);
}

static void output_op_phi(struct function *fn, struct instruction *insn)
{
	LLVMValueRef load = insn->target->priv;

	/* forward load */
	assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
	/* forward load has no parent block */
	assert(!LLVMGetInstructionParent(load));
	/* finalize load in current block  */
	LLVMInsertIntoBuilder(fn->builder, load);
}

static void output_op_ptrcast(struct function *fn, struct instruction *insn)
{
	LLVMValueRef src, target;
	LLVMTypeRef dtype;
	struct symbol *otype = insn->orig_type;
	LLVMOpcode op;
	char target_name[64];

	src = get_operand(fn, otype, insn->src);
	pseudo_name(insn->target, target_name);

	dtype = symbol_type(insn->type);
	switch (insn->opcode) {
	case OP_UTPTR:
	case OP_SEXT:			// FIXME
		assert(is_int_type(otype));
		assert(is_ptr_type(insn->type));
		op = LLVMIntToPtr;
		break;
	case OP_PTRTU:
		assert(is_ptr_type(otype));
		assert(is_int_type(insn->type));
		op = LLVMPtrToInt;
		break;
	case OP_PTRCAST:
	case OP_ZEXT:			// FIXME
		assert(is_ptr_type(otype));
		assert(is_ptr_type(insn->type));
		op = LLVMBitCast;
		break;
	default:
		assert(0);
	}

	target = LLVMBuildCast(fn->builder, op, src, dtype, target_name);
	insn->target->priv = target;
}

static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
{
	LLVMValueRef src, target;
	LLVMTypeRef dtype;
	struct symbol *otype = insn->orig_type;
	char target_name[64];

	if (is_ptr_type(insn->type))	// cast to void* is OP_CAST ...
		return output_op_ptrcast(fn, insn);

	assert(is_int_type(insn->type));

	src = get_operand(fn, otype, insn->src);
	pseudo_name(insn->target, target_name);

	dtype = symbol_type(insn->type);
	if (is_ptr_type(otype)) {
		op = LLVMPtrToInt;
	} else if (is_float_type(otype)) {
		assert(op == LLVMFPToUI || op == LLVMFPToSI);
	} else if (is_int_type(otype)) {
		unsigned int width = otype->bit_size;
		if (insn->size < width)
			op = LLVMTrunc;
		else if (insn->size == width)
			op = LLVMBitCast;
	} else {
		assert(0);
	}

	target = LLVMBuildCast(fn->builder, op, src, dtype, target_name);
	insn->target->priv = target;
}

static void output_op_fpcast(struct function *fn, struct instruction *insn)
{
	LLVMTypeRef dtype = symbol_type(insn->type);
	LLVMValueRef src, target;
	struct symbol *otype = insn->orig_type;
	char name[64];

	assert(is_float_type(insn->type));

	pseudo_name(insn->target, name);
	src = get_operand(fn, otype, insn->src);
	switch (insn->opcode) {
	case OP_FCVTF:
		target = LLVMBuildFPCast(fn->builder, src, dtype, name);
		break;
	case OP_SCVTF:
		target = LLVMBuildSIToFP(fn->builder, src, dtype, name);
		break;
	case OP_UCVTF:
		target = LLVMBuildUIToFP(fn->builder, src, dtype, name);
		break;
	default:
		assert(0);
	}
	insn->target->priv = target;
}

static void output_op_setval(struct function *fn, struct instruction *insn)
{
	struct expression *val = insn->val;
	LLVMValueRef target;

	switch (val->type) {
	case EXPR_LABEL:
		target = LLVMBlockAddress(fn->fn, val->symbol->bb_target->priv);
		break;
	default:
		assert(0);
	}

	insn->target->priv = target;
}

static void output_op_setfval(struct function *fn, struct instruction *insn)
{
	LLVMTypeRef dtype = symbol_type(insn->type);
	LLVMValueRef target;

	target = LLVMConstReal(dtype, insn->fvalue);
	insn->target->priv = target;
}

static void output_insn(struct function *fn, struct instruction *insn)
{
	switch (insn->opcode) {
	case OP_RET:
		output_op_ret(fn, insn);
		break;
	case OP_BR:
		output_op_br(fn, insn);
		break;
	case OP_CBR:
		output_op_cbr(fn, insn);
		break;
	case OP_SYMADDR:
		assert(0);
		break;
	case OP_SETVAL:
		output_op_setval(fn, insn);
		break;
	case OP_SETFVAL:
		output_op_setfval(fn, insn);
		break;
	case OP_SWITCH:
		output_op_switch(fn, insn);
		break;
	case OP_COMPUTEDGOTO:
		assert(0);
		break;
	case OP_PHISOURCE:
		output_op_phisrc(fn, insn);
		break;
	case OP_PHI:
		output_op_phi(fn, insn);
		break;
	case OP_LOAD:
		output_op_load(fn, insn);
		break;
	case OP_STORE:
		output_op_store(fn, insn);
		break;
	case OP_INLINED_CALL:
		break;
	case OP_CALL:
		output_op_call(fn, insn);
		break;
	case OP_ZEXT:
		output_op_cast(fn, insn, LLVMZExt);
		break;
	case OP_SEXT:
		output_op_cast(fn, insn, LLVMSExt);
		break;
	case OP_TRUNC:
		output_op_cast(fn, insn, LLVMTrunc);
		break;
	case OP_FCVTU:
		output_op_cast(fn, insn, LLVMFPToUI);
		break;
	case OP_FCVTS:
		output_op_cast(fn, insn, LLVMFPToSI);
		break;
	case OP_UCVTF: case OP_SCVTF:
	case OP_FCVTF:
		output_op_fpcast(fn, insn);
		break;
	case OP_UTPTR:
	case OP_PTRTU:
	case OP_PTRCAST:
		output_op_ptrcast(fn, insn);
		break;
	case OP_BINARY ... OP_BINARY_END:
		output_op_binary(fn, insn);
		break;
	case OP_FPCMP ... OP_BINCMP_END:
		output_op_compare(fn, insn);
		break;
	case OP_SEL:
		output_op_sel(fn, insn);
		break;
	case OP_SLICE:
		assert(0);
		break;
	case OP_NOT: {
		LLVMValueRef src, target;
		char target_name[64];

		src = pseudo_to_value(fn, insn->type, insn->src);

		pseudo_name(insn->target, target_name);

		target = LLVMBuildNot(fn->builder, src, target_name);

		insn->target->priv = target;
		break;
	}
	case OP_FNEG:
	case OP_NEG: {
		LLVMValueRef src, target;
		char target_name[64];

		src = pseudo_to_value(fn, insn->type, insn->src);

		pseudo_name(insn->target, target_name);

		if (insn->opcode == OP_FNEG)
			target = LLVMBuildFNeg(fn->builder, src, target_name);
		else
			target = LLVMBuildNeg(fn->builder, src, target_name);

		insn->target->priv = target;
		break;
	}
	case OP_CONTEXT:
		assert(0);
		break;
	case OP_RANGE:
		assert(0);
		break;
	case OP_NOP:
		assert(0);
		break;
	case OP_DEATHNOTE:
		break;
	case OP_ASM:
		assert(0);
		break;
	case OP_COPY:
		assert(0);
		break;
	default:
		break;
	}
}

static void output_bb(struct function *fn, struct basic_block *bb)
{
	struct instruction *insn;

	FOR_EACH_PTR(bb->insns, insn) {
		if (!insn->bb)
			continue;

		output_insn(fn, insn);
	}
	END_FOR_EACH_PTR(insn);
}

#define MAX_ARGS	64

static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
{
	struct symbol *sym = ep->name;
	struct symbol *base_type = sym->ctype.base_type;
	struct function function = { .module = module };
	struct basic_block *bb;
	int nr_args = 0;
	int i;

	function.fn = get_sym_value(module, sym);
	LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
	LLVMSetLinkage(function.fn, function_linkage(sym));

	function.builder = LLVMCreateBuilder();

	/* give a name to each argument */
	nr_args = symbol_list_size(base_type->arguments);
	for (i = 0; i < nr_args; i++) {
		char name[MAX_PSEUDO_NAME];
		LLVMValueRef arg;

		arg = LLVMGetParam(function.fn, i);
		snprintf(name, sizeof(name), "ARG%d.", i+1);
		LLVMSetValueName(arg, name);
	}

	/* create the BBs */
	FOR_EACH_PTR(ep->bbs, bb) {
		static int nr_bb;
		LLVMBasicBlockRef bbr;
		char bbname[32];
		struct instruction *insn;

		sprintf(bbname, "L%d", nr_bb++);
		bbr = LLVMAppendBasicBlock(function.fn, bbname);

		bb->priv = bbr;

		/* allocate alloca for each phi */
		FOR_EACH_PTR(bb->insns, insn) {
			LLVMBasicBlockRef entrybbr;
			LLVMTypeRef phi_type;
			LLVMValueRef ptr;

			if (!insn->bb || insn->opcode != OP_PHI)
				continue;
			/* insert alloca into entry block */
			entrybbr = LLVMGetEntryBasicBlock(function.fn);
			LLVMPositionBuilderAtEnd(function.builder, entrybbr);
			phi_type = insn_symbol_type(insn);
			ptr = LLVMBuildAlloca(function.builder, phi_type, "");
			/* emit forward load for phi */
			LLVMClearInsertionPosition(function.builder);
			insn->target->priv = LLVMBuildLoad(function.builder, ptr, "phi");
		} END_FOR_EACH_PTR(insn);
	}
	END_FOR_EACH_PTR(bb);

	FOR_EACH_PTR(ep->bbs, bb) {
		LLVMPositionBuilderAtEnd(function.builder, bb->priv);

		output_bb(&function, bb);
	}
	END_FOR_EACH_PTR(bb);
}

static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
{
	struct expression *initializer = sym->initializer;
	LLVMValueRef initial_value;
	LLVMValueRef data;
	const char *name;

	if (initializer) {
		switch (initializer->type) {
		case EXPR_VALUE:
			initial_value = LLVMConstInt(symbol_type(sym), initializer->value, 1);
			break;
		case EXPR_FVALUE:
			initial_value = LLVMConstReal(symbol_type(sym), initializer->fvalue);
			break;
		case EXPR_SYMBOL: {
			struct symbol *sym = initializer->symbol;

			initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident));
			if (!initial_value)
				initial_value = output_data(module, sym);
			break;
		}
		case EXPR_STRING: {
			const char *s = initializer->string->data;

			initial_value = LLVMConstString(strdup(s), strlen(s) + 1, true);
			break;
		}
		default:
			warning(initializer->pos, "can't initialize type: %s", show_typename(sym));
			initial_value = NULL;
			break;
		}
	} else {
		LLVMTypeRef type = symbol_type(sym);

		initial_value = LLVMConstNull(type);
	}

	if (!initial_value)
		return NULL;

	name = sym->ident ? show_ident(sym->ident) : "" ;

	data = LLVMAddGlobal(module, LLVMTypeOf(initial_value), name);

	LLVMSetLinkage(data, data_linkage(sym));
	if (sym->ctype.modifiers & MOD_CONST)
		LLVMSetGlobalConstant(data, 1);
	if (sym->ctype.modifiers & MOD_TLS)
		LLVMSetThreadLocal(data, 1);
	if (sym->ctype.alignment)
		LLVMSetAlignment(data, sym->ctype.alignment);

	if (!(sym->ctype.modifiers & MOD_EXTERN))
		LLVMSetInitializer(data, initial_value);

	return data;
}

static int is_prototype(struct symbol *sym)
{
	if (sym->type == SYM_NODE)
		sym = sym->ctype.base_type;
	return sym && sym->type == SYM_FN && !sym->stmt;
}

static int compile(LLVMModuleRef module, struct symbol_list *list)
{
	struct symbol *sym;

	FOR_EACH_PTR(list, sym) {
		struct entrypoint *ep;
		expand_symbol(sym);

		if (is_prototype(sym)) {
			// this will do the LLVMAddFunction() we want
			get_sym_value(module, sym);
			continue;
		}

		ep = linearize_symbol(sym);
		if (ep)
			output_fn(module, ep);
		else
			output_data(module, sym);
	}
	END_FOR_EACH_PTR(sym);

	return 0;
}

#ifndef LLVM_DEFAULT_TARGET_TRIPLE
#define LLVM_DEFAULT_TARGET_TRIPLE LLVM_HOSTTRIPLE
#endif

#define X86_LINUX_LAYOUT \
	"e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
	"i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-" \
	"a0:0:64-f80:32:32-n8:16:32-S128"

#define X86_64_LINUX_LAYOUT \
	"e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
	"i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-" \
	"a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"

static void set_target(LLVMModuleRef module)
{
	char target[] = LLVM_DEFAULT_TARGET_TRIPLE;
	const char *arch, *vendor, *os, *env, *layout = NULL;
	char triple[256];

	arch = strtok(target, "-");
	vendor = strtok(NULL, "-");
	os = strtok(NULL, "-");
	env = strtok(NULL, "-");

	if (!os)
		return;
	if (!env)
		env = "unknown";

	if (!strcmp(arch, "x86_64") && !strcmp(os, "linux")) {
		if (arch_m64) {
			layout = X86_64_LINUX_LAYOUT;
		} else {
			arch = "i386";
			layout = X86_LINUX_LAYOUT;
		}
	}

	/* unsupported target */
	if (!layout)
		return;

	snprintf(triple, sizeof(triple), "%s-%s-%s-%s", arch, vendor, os, env);
	LLVMSetTarget(module, triple);
	LLVMSetDataLayout(module, layout);
}

int main(int argc, char **argv)
{
	struct string_list *filelist = NULL;
	struct symbol_list *symlist;
	LLVMModuleRef module;
	char *file;

	symlist = sparse_initialize(argc, argv, &filelist);

	module = LLVMModuleCreateWithName("sparse");
	set_target(module);

	compile(module, symlist);

	/* need ->phi_users */
	dbg_dead = 1;
	FOR_EACH_PTR(filelist, file) {
		symlist = sparse(file);
		if (die_if_error)
			return 1;
		compile(module, symlist);
	} END_FOR_EACH_PTR(file);

	LLVMVerifyModule(module, LLVMPrintMessageAction, NULL);

	LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);

	LLVMDisposeModule(module);

	report_stats();
	return 0;
}