comparison: fix merge_comparison() for &undefined
[smatch.git] / sparse-llvm.c
blobecb5b28ef7bea72e22e223f55ae85b44266e15b2
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>
9 #include <llvm-c/Target.h>
11 #include <stdbool.h>
12 #include <stdio.h>
13 #include <unistd.h>
14 #include <string.h>
15 #include <assert.h>
17 #include "symbol.h"
18 #include "expression.h"
19 #include "linearize.h"
20 #include "flow.h"
22 struct function {
23 LLVMBuilderRef builder;
24 LLVMTypeRef type;
25 LLVMValueRef fn;
26 LLVMModuleRef module;
29 static inline bool symbol_is_fp_type(struct symbol *sym)
31 if (!sym)
32 return false;
34 return sym->ctype.base_type == &fp_type;
37 static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym);
39 static LLVMTypeRef func_return_type(LLVMModuleRef module, struct symbol *sym)
41 return symbol_type(module, sym->ctype.base_type);
44 static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym)
46 LLVMTypeRef *arg_type;
47 LLVMTypeRef func_type;
48 LLVMTypeRef ret_type;
49 struct symbol *arg;
50 int n_arg = 0;
52 /* to avoid strangeness with varargs [for now], we build
53 * the function and type anew, for each call. This
54 * is probably wrong. We should look up the
55 * symbol declaration info.
58 ret_type = func_return_type(module, sym);
60 /* count args, build argument type information */
61 FOR_EACH_PTR(sym->arguments, arg) {
62 n_arg++;
63 } END_FOR_EACH_PTR(arg);
65 arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
67 int idx = 0;
68 FOR_EACH_PTR(sym->arguments, arg) {
69 struct symbol *arg_sym = arg->ctype.base_type;
71 arg_type[idx++] = symbol_type(module, arg_sym);
72 } END_FOR_EACH_PTR(arg);
73 func_type = LLVMFunctionType(ret_type, arg_type, n_arg,
74 sym->variadic);
76 return func_type;
79 static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym)
81 LLVMTypeRef elem_type;
82 struct symbol *base_type;
84 base_type = sym->ctype.base_type;
85 /* empty struct is undefined [6.7.2.1(8)] */
86 assert(base_type->bit_size > 0);
88 elem_type = symbol_type(module, base_type);
89 if (!elem_type)
90 return NULL;
92 return LLVMArrayType(elem_type, sym->bit_size / base_type->bit_size);
95 #define MAX_STRUCT_MEMBERS 64
97 static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym)
99 LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS];
100 struct symbol *member;
101 char buffer[256];
102 LLVMTypeRef ret;
103 unsigned nr = 0;
105 snprintf(buffer, sizeof(buffer), "struct.%s", sym->ident ? sym->ident->name : "anno");
106 ret = LLVMStructCreateNamed(LLVMGetGlobalContext(), buffer);
107 /* set ->aux to avoid recursion */
108 sym->aux = ret;
110 FOR_EACH_PTR(sym->symbol_list, member) {
111 LLVMTypeRef member_type;
113 assert(nr < MAX_STRUCT_MEMBERS);
115 member_type = symbol_type(module, member);
117 elem_types[nr++] = member_type;
118 } END_FOR_EACH_PTR(member);
120 LLVMStructSetBody(ret, elem_types, nr, 0 /* packed? */);
121 return ret;
124 static LLVMTypeRef sym_union_type(LLVMModuleRef module, struct symbol *sym)
126 LLVMTypeRef elements;
127 unsigned union_size;
130 * There's no union support in the LLVM API so we treat unions as
131 * opaque structs. The downside is that we lose type information on the
132 * members but as LLVM doesn't care, neither do we.
134 union_size = sym->bit_size / 8;
136 elements = LLVMArrayType(LLVMInt8Type(), union_size);
138 return LLVMStructType(&elements, 1, 0 /* packed? */);
141 static LLVMTypeRef sym_ptr_type(LLVMModuleRef module, struct symbol *sym)
143 LLVMTypeRef type;
145 /* 'void *' is treated like 'char *' */
146 if (is_void_type(sym->ctype.base_type))
147 type = LLVMInt8Type();
148 else
149 type = symbol_type(module, sym->ctype.base_type);
151 return LLVMPointerType(type, 0);
154 static LLVMTypeRef sym_basetype_type(struct symbol *sym)
156 LLVMTypeRef ret = NULL;
158 if (symbol_is_fp_type(sym)) {
159 switch (sym->bit_size) {
160 case 32:
161 ret = LLVMFloatType();
162 break;
163 case 64:
164 ret = LLVMDoubleType();
165 break;
166 case 80:
167 ret = LLVMX86FP80Type();
168 break;
169 default:
170 die("invalid bit size %d for type %d", sym->bit_size, sym->type);
171 break;
173 } else {
174 switch (sym->bit_size) {
175 case -1:
176 ret = LLVMVoidType();
177 break;
178 case 1:
179 ret = LLVMInt1Type();
180 break;
181 case 8:
182 ret = LLVMInt8Type();
183 break;
184 case 16:
185 ret = LLVMInt16Type();
186 break;
187 case 32:
188 ret = LLVMInt32Type();
189 break;
190 case 64:
191 ret = LLVMInt64Type();
192 break;
193 default:
194 die("invalid bit size %d for type %d", sym->bit_size, sym->type);
195 break;
199 return ret;
202 static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym)
204 LLVMTypeRef ret = NULL;
206 /* don't cache the result for SYM_NODE */
207 if (sym->type == SYM_NODE)
208 return symbol_type(module, sym->ctype.base_type);
210 if (sym->aux)
211 return sym->aux;
213 switch (sym->type) {
214 case SYM_BITFIELD:
215 case SYM_ENUM:
216 ret = symbol_type(module, sym->ctype.base_type);
217 break;
218 case SYM_BASETYPE:
219 ret = sym_basetype_type(sym);
220 break;
221 case SYM_PTR:
222 ret = sym_ptr_type(module, sym);
223 break;
224 case SYM_UNION:
225 ret = sym_union_type(module, sym);
226 break;
227 case SYM_STRUCT:
228 ret = sym_struct_type(module, sym);
229 break;
230 case SYM_ARRAY:
231 ret = sym_array_type(module, sym);
232 break;
233 case SYM_FN:
234 ret = sym_func_type(module, sym);
235 break;
236 default:
237 assert(0);
240 /* cache the result */
241 sym->aux = ret;
242 return ret;
245 static LLVMTypeRef insn_symbol_type(LLVMModuleRef module, struct instruction *insn)
247 if (insn->type)
248 return symbol_type(module, insn->type);
250 switch (insn->size) {
251 case 8: return LLVMInt8Type();
252 case 16: return LLVMInt16Type();
253 case 32: return LLVMInt32Type();
254 case 64: return LLVMInt64Type();
256 default:
257 die("invalid bit size %d", insn->size);
258 break;
261 return NULL; /* not reached */
264 static LLVMLinkage data_linkage(struct symbol *sym)
266 if (sym->ctype.modifiers & MOD_STATIC)
267 return LLVMPrivateLinkage;
269 return LLVMExternalLinkage;
272 static LLVMLinkage function_linkage(struct symbol *sym)
274 if (sym->ctype.modifiers & MOD_STATIC)
275 return LLVMInternalLinkage;
277 return LLVMExternalLinkage;
280 #define MAX_PSEUDO_NAME 64
282 static void pseudo_name(pseudo_t pseudo, char *buf)
284 switch (pseudo->type) {
285 case PSEUDO_REG:
286 snprintf(buf, MAX_PSEUDO_NAME, "R%d", pseudo->nr);
287 break;
288 case PSEUDO_SYM:
289 assert(0);
290 break;
291 case PSEUDO_VAL:
292 assert(0);
293 break;
294 case PSEUDO_ARG: {
295 assert(0);
296 break;
298 case PSEUDO_PHI:
299 snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr);
300 break;
301 default:
302 assert(0);
306 static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo)
308 LLVMValueRef result = NULL;
310 switch (pseudo->type) {
311 case PSEUDO_REG:
312 result = pseudo->priv;
313 break;
314 case PSEUDO_SYM: {
315 struct symbol *sym = pseudo->sym;
316 struct expression *expr;
318 assert(sym->bb_target == NULL);
320 expr = sym->initializer;
321 if (expr) {
322 switch (expr->type) {
323 case EXPR_STRING: {
324 const char *s = expr->string->data;
325 LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) };
326 LLVMValueRef data;
328 data = LLVMAddGlobal(fn->module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str");
329 LLVMSetLinkage(data, LLVMPrivateLinkage);
330 LLVMSetGlobalConstant(data, 1);
331 LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true));
333 result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
334 break;
336 case EXPR_SYMBOL: {
337 struct symbol *sym = expr->symbol;
339 result = LLVMGetNamedGlobal(fn->module, show_ident(sym->ident));
340 assert(result != NULL);
341 break;
343 default:
344 assert(0);
346 } else {
347 const char *name = show_ident(sym->ident);
348 LLVMTypeRef type = symbol_type(fn->module, sym);
350 if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) {
351 result = LLVMGetNamedFunction(fn->module, name);
352 if (!result)
353 result = LLVMAddFunction(fn->module, name, type);
354 } else {
355 result = LLVMGetNamedGlobal(fn->module, name);
356 if (!result)
357 result = LLVMAddGlobal(fn->module, type, name);
360 break;
362 case PSEUDO_VAL:
363 result = LLVMConstInt(insn_symbol_type(fn->module, insn), pseudo->value, 1);
364 break;
365 case PSEUDO_ARG: {
366 result = LLVMGetParam(fn->fn, pseudo->nr - 1);
367 break;
369 case PSEUDO_PHI:
370 result = pseudo->priv;
371 break;
372 case PSEUDO_VOID:
373 result = NULL;
374 break;
375 default:
376 assert(0);
379 return result;
382 static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValueRef off)
384 LLVMTypeRef type = LLVMTypeOf(base);
385 unsigned int as = LLVMGetPointerAddressSpace(type);
386 LLVMTypeRef bytep = LLVMPointerType(LLVMInt8Type(), as);
387 LLVMValueRef addr;
389 /* convert base to char* type */
390 base = LLVMBuildPointerCast(builder, base, bytep, "");
391 /* addr = base + off */
392 addr = LLVMBuildInBoundsGEP(builder, base, &off, 1, "");
393 /* convert back to the actual pointer type */
394 addr = LLVMBuildPointerCast(builder, addr, type, "");
395 return addr;
398 static LLVMRealPredicate translate_fop(int opcode)
400 static const LLVMRealPredicate trans_tbl[] = {
401 [OP_SET_EQ] = LLVMRealOEQ,
402 [OP_SET_NE] = LLVMRealUNE,
403 [OP_SET_LE] = LLVMRealOLE,
404 [OP_SET_GE] = LLVMRealOGE,
405 [OP_SET_LT] = LLVMRealOLT,
406 [OP_SET_GT] = LLVMRealOGT,
407 /* Are these used with FP? */
408 [OP_SET_B] = LLVMRealOLT,
409 [OP_SET_A] = LLVMRealOGT,
410 [OP_SET_BE] = LLVMRealOLE,
411 [OP_SET_AE] = LLVMRealOGE,
414 return trans_tbl[opcode];
417 static LLVMIntPredicate translate_op(int opcode)
419 static const LLVMIntPredicate trans_tbl[] = {
420 [OP_SET_EQ] = LLVMIntEQ,
421 [OP_SET_NE] = LLVMIntNE,
422 [OP_SET_LE] = LLVMIntSLE,
423 [OP_SET_GE] = LLVMIntSGE,
424 [OP_SET_LT] = LLVMIntSLT,
425 [OP_SET_GT] = LLVMIntSGT,
426 [OP_SET_B] = LLVMIntULT,
427 [OP_SET_A] = LLVMIntUGT,
428 [OP_SET_BE] = LLVMIntULE,
429 [OP_SET_AE] = LLVMIntUGE,
432 return trans_tbl[opcode];
435 static void output_op_binary(struct function *fn, struct instruction *insn)
437 LLVMValueRef lhs, rhs, target;
438 char target_name[64];
440 lhs = pseudo_to_value(fn, insn, insn->src1);
442 rhs = pseudo_to_value(fn, insn, insn->src2);
444 pseudo_name(insn->target, target_name);
446 switch (insn->opcode) {
447 /* Binary */
448 case OP_ADD:
449 if (symbol_is_fp_type(insn->type))
450 target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name);
451 else
452 target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
453 break;
454 case OP_SUB:
455 if (symbol_is_fp_type(insn->type))
456 target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name);
457 else
458 target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
459 break;
460 case OP_MULU:
461 if (symbol_is_fp_type(insn->type))
462 target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name);
463 else
464 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
465 break;
466 case OP_MULS:
467 assert(!symbol_is_fp_type(insn->type));
468 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
469 break;
470 case OP_DIVU:
471 if (symbol_is_fp_type(insn->type))
472 target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name);
473 else
474 target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name);
475 break;
476 case OP_DIVS:
477 assert(!symbol_is_fp_type(insn->type));
478 target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
479 break;
480 case OP_MODU:
481 assert(!symbol_is_fp_type(insn->type));
482 target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
483 break;
484 case OP_MODS:
485 assert(!symbol_is_fp_type(insn->type));
486 target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
487 break;
488 case OP_SHL:
489 assert(!symbol_is_fp_type(insn->type));
490 target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
491 break;
492 case OP_LSR:
493 assert(!symbol_is_fp_type(insn->type));
494 target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
495 break;
496 case OP_ASR:
497 assert(!symbol_is_fp_type(insn->type));
498 target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
499 break;
501 /* Logical */
502 case OP_AND:
503 assert(!symbol_is_fp_type(insn->type));
504 target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
505 break;
506 case OP_OR:
507 assert(!symbol_is_fp_type(insn->type));
508 target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
509 break;
510 case OP_XOR:
511 assert(!symbol_is_fp_type(insn->type));
512 target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
513 break;
514 case OP_AND_BOOL: {
515 LLVMValueRef lhs_nz, rhs_nz;
516 LLVMTypeRef dst_type;
518 lhs_nz = LLVMBuildIsNotNull(fn->builder, lhs, "");
519 rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, "");
520 target = LLVMBuildAnd(fn->builder, lhs_nz, rhs_nz, target_name);
522 dst_type = insn_symbol_type(fn->module, insn);
523 target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
524 break;
526 case OP_OR_BOOL: {
527 LLVMValueRef lhs_nz, rhs_nz;
528 LLVMTypeRef dst_type;
530 lhs_nz = LLVMBuildIsNotNull(fn->builder, lhs, "");
531 rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, "");
532 target = LLVMBuildOr(fn->builder, lhs_nz, rhs_nz, target_name);
534 dst_type = insn_symbol_type(fn->module, insn);
535 target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
536 break;
539 /* Binary comparison */
540 case OP_BINCMP ... OP_BINCMP_END: {
541 LLVMTypeRef dst_type = insn_symbol_type(fn->module, insn);
543 if (LLVMGetTypeKind(LLVMTypeOf(lhs)) == LLVMIntegerTypeKind) {
544 LLVMIntPredicate op = translate_op(insn->opcode);
546 target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name);
547 } else {
548 LLVMRealPredicate op = translate_fop(insn->opcode);
550 target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name);
553 target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
554 break;
556 default:
557 assert(0);
558 break;
561 insn->target->priv = target;
564 static void output_op_ret(struct function *fn, struct instruction *insn)
566 pseudo_t pseudo = insn->src;
568 if (pseudo && pseudo != VOID) {
569 LLVMValueRef result = pseudo_to_value(fn, insn, pseudo);
571 LLVMBuildRet(fn->builder, result);
572 } else
573 LLVMBuildRetVoid(fn->builder);
576 static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *insn)
578 LLVMTypeRef int_type, addr_type;
579 LLVMValueRef src, off, addr;
580 unsigned int as;
582 /* int type large enough to hold a pointer */
583 int_type = LLVMIntType(bits_in_pointer);
584 off = LLVMConstInt(int_type, insn->offset, 0);
586 /* convert src to the effective pointer type */
587 src = pseudo_to_value(fn, insn, insn->src);
588 as = LLVMGetPointerAddressSpace(LLVMTypeOf(src));
589 addr_type = LLVMPointerType(insn_symbol_type(fn->module, insn), as);
590 src = LLVMBuildPointerCast(fn->builder, src, addr_type, "");
592 /* addr = src + off */
593 addr = calc_gep(fn->builder, src, off);
594 return addr;
598 static void output_op_load(struct function *fn, struct instruction *insn)
600 LLVMValueRef addr, target;
602 addr = calc_memop_addr(fn, insn);
604 /* perform load */
605 target = LLVMBuildLoad(fn->builder, addr, "load_target");
607 insn->target->priv = target;
610 static void output_op_store(struct function *fn, struct instruction *insn)
612 LLVMValueRef addr, target, target_in;
614 addr = calc_memop_addr(fn, insn);
616 target_in = pseudo_to_value(fn, insn, insn->target);
618 /* perform store */
619 target = LLVMBuildStore(fn->builder, target_in, addr);
621 insn->target->priv = target;
624 static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
626 if (LLVMTypeOf(value) != LLVMInt1Type())
627 value = LLVMBuildIsNotNull(fn->builder, value, "cond");
629 return value;
632 static void output_op_br(struct function *fn, struct instruction *br)
634 if (br->cond) {
635 LLVMValueRef cond = bool_value(fn,
636 pseudo_to_value(fn, br, br->cond));
638 LLVMBuildCondBr(fn->builder, cond,
639 br->bb_true->priv,
640 br->bb_false->priv);
641 } else
642 LLVMBuildBr(fn->builder,
643 br->bb_true ? br->bb_true->priv :
644 br->bb_false->priv);
647 static void output_op_sel(struct function *fn, struct instruction *insn)
649 LLVMValueRef target, src1, src2, src3;
651 src1 = bool_value(fn, pseudo_to_value(fn, insn, insn->src1));
652 src2 = pseudo_to_value(fn, insn, insn->src2);
653 src3 = pseudo_to_value(fn, insn, insn->src3);
655 target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select");
657 insn->target->priv = target;
660 static void output_op_switch(struct function *fn, struct instruction *insn)
662 LLVMValueRef sw_val, target;
663 struct basic_block *def = NULL;
664 struct multijmp *jmp;
665 int n_jmp = 0;
667 FOR_EACH_PTR(insn->multijmp_list, jmp) {
668 if (jmp->begin == jmp->end) { /* case N */
669 n_jmp++;
670 } else if (jmp->begin < jmp->end) { /* case M..N */
671 assert(0);
672 } else /* default case */
673 def = jmp->target;
674 } END_FOR_EACH_PTR(jmp);
676 sw_val = pseudo_to_value(fn, insn, insn->target);
677 target = LLVMBuildSwitch(fn->builder, sw_val,
678 def ? def->priv : NULL, n_jmp);
680 FOR_EACH_PTR(insn->multijmp_list, jmp) {
681 if (jmp->begin == jmp->end) { /* case N */
682 LLVMAddCase(target,
683 LLVMConstInt(LLVMInt32Type(), jmp->begin, 0),
684 jmp->target->priv);
685 } else if (jmp->begin < jmp->end) { /* case M..N */
686 assert(0);
688 } END_FOR_EACH_PTR(jmp);
690 insn->target->priv = target;
693 static void output_op_call(struct function *fn, struct instruction *insn)
695 LLVMValueRef target, func;
696 int n_arg = 0, i;
697 struct pseudo *arg;
698 LLVMValueRef *args;
700 FOR_EACH_PTR(insn->arguments, arg) {
701 n_arg++;
702 } END_FOR_EACH_PTR(arg);
704 args = calloc(n_arg, sizeof(LLVMValueRef));
706 i = 0;
707 FOR_EACH_PTR(insn->arguments, arg) {
708 args[i++] = pseudo_to_value(fn, insn, arg);
709 } END_FOR_EACH_PTR(arg);
711 func = pseudo_to_value(fn, insn, insn->func);
712 target = LLVMBuildCall(fn->builder, func, args, n_arg, "");
714 insn->target->priv = target;
717 static void output_op_phisrc(struct function *fn, struct instruction *insn)
719 LLVMValueRef v;
720 struct instruction *phi;
722 assert(insn->target->priv == NULL);
724 /* target = src */
725 v = pseudo_to_value(fn, insn, insn->phi_src);
727 FOR_EACH_PTR(insn->phi_users, phi) {
728 LLVMValueRef load, ptr;
730 assert(phi->opcode == OP_PHI);
731 /* phi must be load from alloca */
732 load = phi->target->priv;
733 assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
734 ptr = LLVMGetOperand(load, 0);
735 /* store v to alloca */
736 LLVMBuildStore(fn->builder, v, ptr);
737 } END_FOR_EACH_PTR(phi);
740 static void output_op_phi(struct function *fn, struct instruction *insn)
742 LLVMValueRef load = insn->target->priv;
744 /* forward load */
745 assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
746 /* forward load has no parent block */
747 assert(!LLVMGetInstructionParent(load));
748 /* finalize load in current block */
749 LLVMInsertIntoBuilder(fn->builder, load);
752 static void output_op_ptrcast(struct function *fn, struct instruction *insn)
754 LLVMValueRef src, target;
755 char target_name[64];
757 src = insn->src->priv;
758 if (!src)
759 src = pseudo_to_value(fn, insn, insn->src);
761 pseudo_name(insn->target, target_name);
763 assert(!symbol_is_fp_type(insn->type));
765 target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
767 insn->target->priv = target;
770 static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
772 LLVMValueRef src, target;
773 char target_name[64];
775 src = insn->src->priv;
776 if (!src)
777 src = pseudo_to_value(fn, insn, insn->src);
779 pseudo_name(insn->target, target_name);
781 assert(!symbol_is_fp_type(insn->type));
783 if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src)))
784 target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
785 else
786 target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(fn->module, insn), target_name);
788 insn->target->priv = target;
791 static void output_op_copy(struct function *fn, struct instruction *insn,
792 pseudo_t pseudo)
794 LLVMValueRef src, target;
795 LLVMTypeRef const_type;
796 char target_name[64];
798 pseudo_name(insn->target, target_name);
799 src = pseudo_to_value(fn, insn, pseudo);
800 const_type = insn_symbol_type(fn->module, insn);
803 * This is nothing more than 'target = src'
805 * TODO: find a better way to provide an identity function,
806 * than using "X + 0" simply to produce a new LLVM pseudo
809 if (symbol_is_fp_type(insn->type))
810 target = LLVMBuildFAdd(fn->builder, src,
811 LLVMConstReal(const_type, 0.0), target_name);
812 else
813 target = LLVMBuildAdd(fn->builder, src,
814 LLVMConstInt(const_type, 0, 0), target_name);
816 insn->target->priv = target;
819 static void output_insn(struct function *fn, struct instruction *insn)
821 switch (insn->opcode) {
822 case OP_RET:
823 output_op_ret(fn, insn);
824 break;
825 case OP_BR:
826 output_op_br(fn, insn);
827 break;
828 case OP_SYMADDR:
829 assert(0);
830 break;
831 case OP_SETVAL:
832 assert(0);
833 break;
834 case OP_SWITCH:
835 output_op_switch(fn, insn);
836 break;
837 case OP_COMPUTEDGOTO:
838 assert(0);
839 break;
840 case OP_PHISOURCE:
841 output_op_phisrc(fn, insn);
842 break;
843 case OP_PHI:
844 output_op_phi(fn, insn);
845 break;
846 case OP_LOAD:
847 output_op_load(fn, insn);
848 break;
849 case OP_LNOP:
850 assert(0);
851 break;
852 case OP_STORE:
853 output_op_store(fn, insn);
854 break;
855 case OP_SNOP:
856 assert(0);
857 break;
858 case OP_INLINED_CALL:
859 assert(0);
860 break;
861 case OP_CALL:
862 output_op_call(fn, insn);
863 break;
864 case OP_CAST:
865 output_op_cast(fn, insn, LLVMZExt);
866 break;
867 case OP_SCAST:
868 output_op_cast(fn, insn, LLVMSExt);
869 break;
870 case OP_FPCAST:
871 assert(0);
872 break;
873 case OP_PTRCAST:
874 output_op_ptrcast(fn, insn);
875 break;
876 case OP_BINARY ... OP_BINARY_END:
877 case OP_BINCMP ... OP_BINCMP_END:
878 output_op_binary(fn, insn);
879 break;
880 case OP_SEL:
881 output_op_sel(fn, insn);
882 break;
883 case OP_SLICE:
884 assert(0);
885 break;
886 case OP_NOT: {
887 LLVMValueRef src, target;
888 char target_name[64];
890 src = pseudo_to_value(fn, insn, insn->src);
892 pseudo_name(insn->target, target_name);
894 target = LLVMBuildNot(fn->builder, src, target_name);
896 insn->target->priv = target;
897 break;
899 case OP_NEG:
900 assert(0);
901 break;
902 case OP_CONTEXT:
903 assert(0);
904 break;
905 case OP_RANGE:
906 assert(0);
907 break;
908 case OP_NOP:
909 assert(0);
910 break;
911 case OP_DEATHNOTE:
912 break;
913 case OP_ASM:
914 assert(0);
915 break;
916 case OP_COPY:
917 output_op_copy(fn, insn, insn->src);
918 break;
919 default:
920 break;
924 static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation)
926 struct instruction *insn;
928 bb->generation = generation;
930 FOR_EACH_PTR(bb->insns, insn) {
931 if (!insn->bb)
932 continue;
934 output_insn(fn, insn);
936 END_FOR_EACH_PTR(insn);
939 #define MAX_ARGS 64
941 static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
943 unsigned long generation = ++bb_generation;
944 struct symbol *sym = ep->name;
945 struct symbol *base_type = sym->ctype.base_type;
946 struct symbol *ret_type = sym->ctype.base_type->ctype.base_type;
947 LLVMTypeRef arg_types[MAX_ARGS];
948 LLVMTypeRef return_type;
949 struct function function = { .module = module };
950 struct basic_block *bb;
951 struct symbol *arg;
952 const char *name;
953 int nr_args = 0;
955 FOR_EACH_PTR(base_type->arguments, arg) {
956 struct symbol *arg_base_type = arg->ctype.base_type;
958 arg_types[nr_args++] = symbol_type(module, arg_base_type);
959 } END_FOR_EACH_PTR(arg);
961 name = show_ident(sym->ident);
963 return_type = symbol_type(module, ret_type);
965 function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0);
967 function.fn = LLVMAddFunction(module, name, function.type);
968 LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
970 LLVMSetLinkage(function.fn, function_linkage(sym));
972 function.builder = LLVMCreateBuilder();
974 static int nr_bb;
976 FOR_EACH_PTR(ep->bbs, bb) {
977 if (bb->generation == generation)
978 continue;
980 LLVMBasicBlockRef bbr;
981 char bbname[32];
982 struct instruction *insn;
984 sprintf(bbname, "L%d", nr_bb++);
985 bbr = LLVMAppendBasicBlock(function.fn, bbname);
987 bb->priv = bbr;
989 /* allocate alloca for each phi */
990 FOR_EACH_PTR(bb->insns, insn) {
991 LLVMBasicBlockRef entrybbr;
992 LLVMTypeRef phi_type;
993 LLVMValueRef ptr;
995 if (!insn->bb || insn->opcode != OP_PHI)
996 continue;
997 /* insert alloca into entry block */
998 entrybbr = LLVMGetEntryBasicBlock(function.fn);
999 LLVMPositionBuilderAtEnd(function.builder, entrybbr);
1000 phi_type = insn_symbol_type(module, insn);
1001 ptr = LLVMBuildAlloca(function.builder, phi_type, "");
1002 /* emit forward load for phi */
1003 LLVMClearInsertionPosition(function.builder);
1004 insn->target->priv = LLVMBuildLoad(function.builder, ptr, "phi");
1005 } END_FOR_EACH_PTR(insn);
1007 END_FOR_EACH_PTR(bb);
1009 FOR_EACH_PTR(ep->bbs, bb) {
1010 if (bb->generation == generation)
1011 continue;
1013 LLVMPositionBuilderAtEnd(function.builder, bb->priv);
1015 output_bb(&function, bb, generation);
1017 END_FOR_EACH_PTR(bb);
1020 static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
1022 struct expression *initializer = sym->initializer;
1023 LLVMValueRef initial_value;
1024 LLVMValueRef data;
1025 const char *name;
1027 if (initializer) {
1028 switch (initializer->type) {
1029 case EXPR_VALUE:
1030 initial_value = LLVMConstInt(symbol_type(module, sym), initializer->value, 1);
1031 break;
1032 case EXPR_SYMBOL: {
1033 struct symbol *sym = initializer->symbol;
1035 initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident));
1036 if (!initial_value)
1037 initial_value = output_data(module, sym);
1038 break;
1040 case EXPR_STRING: {
1041 const char *s = initializer->string->data;
1043 initial_value = LLVMConstString(strdup(s), strlen(s) + 1, true);
1044 break;
1046 default:
1047 assert(0);
1049 } else {
1050 LLVMTypeRef type = symbol_type(module, sym);
1052 initial_value = LLVMConstNull(type);
1055 name = show_ident(sym->ident);
1057 data = LLVMAddGlobal(module, LLVMTypeOf(initial_value), name);
1059 LLVMSetLinkage(data, data_linkage(sym));
1060 if (sym->ctype.modifiers & MOD_CONST)
1061 LLVMSetGlobalConstant(data, 1);
1062 if (sym->ctype.modifiers & MOD_TLS)
1063 LLVMSetThreadLocal(data, 1);
1064 if (sym->ctype.alignment)
1065 LLVMSetAlignment(data, sym->ctype.alignment);
1067 if (!(sym->ctype.modifiers & MOD_EXTERN))
1068 LLVMSetInitializer(data, initial_value);
1070 return data;
1073 static int compile(LLVMModuleRef module, struct symbol_list *list)
1075 struct symbol *sym;
1077 FOR_EACH_PTR(list, sym) {
1078 struct entrypoint *ep;
1079 expand_symbol(sym);
1080 ep = linearize_symbol(sym);
1081 if (ep)
1082 output_fn(module, ep);
1083 else
1084 output_data(module, sym);
1086 END_FOR_EACH_PTR(sym);
1088 return 0;
1091 #ifndef LLVM_DEFAULT_TARGET_TRIPLE
1092 #define LLVM_DEFAULT_TARGET_TRIPLE LLVM_HOSTTRIPLE
1093 #endif
1095 #define X86_LINUX_LAYOUT \
1096 "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
1097 "i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-" \
1098 "a0:0:64-f80:32:32-n8:16:32-S128"
1100 #define X86_64_LINUX_LAYOUT \
1101 "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
1102 "i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-" \
1103 "a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
1105 static void set_target(LLVMModuleRef module)
1107 char target[] = LLVM_DEFAULT_TARGET_TRIPLE;
1108 const char *arch, *vendor, *os, *env, *layout = NULL;
1109 char triple[256];
1111 arch = strtok(target, "-");
1112 vendor = strtok(NULL, "-");
1113 os = strtok(NULL, "-");
1114 env = strtok(NULL, "-");
1116 if (!os)
1117 return;
1118 if (!env)
1119 env = "unknown";
1121 if (!strcmp(arch, "x86_64") && !strcmp(os, "linux")) {
1122 if (arch_m64) {
1123 layout = X86_64_LINUX_LAYOUT;
1124 } else {
1125 arch = "i386";
1126 layout = X86_LINUX_LAYOUT;
1130 /* unsupported target */
1131 if (!layout)
1132 return;
1134 snprintf(triple, sizeof(triple), "%s-%s-%s-%s", arch, vendor, os, env);
1135 LLVMSetTarget(module, triple);
1136 LLVMSetDataLayout(module, layout);
1139 int main(int argc, char **argv)
1141 struct string_list *filelist = NULL;
1142 struct symbol_list *symlist;
1143 LLVMModuleRef module;
1144 char *file;
1146 symlist = sparse_initialize(argc, argv, &filelist);
1148 module = LLVMModuleCreateWithName("sparse");
1149 set_target(module);
1151 compile(module, symlist);
1153 /* need ->phi_users */
1154 dbg_dead = 1;
1155 FOR_EACH_PTR_NOTAG(filelist, file) {
1156 symlist = sparse(file);
1157 if (die_if_error)
1158 return 1;
1159 compile(module, symlist);
1160 } END_FOR_EACH_PTR_NOTAG(file);
1162 LLVMVerifyModule(module, LLVMPrintMessageAction, NULL);
1164 LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);
1166 LLVMDisposeModule(module);
1168 return 0;