strlen: add a comment and rename some things
[smatch.git] / sparse-llvm.c
blob6f2fbd69b783d6df78205ab233d6fc0eae317370
1 /*
2 * Example usage:
3 * ./sparse-llvm hello.c | llc | as -o hello.o
4 */
6 #include <llvm-c/Core.h>
7 #include <llvm-c/BitWriter.h>
8 #include <llvm-c/Analysis.h>
10 #include <stdbool.h>
11 #include <stdio.h>
12 #include <unistd.h>
13 #include <string.h>
14 #include <assert.h>
16 #include "symbol.h"
17 #include "expression.h"
18 #include "linearize.h"
19 #include "flow.h"
21 struct phi_fwd {
22 struct phi_fwd *next;
24 LLVMValueRef phi;
25 pseudo_t pseudo;
26 bool resolved;
29 struct function {
30 LLVMBuilderRef builder;
31 LLVMTypeRef type;
32 LLVMValueRef fn;
33 LLVMModuleRef module;
35 struct phi_fwd *fwd_list;
38 static inline bool symbol_is_fp_type(struct symbol *sym)
40 if (!sym)
41 return false;
43 return sym->ctype.base_type == &fp_type;
46 static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym);
48 static LLVMTypeRef func_return_type(LLVMModuleRef module, struct symbol *sym)
50 return symbol_type(module, sym->ctype.base_type);
53 static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym)
55 LLVMTypeRef *arg_type;
56 LLVMTypeRef func_type;
57 LLVMTypeRef ret_type;
58 struct symbol *arg;
59 int n_arg = 0;
61 /* to avoid strangeness with varargs [for now], we build
62 * the function and type anew, for each call. This
63 * is probably wrong. We should look up the
64 * symbol declaration info.
67 ret_type = func_return_type(module, sym);
69 /* count args, build argument type information */
70 FOR_EACH_PTR(sym->arguments, arg) {
71 n_arg++;
72 } END_FOR_EACH_PTR(arg);
74 arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
76 int idx = 0;
77 FOR_EACH_PTR(sym->arguments, arg) {
78 struct symbol *arg_sym = arg->ctype.base_type;
80 arg_type[idx++] = symbol_type(module, arg_sym);
81 } END_FOR_EACH_PTR(arg);
82 func_type = LLVMFunctionType(ret_type, arg_type, n_arg,
83 sym->ctype.base_type->variadic);
85 return func_type;
88 static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym)
90 LLVMTypeRef elem_type;
91 struct symbol *base_type;
93 base_type = sym->ctype.base_type;
95 elem_type = symbol_type(module, base_type);
96 if (!elem_type)
97 return NULL;
99 return LLVMArrayType(elem_type, sym->bit_size / 8);
102 #define MAX_STRUCT_MEMBERS 64
104 static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym)
106 LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS];
107 struct symbol *member;
108 char buffer[256];
109 LLVMTypeRef ret;
110 unsigned nr = 0;
112 sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name);
114 ret = LLVMGetTypeByName(module, buffer);
115 if (ret)
116 return ret;
118 ret = LLVMStructCreateNamed(LLVMGetGlobalContext(), buffer);
120 FOR_EACH_PTR(sym->symbol_list, member) {
121 LLVMTypeRef member_type;
123 assert(nr < MAX_STRUCT_MEMBERS);
125 member_type = symbol_type(module, member);
127 elem_types[nr++] = member_type;
128 } END_FOR_EACH_PTR(member);
130 LLVMStructSetBody(ret, elem_types, nr, 0 /* packed? */);
131 return ret;
134 static LLVMTypeRef sym_union_type(LLVMModuleRef module, struct symbol *sym)
136 LLVMTypeRef elements;
137 unsigned union_size;
140 * There's no union support in the LLVM API so we treat unions as
141 * opaque structs. The downside is that we lose type information on the
142 * members but as LLVM doesn't care, neither do we.
144 union_size = sym->bit_size / 8;
146 elements = LLVMArrayType(LLVMInt8Type(), union_size);
148 return LLVMStructType(&elements, 1, 0 /* packed? */);
151 static LLVMTypeRef sym_ptr_type(LLVMModuleRef module, struct symbol *sym)
153 LLVMTypeRef type;
155 /* 'void *' is treated like 'char *' */
156 if (is_void_type(sym->ctype.base_type))
157 type = LLVMInt8Type();
158 else
159 type = symbol_type(module, sym->ctype.base_type);
161 return LLVMPointerType(type, 0);
164 static LLVMTypeRef sym_basetype_type(struct symbol *sym)
166 LLVMTypeRef ret = NULL;
168 if (symbol_is_fp_type(sym)) {
169 switch (sym->bit_size) {
170 case 32:
171 ret = LLVMFloatType();
172 break;
173 case 64:
174 ret = LLVMDoubleType();
175 break;
176 case 80:
177 ret = LLVMX86FP80Type();
178 break;
179 default:
180 die("invalid bit size %d for type %d", sym->bit_size, sym->type);
181 break;
183 } else {
184 switch (sym->bit_size) {
185 case -1:
186 ret = LLVMVoidType();
187 break;
188 case 1:
189 ret = LLVMInt1Type();
190 break;
191 case 8:
192 ret = LLVMInt8Type();
193 break;
194 case 16:
195 ret = LLVMInt16Type();
196 break;
197 case 32:
198 ret = LLVMInt32Type();
199 break;
200 case 64:
201 ret = LLVMInt64Type();
202 break;
203 default:
204 die("invalid bit size %d for type %d", sym->bit_size, sym->type);
205 break;
209 return ret;
212 static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym)
214 LLVMTypeRef ret = NULL;
216 switch (sym->type) {
217 case SYM_BITFIELD:
218 case SYM_ENUM:
219 case SYM_NODE:
220 ret = symbol_type(module, sym->ctype.base_type);
221 break;
222 case SYM_BASETYPE:
223 ret = sym_basetype_type(sym);
224 break;
225 case SYM_PTR:
226 ret = sym_ptr_type(module, sym);
227 break;
228 case SYM_UNION:
229 ret = sym_union_type(module, sym);
230 break;
231 case SYM_STRUCT:
232 ret = sym_struct_type(module, sym);
233 break;
234 case SYM_ARRAY:
235 ret = sym_array_type(module, sym);
236 break;
237 case SYM_FN:
238 ret = sym_func_type(module, sym);
239 break;
240 default:
241 assert(0);
243 return ret;
246 static LLVMTypeRef insn_symbol_type(LLVMModuleRef module, struct instruction *insn)
248 if (insn->type)
249 return symbol_type(module, insn->type);
251 switch (insn->size) {
252 case 8: return LLVMInt8Type();
253 case 16: return LLVMInt16Type();
254 case 32: return LLVMInt32Type();
255 case 64: return LLVMInt64Type();
257 default:
258 die("invalid bit size %d", insn->size);
259 break;
262 return NULL; /* not reached */
265 static LLVMLinkage data_linkage(struct symbol *sym)
267 if (sym->ctype.modifiers & MOD_STATIC)
268 return LLVMPrivateLinkage;
270 return LLVMExternalLinkage;
273 static LLVMLinkage function_linkage(struct symbol *sym)
275 if (sym->ctype.modifiers & MOD_STATIC)
276 return LLVMInternalLinkage;
278 return LLVMExternalLinkage;
281 #define MAX_PSEUDO_NAME 64
283 static void pseudo_name(pseudo_t pseudo, char *buf)
285 switch (pseudo->type) {
286 case PSEUDO_REG:
287 snprintf(buf, MAX_PSEUDO_NAME, "R%d", pseudo->nr);
288 break;
289 case PSEUDO_SYM:
290 assert(0);
291 break;
292 case PSEUDO_VAL:
293 assert(0);
294 break;
295 case PSEUDO_ARG: {
296 assert(0);
297 break;
299 case PSEUDO_PHI:
300 snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr);
301 break;
302 default:
303 assert(0);
307 static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo)
309 LLVMValueRef result = NULL;
311 switch (pseudo->type) {
312 case PSEUDO_REG:
313 result = pseudo->priv;
314 break;
315 case PSEUDO_SYM: {
316 struct symbol *sym = pseudo->sym;
317 struct expression *expr;
319 assert(sym->bb_target == NULL);
321 expr = sym->initializer;
322 if (expr) {
323 switch (expr->type) {
324 case EXPR_STRING: {
325 const char *s = expr->string->data;
326 LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) };
327 LLVMValueRef data;
329 data = LLVMAddGlobal(fn->module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str");
330 LLVMSetLinkage(data, LLVMPrivateLinkage);
331 LLVMSetGlobalConstant(data, 1);
332 LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true));
334 result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
335 break;
337 case EXPR_SYMBOL: {
338 struct symbol *sym = expr->symbol;
340 result = LLVMGetNamedGlobal(fn->module, show_ident(sym->ident));
341 assert(result != NULL);
342 break;
344 default:
345 assert(0);
347 } else {
348 const char *name = show_ident(sym->ident);
350 result = LLVMGetNamedGlobal(fn->module, name);
351 if (!result) {
352 LLVMTypeRef type = symbol_type(fn->module, sym);
353 result = LLVMAddGlobal(fn->module, type, name);
356 break;
358 case PSEUDO_VAL:
359 result = LLVMConstInt(insn_symbol_type(fn->module, insn), pseudo->value, 1);
360 break;
361 case PSEUDO_ARG: {
362 result = LLVMGetParam(fn->fn, pseudo->nr - 1);
363 break;
365 case PSEUDO_PHI:
366 result = pseudo->priv;
367 break;
368 case PSEUDO_VOID:
369 result = NULL;
370 break;
371 default:
372 assert(0);
375 return result;
378 static LLVMTypeRef pseudo_type(struct function *fn, struct instruction *insn, pseudo_t pseudo)
380 LLVMValueRef v;
381 LLVMTypeRef result = NULL;
383 if (pseudo->priv) {
384 v = pseudo->priv;
385 return LLVMTypeOf(v);
388 switch (pseudo->type) {
389 case PSEUDO_REG:
390 result = symbol_type(fn->module, pseudo->def->type);
391 break;
392 case PSEUDO_SYM: {
393 struct symbol *sym = pseudo->sym;
394 struct expression *expr;
396 assert(sym->bb_target == NULL);
397 assert(sym->ident == NULL);
399 expr = sym->initializer;
400 if (expr) {
401 switch (expr->type) {
402 case EXPR_STRING:
403 result = LLVMPointerType(LLVMInt8Type(), 0);
404 break;
405 default:
406 assert(0);
409 break;
411 case PSEUDO_VAL:
412 result = insn_symbol_type(fn->module, insn);
413 break;
414 case PSEUDO_ARG:
415 result = LLVMTypeOf(LLVMGetParam(fn->fn, pseudo->nr - 1));
416 break;
417 case PSEUDO_PHI:
418 assert(0);
419 break;
420 case PSEUDO_VOID:
421 result = LLVMVoidType();
422 break;
423 default:
424 assert(0);
427 return result;
430 static LLVMRealPredicate translate_fop(int opcode)
432 static const LLVMRealPredicate trans_tbl[] = {
433 [OP_SET_EQ] = LLVMRealOEQ,
434 [OP_SET_NE] = LLVMRealUNE,
435 [OP_SET_LE] = LLVMRealOLE,
436 [OP_SET_GE] = LLVMRealOGE,
437 [OP_SET_LT] = LLVMRealOLT,
438 [OP_SET_GT] = LLVMRealOGT,
439 /* Are these used with FP? */
440 [OP_SET_B] = LLVMRealOLT,
441 [OP_SET_A] = LLVMRealOGT,
442 [OP_SET_BE] = LLVMRealOLE,
443 [OP_SET_AE] = LLVMRealOGE,
446 return trans_tbl[opcode];
449 static LLVMIntPredicate translate_op(int opcode)
451 static const LLVMIntPredicate trans_tbl[] = {
452 [OP_SET_EQ] = LLVMIntEQ,
453 [OP_SET_NE] = LLVMIntNE,
454 [OP_SET_LE] = LLVMIntSLE,
455 [OP_SET_GE] = LLVMIntSGE,
456 [OP_SET_LT] = LLVMIntSLT,
457 [OP_SET_GT] = LLVMIntSGT,
458 [OP_SET_B] = LLVMIntULT,
459 [OP_SET_A] = LLVMIntUGT,
460 [OP_SET_BE] = LLVMIntULE,
461 [OP_SET_AE] = LLVMIntUGE,
464 return trans_tbl[opcode];
467 static void output_op_binary(struct function *fn, struct instruction *insn)
469 LLVMValueRef lhs, rhs, target;
470 char target_name[64];
472 lhs = pseudo_to_value(fn, insn, insn->src1);
474 rhs = pseudo_to_value(fn, insn, insn->src2);
476 pseudo_name(insn->target, target_name);
478 switch (insn->opcode) {
479 /* Binary */
480 case OP_ADD:
481 if (symbol_is_fp_type(insn->type))
482 target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name);
483 else
484 target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
485 break;
486 case OP_SUB:
487 if (symbol_is_fp_type(insn->type))
488 target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name);
489 else
490 target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
491 break;
492 case OP_MULU:
493 if (symbol_is_fp_type(insn->type))
494 target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name);
495 else
496 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
497 break;
498 case OP_MULS:
499 assert(!symbol_is_fp_type(insn->type));
500 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
501 break;
502 case OP_DIVU:
503 if (symbol_is_fp_type(insn->type))
504 target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name);
505 else
506 target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name);
507 break;
508 case OP_DIVS:
509 assert(!symbol_is_fp_type(insn->type));
510 target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
511 break;
512 case OP_MODU:
513 assert(!symbol_is_fp_type(insn->type));
514 target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
515 break;
516 case OP_MODS:
517 assert(!symbol_is_fp_type(insn->type));
518 target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
519 break;
520 case OP_SHL:
521 assert(!symbol_is_fp_type(insn->type));
522 target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
523 break;
524 case OP_LSR:
525 assert(!symbol_is_fp_type(insn->type));
526 target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
527 break;
528 case OP_ASR:
529 assert(!symbol_is_fp_type(insn->type));
530 target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
531 break;
533 /* Logical */
534 case OP_AND:
535 assert(!symbol_is_fp_type(insn->type));
536 target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
537 break;
538 case OP_OR:
539 assert(!symbol_is_fp_type(insn->type));
540 target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
541 break;
542 case OP_XOR:
543 assert(!symbol_is_fp_type(insn->type));
544 target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
545 break;
546 case OP_AND_BOOL: {
547 LLVMValueRef x, y;
549 assert(!symbol_is_fp_type(insn->type));
551 y = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, LLVMConstInt(LLVMTypeOf(lhs), 0, 0), "y");
552 x = LLVMBuildICmp(fn->builder, LLVMIntNE, rhs, LLVMConstInt(LLVMTypeOf(rhs), 0, 0), "x");
554 target = LLVMBuildAnd(fn->builder, y, x, target_name);
555 break;
557 case OP_OR_BOOL: {
558 LLVMValueRef tmp;
560 assert(!symbol_is_fp_type(insn->type));
562 tmp = LLVMBuildOr(fn->builder, rhs, lhs, "tmp");
564 target = LLVMBuildICmp(fn->builder, LLVMIntNE, tmp, LLVMConstInt(LLVMTypeOf(tmp), 0, 0), target_name);
565 break;
568 /* Binary comparison */
569 case OP_BINCMP ... OP_BINCMP_END: {
570 if (LLVMGetTypeKind(LLVMTypeOf(lhs)) == LLVMIntegerTypeKind) {
571 LLVMIntPredicate op = translate_op(insn->opcode);
573 target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name);
574 } else {
575 LLVMRealPredicate op = translate_fop(insn->opcode);
577 target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name);
579 break;
581 default:
582 assert(0);
583 break;
586 insn->target->priv = target;
589 static void output_op_ret(struct function *fn, struct instruction *insn)
591 pseudo_t pseudo = insn->src;
593 if (pseudo && pseudo != VOID) {
594 LLVMValueRef result = pseudo_to_value(fn, insn, pseudo);
596 LLVMBuildRet(fn->builder, result);
597 } else
598 LLVMBuildRetVoid(fn->builder);
601 static void output_op_load(struct function *fn, struct instruction *insn)
603 LLVMTypeRef int_type;
604 LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target;
606 /* int type large enough to hold a pointer */
607 int_type = LLVMIntType(bits_in_pointer);
609 /* convert to integer, add src + offset */
610 src_p = pseudo_to_value(fn, insn, insn->src);
611 src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i");
613 ofs_i = LLVMConstInt(int_type, insn->offset, 0);
614 addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i");
616 /* convert address back to pointer */
617 addr = LLVMBuildIntToPtr(fn->builder, addr_i,
618 LLVMTypeOf(src_p), "addr");
620 /* perform load */
621 target = LLVMBuildLoad(fn->builder, addr, "load_target");
623 insn->target->priv = target;
626 static void output_op_store(struct function *fn, struct instruction *insn)
628 LLVMTypeRef int_type;
629 LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target, target_in;
631 /* int type large enough to hold a pointer */
632 int_type = LLVMIntType(bits_in_pointer);
634 /* convert to integer, add src + offset */
635 src_p = pseudo_to_value(fn, insn, insn->src);
636 src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i");
638 ofs_i = LLVMConstInt(int_type, insn->offset, 0);
639 addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i");
641 /* convert address back to pointer */
642 addr = LLVMBuildIntToPtr(fn->builder, addr_i,
643 LLVMPointerType(int_type, 0), "addr");
645 target_in = pseudo_to_value(fn, insn, insn->target);
647 /* perform store */
648 target = LLVMBuildStore(fn->builder, target_in, addr);
650 insn->target->priv = target;
653 static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
655 if (LLVMTypeOf(value) != LLVMInt1Type())
656 value = LLVMBuildIsNotNull(fn->builder, value, "cond");
658 return value;
661 static void output_op_br(struct function *fn, struct instruction *br)
663 if (br->cond) {
664 LLVMValueRef cond = bool_value(fn,
665 pseudo_to_value(fn, br, br->cond));
667 LLVMBuildCondBr(fn->builder, cond,
668 br->bb_true->priv,
669 br->bb_false->priv);
670 } else
671 LLVMBuildBr(fn->builder,
672 br->bb_true ? br->bb_true->priv :
673 br->bb_false->priv);
676 static void output_op_sel(struct function *fn, struct instruction *insn)
678 LLVMValueRef target, src1, src2, src3;
680 src1 = bool_value(fn, pseudo_to_value(fn, insn, insn->src1));
681 src2 = pseudo_to_value(fn, insn, insn->src2);
682 src3 = pseudo_to_value(fn, insn, insn->src3);
684 target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select");
686 insn->target->priv = target;
689 static void output_op_switch(struct function *fn, struct instruction *insn)
691 LLVMValueRef sw_val, target;
692 struct basic_block *def = NULL;
693 struct multijmp *jmp;
694 int n_jmp = 0;
696 FOR_EACH_PTR(insn->multijmp_list, jmp) {
697 if (jmp->begin == jmp->end) { /* case N */
698 n_jmp++;
699 } else if (jmp->begin < jmp->end) { /* case M..N */
700 assert(0);
701 } else /* default case */
702 def = jmp->target;
703 } END_FOR_EACH_PTR(jmp);
705 sw_val = pseudo_to_value(fn, insn, insn->target);
706 target = LLVMBuildSwitch(fn->builder, sw_val,
707 def ? def->priv : NULL, n_jmp);
709 FOR_EACH_PTR(insn->multijmp_list, jmp) {
710 if (jmp->begin == jmp->end) { /* case N */
711 LLVMAddCase(target,
712 LLVMConstInt(LLVMInt32Type(), jmp->begin, 0),
713 jmp->target->priv);
714 } else if (jmp->begin < jmp->end) { /* case M..N */
715 assert(0);
717 } END_FOR_EACH_PTR(jmp);
719 insn->target->priv = target;
722 struct llfunc {
723 char name[256]; /* wasteful */
724 LLVMValueRef func;
727 DECLARE_ALLOCATOR(llfunc);
728 DECLARE_PTR_LIST(llfunc_list, struct llfunc);
729 ALLOCATOR(llfunc, "llfuncs");
731 static struct local_module {
732 struct llfunc_list *llfunc_list;
733 } mi;
735 static LLVMTypeRef get_func_type(struct function *fn, struct instruction *insn)
737 struct symbol *sym = insn->func->sym;
738 char buffer[256];
739 LLVMTypeRef func_type, ret_type;
740 struct pseudo *arg;
741 int n_arg = 0;
742 LLVMTypeRef *arg_type;
744 if (sym->ident)
745 sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name);
746 else
747 sprintf(buffer, "<anon sym %p>", sym);
749 /* VERIFY: is this correct, for functions? */
750 func_type = LLVMGetTypeByName(fn->module, buffer);
751 if (func_type)
752 return func_type;
754 /* to avoid strangeness with varargs [for now], we build
755 * the function and type anew, for each call. This
756 * is probably wrong. We should look up the
757 * symbol declaration info.
760 /* build return type */
761 if (insn->target && insn->target != VOID)
762 ret_type = pseudo_type(fn, insn, insn->target);
763 else
764 ret_type = LLVMVoidType();
766 /* count args, build argument type information */
767 FOR_EACH_PTR(insn->arguments, arg) {
768 n_arg++;
769 } END_FOR_EACH_PTR(arg);
771 arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
773 int idx = 0;
774 FOR_EACH_PTR(insn->arguments, arg) {
775 arg_type[idx++] = pseudo_type(fn, insn, arg);
776 } END_FOR_EACH_PTR(arg);
778 func_type = LLVMFunctionType(ret_type, arg_type, n_arg,
779 insn->fntype->variadic);
781 return func_type;
784 static LLVMValueRef get_function(struct function *fn, struct instruction *insn)
786 struct symbol *sym = insn->func->sym;
787 char buffer[256];
788 LLVMValueRef func;
789 struct llfunc *f;
791 if (sym->ident)
792 sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name);
793 else
794 sprintf(buffer, "<anon sym %p>", sym);
797 /* search for pre-built function type definition */
798 FOR_EACH_PTR(mi.llfunc_list, f) {
799 if (!strcmp(f->name, buffer))
800 return f->func; /* found match; return */
801 } END_FOR_EACH_PTR(f);
803 /* build function type definition */
804 LLVMTypeRef func_type = get_func_type(fn, insn);
806 func = LLVMAddFunction(fn->module, buffer, func_type);
808 /* store built function on list, for later referencing */
809 f = calloc(1, sizeof(*f));
810 strncpy(f->name, buffer, sizeof(f->name) - 1);
811 f->func = func;
813 add_ptr_list(&mi.llfunc_list, f);
815 return func;
818 static void output_op_call(struct function *fn, struct instruction *insn)
820 LLVMValueRef target, func;
821 int n_arg = 0, i;
822 struct pseudo *arg;
823 LLVMValueRef *args;
825 FOR_EACH_PTR(insn->arguments, arg) {
826 n_arg++;
827 } END_FOR_EACH_PTR(arg);
829 args = calloc(n_arg, sizeof(LLVMValueRef));
831 i = 0;
832 FOR_EACH_PTR(insn->arguments, arg) {
833 args[i++] = pseudo_to_value(fn, insn, arg);
834 } END_FOR_EACH_PTR(arg);
836 func = get_function(fn, insn);
837 target = LLVMBuildCall(fn->builder, func, args, n_arg, "");
839 insn->target->priv = target;
842 static void store_phi_fwd(struct function *fn, LLVMValueRef phi,
843 pseudo_t pseudo)
845 struct phi_fwd *fwd;
847 fwd = calloc(1, sizeof(*fwd));
848 fwd->phi = phi;
849 fwd->pseudo = pseudo;
851 /* append fwd ref to function-wide list */
852 if (!fn->fwd_list)
853 fn->fwd_list = fwd;
854 else {
855 struct phi_fwd *last = fn->fwd_list;
857 while (last->next)
858 last = last->next;
859 last->next = fwd;
863 static void output_phi_fwd(struct function *fn, pseudo_t pseudo, LLVMValueRef v)
865 struct phi_fwd *fwd = fn->fwd_list;
867 while (fwd) {
868 struct phi_fwd *tmp;
870 tmp = fwd;
871 fwd = fwd->next;
873 if (tmp->pseudo == pseudo && !tmp->resolved) {
874 LLVMValueRef phi_vals[1];
875 LLVMBasicBlockRef phi_blks[1];
877 phi_vals[0] = v;
878 phi_blks[0] = pseudo->def->bb->priv;
880 LLVMAddIncoming(tmp->phi, phi_vals, phi_blks, 1);
882 tmp->resolved = true;
887 static void output_op_phisrc(struct function *fn, struct instruction *insn)
889 LLVMValueRef v;
891 assert(insn->target->priv == NULL);
893 /* target = src */
894 v = pseudo_to_value(fn, insn, insn->phi_src);
895 insn->target->priv = v;
897 assert(insn->target->priv != NULL);
899 /* resolve forward references to this phi source, if present */
900 output_phi_fwd(fn, insn->target, v);
903 static void output_op_phi(struct function *fn, struct instruction *insn)
905 pseudo_t phi;
906 LLVMValueRef target;
908 target = LLVMBuildPhi(fn->builder, insn_symbol_type(fn->module, insn),
909 "phi");
910 int pll = 0;
911 FOR_EACH_PTR(insn->phi_list, phi) {
912 if (pseudo_to_value(fn, insn, phi)) /* skip VOID, fwd refs*/
913 pll++;
914 } END_FOR_EACH_PTR(phi);
916 LLVMValueRef *phi_vals = calloc(pll, sizeof(LLVMValueRef));
917 LLVMBasicBlockRef *phi_blks = calloc(pll, sizeof(LLVMBasicBlockRef));
919 int idx = 0;
920 FOR_EACH_PTR(insn->phi_list, phi) {
921 LLVMValueRef v;
923 v = pseudo_to_value(fn, insn, phi);
924 if (v) { /* skip VOID, fwd refs */
925 phi_vals[idx] = v;
926 phi_blks[idx] = phi->def->bb->priv;
927 idx++;
929 else if (phi->type == PSEUDO_PHI) /* fwd ref */
930 store_phi_fwd(fn, target, phi);
931 } END_FOR_EACH_PTR(phi);
933 LLVMAddIncoming(target, phi_vals, phi_blks, pll);
935 insn->target->priv = target;
938 static void output_op_ptrcast(struct function *fn, struct instruction *insn)
940 LLVMValueRef src, target;
941 char target_name[64];
943 src = insn->src->priv;
944 if (!src)
945 src = pseudo_to_value(fn, insn, insn->src);
947 pseudo_name(insn->target, target_name);
949 assert(!symbol_is_fp_type(insn->type));
951 target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
953 insn->target->priv = target;
956 static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
958 LLVMValueRef src, target;
959 char target_name[64];
961 src = insn->src->priv;
962 if (!src)
963 src = pseudo_to_value(fn, insn, insn->src);
965 pseudo_name(insn->target, target_name);
967 assert(!symbol_is_fp_type(insn->type));
969 if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src)))
970 target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
971 else
972 target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(fn->module, insn), target_name);
974 insn->target->priv = target;
977 static void output_op_copy(struct function *fn, struct instruction *insn,
978 pseudo_t pseudo)
980 LLVMValueRef src, target;
981 LLVMTypeRef const_type;
982 char target_name[64];
984 pseudo_name(insn->target, target_name);
985 src = pseudo_to_value(fn, insn, pseudo);
986 const_type = insn_symbol_type(fn->module, insn);
989 * This is nothing more than 'target = src'
991 * TODO: find a better way to provide an identity function,
992 * than using "X + 0" simply to produce a new LLVM pseudo
995 if (symbol_is_fp_type(insn->type))
996 target = LLVMBuildFAdd(fn->builder, src,
997 LLVMConstReal(const_type, 0.0), target_name);
998 else
999 target = LLVMBuildAdd(fn->builder, src,
1000 LLVMConstInt(const_type, 0, 0), target_name);
1002 insn->target->priv = target;
1005 static void output_insn(struct function *fn, struct instruction *insn)
1007 switch (insn->opcode) {
1008 case OP_RET:
1009 output_op_ret(fn, insn);
1010 break;
1011 case OP_BR:
1012 output_op_br(fn, insn);
1013 break;
1014 case OP_SYMADDR:
1015 assert(0);
1016 break;
1017 case OP_SETVAL:
1018 assert(0);
1019 break;
1020 case OP_SWITCH:
1021 output_op_switch(fn, insn);
1022 break;
1023 case OP_COMPUTEDGOTO:
1024 assert(0);
1025 break;
1026 case OP_PHISOURCE:
1027 output_op_phisrc(fn, insn);
1028 break;
1029 case OP_PHI:
1030 output_op_phi(fn, insn);
1031 break;
1032 case OP_LOAD:
1033 output_op_load(fn, insn);
1034 break;
1035 case OP_LNOP:
1036 assert(0);
1037 break;
1038 case OP_STORE:
1039 output_op_store(fn, insn);
1040 break;
1041 case OP_SNOP:
1042 assert(0);
1043 break;
1044 case OP_INLINED_CALL:
1045 assert(0);
1046 break;
1047 case OP_CALL:
1048 output_op_call(fn, insn);
1049 break;
1050 case OP_CAST:
1051 output_op_cast(fn, insn, LLVMZExt);
1052 break;
1053 case OP_SCAST:
1054 output_op_cast(fn, insn, LLVMSExt);
1055 break;
1056 case OP_FPCAST:
1057 assert(0);
1058 break;
1059 case OP_PTRCAST:
1060 output_op_ptrcast(fn, insn);
1061 break;
1062 case OP_BINARY ... OP_BINARY_END:
1063 case OP_BINCMP ... OP_BINCMP_END:
1064 output_op_binary(fn, insn);
1065 break;
1066 case OP_SEL:
1067 output_op_sel(fn, insn);
1068 break;
1069 case OP_SLICE:
1070 assert(0);
1071 break;
1072 case OP_NOT: {
1073 LLVMValueRef src, target;
1074 char target_name[64];
1076 src = pseudo_to_value(fn, insn, insn->src);
1078 pseudo_name(insn->target, target_name);
1080 target = LLVMBuildNot(fn->builder, src, target_name);
1082 insn->target->priv = target;
1083 break;
1085 case OP_NEG:
1086 assert(0);
1087 break;
1088 case OP_CONTEXT:
1089 assert(0);
1090 break;
1091 case OP_RANGE:
1092 assert(0);
1093 break;
1094 case OP_NOP:
1095 assert(0);
1096 break;
1097 case OP_DEATHNOTE:
1098 assert(0);
1099 break;
1100 case OP_ASM:
1101 assert(0);
1102 break;
1103 case OP_COPY:
1104 output_op_copy(fn, insn, insn->src);
1105 break;
1106 default:
1107 break;
1111 static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation)
1113 struct instruction *insn;
1115 bb->generation = generation;
1117 FOR_EACH_PTR(bb->insns, insn) {
1118 if (!insn->bb)
1119 continue;
1121 output_insn(fn, insn);
1123 END_FOR_EACH_PTR(insn);
1126 #define MAX_ARGS 64
1128 static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
1130 unsigned long generation = ++bb_generation;
1131 struct symbol *sym = ep->name;
1132 struct symbol *base_type = sym->ctype.base_type;
1133 struct symbol *ret_type = sym->ctype.base_type->ctype.base_type;
1134 LLVMTypeRef arg_types[MAX_ARGS];
1135 LLVMTypeRef return_type;
1136 struct function function = { .module = module };
1137 struct basic_block *bb;
1138 struct symbol *arg;
1139 const char *name;
1140 int nr_args = 0;
1141 struct llfunc *f;
1143 FOR_EACH_PTR(base_type->arguments, arg) {
1144 struct symbol *arg_base_type = arg->ctype.base_type;
1146 arg_types[nr_args++] = symbol_type(module, arg_base_type);
1147 } END_FOR_EACH_PTR(arg);
1149 name = show_ident(sym->ident);
1151 return_type = symbol_type(module, ret_type);
1153 function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0);
1155 function.fn = LLVMAddFunction(module, name, function.type);
1156 LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
1158 LLVMSetLinkage(function.fn, function_linkage(sym));
1160 /* store built function on list, for later referencing */
1161 f = calloc(1, sizeof(*f));
1162 strncpy(f->name, name, sizeof(f->name) - 1);
1163 f->func = function.fn;
1165 add_ptr_list(&mi.llfunc_list, f);
1167 function.builder = LLVMCreateBuilder();
1169 static int nr_bb;
1171 FOR_EACH_PTR(ep->bbs, bb) {
1172 if (bb->generation == generation)
1173 continue;
1175 LLVMBasicBlockRef bbr;
1176 char bbname[32];
1178 sprintf(bbname, "L%d", nr_bb++);
1179 bbr = LLVMAppendBasicBlock(function.fn, bbname);
1181 bb->priv = bbr;
1183 END_FOR_EACH_PTR(bb);
1185 FOR_EACH_PTR(ep->bbs, bb) {
1186 if (bb->generation == generation)
1187 continue;
1189 LLVMPositionBuilderAtEnd(function.builder, bb->priv);
1191 output_bb(&function, bb, generation);
1193 END_FOR_EACH_PTR(bb);
1196 static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
1198 struct expression *initializer = sym->initializer;
1199 LLVMValueRef initial_value;
1200 LLVMValueRef data;
1201 const char *name;
1203 if (initializer) {
1204 switch (initializer->type) {
1205 case EXPR_VALUE:
1206 initial_value = LLVMConstInt(symbol_type(module, sym), initializer->value, 1);
1207 break;
1208 case EXPR_SYMBOL: {
1209 struct symbol *sym = initializer->symbol;
1211 initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident));
1212 if (!initial_value)
1213 initial_value = output_data(module, sym);
1214 break;
1216 case EXPR_STRING: {
1217 const char *s = initializer->string->data;
1219 initial_value = LLVMConstString(strdup(s), strlen(s) + 1, true);
1220 break;
1222 default:
1223 assert(0);
1225 } else {
1226 LLVMTypeRef type = symbol_type(module, sym);
1228 initial_value = LLVMConstNull(type);
1231 name = show_ident(sym->ident);
1233 data = LLVMAddGlobal(module, LLVMTypeOf(initial_value), name);
1235 LLVMSetLinkage(data, data_linkage(sym));
1237 if (!(sym->ctype.modifiers & MOD_EXTERN))
1238 LLVMSetInitializer(data, initial_value);
1240 return data;
1243 static int compile(LLVMModuleRef module, struct symbol_list *list)
1245 struct symbol *sym;
1247 FOR_EACH_PTR(list, sym) {
1248 struct entrypoint *ep;
1249 expand_symbol(sym);
1250 ep = linearize_symbol(sym);
1251 if (ep)
1252 output_fn(module, ep);
1253 else
1254 output_data(module, sym);
1256 END_FOR_EACH_PTR(sym);
1258 return 0;
1261 int main(int argc, char **argv)
1263 struct string_list * filelist = NULL;
1264 char *file;
1266 LLVMModuleRef module = LLVMModuleCreateWithName("sparse");
1268 compile(module, sparse_initialize(argc, argv, &filelist));
1270 FOR_EACH_PTR_NOTAG(filelist, file) {
1271 compile(module, sparse(file));
1272 } END_FOR_EACH_PTR_NOTAG(file);
1274 LLVMVerifyModule(module, LLVMPrintMessageAction, NULL);
1276 LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);
1278 LLVMDisposeModule(module);
1280 return 0;