sparse-llvm.c

   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 insn_symbol_type(LLVMModuleRef module, struct instruction *insn)
 246 {
 247         if (insn->type)
 248                 return symbol_type(module, insn->type);
 249
 250         switch (insn->size) {
 251                 case 8:         return LLVMInt8Type();
 252                 case 16:        return LLVMInt16Type();
 253                 case 32:        return LLVMInt32Type();
 254                 case 64:        return LLVMInt64Type();
 255
 256                 default:
 257                         die("invalid bit size %d", insn->size);
 258                         break;
 259         }
 260
 261         return NULL;    /* not reached */
 262 }
 263
 264 static LLVMLinkage data_linkage(struct symbol *sym)
 265 {
 266         if (sym->ctype.modifiers & MOD_STATIC)
 267                 return LLVMPrivateLinkage;
 268
 269         return LLVMExternalLinkage;
 270 }
 271
 272 static LLVMLinkage function_linkage(struct symbol *sym)
 273 {
 274         if (sym->ctype.modifiers & MOD_STATIC)
 275                 return LLVMInternalLinkage;
 276
 277         return LLVMExternalLinkage;
 278 }
 279
 280 #define MAX_PSEUDO_NAME 64
 281
 282 static void pseudo_name(pseudo_t pseudo, char *buf)
 283 {
 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;
 297         }
 298         case PSEUDO_PHI:
 299                 snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr);
 300                 break;
 301         default:
 302                 assert(0);
 303         }
 304 }
 305
 306 static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo)
 307 {
 308         LLVMValueRef result = NULL;
 309
 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;
 317
 318                 assert(sym->bb_target == NULL);
 319
 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;
 327
 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));
 332
 333                                 result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
 334                                 break;
 335                         }
 336                         case EXPR_SYMBOL: {
 337                                 struct symbol *sym = expr->symbol;
 338
 339                                 result = LLVMGetNamedGlobal(fn->module, show_ident(sym->ident));
 340                                 assert(result != NULL);
 341                                 break;
 342                         }
 343                         default:
 344                                 assert(0);
 345                         }
 346                 } else {
 347                         const char *name = show_ident(sym->ident);
 348                         LLVMTypeRef type = symbol_type(fn->module, sym);
 349
 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);
 358                         }
 359                 }
 360                 break;
 361         }
 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;
 368         }
 369         case PSEUDO_PHI:
 370                 result = pseudo->priv;
 371                 break;
 372         case PSEUDO_VOID:
 373                 result = NULL;
 374                 break;
 375         default:
 376                 assert(0);
 377         }
 378
 379         return result;
 380 }
 381
 382 static LLVMValueRef calc_gep(LLVMBuilderRef builder, LLVMValueRef base, LLVMValueRef off)
 383 {
 384         LLVMTypeRef type = LLVMTypeOf(base);
 385         unsigned int as = LLVMGetPointerAddressSpace(type);
 386         LLVMTypeRef bytep = LLVMPointerType(LLVMInt8Type(), as);
 387         LLVMValueRef addr;
 388
 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;
 396 }
 397
 398 static LLVMRealPredicate translate_fop(int opcode)
 399 {
 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,
 412         };
 413
 414         return trans_tbl[opcode];
 415 }
 416
 417 static LLVMIntPredicate translate_op(int opcode)
 418 {
 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,
 430         };
 431
 432         return trans_tbl[opcode];
 433 }
 434
 435 static void output_op_binary(struct function *fn, struct instruction *insn)
 436 {
 437         LLVMValueRef lhs, rhs, target;
 438         char target_name[64];
 439
 440         lhs = pseudo_to_value(fn, insn, insn->src1);
 441
 442         rhs = pseudo_to_value(fn, insn, insn->src2);
 443
 444         pseudo_name(insn->target, target_name);
 445
 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;
 500
 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;
 517
 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);
 521
 522                 dst_type = insn_symbol_type(fn->module, insn);
 523                 target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
 524                 break;
 525         }
 526         case OP_OR_BOOL: {
 527                 LLVMValueRef lhs_nz, rhs_nz;
 528                 LLVMTypeRef dst_type;
 529
 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);
 533
 534                 dst_type = insn_symbol_type(fn->module, insn);
 535                 target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
 536                 break;
 537         }
 538         default:
 539                 assert(0);
 540                 break;
 541         }
 542
 543         insn->target->priv = target;
 544 }
 545
 546 static void output_op_compare(struct function *fn, struct instruction *insn)
 547 {
 548         LLVMValueRef lhs, rhs, target;
 549         char target_name[64];
 550
 551         lhs = pseudo_to_value(fn, insn, insn->src1);
 552
 553         if (insn->src2->type == PSEUDO_VAL)
 554                 rhs = LLVMConstInt(LLVMTypeOf(lhs), insn->src2->value, 1);
 555         else
 556                 rhs = pseudo_to_value(fn, insn, insn->src2);
 557
 558         pseudo_name(insn->target, target_name);
 559
 560         LLVMTypeRef dst_type = insn_symbol_type(fn->module, insn);
 561
 562         if (LLVMGetTypeKind(LLVMTypeOf(lhs)) == LLVMIntegerTypeKind) {
 563                 LLVMIntPredicate op = translate_op(insn->opcode);
 564
 565                 target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name);
 566         } else {
 567                 LLVMRealPredicate op = translate_fop(insn->opcode);
 568
 569                 target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name);
 570         }
 571
 572         target = LLVMBuildZExt(fn->builder, target, dst_type, target_name);
 573
 574         insn->target->priv = target;
 575 }
 576
 577 static void output_op_ret(struct function *fn, struct instruction *insn)
 578 {
 579         pseudo_t pseudo = insn->src;
 580
 581         if (pseudo && pseudo != VOID) {
 582                 LLVMValueRef result = pseudo_to_value(fn, insn, pseudo);
 583
 584                 LLVMBuildRet(fn->builder, result);
 585         } else
 586                 LLVMBuildRetVoid(fn->builder);
 587 }
 588
 589 static LLVMValueRef calc_memop_addr(struct function *fn, struct instruction *insn)
 590 {
 591         LLVMTypeRef int_type, addr_type;
 592         LLVMValueRef src, off, addr;
 593         unsigned int as;
 594
 595         /* int type large enough to hold a pointer */
 596         int_type = LLVMIntType(bits_in_pointer);
 597         off = LLVMConstInt(int_type, insn->offset, 0);
 598
 599         /* convert src to the effective pointer type */
 600         src = pseudo_to_value(fn, insn, insn->src);
 601         as = LLVMGetPointerAddressSpace(LLVMTypeOf(src));
 602         addr_type = LLVMPointerType(insn_symbol_type(fn->module, insn), as);
 603         src = LLVMBuildPointerCast(fn->builder, src, addr_type, "");
 604
 605         /* addr = src + off */
 606         addr = calc_gep(fn->builder, src, off);
 607         return addr;
 608 }
 609
 610
 611 static void output_op_load(struct function *fn, struct instruction *insn)
 612 {
 613         LLVMValueRef addr, target;
 614
 615         addr = calc_memop_addr(fn, insn);
 616
 617         /* perform load */
 618         target = LLVMBuildLoad(fn->builder, addr, "load_target");
 619
 620         insn->target->priv = target;
 621 }
 622
 623 static void output_op_store(struct function *fn, struct instruction *insn)
 624 {
 625         LLVMValueRef addr, target, target_in;
 626
 627         addr = calc_memop_addr(fn, insn);
 628
 629         target_in = pseudo_to_value(fn, insn, insn->target);
 630
 631         /* perform store */
 632         target = LLVMBuildStore(fn->builder, target_in, addr);
 633
 634         insn->target->priv = target;
 635 }
 636
 637 static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
 638 {
 639         if (LLVMTypeOf(value) != LLVMInt1Type())
 640                 value = LLVMBuildIsNotNull(fn->builder, value, "cond");
 641
 642         return value;
 643 }
 644
 645 static void output_op_cbr(struct function *fn, struct instruction *br)
 646 {
 647         LLVMValueRef cond = bool_value(fn,
 648                         pseudo_to_value(fn, br, br->cond));
 649
 650         LLVMBuildCondBr(fn->builder, cond,
 651                         br->bb_true->priv,
 652                         br->bb_false->priv);
 653 }
 654
 655 static void output_op_br(struct function *fn, struct instruction *br)
 656 {
 657         LLVMBuildBr(fn->builder, br->bb_true->priv);
 658 }
 659
 660 static void output_op_sel(struct function *fn, struct instruction *insn)
 661 {
 662         LLVMValueRef target, src1, src2, src3;
 663
 664         src1 = bool_value(fn, pseudo_to_value(fn, insn, insn->src1));
 665         src2 = pseudo_to_value(fn, insn, insn->src2);
 666         src3 = pseudo_to_value(fn, insn, insn->src3);
 667
 668         target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select");
 669
 670         insn->target->priv = target;
 671 }
 672
 673 static void output_op_switch(struct function *fn, struct instruction *insn)
 674 {
 675         LLVMValueRef sw_val, target;
 676         struct basic_block *def = NULL;
 677         struct multijmp *jmp;
 678         int n_jmp = 0;
 679
 680         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 681                 if (jmp->begin == jmp->end) {           /* case N */
 682                         n_jmp++;
 683                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 684                         assert(0);
 685                 } else                                  /* default case */
 686                         def = jmp->target;
 687         } END_FOR_EACH_PTR(jmp);
 688
 689         sw_val = pseudo_to_value(fn, insn, insn->target);
 690         target = LLVMBuildSwitch(fn->builder, sw_val,
 691                                  def ? def->priv : NULL, n_jmp);
 692
 693         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 694                 if (jmp->begin == jmp->end) {           /* case N */
 695                         LLVMAddCase(target,
 696                                 LLVMConstInt(LLVMInt32Type(), jmp->begin, 0),
 697                                 jmp->target->priv);
 698                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 699                         assert(0);
 700                 }
 701         } END_FOR_EACH_PTR(jmp);
 702
 703         insn->target->priv = target;
 704 }
 705
 706 static void output_op_call(struct function *fn, struct instruction *insn)
 707 {
 708         LLVMValueRef target, func;
 709         int n_arg = 0, i;
 710         struct pseudo *arg;
 711         LLVMValueRef *args;
 712
 713         FOR_EACH_PTR(insn->arguments, arg) {
 714                 n_arg++;
 715         } END_FOR_EACH_PTR(arg);
 716
 717         args = calloc(n_arg, sizeof(LLVMValueRef));
 718
 719         i = 0;
 720         FOR_EACH_PTR(insn->arguments, arg) {
 721                 args[i++] = pseudo_to_value(fn, insn, arg);
 722         } END_FOR_EACH_PTR(arg);
 723
 724         func = pseudo_to_value(fn, insn, insn->func);
 725         target = LLVMBuildCall(fn->builder, func, args, n_arg, "");
 726
 727         insn->target->priv = target;
 728 }
 729
 730 static void output_op_phisrc(struct function *fn, struct instruction *insn)
 731 {
 732         LLVMValueRef v;
 733         struct instruction *phi;
 734
 735         assert(insn->target->priv == NULL);
 736
 737         /* target = src */
 738         v = pseudo_to_value(fn, insn, insn->phi_src);
 739
 740         FOR_EACH_PTR(insn->phi_users, phi) {
 741                 LLVMValueRef load, ptr;
 742
 743                 assert(phi->opcode == OP_PHI);
 744                 /* phi must be load from alloca */
 745                 load = phi->target->priv;
 746                 assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
 747                 ptr = LLVMGetOperand(load, 0);
 748                 /* store v to alloca */
 749                 LLVMBuildStore(fn->builder, v, ptr);
 750         } END_FOR_EACH_PTR(phi);
 751 }
 752
 753 static void output_op_phi(struct function *fn, struct instruction *insn)
 754 {
 755         LLVMValueRef load = insn->target->priv;
 756
 757         /* forward load */
 758         assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
 759         /* forward load has no parent block */
 760         assert(!LLVMGetInstructionParent(load));
 761         /* finalize load in current block  */
 762         LLVMInsertIntoBuilder(fn->builder, load);
 763 }
 764
 765 static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 766 {
 767         LLVMValueRef src, target;
 768         char target_name[64];
 769
 770         src = insn->src->priv;
 771         if (!src)
 772                 src = pseudo_to_value(fn, insn, insn->src);
 773
 774         pseudo_name(insn->target, target_name);
 775
 776         assert(!symbol_is_fp_type(insn->type));
 777
 778         target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
 779
 780         insn->target->priv = target;
 781 }
 782
 783 static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
 784 {
 785         LLVMValueRef src, target;
 786         char target_name[64];
 787
 788         src = insn->src->priv;
 789         if (!src)
 790                 src = pseudo_to_value(fn, insn, insn->src);
 791
 792         pseudo_name(insn->target, target_name);
 793
 794         assert(!symbol_is_fp_type(insn->type));
 795
 796         if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src)))
 797                 target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
 798         else
 799                 target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(fn->module, insn), target_name);
 800
 801         insn->target->priv = target;
 802 }
 803
 804 static void output_insn(struct function *fn, struct instruction *insn)
 805 {
 806         switch (insn->opcode) {
 807         case OP_RET:
 808                 output_op_ret(fn, insn);
 809                 break;
 810         case OP_BR:
 811                 output_op_br(fn, insn);
 812                 break;
 813         case OP_CBR:
 814                 output_op_cbr(fn, insn);
 815                 break;
 816         case OP_SYMADDR:
 817                 assert(0);
 818                 break;
 819         case OP_SETVAL:
 820                 assert(0);
 821                 break;
 822         case OP_SWITCH:
 823                 output_op_switch(fn, insn);
 824                 break;
 825         case OP_COMPUTEDGOTO:
 826                 assert(0);
 827                 break;
 828         case OP_PHISOURCE:
 829                 output_op_phisrc(fn, insn);
 830                 break;
 831         case OP_PHI:
 832                 output_op_phi(fn, insn);
 833                 break;
 834         case OP_LOAD:
 835                 output_op_load(fn, insn);
 836                 break;
 837         case OP_LNOP:
 838                 assert(0);
 839                 break;
 840         case OP_STORE:
 841                 output_op_store(fn, insn);
 842                 break;
 843         case OP_SNOP:
 844                 assert(0);
 845                 break;
 846         case OP_INLINED_CALL:
 847                 assert(0);
 848                 break;
 849         case OP_CALL:
 850                 output_op_call(fn, insn);
 851                 break;
 852         case OP_CAST:
 853                 output_op_cast(fn, insn, LLVMZExt);
 854                 break;
 855         case OP_SCAST:
 856                 output_op_cast(fn, insn, LLVMSExt);
 857                 break;
 858         case OP_FPCAST:
 859                 assert(0);
 860                 break;
 861         case OP_PTRCAST:
 862                 output_op_ptrcast(fn, insn);
 863                 break;
 864         case OP_BINARY ... OP_BINARY_END:
 865                 output_op_binary(fn, insn);
 866                 break;
 867         case OP_BINCMP ... OP_BINCMP_END:
 868                 output_op_compare(fn, insn);
 869                 break;
 870         case OP_SEL:
 871                 output_op_sel(fn, insn);
 872                 break;
 873         case OP_SLICE:
 874                 assert(0);
 875                 break;
 876         case OP_NOT: {
 877                 LLVMValueRef src, target;
 878                 char target_name[64];
 879
 880                 src = pseudo_to_value(fn, insn, insn->src);
 881
 882                 pseudo_name(insn->target, target_name);
 883
 884                 target = LLVMBuildNot(fn->builder, src, target_name);
 885
 886                 insn->target->priv = target;
 887                 break;
 888         }
 889         case OP_NEG:
 890                 assert(0);
 891                 break;
 892         case OP_CONTEXT:
 893                 assert(0);
 894                 break;
 895         case OP_RANGE:
 896                 assert(0);
 897                 break;
 898         case OP_NOP:
 899                 assert(0);
 900                 break;
 901         case OP_DEATHNOTE:
 902                 break;
 903         case OP_ASM:
 904                 assert(0);
 905                 break;
 906         case OP_COPY:
 907                 assert(0);
 908                 break;
 909         default:
 910                 break;
 911         }
 912 }
 913
 914 static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation)
 915 {
 916         struct instruction *insn;
 917
 918         bb->generation = generation;
 919
 920         FOR_EACH_PTR(bb->insns, insn) {
 921                 if (!insn->bb)
 922                         continue;
 923
 924                 output_insn(fn, insn);
 925         }
 926         END_FOR_EACH_PTR(insn);
 927 }
 928
 929 #define MAX_ARGS        64
 930
 931 static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 932 {
 933         unsigned long generation = ++bb_generation;
 934         struct symbol *sym = ep->name;
 935         struct symbol *base_type = sym->ctype.base_type;
 936         struct symbol *ret_type = sym->ctype.base_type->ctype.base_type;
 937         LLVMTypeRef arg_types[MAX_ARGS];
 938         LLVMTypeRef return_type;
 939         struct function function = { .module = module };
 940         struct basic_block *bb;
 941         struct symbol *arg;
 942         const char *name;
 943         int nr_args = 0;
 944
 945         FOR_EACH_PTR(base_type->arguments, arg) {
 946                 struct symbol *arg_base_type = arg->ctype.base_type;
 947
 948                 arg_types[nr_args++] = symbol_type(module, arg_base_type);
 949         } END_FOR_EACH_PTR(arg);
 950
 951         name = show_ident(sym->ident);
 952
 953         return_type = symbol_type(module, ret_type);
 954
 955         function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0);
 956
 957         function.fn = LLVMAddFunction(module, name, function.type);
 958         LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
 959
 960         LLVMSetLinkage(function.fn, function_linkage(sym));
 961
 962         function.builder = LLVMCreateBuilder();
 963
 964         static int nr_bb;
 965
 966         FOR_EACH_PTR(ep->bbs, bb) {
 967                 if (bb->generation == generation)
 968                         continue;
 969
 970                 LLVMBasicBlockRef bbr;
 971                 char bbname[32];
 972                 struct instruction *insn;
 973
 974                 sprintf(bbname, "L%d", nr_bb++);
 975                 bbr = LLVMAppendBasicBlock(function.fn, bbname);
 976
 977                 bb->priv = bbr;
 978
 979                 /* allocate alloca for each phi */
 980                 FOR_EACH_PTR(bb->insns, insn) {
 981                         LLVMBasicBlockRef entrybbr;
 982                         LLVMTypeRef phi_type;
 983                         LLVMValueRef ptr;
 984
 985                         if (!insn->bb || insn->opcode != OP_PHI)
 986                                 continue;
 987                         /* insert alloca into entry block */
 988                         entrybbr = LLVMGetEntryBasicBlock(function.fn);
 989                         LLVMPositionBuilderAtEnd(function.builder, entrybbr);
 990                         phi_type = insn_symbol_type(module, insn);
 991                         ptr = LLVMBuildAlloca(function.builder, phi_type, "");
 992                         /* emit forward load for phi */
 993                         LLVMClearInsertionPosition(function.builder);
 994                         insn->target->priv = LLVMBuildLoad(function.builder, ptr, "phi");
 995                 } END_FOR_EACH_PTR(insn);
 996         }
 997         END_FOR_EACH_PTR(bb);
 998
 999         FOR_EACH_PTR(ep->bbs, bb) {
1000                 if (bb->generation == generation)
1001                         continue;
1002
1003                 LLVMPositionBuilderAtEnd(function.builder, bb->priv);
1004
1005                 output_bb(&function, bb, generation);
1006         }
1007         END_FOR_EACH_PTR(bb);
1008 }
1009
1010 static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
1011 {
1012         struct expression *initializer = sym->initializer;
1013         LLVMValueRef initial_value;
1014         LLVMValueRef data;
1015         const char *name;
1016
1017         if (initializer) {
1018                 switch (initializer->type) {
1019                 case EXPR_VALUE:
1020                         initial_value = LLVMConstInt(symbol_type(module, sym), initializer->value, 1);
1021                         break;
1022                 case EXPR_SYMBOL: {
1023                         struct symbol *sym = initializer->symbol;
1024
1025                         initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident));
1026                         if (!initial_value)
1027                                 initial_value = output_data(module, sym);
1028                         break;
1029                 }
1030                 case EXPR_STRING: {
1031                         const char *s = initializer->string->data;
1032
1033                         initial_value = LLVMConstString(strdup(s), strlen(s) + 1, true);
1034                         break;
1035                 }
1036                 default:
1037                         assert(0);
1038                 }
1039         } else {
1040                 LLVMTypeRef type = symbol_type(module, sym);
1041
1042                 initial_value = LLVMConstNull(type);
1043         }
1044
1045         name = show_ident(sym->ident);
1046
1047         data = LLVMAddGlobal(module, LLVMTypeOf(initial_value), name);
1048
1049         LLVMSetLinkage(data, data_linkage(sym));
1050         if (sym->ctype.modifiers & MOD_CONST)
1051                 LLVMSetGlobalConstant(data, 1);
1052         if (sym->ctype.modifiers & MOD_TLS)
1053                 LLVMSetThreadLocal(data, 1);
1054         if (sym->ctype.alignment)
1055                 LLVMSetAlignment(data, sym->ctype.alignment);
1056
1057         if (!(sym->ctype.modifiers & MOD_EXTERN))
1058                 LLVMSetInitializer(data, initial_value);
1059
1060         return data;
1061 }
1062
1063 static int is_prototype(struct symbol *sym)
1064 {
1065         if (sym->type == SYM_NODE)
1066                 sym = sym->ctype.base_type;
1067         return sym && sym->type == SYM_FN && !sym->stmt;
1068 }
1069
1070 static int compile(LLVMModuleRef module, struct symbol_list *list)
1071 {
1072         struct symbol *sym;
1073
1074         FOR_EACH_PTR(list, sym) {
1075                 struct entrypoint *ep;
1076                 expand_symbol(sym);
1077
1078                 if (is_prototype(sym))
1079                         continue;
1080
1081                 ep = linearize_symbol(sym);
1082                 if (ep)
1083                         output_fn(module, ep);
1084                 else
1085                         output_data(module, sym);
1086         }
1087         END_FOR_EACH_PTR(sym);
1088
1089         return 0;
1090 }
1091
1092 #ifndef LLVM_DEFAULT_TARGET_TRIPLE
1093 #define LLVM_DEFAULT_TARGET_TRIPLE LLVM_HOSTTRIPLE
1094 #endif
1095
1096 #define X86_LINUX_LAYOUT \
1097         "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
1098         "i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-" \
1099         "a0:0:64-f80:32:32-n8:16:32-S128"
1100
1101 #define X86_64_LINUX_LAYOUT \
1102         "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-" \
1103         "i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-" \
1104         "a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
1105
1106 static void set_target(LLVMModuleRef module)
1107 {
1108         char target[] = LLVM_DEFAULT_TARGET_TRIPLE;
1109         const char *arch, *vendor, *os, *env, *layout = NULL;
1110         char triple[256];
1111
1112         arch = strtok(target, "-");
1113         vendor = strtok(NULL, "-");
1114         os = strtok(NULL, "-");
1115         env = strtok(NULL, "-");
1116
1117         if (!os)
1118                 return;
1119         if (!env)
1120                 env = "unknown";
1121
1122         if (!strcmp(arch, "x86_64") && !strcmp(os, "linux")) {
1123                 if (arch_m64) {
1124                         layout = X86_64_LINUX_LAYOUT;
1125                 } else {
1126                         arch = "i386";
1127                         layout = X86_LINUX_LAYOUT;
1128                 }
1129         }
1130
1131         /* unsupported target */
1132         if (!layout)
1133                 return;
1134
1135         snprintf(triple, sizeof(triple), "%s-%s-%s-%s", arch, vendor, os, env);
1136         LLVMSetTarget(module, triple);
1137         LLVMSetDataLayout(module, layout);
1138 }
1139
1140 int main(int argc, char **argv)
1141 {
1142         struct string_list *filelist = NULL;
1143         struct symbol_list *symlist;
1144         LLVMModuleRef module;
1145         char *file;
1146
1147         symlist = sparse_initialize(argc, argv, &filelist);
1148
1149         module = LLVMModuleCreateWithName("sparse");
1150         set_target(module);
1151
1152         compile(module, symlist);
1153
1154         /* need ->phi_users */
1155         dbg_dead = 1;
1156         FOR_EACH_PTR_NOTAG(filelist, file) {
1157                 symlist = sparse(file);
1158                 if (die_if_error)
1159                         return 1;
1160                 compile(module, symlist);
1161         } END_FOR_EACH_PTR_NOTAG(file);
1162
1163         LLVMVerifyModule(module, LLVMPrintMessageAction, NULL);
1164
1165         LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);
1166
1167         LLVMDisposeModule(module);
1168
1169         report_stats();
1170         return 0;
1171 }