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
  10 #include <stdbool.h>
  11 #include <stdio.h>
  12 #include <unistd.h>
  13 #include <string.h>
  14 #include <assert.h>
  15
  16 #include "symbol.h"
  17 #include "expression.h"
  18 #include "linearize.h"
  19 #include "flow.h"
  20
  21 struct function {
  22         LLVMBuilderRef                  builder;
  23         LLVMTypeRef                     type;
  24         LLVMValueRef                    fn;
  25         LLVMModuleRef                   module;
  26 };
  27
  28 static inline bool symbol_is_fp_type(struct symbol *sym)
  29 {
  30         if (!sym)
  31                 return false;
  32
  33         return sym->ctype.base_type == &fp_type;
  34 }
  35
  36 static LLVMTypeRef symbol_type(LLVMModuleRef module, struct symbol *sym);
  37
  38 static LLVMTypeRef func_return_type(LLVMModuleRef module, struct symbol *sym)
  39 {
  40         return symbol_type(module, sym->ctype.base_type);
  41 }
  42
  43 static LLVMTypeRef sym_func_type(LLVMModuleRef module, struct symbol *sym)
  44 {
  45         LLVMTypeRef *arg_type;
  46         LLVMTypeRef func_type;
  47         LLVMTypeRef ret_type;
  48         struct symbol *arg;
  49         int n_arg = 0;
  50
  51         /* to avoid strangeness with varargs [for now], we build
  52          * the function and type anew, for each call.  This
  53          * is probably wrong.  We should look up the
  54          * symbol declaration info.
  55          */
  56
  57         ret_type = func_return_type(module, sym);
  58
  59         /* count args, build argument type information */
  60         FOR_EACH_PTR(sym->arguments, arg) {
  61                 n_arg++;
  62         } END_FOR_EACH_PTR(arg);
  63
  64         arg_type = calloc(n_arg, sizeof(LLVMTypeRef));
  65
  66         int idx = 0;
  67         FOR_EACH_PTR(sym->arguments, arg) {
  68                 struct symbol *arg_sym = arg->ctype.base_type;
  69
  70                 arg_type[idx++] = symbol_type(module, arg_sym);
  71         } END_FOR_EACH_PTR(arg);
  72         func_type = LLVMFunctionType(ret_type, arg_type, n_arg,
  73                                      sym->variadic);
  74
  75         return func_type;
  76 }
  77
  78 static LLVMTypeRef sym_array_type(LLVMModuleRef module, struct symbol *sym)
  79 {
  80         LLVMTypeRef elem_type;
  81         struct symbol *base_type;
  82
  83         base_type = sym->ctype.base_type;
  84
  85         elem_type = symbol_type(module, base_type);
  86         if (!elem_type)
  87                 return NULL;
  88
  89         return LLVMArrayType(elem_type, sym->bit_size / 8);
  90 }
  91
  92 #define MAX_STRUCT_MEMBERS 64
  93
  94 static LLVMTypeRef sym_struct_type(LLVMModuleRef module, struct symbol *sym)
  95 {
  96         LLVMTypeRef elem_types[MAX_STRUCT_MEMBERS];
  97         struct symbol *member;
  98         char buffer[256];
  99         LLVMTypeRef ret;
 100         unsigned nr = 0;
 101
 102         sprintf(buffer, "%.*s", sym->ident->len, sym->ident->name);
 103
 104         ret = LLVMGetTypeByName(module, buffer);
 105         if (ret)
 106                 return ret;
 107
 108         ret = LLVMStructCreateNamed(LLVMGetGlobalContext(), buffer);
 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         switch (sym->type) {
 207         case SYM_BITFIELD:
 208         case SYM_ENUM:
 209         case SYM_NODE:
 210                 ret = symbol_type(module, sym->ctype.base_type);
 211                 break;
 212         case SYM_BASETYPE:
 213                 ret = sym_basetype_type(sym);
 214                 break;
 215         case SYM_PTR:
 216                 ret = sym_ptr_type(module, sym);
 217                 break;
 218         case SYM_UNION:
 219                 ret = sym_union_type(module, sym);
 220                 break;
 221         case SYM_STRUCT:
 222                 ret = sym_struct_type(module, sym);
 223                 break;
 224         case SYM_ARRAY:
 225                 ret = sym_array_type(module, sym);
 226                 break;
 227         case SYM_FN:
 228                 ret = sym_func_type(module, sym);
 229                 break;
 230         default:
 231                 assert(0);
 232         }
 233         return ret;
 234 }
 235
 236 static LLVMTypeRef insn_symbol_type(LLVMModuleRef module, struct instruction *insn)
 237 {
 238         if (insn->type)
 239                 return symbol_type(module, insn->type);
 240
 241         switch (insn->size) {
 242                 case 8:         return LLVMInt8Type();
 243                 case 16:        return LLVMInt16Type();
 244                 case 32:        return LLVMInt32Type();
 245                 case 64:        return LLVMInt64Type();
 246
 247                 default:
 248                         die("invalid bit size %d", insn->size);
 249                         break;
 250         }
 251
 252         return NULL;    /* not reached */
 253 }
 254
 255 static LLVMLinkage data_linkage(struct symbol *sym)
 256 {
 257         if (sym->ctype.modifiers & MOD_STATIC)
 258                 return LLVMPrivateLinkage;
 259
 260         return LLVMExternalLinkage;
 261 }
 262
 263 static LLVMLinkage function_linkage(struct symbol *sym)
 264 {
 265         if (sym->ctype.modifiers & MOD_STATIC)
 266                 return LLVMInternalLinkage;
 267
 268         return LLVMExternalLinkage;
 269 }
 270
 271 #define MAX_PSEUDO_NAME 64
 272
 273 static void pseudo_name(pseudo_t pseudo, char *buf)
 274 {
 275         switch (pseudo->type) {
 276         case PSEUDO_REG:
 277                 snprintf(buf, MAX_PSEUDO_NAME, "R%d", pseudo->nr);
 278                 break;
 279         case PSEUDO_SYM:
 280                 assert(0);
 281                 break;
 282         case PSEUDO_VAL:
 283                 assert(0);
 284                 break;
 285         case PSEUDO_ARG: {
 286                 assert(0);
 287                 break;
 288         }
 289         case PSEUDO_PHI:
 290                 snprintf(buf, MAX_PSEUDO_NAME, "PHI%d", pseudo->nr);
 291                 break;
 292         default:
 293                 assert(0);
 294         }
 295 }
 296
 297 static LLVMValueRef pseudo_to_value(struct function *fn, struct instruction *insn, pseudo_t pseudo)
 298 {
 299         LLVMValueRef result = NULL;
 300
 301         switch (pseudo->type) {
 302         case PSEUDO_REG:
 303                 result = pseudo->priv;
 304                 break;
 305         case PSEUDO_SYM: {
 306                 struct symbol *sym = pseudo->sym;
 307                 struct expression *expr;
 308
 309                 assert(sym->bb_target == NULL);
 310
 311                 expr = sym->initializer;
 312                 if (expr) {
 313                         switch (expr->type) {
 314                         case EXPR_STRING: {
 315                                 const char *s = expr->string->data;
 316                                 LLVMValueRef indices[] = { LLVMConstInt(LLVMInt64Type(), 0, 0), LLVMConstInt(LLVMInt64Type(), 0, 0) };
 317                                 LLVMValueRef data;
 318
 319                                 data = LLVMAddGlobal(fn->module, LLVMArrayType(LLVMInt8Type(), strlen(s) + 1), ".str");
 320                                 LLVMSetLinkage(data, LLVMPrivateLinkage);
 321                                 LLVMSetGlobalConstant(data, 1);
 322                                 LLVMSetInitializer(data, LLVMConstString(strdup(s), strlen(s) + 1, true));
 323
 324                                 result = LLVMConstGEP(data, indices, ARRAY_SIZE(indices));
 325                                 break;
 326                         }
 327                         case EXPR_SYMBOL: {
 328                                 struct symbol *sym = expr->symbol;
 329
 330                                 result = LLVMGetNamedGlobal(fn->module, show_ident(sym->ident));
 331                                 assert(result != NULL);
 332                                 break;
 333                         }
 334                         default:
 335                                 assert(0);
 336                         }
 337                 } else {
 338                         const char *name = show_ident(sym->ident);
 339                         LLVMTypeRef type = symbol_type(fn->module, sym);
 340
 341                         if (LLVMGetTypeKind(type) == LLVMFunctionTypeKind) {
 342                                 result = LLVMGetNamedFunction(fn->module, name);
 343                                 if (!result)
 344                                         result = LLVMAddFunction(fn->module, name, type);
 345                         } else {
 346                                 result = LLVMGetNamedGlobal(fn->module, name);
 347                                 if (!result)
 348                                         result = LLVMAddGlobal(fn->module, type, name);
 349                         }
 350                 }
 351                 break;
 352         }
 353         case PSEUDO_VAL:
 354                 result = LLVMConstInt(insn_symbol_type(fn->module, insn), pseudo->value, 1);
 355                 break;
 356         case PSEUDO_ARG: {
 357                 result = LLVMGetParam(fn->fn, pseudo->nr - 1);
 358                 break;
 359         }
 360         case PSEUDO_PHI:
 361                 result = pseudo->priv;
 362                 break;
 363         case PSEUDO_VOID:
 364                 result = NULL;
 365                 break;
 366         default:
 367                 assert(0);
 368         }
 369
 370         return result;
 371 }
 372
 373 static LLVMRealPredicate translate_fop(int opcode)
 374 {
 375         static const LLVMRealPredicate trans_tbl[] = {
 376                 [OP_SET_EQ]     = LLVMRealOEQ,
 377                 [OP_SET_NE]     = LLVMRealUNE,
 378                 [OP_SET_LE]     = LLVMRealOLE,
 379                 [OP_SET_GE]     = LLVMRealOGE,
 380                 [OP_SET_LT]     = LLVMRealOLT,
 381                 [OP_SET_GT]     = LLVMRealOGT,
 382                 /* Are these used with FP? */
 383                 [OP_SET_B]      = LLVMRealOLT,
 384                 [OP_SET_A]      = LLVMRealOGT,
 385                 [OP_SET_BE]     = LLVMRealOLE,
 386                 [OP_SET_AE]     = LLVMRealOGE,
 387         };
 388
 389         return trans_tbl[opcode];
 390 }
 391
 392 static LLVMIntPredicate translate_op(int opcode)
 393 {
 394         static const LLVMIntPredicate trans_tbl[] = {
 395                 [OP_SET_EQ]     = LLVMIntEQ,
 396                 [OP_SET_NE]     = LLVMIntNE,
 397                 [OP_SET_LE]     = LLVMIntSLE,
 398                 [OP_SET_GE]     = LLVMIntSGE,
 399                 [OP_SET_LT]     = LLVMIntSLT,
 400                 [OP_SET_GT]     = LLVMIntSGT,
 401                 [OP_SET_B]      = LLVMIntULT,
 402                 [OP_SET_A]      = LLVMIntUGT,
 403                 [OP_SET_BE]     = LLVMIntULE,
 404                 [OP_SET_AE]     = LLVMIntUGE,
 405         };
 406
 407         return trans_tbl[opcode];
 408 }
 409
 410 static void output_op_binary(struct function *fn, struct instruction *insn)
 411 {
 412         LLVMValueRef lhs, rhs, target;
 413         char target_name[64];
 414
 415         lhs = pseudo_to_value(fn, insn, insn->src1);
 416
 417         rhs = pseudo_to_value(fn, insn, insn->src2);
 418
 419         pseudo_name(insn->target, target_name);
 420
 421         switch (insn->opcode) {
 422         /* Binary */
 423         case OP_ADD:
 424                 if (symbol_is_fp_type(insn->type))
 425                         target = LLVMBuildFAdd(fn->builder, lhs, rhs, target_name);
 426                 else
 427                         target = LLVMBuildAdd(fn->builder, lhs, rhs, target_name);
 428                 break;
 429         case OP_SUB:
 430                 if (symbol_is_fp_type(insn->type))
 431                         target = LLVMBuildFSub(fn->builder, lhs, rhs, target_name);
 432                 else
 433                         target = LLVMBuildSub(fn->builder, lhs, rhs, target_name);
 434                 break;
 435         case OP_MULU:
 436                 if (symbol_is_fp_type(insn->type))
 437                         target = LLVMBuildFMul(fn->builder, lhs, rhs, target_name);
 438                 else
 439                         target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
 440                 break;
 441         case OP_MULS:
 442                 assert(!symbol_is_fp_type(insn->type));
 443                 target = LLVMBuildMul(fn->builder, lhs, rhs, target_name);
 444                 break;
 445         case OP_DIVU:
 446                 if (symbol_is_fp_type(insn->type))
 447                         target = LLVMBuildFDiv(fn->builder, lhs, rhs, target_name);
 448                 else
 449                         target = LLVMBuildUDiv(fn->builder, lhs, rhs, target_name);
 450                 break;
 451         case OP_DIVS:
 452                 assert(!symbol_is_fp_type(insn->type));
 453                 target = LLVMBuildSDiv(fn->builder, lhs, rhs, target_name);
 454                 break;
 455         case OP_MODU:
 456                 assert(!symbol_is_fp_type(insn->type));
 457                 target = LLVMBuildURem(fn->builder, lhs, rhs, target_name);
 458                 break;
 459         case OP_MODS:
 460                 assert(!symbol_is_fp_type(insn->type));
 461                 target = LLVMBuildSRem(fn->builder, lhs, rhs, target_name);
 462                 break;
 463         case OP_SHL:
 464                 assert(!symbol_is_fp_type(insn->type));
 465                 target = LLVMBuildShl(fn->builder, lhs, rhs, target_name);
 466                 break;
 467         case OP_LSR:
 468                 assert(!symbol_is_fp_type(insn->type));
 469                 target = LLVMBuildLShr(fn->builder, lhs, rhs, target_name);
 470                 break;
 471         case OP_ASR:
 472                 assert(!symbol_is_fp_type(insn->type));
 473                 target = LLVMBuildAShr(fn->builder, lhs, rhs, target_name);
 474                 break;
 475
 476         /* Logical */
 477         case OP_AND:
 478                 assert(!symbol_is_fp_type(insn->type));
 479                 target = LLVMBuildAnd(fn->builder, lhs, rhs, target_name);
 480                 break;
 481         case OP_OR:
 482                 assert(!symbol_is_fp_type(insn->type));
 483                 target = LLVMBuildOr(fn->builder, lhs, rhs, target_name);
 484                 break;
 485         case OP_XOR:
 486                 assert(!symbol_is_fp_type(insn->type));
 487                 target = LLVMBuildXor(fn->builder, lhs, rhs, target_name);
 488                 break;
 489         case OP_AND_BOOL: {
 490                 LLVMValueRef x, y;
 491
 492                 assert(!symbol_is_fp_type(insn->type));
 493
 494                 y = LLVMBuildICmp(fn->builder, LLVMIntNE, lhs, LLVMConstInt(LLVMTypeOf(lhs), 0, 0), "y");
 495                 x = LLVMBuildICmp(fn->builder, LLVMIntNE, rhs, LLVMConstInt(LLVMTypeOf(rhs), 0, 0), "x");
 496
 497                 target = LLVMBuildAnd(fn->builder, y, x, target_name);
 498                 break;
 499         }
 500         case OP_OR_BOOL: {
 501                 LLVMValueRef tmp;
 502
 503                 assert(!symbol_is_fp_type(insn->type));
 504
 505                 tmp = LLVMBuildOr(fn->builder, rhs, lhs, "tmp");
 506
 507                 target = LLVMBuildICmp(fn->builder, LLVMIntNE, tmp, LLVMConstInt(LLVMTypeOf(tmp), 0, 0), target_name);
 508                 break;
 509         }
 510
 511         /* Binary comparison */
 512         case OP_BINCMP ... OP_BINCMP_END: {
 513                 if (LLVMGetTypeKind(LLVMTypeOf(lhs)) == LLVMIntegerTypeKind) {
 514                         LLVMIntPredicate op = translate_op(insn->opcode);
 515
 516                         target = LLVMBuildICmp(fn->builder, op, lhs, rhs, target_name);
 517                 } else {
 518                         LLVMRealPredicate op = translate_fop(insn->opcode);
 519
 520                         target = LLVMBuildFCmp(fn->builder, op, lhs, rhs, target_name);
 521                 }
 522                 break;
 523         }
 524         default:
 525                 assert(0);
 526                 break;
 527         }
 528
 529         insn->target->priv = target;
 530 }
 531
 532 static void output_op_ret(struct function *fn, struct instruction *insn)
 533 {
 534         pseudo_t pseudo = insn->src;
 535
 536         if (pseudo && pseudo != VOID) {
 537                 LLVMValueRef result = pseudo_to_value(fn, insn, pseudo);
 538
 539                 LLVMBuildRet(fn->builder, result);
 540         } else
 541                 LLVMBuildRetVoid(fn->builder);
 542 }
 543
 544 static void output_op_load(struct function *fn, struct instruction *insn)
 545 {
 546         LLVMTypeRef int_type;
 547         LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target;
 548
 549         /* int type large enough to hold a pointer */
 550         int_type = LLVMIntType(bits_in_pointer);
 551
 552         /* convert to integer, add src + offset */
 553         src_p = pseudo_to_value(fn, insn, insn->src);
 554         src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i");
 555
 556         ofs_i = LLVMConstInt(int_type, insn->offset, 0);
 557         addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i");
 558
 559         /* convert address back to pointer */
 560         addr = LLVMBuildIntToPtr(fn->builder, addr_i,
 561                                  LLVMTypeOf(src_p), "addr");
 562
 563         /* perform load */
 564         target = LLVMBuildLoad(fn->builder, addr, "load_target");
 565
 566         insn->target->priv = target;
 567 }
 568
 569 static void output_op_store(struct function *fn, struct instruction *insn)
 570 {
 571         LLVMTypeRef int_type;
 572         LLVMValueRef src_p, src_i, ofs_i, addr_i, addr, target, target_in;
 573
 574         /* int type large enough to hold a pointer */
 575         int_type = LLVMIntType(bits_in_pointer);
 576
 577         /* convert to integer, add src + offset */
 578         src_p = pseudo_to_value(fn, insn, insn->src);
 579         src_i = LLVMBuildPtrToInt(fn->builder, src_p, int_type, "src_i");
 580
 581         ofs_i = LLVMConstInt(int_type, insn->offset, 0);
 582         addr_i = LLVMBuildAdd(fn->builder, src_i, ofs_i, "addr_i");
 583
 584         /* convert address back to pointer */
 585         addr = LLVMBuildIntToPtr(fn->builder, addr_i,
 586                                  LLVMPointerType(int_type, 0), "addr");
 587
 588         target_in = pseudo_to_value(fn, insn, insn->target);
 589
 590         /* perform store */
 591         target = LLVMBuildStore(fn->builder, target_in, addr);
 592
 593         insn->target->priv = target;
 594 }
 595
 596 static LLVMValueRef bool_value(struct function *fn, LLVMValueRef value)
 597 {
 598         if (LLVMTypeOf(value) != LLVMInt1Type())
 599                 value = LLVMBuildIsNotNull(fn->builder, value, "cond");
 600
 601         return value;
 602 }
 603
 604 static void output_op_br(struct function *fn, struct instruction *br)
 605 {
 606         if (br->cond) {
 607                 LLVMValueRef cond = bool_value(fn,
 608                                 pseudo_to_value(fn, br, br->cond));
 609
 610                 LLVMBuildCondBr(fn->builder, cond,
 611                                 br->bb_true->priv,
 612                                 br->bb_false->priv);
 613         } else
 614                 LLVMBuildBr(fn->builder,
 615                             br->bb_true ? br->bb_true->priv :
 616                             br->bb_false->priv);
 617 }
 618
 619 static void output_op_sel(struct function *fn, struct instruction *insn)
 620 {
 621         LLVMValueRef target, src1, src2, src3;
 622
 623         src1 = bool_value(fn, pseudo_to_value(fn, insn, insn->src1));
 624         src2 = pseudo_to_value(fn, insn, insn->src2);
 625         src3 = pseudo_to_value(fn, insn, insn->src3);
 626
 627         target = LLVMBuildSelect(fn->builder, src1, src2, src3, "select");
 628
 629         insn->target->priv = target;
 630 }
 631
 632 static void output_op_switch(struct function *fn, struct instruction *insn)
 633 {
 634         LLVMValueRef sw_val, target;
 635         struct basic_block *def = NULL;
 636         struct multijmp *jmp;
 637         int n_jmp = 0;
 638
 639         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 640                 if (jmp->begin == jmp->end) {           /* case N */
 641                         n_jmp++;
 642                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 643                         assert(0);
 644                 } else                                  /* default case */
 645                         def = jmp->target;
 646         } END_FOR_EACH_PTR(jmp);
 647
 648         sw_val = pseudo_to_value(fn, insn, insn->target);
 649         target = LLVMBuildSwitch(fn->builder, sw_val,
 650                                  def ? def->priv : NULL, n_jmp);
 651
 652         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 653                 if (jmp->begin == jmp->end) {           /* case N */
 654                         LLVMAddCase(target,
 655                                 LLVMConstInt(LLVMInt32Type(), jmp->begin, 0),
 656                                 jmp->target->priv);
 657                 } else if (jmp->begin < jmp->end) {     /* case M..N */
 658                         assert(0);
 659                 }
 660         } END_FOR_EACH_PTR(jmp);
 661
 662         insn->target->priv = target;
 663 }
 664
 665 static void output_op_call(struct function *fn, struct instruction *insn)
 666 {
 667         LLVMValueRef target, func;
 668         int n_arg = 0, i;
 669         struct pseudo *arg;
 670         LLVMValueRef *args;
 671
 672         FOR_EACH_PTR(insn->arguments, arg) {
 673                 n_arg++;
 674         } END_FOR_EACH_PTR(arg);
 675
 676         args = calloc(n_arg, sizeof(LLVMValueRef));
 677
 678         i = 0;
 679         FOR_EACH_PTR(insn->arguments, arg) {
 680                 args[i++] = pseudo_to_value(fn, insn, arg);
 681         } END_FOR_EACH_PTR(arg);
 682
 683         func = pseudo_to_value(fn, insn, insn->func);
 684         target = LLVMBuildCall(fn->builder, func, args, n_arg, "");
 685
 686         insn->target->priv = target;
 687 }
 688
 689 static void output_op_phisrc(struct function *fn, struct instruction *insn)
 690 {
 691         LLVMValueRef v;
 692         struct instruction *phi;
 693
 694         assert(insn->target->priv == NULL);
 695
 696         /* target = src */
 697         v = pseudo_to_value(fn, insn, insn->phi_src);
 698
 699         FOR_EACH_PTR(insn->phi_users, phi) {
 700                 LLVMValueRef load, ptr;
 701
 702                 assert(phi->opcode == OP_PHI);
 703                 /* phi must be load from alloca */
 704                 load = phi->target->priv;
 705                 assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
 706                 ptr = LLVMGetOperand(load, 0);
 707                 /* store v to alloca */
 708                 LLVMBuildStore(fn->builder, v, ptr);
 709         } END_FOR_EACH_PTR(phi);
 710 }
 711
 712 static void output_op_phi(struct function *fn, struct instruction *insn)
 713 {
 714         LLVMValueRef load = insn->target->priv;
 715
 716         /* forward load */
 717         assert(LLVMGetInstructionOpcode(load) == LLVMLoad);
 718         /* forward load has no parent block */
 719         assert(!LLVMGetInstructionParent(load));
 720         /* finalize load in current block  */
 721         LLVMInsertIntoBuilder(fn->builder, load);
 722 }
 723
 724 static void output_op_ptrcast(struct function *fn, struct instruction *insn)
 725 {
 726         LLVMValueRef src, target;
 727         char target_name[64];
 728
 729         src = insn->src->priv;
 730         if (!src)
 731                 src = pseudo_to_value(fn, insn, insn->src);
 732
 733         pseudo_name(insn->target, target_name);
 734
 735         assert(!symbol_is_fp_type(insn->type));
 736
 737         target = LLVMBuildBitCast(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
 738
 739         insn->target->priv = target;
 740 }
 741
 742 static void output_op_cast(struct function *fn, struct instruction *insn, LLVMOpcode op)
 743 {
 744         LLVMValueRef src, target;
 745         char target_name[64];
 746
 747         src = insn->src->priv;
 748         if (!src)
 749                 src = pseudo_to_value(fn, insn, insn->src);
 750
 751         pseudo_name(insn->target, target_name);
 752
 753         assert(!symbol_is_fp_type(insn->type));
 754
 755         if (insn->size < LLVMGetIntTypeWidth(LLVMTypeOf(src)))
 756                 target = LLVMBuildTrunc(fn->builder, src, insn_symbol_type(fn->module, insn), target_name);
 757         else
 758                 target = LLVMBuildCast(fn->builder, op, src, insn_symbol_type(fn->module, insn), target_name);
 759
 760         insn->target->priv = target;
 761 }
 762
 763 static void output_op_copy(struct function *fn, struct instruction *insn,
 764                            pseudo_t pseudo)
 765 {
 766         LLVMValueRef src, target;
 767         LLVMTypeRef const_type;
 768         char target_name[64];
 769
 770         pseudo_name(insn->target, target_name);
 771         src = pseudo_to_value(fn, insn, pseudo);
 772         const_type = insn_symbol_type(fn->module, insn);
 773
 774         /*
 775          * This is nothing more than 'target = src'
 776          *
 777          * TODO: find a better way to provide an identity function,
 778          * than using "X + 0" simply to produce a new LLVM pseudo
 779          */
 780
 781         if (symbol_is_fp_type(insn->type))
 782                 target = LLVMBuildFAdd(fn->builder, src,
 783                         LLVMConstReal(const_type, 0.0), target_name);
 784         else
 785                 target = LLVMBuildAdd(fn->builder, src,
 786                         LLVMConstInt(const_type, 0, 0), target_name);
 787
 788         insn->target->priv = target;
 789 }
 790
 791 static void output_insn(struct function *fn, struct instruction *insn)
 792 {
 793         switch (insn->opcode) {
 794         case OP_RET:
 795                 output_op_ret(fn, insn);
 796                 break;
 797         case OP_BR:
 798                 output_op_br(fn, insn);
 799                 break;
 800         case OP_SYMADDR:
 801                 assert(0);
 802                 break;
 803         case OP_SETVAL:
 804                 assert(0);
 805                 break;
 806         case OP_SWITCH:
 807                 output_op_switch(fn, insn);
 808                 break;
 809         case OP_COMPUTEDGOTO:
 810                 assert(0);
 811                 break;
 812         case OP_PHISOURCE:
 813                 output_op_phisrc(fn, insn);
 814                 break;
 815         case OP_PHI:
 816                 output_op_phi(fn, insn);
 817                 break;
 818         case OP_LOAD:
 819                 output_op_load(fn, insn);
 820                 break;
 821         case OP_LNOP:
 822                 assert(0);
 823                 break;
 824         case OP_STORE:
 825                 output_op_store(fn, insn);
 826                 break;
 827         case OP_SNOP:
 828                 assert(0);
 829                 break;
 830         case OP_INLINED_CALL:
 831                 assert(0);
 832                 break;
 833         case OP_CALL:
 834                 output_op_call(fn, insn);
 835                 break;
 836         case OP_CAST:
 837                 output_op_cast(fn, insn, LLVMZExt);
 838                 break;
 839         case OP_SCAST:
 840                 output_op_cast(fn, insn, LLVMSExt);
 841                 break;
 842         case OP_FPCAST:
 843                 assert(0);
 844                 break;
 845         case OP_PTRCAST:
 846                 output_op_ptrcast(fn, insn);
 847                 break;
 848         case OP_BINARY ... OP_BINARY_END:
 849         case OP_BINCMP ... OP_BINCMP_END:
 850                 output_op_binary(fn, insn);
 851                 break;
 852         case OP_SEL:
 853                 output_op_sel(fn, insn);
 854                 break;
 855         case OP_SLICE:
 856                 assert(0);
 857                 break;
 858         case OP_NOT: {
 859                 LLVMValueRef src, target;
 860                 char target_name[64];
 861
 862                 src = pseudo_to_value(fn, insn, insn->src);
 863
 864                 pseudo_name(insn->target, target_name);
 865
 866                 target = LLVMBuildNot(fn->builder, src, target_name);
 867
 868                 insn->target->priv = target;
 869                 break;
 870         }
 871         case OP_NEG:
 872                 assert(0);
 873                 break;
 874         case OP_CONTEXT:
 875                 assert(0);
 876                 break;
 877         case OP_RANGE:
 878                 assert(0);
 879                 break;
 880         case OP_NOP:
 881                 assert(0);
 882                 break;
 883         case OP_DEATHNOTE:
 884                 break;
 885         case OP_ASM:
 886                 assert(0);
 887                 break;
 888         case OP_COPY:
 889                 output_op_copy(fn, insn, insn->src);
 890                 break;
 891         default:
 892                 break;
 893         }
 894 }
 895
 896 static void output_bb(struct function *fn, struct basic_block *bb, unsigned long generation)
 897 {
 898         struct instruction *insn;
 899
 900         bb->generation = generation;
 901
 902         FOR_EACH_PTR(bb->insns, insn) {
 903                 if (!insn->bb)
 904                         continue;
 905
 906                 output_insn(fn, insn);
 907         }
 908         END_FOR_EACH_PTR(insn);
 909 }
 910
 911 #define MAX_ARGS        64
 912
 913 static void output_fn(LLVMModuleRef module, struct entrypoint *ep)
 914 {
 915         unsigned long generation = ++bb_generation;
 916         struct symbol *sym = ep->name;
 917         struct symbol *base_type = sym->ctype.base_type;
 918         struct symbol *ret_type = sym->ctype.base_type->ctype.base_type;
 919         LLVMTypeRef arg_types[MAX_ARGS];
 920         LLVMTypeRef return_type;
 921         struct function function = { .module = module };
 922         struct basic_block *bb;
 923         struct symbol *arg;
 924         const char *name;
 925         int nr_args = 0;
 926
 927         FOR_EACH_PTR(base_type->arguments, arg) {
 928                 struct symbol *arg_base_type = arg->ctype.base_type;
 929
 930                 arg_types[nr_args++] = symbol_type(module, arg_base_type);
 931         } END_FOR_EACH_PTR(arg);
 932
 933         name = show_ident(sym->ident);
 934
 935         return_type = symbol_type(module, ret_type);
 936
 937         function.type = LLVMFunctionType(return_type, arg_types, nr_args, 0);
 938
 939         function.fn = LLVMAddFunction(module, name, function.type);
 940         LLVMSetFunctionCallConv(function.fn, LLVMCCallConv);
 941
 942         LLVMSetLinkage(function.fn, function_linkage(sym));
 943
 944         function.builder = LLVMCreateBuilder();
 945
 946         static int nr_bb;
 947
 948         FOR_EACH_PTR(ep->bbs, bb) {
 949                 if (bb->generation == generation)
 950                         continue;
 951
 952                 LLVMBasicBlockRef bbr;
 953                 char bbname[32];
 954                 struct instruction *insn;
 955
 956                 sprintf(bbname, "L%d", nr_bb++);
 957                 bbr = LLVMAppendBasicBlock(function.fn, bbname);
 958
 959                 bb->priv = bbr;
 960
 961                 /* allocate alloca for each phi */
 962                 FOR_EACH_PTR(bb->insns, insn) {
 963                         LLVMBasicBlockRef entrybbr;
 964                         LLVMTypeRef phi_type;
 965                         LLVMValueRef ptr;
 966
 967                         if (!insn->bb || insn->opcode != OP_PHI)
 968                                 continue;
 969                         /* insert alloca into entry block */
 970                         entrybbr = LLVMGetEntryBasicBlock(function.fn);
 971                         LLVMPositionBuilderAtEnd(function.builder, entrybbr);
 972                         phi_type = insn_symbol_type(module, insn);
 973                         ptr = LLVMBuildAlloca(function.builder, phi_type, "");
 974                         /* emit forward load for phi */
 975                         LLVMClearInsertionPosition(function.builder);
 976                         insn->target->priv = LLVMBuildLoad(function.builder, ptr, "phi");
 977                 } END_FOR_EACH_PTR(insn);
 978         }
 979         END_FOR_EACH_PTR(bb);
 980
 981         FOR_EACH_PTR(ep->bbs, bb) {
 982                 if (bb->generation == generation)
 983                         continue;
 984
 985                 LLVMPositionBuilderAtEnd(function.builder, bb->priv);
 986
 987                 output_bb(&function, bb, generation);
 988         }
 989         END_FOR_EACH_PTR(bb);
 990 }
 991
 992 static LLVMValueRef output_data(LLVMModuleRef module, struct symbol *sym)
 993 {
 994         struct expression *initializer = sym->initializer;
 995         LLVMValueRef initial_value;
 996         LLVMValueRef data;
 997         const char *name;
 998
 999         if (initializer) {
1000                 switch (initializer->type) {
1001                 case EXPR_VALUE:
1002                         initial_value = LLVMConstInt(symbol_type(module, sym), initializer->value, 1);
1003                         break;
1004                 case EXPR_SYMBOL: {
1005                         struct symbol *sym = initializer->symbol;
1006
1007                         initial_value = LLVMGetNamedGlobal(module, show_ident(sym->ident));
1008                         if (!initial_value)
1009                                 initial_value = output_data(module, sym);
1010                         break;
1011                 }
1012                 case EXPR_STRING: {
1013                         const char *s = initializer->string->data;
1014
1015                         initial_value = LLVMConstString(strdup(s), strlen(s) + 1, true);
1016                         break;
1017                 }
1018                 default:
1019                         assert(0);
1020                 }
1021         } else {
1022                 LLVMTypeRef type = symbol_type(module, sym);
1023
1024                 initial_value = LLVMConstNull(type);
1025         }
1026
1027         name = show_ident(sym->ident);
1028
1029         data = LLVMAddGlobal(module, LLVMTypeOf(initial_value), name);
1030
1031         LLVMSetLinkage(data, data_linkage(sym));
1032
1033         if (!(sym->ctype.modifiers & MOD_EXTERN))
1034                 LLVMSetInitializer(data, initial_value);
1035
1036         return data;
1037 }
1038
1039 static int compile(LLVMModuleRef module, struct symbol_list *list)
1040 {
1041         struct symbol *sym;
1042
1043         FOR_EACH_PTR(list, sym) {
1044                 struct entrypoint *ep;
1045                 expand_symbol(sym);
1046                 ep = linearize_symbol(sym);
1047                 if (ep)
1048                         output_fn(module, ep);
1049                 else
1050                         output_data(module, sym);
1051         }
1052         END_FOR_EACH_PTR(sym);
1053
1054         return 0;
1055 }
1056
1057 int main(int argc, char **argv)
1058 {
1059         struct string_list * filelist = NULL;
1060         char *file;
1061
1062         LLVMModuleRef module = LLVMModuleCreateWithName("sparse");
1063
1064         compile(module, sparse_initialize(argc, argv, &filelist));
1065
1066         /* need ->phi_users */
1067         dbg_dead = 1;
1068         FOR_EACH_PTR_NOTAG(filelist, file) {
1069                 compile(module, sparse(file));
1070         } END_FOR_EACH_PTR_NOTAG(file);
1071
1072         LLVMVerifyModule(module, LLVMPrintMessageAction, NULL);
1073
1074         LLVMWriteBitcodeToFD(module, STDOUT_FILENO, 0, 0);
1075
1076         LLVMDisposeModule(module);
1077
1078         return 0;
1079 }