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 LLVMTypeRef type; 25 LLVMValueRef fn; 26 LLVMModuleRef module; 27 }; 28 29 static inline bool symbol_is_fp_type(struct symbol *sym) 30 { 31 if (!sym) 32 return false; 33 34 return sym->ctype.base_type == &fp_type; 35 } 36 37 static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym); 38 39 static LLVMTypeRef func_return_type(LLVMModuleRef module, struct symbol *sym) 40 { 41 return symbol_type(module, sym->ctype.base_type); 42 } 43 44 static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym) 45 { 46 LLVMTypeRef *arg_type; 47 LLVMTypeRef func_type; 48 LLVMTypeRef ret_type; 49 struct symbol *arg; 50 int n_arg = 0; 51 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. 56 */ 57 58 ret_type = func_return_type(module, sym); 59 60 /* count args, build argument type information */ 61 FOR_EACH_PTR(sym->arguments, arg) { 62 n_arg++; 63 } END_FOR_EACH_PTR(arg); 64 65 arg_type = calloc(n_arg, sizeof(LLVMTypeRef)); 66 67 int idx = 0; 68 FOR_EACH_PTR(sym->arguments, arg) { 69 struct symbol *arg_sym = arg->ctype.base_type; 70 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); 75 76 return func_type; 77 } 78 79 static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym) 80 { 81 LLVMTypeRef elem_type; 82 struct symbol *base_type; 83 84 base_type = sym->ctype.base_type; 85 /* empty struct is undefined [6.7.2.1(8)] */ 86 assert(base_type->bit_size > 0); 87 88 elem_type = symbol_type(module, base_type); 89 if (!elem_type) 90 return NULL; 91 92 return LLVMArrayType(elem_type, sym->bit_size / base_type->bit_size); 93 } 94 95 #define MAX_STRUCT_MEMBERS 64 96 97 static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym) 98 { 99 LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS]; 100 struct symbol *member; 101 char buffer[256]; 102 LLVMTypeRef ret; 103 unsigned nr = 0; 104 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; 109 110 FOR_EACH_PTR(sym->symbol_list, member) { 111 LLVMTypeRef member_type; 112 113 assert(nr < MAX_STRUCT_MEMBERS); 114 115 member_type = symbol_type(module, member); 116 117 elem_types[nr++] = member_type; 118 } END_FOR_EACH_PTR(member); 119 120 LLVMStructSetBody(ret, elem_types, nr, 0 /* packed? */); 121 return ret; 122 } 123 124 static LLVMTypeRef sym_union_type(LLVMModuleRef module, struct symbol *sym) 125 { 126 LLVMTypeRef elements; 127 unsigned union_size; 128 129 /* 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. 133 */ 134 union_size = sym->bit_size / 8; 135 136 elements = LLVMArrayType(LLVMInt8Type(), union_size); 137 138 return LLVMStructType(&elements, 1, 0 /* packed? */); 139 } 140 141 static LLVMTypeRef sym_ptr_type(LLVMModuleRef module, struct symbol *sym) 142 { 143 LLVMTypeRef type; 144 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); 150 151 return LLVMPointerType(type, 0); 152 } 153 154 static LLVMTypeRef sym_basetype_type(struct symbol *sym) 155 { 156 LLVMTypeRef ret = NULL; 157 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; 172 } 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; 196 } 197 } 198 199 return ret; 200 } 201 202 static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym) 203 { 204 LLVMTypeRef ret = NULL; 205 206 /* don't cache the result for SYM_NODE */ 207 if (sym->type == SYM_NODE) 208 return symbol_type(module, sym->ctype.base_type); 209 210 if (sym->aux) 211 return sym->aux; 212 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); 238 } 239 240 /* cache the result */ 241 sym->aux = ret; 242 return ret; 243 } 244 245 static LLVMTypeRef int_type_by_size(int size) 246 { 247 switch (size) { 248 case 1: return LLVMInt1Type(); 249 case 8: return LLVMInt8Type(); 250 case 16: return LLVMInt16Type(); 251 case 32: return LLVMInt32Type(); 252 case 64: return LLVMInt64Type(); 253 254 default: 255 die("invalid bit size %d", size); 256 break; 257 } 258 return NULL; /* not reached */ 259 } 260 261 static LLVMTypeRef insn_symbol_type(LLVMModuleRef module, struct instruction *insn) 262 { 263 if (insn->type) 264 return symbol_type(module, insn->type); 265 266 return int_type_by_size(insn->size); 267 } 268 269 static LLVMLinkage data_linkage(struct symbol *sym) 270 { 271 if (sym->ctype.modifiers & MOD_STATIC) 272 return LLVMPrivateLinkage; 273 274 return LLVMExternalLinkage; 275 } 276 277 static LLVMLinkage function_linkage(struct symbol *sym) 278 { 279 if (sym->ctype.modifiers & MOD_STATIC) 280 return LLVMInternalLinkage; 281 282 return LLVMExternalLinkage; 283 } 284 285 #define MAX_PSEUDO_NAME 64 286 287 static void pseudo_name(pseudo_t pseudo, char *buf) 288 { 289 switch (pseudo->type) { 290 case PSEUDO_REG: 291 snprintf(buf, MAX_PSEUDO_NAME, "R%d", pseudo->nr); 292 break; 293 case PSEUDO_SYM: 294 assert(0); 295 break; 296 case PSEUDO_VAL: 297 assert(0); 298 break; 299 case PSEUDO_ARG: { 300 assert(0); 301 break; 302 } 303 case PSEUDO_PHI: 304 snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr); 305 break; 306 default: 307 assert(0); 308 } 309 } 310 311 static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo) 312 { 313 LLVMValueRef result = NULL; 314 315 switch (pseudo->type) { 316 case PSEUDO_REG: 317 result = pseudo->priv; 318 break; 319 case PSEUDO_SYM: { 320 struct symbol *sym = pseudo->sym; 321 struct expression *expr; 322 323 assert(sym->bb_target == NULL); 324 325 expr = sym->initializer; 326 if (expr) { 327 switch (expr->type) { 328 case EXPR_STRING: { 329 const char *s = expr->string->data; 330 LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) }; 331 LLVMValueRef data; 332 333 data = LLVMAddGlobal(fn->module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str"); 334 LLVMSetLinkage(data, LLVMPrivateLinkage); 335 LLVMSetGlobalConstant(data, 1); 336 LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true)); 337 338 result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices)); 339 break; 340 } 341 case EXPR_SYMBOL: { 342 struct symbol *sym = expr->symbol; 343 344 result = LLVMGetNamedGlobal(fn->module, show_ident(sym->ident)); 345 assert(result != NULL); 346 break; 347 } 348 default: 349 assert(0); 350 } 351 } else { 352 const char *name = show_ident(sym->ident); 353 LLVMTypeRef type = symbol_type(fn->module, sym); 354 355 if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) { 356 result = LLVMGetNamedFunction(fn->module, name); 357 if (!result) 358 result = LLVMAddFunction(fn->module, name, type); 359 } else { 360 result = LLVMGetNamedGlobal(fn->module, name); 361 if (!result) 362 result = LLVMAddGlobal(fn->module, type, name); 363 } 364 } 365 break; 366 } 367 case PSEUDO_VAL: 368 result = LLVMConstInt(int_type_by_size(pseudo->size), pseudo->value, 1); 369 break; 370 case PSEUDO_ARG: { 371 result = LLVMGetParam(fn->fn, pseudo->nr - 1); 372 break; 373 } 374 case PSEUDO_PHI: 375 result = pseudo->priv; 376 break; 377 case PSEUDO_VOID: 378 result = NULL; 379 break; 380 default: 381 assert(0); 382 } 383 384 return result; 385 } 386 387 static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValueRef off) 388 { 389 LLVMTypeRef type = LLVMTypeOf(base); 390 unsigned int as = LLVMGetPointerAddressSpace(type); 391 LLVMTypeRef bytep = LLVMPointerType(LLVMInt8Type(), as); 392 LLVMValueRef addr; 393 394 /* convert base to char* type */ 395 base = LLVMBuildPointerCast(builder, base, bytep, ""); 396 /* addr = base + off */ 397 addr = LLVMBuildInBoundsGEP(builder, base, &off, 1, ""); 398 /* convert back to the actual pointer type */ 399 addr = LLVMBuildPointerCast(builder, addr, type, ""); 400 return addr; 401 } 402 403 static LLVMRealPredicate translate_fop(int opcode) 404 { 405 static const LLVMRealPredicate trans_tbl[] = { 406 [OP_SET_EQ] = LLVMRealOEQ, 407 [OP_SET_NE] = LLVMRealUNE, 408 [OP_SET_LE] = LLVMRealOLE, 409 [OP_SET_GE] = LLVMRealOGE, 410 [OP_SET_LT] = LLVMRealOLT, 411 [OP_SET_GT] = LLVMRealOGT, 412 /* Are these used with FP? */ 413 [OP_SET_B] = LLVMRealOLT, 414 [OP_SET_A] = LLVMRealOGT, 415 [OP_SET_BE] = LLVMRealOLE, 416 [OP_SET_AE] = LLVMRealOGE, 417 }; 418 419 return trans_tbl[opcode]; 420 } 421 422 static LLVMIntPredicate translate_op(int opcode) 423 { 424 static const LLVMIntPredicate trans_tbl[] = { 425 [OP_SET_EQ] = LLVMIntEQ, 426 [OP_SET_NE] = LLVMIntNE, 427 [OP_SET_LE] = LLVMIntSLE, 428 [OP_SET_GE] = LLVMIntSGE, 429 [OP_SET_LT] = LLVMIntSLT, 430 [OP_SET_GT] = LLVMIntSGT, 431 [OP_SET_B] = LLVMIntULT, 432 [OP_SET_A] = LLVMIntUGT, 433 [OP_SET_BE] = LLVMIntULE, 434 [OP_SET_AE] = LLVMIntUGE, 435 }; 436 437 return trans_tbl[opcode]; 438 } 439 440 static void output_op_binary(struct function *fn, struct instruction *insn) 441 { 442 LLVMValueRef lhs, rhs, target; 443 char target_name[64]; 444 445 lhs = pseudo_to_value(fn, insn, insn->src1); 446 447 rhs = pseudo_to_value(fn, insn, insn->src2); 448 449 pseudo_name(insn->target, target_name); 450 451 switch (insn->opcode) { 452 /* Binary */ 453 case OP_ADD: 454 if (symbol_is_fp_type(insn->type)) 455 target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name); 456 else 457 target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name); 458 break; 459 case OP_SUB: 460 if (symbol_is_fp_type(insn->type)) 461 target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name); 462 else 463 target = LLVMBuildSub(fn->builder, lhs, rhs, target_name); 464 break; 465 case OP_MULU: 466 if (symbol_is_fp_type(insn->type)) 467 target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name); 468 else 469 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name); 470 break; 471 case OP_MULS: 472 assert(!symbol_is_fp_type(insn->type)); 473 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name); 474 break; 475 case OP_DIVU: 476 if (symbol_is_fp_type(insn->type)) 477 target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name); 478 else 479 target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name); 480 break; 481 case OP_DIVS: 482 assert(!symbol_is_fp_type(insn->type)); 483 target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name); 484 break; 485 case OP_MODU: 486 assert(!symbol_is_fp_type(insn->type)); 487 target = LLVMBuildURem(fn->builder, lhs, rhs, target_name); 488 break; 489 case OP_MODS: 490 assert(!symbol_is_fp_type(insn->type)); 491 target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name); 492 break; 493 case OP_SHL: 494 assert(!symbol_is_fp_type(insn->type)); 495 target = LLVMBuildShl(fn->builder, lhs, rhs, target_name); 496 break; 497 case OP_LSR: 498 assert(!symbol_is_fp_type(insn->type)); 499 target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name); 500 break; 501 case OP_ASR: 502 assert(!symbol_is_fp_type(insn->type)); 503 target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name); 504 break; 505 506 /* Logical */ 507 case OP_AND: 508 assert(!symbol_is_fp_type(insn->type)); 509 target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name); 510 break; 511 case OP_OR: 512 assert(!symbol_is_fp_type(insn->type)); 513 target = LLVMBuildOr(fn->builder, lhs, rhs, target_name); 514 break; 515 case OP_XOR: 516 assert(!symbol_is_fp_type(insn->type)); 517 target = LLVMBuildXor(fn->builder, lhs, rhs, target_name); 518 break; 519 case OP_AND_BOOL: { 520 LLVMValueRef lhs_nz, rhs_nz; 521 LLVMTypeRef dst_type; 522 523 lhs_nz = LLVMBuildIsNotNull(fn->builder, lhs, ""); 524 rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, ""); 525 target = LLVMBuildAnd(fn->builder, lhs_nz, rhs_nz, target_name); 526 527 dst_type = insn_symbol_type(fn->module, insn); 528 target = LLVMBuildZExt(fn->builder, target, dst_type, target_name); 529 break; 530 } 531 case OP_OR_BOOL: { 532 LLVMValueRef lhs_nz, rhs_nz; 533 LLVMTypeRef dst_type; 534 535 lhs_nz = LLVMBuildIsNotNull(fn->builder, lhs, ""); 536 rhs_nz = LLVMBuildIsNotNull(fn->builder, rhs, ""); 537 target = LLVMBuildOr(fn->builder, lhs_nz, rhs_nz, target_name); 538 539 dst_type = insn_symbol_type(fn->module, insn); 540 target = LLVMBuildZExt(fn->builder, target, dst_type, target_name); 541 break; 542 } 543 default: 544 assert(0); 545 break; 546 } 547 548 insn->target->priv = target; 549 } 550 551 static void output_op_compare(struct function *fn, struct instruction *insn) 552 { 553 LLVMValueRef lhs, rhs, target; 554 char target_name[64]; 555 556 lhs = pseudo_to_value(fn, insn, insn->src1); 557 558 if (insn->src2->type == PSEUDO_VAL) 559 rhs = LLVMConstInt(LLVMTypeOf(lhs), insn->src2->value, 1); 560 else 561 rhs = pseudo_to_value(fn, insn, insn->src2); 562 563 pseudo_name(insn->target, target_name); 564 565 LLVMTypeRef dst_type = insn_symbol_type(fn->module, insn); 566 567 if (LLVMGetTypeKind(LLVMTypeOf(lhs)) == LLVMIntegerTypeKind) { 568 LLVMIntPredicate op = translate_op(insn->opcode); 569 570 target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name); 571 } else { 572 LLVMRealPredicate op = translate_fop(insn->opcode); 573 574 target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name); 575 } 576 577 target = LLVMBuildZExt(fn->builder, target, dst_type, target_name); 578 579 insn->target->priv = target; 580 } 581 582 static void output_op_ret(struct function *fn, struct instruction *insn) 583 { 584 pseudo_t pseudo = insn->src; 585 586 if (pseudo && pseudo != VOID) { 587 LLVMValueRef result = pseudo_to_value(fn, insn, pseudo); 588 589 LLVMBuildRet(fn->builder, result); 590 } else 591 LLVMBuildRetVoid(fn->builder); 592 } 593 594 static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *insn) 595 { 596 LLVMTypeRef int_type, addr_type; 597 LLVMValueRef src, off, addr; 598 unsigned int as; 599 600 /* int type large enough to hold a pointer */ 601 int_type = LLVMIntType(bits_in_pointer); 602 off = LLVMConstInt(int_type, insn->offset, 0); 603 604 /* convert src to the effective pointer type */ 605 src = pseudo_to_value(fn, insn, insn->src); 606 as = LLVMGetPointerAddressSpace(LLVMTypeOf(src)); 607 addr_type = LLVMPointerType(insn_symbol_type(fn->module, insn), as); 608 src = LLVMBuildPointerCast(fn->builder, src, addr_type, ""); 609 610 /* addr = src + off */ 611 addr = calc_gep(fn->builder, src, off); 612 return addr; 613 } 614 615 616 static void output_op_load(struct function *fn, struct instruction *insn) 617 { 618 LLVMValueRef addr, target; 619 620 addr = calc_memop_addr(fn, insn); 621 622 /* perform load */ 623 target = LLVMBuildLoad(fn->builder, addr, "load_target"); 624 625 insn->target->priv = target; 626 } 627 628 static void output_op_store(struct function *fn, struct instruction *insn) 629 { 630 LLVMValueRef addr, target, target_in; 631 632 addr = calc_memop_addr(fn, insn); 633 634 target_in = pseudo_to_value(fn, insn, insn->target); 635 636 /* perform store */ 637 target = LLVMBuildStore(fn->builder, target_in, addr); 638 639 insn->target->priv = target; 640 } 641 642 static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value) 643 { 644 if (LLVMTypeOf(value) != LLVMInt1Type()) 645 value = LLVMBuildIsNotNull(fn->builder, value, "cond"); 646 647 return value; 648 } 649 650 static void output_op_cbr(struct function *fn, struct instruction *br) 651 { 652 LLVMValueRef cond = bool_value(fn, 653 pseudo_to_value(fn, br, br->cond)); 654 655 LLVMBuildCondBr(fn->builder, cond, 656 br->bb_true->priv, 657 br->bb_false->priv); 658 } 659 660 static void output_op_br(struct function *fn, struct instruction *br) 661 { 662 LLVMBuildBr(fn->builder, br->bb_true->priv); 663 } 664 665 static void output_op_sel(struct function *fn, struct instruction *insn) 666 { 667 LLVMValueRef target, src1, src2, src3; 668 669 src1 = bool_value(fn, pseudo_to_value(fn, insn, insn->src1)); 670 src2 = pseudo_to_value(fn, insn, insn->src2); 671 src3 = pseudo_to_value(fn, insn, insn->src3); 672 673 target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select"); 674 675 insn->target->priv = target; 676 } 677 678 static void output_op_switch(struct function *fn, struct instruction *insn) 679 { 680 LLVMValueRef sw_val, target; 681 struct basic_block *def = NULL; 682 struct multijmp *jmp; 683 int n_jmp = 0; 684 685 FOR_EACH_PTR(insn->multijmp_list, jmp) { 686 if (jmp->begin == jmp->end) { /* case N */ 687 n_jmp++; 688 } else if (jmp->begin < jmp->end) { /* case M..N */ 689 assert(0); 690 } else /* default case */ 691 def = jmp->target; 692 } END_FOR_EACH_PTR(jmp); 693 694 sw_val = pseudo_to_value(fn, insn, insn->target); 695 target = LLVMBuildSwitch(fn->builder, sw_val, 696 def ? def->priv : NULL, n_jmp); 697 698 FOR_EACH_PTR(insn->multijmp_list, jmp) { 699 if (jmp->begin == jmp->end) { /* case N */ 700 LLVMAddCase(target, 701 LLVMConstInt(LLVMInt32Type(), jmp->begin, 0), 702 jmp->target->priv); 703 } else if (jmp->begin < jmp->end) { /* case M..N */ 704 assert(0); 705 } 706 } END_FOR_EACH_PTR(jmp); 707 708 insn->target->priv = target; 709 } 710 711 static void output_op_call(struct function *fn, struct instruction *insn) 712 { 713 LLVMValueRef target, func; 714 int n_arg = 0, i; 715 struct pseudo *arg; 716 LLVMValueRef *args; 717 718 FOR_EACH_PTR(insn->arguments, arg) { 719 n_arg++; 720 } END_FOR_EACH_PTR(arg); 721 722 args = calloc(n_arg, sizeof(LLVMValueRef)); 723 724 i = 0; 725 FOR_EACH_PTR(insn->arguments, arg) { 726 args[i++] = pseudo_to_value(fn, insn, arg); 727 } END_FOR_EACH_PTR(arg); 728 729 func = pseudo_to_value(fn, insn, insn->func); 730 target = LLVMBuildCall(fn->builder, func, args, n_arg, ""); 731 732 insn->target->priv = target; 733 } 734 735 static void output_op_phisrc(struct function *fn, struct instruction *insn) 736 { 737 LLVMValueRef v; 738 struct instruction *phi; 739 740 assert(insn->target->priv == NULL); 741 742 /* target = src */ 743 v = pseudo_to_value(fn, insn, insn->phi_src); 744 745 FOR_EACH_PTR(insn->phi_users, phi) { 746 LLVMValueRef load, ptr; 747 748 assert(phi->opcode == OP_PHI); 749 /* phi must be load from alloca */ 750 load = phi->target->priv; 751 assert(LLVMGetInstructionOpcode(load) == LLVMLoad); 752 ptr = LLVMGetOperand(load, 0); 753 /* store v to alloca */ 754 LLVMBuildStore(fn->builder, v, ptr); 755 } END_FOR_EACH_PTR(phi); 756 } 757 758 static void output_op_phi(struct function *fn, struct instruction *insn) 759 { 760 LLVMValueRef load = insn->target->priv; 761 762 /* forward load */ 763 assert(LLVMGetInstructionOpcode(load) == LLVMLoad); 764 /* forward load has no parent block */ 765 assert(!LLVMGetInstructionParent(load)); 766 /* finalize load in current block */ 767 LLVMInsertIntoBuilder(fn->builder, load); 768 } 769 770 static void output_op_ptrcast(struct function *fn, struct instruction *insn) 771 { 772 LLVMValueRef src, target; 773 char target_name[64]; 774 775 src = insn->src->priv; 776 if (!src) 777 src = pseudo_to_value(fn, insn, insn->src); 778 779 pseudo_name(insn->target, target_name); 780 781 assert(!symbol_is_fp_type(insn->type)); 782 783 target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(fn->module, insn), target_name); 784 785 insn->target->priv = target; 786 } 787 788 static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op) 789 { 790 LLVMValueRef src, target; 791 char target_name[64]; 792 793 src = insn->src->priv; 794 if (!src) 795 src = pseudo_to_value(fn, insn, insn->src); 796 797 pseudo_name(insn->target, target_name); 798 799 assert(!symbol_is_fp_type(insn->type)); 800 801 if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src))) 802 target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(fn->module, insn), target_name); 803 else 804 target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(fn->module, insn), target_name); 805 806 insn->target->priv = target; 807 } 808 809 static void output_insn(struct function *fn, struct instruction *insn) 810 { 811 switch (insn->opcode) { 812 case OP_RET: 813 output_op_ret(fn, insn); 814 break; 815 case OP_BR: 816 output_op_br(fn, insn); 817 break; 818 case OP_CBR: 819 output_op_cbr(fn, insn); 820 break; 821 case OP_SYMADDR: 822 assert(0); 823 break; 824 case OP_SETVAL: 825 assert(0); 826 break; 827 case OP_SWITCH: 828 output_op_switch(fn, insn); 829 break; 830 case OP_COMPUTEDGOTO: 831 assert(0); 832 break; 833 case OP_PHISOURCE: 834 output_op_phisrc(fn, insn); 835 break; 836 case OP_PHI: 837 output_op_phi(fn, insn); 838 break; 839 case OP_LOAD: 840 output_op_load(fn, insn); 841 break; 842 case OP_LNOP: 843 assert(0); 844 break; 845 case OP_STORE: 846 output_op_store(fn, insn); 847 break; 848 case OP_SNOP: 849 assert(0); 850 break; 851 case OP_INLINED_CALL: 852 assert(0); 853 break; 854 case OP_CALL: 855 output_op_call(fn, insn); 856 break; 857 case OP_CAST: 858 output_op_cast(fn, insn, LLVMZExt); 859 break; 860 case OP_SCAST: 861 output_op_cast(fn, insn, LLVMSExt); 862 break; 863 case OP_FPCAST: 864 assert(0); 865 break; 866 case OP_PTRCAST: 867 output_op_ptrcast(fn, insn); 868 break; 869 case OP_BINARY ... OP_BINARY_END: 870 output_op_binary(fn, insn); 871 break; 872 case OP_BINCMP ... OP_BINCMP_END: 873 output_op_compare(fn, insn); 874 break; 875 case OP_SEL: 876 output_op_sel(fn, insn); 877 break; 878 case OP_SLICE: 879 assert(0); 880 break; 881 case OP_NOT: { 882 LLVMValueRef src, target; 883 char target_name[64]; 884 885 src = pseudo_to_value(fn, insn, insn->src); 886 887 pseudo_name(insn->target, target_name); 888 889 target = LLVMBuildNot(fn->builder, src, target_name); 890 891 insn->target->priv = target; 892 break; 893 } 894 case OP_NEG: 895 assert(0); 896 break; 897 case OP_CONTEXT: 898 assert(0); 899 break; 900 case OP_RANGE: 901 assert(0); 902 break; 903 case OP_NOP: 904 assert(0); 905 break; 906 case OP_DEATHNOTE: 907 break; 908 case OP_ASM: 909 assert(0); 910 break; 911 case OP_COPY: 912 assert(0); 913 break; 914 default: 915 break; 916 } 917 } 918 919 static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation) 920 { 921 struct instruction *insn; 922 923 bb->generation = generation; 924 925 FOR_EACH_PTR(bb->insns, insn) { 926 if (!insn->bb) 927 continue; 928 929 output_insn(fn, insn); 930 } 931 END_FOR_EACH_PTR(insn); 932 } 933 934 #define MAX_ARGS 64 935 936 static void output_fn(LLVMModuleRef module, struct entrypoint *ep) 937 { 938 unsigned long generation = ++bb_generation; 939 struct symbol *sym = ep->name; 940 struct symbol *base_type = sym->ctype.base_type; 941 struct symbol *ret_type = sym->ctype.base_type->ctype.base_type; 942 LLVMTypeRef arg_types[MAX_ARGS]; 943 LLVMTypeRef return_type; 944 struct function function = { .module = module }; 945 struct basic_block *bb; 946 struct symbol *arg; 947 const char *name; 948 int nr_args = 0; 949 950 FOR_EACH_PTR(base_type->arguments, arg) { 951 struct symbol *arg_base_type = arg->ctype.base_type; 952 953 arg_types[nr_args++] = symbol_type(module, arg_base_type); 954 } END_FOR_EACH_PTR(arg); 955 956 name = show_ident(sym->ident); 957 958 return_type = symbol_type(module, ret_type); 959 960 function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0); 961 962 function.fn = LLVMAddFunction(module, name, function.type); 963 LLVMSetFunctionCallConv(function.fn, LLVMCCallConv); 964 965 LLVMSetLinkage(function.fn, function_linkage(sym)); 966 967 function.builder = LLVMCreateBuilder(); 968 969 static int nr_bb; 970 971 FOR_EACH_PTR(ep->bbs, bb) { 972 if (bb->generation == generation) 973 continue; 974 975 LLVMBasicBlockRef bbr; 976 char bbname[32]; 977 struct instruction *insn; 978 979 sprintf(bbname, "L%d", nr_bb++); 980 bbr = LLVMAppendBasicBlock(function.fn, bbname); 981 982 bb->priv = bbr; 983 984 /* allocate alloca for each phi */ 985 FOR_EACH_PTR(bb->insns, insn) { 986 LLVMBasicBlockRef entrybbr; 987 LLVMTypeRef phi_type; 988 LLVMValueRef ptr; 989 990 if (!insn->bb || insn->opcode != OP_PHI) 991 continue; 992 /* insert alloca into entry block */ 993 entrybbr = LLVMGetEntryBasicBlock(function.fn); 994 LLVMPositionBuilderAtEnd(function.builder, entrybbr); 995 phi_type = insn_symbol_type(module, insn); 996 ptr = LLVMBuildAlloca(function.builder, phi_type, ""); 997 /* emit forward load for phi */ 998 LLVMClearInsertionPosition(function.builder); 999 insn->target->priv = LLVMBuildLoad(function.builder, ptr, "phi"); 1000 } END_FOR_EACH_PTR(insn); 1001 } 1002 END_FOR_EACH_PTR(bb); 1003 1004 FOR_EACH_PTR(ep->bbs, bb) { 1005 if (bb->generation == generation) 1006 continue; 1007 1008 LLVMPositionBuilderAtEnd(function.builder, bb->priv); 1009 1010 output_bb(&function, bb, generation); 1011 } 1012 END_FOR_EACH_PTR(bb); 1013 } 1014 1015 static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym) 1016 { 1017 struct expression *initializer = sym->initializer; 1018 LLVMValueRef initial_value; 1019 LLVMValueRef data; 1020 const char *name; 1021 1022 if (initializer) { 1023 switch (initializer->type) { 1024 case EXPR_VALUE: 1025 initial_value = LLVMConstInt(symbol_type(module, sym), initializer->value, 1); 1026 break; 1027 case EXPR_SYMBOL: { 1028 struct symbol *sym = initializer->symbol; 1029 1030 initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident)); 1031 if (!initial_value) 1032 initial_value = output_data(module, sym); 1033 break; 1034 } 1035 case EXPR_STRING: { 1036 const char *s = initializer->string->data; 1037 1038 initial_value = LLVMConstString(strdup(s), strlen(s) + 1, true); 1039 break; 1040 } 1041 default: 1042 assert(0); 1043 } 1044 } else { 1045 LLVMTypeRef type = symbol_type(module, sym); 1046 1047 initial_value = LLVMConstNull(type); 1048 } 1049 1050 name = show_ident(sym->ident); 1051 1052 data = LLVMAddGlobal(module, LLVMTypeOf(initial_value), name); 1053 1054 LLVMSetLinkage(data, data_linkage(sym)); 1055 if (sym->ctype.modifiers & MOD_CONST) 1056 LLVMSetGlobalConstant(data, 1); 1057 if (sym->ctype.modifiers & MOD_TLS) 1058 LLVMSetThreadLocal(data, 1); 1059 if (sym->ctype.alignment) 1060 LLVMSetAlignment(data, sym->ctype.alignment); 1061 1062 if (!(sym->ctype.modifiers & MOD_EXTERN)) 1063 LLVMSetInitializer(data, initial_value); 1064 1065 return data; 1066 } 1067 1068 static int is_prototype(struct symbol *sym) 1069 { 1070 if (sym->type == SYM_NODE) 1071 sym = sym->ctype.base_type; 1072 return sym && sym->type == SYM_FN && !sym->stmt; 1073 } 1074 1075 static int compile(LLVMModuleRef module, struct symbol_list *list) 1076 { 1077 struct symbol *sym; 1078 1079 FOR_EACH_PTR(list, sym) { 1080 struct entrypoint *ep; 1081 expand_symbol(sym); 1082 1083 if (is_prototype(sym)) 1084 continue; 1085 1086 ep = linearize_symbol(sym); 1087 if (ep) 1088 output_fn(module, ep); 1089 else 1090 output_data(module, sym); 1091 } 1092 END_FOR_EACH_PTR(sym); 1093 1094 return 0; 1095 } 1096 1097 #ifndef LLVM_DEFAULT_TARGET_TRIPLE 1098 #define LLVM_DEFAULT_TARGET_TRIPLE LLVM_HOSTTRIPLE 1099 #endif 1100 1101 #define X86_LINUX_LAYOUT \ 1102 "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \ 1103 "i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-" \ 1104 "a0:0:64-f80:32:32-n8:16:32-S128" 1105 1106 #define X86_64_LINUX_LAYOUT \ 1107 "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \ 1108 "i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-" \ 1109 "a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" 1110 1111 static void set_target(LLVMModuleRef module) 1112 { 1113 char target[] = LLVM_DEFAULT_TARGET_TRIPLE; 1114 const char *arch, *vendor, *os, *env, *layout = NULL; 1115 char triple[256]; 1116 1117 arch = strtok(target, "-"); 1118 vendor = strtok(NULL, "-"); 1119 os = strtok(NULL, "-"); 1120 env = strtok(NULL, "-"); 1121 1122 if (!os) 1123 return; 1124 if (!env) 1125 env = "unknown"; 1126 1127 if (!strcmp(arch, "x86_64") && !strcmp(os, "linux")) { 1128 if (arch_m64) { 1129 layout = X86_64_LINUX_LAYOUT; 1130 } else { 1131 arch = "i386"; 1132 layout = X86_LINUX_LAYOUT; 1133 } 1134 } 1135 1136 /* unsupported target */ 1137 if (!layout) 1138 return; 1139 1140 snprintf(triple, sizeof(triple), "%s-%s-%s-%s", arch, vendor, os, env); 1141 LLVMSetTarget(module, triple); 1142 LLVMSetDataLayout(module, layout); 1143 } 1144 1145 int main(int argc, char **argv) 1146 { 1147 struct string_list *filelist = NULL; 1148 struct symbol_list *symlist; 1149 LLVMModuleRef module; 1150 char *file; 1151 1152 symlist = sparse_initialize(argc, argv, &filelist); 1153 1154 module = LLVMModuleCreateWithName("sparse"); 1155 set_target(module); 1156 1157 compile(module, symlist); 1158 1159 /* need ->phi_users */ 1160 dbg_dead = 1; 1161 FOR_EACH_PTR_NOTAG(filelist, file) { 1162 symlist = sparse(file); 1163 if (die_if_error) 1164 return 1; 1165 compile(module, symlist); 1166 } END_FOR_EACH_PTR_NOTAG(file); 1167 1168 LLVMVerifyModule(module, LLVMPrintMessageAction, NULL); 1169 1170 LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0); 1171 1172 LLVMDisposeModule(module); 1173 1174 report_stats(); 1175 return 0; 1176 } 1177