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
22 struct function {
23 LLVMBuilderRef builder;
24 LLVMValueRef fn;
25 LLVMModuleRef module;
26 };
27
28 static LLVMTypeRef symbol_type(struct symbol *sym);
29
func_return_type(struct symbol * sym)30 static LLVMTypeRef func_return_type(struct symbol *sym)
31 {
32 return symbol_type(sym->ctype.base_type);
33 }
34
sym_func_type(struct symbol * sym)35 static 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
sym_array_type(struct symbol * sym)52 static 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
sym_struct_type(struct symbol * sym)70 static 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
sym_union_type(struct symbol * sym)97 static 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
sym_ptr_type(struct symbol * sym)114 static 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
sym_basetype_type(struct symbol * sym)127 static 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
symbol_type(struct symbol * sym)175 static 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
insn_symbol_type(struct instruction * insn)221 static 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
data_linkage(struct symbol * sym)240 static LLVMLinkage data_linkage(struct symbol *sym)
241 {
242 if (sym->ctype.modifiers & MOD_STATIC)
243 return LLVMPrivateLinkage;
244
245 return LLVMExternalLinkage;
246 }
247
function_linkage(struct symbol * sym)248 static 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
pseudo_name(pseudo_t pseudo,char * buf)258 static 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
get_sym_value(LLVMModuleRef module,struct symbol * sym)283 static 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
constant_value(unsigned long long val,LLVMTypeRef dtype)326 static 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
val_to_value(unsigned long long val,struct symbol * ctype)355 static 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
pseudo_to_value(struct function * fn,struct symbol * ctype,pseudo_t pseudo)369 static 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
pseudo_to_rvalue(struct function * fn,struct symbol * ctype,pseudo_t pseudo)403 static 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
value_to_ivalue(struct function * fn,struct symbol * ctype,LLVMValueRef val)413 static 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
value_to_pvalue(struct function * fn,struct symbol * ctype,LLVMValueRef val)428 static 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
adjust_type(struct function * fn,struct symbol * ctype,LLVMValueRef val)447 static 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 */
get_operand(struct function * fn,struct symbol * ctype,pseudo_t pseudo)460 static 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 */
get_ioperand(struct function * fn,struct symbol * ctype,pseudo_t pseudo)471 static 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
calc_gep(LLVMBuilderRef builder,LLVMValueRef base,LLVMValueRef off)477 static 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
translate_fop(int opcode)494 static 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
translate_op(int opcode)516 static 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
output_op_binary(struct function * fn,struct instruction * insn)534 static 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
output_op_compare(struct function * fn,struct instruction * insn)619 static 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
output_op_ret(struct function * fn,struct instruction * insn)672 static 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
calc_memop_addr(struct function * fn,struct instruction * insn)683 static 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
output_op_load(struct function * fn,struct instruction * insn)705 static 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
output_op_store(struct function * fn,struct instruction * insn)719 static 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
bool_value(struct function * fn,LLVMValueRef value)731 static 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
output_op_cbr(struct function * fn,struct instruction * br)739 static 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
output_op_br(struct function * fn,struct instruction * br)749 static void output_op_br(struct function *fn, struct instruction *br)
750 {
751 LLVMBuildBr(fn->builder, br->bb_true->priv);
752 }
753
output_op_sel(struct function * fn,struct instruction * insn)754 static 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
output_op_switch(struct function * fn,struct instruction * insn)769 static 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
output_op_call(struct function * fn,struct instruction * insn)797 static 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
output_op_phisrc(struct function * fn,struct instruction * insn)827 static void output_op_phisrc(struct function *fn, struct instruction *insn)
828 {
829 insn->src->priv = get_operand(fn, insn->type, insn->src);
830 }
831
output_op_phi(struct function * fn,struct instruction * insn)832 static 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
output_op_ptrcast(struct function * fn,struct instruction * insn)839 static 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
output_op_cast(struct function * fn,struct instruction * insn,LLVMOpcode op)877 static 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
output_op_fpcast(struct function * fn,struct instruction * insn)911 static 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
output_op_label(struct function * fn,struct instruction * insn)938 static void output_op_label(struct function *fn, struct instruction *insn)
939 {
940 insn->target->priv = LLVMBlockAddress(fn->fn, insn->bb_true->priv);
941 }
942
output_op_setval(struct function * fn,struct instruction * insn)943 static 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
output_op_setfval(struct function * fn,struct instruction * insn)959 static 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
output_insn(struct function * fn,struct instruction * insn)968 static 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
output_bb(struct function * fn,struct basic_block * bb)1103 static 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
output_fn(LLVMModuleRef module,struct entrypoint * ep)1118 static 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
output_data(LLVMModuleRef module,struct symbol * sym)1190 static 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
is_prototype(struct symbol * sym)1251 static 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
compile(LLVMModuleRef module,struct symbol_list * list)1258 static 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
set_target(LLVMModuleRef module)1297 static 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
main(int argc,char ** argv)1331 int 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