1/*
2 * Example usage:
3 *	./sparse-llvm hello.c | llc | as -o hello.o
4 */
5
6#include <llvm-c/Core.h>
7#include <llvm-c/BitWriter.h>
8#include <llvm-c/Analysis.h>
9#include <llvm-c/Target.h>
10
11#include <stdbool.h>
12#include <stdio.h>
13#include <unistd.h>
14#include <string.h>
15#include <assert.h>
16
17#include "symbol.h"
18#include "expression.h"
19#include "linearize.h"
20#include "flow.h"
21
22struct function {
23	LLVMBuilderRef			builder;
24	LLVMValueRef			fn;
25	LLVMModuleRef			module;
26};
27
28static LLVMTypeRef symbol_type(struct symbol *sym);
29
30static LLVMTypeRef func_return_type(struct symbol *sym)
31{
32	return symbol_type(sym->ctype.base_type);
33}
34
35static LLVMTypeRef sym_func_type(struct symbol *sym)
36{
37	int n_arg = symbol_list_size(sym->arguments);
38	LLVMTypeRef *arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
39	LLVMTypeRef ret_type = func_return_type(sym);
40	struct symbol *arg;
41	int idx = 0;
42
43	FOR_EACH_PTR(sym->arguments, arg) {
44		struct symbol *arg_sym = arg->ctype.base_type;
45
46		arg_type[idx++] = symbol_type(arg_sym);
47	} END_FOR_EACH_PTR(arg);
48
49	return LLVMFunctionType(ret_type, arg_type, n_arg, sym->variadic);
50}
51
52static LLVMTypeRef sym_array_type(struct symbol *sym)
53{
54	LLVMTypeRef elem_type;
55	struct symbol *base_type;
56
57	base_type = sym->ctype.base_type;
58	/* empty struct is undefined [6.7.2.1(8)] */
59	assert(base_type->bit_size > 0);
60
61	elem_type = symbol_type(base_type);
62	if (!elem_type)
63		return NULL;
64
65	return LLVMArrayType(elem_type, sym->bit_size / base_type->bit_size);
66}
67
68#define MAX_STRUCT_MEMBERS 64
69
70static LLVMTypeRef sym_struct_type(struct symbol *sym)
71{
72	LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS];
73	struct symbol *member;
74	char buffer[256];
75	LLVMTypeRef ret;
76	unsigned nr = 0;
77
78	snprintf(buffer, sizeof(buffer), "struct.%s", sym->ident ? sym->ident->name : "anno");
79	ret = LLVMStructCreateNamed(LLVMGetGlobalContext(), buffer);
80	/* set ->aux to avoid recursion */
81	sym->aux = ret;
82
83	FOR_EACH_PTR(sym->symbol_list, member) {
84		LLVMTypeRef member_type;
85
86		assert(nr < MAX_STRUCT_MEMBERS);
87
88		member_type = symbol_type(member);
89
90		elem_types[nr++] = member_type;
91	} END_FOR_EACH_PTR(member);
92
93	LLVMStructSetBody(ret, elem_types, nr, 0 /* packed? */);
94	return ret;
95}
96
97static LLVMTypeRef sym_union_type(struct symbol *sym)
98{
99	LLVMTypeRef elements;
100	unsigned union_size;
101
102	/*
103	 * There's no union support in the LLVM API so we treat unions as
104	 * opaque structs. The downside is that we lose type information on the
105	 * members but as LLVM doesn't care, neither do we.
106	 */
107	union_size = sym->bit_size / 8;
108
109	elements = LLVMArrayType(LLVMInt8Type(), union_size);
110
111	return LLVMStructType(&elements, 1, 0 /* packed? */);
112}
113
114static LLVMTypeRef sym_ptr_type(struct symbol *sym)
115{
116	LLVMTypeRef type;
117
118	/* 'void *' is treated like 'char *' */
119	if (is_void_type(sym->ctype.base_type))
120		type = LLVMInt8Type();
121	else
122		type = symbol_type(sym->ctype.base_type);
123
124	return LLVMPointerType(type, 0);
125}
126
127static LLVMTypeRef sym_basetype_type(struct symbol *sym)
128{
129	LLVMTypeRef ret = NULL;
130
131	if (is_float_type(sym)) {
132		switch (sym->bit_size) {
133		case 32:
134			ret = LLVMFloatType();
135			break;
136		case 64:
137			ret = LLVMDoubleType();
138			break;
139		case 80:
140			ret = LLVMX86FP80Type();
141			break;
142		default:
143			die("invalid bit size %d for type %d", sym->bit_size, sym->type);
144			break;
145		}
146	} else {
147		switch (sym->bit_size) {
148		case -1:
149			ret = LLVMVoidType();
150			break;
151		case 1:
152			ret = LLVMInt1Type();
153			break;
154		case 8:
155			ret = LLVMInt8Type();
156			break;
157		case 16:
158			ret = LLVMInt16Type();
159			break;
160		case 32:
161			ret = LLVMInt32Type();
162			break;
163		case 64:
164			ret = LLVMInt64Type();
165			break;
166		default:
167			die("invalid bit size %d for type %d", sym->bit_size, sym->type);
168			break;
169		}
170	}
171
172	return ret;
173}
174
175static LLVMTypeRef symbol_type(struct symbol *sym)
176{
177	LLVMTypeRef ret = NULL;
178
179	/* don't cache the result for SYM_NODE */
180	if (sym->type == SYM_NODE)
181		return symbol_type(sym->ctype.base_type);
182
183	if (sym->aux)
184		return sym->aux;
185
186	switch (sym->type) {
187	case SYM_BITFIELD:
188		ret = LLVMIntType(sym->bit_size);
189		break;
190	case SYM_RESTRICT:
191	case SYM_ENUM:
192		ret = symbol_type(sym->ctype.base_type);
193		break;
194	case SYM_BASETYPE:
195		ret = sym_basetype_type(sym);
196		break;
197	case SYM_PTR:
198		ret = sym_ptr_type(sym);
199		break;
200	case SYM_UNION:
201		ret = sym_union_type(sym);
202		break;
203	case SYM_STRUCT:
204		ret = sym_struct_type(sym);
205		break;
206	case SYM_ARRAY:
207		ret = sym_array_type(sym);
208		break;
209	case SYM_FN:
210		ret = sym_func_type(sym);
211		break;
212	default:
213		assert(0);
214	}
215
216	/* cache the result */
217	sym->aux = ret;
218	return ret;
219}
220
221static LLVMTypeRef insn_symbol_type(struct instruction *insn)
222{
223	if (insn->type)
224		return symbol_type(insn->type);
225
226	switch (insn->size) {
227		case 8:		return LLVMInt8Type();
228		case 16:	return LLVMInt16Type();
229		case 32:	return LLVMInt32Type();
230		case 64:	return LLVMInt64Type();
231
232		default:
233			die("invalid bit size %d", insn->size);
234			break;
235	}
236
237	return NULL;	/* not reached */
238}
239
240static LLVMLinkage data_linkage(struct symbol *sym)
241{
242	if (sym->ctype.modifiers & MOD_STATIC)
243		return LLVMPrivateLinkage;
244
245	return LLVMExternalLinkage;
246}
247
248static LLVMLinkage function_linkage(struct symbol *sym)
249{
250	if (sym->ctype.modifiers & MOD_STATIC)
251		return LLVMInternalLinkage;
252
253	return LLVMExternalLinkage;
254}
255
256#define MAX_PSEUDO_NAME 64
257
258static const char *pseudo_name(pseudo_t pseudo, char *buf)
259{
260	switch (pseudo->type) {
261	case PSEUDO_REG:
262		snprintf(buf, MAX_PSEUDO_NAME, "R%d.", pseudo->nr);
263		break;
264	case PSEUDO_PHI:
265		snprintf(buf, MAX_PSEUDO_NAME, "PHI%d.", pseudo->nr);
266		break;
267	case PSEUDO_SYM:
268	case PSEUDO_VAL:
269	case PSEUDO_ARG:
270	case PSEUDO_VOID:
271		buf[0] = '\0';
272		break;
273	case PSEUDO_UNDEF:
274		assert(0);
275		break;
276	default:
277		assert(0);
278	}
279
280	return buf;
281}
282
283static LLVMValueRef get_sym_value(LLVMModuleRef module, struct symbol *sym)
284{
285	const char *name = show_ident(sym->ident);
286	LLVMTypeRef type = symbol_type(sym);
287	LLVMValueRef result = NULL;
288	struct expression *expr;
289
290	assert(sym->bb_target == NULL);
291
292	expr = sym->initializer;
293	if (expr && !sym->ident) {
294		switch (expr->type) {
295		case EXPR_STRING: {
296			const char *s = expr->string->data;
297			LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) };
298			LLVMValueRef data;
299
300			data = LLVMAddGlobal(module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str");
301			LLVMSetLinkage(data, LLVMPrivateLinkage);
302			LLVMSetGlobalConstant(data, 1);
303			LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true));
304
305			result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
306			return result;
307		}
308		default:
309			break;
310		}
311	}
312
313	if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) {
314		result = LLVMGetNamedFunction(module, name);
315		if (!result)
316			result = LLVMAddFunction(module, name, type);
317	} else {
318		result = LLVMGetNamedGlobal(module, name);
319		if (!result)
320			result = LLVMAddGlobal(module, type, name);
321	}
322
323	return result;
324}
325
326static LLVMValueRef constant_value(unsigned long long val, LLVMTypeRef dtype)
327{
328	LLVMValueRef result;
329
330	switch (LLVMGetTypeKind(dtype)) {
331	case LLVMPointerTypeKind:
332		if (val != 0) {	 // for example: ... = (void*) 0x123;
333			LLVMTypeRef itype = LLVMIntType(bits_in_pointer);
334			result = LLVMConstInt(itype, val, 1);
335			result = LLVMConstIntToPtr(result, dtype);
336		} else {
337			result = LLVMConstPointerNull(dtype);
338		}
339		break;
340	case LLVMIntegerTypeKind:
341		result = LLVMConstInt(dtype, val, 1);
342		break;
343	case LLVMArrayTypeKind:
344	case LLVMStructTypeKind:
345		if (val != 0)
346			return NULL;
347		result = LLVMConstNull(dtype);
348		break;
349	default:
350		return NULL;
351	}
352	return result;
353}
354
355static LLVMValueRef val_to_value(unsigned long long val, struct symbol *ctype)
356{
357	LLVMValueRef result;
358	LLVMTypeRef dtype;
359
360	assert(ctype);
361	dtype = symbol_type(ctype);
362	result = constant_value(val, dtype);
363	if (result)
364		return result;
365	sparse_error(ctype->pos, "no value possible for %s", show_typename(ctype));
366	return LLVMGetUndef(symbol_type(ctype));
367}
368
369static LLVMValueRef pseudo_to_value(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
370{
371	LLVMValueRef result = NULL;
372
373	switch (pseudo->type) {
374	case PSEUDO_REG:
375		result = pseudo->priv;
376		break;
377	case PSEUDO_SYM:
378		result = get_sym_value(fn->module, pseudo->sym);
379		break;
380	case PSEUDO_VAL:
381		result = val_to_value(pseudo->value, ctype);
382		break;
383	case PSEUDO_ARG: {
384		result = LLVMGetParam(fn->fn, pseudo->nr - 1);
385		break;
386	}
387	case PSEUDO_PHI:
388		result = pseudo->priv;
389		break;
390	case PSEUDO_VOID:
391		result = NULL;
392		break;
393	case PSEUDO_UNDEF:
394		result = LLVMGetUndef(symbol_type(ctype));
395		break;
396	default:
397		assert(0);
398	}
399
400	return result;
401}
402
403static LLVMValueRef pseudo_to_rvalue(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
404{
405	LLVMValueRef val = pseudo_to_value(fn, ctype, pseudo);
406	LLVMTypeRef dtype = symbol_type(ctype);
407	char name[MAX_PSEUDO_NAME];
408
409	pseudo_name(pseudo, name);
410	return LLVMBuildBitCast(fn->builder, val, dtype, name);
411}
412
413static LLVMValueRef value_to_ivalue(struct function *fn, struct symbol *ctype, LLVMValueRef val)
414{
415	const char *name = LLVMGetValueName(val);
416	LLVMTypeRef dtype = symbol_type(ctype);
417
418	if (LLVMGetTypeKind(LLVMTypeOf(val)) == LLVMPointerTypeKind) {
419		LLVMTypeRef dtype = LLVMIntType(bits_in_pointer);
420		val = LLVMBuildPtrToInt(fn->builder, val, dtype, name);
421	}
422	if (ctype && is_int_type(ctype)) {
423		val = LLVMBuildIntCast(fn->builder, val, dtype, name);
424	}
425	return val;
426}
427
428static LLVMValueRef value_to_pvalue(struct function *fn, struct symbol *ctype, LLVMValueRef val)
429{
430	const char *name = LLVMGetValueName(val);
431	LLVMTypeRef dtype = symbol_type(ctype);
432
433	assert(is_ptr_type(ctype));
434	switch (LLVMGetTypeKind(LLVMTypeOf(val))) {
435	case LLVMIntegerTypeKind:
436		val = LLVMBuildIntToPtr(fn->builder, val, dtype, name);
437		break;
438	case LLVMPointerTypeKind:
439		val = LLVMBuildBitCast(fn->builder, val, dtype, name);
440		break;
441	default:
442		break;
443	}
444	return val;
445}
446
447static LLVMValueRef adjust_type(struct function *fn, struct symbol *ctype, LLVMValueRef val)
448{
449	if (is_int_type(ctype))
450		return value_to_ivalue(fn, ctype, val);
451	if (is_ptr_type(ctype))
452		return value_to_pvalue(fn, ctype, val);
453	return val;
454}
455
456/*
457 * Get the LLVMValue corresponding to the pseudo
458 * and force the type corresponding to ctype.
459 */
460static LLVMValueRef get_operand(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
461{
462	LLVMValueRef target = pseudo_to_value(fn, ctype, pseudo);
463	return adjust_type(fn, ctype, target);
464}
465
466/*
467 * Get the LLVMValue corresponding to the pseudo
468 * and force the type corresponding to ctype but
469 * map all pointers to intptr_t.
470 */
471static LLVMValueRef get_ioperand(struct function *fn, struct symbol *ctype, pseudo_t pseudo)
472{
473	LLVMValueRef target = pseudo_to_value(fn, ctype, pseudo);
474	return value_to_ivalue(fn, ctype, target);
475}
476
477static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValueRef off)
478{
479	LLVMTypeRef type = LLVMTypeOf(base);
480	unsigned int as = LLVMGetPointerAddressSpace(type);
481	LLVMTypeRef bytep = LLVMPointerType(LLVMInt8Type(), as);
482	LLVMValueRef addr;
483	const char *name = LLVMGetValueName(off);
484
485	/* convert base to char* type */
486	base = LLVMBuildPointerCast(builder, base, bytep, name);
487	/* addr = base + off */
488	addr = LLVMBuildInBoundsGEP(builder, base, &off, 1, name);
489	/* convert back to the actual pointer type */
490	addr = LLVMBuildPointerCast(builder, addr, type, name);
491	return addr;
492}
493
494static LLVMRealPredicate translate_fop(int opcode)
495{
496	static const LLVMRealPredicate trans_tbl[] = {
497		[OP_FCMP_ORD]	= LLVMRealORD,
498		[OP_FCMP_OEQ]	= LLVMRealOEQ,
499		[OP_FCMP_ONE]	= LLVMRealONE,
500		[OP_FCMP_OLE]	= LLVMRealOLE,
501		[OP_FCMP_OGE]	= LLVMRealOGE,
502		[OP_FCMP_OLT]	= LLVMRealOLT,
503		[OP_FCMP_OGT]	= LLVMRealOGT,
504		[OP_FCMP_UEQ]	= LLVMRealUEQ,
505		[OP_FCMP_UNE]	= LLVMRealUNE,
506		[OP_FCMP_ULE]	= LLVMRealULE,
507		[OP_FCMP_UGE]	= LLVMRealUGE,
508		[OP_FCMP_ULT]	= LLVMRealULT,
509		[OP_FCMP_UGT]	= LLVMRealUGT,
510		[OP_FCMP_UNO]	= LLVMRealUNO,
511	};
512
513	return trans_tbl[opcode];
514}
515
516static LLVMIntPredicate translate_op(int opcode)
517{
518	static const LLVMIntPredicate trans_tbl[] = {
519		[OP_SET_EQ]	= LLVMIntEQ,
520		[OP_SET_NE]	= LLVMIntNE,
521		[OP_SET_LE]	= LLVMIntSLE,
522		[OP_SET_GE]	= LLVMIntSGE,
523		[OP_SET_LT]	= LLVMIntSLT,
524		[OP_SET_GT]	= LLVMIntSGT,
525		[OP_SET_B]	= LLVMIntULT,
526		[OP_SET_A]	= LLVMIntUGT,
527		[OP_SET_BE]	= LLVMIntULE,
528		[OP_SET_AE]	= LLVMIntUGE,
529	};
530
531	return trans_tbl[opcode];
532}
533
534static void output_op_binary(struct function *fn, struct instruction *insn)
535{
536	LLVMValueRef lhs, rhs, target;
537	char target_name[64];
538
539	lhs = get_ioperand(fn, insn->type, insn->src1);
540	rhs = get_ioperand(fn, insn->type, insn->src2);
541
542	pseudo_name(insn->target, target_name);
543
544	switch (insn->opcode) {
545	/* Binary */
546	case OP_ADD:
547		target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
548		break;
549	case OP_SUB:
550		target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
551		break;
552	case OP_MUL:
553		target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
554		break;
555	case OP_DIVU:
556		target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name);
557		break;
558	case OP_DIVS:
559		assert(!is_float_type(insn->type));
560		target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
561		break;
562	case OP_MODU:
563		assert(!is_float_type(insn->type));
564		target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
565		break;
566	case OP_MODS:
567		assert(!is_float_type(insn->type));
568		target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
569		break;
570	case OP_SHL:
571		assert(!is_float_type(insn->type));
572		target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
573		break;
574	case OP_LSR:
575		assert(!is_float_type(insn->type));
576		target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
577		break;
578	case OP_ASR:
579		assert(!is_float_type(insn->type));
580		target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
581		break;
582
583	/* floating-point */
584	case OP_FADD:
585		target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name);
586		break;
587	case OP_FSUB:
588		target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name);
589		break;
590	case OP_FMUL:
591		target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name);
592		break;
593	case OP_FDIV:
594		target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name);
595		break;
596
597	/* Logical */
598	case OP_AND:
599		assert(!is_float_type(insn->type));
600		target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
601		break;
602	case OP_OR:
603		assert(!is_float_type(insn->type));
604		target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
605		break;
606	case OP_XOR:
607		assert(!is_float_type(insn->type));
608		target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
609		break;
610	default:
611		assert(0);
612		break;
613	}
614
615	target = adjust_type(fn, insn->type, target);
616	insn->target->priv = target;
617}
618
619static void output_op_compare(struct function *fn, struct instruction *insn)
620{
621	LLVMValueRef lhs, rhs, target;
622	char target_name[64];
623
624	lhs = pseudo_to_value(fn, NULL, insn->src1);
625	if (insn->src2->type == PSEUDO_VAL)
626		rhs = constant_value(insn->src2->value, LLVMTypeOf(lhs));
627	else
628		rhs = pseudo_to_value(fn, NULL, insn->src2);
629	if (!rhs)
630		rhs = LLVMGetUndef(symbol_type(insn->type));
631
632	pseudo_name(insn->target, target_name);
633
634	LLVMTypeRef dst_type = insn_symbol_type(insn);
635
636	switch  (LLVMGetTypeKind(LLVMTypeOf(lhs))) {
637	case LLVMPointerTypeKind:
638		lhs = value_to_pvalue(fn, &ptr_ctype, lhs);
639		rhs = value_to_pvalue(fn, &ptr_ctype, rhs);
640		/* fall through */
641
642	case LLVMIntegerTypeKind: {
643		LLVMIntPredicate op = translate_op(insn->opcode);
644
645		if (LLVMGetTypeKind(LLVMTypeOf(rhs)) == LLVMPointerTypeKind) {
646			LLVMTypeRef ltype = LLVMTypeOf(lhs);
647			rhs = LLVMBuildPtrToInt(fn->builder, rhs, ltype, "");
648		}
649		target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name);
650		break;
651	}
652	case LLVMHalfTypeKind:
653	case LLVMFloatTypeKind:
654	case LLVMDoubleTypeKind:
655	case LLVMX86_FP80TypeKind:
656	case LLVMFP128TypeKind:
657	case LLVMPPC_FP128TypeKind: {
658		LLVMRealPredicate op = translate_fop(insn->opcode);
659
660		target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name);
661		break;
662	}
663	default:
664		assert(0);
665	}
666
667	target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
668
669	insn->target->priv = target;
670}
671
672static void output_op_ret(struct function *fn, struct instruction *insn)
673{
674	pseudo_t pseudo = insn->src;
675
676	if (pseudo && pseudo != VOID) {
677		LLVMValueRef result = get_operand(fn, insn->type, pseudo);
678		LLVMBuildRet(fn->builder, result);
679	} else
680		LLVMBuildRetVoid(fn->builder);
681}
682
683static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *insn)
684{
685	LLVMTypeRef int_type, addr_type;
686	LLVMValueRef src, off, addr;
687	unsigned int as;
688
689	/* int type large enough to hold a pointer */
690	int_type = LLVMIntType(bits_in_pointer);
691	off = LLVMConstInt(int_type, insn->offset, 0);
692
693	/* convert src to the effective pointer type */
694	src = pseudo_to_value(fn, insn->type, insn->src);
695	as = LLVMGetPointerAddressSpace(LLVMTypeOf(src));
696	addr_type = LLVMPointerType(insn_symbol_type(insn), as);
697	src = LLVMBuildPointerCast(fn->builder, src, addr_type, LLVMGetValueName(src));
698
699	/* addr = src + off */
700	addr = calc_gep(fn->builder, src, off);
701	return addr;
702}
703
704
705static void output_op_load(struct function *fn, struct instruction *insn)
706{
707	LLVMValueRef addr, target;
708	char name[MAX_PSEUDO_NAME];
709
710	addr = calc_memop_addr(fn, insn);
711
712	/* perform load */
713	pseudo_name(insn->target, name);
714	target = LLVMBuildLoad(fn->builder, addr, name);
715
716	insn->target->priv = target;
717}
718
719static void output_op_store(struct function *fn, struct instruction *insn)
720{
721	LLVMValueRef addr, target_in;
722
723	addr = calc_memop_addr(fn, insn);
724
725	target_in = pseudo_to_rvalue(fn, insn->type, insn->target);
726
727	/* perform store */
728	LLVMBuildStore(fn->builder, target_in, addr);
729}
730
731static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
732{
733	if (LLVMTypeOf(value) != LLVMInt1Type())
734		value = LLVMBuildIsNotNull(fn->builder, value, LLVMGetValueName(value));
735
736	return value;
737}
738
739static void output_op_cbr(struct function *fn, struct instruction *br)
740{
741	LLVMValueRef cond = bool_value(fn,
742			pseudo_to_value(fn, NULL, br->cond));
743
744	LLVMBuildCondBr(fn->builder, cond,
745			br->bb_true->priv,
746			br->bb_false->priv);
747}
748
749static void output_op_br(struct function *fn, struct instruction *br)
750{
751	LLVMBuildBr(fn->builder, br->bb_true->priv);
752}
753
754static void output_op_sel(struct function *fn, struct instruction *insn)
755{
756	LLVMValueRef target, src1, src2, src3;
757	char name[MAX_PSEUDO_NAME];
758
759	src1 = bool_value(fn, pseudo_to_value(fn, NULL, insn->src1));
760	src2 = get_operand(fn, insn->type, insn->src2);
761	src3 = get_operand(fn, insn->type, insn->src3);
762
763	pseudo_name(insn->target, name);
764	target = LLVMBuildSelect(fn->builder, src1, src2, src3, name);
765
766	insn->target->priv = adjust_type(fn, insn->type, target);
767}
768
769static void output_op_switch(struct function *fn, struct instruction *insn)
770{
771	LLVMValueRef sw_val, target;
772	struct basic_block *def = NULL;
773	struct multijmp *jmp;
774	int n_jmp = 0;
775
776	FOR_EACH_PTR(insn->multijmp_list, jmp) {
777		if (jmp->begin <= jmp->end) {
778			n_jmp += (jmp->end - jmp->begin) + 1;
779		} else					/* default case */
780			def = jmp->target;
781	} END_FOR_EACH_PTR(jmp);
782
783	sw_val = get_ioperand(fn, insn->type, insn->cond);
784	target = LLVMBuildSwitch(fn->builder, sw_val,
785				 def ? def->priv : NULL, n_jmp);
786
787	FOR_EACH_PTR(insn->multijmp_list, jmp) {
788		long long val;
789
790		for (val = jmp->begin; val <= jmp->end; val++) {
791			LLVMValueRef Val = val_to_value(val, insn->type);
792			LLVMAddCase(target, Val, jmp->target->priv);
793		}
794	} END_FOR_EACH_PTR(jmp);
795}
796
797static void output_op_call(struct function *fn, struct instruction *insn)
798{
799	LLVMValueRef target, func;
800	struct symbol *ctype;
801	int n_arg = 0, i;
802	struct pseudo *arg;
803	LLVMValueRef *args;
804	char name[64];
805
806	n_arg = pseudo_list_size(insn->arguments);
807	args = calloc(n_arg, sizeof(LLVMValueRef));
808
809	PREPARE_PTR_LIST(insn->fntypes, ctype);
810	if (insn->func->type == PSEUDO_REG || insn->func->type == PSEUDO_PHI)
811		func = get_operand(fn, ctype, insn->func);
812	else
813		func = pseudo_to_value(fn, ctype, insn->func);
814	i = 0;
815	FOR_EACH_PTR(insn->arguments, arg) {
816		NEXT_PTR_LIST(ctype);
817		args[i++] = pseudo_to_rvalue(fn, ctype, arg);
818	} END_FOR_EACH_PTR(arg);
819	FINISH_PTR_LIST(ctype);
820
821	pseudo_name(insn->target, name);
822	target = LLVMBuildCall(fn->builder, func, args, n_arg, name);
823
824	insn->target->priv = target;
825}
826
827static void output_op_phisrc(struct function *fn, struct instruction *insn)
828{
829	insn->src->priv = get_operand(fn, insn->type, insn->src);
830}
831
832static void output_op_phi(struct function *fn, struct instruction *insn)
833{
834	LLVMTypeRef dst_type = insn_symbol_type(insn);
835
836	insn->target->priv = LLVMBuildPhi(fn->builder, dst_type, "");
837}
838
839static void output_op_ptrcast(struct function *fn, struct instruction *insn)
840{
841	LLVMValueRef src, target;
842	LLVMTypeRef dtype;
843	struct symbol *otype = insn->orig_type;
844	LLVMOpcode op;
845	char target_name[64];
846
847	src = get_operand(fn, otype, insn->src);
848	pseudo_name(insn->target, target_name);
849
850	dtype = symbol_type(insn->type);
851	switch (insn->opcode) {
852	case OP_UTPTR:
853	case OP_SEXT:			// FIXME
854		assert(is_int_type(otype));
855		assert(is_ptr_type(insn->type));
856		op = LLVMIntToPtr;
857		break;
858	case OP_PTRTU:
859		assert(is_ptr_type(otype));
860		assert(is_int_type(insn->type));
861		op = LLVMPtrToInt;
862		break;
863	case OP_PTRCAST:
864	case OP_ZEXT:			// FIXME
865		assert(is_ptr_type(otype));
866		assert(is_ptr_type(insn->type));
867		op = LLVMBitCast;
868		break;
869	default:
870		assert(0);
871	}
872
873	target = LLVMBuildCast(fn->builder, op, src, dtype, target_name);
874	insn->target->priv = target;
875}
876
877static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
878{
879	LLVMValueRef src, target;
880	LLVMTypeRef dtype;
881	struct symbol *otype = insn->orig_type;
882	char target_name[64];
883
884	if (is_ptr_type(insn->type))	// cast to void* is OP_CAST ...
885		return output_op_ptrcast(fn, insn);
886
887	assert(is_int_type(insn->type));
888
889	src = get_operand(fn, otype, insn->src);
890	pseudo_name(insn->target, target_name);
891
892	dtype = symbol_type(insn->type);
893	if (is_ptr_type(otype)) {
894		op = LLVMPtrToInt;
895	} else if (is_float_type(otype)) {
896		assert(op == LLVMFPToUI || op == LLVMFPToSI);
897	} else if (is_int_type(otype)) {
898		unsigned int width = otype->bit_size;
899		if (insn->size < width)
900			op = LLVMTrunc;
901		else if (insn->size == width)
902			op = LLVMBitCast;
903	} else {
904		assert(0);
905	}
906
907	target = LLVMBuildCast(fn->builder, op, src, dtype, target_name);
908	insn->target->priv = target;
909}
910
911static void output_op_fpcast(struct function *fn, struct instruction *insn)
912{
913	LLVMTypeRef dtype = symbol_type(insn->type);
914	LLVMValueRef src, target;
915	struct symbol *otype = insn->orig_type;
916	char name[64];
917
918	assert(is_float_type(insn->type));
919
920	pseudo_name(insn->target, name);
921	src = get_operand(fn, otype, insn->src);
922	switch (insn->opcode) {
923	case OP_FCVTF:
924		target = LLVMBuildFPCast(fn->builder, src, dtype, name);
925		break;
926	case OP_SCVTF:
927		target = LLVMBuildSIToFP(fn->builder, src, dtype, name);
928		break;
929	case OP_UCVTF:
930		target = LLVMBuildUIToFP(fn->builder, src, dtype, name);
931		break;
932	default:
933		assert(0);
934	}
935	insn->target->priv = target;
936}
937
938static void output_op_label(struct function *fn, struct instruction *insn)
939{
940	insn->target->priv = LLVMBlockAddress(fn->fn, insn->bb_true->priv);
941}
942
943static void output_op_setval(struct function *fn, struct instruction *insn)
944{
945	struct expression *val = insn->val;
946	LLVMValueRef target;
947
948	switch (val->type) {
949	case EXPR_LABEL:
950		target = LLVMBlockAddress(fn->fn, val->symbol->bb_target->priv);
951		break;
952	default:
953		assert(0);
954	}
955
956	insn->target->priv = target;
957}
958
959static void output_op_setfval(struct function *fn, struct instruction *insn)
960{
961	LLVMTypeRef dtype = symbol_type(insn->type);
962	LLVMValueRef target;
963
964	target = LLVMConstReal(dtype, insn->fvalue);
965	insn->target->priv = target;
966}
967
968static void output_insn(struct function *fn, struct instruction *insn)
969{
970	switch (insn->opcode) {
971	case OP_RET:
972		output_op_ret(fn, insn);
973		break;
974	case OP_BR:
975		output_op_br(fn, insn);
976		break;
977	case OP_CBR:
978		output_op_cbr(fn, insn);
979		break;
980	case OP_SYMADDR:
981		assert(0);
982		break;
983	case OP_LABEL:
984		output_op_label(fn, insn);
985		break;
986	case OP_SETVAL:
987		output_op_setval(fn, insn);
988		break;
989	case OP_SETFVAL:
990		output_op_setfval(fn, insn);
991		break;
992	case OP_SWITCH:
993		output_op_switch(fn, insn);
994		break;
995	case OP_COMPUTEDGOTO:
996		assert(0);
997		break;
998	case OP_PHISOURCE:
999		output_op_phisrc(fn, insn);
1000		break;
1001	case OP_PHI:
1002		output_op_phi(fn, insn);
1003		break;
1004	case OP_LOAD:
1005		output_op_load(fn, insn);
1006		break;
1007	case OP_STORE:
1008		output_op_store(fn, insn);
1009		break;
1010	case OP_INLINED_CALL:
1011		break;
1012	case OP_CALL:
1013		output_op_call(fn, insn);
1014		break;
1015	case OP_ZEXT:
1016		output_op_cast(fn, insn, LLVMZExt);
1017		break;
1018	case OP_SEXT:
1019		output_op_cast(fn, insn, LLVMSExt);
1020		break;
1021	case OP_TRUNC:
1022		output_op_cast(fn, insn, LLVMTrunc);
1023		break;
1024	case OP_FCVTU:
1025		output_op_cast(fn, insn, LLVMFPToUI);
1026		break;
1027	case OP_FCVTS:
1028		output_op_cast(fn, insn, LLVMFPToSI);
1029		break;
1030	case OP_UCVTF: case OP_SCVTF:
1031	case OP_FCVTF:
1032		output_op_fpcast(fn, insn);
1033		break;
1034	case OP_UTPTR:
1035	case OP_PTRTU:
1036	case OP_PTRCAST:
1037		output_op_ptrcast(fn, insn);
1038		break;
1039	case OP_BINARY ... OP_BINARY_END:
1040		output_op_binary(fn, insn);
1041		break;
1042	case OP_FPCMP ... OP_BINCMP_END:
1043		output_op_compare(fn, insn);
1044		break;
1045	case OP_SEL:
1046		output_op_sel(fn, insn);
1047		break;
1048	case OP_SLICE:
1049		assert(0);
1050		break;
1051	case OP_NOT: {
1052		LLVMValueRef src, target;
1053		char target_name[64];
1054
1055		src = pseudo_to_value(fn, insn->type, insn->src);
1056
1057		pseudo_name(insn->target, target_name);
1058
1059		target = LLVMBuildNot(fn->builder, src, target_name);
1060
1061		insn->target->priv = target;
1062		break;
1063	}
1064	case OP_FNEG:
1065	case OP_NEG: {
1066		LLVMValueRef src, target;
1067		char target_name[64];
1068
1069		src = pseudo_to_value(fn, insn->type, insn->src);
1070
1071		pseudo_name(insn->target, target_name);
1072
1073		if (insn->opcode == OP_FNEG)
1074			target = LLVMBuildFNeg(fn->builder, src, target_name);
1075		else
1076			target = LLVMBuildNeg(fn->builder, src, target_name);
1077
1078		insn->target->priv = target;
1079		break;
1080	}
1081	case OP_CONTEXT:
1082		assert(0);
1083		break;
1084	case OP_RANGE:
1085		assert(0);
1086		break;
1087	case OP_NOP:
1088		assert(0);
1089		break;
1090	case OP_DEATHNOTE:
1091		break;
1092	case OP_ASM:
1093		assert(0);
1094		break;
1095	case OP_COPY:
1096		assert(0);
1097		break;
1098	default:
1099		break;
1100	}
1101}
1102
1103static void output_bb(struct function *fn, struct basic_block *bb)
1104{
1105	struct instruction *insn;
1106
1107	FOR_EACH_PTR(bb->insns, insn) {
1108		if (!insn->bb)
1109			continue;
1110
1111		output_insn(fn, insn);
1112	}
1113	END_FOR_EACH_PTR(insn);
1114}
1115
1116#define MAX_ARGS	64
1117
1118static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
1119{
1120	struct symbol *sym = ep->name;
1121	struct symbol *base_type = sym->ctype.base_type;
1122	struct function function = { .module = module };
1123	struct basic_block *bb;
1124	int nr_args = 0;
1125	int i;
1126
1127	function.fn = get_sym_value(module, sym);
1128	LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
1129	LLVMSetLinkage(function.fn, function_linkage(sym));
1130
1131	function.builder = LLVMCreateBuilder();
1132
1133	/* give a name to each argument */
1134	nr_args = symbol_list_size(base_type->arguments);
1135	for (i = 0; i < nr_args; i++) {
1136		char name[MAX_PSEUDO_NAME];
1137		LLVMValueRef arg;
1138
1139		arg = LLVMGetParam(function.fn, i);
1140		snprintf(name, sizeof(name), "ARG%d.", i+1);
1141		LLVMSetValueName(arg, name);
1142	}
1143
1144	/* create the BBs */
1145	FOR_EACH_PTR(ep->bbs, bb) {
1146		static int nr_bb;
1147		LLVMBasicBlockRef bbr;
1148		char bbname[32];
1149
1150		sprintf(bbname, "L%d", nr_bb++);
1151		bbr = LLVMAppendBasicBlock(function.fn, bbname);
1152
1153		bb->priv = bbr;
1154	}
1155	END_FOR_EACH_PTR(bb);
1156
1157	FOR_EACH_PTR(ep->bbs, bb) {
1158		LLVMPositionBuilderAtEnd(function.builder, bb->priv);
1159
1160		output_bb(&function, bb);
1161	}
1162	END_FOR_EACH_PTR(bb);
1163
1164	FOR_EACH_PTR(ep->bbs, bb) {	// complete the OP_PHIs
1165		struct instruction *insn;
1166
1167		FOR_EACH_PTR(bb->insns, insn) {
1168			pseudo_t phi;
1169
1170			if (!insn->bb || insn->opcode != OP_PHI)
1171				continue;
1172
1173			FOR_EACH_PTR(insn->phi_list, phi) {
1174				struct instruction *phisrc;
1175				LLVMBasicBlockRef bref;
1176				LLVMValueRef vref;
1177
1178				if (phi == VOID)
1179					continue;
1180
1181				phisrc = phi->def;
1182				bref = phisrc->bb->priv;
1183				vref = phisrc->src->priv;
1184				LLVMAddIncoming(insn->target->priv, &vref, &bref, 1);
1185			} END_FOR_EACH_PTR(phi);
1186		} END_FOR_EACH_PTR(insn);
1187	} END_FOR_EACH_PTR(bb);
1188}
1189
1190static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
1191{
1192	struct expression *initializer = sym->initializer;
1193	LLVMValueRef initial_value;
1194	LLVMValueRef data;
1195	const char *name;
1196
1197	if (initializer) {
1198		switch (initializer->type) {
1199		case EXPR_VALUE:
1200			initial_value = LLVMConstInt(symbol_type(sym), initializer->value, 1);
1201			break;
1202		case EXPR_FVALUE:
1203			initial_value = LLVMConstReal(symbol_type(sym), initializer->fvalue);
1204			break;
1205		case EXPR_SYMBOL: {
1206			struct symbol *sym = initializer->symbol;
1207
1208			initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident));
1209			if (!initial_value)
1210				initial_value = output_data(module, sym);
1211			break;
1212		}
1213		case EXPR_STRING: {
1214			const char *s = initializer->string->data;
1215
1216			initial_value = LLVMConstString(strdup(s), strlen(s) + 1, true);
1217			break;
1218		}
1219		default:
1220			warning(initializer->pos, "can't initialize type: %s", show_typename(sym));
1221			initial_value = NULL;
1222			break;
1223		}
1224	} else {
1225		LLVMTypeRef type = symbol_type(sym);
1226
1227		initial_value = LLVMConstNull(type);
1228	}
1229
1230	if (!initial_value)
1231		return NULL;
1232
1233	name = sym->ident ? show_ident(sym->ident) : "" ;
1234
1235	data = LLVMAddGlobal(module, LLVMTypeOf(initial_value), name);
1236
1237	LLVMSetLinkage(data, data_linkage(sym));
1238	if (sym->ctype.modifiers & MOD_CONST)
1239		LLVMSetGlobalConstant(data, 1);
1240	if (sym->ctype.modifiers & MOD_TLS)
1241		LLVMSetThreadLocal(data, 1);
1242	if (sym->ctype.alignment)
1243		LLVMSetAlignment(data, sym->ctype.alignment);
1244
1245	if (!(sym->ctype.modifiers & MOD_EXTERN))
1246		LLVMSetInitializer(data, initial_value);
1247
1248	return data;
1249}
1250
1251static int is_prototype(struct symbol *sym)
1252{
1253	if (sym->type == SYM_NODE)
1254		sym = sym->ctype.base_type;
1255	return sym && sym->type == SYM_FN && !sym->stmt;
1256}
1257
1258static int compile(LLVMModuleRef module, struct symbol_list *list)
1259{
1260	struct symbol *sym;
1261
1262	FOR_EACH_PTR(list, sym) {
1263		struct entrypoint *ep;
1264		expand_symbol(sym);
1265
1266		if (is_prototype(sym)) {
1267			// this will do the LLVMAddFunction() we want
1268			get_sym_value(module, sym);
1269			continue;
1270		}
1271
1272		ep = linearize_symbol(sym);
1273		if (ep)
1274			output_fn(module, ep);
1275		else
1276			output_data(module, sym);
1277	}
1278	END_FOR_EACH_PTR(sym);
1279
1280	return 0;
1281}
1282
1283#ifndef LLVM_DEFAULT_TARGET_TRIPLE
1284#define LLVM_DEFAULT_TARGET_TRIPLE LLVM_HOSTTRIPLE
1285#endif
1286
1287#define X86_LINUX_LAYOUT \
1288	"e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
1289	"i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-" \
1290	"a0:0:64-f80:32:32-n8:16:32-S128"
1291
1292#define X86_64_LINUX_LAYOUT \
1293	"e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
1294	"i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-" \
1295	"a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
1296
1297static void set_target(LLVMModuleRef module)
1298{
1299	char target[] = LLVM_DEFAULT_TARGET_TRIPLE;
1300	const char *arch, *vendor, *os, *env, *layout = NULL;
1301	char triple[256];
1302
1303	arch = strtok(target, "-");
1304	vendor = strtok(NULL, "-");
1305	os = strtok(NULL, "-");
1306	env = strtok(NULL, "-");
1307
1308	if (!os)
1309		return;
1310	if (!env)
1311		env = "unknown";
1312
1313	if (!strcmp(arch, "x86_64") && !strcmp(os, "linux")) {
1314		if (arch_m64) {
1315			layout = X86_64_LINUX_LAYOUT;
1316		} else {
1317			arch = "i386";
1318			layout = X86_LINUX_LAYOUT;
1319		}
1320	}
1321
1322	/* unsupported target */
1323	if (!layout)
1324		return;
1325
1326	snprintf(triple, sizeof(triple), "%s-%s-%s-%s", arch, vendor, os, env);
1327	LLVMSetTarget(module, triple);
1328	LLVMSetDataLayout(module, layout);
1329}
1330
1331int main(int argc, char **argv)
1332{
1333	struct string_list *filelist = NULL;
1334	struct symbol_list *symlist;
1335	LLVMModuleRef module;
1336	char *file;
1337
1338	symlist = sparse_initialize(argc, argv, &filelist);
1339
1340	module = LLVMModuleCreateWithName("sparse");
1341	set_target(module);
1342
1343	compile(module, symlist);
1344
1345	FOR_EACH_PTR(filelist, file) {
1346		symlist = sparse(file);
1347		if (die_if_error)
1348			return 1;
1349		compile(module, symlist);
1350	} END_FOR_EACH_PTR(file);
1351
1352	LLVMVerifyModule(module, LLVMPrintMessageAction, NULL);
1353
1354	LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);
1355
1356	LLVMDisposeModule(module);
1357
1358	report_stats();
1359	return 0;
1360}
1361